15

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" ?

  • For each permutation (corresponding to an extraction order) you can compute the probabilities recursively in $O(n^2)$ time so it shouldn't be hard to extend your table out to $n=10$ or so. – Steven Stadnicki Feb 24 '18 at 01:19
  • 2
    I confirmed this up until $n=9$ with a python script. – saulspatz Mar 01 '18 at 20:07
  • @saulspatz thank you: I already did some simulations before posting the question, that's why I believe it is true –  Mar 01 '18 at 22:47

3 Answers3

3

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.

Steven Stadnicki
  • 51,746
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.

mjqxxxx
  • 41,358
  • 1
    A heuristic argument for the tightness i.e. convergence to $i/\binom n2$ is to consider the long-run behaviour of the game where players are chosen independently with replacement, from the uniform distribution on ${1,\dots,n},$ at each round. This gives a Markov chain with transition probabilities given by $p_{i,j}=\tfrac{j}{i+j}/n$ for $i\neq j.$ The distribution $\pi_i=i/\binom n2$ satisfies the detailed balance equation, and the chain is ergodic, so $\pi$ is the limiting distribution. – Dap Mar 03 '18 at 18:17
  • Err, make that $\binom{n+1}2$ in the previous comment – Dap Mar 03 '18 at 19:12
  • Code seems rather odd. In the for (j, pj) in winners(T, cache).items() loop I can't see where pj is used. – saulspatz Mar 04 '18 at 16:20
  • @saulspatz: the pj is a "dummy variable". Some people suggest using an underscore or a variable name starting with "dummy", but there's no PEP8 rule (official Python convention). – Dap Mar 06 '18 at 12:16
  • @Dap I meant that I don't understand why it isn't being used. It seems to me that in the loop should have pj in place of 1.0 in the formulas. When I run sum(winners((1,2,3)).values()) I get 1.9999999999999998. – saulspatz Mar 06 '18 at 15:09
  • @Dap When I make that change, the calculations agree with my brute-force answers to 15 decimal places for $2 \le n \le 7$ The speedup is truly impressive +1. – saulspatz Mar 06 '18 at 16:17
  • My last comment should have been addressed to mjqxxxx instead of Dap, but it's too late to edit it. There's an error in the code. Please read my previous comments. – saulspatz Mar 06 '18 at 16:26
  • Whoops, you're right... I shortened that code after pasting it into my answer and tried to sync by hand :). I'll fix it. – mjqxxxx Mar 06 '18 at 23:50
0

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

Paolo Leonetti
  • 15,423
  • 3
  • 24
  • 57
  • This doesn't give a polynomial time algorithm in any way I can see - there are exponentially many $p(a\upharpoonright S)$ values. Also, currently, $p(a\upharpoonright b)$ is defined but the equations only use $p(a\upharpoonright S)$ for a set $S,$ to mean the probability that $a$ wins in the game with players in $S.$ – Dap Mar 04 '18 at 19:05
  • @Dap: thanks for pointing out the notation inconsistency, I fixed it. However, about the polynomial time, I wasn't thinking on the restrictions $p(a \upharpoonright S)$ for all subsets $S$, but to obtain it recursively from subsets to cardinality $2$, to subsets of cardinality $3$, up to $n$, which requires $\le \sum_{i\le n}i$ operations. – Paolo Leonetti Mar 04 '18 at 23:01