This is a game theory problem from the Riddler. Three dodgeball players, who survives?

Three expert dodgeballers engage in a duel — er, a “truel” — where they all pick up a ball simultaneously and attempt to hit one of the others. Any survivors then immediately start over, attempting to hit each other again. They are equally fast but unequally accurate. Name them Abbott, Bob and Costello. Each has an accuracy of a, b and c, respectively. That is, if Abbott aims at something, he hits it with probability a, Bob with probability b and Costello with probability c. The abilities of each player are known by the others. Let’s say Abbott is a perfect shot: a = 1. Suppose the players follow an optimal strategy, with the goal being survival. Which player, for every possible combination of Bob and Costello’s abilities (b and c), is favored to survive this truel?

Here is my solution:

[Show Solution]

Before I begin, I’d like to thank commenters Guy Moore and Jason Weisman for sharing their own solutions and for pointing out a different way of interpreting the problem. The “Random-ball” variant is due to Guy Moore. Ok, here we go…

### What is a solution, anyway?

The problem talks about “optimal strategies”, so it’s worth discussing what this means so we’re all on the same page. An optimal strategy is a Nash equilibrium. It’s a set of strategies for each player such that if any one player changed their strategy (while the others held their strategies fixed), it would result in a worse outcome for that player. Hence, no player has any incentive to change their strategy.

A *strategy* is a rule that tells you what to do based on what you observe. In this game, an example of a strategy would be “always aim to hit the remaining player with the best accuracy”. This is an example of a *pure* strategy because each player always behaves the same way no matter what they observe. Not every game is guaranteed to have a Nash equilibrium consisting of pure strategies. In some games, such as rock-paper-scissors, it’s optimal to use a mixed strategy. That is, a probabilistic strategy such as “pick rock paper or scissors randomly and with equal probability”. If you used a pure strategy in rock-paper-scissors, your opponents would counter you and you would lose every time!

It turns out that every finite game has at least one mixed Nash equilibrium. So we need not worry about the case where there is no optimal solution. That being said, it’s entirely possible for there to exist many Nash equilibria! So we shouldn’t be surprised if this turns out to be the case…

### Murder-ball vs Coinflip-ball vs Random-ball

There are at least three ways of interpreting the problem. In the first interpretation, if two players target each other and hit, then both players are eliminated. I’ll call this variant “Murder-ball”. In Murder-ball, it’s possible for nobody to win! The second interpretation is that whenever two players hit each other, we should flip a coin and the loser of the coin flip gets eliminated. We also flip a 3-way coin to deal with the case where all three players would be simultaneously eliminated. I’ll call this “Coinflip-ball”. Finally, we could interpret the game as having a randomly chosen shooting order for the players. I’ll call this variant “Random-ball”. In Random-ball, if A hits B and B hits C, but the order is such that A shoots first, then B gets eliminated before shooting C and C survives. All these variants have different solutions!

### Two players

Let’s start by considering the case with only two players $P$ and $Q$; a duel! In this case, there are no decisions to make. The players always target each other. Suppose the two players have probabilities of $p$ and $q$ to hit each other, respectively, and we want to figure out the probability that either player will win the duel. In Murder-ball, Player $P$ can only win if he hits $Q$ and $Q$ misses $P$. The probability of this occurring is $p(1-q)$. But if both players miss (probability $(1-p)(1-q)$) then the game repeats. So the chance that $P$ is the ultimate winner is:

\begin{align}

\mathbb{P}_P &= p(1-q)\biggl(1+(1-p)(1-q)+(1-p)^2(1-q)^2+\cdots\biggr) \\

&= \frac{p(1-q)}{1-(1-p)(1-q)}

\end{align}Repeating a similar argument for the other player, we find the probabilities of interest are:

\begin{gather}

\mathbb{P}_P = \frac{p(1-q)}{1-(1-p)(1-q)},

\qquad

\mathbb{P}_Q = \frac{(1-p)q}{1-(1-p)(1-q)}, \\

\qquad

\mathbb{P}_0 = \frac{pq}{1-(1-p)(1-q)}.

\end{gather}Here, $\mathbb{P}_0$ is the probability that the two players simultaneously hit each other, so nobody wins. Naturally, the three probabilities above sum to $1$.

In Coinflip-ball and Random-ball, Player $P$ can also win if both players hit each other but he wins the coin flip. It turns out that in this case, it’s impossible for *nobody* to win, and $\mathbb{P}_0$ from the solution above gets split evenly between both players.

### Three players

