mlsanityData to 7 Oct 2026

Optimal Full Ranking from Pairwise Comparisons

arXiv 2101.08421 ↗First posted 21 Jan 2021math.ST stat.ML stat.THcited by 16

Not on the map. Why?

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.

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

Builds on

12 of 50 references.

References · 12

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2013Consistency of spectral clustering in stochastic block modelscited by 128
  3. 2015Simple, Robust and Optimal Ranking from Pairwise Comparisonscited by 68
  4. 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 46
  5. 2015Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisonscited by 34
  6. 2015Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issuescited by 32
  7. 2019Iterative Algorithm for Discrete Structure Recoverycited by 21
  8. 2017Minimax Rates and Efficient Algorithms for Noisy Sortingcited by 15
  9. 2013Minimax rates in permutation estimation for feature matchingcited by 13
  10. 2016Top-K Ranking from Pairwise Comparisons: When Spectral Ranking is Optimalcited by 9
  11. 2016Competitive analysis of the top-K ranking problemcited by 6
  12. 2016Linear Regression with an Unknown Permutation: Statistical and Computational Limitscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 3; 2024: 5; 2025: 1; 2026: 4.

16 papers.

Sort:

By area:

  1. 2021Uncertainty quantification in the Bradley-Terry-Luce modelcited by 28
  2. 2024Efficient LLM Comparative Assessment: a Product of Experts Framework for Pairwise Comparisonscited by 22
  3. 2021Lagrangian Inference for Ranking Problemscited by 19
  4. 2022Uncertainty Quantification of MLE for Entity Ranking with Covariatescited by 16
  5. 2024Sequential Manipulation Against Rank Aggregation: Theory and Algorithmcited by 7
  6. 2023Ranking from Pairwise Comparisons in General Graphs and Graphs with Localitycited by 3
  7. 2023Improved theoretical guarantee for rank aggregation via spectral methodcited by 2
  8. 2024Statistical inference for pairwise comparison modelscited by 2
  9. 2025Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspectivecited by 2
  10. 2023Sharp analysis of EM for learning mixtures of pairwise differencescited by 1
  11. 2024Rate-Optimal Rank Aggregation with Private Pairwise Rankingscited by 1
  12. 2024Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisonscited by 1
4 more
  1. 2026Distribution-informed Efficient Conformal Prediction for Full Rankingcited by 0
  2. 2026Privacy utility trade offs for parameter estimation in degree heterogeneous higher order networkscited by 0
  3. 2026Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry modelcited by 0
  4. 2026Population-Level Generative Modeling for Ranking Datacited by 0