# Simple, Robust and Optimal Ranking from Pairwise Comparisons

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2015.

## Built on by (most cited first, 30 of 70)

- [Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting](https://mlsanity.com/paper/2306.17563/) (2023)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF](https://mlsanity.com/paper/2312.08358/) (2023)
- [LiPO: Listwise Preference Optimization through Learning-to-Rank](https://mlsanity.com/paper/2402.01878/) (2024)
- [PAL: Pluralistic Alignment Framework for Learning from Heterogeneous Preferences](https://mlsanity.com/paper/2406.08469/) (2024)
- [Semantic Operators: A Declarative Model for Rich, AI-based Data Processing](https://mlsanity.com/paper/2407.11418/) (2024)
- [Diversity Enhanced Active Learning with Strictly Proper Scoring Rules](https://mlsanity.com/paper/2110.14171/) (2021)
- [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)
- [LLM-RankFusion: Mitigating Intrinsic Inconsistency in LLM-based Ranking](https://mlsanity.com/paper/2406.00231/) (2024)
- [Poisoning Attack against Estimating from Pairwise Comparisons](https://mlsanity.com/paper/2107.01854/) (2021)
- [A Statistical Framework for Ranking LLM-Based Chatbots](https://mlsanity.com/paper/2412.18407/) (2024)
- [Equivariance Allows Handling Multiple Nuisance Variables When Analyzing Pooled Neuroimaging Datasets](https://mlsanity.com/paper/2203.15234/) (2022)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Bayesian Estimate of Mean Proper Scores for Diversity-Enhanced Active Learning](https://mlsanity.com/paper/2312.10116/) (2023)
- [Active Preference Learning for Ordering Items In- and Out-of-sample](https://mlsanity.com/paper/2405.03059/) (2024)
- [Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method](https://mlsanity.com/paper/2109.13743/) (2021)
- [Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applications](https://mlsanity.com/paper/2201.08105/) (2022)
- [Decreasing Annotation Burden of Pairwise Comparisons with Human-in-the-Loop Sorting: Application in Medical Image Artifact Rating](https://mlsanity.com/paper/2202.04823/) (2022)
- [A Multi-Task Evaluation of LLMs' Processing of Academic Text Input](https://mlsanity.com/paper/2508.11779/) (2025)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Meta-Analysis of Randomized Experiments with Applications to Heavy-Tailed Response Data](https://mlsanity.com/paper/2112.07602/) (2021)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Medical Triage as Pairwise Ranking: A Benchmark for Urgency in Patient Portal Messages](https://mlsanity.com/paper/2601.13178/) (2026)
- [Prompt-Dependent Ranking of Large Language Models with Uncertainty Quantification](https://mlsanity.com/paper/2603.03336/) (2026)
- [Ranking with Confidence for Large Scale Comparison Data](https://mlsanity.com/paper/2202.01670/) (2022)
- [Learning to Compare Hardware Designs for High-Level Synthesis](https://mlsanity.com/paper/2409.13138/) (2024)
- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [Soft Condorcet Optimization for Ranking of General Agents](https://mlsanity.com/paper/2411.00119/) (2024)

## Abstract (arXiv)

We consider data in the form of pairwise comparisons of n items, with the goal of precisely identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Copeland counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three attractive features: (a) its computational efficiency leads to speed-ups of several orders of magnitude in computation time as compared to prior work; (b) it is robust in that theoretical guarantees impose no conditions on the underlying matrix of pairwise-comparison probabilities, in contrast to some prior work that applies only to the BTL parametric model; and (c) it is an optimal method up to constant factors, meaning that it achieves the information-theoretic limits for recovering the top k-subset. We extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric, and more generally, to any arbitrary error requirement that satisfies a simple and natural monotonicity condition.