I will solve the Murder-ball case in detail. With three players, each has a choice of who to target. We will make no assumptions about the nature of the strategies used, and we will allow for the possibility of using a mixed strategy. An example of a mixed strategy would be “Player $A$ should target $B$ with probability $0.4$ and $C$ with probability $0.6$”. In some games, such as rock-paper-scissors, it’s optimal to use a mixed strategy because if you always did the same thing, your opponents would realize this and you would lose every time! So, let’s define the numbers $x,y,z$ as follows:

\begin{align}

&A\text{ targets }B\text{ with prob }x\text{ and targets }C\text{ with prob }(1-x)\\

&B\text{ targets }C\text{ with prob }y\text{ and targets }A\text{ with prob }(1-y)\\

&C\text{ targets }A\text{ with prob }z\text{ and targets }B\text{ with prob }(1-z)

\end{align}We can compute the probabilities that any player will win by enumerating the possible ways it can happen. I’ll give one example to illustrate. To compute the probability that $A$ wins, it can happen in two main ways:

- $B$ and $C$ are eliminated simultaneously and $A$ survives. This can happen in three ways. Either $B$ and $C$ hit each other, or $B$ hits $C$ and $A$ hits $B$, or $C$ hits $B$ and $A$ hits $C$. We can also have everybody survive for some number of rounds first! The total probability is:

\[

\frac{a b (1-c) x y + a (1-b) c (1-x) (1-z) + b c y (1-z)}{1-(1-a)(1-b)(1-c)}

\] - $B$ is eliminated first, and then $A$ wins the duel with $C$ (a case we already solved with $p$ and $q$ above). In any case, $B$ must miss his shot. Either $A$ and $C$ both target $B$ and at least one of them hits, or only one of them targets $B$ and the other misses. The total probability in this case is:

\[

\frac{a(1-c)}{1-(1-a)(1-c)} \frac{(1-b)\left(a (1-c) x + (1-a) c (1-z) + a c x (1-z)\right)}{1-(1-a)(1-b)(1-c)}

\] - $C$ is eliminated first, and then $A$ wins the duel with $B$. This case is similar to the previous one and the total probability is:

\[

\frac{a(1-b)}{1-(1-a)(1-b)} \frac{(1-c)\left(a (1-b) (1-x) + (1-a) b y + a b (1-x) y\right)}{1-(1-a)(1-b)(1-c)}

\]

Summing the three probabilities above, we get $\mathbb{P}_A$, the probability that $A$ wins. We can do a similar computation to get the probability that $B$ wins, that $C$ wins, and that nobody wins (all four probabilities will sum to $1$). By symmetry, the formula for $\mathbb{P}_B$ can be obtained by just cyclically permuting all variables: $a\to b\to c \to a$ and $x \to y \to z \to x$. Finally, the probability that nobody wins is such that all four probabilities sum to one: $\mathbb{P}_0 =1-\mathbb{P}_A-\mathbb{P}_B-\mathbb{P}_C$.

### Murder-ball optimal strategies

We now have the probabilities that each player wins, and these are the functions:

\[

\mathbb{P}_A(x,y,z),\quad \mathbb{P}_B(x,y,z),\quad \mathbb{P}_C(x,y,z).

\]Each function is parameterized by $a,b,c$, the accuracy of each player, and is a function of $(x,y,z)$, the (mixed) strategy being used. Our goal is to find a choice of $(x,y,z)$ such that no change in $x$ alone can improve $\mathbb{P}_A$, no change in $y$ alone can improve $\mathbb{P}_B$, and no change in $z$ alone can improve $\mathbb{P}_C$. A key observation that will help us solve the problem is that all three functions are linear in $x$, $y$, and $z$ separately. When optimizing a linear function, the maximum always occurs at a boundary. This implies that there must exist pure Nash equilibria!!! So we can restrict our search to cases where $x$, $y$, and $z$ are each $0$ or $1$. So there are 8 strategies in total.

I computed the Nash equilibria via an exhaustive search. For each value of $(a,b,c)$, I computed the values of $(\mathbb{P}_A,\mathbb{P}_B,\mathbb{P}_C)$ for all 8 strategies, tried changing $(x,y,z)$ for each one to see if it was a Nash equilibrium, and if I found multiple Nash equilibria, I chose one at random. Then, I made a plot illustrating who wins when. When $a=1$, we obtain the following picture:

What a mess! There are many Nash equilibria here, and pretty much anything can happen. The reason is that without a coinflip, the player targeted by Abbott will always lose. So, in fact, anything that player does is optimal! That losing player has a big effect on which remaining player wins, and hence the messy solutions. However, these Nash equilibria are mostly *unstable*. That is, if we change Abbott’s accuracy to $a=0.99$, the picture changes completely:

### Coinflip-ball optimal strategies

