Generator

Best replies in a coordination game

A generator in the applied library, called 102 times across 16 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

game is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

Best replies in a coordination game. A bimatrix with every best reply marked on both sides and every cell that is a best reply for both boxed as a pure equilibrium. 2 such cells were found.

Fictitious play that never settles

Fictitious play that never settles. Shapley's 3 × 3 game, 34 runs in 2,000,000 rounds; final mixtures row 0.371, 0.456, 0.173, column 0.253, 0.544, 0.203.

Six profiles, visited in turn for ever

Six profiles, visited in turn for ever. Cycle (2,3) → (3,3) → (3,1) → (1,1) → (1,2) → (2,2); last runs 8639, 12662, 18558, 27199, 39863, 58423, 85624, 125489, 183914, 269540, 395031, 578947.

Runs that grow by a factor never settle

Runs that grow by a factor never settle. Shapley runs 1, 2, 4, 7, 11, 17, 26, 39, 58, 86, 127, 187, 275, 404, 593, 870, …, ratio 1.465579; rock–paper–scissors runs 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, …, last 2823, 2825, 2827.

In a zero-sum game the spiral closes in

In a zero-sum game the spiral closes in. Rock–paper–scissors distance from equilibrium: t=2: 4.08e-1; t=179: 3.73e-2; t=756: 1.68e-2; t=2648: 9.16e-3; t=8864: 7.85e-3; t=29251: 5.27e-3; t=96143: 2.73e-3; t=315619: 1.21e-3; t=1035734: 5.73e-4; slope -0.505.

Two guarantees closing on the value

Two guarantees closing on the value. t=11: [-0.1818, 0.1818]; t=154: [-0.0584, 0.0584]; t=543: [-0.0295, 0.0295]; t=1586: [-0.0177, 0.0177]; t=4393: [-0.0107, 0.0107]; t=11955: [-0.0064, 0.0064]; t=32303: [-0.0039, 0.0039]; t=87072: [-0.0024, 0.0024]; t=234489: [-0.0015, 0.0015]; t=631284: [-0.0009, 0.0009]; final mixture 0.2500, 0.5007, 0.2493.

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Applied

A best reply to the past

Let two players each answer the whole history of the other's play as though it were a fixed plan. In a zero-sum game the history closes in on the equilibrium, as Julia Robinson proved in 1951. In Lloyd Shapley's three-by-three game it never does: play runs round six profiles for ever, each run the one before plus the one three before plus two, so the runs grow by the real root of x³ = x² + 1 and every run is a fixed share of all the history.

Applied

A mixture that is a population

A mixed equilibrium between two choosers is a knife-edge nobody has a reason to stand on. Read the same mixture as a population whose shares grow with how well they do, and it becomes a point every population is carried to — or one every population circles for ever without arriving.

Applied

A signal both can see

Two choosers who randomise privately can reach a set of outcomes that is smaller, and worse, than the set they reach when a device draws one cell and whispers each of them their half of it. Nothing is enforced and nobody is bound, and the arrangement is stable anyway.

Applied

A third of random games have no pure equilibrium

Fill a game's payoff table with random numbers and ask whether some cell is each player's best reply to the other. Exactly one cell is expected to be, at every size, and the chance that none is climbs from one in eight to 1/e — the same constant that counts the shuffles in which nobody gets their own hat back, and for the same reason.

Applied

Every random game has an odd number of equilibria

Find every equilibrium of eleven thousand random games — pure and mixed, by trying every pair of strategy sets the players might mix over — and the totals are 1, 3, 5, 7, … and never an even number. The count is a sum of signs: equilibria of index +1 outnumber those of −1 by exactly one in every game. The average grows about 28% with each strategy added, and searching for the game with the most turns up the coordination game's 2ⁿ − 1, a pattern that holds only up to five strategies.

Applied

Patience instead of a contract

Commitment had to assume an announcement binds. Play the same game again tomorrow and the assumption is unnecessary — the future does the binding. What it costs is that nearly every outcome becomes an equilibrium, so a theory that could not choose between two now cannot choose between infinitely many.

Applied

Sellers in a square town

On a street, two sellers settle back to back in the middle, three never settle, and four settle in pairs at the quarter points. Spread the customers over a square town instead and the first fact survives while the third does not: the street's pairs leave a seller half a per cent of the town to gain by stepping off the line. Computing every seller's market exactly and searching for an arrangement where nobody wants to move finds one only for two sellers.

Applied

Sellers on a street stand back to back

Put two ice-cream sellers on a beach and they end up side by side in the middle, though customers would walk half as far if they stood at the quarter marks. Three sellers never settle at all: whoever is squeezed in the middle leaps outside, for ever. Four stand in pairs, five in pairs with one alone in the centre, six in endlessly many ways. Let them set prices too, with travel costing the square of the distance, and the conclusion reverses: the two sellers move as far apart as the beach allows.

Applied

The landscape nobody is looking at

Letting participants move one at a time to whatever is currently better can cycle forever, and on a network of congestible roads it cannot. The reason is a single number attached to each state that falls by exactly what the mover saves.

Applied

The reading that is almost right

Every account of simultaneous choice so far has assumed the payoffs are known to both choosers and known to be known. Replace that with each chooser seeing a private reading off by a little, and a band of equilibria closes to a single point — so the assumption nobody states decides the answer.

Applied

The road that makes everyone later

An equilibrium is a state nobody can improve alone, which is a much weaker thing than a state anybody would choose. Adding a link that costs nothing to use makes every traveller in this network strictly slower, and the arithmetic says by exactly how much.

Applied

The value from both sides

Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.

Applied

Two auctions that earn the same

In one sealed-bid auction the winner pays its own bid; in the other it pays the second-highest bid. Bidders behave completely differently — in the second they bid what the object is worth to them, in the first they shade their bids down by exactly a fraction — and the seller's revenue is spread differently. Yet the seller expects to collect precisely the same amount, (n − 1)/(n + 1) for n bidders with values spread evenly, and so does an auction in which everybody pays. The equality breaks the moment bidders dislike risk, and it says nothing about how much a reserve price can add.

Applied

Two colonels and a linear programme

Two colonels divide their soldiers among three battlefields at once, and whoever sends more to a field wins it. Every division can be beaten by some other, so neither colonel has a safe plan — until they are allowed to choose at random. The best random choice is a linear programme, the opponent's best is its dual, and the theorem that the two meet is von Neumann's. With nine soldiers each, one optimal plan uses only seven divisions, and on every field it sends each number from nought to six exactly once.

Applied

Two equilibria and no way to choose

A game can have two states nobody wants to leave, one paying more than the other, and the definition of an equilibrium has nothing to say about which happens. The two standard tie-breakers disagree, and the one that wins is usually the worse.

Applied

Worth more for being seen first

Moving first sounds like a disadvantage, since the other side gets to see the move and answer it. When the move is a mixture that is announced and believed, it is never a disadvantage, it is worth exactly nothing in a game of pure conflict, and in other games it is worth more than any equilibrium — sometimes by announcing an action that would never be played in secret.

The whole library · What the figures prove