An Analysis of Elo Rating Systems via Markov Chains
Authors: Sam Olesker-Taylor
Luca Zanetti
Venue: NeurIPS 2024 poster (2024)
Keywords: Elo ratings
Bradley–Terry–Luce model
tournament design
concentration
Primary area: probabilistic_methods
TL;DR: We present an analysis of Elo rating systems under the Bradley–Terry–Luce model

Abstract: We present a theoretical analysis of the Elo rating system, a popular method for ranking skills of players in an online setting. In particular, we study Elo under the Bradley-Terry-Luce model and, using techniques from Markov chain theory, show that Elo learns the model parameters at a rate competitive with the state-of-the-art. We apply our results to the problem of efficient tournament design and discuss a connection with the fastest-mixing Markov chain problem.

An Analysis of Elo Rating Systems via Markov Chains
Sam Plesker-Taylor Department of Statistics University of Warwick Coventry, CV4 7AL, UK sam. taleekee-tayyyoorrraraac
Luca Zanetti
Department of Mathematical Sciences University of Bath Bath, BA2 7AY, UK 1z20408bath ac. uk
Abstract
We present a theoretical analysis of the Elo rating system, a popular method for ranking skills of players in online setting. In particular, we study Elo under the Seadley-Terry-Luce
model and, using techniques from Markov chain theory, show that Elo learns the model parameters at rate competitive with the state of the art. We apply our results to the problem of efficient tournament design and discuss a connection with the fastest-mixing Markov chain problem.
Introduction
The Elo rating system is a popular method for calculating the relative skills of players (or teams) in sports analytics and particularly chess 22] 1 3. It is based simple zero-sum update rule: if player i beats player j. then the rating of player increases proportionally to the model probability that would lose to j. while the rating of decreases by the same amount. This amount depends on the previously estimated difference in skills between and j.
Despite their widespread popularity, Elo rating systems still lack rigorous theoretical understand- ing (6) Here, we take a probabilistic approach and study Elo under the
Gradley-Terry
Luce model (BTL) [II 28). In this model, the probability Pij that wins against j is w;/ + wy). where wy is the strength of player k. In Elo, this is usually reparametrised via wi = cpk:
Pt. = e /ee + + 1/(1 + el: = (pp - -P);
where Pk is the true rating and (2)) == 1/(1 + exp((=2) for 2 R the sigmoid function. In this setting, after observing i beat the corresponding Elo ratings I; and x updated
+ n - x;)) and Ij +- J n x..)
where the step-size 77 > 0 is chosen by the modeller. The size of the update depends exponentially on the difference in ratings: beating a much lower rated opponent does not change the ratings much.
The goal of the Elo rating system is to estimate the true ratings of players by observing results of matches between pairs of players. is, therefore, aiming to solve the problem of ranking from pairwise comparisons. Compared with most algorithms in the area 5 20 27 37), however, Elo benefits from three qualities that help explain its popularity in real-world applications: simplicity, interpretability and the ability to update a ranking of the players in an online fashion.
The knowledgeable reader might have noticed that Elo's 's update rule is actually based on the gradient of the BTL log-likelihood Elo can be interpreted simply as stochastic gradient descent with fixed step-size. Rather than studying Elo from convex optimisation angle, however, we take more probabilistic point of view: we assume at each time f, players i and j are selected to play against one another with probability 96.j- This allows us interpret Elo Markov chain over R and deploy powerful tools to study its behaviour. On the other hand, this approach also presents us with some challenges: Elo is not reversible Markov chain and, while it has unique stationary distribution, assuming a minor and natural condition on (g.,)) J.g (7), it does not converge to it in total variation [6].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1
Our Results
shows that Elo ratings, averaged over time, well-approximate the true ratings of the players with high probability. In order avoid the potential of unbounded ratings, which are unrealistic in practice, we consider a variant of Elo in which ratings are capped, whilst maintaining their zero-sum property. We obtain rates of convergence with respect the number of observed matches that are competitive against the state of the art in the BTL literature. In contrast most other algorithms for the BTL model studied in the literature, Elo learns the parameters of BTL model in an online fashion. These rates of convergence is remarkable since Elo was originally conceived as simple ranking system for chess players. Furthermore, our approach is very robust, and also applies to a parallel spt-up in which multiple games are played concurrently.
Our main contribution (Theorem 2.5
We also discuss the problem of tournament design: assume are given tournament (compari- son) graph = ([n], E), and we would like to choose the match-up probabilities (t.)) (E.)) so that Elo's convergence rate is maximised. We highlight connection between this problem and that of finding the fastest mixing Markov chain on G [10) 39). where the corresponding Markov chain on the graph is either in discrete continuous time depending
whether optimise number of games or parallel rounds, respectively, As far as we know, this connection has not been made formally before in the sequential set-up, and both the analysis and optimisation of the parallel set-up are new. In $4 we also provide experimental results that showcase the usefulness of our strategy.
1.2 Related Work
Despite Elo ratings being the standard ranking system in many sports analytics communities (38) there is a scarcity of work analysing Elo from a probabilistic perspective. In particular, we are aware only of (). and the unpublished notes 7 by the same author, in which Elo is studied Markov process and convergence in distribution to a unique stationary distribution is proved.
If we consider Elo technique to estimate the parameters of the BTL model, there is wealth of recent literature on the topic by the machine learning community 220 37 31 51 27,9) 9. In contrast to setting, however, previous work typically considers offline scenario, in which the ratings of the players are computed after all the scheduled matches have taken place. By standard concentration inequalities, this allows one to obtain very good approximation of the probability player wins against their neighbours in the comparison graph. The goal is then to deduce a global ranking of the players from such (very good) local information. In our setting, Elo ratings dynamically updated hefore a good local approximation is achieved, which makes the analysis more challenging and requires the use of powerful, but delicate, concentration inequalities for Markov chains.
comparison between the rate of convergence for Elo ratings obtained in our work and the rate of convergence of other algorithms for the BTL model is discussed in 2
Finally, we mention that the connection between Markov chains and stochastic gradient descent with fixed step size has been studied before, e.g., in 17
2 Convergence Rates of Elo Ratings
In this section, we state our main result on the convergence rate of the time-averaged Elo ratings, discuss related work and outline the most important parts of the proof.
Throughout the paper, "f S gg means "f =Og)", "f < g" means "f= olg)" and "whp" means "with probability 1 - that X n.
the notation Ô(-) hides logarithmic factors; finally, [x[[] indicates
2.1 Our Results
We start with the explicit definition of our Markov chain.
Definition 2.1 (Elo Process). Let M E IR and n 2 2. Let E [-M, MJ" with Ee Pk = 0. Let g be a distribution on unordered pairs in [m]. Let E (0, 1). A step of Elow (g, (..))) proceeds as follows.
0. Suppose that the current vector of ratings is R

---

1. Choose unordered pair J} to play according to q:
P[ [i.j}] {(.) for all i, E [n].
2. Suppose that Player / beats J, which has probability a a pJ). Update ratings 2 and zy;
ry 21 + na(s_ 21); IJ f zJ n0 (z) 11).
3. Orthogonally project the full vector of ratings to | M, M\" n f E E Σx 2/. = 0}.
Let X denote the rating of Player i at time t. and π the equilibrium distribution R". Denote by
ALT -IT-' X for k E [x] and t, T
the time-averaged ratings. We typically start from X (0, ..., 0). The (deterministic) time T is a burn-in phase, which allows the Elo ratings to get 'near' the true skills, after which we start averaging.
Remark 2.2. The projection step ensures the Elo ratings do not become too large. is required for our analysis, but not usually implemented in practice. Indeed, our experiments, discussed in $ suggest that, as long as the step-size 1j is small enough, Elo ratings remain bounded. Algorithms which estimate BTL parameters typically require some sort of projection [20 or regularisation [27]. A simple and efficient algorithm to realise the orthogonal projection is presented in the Appendix.
We show, for a suitable choice of parameters f, T and 1j, that the time-averages are concentrated around the true ratings. In other words, we can use Elo to obtain an MCMC estimate of the true ratings.
Elo ratings in equilibrium are, in general, a biased estimator of the true ratings: i.e., E [X]] + Pk- Hence, there will be both bias and an error term in our MCMC-type estimate of || pll2-
The MCMC convergence rate depends on a spectral gap Ag- This parameter quantifies how fast local information about the relative strengths of two players is propagated to the rest of the ratings. Similar parameters appear in most of the related literature, c.g., [37 227]
Definition 2.3 (Spectral Gap). Let q be distribution unordered pairs in [n]] Define qi.j U(5+} d,j = 1i j} Σx 9i,k and A., == da qú for i,j E [m]] Let X, denote the spectral gap (second smallest eigenvalue) of the Laplacian A. Always, A1 = O and is positive semi-definite.
Remark 2.4. Equivalently, Xg is the spectral gap of the continuous- time Markov chain on [r]] with transition rates qt,j = 9/t,' for i E [n]. Note the scaling: Σi, Pi,j 2. So, the typical time until the continuous-tinn time chain jumps is order n, not order 1. This implies X, I 4/ n; see Lemma B.2
We assume A₂ > 0. This holds unless there exists a non-empty subset S Σ [n] with Eiesies $5 0-i.e., players in S never play those in S This makes estimation of the ratings impossible.
Our main result measures the disparity between the time-averaged Elo ratings and the true ratings.
Theorem 2.5 (Convergence Rate). Let X Elow (q. p; 1)), as in Definition 2.1 Then, there exists constant Co. depending only on (C1, C2). such that if
Let C1 C2 < co.
min n, L/t} 2 n C1 and min(t,T} 2 Cot., where t, 2M, 11 -1 ;,g' log
then
CoEtMs (1+ n
(log (bgg))² Aat
)
P 1 |1A - 212 < Agn
2 1 - Cs
In particular, if x (logn) n)2((Att). then
AM (log n)
1
- - pl1 S
whp
as
+ 00.
Agm
Remark 2.6. Ideally, = [2(1); e.g., if is uniform over the edges of an expander graph, then Agn In this case, we view (logn)?/(AAn)
Õ(1) as the error's pre-factor and 1/()ttt as the (squared) convergence rate. Also, we can then choose 7 = Ộ(1) and obtain non-trivial convergence results. This choice of 1) is comparable to that used in practice. Moreover, average, only Ó(1) games per player are need to be observed to guarantee good approximation of the ratings.
The yy term arises from the average bias n Ex-= [X] which is non-zero in general. An estimate on the average variance 1 Σn Varx [Xx] is necessary to obtain the MCMC convergence rate.
3

---

Theorem 2.7 (Bias and Variance). If π is the equilibrium distribution of Elo (q. p:n), then
+ -x pll 4e 4etM (hp2)) and 1/4 Ex Varx [Xx] 4e
2 n/ (Agm).
Despite Elo ratings being biased, the estimated probability a player wins their next match is not: Eje(n) 9h (o X,)l Sj (p Pÿ) for all i [n].
This holds when no projection step is performed part of the Elo update (equivalently, M == +oo).
The mixing time more delicate, as the chain makes deterministic-size discrete jumps, but its cquilibrium distribution is continuous and, therefore, the chain does not converge in total variation. Instead, we measure convergence in the Wasserstein, also known as transportation, distance.
Theorem 2.8 (Contraction).. If X, Y EloM (q, 1)) then there exists a step-by-step coupling with ( (Ilx Y S (1 = -112 where k= g -2M n1
2M
Markov chains satisfying the contraction property (i.e., positively curved) satisfy powerful concentra- tion inequalities, developed particularly by Joulin and Ollivier [22
24 The idea is that if ||X 1 = Do, then D == | "1I22 is small when = K log D For us, D < n,n, leading to 6, X K log n. In the reversible case, this can provide bounds, e.g., on the spectral gap.
23
34
33
The approach is particularly applicable to Markov chains on finite metric spaces, such as graphs. The set-up of finite graphs was analysed by Bubley and Dyer [12] under the name path coupling. In this
case, TE [ < ] 2 implies PP P[X = Y 2 2. since the minimum graph distance between x + y is 1.
Our underlying metric space is (IR", I12). however. Inequalities for this more general set-up have been developed, but they often give weaker bounds. our case, they lose a factor 1/(1>x, X the convergence rate. Morally, though, the exponential convergence at rate still implies that 1/x is the correct timescale for mixing and concentration, perhaps up to some logarithmic factors. Establishing this rigorously is the most challenging part of our work from a technical point of view.
2.2 Comparison with Related Work
In this section, compare the convergence rate of Elo given by Theorem 2.5 against the state of the art for BTL estimation. We highlight, once again, that previous work focusses on the problem of offline estimation, whilst Elo works in the more challenging online setting. Nevertheless, Elo is able to match the state-of-the-ar algorithms in the offline setting for wide range of parameters.
Our results imply that Elo provides estimator أ of p with I p1l 3 S c (log (logn)² n)²/(23 /(2)t) whp. This matches, up to a log factor, the results by Hajek, Oh and Xu [20]. who prove that the MLE constrained on M, MI"
R" Σn Zg 0), PMI.C. satisfies | The dependency on X, has been improved by Shah, Balakrishnan and Bradley (37 who show l| - 2| S ne &M log (Agt)) Since n/ 2 1/4, this is at least as good as our result, and potentially better for certain choices of q. However, up log factors, q corresponds to sampling edges of an expander graph-ea e.g., a complete graph, or an Erdōs-Rényi graph with parameter p > (logn)/n. n.. Our result improves the constant in front of M.
< e log n/ (A]t).
result matches theirs when
More recently, Li, Shrotriya and Rinaldo [27 proved a regularised version of the MLE, PMER, achieves ||PLER - = S 22 (2)()), where ö is the ratio between the maximum and average degree of the comparison graph G = [[m). F)) with F = ( 96. 0} and ME = max
lp: Pg] < 2 max; lpxl. A version of our analysis also applies with ME. instead of M, but we are not able to prove max., >>
X X11 Me + holds for polynomially long. Notice that their result is weaker when the comparison graph is relatively sparse but has a few high degree nodes. Moreover, they require each player to play the same number of matches; i.e., li, = 1/|E| for [ E E. Both limitations are particularly problematic in the context of tournament design discussed in O On the other hand, they obtain for error bounds too. We refer to 27 for further discussion of previous work.
2.3 Outline of Proof
We now highlight the key steps in estimating the MCMC-type error ; || - -pli in Theorem 2.5 where ArT is the t-step time average of the ratings X after a burn-in phase of length T. We use
- -lll
1A
E, |x + E, [x pll2

---

bounding these error and bias terms separately, via Theorems 2.8 and 2.7 respectively. Their proofs rely on estimating the change in l norm a single step, and using the Lipschitz property of the sigmoid function o, along with some other careful manipulations. The full proofs are given in the appendix.
The primary challenge is to leverage the positive curvature result of Theorem 2.8 to deduce the required concentration inequality in Theorem 2.5 As noted at the end of $2.1 positive curvature is well-suited to this goal. but the specifics of our set-up cause significant diffieulties. Particularly, the aforementioned results reliant only on curvature are not sufficiently strong for our purposes.
A further complication is that Elo is non-reversible Markov chain. There is general understanding, or perhaps belief, in the MCMC community that non-reversibility can improve concentration results. This has lead to many strategies being proposed, such non-backinn conbbacktracking lifting, zig-zag; see, g 25 Even an alternative definition of the spectral gap has been proposed [13] this gap controls convergence of empirical averages, rather than convergence equilibrium.
e.g. 14 16
30
Unfortunately, the majority of general concentration results based on spectral properties [9] 26
35 36] are actually worse in the non-reversible set-up: they bound the convergence rates by those of the multiplicative or additive reversibilisation. These can be hard to estimate, needing detailed knowledge of the equilibrium distribution, and the resulting bounds are often crude.
Finally, we mention that bounds on the total-variation mixing time can be leveraged to provide concentration bounds; see, particularly, [T5 33). However, Elo does not converge in total variation! Indeed, X finitely supported, on most (2n)* states, given X but ' is continuous. These (2n) states can be used to distinguish X and x. Nevertheless, is this mixing-time approach that we adapt.
The contraction property implies that realisations X and Y can be coupled so that their expected relative distance decreases exponentially, with rate K. This is ideal for using the coupling approach to mixing. However, it not possible to guarantee that X Y some point, due the chain's 's finite support. Instead, we analyse noisy version: after each update, some (continuous) noise is added to the ratings. This must be added carefully to preserve the contraction in Theorem 2.8
Denote the noisy versions U and V. Once U and V are sufficiently close, the additive noise can be used to couple them exactly, to get U Vt. The size of the noise must be balanced: too small and this final coupling step is too difficult; too big and U can no longer be compared with X.
We delve deeper into this noisy approximation, explaining what noise to add, how it accumulates and what the resulting mixing time is. The interaction of the noise with the projection step is delicate and technical; we omit it from the description here, but it should be kept in the back of the mind.
Noisy Version & Error. We consider the following noisy version U of the Elo process X. Let > 0.
1. Draw U++1/2 according to an uncapped Elo step started from ie., as if M co. Suppose that Players and j were chosen-i.e., {k U + U = (i,j).
2. Draw Ü,, Ü, and jid Unif([-Vā +vō)) independently and set Ug = 0 for & & {i.j}. Set
U = 1/21/2 + Uh for k E [m].
This does not preserve the zero-sum property, as the additive noise is independent. The independence is crucial later to allow two version to coalesce. We need to control the cumulation until that point.
We control the difference between X and U via the natural coupling: pick the same pair of players to play, and observe the same result; sample the noise independently. Careful computation gives
| u1 1|1 S || 1 + 2V8 || - U²I11 +/8 < ... 21V5.
The second inequality actually says that Elo is non-negatively curved in &,. Iterating this,
|l -E=Ixx x - U
S t 1. |X U S tv8 deterministically.
A
Curvature. We the natural coupling between two noisy versions U and V: choose the same players, observe the same result and add the same noise. Then, there is still rate-K contraction:
E. v [||U]] 1 V [12 < E vo 1/2 1/2 [2] < (1 k)]lu² - -
A
5

---

Mixing Time. We bound the total-variation mixing time of the noisy chain via the coupling method:
Po [U E :] Po [V' E -JllT S (wo L + V-J.
First, we burn-in using the natural coupling, then use a new coupling which exploits the noise.
We start with the natural coupling as given above. Using the rate-k curvature.
EII|U* [l2l s (1 - x) 12112 - 2M nt 8² if 2 is = = log 1og(2Mn/88).
Hence,
P PI||" - - 6) S P(| - V' 12 8) I if t t2ts.
Once the absolute difference - - V are at most for all k; the additive noise, which order vo, dominates the change in difference after single Elo step, which is order 5. Thus, with complementrry probability order 8/vō = Vo, we can couple the noise that the rating of a player the same in both U and in V after they play a game. Moreover, such a successful step preserves the foo bound of 8.
The L bound implies that all players chosen within ts steps with probability least 1 - 8. Hence, the probability of not successfully matching all ratings after t. steps is at most order 5 + Vöts-
Combining these two bounds gives a bound of order 8 + vota on the taral-variation distance at time 2tg. The polynomial growth/decay assumptions in the theorem allow us choose be an appropriate inverse polynomial (in n) and obtain Vot. << and Lg = K -1 log n
4. A
The above mixing-time time bound allows us to establish concentration of time- averages of the noisy Elo ratings, using results from [35. Particularly, under certain assumptions, if Z is a Markov chain with equilibrium distribution and mixing time l,, then
- log Px [|+ E:= f(z") - 2 <) ž 2t/tt
where vr = [/] and oj = [/]= Notice that this requires 7 ~ which we do not impose; this requirement can be circumnavigated by using a burn-in, again comparing with a noisy version.
We want to take f == fu to be the projection onto the k-th coordinate, which is the k-th player's rating, for each k then do a union bound over the n players. This motivates taking
fe 1 log n
1) log n log
1 (logn)²
which satisfies 1 E
Agm Az9l
Ag Aat
using Theorem 2.7 This is the decay rate required in Theorem
2.5 but for the noisy version.
We need to compare the noisy version with the original. We do this via the estimate established earlier:
| x- - U* E X - U S tvō deterministically.
We are taking / to be polynomial in n, and can choose 8-1 to be sufficiently large polynomial so that this accumulated error small. Care must be taken to make all this rigorous, but once is done, we are able to deduce the concentration result for the original Elo process.
3 Tournament Design
3.1 Our Results
In this section, we assume we are given a comparison graph G = ([n), E), where edge [i.j} E E indicates that Players and j are able play against one another. We want construct distribution over edges E of G so that Elo can most efficiently approximate the true ratings of the players.
The decay rate in Theorem 2.5 is governed by the spectral gap Ay. So, want to maximise Ag. Let
A : sup Ag q E 1] EEEE ge = 1].
This equals the largest spectral gap achievable by a continuous-time Markov chain on [M] with transitions only across edges of G and average jump-rate 1/n. It is the fastesi-mixing Markov chain problem, introduced by Sun et [39], and can be formulated as semidefinite program. Olesker- Taylor and Zanetti [32] recently proved that Aagn 2 1/ (diiam G This implics the following.

---

Corollary 3.1 (Optimised g). Suppose that the comparison graph G = ([m), is given. In the set-up of Theorem 2.5 there exists a distribution q on the edges E such that
+ 1 p11 - S n(diam (log ()2lg)))// whp if n n n(diam (logg)))
This choice of probabilities
improve drastically over uniform weights as used by 277. E.g. if G consists of two cliques connected by edges, then An S k/n2 when qe == 1/| is uniform over E, whilst the optimal n x [32]. As a consequence, with the optimal choice of q. only ((n) total matches need to played obtain good approximation of the true ratings, compared with O(n"/k) for uniform q. Here, Ó-)) indicates the asymptotic order up to logarithmic factors. This demonstrates the power of being able to choose given G.
Elo naturally parallelises: if two games consist of disjoint pairs of players, then the Elo update resulting from one independent of the result the other. Hence, if we wish to minimise the number of rounds (i..., sets of games that be played in parallel). rather than games, should consider distribution on the set M of matchings of the graph G = ([z)), E)-ie,. collections of disjoint edges.
Definition 3.2 (Parallel Elo). Let y be a distribution on .M. single step ParElo (7, P; 7)) first selects matching S C E according q and applies the Elo update (with scale 17) to each pair in S. Then, the resulting vector is orthogonally projected back to zero-sum vectors in -M,, +M]".
Our analysis is robust enough to handle the parallel case, obtaining convergence rate 1/tt,t), where now Ze is the marginal probability that edge E E appears in the matching:
le = EsEMEeS 4s.
Theorem 3.3 (Parallel), Let X ParEloys p:n). Then, under the conditions of Theorem 2.5
e4M (logn)² 1
whp if 17 x (logn)) n1)
1| - pl Agn/N
Ayt
Ayt
where N = EoEE le is the mean size of the matching. To emphusise, here, l. and T count rounds. Remark 3.4. It can be shown that this factor N is needed in the pre-factor via a time-change analysis. It is natural to optimise X, over & which can arise as the marginals of a distribution on M. Clearly,
= EeEBikEe ge S for all I E [n]]
for any such q. Thus, the matrix Q = (Kij)ijev is substochastic, so X, corresponds to the spectral gap of the discrete-time Markov chain on G = ([r),, E) with weights q.j Q(.j)- Let
Muse = sup q E [0, 1 max4e(<) 9: 1).
This is the optimal spectral gap of a discrete-time Markov chain on [n] with transitions allowed only across edges G and uniform stationary distribution. Again, Xasse can be formulated semidefinite program I00 and is related to the vertex conductance via Cheeger-type inequality [32]
We show that distribution & matchings with Ag 2 3 Xise can be found by decomposing the substochastic Q into a convex combination permutation matrices using the Trrkhoff-von-Neuree theorem, followed by decomposing each permutation into disjoint cycles.
Corollary 3.5 (Optimised Φ) Suppose that the comparison graph G ([n), E) is given. In the set-up of Theorem 3.3 there exists a distribution q on matchings M such that
4M (log ni2 n/N
(logn)² Aiset
1A - 2l12
whp if =
In many examples, such as if G = ([n]. E) is an expander, but also if G is a cycle, then Xjice x A In this case, parallel Elo really is good, up constants, as steps of the original ('series") Elo. (Recall that = Σ. g. = is required for X but that N x n is possible for X
Other times, there is already continuous-time chain, with average jump-rate which has spectral gap order 1; e.g., two cliques connected by a single edge. this case, the optimal parallel version gives real improvement, even measured by rounds. over the optimally weighted series version.
7

---

3.2 Comparison with Related Work
The problem of designing an efficient tournament graph is related to active ranking [21. Active ranking, however, allows one to choose which matches to schedule next after observing the results of some matches. For example, Yan et [40] propose an algorithm to identify the most informative pair of players given previous outcomes, and obtain regret bounds between Elo and the true ratings when matchups are scheduled according to their algorithm. In contrast, we are interested in designing probability distribution over matches in an offline manner, without the possibility of changing such distribution after observing some results.
This problem has been considered by Li, Shrotriya and Rinaldo 227 conquer strategy that essentially requires oversampling edges across bottlenecks in the graph. The drawback of this strategy is that it requires partitioning the graph into well well-connected pieces, which is a non-trivial task itself. Furthermore, [27] does not provide explicit bounds on the sample complexity that can be obtained in this way, besides discussing a few examples where the bottleneck is known.
They discuss a divide-and-
Nonetheless, our approach shares some similarity with (27]: the fastest-mixing Markov chain implicitly up-weights edges across bottlenecks. The main advantage, however, is that it provides the optimal spectral gap allowed by graph topology, which is related to the diameter of the graph [32). Moreover, both Aus and Adise can be formulated as SDPs, for which fast (polynomial- time) solvers exist. We remark, however, that this construction might require certain nodes to play an overwhelmingly large number of matches: this would be problematic for the results of [27]. As far as we know, minimising the number of 'parallel rounds' has not been considered before.
Experimental Results
We close with discussion of some specific examples and experimental results. Additional experiments are discussed in the Appendix. We start by considering dumbbell tournament graphs consisting of two cliques of n/2 20 vertices connected by a matching of k E {1, 20) edges. For each graph, we perform Elo simulations where the match-ups between players are sampled according to the following probability distributions.
1. The uniform distribution qu over the edges of the graph.
2. The optimal sequential Tsg derived from the fastest-mixing continuous-time Markov chain.
3. The distribution over matchings qaar derived from the fastest mixing discrete-time Markov chain, where multiple games are played in parallel each round.
From $3
we know that Agu x k/n=, Xui 1/n and Xxe x <k/n.
We sample the true ratings of the players according to independent Gaussians, with mean equal to I on one clique, mean 2 on the other, and standard deviation equal to 0.2 in both. This difference in average ratings between cliques simulates a scenario where the two eliques correspond to two different leagues of slightly different strength on average.
We perform Elo simulations initialising the Elo ratings at zero and setting 17 0.1. For each graph. we repeat each experiment ten times, each time sampling new true ratings. Experimental results are displayed in Figures [ and 2 Simulations are repeated ten times: lines correspond to the average lz f2-distance between time-averaged Elo ratings and the true ratings, divided by the number of players (n = 40). Shaded regions corresponds to 25-75 percentile over these ten trials. Cyan and blue lines correspond to the same experiments where we have sampled multiple games in parallel as described in }3} we display the decay of error wrt the total number of games played in cyan and wrt the number of parallel rounds in blue. The blue line is solid for the first 2- 10 games (same number of games displayed in cyan).
We display the experimental results for A = 1, i.c., two cliques of 20 vertices connected by a single edge, in Figure The experiments align with the theoretical results of }3) when 1, the spectral gap Xy,, of the optimal sequential distribution is of the same order of the spectral gap for our nearly parallel construction ADy Indeed, if convergence is measured wrt the number of rounds, the two corresponding errors seems to decay at a similar same rate, with the parallel version being slightly better, but requiring more than ten times the total number of games. As predicted by the theory, both distributions result in much faster convergence than the uniform distribution. If we measure the total
8

---

0.35
0.30
optinall sequerrid
unifrrm
0.30
paralle games
6.25
0.25
0.20
0.20
6.15
6.0
uniform
3.05
optimal sequandal
0.00
game:
9.03
parallel rourds
0.00
10000 12300
15000
number garnenhounds
number gammarrtunds
Figure 1: Elo simulation results for dumbbell graph with one edge between two cliques of 20 vertices. Match-ups sampled from three dif- ferent probability distributions.
Figure 2: Elo simulation results for dumbbell graph with a perfect matching of 20 edges be- tween two cliques of 20 vertices.
number games rather than rounds, the parallel version still results in a faster convergence than the uniform distribution, but not overwhelmingly so.
We now consider dumbbell graph with k: n/2,, i.e., cliques connected by perfect matching. In this case, the fastest discrete- and continuous-time Markov chains have the same order-1 spectral gap. However, since the spectral gap for sequential Elo is then rescaled by factor of 1/n,, to achieve convergence, we expect the number of rounds for the parallel version to be much smaller than the number of games required by the sequential one; convergence should instead happen the same rate when measured in the total number of games. This is clearly shown in Figure 2 The uniform distribution performs much worse, which we would expect from its order- 1/nr spectral gap. In the optimal parallel and sequential distributions, the probability to sample an edge from the bottleneck or from inside the cliques balanced, while the uniform distribution oversamples edges inside the cliques. Experiments for the intermediate case of l E (5, 10) are discussed in the Appendix.
We end this section by discussing experimental results concerning the maximum rating reached by Elo. Figure 3 displays the behaviour of the largest Elo rating in absolute value, where pairs of players are selected uniformly at random (i.e., the underlying graph is complete graph). The true ratings are sampled uniformly random in [],, The initial Elo ratings are set equal to zero. We simulate up to 50000 matches for number of players that goes from 100 to 1000. We observe that the maximum rating is always below 1.75, corroborating our belief that, in many scenarios, the maximum Elo rating does not di- verge for a long time. Further experiments and discussions are given the Appendix.
1.75
1.29
1.00
0.50
m=500
1-1000
10000
200001
30:000
40000
50000
numbor of games
Figure Largest Elo rating absolute value for a complete graph of varying size. True ratings are uniformly distributed [-1,
Conclusion and Open Problems
Our work is first step towards establishing the theoretical foundations of the Elo rating system, popular ranking method in sports analytics. In particular, our main contribution an analysis of Elo under the BTL model, establishing convergence results competitive with the state of the art.
There are several questions prompted by our work. First, from a technical point of view, we would like to control the maximal Elo rating. This is necessary to understand when we can remove the projection step in our definition of the Elo Markov chain, and make our theoretical results more aligned with practice.

---

Moreover, we would like to better understand the shape of the stationary distribution of Elo. This could help us, for example, obtain bounds on the rate of convergence in ex0
Finally, touted strength of the Elo rating system practical applications is its ability to dynamically update the ratings in response changes in players' skills. Can model these changes in way that allows us to prove Elo can keep track of them, and bound the corresponding mean squared error? Such questions are often studied in the statistics literature; see, e.g., the recent paper [18] for details.
References
[1] ATP Elo ratings (lennisabstrrat..com) ratings. html
[2] Elo Rating System (chess.com). http::///www...sssscccccm//////a
[3] Introducing NFL Elo Ratings (fivethirtyeight.coom) htapsureee-atcoocccccggg--------
https://fiveehhityyeihhtt
[4] World Football Elo Ratings, https://ww..eorrtiimn net/
[5] Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 70-79. PMLR, 10-15 Jul 2018.
[6] David Aldous. Elo ratings and the sports model: A neglected topic in applied probability? Statistical Science, 32(4):616-629, 2017.
[7] David Aldous. Mathematical probability foundations of dynamic sports ratings. Draft, January 2017.
[8] Simon Apers, Francesco Ticozzi, and Alain Sarlette. Lifting markov chains to mix faster: Limits and opportunities. arXiv: / 705. 082533 [math], May 2017.
(9] Heejong Bong and Alessandro Rinaldo. Generalized results for the existence and consistency of the MLE in the bradley-terry-luc model. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 2160-2177. PMLR, 2022.
[10] Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM Review, 46(4):667-689, 2004.
[11] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs. The method of paired comparisons. Biometrika, 39:324-345, 1952.
[12] Ross Bubley and Martin Dyer. Path coupling: A technique for proving rapid mixing in markov chains. In Proceedings of the 38th Anmual Symposium on Foundations of Computer Science, FOCS '97, pages 223-, Washington, DC, USA, 1997. IEEE Computer Society.
[13] Sourav Chatterjee. Spectral gap of nonreversible markov chains. a0X1 [math], October 2023.
[14] Fang Chen, László Lovász, and Igor Pak. Lifting markov chains to speed up mixing. In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), page 275-281, ACM, New York, 1999.
[15] Kai-Min Chung, Henry Lam, Zhemming Liu, and Michael Mitzenmacher. bounds for markov chains: Generalized and simplified. In 29th International Symposium on Theoretical Aspects of Computer Science, volume 14 of L/Plcs. Leibniz Int. Proc. Inform., page 124-135. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2012.
[16) Persi Diaconis, Susan Holmes, and Radford M. Neal. Analysis of a nonreversible markov chain sampler. Annals of Applied Probability, 10(3):726-552, 2000.
10

---

[17] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. Ann. Statist., 48(3):1348-13383 2020.
[18] Samuel Duffield, Samuel Power, and Lorenzo Rimella, Space Perspective on Modelling and Inference for Online Skill Rating, September 2023.
[19] David Gillman. A chernoff bound for random walks on expander graphs. SIAM J. Comput., 12:3):2222-2200 1998.
[20] Bruce Hajek, Sewoong Oh, and Jiaming Xu. Minimax-optimal inference from partial rankings. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[21] Reinhard Heckel, Nihar B. Shah, Kannan Ramchandran, and Martin J. Wainwright. Active ranking from pairwise comparisons and when parametric assumptions do not help. Ann. Statist., 47(6):3099-3126, 2019.
[22] Aldéric Joulin. Poisson-type deviation inequalities for curved continuous-tine time markov chains. Bernoulli, Official Journal of the Bernoulli Society for Mathematical Statistics and Probability, 13(3):782-798, 2007.
[23] Aldéric Joulin. A new poisson-type deviation inequality for markov jump processes with positive wasserstein curvature. Bernoulli. Official Journal of the Bernoulli Society for Mathematical Statistics and Probability, 15(2):532-555 559, 2009.
[24] Aldéric Joulin and Yann Ollivier. Curvature, concentration and error estimates for markov chain monte carlo. Annals of Probability, 38(6):2418-244) 2010.
[25] Jere Koskela. Zig-zag sampling for discrete structures and nonreversible phylogenetic meme. Journal of Computational and Graphical Sutistics,, (386666646 2022.
[26] Pascal Lezaud. Chernoff and in Applied and Industrial Mathematics, 5:183-201 2001.
inequalities for markov processes. European Series
[27] Wanshan Li, Shamindra Shrotriya, and Alessandro Rinaldo. -bounds of the mle in the btl model under general comparison graphs. James Cussens and Kun Zhang, editors, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, page 1178-1187. PMLR, 2022.
[28] R. Duncan Luce. Individual choice behavior: A theoretical analysis. John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1959.
[29] Math Stack Exchange. Projections Onto Convex Sets Decrease Distances in Hilbert Spaces. Mathematics Stack Exchange.
[30] Radford M. Neal. Improving asymptotic variance of meme estimators: Non-reversible chains are better. arXiv: 0407281 [math], July 2004.
[31] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266-25) 287, 2017.
[32] Sam Olesker Olesker-Taylor and Luca Zanetti. Geometric bounds on the fastest mixing markov chain. In Mark Braverman, editor, 13th Innovations in Theoreticul Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings Informatics (LIPIcs), page 109:1-109:1, Dagstuhl, Germany, January 2022. Schloss Dagstuhl Leibniz-7entrru für Informatik.
[33] Yann Ollivier. Ricci curvature of metric spaces. Comptes Rendus Mathematique, Academie des Sciences. Paris, (55(11):6443664) 2007.
[34] Yann Ollivier. Ricci curvature of markov chains metric spaces. Journal of Functional Analysis, 256()):810-866 2009.
[35] Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20:no. 79, 32, 2015.

