Papers › ℓ_∞-Bounds of the MLE in the BTL Model under General Comparison Graphs
ℓ_∞-Bounds of the MLE in the BTL Model under General Comparison Graphs
Wanshan Li, Shamindra Shrotriya, Alessandro Rinaldo
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections