Rank Aggregation.pdf

This method modifies RankCentrality for rank aggregation to account for few comparisons and incorporates additional feature information.
Key aspects include:
- Modifying RankCentrality to return meaningful rankings under scarce comparisons.
- Incorporating feature information using diffusion-based methods, outperforming state-of-the-art methods in practice.
- Providing improved sample complexity for RankCentrality in various sampling schemes.
The Bradley-Terry-Luce (BTL) model is used, assuming a positive score for each item, with the probability of one item being preferred over another based on these scores.
Two main contributions are made:
1. Algorithm 1, Regularized RankCentrality, which returns meaningful rankings even under scarcity and incorporates feature information.
2. An improved sample complexity bound for the RankCentrality algorithm, such as from O(n5 log n) to O(n log n) when pairs are sampled uniformly.
Related works include literature on ranking from pairwise comparisons under various models, such as parametric and non-parametric settings, and other estimators like the Borda count and Condorcet winner.
Spectral methods, including the RankCentrality algorithm, are discussed, assuming access to a collection of independent and identically distributed pairwise comparisons.
The BTL model and its variants, such as the constrained MLE and regularized MLE, are reviewed, with known results on the BTL-MLE, including minimax optimality for the ℓ2 error and recovery of a ranking.