A game with $n$ players

Question

Consider $n$ player numbered $1,2,\ldots,n$. If player $i$ fights against $j$ then $i$ wins with probability $i/(i+j)$. There are no ties.

A player $i_1$ is extracted at random. Then, a second different player $i_2$ is extracted at random. They fight against each other.

Then, we extract another player $i_3$ ($\neq i_1,i_2$). The winner of the latter round fights against $i_3$.

The fights continues until all players have been extracted, hence $n-1$ fights in total.

Now, it is really intuitive that $i$ wins the game with bigger probability than $j$ whenever $i>j$. I can prove it manually for $n\le 3$. Is it possible to prove it formally?

Answer 1

This can be proved by induction on $n$ if we alter the rules to make the game a bit more general. Say that player $i$ has power $p_i\ge 0,$ and that when players $i,j$ meet, the probability that player $i$ wins is $p_i/(p_i+p_j).$ Then I claim that player $i$ is more likely to win the tournament than player $j$ if and only if $p_i > p_j$.

Let $[n] = {1,2,\cdots,n}$. Denote the probability that player $k$ wins a tournament among the players in $X \subseteq [n]$ by $P(k, X).

First let us observe that the probability that player $i$ wins the tournament is an increasing function of $p_i,$ if the powers of all other players does not change. This is clear, because if we compare any two tournaments, the probability that player $i$ survives any given match is greater when his power is greater, since $x/(x+a)$ is a strictly increasing function of $x$.

Now let us prove the theorem. It is true by definition if $n=2,$ so suppose $n>2$ and the theorem is true for $n-1.$ We will look at all the cases that can occur in the match, and show that player $i's$ probability of winning is greater than player $j$'s in each case. EDIT: There are $\binom{n}{2}$ possible meetings in the first round, and each meeting has two possible outcomes, so there are $n(n-1)$ possible outcomes in the first round. If we add up the probabilities that player $i$ wins given that outcome multiplied by the probability of that outcome, we have have the probability that $i$ wins. There is no need to look at further rounds. What the proof does is match up those outcome for $i$ and $j$ and prove that the conditional probability that $i$ is the eventual winner is greater than the conditional probability that $j$ is the eventual winner in each case.

First, it may be that in the first match, neither player competes. Then player $i$'s probability of winning in greater, no matter who wins, by the induction hypothesis.

Next, players $i$ and $j$ may meet. In this case, player $i$'s probability of winning the tournament is $$ P_i=\frac{p_i}{p_i+p_j}P(i,[n]\setminus\{j\})$$ and player $j$'s probability of winning is $$P_j= \frac{p_j}{p_i+p_j}P(j,[n]\setminus\{i\})$$ By the observation before the proof, each term in $P_i$ is greater than the corresponding term in $P_j.$

We have to deal with the case where one of the players is selected, and the other not.

Now suppose player $k$ is selected, where $k\ne i,j$ and the other player selected is one of $i, j.$ This case is very like to the last one. We have $$ P_i=\frac{p_i}{p_i+p_k}P(i,[n]\setminus\{k\})\text{ and } P_j=\frac{p_j}{p_j+p_k}P(j,[n]\setminus\{k\}).$$ Once again, we use the observation to see that each term in $P_i$ is greater than the corresponding term in $P_j$.

So my foolish guess at the probability was wrong, but the general approach was right. Somewhere in Three Pearls of Number Theory Khintchine remarks that's it's often easier to prove a stronger statement by induction than a weaker one, because we get to make a more power induction hypothesis. This is an extreme case. If you required the players to be numbered with consecutive integers, you can't even approach it by induction.

Here's another idea. Suppose the game is played like the Highlander. Every time you win a match, you acquire your opponent's power, in addition to your own. I'm sure once again that a more powerful player is more probable to win, and the above proof can probably be modified to deal with this case, but I wonder if there might be a tractable formula for the probability of winning.

Answer 2

A player's chance to win the tournament is the average over all permutations of the contestants of his chance to win that permutation. For a given permutation, consider the probability that $i$ wins the tournament and compare that with the probability that $j$ wins the permutation where $i$ and $j$ are interchanged. We will still account for all the permutations for each of $i$ and $j$, but we can compare these two easily. The probability distribution of the opponent coming to $i$ in the first case or $j$ in the second case is the same, so $j$ will have a lower probability to win the first fight. At each stage along the way except the one where $i$ would meet $j$ they are meeting the same opponent, so again $j$ has a lower probability of winning. At the stage where $i$ and $j$ would meet assuming the first to be extracted keeps winning, $i$ has a higher probability of winning, so $i$ has a higher probability of winning overall.