mlsanityData to 14 Oct 2026

Simple, Robust and Optimal Ranking from Pairwise Comparisons

arXiv 1512.08949 ↗First posted 30 Dec 2015cs.LG cs.AI cs.ITcited by 70

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 8; 2023: 8; 2024: 14; 2025: 17; 2026: 14.

70 papers.

Sort:

By area:

  1. 2023Large Language Models are Effective Text Rankers with Pairwise Ranking Promptingcited by 307
  2. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  3. 2023Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHFcited by 133
  4. 2024LiPO: Listwise Preference Optimization through Learning-to-Rankcited by 96
  5. 2024PAL: Pluralistic Alignment Framework for Learning from Heterogeneous Preferencescited by 54
  6. 2024Semantic Operators: A Declarative Model for Rich, AI-based Data Processingcited by 34
  7. 2021Diversity Enhanced Active Learning with Strictly Proper Scoring Rulescited by 22
  8. 2021Lagrangian Inference for Ranking Problemscited by 19
  9. 2021Optimal Full Ranking from Pairwise Comparisonscited by 16
  10. 2022Uncertainty Quantification of MLE for Entity Ranking with Covariatescited by 16
  11. 2024LLM-RankFusion: Mitigating Intrinsic Inconsistency in LLM-based Rankingcited by 16
  12. 2021Poisoning Attack against Estimating from Pairwise Comparisonscited by 14
38 more
  1. 2024A Statistical Framework for Ranking LLM-Based Chatbotscited by 12
  2. 2022Equivariance Allows Handling Multiple Nuisance Variables When Analyzing Pooled Neuroimaging Datasetscited by 7
  3. 2024Learning-Augmented Priority Queuescited by 7
  4. 2023Bayesian Estimate of Mean Proper Scores for Diversity-Enhanced Active Learningcited by 6
  5. 2024Active Preference Learning for Ordering Items In- and Out-of-samplecited by 6
  6. 2021Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Methodcited by 5
  7. 2022Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applicationscited by 5
  8. 2022Decreasing Annotation Burden of Pairwise Comparisons with Human-in-the-Loop Sorting: Application in Medical Image Artifact Ratingcited by 5
  9. 2025A Multi-Task Evaluation of LLMs' Processing of Academic Text Inputcited by 5
  10. 2021Semi-verified PAC Learning from the Crowdcited by 4
  11. 2021Meta-Analysis of Randomized Experiments with Applications to Heavy-Tailed Response Datacited by 4
  12. 2022Dynamic Ranking and Translation Synchronizationcited by 4
  13. 2026Medical Triage as Pairwise Ranking: A Benchmark for Urgency in Patient Portal Messagescited by 4
  14. 2026Prompt-Dependent Ranking of Large Language Models with Uncertainty Quantificationcited by 4
  15. 2022Ranking with Confidence for Large Scale Comparison Datacited by 3
  16. 2024Learning to Compare Hardware Designs for High-Level Synthesiscited by 3
  17. 2024Minimax Hypothesis Testing for the Bradley-Terry-Luce Modelcited by 3
  18. 2024Soft Condorcet Optimization for Ranking of General Agentscited by 3
  19. 2023On the Optimal Bounds for Noisy Computingcited by 2
  20. 2023Improved theoretical guarantee for rank aggregation via spectral methodcited by 2
  21. 2025Is Elo Rating Reliable? A Study Under Model Misspecificationcited by 2
  22. 2025Efficient Bayesian Inference from Noisy Pairwise Comparisonscited by 2
  23. 2026ACES: Who Tests the Tests? Leave-One-Out AUC Consistency for Code Generationcited by 2
  24. 2026A Unified Perturbation Framework for Analyzing Leaderboard Stability and Manipulationcited by 2
  25. 2022On Top-k Selection from m-wise Partial Rankings via Borda Countingcited by 1
  26. 2023Noisy Computing of the mathsfOR and mathsfMAX Functionscited by 1
  27. 2024Rate-Optimal Rank Aggregation with Private Pairwise Rankingscited by 1
  28. 2024Baby Bear: Seeking a Just Right Rating Scale for Scalar Annotationscited by 1
  29. 2024Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisonscited by 1
  30. 2025Learning Parametric Distributions from Samples and Preferencescited by 1
  31. 2025JointRank: Rank Large Set with Single Passcited by 1
  32. 2025Optimal Differentially Private Ranking from Pairwise Comparisonscited by 1
  33. 2025Interestingness First Classifierscited by 1
  34. 2025Access Paths for Efficient Ordering with Large Language Modelscited by 1
  35. 2025Top-k Feature Importance Rankingcited by 1
  36. 2025Testing the Testers: Human-Driven Quality Assessment of Voice AI Testing Platformscited by 1
  37. 2025ExPairT-LLM: Exact Learning for LLM Code Selection by Pairwise Queriescited by 1
  38. 2026Active Seriation: Efficient Ordering Recovery with Statistical Guaranteescited by 1

50 most cited of 70 All 70 (JSON)