Georgia Institute of Technology College of Sciences

We consider the problem of estimating pairwise comparison probabilities in a tournament setting after observing every pair of teams play with each other once. We assume the true pairwise probability matrix satisfies a stochastic transitivity condition which is popular in the Social Sciences.This stochastic transitivity condition generalizes the ubiquitous Bradley- Terry model used in the ranking literature. We propose a computationally efficient estimator for this problem, borrowing ideas from recent work on Shape Constrained Regression. We show that the worst case rate of our estimator matches the best known rate for computationally tractable estimators. Additionally we show our estimator enjoys faster rates of convergence for several sub parameter spaces of interest thereby showing automatic adaptivity. We also study the missing data setting where only a fraction of all possible games are observed at random.