An Analysis of Elo Rating Systems via Markov Chains

Authors: sam  olesker-taylor
luca  zanetti
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 10:39:37

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.

Main paper: 
 introduction: 
 The Elo rating system is a popular method for calculating the relative skills of players (or teams) in sports analytics and particularly chess [2, 4, 1, 3] . It is based on a simple zero-sum update rule: if player i beats player j, then the rating of player i increases proportionally to the model probability that i would lose to j, while the rating of j decreases by the same amount. This amount depends on the previously estimated difference in skills between i and j.Despite their widespread popularity, Elo rating systems still lack a rigorous theoretical understanding [6] . Here, we take a probabilistic approach and study Elo under the well-known Bradley-Terry-Luce model (BTL) [11, 28] . In this model, the probability p i,j that i wins against j is w i /(w i + w j ), where w k is the strength of player k. In Elo, this is usually reparametrised via w k = e ρ k : p i,j = e ρi /(e ρi + e ρj ) = 1/(1 + e ρj -ρi ) = σ(ρ i -ρ j ), where ρ k is the true rating of k and σ(z) := 1/(1 + exp(-z)) for z ∈ R is the sigmoid function. In this setting, after observing i beat j, the corresponding Elo ratings x i and x j are updated as x i ← x i + ησ(x j -x i ) and x j ← x j -ησ(x j -x i ), where the step-size η > 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 n players by observing results of matches between pairs of players. It is, therefore, aiming to solve the problem of ranking from pairwise comparisons. Compared with most algorithms in the area [5, 20, 27, 31, 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 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 a convex optimisation angle, however, we take a more probabilistic point of view: we assume at each time t, players i and j are selected to play against one another with probability q i,j . This allows us to interpret Elo as a Markov chain over R n and deploy powerful tools to study its behaviour. On the other hand, this approach also presents us with some challenges: Elo is not a reversible Markov chain and, while it has a unique stationary distribution, assuming a minor and natural condition on (q i,j ) i,j [7] , it does not converge to it in total variation [6] .Our main contribution (Theorem 2.5) shows that Elo ratings, averaged over time, well-approximate the true ratings of the players with high probability. In order to 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 to the number of observed matches that are competitive against the state of the art in the BTL literature. In contrast to most other algorithms for the BTL model studied in the literature, Elo learns the parameters of a BTL model in an online fashion. These rates of convergence is remarkable since Elo was originally conceived as a simple ranking system for chess players. Furthermore, our approach is very robust, and also applies to a parallel set-up in which multiple games are played concurrently.We also discuss the problem of tournament design: we assume we are given a tournament (comparison) graph G = ([n], E), and we would like to choose the match-up probabilities (q i,j ) {i,j}∈E so that Elo's convergence rate is maximised. We highlight a 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 or continuous time depending on whether we 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.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 [6] , and the unpublished notes [7] by the same author, in which Elo is studied as a Markov process and convergence in distribution to a unique stationary distribution is proved.If we consider Elo as a technique to estimate the parameters of the BTL model, there is a wealth of recent literature on the topic by the machine learning community [20, 37, 31, 5, 27, 9] . In contrast to our setting, however, previous work typically considers an 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 a very good approximation of the probability a 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 are dynamically updated before 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.A 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] .1. Choose unordered pair {I, J} to play according to q: P[{I, J} = {i, j}] = q {i,j} for all i, j ∈ [n].2. Suppose that Player I beats J, which has probability σ(ρ I -ρ J ). Update ratings x I and x J :x I ← x I + ησ(x J -x I ); x J ← x J -ησ(x J -x I ). 
comparison with related work: 
 In this section, we 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-art algorithms in the offline setting for a wide range of parameters.Our results imply that Elo provides an estimator ρ of ρ with ∥ρ -ρ∥ 2 2 ≲ e 4M (log n) 2 /(λ 2 q t) whp. This matches, up to a log factor, the results by Hajek, Oh and Xu [20] , who prove that the MLE constrained on 2 2 ≲ e 8M log n/(λ 2 q t). The dependency on λ q has been improved by Shah, Balakrishnan and Bradley [37] , who show ∥ρ MLC -ρ∥ 2 2 ≲ ne 8M log n/(λ q t). Since n/λ q ≥ 1/4, this is at least as good as our result, and potentially better for certain choices of q. However, up to log factors, our result matches theirs when q corresponds to sampling edges of an expander graph-e.g., a complete graph, or an Erdős-Rényi graph with parameter p ≫ (log n)/n. Our result improves the constant in front of M .[-M, M ] n ∩{x ∈ R n | k x k = 0}, ρ MLC , satisfies ∥ρ MLC -ρ∥More recently, Li, Shrotriya and Rinaldo [27] proved a regularised version of the MLE, ρ MLR , achieves ∥ρ MLR -ρ∥ 2 2 ≲ e 2M E δ/(λ 2 q t), where δ is the ratio between the maximum and average degree of thecomparison graph G = ([n], E) with E = {{i, j} | q i,j > 0} and M E = max i,j:qi,j >0 |ρ i -ρ j | ≤ 2 max k |ρ k |.A version of our analysis also applies with M E , instead of M , but we are not able to prove max i,j:qi,j >0 |X t i -X t j | < M E + 1 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., q i,j = 1/|E| for {i, j} ∈ E. Both limitations are particularly problematic in the context of tournament design discussed in §3. On the other hand, they obtain ℓ ∞ error bounds too. We refer to [27] for further discussion of previous work.We now highlight the key steps in estimating the MCMC-type error 1 n ∥A t,T -ρ∥ 2 2 in Theorem 2.5, where A t,T is the t-step time average of the ratings X after a burn-in phase of length T . We use∥A t,T -ρ∥ 2 ≤ ∥A t,T -E π [X 0 ]∥ 2 + ∥ E π [X 0 ] -ρ∥ 2 ,bounding these error and bias terms separately, via Theorems 2.8 and 2.7, respectively. Their proofs rely on estimating the change in ℓ 2 norm a single step, and using the Lipschitz property of the sigmoid function σ, 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 difficulties. Particularly, the aforementioned results reliant only on curvature are not sufficiently strong for our purposes.A further complication is that Elo is a non-reversible Markov chain. There is a 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 as non-backtracking, lifting, or zig-zag; see, e.g., [14, 16, 30, 8, 25] . Even an alternative definition of the spectral gap has been proposed [13] ; this gap controls convergence of empirical averages, rather than convergence to equilibrium.Unfortunately, the majority of general concentration results based on spectral properties [19, 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, [15, 35] . However, Elo does not converge in total variation! Indeed, X t is finitely supported, on at most (2n) t states, given X 0 , but π is continuous. These (2n) t states can be used to distinguish X t and π. Nevertheless, it is this mixing-time approach that we adapt.The contraction property implies that two realisations X and Y can be coupled so that their expected relative distance decreases exponentially, with rate κ. This is ideal for using the coupling approach to mixing. However, it is not possible to guarantee that X t = Y t at some point, due to the chain's finite support. Instead, we analyse a 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 t = V t . 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 t+1/2 according to an uncapped Elo step started from U t -i.e., as if M = ∞.Suppose that Players i and j were chosen-i.e., {k | Ut+1/2 k ̸ = U t k } = {i, j}. 2. Draw Ũi , Ũj ∼ iid Unif([- √ δ, + √ δ]) independently and set Ũk := 0 for k / ∈ {i, j}. SetU t+1 k := U t+1/2 k + Ũk for k ∈ [n].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∥X t+1 -U t+1 ∥ 1 ≤ ∥X t+1/2 -U t+1/2 ∥ 1 + 2 √ δ ≤ ∥X t -U t ∥ 1 + 2 √ δ ≤ ... ≤ 2t √ δ.The second inequality actually says that Elo is non-negatively curved in ℓ 1 . Iterating this,1 t t-1 s=0 X s -1 t t-1 s=0 U s 1 ≤ 1 t t-1 s=0 ∥X s -U s ∥ 1 ≤ t √ δ deterministically. △ Curvature.We use 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-κ contraction:E u 0 ,v 0 [∥U 1 -V 1 ∥ 2 ] ≤ E u 0 ,v 0 [∥U 1/2 -V 1/2 ∥ 2 ] ≤ (1 -κ)∥u 0 -v 0 ∥ 2 . △Mixing Time. We bound the total-variation mixing time of the noisy chain via the coupling method:P u 0 [U t ∈ •] -P v 0 [V t ∈ •] TV ≤ P (u 0 ,v 0 ) [U t ̸ = V t ]. 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-κ curvature,E[∥U t -V t ∥ 2 ] ≤ (1 -κ) t ∥U 0 -V 0 ∥ 2 ≤ 2M ne -κt ≤ δ 2 if t ≥ t δ := κ -1 log(2M n/δ 2 ). Hence, P[∥U t -V t ∥ ∞ > δ] ≤ P[∥U t -V t ∥ 2 > δ] ≤ δ if t ≥ t δ .Once the absolute difference |U t δ k -V t δ k | are at most δ for all k, the additive noise, which is order √ δ, dominates the change in difference after a single Elo step, which is order δ. Thus, with complementary probability order δ/ √ δ = √ δ, we can couple the noise so that the rating of a player is the same in both U and in V after they play a game. Moreover, such a successful step preserves the ℓ ∞ bound of δ.The ℓ ∞ bound implies that all players are chosen within t δ steps with probability at least 1 -δ. Hence, the probability of not successfully matching all ratings after t δ steps is at most order δ + √ δt δ .Combining these two bounds gives a bound of order δ + √ δt δ on the total-variation distance at time 2t δ . The polynomial-growth/decay assumptions in the theorem allow us to choose δ to be an appropriate inverse polynomial (in n) and obtain δ +√ δt δ ≪ 1 and t δ ≍ κ -1 log n ≍ t ⋆ . △The above mixing-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 t ⋆ , then-log P π 1 t t-1 s=0 f (Z s ) -π f ≥ ζ ≳ σ -2 f ζ 2 t/t ⋆ , where π f = E π [f ] and σ 2 f := Var π [f ].Notice that this requires Z 0 ∼ π, 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 := f k 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ζ 2 k ≍ σ 2 f k t ⋆ log n t , which satisfies 1 n k ζ 2 k ≍ η λ q n log n λ q η log n t = 1 λ q n (log n) 2 λ q t ,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:1 t t-1 s=0 X s -1 t t-1 s=0 U s 1 ≤ 1 t t-1 s=0 ∥X s -U s ∥ 1 ≤ t √ δ deterministically.We are taking t to be polynomial in n, and can choose δ -1 to be a sufficiently large polynomial so that this accumulated error is small. Care must be taken to to make all this rigorous, but once it is done, we are able to deduce the concentration result for the original Elo process.3 Tournament Design 
orthogonally project the full vector of ratings to: 
 [-M, M ] n ∩ {x ′ ∈ R n | k x ′ k = 0}. Let X tk denote the rating of Player k at time t, and π the equilibrium distribution on R n . Denote by A t,T k := 1 t T +t-1 s=T X s k for k ∈ [n] and t, T > 0 the time-averaged ratings. We typically start from X 0 = (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. It is required for our analysis, but not usually implemented in practice. Indeed, our experiments, discussed in §4, suggest that, as long as the step-size η 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 t, T and η, 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 0 k ] ̸ = ρ k . Hence, there will be both a bias and an error term in our MCMC-type estimate of ∥A t,T -ρ∥ 2 .The MCMC convergence rate depends on a spectral gap λ q . 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, e.g., [37, 27] . Definition 2.3 (Spectral Gap). Let q be a distribution on unordered pairs in [n]. Define q i,j := q {i,j} , d i,j := 1{i = j} k q i,k and ∆ i,j := d i,j -q i,j for i, j ∈ [n]. Let λ q denote the spectral gap (second smallest eigenvalue) of the Laplacian ∆. Always, ∆1 = 0 and ∆ is positive semi-definite. Remark 2.4. Equivalently, λ q is the spectral gap of the continuous-time Markov chain on [n] with transition rates q i,j = q {i,j} for i, j ∈ [n]. Note the scaling: i,j q i,j = 2. So, the typical time until the continuous-time chain jumps is order n, not order 1. This implies λ q ≤ 4/n; see Lemma B.2.We assume λ q > 0. This holds unless there exists a non-empty subset S ⊊ [n] with i∈S,j̸ ∈S q i,j = 0-i.e., players in S never play those in S c . 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 ∼ Elo M (q, ρ; η), as in Definition 2.1. Let C 1 , C 2 < ∞. Then, there exists a constant C 0 , depending only on (C 1 , C 2 ), such that if min{λ q , η, 1/t} ≥ n -C1 and min{t, T } ≥ C 0 t ⋆ , where t ⋆ := e 2M η -1 λ -1 q log n, thenP 1 n ∥A t,T -ρ∥ 2 2 ≤ C 0 e 4M λ q n η + (log n) 2 λ q t ≥ 1 -n -C2 .In particular, if η ≍ (log n) 2 /(λ q t), then1 n ∥A t,T -ρ∥ 2 2 ≲ e 4M (log n) 2 λ q n 1 λ q t whp as n → ∞.Remark 2.6. Ideally, λ q n = Ω(1); e.g., if q is uniform over the edges of an expander graph, then λ q n ≍ 1. In this case, we view (log n) 2 /(λ q n) = Õ(1) as the error's pre-factor and 1/(λ q t) as the (squared) convergence rate. Also, we can then choose η = Ω(1) and obtain non-trivial convergence results. This choice of η is comparable to that used in practice. Moreover, on average, only Õ(1) games per player are need to be observed to guarantee good approximation of the ratings.The η term arises from the average bias1 n ∥ E X∼π [X]-ρ∥ 2 2, which is non-zero in general. An estimate on the average variance 1 n k Var X∼π [X k ] is necessary to obtain the MCMC convergence rate. Theorem 2.7 (Bias and Variance). If π is the equilibrium distribution of Elo M (q, ρ; η), then1 n ∥ E X∼π [X] -ρ∥ 2 2 ≤ 4e 4M η/(λ q n) and 1 n k Var X∼π [X k ] ≤ 4e 2M η/(λ q n).Despite Elo ratings being biased, the estimated probability a player wins their next match is not:j∈[n] q i,j E X∼π [σ(X i -X j )] = j∈[n] q i,j σ(ρ i -ρ j ) for all i ∈ [n]. This holds when no projection step is performed as part of the Elo update (equivalently, M := +∞).The mixing time is more delicate, as the chain makes deterministic-size discrete jumps, but its equilibrium 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 ∼ Elo M (q, ρ; η), then there exists a step-by-step coupling withE (x,y) [∥X t -Y t ∥ 2 2 ] ≤ (1 -κ) t ∥x -y∥ 2 2where κ := 1 8 e -2M ηλ.Markov chains satisfying the contraction property (i.e., positively curved) satisfy powerful concentration inequalities, developed particularly by Joulin and Ollivier [22, 23, 34, 33, 24] . The idea is that if∥X 0 -Y 0 ∥ 2 = D 0 , then D t := ∥X t -Y t ∥ 2 is small when t ≍ κ -1 log D 0 . For us, D 0 ≤ 2M n, leading to t ⋆ ≍ κ -1 log n.In the reversible case, this can provide bounds, e.g., on the spectral gap.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,E[D t ] ≤ 1 2 implies P[X t = Y t ] ≥ 1 2, since the minimum graph distance between x ̸ = y is 1. Our underlying metric space is (R n , ∥ • ∥ 2 ), however. Inequalities for this more general set-up have been developed, but they often give weaker bounds. In our case, they lose a factor 1/(ηλ q ) ≳ n in the convergence rate. Morally, though, the exponential convergence at rate κ still implies that 1/κ 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.In this section, we assume we are given a comparison graph G = ([n], E), where edge {i, j} ∈ E indicates that Players i and j are able to play against one another. We want to construct a distribution q 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 λ q . So, we want to maximise λ q . Let λ ⋆ cts := sup λ q q ∈ [0, 1] E , e∈E q e = 1 . This equals the largest spectral gap achievable by a continuous-time Markov chain on [n] with transitions only across edges of G and average jump-rate 1/n. It is the fastest-mixing Markov chain problem, introduced by Sun et al. [39] , and can be formulated as a semidefinite program. Olesker-Taylor and Zanetti [32] recently proved that λ ⋆ cts n ≳ 1/(diam G) 2 . This implies the following.Corollary 3.1 (Optimised q). Suppose that the comparison graph G = ([n], E) is given. In the set-up of Theorem 2.5, there exists a distribution q on the edges E such that1 n ∥A t,T -ρ∥ 2 2 ≲ n(diam G) 2 (log n) 2 /t whp if η ≲ n(diam G) 2 (log n) 2 /t.This choice of probabilities q can improve drastically over uniform weights-as used by [27] . E.g., if G consists of two cliques connected by k edges, then λ q n ≲ k/n 2 when q e := 1/|E| is uniform over E, whilst the optimal λ ⋆ cts n ≍ 1 [32] . As a consequence, with the optimal choice of q, only Õ(n) total matches need to be played to obtain a good approximation of the true ratings, compared with Õ(n 3 /k) for a uniform q. Here, Õ(•) indicates the asymptotic order up to logarithmic factors. This demonstrates the power of being able to choose q, given G.Elo naturally parallelises: if two games consist of disjoint pairs of players, then the Elo update resulting from one is independent of the result of the other. Hence, if we wish to minimise the number of rounds (i.e., sets of games that can be played in parallel), rather than games, we should consider a distribution q on the set M of matchings of the graph G = ([n], E)-i.e., collections of disjoint edges. Definition 3.2 (Parallel Elo). Let q be a distribution on M. A single step of ParElo M (q, ρ; η) first selects a matching S ⊆ E according to q and applies the Elo update (with scale η) to each pair in S. Then, the resulting vector is orthogonally projected back to zero-sum vectors in [-M, +M ] n .Our analysis is robust enough to handle the parallel case, obtaining convergence rate 1/(λ q t), where now q e is the marginal probability that edge e ∈ E appears in the matching: q e := S∈M:e∈S qS . Theorem 3.3 (Parallel). Let X ∼ ParElo M (q, ρ; η). Then, under the conditions of Theorem 2.5,1 n ∥A t,T -ρ∥ 2 2 ≲ e 4M (log n) 2 λ q n/N 1 λ q t whp if η ≍ (log n) 2 λ q t ,where N := e∈E q e is the mean size of the matching. To emphasise, here, t 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 λ q over q which can arise as the marginals of a distribution q on M. Clearly,q k := e∈E:k∈e q e ≤ 1 for all k ∈ [n]for any such q. Thus, the matrix Q = (q i,j ) i,j∈V is substochastic, so λ q corresponds to the spectral gap of the discrete-time Markov chain on G = ([n], E) with weights q i,j = q {i,j} . Letλ ⋆ disc := sup{λ q | q ∈ [0, 1] E , max k∈[n] q k ≤ 1}. This is the optimal spectral gap of a discrete-time Markov chain on [n] with transitions allowed only across edges of G and uniform stationary distribution. Again, λ ⋆ disc can be formulated as a semidefinite program [10] and is related to the vertex conductance via a Cheeger-type inequality [32] .We show that a distribution q over matchings with λ q ≥ 1 3 λ ⋆ disc can be found by decomposing the substochastic Q into a convex combination of permutation matrices using the Birkhoff-von-Neumann theorem, followed by decomposing each permutation into disjoint cycles. Corollary 3.5 (Optimised q). 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 that1 n ∥A t,T -ρ∥ 2 2 ≲ e 4M (log n) 2 λ ⋆ disc n/N 1 λ ⋆ disc t whp if η ≍ (log n) 2 λ ⋆ disc t . In many examples, such as if G = ([n], E) is an expander, but also if G is a cycle, then λ ⋆ disc ≍ nλ ⋆ cts .In this case, parallel Elo really is as good, up to constants, as n steps of the original ('series') Elo. (Recall that N = e q e = 1 is required for λ ⋆ cts , but that N ≍ n is possible for λ ⋆ disc .) Other times, there is already a continuous-time chain, with average jump-rate 1, which has spectral gap order 1; e.g., two cliques connected by a single edge. In this case, the optimal parallel version gives no real improvement, even measured by rounds, over the optimally weighted series version.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 al. [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 a 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 [27] . They discuss a divide-andconquer 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-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.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 a graph topology, which is related to the diameter of the graph [32] . Moreover, both λ ⋆ cts and λ ⋆ disc can be formulated as SDPs, for which fast (polynomialtime) 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.par derived from the fastest mixing discrete-time Markov chain, where multiple games are played in parallel in each round.From §3, we know that λ q U ≍ k/n 3 , λ q ⋆ seq ≍ 1/n and λ q ⋆ par ≍ k/n. We sample the true ratings of the players according to independent Gaussians, with mean equal to 1 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 cliques correspond to two different leagues of slightly different strength on average. We perform Elo simulations initialising the Elo ratings at zero and setting η = 0.1. For each graph, we repeat each experiment ten times, each time sampling new true ratings. Experimental results are displayed in Figures 1 and 2 . Simulations are repeated ten times: lines correspond to the average ℓ 2 2 -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 4 games (same number of games displayed in cyan).We display the experimental results for k = 1, i.e., two cliques of 20 vertices connected by a single edge, in Figure 1 . The experiments align with the theoretical results of §3: when k = 1, the spectral gap λ q ⋆ seq of the optimal sequential distribution is of the same order of the spectral gap for our nearly parallel construction λ q ⋆ par . 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 number of games rather than rounds, the parallel version still results in a faster convergence than the uniform distribution, but not overwhelmingly so.We now consider a dumbbell graph with k = n/2, i.e., two cliques connected by a 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 a 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 at 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/n 2 spectral gap. In the optimal parallel and sequential distributions, the probability to sample an edge from the bottleneck or from inside the cliques is balanced, while the uniform distribution oversamples edges inside the cliques. Experiments for the intermediate case of k ∈ {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 a complete graph). The true ratings are sampled uniformly at random in [-1, 1]. The initial Elo ratings are set equal to zero. We simulate up to 50000 matches for a 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 diverge for a long time. Further experiments and discussions are given in the Appendix. 
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 ∈ {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 q U over the edges of the graph. 2. The optimal sequential q ⋆ seq derived from the fastest-mixing continuous-time Markov chain.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: in the main body of the paper, we include enough details in order to reproduce 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 or 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 is a specific model and empirical evaluation, it 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example , with an open-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 to 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. 
conclusion and open problems: 
 Our work is a first step towards establishing the theoretical foundations of the Elo rating system, a popular ranking method in sports analytics. In particular, our main contribution is 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 ℓ ∞ .Finally, a touted strength of the Elo rating system in practical applications is its ability to dynamically update the ratings in response to changes in players' skills. Can we model these changes in a 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? 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 to 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 as 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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 a 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 a 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:[Yes] Justification: our code uses an existing library to compute a von Neumann-Birkhoff decomposition of a matrix. We have included the library and its licence in the supplementary material. Guidelines:• The answer NA means that the paper does not 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 a 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 be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
 
 Appendix: 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 to dumbbell graphs. In particular, we consider graphs consisting of two cliques of 20 vertices connected by 5 (left) and 10 (right) edges arranged in a matching. The experimental setup is the same as the one 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 really improve its spectral gap, which depends mainly on the (unchanged) diameter. We also consider a pyramidal graph, which is constructed as follows. We first sample three Erdős-Rényi random graphs with size, resp., n 1 = 64, n 2 = 32 and n 3 = 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 5 ). This graph is constructed to 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, we repeat the simulations ten 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-Rényi at the bottom of the pyramid, mean 1 for the Erdős-Rényi in the middle, 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 6 . 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 §3: 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 a topology corresponding to the giant component of an Erdős-Rényi random graph of n = 100 vertices and density p = 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 on 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 a 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. 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 8 , we present experiments for a 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 i won't increase by much. This is because the sigmoid function σ 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 i cannot maintain an abnormally large rating for too long. Indeed, it appears very unlikely that such balanced but "abnormal" configurations are ever reached. In the two-player case, the situation is simpler: if player 1 has Elo rating x 1 , then player 2 has x 2 = -x 1 , 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 x 1 before a game, then their rating x ′ 1 after the game hasE[|x ′ 1 -ρ 1 |] < |x 1 -ρ 1 |, if η < 1 2 .Suppose that the same argument holds for n > 2 players: i.e., typically, Elo ratings are biased towards the true skills. Biased random walks on R have exponential tails. So, if η ≪ 1/ log n, then it is super-polynomially unlikely that a 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/n 10 .Unfortunately, we weren't able to make this argument formal for n > 2 players. We leave proving that indeed, with high probability, the maximum rating remains small for a large number of steps as an open problem.There are a few results which we use repeatedly throughout the proofs. We collect them here.Recall that λ q is the spectral gap of the continuous-time Markov chain on [n] with transition rates (q i,j ) i,j∈ [n] . We repeatedly use the standard Dirichlet characterisation of the spectral gap. Proposition B.1 (Dirichlet Characterisation of the Spectral Gap). The spectral gap λ q satisfiesλ q = 1 2 min z∈R n \{0}:z⊥1 i,j∈[n] q i,j (z i -z j ) 2 ∥z∥ 2 2 .In particular, for all z ∈ R n with k z k = 0,i,j∈[n] q i,j (z i -z j ) 2 ≥ 2λ q ∥z∥ 2 2 . Lemma B.2. Let q i,j ∈ [0, 1]for all i, j ∈ [n] with i,j q i,j = 2. Let λ q denote the spectral gap of the continuous-time Markov chain on [n] with transition rates (q i,j ) i,j∈ [n] . Then, λ q ≤ 2/(n -1) ≤ 4/n.Proof. We apply the Dirichlet characterisation (Proposition B.1) withz i := 1{i = k} -1 n . Then, z ⊥ 1, ∥z∥ 2 2 = (1 -1/n) 2 + (n -1)/n 2 = 1 -1/n = (n -1)/n and 1 2 i,j∈[n] q i,j (z i -z j ) 2 /∥z∥ 2 2 = 1 2 i,j∈[n] q i,j (1{i = k} -1{j = k}) 2 n n-1 = 1 2 n n-1 j:j̸ =k q k,j + i:i̸ =k q i,k = n n-1 ℓ q k,ℓ .Choosing k to minimise this final sum gives ℓ q k,ℓ ≤ 2 n since the average1 n k ℓ q k,ℓ = 2 n . So, λ q ≤ n n-1 • 2 n = 2/(n -1) ≤ 4/n.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 is already biased in the sense that the expected rating in equilibrium is not the true rating:E π [X] ̸ = ρ.The only property of the projection that we use is the following monotonicity result. Proposition B.3 (Projection Monotonicity). Let Ω ⊆ R n be a closed, convex set. DefineΠ Ω (x) := arg min x ′ ∈Ω ∥x -x ′ ∥ 2 for x ∈ R n ;that is, Π Ω is the orthogonal projection to Ω. Then,∥Π Ω (x) -Π Ω (y)∥ 2 ≤ ∥x -y∥ 2 for all x, y ∈ R n ;that is, Π Ω (x) is at least as close to Π Ω (y) as x is to y, in ℓ 2 .Versions of this result are well-known. An elementary proof can be found at [29] . We apply this withΩ := {x ∈ R n | ∥x∥ ∞ ≤ M, k x k = 0}, which is convex. Our results apply whenever this monotonicity property holds.The orthogonal projection Π Ω (x) can be efficiently computed as follows. We first project x to {y ∈ R n | ∥y∥ ∞ ≤ M }. This can be done by simply replacing any x i < -M with -M and any x i > M with M . Let x ′ be the resulting vector. Notice that x ′ might not satisfy the constraint k x ′ k = 0: we need to subtract the displaced mass k x ′ k to the rest of the vector while minimising Π Ω (x) := arg min x ′′ ∈Ω ∥x -x ′′ ∥ 2 . Assume k x ′ k > 0 (the symmetric case can be handled similarly). We set x ′′ i = -M for all the coordinates i such that x ′ i = -M and call i frozen. To minimise ∥x -x ′′ ∥ 2 , we want to distributek x ′ k to the unfrozen coordinates so that x -x ′′ 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 ′′ i = -M for a new, previously unfrozen, coordinate i before we have subtracted all the displaced mass. If that happens, we simply freeze i and proceed in distributing the remaining displaced mass to the unfrozen coordinates (until a new coordinate is frozen). We keep repeating the procedure since all the mass is allocated. Notice that we can allocate all the mass since we assumed k x ′ k > 0. Moreover, the procedure lasts at most n steps since at each step we freeze a new coordinate until we have completed constructing the desired vector.There is an inherent bias and variance in the Elo ratings. It would be natural to 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 denotep i,j (z) := σ(z i -z j ) for z ∈ R n and i, j ∈ [n].In particular, p i,j (ρ) is the true probability that Player i beats j and p i,j (x) is the model probability if the current ratings are x. Additionally, we split up the Elo step into the update and the projection:• if the current vector is X t , then let X t+1/2 denote an uncapped step;• then, X t+1 = Π M (X t+1/2 ), where Π M is the orthogonal projection.We do not quantify the bias and variance player-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 π [X 0 ] -ρ∥ 2 2 ≤ E π [∥X 0 -ρ∥ 2 2 ] ≤ 4e 4M η/λ q ; k Var π [X 0 k ] = E π [∥X 0 -E π [X 0 ]∥ 2 2 ] ≤ 4e 2M η/λ q .Proof: Bias. First and foremost, the Cauchy-Schwarz inequality gives∥ E π [X 0 ] -ρ∥ 2 2 ≤ E π [∥X 0 -ρ∥ 2 2 ].We start the system from equilibrium and use stationarity: X 0 ∼ π =⇒ X 1 ∼ π. Also, we can ignore the projection step, whilst still assuming that all vectors have ℓ ∞ norm at most M , due to the projection monotonicity of Proposition B.3: noting that ∥ρ∥ ∞ ≤ M , so Π M (ρ) = ρ, we have∥X 1 -ρ∥ 2 = ∥Π M (X 1/2 ) -π M (ρ)∥ 2 ≤ ∥X 1/2 -ρ∥ 2 .Write E x,{i,j} [•] to indicate that the pair {i, j} is chosen in the first step and X 0 = x. Then,E x,{i,j} (X 1/2 i -ρ i ) 2 = p i,j (ρ) x i -ρ i + η 1 -p i,j (x) 2 + 1 -p i,j (ρ) x i -ρ i -ηp i,j (x) 2 = (x i -ρ i ) 2 + η 2 p i,j (ρ) 1 -p i,j (x) 2 + 1 -p i,j (ρ) p i,j (x) 2 + 2η p i,j (ρ) 1 -p i,j (x) -1 -p i,j (ρ) p i,j (x) (x i -ρ i ) ≤ (x i -ρ i ) 2 + η 2 -2η p i,j (x) -p i,j (ρ) (x i -ρ i ).An analogous statement holds for X 1/2 j -ρ j , with i and j swapped:E x,{i,j} (X 1/2 j -ρ j ) 2 ≤ (x j -ρ j ) 2 + η 2 -2η p j,i (x) -p j,i (ρ) (x j -ρ j ) = (x j -ρ j ) 2 + η 2 + 2η p i,j (x) -p i,j (ρ) (x j -ρ j ),using the fact that p j,i (•) = 1 -p i,j (•). For k / ∈ {i, j},E x,{i,j} (X 1/2 k -ρ k ) 2 = (x k -ρ k ) 2 .Bringing these three cases (indicesk = i, k = j and k ∈ [n] \ {i, j}) together, E x,{i,j} ∥X 1/2 -ρ∥ 2 2 ≤ ∥x -ρ∥ 2 2 + 2η 2 -2η p i,j (x) -p i,j (ρ) (x i -ρ i ) -(x j -ρ j ) = ∥x -ρ∥ 2 2 + 2η 2 -2η p i,j (x) -p i,j (ρ) (x i -x j ) -(ρ i -ρ j ) . Now, p i,j (x) -p i,j (ρ) = σ(x i -x j ) -σ(ρ i -ρ i ) and (x i -x j ) -(ρ i -ρ j ) have the same sign. Also, |p i,j (x) -p i,j (ρ)| = σ (x i -x j ) -(ρ i -ρ j ) + ρ i -ρ j ≥ min z ∈ [-4M, 4M ]|σ ′ (z)| • |(x i -x j ) -(ρ i -ρ j )| ≥ 1 4 e -4M |(x i -x j ) -(ρ i -ρ j )| since x i , x j , ρ i , ρ j ∈ [-M, M ], so |(x i -x j ) -(ρ i -ρ j )| ≤ 4M and σ ′ (z) = σ(z) 1 -σ(z) . Hence, E x,{i,j} ∥X 1/2 -ρ∥ 2 2 ≤ ∥x -ρ∥ 2 2 + 2η 2 -1 2 η (x i -x j ) -(ρ i -ρ j ) 2 = ∥x -ρ∥ 2 2 + 2η 2 -1 2 e -4M η (x i -ρ i ) -(x j -ρ j ) 2 .We now average this over {i, j}:E x ∥X 1/2 -ρ∥ 2 2 ≤ ∥x -ρ∥ 2 2 + 2η 2 -1 2 e -4M η i,j q {i,j} |(x i -ρ i ) -(x j -ρ j )| 2 .:= x -ρ, E x ∥X 1/2 -ρ∥ 2 2 ≤ ∥x -ρ∥ 2 2 + 2η 2 -1 2 e -4M ηλ q ∥x -ρ∥ 2 2 = (1 -1 2 e -4M ηλ q )∥x -ρ∥ 2 2 + 2η 2 ; again, k z k = k x k -k ρ k = 0.In particular, stationarity implies thatE π ∥X 0 -ρ∥ 2 2 = E π ∥X 1 -ρ∥ 2 2 ≤ E π ∥X 1/2 -ρ∥ 2 2 ≤ 4e 4M η/λ q .We perform a 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 -1 2 e -4M ηλ q )-factor above suggests curvature κ ≍ e -4M ηλ q , which is indeed what we show in Proposition D.4.We now turn to the variance, for which we use a similar approach. It is a little more technically challenging, using the slightly cumbersome law of total variance: for random variables A and B,Var[B] = E[Var[B | A]] + Var[E[B | A]].Proof: Variance. The sum of variances is the expectation of an ℓ 2 distance:k Var[Z k ] = k E (Z k -E[Z k ]) 2 = E k (Z k -E[Z k ]) 2 = E ∥Z -E[Z]∥ 2 2 , for any random variable Z ∈ R n . Also, for any c ∈ R n , Var[Z] = E[(Z -E[Z]) 2 ] ≤ E[(Z -c) 2 ].Applying this and the monotonicity of the orthogonal projection from Proposition B.3 givesk Var[X 1 k ] = E ∥X 1 -E[X 1 ]∥ 2 2 ≤ E ∥Π M (X 1/2 ) -E[X 1/2 ]∥ 2 2 ≤ E ∥X 1/2 -E[X 1/2 ]∥ 2 2 = k Var[X 1/2]. Hence, it suffices to prove the bound for X 1/2 -i.e., for the Elo update without capping.Use subscript {i, j} to indicate that this pair is chosen in the first game, as before. Let {I, J} be a pair of (distinct) indices drawn according to q. Then, by the law of total variance,k Var[X 1/2 k ] = k E[Var {I,J} [X 1/2 k ]] + k Var[E {I,J} [X 1/2 k ]].We studied the first term (aka the "unexplained variance") first. First,k E[Var {I,J} [X 1/2 k ]] = k i,j q {i,j} Var {i,j} [X 1/2 k ] = i,j q {i,j} k Var {i,j} [X 1/2 k ].We now bound Var {i,j} [X 1/2 k ] over three cases: k = i, k = j and k / ∈ {i, j}. We haveVar {i,j} [X 1/2 i ] = Var {i,j} [X 0 i -ηp i,j (X 0 )] + η 2 Var {i,j} Bern(p i,j (ρ)) ≤ Var[X 0 i ] -2η Cov X 0 i , σ(X 0 i -X 0 j ) + 1 2 η 2 , since the maximal variance of a [0, 1]-valued random variable is 1 4 . Analogously, Var {i,j} [X 1/2 j ] ≤ Var[X 0 j ] -2η Cov[X 0 j , σ(X 0 j -X 0 i )] + 1 2 η 2 = Var[X 0 j ] + 2η Cov X 0 j , σ(X 0 i -X 0 j ) + 1 2 η 2 , since σ(-z) = 1 -σ(z). For k / ∈ {i, j}, Var {i,j} [X 1/2 k ] = Var[X 0 k ]. Bringing these three cases together, k Var {i,j} [X 1/2 k ] ≤ k Var[X 0 k ] + η 2 -2η Cov X 0 i -X 0 j , σ(X 0 i -X 0 j ) . Now, σ : R → [0, 1] is increasing. So, Cov[Y, σ(Y )] ≥ 0 for any random variable Y . Moreover, |σ(y)-1 2 | = |σ(y)-σ(0)| ≥ min z ∈ [-2M, 2M ]|σ ′ (z)|•|y| ≥ 1 4 e -2M |y| for all y ∈ [-2M, 2M ]. Since X 0 i -X 0 j ∈ [-2M, 2M ], applying this gives Cov {i,j} X 0 i -X 0 j , σ(X 0 i -X 0 j ) ≥ 1 4 e -2M Var {i,j} [X 0 i -X 0 j ]. Plugging this in above, k Var {i,j} [X 1/2 k ] ≤ k Var[X 0 k ] + η 2 -1 2 e -2M η Var {i,j} [X 0 i -X 0 j ].We now average over {i, j}:i,j q {i,j} k Var {i,j} [X 1/2 k ] ≤ k Var[X 0 k ] + η 2 -1 2 e -2M η i,j q {i,j} Var {i,j} [X 0 i -X 0 j ].Variances are (weighted) sums of squares, which leads to a spectral-gap estimate again:i,j q {i,j} Var {i,j} [X 0 i -X 0 j ] = i,j q {i,j} Var {i,j} (X 0 i -E[X 0 i ]) -(X 0 j -E[X 0 j ]) = i,j q {i,j} E (X 0 i -E[X 0 i ]) -(X 0 j -E[X 0 j ]) 2 = E i,j q {i,j} (X 0 i -E[X 0 i ]) -(X 0 j -E[X 0 j ]) 2 ≥ E λ q k (X 0 k -E[X 0 k ]) 2 = λ q k Var[X 0 k ],by applying the Dirichlet characterisation of the spectral gap with z := X 0 -E[X 0 ]. Thus, i,j q {i,j} k Var {i,j} [X1/2 k ] ≤ k Var[X 0 k ] + η 2 -1 2 e -2M ηλ q k Var[X 0 k ] = (1 -1 2 e -2M ηλ q ) k Var[X 0 k ] + η 2 .We would like to deduce that k Var π [X 0 k ] ≤ 4e 2M η/λ q now, analogously to before. But, we must remember the second term in the law of total variance (aka the "explained variance"). We haveVar E {I,J} [X 1/2 k ] ≤ 1 2 η 2 q k = 1 2 η 2 ℓ q {k,ℓ} .Indeed, if Player k is picked-i.e., k ∈ {I, J}-then X 1/2 k moves up/down to one of two values which differ by η; if Player k is not picked, then X 1/2 k does not move. The maximal variance of such a random variable is 1 2 η 2 q k , where q k = ℓ q {k,ℓ} is the probability that Player k is picked. Hence,k Var E {I,J} [X 1/2 k ] ≤ 1 2 η 2 k q k = η 2 , noting the double-counting of edges in k q k = k,ℓ q {k,ℓ} = 2.Combining the bounds for the unexplained and explained components of the variance,k Var[X 1/2 k ] ≤ (1 -1 2 e -2M ηλ q ) k Var[X 0 k ] + 2η 2 .In particular, stationarity implies that k Var π [X1/2 k ] = k Var π [X 0 k ], so k Var π [X 0 k ] = k Var π [X 1 k ] ≤ k Var π [X 1/2 k ] ≤ 4e 2M η/λ q .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 = ∞) implies thatE π [X i ] = E π X i + η j q {i,j} p i,j (ρ) -p i,j (X) = E π [X i ] + η j q {i,j} E π [p i,j (ρ)] -j q {i,j} E π [p i,j (X)]. Therefore, j q {i,j} p i,j (ρ) = j q {i,j} E π [p i,j (X)]. The right-hand side is the expectation of the estimated probability that Player i wins their next game (not conditioning on their opponent) in equilibrium and the left-hand side is 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 π [p 1,2 (X)] = p 1,2 (ρ). We can deduce from this, however, that the estimated rating is biased, if ρ ̸ = (0, 0). We do this now, but only informally.The ratings are zero-sum, so it suffices to consider X 1 and ρ 1 . Suppose that ρ 1 > 0 and that η is small-much smaller than ρ 1 . Then, the rating X 1 concentrates around ρ 1 . The win-probability function σ is strictly convex and increasing in (0, ∞), which suggests thatp 1,2 E π [X 1 ] < E π p 1,2 (X 1 ) = p 1,2 (ρ), and hence E π [X 1 ] ̸ = ρ.Of course, P π [X 1 > 0] ̸ = 1. This can be handled using the quantified version of Jensen's inequality and large deviation estimates on P π [X 1 < 0]. If ρ 1 is large, then, very roughly, the latter probability is like e -ρ 2 1 , whilst the quantified difference from equality is like e -ρ1 ; the latter dominates. The n-player case is more complicated. It is possible that a particular choice of (ρ, q) could lead to certain players' having unbiased estimates. However, they will be biased in general.The ratings are biased, typically, but the win-probabilities at equilibrium are unbiased in the uncapped setting. Moreover, the real ratings are the only vector ρ giving rise to these win-probabilities. Proposition C.3. Let x, ρ ∈ R n with k ρ k = 0 = k x k . Then, j q {i,j} p i,j (x) = j q {i,j} p i,j (ρ) for all i ∈ [k] if and only if x = ρ. Proof. The "if" direction is obvious. We prove the "only if" direction by constructing a minimisation problem over zero-sum vectors in R n with the following two properties:1. it has a unique minimum at ρ; 2. x is a minimum if and only if it satisfies the equations in the statement.Define f : R n → R by f (x) := i 1 2 j q {i,j} log 1 + e xi-xj -x i j q {i,j} p i,j (ρ) -1 2 for x ∈ R n . Then, f is strictly convex in {x ∈ R n | k x k = 0}, and thus has a unique minimiser in that set. We now take the gradient of f and compare it with 0: ∂f ∂xi (x) = 1 2 j q {i,j} 2p i,j (x)-1j q {i,j} p i,j (ρ)-1 2 = j q {i,j} p i,j (x)j q {i,j} p i,j (ρ). Hence, x is a minimum if and only if k x k = 0 and j q {i,j} p i,j (x) = j q {i,j} p i,j (ρ).Notice that if we only desire estimates on the win-probabilities, then the whole Elo framework is not needed: simply tracking the empirical proportion of games won between each pair of players suffices.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.We introduce the concept of curvature for a Markov chain P on a general metric space (Ω, d). Definition D.1 (Transportation Distance). Let µ and π be probability measures on Ω. The transportation distance W 1 (µ, π) represents the 'best' way to send µ to π so that, on average, points are moved by the smallest distance:W 1 (µ, π) := inf Q E Q d(X, Y ) ,where the infimum is over all couplings Q of (µ, π)-i.e., X ∼ µ and Y ∼ π, marginally, under Q. Definition D.2 (Curvature of Markov Chains). The (Ricci) curvature of P is κ P := inf x,y∈Ω κ x,y where κ x,y := 1 -W 1 (P x,• , P y,• )/d(x, y) for x, y ∈ Ω.A standard application of the triangle inequality and iteration establishing the following result. Lemma D.3 (Contraction of Distance). For all measures µ and π and all t ≥ 0,W 1 (µP, πP ) ≤ (1 -κ P )W 1 (µ, π) and W 1 (µP t , πP t ) ≤ (1 -κ P ) t W 1 (µ, π).This reduces to the well-known set-up of path coupling [12] when (Ω, d) is a finite graph endowed with the usual graph distance. Our set-up, however, is very different:(Ω, d) = (R n , ∥ • ∥ 2 ).Exact calculation of the curvature is rarely required. Rather, a 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 as close to 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.We determine the worst-case rate of contraction rate 1 -κ starting from ratings (x, y) ∈ Ω 2 : we show that κ ≳ λ q where λ q is the spectral gap of the auxiliary random walk with rates (q i,j ). Proposition D.4 (Curvature). Let κ denote the curvature of Elo in ∥ • ∥ 2 . Then,κ ≥ 1 8 ηe -2M λ q . Proof. Let x = (x k ) k∈[n] ∈ Ω and y = (y k ) k∈[n]∈ Ω be two sets of ratings. We want to boundE x,y [∥X 1 -Y 1 ∥ 2 ] ≤ (1 -ρ)∥x -y∥ 2for some ρ ≥ 0 under some coupling. First, we observe that we can ignore the projection step in the Elo update, by Proposition B.3:∥X 1 -Y 1 ∥ 2 = ∥Π M (X 1/2 ) -Π M (Y 1/2 )∥ 2 ≤ ∥X 1/2 -Y 1/2 ∥ 2 .Again, this is using the notation X 1/2 to indicate the uncapped Elo update, andX 1 = Π M (X 1/2 ).We thus study (X 1/2 , Y 1/2 ), under the assumption ∥x∥ ∞ , ∥y∥ ∞ ≤ M . We use the trivial coupling:• the same pair (I, J) of players is chosen;• the result of the match is the same-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 I beats J depends on the state, but the real probability does not. Write E {i,j} [•] for the law conditional on choosing pair {i, j} to play.Recall that, for z ∈ R n and i, j ∈ [n], we write p i,j (z) := σ(z j -z i ) for the estimated probability that i beats j using ratings z. If Player i beats j, then i gains ηp j,i points; similarly, i loses ηp j,i points if Player j beats i. Observing that p j,i (x) -p j,i (y) = p i,j (y) -p i,j (x), we obtainE {i,j} (X 1/2 i -Y 1/2 i ) 2 = p i,j (ρ) (x i -y i ) + η p j,i (x) -p j,i (y) 2 + (1 -p i,j (ρ)) (x i -y i ) -η p i,j (x) -p i,j (y) 2 = (x i -y i ) -η p i,j (x) -p i,j (y) 2 = (x i -y i ) 2 + η 2 p i,j (x) -p i,j (y) 2 -2η(x i -y i ) p i,j (x) -p i,j (y) .Switching the roles of i and j and using the fact that p i,j = 1 -p j,i again, we obtainEQUATION.For all other k-i.e., for k / ∈ {i, j}-we have X1/2 k = x k and Y 1/2 k = y k . Hence, E {i,j} ∥X 1/2 -Y 1/2 ∥ 2 2 -∥x -y∥ 2 2 ≤ 2η 2 p i,j (x) -p i,j (y) 2 -2η (x i -x j ) -(y i -y j ) p i,j (x) -p i,j (y) ≤ -η (x i -x j ) -(y i -y j ) σ(x i -x j ) -σ(y i -y j ) ,with the final inequality using the fact that σ is 1-Lipschitz and η < 1 2 . We now bound the difference in probabilities. For x, ȳ ∈ R with x ≥ ȳ, we have|σ(x) -σ(ȳ)| ≥ min z∈[ȳ,x] |σ ′ (z)||x -ȳ| ≥ 1 4 e -max{|x|,|ȳ|} |x -ȳ|. Combining the previous results, E {i,j} ∥X 1/2 -Y 1/2 ∥ 2 2 -∥x -y∥ 2 2 ≤ -1 4 ηe -max{|xi-xj |,|yi-yj |} |(x i -x j ) -(y i -y j )| 2 ≤ -1 4 ηe -2M |(x i -x j ) -(y i -y j )| 2 = -1 4 ηe -2M |(x i -y i ) -(x j -y j )| 2, using the fact that ∥x∥ ∞ , ∥y∥ ∞ ≤ M . Summing over (i, j), weighted by q i,j , givesE ∥X 1/2 -Y 1/2 ∥ 2 2 -∥x -y∥ 2 2 = i,j∈[n]:i<j q {i,j} E {i,j} ∥X 1/2 -Y 1/2 ∥ 2 2 -∥x -y∥ 2 2 ≤ -1 4 ηe -2M i,j∈[n]:i<j q i,j |(x i -y i ) -(x j -y j )| 2. Now, applying the Dirichlet characterisation of the spectral gap (Proposition B.1) with z := x -y,E ∥X 1/2 -Y 1/2 ∥ 2 2 -∥x -y∥ 2 2 ≤ -1 4 ηe -2M λ q ∥x -y∥ 2 2 ; note that k x k = 0 = k y k , so k z k = 0. Jensen's inequality then gives E ∥X 1/2 -Y 1/2 ∥ 2 ≤ E ∥X 1/2 -Y 1/2 ∥ 2 2 1/2 ≤ (1 -1 4 ηe -2M λ q ) 1/2 ∥x -y∥ 2 ≤ (1 -1 8 ηe -2M λ q )∥x -y∥ 2 . Hence, recalling that ∥X 1 -Y 1 ∥ 2 ≤ ∥X 1/2 -Y 1/2 ∥ 2 ,κ x,y ≥ 1 8 ηe -2M λ q , and so κ = inf x,y∈Ω κ x,y ≥ 1 8 ηe -2M λ q .Our goal is to establish concentration of time-averaged statistics of the Elo process. General results of this form as known as "Chernoff-type bounds for Markov chains". There is a great deal of literature on such concentration bounds. The version we state here is most-closely related to Theorem 3.4 and Proposition 3.4 in [35] ; see also Theorem 3 in [15] , particularly. Definition D.5 (Mixing Time). Let µ and π be measures on a state space Ω. Then, the total-variation (TV) distance between µ and π is defined to be ∥µ -π∥ TV := sup A |µ(A) -π(A)|, where the supremum is over measurable subsets of Ω. Let X = (X t ) t≥0 be a Markov chain on Ω, and let π denote its equilibrium distribution. The (precision-ε) mixing time ist mix (ε) := inf{t ≥ 0 | max x∈Ω ∥ P x [X t ∈ •] -π∥ TV ≤ ε}.By convention, we abbreviate t mix := t mix ( 1 4 ). Theorem D.6 (Concentration). Let X = (X t ) t≥0 be a uniformly ergodic, irreducible Markov chain on a state space Ω, started from its equilibrium distribution π. Let t mix denote its 1 4 -mixing time. 2 dπ denote the mean and variance, respectively, of f under π. Let ζ > 0 and t ≥ 0 be an integer. Then,Let f : Ω → R be a bounded function: ∥f ∥ ∞ < ∞. Let π(f ) := E π [f ] = Ω f dπ and σ 2 f := Var π [f ] = Ω (f -π(f ))P π 1 t t-1 s=0 f (X s ) -π(f ) ≥ ζ ≤ 2 exp - ζ 2 t/t mix 16(1 + 2t mix /t)σ 2 f + 80ζ∥f ∥ ∞ /t . In particular, if t ≥ max{32t mix , 40ζσ 2 f ∥f ∥ ∞ }, then P π 1 t t-1 s=0 f (X s ) -π(f ) ≥ ζ ≤ 2 exp -1 20 σ -2 f • ζ 2 t/t mix . Remark D.7 (Connection to Curvature).The following description applies to finite state spaces Ω; 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 t rel = 1/λ in the reversible case: λ ≥ κ, and hence t rel = 1/λ ≤ κ -1 . However, it also upper-bounds the mixing time without requiring reversibility, with an additional factor depending on the diameter:t mix (ε) ≤ κ -1 log diam Ω + log(1/ε) ,assuming that d(x, y) ≥ 1{x ̸ = y}. The argument for this is straight-forward: briefly,P[X t ̸ = Y t ] = E[1{X t ̸ = Y t }] ≤ E[d(X t , Y t )] ≤ (1 -κ) t d(X 0 , Y 0 ) ≤ e -κtdiam Ω, then use the standard TV-coupling relation. This can then be plugged into the previous concentration bound, obtaining exponential decay in κt/ 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 set; thus, its TV distance to equilibrium, which is continuously-supported, is 1 (maximal). We circumnavigate this by introducing a noisy version in the proof. This is detailed later. Theorem D.8 (MCMC Convergence of Time Averages). Let f : R n → R be a 1-Lipschitz function and ζ ∈ (0, 1). Let µ f := E π [f ] and σ 2 f := Var π [f ] denote, respectively, its mean and variance under π, the unique invariant distribution of X. For t, T > 0, denote the time average of f in [T,T + t -1] A t,T f := 1 t T +t-1 s=T f (X s ). Suppose that ∥f ∥ ∞ ≤ 1 5 t. Let C 1 , C 2 < ∞.Then, there exists a constant C 0 < ∞, depending only on C 1 , C 2 and f , such that ifmin{λ q , η, 1/t, ζ} ≥ n -C1 and min{t, T } ≥ C 0 t ⋆ where t ⋆ := e 2M η -1 λ -1 q log n, then P 0 [ 1 t T +t-1 s=T f (X s ) -µ f ≥ C 0 ζ] ≤ n -C2 + 2 exp -σ -2 f ζ 2 t/t ⋆ .In particular, under these assumptions, taking ζ ≍ σ f t ⋆ log n/t = e M σ f log n/ ηλ q t,P A t,T f -µ f ≥ C 0 e M σ f √ η log n λ q t ≤ n -C2 .Remark D.9 (Convergence Rate). If X 1 , X 2 , ... were iid, then we would have 1/ √ t decay. Chernoff bounds for reversible Markov chains require t to be replaced by λt, where λ is the spectral gap. The idea is that t rel = 1/λ steps of the Markov chain are required to decorrelate terms when near equilibrium. For non-reversible Markov chains, running for t ⋆ does the job.Connecting this to the curvature κ, roughly, t ⋆ ≲ κ -1 log diam Ω if κ > 0; see Remark D.7. The Elo process is not reversible and we, in essence, bound t ⋆ ≲ κ -1 log n and κ ≍ ηλ q .Remark D.7 connects curvature and the mixing time for finite Markov chains: in essence, curvature allows us to bring two copies exactly together. The Elo process, which lives in the continuum R n , does not have this property. We can get them extremely close, though. So, morally, the bound of κ -1 log diam Ω ≍ λ -1 q log n on 'mixing' suggested by curvature feels correct. We rigorise this idea by adding a small amount of independent noise to the ratings after every step. This noise is then used to couple the two copies once they are extremely close.Outline of Proof of Theorem D.8. The proof has multiple steps, which we outline now.I Approximate the Elo process by a noisy version and control the error. II 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 a burn-in to get the process quantitatively close to equilibrium. V 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 a noisy version. This circumnavigates issues surrounding the discrete support of X t versus the continuous support of its equilibrium distribution.All the statements consist of generic constants C 0 , C 1 , C 2 < ∞. Rather than carry all these dependencies, we make the specific (arbitrary) choice C 1 := 5 and exhibit a C 2 for which this works. The results can easily be extended to the general set-up, albeit with more notation. With this in mind, let δ := n -24 .Step I: Noisy Version & Error. We consider the following noisy version U of the Elo process X.1. Suppose U 0 = u 0 . Draw u 1/3 according to an uncapped Elo step-i.e., as if M = ∞started from u 0 . Suppose Players i and j were chosen-i.e., {k ∈[n] | u 1/3 k ̸ = u 0 k } = {i, j}. 2. Draw ũi , ũj ∼ iid Unif([- √ δ, + √ δ]) independently of all else and set ũk := 0 for k / ∈ {i, j}. Set u 2/3 := u 1/3 + ũ.3. Define U 1 := u 1 by orthogonally projecting u 2/3 to [-M, M ] n preserving the sum.Note that this does not preserve the zero-sum property, as ũi ̸ = ũj . We see later, though, that it is important-crucial, even-for these additive noise terms to be taken independently.We must control the error between the noisy and original versions. To do this, we use the trivial 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.Suppose that (X 0 , Y 0 ) = (x, y) and generate (X 1 , Y 1 ) = (x ′ , y ′ ) from a single step of the trivial Elo-update coupling. Suppose that Players i and j play. Let s ∈ {0, 1} be the indicator that Player i beats j-the 'score'. Then,EQUATION) and y ′ i = y i + η s -p i,j (y) . Subtracting the second from the first givesx ′ i -y ′ i = x i -y i -η p i,j (x) -p i,j (y) .Analogously,x ′ j -y ′ j = x i -y j + η p i,j (x) -p i,j (y) . Subtracting these,(x ′ i -y ′ i ) -(x ′ j -y ′ j ) = (x i -y i ) -(x j -y j ) -2η p i,j (x) -p i,j (y) .But, p i,j (z) = σ(z i -z j ) and σ is 1-Lipschitz, sox i -x j ≤ y i -y j if and only if p i,j (x) ≤ p i,j (y)and |p i,j (x) -p i,j (y)| ≤ |(x i -x j ) -(y i -y j )| = |(x i -y i ) -(x j -y j )|; also, η ≤ 1 2 . Hence, |(x ′ i -y ′ i ) -(x ′ j -y ′ j )| ≤ |(x i -y i ) -(x j -y j )| ≤ |x i -y i | + |x j -y j |. Also, trivially, |(x ′ i -y ′ i ) + (x ′ j -y ′ j )| = |(x i -y i ) + (x j -y j )| ≤ |x i -y i | + |x j -y j |, since the Elo update is zero-sum. Combining these bounds, |x ′ i -y ′ i | + |x ′ j -y ′ j | = max |(x ′ i -y ′ i ) -(x ′ j -y ′ j )|, |(x ′ i -y ′ i ) + (x ′ j -y ′ j )| ≤ |x i -y i | + |x j -y j |.In other words, an Elo update does not increase the ℓ 1 distance between the two sets of ratings:∥x ′ -y ′ ∥ 1 ≤ ∥x -y∥ 1 .This actually immediately implies that the Elo process is non-negatively curved in ℓ 1 .A consequences of this is that that error can only arise from the additive-noise step:∥X s -U s ∥ 1 ≤ ∥X s-1/2 -U s-1/2 ∥ 1 ≤ ∥X s-1 -U s-1 ∥ 1 + √ δ ≤ . . . ≤ s √ δ.Step I:1 t t-1 s=0 ∥X s -U s ∥ 1 ≤ 1 2 t √ δ ≤ n -7 deterministically. (I)We can now 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 II: Curvature. We use the same coupling as before and the same noise in each process.(i) Suppose that (U 0 , V 0 ) = (u 0 , v 0 ). Draw (u 1/3 , v 1/3 ) according to a single step of the trivial Elo coupling started from (u 0 , v 0 ). Suppose that Players i and j were chosen.(ii) Draw a single noise vector n-i.e., ũi , ũj ∼ iid Unif([-√ δ, + √ δ]) and ũk := 0 for k / ∈ {i, j}. Set u 2/3 := u 1/3 + ũ and v 2/3 := v 1/3 + ũ.(iii) Define U 1 := u 1 and V 1 := v 1 by projecting to [-M, M ] n preserving the respective sums.We have already shown that the trivial Elo coupling contracts. The added noise does not hurt:∥u 1 -v 1 ∥ 2 ≤ ∥u 2/3 -v 2/3 ∥ 2 ≤ ∥u 1/3 -v 1/3 ∥ 2 .Hence, the two-stage coupling contracts at least as well as the original, completingStep II:E[∥U 1 -V 1 ∥ 2 ] ≤ E[∥U 1/3 -V 1/3 ∥ 2 ] ≤ (1 -κ)∥U 0 -V 0 ∥ 2 . (II)The reason for adding the noise is to be able to couple two systems U and V , and hence bound the mixing time. We can then apply the general concentration result of Theorem D.6.Step III: Mixing Time. Suppose that (U 0 , V 0 ) = (u 0 , v 0 ) with ∥u 0 -v 0 ∥ ∞ ≤ δ. From this point, we proceed via a slightly different coupling, replacing (i, ii, iii) with (i ′ , ii ′ , iii ′ ), defined below.(i ′ ) Suppose that (U 0 , V 0 ) = (u 0 , v 0 ). Draw (u 1/3 , v 1/3 ) according to a single step of the trivial Elo coupling started from (u 0 , v 0 ) without capping. Suppose that Players i and j were chosen.(ii ′ ) Draw ũk ∼ Unif([- √ δ, + √ δ)) and set ṽk := ũk +(u1/3 k -v 1/3 k ) ∈ [- √ δ, + √ δ] mod 2 √ δ independently for k ∈ {i, j}. (Here, "mod 2 √δ" means "adjusting by additive multiples of 2 √ δ as necessary so that ṽk ∈ [-√ δ, + √ δ)".) Set ũk , ṽk := 0 for k / ∈ {i, j}. Set u 2/3 := u 1/3 + ũ and v 2/3 := v 1/3 + ṽ.(iii ′ ) Set U 1 := u 1 := Π M (u 2/3 ) and V 1 := v 1 := Π M (v 2/3).If ∥u 0 -v 0 ∥ ∞ ≤ δ and Players i and j play, leading to (u 1/3 , v 1/3 ) under the Elo coupling, thenmax{|u 1/3 i -v 1/3 i |, |u 1/3 j -v 1/3j |} ≤ 3δ, regardless of which player won. Hence, in the notation of the coupling,u 2/3 k ≡ u 1/3 k + ũk = v 1/3 k + ṽk ≡ v 2/3 k for both k ∈ {i, j} if ũi , ũj ∈ [- √ δ +3δ, + √ δ -3δ].Say that a step is successful if this holds and fails otherwise. The probability of failure is at most 6 √ δ. If it succeeds, then Players i and j are coupled and the bound of δ on the ℓ ∞ norm is preserved.We now iterate. Suppose that ∥U 0 -V 0 ∥ ∞ ≤ δ. and Players i t and j t are chosen in step t. Letτ c := inf t ≥ 0 ∪ s≤t {i t , j t } = [n]be the first time that all players have been chosen. If all the first τ c steps are successful, then all players' ratings are coupled. Call this event C; then,P[C | τ c ≤ t] ≥ 1 -6 √ δt.It remains to analyse two times:• the 'burn-in' time τ b to get to ℓ ∞ norm at most δ, using coupling (i, ii, iii); • the remaining 'coupling time' τ c started after the burn in, using coupling (i ′ , ii ′ , iii ′ ).The first is easy to handle using curvature:E[∥U t -V t ∥ ∞ ] ≤ E[∥U t -V t ∥ 2 ] ≤ e -κt ∥U 0 -V 0 ∥ 2 ≤ e -κt • 2M n. Thus, P[τ b > t] ≤ P[∥U t -V t ∥ ∞ > δ] ≤ E[∥U t -V t ∥ ∞ ]/δ ≤ δ if t ≥ t δ := κ -1 log(2M n/δ 2 ).The second is equally easy. Start with (U 0 , V 0 ) such that |U 0 i -V 0 i | ≥ 1 for all i. Now, if ∥U t -V t ∥ ∞ ≤ δ < 1, then all players must have been chosen. Hence,P[τ c > t | C] ≤ P[∥U t -V t ∥ ∞ > δ] ≤ δ if t ≥ t δ = κ -1 log(2M n/δ 2 ).Let τ := inf{t ≥ 0 | U t = V t } denote the coalesce time. Putting the above parts together,P[τ > 2t δ ] ≤ P[τ b > t δ ] + P[τ c > t δ ] + P[C c | τ c ≤ t δ ] ≤ 2δ + 6 √ δt δ .We have κ -1 = 8e 2M η -1 λ -1 q ≤ n 11 . So, recalling that δ = n -24 , we have6 √ δt δ ≤ 6n -12 • n 11 • 72 log n = 432n -1 log n ≪ 1.Hence, 2δ + 6√ δt δ ≤ 1 4 . Also, δ = n -24 and M ≤ 1 2 n, so t δ = κ -1 log(2M n/δ 2 ) ≤ 8e 2M η -1 λ -1 q • 50 log n = 400e 2M η -1 λ -1 q log n = 400t ⋆ . This completes Step III: t ⋆ ( 1 4 ) ≤ t ⋆ (2δ + 6 √ δt δ ) ≤ 2t δ ≤ 800t ⋆ = 800e 2M η -1 λ -1 q log n. (III)The general concentration result of Theorem D.6 applies only for a 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.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 1 -κ by (II),T +t-1 s=T E[∥U s -V s ∥ 1 ] ≤ T +t-1 s=T E[∥U s -V s ∥ 2 ] ≤ s≥T e -κs • 2M n ≤ 4M nκ -1 e -κT ≤ δ 1/3 = n -8 if T ≥ T δ := κ -1 log(2M nκ -1 /δ 1/3 ).Analogously to the previous step, this time using also κ -1 ≤ n 5 , we haveT δ = κ -1 log(2M nκ -1 /δ) ≤ 8e 2M η -1 λ -1 q • 31 log n ≤ 250e 2M η -1 λ -1 q log n = 250t ⋆ .Also, t ≥ κ -1 ≥ n. We can then deduce the estimate desired for Step IV:E 1 t T +t-1 s=T ∥U s -V s ∥ 1 ≤ δ 1/3 /t ≤ n -9 if T ≥ 250t ⋆ . (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 of large numbers,|π(f ) -π(f )| = lim k→∞ 1 k L+k-1 ℓ=L (f (Y ℓ ) -f (V ℓ ))almost surely for all L ∈ N.In the curvature proof, we showed a ℓ 2 2 -contraction of 1 -2κ for the Elo process; see Proposition D.4. Adding the noise can increase the ℓ 2 distance squared by at most 10M √ δ. Hence,d ℓ := E[∥Y ℓ -V ℓ ∥ 2 2 ] satisfies d ℓ ≤ (1 -2κ)d ℓ-1 + 10M √ δ.Iterating this,d ℓ ≤ • • • ≤ 2M n(1 -2κ) ℓ + 5M √ δκ -1 ≤ 6M √ δκ -1 if ℓ ≥ L,for some sufficiently large L. By Cauchy-Schwarz,E[∥Y ℓ -V ℓ ∥ 2 ] ≤ √ d ℓ .Hence,E 1 k L+k-1 ℓ=L ∥Y ℓ -V ℓ ∥ 2 ≤ 1 k L+k-1 ℓ=L d ℓ ≤ 3δ 1/4 (M/κ) 1/2 .Plugging this in above, for a 1-Lipschitz function f , using∥ • ∥ 1 ≤ √ n∥ • ∥ 2 , we obtain |π(f ) -π(f )| ≤ δ 1/4 (10M n/κ) 1/2 .Finally, we observe that 10M n/κ ≤ n 7 , completing Step V:|π(f ) -π(f )| ≤ n 7/2 δ 1/4 = n -5/2 . (V)We bring the previous give steps together to 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 an arbitrary initial condition;• U is the noisy Elo process, started from the same state as X-i.e., U 0 = X 0 ; • V is the noisy Elo process, started from equilibrium π.Recall that ∥f ∥ Lip ≤ 1. This with the triangle inequality allows us to control the steps individually:1 t T +t-1 s=T f (X s ) -π(f ) ≤ 1 t T +t-1 s=T ∥X s -U s ∥ 1 Step I + 1 t T +t-1 s=T ∥U s -V s ∥ 1 Step IV + 1 t T +t-1 s=T f (V s ) -π(f ) Step III + π(f ) -π(f ) Step VThe first term is at most 1 2 t √ δ ≤ n -7 deterministically by Step I and the last is at most n 7/2 δ 1/4 = n -5/2 by Step V. The second term is at most δ 1/3 /n = n -9 in expectation by Step IV, which we plug into Markov's inequality. We assume that ζ ≥ n -2 , so that each of the first two terms is smaller than ζ, and n -5 /ζ ≤ n -3 . The remaining term is controlled via the general concentration result of Theorem D.6, using the bound t ⋆ ( 1 4 ) ≤ 800t ⋆ = 800e 2M η -1 λ -1 q log n from Step III. Hence,P 1 t T +t-1 s=T f (X s ) -π(f ) > 9ζ ≤ P 1 t T +t-1 s=T U s -1 t T +t-1 s=T V s 1 > ζ + P 1 t T +t-1 s=T f (V s ) -π(f ) > 5ζ ≤ n -6 + 2 exp -σ -2 f ζ 2 t/t ⋆ . We can apply Theorem D.6 if t ≥ 25600t ⋆ = 32 • 800t ⋆ due to Step III and Step IV if T ≥ 250t ⋆ .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 We start by recalling Theorem 2.5 for the reader's convenience, numbered here as Theorem D.10. Theorem D.10 (MCMC Estimator of Time-Averaged Ratings; Theorem 2.5). Denote the timeaveraged ratingζ := 2σ f t ⋆ log n/t = 2e M log n/ ηλ q t.A t,T k := 1 t T +t-1 s=T X s k for k ∈ [n] and t, T > 0. Let C 1 , C 2 < ∞.Then, there exists a constant C 0 < ∞, depending only on C 1 and C 2 , such that if min{λ q , η, 1/t} ≥ n -C1 and min{t, T } ≥ C 0 t ⋆ where t ⋆ := e 2M η -1 λ -1 q log n, thenP 1 n ∥A t,T -ρ∥ 2 2 ≤ C 0 e 4M λ q n η + (log n) 2 λ q t ≥ 1 -n -C2 .The same result holds for 1 n ∥A t,T -ρ∥ 1 , the average distance in the ℓ 1 (rather than ℓ 2 ) sense.Proof of Theorem 2.5/D.10. The two terms inside the probability come from the MCMC-convergence error and the equilibrium-distribution bias. We use the abbreviationsA t k := 1 t T +t-1 s=T X s k , β k := |π(Π k ) -ρ k | and σ 2 k := σ 2 Π k = Var π [Π k ],where Π k : R n → R is the k-th projector. We separate the MCMC and bias parts:∥A t -ρ∥ 2 2 ≤ 2∥A t -π(Π)∥ 2 2 + 2∥π(Π) -ρ∥ 2 2 .For the bias part, we simply note for now that∥π(Π) -ρ∥ 2 2 = k |π(Π k ) -ρ k | 2 = k β 2 k =: n β2 .We now turn to the MCMC time-averages. Applying Theorem D.8 with f := Π k ,P A t,T k -π(Π k ) ≥ C 0 e M σ k log n/ ηλ q t ≤ n -C2, under the assumptions of that theorem. We perform a union bound over the n players:P 1 n ∥A t,T -π(Π)∥ 2 2 ≥ C 0 e 2M σ2 (log n) 2 /(ηλ q t) ≤ n -C2+1 where σ2 := 1 n k∈[n] σ 2 k .These bias and (average) variance terms are exactly what we handled in Theorem 2.7:β2 ≤ 4e 4M η/(λ q n) and σ2 ≤ 4e 2M η/(λ q n).The first part of Theorem 2.5 now follows from plugging these in above and some small manipulations.To obtain the 1/(λ q t) decay, we just need to check that t ≫ t ⋆ :t ⋆ t = e 2M λ -1 q log n ηt ≍ e 2M λ -1 q log n λ -1 q (log n) 2 = e 2M log n ≪ 1.Our previous bounds on the bias and the variance included the spectral gap λ q obtained from sequential analysis-namely, we used e q e = 1. These expressions change in the parallel set-up. This has a 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 ratingA t,T k := 1 t T +t-1 s=T X s k for k ∈ [n] and t, T > 0,where X s is the state after s ≥ 0 Elo rounds. Then, under the conditions of Theorem 2.5,P 1 n ∥A t,T -ρ∥ 2 2 ≤ Ce 4M λ q n/N η + (log n) 2 λ q t = 1 -o(1),where N := e∈E q e is the mean size of the matching; to emphasise, here, t and T count rounds.Moreover, there exists a distribution q = (q S ) S∈M over matchings whose induced distribution q = (q e ) e∈E over pairs satisfies λ q ≥ 1 3 λ ⋆ disc . In particular,∥A t,T -ρ∥ ⋆ ≲ e 2M log n λ ⋆ disc n/N 1 λ ⋆ disc t whp if η ≍ (log n) 2 λ ⋆ disc t .We separate the proof of Theorem E.1 into two parts: the convergence and the existence of a parallelisable q with λ q ≥ 1 3 λ ⋆ disc . The "in particular" part follows exactly as for Theorem 2.5.Proof of Theorem E.1: Convergence. Write β2 := 1 n ∥π(Π) -ρ∥ 2 2 and σ2 := 1 n k Var π [Π k ] for the average ℓ 2 -bias and variance of 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 e q e = 1 when averaging 2η 2 over {i, j}. Letting N := e q e = E S∼q [|S|] denote the expected size of the random matching q corresponding to q, the same analysis givesE x ∥X 1/2 -ρ∥ 2 2 ≤ ∥x -ρ∥ 2 2 + 2N η 2 -1 2 e -4M η i,j q {i,j} |(x i -ρ i ) -(x j -ρ j )| 2 .Inspecting the analysis of the variance to see where e q e = 1 is used, we getk Var[X 1/2 k ] ≤ k Var[X 0 k ] + 3 2 N η 2 -1 2 e -2M ηλ q k Var[X 0 k ].The proofs then proceed as before to give the bounds β2 ≤ 4e 4M ηN/(λ q n) and σ2 ≤ 3e 2M ηN/(λ q n).The argument for the deduction of Theorem 2.5 givesP 1 n ∥A t,T -ρ∥ 2 2 ≤ C 0 ( β2 + σ2 /(ηλ q t ) ≥ 1 -n -C2; now, (t, T ) in A t,T correspond to the number of rounds and q may have e q e > 1-and, so, λ q may be larger than 1/n, but not than N/n. Plugging in the new bounds for β and σ,P 1 n ∥A t,T -ρ∥ 2 2 ≤ C 0 e 4M λ q n/N η + (log n) 2 λ q t ≥ 1 -n -C2 .Proof of Theorem E.1: λ q ≳ λ ⋆ disc . Let q be an optimiser of λ ⋆ disc : λ q = λ ⋆ disc . It can be formulated as a semidefinite program [10] , so its solution can be approximated arbitrarily well in polynomial time.Extending q from E to [n] 2 by q i,j := q {i,j} 1{{i, j} ∈ E} defines a symmetric and substochatic matrix with the same Dirichlet form. Adjusting the diagonal has no effect on the Dirichlet form, so we may assume that it is, in fact, stochastic: its row sums are all exactly 1. The spectral gp of this q is still λ q , by the Dirichlet characterisation (Proposition B.1).The Birkhoff-von Neumann theorem allows the decomposition of any n × n doubly stochastic matrix into a convex combination of (at most) n 2 permutation matrices in polynomial time:q = n 2 ℓ=1 α ℓ P σ ℓ where α ∈ [0, 1] n 2with ℓ α ℓ = 1 and P σ is the permutation matrix for σ ∈ Symm(n):(P σ ) i,j = 1{j = σ(i)} for all i, j ∈ [n].This can be chosen so that each permutation matrix has non-zero entries only over graph edges.Given a permutation σ i , we decompose it into disjoint cycles. These cycles actually correspond to cycles in the graph; we can discard cycles with only one element. Let v 1 , v 2 , ..., v k 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 {v i , v i+1 } with odd i ∈ {1, ..., k -1};• one containing all the edges in the cycle of type {v i , v i+1 } with even i ∈ {1, ..., k -1};• one matching containing the single edge {v k , v 1 }. This decomposition gives rise to a procedure to sample matchings in the graph.1. Sample a permutation Σ according to the convex combination: P[Σ = σ ℓ ] = α ℓ 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 a matching. Moreover, the probability that a given edge {i, , j} ∈ E belongs to the sampled matching is precisely 1 3 q i,j = 1 3 q {i,j} . Hence, we have constructed a matching with associated spectral gap at least 1 3 λ q . But, by assumption, λ q = λ ⋆ disc , completing the proof.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 crossreferenced. • All assumptions should be clearly stated or referenced in 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 to provide a 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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	The definition of new variables is extensive but less detailed explanation, making this paper is challenging to understand. 
2.	The 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.
3.	Does 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. 
4.	What’s the technique novelty of this paper? The form of the convergence rate result is very similar to those of previous works. 
5.	If 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.
questions: questions: 1.	In definition 2.3, what the dij and deltaij means? There seem lack some detailed explanation of these symbols’ physical meaning. 
2.	What the symbol in the “equation” in line 110 mean? This symbol appears frequently in whole paper, but less explanation.
limitations: limitations: Please refer to weaknesses
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Due to lack of expertise of the reviewer for this author, this is left blank
limitations: limitations: Yes
paper_summary: paper_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). 

The authors further investigates the problem of finding efficient matching graphs (tournament design) to accelerate the convergence of the elo process. 

Although 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).
strength_weakness: strength_weakness: ### (minor) Reordering a few results?

