A best reply to the past

An equilibrium of a game says what players do if each is already playing a best reply to the others. It says nothing about how they would get there. The value from both sides found the equilibrium of a zero-sum game by linear programming, as a calculation done once, from outside; a mixture that is a population found it, sometimes, as the resting point of a population that shifts towards whatever is doing well. This essay takes a third route, the oldest learning rule in game theory, and finds that it succeeds in one large class of games, fails completely in a three-by-three game, and fails in a way that can be computed to the round.

The rule is fictitious play, proposed by George Brown in 1951. Each player keeps a record of everything the other has played and treats that record as though it were a fixed mixed strategy: if the opponent has played rock forty per cent of the time so far, the player acts as though rock will come with probability forty per cent. Each round, each player plays a best reply to that belief. Nobody is strategic about the learning itself, and nobody remembers anything but counts. The question is whether the records, the empirical mixtures, approach an equilibrium.

The rule, played exactly #

Every figure here runs the rule exactly, with counts kept as whole numbers. A best reply is computed against the counts themselves rather than against fractions, which changes nothing, since dividing by the number of rounds does not change which reply is best, and it keeps the play free of rounding. The rule also needs a convention for ties, since at the start, and occasionally later, two replies can be equally good; here a tie always goes to the lower-numbered strategy. With that fixed, every run of the rule is a deterministic sequence, and the same two million rounds come out every time.

The natural unit of the play is the run: a stretch of consecutive rounds in which neither player changes what they do. Within a run the counts of the two strategies being played grow, the other players’ beliefs shift slowly towards them, and the run ends at the round when one player’s best reply flips. The record of a game under fictitious play is the sequence of its runs and their lengths, and almost everything the figures show is read from that sequence.

Shapley’s game #

Lloyd Shapley wrote down the game in 1964 to show that the rule can fail. Each player has three strategies. The row player is paid one for matching the column player’s number and nothing otherwise. The column player is paid one for being one ahead of the row player, counting round so that one is ahead of three. Nobody’s payoff is anybody’s loss, so this is not a zero-sum game, and its only equilibrium is for both players to mix all three strategies equally.

Run from the profile in which both play their first strategy, the play passes through six profiles in a fixed order and returns, again and again. Each move is a chase. In profile (2, 3), with the row player on 2 and the column player on 3, the row player is missing; once enough rounds have accumulated, the history makes 3 the row player’s best reply and play moves to (3, 3). Now the column player is not ahead, and once the row player’s history leans far enough towards 3, the column player moves to 1, which is one ahead of 3. And so on round the six profiles. Every best reply is a reply to the history, and the history lags behind the present, so each player is always answering the play of some rounds ago.

The record of runs is exact and strange. The first runs last 1, 2, 4, 7, 11, 17, 26, 39, 58, 86 rounds, and after 2,000,000 rounds there have been thirty-four runs, the last one nearly six hundred thousand rounds long. Every run, from the fourth on, is exactly the run before it plus the run three before it plus two: $26 = 17 + 7 + 2$, $39 = 26 + 11 + 2$, $578{,}947 = 395{,}031 + 183{,}914 + 2$. The figure’s check confirms the rule at every one of the thirty runs it applies to.

Runs that grow by a factor #

The recurrence fixes the long-run growth. A sequence obeying $L_k = L_{k-1} + L_{k-3}$, plus a constant that stops mattering as the terms grow, increases in the end by a constant factor $x$ satisfying $x^3 = x^2 + 1$. That equation’s real root is $1.4655712\ldots$, sometimes called the supergolden ratio, the cousin of the golden ratio for a recurrence that looks three steps back instead of two.

That growth is the whole reason the mixtures never settle. If each run is $1.4656$ times the previous one, then the current run is always a fixed share of everything that has happened — about a third of all the rounds so far — so the latest run always moves the empirical mixture a fixed distance. The mixture is dragged towards the corner of the current profile for a third of the history, then towards the next, and round it goes. The loops in the hero figure do not shrink because the runs keep pace with the history they are added to. After two million rounds the row player’s mixture is $(0.371, 0.456, 0.173)$, as far from a third each as it was after two thousand, and it will be just as far after two billion.

