Skip to main content
Proof of optimality
Source Link
Magma
  • 5.4k
  • 15
  • 31

Alice can achieve a victory probability of

$1$ if $N = 1$, and arbitrarily close to $100\%$$1$ if $N > 1$.

Proof:

For $N = 1$, Alice just gives herself a $100\%$ gun and goes first. For $N > 1$, Alice chooses $N+1$ gun accuracies uniformly randomly from the interval $[1-\varepsilon/N,1]$ for a very small $\varepsilon$, and assigns them to players arbitrarily in arbitrary turn order in her mind. Now almost surely (with probability $1$) there is no situation where any player has a choice between two or more shots that grant him equal odds of survival, so all players have a unique deterministic strategy. Now with probability at least $1-\varepsilon$ the first $N$ shots will hit, so there is a particular player that would have very high chances of winning the game with this setup. So to make her own chances of victory at least $1-\varepsilon$, all Alice has to do is to exchange her assigned position and gun with the position and gun of this winning player.

Proof that there is no better strategy:

Assume Alice has a strategy for $N > 1$ that wins with probability $1$. Since Alice's strategy yields certain victory, the other players don't really care about who they shoot since they're doomed anyway, and since Alice cannot prevent all other players from shooting, one of these shots may hit her after all. Contradiction.

Alice can achieve a victory probability of

arbitrarily close to $100\%$.

Proof:

Alice chooses $N+1$ gun accuracies uniformly randomly from the interval $[1-\varepsilon/N,1]$ for a very small $\varepsilon$, and assigns them to players arbitrarily in arbitrary turn order in her mind. Now almost surely (with probability $1$) there is no situation where any player has a choice between two or more shots that grant him equal odds of survival, so all players have a unique deterministic strategy. Now with probability at least $1-\varepsilon$ the first $N$ shots will hit, so there is a particular player that would have very high chances of winning the game with this setup. So to make her own chances of victory at least $1-\varepsilon$, all Alice has to do is to exchange her assigned position and gun with the position and gun of this winning player.

Alice can achieve a victory probability of

$1$ if $N = 1$, and arbitrarily close to $1$ if $N > 1$.

Proof:

For $N = 1$, Alice just gives herself a $100\%$ gun and goes first. For $N > 1$, Alice chooses $N+1$ gun accuracies uniformly randomly from the interval $[1-\varepsilon/N,1]$ for a very small $\varepsilon$, and assigns them to players arbitrarily in arbitrary turn order in her mind. Now almost surely (with probability $1$) there is no situation where any player has a choice between two or more shots that grant him equal odds of survival, so all players have a unique deterministic strategy. Now with probability at least $1-\varepsilon$ the first $N$ shots will hit, so there is a particular player that would have very high chances of winning the game with this setup. So to make her own chances of victory at least $1-\varepsilon$, all Alice has to do is to exchange her assigned position and gun with the position and gun of this winning player.

Proof that there is no better strategy:

Assume Alice has a strategy for $N > 1$ that wins with probability $1$. Since Alice's strategy yields certain victory, the other players don't really care about who they shoot since they're doomed anyway, and since Alice cannot prevent all other players from shooting, one of these shots may hit her after all. Contradiction.

Source Link
Magma
  • 5.4k
  • 15
  • 31

Alice can achieve a victory probability of

arbitrarily close to $100\%$.

Proof:

Alice chooses $N+1$ gun accuracies uniformly randomly from the interval $[1-\varepsilon/N,1]$ for a very small $\varepsilon$, and assigns them to players arbitrarily in arbitrary turn order in her mind. Now almost surely (with probability $1$) there is no situation where any player has a choice between two or more shots that grant him equal odds of survival, so all players have a unique deterministic strategy. Now with probability at least $1-\varepsilon$ the first $N$ shots will hit, so there is a particular player that would have very high chances of winning the game with this setup. So to make her own chances of victory at least $1-\varepsilon$, all Alice has to do is to exchange her assigned position and gun with the position and gun of this winning player.