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.

Keywords

Subject