The same figure shows the contrast that makes Shapley’s game exceptional. Rock–paper–scissors, under the same rule, also cycles — started from the same profile, both players play the same thing in every run and go round rock, paper, scissors by the same kind of chase — but its runs grow by exactly two rounds each time: 1, 3, 5, 7, 9, …, reaching $2{,}827$ after $1{,}414$ runs. After $k$ runs about $k^2$ rounds have passed, and a single run is about $2k$ of them, a vanishing share. Arithmetic growth lets the history win; geometric growth never does.

A triangle the play cannot leave #

The loops in the hero figure close onto a fixed shape, and that shape has a name. Run fictitious play in continuous time — each player’s mixture moving steadily towards its current best reply, which is the limit of the discrete rule when the history is long — and in Shapley’s game the mixtures converge not to the equilibrium but to a closed orbit, a triangle in each player’s simplex. Andrea Gaunersdorfer and Josef Hofbauer described it in 1995 and called it the Shapley triangle. Its corners are the mixtures at which a best reply switches, and it is attracting: mixtures that start near the equilibrium spiral out to it, and mixtures that start near the edges spiral in. The discrete play follows the same triangle with ever longer runs along each side, and the triangle in the hero figure, traced by two million rounds, is that orbit.

The equilibrium is still there at the centre, and it is still the only equilibrium of the game. It is simply unstable under this kind of learning. A population that started exactly at a third each would stay there; anything else is carried out to the triangle and round it. That is the same distinction a mixture that is a population drew for evolutionary dynamics, where rock–paper–scissors with wins worth exactly what losses cost had orbits circling its centre for ever and never reaching it. Fictitious play is more decisive than the replicator dynamic in the zero-sum case — it closes in where the replicator only circles — and more decisive in the other direction in Shapley’s game, where it runs away to a limit cycle.

Why a lag is enough is clearest from the order of the six profiles. The row player’s best reply is the column player’s most frequent recent strategy, and the column player’s best reply is one ahead of the row player’s. So when the row player catches up, the column player has already moved on, and the row player is replying to where the column player was. In the equilibrium every strategy is equally frequent and the chase has nowhere to go; one step away from it, the chase takes over, and the runs grow because each player must accumulate more history to overturn a longer past. Three strategies each are the fewest that allow such a chase to escalate: with two, Miyasawa’s theorem says the play always converges.

The constant itself, the root of $x^3 = x^2 + 1$, is the three-step cousin of the golden ratio that the rectangle that eats itself found from a two-step rule. Roughly, the recurrence looks three runs back because a run ends when one of the opponent’s counts overtakes another, and in a cycle of six profiles, in which each player changes strategy every second run, the count to be overtaken was last added to about three runs earlier; the figure’s check is what makes the recurrence exact rather than rough.

In a zero-sum game the spiral closes in #

Rock–paper–scissors is zero-sum: what one player wins the other loses. For that class of games Julia Robinson proved in 1951, the year the rule was proposed, that fictitious play always works: the empirical mixtures approach the set of equilibria, in every zero-sum game of any size.

The mixture spirals in. Its distance from a third each falls from $0.41$ after two rounds to $0.037$ after 179, $0.0027$ after a hundred thousand and $0.00057$ after a million, and on logarithmic axes the decline has slope $-0.51$. That rate comes straight from the runs. The mixture overshoots the equilibrium by about the length of the current run as a share of the history, which is of order $\sqrt t / t = t^{-1/2}$ after $t$ rounds. Samuel Karlin conjectured in 1959 that $t^{-1/2}$ is the rate in every zero-sum game. It is the rate here, and it is not the rate in general: Constantinos Daskalakis and Qinxuan Pan showed in 2014 that with ties broken adversarially, fictitious play on some zero-sum games converges far more slowly. Whether Karlin’s rate holds when ties are broken in some reasonable fixed way, as here, is still open.

Two guarantees closing on the value #

Robinson’s proof works through two numbers that the next figure tracks in a zero-sum game with a less symmetric answer. Take rock–paper–scissors and make rock’s win over scissors worth two instead of one. The game is still zero-sum and its value is still nought, by symmetry between the players, but the equilibrium shifts: rock is now tempting, paper is the answer to rock, and the optimal mixture is a quarter rock, a half paper and a quarter scissors.

