How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
Abstract
We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires Ω(1/Δ2) repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using O(log(1/Δ)) repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only O(1) comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.
Related
- Low Rank for Rank: Uncertainty-Aware Task-Specific LLM Ranking under Sparse Pairwise Comparisons
- Pairwise comparisons meet optimal transport theory
- From intersection names to street rankings in Kyoto: Comparing ranking methods for incomplete pairwise data
- Selecting the Best Few with Human Evaluators: Adaptively Combining Ratings and Pairwise Comparisons
- Are implicit schemes needed in adaptive time stepping for PDEs?
BibTeX
@misc{aiyer2026many,
title = {{How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?}},
author = {Shashaank Aiyer and Han Shao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10795},
eprint = {2610.10795},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10795},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
AU - Shashaank Aiyer
AU - Han Shao
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10795
UR - https://arxiv.org/abs/2610.10795
AB - We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires Ω(1/Δ^2) repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using O(log(1/Δ)) repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only O(1) comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.
ER -