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?



For a round-robin tournament, what is the favorite's least favorite size?
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))$.


