arXiv：cs.LG· Shashaank Aiyer, Han Shao·· 4 小时前
异构偏好下排序需要多少次重复成对比较？——MLE 与 Russian Roulette 算法的比较研究
How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
AI 导读
针对偏好因用户和任务而异时的成对比较排序问题，研究者提出两种基于 MLE 的变体和一种 Russian Roulette 随机算法，将每个上下文所需的重复比较次数从朴素 MLE 的 Ω(1/Δ²) 降至 O(log(1/Δ))，并证明该对数依赖是最优的。
正文
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 $\Omega(1/\Delta^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/\Delta))$ 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.
| Comments: | 53 pages, 4 figures |
| Subjects: | Machine Learning (cs.LG); Information Theory (cs.IT) |
| Cite as: | arXiv:2610.10795 [cs.LG] |
| (or arXiv:2610.10795v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10795 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Shashaank Aiyer [view email]
[v1]
Wed, 7 Oct 2026 18:52:18 UTC (1,223 KB)
来源：arXiv：cs.LG · arxiv.org