I will omit the derivations for Coinflip-ball because the algebra is quite lengthy and tedious to write out, but the idea is similar in spirit to how I derived the probabilities for the Murder-ball variant. As in the Murder-ball case, all probabilities are linear in $(x,y,z)$, so once again, pure Nash equilibria must exist. As above, I used an exhaustive search to plot the probability of winning for each player. Here is what I obtained in the case where $a=1$.

For most of the cases, the strategies are obvious. For example, when $b=0.8$ and $c=0.5$, the optimal strategy is for Abbott and Bob to target each other and for Costello to target Abbott. In this case, it turns out Costello wins most of the time! In the top right corner, you’ll notice that there is a mixture of possible outcomes because there are multiple Nash equilibria there. In that region, all three players are highly accurate and the strategy of ganging up on Abbott is no longer optimal. In this regime, it’s Nash-optimal for the three players to target each other in a chain (A to B to C to A) or (A to C to B to A). This is a result of the rules of the game. In my interpretation of Coinflip-ball, if all three players hit each other simultaneously, the outcome of the game is decided by a coin flip where each player has an equal chance to win.

### Random-ball optimal strategies

Again, I omit the derivation. This case yields a solution similar to the other two, where pure Nash equilibria always exist. However, in this case, it’s even nicer: the Nash equilibria are unique! This means there is an unambiguous best strategy for all players. Here is what I obtained in the case where $a=1$.

The uniqueness of the Nash equilibria is reflected in the fact that every region is solid; there is no overlap anywhere.

### Inaccurate Abbott

Of course, I had to see what would happen in the case where Abbott is not perfectly accurate. Prepare to have your mind blown…

Here is the case of Coinflip-ball:

You’ll notice that when $a=0$ the optimal solution is just split along the line $b=c$, where the more accurate player wins. This makes sense; Abbott will always lose no matter what he does so it’s up to the remaining two players to duke it out.

Here is the case of Murder-ball:

This time, in the case $a=0$, Bob and Costello are not threatened by Abbott so they target each other. If both Bob and Costello are very accurate, then there is a good chance that they eliminate each other, and in this case Abbott wins!

Finally, here is the case of Random-ball:

Hi Laurent,

Very interesting. However I interpreted the question somewhat differently.

In the simpler version (Riddler Express) it states that when two equally fast players compete, each has a 1/2 chance of winning — it is a coin flip who gets off the shot first, and when they hit, the other competitor dies before being able to return fire. Therefore I interpreted the problem such that the order of “shooting” is random (1/6 chance each that A shoots before B before C, and each of the other 5 permutations of the order) rather than perfectly simultaneous. In this case the optimal strategies are the same, but the outcomes are somewhat different, in particular B can win if someone gets off a shot on A before A can shoot B. In this case there is a region at large b and medium-small c where B has the best chance of winning (and someone always wins).

In particular I found the probability for A to win to be

(2-b)(2-3c+c^2)/4

and for B to win, assuming b>c, to be

b(2-c)(3b+3c-2bc)/( 12(b+c-bc) )

with the probability for C to win being 1 minus the sum of these two. This led to

https://theorie.ikp.physik.tu-darmstadt.de/qcd/wins.pdf

(pardon the very poor graphics)

Neat! I’ve given the problem more thought and, actually, I think my solution is incomplete (different interpretations notwithstanding). I’ll update my blog post tomorrow when I have a bit more time… Stay tuned!

Solution updated. I also included the case where a < 1

I interpreted the puzzle to mean that players throw simultaneously in each round. If two throw accurately at each other, then the winner is determined by a coin flip.

If player P and Q throw at each other there are four possible outcomes:

1. both throw accurately with probability pq, Pp=0.5, Pq=0.5

2. P throws accurately, Q inaccaurately with probability p(1-q), Pp=1, Pq=0

3. P throws inaccurately, Q accurately with probability (1-p)q, Pp=0, Pq=1

4. both throw inaccurately with (1-p)(1-q), Pp=P, Pq=Q (throw again)

Probability of P winning:

P=0.5pq + p(1-q) + (1-p)(1-q) P

Simplifying,

P=p(1-q/2)/(p+q-pq)

Q=q(1-p/2)/(p+q-qp)

Following similar logic as described above, B and C always target A in round 1. A will target B if b>c, C if c>b.

Assuming, without loss of generality that b>c.

In the “truel”, C wins in the first round with probability (1-b/2)c, i.e.., A beats B and C throws accurately and eliminates A.

Otherwise, if A beats B and C throws inaccurately then A throws against C in the second round. This happens with probability (1-b/2)(1-c). A wins with overall probability (1-b/2)(1-c)(1-c/2), C wins with overall probability (1-b/2)(1-c)c/2.

