在异质性下排名需要多少次重复的成对比较？

当用户和任务的偏好不同时，我们通过成对比较来研究人口平均效用的排名模型。先前的研究表明，即使有任意多个用户，每个用户的单次比较也可能不足以识别具有最高平均效用的替代方案（Golz 等人，2025）。我们研究每个用户任务上下文中有多少次重复比较对于排名恢复是必要且充分的。在具有固定逆温度的异构 Bradley-Terry 模型下，我们从基于 MLE 的朴素算法开始，该算法需要每个上下文进行 $Ω(1/Δ^2)$ 重复比较，以确保排名恢复。然后，我们提出了两个基于 MLE 的变体和一个随机的俄罗斯轮盘赌式算法，该算法使用每个上下文的 $O(\log(1/Δ))$ 重复比较来恢复排名，并且我们证明这种对数依赖性是最优的。尽管存在这种最坏情况的要求，但我们的俄罗斯轮盘赌算法在预期中仅对每个上下文使用 $O(1)$ 比较。基于Arena数据的综合实验和半综合实验比较了四种算法 具有不同程度的偏好异质性和不同背景分布的设置。