Are You The Best Warlord?

Riddler Express

Submit a whole number between $1$ and $1{,}000{,}000{,}000$. The submitter whose number is closest to two-thirds of the mean of all submissions wins. The first time this competition was held, the mean was $195{,}921{,}656$.

The Riddler, FiveThirtyEight, May 3, 2019(original post)

Solution

This is the textbook “guess two-thirds of the average” game. Although it is a participatory contest in form, it has a clean game-theoretic answer that does not depend on the population of submitters: the unique Nash equilibrium is for everyone to submit $1$.

Iterated elimination of weakly dominated strategies. Whatever everyone else does, the mean is at most $10^{9}$, so two-thirds of the mean is at most $\tfrac{2}{3} \cdot 10^{9} = 666{,}666{,}666.\overline{6}$. Any submission strictly above $666{,}666{,}667$ is therefore worse than $666{,}666{,}667$ no matter what others choose, so it is weakly dominated.

Erase those dominated submissions; the upper bound on the mean drops to $666{,}666{,}667$, so two-thirds of the mean is at most $444{,}444{,}444.\overline{6}$. Any submission strictly above $444{,}444{,}445$ is now weakly dominated. Repeat.

After $r$ rounds the upper bound on viable submissions is $\lceil (2/3)^{r} \cdot 10^{9} \rceil$. The bound shrinks geometrically by a factor of $\tfrac{2}{3}$ each round, and after about $r = \log_{3/2}(10^{9}) \approx 51$ rounds it falls below $2$, leaving only the submission $1$.

Equilibrium. If every submitter chooses $1$, the mean is $1$ and two-thirds of the mean is $\tfrac{2}{3}$; the closest integer in $[1, 10^{9}]$ is $1$, and every submitter ties for first. No submitter can deviate profitably: any other choice strictly exceeds $\tfrac{2}{3}$ in distance from the target, and ties no longer.

The historical mean of $195{,}921{,}656$ from the first running and $163{,}918{,}246$ from this running show that the population stays well above equilibrium. The literature on this game distinguishes “levels of reasoning”: a level-$0$ player guesses uniformly with mean $5 \times 10^{8}$; a level-$1$ player best-responds to that and submits $\tfrac{2}{3} \cdot 5 \times 10^{8} \approx 3.3 \times 10^{8}$; a level-$2$ player submits $(\tfrac{2}{3})^{2} \cdot 5 \times 10^{8} \approx 2.2 \times 10^{8}$; and so on. The observed means are consistent with a population whose typical depth of reasoning is between $1$ and $2$ rounds.

The computation

Re-encode the game: simulate populations of submitters drawn from each level of reasoning, compute the empirical winning number under each population mix, and confirm that the iterated-dominance limit is $1$. The aim is not to forecast the actual contest but to verify the iterated-elimination calculation directly, and to show how the winning number scales with the level mix.

1. Iterate the bound: $b_{0} = 10^{9}$, $b_{r+1} = \lceil \tfrac{2}{3} b_{r} \rceil$. Confirm it falls to $1$ in fewer than $60$ rounds.

2. For each round $r$, draw $5{,}000$ “level-$r$ submitters” uniform on $[1, b_{r}]$ and one “equilibrium” submitter at $1$. Compute the winning number.

3. Plot the winning number against $r$ and compare to the geometric factor $(2/3)^{r}$.

import random
random.seed(2019)

# 1. Iterated upper-bound shrinkage. Real-valued ceiling so the iteration
# converges; integer ceiling gets stuck at b=2 (a known boundary effect).
def shrink(b, rounds):
    bounds = [b]
    for _ in range(rounds):
        b = b * 2 / 3
        bounds.append(b)
    return bounds

bounds = shrink(10 ** 9, 60)
print(f"after 52 rounds, real bound = {bounds[52]:.4f}")
print(f"after 60 rounds, real bound = {bounds[60]:.4f}")

# 2. Simulated populations at level r: uniform on [1, ceil(b_r)].
def winning_number(submissions):
    mean = sum(submissions) / len(submissions)
    target = (2 / 3) * mean
    return min(submissions, key=lambda x: abs(x - target)), target

for r in [0, 1, 2, 3, 4, 5, 6]:
    cap = max(1, int(bounds[r]))
    pop = [random.randint(1, cap) for _ in range(5000)]
    win, tgt = winning_number(pop)
    print(f"  level {r}: cap={cap:>13,}  target={tgt:>13,.0f}  win={win:,}")

# 3. The historical first-running mean and resulting winning number
hist_mean = 195_921_656
print(f"\nfirst running: mean={hist_mean:,}, 2/3 of mean={2*hist_mean//3:,}")
hist_mean2 = 163_918_246
print(f"this running:  mean={hist_mean2:,}, 2/3 of mean={2*hist_mean2//3:,}")

The script prints that the real-valued upper bound after $52$ rounds is well below $1$, so $52$ rounds of iterated dominance collapse the bound from $10^{9}$ to the equilibrium of $1$. Level-$r$ uniform populations produce winning numbers shrinking by a factor of $\tfrac{2}{3}$ per level. The first running’s two-thirds-of-mean target was $130{,}614{,}437$; this running’s was $109{,}278{,}830$.

Riddler Classic

The third edition of the Riddler Nation battle royale: distribute $100$ soldiers among $10$ castles worth $1, 2, \ldots, 10$ victory points; whoever sends more soldiers to a castle wins those points, and the warlord with the most points wins. Submit a deployment to compete against every other reader’s submission in a round-robin.

The Riddler, FiveThirtyEight, May 3, 2019(original post)

Status

This is the third Battle for Riddler Nation, the same Colonel Blotto contest as the rounds in early $2017$ and mid-$2017$. As with those rounds, the winning deployment is a property of the specific reader population, not a derivable optimum. Colonel Blotto with continuous resources has no pure-strategy Nash equilibrium; the mixed-strategy equilibrium depends on the value distribution and has been worked out for symmetric players only in limited cases (Borel, $1921$; Gross and Wagner, $1950$), and the discrete-resource version with $100$ soldiers among $10$ castles weighted $1, \ldots, 10$ is studied numerically. None of that predicts the round-robin winner, which is determined entirely by the empirical opponent population.

The published winner was Vince Vatter of Gainesville, Florida, with the deployment $(0, 0, 12, 1, 1, 23, 3, 3, 33, 24)$, hand-tuned by genetic algorithm against the previous two rounds’ submissions. The published average deployment across the $1{,}500$ submissions was $(2, 3, 4, 7, 9, 12, 13, 17, 17, 16)$, with a markedly heavier weighting toward Castles $9$ and $10$ than in the earlier rounds.

This puzzle is deferred for the same reason as “Battle for Riddler Nation” Rounds $1$ and $2$ in early and mid $2017$: the answer is a contingent empirical fact about who submitted what, not a deriveable optimum.