# Optimal Full Ranking from Pairwise Comparisons

arXiv: https://arxiv.org/abs/2101.08421 · HTML: https://mlsanity.com/paper/2101.08421/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 50 references that are in the map.
- First posted on arXiv 21 Jan 2021.

## Builds on (most cited first, 12 of 12)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Top-K Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal](https://mlsanity.com/paper/1603.04153/) (2016)
- [Competitive analysis of the top-K ranking problem](https://mlsanity.com/paper/1605.03933/) (2016)
- [Linear Regression with an Unknown Permutation: Statistical and Computational Limits](https://mlsanity.com/paper/1608.02902/) (2016)

## Built on by (most cited first, 16 of 16)

- [Uncertainty quantification in the Bradley-Terry-Luce model](https://mlsanity.com/paper/2110.03874/) (2021)
- [Efficient LLM Comparative Assessment: a Product of Experts Framework for Pairwise Comparisons](https://mlsanity.com/paper/2405.05894/) (2024)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [Sequential Manipulation Against Rank Aggregation: Theory and Algorithm](https://mlsanity.com/paper/2407.01916/) (2024)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Statistical inference for pairwise comparison models](https://mlsanity.com/paper/2401.08463/) (2024)
- [Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective](https://mlsanity.com/paper/2501.18282/) (2025)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [Rate-Optimal Rank Aggregation with Private Pairwise Rankings](https://mlsanity.com/paper/2402.16792/) (2024)
- [Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2412.16181/) (2024)
- [Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model](https://mlsanity.com/paper/2607.22221/) (2026)
- [Distribution-informed Efficient Conformal Prediction for Full Ranking](https://mlsanity.com/paper/2601.23128/) (2026)
- [Privacy utility trade offs for parameter estimation in degree heterogeneous higher order networks](https://mlsanity.com/paper/2602.03948/) (2026)
- [Population-Level Generative Modeling for Ranking Data](https://mlsanity.com/paper/2608.08422/) (2026)

## Abstract (arXiv)

We consider the problem of ranking n players from partial pairwise comparison data under the Bradley-Terry-Luce model. For the first time in the literature, the minimax rate of this ranking problem is derived with respect to the Kendall's tau distance that measures the difference between two rank vectors by counting the number of inversions. The minimax rate of ranking exhibits a transition between an exponential rate and a polynomial rate depending on the magnitude of the signal-to-noise ratio of the problem. To the best of our knowledge, this phenomenon is unique to full ranking and has not been seen in any other statistical estimation problem. To achieve the minimax rate, we propose a divide-and-conquer ranking algorithm that first divides the n players into groups of similar skills and then computes local MLE within each group. The optimality of the proposed algorithm is established by a careful approximate independence argument between the two steps.