Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

Abstract

Data in the form of pairwise comparisons arises in many domains, including preference elicitation, sporting competitions, and peer grading among others. We consider parametric ordinal models for such pairwise comparison data involving a latent vector $w^{\ast }\in {\mathbb{R}}^d$ that represents the "qualities" of the $d$ items being compared; this class of models includes the two most widely used parametric models--the Bradley-Terry-Luce (BTL) and the Thurstone models. Working within a standard minimax framework, we provide tight upper and lower bounds on the optimal error in estimating the quality score vector $w^{\ast }$ under this class of models. The bounds depend on the topology of the comparison graph induced by the subset of pairs being compared via its Laplacian spectrum. Thus, in settings where the subset of pairs may be chosen, our results provide principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors.

39 pages, 5 figures. Significant extension of arXiv:1406.6618

References in corpus (3)

• Noisy Sorting Without Resampling
• Minimax-optimal Inference from Partial Rankings
• When is it Better to Compare than to Score?

Cited by in corpus (10)

• Poisoning Attack against Estimating from Pairwise Comparisons
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Strategy for Boosting Pair Comparison and Improving Quality Assessment Accuracy
• Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
• Simultaneous Preference and Metric Learning from Paired Comparisons
• Spectral Methods for Ranking with Scarce Data
• Graph Resistance and Learning from Pairwise Comparisons
• Active embedding search via noisy paired comparisons
• A Normal Approximation Method for Statistics in Knockouts
• Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice