March 06, 2026
We consider a general round-robin tournament model with equally strong players, where \(X_{ij}\) denotes the score of player \(i\) against player \(j\). We assume that \(X_{ij}\) takes values in a countable subset of \([0,1]\) and satisfies \(X_{ij}+X_{ji}=1\). We prove that if \(k(n)\to\infty\) as \(n\to\infty\) and \(\frac{k(n)^2\log\!\bigl(n/k(n)\bigr)}{\sqrt n}\to 0,\) then, with probability tending to one, the largest \(k(n)\) scores are all distinct. In particular, this holds whenever \(k(n)=o\!\Bigl(\bigl(n/\log n\bigr)^{1/4}\Bigr).\) By symmetry, the same conclusion also holds for the lowest \(k(n)\) scores. The obtained scale coincides with the one arising in classical problems on distinct extreme degrees in Erdős–Rényi random graphs, despite the fundamentally different dependence structure. This suggests that distinctness of extreme values may persist under broad classes of models exhibiting weak dependence.
0
0
Title
Cramér transform; complete graph; concentration function; large deviations; negative dependence; order statistics.
In a round-robin tournament, each of \(n\) players competes against each of the other \(n-1\) players. When player \(i\) plays against player \(j\), player \(i\)’s reward is a random variable \(X_{ij}\). Let \[\label{eq:not} s_i(n)=\sum_{j=1,\, j\neq i}^{n} X_{ij}\tag{1}\] denote the score of player \(i\), \(1\le i\le n\), after playing against all other \(n-1\) players. We assume that the \({n \choose 2}\) pairs \(\left(X_{ij},X_{ji}\right)\), \(1\le i<j\le n\), corresponding to different matches are independent. We refer to \(\bigl(s_1(n),s_2(n),\ldots,s_n(n)\bigr)\) as the score sequence of the tournament.
Model \(M_{[0,\,1]}\): Let \(D \subset [0, 1]\) be a countable set of all possible values of \(X_{ij}\). Each value in \(D\) occurs with positive probability. For \(i\neq j\), \(X_{ij}+X_{ji}=1\), \(X_{ij}, X_{ji} \in D\). This together with the assumption that all players are equally strong (i.e., \(X_{ij}\) are identically distributed), implies \[\label{eq:symD} 0<\mathbb{P}\left(X_{ij}=a\right)=\mathbb{P}\left(X_{ij}=1-a\right)\,\,\,\, \text{for any}\,\,\,\, a\in D.\tag{2}\] We assume that \(|D|>1\) and that all pairs \(\left(X_{ij},X_{ji}\right)\), \(1\le i<j\le n\), are independent.
The classical round-robin tournament corresponds to \(D=\{0,1\},\) which we denote by Model \(M_1\), the classical chess model corresponds to \(D=\left\{0,\frac{1}{2},1\right\}\) (Model \(M_2\)). More generally, we consider the finite grid model \(M_k=\left\{0, \frac{1}{k}, \frac{2}{k},\ldots, \frac{k}{k}\right\}\). As another example, one may think of the game of Go, where k can represent the squared board size plus one, allowing also for score zero.
The problem of measuring players’ strengths in chess tournaments via paired comparisons has a long history, beginning with [1]. In [2], a model for winning probabilities was proposed, and maximum likelihood estimators were derived and applied to the analysis of a chess tournament. The combinatorial investigation of Models \(M_1\) and \(M_2\) was initiated in [3], [4] and continues to this day; see, for example, [5], [6], B2026?. An introduction to the combinatorial and probabilistic aspects of tournaments, along with extensive references to earlier works, is provided in the classical monograph [7]; see also the corrected 2013 version available via Project Gutenberg.
Round-robin tournaments provide a natural probabilistic framework for paired-comparison models and related statistical inference, beginning with the works of [2], [8], broadly discussed in the monograph [9], and continuing to attract considerable attention to this day; see, for example, [10], [11]. The asymptotic distribution of extreme scores in Model \(M_{[0,1]}\) was recently derived in [12], where further connections and an extensive bibliography are provided. A related but different problem was considered recently in [13].
Let \(r_n(M)\) denote the probability that the tournament with \(n\) players has a unique player with maximum score under model \(M\). [14] stated, without proof, that in a classical round-robin tournament (Model \(M_1\)), the probability that there is a unique player with the maximum score tends to \(1\) as \(n\) tends to infinity, i.e., \[\label{eq:C1} {\displaystyle \lim_{n\rightarrow \infty}r_n(M_1)=1.}\tag{3}\] In a survey paper, [15] noted that Epstein’s problem 3 was still unsolved at the time. In a recent publication, [16] proved 3 using a method introduced in [17]. More recently, [18] extended this result to the model \(M_{[0,1]}\).
We denote the vector of ordered scores by \[s_{(1)}(n)\le s_{(2)}(n)\le\cdots\le s_{(n)}(n).\]
Define the event \[\label{eq:U} U_{n,k} = \Bigl\{ \text{the k largest scores } s_{(n-k+1)}(n), s_{(n-k+2)}(n), \ldots, s_{(n)}(n) \text{ are pairwise distinct} \Bigr\}.\tag{4}\]
In this work, we obtain conditions on \(k(n)\) under which \[\lim_{n\to\infty}\mathbb{P}\!\left(U_{n,k(n)}\right)=1.\]
The tournament can be represented by a complete directed graph whose vertices correspond to the players. For each pair of distinct vertices \(i\) and \(j\), the directed edges \((i,j)\) and \((j,i)\) are assigned weights \(X_{ij}\) and \(X_{ji}\) satisfying \(X_{ij}+X_{ji}=1.\) Thus, each match distributes one unit of score between the two players. It is important to note that related questions have also been studied in the theory of random graphs. In the Erdős–Rényi random graph model [19]–[22], there are \(n\) vertices, and each unordered pair of distinct vertices \(i\) and \(j\) is connected by an undirected edge independently with probability \(p\) (which may depend on \(n\)). A related problem concerning the distinctness of extreme vertex degrees was posed in [23] and studied by [24]. An interesting application of the obtained results on the gaps between extreme degrees was found in the construction of a simple algorithm for the graph isomorphism problem [22], [25].
This direction remains an active area of research to this day; see, for example, [26] and [27]. Although the dependence structure in random tournaments is fundamentally different and exhibits negative dependence, the behavior of the extreme scores turns out to be strikingly similar to that in random graphs. Our proof uses different methods and relies on large deviations, concentration inequalities, and the negative dependence structure of tournament scores, in particular negative association. In contrast to the random graph setting, our proof relies crucially on negative association. It remains open whether the obtained scale is tight.
Theorem 1. If \(k(n)\to\infty\) as \(n\to\infty\) and \[\frac{k(n)^2\log\!\bigl(n/k(n)\bigr)}{\sqrt{n}}\to 0,\] then \[\lim_{n\to\infty}\mathbb{P}\bigl(U_{n,k(n)}\bigr)=1.\]
Corollary 1. If \(k(n)=o\!\Big(\big(n/\log n\big)^{1/4}\Big)\), the condition of Theorem 1 holds.
A related property concerning the set of the smallest scores can be obtained due to the symmetry of the outcome distribution assumed in 2 . Recall the definition \(U_{n,k}\) in 4 and define \[\widetilde{U}_{n,k} =\Bigl\{ \text{the k smallest scores } s_{(1)}(n), s_{(2)}(n), \ldots, s_{(k)}(n) \text{ are pairwise distinct} \Bigr\}.\]
Claim 1. For each \(k\in \left\{1, 2, \ldots, n\right\}\), \[\mathbb{P}\big(U_{n,k}\big) = \mathbb{P}\big(\widetilde{U}_{n,k}\big).\]
Proof. (Corollary 1 ) Let \(\widetilde{T}_n\) be the tournament obtained from \(T_n\) by reversing every edge. Then \(\widetilde{T}_n\) has the same distribution as \(T_n\), and its scores satisfy \[\widetilde{s}_i=(n-1)-s_i, \qquad 1\le i\le n.\]
Hence, the event that the top \(k\) scores are pairwise distinct in \(T_n\) coincides with the event that the bottom \(k\) scores are pairwise distinct in \(\widetilde{T}_n\). Since \(\widetilde{T}_n \stackrel{d}{=} T_n\), the conclusion follows. ◻
Proof. (Theorem 1)
To prove the theorem, we require the following notation and three propositions.
From the symmetry \(X_{ij} \stackrel{d}{=} 1-X_{ij}\) it follows that \[\mu=\mathbb{E}(X_{ij})=\frac{1}{2}.\] Since \(X_{ij}\in[0,1]\), we also have \[\sigma=\bigl(\mathrm{Var}(X_{ij})\bigr)^{1/2}\le \frac{1}{2}.\] Furthermore, let \[\begin{align} \label{eq:tn} t_{n, k}=(n-1)\mu+x_{n, k} (n-1)^{1/2}\sigma, \end{align}\tag{5}\] where \(x_{n,k}\) will later be chosen so that the expected number of scores exceeding \(t_{n,k}\) is of order \(k\).
Let \[I_j(t)=\mathbf{1}\{s_j(n)>t\}, \qquad Z_t=\sum_{j=1}^n I_j(t).\]
Define \[W_n(t)=\sum_{1\le v<u\le n}\mathbf{1}\{t<s_u(n)=s_v(n)\}.\]
Proposition 1. Let \(k(n)\to\infty\) with \(k(n)=o(n)\). Then, for any fixed \(\delta\in(0,1)\), one can choose \(x_{n,k}\to\infty\) satisfying \(x_{n,k}=o(n^{1/6})\) and \[\label{eq:Cond} x_{n,k}^2=2\log\!\bigl(n/k(n)\bigr)+O\!\bigl(\log\log(n/k(n))\bigr)\qquad{(1)}\] such that \[n\,\mathbb{P}\!\left(s_1(n)>t_{n,k}\right)\sim (1+\delta)\,k(n).\]
Proof. See appendix 3. ◻
Proposition 2. Suppose that \(k(n)\to\infty\) with \(k(n)=o(n)\) and that \(x_{n,k}\to\infty\) with \(x_{n,k}=o(n^{1/6})\). Assume further that \(k(n)\) and \(x_{n,k}\) satisfy ?? . Then, for \(t_{n, k}\) defined in 5 , \[\lim_{n \to \infty} \mathbb{P}\!\left(Z_{t_{n, k}}<k(n)\right)=0.\]
Proof. See appendix 4. ◻
Proposition 3. Assume Model \(M_{[0,1]}\) with countable support \(D\subset[0,1]\), \(|D|>1\). Let \(k(n)\to\infty\), \(k(n)=o(n)\), and suppose that \(x_{n,k}\to\infty\) with \(x_{n,k}=o(n^{1/6})\) satisfy ?? . Let \(t_{n,k}\) be defined in 5 . Then there exists a constant \(C>0\) such that for all sufficiently large \(n\), \[\mathbb{E}\!\left(W_n(t_{n,k})\right) \le C\,\frac{k(n)^2 \log\!\bigl(n/k(n)\bigr)}{\sqrt n}.\]
Proof. See appendix 5. ◻
Therefore, noting that \(W_n(t_{n,k})\ge \mathbf{1}\{W_n(t_{n,k})\ge 1\}\ge 0\), we obtain from Proposition 3 that if \(k(n)\rightarrow \infty\), as \(n\rightarrow \infty\), so that \(\frac{k(n)^2\bigl(\log(n/k(n))\bigr)}{\sqrt{n}}\rightarrow 0\), then \[\label{eq:pronew} \lim_{n \to \infty} \mathbb{P}\bigl(W_n(t_{n, k}) = 0\bigr) = 1.\tag{6}\]
Define \[\label{eq:int} G=\{Z_{t_{n, k}}\ge k\}\cap\{W_n(t_{n, k})=0\}.\tag{7}\]
Since \(G\subseteq U_{n,k}\), it follows from 7 that \[\label{eq:Ine1} 0\le \mathbb{P}\!\left(U^{C}_{n,k}\right) \le \mathbb{P}\!\left(G^{C}\right) \le \mathbb{P}\!\left(Z_{t_{n, k}}<k\right)+\mathbb{P}\!\left(W_n(t_{n, k})>0\right).\tag{8}\] Combining 8 with Proposition 2 and 6 completes the proof of Theorem 1. ◻
Proof. (Proposition 1) If \(x_{n, k}\rightarrow \infty\), as \(n\rightarrow \infty\), so that \(x_{n, k}=o(n^{1/6})\) and \(X_{ij} \in [0, 1]\), then it follows from [28] that \[\begin{align} \label{eq:LD1} & \mathbb{P}(s_1(n)>t_{n, k})\sim 1-\Phi(x_{n, k}), \end{align}\tag{9}\] where \(\Phi()\) denotes the standard normal distribution function. Also, since \(x_{n, k}\rightarrow \infty\) as \(n\rightarrow \infty\) (see for example, [29]), \[\label{eq:LD2} 1-\Phi(x_{n, k})\sim \frac{1}{x_{n, k}}\varphi(x_{n, k}),\tag{10}\] where \(\varphi()\) is the PDF of a standard normal random variable.
From 9 and 10 , it follows that if \(x_{n, k}\to\infty\) as \(n\to\infty\) and \(x_{n, k}=o(n^{1/6})\), then \[\label{eq:LD3} \mathbb{P}(s_1(n)>t_{n, k})\sim \frac{1}{x_{n, k}}\,\varphi(x_{n, k}).\tag{11}\]
Let \(k=k(n)\) and \(x=x_{n,k}>0\) satisfy \[\label{eq:sat} \frac{n}{\sqrt{2\pi}}\, \frac{1}{x}\,e^{-x^2/2} =(1+\delta)\,k .\tag{12}\] Equivalently, \[e^{-x^2/2} = \frac{(1+\delta)\,k\,x\sqrt{2\pi}}{n}.\] Therefore, \[\frac{x^2}{2} = \log\frac{n}{k} -\log x -\frac{1}{2}\log(2\pi) -\log(1+\delta),\] and hence \[\label{eq:xx} x^2 = 2\log(n/k) +O(\log\log(n/k)).\tag{13}\] Assuming that \(k(n)=o(n)\), it follows from 13 that \(x_{n,k}=o(n^{1/6})\) and appealing to 11 , 12 and 13 we complete the proof of Proposition 1. ◻
Proof. Recall that \(Z_t=\sum_{j=1}^n \mathbf{1}\{s_j(n)>t\},\) that \(t_{n,k}\) is defined in 5 , and that the scores \(s_1(n),\ldots,s_n(n)\) are identically distributed. Suppose that \(k(n)\to\infty\) with \(k(n)=o(n)\) and that \(x_{n,k}\to\infty\) with \(x_{n,k}=o(n^{1/6})\). Assume further that \(k(n)\) and \(x_{n,k}\) satisfy ?? . Then, from Proposition 1, it follows that for any fixed \(\delta\in(0,1)\), \[\label{eq:AZ} \mathbb{E}\!\left(Z_{{t_{n, k}}}\right)=n\mathbb{P}\!\left(s_1(n)>t_{n, k}\right)\sim (1+\delta)\,k(n)\to\infty .\tag{14}\] Let \[\eta=\frac{\delta}{1+\delta}\in(0,1).\] Appealing to 14 , we obtain \[(1-\eta)\mathbb{E}\!\left(Z_{{t_{n, k}}}\right) =\frac{\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)}{1+\delta} \sim k(n),\] and therefore, for all sufficiently large \(n\), \[k(n)\le (1-\eta/2)\mathbb{E}\!\left(Z_{{t_{n, k}}}\right).\] Hence \[\begin{align} \label{eq:inZ} & 0\le \mathbb{P}\!\left(Z_{{t_{n, k}}}<k(n)\right) \le \mathbb{P}\!\left(Z_{{t_{n, k}}}<(1-\eta/2)\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)\right)\\ & = \mathbb{P}\!\left(Z_{{t_{n, k}}}-\mathbb{E}\!\left(Z_{{t_{n, k}}}\right) <-(\eta/2)\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)\right) \nonumber \le \mathbb{P}\!\left(\big|Z_{{t_{n, k}}}-\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)\big| >(\eta/2)\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)\right)\\ \nonumber & \le \frac{Var(Z_{{t_{n, k}}})}{(\eta/2)^2\big(\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)\big)^2} \le \frac{\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)}{(\eta/2)^2\big(\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)\big)^2} = \frac{4}{\eta^2\,\mathbb{E}\!\left(Z_{{t_{n, k}}}\right)}, \end{align}\tag{15}\] where the first inequality follows from adding a nonnegative term, the second from Chebyshev’s inequality, and the third from the facts that \(Var(I_1({t_{n, k}}))\le \mathbb{E}(I_1({t_{n, k}}))\) and \[\operatorname {Cov}(I_1({t_{n, k}}),I_2({t_{n, k}}))\leq 0.\] The covariance bound \(\operatorname{Cov}(I_1(t_{n,k}),I_2(t_{n,k}))\le 0\) holds because the vector \((I_1(t_{n,k}),\ldots,I_n(t_{n,k}))\) is negatively associated as proved in [30]. Combining 14 with 15 under assumptions of the proposition, we obtain \[\lim_{n \to \infty} \mathbb{P}\!\left(Z_{t_{n, k}}<k(n)\right)=0.\] ◻
Proof. Recall that \(W_n(t)=\sum_{1\le v<u\le n}\mathbf{1}\{t<s_u(n)=s_v(n)\}.\) Also, in view of the definition of the scores in 1 , let \(s_u(n-1)\) denote the total score of player \(u\) in the tournament obtained after removing one opponent, that is, after \(n-2\) matches. Assume from now that \(n\ge3\), and let \[A_n=\{x:\;t_{n,k}-1<x\le n-2 \;\text{and x is an attainable value of } s_u(n-1)\}.\]
By the argument used in Proposition 2 of [18], conditioning on the outcome of the match between players \(u\) and \(v\), one obtains \[\label{eq:AM1} \mathbb{E}\!\left(W_n(t_{n,k})\right) \le \frac{n(n-1)}{2}\,\mathbb{P}\!\left(s_v(n-1)>t_{n,k}-1\right)\, \sup_{x\in A_n}\mathbb{P}\!\left(s_1(n-1)=x\right). .\tag{16}\]
It follows from the definition of \(t_{n, k}\) in 5 and the fact that \(\mu=1/2\) that for sufficiently large \(n\) \[\label{eq:L} t_{n, k} - 1 \ge (n-2)\mu + x_{n, k} (n-2)^{1/2}\sigma:=l_{n, k}.\tag{17}\]
Let \(m = n - 2\) and \(S_m = s_1(n-1)\).
For any \(\theta\in\mathbb{R}\), define the tilted random variable \[\label{eq:til} \Pr_{\theta}(S_m=x) =\frac{\mathbb{E}\!\left(e^{\theta S_m}\mathbf{1}_{\{S_m=x\}}\right)}{\mathbb{E}\!\left(e^{\theta S_m}\right)}.\tag{18}\]
By the definition 18 , we have
\[\begin{align} \label{eq:b} & \mathbb{P}(S_m=x)=e^{-\theta x}\,\mathbb{E}\!\left(e^{\theta S_m}\mathbf{1}_{\{S_m=x\}}\right)= e^{-\theta x}\,\mathbb{E}\!\left(e^{\theta S_m}\right)\, \frac{\mathbb{E}\!\left(e^{\theta S_m}\mathbf{1}_{\{S_m=x\}}\right)}{\mathbb{E}\!\left(e^{\theta S_m}\right)}\nonumber\\[4pt] &=e^{-\theta x}\,\mathbb{E}\!\left(e^{\theta S_m}\right)\, \Pr_\theta(S_m=x). \end{align}\tag{19}\]
For \(\theta>0\) and \(x>l_{n,k}\), it follows from 17 and 19 that \[\begin{align} \label{eq:new1} \mathbb{P}(S_m=x) = e^{-\theta x}\,\mathbb{E}\!\left(e^{\theta S_m}\right)\, \Pr_\theta(S_m=x) \le e^{-\theta l_{n, k}}\,\mathbb{E}\!\left(e^{\theta S_m}\right)\Pr_\theta (S_m=x), \end{align}\tag{20}\] where the inequality follows because \(e^{-\theta x}\) is non-increasing in \(x\) for \(\theta>0\) and \(x>l_{n,k}\).
Therefore, for \(\theta>0\), and for sufficiently large \(n\) \[\label{eq:sup} \sup_{x>t_{n, k}-1}\mathbb{P}(S_m=x) \le \sup_{x>l_{n, k}}\mathbb{P}(S_m=x) \le e^{-\theta l_{n, k}}\,\mathbb{E}\!\left(e^{\theta S_m}\right) \sup_{x>l_{n, k}}\Pr_\theta(S_m=x).\tag{21}\]
Assuming ?? and \(k(n)=o(n)\), equation (18) of [18] implies that, under Model \(M_{[0,1]}\), for all sufficiently large \(n\) and \(\theta>0\), \[\begin{align} \label{eq:first} e^{-\theta l_{n, k}} \mathbb{E}\!\left(e^{\theta S_m}\right) \le e^{\Big(-\frac{x_{n, k}^2}{2} + o(1)\Big)}. \end{align}\tag{22}\]
Also using Kolmogorov’s inequality on the rate of decrease of Lévy’s concentration function for the sum of independent discrete random variables obtained by [31] (see also [32], pages 56 and 319), equation (19) of [18] shows that, under Model \(M_{[0,1]}\), \[\begin{align} & \label{eq:second} \sup_{x > l_{n, k}} \Pr_\theta(S_m = x) \le \frac{c}{\sqrt{m}}, \end{align}\tag{23}\] for some constant \(c>0\).
Combining 21 , 22 , and 23 we obtain for sufficiently large \(n\), \[\label{eq:AM2} \sup_{x \in A_n} \mathbb{P}(s_1(n-1) = x)\leq O\left(\frac{1}{n^{1/2}}e^{\Big(-\frac{x_{n, k}^2}{2} + o(1)\Big)}\right).\tag{24}\]
By Proposition 1 applied with \(n\) replaced by \(n-1\), and using ?? , \[\mathbb{P}\!\left(s_v(n-1)>t_{n,k}-1\right) \le C_1 \frac{k(n)\sqrt{\log(n/k(n))}}{n}.\]
Also, 24 and ?? imply \[\sup_{x\in A_n}\mathbb{P}(s_1(n-1)=x) \le C_2 \frac{k(n)\sqrt{\log(n/k(n))}}{n^{3/2}}.\] Substituting these bounds into 16 yields \[\mathbb{E}(W_n(t_{n,k})) \le C\,\frac{k(n)^2\log(n/k(n))}{\sqrt n}.\] ◻
I would like to thank Noga Alon for valuable discussions, John W. Moon and Miklós Simonovits for helpful comments and suggestions. I thank Boris Alemi for carrying out the computations on the department’s high-performance computer. This research was supported in part by BSF grant 2020063.
email: yaakovm@umbc.edu↩︎