I believe that slightly reordering results in section 2.1 would help to streamline the paper.
For 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.

It 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.
Although they are interesting on their own, it may be worth putting them in a dedicated subsection.

### (minor) Typography

The paper does not exploit the large text width of NeurIPS' template.
For instance:
- at lines 597 and 599, the $\le$ and $=$ are missaligned
- 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).
questions: questions: ### General questions 

- Analysis this Elo system seems so natural to do with a SGD approach. Is there any in the literature?

- 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?

- 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. 

### Miscellaneous

-  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 
$$
||\hat{\mu}_n - \mu || \rightarrow 0
$$ almost surely, where the norm is the total variation distance.

- You use the terminology "negatively curved" for "contraction" and "non-positively curve" for "non-expansive". Is there a reason for this?
limitations: 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$). 


### Miscellaneous
- 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not see any particular weakness to the present manuscript.
questions: questions: Here are some specific remarks and suggestions: 

p.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)$

p.3 l.3 "$\pi$ the equilibrium distribution": I suggest adding a reference where existence and uniqueness of the invariant distribution is proved

p.3 l.100 the notation is $\succeq$ is not defined. It does not seem to be used elsewhere in the paper.

p.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?

p.4 l.146 "Since $n / \lambda_q \geq 1$": I think the authors mean $\lambda_q \leq 4/n$

