Every random game has an odd number of equilibria

A third of random games have no pure equilibrium counted the cells of a random payoff table that are each player’s best reply to the other, and found exactly one on average. That count leaves out most of the equilibria. A Nash equilibrium may have each player choose at random among several strategies, with probabilities that make the other player indifferent among the strategies it uses — the mixtures of a mixture that is a population and of matching pennies. Every game has at least one equilibrium of this kind, by Nash’s theorem, and the question here is how many a random game has in total.

That count is harder than the pure one, because a mixed equilibrium is not a cell of the table. It is the solution of a system of linear equations, and which system depends on which strategies each player mixes over. But it can be done exactly, by trying every possibility, and two things come out of doing it. One is that the number of equilibria of a random game is always odd. The other is that it grows, slowly, and that the growth is entirely in the mixed equilibria.

Finding every equilibrium by trying every support #

The set of strategies a player uses with positive probability is its support. If the column player mixes over a set $J$ of columns with probabilities $y$, the row player is willing to mix over a set $I$ of rows only if every row in $I$ earns the same expected payoff against $y$, and no row outside $I$ earns more. That is a system of linear equations — one for each row in $I$, plus the condition that the probabilities in $y$ add to one — and the same holds with the roles exchanged.

So equilibria can be found by brute force. For every pair of supports, solve the two systems. Keep the solution if both are genuine probability vectors, positive on their supports, and if no strategy outside either support would do better. This is support enumeration, and for a game with $n$ strategies on each side it means at most $(2^n - 1)^2$ pairs of systems. In a random game only pairs of equal size can work. A random payoff table is nondegenerate: $k$ strategies of one player can make at most $k$ strategies of the other indifferent, so a support of size $k$ must face a support of size $k$. That cuts the work to $\sum_k \binom{n}{k}^2$ pairs — 69 for four strategies, 3,431 for seven.

The hero figure is the whole search for one four-by-four game. Each shaded cell is a pair of supports of equal size and a pair of small linear systems; seven of the 69 succeed. The three on the diagonal of single strategies are pure equilibria. The other four mix, two over pairs of strategies, one over a pair on one side against a pair on the other, and one over three strategies each.

One mixed equilibrium, worked by hand #

The linear systems are small enough to solve on paper in the two-by-two case, and doing so shows what the census is computing. Take a coordination game in which both players earn 2 if they meet at the top-left cell, 1 if they meet at the bottom-right, and 0 if they miss. Suppose the column player chooses left with probability $q$. The row player’s expected payoff is $2q$ from top and $1 - q$ from bottom, and it is willing to mix only if the two are equal: $2q = 1 - q$, so $q = \tfrac13$. By the same reasoning the row player must choose top with probability $\tfrac13$ to make the column player indifferent.

So the game has three equilibria: the two pure cells, each a convention, and the mixture in which each player chooses its better convention only a third of the time and they miss each other more often than not. That mixed equilibrium is the one of index $-1$. It is the knife-edge between the two conventions, where a slight lean either way tips play into one of them, which is why it is the unstable one. And its probabilities are set by the other player’s payoffs, not the player’s own. That is the feature of mixed equilibria that the value from both sides found in zero-sum games, where each player’s mixture is chosen to neutralise the opponent’s options.

Support enumeration does exactly this for every pair of equal-sized supports, with larger systems. The answer is kept only when the probabilities come out positive and no unused strategy beats the used ones.

The count is odd, every time #

Doing this for 4,000 random two-by-two games, 3,000 three-by-three, and fewer of the larger sizes up to 300 seven-by-seven games — 11,200 games in all — gives the distribution of the number of equilibria.

Every game has 1, 3, 5, 7, 9 or 11 equilibria, and not one has an even number. At two strategies, seven games in eight have exactly one equilibrium and one in eight has three. That eighth is the coordination-shaped games, where two pure equilibria are joined by a mixed one between them; two equilibria and no way to choose drew one. As $n$ grows the distribution flattens and moves right. At seven strategies only 19% of games have a unique equilibrium, and a few have nine or eleven.

