We consider data in the form of pairwise comparisons of n items, with the goal of precisely identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We consider a simple counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three important and useful features: (a) Computational efficiency: the simplicity of the method leads to speed-ups of several orders of magnitude in computation time as compared to prior work; (b) Robustness: our theoretical guarantees make no assumptions on the pairwise-comparison probabilities, while prior work is restricted to the specific BTL model and performs poorly if the data is not true to it; and (c) Optimality: we show that up to constant factors, our algorithm achieves the information-theoretic limits for recovering the top-k subset. Finally, we extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric.

本研究旨在通过成对比较的数据形式，使用 Copeland 计数算法实现对 n 个项目的排序，使其具有计算效率高，鲁棒性强，接近信息论极限等特点，并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。

简单、健壮且最优排名的配对比较