# ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 48 references that are in the map.
- First posted on arXiv 20 Oct 2021.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014)
- [Rank Aggregation via Heterogeneous Thurstone Preference Models](https://mlsanity.com/paper/1912.01211/) (2019)
- [On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons](https://mlsanity.com/paper/1909.03194/) (2019)
- [Graph Resistance and Learning from Pairwise Comparisons](https://mlsanity.com/paper/1902.00141/) (2019)
- [Statistical Modelling of Citation Exchange Between Statistics Journals](https://mlsanity.com/paper/1312.1794/) (2013)
- [Spectral Methods for Ranking with Scarce Data](https://mlsanity.com/paper/2007.01346/) (2020)

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

- [Spectral Ranking Inferences based on General Multiway Comparisons](https://mlsanity.com/paper/2308.02918/) (2023)
- [Sequential Manipulation Against Rank Aggregation: Theory and Algorithm](https://mlsanity.com/paper/2407.01916/) (2024)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [What Does Preference Learning Recover from Pairwise Comparison Data?](https://mlsanity.com/paper/2602.10286/) (2026)
- [An Analysis of Elo Rating Systems via Markov Chains](https://mlsanity.com/paper/2406.05869/) (2024)
- [Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem](https://mlsanity.com/paper/2310.02016/) (2023)
- [Random pairing MLE for estimation of item parameters in Rasch model](https://mlsanity.com/paper/2406.13989/) (2024)
- [Bradley-Terry model under general comparison graphs](https://mlsanity.com/paper/2610.06237/) (2026)

## Abstract (arXiv)

The Bradley-Terry-Luce (BTL) model is a popular statistical approach for estimating the global ranking of a collection of items using pairwise comparisons. To ensure accurate ranking, it is essential to obtain precise estimates of the model parameters in the ℓ∞-loss. The difficulty of this task depends crucially on the topology of the pairwise comparison graph over the given items. However, beyond very few well-studied cases, such as the complete and Erd"os-R'enyi comparison graphs, little is known about the performance of the maximum likelihood estimator MLE) of the BTL model parameters in the ℓ∞-loss under more general graph topologies. In this paper, we derive novel, general upper bounds on the ℓ∞ estimation error of the BTL MLE that depend explicitly on the algebraic connectivity of the comparison graph, the maximal performance gap across items and the sample complexity. We demonstrate that the derived bounds perform well and in some cases are sharper compared to known results obtained using different loss functions and more restricted assumptions and graph topologies. We carefully compare our results to Yan et al. (2012), which is closest in spirit to our work. We further provide minimax lower bounds under ℓ∞-error that nearly match the upper bounds over a class of sufficiently regular graph topologies. Finally, we study the implications of our ℓ∞-bounds for efficient (offline) tournament design. We illustrate and discuss our findings through various examples and simulations.