Probability of survival using optimal strategy

Question

Three archers, $A$, $B$, and $C$, are standing equidistant from each other, forming an equilateral triangle. Archer $A$, $B$, and $C$ have $\dfrac13$, $\dfrac23$, and $\dfrac33$ probability of hitting the target they aimed, respectively.

The three archers will play a survival game. The objective of the game for all players is to kill the other two archers and be the only survivor. The order of shooting will be in alphabetical order ($A$, $B$, then $C$).

Assuming that an archer will die if he is hit by an arrow aimed at him and that all archers will make the best moves possible to maximize their chances of winning (surviving), what is the probability that archer $A$ will survive and win?

Details and Assumptions:

The archers are allowed to skip their turn if they want to. If so, there is a $0$ probability chance of hitting any target.

I've been trying different possibilities and yet can't seem to reach a conclusion. I can think of cases where $A$ might survive. For example, $A$ might succeed in killing $C$ first (so as to maximize his chances of survival); $B$ might fail in his attempt to kill $A$ and consequently, $A$ might as well succeed in killing $B$ before he himself is killed.

I understand that the optimal strategy for both $A$ and $B$ will be to kill $C$ first.

How am I supposed to formulate the entire game in terms of probabilities with a number of possibilities?

Please help me devise the optimal strategy for $A$. Thanks a lot!

Answer 1

Let's start out by considering two-player games. Suppose we have two players X and Y, whose probabilities of hitting on a given shot are $x$ and $y$ respectively, both greater than zero.

For this two-player game, let $p$ denote "the probability that player X will eventually win, given that it is currently his turn" and let $q$ denote "the probability that X will eventually win, given that it is currently Y's turn". (In both cases, assuming that all players are playing optimally to maximise their chance of winning.)

On X's turn, he has two options:

