Truel extended to n persons - MathOverflow

Truel extended to n persons

2011-08-03T16:51:59Z

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.

Answer by Robert Israel for Truel extended to n persons

2011-08-04T00:17:16Z

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.

Answer by Robert Israel for Truel extended to n persons

2011-08-04T16:19:04Z

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$.