---

[36] Daniel Paulin. Mixing and concentration by ricci curvature. Journal of Functional Analysis, 27065):1633-166,, 2016.
[37] Nihar Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin Wainwright. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 856-865, San Diego, California, USA, 09-12 May 2015. PMLR.
[38] Ray Stefani. The methodology of officially recognized international sports rating systems. Journal of Quantitative Analysis in Sports, 7(4), 2011.
[39] Jun Sun, Stephen Boyd, Lin Xiao, and Persi Diaconis. The fastest mixing markov process on graph and connection to maximum variance unfolding problem. SIAM Review, 48(4):681-69) 1-99, 2006.
[40] Xue Yan, Yali Du, Binxin Ru, Jun Wang, Haifeng Zhang, and Xu Chen. Learning to identify top Elo ratings: dueling bandits approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8797-8805, 2022.
12

---

A Experiments: Further Discussion and Figures
In this appendix we discuss additional experimental results. Code for our experiments is included in the supplementary material.
In Figure 4 we display further experiments related dumbbell graphs. In particular, consider
graphs consisting of two cliques of 20 vertices connected by (left) and 10 (right) edges arranged in matching. The experimental setup is the same the discussed in 4 Notice how, the more edges are added to the bottleneck, the better the distribution optimised for parallel rounds performs. The optimal sequential distribution, instead, performs roughly the same: adding edges in the bottleneck doesn't It really improve its spectral gap, which depends mainly on the (unchanged) diameter.
spdiral resuendal
Aptiral resuMIds!
caral parroo
paraBal guIrAs D1 FoLndh
Lorol rounds
0.15
0.39
2000
70:00
10000
12500
15000
17500 20003
5902
30000 12:00 15000 17500 20000 number gamoreoands
rumber gemoiir.rdd
Figure 4: Elo simulation results for dumbbell graphs with h: 5 (left) and l = 10 (right) edges between two cliques of 20 vertices.
We also consider a pyramidal graph, which is constructed as follows. We first sample three Erdós- Rényi random graphs with size, resp., n2 64, n2 32 and n3 16, and density p 1/2. We then connect the first graph to the second and the second to the third with two sparse cuts (see Figure ( This graph is constructed loosely resemble the pyramidal structure of, e.g., national sport leagues.
We conduct Elo simulations with the same set-up as for dumbbell graphs discussed earlier. In particular, repeat the simulations times, resampling each time the players' true ratings. The true ratings are sampled as follows: independent normal distributions of standard deviation 0.2 and mean 0 for the Erdös Frdōs-Rééyí the bottom of the pyramid, mean for the Erdös-Rényi in the middle,
0.5
0.2
sptmal secuential
para games
lel rounds
1500
5000
7500
15000
12500 15000 17500 20000
number
Figure 6: Elo simulation results for the pyramidal graph.
Figure 5: Schematic representation of the pyra- midal graph.
13

---

and mean 2 for the one at the top. This is, again, to loosely simulate the fact that sport leagues are characterised by stronger players/teams towards the top of the pyramid, Experimental results are shown in Figure In particular, we observe that the rate of converge for the uniform distribution is much slower than for the optimal sequential one. This is, again, predicted by the results of } the two bottlenecks slow down the convergence in the uniform case; while the small diameter assures faster convergence for the optimal distribution by Corollary 3.1 The distribution optimised for parallel Elo, instead, guarantees very fast convergence when measured according to the number of rounds.
In Figure 7 we display experimental results for topology corresponding to the giant component of an Erdós-Rényi random graph of n 100 vertices and density = 0.02. True ratings are distributed as independent standard Gaussians. This graph has reasonably good connectivity, so we expect the number of games required to converge to be roughly equal for all the sampling distributions considered, with a good scope for parallelisation. This is confirmed by the error plot. What is perhaps surprising is that the optimal sequential distribution actually performs slightly worse than the uniform one. This can be explained by the fact that the spectral gap measures the rate of convergence for the worst possible vector of ratings: if the ratings do not depend the topology of the graph, like in this example, the inverse of the spectral gap is an overtly pessimistic upper bound. Indeed, the optimal sequential distribution tends to oversample nodes that are in central position in the graph and undersample nodes at the periphery. This should make convergence faster because it allows faster movement of information between distant nodes, but in this specific example is not helpful: since ratings are sampled in a iid fashion, the faster movement of information globally is not very helpful and is upset by slower convergence for undersampled nodes.
ueeter
ms! sequentbl
10-
paralli games
3.-
366
0.6
02
30-
2500
3000
7503
2003E
32500
35000 17500 20200
Left: topology of the giant component of an Erdös-Rényi Rényi random graph of n = 100 vertices and density p = 0.02; edges are reweighed according the distribution corresponding the fastest mixing comtinuous-time Markov chain. Right: Elo simulation results for the same graph.
Figure 7:
We now present further experiments about the maximum Elo rating (in absolute value). Again, we sample true ratings independently and uniformly in [-1, 1). In Figure g we present experiments for path (left) and star (right) topology of varying size. In both cases, the largest Elo rating in absolute value remains smaller than twice the largest true rating. Notice that in the star graph the central node plays all the matches; this means the same player plays in total fifty-thousands matches without its value becoming particularly large.
Of course, these simulations are far from definitive: there are countless of ways in which to choose the true ratings and the graph topology. Our belief that these experiments are indicative of a more general behaviour is due to the peculiarities of the Elo rating systems. In particular, the Elo update offers diminishing returns: if the rating of i is relatively much larger than the rating of j. if i wins against j. the rating of won't increase by much. This is because the sigmoid function o approaches zero very fast.
Despite this, proving that the maximum rating cannot increase significantly appears much harder. This is due to the fact that the maximum rating is not a supermartingale: if all of the neighbours of the node i with largest true rating have abnormally large rating, the rating of i is likely to increase, no matter how large it already was. However, because the zero-sum property of the ratings, the neighbours of cannot maintain an abnormally large rating for too long. Indeed, it appears very unlikely that such balanced but "abnormal" configurations are ever reached.
14

---

1.50
125
1.23
nastuu
0.52
s2000
Figure 8: Behaviour of the largest Elo rating in absolute value for path (left) and star (right) graphs of varying size.
In the two-player case, the situation is simpler: if player has Elo rating 21, then player 2 has I2 = -21, by the zero-sum nature. It is straightforward to check that the Elo ratings are biased towards the true skills: that is, if player 1 has rating æ1 before game, then their rating x' after the game has [[[x=] - pıl] < 11 - P1l. if < 2.
Suppose that the same argument holds for 2 players: i.e. typically, Elo ratings are biased towards the true skills. Biased random walks on have exponential tails. So, if 1 < 1/ log n, then it is super-polynomially unlikely that given Elo rating will be more than 1 away from the corresponding true skill, in equilibrium. A union bound over the n players allows us to deduce that the maximum Elo rating is at most 1 more than the maximum true skill, with probability at least 1 - 1/n22
Unfortunately, we weren't 't able to make this argument formal for players. We leave proving that indeed, with high probability, the maximum rating remains small for large number of steps as an open problem.
B Convergence Proofs: Preliminaries
There are a few results which we use repeatedly throughout the proofs. We collect them here.
B.1 Dirichlet Characterisation of the Spectral Gap
Recall that Ag is the spectral gap of the continuous-time Markov chain on [n] with transition rates (gL))ade(n)- We repeatedly use the standard Dirichlet characterisation of the spectral gap. Proposition B.1 (Dirichlet Characterisation of the Spectral Gap). The spectral gap Xg satisfies
Xy 1 min Ense(w (, 2,)² /|
=ER (10%=111
In particular, for all I=" with Ex 2x O.
Enseti Al5(2 2z)² 22y 12111
Lemma B.2. Let Bod E j0, 1.1 all i,j E [m] with Eis Jr.t 2. Let Xi denote the spectral gap of the continuous-tine time Markov chain on [n]] with transition rates (g.))s.e(n)- Then,
Xg 2/(n 1) < 4/n.
Proof. We apply the Dirichlet characterisation (Proposition B.I with 2; = 1li k} 1 Then,
1, | (1 1/n)² (n 1)/n² = 1/n (n (n11//n
and 1 [.je 4. ((,=====)))))))) /111/11=113 Ei Ki (1fi = k) 1 - 11== n-
= _ (Ejsjtk 9k.t + Eista 9t.x) -²= Σ9 qk.e-
Choosing l to minimise this final sum gives Σe Ob. S 2 since the average 1 Ex Ee ak.t = n So.
A < -
2/(n - 4/n.
15

---

B.2 Capping the Ratings
Capping at +M has the benefit of restricting the process remains in a compact set. The disadvantage. though, is that the Elo update is more complicated. It also biases the process compared with the original. However, as we discuss in Remark C.2 below, the original process already biased in the sense that the expected rating in equílibrium is not the true rating: E=[x]] # p.
The only property of the projection that we use is the following monotonicity result. Proposition B.3 (Projection Monotonicity). Ler Ω S R" be closed, convex set. Define (a) arg min || 1e--at 2' for x E ER;
that is, Ug is the orthogonal projection to S2. Then,
[z] In S || vlla for all 2, R.yRR"
that is, (1) is al least as close to (Ts(()) as x is to y, in lz.
Versions of this result are well-known. An elementary proof can be found at (2)]. We apply this with Q = { R" ||]]||>> S M, Σσ Ta = 0}, which is convex. Our results apply whenever this monotonicity property holds.
The orthogonal projection [z(()) can be efficiently computed as follows. We first project to {y E R |lylloo I M). This can be done by simply replacing any x, < -M with -M and any T M with M. Let æ' be the resulting vector. Notice that x' might not satisfy the constraint Ex Jh = O: we need to subtract the displaced mass Σ, x' to the rest of the vector while minimising (z) = arg ming-een | r"ll2- Assume Σx FA > 0 (the symmetric case can be handled similarly). We set x"" = -M for all the coordinates such that z = -M and call i frozen. To minimise ||æ x" ||, we want to distribute - Σx x to the unfrozen coordinates so that xx is as balanced as possible in each coordinate (this can be imagined as a water-filling procedure). In doing so, however, we might make x -M for new, previously unfrozen, coordinate before we have subtracted all the displaced mass. If that happens, we simply freeze i and proceed in distributing the remaining displaced mass the unfrozen coordinates (until repeating the procedure since all the mass is allocated. Notice that we can allocate all the mass since we assumed Σn o O. Moreover, the procedure lasts most steps since each step we freeze new coordinate until we have completed constructing the desired vector.
coordinate is frozen). We keep
C Convergence Proofs: Bias and Variance
There is an inherent bias and variance in the Elo ratings. It would be natural assume that the expected value of a player's rating in equilibrium is equal to their real skill. After all, at least in the two-player case, an individual step is always biased towards the real skill. However, even for two players, this is not true. In this section, we quantify the bias and the variance in equilibrium.
Throughout this section and the next, we denote
(=)(2) == ofz - 2,) for ZER" and i, [m]]
In particular, (p) is the true probability that Player i beats j and p(. (x) is the model probability if the current ratings are æ. Additionally, we split up the Elo step into the update and the projection:
if the current vector is X then let x denote an uncapped step:
then, X IT [X where M is the orthogonal projection.
We do not quantify the bias and variance Slayer-by-player but rather average over all players.
Theorem C.1 (Bias and Variance; Theorem 2.7 The following bias and variance estimates hold:
E_ [ pl1
<
E [| - p1131 - 4M n/ Dogi
Σg Var, [ E+
x E, [ < 2 m/ >uy.
Proof: Bias. First and foremost, the
inequality gives
|| E, [X pll < [x[|Xx -l
16

---

We start the system from equilibrium and use stationarity: X ~ π - X ~ т. Also, we can ignore the projection step, whilst still assuming that all vectors have Eo norm at most M, due the
projection monotonicity of Proposition B.3 noting that l|ell I M, so aas = P. we have
| 2اl2 | (x!/2) TMM (p)ll2 - |x pll2-
Write Beg [1] to indicate that the pair {i chosen in the first step and x0 = x. Then,
(i,(( [[X 12 - p.)²] (()( - Ps + 7 (z)) + (1 - P.)(()))) (z: - P: - -n)))(z)) + (1 Pi.j (p) P.)()))))))
= =xx - pi)² + n²² (pt,) - (x)
+ - - (r.) (s. -P))
(1 p()(p)) Pt.j (z) (os - pi) (0)()
S (x)- - p;) +
pi).
An analogous statement holds for x py. with i and swapped:
E (e,(ss) [xx]/2 - -p;) (xy - 03)² + n²² - (n),) - Ps.( - pi) = =x pj)² + n² + 2n)(p,((z) (x) - Pr.j (p)( (z) -p)),
using the fact that p.,(()) = 1 - -...(.)).. For & & {i,j}.
(x,( (x//12 - px] = (Ik - pk)²
Bringing these three cases (indices k = = and k [n] \ {i.j)) together,
(i,i [||x p1:3 S || p1l + 21j² - 2n(pi, (x) - (p) ((04 - pi) - (2z - pj)) = || p1. + 21/² - 2n(pi Pt., (p)) ((1; - xz)) - (p: pj)).
Now, Pi, (x) - (p) = oex; - 2,) - -ppp - p.) and (z, - xz,) - (p: - -p,) have the same sign. Also,
(2)(()) - Pr.s(p) = aa - 2;) -2) - - (p:
2 min x E 1-4M,, 4M]lo'(2) ((x;- -2,)) - -pp:- 10:0-00 -p))
2 2M
4M [z:;
2y) - (p - -p}]
since zı, Pj, Pj E 1- M). so |(: x,) (p: -3)l s 4M and d'(z) = a(z)(1 o(2)).
Hence,
Eg [1|X1/2 - - S || - p + 27² _ 4M 7 (c: - xz)) - (pi -p))²
= || - p 27
4M n ((zz - p.) - -(03- - -p)))
2
We now average this over {i
Eg [|X] /2 p| S || - pl1 + 2n²² - _ 4M,
11 -MM
Eis 91.,)) ((x; - pi) (zz - -p;)1
Now, applying the Dirichlet characterisation of the spectral gap (Proposition B.1 with 2 = x p.
Eg [|xx 1/2 - p| S || - --13= + 2n)² - f ?>yl1= - 2l1 = (1 - _e= 4M n12))l - + -
again,
Σe 24 = Σx Fx - EE Ps = 0. In particular, stationarity implies that
E |||X 0 -|13] = E, |||X - 212 < E. 1/2 1/2 - pl < 4e 4M m/>g.
We perform very similar calculation when bounding the curvature; see Definition D.2
This is the
exponential contraction rate between a pair of systems X and Y. The (1 - Je 4M,
n
factor above
suggests curvature k x e -4M 11A, which is indeed what we show in Proposition D.4
We now turn to the variance, for which we use similar approach. It is little more technically challenging, using the slightly cumbersome law of total variance: for random variables A and B,
War B3] = [B Al] + Var[E[B
A]].
17

