Research map / Probabilistic and scientific modeling / Variational and generative sampling
An Analysis of Elo Rating Systems via Markov Chains
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes the Elo rating system as a Markov chain under the Bradley-Terry-Luce model, proving time-averaged Elo ratings converge to true ratings at a rate competitive with offline MLE methods, and connects optimal tournament design to fastest-mixing Markov chains.
Problem
Elo rating systems are popular for ranking players online but lack rigorous theoretical understanding; it is unclear how fast Elo learns BTL model parameters from sequential pairwise match results.
Approach
Model Elo as a Markov chain over R^n under the BTL model, use contraction (positive curvature) via a noisy coupled version and Markov chain concentration to show time-averaged Elo ratings concentrate around true ratings; optimise match-up distribution via the fastest-mixing Markov chain / spectral gap for tournament design.</1ccore_idea>
Key results
- Theorem: with eta ~ (log n)^2/(lambda_q t), (1/n)||A - rho||^2 is O(e^{4M}(log n)^2/(lambda_q^2 n t)) whp, matching up to log factors the offline MLE rates.
- Dumbbell experiments: optimised sequential and parallel distributions converge far faster than uniform sampling, e.g. uniform spectral gap scales as k/n^3 versus 1/n for the optimal distribution.
- Largest Elo rating in absolute value on complete graphs stayed below 1.75 for up to 50000 matches with 100-1000 players (true ratings in [-1,1]).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the optimal sequential match distribution instead of uniform edge sampling | Elo · Dumbbell graph, k=1 | mean squared rating error | Helped |
| Use the optimal parallel match distribution instead of uniform edge sampling | Elo · Dumbbell graph, k=1 | mean squared rating error | Helped |
| Use optimal parallel matchings instead of optimal sequential sampling | Elo · Dumbbell graph, k=1, measured in rounds | mean squared rating error | Mixed |
| Use optimal parallel matchings instead of sequential sampling | Elo · Dumbbell graph, k=20 | mean squared rating error | Mixed |
| Use uniform edge sampling instead of the optimal sampling distributions | Elo · Dumbbell graph, k=20 | mean squared rating error | Hurt |
| Use optimal parallel sampling instead of sequential sampling | Elo · Dumbbell graphs, k=5 and k=10, measured in rounds | mean squared rating error | Helped |
| Add edges across the bottleneck | Elo with optimal sequential match sampling · Dumbbell graphs, k=5 and k=10 | mean squared rating error | No clear effect |
| Use optimal sequential sampling instead of uniform edge sampling | Elo · Pyramidal graph | mean squared rating error | Helped |
| Use optimal parallel matchings instead of uniform edge sampling | Elo · Pyramidal graph, measured in rounds | mean squared rating error | Helped |
| Use optimal sequential sampling instead of uniform edge sampling | Elo · Erdős–Rényi giant component, n=100, p=0.02 | mean squared rating error | Hurt |
| Run Elo on a complete graph with uniformly sampled pairs | Elo initialized at zero · Complete graph of varying size, up to 50000 matches | maximum absolute Elo rating: below 1.75 | Helped |
Surprising findings
- On an Erdos-Renyi graph, the spectral-gap-optimal sequential distribution performed slightly worse than uniform sampling, because the spectral gap is a worst-case bound.
Limitations
- Analysis requires a projection step to keep ratings bounded; the unprojected Elo is not covered by the theory.
- Mixing argument uses noisy version and works in Wasserstein-type metric since Elo does not converge in total variation.
- Bounds on the maximum rating and l-infinity error remain open.
Experimental setup
Metrics: squared l2 error of time-averaged ratings divided by n largest absolute Elo rating
Baselines: uniform match-up distribution maximum likelihood estimation with constraints (Hajek, Oh and Xu) Li, Shrotriya and Rinaldo regularised MLE
Builds on: Elo rating system Bradley-Terry-Luce model fastest-mixing Markov chain Joulin-Ollivier curvature concentration
Closest papers by meaning
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.86)
- Elo Uncovered: Robustness and Best Practices in Language Model Evaluation (NeurIPS 2024 · similarity 0.84)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.84)
- Foundations of the Theory of Performance-Based Ranking (CVPR 2025 · similarity 0.84)
- Sampling for Beyond-Worst-Case Online Ranking (AAAI 2024 · similarity 0.83)
- Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.