The oddness is a theorem. Robert Wilson proved in 1971 that every nondegenerate game has an odd number of equilibria, and for two-player games it also follows from the algorithm of Carlton Lemke and Joseph Howson of 1964. That algorithm follows a path through the corners of two polytopes from an artificial starting point to an equilibrium. Every equilibrium is an end of exactly one such path; the paths that do not start at the artificial point pair equilibria off with one another; and the one that does start there ends at one left over. Equilibria come in pairs plus one. The census confirms it on every game, and the theorem says it could not have done otherwise.

Plus one and minus one #

The pairing has a quantitative form that the census can check directly. Every equilibrium of a nondegenerate game carries an index, a sign of $+1$ or $-1$ that records which way a small deformation of the game would push it. For two-player games with positive payoffs, the index of an equilibrium mixing over $k$ strategies each is

$$(-1)^{k+1}\,\operatorname{sign}\bigl(\det A_{IJ} \cdot \det B_{IJ}\bigr),$$

the signs of the two $k$-by-$k$ blocks of payoffs on the supports. The index theorem says the indices of all equilibria of a game add up to $+1$.

Every game in the census lies on the line one above the diagonal. Seven thousand four hundred and thirty-one have a single equilibrium of index $+1$ and nothing else. Nearly three thousand have two of index $+1$ and one of $-1$, and the rest climb the line to nine against eight. A count that is always one more than another count is always odd, and that is Wilson’s theorem seen as arithmetic.

The index also says where the mixed equilibria are. A pure equilibrium of a random game always has index $+1$, since for $k = 1$ the two determinants are single positive payoffs. So a game with $p$ pure equilibria needs $p - 1$ more equilibria of index $-1$ than mixed ones of index $+1$ to balance. Between every two pure equilibria there is, in effect, a mixed one of opposite sign — the unstable mixture in the stag hunt, poised between the two conventions. That is the configuration a mixture that is a population drew for the stag hunt, whose mixed equilibrium was a watershed between two basins: index $-1$ equilibria are the ones that evolutionary dynamics flee.

How the number grows #

The mean number of equilibria rises with the size of the game.

From 1.25 at two strategies the mean rises to 1.64, 2.11, 2.72, 3.43 and 4.39 at seven. On the logarithmic scale that is close to a straight line, an exponential growth of about $e^{0.24}$ per strategy at these sizes. The pure equilibria stay at one on average, exactly as the previous count said they must, so all of the growth is in the mixed equilibria. Andrew McLennan and Johannes Berg computed the expectation exactly in 2005 for payoffs drawn from a bell curve and found exponential growth at a rate of about $0.28$ per strategy. The measured $0.24$ is consistent with that rate being approached from below at small sizes.

Exponential growth in the mean does not mean that a typical game has many equilibria. The mean is pulled up by the rare games with nine or eleven, while at seven strategies a third of games have one or three. The mean also says nothing about whether the equilibria are easy to find. The census found them by trying every support, at a cost that grows like $4^n$. Finding even one equilibrium of a two-player game is PPAD-complete, the complexity class the cost of finding a fixed point belongs to, and no algorithm substantially faster than search is known for it.

What the equilibria mix over #

Most of the mixed equilibria of a random game mix over a modest number of strategies.

At seven strategies, 23% of equilibria are pure, 32% mix over two strategies on each side, 28% over three, 14% over four, and the sizes above that are rare. Full mixing over all seven strategies occurred in none of the 300 games. The count is shaped by two opposing effects. There are most pairs of supports at the middle sizes — $\binom{7}{3}^2 = 1{,}225$ pairs of size three against 49 of size one — but a larger support asks more of chance. Every strategy in it must earn exactly the same, and every strategy outside it must earn less, so the probability that a given large pair works is small. The product of the two peaks near a third of $n$.

That is also why the growth is slow. Each additional strategy multiplies the number of candidate support pairs by about four, but the chance that a given pair succeeds falls by nearly as much, and what is left is the factor of about $1.28$.

The game with the most equilibria #

Random games have few equilibria on average. How many can a game have at most? The obvious candidate is the coordination game, in which each player is paid one if their choices match and nothing otherwise. Every nonempty set of strategies, used by both players with equal probabilities, is an equilibrium, so the coordination game with $n$ strategies has exactly $2^n - 1$ — checked here for $n$ up to five. Thomas Quint and Martin Shubik conjectured in 1997 that no nondegenerate game has more.

