# Minimax Hypothesis Testing for the Bradley-Terry-Luce Model

arXiv: https://arxiv.org/abs/2410.08360 · HTML: https://mlsanity.com/paper/2410.08360/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 96 references that are in the map.
- First posted on arXiv 10 Oct 2024.

## Builds on (most cited first, 21 of 21)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Uncertainty quantification in the Bradley-Terry-Luce model](https://mlsanity.com/paper/2110.03874/) (2021)
- [Ranking Inferences Based on the Top Choice of Multiway Comparisons](https://mlsanity.com/paper/2211.11957/) (2022)
- [On Universal Features for High-Dimensional Learning and Inference](https://mlsanity.com/paper/1911.09105/) (2019)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization](https://mlsanity.com/paper/1504.01070/) (2015)
- [Learning from Comparisons and Choices](https://mlsanity.com/paper/1704.07228/) (2017)
- [On kernel methods for covariates that are rankings](https://mlsanity.com/paper/1603.08035/) (2016)
- [A General Pairwise Comparison Model for Extremely Sparse Networks](https://mlsanity.com/paper/2002.08853/) (2020)
- [Nonparametric Estimation in the Dynamic Bradley-Terry Model](https://mlsanity.com/paper/2003.00083/) (2020)
- [Byzantine Spectral Ranking](https://mlsanity.com/paper/2211.07902/) (2022)
- [Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice](https://mlsanity.com/paper/2001.07042/) (2020)
- [Identity testing of reversible Markov chains](https://mlsanity.com/paper/2105.06347/) (2021)
- [Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions](https://mlsanity.com/paper/2006.11909/) (2020)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Estimation of Skill Distributions](https://mlsanity.com/paper/2006.08189/) (2020)

## Built on by (most cited first, 3 of 3)

- [Hypothesis Testing for Generalized Thurstone Models](https://mlsanity.com/paper/2512.02912/) (2025)
- [Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries](https://mlsanity.com/paper/2605.23854/) (2026)
- [A theoretical guarantee for SyncRank](https://mlsanity.com/paper/2509.22766/) (2025)

## Abstract (arXiv)

The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a collection of items or agents based on pairwise comparisons among them. Given n agents, the BTL model endows each agent i with a latent skill score αi > 0 and posits that the probability that agent i is preferred over agent j is αi/(αi + αj). In this work, our objective is to formulate a hypothesis test that determines whether a given pairwise comparison dataset, with k comparisons per pair of agents, originates from an underlying BTL model. We formalize this testing problem in the minimax sense and define the critical threshold of the problem. We then establish upper bounds on the critical threshold for general induced observation graphs (satisfying mild assumptions) and develop lower bounds for complete induced graphs. Our bounds demonstrate that for complete induced graphs, the critical threshold scales as Theta((nk)-1/2) in a minimax sense. In particular, our test statistic for the upper bounds is based on a new approximation we derive for the separation distance between general pairwise comparison models and the class of BTL models. To further assess the performance of our statistical test, we prove upper bounds on the type I and type II probabilities of error. Much of our analysis is conducted within the context of a fixed observation graph structure, where the graph possesses certain ``nice'' properties, such as expansion and bounded principal ratio. Additionally, we derive several auxiliary results, such as bounds on principal ratios of graphs, ℓ2-bounds on BTL parameter estimation under model mismatch, stability of rankings under the BTL model, etc. We validate our theoretical results through experiments on synthetic and real-world datasets and propose a data-driven permutation testing approach to determine test thresholds.