# Approximate Ranking from Pairwise Comparisons

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2018.

## Built on by (most cited first, 21 of 21)

- [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)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Active Preference Learning for Ordering Items In- and Out-of-sample](https://mlsanity.com/paper/2405.03059/) (2024)
- [Neural Improvement Heuristics for Graph Combinatorial Optimization Problems](https://mlsanity.com/paper/2206.00383/) (2022)
- [What Does Preference Learning Recover from Pairwise Comparison Data?](https://mlsanity.com/paper/2602.10286/) (2026)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)
- [PITA: Preference-Guided Inference-Time Alignment for LLM Post-Training](https://mlsanity.com/paper/2507.20067/) (2025)
- [Efficient Bayesian Inference from Noisy Pairwise Comparisons](https://mlsanity.com/paper/2510.09333/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Efficient Pointwise-Pairwise Learning-to-Rank for News Recommendation](https://mlsanity.com/paper/2409.17711/) (2024)
- [Interestingness First Classifiers](https://mlsanity.com/paper/2508.19780/) (2025)
- [Top-k Feature Importance Ranking](https://mlsanity.com/paper/2509.15420/) (2025)
- [Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholds](https://mlsanity.com/paper/2510.01871/) (2025)
- [Bradley-Terry Rankings for Recommender Systems Across Dataset Taxonomies](https://mlsanity.com/paper/2606.07492/) (2026)
- [Cost-Aware Best-LLM Identification using Dueling Feedback](https://mlsanity.com/paper/2609.30360/) (2026)

## Abstract (arXiv)

A common problem in machine learning is to rank a set of n items based on pairwise comparisons. Here ranking refers to partitioning the items into sets of pre-specified sizes according to their scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defined as the probability that it beats a randomly chosen other item. Finding an exact ranking typically requires a prohibitively large number of comparisons, but in practice, approximate rankings are often adequate. Accordingly, we study the problem of finding approximate rankings from pairwise comparisons. We analyze an active ranking algorithm that counts the number of comparisons won, and decides whether to stop or which pair of items to compare next, based on confidence intervals computed from the data collected in previous steps. We show that this algorithm succeeds in recovering approximate rankings using a number of comparisons that is close to optimal up to logarithmic factors. We also present numerical results, showing that in practice, approximation can drastically reduce the number of comparisons required to estimate a ranking.