Generalizing the "shooting puzzle"

Question

Inspired by this puzzle.

You have $n$ shooters having a duel, labeled $1, 2, ... n$. Each shooter has an accuracy of $k_n$, with each $k_n$ some probability in $(0,1]$, with $k_1 < k_2 < ... < k_n$. The first shooter is the least accurate, while the last shooter is the most accurate.

The duel works as followers. Starting with the least accurate (1) and working towards the most accurate (n), each shooter may choose to pass or to shoot at one person. If they hit, the target is out of the duel. If after the most accurate remaining shooter's turn there is still more than one shooter left, the cycle restarts with the least accurate remaining shooter. They game ends when one shooter is left, who wins the duel.

What is each shooter's general strategy to maximize their chance of winning? Do their strategies change if the game ends when there are two shooters left?

Answer 1

Edited: OK, so on reflection my original answer shown below in italics was not entirely correct. For n>=4 player n-2 should never pass.

(Original non-optimal strategy for n>=4)... For n>3 1..n-3 shoot at n n-2 shoots or passes depending on specific accuracy of duelists n-2, n-1, and n n-1 shoots at n n shoots at n-1

To illustrate this, imagine if four very good shots (accuracy 0.997, 0.998, 0.999, and 1.0 respectively) are in a quaduel. Best strategy for 1 is still to shoot 4, then 2 shoots 3, then 4 shoots 2. But in the 3% of occasions where 1 misses, it is not best for 2 to pass as then 3 shoots 4, 1 passes, 2 shoots 3 and 1 shoots 2. Instead, 2 should shoot 1 and 3 shoots 4, 2 shoots 3 and lives.

Updated conjectures for optimal strategies below:

For n=2

1 shoots at 2 
2 shoots at 1

For n=3

1 shoots or passes depending on specific accuracy of each duelist  
2 shoots at 3
3 shoots at 2

For n>3

1..n-3 shoot at n
n-2 shoots at n depending on accuracy of duelists n-2, n-1, and n, or shoots n-3
n-1 shoots at n
n shoots at n-1

Justification

For n=2 it is clearly better to shoot than to pass as, if 1 has accuracy x and 2 has accuracy y, shooting first gives 1 the probability of survival x/(x+y-xy) which is strictly greater than (x-xy)/(x+y-xy) which is the probability of survival if 1 waits for 2 to shoot first.

For n=3 and probabilities x < y < z for i,2,3 respectively, 1 will shoot if the inequality

 (x-xy)(y+z-yz)(x+z-xz) > xy(x+z-xz) + x(z-yz)(x+y-xy) 

is true (someone with access to Mathematica may be able to simplify or make better sense than that), otherwise (s)he will pass. This results from the two scenarios:

1) successfully shooting 3 and then being second shot in a duel against 2, or

2) failing to shoot 3 (possibly repeatedly) or waiting for 2 and 3 to fight it out in which case (s)he will end up as first shot in a duel with 2 or 3 (there will be a different probability of each of those cases).

Shooters 2 and 3 are effectively in a duel and will shoot at each other as in the n=2 case.

For n>3 n-1 and n still are still effectively in a duel so will duke it out. n-2 is in a similar position as in the n=3 case so will make a similar choice to shoot at n (or not). But instead of passing it is better to remove the biggest threat amongst the weaker players. The choice criterion (shoot n or not?) will be a little different than that for the n=3 game, but in most cases not significantly different. 1..n-3 are always better off if they eventually end up as '3rd-man' in a duel where the stronger players are weaker shots so, for example in the n=4 situation, 1 would rather face 2 and 3 than 2 and 4 or 3 and 4, so the weaker players are always be happy to shoot at the strongest surviving player.

I think these tactics are will be valid for most situations. But for 5 or more players, if they are all very strong, there may be situations where it is still occasionally better for some weaker players to pass.

Answer 2

I think it is in $k_1, k_2, ... , k_{n-1}$ interest to each shoot $k_n$. If they all miss, it is $k_n$ interest to shoot the $n-1$ st shooter. This strategy may require collusion, and perfect information. When two players are left, it is still a valid strategy.

Answer 3

This problem is not well-defined if you allow players to pass their turns without additional constraints. Because you cannot rule out the situation where everyone just chooses to pass, in which case you're in a impasse: everyone survives and the game never ends.

One way to avoid this is to stipulate that players can choose to pass at most $M$ times, for any $M$ you like. Then you can use dynamic programming to solve the general case by working backward starting with the case where everyone has used up their "pass rights". Then work down the following ladder:

• Only one of the players has one pass right.

• Two of the players have one pass right each.

  ...

• All of the players have one pass right each.

• Two of the players have two pass rights each, the rest have one each.

  ...

• All of the players have two pass rights each.

  ...

• All of the players have $M$ pass rights each.

So let's consider the starting case where no one has any pass right. This too can be solved by dynamic programming starting with the case where only one player is left. If my programming is correct, there seems to be no general rules and players choices of targets seems unintuitive. Some examples:

1. Accuracies: $0.2,0.4,0.6,0.8,1$, then targets for the players are $5,5,2,5,4$.
2. If you change accuracy of player 2 above from 0.4 to 0.5 however, Targets change to $4,5,2,5,4$. Try explain that!
3. Ten shooters, accuracies: $0.1,0.2,...,0.9,1$. Targets choices are $ 4, 1, 5, 9, 2, 9 , 6 , 7 , 10 , 3$. No intuition can explain that.

---

For pass rights cases, the programming becomes a bit messy, although the method is clear. Computational complexity may be something to the order of $O(2^{nM^2})$. So $n=10$ with even 2 pass rights is probably infeasible to calculate.