• Shoot at Y, with probability $x$ of hitting (in which case he automatically wins) and $1-x$ of missing (in which case it becomes Y's turn).
• Pass, and let Y take a turn.

If X shoots, his probability of winning is $x + (1-x)q$. (Probability $x$ of winning on this shot, plus probability that the turn passes to Y, but X eventually wins.)

If X passes, his probability of winning is $q$.

On Y's turn, he has the options of shooting at X (win probability: $y + (1-y)(1-p)$) or passing (win probability: $1-p$).

Hence, on his turn Y can achieve a win probability of at least $y$ by shooting at X. Hence, $q <= (1-y) < 1$.

It follows that $x > qx$ and hence $x + (1-x)q > q$. Therefore, in the two-player game, X should always shoot at Y rather than passing, and by a symmetrical argument Y should always shoot at X rather than passing. (Not a very surprising finding!)

Since shooting is always the optimal strategy for the two-player games, we know:

$p = x + (1-x)q$

$q = 1 - (y + (1-y)(1-p)) = p(1-y)$

Solving these simultaneously gives:

$p = x/(x+y-xy)$ $q = x(1-y)/(x+y-xy)$

We can apply this formula to each of the possible two-player scenarios:

• If A and B are playing, A's probability of victory works out to 3/7 if it's his shot next, and 1/7 otherwise.
• If A and C are playing, A's probability of victory is 1/3 if it's his shot next, and 0 otherwise.
• If B and C are playing, B's probability of victory is 2/3 if it's his shot next, and 0 otherwise.

For three-player games, you can apply a similar approach: for each possible scenario (A to shoot, B to shoot, C to shoot) and for each possible choice (shoot at next player, shoot at previous player, pass) you can specify the ultimate probability of victory as functions of the probabilities for other scenarios.

In the general case, finding optimal strategies can get very messy, because of circular dependencies between these probabilities. In some cases, you might even end up with deadlock. For example, if every player has a 99% chance of hitting, then you end up with a Mexican standoff where each player's optimal strategy is to pass until somebody else shoots first; in that scenario there is no well-defined probability of victory because the game goes on forever.

However, for this particular scenario there is an optimal strategy for each player. We can find it as follows:

Start by considering the case where both A and B have missed or passed, and C gets a turn. C has three options:

• Shoot A, reducing the problem to the two-player BC game with B next to shoot. We already know that C's chance of winning from here is 1/3.
• Shoot B, reducing the problem to the two-player AC game with A next to shoot. We already know that C's chance of winning from here is 2/3.
• Pass. Chance of winning: not yet known, depends on who the other players target.

From this, we know that if it gets to C's turn, then he has a strategy that gives at least a 2/3 probability of winning. Hence, if C gets a turn, the other players have no more than a 1/3 probability of winning. We also know that shooting at A is not his best option while B is in the game.

Now rewind to the case where A has passed or missed, and it's B's turn. One possible strategy B could follow is: "shoot at C until C is down, and then shoot at A".

If he follows this strategy, he has a 2/3 chance of hitting C on his next/first attempt; if he does hit, then we know he has a 4/7 chance of winning the ensuing "A vs B, A shoots first" game. Multiplying these gives at least an 8/21 chance of victory from this strategy. (Possibly more, because we haven't looked at cases where B misses C on his first attempt and ends up winning anyway.)

If B does not shoot at C, then C definitely gets a turn, and we know that this gives B no more than a 1/3 chance of winning. 1/3 is less than 8/21, so B's optimal strategy must be to shoot at C (and then A, once C is out of the picture).

So we know that as long as all three are in the game, B will be shooting at C, and C will either pass or shoot at B. At this point, nobody is shooting at A.

Now, let's consider A's options during the three-player phase of the game:

• Pass, until one of the other players is eliminated. When that happens, it will be A's turn. A's probability of victory will be either 1/3 (if C remains) or 3/7 (if B remains).
• Shoot at B. If A misses (2/3 chance), the consequences are the same as for passing, but if A does take out B (1/3 chance), then A will automatically lose as it's C's turn next. So this is clearly worse than passing.
• Shoot at C. If A misses (2/3 chance), the consequences are the same as for passing. If B does take out C (1/3 chance), then we go to the "A vs. B" game with B's turn next. We know that A's chances of victory from there are only 1/7, which is worse than either of the possibilities from passing. So this option is also worse than passing.

Hence, A's best option is to keep passing until one of the other players is eliminated. It then follows that C's optimal strategy is to target B first (because we already know targeting A is suboptimal, and if A and C both pass, B is just going to keep on shooting at C until he hits, which would give C no chance to win).

Hence, the possible outcomes with everybody playing optimally are:

A passes, B hits C (2/3 chance), A then has 3/7 chance of defeating B.

A passes, B misses C (1/3 chance), C hits B, A then has 1/3 chance of defeating C.

A's total chance of victory is 2/3 * 3/7 + 1/3 * 1/3 = 25/63.

Answer 2

For each round there is only one optimal stragety for each player.

1. When the 'game' starts, A shouldn't try to kill B, because if he succeeds, by 100% he will be killed by C. Also, A shouldn't try to kill C. If he succeeds, by $\dfrac{2}{3} $ he will be killd by B. If he does nothing, he is safe for the first round. B must try to kill C, else certainly C will try kill B. C has not any reason to kill A first either, since B is twice as likely to kill him. So, in the first round, A has a 100% chance of survival.

2. In the second round, A has $\dfrac{1}{3} $ probability to kill the winner of the first round and thus, to win the game. So, in general, A has at least $\dfrac{1}{3} $ probability to be the winner. If C is the winner of the first round, $\dfrac{1}{3} $ is all the chance A will have. The total probability for this to hapen is $\dfrac{1}{3}\cdot\dfrac{1}{3}=\dfrac{1}{9} $. For C to kill A, he must first survive from the first round $(\dfrac{1}{3} )$ and then he must survive from A in the second round $(\dfrac{2}{3} )$. But then he will certainly kill A. So, the total probability for this is $\dfrac{1}{3}\cdot\dfrac{2}{3}=\dfrac{2}{9} $. Whith simmilar reasoning, the total probability for A to kill B in the second round is $\dfrac{2}{3}\cdot\dfrac{1}{3}=\dfrac{2}{9} $. For B to kill A: He must kill C $(\dfrac{2}{3} )$, then, he must survive from A $(\dfrac{2}{3} )$, then he must kill A $(\dfrac{2}{3} )$. Thus the probability is $\dfrac{2}{3}\cdot\dfrac{2}{3}\cdot\dfrac{2}{3}=\dfrac{8}{27} $. Now, there is also a chance that nobody get killed in the second round: C is dead in round 1 $(\dfrac{2}{3} )$, A fails to kill B $(\dfrac{2}{3} )$ and B fails to kill A $(\dfrac{1}{3} )$. This gives: $\dfrac{2}{3}\cdot\dfrac{2}{3}\cdot\dfrac{1}{3}=\dfrac{4}{27} $. If we are correct, adding up all probabilities in each round should give 1. Indeed, $\dfrac{2}{9}+\dfrac{1}{9}+\dfrac{8}{27}+\dfrac{2}{9}+\dfrac{4}{27}=1 $.

3. We will examine two cases: Case (a) is the probability for someone to die exactly at round 3. Case (b) is the probability for someone to die either in round 1, or in round 2 or in round 3.

   (a) If there is going to be a third round, then C is dead in the first round and nobody died in the second. So now, since we omit the cases were somebody dies, the total propabilities must sum up to $\dfrac{4}{27} $. It's A's turn, and he will try to kill B. Total probability: $\dfrac{4}{27}\cdot\dfrac{1}{3}=\dfrac{4}{81} $. B kills A: $\dfrac{4}{27}\cdot\dfrac{2}{3}\cdot\dfrac{2}{3}=\dfrac{16}{243} $. Nobody dies: $\dfrac{4}{27}\cdot\dfrac{2}{3}\cdot\dfrac{1}{3}=\dfrac{8}{243} $.

   (b) There is a probability $\dfrac{2}{9} $ for A to kill B in round 2. If this does not happen, there is additional probability $\dfrac{4}{81} $ for A to kill B in round 3. Thus, there is total probability $\dfrac{2}{9}+\dfrac{4}{81}=\dfrac{22}{81} $ for A to kill B either in round 2 or in round 3. For a to kill C, there isn' t any additional probability in round 3, so it remains $\dfrac{1}{9} $. For B to kill A, we have $\dfrac{8}{27} $ in round 2 and additional

To put the numbers in a table, "$\frac{X}{Y}$" will mean "X kills Y". "$\textrm{Ø}$" means "nobody" and n is the number of the round.

\begin{array}{|c|c|c|c|c|c|c|c|} \hline n & \frac{A}{B} & \frac{A}{C} & \frac{B}{A} & \frac{B}{C} & \frac{C}{A} & \frac{C}{B} & \frac{\textrm{Ø}}{\textrm{Ø}} \\ \hline 1 & 0 & 0 & 0 & \frac{2}{3} & 0 & \frac{1}{3} & 0 \\ \hline 2a & \frac{2}{9} & \frac{1}{9} & \frac{8}{27} & 0 & \frac{2}{9} & 0 & \frac{4}{27} \\ \hline 2b & \frac{2}{9} & \frac{1}{9} & \frac{8}{27} & \frac{2}{3} & \frac{2}{9} & \frac{1}{3} & \frac{4}{27} \\ \hline 3a & \frac{4}{81} & 0 & \frac{16}{243} & 0 & 0 & 0 & \frac{8}{243} \\ \hline 3b & \frac{22}{81} & \frac{1}{9} & \frac{88}{243} & 0 & \frac{2}{9} & 0 & \frac{8}{243} \\ \hline 3c & \frac{22}{81} & \frac{1}{9} & \frac{88}{243} & \frac{2}{3} & \frac{2}{9} & \frac{1}{3} & \frac{8}{243} \\ \hline \end{array}

Row 2a - if we ignore last column - shows the probabilities for each archer to kill each other in the second round alone. The sum is allomost 1, because most probably one person will die, minus $\dfrac{4}{27} $ for the case that nobody dies in this round (last column). If we add the later to the sum, we get exactly 1. Row 2b shows the probabilities for each archer to kill each other, for either the first or the second round. Now, because most probably two persons will die, the sum will be almost 2. Think of it: if two archers would die with 100% probability each, adding their probabilities would give as 2. Row 3a gives the probabilities for each archer to kill each other in the third round alone. This, plus the probability for the case that nobody dies, will add up to $\dfrac{4}{27} $ - the probabiliy for a third round. Row 3b shows the probabilities for each archer to kill each other, for either the third or the second round. Together with the chance that nobody dies, it gives 1 (for only 1 person will die). Row 3c shows the probabilities for each archer to kill each other, for either the third or the second or the first round. Now again, we get a sum almost =2 (minus $\frac{8}{243} $).

Now, lets calculate the probability for surviving for each of the first three rounds and for each archer.

Round 1:

1. A will certainly survive the first round: 1.

2. In order for B to survive the first round, he must kill C: $\dfrac{2}{3} $

3. In order for C to survive the first round, he must kill B: $\dfrac{1}{3} $

Round 2:

1. In order for A to survive the second round, either he must kill B, or he must kill C, or both A and B survive. That is: $\dfrac{2}{9}+\dfrac{1}{9}+\dfrac{4}{27}=\dfrac{13}{27} $.

2. In order for B to survive the second round, either he must kill A, (that means C is already dead), or both A and B survived. That is: $\dfrac{8}{27}+\dfrac{4}{27}=\dfrac{12}{27} $.

3. The possibility that C survives is the same as C killing A: $\dfrac{2}{9} $.

These three eventualities are not independet. More specifically, the possibility that A survives intersects the possibillity that B survives, at the possibility that both survived. So, we can not add their corresponding probabilities, otherwise, we will count the probabillity that they both survive twice. But we can see we are in the right route: $\left(\dfrac{13}{27}+\dfrac{12}{27}-\dfrac{4}{27}\right)+\dfrac{2}{9}=1 $.

Round 3:

1. The probability for A to survive, counting up to the third round, is: $\dfrac{22}{81}+\dfrac{1}{9}+\dfrac{8}{243}=\dfrac{101}{243} $.

2. The probability for B to survive, counting up to the third round, is: $\dfrac{88}{243}+\dfrac{8}{243}=\dfrac{96}{243} $.

3. The probability for c to survive, counting up to the third round, is: $\dfrac{2}{9}=\dfrac{54}{243} $.

Again, case 1 intersects case 2. Check: $\left(\dfrac{101}{243}+\dfrac{96}{243}-\dfrac{8}{243}\right)+\dfrac{54}{243}=1 $.

\begin{array}{|c|c|c|c|} \hline n & A & B & C \\ \hline 1 & 1 & \frac{2}{3} & \frac{1}{3} \\ \hline 2 & \frac{13}{27} & \frac{12}{27} & \frac{2}{9}\\ \hline 3 & \frac{101}{243} & \frac{96}{243} & \frac{2}{9}\\ \hline \end{array}

Now we are ready to find the general term for the total probability $P_{A}(n) $ for A to survive, counting n rounds, for $n>1$. This is the probability that A won the game in a previus round, $W_{A}(n-1) $, plus the probability that A kills B at round n, $P_{\frac{A}{B}}(n) $, plus the probability that they both survive the round, $P_{\textrm{Ø}}(n) $. Thus, we get:

$$P_{A}(n)=W_{A}(n-1)+P_{\frac{A}{B}}(n)+P_{\textrm{Ø}}(n) $$

A will win round n only if he kills B, so: $W_{A}(n)=W_{A}(n-1)+P_{\frac{A}{B}}(n) $. We know that $W_{A}(1)=0 $ and $W_{A}(2)=\dfrac{2}{9}+\dfrac{1}{9}=\dfrac{1}{3} $. Therefore: $W_{A}(n)=\dfrac{1}{3}+\begin{array}{c} n\\ \sum\\ k=3 \end{array}P_{\frac{A}{B}}(k) $. This gives:

$$P_{A}(n)=\dfrac{1}{3}+\begin{array}{c} n\\ \sum\\ k=3 \end{array}P_{\frac{A}{B}}(k)+P_{\textrm{Ø}}(n) $$

Each time A throws an arrow, he has $\dfrac{1}{3} $ probability to hit the target. So, $P_{\frac{A}{B}}(n) $ is $\dfrac{1}{3} $ times the probability of round n to occur. The later is $P_{\textrm{Ø}}(n-1) $, because round n will occur, only if nobody died in round n-1 (for n>2). So we get:

$$P_{A}(n)=\dfrac{1}{3}+\dfrac{1}{3}\begin{array}{c} n\\ \sum\\ k=3 \end{array}P_{\textrm{Ø}}(k-1)+P_{\textrm{Ø}}(n) $$

$P_{\textrm{Ø}}(1)=0 $, $P_{\textrm{Ø}}(2)=\dfrac{4}{27} $ and $P_{\textrm{Ø}}(n) $ is the probability that A failed to kill B $(\dfrac{2}{3} )$, times the probability that B failed to kill A $(\dfrac{1}{3} )$, times the probability of round n to occur: $P_{\textrm{Ø}}(n)=\dfrac{2}{9}P_{\textrm{Ø}}(n-1) $. Thus, for $n>1$:

$P_{\textrm{Ø}}(n)=P_{\textrm{Ø}}(2)\begin{array}{c} n\\ \prod\\ k=3 \end{array}\dfrac{2}{9}=\dfrac{4}{27}\left(\dfrac{2}{9}\right)^{n-2} $ or, since $\dfrac{4}{27}=\dfrac{2}{9}\cdot\dfrac{2}{3} $,

$$P_{\textrm{Ø}}(n)=\dfrac{2}{3}\left(\dfrac{2}{9}\right){}^{n-1} $$

(REMEMBER: THIS DOES NOT WORK FOR n=1)

Thus: $P_{A}(n)=\dfrac{1}{3}+\dfrac{1}{3}\begin{array}{c} n\\ \sum\\ k=3 \end{array}\dfrac{2}{3}\left(\dfrac{2}{9}\right)^{k-2}+P_{\textrm{Ø}}(n)\Rightarrow $

$P_{A}(n)=\dfrac{1}{3}+\dfrac{2}{9}\begin{array}{c} n\\ \sum\\ k=3 \end{array}\left(\dfrac{2}{9}\right)^{k-2}+P_{\textrm{Ø}}(n)\Rightarrow $

$P_{A}(n)=\dfrac{1}{3}+\dfrac{9}{2}\begin{array}{c} n\\ \sum\\ k=3 \end{array}\left(\dfrac{2}{9}\right)^{k}+P_{\textrm{Ø}}(n)\Rightarrow $

$P_{A}(n)=\dfrac{9}{2}\begin{array}{c} n\\ \sum\\ k=0 \end{array}\left(\dfrac{2}{9}\right)^{k}-\dfrac{97}{18}+P_{\textrm{Ø}}(n) $

(This dosen't work for n=1 either. But if we put $P_{\textrm{Ø}}(1)=\dfrac{2}{3}\left(\dfrac{2}{9}\right){}^{1-1} $ , two mistakes cancel each other, and it works!).

To calculate the total probability for A to win, in all possible rounds, we take the limit towards infinity.

$W_{A}(\infty)=\underset{n\rightarrow\infty}{\lim}P_{A}(n) $ and since $\underset{n\rightarrow\infty}{\lim}P_{\textrm{Ø}}(n)=0 $:

$W_{A}(\infty)=\underset{n\rightarrow\infty}{\lim}\left[\dfrac{9}{2}\begin{array}{c} n\\ \sum\\ k=0 \end{array}\left(\dfrac{2}{9}\right)^{k}-\dfrac{97}{18}\right]\Rightarrow $

$W_{A}(\infty)=\dfrac{9}{2}\begin{array}{c} \infty\\ \sum\\ k=0 \end{array}\left(\dfrac{2}{9}\right)^{k}-\dfrac{97}{18}\Rightarrow$

$W_{A}(\infty)=\dfrac{9}{2}\cdot\dfrac{1}{1-\frac{2}{9}}-\dfrac{97}{18}\Rightarrow$

$$W_{A}(\infty)=\dfrac{25}{63}$$