A game with $n$ players - II

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, given $i\le j$, I think that player $i$ wins the game with probability at most $i/j$ times the probability that player $j$ wins the game. (I can prove it manually for $n\le 4$.)

Question. Is it possible to prove it for all $n$?

Ps. Another property of the same game has been asked here.

Ps2. Is it a "known game" ?

Answer 1

To flesh out my comment a bit: you can extend your calculations out further without much difficulty, at least to $n=10$ or $n=12$ish. Iterate over all $n!$ permutations of $1..n$, and for each permutation $\rho=p_1p_2p_3\ldots p_n$ (note that this is 'mapping' notation, not cycle notation) you can compute the probability that each number is the winner by maintaing a list of the probabilities $x_1, \ldots, x_n$ that each element is the winner of the tournament (for the current permutation): initialize with $x_{p_1}=1$, and then at step $i$ (for $i=2\ldots n$), set $x_{p_j}=x_{p_j}\times\dfrac{p_j}{p_j+p_i}$ for all $j\lt i$, and set $x_{p_i}=1-\sum_{j\lt i}x_{p_j}$. Finally, just accumulate over all permutations.

Answer 2

For each subset $S\subseteq \{1,2,\ldots, n\}$, you can calculate the probability that each $i\in S$ is the winner of a random tournament of $S$. You will do this recursively. For singleton subsets, clearly the sole player is the winner. (Hooray!) For a set of size $m > 1$, iterate over the $m$ players, considering each in turn to be the last player (which will happen with probability $1/m$). In each case, the first $m-1$ players play a random tournament, which has $m-1$ possible winners whose probabilities we already computed and cached; and in each of these cases, either the last player ($i$) or the winner-so-far ($j$) is the final winner, with probabilities $i/(i+j)$ and $j/(i+j)$. So you're iterating over only $m(m-1)$ cases to get the random-tournament-winner probabilities for a particular set of size $m$, once you've done it for sets of size $m-1$. At worst it's taking $n(n-1)2^n$ steps to get the random-tournament probabilities for $\{1,2,\ldots, n\}$. This is very efficient; the Python code below runs for $n=20$ in less than a minute.

def winners(S, cache={}):
  # S will be a sorted tuple
  if cache.has_key(S): return cache[S]
  m = len(S)
  ret = {}
  for ix in xrange(m):
    i = S[ix]
    T = S[:ix] + S[(ix+1):]
    if not T:
      ret[i] = 1.0
    else:
      for (j, pj) in winners(T, cache).items():
        ret[i] = ret.get(i, 0.0) + (1.0 * pj * i) / (m * (i+j))
        ret[j] = ret.get(j, 0.0) + (1.0 * pj * j) / (m * (i+j))
  cache[S] = ret
  return ret

The results are interesting. Not only is the hypothesis true, at least that far out, but the inequality also becomes tight: the probability that $i$ wins appears to converge uniformly to $2i / (n(n+1))$ with increasing $n$. By $n=20$, each probability is within about $6\%$ of this.

Answer 3

This does also not answer the original question, but it provides a more efficient way to calculate the probabilities $p(i)$ of winning in $O(n^2)$ operations (in particular, less than exponential time).

For each $a \in \{1,\ldots,n\}$ and set $I$ such that $\{a\}\subseteq I\subseteq \{1,\ldots,n\}$, let $p(a\upharpoonright I)$ be the probability that player $a$ wins in the restricted game $I$. Then, fix $i \in \{1,\ldots,n\}$. By a simmetric argument, the probability that the permutation $\sigma$ (in the symmetric group $S_n$) of $\{1,\ldots,n\}$ verifies $\sigma(i)=k$ is equal to $1/n$ for all $k=1,\ldots,n$. Set also $[n]:=\{1,\ldots,n\}$.

It follows that \begin{align} p(i)&=\frac{1}{n}\left(\sum_{1\le j\le n, i\neq j} p(i | \sigma(j)=n ) + p(i | \sigma(i)=n )\right)\\ &=\frac{1}{n}\left(\sum_{1\le j\le n, i\neq j} p(i \upharpoonright ([n]\setminus \{j\}) )\frac{i}{i+j} + \sum_{1\le j\le n, i\neq j} p(j \upharpoonright ([n]\setminus \{i\}) )\frac{i}{i+j} \right) \\ &= \frac{i}{n} \sum_{1\le j\le n, i\neq j} \frac{p(i \upharpoonright ([n]\setminus \{j\}) )+p(j \upharpoonright ([n]\setminus \{i\}) )}{i+j}. \end{align}

(Probably the above formula can be used to prove the claim by induction, but I am not sure about it.)