# Truel extended to n persons

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.

-
I had to edit the problem several times because I have to avoid using "<" after "0", or there will be errors with the display. Sorry for that. I don't know what's wrong. Please take a look at the problem again. – user16033 Aug 3 '11 at 17:30
< is interpreted as a start of an HTML element by the system. There are two ways how to avoid problems with it: (1) Leave a blank space after each < . This tells markdown it's not a tag, and the extra space is ignored inside TeX math. (2) Put backticks around the whole math expression (including the dollars) which contains the < . – Emil Jeřábek Aug 3 '11 at 17:41
@Emil and unknown: alternatively, you should be able to use "\lt" instead of <. – Thierry Zell Aug 3 '11 at 19:44
@Thierry: That will just make it look messier. A cleaner markdown usage makes for easier edits later on. – Rodrigo A. Pérez Dec 15 '12 at 5:37

Consider a scenario with firing order $(1,2,\ldots,n)$ where players 1 to $n-3$ have hit probabilities so close to 0 that their only real purpose is to allow the top 3 players to waste shots, while players n-2 to n have hit probabilities very close to 1. Clearly player $n$ will be the target whenever player $n-2$ or $n-1$ makes a non-wasted shot, so his best chance at survival will always be to shoot player $n-1$ and hope that player $n-2$ misses. Therefore player $n-1$ will always shoot player $n$ and hope that player $n-2$ misses. On the other hand, whenever players $n-1$ and $n$ and some of $1$ to $n-3$ are still alive, player $n-2$ would be foolish to shoot player $n$ or $n-1$ (becoming the target for the next shot): instead he shoots a low-ranking player (presumably number $n-3$ if available), and next will get to shoot at the survivor of players $n-1$ and $n$.
I tried the case $n=10$ with hitting probabilities $1/20, 3/20, \ldots, 19/20$. If my programming is correct, there are very many cases where the optimal strategy does not say to shoot at the most accurate person alive. For example, when all are still alive players 1 to 10 should target players 8, 7, 5, 2, 9, 8, 3, 5, 5, 9 respectively. – Robert Israel Aug 4 '11 at 21:49
You have to consider the survival probabilities (under optimal play) of each player given the set of initial players and whose turn it is. So if there are initially $n$ players, there are $\sum_{j=1}^n j {n \choose j} = n 2^{n-1}$ scenarios (set of players + whose turn). Not bad at all if $n = 10$, but $n=30$ would be challenging. – Robert Israel Dec 17 '15 at 22:30