# Top-K Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2016.

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

- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem](https://mlsanity.com/paper/2310.02016/) (2023)
- [Random pairing MLE for estimation of item parameters in Rasch model](https://mlsanity.com/paper/2406.13989/) (2024)
- [Beyond Kemeny Medians: Consensus Ranking Distributions Definition, Properties and Statistical Learning](https://mlsanity.com/paper/2602.10640/) (2026)
- [Optimal Top-k Identification from Pairwise Comparisons](https://mlsanity.com/paper/2607.08979/) (2026)
- [Preference Reasoning under Indeterminacy in Large Language Models](https://mlsanity.com/paper/2608.18631/) (2026)
- [Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs](https://mlsanity.com/paper/2610.09030/) (2026)

## Abstract (arXiv)

We explore the top-K rank aggregation problem. Suppose a collection of items is compared in pairs repeatedly, and we aim to recover a consistent ordering that focuses on the top-K ranked items based on partially revealed preference information. We investigate the Bradley-Terry-Luce model in which one ranks items according to their perceived utilities modeled as noisy observations of their underlying true utilities. Our main contributions are two-fold. First, in a general comparison model where item pairs to compare are given a priori, we attain an upper and lower bound on the sample size for reliable recovery of the top-K ranked items. Second, more importantly, extending the result to a random comparison model where item pairs to compare are chosen independently with some probability, we show that in slightly restricted regimes, the gap between the derived bounds reduces to a constant factor, hence reveals that a spectral method can achieve the minimax optimality on the (order-wise) sample size required for top-K ranking. That is to say, we demonstrate a spectral method alone to be sufficient to achieve the optimality and advantageous in terms of computational complexity, as it does not require an additional stage of maximum likelihood estimation that a state-of-the-art scheme employs to achieve the optimality. We corroborate our main results by numerical experiments.