A third of random games have no pure equilibrium

Every game drawn in the essays before this one was chosen to make a point. Two equilibria and no way to choose was built so that two cells were both stable. The value from both sides used zero-sum games, where one player’s gain is the other’s loss. The landscape nobody is looking at used a congestion game, whose potential function guarantees an equilibrium in pure strategies. Chosen examples show what can happen. They do not say what usually happens, and for that the natural experiment is to stop choosing: fill the payoff table with random numbers and see what kind of game comes out.

The first question to ask of a random game is whether it has a pure equilibrium — a cell where the row player’s choice is the best reply to the column player’s and the column player’s choice is the best reply to the row player’s, with neither of them randomising. Nash’s theorem guarantees an equilibrium in mixed strategies always; pure ones are not guaranteed, and matching pennies has none. The answer for random games turns out to be exact, simple and surprising. The expected number of pure equilibria is exactly one at every size. The chance of none at all tends to $1/e$.

Best replies as a random mapping #

The structure that makes the question tractable is visible in the figure. In each column exactly one cell carries a blue dot, because the row player has exactly one best reply to each column when payoffs are drawn from a continuous distribution and ties have probability zero. In each row exactly one cell carries a green dot. A pure equilibrium is a cell with both.

With independent payoffs, which row is best against a given column is uniform over the $n$ rows and independent of everything else, and likewise which column is best against a given row. So the best replies are two random functions — one from columns to rows, one from rows to columns — and a pure equilibrium is a pair (row $i$, column $j$) where the first function sends $j$ to $i$ and the second sends $i$ to $j$. Each of the $nm$ cells qualifies with probability exactly $\tfrac1n \cdot \tfrac1m$, so the expected number of pure equilibria is

$$nm \cdot \frac{1}{nm} = 1,$$

at every size, for every shape of game, for every continuous payoff distribution. Nothing about the payoffs’ values matters except their order within each row and column.

One game in eight, and then 1/e #

The expected number is one; the chance of none is not zero, because the count varies around its mean. Inclusion–exclusion gives it exactly. The expected number of ways to choose $k$ pure equilibria together, $\mathbb{E}\binom{X}{k}$, is the number of ways to pick $k$ distinct rows and $k$ distinct columns and pair them, times the chance that all $2k$ best replies point the right way:

$$\mathbb{E}\binom{X}{k} = \frac{(n)_k\,(m)_k}{k!\,(nm)^k},$$

where $(n)_k = n(n-1)\cdots(n-k+1)$. Alternating sums of these give the probability of every value of $X$.

For a two-by-two game the sum has three terms: $1 - 1 + \tfrac18 = \tfrac18$. One random two-by-two game in eight has no pure equilibrium. Those are the games shaped like matching pennies, in which the best replies chase each other around all four cells. At three strategies the chance is $0.214$, at five $0.283$, at ten $0.328$. In the limit every term of the inclusion–exclusion sum becomes $(-1)^k/k!$, and the sum becomes

$$1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots = \frac1e.$$

The approach is slow and steady. At twenty strategies the chance is still $0.349$, and at a hundred $0.364$; the shortfall is almost exactly $1/(en)$, so the exact chance is very nearly $(1 - 1/n)/e$. Sampled games at six sizes, four thousand of each, agree with the exact values within their sampling error.

The two-by-two case by hand #

The one in eight can be checked without any formula, and the check shows where the structure comes from. In a two-by-two game the row player has a best reply to each of the two columns, top or bottom, and the column player has a best reply to each of the two rows, left or right. That is four binary choices, each equally likely and independent of the others, so there are sixteen equally likely patterns of best replies, and every pattern decides the pure equilibria completely.

Count them. Suppose the row player’s best reply is the same row against both columns — say top, which happens in half the patterns. Then top dominates bottom, the column player replies to top with its best reply there, and that cell is an equilibrium; the other column’s top cell is not, because the column player does not choose it against top. Exactly one equilibrium. The same is true when the column player has a dominant column. Patterns in which neither player has a dominant strategy number $2 \times 2 = 4$ of the sixteen. In those the row player matches the column (top against left, bottom against right) or mismatches it, and the column player likewise.