p.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.

p.5 in l.200 and l.202 what is the $\Delta$ sign at the end of the equations?

p.5 l.242 the notation $\tilde{O}$ is not defined

p.15 Prop. B.1 I think there is a missing $1/2$ factor in the Dirichlet characterization of $\lambda_q$.

p.15 l.541 "Eloupdate" should be "Elo update"

p.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

p.16 Appendix C: the notation $X^{1/2}$ is not introduced

p.17 l.589 "We now turn to the bias" should be "We now turn to the variance"

p.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

p.18 l.607: "$z:=x^{0} - \mathbb{E} [X^0]$ should be $z := X^{0} - \mathbb{E} [X^0]$

p.18 l.611-612 " the maximal variance of such a random variable is $q_k /2$: there should be an additional factor $\eta^2$

p.19 l.617 the step-size $\eta$ is missing in this equation

p.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

p.21 in the equation after l.679 what is $\pi_{i,j}$? 

p.21 l.683 $\bar{z} \in [\bar{y},\bar{x}]$ should be an index of the minimum

p21 in the second equation after l.685 I think the notation $E_{\ast}$ is not defined

p.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".

p.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.

p.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

p.22 l.717 use only one notation among $\mu_f$ or $\pi(f)$ for the expectation.

p.23 l.738 again the mysterious $\Delta$ sign

