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