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 proportion of won games converges almost surely to $p$ for the favorite and almost surely to $1/2$ for the other players, so we can easily separate the favorite from the best of the rest; the lack of independence among the non-favorites can be finessed by using a union bound.

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?

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?

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(n,p)$ 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 proportion of won games converges almost surely to $p$ for the favorite and almost surely to $1/2$ for the other players, so we can easily separate the favorite from the best of the rest; the lack of independence among the non-favorites can be finessed by using a union bound.

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?

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 proportion of won games converges almost surely to $p$ for the favorite and almost surely to $1/2$ for the other players, so we can easily separate the favorite from the best of the rest; the lack of independence among the non-favorites can be finessed by using a union bound.

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?