If both match — a coordination game — there are two equilibria, on the diagonal. If both mismatch — a coordination game in the other diagonal — there are two again. If one matches and the other mismatches, the best replies chase each other round all four cells, as in matching pennies, and there is none. So two patterns of the sixteen give none, two give two and the remaining twelve give exactly one: $\tfrac18$, $\tfrac18$ and $\tfrac34$, the figure’s first column. The three classical two-by-two games — dominance, coordination and matching pennies — are the three outcomes of the count, in proportions twelve, two and two.

Why this is the hat-check constant #

The sum $1 - 1 + \tfrac1{2!} - \tfrac1{3!} + \cdots$ is the one that counts what does not happen in the oldest problem of its kind. When $n$ people’s hats are handed back at random, the chance that nobody gets their own tends to $1/e$, and inclusion–exclusion gives it as exactly this alternating series truncated at $n$.

The resemblance is not a coincidence of formulas. In both problems there are about $n$ independent chances, each of size about $1/n$, for a coincidence to occur — a person matched with their own hat, a row and column matched with each other — and the chances are nearly independent. Whenever many rare, nearly independent events have a total expected count of one, the number that occur is close to Poisson with mean one, and the chance that none occurs is close to $e^{-1}$. The hats and the games are two instances of the Poisson approximation to a sum of rare events, and the constant belongs to that approximation rather than to either problem.

The games converge more slowly than the hats. For hats the error after $n$ terms is factorially small, less than $1/(n+1)!$. For games the error is of order $1/n$, because the events are less independent. Two cells in the same row cannot both be equilibria, since the column player has only one best reply in each row. So the occurrences repel each other slightly, and the correction is the $1/(en)$ that the figure shows.

The whole distribution, not just the zero #

The same sums give the chance of exactly one, two or more pure equilibria.

At two strategies the distribution is lopsided: three-quarters of games have exactly one pure equilibrium, one in eight has none and one in eight has two. As $n$ grows the distribution spreads out towards the Poisson law, in which none and one are equally likely at $0.368$ each, two has chance $0.184$ and three $0.061$. Because the mean is pinned at one, every game with two or three pure equilibria has to be balanced by games with none. The growing chance of having none is the same fact as the growing chance of having several.

That is the first lesson of the random-game picture for anyone choosing among equilibria. A large random game has on average one pure equilibrium, but “on average one” means none in a third of games, exactly one in a third, and two or more in roughly a quarter. The equilibrium selection problem — which equilibrium will be played when there are several — arises in about a quarter of large random games through pure equilibria alone, before any mixed ones are counted.

What best-reply play does instead #

A game without a pure equilibrium is not a game without structure. Start anywhere and let the players take turns switching to their best reply. Because each player has exactly one best reply to each strategy of the other, the process is deterministic, and with finitely many cells it must eventually repeat. It ends in a cycle. A cycle of length two is a pure equilibrium; longer cycles are loops in which the players chase each other for ever, like matching pennies spread over more strategies.

The count of cycles follows the same arithmetic. A cycle through $k$ rows and $k$ columns needs $2k$ best replies to line up, and the expected number of such cycles is $(n)_k^2/(k\,n^{2k})$, which tends to $1/k$. At ten strategies the expected numbers are $1$, $0.405$, $0.173$ and $0.064$ for cycles of two, four, six and eight moves, and sampled games agree. In the limit the number of cycles of each length is Poisson with mean $1/k$, and the cycles of different lengths are independent.

This is the cycle structure of a random permutation, which has on average $1/k$ cycles of length $k$. The best replies are not a permutation — two columns can share a best row — but on the cycles the mapping is a permutation, and random mappings carry random permutations on their cycles. Best-reply dynamics in a random game reaches a pure equilibrium only if it starts in that equilibrium’s basin. The basins of the longer cycles are, on average, just as large.

Every shape of game #

Square games are a convenience. A game can give the two players different numbers of strategies, and the exact formula handles any shape.

The first row and column are all ones: if one player has a single strategy, the other simply replies to it, and that reply is a pure equilibrium. Everywhere else the chance drops quickly. Two strategies against two gives $0.875$; two against twelve gives $0.771$; twelve against twelve gives $0.665$. The limit is $1 - 1/e = 0.632$ whenever both $n$ and $m$ grow, and lopsided shapes approach it from slightly above.

