Efficient computation of rankings from pairwise comparisons
arXiv:2207.00076
Abstract
We study the ranking of individuals, teams, or objects, based on pairwise comparisons between them, using the Bradley-Terry model. Estimates of rankings within this model are commonly made using a simple iterative algorithm first introduced by Zermelo almost a century ago. Here we describe an alternative and similarly simple iteration that provably returns identical results but does so much faster -- over a hundred times faster in some cases. We demonstrate this algorithm with applications to a range of example data sets and derive a number of results regarding its convergence.
25 pages, 1 figure, 1 table; additional material on MAP estimation and rates of convergence
Cited by in corpus (4)
- Luck, skill, and depth of competition in games and social hierarchies
- Efficient Portfolio Selection through Preference Aggregation with Quicksort and the Bradley--Terry Model
- Analysis of the inference of ratings and rankings in complex networks using discrete exterior calculus on higher--order networks
- Efficient inference of rankings from multi-body comparisons