Ranking accuracy improves with repeated user comparisons under varying preferences
How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
Machine LearningInformation Theory
Summary
This paper looks at how to figure out which option is best when people have different preferences and compare options in pairs. Earlier work showed that asking each person to compare options just once might not find the true best option. The authors study how many times each person needs to compare to get the right ranking. They propose algorithms that need only a small number of repeated comparisons, sometimes just a few on average, to accurately find the top option across all users. They test these methods using simulated data and data from a gaming platform to see how well they work.
What this means in practice
- •For recommendation system engineers: Improve ranking algorithms by optimizing repeated pairwise comparisons to handle diverse user preferences efficiently.
- •For online game designers: Design better player skill ranking systems that require fewer repeated match results per player despite diverse game conditions.
Tested on simulated data.
Authors
Shashaank Aiyer, Han Shao
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.