Simple, Robust and Optimal Ranking from Pairwise Comparisons
From MaRDI portal
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.
Recommendations
- Ranking and selection for pairwise comparison
- On a pairwise comparison-based consistent non-numerical ranking
- scientific article; zbMATH DE number 218751
- Active ranking from pairwise comparisons and when parametric assumptions do not help
- Paired comparisons analysis: an axiomatic approach to ranking methods
- scientific article; zbMATH DE number 177212
- Ranking procedures by pairwise comparison using random sets and the imprecise Dirichlet model
Cites work
- Asymptotic Improvement of the Gilbert–Varshamov Bound on the Size of Binary Codes
- Choice by elimination
- Concentration inequalities. A nonasymptotic theory of independence
- Database Theory - ICDT 2005
- Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
- scientific article; zbMATH DE number 3152611 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 5485441 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 3478749 (Why is no real title available?)
- scientific article; zbMATH DE number 3073477 (Why is no real title available?)
- Inferring Rankings Using Constrained Sensing
- Matrix estimation by universal singular value thresholding
- MM algorithms for generalized Bradley-Terry models.
- Noisy sorting without resampling
- Optimal aggregation algorithms for middleware.
- Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
Cited in
(43)- Top-\(\kappa\) selection with pairwise comparisons
- Pairwise ranking: choice of method can produce arbitrarily different rank order
- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
- Ranking recovery from limited pairwise comparisons using low-rank matrix completion
- Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method
- Optimal full ranking from pairwise comparisons
- Worst-case versus average-case design for estimation from partial pairwise comparisons
- Active ranking from pairwise comparisons and when parametric assumptions do not help
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Optimizing positional scoring rules for rank aggregation
- HodgeRank is the limit of Perron Rank
- Data-driven rank breaking for efficient rank aggregation
- Optimal data collection for informative rankings expose well-connected graphs
- scientific article; zbMATH DE number 5940804 (Why is no real title available?)
- Complete ranking procedures with appropriate loss functions
- A minimum violations ranking method
- Generalized rank-breaking: computational and statistical tradeoffs
- Competitive analysis of the top-K ranking problem
- Methods of Tropical Optimization in Rating Alternatives Based on Pairwise Comparisons
- scientific article; zbMATH DE number 6125202 (Why is no real title available?)
- On a pairwise comparison-based consistent non-numerical ranking
- Robust Learning of Consumer Preferences
- A Framework for Ranking Vacuity Results
- Low permutation-rank matrices: structural properties and noisy completion
- Ranking with a P-Norm Push
- Rank Centrality: Ranking from Pairwise Comparisons
- Time-homogeneous top-\(K\) ranking using tensor decompositions
- Ranking and selection for pairwise comparison
- Subset simulation for probabilistic computer models
- \textsc{PeerNomination}: a novel peer selection algorithm to handle strategic and noisy assessments
- Lagrangian Inference for Ranking Problems
- Evaluating countries' performances by means of rank trajectories: functional measures of magnitude and evolution
- Grouped rank centrality: ranking and grouping from pairwise comparisons simultaneously
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Bias-aware ranking from pairwise comparisons
- Improved theoretical guarantee for rank aggregation via spectral method
- Pair-matching: link prediction with adaptive queries
- Approximate maximum rank aggregation: beyond the worst-case
- A spectral approach for the dynamic Bradley-Terry model
- Rate-Optimal Rank Aggregation with Private Pairwise Rankings
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems
- The information limit of consensus detection on bounded ordinal scales
- A prudent characterization of the ranked pairs rule
This page was built for publication: Simple, Robust and Optimal Ranking from Pairwise Comparisons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558526)
