Rank aggregation is part of many fields
- (Computational) Social Choice theory
    - ad hoc methods
        - elimination:
            - Bordas method of Marks
            -Concorcet method
        - non-elimination:
            - Runoff from top
            - Runoff from bottom
            - American system
            - Pairwise majority rule
    - Axiomatic (measure of distance of the desired consensus from the individual voter responses)
        - Branch-and-bound
- Statistics
    - badness-of-fit functions:
        - Principal component analysis
        - Multidimensional scaling
        - Unfolding methods
        - Preference mapping methods
    - probabilistic methods
        - under assumption of homogeneous judges
            - distance based models (Mallows)
            - multi-stage models
            - Thurstonian
        - under assumption of heterogeneous judges
            - Bradley-Terry-Luce
            - mixtures of distance based
            - clustering techniques
There are various problems within the field of rank aggregation:
- Social Choice: Finding a single collective ranking
- Finding personalized rankings
- Finding top K (with special case being the top 1 winner selection)
- Clustering within individual rankings
- Inferencing / completing ranks
Models
- Paramatric - A parametric model is defined by a strictly increasing and continuous function O.
    - Badley-Terry-Luce (O is the sigmoid function)
    - Thurstone (O is the Gaussian CDF)
- Kendall tau distance: equal to the total number of steps to migrate from the first to the second ranking by reversing adjacent pairs of objects
- Kemeny (Kendall + ties): counts the number of interchanges of couples of elements that are required to transform one (partial) ranking into another
- Spearman
- Multinomial Logit
- Condorcet (A candidate x is said to beat candidate y in a pairwise election (comparison) if the majority of voters prefer x to y, i.e., rank x above y. A candidate that beats every other candidate in a pairwise election is the winner of the entire election)
    - Simpson's rule
    - Copeland's method (For each candidate x,the Copeland score of x is the number of candidates y such that x >majority y. The candidate with the highest Copeland score is the winner of the election)
    - Dodgson's rule (For each candidate x, the Dodgson score of x is the smallest number of sequential exchanges of adjacent candidates in the preference profile needed to make x a Condorcet winner)
    - Young's method
Algorithm - rank aggregation with ties
- Ailon 3/2
- BioConsert (top all-rounder. Alternatives are mostly for extreme situations)
- BnB
- BordaCount (great when short run-time matters when few ties are involved)
  • The Borda count satisfies the monotonicity criterion, the consistency criterion, the participation criterion, the resolvability criterion, the plurality criterion (trivially), reversal symmetry, and the Condorcet loser criterion
  • The Borda count does not satisfy the Condorcet criterion, the independence of irrelevant alternatives criterion, the independence of clones criterion, the later-no-harm criterion, or the majority criterion.
  • - Chanas
    - ChanasBoth
    - CopelandMethod
    - FaginDyn
    - ILP
    - KwikSort (best quality results for extremely large datasets (also being positively influenced by similarity of datasets)
    - MC4
    - MEDRank (excellent candidate when short run-time matters and many ties are involved)
    - Pick-a-Perm
    - RepeatChoice
    Algorithms - Top K
    - Spectral MLE
    - PageRank
    - Rank Centrality
    Smith set is the smallest non-empty set of candidates in a particular election such that each member of this set beats every other candidate outside the set in a pairwise comparison. The edge compression algorithm works as follows. Starting from the whole set of candidates C, we compute a Smith set, and append it to the list of clusters. Then we reapply the same procedure iteratively on the remaining majority graph until no candidate remains. We end up with a sequence of clusters formed by the successively computed Smith sets.
    Floyd-Warshall algorithm