# Competitive analysis of the top-K ranking problem

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

## Key facts

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

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

- [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)
- [Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization](https://mlsanity.com/paper/2402.18917/) (2024)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [Optimal Differentially Private Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2507.09388/) (2025)
- [Achievability and Impossibility of Exact Pairwise Ranking](https://mlsanity.com/paper/2111.10021/) (2021)

## Abstract (arXiv)

Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top K items from noisy pairwise comparisons. In our setting, we are non-actively given r pairwise comparisons between each pair of n items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top-K problem. In particular, we present a linear time algorithm for the top-K problem which has a competitive ratio of tildeO(√n); i.e. to solve any instance of top-K, our algorithm needs at most tildeO(√n) times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top-K problem have competitive ratios of tildeOmega(n) or worse). We further show that this is tight: any algorithm for the top-K problem has competitive ratio at least tildeOmega(√n).