Simple, Robust and Optimal Ranking from Pairwise Comparisons

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.

• Publication year

  2015

• Venue

  Journal of machine learning research

• Publication date

  2015-12-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1512.08949
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Design and Analysis of the NIPS 2016 Review Process

  2017cited by this paper
• Low Permutation-Rank Matrices: Structural Properties and Noisy Completion

  2017cited by this paper
• Learning From People

  2017cited by this paper
• An Exploratory Study of Reliability of Ranking vs. Rating in Peer Assessment

  2017cited by this paper
• Feeling the bern: Adaptive estimators for Bernoulli probabilities of pairwise comparisons

  2016cited by this paper
• Active ranking from pairwise comparisons and when parametric assumptions do not help

  2016cited by this paper
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

  2015cited by this paper
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues

  2015cited by this paper
• Sparse Dueling Bandits

  2015cited by this paper
• Ranking from Stochastic Pairwise Preferences: Recovering Condorcet Winners and Tournament Solution Sets at the Top

  2015cited by this paper
• Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons

  2015cited by this paper
• A Topic Modeling Approach to Ranking

  2014cited by this paper
• A Statistical Convergence Perspective of Algorithms for Rank Aggregation from Pairwise Data

  2014cited by this paper
• Minimax-optimal Inference from Partial Rankings

  2014cited by this paper
• Computing Parametric Ranking Models via Rank-Breaking

  2014cited by this paper
• Efficient Ranking from Pairwise Comparisons

  2013cited by this paper
• Learning to Top-K Search using Pairwise Comparisons

  2013cited by this paper
• Top-k Selection based on Adaptive Sampling of Noisy Preferences

  2013cited by this paper
• Information Complexity in Bandit Subset Selection

  2013cited by this paper
• A Case for Ordinal Peer-evaluation in MOOCs

  2013cited by this paper
• Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

  2013cited by this paper
• Concentration Inequalities: A Nonasymptotic Theory of Independence

  2013cited by this paper
• Efficient rank aggregation using partial data

  2012cited by this paper
• Iterative ranking from pair-wise comparisons

  2012cited by this paper
• Matrix estimation by Universal Singular Value Thresholding

  2012cited by this paper
• User rankings from comparisons: Learning permutations in high dimensions

  2011cited by this paper
• Active Ranking using Pairwise Comparisons

  2011cited by this paper
• Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity

  2011cited by this paper
• Introduction to Nonparametric Estimation

  2008cited by this paper
• Inferring rankings under constrained sensing

  2008cited by this paper
• A survey of top-k query processing techniques in relational database systems

  2008cited by this paper
• Noisy sorting without resampling

  2007cited by this paper
• How to rank with few errors A PTAS for Weighted Feedback Arc Set on Tournaments

  2006cited by this paper
• CellProfiler: image analysis software for identifying and quantifying cell phenotypes

  2006cited by this paper
• Finding and approximating top-k answers in keyword proximity search

  2006cited by this paper
• Efficient Computation of Frequent and Top-k Elements in Data Streams

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• KLEE: A Framework for Distributed Top-k Query Algorithms

  2005cited by this paper
• Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes

  2004cited by this paper
• MM algorithms for generalized Bradley-Terry models

  2003cited by this paper
• Distributed top-k monitoring

  2003cited by this paper
• Optimal aggregation algorithms for middleware

  2001cited by this paper
• DECISIONS, E RROR A ND H ETEROGENEITY

  1997cited by this paper
• A law of comparative judgment.

  1994cited by this paper
• On the evolution of random graphs

  1984cited by this paper
• The evolution of random graphs

  1984cited by this paper
• Individual Choice Behavior: A Theoretical Analysis

  1979cited by this paper
• Elimination by aspects: A theory of choice.

  1972cited by this paper
• Stochastic transitivity and cancellation of preferences between bitter-sweet solutions

  1965cited by this paper
• Individual Choice Behavior: A Theoretical Analysis.

  1960cited by this paper
• Experimental Tests of Stochastic Decision Theory

  1957cited by this paper
• Decisions

  1952cited by this paper
• RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS THE METHOD OF PAIRED COMPARISONS

  1952cited by this paper
• RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS

  1952cited by this paper
• Mémoire sur les élections au scrutin

  year unknowncited by this paper

• Medical Triage as Pairwise Ranking: A Benchmark for Urgency in Patient Portal Messages

  2026cites this paper
• Distribution-informed Efficient Conformal Prediction for Full Ranking

  2026cites this paper
