For a round-robin tournament, what is the favorite's least favorite size?

Question

Suppose we have a round-robin tournament (i.e., each player plays exactly one game with each other player) with $n$ players, who are all equally skillful except for one player, the favorite, whose probability of winning a game against any other player is some fixed value $p > 1/2$. Assume that all games are independent, and also that no individual game ends in a tie. The winner of the tournament is the player who wins the most games; let us assume that if several players are tied for first place, then one of them is chosen (uniformly) at random to be the winner. Let $\pi(p,n)$ be the probability that the favorite wins the tournament.

Fact. For any fixed $p>1/2$, $\lim_{n\to\infty} \pi(p,n) = 1$.

Sketch of proof: The probability that a given ordinary player scores higher than the favorite goes to zero at a rate that is exponentially fast in $n$ (by, e.g., Hoeffding's inequality), but there are only $n$ competitors, so even a union bound suffices to show that the probability that any player scores higher than the favorite goes to zero exponentially fast.

In light of the above Fact, it may be slightly surprising that for a fixed $p$, especially for $p$ close to $1/2$, the value of $\pi(p,n)$ actually declines for a while (as $n$ increases), and I think it may even wobble around, before eventually climbing to 1.

Intuitively, what's happening for small $n$ is that the increase in the number of competitors is increasing the chances that one of them will do well and upset the favorite, and that this is initially a more important effect than the fact that the increase in the number of games is giving the favorite an opportunity to demonstrate a skill edge.

This has led me to consider the following question.

Let $N(\epsilon)$ denote the value of $n$ that minimizes $\pi(1/2 + \epsilon, n)$. What can be said about $N(\epsilon)$ as $\epsilon\to0$?

Presumably, $\lim_{\epsilon\to0} N(\epsilon) = \infty$, but approximately how fast?

Answer 1

I can show that $N(\epsilon)$ is equal to $\epsilon^{-2}$ up to a log factor on each side.

The strategy I'll use is to give an upper bound for $\pi(1/2+\epsilon,n)$. Optimizing it, we obtain an upper bound for $\pi(1/2+\epsilon,N(\epsilon))$. Then using lower bounds for $\pi(1/2+\epsilon,n)$ we can rule out certain values of $n$ as being $N(\epsilon)$.

For any $m \geq\epsilon n$, we have the upper bound $$ \pi(1/2+\epsilon,n) \leq \frac{(1+2\epsilon)^{n/2+m} (1-2\epsilon)^{n/2-m} }{n} + e^{ - 2 (m-\epsilon n)^2/n}$$

Indeed by Hoeffding's inequality the second term is an upper bound on the probability of getting greater than $m$ wins, so it suffices to prove the first term is an upper bound on the probability of winning the tournament with at most $m$ wins. However, for each possible outcome of the tournament (specifying the winner of every match) involving at most $m$ wins for a certain player, the probability of getting it when that player is the a favorite divided by the probability of getting it if that player is the same as all the others is at most $(1+2 \epsilon)^m (1-2\epsilon)^{n-m}$ (just multiply out the probability). Hence the probability of winning the tournament with at most $m$ wins as the favorite is at most $(1+2 \epsilon)^m (1-2\epsilon)^{n-m}$ times the probability of winning the tournament as an average player and at most $m$ wins, which is at most the probability of winning the tournament as an average player, which is $< 1/n$.

We can further estimate $$ (1+2\epsilon)^{n/2+m} (1-2\epsilon)^{n/2-m} = e^{ 4 \epsilon m - \frac{(2\epsilon)^2}{2} n + O( \epsilon^3 n ) }$$

So setting $m = \epsilon n + \sqrt{n \log n /2}$, the second term is $1/n$ and the first term is $$\frac{ e^{2 \epsilon^2 n + 2 \epsilon \sqrt{2 n \log n}} }{n}$$ so choosing $n$ to be approximately $\epsilon^{-2}/ \log (\epsilon^{-1})$, the exponent is $O(1)$, so $\pi(1/2+\epsilon,n)=O(1/n) = O( \log (\epsilon^{-1})/ \epsilon^{-2})$.

Thus $\pi(1/2+\epsilon,N(\epsilon)) = O( \log (\epsilon^{-1})/ \epsilon^{-2})$.

Now using the lower bound $\pi(1/2+\epsilon, n) \geq 1/n$, we obtain $N(\epsilon) \geq C \epsilon^{-2} / \log (\epsilon^{-1})$ for some constant $C$.

To upper bound $N(\epsilon)$, we use a different lower bound. By Hoeffding's inequality, the probability that either some player scores above $(1/2 + \epsilon/2 n)$ or the favorite scores below $(1/2 + \epsilon/2 n)$ is at most $e^{ - \epsilon^2 n /2}$, so $\pi(1/2+\epsilon,n) \geq 1 -n e^{-\epsilon^2 n/2}$. In particular, because $\pi(1/2+\epsilon,N(\epsilon))=o(1)$ then $ \epsilon^2 N(\epsilon)/2 \geq \log N(\epsilon) - o(1)$, so $N(\epsilon)/\log N(\epsilon) \geq 2 \epsilon^{-2} (1-o(1))$ and hence $N(\epsilon) \geq 4 \epsilon^{-2} \log (\epsilon^{-1}) (1+o(1))$.

Answer 2

(This is not a solution. I post as an answer beacuse I don't have a privilege to leave a comment) Another approach is to begin with an elementary method that Illustrates the hardness of the problem.

I will ease the condition to a condition that no player won more games than the best player.

In that setting the native elementary approach is much easier: Let $ k = {n+1 \choose 2} $ and $ m $ be the number of the best player's wins, denote also the number of solutions for $ \sum_{i=1}^n x_i = l $ by $ s(n,l) $ (trivial), and the number of solutions for $ \sum_{i=1}^n x_i = l $ s.t. $ \forall i (x_i \leq b) $ by $ sb(n,l,b) $ (simple calculation using the Inclusion–exclusion principle).

Than we get that: $$ \pi_2(p_\epsilon, n+1) = \sum_{m=0}^n \frac{sb(n,k-m,m)}{s(n,k-m)} (1/2)^{k-m} p_\epsilon^m (1-p_\epsilon)^{n-m}$$ Which is hard to analyse, so asymptotic methods like in the Arthur's answer are better.

Answer 3

An Introduction:

We have one favorite and $m\in\mathbb N:=\{1\ 2\ \ldots\}$ patzers like me for a total of $n:=m+1$ fearless chess players (who are like basketball teams--no draws are allowed). A probability win in a game between patzers is $\frac 12, $ and $\ p:=\frac 12+\epsilon\ $ for the favorite, and $\ \frac 12-\epsilon\ $ against the favorite, where $\ 0<\epsilon<\frac 12$.

Let's concentrate on the subtournament of patzers only. The expected value of each of them is then$\ \frac {m-1}2.\ $ The variance of a $1$-game event between them is

$$\frac 12\cdot\left(\frac 12\right)^2 + \frac 12\cdot\left(\frac 12\right)^2\ =\ \frac 14 $$

Thus a variance of the whole subtournament for one player is $\ \frac {m-1}4\ $ hence the respective standard deviation is $\ \frac {\sqrt{m-1}}2.\ $ Thus, the probability of a patzer scoring at least $\ M\ :=\ \frac{m-1}2 + \frac{\sqrt{m-1}}2\ $ points is at least $15\% = 0.15\ $ -- a player like this would score $M$ points in $15$ tournaments out of a $100$, on average.

On the other hand, the favorite scores at the most $\ F\ :=\ m\cdot p\ $ on at least half occasions (i.e. tournaments). The games of the favorite are independent of the games between lesser competitors. Thus the probability of a patzer getting score $\ \ge M,\ $ and of favorite getting not more than $\ F,\ $ is at least $\ 7.5\%.$

However, $\ F\le M\ $ whenever

$$ p\ \le\ \frac{m-1+\sqrt{m-1}}{2\cdot m} \,\ =\,\ \frac 12 + \frac{\sqrt{m-1}-1}{2\cdot m} $$

Then the probability of the favorite winning a tournament is not more than $\ 92.5\%:\ $

$$ \pi\ \left(\frac 12 + \frac{\sqrt{n-2}-1}{2\cdot (n-1)},\ n\right)\,\ \le\,\ 0.925 $$

This may serve as a first, very crude insight into the problem.