10
$\begingroup$

Alice is involved in a duel with $N$ other opponents. She can choose a gun for herself with any hit probability as she wishes. She also prepares guns for her opponents, whose hit probabilities she can freely determine provided they're no less than 1%.

Each player takes turns to shoot in the order specified by Alice. In his/her turn, a player must shoot one shot at another player. This process continues until only one survives. Players are intelligent and rational. They correctly calculate which targets to shoot to maximize their own survival probabilities. (In case where different choices of target yield equally maximizing survival probability for a shooter, he/she just randomly shoot one of those targets.)

An example: when $N=2$, if Alice give herself a gun with hit probability 100%, and give both of her opponents guns with hit probability 1%, she can guarantee herself survival probability of 99% by specifying herself as the first one to shoot. The 99% survival rate is achieved by her randomly killing one of the opponent and dodging the other's bullet.

Question: Is there a strategy for Alice to achieve decent survival probability for a very large $N$? What are some good strategies?


Hint:

If $N$ is large, say 100, it'll be a terrible idea for Alice to choose 100% gun for herself and give all her opponents 1% guns. She will become targets of many, and minnows do bring down a giant if they're a vast crowd.

$\endgroup$
4
  • $\begingroup$ I think this question is similar (modified version) to a pirate captain who wants to distribute a certain amount of coins to other fellow pirates on a vote basis. If majority doesn't agree with the captain, the captain is killed and new one will be elected and then distribution begins again. $\endgroup$ Commented Jun 13, 2020 at 8:42
  • 2
    $\begingroup$ @JohnBrookfields The pirate game is a great one, but bears no connection to this one. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 9:11
  • 2
    $\begingroup$ If there are a million shooters with 1% accuracy and one with 100% accuracy, it is not clear everybody will shoot at the 100% shooter. Because after the 100% shooter is dead, people will shoot each others. It is interesting for a 1% shooter to work on reducing the number of 1% shooters before the 100% shooter dies. It becomes interesting to shoot the 100% shooter only when his turn is approaching. $\endgroup$
    – Florian F
    Commented Jun 13, 2020 at 19:27
  • $\begingroup$ @FlorianF Very shrewd observation! Actually you don't need a number as large as a million at all. My estimation is that when there're about a few hundred shooters, some 1% will start to shoot each other already, if you really work out the math. Of course, that computation will be infeasible to carry out by hand because for optimal strategies you have to start the recursion from $N=1$ and work upward. A computer program may or may not be feasible for that task, depending on how fast the complexity goes up with $N$. $\endgroup$
    – Eric
    Commented Jun 14, 2020 at 0:08

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ You nailed it, congrats! :) $\endgroup$
    – Eric
    Commented Jun 14, 2020 at 0:40
  • 1
    $\begingroup$ So we offload the burden of calculating who has the highest probability of winning to Alice? In effect, when the question says the players can calculate correctly the winning chances, we are using that information to get to the answer directly without us knowing which one is the winning player? Wow. $\endgroup$
    – justhalf
    Commented Jun 14, 2020 at 1:00
  • $\begingroup$ @justhalf In principle, you can always do the calculation by starting from $N=2$ and work your way upwards, a rough estimation of computational complexity is about $O(N^22^N)$ for large $N$. Magma's is basically an existence proof, calculation is implicit, but not absent. $\endgroup$
    – Eric
    Commented Jun 14, 2020 at 1:48
  • 1
    $\begingroup$ For example the probability of at least $1-\varepsilon$ for the first $N$ shots to hit is not qualified. I guess the actual lower limit is $\left(1-\frac{\varepsilon}{N}\right)^N$? Some steps are required to say that it is higher than $1-\varepsilon$. $\endgroup$
    – justhalf
    Commented Jun 14, 2020 at 2:01
  • 2
    $\begingroup$ @justhalf You can verify that the function $f(N)=\left(1-\frac{\varepsilon}{N}\right)^N$ is increasing in N and $f(1)=1-\varepsilon$. $\endgroup$
    – Eric
    Commented Jun 14, 2020 at 2:16
1
$\begingroup$

With $N$ others, let's take the default strategy to be that Alice has a 100% gun while all others have 1% guns, with Alice shooting first. It is instructive to see what kind of survival probability this gives Alice.

In the first turn, Alice kills one other. There are $(N-1)$ left, and they will all aim at her. Her chance of surviving this turn is $0.99^{N-1}$.

