n players numbered 1~n play a shooting game. Their accuracy rates p1~pn are strictly between 0 and 1, and strictly increases from p1 to pn. This is common knowledge.


Before the game starts, the referee arranges the n players in some order. When game starts, players take turns to fire at one another according to that order. (For example, if n=4, and the referee arranges the players in order (3,4,1,2), when game starts, 3 fires first, then 4 fires, then 1, then 2, then 3 again, so on and so forth, as long as they are alive) The last person left is the winner of the game. 


To be more specific, define $S\_{i}$={1,2,3,...,i-1,i+1,i+2,...,n}. Let $S\_{i}^{k}$ be any subset of $S\_{i}$ that contains k elements(n>k>0). Then the strategy of player i is a function that maps $S\_{i}^{k}$ to one of its element, for any $S\_{i}^{k}$. What this definition means is that, given any k players (excluding i himself) left, player i's strategy tells him whom to shoot first. Notice that we rule out the possibility that any player can hold fire in his turn: he must choose someone to shoot.


After the referee arranges the firing order, all players must announce their strategies simultaneously. A player's payoff is his winning probability. 




---


Question 1: Is there always an Nash equilibrium in this game, for any firing order? 


Question 2: Suppose firing order is (1,2,3,...,n). Which players have **fixed** optimal strategies with respect to changes in (p1,p2,...,pn)? (When n=3, all have fixed optimal strategies; when n=4, player 1,2 and 4 have fixed optimal strategies) Furthermore, these fixed optimal strategies are intuitive and simple in the sense that they always instruct the player to **fire at the most accurate person alive**. I guess there could be regularities as n gets larger? At least can we say for player 1 **this strategy** is always optimal? 




---


EDIT: "dominant strategy" in Question 2 is changed to "fixed optimal strategy with respect to changes in probabilities", which is more appropriate.



Truel extended to n persons
This is a non-cooperative game of perfect information. In the absence of degeneracy, there is always a unique optimal pure strategy for each player. Note that your probability of hitting your target doesn't depend on who the target is, and the situation if you miss also doesn't depend on who the target is. Thus your only concern is what happens if you hit your target. You shoot at the target whose death would give you the highest probability of being the survivor. These probabilities for all participants can be computed by "dynamic programming", starting with the case of only one surviving participant and working backwards.
The only complication is how ties might be broken.


