在异质性条件下进行排序需要多少次重复的成对比较？

arXiv:2610.10795v1 公告类型：新 摘要：我们研究如何根据成对比较，按照总体平均效用对选项进行排序，其中用户和任务之间的偏好存在差异。已有研究表明，即使用户数量任意多，每位用户仅进行一次比较也可能不足以确定平均效用最高的选项（Golz et al., 2025）。我们考察在每个用户—任务情境中需要进行多少次重复比较，才能充分且必要地恢复排序。在固定逆温度的异质 Bradley-Terry 模型下，我们首先提出一种基于朴素 MLE 的算法；为确保恢复排序，该算法要求每个情境进行 $\Omega(1/\Delta^2)$ 次重复比较。随后，我们提出两种基于 MLE 的变体，以及一种 Russian Roulette-style 随机算法；它们仅需在每个情境中进行 $O(\log(1/\Delta))$ 次重复比较即可恢复排序，并证明这种对数级依赖是最优的。尽管在最坏情况下需要这么多比较，我们的 Russian Roulette 算法在期望意义下每个情境仅使用 $O(1)$ 次比较。我们在偏好异质性程度不同且情境分布各异的设置下，开展了合成实验和基于 Arena 数据的半合成实验，对这四种算法进行了比较。