Minimax Bounds for Generalized Pairwise Comparisons

We introduce the General Pairwise Model (GPM), a general parametric framework for pairwise comparison. Under the umbrella of the exponential family, the GPM unifies many popular models with discrete observations, including the Thurstone (Case V), Berry-Terry-Luce (BTL) and Ordinal Models, along with models with continuous observations, such as the Gaussian Pairwise Cardinal Model. We establish minimax lower bounds with tight topological dependence. When applied as a special case to the Ordinal Model, our results uniformly improve upon previously known lower bounds and confirms one direction of a conjecture put forth by Shah et al., (2016). Performance guarantees of the MLE for a broad class of GPMs with subgaussian assumptions are given and compared against our lower bounds, showing that in many natural settings the MLE is optimal up to constants. Matching lower and upper bounds (up to constants) are achieved by the Gaussian Pairwise Cardinal Model, suggesting that our lower bounds are best-possible under the few assumptions we adopt.