Finally, if in the first round B beats A with probability b/2 and throws against C in the second round. B wins with overall probability (b/2)b(1-c/2)/(b+c-bc), C wins with overall probability (b/2)c(1-b/2)/(b+c-bc).

Overall probabilities of winning for each player:

PA = (1-b/2)(1-c)(1-c/2)

PB = (1-b/2)(1-c)c/2 + (b/2)b(1-c/2)/(b+c-bc)

PC = (1-b/2)c + (1-b/2)(1-c)c/2 + (b/2)c(1-b/2)/(b+c-bc)

Graph showing who is most likely to win: https://goo.gl/BrYdbL

Google spreadsheet: https://goo.gl/LT5GCr

I updated my solution. Hope you enjoy!

Hi Jason,

I am not sure of the logic in the Truel round. I treated the “duel” the same way as you — 50/50 who shoots the other first — but by similar logic it should be possible that C shoots A before A gets off a shot against B, whereas you seem to assume A,B finish potentially shooting each other and -then- C’s bullet arrives. Hence I get somewhat different results, although the pattern is the same.

Laurent, I may be missing something but had convinced myself that there is a pure strategy solution where players B and C both target A and A targets the better thrower between B and C. Assuming b>c, call this strategy BAA.

After some algebra the probabilities of winning among the three (assuming b>c) are:

PA=(1-b/2)*(1-c)*(1-c/2)

PB=b^2/2*(1-c/2)/(b+c-b*c)

PC=(1-b/2)*c+(1-b/2)*(1-c)*c/2+(1-b/2)*b*c/2/(b+c-b*c)

To determine whether BAA is an equilibrium, each of the players looks at the whether changing could increase the winning likelihood. So A compares this with PA under strategy CAA, B compares PB under strategy BCA, C compares PC under strategy BAB.

These are:

PA (CAA) = (1-c/2)*(1-b)*(1-b/2)

PB (BCA) = 0

PC (BAB) = b/2*c+(1-b/2)*c/2+b/2*(1-c)*c*(1-b/2)/(b+c-b*c)

The first two cases are apparent that PA (BAA) > PA (CAA) and PB (BAA) > PB (BCA) and with a little algebra it can also be shown that PC (BAA) > PC (BAB).

So there does not appear to be an incentive for any of the players to diverge from the pure strategy BAA. Not clear to me how the upper right portion of your coinflip-ball solution is justified.

Ok, maybe a difference in rules interpretation. I assumed all players throw simultaneously in each round, no timing differences. So, for example, in my interpretation BCA would result in certain elimination for B (A throws at B with 100% accuracy, B throws at C, C throws at A). With these rules I believe BAA is the pure strategy solution. In your interpretation it’s possible that C eliminates A before he has a chance to throw, so B has a chance to win in this scenario?

Right, in my interpretation if the players use strategy BCA, then there is 1/6 chance each

that the actual order of throws is (A,B,C), (A,C,B), … and for those cases where C hits A before A throws, then B survives. Which means B is more likely to survive by -missing- C, making it clear that this strategy is not optimal for B.

We will have to see what interpretation the Riddler had in mind. I really enjoy these puzzles,

but I have to admit that some of the problems are written unclearly such that there are

multiple interpretations. I was really not sure how to interpret this one and I see that other

people found what I see as equally valid alternative interpretations.

I solved it using your interpretation of the game and also included an animation for this case. I think this is the best interpretation; it yields a game with unique Nash equilibria!

Laurent, thanks for updating the random-ball interpretation.

Congrats to both of you for call outs in this week’s 538 Riddler solution!

Regards,

Jason

Thanks Jason. But I still find it strange that the column showed graphics based on two different interpretations of his ambiguous question, and yet the fivethirtyeight column didn’t seem to recognize that the solutions were solving different problems!

Laurent, as usual you have done an amazing job and I really like the graphics.

Guy, agree this week’s solution to 538 Riddler was not rigorous or detailed enough. For sure Laurent’s analysis is much more complete and satisfying.

I was involved with one problem last year that I am fairly certain provided an incorrect solution. Trying to get an acknowledgement and correction resulted in a lot of frustration on my end and no response from Oliver. See below links. After that I figured best to enjoy the challenge but try not be overly critical about the shortcomings presentation.

https://twitter.com/jason_weisman/status/921369527241363456

https://twitter.com/jason_weisman/status/916330448137129984

https://twitter.com/jason_weisman/status/917153789173526529

Ah yes, that problem. I think I solved it the same way you did.

Well I guess no one is perfect….

guy