In the second turn, Alice kills one more. There are now $(N-2)$ left, so her chance of surviving this turn is $0.99^{N-2}$.

Continuing with this idea, Alice's total survival probability is: $$\mathbb{P}(\text{survival}) = 0.99^{N-1} \times 0.99^{N-2} \times \dots \times 0.99^1 = 0.99^{T_{N-1}},$$ where $T_n$ is the $n$th triangular number.

Here's what that looks like for various values of $N$. $$ \begin{array}{|c | c |}\hline N & \mathbb{P}(\text{survival}) \\ \hline 2 & 0.99\\ \hline 3 & 0.9703\\ \hline 4 & 0.9415\\ \hline 5 & 0.9044\\ \hline 8 & 0.7547\\ \hline 10 & 0.6362\\ \hline 12 & 0.5151\\ \hline 15 & 0.3481\\ \hline \end{array}$$ With more than 12 opponents, her survival rate drops to below 50% with the default strategy. It makes sense to consider other methods for large $N$.

We might try a hidden strategy. Alice hides in plain sight by giving other players higher hit rates. As a starting point, we could give all other players 51% guns. Alice get a 50% gun (for now, let's just say she shoots last). Being intelligent and rational, the players will always aim at each other first. This will then always reduce to a one-to-one contest, where Alice has a 50% chance of survival (you can replace 51% with $(50+\delta)\%$ for any small $\delta > 0$). Based on this, the ceiling appears to be 50% for large $N$ with the best available strategy, but I'm not certain of this.

$\endgroup$
4
  • $\begingroup$ Nice try! But let's consider (1,2,3,Alice) with Alice 50% and the others 51% as you suggested. If 1 kills Alice, it's (1,2,3) with 2 shooting. A little calculation shows that 1 has surviving chance about 33.5% in this case. If 1 kills 3 (or 2, it doesn't matter for him), then it's (1,2,Alice) with 2 shooting first. A little calculation shows that 1 has surviving chance of only 14.2%. So 1 will shoot Alice. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 15:44
  • $\begingroup$ Intuitively, killing Alice is better for 1 because 2 will randomize between 1 and 3 if Alice is dead, but if Alice is alive, 2 will just shoot 1. 1 wants someone to share the burden of 2's shot, which is impossible with Alice alive. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 15:44
  • $\begingroup$ So Alice's hit rate needs to be significantly lower than 51% percent for 1 to NOT shoot her. She probably needs a 30%-something gun to compensate for 2's concentrated fire after 1 kills 3. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 15:54
  • $\begingroup$ Also, you may want to take a look at Florian's and my comment about the default strategy under the question. $\endgroup$
    – Eric
    Commented Jun 14, 2020 at 1:02
0
$\begingroup$

Give everyone else 100% guns. Give herself an 99% gun. Shoot last.

Everyone else will shoot somebody with a 100% gun. By the time she shoots, there will be 1 opponent left. She wins with 99%, and the other remaining person wins with 1%.

$\endgroup$
7
  • 1
    $\begingroup$ I'm afraid this strategy won't work. Let's consider 4 players, shooting in the order 1,2,3,Alice. If 1 shoots 2, he'll be killed by 3 and has zero chance to survive. Same thing if he shoots 3, get killed by 2. If 1 shoots Alice, now there are 1,2,3 left and it's 2's turn to shoot. It's equally good for 2 to shoot 1 or 3, so he'll shoot randomly. This leaves player 1 50% chance to survive. So 1's best choice is to shoot Alice. Alice is doomed. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 13:04
  • $\begingroup$ @Eric right. 1 is a special case. I think anyone else who shoots Alice will not get a second shot. $\endgroup$
    – David G.
    Commented Jun 13, 2020 at 13:34
  • $\begingroup$ besides, even if everyone avoids shooting Alice, by the time Alice shoots ,there will be N/2 opponents left, not one. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 14:00
  • $\begingroup$ @Eric That's only if everyone shoots forward. But you are correct that there can be more than one survivor. On the other hand, if everybody (other than 1) shoots someone who has already shot, there will be only one left when Alice comes up. Ah... complexity. $\endgroup$
    – David G.
    Commented Jun 13, 2020 at 14:40
  • 1
    $\begingroup$ @DavidG. If you allow communication between players before the game, it becomes a totally different game instead. $\endgroup$
    – Eric
    Commented Jun 13, 2020 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.