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 criterionThe 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