Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model

Abstract

Zermelo's algorithm is a classical method for computing the maximum likelihood estimator in the Bradley--Terry (BT) model, but its convergence can be slow in practice. To accelerate computation, Newman introduced a family of Zermelo-type fixed-point iterations parameterized by $\hat{I}\pm$, with Zermelo's algorithm recovered at $\hat{I}\pm =1$. Empirical evidence suggests that the choice $\hat{I}\pm =0$ often converges substantially faster, making it a promising alternative, yet the mechanism underlying this acceleration remains elusive. This paper provides theoretical insight into this phenomenon through a systematic local convergence analysis. We derive closed-form expressions for local convergence factors under synchronous and asynchronous updates and analyze their dependence on $\hat{I}\pm$ via spectral analysis of the associated Jacobian matrices. For synchronous updates, we show that the algorithm may fail to converge when $\hat{I}\pm <1$, and its local convergence factor is quasi-convex in $\hat{I}\pm$ under the population BT model. In contrast, asynchronous updates are always locally convergent, and their local convergence factor is provably monotonically increasing in $\hat{I}\pm$ under the population BT model of consistently ordered bipartite comparison graphs, establishing the optimality of $\hat{I}\pm =0$ in this setting. We further establish asymptotic approximation results for the population convergence factors under the BT model, justifying their practical relevance. Numerical experiments on synthetic and real-world datasets confirm the theory. Our analysis complements existing convergence results and shows that the acceleration of $\hat{I}\pm =0$ arises not only from the parameter choice but, more importantly, from the use of asynchronous updates.

46 pages