---

Proof: Variance. The sum of variances is the expectation of an Eg distance:
Σx Var[Ze] = Σx
R E [2 - [[ - E E (2x - - - E [[ 2
for any random variable Z E IR" Also, for any c E R,,
Var | = [ Z - [ - B - c)²].
Applying this and the monotonicity of the orthogonal projection from Proposition B.3 gives
Σx Var [X = E [|
11
- E [I (X //2 - E [[x
< < [||// E x = Ex Var[x212]
Hence, it suffices to prove the bound for x1/=_iee.. for the Elo update without capping.
Use subscript {i.j} to indicate that this pair is chosen in the first game, as before. Let J be pair of (distinct) indices drawn according to q. Then, by the law of total variance,
Σx Var X / = Σx ( [1 + Σx "ar(B [x)
We studied the first term (aka the "unexplained variance") first. First,
Σx ( 11 Σx En, ((55) (a.( [x] = Eis 90-1 Ex (x,)
We now bound Var (i.j) k
/2- over three cases: A = i, = j and l: & {i.j]- We have Var [X," |2] (ar( [X, mP (x + n7² (in) [Bern(P.)(o)]] Var[X - 21 Cov [x ox xÿ)] + nn²
since the maximal variance of [0, 1] valuud random variable is 1.- Analogously,
(a)( [x] 1 S Var [ar[x]]] - 2n Cov (x3 xx01+ + 2/2 Var [x]] + 21/ Cov (X3, oXp x311 + =
since o(-2) - (2). For k & (i.j}.
Var [x = Var[X
Bringing these three cases together,
Ex Var [x/ s Σx Var [X)] n²² 2n Cov xX- - Xy, (xp xy)]-
Now, a: : E + [0, 1] is increasing. So, Cov(Y, (Y 2 0 for any random variable Y. Moreover, _ -
(a())
= jo (0)] 2 min = E [-2M, 2M]
2M]|o'()) (z) 2 te 2M lul for all ye E 1-2M, 2M).
Since X x9 E 1-2M, 2MM, applying this gives
Cov( [X] - X3, oxx x3)] 2 Le=" 2M |XP X99.
Plugging this in above,
- En (ar X 1/2 S Σn Var[x - je 2M 17 Var 1X,- - -x-1-
We now average over {i
Eis (in [in En (ar (x 1/2 < En Var[x +1² - -e 2M Eis (an (a -op9-xxp X91.
Variances are (weighted) sums of squares, which leads to spectral-gap estimate again:
Ens U(s,) Varmen -X]1
-Eiy 96.51 Varqs.) - -((?))
Eis (6.1 BR [[(( - -E(x!)) (X) - B[X}D)
=E EES 91003 ((XP-
(XX--E(XX)) -[(X)) - (X9- - E|
2 E AAg (x 1 = = Ay Ex Var[x?]]
18

---

by applying the Dirichlet characterisation of the spectral gap with = X - - Thus,
Eis (is) En (i.) [X /
>x Var[X + r2² Lee -2hd 2 En Varl [a][
= (1 _ 2M M) E Varl X + +
We would like to deduce that En Var, [Xg] I 4e2M n/ X now, analogously before. But, we must remember the second term in the law of total variance (aka the "explained variance"), We have
Var Var[B [ 1 - 2 9h 2n ((..))
Indeed, if Player à is picked-ic., & E [1, X 1/2 moves up/down to one of two values which differ by 1y; if Player is not picked, then x does not move. The maximal variance such a random variable " qu, where Qh = Ee ((,,) the probability that Player k picked. Hence,
Σx Var [1 [X |
11/²² Σn 9k = =
noting the double-counting of edges in Σx Qk = Σx,e ke 9(h.e) = 2.
Combining the bounds for the unexplained and explained components of the variance,
Σx Var [X 1/2 $ (1 _ 2M m)2y) E Var[x + 2n7².
In partieular, stationarity implies that Σx k Var= [x1 Σx k Var [X2],
Σx V >x Var, H & Var [ / I 2M \/>
We controlled the bias, but did not actually argue that it is non-zero. Remark C.2 (Bias in Expected Rating). The uncapped Elo update (M = oc) implies that
E [x E, [X, 7 E, ((s)) (p))(p) (X))]
= [X, + n nE,, ((i,) E. [prs(p]]] - E, 9(1)) E. (x))
Therefore,
Eg SngsspPis(p) -, Ex (x)]
The right-hand side is the expectation of the estimated probability that Player wins their next game (not conditioning on their opponent) equilibrium and the left-hand side the true probability. The equality shows that the win-probability estimator for each player is unbiased.
In the two-player case, this actually implies that E,, (1),2(()) (p))(p). We can deduce from this, however, that the estimated rating is biased, if p * (0,0). We do this now, but only informally.
The ratings are pero-sum, it suffices to consider X, and P1. Suppose that P1 > 0 and that is small- much smaller than P1. Then, the rating X2 concentrates around P1. The win-probability function ø is strietly convex and increasing in (0, oo), which suggests that
P1.2 [L, (xl)) Ex, [X = pp.)(p). and hence EE, [X1] * p.
Of course, [x > 0 1. This can be handled using the quantified version of Jensen's 's inequality and large deviation estimates on [ < Oj. If pi is large, then, very roughly, the latter probability like - whilst the quantified difference from equality is like = the latter dominates.
The r--laaeer case more complicated. possible that a particular choice of (p, q) could lead to certain players' having unbiased estimates. However, they will be biased in general.
The ratings are biased, typically, but the win- win-probabilities at equilibrium are unbiased in the uncapped setting. Moreover, the real ratings are the only vector giving rise to these sin-probabilities.
Proposition C.3. Let x, P. E I2" with E Pk 0 Σ Ik. Ik. Then,
Σ, ( E, for all e [k) and only if x =
Proof. The "if" direction obvious. We prove the "only if" direction by constructing a minimisation problem over zero-sum vectors in [ with the following two properties:
19

---

1. it has unique minimum at p;
2. x. is minimum if and only if it satisfies the equations in the statement.
Define f:R² R by
(x)== 98s) log(1 - I4 E, m8st (p)s(0) 2)) for E ERR.
Then, is strictly convex {a E Rh Ex 22 = 0). and thus has unique minimiser that set. We now take the gradient of and compare with 0:
of (z) : E, 91.5) (2 -1 1)-E)) E, mhst (pL (0)- = -E (u.)p,,,,))) ",..,.,0) dz,
Hence, x: is a minimum and only if >x Ix = 0 and Σ, ((.)))p)()) = E, ((s)).s(p)
Notice that if we only desire estimates on the win-probabilities, then the whole Elo framework is needed: simply tracking the empirical proportion of games between each pair of players suf- fices.
D Convergence Proofs: Curvature and Concentration
Our time-averaged MCMC-type concentration estimates rely crucially on curvature bounds. We start by introducing curvature, then bounding it in the case of the Elo ratings. We then apply it to obtain concentration results for time-averaged ratings.
D.1 Curvature Definitions
We introduce the concept of curvature for a Markov chain on a general metric space (9,, d). Definition D.1 (Transportation Distance). Let μ and æ probability measures on f2. The trans- portation distance Wi (n, π) represents the 'best' way to send μ to that, average, points are moved by the smallest distance:
Wi Wi(u = info Be ()(,
where the infimum over all couplings Q of (J,, i.e., X a and Y и,, marginally, under Q Definition D.2 (Curvature of Markov Chains). The (Riccí) curvature of P is
Kp == inf Kz.y where
Ka.y = 1 (P Py.)/d(x,,)) for 2, E Ω.
standard application of the triangle inequality and iteration establishing the following result.
Lemma D.3 (Contraction of Distance). For all measures is and and all 2
W1 (HPP PP) s (1 (1- (i) and Wi(uPt, TPP') < (1 k.)' (H,
This reduces to the well-known set-up of path coupling when (2, d) is finite graph endowed with the usual graph distance. Our set-up, however, is very different: (S, d) (R.". 222)
Exact calculation of the curvature is rarely required. Rather, particular coupling is analysed, giving an upper bound on the transportation distance and hence, by extension, an upper bound on the curvature. The key is finding close optimal a coupling as possible.
The next subsection establishes an upper bound on the curvature of the Elo process. The final subsection of the section develops applies curvature to concentration.
D.2 Curvature Bounds for the Elo Process
We determine the worst-case rate of contraction rate - к starting from ratings (z, y) S?: we show that Z X where A, is the spectral gap of the auxiliary random walk with rates (g:.). Proposition D.4 (Curvature). Let k denote the curvature of Elo in || l12. Then,
me
2M
Xg.
20

---

Proof. Let x = (x))) E Ω2 and y = (Ue))e(()) E Ω be two sets of ratings. We want to bound
Er,yIII*= - [2] S (1 p}إ[2 y/2 for some p 2 0 under some coupling.
First, we observe that we can ignore the projection step in the Elo update, by Proposition B.3
||x Y- || (x112) I
|| - y 12-
Again, this is using the notation X to indicate the uncapped Elo update, and x = I (x1/2). We thus study (x 1/2 Y1//),, under the assumption || lly/loo I M. We use the trivial coupling:
. the same pair (T) of players is chosen;
the result of the match is the same came-i.e. the same player wins in both systems.
This is legitimate because neither the choice of players nor the law of the outcome depends on the current state-the estimated probability that 7 beats J depends on the state, but the real probability does not. Write ((s,)() [t] for the law conditional on choosing pair { to play.
Recall that, for I" and i E [n], write (z, == o22 24) for the estimated probability that i beats j using ratings z. If Player i beats j. then i gains np,, points; similarly, i loses rP, points if Player beats i. Observing that Pz,(zz) (y) = Pt,](V) Pt.((2), we obtain
((s)) [(x] - xx, = Pt,s (0) ((as - u) + (P)s(()) - (y)))
+ (1 - Pt., (p)) ((x= - vi) m(p)((t) - (v)))
((1; y/i 7 (p(((xr) pco pv)l1))
(x; 2 + 1"² (pin(a) Pru (v))² -2n(1; (pis(()) pi)(
Switching the roles of and j and using the fact that Ps.j - pj.s again, we obtain
B(is) [(x] - /3]] = (I, - v2 + 7 (P)n(z) - p))( 2 -2n(x, ()) - -pj((1) = (zy - ) + (P),(z) - pv,(1))² 2 + +2n(1, ()) - Pt. (v)).
For all other h: i.. for k E j} we have X²_²² = Iy and /1/² yk. Hence,
B(s,) || 1/2 - 1/2 - || v12
S 2n (pi. (x) - pv) 23 (2t; xz)) - (y: 41) (p)s(w) - pt.
S - (z: - xz) (u - 8o | -2)) - σw: - y,) |.
with the final inequality using the fact that o is 1-Lipschitz and 17 < 2.
We now bound the difference in probabilities. For w. E IR with . 2 T. we have
(a()) - (v)) 2 minse(g,a) [0((=) - 전l 2 te- max (111.1000 7/.
Combining the previous results,
((ss) [||x1/2 | - || v112 < 1 ne maax = 1リ (2:; - 2,,) - (y)s y;)1
< - -ttne 2M (x:; x.) - (v: 11)1² - tnn 2M (x;; vi) (x, , )
using the fact that ||>||| oo. 118/100 S M. Summing over (i, weighted by qt.s. gives
E 1|2 1// ||] || - -112
Eije[n]iks ((.1) B 1/2 -1 -y - || v12
< - 2M EijeE(] Ut (a:; - v1) - (xr, - , 12
Now, applying the Dirichlet characterisation of the spectral gap (Proposition B.I with 2 = x y. || w1l < ne 2M >, | -
E ||| 1/2 1 [|]]
note that Σn T = 0 = Σx Uk. so Σ₁ = 0. Jensen's 's inequality then gives
- |[ E
s E [||x1//2 - 1 1/2
< (1
2M X₂y //2 -
-2M
vlla S (1 -1- n 2M 1/)l| yl12-
Hence, recalling that ||X| - 11 - || - -
Kzyy 2 me
2M Xy. and
k inf a. NER Ke, 2 me -2M Xy.
21

---

D.3 Concentration Statements
Our goal is establish concentration of anneravee statistics of the Elo process. General results of this form as known as "Chemoff-tyye bounds for Markov chains". There is great deal of literature on such concentration bounds. The version we state here is most-closely related Theorem 3.4 and Proposition 3.4 in [35] see also Theorem 3 in [1], particularly.
Definition D.5 (Mixing Time). Let μu and π be measures on state space Q. Then, the total-variation (TV) distance between μl and π is defined to be
|| TV = supA (m(A) *(A),,
where the supremum is over measurable subsets of Ω. Let X (Xe) be Markov chain on S2 and let π denote its equilibrium distribution. The (precision-e) mixing time is
mmix (c) == inf (t 2 0 maxzen Px E -]- x 1I Sc}.
By convention, abbreviate miix tmmx(
Theorem D.6 (Concentration). Let X (Xi)s20 be a uniformly ergodic, irreducible Markov chain on a state space Q. started from its equilibrium distribution и. Let tix denote its mmixing time.
Let Ω R be bounded function: |l co. Let π (f) Ex .n2 f and of Var [ = [ - dd denote the mean and variance, respectively, of f under a.
Let Ç > 0 and t 2 0 be an integer. Then,
22t/tmix
E. f(x*) - (f)) - 2 c] 2 exp 16(1 + 2m /mix/())/ - 80C 80C1151|00/
In particular, ift max mi:: 406o311/11>> then
I+ f(x)) x (f) 2 <) cxp(( 07 2. -22t/tmix).
Remark D.7 (Connection to Curvature). The following description applies to finite state spaces Q2 we have to be more careful in our Elo application later, since that state space is uncountably infinite.
It is well known that curvature bounds the spectral gap and relaxation time 4et 1/A in the reversible case: X 2 K, and hence fxel = 1/A <-- However, it also upper-bounds the mixing time without requiring reversibility, with an additional factor depending on the diameter:
mmxx (e) < (log diam Ω + log(1/e)),
assuming that d(z, v) 2 1xx * v). The argument for this is straight-forward: briefly,
P + Y,] E[ * Y.) < [d(,,, YJ) < (1 x))'d(Xo. Yo) S kt diam Ω
then use the standard TV-coupling relation. This can then be plugged into the previous concentration bound, obtaining exponential decay in kt/ log diam Ω
Applying the theorem to the Elo process has a number of complications, primarily that it does not have a finite mixing time: given the initial ratings, it is always supported on a certain countable is 1 (maximal). We
set; thus, its TV distance equilibrium, which is continuously-supporte circumnavigate this by introducing a noisy version the proof. This is detailed later.
Theorem D.8 (MCMC Convergence of Time Averages). Let f T - R be a 1-Lipschitz, funschittfunntion and Ç 1). pep = [f] and o² = Var, denote, respectively, its mean and variance under n, the unique invariant distribution of X. Fort, 1,T O, denote the time average of f in [T, T + [-1
A T Eftt S(X*).
Suppose that ll S ft. Let C₁, C2 < co. Then, there exists a constant Co < oc, depending only on Cr. C2 and f. such that if
minfAg: 77, 1/t, 5) 2 -O= and min(t, T} 2 Cut. where := 2M 17 11 22 log n,
then
Poll+ - f(x*) msl 2 Coc] S CC 2exp( (expppo022220 (exttt))7(2t/ttt)
In particular, under these assumptions, taking Ç x df log M o log n/ /1>xtt
PP P[AATT 1451 2 M M of logn Sn C2
vn Agt
22

---

Remark D.9 (Convergence Rate). If X''', , were iid, then we would have 1/v decay. Chernoff bounds for reversible Markov chains require to be replaced by Xt, where X is the spectral gap. The idea is that lel 1 steps of the Markov chain are required to decorrelate terms when near equilibrium. For non-reversible Markov chains, running for L. does the job.
Connecting this to the curvature K, roughly, t, S x- log diam S2 if K >> 0; see Remark D.7 The Elo process is not reversible and we, in essence, bound t, X x-= log n and 111g.
D.4 Concentration Proofs
Remark [D7 connects curvature and the mixing time for finite Markov chains: in essence, curvature allows to bring two copies exactly together. The Elo process, which lives in the continuum R", does not have this property. We can get them extremely close, though. So, morally, the bound of x-1 log diam Q x X log on 'mixing' suggested by curvature feels correct.
We rigorise this idea by adding small amount of independent noise to the ratings after every step. This noise is then used to couple the two copies once they extremely close.
Outline of Proof of Theorem D.8 The proof has multiple steps, which we outline now.
1 Approximate the Elo process by noisy version and control the error.
Check that the curvature of the noisy process is at least as good as the original.
III Control the mixing time, and hence concentration, of the noisy process. IV Use burn-in to get the process quantitatively close to equilibrium. Compare the equilibrium distributions for the original and noisy versions.
Finally, we bring all the piece together to conclude the proof, checking a variety of conditions.
We approximate the Elo process by noisy version. This circumnavigates issues surrounding the discrete support of X, versus the continuous support of its equilibrium distribution.
All the statements consist of generic constants Co, C1, C2 < co. Rather than earry all these depen- dencies, we make the specific (arbitrary) choice C1 := 5 and exhibit a C2 for which this works. The results can easily be extended the general set-up, albeit with more notation. With this in mind, let n 24
Steple Noisy Version Error. We consider the following noisy version U of the Elo process X.
1. Suppose U wº. Draw u 1/3 according to uncapped Elo step ie.. as if M
started from wº. Suppose Players i j j were chosen-i.e., (k E [n]]
ugg J = = (1,j}.
1/3
2. Draw ū. ūz rid Unif([-Vo,+ +v independently of all else and set ūg = for k $ {i,j}. Set
u 2/3 1/3 +
3. Define U = w² by orthogonally projecting 2/23 to |-M, M] preserving the sum.
Note that this does not preserve the zero-sum property, ū; f ūj. We see later, though, that is
even for these additive noise terms to be taken independently.
We must control the error between the noisy and original versions. To do this, coupling, as before: the same players and result is used. The error does not accumulate super-linearly due to the contractive nature of the Elo update step, as we explain now.
the trivial
Suppose that (X'9, yo) = (a, y) and generate (X1, Y!) (x'. v/) from a single step of the trivial Elo-update coupling. Suppose that Players and j play. Let E {0, 1) be the indicator that Player i beats jhe 'score'. Then,
z = 77s (x)) and v/4 = ys nn(s PL.(
Subtracting the second from the first gives
2 - 3/ .z yi (p))(()) (v))
23

---

Analogously,
Mj + a/j v/ 2, -9
(p)),(()) - Pt.(1)).
Subtracting these,
(0) v/)) (xr) vz) = (xt vi) - (x, Uj) (p(s)(( - pio(
But, (z.)()) (2 24) and is 1-Lipschitz.
zj - Uj if and only if Pi,(2) S Pi.(u)
and
(2)((2) Pt.j [b)) - ((x m,) - (y -3y51 = [xz vs) - (xz y;)1;
also, 17 S Hence,
1( - v/1) - (1/)- - -///1 $ 1(2; yi) (x, - -ys)1 s lx, - Val + |2g - Uز
Also, trivially,
((r1 v/1) (x'g w/)1 1zx y:) + (xr, 11y1 S 1x; Val + 12g 251
since the Elo update is zero-sum. Combining these bounds.
b - + -
- 2رك1 = max
1 [[ - v/4) (a') 2/)1, 1(x1 - v/ + (2ty v/y1 S |., - - + |o - Vsl-
In other words, Elo update does not increase the l distance between the of ratings:
| 1/11 - 2 y|11.
This actually immediately implies that the Elo process is non-negatively curved in é
A consequences of this is that that error only arise from the additive-noise step:
| - < || -x-11/2_ 1--1/2111 S -x U--1|| v S 1..5...5 8vo.
Iterating this completes Step
E || - U S 5 deterministically.
We work with the noisy version U, rather than the original version X. The key statistic for our analysis is the curvature. This is not hurt by adding noise.
Step 17 Curvature. We use the same coupling before and the same noise in each process.
(i) Suppose that (U), Vo) = (w², v0). Draw (u//3, 22/33 according to a single step of the trivial Elo coupling started from (u", v²). Suppose that Players and j were chosen.
(ii) Draw single noise vector i.e., ūü ūi Gid Unif([- + v8] and üg 0 for k &
{i, j). Set
2/3 = u 1/3 + and 2//3 = 1/3 + ū.
(iii) Define U1 = ul and / vf by projecting to [- M, M) preserving the respective sums.
We have already shown that the trivial Elo coupling contracts. The added noise does not hurt:
| - 1l112 < ||/2// - 2 < |// 2//3//2-
Hence, the two-stage coupling contracts at least as well as the original, completing Step
E|||0* - [2] < 2/ /
[|] < (1 k) - v
The reason for adding the noise be able to couple two systems and V. and hence bound the mixing time. We can then apply the general concentration result of Theorem D.6
Step MI Mixing Time. Suppose that (U Vo) = (u", n with proceed via slightly different coupling, replacing
8. From this point,
with defined below.
24

---

(i') Suppose that (U9.V9) (u², v²)) Draw (u (u//3,1//3) according to single step of the trivial Elo coupling started from (u", v²)) without capping. Suppose that Players i and j were chosen.
(ii') Draw üi Unif([-Vō, + v))) and set 8x = u (" 1/3 - / E [-vō, + vo mod 2 independently for E {i.j}. (Here, "mod 2 means "adjusting by additive multiples of 2vō as necessary so that i E [- V8, +Vō)") Set ük, 0x == 0 for k & {i,5}. Set
u 2/3 = u 1/3 + ū and 2//3 = w +
(ii') Set U == u² == aas (2) and V = r² = (12/3))
If ||u2 v loo S å and Players and j play, leading to (u²/3, /1/3) under the Elo coupling, then max (lu 1/1,, |u 1/3 36, regardless of which player won. Hence, in the notation of the coupling,
2/3 for both E {i,}) if ie,ūū E E--5++30, +VB -3).. Say that a step successful if this holds and fails otherwise. The probability of failure is at most 6v6. If succeeds, then Players and j are coupled and the bound of on the &o norm is preserved.
2/3 1/3 + + = u/ 1/3 +8x = dk
Wk 1/g
We now iterate. Suppose that | lcx S 6. and Players i and je are chosen in step t. Let
Te = inf { 2 Uoge Je} = [m]}
be the first time that all players have been chosen. If all the first steps are successful, then all players' ratings are coupled. Call this event C; then, P(C To I t) 2 11 11-6vt..
It remains to analyse two times:
* the 'burn-in' time To to get loo norm at most 6, using coupling the remaining 'coupling time' Te started after the burn in, using coupling
The first is easy to handle using curvature:
E||IU* |=]] s B[IIU* V*lla] S e = 1012 Se- kt, 2M.
Thus,
F(T, > 1] s PP||U* - 1l > 8) S V'Il"10'''
if 82 to = x- x- logg (2g(2//8))
The second is equally easy. Start with (U", Vo) such that I V19 2 for all i. Now, | - Vl < 6 < 1, then all players must have been chosen. Hence,
P|T. > t CJ s P[|U" - lo > 8) < if t2 to = x log (2MMm68²)
Let = inf(t 2 0| U Vt} denote the coalesce time. Putting the above parts together,
P(T > 2ts] S PlT, ts} P T.. ts] + IC To t& 25 6 5tg-
We have x- = 2M n \11 $ n || So, recalling that = n
24 we have
6Vola < 6n 12 n 11 72 log n 432n log n 1.
Hence, 28 + 16ttss < 1.- Also, -2
24 and M < Im, so
4s = x log 02) < 2M, 2a 50 log n 400c 2M 17 Xx loo n 4000,.
This completes Step III
4. (() < 4. (26 + 6v vots) < 21 S 800/ = 2M 2M, 11 11- 1 log n.
|||
The general concentration result of Theorem D.6 applies only for Markov chain started from equilibrium. We start another chain V from equilibrium and use a burn-in to get U and V close, quantified by curvature. The error between the time-averaged U- and V-sums is then small.
25

---

Step IV Burn-In Let V be a noisy Elo process, started from its equilibrium distribution which will differ from и slightly. Under the above coupling, which has contraction rate by
-+t- E - V E - E
V* - E.2t c ne 2M I AM ] = if T T = n- log (22M2221/// 1/81/3).
Analogously to the previous step, this time using also A. -1 S n,, we have
To = K log(2MMn 16) S 8c2M 1j x 31 log n v 250e of x logn 2500
Also, 1 2 x- 2 n. We can then deduce the estimate desired for Step IV
B E T+-1 -0 - [h] - St if T 250
IV
Step V Equilibrium Distributions. The original and noisy Elo processes have different equilibrium distributions; call them and म. respectively. Let Y and V be an original, respectively noisy, Elo process started from π,, respectively Then, by the strong law large numbers,
T (f) - # #f))
lim E
(((")))((0))))))-))) -((())(((())) almost surely for all LEN.
In the curvature proof, we showed a fg-contraction of 1 - 2x for the Elo process; see Proposition D.4 Adding the noise increase the &2 distance squared by most 10Mv& Hence,
de = E R| v
satisfies de S (1 2x 10MV5.
Iterating this,
de 5 .... S 2M 2x)² 5M dx S 6M if EZ for some sufficiently large By Cauchy- E[J|Y V212] S VT. Hence, E E I - v [12] S ビdth + dd - 36 (M/x)/12
Plugging this in above, for a L-Lipschitz function f. using || 1115 vīl 112, we obtain
[T(() #(f) - 8// (10MMn/K))
Finally, we observe that 10Mn/K S n²,, completing Step V
(5) - # (()) - n. 7/2 = n 5/2
We bring the previous give steps together conclude the proof.
Conclusion of Proof of Theorem D.8 We use the following notation, inline with the above:
X is the original Elo process, started from arbitrary initial condition;
U is the noisy Elo process, started from the same state as X X-iie., U = =x
V is the noisy Elo process, started from equilibrium #.
Recall that [| I This with the triangle inequality allows to control the steps individually:
1 D T+ f(X)) - x()
< I+t-l -X*-U*I
Step
+ & E ||U VV
Step IV
+ 1 -TT ((V")-(())
-
Step III
+ - -
Step V
The first term is at most 1/58 < 7 deterministically by Step I and the last is most n 7/2
55/ by Step v The second term is at most 81/3 /n = -9 in expectation by Step Iv which we
plug into Markov's inequality. We assume that Ç 2 n so that each of the first two terms is smaller
26

---

than Ç. and n 5 /S S n
3 The remaining term is controlled via the general concentration result of log n from Step III Hence,
Theorem D.6 using the bound t. (G) I 800t, 800e 2M
7) x
F Σ s=7 T+ - =(f] 9c]
- P P - U - -/E voll >
+ +P[ E f(V*) xx(f > 5c]
S n + 2 exp (ttt)
We can apply Theorem D.6 if 1 25600 32 8001, due to Step |II and Step IV if 2 250
Finally, we make a specific choice of Ç. There is already a polynomial term in the error probability, so we want to choose as small as possible whilst preserving this. Thus, we take
Ç : (==oyvll logn//// n/t 2e logn/ ndgl.
D.5 Deduction of Theorem 2.5 from Theorems 2.7 and D.8
We start by recalling Theorem 2.5 for the reader's convenience, numbered here as Theorem D.10
Theorem D.10 (MCMC Estimator Time-Averaged Ratings; Theorem 2.5). Denote the time- averaged rating
T+t-1 X for k E [n]] and t. 0. A=='= ==== 1
Let C1, C, < cc. Then, there exists constant Co < co, depending only on C1 and Cz. such that if
min n. 1/t) 2 Ct and min(t, T) 2 Cot. where t, == e Xx log n,
then
Coeass Ayn
(log (logn)3) (
P H 212 <
2 11-
Dat
The same result holds for 1 11AAT pll1, the average distance the & (rather than tg) sense.
Proof of Theorem 2.5 The two termss inside the probability come from the MCMC-comvergencee error and the equilibruumddistrbbute bias. use abbreviations
A = T+ X B = | (II)) pkl and == oî. -Var, [[]]
where 11g Rn + IR is the k-th projector. We separate the MCMC and bias parts:
|| 2l2 = 2|| x (II) + 2I[ - p122-
For the bias part, simply note for now that
[[(II) p13 Σ. ((la)) pxl Σx 82 =: nn32.
We now turn to the MCMC time-averages. Applying Theorem D.8 with = Il
P[| (IIx)| 2 Che 0% log n/ /1\at] I n C22
under the assumptions that theorem. We perform union bound over the n players:
PP [[ n (IT) 2 CM (log (m1r;))))))))) S -C+1 where x² = Ex
CC+1
These bias and (average) variance terms are exactly what we handled Theorem 2.7
8² < 46
7/ (Apm) and x² < 2c 1 (Ay.).
The first part Theorem 2.5
2.5 now follows from plugging these in above and some small manipulations.
To obtain the 1/(A,() decay, we just need to check that > l,:
t. e 2M x log
2M X logn 2M
<
\ (log n) log n
27

---

E Convergence Proofs: Parallel Matches
Our previous bounds on the bias and the variance included the spectral gap X obtained from sequential analysis-namenn we used Le = These expressions change in the parallel set-up. This has knock-on effect on the two terms in Theorem 2.5
We now state an extended version of Theorem 3.3
Theorem E.1. Denote the time-averaged rating
A 1/2 EEer X for k E [m] and 1, 1,T>
where X is the state after 2 0 Elo rounds. Then, under the conditions of Theorem 2.5
CeaM (n+ (logn)² Aut
-1 =1
P |44T - pll Xyn/N
where N == EeEE is the mean size of the matching; to emphasise, here, and T count rounds. Moreover, there exists a distribution q (ās)SEM over matchings whose induced distribution q = (ge)een v. over pairs satisfies 0g 2 3 3dasee In particular,
|| -ll+
2MM logn
1
whp
if 17
n) Adiso
Niise
We separate the proof of Theorem
E. into two parts: the convergence and the existence of parallelisable q with Ag 2 3 Mine The "in particular" part follows exactly as for Theorem 2.5
Proof of Theorem E. Convergence. Write 32 = | (II) - pll3 and π² = 1 Ex Var, [Tg]] for the average bias and variance the ratings, respectively, as we did in the deduction of Theorem 2.5
The analysis of the bias is unchanged until we average over the choice {i,j} of players. Then, we implicitly used Ee 9e 1 when averaging 21j² over {i,j]. Letting N = qe [ssq[[S[]] denote the expected size of the random matching ğ corresponding to q, the same analysis gives
Ez || p| S || p1l + 2N 1 4M 1) Ei, ((r - pe) - (x, - p,)1
Inspecting the analysis of the variance see where E. 9. is used, we get
Σx Varlx < Σ Var[x + _ N1
_e 2M 1119 Ex Var Var[X
The proofs then proceed as before to give the bounds
8 s 4e AM (App)) and
0² S 32 2M (),m))mt).
The argument for the deduction of Theorem 2.5 gives
P P pl2 S Co( + 8 (n),t) 21-1
now, (t, in ALT correspond to the number of rounds and may have Ee 9e > l-and, so, Ag may be larger than 1/n, but not than N/n. Plugging in the new bounds for and o.
F - p13
CoEAM ( + (logm)) Agn/N
(log n)) "²
2 21-n
Aal
Proof of Theorem E.I Ag Xissc Let q be an optimiser of Xiro >₂= X can be formulated as a semidefinite program [10]. so its solution can be approximated arbitrarily well in polynomial time.
Extending 9 from E to [n] by la {(i.j) [f E E} defines symmetric and substochatic matrix with the same Dirichlet form. Adjusting the diagonal has no effect on the Dirichlet form, so may assume that in fact, stochastic: its row sums all exactly 1. The spectral gp of this q is still Ay, by the Dirichlet characterisation (Proposition B.
The Birkhoff-von Neumann theorem allows the decomposition of any x doubly stochastic matrix into a convex combination of (at most) n² permutation matrices polynomial time:
q=
1= arPot
28

---

where a E [0, 1]m² with Ee = and P. is the permutation matrix for a E Symm(n):
(Po). = o for all i,j E [n].
This can chosen so that each permutation matrix has non-zero entries only over graph edges.
Given a permutation o, we decompose into disjoint cycles. These cycles actually correspond to cycles in the graph; we discard eycles with only element. Let v1, 02:--1 Ug be the vertices of a particular cycle of length k. Then, we can decompose the cycle into three matchings:
one containing all the edges in the cycle of type (U,, U++1) with odd i E {1,..., k: 1);
one containing all the edges in the cycle of type {u,, 0,41) with even i {1,..., k - 1}: matching containing the single edge {uz, U1 }.
This decomposition gives rise to procedure to sample matchings in the graph.
1. Sample a permutation E according to the convex combination: P[ = or| = a for each &.
2. For each cycle in Σ. independently sample one of the three induced matchings listed above, each with probability 1/3.
The vertices in different cycles in a permutation are distinct. Hence, this procedure does indeed product matching. Moreover, the probability that given edge (i. E belongs to the sampled matching is precisely 39.. = 39(0)) Hence, we have constructed a matching with associated spectral gap at least Ag. But, by assumption, Ag = Xise completing the proof.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the abstract and introduction make clear the contributions of our paper. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We discuss limitations of our work in the introduction and clearly state the assumptions of our results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: complete proofs are included in the Appendix. An outline of the proof of our main result is included in the main body of the text.
30

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: in the main body of the paper, include enough details in order to repro- duce our experimental results. The supplementary material includes our code so that our experiments can be reproduced and verified.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- ppen-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer: [Yes]
Justification: code is included in the supplementary material. Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
public/guides: httes//oooSSuuaiioioooooo.o
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
7/nips. htaips.cc/pbllc/guuddee http///ooessiiiiiiooooooooooooaa
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: we have included our choice of parameters in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: we include contidence intervals in the plots of our experiments. Statistical significance tests are not really relevant for our experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: the computer resources are not really relevant for interpreting our experiments. We include the number of games simulated which is better way to measure the complexity of the algorithm analysed.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification: have read the NeurlPS Code of Ethics and paper conform to it. Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
we do not foresee any particular societal impact of our paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
33

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learss from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:[Yee [Ye]]
Justification: our code uses an existing library to compute a von Neumann -irrhhoff de- composition of a matrix. We have included the library and its licence in the supplementary material.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww.coo///aaoooo datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
34

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: no new assets released. Code included for reprodueibility has been commented and include README file.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
35


Reviews:
[{"review_id": "l52Tgvc8Fj", "reviewer": "Reviewer_ZrEV", "summary": "The paper presents a novel theoretical analysis of the Elo rating system, a well-established method for ranking player skills in online gaming and sports contexts, particularly in chess. The authors analyze the Elo system under the Bradley-Terry-Luce (BTL) model, employing techniques from Markov chain theory to demonstrate that the Elo system can learn model parameters at a competitive rate compared to state-of-the-art methods. The paper also explores the implications of this analysis on the design of efficient tournaments and draws parallels with the fastest-mixing Markov chain problem. The authors provide rigorous proofs and a discussion of limitations, showcasing the robustness of their analytical approach.", "questions": "1.\tIn definition 2.3, what the dij and deltaij means? There seem lack some detailed explanation of these symbols’ physical meaning. \n2.\tWhat the symbol in the “equation” in line 110 mean? This symbol appears frequently in whole paper, but less explanation.", "limitations": "Please refer to weaknesses", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Theoretical Rigor**: The paper offers a thorough theoretical analysis of the Elo system, contributing to a deeper understanding of its performance under the BTL model. The use of Markov chain theory to analyze convergence rates adds significant value to the existing literature on the Elo ranking system.\n\n\n2. **Connection to Tournament Design**: The paper's exploration of tournament design and its relation to the fastest-mixing Markov chain problem is a novel contribution, potentially offering practical insights for tournament organizers.\n\n3. **Clarity and Structure**: The paper is well-structured, with clear explanations of the methods used and the results obtained. The inclusion of and detailed proof guidelines and comparisons with related work enhances authors to understand the research.", "weaknesses": "1.\tThe definition of new variables is extensive but less detailed explanation, making this paper is challenging to understand. \n2.\tThe theoretical result in Theorem2.5 is based on a somehow strong assumption of “The (deterministic) time T is a burn-in phase, which allows the Elo ratings to get 'near' the true skills, after which we start averaging”. So, this theorem only claims the convergence rate at the burn-in phase when the Elo ratings may get 'near' the true skills. If the convergence rate from the start phase could be given would be better, even though requires some conditions like the winning rate among players should be enough to make a difference.\n3.\tDoes the convergence rate in this paper definitely outperform those in other papers? In section 2.2, this paper says “Our result improves the constant in front of M”, but the estimation error of this paper is related to (logn)^2 but those of previous works are only related to logn, they are better than this paper’s result. \n4.\tWhat’s the technique novelty of this paper? The form of the convergence rate result is very similar to those of previous works. \n5.\tIf the convergence rate is similar/comparable to previous work, the innovation of this paper is limited because there has existed convergence rate analysis of Elo rating system, and the usage of Markov chain theory does not gain significant improvement on convergence rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and in particular for highlighting our paper offers \"a thorough theoretical analysis of the Elo system\". We first address the weaknesses highlighted.\n\n1. We will try and add further explanations for the various quantities used in the paper in the camera-ready version. Since the camera-ready version allows for an additional page, this should not be too hard.\n\n2. We believe with some technical work it is possible to obtain a (potential weaker) bound that does not require a burn-in time. This is due to the fact that the burn-in time T is at least a factor of log n smaller than the total \"averaging\" time t. \\\nPerhaps more pertinently, the time T is deterministic, and fully determined by measurable statistics of the system: the spectral gap λ_q of the choices q and the number n of players. It isn't some ill-defined concept of 'near', which can't actually be known.\n\n3. Points 3-5 essentially ask what are the improvement over previous work. We would like to point out our work is, as far as we know, the first to analyse \"online\" Elo, which is what is actually used in practice. Previous work obtained similar bounds only for *offline* algorithms for Bradley-Terry-Luce estimation, exploiting ad-hoc algorithms that are not actually commonly used in practice. \\\nUsing a Markov chain approach allows us to obtain concentration results. Moreover, we believe it allows us a finer understanding of the process. Mixing is perhaps the most important of these, as it measure the time for the system to 'relax' to equilibrium. In other words, after mixing time steps, the system is close to the true ratings whp, regardless of the initial state. Since Elo is a commonly used algorithm in practice, we believe these results are interesting on their own. \\\nAs a minor point, to reply to point 3, we remark that if M > log log n, then the constant in front of M is actually more important than the additional log(n) factor.\n\nQuestions:\n\n1. $\\Delta$ is simply the Laplacian of the Markov chain with transition rates $(q_{i,j})$. This is a standard matrix used in the analysis of Markov chains. You can view $d_{i,j}$ as the \"degrees\" of the graph with edge weights $(q_{i,j})$. \n\n2. $x \\asymp y$ simply means that there are absolute constants $c_1,c_2$ such that $c_1 x \\le y \\le c_2 x$. We will add an explanation to the revised version of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U0VUvKu7jA", "reviewer": "Reviewer_ZKzd", "summary": "The authors analyze Elo ratings under the BTL assumption and show that the Elo update system converges to the true ratings of the player with high probability. They do this analysis for an online setting compared to other work that has analyzed this for the offline setting (where a pool of data is collected). They then show how this leads to a tournament design.", "questions": "Due to lack of expertise of the reviewer for this author, this is left blank", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Elo is a popular algorithm that is used from chess to sports like football and baseball. As such it is of broad interest and these results show why this method works. The authors do a thorough analysis and provide empirical data to support their conclusions.", "weaknesses": "The work analyzes an algorithm that has been popular and so the contribution doesn't bring any new ideas to the improvement of the ratings system. This raises the question about the magnitude of the contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and in particular for highlighting that our work provides a thorough analysis of an algorithm with broad interest.\n\nAbout the weakness highlighted, first, we believe that before improving upon a technique, it is important to understand that technique well. Elo is popular, as pointed out, yet has very little theoretical backing. Our paper is a step in this direction, and further work might be inspired by our theoretical understanding to obtain improvements on Elo. In particular, we highlight the biased nature of the Elo updates: it would be nice to design an unbiased update scheme *without* knowledge of the true ratings, but this seems difficult.\n\nSecond, our observations about tournament design might be of practical interest to schemes which learn from pairwise comparisons, potentially leading to improvements.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kYc5xKHm3b", "reviewer": "Reviewer_EfRM", "summary": "This paper provides convergence guarantees for the time-averages of a natural dynamics (Elo) modelized after the Bradley-Terry-Luce model of elo. If the system has $n$ players and $t$ is the number of time steps, the error is shown to be $(e^{4M}/\\lambda_q)(n^{-\\alpha} + \\log(n) \\sqrt{1/t})$ with probability $1 - n^{-\\beta}$ in $\\ell_2$-norm, where $\\alpha, \\beta > 0$ are universal constants (under assumptions on the learning stepsizes), $M > 0$ is the truncation constant and $\\lambda_q$ the spectral gap of the matching graph (tournament design). \n\nThe authors further investigates the problem of finding efficient matching graphs (tournament design) to accelerate the convergence of the elo process. \n\nAlthough the analysis is *online* (the elo is adapted along the matches), the convergence guarantees nearly match the best known *offline* guarantees (computing the elo by batches, after all the matches have been played).", "questions": "### General questions \n\n- Analysis this Elo system seems so natural to do with a SGD approach. Is there any in the literature?\n\n- Why do the asymptotic convergence guarantees depend on the number of players? Is this an inevitable feature? I would expect that, if the the stepsize is small enough (or vanishing), the system overall converges to the true elo values. Is this not the case?\n\n- From a more SGD viewpoint and looking at the average dynamics (the dynamics in line 18 are a Robbins-Monro scheme of a continuous time gradient descent), is the objective function convex? If so, SGD is known to have a few theoretical guarantees and I am curious to know how it compares with your results. \n\n### Miscellaneous\n\n-  At line 178, you say that Elo doesn't converge in total variation. Is this because the learning stepsize is constant? At the next line, you seem to claim that this comes from the fact that $X^t$ is finitely supported while $\\pi$ has continuous support. It seems wrong to me because if $\\hat{\\mu}_n$ denotes the empirical distribution (finitely supported) obtained by sampling the gaussian $\\mu = \\mathcal{N}(0, 1)$, I think that \n$$\n||\\hat{\\mu}_n - \\mu || \\rightarrow 0\n$$ almost surely, where the norm is the total variation distance.\n\n- You use the terminology \"negatively curved\" for \"contraction\" and \"non-positively curve\" for \"non-expansive\". Is there a reason for this?", "limitations": "- The guarantees only hold under the assumption that *there exists* a true rating of players, $\\rho$, itself generating the outcomes of matches. It is known that in general, the strength of human players is not an order, and more rock-paper-scissors like ($i$ beats $j$, $j$ beats $k$ yet $k$ beats $i$). \n\n\n### Miscellaneous\n- Despite the effort provided by the authors to make the proof clear, the review time was too short so that I could provide a technical review of the results, especially because the present work is not exactly my domain specialty. Hence the present review is mostly high level and the confidence level is low.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The model is clear and well explained.\n- The result is pretty difficult. Despite its difficulty, there is a real effort of presentation, to provide intuition and to split the proofs into comprehensible steps (e.g., section D.4). \n- The statements are clear and the results are interesting.", "weaknesses": "### (minor) Reordering a few results?\n\nI believe that slightly reordering results in section 2.1 would help to streamline the paper.\nFor instance, remark 2.4 (plus lines 194-195) would be better *after* the statement of Theorem 2.5 in my opinion, because they make more sense once one has read the main statement.\n\nIt isn't clear at first glance that Theorems 2.7 and 2.8 are preliminary results of Theorem 2.5, and it made me confused a little bit.\nAlthough they are interesting on their own, it may be worth putting them in a dedicated subsection.\n\n### (minor) Typography\n\nThe paper does not exploit the large text width of NeurIPS' template.\nFor instance:\n- at lines 597 and 599, the $\\le$ and $=$ are missaligned\n- at line 606, the second block of aligned equations do not require a linebreak (from what I can measure). Other equations could enjoy such improvements (e.g., line 829).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer has found our results interesting. We thank the reviewer for their comments about presentation and typography: we will definitely take them into consideration when preparing the revised version of our manuscript.\n\nWe now reply to their general questions.\n\n1. We have not been able to find an analysis of Elo with an SGD approach in the literature. See also point 3 below.\n\n2. We are not exactly sure what the reviewer is meaning with this, so we kindly ask them to point out if our reply does not address their question. The convergence rate needs to depend in some way on the number of players, since each player needs to have played at least once for convergence to happen. If the step size vanishes, then yes, the system converges to the true ratings (this is a consequence of Thm 2.5 in our paper). However, a non-vanishing step-size, no matter how small it is, will result in a non-zero bias.\n\n3. The function is convex and we agree we could have studied Elo using known theoretical guarantees for SGD. However, using off-the-shelf theorems for SGD, as far as we know, results in non-optimal rates and guarantees only in expectation. That does not mean that a more sophisticated analysis from an optimisation point of view could not address these issues, but then we are not sure this would actually yield a simpler analysis. In addition to that, we believe a Markov chain analysis has its own intrinsic value since it allows us to separate the contribution in the convergence rate due to the bias and the mixing time of the underlying process.\n\nMiscellaneous questions:\n\n1. We do not think the example mentioned by the reviewer is correct. We believe the total variation distance between the empirical distribution of a sequence of Gaussians and the Gaussian cumulative distribution is actually equal to one. For a reference, see the first page of \"No Empirical Probability Measure Can Converge in the Total Variation Sense for all Distributions\" by Luc Devroye and László Győrfi in The Annals of Statistics, Vol. 18, No. 3 (Sep., 1990), pp. 1496-1499. \\\nThe reason Elo does not converge in total variation, however, is actually simpler: when we fix the starting point of the process, after t steps, the distribution is supported on a deterministic set of finite size: for each Elo step, you can choose one of the $n \\choose 2$ pairs of players and we have at most two outcomes. Assuming the invariant distribution of the process is atomless, then the total variation distance between the distribution of Elo and the invariant distribution cannot converge to zero as t goes to infinity. We further remark that this observation has been made before by Aldous (reference [7] in our paper).\n\n2. We use the term curvature in the sense of Ollivier because it is a common concept in the analysis of Markov chains. We can try and make our writing more clear for a broader audience.\n\nAbout the limitation pointed out by the reviewer: we agree the Bradley-Terry-Luce model is not necessarily an accurate representation of reality. It would be very interesting to study extensions of the Bradley-terry-Luce model beyond linear orderings of players, but this is outside the scope of our contribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7dRBamrIcQ", "reviewer": "Reviewer_M8kb", "summary": "The paper proves results about the Elo rating system, as used for instance in chess, using tools from probability and Markov chain theory. The Bradley-Terry-Luce model assumes a true ranking exists and that the Elo ranking evolves via a Markov chain when two players compete against each other. Although the stationary measure of the Elo process provides a biased estimator of the true ranking, this bias can be sufficiently small to provide a good approximation of the true ranking nonetheless. The main results consist in finite-time l2 bounds between the true ranking and the estimated Elo ranking, that show how the Elo process can approximate the true ranking. Some experimental results are also given.", "questions": "Here are some specific remarks and suggestions: \n\np.2-3 In Def. 2.1 I think it is bit surprising at first that $\\rho$ does not appear explicitely. I suggest precising that $\\rho$ is the true ranking and that $I$ beats $J$ with probability $p_{IJ}(\\rho)$\n\np.3 l.3 \"$\\pi$ the equilibrium distribution\": I suggest adding a reference where existence and uniqueness of the invariant distribution is proved\n\np.3 l.100 the notation is $\\succeq$ is not defined. It does not seem to be used elsewhere in the paper.\n\np.3 l.103 \"is order $n$\" should be \"is \\emph{of} order $n$\". \"This implies $\\lambda_q \\leq 4/n$ always\": could you provide a short argument for this?\n\np.4 l.146 \"Since $n / \\lambda_q \\geq 1$\": I think the authors mean $\\lambda_q \\leq 4/n$\n\np.5 \"Even an alternative definition of the spectral gap has been proposed [13]\": I think this sentence is a bit misleading as it could suggest that the spectral gap of [13], defined as in the manuscript as the second smallest singular value of the Laplacian, can be used to control the convergence to equilibrium of a Markov chain, as is done classically using multiplicative or additive reversibilization. [13] shows however this notion of spectral gap is related to convergence of empirical averages.\n\np.5 in l.200 and l.202 what is the $\\Delta$ sign at the end of the equations?\n\np.5 l.242 the notation $\\tilde{O}$ is not defined\n\np.15 Prop. B.1 I think there is a missing $1/2$ factor in the Dirichlet characterization of $\\lambda_q$.\n\np.15 l.541 \"Eloupdate\" should be \"Elo update\"\n\np.16 l.548 [29] is a stack exchange post, which to me is not a good reference. I would either give a classical reference or not give any reference at all, given the result stated is simply the convergence theorem on Hilbert spaces\n\np.16 Appendix C: the notation $X^{1/2}$ is not introduced\n\np.17 l.589 \"We now turn to the bias\" should be \"We now turn to the variance\"\n\np.18 l.598 I think two factors $1/4$ and $1/2$ have been swapped: the maximal variance of a $[0,1]$ valued random variable is $1/4$, so the $\\eta^2$ terms add up to give $\\eta^2 / 2$ instead of $\\eta^2 / 4$. This error is maintained throughout the proof and gives eventually a factor $4$ instead of $3$ in Theorem 2.7\n\np.18 l.607: \"$z:=x^{0} - \\mathbb{E} [X^0]$ should be $z := X^{0} - \\mathbb{E} [X^0]$\n\np.18 l.611-612 \" the maximal variance of such a random variable is $q_k /2$: there should be an additional factor $\\eta^2$\n\np.19 l.617 the step-size $\\eta$ is missing in this equation\n\np.21 l.677-679 the notations and remarks given in this paragraph have already been used in Appendix C, so I suggest moving it there\n\np.21 in the equation after l.679 what is $\\pi_{i,j}$? \n\np.21 l.683 $\\bar{z} \\in [\\bar{y},\\bar{x}]$ should be an index of the minimum\n\np21 in the second equation after l.685 I think the notation $E_{\\ast}$ is not defined\n\np.22 Are ergodicity and irreducibility sufficient for Theorem D.5 to hold? I think the results from [35] require a stronger form of \"uniform ergodicity\".\n\np.22 In Theorem D.5 \"Let $t_{\\mathrm{mix}}$ denote its mixing time. I think it would be worth giving a definition of the mixing time. Also it depends on a parameter $\\epsilon$ so the authors should precise if they consider a particular $\\epsilon$, e.g. 1/4. Also I find slighlty confusing that the notation $t_{\\mathrm{mix}}$ is also used, e.g. in Theorem D.7, to denote an upper bound on the mixing time.\n\np.22 In Theorem D.7 the result seems to be stated (and is proved) for a $1$-lipschitz function. In general I expect there should be a dependency in the lipschitz constant\n\np.22 l.717 use only one notation among $\\mu_f$ or $\\pi(f)$ for the expectation.\n\np.23 l.738 again the mysterious $\\Delta$ sign\n\np.23 l.741-743 about the generic constants: I haven't checked all the calculations but I think they are correct, however I must say the implicit assumptions made on $\\eta, \\lambda_q$, etc; are not always super clear. For instance p.25 I do not see why $t \\geq \\kappa^{-1} \\geq n$. ALso why the equation of l/812 establishes a bound in $\\delta^{1/3} = n^{-8}$ and then in l.814 it becomes $\\delta^{1/6}$?\n\np.23 l.756 \"Let $s \\in \\{0,1 \\}$\" there is a slight abuse of notation in that $s$ is also used at the end of the proof as a summation index. Maybe write $S$, although I admit there is little risk of confusing.\n\np.26 in l.821 there is a missing expectation\n\np.26 l.829 I think using the lipschitz condition requires applying the triangular inequality first, in which case there should be norms inside the summation for the step I and step IV terms\n\np.26 l.831 \"The second term is at most $\\delta^1/3\"$: but the step step concluded with abound of $\\delta^{1/6} / n = n^{-5}$. This probably does not affect the result, but I think these inequalities based on implicit assumptions changing from line to line are confusing and could be made clearer.\n\np.26 l.834: the right-hand side of the inequality on $t_{\\mathrm{mix}}(1/4)$ is $800 t_{\\mathrm{mix}}$ given what precedes, not $t_{\\mathrm{mix}} = 800 \\ldots$.\n\np.27 l.844 $\\sum_{k} | A^{t,T}_{k} - \\rho_j |_1$: write this either as a sum or as an $\\ell^1$ norm\n\np.27 Proof of Theroem 2.5 why introduce the new notation $\\Pi_k$?\n\np.29 l.895 \"the single edge $\\{ c_k, c_1 \\}$\": I guess this is in fact $\\{ v_k, v_1 \\}$\n\np.29 l.898: I am not sure to understand how the cycles are sampled: is it each with probability $1/3$?", "limitations": "The paper addresses the limitations of the results which are ground for future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results proved are of interest, especially as the existing literature on the subject is scarce and in particular there has not been many works studying the Elo process as a Markov chain. The paper is quite well-written and does a good job at conveying the main ideas of the proof. The mathematical content is serious and I have not detected any major mistake in the proofs.", "weaknesses": "I do not see any particular weakness to the present manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer greatly for their extremely thorough review of our paper. We are pleased they found the results of interest and importance, as well as finding the presentation well-written. No general points were raised, but many (very helpful) minor points were. We just wanted to highlight a few here.\n\n(4) p.3 l.103. This follows from the Dirichlet characterisation (Prop B.1, with the corrected factor of 1/2). Fix $k$ and take $z_i \\coloneqq 1\\\\{i = k\\\\} - 1/n$. This gives Rayleigh quotient $n/(n-1) \\cdot \\sum_l q_{k,l}$. Since $\\sum_k \\sum_l q_{k,l} = 2$, we can choose $k$ so that $\\sum_l q_{k,l} \\le 2/n$. Hence, $\\lambda \\le 2/(n-1) \\le 4/n$.\n\n(6) p.5. You are correct that this version is for empirical averages, *not* mixing/similar. We shall clarify this.\n\n(7) p.5 in l.200 and l.202. This triangle merely indicates the end of a remark/similar, analogously to a square at the end of a proof. We first saw this used in one of Geoffrey Grimmett's books, and liked it.\n\n(11) p.16 l.548. We weren't aware that this is just the convergence theorem on Hilbert spaces. Functional analysis is far from our area of expertise. And, actually, looking online, we don't see exactly how this relates. If you would be able to provide a reference, that would be very appreciated. \\\nWe agree a stackexchange post is not the best reference, but we found the proof referenced quite elegant, so we decided to cite it.\n\n(19) p.21. This was supposed to be $p_{i,j}(\\rho)$. At one stage, we were using $\\pi_{i,j}$ for the true probabilities and $p_{i,j}$ for the estimated ones, but decided it was better to be explicit, writing $p_{i,j}(\\cdot)$ where $\\cdot$ varies. Apologies for missing this one; it will be corrected.\n\n(22) p.22. You're right: *uniform* ergodicity is required. Fortunately, chains on compact spaces which converge in TV are almost always uniformly ergodic in practice, and this is the case for the noisy Elo chain. In fact, positive curvature immediately implies this. We will address this lack of clarity in the camera-ready version.\n\n(24) p.22 Theorem D.7. You're right again: we meant *1*-Lipschitz functions. This is of course without loss of generality since, if $f$ is L-Lipschitz, then $g(x) := f(x)/L$ is 1-Lipschitz, so this is enough for the proof. But we would need to add in the dependence on the Lipschitz constant  as you rightly point out. We will clarify this in the revised version of our manuscript\n\n(27) p.23 l.741-743 (31) p.26 l.831. Good spot. We changed the definition of $\\delta$ (namely, the power of $n$) whilst writing the paper, and have clearly made a couple of mistakes. Hopefully, there is no cause for doubt that the argument works, but we definitely should correct the numbers so that it's all above board.\n\n(32) p.26 l.834. Good spot, we have conflicting definitions of tmix, differing by a factor 800. We shall correct this, making sure that the correct constants appear in the appropriate places.\n\n(36) p.29 l.898. We first sample a permutation $\\Sigma$ from the Birkhoff-von Neumann decomposition; we then decompose $\\Sigma$ into disjoint cycles; for any disjoint cycle we sample one of the three matchings described in the bullet list in the paper, each with probability $1/3$. So at the end, edges coming from all cycles in $\\Sigma$ will appear in the final sampled matching, but not all edges of a given cycle, only a vertex-disjoint subset.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the Elo rating system, a popular method to calculate relative skills in zero-sum games. The authors assume a BTL model and show that the Elo rating converges fast with high probability.

I have carefully read the paper, the reviews, and the rebuttal. I like this work, and I think the conclusions it provides and the tools it develops are interesting to the community.

Overall, I recommend acceptance.
Decision: Accept (poster)