At every round two quantities can be read off the counts. One is what a best reply to the opponent’s history would earn, which can never be less than the value of the game, since the value is the most the opponent can hold anyone to. The other is what the player’s own history guarantees against the opponent’s best reply, which can never be more than the value. They bracket the value from both sides at every round, and Robinson’s theorem is that the bracket shrinks to nothing. Here it closes from $\pm 0.18$ after eleven rounds to $\pm 0.0009$ after 631,284, and the row player’s mixture approaches $(0.2500, 0.5007, 0.2493)$ — the lopsided equilibrium, found by players who never computed anything but best replies.

That bracket is the zero-sum game’s two-sided view, which the value from both sides set up as a pair of linear programs, here produced by learning. It is also why the rule fails outside zero-sum games. In Shapley’s game there is no single value for the two players’ guarantees to close on: what one player can secure and what the other can hold them to are not tied together, and nothing forces the history towards the equilibrium.

When interests coincide #

The other extreme from zero-sum is a game in which both players are paid the same: they want only to coordinate. The last figure uses a three-by-three game that pays both players 2, 3 or 4 for meeting on the first, second or third strategy, and nothing for missing.

From every one of the nine starting profiles, play settles on a diagonal profile within two rounds and stays there. It does not always find the best one: started on the first diagonal profile, it stays there, since each player’s best reply to a history of 1s is 1, and five of the nine starts end on the best profile, three on the middle one and one on the worst. That is still convergence to an equilibrium, which is all the rule promises; which equilibrium a learning rule lands on is the selection problem two equilibria and no way to choose left without a principled answer, and here the answer is decided by the first round. Dov Monderer and Lloyd Shapley proved in 1996 that fictitious play converges in every game of common interest, and more generally in every game with a potential — a single function that every player’s improvement increases, the structure the landscape nobody is looking at described. Kenji Miyasawa had proved convergence for every two-by-two game in 1961.

So the rule works at both extremes, pure conflict and pure common interest, and fails in between. Shapley’s game sits in the gap: neither zero-sum nor a potential game, and three strategies are enough for the chase to run away.

What the play cannot show #

Each figure is one run of a deterministic rule from one starting point, with one convention for ties. The exact recurrence in Shapley’s game is a fact about that run: from a different start, or with ties broken the other way, the first few runs differ, and whether the recurrence and its constant are the same is not something these figures check. Shapley’s own proof that the play cycles does not depend on such details; it shows that the mixtures stay a fixed distance from the equilibrium whatever happens, by bounding the runs from below, and the exact sequence here is a finer statement than his theorem.

The figures also show nothing about games with more strategies or more players. Robinson’s theorem holds for zero-sum games of any size; Monderer and Shapley’s for potential games of any size; but the space between, of general games, is large, and the behaviour of fictitious play there ranges from convergence to cycles to orbits that never repeat. Which games are which is not decided by any simple criterion.

Still open: how fast, and how often #

Two questions remain open in the cases that are understood best. The first is Karlin’s: whether fictitious play converges at the rate $t^{-1/2}$ in every zero-sum game when ties are broken in a fixed, non-adversarial way. The rock–paper–scissors and lopsided runs both show that rate, and no counterexample with fair tie-breaking is known, but neither is a proof.

The second is about typical games. In a game whose payoffs are drawn at random — where a third of random games have no pure equilibrium at all, so any convergence must be to a mixture, and the setting of every random game has an odd number of equilibria — how often does fictitious play converge? For two-by-two games the answer is always. For larger games numerical studies find cycling in a substantial share, growing with the number of strategies, but no exact or asymptotic formula for that share is known, and it depends on what is meant by convergence for games with several equilibria.

Learning that lags #

Fictitious play is learning with no model of the opponent beyond a frequency count, and its failure in Shapley’s game has a simple description: each player is always replying to an average over the past, and in a game where the right reply to someone’s current play is the wrong reply to their past, a lag is enough to make the averages run in circles. In zero-sum games the lag does no harm, because the two players’ guarantees pin each other to the value, and in games of common interest there is nothing to chase. In between, three strategies each and a one-step offset in what the players want are enough for the runs to grow by the root of $x^3 = x^2 + 1$, for every run to be a third of the history, and for two million rounds of careful learning to leave both players exactly as far from equilibrium as they started.