Efficient computation of rankings from pairwise comparisons
This provides a more efficient solution for ranking tasks in fields like sports or recommendation systems, though it is incremental as it builds on a century-old method.
The paper tackles the problem of ranking items from pairwise comparisons using the Bradley-Terry model, and introduces an alternative iterative algorithm that is over a hundred times faster than the existing method while producing identical results.
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.