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.

  • $\begingroup$ 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. $\endgroup$ – user16033 Aug 3 '11 at 17:30
  • 2
    $\begingroup$ < 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 < . $\endgroup$ – Emil Jeřábek Aug 3 '11 at 17:41
  • 2
    $\begingroup$ @Emil and unknown: alternatively, you should be able to use "\lt" instead of <. $\endgroup$ – Thierry Zell Aug 3 '11 at 19:44
  • $\begingroup$ @Thierry: That will just make it look messier. A cleaner markdown usage makes for easier edits later on. $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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. $\endgroup$ – Robert Israel Aug 4 '11 at 21:49
  • $\begingroup$ @Robert: If I computed it correctly, with the same probabilities, if players are allowed to hold fire in his turn, then 1 to 10 should target: 4,5,5,2,3,H,1,1,7,8, where H means hold fire. Interestingly, anyone could be a first target, even if he's most inaccurate. $\endgroup$ – user16033 Aug 5 '11 at 3:27

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.

  • $\begingroup$ @Robert: Thanks! I agree there's always a unique pure strategy for a player. And indeed with probabilities given, we can recursively determine everyone's optimal strategy. But this doesn't answer Quesiton 2 (which i've modified): Will the naive strategy always remain most players' optimal strategy as n gets larger? Or can we predict which players will always be able to adopt the naive strategy as optimal, as n gets larger? $\endgroup$ – user16033 Aug 4 '11 at 2:16
  • $\begingroup$ @Robert: Can you tell us how you programmed it, more specificly? Whose death maximizes your probability of survive is so entangled with what all others do at each level that there're to much probabilities to specify or compute. $\endgroup$ – Eric Dec 17 '15 at 1:27
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Dec 17 '15 at 22:30
  • $\begingroup$ Nice insight! I've explained the dynamic programming algorithm in more detail at cs.stackexchange.com/a/71133/755. (Cc: @Eric) $\endgroup$ – D.W. Mar 4 '17 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.