p.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}$?

p.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.

p.26 in l.821 there is a missing expectation

p.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

p.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.

p.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$.

p.27 l.844 $\sum_{k} | A^{t,T}_{k} - \rho_j |_1$: write this either as a sum or as an $\ell^1$ norm

p.27 Proof of Theroem 2.5 why introduce the new notation $\Pi_k$?

p.29 l.895 "the single edge $\{ c_k, c_1 \}$": I guess this is in fact $\{ v_k, v_1 \}$

p.29 l.898: I am not sure to understand how the cycles are sampled: is it each with probability $1/3$?
limitations: limitations: The paper addresses the limitations of the results which are ground for future work.

Comments: title: Reply to rebutal
comment: Thanks for your response. We think there is a slight misunderstanding: the primary purpose of Elo is to provide a **live** ranking of players in a sport. Fans and pundits, even players, want this, so they can see how their current performance stacks up against others, and can be used to estimate the chances of future matches. The ratings are updated after a match in a simple, intuitive way. It's used in a variety of sports for exactly this purpose.

An offline system is not suited for this: if you recompute the MLE every time a game is played, the changes in the ranking are opaque and not easily understandable. Moreover, if player A plays against B, only the Elo ratings of A and B are affected, while recomputing the MLE will likely result in all players having a different rating.

