Simple, Robust and Optimal Ranking from Pairwise Comparisons

Abstract

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.

Changes in version 2: In addition to recovery in the exact and Hamming metrics, v2 analyzes a general, abstract recovery criterion based on a notion of "allowed sets"

Cited by in corpus (29)

• Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Poisoning Attack against Estimating from Pairwise Comparisons
• Data-driven Rank Breaking for Efficient Rank Aggregation
• Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal
• Lagrangian Inference for Ranking Problems
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• Comparison-Based Framework for Psychophysics: Lab versus Crowdsourcing
• Phase Transitions in Approximate Ranking
• A Machine Learning Approach to Predicting Continuous Tie Strengths
• Preference Modeling with Context-Dependent Salient Features
• Simultaneous Preference and Metric Learning from Paired Comparisons
• Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
• Aggregation of pairwise comparisons with reduction of biases
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
• Lower Bounds on the Bayes Risk of the Bayesian BTL Model with Applications to Comparison Graphs
• Recovery Guarantees for Time-varying Pairwise Comparison Matrices with Non-transitivity
• Spectral Methods for Ranking with Scarce Data
• A Ranking Model Motivated by Nonnegative Matrix Factorization with Applications to Tennis Tournaments
• Predicting Choice with Set-Dependent Aggregation
• Pair-Matching: Links Prediction with Adaptive Queries
• Active embedding search via noisy paired comparisons
• Adversarial Top-$K$ Ranking
• Secretary Ranking with Minimal Inversions
• Aggregating Incomplete and Noisy Rankings
• Achievability and Impossibility of Exact Pairwise Ranking
• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations