Bradley-Terry model under general comparison graphs
Abstract
The Bradley-Terry model is a parametric model for ranking from pairwise comparisons. Existing asymptotic theory for the maximum likelihood estimator (MLE) in regimes where the number of objects grows often requires homogeneity assumptions or compatibility conditions on comparison graphs, which limits its applicability to many practical settings. In this work, we establish uniform consistency of the MLE under general deterministic comparison designs. Our pairwise error bound consists of a pair-specific term governed by the effective resistance between the corresponding objects and a global term governed by the spectral gap of the unnormalized graph Laplacian. The bound is tight up to logarithmic factors for certain graph sequences. For any prespecified sequence of pairs satisfying an additional balancing condition, we further establish asymptotic normality of the corresponding estimated utility differences. As an application, we obtain uniform consistency for independent-edge random graph designs whenever the minimum edge probability exceeds the Erdős-Rényi connectivity threshold by a logarithmic factor, as well as asymptotic normality under additional balancing conditions.
Related
- When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting
- Alternative Strategies for Active Learning with Bayesian Bradley Terry Model
- Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs
- Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs
- Convergence and acceleration of a nonlinear fixed-point iteration for computing the Fitness Centrality of general graphs
BibTeX
@misc{han2026bradleyterry,
title = {{Bradley-Terry model under general comparison graphs}},
author = {Ruijian Han and Yuanhang Luo and Yiming Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06237},
eprint = {2610.06237},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06237},
}
RIS
TY - UNPB
TI - Bradley-Terry model under general comparison graphs
AU - Ruijian Han
AU - Yuanhang Luo
AU - Yiming Xu
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06237
UR - https://arxiv.org/abs/2610.06237
AB - The Bradley-Terry model is a parametric model for ranking from pairwise comparisons. Existing asymptotic theory for the maximum likelihood estimator (MLE) in regimes where the number of objects grows often requires homogeneity assumptions or compatibility conditions on comparison graphs, which limits its applicability to many practical settings. In this work, we establish uniform consistency of the MLE under general deterministic comparison designs. Our pairwise error bound consists of a pair-specific term governed by the effective resistance between the corresponding objects and a global term governed by the spectral gap of the unnormalized graph Laplacian. The bound is tight up to logarithmic factors for certain graph sequences. For any prespecified sequence of pairs satisfying an additional balancing condition, we further establish asymptotic normality of the corresponding estimated utility differences. As an application, we obtain uniform consistency for independent-edge random graph designs whenever the minimum edge probability exceeds the Erdős-Rényi connectivity threshold by a logarithmic factor, as well as asymptotic normality under additional balancing conditions.
ER -