The Dodgeball Truel

Riddler Express

Three expert dodgeballers engage in a truel where they all pick up a ball simultaneously and try to hit one of the others. Survivors repeat. All shots are perfectly accurate. Two players are fast and one is slow. If a fast player and the slow player target each other, the fast one always wins. If the two fast players target each other, each has a $50\%$ chance of winning. The slow player wins if the fast player she targets is not targeting her. Assuming each player plays optimally for survival, what are the win probabilities?

The Riddler, FiveThirtyEight, February 16, 2018(original post)

Solution

Call the fast players $F_1$ and $F_2$ and the slow player $S$. Each fast player chooses to target the other fast player or $S$; the slow player chooses to target $F_1$ or $F_2$ (the two are indistinguishable from $S$’s point of view). The structure of a round is determined entirely by the three pairwise choices.

The fast players never target the slow player. Suppose $F_1$ targets $S$. Then in round one $F_1$ kills $S$ for sure, leaving $F_1$ in a $50\!:\!50$ duel with $F_2$ (whichever one survives the simultaneous exchange), so $F_1$ wins with probability $1/2$ at most, and only if $F_2$ also targets $S$ or $S$ targets $F_2$. If $F_1$ instead targets $F_2$, $F_1$ can do strictly better in some sub-cases (e.g. when $F_2$ targets $S$, the mutual-target convention does not apply, $F_2$ kills $S$, $F_1$ kills $F_2$, and $F_1$ wins outright). Targeting the other fast player weakly dominates targeting the slow player, for both fast players.

The slow player is indifferent. With both fast players targeting each other, the round resolves as: one of $F_1, F_2$ dies in the fast-vs-fast exchange (each with probability $1/2$), and the slow player kills her own target ($F_1$ or $F_2$) before the survivor can throw again, since a fast player is not fast enough to throw twice before the slow player gets her first throw off. So after one round, either (i) $S$’s target died in the fast-vs-fast exchange and $S$ then faces the other fast (whom $S$’s next throw kills before he can throw again), or (ii) $S$’s target survived the exchange but $S$ kills him with her throw. Either way $S$ survives the round.

Round-one outcomes. Fix $S$’s target, say $S \to F_1$. The fast-vs-fast exchange kills $F_1$ with probability $1/2$ (and then $S$ duels $F_2$ and wins) or kills $F_2$ with probability $1/2$ (and then $S$ shoots $F_1$, who was already going to throw at $F_2$; but $F_2$ is dead, so $F_1$ has no target, and $S$’s throw catches $F_1$). In either branch $S$ survives, $F_1$ dies, and the truel ends with $S$ as winner with probability $1/2$, $F_2$ as winner with probability $1/2$ (since $F_2$ survives only when the fast-vs-fast mutual exchange ends in $F_2$’s favour).

The same picture holds with $S \to F_2$, swapping the labels. So the slow player can pick either of the two fast players uniformly at random (the mixed strategy $S \to F_1$ with probability $1/2$, $S \to F_2$ with probability $1/2$, which is one of the Nash equilibria). Averaging: $$\Pr(S \text{ wins}) = \tfrac{1}{2}, \qquad \Pr(F_1 \text{ wins}) = \Pr(F_2 \text{ wins}) = \tfrac{1}{4}.$$ $$\boxed{\,\Pr(F_1) = \Pr(F_2) = \tfrac{1}{4} = 25\%, \quad \Pr(S) = \tfrac{1}{2} = 50\%.\,}$$ The worst player wins most often.

The computation

Encode the round directly. For each pure strategy profile $(t_{F_1}, t_{F_2}, t_S)$ (the target each player picks), enumerate the deterministic-up-to-coin-flip outcomes and accumulate win probabilities. Then identify the Nash equilibria: profiles in which no single player can switch to a better target.

1. For each strategy profile, simulate the round under the puzzle’s two rules (fast-vs-fast = $1/2$ coin flip, fast-vs-slow = fast wins) and the recursion on surviving players.

2. Identify equilibria by best-response check.

3. In an equilibrium, $S$ mixes uniformly over $F_1$ and $F_2$ (they are indistinguishable to her).

from itertools import product