A blind search finds the maximum for two and three strategies, and at four it stalls at eleven, short of the coordination game’s fifteen. Games near the maximum are a vanishing corner of the space, and small perturbations of a random game do not lead there. The search is evidence of how rare highly multiple games are, not of where the maximum lies.

The maximum itself is known for small sizes, and the conjecture is false. It holds for up to four strategies, and for four it was proved by Andrew McLennan and In-Uck Park. But in 1999 Bernhard von Stengel constructed a six-by-six game with 75 equilibria, more than the coordination game’s 63, using polytopes whose corners can be arranged to align in more ways than a coordination game allows. For five strategies the maximum is still not known. So $2^n - 1$ is the right answer exactly where a search could check it and wrong beyond, a pattern that holds only in small cases.

When the count is not odd #

Oddness needs the game to be nondegenerate, and the census’s random payoffs guarantee that with probability one. Games people write down are often degenerate. A game in which every payoff is zero has every pair of strategies as an equilibrium, a continuum of them. A game with a tie in the right place can have exactly two equilibria: change matching pennies so that one player is indifferent between its two strategies against one column, and the mixed equilibrium can slide into a pure one and the two merge. Degenerate games are a set of measure zero among all games. But they are exactly the ones with round-number payoffs and symmetries, which are the games that textbooks and economists write down.

The index theorem explains what happens at a degeneracy. As a game is deformed continuously, equilibria move continuously, and they appear and disappear only in pairs of opposite index colliding — a $+1$ and a $-1$ meeting and annihilating, or being born together. Through every such event the sum of indices stays at $+1$. That is the mechanism the reading that is almost right used in a different setting, where a small perturbation selected one equilibrium of a game that had several: perturbations move equilibria, and only pairs of them can vanish.

The same continuity underlies the existence argument. Nash’s theorem is a fixed-point theorem, and a fixed point of a continuous map has an index for the same reason an equilibrium does. The two indices are one notion, and the landscape nobody is looking at is the special case where a potential function turns the pure equilibria into the bottoms of valleys, so that every downhill walk ends at one.

What a census of random games cannot say #

Each count in the census is exact for its game. Support enumeration finds every equilibrium of a nondegenerate game, and oddness and the index sum were checked on all 11,200. But the census is a sample of games. Its distributions carry sampling error, a few per cent at the largest sizes, where there are only 300 games. And it is a sample from one distribution — independent payoffs from a bell curve — whose results need not carry over to games with structure.

Nor does the census say which equilibrium is played. A random seven-by-seven game has on average more than four equilibria, of which one is pure on average. Which of them, if any, describes behaviour is the question of equilibrium selection. The index gives one partial answer: equilibria of index $-1$ are unstable under every natural adjustment dynamic, so they are unlikely descriptions of anything that persists. The rest is not settled by counting.

Still open: the maximum, and the typical case #

The maximum number of equilibria of an $n$-by-$n$ nondegenerate game is not known for any $n$ from five upwards. Von Stengel’s constructions give games whose count grows like $2.414^n/\sqrt n$, faster than the coordination game’s $2^n$. The best upper bound, from counting the corners of the polytopes involved, grows like $2.598^n/\sqrt n$. The true growth rate lies somewhere between the two.

For the typical case, McLennan and Berg’s exponential rate describes the mean. The distribution of the count around the mean — how often a random game has a unique equilibrium as $n$ grows — is less understood. The census shows the unique-equilibrium share falling from 87% at two strategies to 19% at seven, and whether it tends to zero, and how fast, is open. So are the analogous questions for games with more than two players, where the equilibria are solutions of polynomial rather than linear systems, the counts grow much faster, and the methods of the two-player case do not apply.

Odd, slowly growing, and mostly mixed #

A random game has a pure equilibrium on average once, and its total number of equilibria is odd because the indices add to one. It grows by about a quarter for each added strategy, entirely through mixed equilibria over a modest number of strategies. Most of it is invisible to anyone who looks only at the table’s cells. The search for the game with the most equilibria finds the coordination game’s $2^n - 1$, which fails beyond five strategies. What counting cannot decide is which of the equilibria anyone will play.