A Suspicious Tournament and a Gold-Hungry War

The Riddler for December 9, 2016. The Express is a clean impossibility argument; the Classic is a Bayesian game that unravels all the way to ruin.

Riddler Express

In a round-robin tournament of $N$ players (every pair plays once, winner gets a point, no ties), a fan spots a three-way cycle: A lost to B, B lost to C, and C lost to A. The same fan also notes that every player finished with a different score. Can both observations be true, or was a scoring mistake made?

The Riddler, FiveThirtyEight, December 9, 2016(original post)

Solution

The two observations cannot both hold, so a mistake was made. The argument is short once you see what all-distinct scores forces.

Each player plays $N-1$ games, so scores live in $\{0, 1, \dots, N-1\}$. If all $N$ scores are different, they must be exactly $0, 1, 2, \dots, N-1$, one of each. Now read the standings from the bottom. The player with $0$ points lost every game, so everyone beat them. Set that player aside; the next-lowest scored $1$, and that single win can only have been against the $0$-point player, so this player lost to everyone still above them. Repeating, each player beat precisely those below them in the standings and lost to all those above. That is a strict pecking order: the tournament is transitive.

In a transitive tournament there are no upsets to chain into a cycle. Take the three players A, B, C and suppose they finish in that order, A highest. Then A beat both B and C, in particular A beat B. But the fan saw A lose to B. Contradiction. So $$\boxed{\text{a mistake was made}}:$$ distinct scores and a three-way cycle cannot coexist.

The computation

Encode the claim exhaustively for small $N$: generate every possible tournament, keep those whose scores are all distinct, and check whether any of them contains a three-way cycle. None should.

import itertools
def audit(N):
    pairs = list(itertools.combinations(range(N), 2)); distinct = cyclic = 0
    for bits in itertools.product((0, 1), repeat=len(pairs)):
        beats = [[False] * N for _ in range(N)]
        for (i, j), b in zip(pairs, bits):
            (beats[i].__setitem__(j, True) if b else beats[j].__setitem__(i, True))
        score = [sum(row) for row in beats]
        if len(set(score)) < N: continue                       # need all distinct
        distinct += 1
        if any(beats[b][a] and beats[c][b] and beats[a][c]
               for a, b, c in itertools.permutations(range(N), 3)):
            cyclic += 1
    return distinct, cyclic
for N in (3, 4, 5):
    d, c = audit(N)
    print(f"N={N}: distinct-score tournaments={d}, of which contain a 3-cycle={c}")
# N=3: distinct-score tournaments=6, of which contain a 3-cycle=0
# N=4: distinct-score tournaments=24, of which contain a 3-cycle=0
# N=5: distinct-score tournaments=120, of which contain a 3-cycle=0

Riddler Classic

Two countries each draw an army strength uniformly from $[0,1]$, known only to themselves. Simultaneously each declares “peace” or “war”. If both say peace, each keeps its gold (worth $1 trillion). If either says war, they fight and the stronger army takes both hoards ($2 trillion to the winner, $0 to the loser). What is each country’s optimal strategy?

Extra credit: what if one declares first? What if winning is worth $5 trillion?

The Riddler, FiveThirtyEight, December 9, 2016(original post)

Solution

By symmetry, look for an equilibrium where each country declares war exactly when its strength exceeds some threshold $X$, and ask what your best response is if your opponent plays that way. The key observation is that your declaration only matters when your opponent declares peace, that is when their strength is below $X$; if they declare war, you are dragged into the fight no matter what you say.

So condition on the opponent being below $X$. Among those opponents, your strength is compared against a draw uniform on $[0,X]$. Declaring peace banks the sure $1 trillion. Declaring war instead wins $2 trillion whenever you are the stronger one, which happens with probability more than $\tfrac12$ as soon as your strength exceeds $X/2$ (you certainly beat everyone below $X$ once your strength tops $X$, and you are favoured well before that). Working out the indifference point, war pays better than the sure $1 trillion precisely when your strength exceeds $X/2$. Your best response to threshold $X$ is therefore threshold $X/2$, strictly lower.

That is fatal to any positive threshold. If the equilibrium threshold were $X>0$, the best response would be $X/2$, whose best response is $X/4$, and so on down. The only fixed point is $$\boxed{X = 0: \text{ always declare war}}.$$ Since strengths are always above $0$, both countries declare war in every situation.

Extra Credit

Sequential moves; or winning worth $5 trillion.

Solution

Neither change helps. If one country must declare first, declaring peace only signals weakness, low strength, which invites the opponent to attack, so the same undercutting collapses the strategies back to always declaring war. And raising the prize from $2 trillion to $5 trillion only sweetens war, making peace even less tempting. The equilibrium is unchanged: both declare war in every case. War, it turns out, is good for one thing, a Nash equilibrium.

The computation

Encode the best-response step that drives the unravelling: fix the opponent’s threshold $X$, simulate many strength pairs, and find the threshold that maximises your payoff. It should land on $X/2$ every time, confirming the slide to zero.

import numpy as np
def best_response(X, V=2, n=400_000, seed=0):
    rng = np.random.default_rng(seed); me = rng.random(n); opp = rng.random(n)
    def payoff(t):
        war = (me > t) | (opp > X)                       # war if either declares it
        return np.where(~war, 1.0, np.where(me > opp, V, 0.0)).mean()
    ts = np.linspace(0, 1, 101)
    return max(ts, key=payoff)
for X in (0.8, 0.5, 0.25):
    print(f"opponent threshold {X}: best response ~ {best_response(X):.2f}  (= X/2)")
print("X -> X/2 -> ... -> 0: the only equilibrium threshold is 0, always declare war")
# opponent threshold 0.8: best response ~ 0.41  (= X/2)
# opponent threshold 0.5: best response ~ 0.25  (= X/2)
# opponent threshold 0.25: best response ~ 0.12  (= X/2)
# X -> X/2 -> ... -> 0: the only equilibrium threshold is 0, always declare war