• The issue of sparse networks in sports competitions: can Elo ratings efficiently compare football teams that never play a match?

  2026cites this paper
• Beyond Kemeny Medians: Consensus Ranking Distributions Definition, Properties and Statistical Learning

  2026cites this paper
• Prompt-Dependent Ranking of Large Language Models with Uncertainty Quantification

  2026cites this paper
• Flexible Windowing for Correlation-Aware Ranking in Anomalous Environments

  2025cites this paper
• Top-k Feature Importance Ranking

  2025cites this paper
• Estimating the Error of Large Language Models at Pairwise Text Comparison

  2025cites this paper
• Pairwise Sample Complexity for Fair Active Ranking with Cascaded Norm Objectives

  2025cites this paper
• Interestingness First Classifiers

  2025influential citation
• Redefining lameness assessment: Constructing lameness hierarchy using crowd-sourced data

  2025cites this paper
• Learning Parametric Distributions from Samples and Preferences

  2025cites this paper
• ExPairT-LLM: Exact Learning for LLM Code Selection by Pairwise Queries

  2025cites this paper
• LLMs Can Assist with Proposal Selection at Large User Facilities

  2025cites this paper
• Designing Rules to Pick a Rule: Aggregation by Consistency

  2025cites this paper
• Optimal Differentially Private Ranking from Pairwise Comparisons*

  2025influential citation
• Testing the Testers: Human-Driven Quality Assessment of Voice AI Testing Platforms

  2025cites this paper
• Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications

  2025cites this paper
• Topic-Guided Reinforcement Learning with LLMs for Enhancing Multi-Document Summarization

  2025cites this paper
• Introducing Powerwise (PWR): A pairwise and Power Rating method for selecting at-large teams to the NCAA Division I Men's Lacrosse Championship

  2025cites this paper
• A Multi-Task Evaluation of LLMs' Processing of Academic Text Input

  2025cites this paper
• Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation

  2025cites this paper
• Eliminating Retrieval Knowledge Conflicts: Cross-Validation Re-ranking with Large Language Models

  2025cites this paper
• Rank Aggregation under Weak Stochastic Transitivity via a Maximum Score Estimator

  2025cites this paper
• Access Paths for Efficient Ordering with Large Language Models

  2025cites this paper
• PAL: Sample-Efficient Personalized Reward Modeling for Pluralistic Alignment

  2025cites this paper
• Is Elo Rating Reliable? A Study Under Model Misspecification

  2025cites this paper
• Semantic Operators and Their Optimization: Towards AI-Based Data Analytics with Accuracy Guarantees

  2025cites this paper
• A comparison-relationship-surrogate evolutionary algorithm for multi-objective optimization

  2025cites this paper
• The Majority Vote Paradigm Shift: When Popular Meets Optimal

  2025cites this paper
• JointRank: Rank Large Set with Single Pass

  2025cites this paper
• Semantic Operators: A Declarative Model for Rich, AI-based Data Processing

  2024cites this paper
• Minimax Hypothesis Testing for the Bradley–Terry–Luce Model

  2024cites this paper
• Statistical Inference of a Ranked Community in a Directed Graph

  2024cites this paper
• AutoMode-ASR: Learning to Select ASR Systems for Better Quality and Cost

  2024cites this paper
• Inference of rankings planted in random tournaments

  2024cites this paper
• A Graph Theoretic Approach for Preference Learning with Feature Information

  2024cites this paper
• Learning to Compare Hardware Designs for High-Level Synthesis

  2024cites this paper
• LLM-RankFusion: Mitigating Intrinsic Inconsistency in LLM-based Ranking

  2024cites this paper
• Learning-Augmented Priority Queues

  2024cites this paper
• Rate-Optimal Rank Aggregation with Private Pairwise Rankings

  2024cites this paper
• Baby Bear: Seeking a Just Right Rating Scale for Scalar Annotations

  2024cites this paper
• Noisy Computing of the Threshold Function

  2024cites this paper
• Soft Condorcet Optimization for Ranking of General Agents

  2024cites this paper
• Active Preference Learning for Ordering Items In- and Out-of-sample

  2024cites this paper
• LiPO: Listwise Preference Optimization through Learning-to-Rank

  2024cites this paper
• Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons

  2024cites this paper
• Learning Populations of Preferences via Pairwise Comparison Queries

  2024cites this paper
• PAL: Pluralistic Alignment Framework for Learning from Heterogeneous Preferences

  2024cites this paper
