3
$\begingroup$

Players #1 to #10 with hit probabilities $0.1,0.2,...,0.9,1$ (which are common knowledge) take part in a shooting game.

Rules of the game: Players from #1 to #10 take turns to fire at each other. After round one, survivors repeat the circle (still in the order of #1 to #10). The game lasts many rounds until only one player survives. Players are rational and each calculates to maximize his survival probability.

Question: What is each player's optimal choice of target in his turn, when all 10 players are alive? And what are their respective survival probabilities? (Technically, I'm looking for a pure strategy subgame perfect Nash equilibrium, where the players follow deterministic strategies. Barring the very unlikely circumstance of ties, in which firing at one or the other player yields the same survival probability for the shooter, such an equilibrium is unique.)


My problem is I don't know how to write a tractable program to solve it. Let's consider 4 players with probabilities $(p_1,p_2,p_3,p_4)$. In this case, my reasoning is that the problem is solved by the following equations:

$s_{i1}^4 = p_1*$(i's survival probability after 1 hits his target) $+ (1-p_1) * s_{i2}^4$

$s_{i2}^4 = p_2*$(i's survival probability after 2 hits his target) $+ (1-p_2) * s_{i3}^4$

$s_{i3}^4 = p_3*$(i's survival probability after 3 hits his target) $+ (1-p_3) * s_{i4}^4$

$s_{i4}^4 = p_4*$(i's survival probability after 4 hits his target) $+ (1-p_4) * s_{i1}^4$

for $i=1,2,3,4$, where $s_{ij}^4$ denotes i's survival probability when it's j's turn to fire, with 4 player alive. Notice that after a play hits his target, there's only 3 players left. So if we already know the 3 players case, the above equations can be solved. But I have no idea how to define a suitable structure and sub-programs to implement these thought... or maybe this is not the best way to look at the problem?

$\endgroup$
4
$\begingroup$

Robert Israel's answer on Math Overflow provides the key insight:

  • If $S$ is the set of players remaining alive and it is player $j$'s turn, player $j$ should shoot at the player $k$ such that, if $k$ dies, the remaining set gives $j$ the best survival chances.

This enables us to build a dynamic programming algorithm, as Robert Israel states. I'll explain in a bit more detail how that works.

Represent a configuration of the game by $(S,j)$, where $S$ is the set of players remaining alive and $j$ is the player whose turn it is to shoot next. Define $f_i(S,j)$ to be $i$'s probability of survival, under the equilibrium strategy for all (under optimal play), in configuration $(S,j)$. Then the insight above means that in configuration $(S,j)$, player $j$ should shoot at the player $k$ such that $f_j(S\setminus\{k\},j+1)$ is as large as possible.

(As a conventional notation, when I write $(S,j+1)$, you should interpret $j+1$ as the next person to shoot after $j$, given that players $S$ are alive.)

Based on this, we can write recursive equations for $f$:

$$f_i(S,j) = p_j \cdot f_i(S \setminus \{g(S,j)\}, j+1) + (1-p_j) \cdot f_i(S,j+1)$$

where

$$g(S,j) = \arg \max_k p_j(S \setminus \{k\}, j+1).$$

We'll start by calculating the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=1$. Then, we'll calculate the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=2$. Then, we'll calculate the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=3$.

At the $k$th stage, to calculate the $f$-values, we solve a system of linear equations in $k^2 \times {n \choose k}$ unknowns. (The unknowns are the terms $f_i(S,j)$ where $|S|=k$ and $i,j \in S$. Note that at this point $f_i(S \setminus \{\text{anything}\},j$ is known, since the first argument to $f$ will be a set of size $k-1$, which we've already calculated in the previous stage.) In your problem, $n=10$, so the $k$th stage involves solving a system of linear equations in $k^2 \times {10 \choose k}$ unknowns. This has a maximum at $k=6$, where we have 7560 unknowns. The system of linear equations can be solved using Gaussian elimination, which takes cubic time. In particular, Gaussian elimination on a $7560 \times 7560$ matrix is entirely feasible on a computer (probably it will take at most seconds).

Therefore, this should provide an efficient algorithm to compute the survival probabilities and strategy you are looking for.

$\endgroup$
  • $\begingroup$ Thank you. This is essentially my equations for the 4 players case, but in a more compact and detailed form. I knew this part. What I have trouble with is how to convert these into code lines. For example, the subscript $i$ of $f_i$ depends on the set $S$, etc.. $\endgroup$ – Eric Mar 5 '17 at 6:55
  • $\begingroup$ @Eric, $i$ doesn't depend on $S$. For each triple $(i,S,j)$ where $S \subseteq \{1,2,\dots,10\}$, $|S|=k$, $i \in S$, and $j \in S$, you have one unknown. You build up a system of linear equations in those unknowns, then you solve it (probably by constructing a matrix in memory, then invoking a library to invert it or solve the linear system). This is a bit more specific than what you had in your question, because it specifies how to calculate who each player's target is at each stage of the game. $\endgroup$ – D.W. Mar 5 '17 at 11:36

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.