Learn the equilibrium with no linear program — just best-respond to the running average of what the other player did. Brown proposed it; Robinson proved it converges. The minimax value appears out of two players guessing at each other's habits.
source Julia Robinson, An Iterative Method of Solving a Game, Annals of Mathematics 54(2), 1951, pp. 296–301 — method of G. W. Brown (1951). No stable open primary; cited by journal / volume / year amber. Rendered, not quoted.
Two players, a zero-sum payoff matrix A. Row maximises, Column minimises. Each round every player plays a best response to the empirical frequency of the opponent's past moves — the belief is just "how often have they done each thing so far."
Belief update: v ← v + e(action). Best response: argmaxₕ Aₕ·(v/t) for Row, argmin⫺ (Aᵀ)⫺·(u/t) for Column. No LP is ever solved — only counting and a max.
Two running estimates of the value bracket it: the upper U=maxₕ Aₕ·v /t (Row's best reply to Column's history) and the lower L=min⫺ uᵀA⫺ /t. Always L ≤ value ≤ U.
Neighbour: the-minimax (von Neumann, 1928). There the value is the answer to one linear program; here the same value is reached without ever writing that program — it precipitates from repeated best-response.
Fictitious play is the constructive, learning-shaped proof that the minimax value is not just an existence theorem: two myopic bookkeepers converge to it. Downstream this becomes regret-matching and self-play.
Live re-check of the engine below. Confirms convergence on the honest run; flips red the instant the tamper (window 6) is engaged, because the value gap stops closing.
Zero-sum game (Row payoff A). Non-uniform mixed equilibrium so a cheat cannot fake it by symmetry:
Equilibrium (closed form): Row (¼,¾), Column (½,½), value = 1.5. Also selfchecked: Matching Pennies → (½,½).
mode: fictitious play — best-respond to full history.
The gap U−L collapses toward 0 and the running value converges to 1.5 — the minimax value — while the empirical mix approaches Row (¼,¾). Reached by counting alone. Robinson 1951
Convergence is not universal. Robinson's proof covers zero-sum (and 2×n) games. In general-sum games fictitious play can fail: Shapley (1964) exhibits a 3×3 game where the empirical play cycles forever and never settles.
Even where it converges, the rate is slow — the gap shrinks like ~t−1/2 in the worst directions, and ties in the best response must be broken by a fixed, disclosed rule or the path is ill-defined.
"Fictitious play finds a Nash equilibrium in any game."
→ Only in special classes (zero-sum, 2×n, potential, dominance-solvable). Shapley's game is the standing counterexample.
"The per-round play converges to the equilibrium strategy."
→ No — the time-average (empirical frequency) converges. The actual moves keep jumping between pure best responses.
"It's just averaging, so any short memory works."
→ The full history is load-bearing. Truncate it (window 6) and the process cycles. See the tamper.
Planted, disclosed void: replace "best-respond to the whole history" with "best-respond to the opponent's last move only" (Cournot, one-step memory). The play cycles; on this game the empirical mix locks to (½,½) instead of (¼,¾), so the gap stalls near 0.5 and never closes. The witness (7) catches it.