We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking includes as special cases the identification of the top-k items and the total ordering of the items. We first analyze a sequential ranking algorithm that counts the number of comparisons won, and uses these counts to decide whether to stop, or to compare another pair of items, chosen based on confidence intervals specified by the data collected up to that point. We prove that this algorithm succeeds in recovering the ranking using a number of comparisons that is optimal up to logarithmic factors. This guarantee does not require any structural properties of the underlying pairwise probability matrix, unlike a significant body of past work on pairwise ranking based on parametric models such as the Thurstone or Bradley-Terry-Luce models. It has been a long-standing open question as to whether or not imposing these parametric assumptions allow for improved ranking algorithms. Our second contribution settles this issue in the context of the problem of active ranking from pairwise comparisons: by means of tight lower bounds, we prove that perhaps surprisingly, these popular parametric modeling choices offer little statistical advantage.

文中提出了一种基于序列或主动排名的算法，该算法基于嘈杂的成对比较将一组n个项目排名并将这些项根据其得分分成预先指定大小的集合；本文针对这种算法进行了分析，证明了在某些情况下具有最优性并且不需要任何假设，比如在参数模型下进行的排名。

来自配对比较的主动排序及其在参数假设无法提供帮助时的应用