An "active" system, where you have the flexibility to decide who plays who in the next match, is also not well suited in many scenarios (such as in sports analytics) since you often cannot choose who will play next, but at most you can only decide a schedule before you begin observing outcomes of the matches.

In any case, what our work shows is that actually Elo still performs very competitively with state-of-the-art offline algorithms, even though it's online and not "active".
Thank you for your explanation! I understand the difference between your work and [1]. However, I am curious about the rationality of the Elo rating system, which is designed to estimate players' skills and dynamically select matches based on Elo scores, in a fixed schedule setting. Using "a fixed schedule decided before any game has been played" seems akin to tournament designs like round-robin or elimination. Under such fixed tournament schedules, the Elo rating system appears unsuitable because the player matching function is not utilized, and other offline methods, such as MLE and directly computing winning rate, could provide more accurate estimations.
Thanks to the reviewer for bringing up reference [1]. 

We will discuss it in a bit more details in the revised version of our paper, but we wanted to briefly mention that their setup is quite different than our traditional online Elo scenario, and it is rather more similar to active ranking: instead of observing players play against one another according to a fixed schedule decided before any game has been played, in [1] they actively choose the next pair of players to match up based on the outcome of previous matches.
Thanks for your response
Thank you for your detailed responses. This paper focuses on online Elo ratings, whereas previous works have concentrated on offline settings. This problem setting is interesting to me and addresses most of my concerns. Thus, I will maintain my positive score. Additionally, Reference [1], which also analyzes online Elo ratings, may be worth discussing.

[1] Yan, Xue, et al. "Learning to identify top elo ratings: A dueling bandits approach." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 8. 2022.
Thank you. 
You have addressed most of my concerns (including question 2).

For the miscellaneous question 1, I was mistaking convergence in distribution for convergence in TV. For my failed counter-example you can simply set $A_n := \mathbb{R} \setminus \mathrm{supp}(\mu_n)$ and you get $\mu(A_n) = 1 \ne 0 = \mu_n(A_n)$.
I thank the authors for their response and hope my feedback has been helpful. 

Regarding the "convergence theorem on Hilbert spaces", I actually meant projection, not convergence, and it seems indeed that many textbooks never mention the contraction property of the orthogonal projection, so a reference is not easy to find. Overall this was a very minor point.