Pairwise Comparison Models for High-Dimensional Ranking

Data in the form of pairwise comparisons between a collection of n items arises in many settings, including voting schemes, tournament play, and online search rankings. We study a flexible non-parametric model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity (SST). The SST class includes a large family of classical parametric models as special cases, among them the Bradley-Terry-Luce and Thurstone models, but is substantially richer. We provide a sharp characterization of the minimax risk for estimating the matrix of pairwise comparisons, and discuss various computational issues that arise in achieving it in an efficient way.Based on joint work with Nihar Shah, Sivaraman Balakrishman and Aditya Guntuboyina.