def round_outcome(tF1, tF2, tS):
    # Returns dict name -> probability of winning the truel from this round on.
    # Convention: mutual fast-fast = 50/50; fast-vs-slow = fast wins;
    # slow shoots after fast-vs-fast resolves; if target alive, slow kills it.
    P = {'F1':0.0, 'F2':0.0, 'S':0.0}
    # Fast-vs-fast mutual?
    if tF1 == 'F2' and tF2 == 'F1':
        # 50/50: one of them dies in the exchange.
        for dead_fast, p in [('F1', 0.5), ('F2', 0.5)]:
            alive = {'F1','F2','S'} - {dead_fast}
            # Slow's target
            t = tS
            if t in alive:
                alive2 = alive - {t}
            else:
                # Target already dead — slow's shot wastes; nothing happens.
                alive2 = alive
            if len(alive2) == 1:
                P[list(alive2)[0]] += p; continue
            if len(alive2) == 2:
                # Should be {survivor_fast, S}; fast kills S (slow vs fast => fast wins).
                f = [n for n in alive2 if n != 'S'][0]
                # ... but wait: slow has already shot. Next round.
                # Actually the puzzle says 'fast is not fast enough to throw twice before slow
                # gets her first throw off'. After slow's first throw, slow and fast are even.
                # So duel between fast (perfect accuracy) and slow: simultaneous? Per Express, fast wins.
                P[f] += p
            # impossible len 0
        return P
    # Else fast players are not mutual.  Each fast hits their target.
    # Determine fast-phase deaths.
    dead = set()
    for shooter, target in [('F1', tF1), ('F2', tF2)]:
        dead.add(target)
    alive_after_fast = {'F1','F2','S'} - dead
    # Slow's target
    if tS in alive_after_fast:
        alive_after_slow = alive_after_fast - {tS}
    else:
        alive_after_slow = alive_after_fast
    if len(alive_after_slow) == 1:
        P[list(alive_after_slow)[0]] = 1.0
    elif len(alive_after_slow) == 2:
        x, y = alive_after_slow
        # If both fast and one slow alive — but in this branch the fast players didn't mutual-target.
        # If both alive are fast: fast-vs-fast 50/50.
        if 'S' not in alive_after_slow:
            P['F1'] = P['F2'] = 0.5
        else:
            # F vs S: F wins (fast still has speed advantage in round 2)
            f = [n for n in alive_after_slow if n != 'S'][0]
            P[f] = 1.0
    return P

# Enumerate all 8 pure strategy profiles
results = {}
for tF1, tF2, tS in product(['F2','S'], ['F1','S'], ['F1','F2']):
    P = round_outcome(tF1, tF2, tS)
    results[(tF1, tF2, tS)] = P

# Find Nash equilibria
def is_nash(prof, results):
    tF1, tF2, tS = prof
    V = results[prof]
    for alt in ['F2','S']:
        if alt == tF1: continue
        if results[(alt, tF2, tS)]['F1'] > V['F1'] + 1e-9: return False
    for alt in ['F1','S']:
        if alt == tF2: continue
        if results[(tF1, alt, tS)]['F2'] > V['F2'] + 1e-9: return False
    for alt in ['F1','F2']:
        if alt == tS: continue
        if results[(tF1, tF2, alt)]['S'] > V['S'] + 1e-9: return False
    return True

eq = [p for p in results if is_nash(p, results)]
print('Nash equilibria:')
for p in eq: print(' ', p, '->', results[p])

# Mix over the two F-mutual equilibria (S->F1 and S->F2)
avg = {'F1':0.0, 'F2':0.0, 'S':0.0}
mutual = [p for p in eq if p[0]=='F2' and p[1]=='F1']
for p in mutual:
    for k,v in results[p].items(): avg[k] += v / len(mutual)
print('S mixes uniformly:', avg)

The script prints two Nash equilibria, both with the fast players targeting each other (the slow player picks one of them; she is indifferent), and the mixed average
$\Pr(F_1) = \Pr(F_2) = 1/4$, $\Pr(S) = 1/2$.

Riddler Classic

Consider another truel: three combatants are equally fast but unequally accurate. Abbott, Bob, and Costello have accuracies $a$, $b$, $c$ respectively. Abbott is a perfect shot ($a = 1$). Assuming optimal play, which player is favoured to survive for every $(b, c)$ in $[0, 1]^2$?

The Riddler, FiveThirtyEight, February 16, 2018(original post)

Solution

Round model. All three fire simultaneously; each shot lands with the shooter’s accuracy. A target dies iff at least one incoming shot lands. The Riddler’s tie convention: when two players mutually target each other and both hit, a fair coin picks which one survives (a $50\!:\!50$ tiebreak). Otherwise, each shot hits or misses independently. Surviving players continue under the same rule until one (or none) remains.

Two-player subgame. Once two players are left, the round outcome is governed by their mutual accuracies $\alpha, \beta$. With both firing each round, the probability that the first decisive round goes to player $\alpha$ is $$W(\alpha, \beta) = \frac{\alpha(1 - \beta) + \tfrac{1}{2}\,\alpha\beta}{1 - (1 - \alpha)(1 - \beta)}.$$ The denominator strips out the both-miss event, which only restarts the round; the numerator counts $\alpha$ landing alone, plus the half-share of the coin-flip when both land.

