Thread: Game theory: problem of the shooters

n shooters numbered 1~n play a game. Their probability of hitting a target are 0<p1<p2<p3<...<pn<1.

Before the game, the referee arranges the n players in some order. When the game starts, each player takes turns to shoot each other according to that order (For example if the order is 4,3,6,1,... then shooter 4 fires first, then shooter 3 fires, then shooter 6, ect, if they are still alive). When the last alive person in the order finished shooting, the first alive person in the order again resumes, so on and so forth according to the order. The game ends when there's only one person left. We say that he survives.

After the referee arranged the order, each player must simultaneously determine his shooting priority list for the rest n-1 people except himself. He must adhere to the list throughout the game, i.e., always shoot the first alive person on that list. We call this priority list his strategy. Obviously, each player has (n-1)! strategies to choose. Each player wants to maximize his surviving probability.

Question 1: Suppose the referee arranges the shooters in the order: 1,2,3,...,n. Is there a dominant strategy for shooter 1? (A dominant strategy is the best strategy for the play no matter what other plays' strategies are, i.e., it always maximizes his surviving probability, regardless of what strategies other people choose)

Question 2: Is there a Nash equilibrium for the order in Q1?

Question 3: Suppose the referee arranges the shooters in some arbitary order, is there always a dominant strategy for the first person in that order? Is there always a Nash equilibrium?

Question 4: Above is a simplistic way to specify players' strategies. When there are fewer players left, a shooter may very well want to change his shooting priorities. Thus it is more reasonable to place no restriction on who the shooter must shoot first (of course, he must shoot some person other than himself. But there's no restrictions on who, in any case). Alternatively, in this case we can think of his strategy as specifying the shooting priority list for any k people (k=2,3,4,...,n-1). How can we rethink Q1~Q3 in this case?

--------------------------------------------------------------------------------
It is a puzzle in many books when n=3. But i've been considering the general case: whether the problem remains simple or becomes intractably complex. Any suggestions or opinions are welcome.

I've considered the case of four shooters. I considered strategies in the sense of question 4, with the referee's order (1,2,3,4). What I discover is this:

1's dominant strategy: (4,3,2) in case there are four people and (3,2) (4,2) (4,3) in case there're 3
2's dominant strategy: (4,3,1) and (3,1) (4,1) (4,3)
4's dominant strategy: (3,2,1) and (2,1) (3,2) (3,1)

these 3 people behave normally: they just shoot the most accurate shooters first.

3's best strategy, however, turns out to be unexpected. To appreciate this, let p1=0.91, p2=0.92, p3=0.93, p4=0.94. In case of 4 people, what will 3 do? Now the effective order is (3,4,1,2). If 3 shoot 4 first, he has very high probability of success. But if 4 dies, the effective order becomes (1,2,3). From the above we know 1 and 2 will shoot 3 first, thus 3 puts himself in a very dangerous position. Actually, it is best for 3 to shoot 2 first! If 2 dies, the effective order becomes (4,1,3). Then 4 will shoot 3 first, but this threat is far less than the combined thread from 1 and 2. Furthermore, 1 wil first shoot 4 instead of 3 with high probability of success, increasing 3's chance of survival even more.

But if the probabilities are something like p1=0.1, p2=0.12, p3=0.9, p4=0.99, then it is best for 3 to shoot 4 first in case of four people. So given arbitary order, the first shooter doesnt' have a dominant strategy.

I don't know if when the order is (1,2,3,...,n), "shoot the most accurate person" is still 1's dominant strategy when n>4, although it is true that more and more people will behave "unexpectedly" in the sense that they violate the "shoot the most accurate person" rule to maximize their chances of survival. I guess the dynamics will turn out to be really messy ? Is there a more clear way to look at this?

One of my friends tells me this illuminating idea: whenever it comes to someone to shoot, he cast the remaining shooters in 2 sets: set A contains all shooters who are more accurate than him; set B contains all shooters who are less accurate than him. He then sum up all the probabilities in A and B respectively. He shoots the most accurate person in set A or B iff its sum is the larger one.

It's a guess. He cannot tell why. But this it conforms to the n=4 example in #2 and #3. Does anybody have any thoughts on this?