13
$\begingroup$

$n$ players indexed $1,2,...,n$ play a game of mock duel. The rules are simple: starting from player $1$, each player takes turns to act in the order $1,2,...,n,1,2,...$. In his turn, a player randomly chooses one of the other remaining players as target, and fires one shot at him. If hit, the target is removed from the game. Whoever survives to the last is the winner. All players have the same marksmanship $0\lt p\le 1$, meaning that their shots hit target with probability $p$.

An example: if $p=1$ and $n=3$, player $1$ randomly chooses $2$ or $3$ as his target and fires one shot. The survivor of $1$'s shot will shoot next and fire at the only other remaining player, player $1$. Hence in this case the three players have winning probabilities $0,0.5,0.5$ respectively.

Question: which player has the highest winning probability for large $n$'s?

To be more specific, let's define $B(n)$ to be the player with the highest winning probability for the $n$-players game. Are there any regularity about where $B(n)$ tends to occur in $(1,2,...,n)$? In particular:

  1. Does $\lim_{n \to \infty} B(n)/n$ exist for any $p$?

  2. Is $\lim_{n \to \infty} B(n)=1$ if $p$ is sufficiently small?

Edit: Clarified the rules to address possible ambiguity suggested in the comments.


If my calculation is correct, the winning probability for player $k$ in the $n$ players game, $s(n,k)$, is given by the recursive formula:

$$ \begin{align} & s(n,1)=(1-p)s(n,n)+ps(n-1,n-1)\\ & s(n,2)=(1-p)s(n,1)+\frac{n-2}{n-1}ps(n-1,1)\\ & s(n,k)=(1-p)s(n,k-1)+\frac{n-k}{n-1}ps(n-1,k-1)+\frac{k-2}{n-1}ps(n-1,k-2) \end{align} $$ for $k\gt 2$.

For large $n$'s and $p=1$, plotting $s(n,k)$ against $k$ looks like sinusoid:

enter image description here

If you plot the peaks of these curves (i.e. $B(n)$) against $n$, you get this:

enter image description here

At first glance it seems $B(n)$ just oscillates between $1$ and $n$ in a self-similar fashion. But actually the hill tips wear off further and further away from the diagonal line as $n$ increases and the valleys also grow flatter:

enter image description here

One can wonder whether the hills will eventually fall to small bumps or be flattened relative to the diagonal line, meaning that $\lim_{n \to \infty} B(n)/n=0$.

On the other hand, $B(n)=1$ becomes more often as $p$ gets smaller. Blue curves are $B(n)$ for $p=0.5,0.48,0.46$ respectively, for $n$ up to 5000 (larger $n$'s take exponentially more time to compute):

enter image description here enter image description here enter image description here

Can we claim that $\lim_{n \to \infty} B(n)=1$ for small $p$? Or is there always exceptions?

$\endgroup$
17
  • $\begingroup$ Do the players decide who they fire at, or is that also random? Assuming they decide, then the question isn't necessarily well-formed yet, as there could be multiple Nash equilibria (intuitively the first player has an advantage, but the other players could gang up on that player, etc). $\endgroup$ – Sean Eberhard Jun 14 '20 at 16:15
  • 3
    $\begingroup$ Related to oeis.org/A071818 $\endgroup$ – Julian Rosen Jun 14 '20 at 19:42
  • 1
    $\begingroup$ @Eric I think there's ambiguity regarding "fire one shot randomly". Does it imply that the target is chosen (uniformly?) at random, that the shot has a chance of missing, or both? $\endgroup$ – Ilkka Törmä Jun 16 '20 at 6:01
  • 2
    $\begingroup$ I agree, after thinking about it for more than 1 minute, it's clear that this question is not at all about a game. But you made that kind of hard on your reader by saying "game" in the title, first line of the question, etc. $\endgroup$ – Sean Eberhard Jun 16 '20 at 11:36
  • 2
    $\begingroup$ @DieterKadelka p=1 means player 1 will remove his target for certain. Whoever his target happens to be, after that target is removed, there're now n-1 players and he becomes the last one of them to shoot. $\endgroup$ – Eric Jun 16 '20 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.