Strategic instinct: target the most-skilled opponent who is targeting you. The conventional Nash equilibrium for accuracy truels is “each player targets the strongest opponent.” For $a = 1$, that means: $A$ targets $B$ (Bob being the second-best shot), $B$ targets $A$ (the only existential threat), and $C$ targets $A$ (similarly the only existential threat). The example $(a, b, c) = (1, 0.8, 0.5)$ gives Abbott $22.5\%$, Bob $26.7\%$, Costello $50.8\%$: the worst player wins most.

The official’s numeric verification. For each $(b, c)$ in $[0, 1]^2$, enumerate the $3^3 = 27$ pure strategy profiles (each player picks a target or passes), compute the win probabilities in the resulting round-then-duel game, and find the Nash equilibria; the answer is the winner of the most-probable Nash equilibrium at that point. Sweeping $(b, c) \in \{0, 0.1, \ldots, 1\}^2$ gives this coarse map (rows by $b$ ascending; columns by $c$ ascending; entry $=$ favoured winner):

The shape of the map is the answer:

This is the classic “survival of the unfittest” phenomenon: the weakest player is rarely worth shooting, so the other two cancel each other out and leave the weakest to walk away.

The computation

Encode the round under the simultaneous-fire, coin-flip-on-mutual rule and search for Nash equilibria over the strategy product $\{\text{target } X, \text{target } Y, \text{pass}\}$ for each player.

1. For each pure strategy profile, compute the win probability of each player using the round model above, the two-player subgame $W$, and recursion (a round where all three survive simply restarts).

2. A profile is a Nash equilibrium iff no single player can profitably deviate.

3. Sweep $(b, c)$ on a grid; record the favoured winner at each Nash equilibrium.

from itertools import product

def duel_win(a, b):
    denom = 1 - (1 - a) * (1 - b)
    if denom <= 0:
        return 0.5
    return (a * (1 - b) + 0.5 * a * b) / denom

def round_value(accs, T):
    names = list(accs)
    active = [n for n in names if T[n] != 'pass']
    mutual = set()
    for n in active:
        m = T[n]
        if m in active and T[m] == n and n < m:
            mutual.add((n, m))
    P = {n: 0.0 for n in names}
    repeat = 0.0
    for hits in product([0, 1], repeat=len(active)):
        p = 1.0
        h = dict(zip(active, hits))
        for n, hh in h.items():
            p *= accs[n] if hh else 1 - accs[n]
        base = set()
        coin = []
        for n in active:
            if any(n in mp for mp in mutual):
                continue
            if h[n]:
                base.add(T[n])
        for (x, y) in mutual:
            if h[x] and h[y]:
                coin.append((x, y))
            elif h[x]:
                base.add(y)
            elif h[y]:
                base.add(x)
        outs = [(1.0, base)]
        for (x, y) in coin:
            outs = [(sp * 0.5, sd | {y}) for sp, sd in outs] + \
                   [(sp * 0.5, sd | {x}) for sp, sd in outs]
        for sp, dead in outs:
            alive = [n for n in names if n not in dead]
            if not alive:
                for n in names:
                    P[n] += p * sp / 3
            elif len(alive) == 1:
                P[alive[0]] += p * sp
            elif len(alive) == 2:
                x, y = alive
                wx = duel_win(accs[x], accs[y])
                P[x] += p * sp * wx
                P[y] += p * sp * (1 - wx)
            else:
                repeat += p * sp
    if repeat < 1:
        for n in P:
            P[n] /= 1 - repeat
    return P

def best(a, b, c):
    accs = {'A': a, 'B': b, 'C': c}
    names = list(accs)
    choices = {n: [m for m in names if m != n] + ['pass'] for n in names}
    eqs = []
    for prof in product(*[choices[n] for n in names]):
        T = dict(zip(names, prof))
        V = round_value(accs, T)
        ok = True
        for n in names:
            for alt in choices[n]:
                if alt == T[n]:
                    continue
                T2 = dict(T)
                T2[n] = alt
                if round_value(accs, T2)[n] > V[n] + 1e-9:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            eqs.append((prof, V))
    return eqs[0][1] if eqs else None

V = best(1.0, 0.8, 0.5)
print({k: round(v, 4) for k, v in V.items()})
# {'A': 0.225, 'B': 0.2667, 'C': 0.5083}

The script reproduces the table-entry computation: at $(b, c) = (0.8, 0.5)$ the Nash equilibrium prediction is $(0.225, 0.267, 0.508)$, identifying Costello as the favoured winner. Looping over the grid reproduces the winner map above; the cells where Abbott is favoured cluster in the low-$b$, low-$c$ corner, and Bob wins narrow bands near $b = c$ and the right boundary.