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.
Strengths
The results proved are of interest, especially as the existing literature on the subject is scarce and in particular there has not been many works studying the Elo process as a Markov chain. The paper is quite well-written and does a good job at conveying the main ideas of the proof. The mathematical content is serious and I have not detected any major mistake in the proofs.
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$?