• A Statistical Framework for Ranking LLM-Based Chatbots

  2024cites this paper
• Improved theoretical guarantee for rank aggregation via spectral method

  2023cites this paper
• Noisy Computing of the OR and MAX Functions

  2023cites this paper
• Testing for the Bradley-Terry-Luce Model

  2023cites this paper
• Variable-Length Insertion-Based Noisy Sorting

  2023cites this paper
• Learning Preference Distributions From Pairwise Comparisons

  2023cites this paper
• Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting

  2023cites this paper
• A spectral approach for the dynamic Bradley–Terry model

  2023cites this paper
• Ranking a Set of Objects Using Heterogeneous Workers: QUITE an Easy Problem

  2023influential citation
• Approximate Maximum Rank Aggregation: Beyond the Worst-Case

  2023cites this paper
• Bayesian Estimate of Mean Proper Scores for Diversity-Enhanced Active Learning

  2023cites this paper
• HALP: Heuristic Aided Learned Preference Eviction Policy for YouTube Content Delivery Network

  2023cites this paper
• Subset simulation for probabilistic computer models

  2023cites this paper
• Grouped rank centrality: Ranking and grouping from pairwise comparisons simultaneously

  2023cites this paper
• Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons

  2023cites this paper
• Physically-plausible illumination distribution estimation

  2023cites this paper
• On the Optimal Bounds for Noisy Computing

  2023cites this paper
• Ranking and selection for pairwise comparison

  2023cites this paper
• Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF

  2023cites this paper
• Decreasing Annotation Burden of Pairwise Comparisons with Human-in-the-Loop Sorting: Application in Medical Image Artifact Rating

  2022cites this paper
• Noisy Sorting Capacity

  2022cites this paper
• Equivariance Allows Handling Multiple Nuisance Variables When Analyzing Pooled Neuroimaging Datasets

  2022cites this paper
• PeerNomination: A novel peer selection algorithm to handle strategic and noisy assessments

  2022cites this paper
• Noisy Sorting Capacity

  2022cites this paper
• Integrating Rankings into Quantized Scores in Peer Review

  2022cites this paper
• Uncertainty Quantification of MLE for Entity Ranking with Covariates

  2022cites this paper
• Ranking with Confidence for Large Scale Comparison Data

  2022cites this paper
• The incomplete Analytic Hierarchy Process and Bradley-Terry model: (in)consistency and information retrieval

  2022cites this paper
• Efficient and Accurate Top-K Recovery from Choice Data

  2022cites this paper
• Detecting Abrupt Changes in Sequential Pairwise Comparison Data

  2022cites this paper
• Dynamic ranking and translation synchronization

  2022cites this paper
• Characterizing the Progression of Pulmonary Edema Severity: Can Pairwise Comparisons in Radiology Reports Help?

  2022cites this paper
• Evaluating countries’ performances by means of rank trajectories: functional measures of magnitude and evolution

  2022cites this paper
• Practical Event Location Estimation Algorithm for Power Transmission System Based on Triangulation and Oscillation Intensity

  2022cites this paper
• Matchmaker: Data Drift Mitigation in Machine Learning for Large-Scale Systems

  2022cites this paper
• Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applications

  2022cites this paper
• DECISION SUPPORT SYSTEM FOR SELECTING DOCTORS IN APPLICATION X USING ANALYTICAL HIERARCHY PROCESS (AHP)

  2022cites this paper
• Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity

  2022cites this paper
• PAC Top-k Identification under SST in Limited Rounds

  2022cites this paper
• Learning Preference Distributions From Distance Measurements

  2022cites this paper
• Active Ranking without Strong Stochastic Transitivity

  2022cites this paper
• Lagrangian Inference for Ranking Problems

  2021cites this paper
• Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method

  2021cites this paper
• A heuristic for statistical seriation

  2021influential citation
• Sorting is All You Need for Medical Image Rating

  2021cites this paper
• Learning to Rank Model Performance and Review with Pairwise Transformations

  2021cites this paper
• Recovery Guarantees for Time-varying Pairwise Comparison Matrices with Non-transitivity

  2021influential citation
• Semi-Verified PAC Learning from the Crowd

  2021cites this paper
• Poisoning Attack Against Estimating From Pairwise Comparisons

  2021cites this paper
• Ranking recovery from limited pairwise comparisons using low-rank matrix completion

  2021cites this paper
• Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT

  2021cites this paper