Active Ranking from Pairwise Comparisons and when Parametric Assumptions
  Don't Help
  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 allows for improved ranking algorithms. For stochastic
comparison models, in which the pairwise probabilities are bounded away from
zero, our second contribution is to resolve this issue by proving a lower bound
for parametric models. This shows, perhaps surprisingly, that these popular
parametric modeling choices offer at most logarithmic gains for stochastic
comparisons.
