{"id":2237,"date":"2018-02-18T15:12:27","date_gmt":"2018-02-18T21:12:27","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=2237"},"modified":"2018-02-23T03:38:28","modified_gmt":"2018-02-23T09:38:28","slug":"the-dodgeball-duel","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/the-dodgeball-duel\/","title":{"rendered":"The Dodgeball duel"},"content":{"rendered":"

This is a game theory problem from the Riddler<\/a>. Three dodgeball players, who survives?<\/p>\n

\nThree expert dodgeballers engage in a duel \u2014 er, a “truel” \u2014 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\u2019s 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\u2019s abilities (b and c), is favored to survive this truel?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

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…<\/p>\n

What is a solution, anyway?<\/h3>\n

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<\/a>. 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.<\/p>\n

A strategy<\/em> 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<\/em> 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<\/a>, it’s optimal to use a mixed strategy<\/a>. 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!<\/p>\n

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…<\/p>\n

Murder-ball vs Coinflip-ball vs Random-ball<\/h3>\n

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!<\/p>\n

Two players<\/h3>\n

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:
\n\\begin{align}
\n\\mathbb{P}_P &= p(1-q)\\biggl(1+(1-p)(1-q)+(1-p)^2(1-q)^2+\\cdots\\biggr) \\\\
\n&= \\frac{p(1-q)}{1-(1-p)(1-q)}
\n\\end{align}Repeating a similar argument for the other player, we find the probabilities of interest are:
\n\\begin{gather}
\n\\mathbb{P}_P = \\frac{p(1-q)}{1-(1-p)(1-q)},
\n\\qquad
\n\\mathbb{P}_Q = \\frac{(1-p)q}{1-(1-p)(1-q)}, \\\\
\n\\qquad
\n\\mathbb{P}_0 = \\frac{pq}{1-(1-p)(1-q)}.
\n\\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$.<\/p>\n

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<\/em> to win, and $\\mathbb{P}_0$ from the solution above gets split evenly between both players.<\/p>\n

Three players<\/h3>\n

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<\/a>. 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<\/a>, 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:
\n\\begin{align}
\n&A\\text{ targets }B\\text{ with prob }x\\text{ and targets }C\\text{ with prob }(1-x)\\\\
\n&B\\text{ targets }C\\text{ with prob }y\\text{ and targets }A\\text{ with prob }(1-y)\\\\
\n&C\\text{ targets }A\\text{ with prob }z\\text{ and targets }B\\text{ with prob }(1-z)
\n\\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:<\/p>\n

    \n
  1. $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:
    \n\\[
    \n\\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)}
    \n\\]<\/p>\n
  2. $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:
    \n\\[
    \n\\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)}
    \n\\]<\/p>\n
  3. $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:
    \n\\[
    \n\\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)}
    \n\\]\n<\/ol>\n

    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$.<\/p>\n

    Murder-ball optimal strategies<\/h3>\n

    We now have the probabilities that each player wins, and these are the functions:
    \n\\[
    \n\\mathbb{P}_A(x,y,z),\\quad \\mathbb{P}_B(x,y,z),\\quad \\mathbb{P}_C(x,y,z).
    \n\\]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.<\/p>\n

    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:<\/p>\n

    \"\"<\/a><\/p>\n

    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<\/em>. That is, if we change Abbott’s accuracy to $a=0.99$, the picture changes completely:<\/p>\n

    \"\"<\/a><\/p>\n

    Coinflip-ball optimal strategies<\/h3>\n

    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$.<\/p>\n

    \"\"<\/a><\/p>\n

    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.<\/p>\n

    Random-ball optimal strategies<\/h3>\n

    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$.<\/p>\n

    \"\"<\/a><\/p>\n

    The uniqueness of the Nash equilibria is reflected in the fact that every region is solid; there is no overlap anywhere.<\/p>\n

    Inaccurate Abbott<\/h3>\n

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

    Here is the case of Coinflip-ball:<\/p>\n

    <\/a><\/p>\n

    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.<\/p>\n

    Here is the case of Murder-ball:<\/p>\n

    <\/a><\/p>\n

    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!<\/p>\n

    Finally, here is the case of Random-ball:<\/p>\n

    <\/a><\/p>\n<\/div>\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"

    This is a game theory problem from the Riddler. Three dodgeball players, who survives? Three expert dodgeballers engage in a duel \u2014 er, a “truel” \u2014 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 … Continue reading “The Dodgeball duel”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2259,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[33,8,2],"class_list":["post-2237","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-game-theory","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2237","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2237"}],"version-history":[{"count":12,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2237\/revisions"}],"predecessor-version":[{"id":2260,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2237\/revisions\/2260"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2259"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}