The table also shows how little the second player’s size matters once the first is moderate. Along the row for three strategies the chance runs $0.83$, $0.79$, $0.76$, $0.75$ and then barely moves. The coincidences that create a pure equilibrium are spread evenly over the table, and a larger table offers more of them while making each one rarer in exact proportion.

Conflict removes pure equilibria, not randomness #

Independent payoffs are one end of a range. Draw the two players’ payoffs in each cell from a joint distribution with correlation $\rho$. At $\rho = 1$ they are paid the same, a game of pure common interest. At $\rho = -1$ one’s gain is the other’s loss, a zero-sum game. At $\rho = 0$ is the independent case above.

The curve falls monotonically from almost one to exactly zero. At $\rho = 1$ the cell with the largest shared payoff is a best reply for both players, so a common-interest game always has a pure equilibrium. At $\rho = -1$ a pure equilibrium is a cell that is the smallest in its row and the largest in its column of a single matrix — a saddle point — and the chance that a random six-by-six matrix has one is

$$\frac{6!\,6!}{11!} \approx 0.013,$$

a formula that counts orderings: of the $n + m - 1$ entries in a cell’s row and column, the cell must sit above the $n - 1$ others in its column and below the $m - 1$ others in its row, and at most one cell can do so. For larger zero-sum games the chance falls towards zero factorially fast. That is why the value from both sides needed mixed strategies to make maximin and minimax agree: in a zero-sum game, pure solutions are the rare exception.

So the third of random games without a pure equilibrium is not a fact about randomness alone. It is a fact about the balance of interests that independent payoffs represent. The more opposed the players’ interests, the more best replies chase each other in cycles. The more aligned, the more often they meet.

What the exact formula does not cover #

The formula assumes payoffs drawn independently from a continuous distribution, and two things lie outside it. Real games have ties, or structure that makes ties likely, such as payoffs that are small whole numbers, and with ties a cell can be a best reply jointly with others and the counting changes. And real games are rarely independent across cells. A game with an underlying potential, like the congestion games of the landscape nobody is looking at, always has a pure equilibrium, while independent random games have one only two times in three.

The figures also say nothing about mixed equilibria, which every game has. A random game with no pure equilibrium still has at least one mixed equilibrium by Nash’s theorem, and a random game with one pure equilibrium may have mixed ones as well. How many there are in total is a different and harder count, because mixed equilibria are not cells of a table but solutions of systems of equations, one system for each pair of strategy sets the players might mix over.

Still open: the structure behind the Poisson law #

For independent payoffs the pure-equilibrium count is understood exactly. The live questions are about games with dependence, which is what real games have. For random games on networks — each player’s payoff depending only on a few neighbours’ choices — the number of pure equilibria can grow exponentially with the number of players, and its distribution is known only in special cases. For random games with many players and few strategies each, the chance of a pure equilibrium tends to $1 - 1/e$ as well under independence, but with correlated payoffs or with payoffs from structured families the limit depends on the dependence in ways that are mapped only for particular models.

There is also a question about dynamics that the cycle count raises. In a large random game, how long does best-reply play take to reach its cycle, and what fraction of starting points reach a pure equilibrium rather than a loop? For random mappings the answer is classical — the typical path to a cycle has length of order $\sqrt n$ — but best-reply play has more than one form, simultaneous and alternating, and different update rules give different answers. Which rules reach equilibria most often in random games, and whether any simple rule reaches one whenever one exists, is studied and not settled.

One expected equilibrium, and a constant from the hat check #

A random payoff table has, on average, exactly one cell that is each player’s best reply to the other. It has none about a third of the time, with chance $\tfrac18$ at two strategies climbing to $1/e$ as the game grows. The mechanism is the same one that sends shuffled hats back to their owners, a sum of rare coincidences whose count tends to Poisson. When the cell is missing, best replies chase each other round cycles whose lengths follow the law of a random permutation. How many cells there are depends far more on how aligned the players’ interests are than on the size of the game. Pure equilibria are the common case in common-interest games and the rare case in zero-sum ones, and independent payoffs sit in between at exactly one on average. That middle position is the honest default for a game nobody designed, and the right baseline against which any designed game’s equilibria should be judged.