2

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?

saulspatz
  • 53,131
  • Sure. The probability space is all permutations of ${1,\dots,n}$. Match a permutation $\sigma$ with the permutation $\sigma'=(i,j)\sigma(i,j)$. Prove that the probality of $i$ winning is greater for $j$ in condition $\sigma$ than it is for $i$ to win in $\sigma'.$ Since $\sigma''=\sigma$ this pairing gets us the inequality you want. It's a bit tedious, probably, but this is essentially the intuition. – Thomas Andrews Feb 18 '18 at 23:14
  • I think you can do it by induction if you generalize it a bit. Say the players have powers $p_1, p_2, ..., p_n.$ When players $i,j$ each player's probability of winning is proportional to his power. Then I would guess that player $i$'s probability of winning the whole match is $p_i/\sum{p_k}$ If that's true, I'd bet it's easy to show by induction. – saulspatz Feb 18 '18 at 23:24
  • @ThomasAndrews Thank you: I already tried that way before posting the question. But there are some permutations $\sigma$ for which, even if $i>j$, the probability of $i$ winning "in that particular permutation $\sigma$" is smaller than the one of $j$.. Hence, there should be some regroupment argument of permutations, e.g., all permutations for which $\sigma(i)$ is kept fixed. But I couldn't formalize it even it seems that it has to be true (maybe for some trivial reason, I don't know).. –  Feb 18 '18 at 23:37
  • @saulspatz Thanks also to you! Btw, you can prove that your claim (I tried that one too!) is false already for $n=3$.. –  Feb 18 '18 at 23:39
  • You're right. I just proved it false for $n=3,$ and was just about to post a note to that effect. – saulspatz Feb 18 '18 at 23:43

2 Answers2

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.

saulspatz
  • 53,131
  • Dear saulspatz thanks for your answer: however, I don't understand a step (I am sorry if this will be a trivia question for you). In the case you assume that, in the first stage, a different player $k$ is extracted and has to play with, let's say $i$. Then I agree that $P_i=\frac{p_i}{p_i+p_k}P(i,[n]\setminus {k})$. But why $P_j$ will have that form? –  Feb 19 '18 at 01:07
  • @Nduccio I'm comparing the case where $i,k$ are matched in the first round to the case where $j,k$ are matched in the first round. BTW, don't apologize. If I don't want to answer your questions, I shouldn't post answers. – saulspatz Feb 19 '18 at 01:09
  • Oh ok: but in the first case where $i,k$ are matched in the first round (and $j$ in later rounds) how do you know that $P_i$ is still greater than $P_j$? I mean, the case $j,k$ in the first round is another case.. Btw I agree with you that also the "highlander" variant should be true :) –  Feb 19 '18 at 01:12
  • @Nduccio Let me try to make the answer more detailed for you. Give me a few minutes. – saulspatz Feb 19 '18 at 01:16
  • Dear saulspatz I have all the time you want: thanks a lot for your patience :) –  Feb 19 '18 at 01:21
  • I read your edit: after a second thought, would it be correct to say that, just in the last case where exactly one between $i$ and $j$ are playing at the first round, you are considering pairs of permutations $\sigma$ and $\sigma^\prime$, where $\sigma^\prime$ exchanges only the positions of $i$ and $j$? –  Feb 19 '18 at 01:35
  • Yes, that's what I'm doing. My proof is essentially the same as the one that Ross Millikan posted, except that I tried to make it more explicit. – saulspatz Feb 19 '18 at 02:00
  • Apart from the induction, I wouldn't say it is logically the same: he fixes a correspondence between permutations, while you fix only the first two players playing. However, this morning I realize I have one more doubt (sorry for this): if $i,k$ are extrected at the first round, then the probability of $i$ winning should be $p_i^{n-1}/\prod_{i\neq t}{p_i+p_t}$, right? And the probability of $j$ winning is $$p_i/(p_i+k)P(j,[n]\setminus {k}) + p_k/(p_i+p_k)P(j,[n]\setminus {i})$$.. In this case why $P_i>P_j$? –  Feb 19 '18 at 10:38
  • No, I don't understand how you get that at all. – saulspatz Feb 19 '18 at 10:41
  • My fault, I see now your point! –  Feb 19 '18 at 14:19
1

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.

Ross Millikan
  • 374,822
  • Dear Ross Millikan, if I am not wrong, you are basically saying that, pairing $\sigma$ with $\sigma^\prime$ (which exchanges $i$ with $j$), then the probability of $i$ winning in $\sigma$ is greater than the probability of $j$ winning in $\sigma^\prime$. But I think that this depends on the positions of $\sigma(i)$ and $\sigma(j)$... –  Feb 19 '18 at 01:24
  • That is my claim. I make the point that the positions of $\sigma(i)$ and $\sigma'(j)$ are the same. That is the correspondence between $\sigma$ and $\sigma'$ – Ross Millikan Feb 19 '18 at 04:30