14
$\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$ Commented Jun 14, 2020 at 16:15
  • 3
    $\begingroup$ Related to oeis.org/A071818 $\endgroup$ Commented Jun 14, 2020 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$ Commented Jun 16, 2020 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$ Commented Jun 16, 2020 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
    Commented Jun 16, 2020 at 13:33

0

You must log in to answer this question.

Browse other questions tagged .