Active ranking from pairwise comparisons and when parametric assumptions do not help (Q2284367)

The paper deals with the problem of finding a partial or complete ranking of a set of \(n\) items based on active pairwise comparisons in a sequential fashion. The outcomes of comparisons are stochastic, i.e. item \(i\) beats item \(j\) with an unknown probability \(M_{ij}\in (0,~1).\) The outcomes of pairwise comparisons are assumed to be stochastically mutually independent, and moreover the probabilities \(M_{ij}\) are separated away from zero and one. The ordering of the items is defined in terms of their (unknown) scores, where the score \(\tau_i\) of item \(i\) is the probability that item \(i\) beats an item chosen uniformly at random from all other items. An algorithm is presented 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. It is shown that the algorithm succeeds in recovering the ranking using a number of comparisons (which is called the sample complexity) that is optimal up to logarithmic factors. Moreover it is proven that the algorithm remains optimal when imposing common parametric assumptions on the probabilities \(M_{ij}\) such as the Bradley-Terry-Luce model (see [\textit{R. D. Luce}, Individual choice behavior. A theoretical analysis. New York: John Wiley \& Sons, Inc.; London: Chapman \& Hall, Ltd. (1959; Zbl 0093.31708)]) or Thurstone model (see [\textit{L. Thurstone}, ``A law of comparative judgment'', Psychol. Rev. 34, No. 4, 273--286 (1927; \url{doi:10.1037/h0070288})]). This shows, quite surprisingly, that popular parametric modeling choices offer at most a logarithmic gain in the sample complexity; this gain needs to be weighed against the potential lack of robustness incurred by using a parametric mode, as shown in the numerical results section. The discussion in the paper notices that for essentially deterministic comparison models (meaning that the probabilities \(M_{ij}\) may be arbitrarily close to zero ore one), there indeed can be significant gains in the sample complexity if to use the parametric assumptions.