The Dodgeball duel

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]

14 thoughts on “The Dodgeball duel”

  1. 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)

    1. 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!

  2. 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

    1. 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.

  3. 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.

  4. 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?

    1. 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.

      1. 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!

  5. 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

    1. 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.

      1. 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

Leave a Reply to Jason Weisman Cancel reply

Your email address will not be published. Required fields are marked *