Basic Solution Concepts and the Complexity of Nash Equilibria

Motivation: why a computer scientist cares about equilibria

Game theory models situations in which multiple participants interact or affect each other’s outcomes. The Internet is such a situation at enormous scale: thousands of ISPs routing each other’s traffic, millions of traffic streams sharing links, buyers and sellers in automated markets. None of these agents is controlled by a central designer, and each acts in its own interest.

Two questions run through this note, and they pull against each other:

What is a stable outcome? We need solution concepts that formalize “no participant wants to unilaterally deviate.”
Can that outcome be found? A solution concept that no algorithm can compute is a poor prediction of what agents will do.

ImportantWhy computability is a modelling prerequisite

A Nash equilibrium is above all a conceptual tool — a prediction about rational strategic behaviour in a context devoid of computation. So why should complexity matter?

Because if an equilibrium concept is not efficiently computable, much of its credibility as a prediction of the behaviour of rational agents is lost. There is no clear reason why a group of agents cannot be simulated by a machine. In Kamal Jain’s words: “If your laptop cannot find it, neither can the market.”

(One might object that market agents work in parallel and so are more powerful than ordinary algorithms — but parallelism is no cure for exponential worst case.)

Classical games, and where they arise on the Internet

The Prisoner’s Dilemma

ExamplePrisoners’ dilemma

Two prisoners each choose to confess or remain silent. Both silent: the authorities cannot prove the charges and each serves 2 years for minor offenses. Only one confesses: his term drops to 1 year and he testifies against the other, who gets 5. Both confess: each gets a break for cooperating and serves 4 years rather than 5.

Cost matrix (row player’s cost, column player’s cost):

$P_1$ \ $P_2$	Confess	Silent
Confess	$4,\ 4$	$1,\ 5$
Silent	$5,\ 1$	$2,\ 2$

IntuitionThe tension

The only stable solution is that both confess: in each of the other three cases at least one player can switch from silent to confess and improve his own payoff. Yet a much better outcome for both is mutual silence — which is not stable even if carefully planned, since each player is tempted to defect and serve less time.

ExampleISP routing game — the same matrix

Two ISPs with separate networks exchange traffic through two peering points $C$ and $S$ . ISP 1 must send traffic from $s_1$ in its own domain to $t_1$ in ISP 2’s domain, and symmetrically for ISP 2.

ISPs behave selfishly: they send traffic to the closest peering point, since the ISP containing the destination must route it onward no matter where it enters. Peering point $C$ is closer — cost 1 to ISP 1 (one edge) versus 2 for the farther point $S$ . But $S$ is more directly on route: the total path through $C$ has length 4, through $S$ only 2.

So each ISP has two choices, one better selfishly ( $C$ ) but worse for the other player. With $C\ \leftrightarrow$ “confess” and $S\ \leftrightarrow$ “silent”, the cost matrix is exactly the Prisoner’s Dilemma.

flowchart LR
  s1["s1 (ISP 1)"] -->|cost 1| C[Peering C]
  s1 -->|cost 2| S[Peering S]
  C -->|long path| t1["t1 (ISP 2)"]
  S -->|short path| t1

Many players: pollution and the commons

ExamplePollution game — Prisoner’s Dilemma with $n$ players

Each of $n$ countries chooses whether to pass pollution-control legislation. Control costs 3 to the country; each country that pollutes adds 1 to the cost of all countries (health costs and so on). Note $3 \gg 1$ : the cost of being responsible far exceeds the cost one pays for another’s irresponsibility.

If $k$ countries do not control, each of them incurs cost $k$ , and each of the other $n-k$ incurs $k+3$ . The only stable solution is that nobody controls pollution, costing $n$ each — whereas universal control would cost only 3 each.

IntuitionWhat the games so far have in common

In both, there is a unique optimal selfish strategy independent of what others do. No matter the opponents’ play, each player is better off playing it. The next game breaks this: players’ optimal strategies depend on what others play.

ExampleTragedy of the commons — shared bandwidth

$n$ players share a channel of capacity 1. Player $i$ ‘s strategy is to send $x_i \in [0,1]$ units of flow — an infinite strategy set. If $\sum_j x_j \ge 1$ nobody gets any benefit; otherwise player $i$ ‘s value is

$x_i\left(1 - \sum_j x_j\right)$

capturing the trade-off: benefit grows with your own share but deteriorates as total bandwidth rises.

Solving for stability. Fix player $i$ and let $t = \sum_{j\ne i}x_j < 1$ . Sending $x$ yields $x(1-t-x)$ ; elementary calculus gives the optimum $x = (1-t)/2$ . A strategy vector is stable when all players play their optimal selfish strategy, i.e. $x_i = \left(1 - \sum_{j\ne i}x_j\right)/2$ for all $i$ , whose unique solution is

$x_i = \frac{1}{n+1} \quad \text{for all } i$

Why it is a tragedy. Player $i$ ‘s value is $x_i(1-\sum_{j\ne i}x_j) = 1/(n+1)^2$ , so the total over all players is $n/(n+1)^2 \approx 1/n$ . But if the total bandwidth used were $\sum_i x_i = 1/2$ the total value would be $1/4$ — roughly $n/4$ times bigger. The $n$ users overuse the common resource so badly that its total value collapses. The pollution game has the same character, with the environment as the overused commons and cost rising from 3 to $n$ .

Coordination and anticoordination

ExampleBattle of the sexes

A boy and a girl choose between a baseball game and a softball game. The boy prefers baseball, the girl softball, but both prefer being together. Payoffs (girl, boy):

Girl \ Boy	B	S
B	$5,\ 6$	$1,\ 1$
S	$2,\ 2$	$6,\ 5$

The two mismatched outcomes are not stable — either player can improve by switching. The two matched outcomes are both stable; the girl prefers one and the boy the other. This is a coordination game: multiple outcomes can be stable.

ExampleRouting congestion game — an anticoordination game

Two traffic streams originate at proxy node $O$ and must reach the network through connection points $A$ or $B$ , with $A$ slightly closer. Both points congest easily, so sending both streams through the same one causes extra delay. Cost matrix:

1 \ 2	A	B
A	$5,\ 5$	$1,\ 2$
B	$2,\ 1$	$6,\ 6$

Good outcomes here require routing on different paths — the mirror image of Battle of the Sexes, where good outcomes required attending the same game.

When no stable outcome exists

ExampleMatching pennies

Each player chooses heads or tails. The row player wins if the pennies match, the column player if they do not ( $1$ = win, $-1$ = loss):

1 \ 2	H	T
H	$1,\ -1$	$-1,\ 1$
T	$-1,\ 1$	$1,\ -1$

One can read this as a routing congestion variant in which the column player wants good service (different routes) while the row player wants only to disrupt him (same route). This game has no stable solution. Instead it seems best for players to randomize, to thwart the other’s strategy.

Formalizing a game

All the games above are one-shot simultaneous move games: all players simultaneously choose an action from their strategy set.

DefinitionSimultaneous move game

A set of $n$ players $\{1,\ldots,n\}$ ; each player $i$ has a strategy set $S_i$ , selects $s_i \in S_i$ , and we write $s = (s_1,\ldots,s_n)$ for the strategy vector and $S = \times_i S_i$ for the set of all of them.

The vector $s$ determines each player’s outcome. To specify the game we give, for each player, a preference ordering on outcomes: a complete, transitive, reflexive binary relation on $S$ . Player $i$ weakly prefers $S_1$ to $S_2$ if $i$ either prefers it or considers them equally good.

The simplest way to specify preferences is to assign a value to each outcome, as a payoff $u_i : S\to\mathbb{R}$ or a cost $c_i : S\to\mathbb{R}$ . These are interchangeable: $u_i(s) = -c_i(s)$ .

ImportantWhat makes this a game rather than $n$ optimization problems

Had we defined $u_i$ as a function of $s_i$ alone — player $i$ ‘s own strategy — we would have $n$ independent optimization problems. In a game, each player’s payoff depends not only on his own strategy but on the strategies chosen by all players. That coupling is the whole subject.

ConventionNotation for deviations

$s_{-i}$ denotes the $(n-1)$ -dimensional vector of strategies played by everyone except $i$ , so $u_i(s_i, s_{-i})$ is the same as $u_i(s)$ with player $i$ ‘s component made explicit. Similarly $s_A$ and $s_{-A}$ for a coalition $A$ .

Standard form versus compact representation

DefinitionStandard (matrix) form

Explicitly list all strategies and all utilities. Convenient for 2 players with few strategies each — as used above for the Prisoner’s Dilemma and Battle of the Sexes.

WarningStandard form is usually exponentially large

For most games we care about, the explicit representation is exponential in the natural description — possibly bigger, or infinite. Two separate reasons:

Many players. The pollution game has $n$ players with 2 strategies each, hence $2^n$ strategy vectors, though its description is tiny.
Many strategies per player. In routing games each player’s strategy space is all source–destination paths in the network. In the Tragedy of the Commons the strategy set is infinite, since any $x\in[0,1]$ is a strategy.

Compact representations exploit structure: the payoff may depend only on how many players choose each strategy rather than exactly which (the pollution game), or on the total load on each edge of a chosen path, or only on the strategies of a few neighbours rather than all participants (see and graphical-games).

Solution concepts

Dominant strategy solution

DefinitionDominant strategy solution

A strategy vector $s \in S$ is a dominant strategy solution if for each player $i$ and each alternate vector $s' \in S$ ,

$u_i(s_i, s'_{-i}) \ge u_i(s'_i, s'_{-i})$

i.e. each player has a unique best strategy independent of what the others do. The Prisoner’s Dilemma and the Pollution Game have this property.

WarningDominant does not mean good

A dominant strategy solution may not give an optimal payoff to any player — in both games above, all players’ payoffs can be improved simultaneously. Stability and efficiency are different things, and the gap between them is the subject of inefficiency-of-equilibria-introduction.

NoteVery few games have one — so we design games that do

Requiring a single dominant strategy per player is extremely stringent. Mechanism design (introduction-to-mechanism-design) turns this around: design games that have dominant strategy solutions leading to desirable outcomes.

Vickrey auction: designing for dominant strategies

ExampleSecond price auction

We must design an auction to sell a painting. Each bidder $i$ has value $v_i$ ; payoff 0 for not winning, $v_i - p$ for winning at price $p$ . Each player’s strategy is his sealed bid.

First price (highest bidder pays his bid) has no dominant strategy solution — a player’s best bid depends on what he believes about others. Deciding what to bid is a hard problem and may produce unpredictable behaviour (see ).

Vickrey’s mechanism awards the painting to the highest bidder but charges the second highest bid. This has the remarkable property that each player’s dominant strategy is to report his true value, independent of everyone else. Even with a very high true value he is in no danger of overpaying: if he wins, he pays no more than the second highest bid.

ImportantTwo further properties

Socially optimal outcome. The painting goes to the bidder who values it most. This is often the larger goal: when governments auction wireless spectrum, the aim is typically not maximum profit but getting the spectrum to the companies with the best technology.
Simplicity of play. In a dominant strategy game each player’s optimal strategy is independent of others’ choices, so one can implement any such game by asking all players for their valuation functions and letting the designer play on their behalf — the revelation principle.

CautionLimits of direct revelation

Valuation functions can be very complex, so direct revelation may require extensive, possibly exponential, communication. Direct revelation mechanisms also assume a central trusted party — cryptographic techniques let a group implement such a mechanism without one (see cryptography-and-game-theory).

Pure Nash equilibrium

DefinitionNash equilibrium

A strategy vector $s \in S$ is a Nash equilibrium if for all players $i$ and all alternates $s_i' \in S_i$ ,

$u_i(s_i, s_{-i}) \ge u_i(s_i', s_{-i})$

No player can improve his payoff by changing his own strategy, assuming all others stick to theirs.

IntuitionSelf-enforcing

Once the players are playing such a solution, it is in every player’s interest to stick to his strategy. This formalizes the stability we used informally in the Tragedy of the Commons and the Battle of the Sexes.

NoteRelation to dominant strategies

A dominant strategy solution is a Nash equilibrium, and if it is strictly dominating it is the unique one. But Nash equilibria need not be unique — coordination games have several.

WarningMultiplicity undermines prediction

Since dominant strategy solutions are Nash equilibria, Nash equilibria need not be optimal for the players. Worse, with multiple equilibria the payoffs can differ widely: a small change to the Battle of the Sexes payoffs leaves two stable solutions with one far better for both.

This makes Nash less convincing as a prediction: which equilibrium should we expect, and with independent play, how would players know which one to coordinate on? At least each is stable once proposed.

Mixed strategy Nash equilibrium

DefinitionMixed strategy

Enhance each player’s choices so he may pick a probability distribution over his strategy set. Players select independently, inducing a distribution over strategy vectors.

NoteRisk neutrality is an assumption

When outcomes are random, how does a player evaluate them? Would he prefer a small positive utility with high probability over a small chance of a large loss? For mixed Nash equilibrium we assume players are risk-neutral: they maximize expected payoff.

TheoremNash (1951)

Any game with a finite set of players, each having a finite set of strategies, has a Nash equilibrium of mixed strategies.

ExampleMatching pennies, resolved

With each player picking each strategy with probability $1/2$ , the expected payoff of each is 0 and neither can improve by a different randomization — a stable solution where no pure one existed.

WarningBoth finiteness hypotheses matter

Games with infinitely many players, or finitely many players with infinite strategy sets, may have no Nash equilibrium.

ExamplePricing game with no equilibrium, pure or mixed

Two sellers face three buyers. Buyers $A$ and $C$ can reach only seller 1 and seller 2 respectively; buyer $B$ can buy from either. All buyers want one unit and have budget (max value) 1. Sellers name prices $p_i \in [0,1]$ ; $B$ buys from the cheaper, ties going to seller 1. No production costs, and sellers may not price-discriminate — one price per seller. Each player has uncountably many strategies.

No pure equilibrium. If $p_1 > 1/2$ , seller 2 undercuts with $1/2 < p_2 < p_1$ , earning more than 1 (both buyers); then seller 1 undercuts, and so on — so no equilibrium has $p_1 > 1/2$ . If $p_1 \le 1/2$ , seller 2’s unique best response is $p_2 = 1$ (abandon $B$ , milk $C$ ); but then seller 1 raises his price. So $p_1 \le 1/2$ fails too.

It is harder to argue, but there is no mixed equilibrium either.

Correlated equilibrium

ExampleTraffic light

Two drivers reach an intersection simultaneously. Crossing successfully pays 1, not crossing pays 0, and a crash costs $-100$ :

1 \ 2	Cross	Stop
Cross	$-100,\ -100$	$1,\ 0$
Stop	$0,\ 1$	$0,\ 0$

Three Nash equilibria: two letting exactly one car cross (payoff 1 each), and a mixed one in which both cross with probability $\epsilon = 1/101$ and crash with probability $\epsilon^2$ . The first two are efficient but unfair; the third is fair but has low expected payoff ( $\approx 0.0001$ ) and a positive chance of a crash.

ImportantWhat correlation buys

In a Nash equilibrium players choose independently. In a correlated equilibrium a coordinator chooses strategies for both — but the chosen strategies must still be stable: each player must find it in his interest to follow the recommendation. Here the coordinator can randomly let one car cross; the one told to stop has payoff 0, but knows that crossing would cause a crash. A traffic light is a correlation device.

DefinitionCorrelated equilibrium (Aumann 1959)

A probability distribution $p(s)$ over strategy vectors $s \in \times_i S_i$ such that for all players $i$ and all $s_i, s_i' \in S_i$ ,

$\sum_{s_{-i}} p(s_i, s_{-i})\,u_i(s_i, s_{-i}) \;\ge\; \sum_{s_{-i}} p(s_i, s_{-i})\,u_i(s_i', s_{-i})$

In words: if player $i$ receives suggested strategy $s_i$ , his expected profit cannot be increased by switching to some $s_i'$ .

NoteNash is the uncorrelated special case

Nash equilibria are exactly the correlated equilibria whose distribution over $S$ is a product of independent per-player distributions. Correlation allows a strictly richer set of equilibria — and, as we will see, a computationally far friendlier one.

Computing equilibria: the two-player zero-sum case

DefinitionZero-sum game

A two-player game is zero-sum if the payoffs sum to zero for every strategy choice. It suffices to give the row player’s payoff matrix $A$ : his winnings and the column player’s loss.

Let $p^*, q^*$ be a Nash equilibrium pair of distributions, with value $v^* = p^*Aq^*$ (row vector times matrix times column vector).

IntuitionThe key property: equilibria survive being announced

A Nash equilibrium is stable even if the players know each other’s distributions. So consider the row player publicly announcing a mixed strategy $p$ . The column player’s expected payoffs across his strategies are the entries of $pA$ , and he will play where that is minimized. The row player should therefore maximize that minimum — and this is a linear program.

FormulaThe two linear programs

Row player’s maximum safe value:

$v_r = \max v \quad \text{s.t.}\quad p \ge 0,\ \ \sum_i p_i = 1,\ \ (pA)_j \ge v \ \text{ for all } j$

Column player’s minimum safe value:

$v_c = \min v \quad \text{s.t.}\quad q \ge 0,\ \ \sum_j q_j = 1,\ \ (Aq)_i \le v \ \text{ for all } i$

DerivationWhy

v_r = v^* = v_c

Clearly $v_r \le v^*$ : the row player can guarantee $v_r$ , so he must win at least that much in any equilibrium. Conversely, an equilibrium is stable even if known to the opponent, so the column player must in fact be selecting the columns with minimum value in $p^*A$ — giving $v^* \le v_r$ . Hence $v_r = v^*$ , and the symmetric argument gives $v^* = v_c$ .

TheoremMinimax

Optimum solutions to the pair of linear programs above give probability distributions forming a Nash equilibrium of the two-person zero-sum game.

ProofNeither player can move

Let $p, q$ be optima; we argued $v_c = v_r$ . Playing this pair, the row player cannot increase his win because the column player’s strategy guarantees he loses no more than $v_c$ ; the column player cannot decrease his loss because the row player’s strategy guarantees winning $v_r$ . So the pair is at equilibrium.

∎

RemarkTwo routes to the same fact

The two programs are LP duals of each other. We established $v_r = v_c$ using the existence of a Nash equilibrium (Nash’s theorem); linear programming duality also implies it directly — which yields an independent proof that Nash equilibria exist in the zero-sum two-player case, without Brouwer.

Best response dynamics and learning

DefinitionImproving and best response

Given $s$ and player $i$ , a change from $s_i$ to $s_i'$ is an improving response if $u_i(s_i', s_{-i}) > u_i(s)$ , and a best response if $s_i'$ maximizes $\max_{s_i'\in S_i} u_i(s_i', s_{-i})$ . Repeatedly letting some player make an improving or best response move is perhaps the most natural game play.

Game	Behaviour of best-response dynamics
Prisoner’s Dilemma, coordination game	Reaches a Nash equilibrium in a few steps
Tragedy of the Commons	Never reaches it in finitely many steps, but converges to it
Matching pennies	Cycles through all 4 strategy vectors forever

IntuitionCycling can still be convergence of a sort

In matching pennies no pure equilibrium exists, yet the average payoff converges to 0 — the equilibrium payoff — and the frequencies with which the four strategy vectors are played converge to the equilibrium probabilities ( $1/4$ each).

NoteWhat is actually provable

Best-response behaviour is not strong enough to guarantee convergence in most games. Instead one considers improving-response “learning” strategies that react to the frequencies played so far rather than only the current play. For two-player zero-sum games such play does converge to Nash. In general, learning strategies do not converge to Nash equilibria — they converge to the larger region of correlated equilibria. See learning-and-regret-minimization.

Games with turns and subgame perfection

Many games have multiple turns: card and board games, but also economic situations (a provider sets up a service at turn 1; users decide whether to use it at turn 2).

ImportantReducing turns to simultaneous moves, and what breaks

We can reduce such a game to a simultaneous-move game by having each player select a full strategy up front — a strategy for each turn, as a function of the state of the game. These get enormous: a full strategy for chess specifies a move for every possible sequence of previous moves. Games with turns are another example of a compactly represented game.

In this reduction the notion of Nash equilibrium becomes too weak, because the asymmetry between the players created by the order of moves is diminished.

ExampleUltimatum game

Seller $S$ offers a price $p$ ; buyer $B$ then reacts. The seller values the good at 0, so his payoff is $p$ on a sale and 0 otherwise; the buyer has value $v$ , so his payoff is $v - p$ if he buys and 0 if not. Under full information (the seller knows $v$ ) we expect the seller to offer just under $v$ and the buyer to buy: the first player leads and collects almost all the profit.

But there are many other Nash equilibria. The buyer’s strategy is a function of the offered price. “Buy if the price is under $v$ ” is one equilibrium. But so is “buy only if $p \le m$ ” for any $m \le v$ : it looks bad (why leave $v-p$ on the table when $m < p < v$ ?), yet given that buyer strategy, the seller’s best move is to offer exactly $m$ , since anything higher earns nothing. This pair is a Nash equilibrium for every $m$ .

DefinitionSubgame perfect equilibrium

Strengthens Nash by making the order of turns part of the definition: require that the strategy played is Nash even after any prefix of the game has already been played. This rules out the unnatural “buy only at $p\le m$ ” threats, which are not credible once the price is actually on the table.

NoteWhere the machinery is

The formal model of a game with turns — the extensive form, with information sets modelling imperfect information — together with the algorithm for computing subgame perfect equilibria and the sequence form that avoids the exponential blowup of the strategic form, is developed in below.

Bayesian games

ImportantLimited information about other players

One source of limited information is not knowing other players’ properties and preferences, hence not knowing what strategies they will select. Think of bridge: players know the probability distribution of others’ cards but not the cards.

ExampleBayesian first price auction

In a first price auction all players bid, the highest wins and pays his bid. If valuations were common knowledge, the highest-value player would bid the second valuation and win at (essentially) the second-price outcome. But how should players bid without knowing others’ valuations? Their bids now depend on their beliefs.

In the standard setup, players draw valuations from independent distributions that are themselves public knowledge. When the distributions are independent and identical, the unique Nash equilibrium is a pleasing analogue of the second price auction: player $i$ with valuation $v_i$ bids the expected second valuation conditioned on $v_i$ being the maximum.

Cooperative games

Everything so far was non-cooperative: players deviate alone, and do not coordinate their moves in groups. Cooperative game theory concerns groups that coordinate.

Strong Nash equilibrium

DefinitionStrong Nash equilibrium (Aumann 1974)

Here utility is nontransferable, so for a coalition to be happy the utility of each member must not decrease. For a strategy vector $s$ and a set $A$ of players, a joint deviation is a vector $s'_A$ with $u_i(s) \le u_i(s'_A, s_{-A})$ for all $i\in A$ and strict for at least one. A strategy vector is strong Nash if no subset $A$ has a joint deviation.

WarningVery appealing, very rare

Strong Nash equilibria have a very strong reinforcing property — and very few games have them. A nice exception is the game version of the stable marriage problem, where the natural deviation is a pair who prefer each other to their current partners (mechanism-design-without-money). Coalitions of size 2 are also the natural unit of instability in network-formation-games.

Transferable utility: core and Shapley value

With transferable utility, the game becomes one of dividing a value or sharing a cost and the concern is fairness. Let $N$ be $n$ players and let each subset $A$ have cost $c(A)$ (or value $v(A)$ ). A cost-sharing assigns shares $x_i$ , required to be budget balanced: $\sum_{i\in N}x_i = c(N)$ .

DefinitionThe core

A cost-share vector is in the core if no subset would decrease its shares by breaking away:

$\sum_{i\in A} x_i \le c(A) \qquad \text{for all sets } A$

A violation of this inequality corresponds exactly to a set $A$ that benefits by seceding.

NoteThe algorithmic questions

Given $c$ , is there a cost-sharing in the core? How hard is it to find one, and to decide whether the core is nonempty? Both have been studied extensively for fundamental games. If the core is empty or intractable, one can relax the notion so that subsets secede only on substantial gains. See cost-sharing.

DefinitionShapley value

Based on marginal costs. Ordering $N$ as $1,\ldots,n$ and writing $N_i = \{1,\ldots,i\}$ , player $i$ ‘s marginal cost is $c(N_i) - c(N_{i-1})$ — which of course depends on the order. The Shapley value assigns to $i$ the expected marginal cost over a uniformly random order of the players.

RemarkExistence versus core membership

One advantage of the Shapley value is that it always exists; however, it may not be in the core, even for games whose core is nonempty. It can be characterized as the unique cost-sharing scheme satisfying several different sets of axioms.

Markets and their algorithmic issues

[!MOTIVATION] Why general equilibrium theory needs an algorithmic version In a capitalist economy, crucial regulatory functions — stability, efficiency, fairness — are relegated to pricing mechanisms with little intervention, which is why general equilibrium theory occupies a central place in mathematical economics. From our viewpoint its shortcoming is that it is mostly a nonalgorithmic theory. With numerous new Internet markets and massive computational power available to run them, there is a need for an inherently algorithmic theory of market equilibria — which can also predict the repercussions of technological advances, new goods, or tax changes.

NoteThe classical result and the modern approach

Central to price stability is parity between demand and supply. With one good the equilibrium price is where the demand and supply curves intersect, and deviations are pushed back by market forces. The celebrated Arrow–Debreu theorem (1954) shows equilibrium prices exist in a very general model with multiple goods and agents.

Equilibria for several fundamental market models are optimal solutions to nonlinear convex programs, suggesting two algorithmic approaches: combinatorial algorithms, and convex-programming methods. See computing-market-equilibria.

An algorithm for a simple market

Setup. Divisible goods $A$ and buyers $B$ . Buyer $i$ has money $m_i \in \mathbb{Z}_+$ ; good $j$ is available in amount $a_j\in\mathbb{Z}_+$ . Buyer $i$ can access only a subset $S_i \subseteq A$ , is indifferent among goods in $S_i$ , and wants to maximize the total amount obtained. (An example: identical goods sold in different markets, each buyer reaching only some.) WLOG all $m_i \ne 0$ , $a_j \ne 0$ , each $S_i \ne \emptyset$ , and each good is wanted by someone.

Once prices are fixed, buyer $i$ is interested only in the cheapest goods in $S_i$ , say $S_i'$ ; any allocation from $S_i'$ exhausting her money is an optimal basket. Prices are market clearing if each buyer can be assigned an optimal basket with no surplus or deficiency of any good. For this market equilibrium prices are unique.

DefinitionNotation

Bipartite graph $G = (A,B,E)$ with edge $(j,i)$ when $j \in S_i$ ; by assumption every vertex has nonzero degree. For $S\subseteq A$ , $a(S) = \sum_{j\in S}a_j$ ; for $T\subseteq B$ , $m(T) = \sum_{i\in T}m_i$ . The neighbourhood $\Gamma(S) = \{i \in B \mid S_i \cap S \ne \emptyset\}$ .

A uniform price $x$ is feasible if

$\forall S \subseteq A, \quad x\cdot a(S) \le m(\Gamma(S))$

and a set $S$ is tight (w.r.t. feasible $x$ ) if $x\cdot a(S) = m(\Gamma(S))$ .

LemmaFeasibility characterizes sellability

A uniform price $x$ on all goods is feasible if and only if all goods can be sold so that each buyer gets goods she is interested in.

ProofMax-flow min-cut

( $\Rightarrow$ direction, easy) If $x\cdot a(S) > m(\Gamma(S))$ for some $S$ , the goods in $S$ cannot all be sold at price $x$ — the interested buyers simply lack the money.

( $\Leftarrow$ ) Build network $N$ : direct the edges of $G$ from $A$ to $B$ with infinite capacity; add source $s$ with edges to each $j\in A$ of capacity $x\cdot a_j$ ; add sink $t$ with edges from each $i \in B$ of capacity $m_i$ . Selling all goods corresponds to a feasible flow saturating all edges out of $s$ .

Suppose no such flow exists. By max-flow min-cut the minimum cut has capacity below $x\cdot a(A)$ . Let $S$ be the goods on the $s$ -side. Since edges $(j,i)$ for $j\in S$ have infinite capacity, $\Gamma(S)$ must also be on the $s$ -side, so the cut capacity is at least $x\cdot a(A-S) + m(\Gamma(S))$ . If that is less than $x\cdot a(A)$ then $x\cdot a(S) > m(\Gamma(S))$ , contradicting feasibility.

∎

ImportantThe algorithm

If a set $S$ is tight, then selling all of $S$ exactly exhausts the money of $\Gamma(S)$ — so $x$ is a market clearing price for the goods in $S$ . The idea is to find such a set, allocate, and recurse.

Start at $x = 0$ (trivially feasible) and raise $x$ continuously, maintaining feasibility, until a nonempty set goes tight. Let $x^*$ be the smallest such $x$ and $S^*$ the maximal tight set (which is unique).
Finding them: $x^*$ is the largest $x$ at which $(s,\ A\cup B\cup t)$ remains a min-cut in $N$ , so binary search works. Then compute the set $W$ of nodes reaching $t$ in the residual graph — the $t$ -side of the maximal min-cut — and set $S^* = A - W$ .
Fix the prices of $S^*$ at $x^*$ , compute a max-flow at $x = x^*$ , and use it to allocate $S^*$ to $\Gamma(S^*)$ , spending all of $m(\Gamma(S^*))$ .
Remove $S^*$ and $\Gamma(S^*)$ , initialize the remaining prices to $x^*$ , and raise until a new set goes tight. Terminate when all goods are priced.

LemmaThe recursion is well posed

$x^*$ is feasible for the problem restricted to $A - S^*$ and $B - \Gamma(S^*)$ , and in the induced subgraph all vertices have nonzero degree.

ProofFlow through the remaining goods must exit through the remaining buyers

In the max-flow at $x = x^*$ , the flow through $S^*$ completely uses up the capacity of the edges from $\Gamma(S^*)$ to $t$ . So all flow through $A - S^*$ must exit via $B - \Gamma(S^*)$ , and the first claim follows from the previous lemma. A good $j \in A-S^*$ must have nonzero degree into $B - \Gamma(S^*)$ ; and each buyer $i \in B - \Gamma(S^*)$ has nonzero degree in $G$ with no edges to $S^*$ , hence nonzero degree into $A - S^*$ .

∎

TheoremCorrectness and running time

The algorithm computes equilibrium prices and allocations in polynomial time.

ProofMonotone prices across iterations

At termination all goods are priced and hence fully sold, and by the second claim of the lemma every buyer lies in the neighbourhood of some tight set found, so every buyer is allocated goods for her money.

Each buyer gets an optimal bundle. Since $S^*$ was the maximal tight set at $x^*$ , prices must strictly rise before a new set goes tight — so prices are monotone increasing across iterations and every good in $A - S^*$ is priced above $x^*$ . Hence each buyer in $\Gamma(S^*)$ , allocated only from $S^*$ , received the cheapest goods available to her. Induction completes the argument.

Time. At most $\lvert A\rvert$ iterations, each dominated by finding $x^*$ and $S^*$ . Since $x^* = m(\Gamma(S^*))/a(S^*)$ has polynomial-sized integer numerator and denominator, the binary search takes polynomial time.

∎

Bimatrix games and the best response condition

Define NASH to be: given a game in strategic form, find a Nash equilibrium. Since it calls for a real-valued distribution per player, it looks prima facie like a problem in continuous mathematics. A little thought shows it is essentially combinatorial.

ConventionNotation for two-player games

Let $(A,B)$ be a bimatrix game: $A$ and $B$ are $m\times n$ payoff matrices to the row player 1 and column player 2, who simultaneously choose a row $i$ and a column $j$ and receive $a_{ij}$ and $b_{ij}$ .

Payoffs are risk-neutral utilities, so preferences are invariant under positive-affine transformations — hence $A$ and $B$ may be assumed nonnegative with rational (or integer) entries when they are algorithmic input. All vectors are column vectors; $\mathbf{0}$ is all-zeros, $\mathbf{1}$ all-ones, and inequalities like $x\ge0$ hold componentwise.

It is useful to keep the two pure strategy sets disjoint:

$M = \{1,\ldots,m\}, \qquad N = \{m+1,\ldots,m+n\}$

so $x \in \mathbb{R}^M$ , $y\in\mathbb{R}^N$ and $A, B \in \mathbb{R}^{M\times N}$ . The support of a mixed strategy is the set of pure strategies with positive probability.

TheoremBest response condition

Let $x,y$ be mixed strategies. Then $x$ is a best response to $y$ if and only if for all $i \in M$ ,

$x_i > 0 \implies (Ay)_i = u = \max\{(Ay)_k \mid k \in M\}$

ProofThe payoff is the maximum minus a sum of non-negative losses

$(Ay)_i$ is player 1’s expected payoff when playing row $i$ . Then

$x^\top Ay = \sum_{i\in M} x_i (Ay)_i = \sum_{i\in M} x_i\big(u - (u - (Ay)_i)\big) = u - \sum_{i\in M} x_i\big(u - (Ay)_i\big)$

So $x^\top Ay \le u$ , since $x_i \ge 0$ and $u - (Ay)_i \ge 0$ for all $i$ ; and $x^\top Ay = u$ iff $x_i > 0$ implies $(Ay)_i = u$ .

∎

IntuitionTwo readings of the same fact

Geometric: $x^\top Ay$ is linear in $x$ , so if it is maximized on a face of the simplex of mixed strategies it is maximized on every vertex (pure strategy) of that face, and hence on every convex combination of them.

Algorithmic: it states a finite, easily checked condition about the player’s pure strategies rather than about the infinite set of mixed strategies. All pure strategies in the support must have maximum, and hence equal, expected payoff — which gives equations for the opponent’s probabilities.

IntuitionThe subtle nature of mixing

Players combine pure best responses — instead of just playing one of them, for the same utility — in order to create for the other players a range of best responses that will sustain the equilibrium. You do not randomize for your own sake; you randomize to keep your opponent indifferent.

A worked $3\times2$ example

ExampleThe running example

$A = \begin{bmatrix}3&3\\2&5\\0&6\end{bmatrix}, \qquad B = \begin{bmatrix}3&2\\2&6\\3&1\end{bmatrix}$

with $M = \{1,2,3\}$ and $N = \{4,5\}$ .

Pure equilibrium. Row 1 together with column 4 — i.e. $\big((1,0,0)^\top, (1,0)^\top\big)$ , a support of size 1 each.

Why any other equilibrium must be mixed on both sides. Every pure strategy of a player has a unique pure best response of the other, so in any other equilibrium each player mixes at least two pure strategies.

DerivationThe two mixed equilibria, and one support pair that fails

Support $\{1,2\}$ for player 1. Player 1 makes player 2 indifferent by solving $x_1 + x_2 = 1$ and $3x_1 + 2x_2 = 2x_1 + 6x_2$ , giving $x = (4/5, 1/5)$ . In turn player 2 must make player 1 indifferent between rows 1 and 2: $3y_4 + 3y_5 = 2y_4 + 5y_5$ , giving $(y_4,y_5) = (2/3,1/3)$ . Then $Ay = (3,3,2)^\top$ , so the best response condition holds — row 3 is not a best response and correctly has probability 0.

Support $\{2,3\}$ . A second equilibrium is $(x,y) = \big((0,1/3,2/3)^\top, (1/3,2/3)^\top\big)$ with $x^\top B = (8/3,8/3)$ and $Ay = (3,4,4)^\top$ . Again the support contains only rows where $(Ay)_i$ is maximal.

Support $\{1,3\}$ fails, for two separate reasons. Player 2 would need $y = (1/2,1/2)$ to equalize rows 1 and 3 — but then $Ay = (3, 7/2, 3)^\top$ , so rows 1 and 3 tie without being maximal. And making player 2 indifferent via $3x_1 + 3x_3 = 2x_1 + x_3$ with $x_1 + x_3 = 1$ gives $x_1 = 2$ , $x_3 = -1$ — not a probability vector.

Nondegeneracy and support enumeration

DefinitionNondegenerate game

A two-player game is nondegenerate if no mixed strategy of support size $k$ has more than $k$ pure best responses. (Violated, for instance, if some pure strategy has two pure best responses.)

CorollaryEqual support sizes

In any Nash equilibrium $(x,y)$ of a nondegenerate bimatrix game, $x$ and $y$ have supports of equal size — immediate from the best response condition.

IntuitionWhy support testing can restrict to equal sizes

In the example, we need not consider an $x$ giving all three rows positive probability, since player 1 would have to be indifferent among all three. But $y$ is already uniquely determined by equalizing two rows, after which the third row’s payoff differs. That is the typical, nondegenerate case.

AlgorithmEquilibria by support enumeration

Input: a nondegenerate bimatrix game. Output: all Nash equilibria.

For each $k = 1,\ldots,\min\{m,n\}$ and each pair $(I,J)$ of $k$ -sized subsets of $M$ and $N$ , solve

$\sum_{i\in I} x_i b_{ij} = v \ (j\in J), \quad \sum_{i\in I}x_i = 1, \quad \sum_{j\in J} a_{ij}y_j = u \ (i \in I), \quad \sum_{j\in J}y_j = 1$

and check $x \ge 0$ , $y\ge0$ and the best response condition for both.

NoteWhen the equations misbehave

No solution means no equilibrium for that support pair. Nonunique solutions occur only for degenerate games, since a linear dependency would let us shrink the support — see .

Supports in general, and the rationality divide

ImportantNASH is a search for supports

Once one support per player is identified, the mixed strategies follow by solving algebraic equations (linear, for two players): for each player $i$ with support size $k_i$ we have $k_i$ variables, one equation saying they sum to 1, and $k_i - 1$ equations saying the $k_i$ expected utilities are equal. Solving $\sum_i k_i$ equations in $\sum_i k_i$ unknowns yields the probabilities; if they are real, nonnegative, and the utility expectation is maximized at the support, we have a Nash equilibrium.

ExampleA symmetric $3\times3$ game

A game is symmetric if $B = A^\top$ . Take

$A = \begin{pmatrix} 0 & 3 & 0 \\ 0 & 0 & 3 \\ 2 & 2 & 2\end{pmatrix}$

Consider both players playing $(0, 1/3, 2/3)$ — a symmetric equilibrium. (A variant of Nash’s proof shows every symmetric game, with any number of players, has a symmetric equilibrium; it may have non-symmetric ones too.) Against that mix the utilities of the three strategies are $1, 2, 2$ , so every strategy in the support (2 and 3) is a best response and this is indeed a Nash equilibrium.

The oddity: from player 1’s point of view, playing just 2, or just 3, or any mixture, is equally beneficial. The only advantage of the precise mix $(0,1/3,2/3)$ is that it motivates the other player to do the same.

NoteTwo players are special: rationality

With integer utilities (as makes sense computationally), two-player equilibria necessarily have rational probabilities, being solutions of linear systems with integer coefficients. This fails in general: Nash’s original paper includes a beautiful three-player poker game whose only equilibrium is irrational. This distinction resurfaces at every stage below — most sharply in .

NoteWhy two players are tractable at all

Two-player games can be studied with polyhedra, because each player’s expected payoffs are linear in the other player’s mixed strategy probabilities. With three or more players the expected payoffs are products of the others’ probabilities, giving polynomial equations that need entirely different methods.

Most algorithms proposed over the past half century are combinatorial and work by seeking supports — and none is known to be efficient.

Is NASH NP-complete?

WarningNo — and the reason is instructive

NASH is a very different kind of intractable problem, for which NP-completeness is the wrong concept. The basic reason: every game is guaranteed to have a Nash equilibrium. In a typical NP-complete problem such as satisfiability, the sought solution may or may not exist, and NP-complete problems owe much of their difficulty and their susceptibility to reductions to precisely that dichotomy.

ProofWhy a reduction from SAT would collapse NP and coNP

Suppose NASH were NP-complete via a reduction from satisfiability: an efficiently computable $f$ mapping formulae to games such that $\varphi$ is satisfiable iff any Nash equilibrium of $f(\varphi)$ satisfies some easy-to-check property $\Pi$ . Then given any unsatisfiable $\varphi$ we could guess a Nash equilibrium of $f(\varphi)$ and check that it fails $\Pi$ — an NP certificate for unsatisfiability, implying $\text{NP} = \text{coNP}$ .

∎

NoteWhy the TSP is not a counterexample

The travelling salesman problem always has a solution too, but that solution (the optimum tour) is hard to verify. To enter the realm of NP-completeness such optimization problems are first turned into decision problems — “is there a tour of length $\le B$ ?” — which is much closer to satisfiability.

NASH versus Brouwer

ImportantExistence comes from a nonconstructive theorem

Nash’s proof reduces the existence of a mixed equilibrium to Brouwer’s fixpoint theorem: every continuous $f$ from the $n$ -dimensional unit ball to itself has a point with $f(x) = x$ . Brouwer’s theorem is well known for its nonconstructive nature, and finding a Brouwer fixpoint is itself a hard problem — again in the specialized sense, since a solution is guaranteed there too.

Is there a reduction in the opposite direction, making NASH exactly as hard as finding a Brouwer fixpoint? Yes — and that is a useful alternative way of understanding the main result of this note.

Generalizations are NP-complete

TheoremGilboa and Zemel (1989)

The following are NP-complete, even for symmetric two-player games in strategic form. Does the game have

at least two Nash equilibria?
a Nash equilibrium in which player 1 has utility at least a given amount?
a Nash equilibrium in which the two players have total utility at least a given amount?
a Nash equilibrium with support of size greater than a given number?
a Nash equilibrium whose support contains strategy $s$ ?
a Nash equilibrium whose support does not contain $s$ ? — and so on.

ProofSketch (Conitzer and Sandholm 2003)

Reduction from satisfiability. Construct a symmetric game whose strategies are all literals and whose Nash equilibria are all truth assignments: choosing for each of the $n$ variables either it or its negation and playing it with probability $1/n$ gives a symmetric equilibrium, and all equilibria are of this sort. Add a new pure equilibrium $(d,d)$ with lower utility, where $d$ is a default strategy. Then add one strategy per clause, such that the strategy for clause $C$ is attractive against a given truth assignment only if all three literals of $C$ are contradicted. Once a clause becomes attractive it destroys the assignment equilibrium and makes play drift to $(d,d)$ . The equilibria of the resulting game are precisely $(d,d)$ plus all satisfying assignments, from which every item above follows easily.

∎

IntuitionThe pattern

Twist NASH in any way that deprives it of its existence guarantee and NP-completeness comes into play almost immediately. The guaranteed existence is exactly what shields the pure search problem from this theory — and exactly what forces us to a different complexity class.

Equilibria via labeled polytopes

Support enumeration is crude. To identify the possible supports systematically we use best response polytopes, which express the best-response inequalities and the nonnegativity constraints directly.

DefinitionPolyhedral vocabulary

An affine combination of $z_1,\ldots,z_k$ is $\sum_i z_i\lambda_i$ with $\sum_i\lambda_i = 1$ ; a convex combination additionally has $\lambda_i\ge0$ . Points are affinely independent if none is an affine combination of the others; a convex set has dimension $d$ iff it has $d+1$ , but no more, affinely independent points.

A polyhedron in $\mathbb{R}^d$ is $\{z \mid Cz \le q\}$ ; it is full-dimensional if it has dimension $d$ , and a polytope if bounded. A face is $\{z\in P \mid c^\top z = q_0\}$ where $c^\top z\le q_0$ holds throughout $P$ ; a vertex is the unique element of a 0-dimensional face, an edge a 1-dimensional face, a facet a face of dimension $d-1$ .

Any nonempty face is obtained by turning some defining inequalities into equalities — the binding inequalities. A facet is characterized by a single irredundant binding inequality (one that cannot be dropped without changing the polyhedron). $P$ is simple if no point lies on more than $d$ facets.

The best response polyhedra

FormulaBest response polyhedra

$P = \{(x,v) \in \mathbb{R}^M\times\mathbb{R} \mid x \ge 0,\ \mathbf{1}^\top x = 1,\ B^\top x \le \mathbf{1}v\}$ $Q = \{(y,u) \in \mathbb{R}^N\times\mathbb{R} \mid Ay \le \mathbf{1}u,\ y\ge0,\ \mathbf{1}^\top y = 1\}$

IntuitionThe upper envelope

$Q$ is the set of player 2’s mixed strategies together with the upper envelope of expected payoffs to player 1: the inequalities $Ay \le \mathbf{1}u$ say $u$ is at least the expected payoff of each pure strategy of player 1, and $y\ge0$ , $\mathbf{1}^\top y = 1$ say $y$ is a probability vector.

For the running example, $Q$ is the set of triples $(y_4,y_5,u)$ with $3y_4 + 3y_5 \le u$ , $2y_4+5y_5\le u$ , $0y_4+6y_5\le u$ , $y\ge0$ , $y_4+y_5=1$ . Its facets are labelled either by player 1’s strategies $i\in M$ — indicating his best responses and payoff, e.g. row 1 is a best response when $y_4 \ge 2/3$ — or by player 2’s own strategies $j\in N$ , indicating $y_j = 0$ .

DefinitionLabels

A point $(y,u)$ of $Q$ has label $k \in M\cup N$ if the $k$ th defining inequality is binding: for $k = i\in M$ that is $\sum_{j\in N}a_{ij}y_j = u$ (meaning $i$ is a best response to $y$ ), and for $k = j \in N$ it is $y_j = 0$ . Correspondingly $(x,v) \in P$ has label $i\in M$ if $x_i = 0$ , and label $j\in N$ if $\sum_{i\in M}b_{ij}x_i = v$ .

A pair is completely labeled if every label in $M\cup N$ appears on one side or the other.

ImportantCompletely labeled $=$ Nash equilibrium

A missing label would mean a pure strategy — say $i$ of player 1 — that does not have probability zero ( $x_i > 0$ ) and is not a best response ( $\sum_j a_{ij}y_j < u$ ), since inequality $i$ is binding in neither polyhedron. That is exactly a violation of the best response condition. Conversely, if every label appears, each pure strategy is either a best response or has probability zero — so $x$ and $y$ are mutual best responses.

Normalizing away the payoff variables

DerivationDividing through by the payoff

Assume

$A^\top \text{ and } B \text{ are nonnegative with no zero column} \tag{$\ast$}$

which guarantees the payoffs $u,v$ are positive. (We could simply assume $A,B>0$ , but zero entries are useful — e.g. the identity matrix — and even negative entries are fine as long as the upper envelope stays positive.)

Divide each inequality $\sum_i b_{ij}x_i \le v$ by $v$ and rename $x_i/v$ as $x_i$ ; do the same for $Q$ with $u$ . This gives full-dimensional polytopes

$\overline P = \{x\in\mathbb{R}^M \mid x \ge 0,\ B^\top x \le \mathbf{1}\}, \qquad \overline Q = \{y \in \mathbb{R}^N \mid Ay\le\mathbf{1},\ y \ge 0\}$

In effect we have normalized the expected payoffs to 1 and dropped the normalization constraints on $x$ and $y$ . Nonzero $x\in\overline P$ and $y\in\overline Q$ are rescaled back by $v = 1/\mathbf{1}^\top x$ and $u = 1/\mathbf{1}^\top y$ — and those scaling factors are precisely the expected payoffs to the other player.

NoteProjective transformation

$(x,v)\mapsto x\cdot(1/v)$ is a bijection $P \to \overline P - \{\mathbf{0}\}$ , and similarly for $Q$ . These maps are not linear — they are projective transformations — but they preserve face incidences, hence labels. So an equilibrium is a completely labeled pair $(x,y) \in \overline P\times \overline Q - \{(\mathbf{0},\mathbf{0})\}$ .

ExampleVertices of the running example

$\overline Q$ has vertices $\mathbf{0}$ (labels 4, 5), $p = (0, 1/6)$ (labels 3, 4), $q = (1/12, 1/6)$ (labels 2, 3), $r = (1/6, 1/9)$ (labels 1, 2), $s = (1/3, 0)$ (labels 1, 5).

$\overline P$ has vertices $\mathbf{0}$ (labels 1, 2, 3), $a = (1/3,0,0)$ (2, 3, 4), $b = (2/7, 1/14, 0)$ (3, 4, 5), $c = (0,1/6,0)$ (1, 3, 5), $d = (0, 1/8, 1/4)$ (1, 4, 5), $e = (0,0,1/3)$ (1, 2, 4).

The three completely labeled vertex pairs are $(a,s)$ — the pure equilibrium — and the mixed equilibria $(b,r)$ and $(d,q)$ . Vertices $c$ , $e$ of $\overline P$ and $p$ of $\overline Q$ belong to no equilibrium.

Note the vectors alone display only the player’s own labels (unplayed own strategies); the other player’s best-response information matters just as much.

ImportantNondegeneracy, geometrically

The game is nondegenerate iff no point of $\overline P$ has more than $m$ labels and no point of $\overline Q$ has more than $n$ labels. Then both are simple polytopes. Only vertices can carry $m$ (resp. $n$ ) labels — a non-vertex with $m$ labels would lie on a higher-dimensional face, whose vertices would carry additional labels. So only vertices need be inspected.

WarningSimple is not the same as nondegenerate

Even with $\overline P,\overline Q$ simple, the game can be degenerate if the description is redundant: some inequality omittable yet sometimes binding. This happens when a player has a pure strategy weakly dominated by, or payoff equivalent to, some mixed strategy. Neither pathology occurs for generic payoffs — which is the geometric content of the nondegeneracy assumption. (A strictly dominated strategy may occur generically, but its inequality is never binding, so it causes no degeneracy.)

AlgorithmEquilibria by vertex enumeration

For each vertex $x$ of $\overline P - \{\mathbf{0}\}$ and each vertex $y$ of $\overline Q - \{\mathbf{0}\}$ : if $(x,y)$ is completely labeled, output $(x/\mathbf{1}^\top x,\ y/\mathbf{1}^\top y)$ .

NoteWhy this beats support enumeration

With $m = n$ there are roughly $4^n$ support pairs to test, but by the upper bound theorem for polytopes $\overline P$ and $\overline Q$ have fewer than $2.6^n$ vertices — less work, assuming complementary pairs are found efficiently.

Enumerating vertices is standard computational geometry. The elegant lrs (lexicographic reverse search) algorithm fixes a known vertex — here $\mathbf{0}$ , maximizing $x\mapsto-\mathbf{1}^\top x$ — and a unique simplex pivoting rule (e.g. Bland’s least-index rule), which generates from every vertex a unique path to $\mathbf{0}$ , defining a directed tree rooted there. The algorithm explores that tree by depth-first search, reverting the simplex steps.

The Lemke–Howson algorithm

Support and vertex enumeration find all equilibria. The Lemke–Howson (LH) algorithm finds one, and provides an elementary proof that equilibria exist. It follows a path of vertex pairs of $\overline P\times\overline Q$ starting at $(\mathbf{0},\mathbf{0})$ and ending at a Nash equilibrium, alternately following edges of one polytope while holding the vertex of the other fixed.

DefinitionDropping and picking up labels

By nondegeneracy a vertex of $\overline P$ carries $m$ labels and an edge is defined by $m-1$ labels. Dropping label $\ell$ at a vertex means traversing the unique edge carrying all its labels except $\ell$ . The endpoint has a new label, said to be picked up.

In the example, dropping label 2 at vertex $\mathbf{0}$ of $\overline P$ gives the edge defined by labels 1 and 3, joining $\mathbf{0}$ to $c$ — and label 5 is picked up at $c$ .

ImportantThe artificial equilibrium

$(\mathbf{0},\mathbf{0})$ is completely labeled, since every pure strategy has probability zero — but it is not a Nash equilibrium, because the zero vector cannot be rescaled to a mixed strategy. It is the artificial equilibrium, and it is the algorithm’s starting point.

AlgorithmLemke–Howson

Input: a nondegenerate bimatrix game. Output: one Nash equilibrium.

Choose $k \in M\cup N$ , the missing label. Set $(x,y) = (\mathbf{0},\mathbf{0})$ and drop $k$ (from $x$ if $k\in M$ , from $y$ if $k\in N$ ). Loop: let $\ell$ be the label picked up at the new vertex pair. If $\ell = k$ , terminate with Nash equilibrium $(x,y)$ , rescaled. Otherwise drop $\ell$ in the other polytope and repeat.

ExampleTracing the path with missing label

k = 2

Start at $(\mathbf{0},\mathbf{0})$ . Drop label 2 in $\overline P$ : traverse the edge (labels 1, 3) from $\mathbf{0}$ to $c$ , picking up 5. Now at $(c,\mathbf 0)$ all labels but 2 are present, and 5 is duplicate (a label of both $c$ and $\mathbf 0$ ).

Drop 5 in $\overline Q$ , holding $c$ fixed: edge from $\mathbf{0}$ to $p$ , picking up 3, now duplicate. Drop 3 in $\overline P$ : the edge defined by labels 1 and 5 joins $c$ to $d$ , picking up 4. Drop 4 in $\overline Q$ : the edge from $p$ to $q$ , picking up 2 — the missing label. So $(d,q)$ is completely labeled and is the equilibrium found.

Path: $(\mathbf 0,\mathbf 0), (c,\mathbf 0), (c,p), (d,p), (d,q)$ .

IntuitionWhat the steps mean in game terms

The first two steps amount to taking a pure strategy (the missing label $k$ , say of player 1) and its best response $j$ , giving a pure pair $(k,j)$ . If that is not already an equilibrium, the best response $i$ to $j$ is not $k$ — so $i$ is duplicate and now gets positive probability alongside $k$ .

In general a duplicate label is either a new best response that is about to receive positive probability, or a pure strategy whose probability has just become zero, so it need no longer be maintained as a best response and the path moves away from that best-response facet.

ProofTermination

$\overline P\times\overline Q$ has finitely many vertex pairs, and the next pair on the path is always unique. Hence no pair can be revisited — revisiting would have provided an extra way to proceed in the first place. So the path must end, and it can only end at a completely labeled pair.

∎

ImportantThe path lives on the product polytope

Formally the LH path consists of the pairs $(x,y)$ that are $k$ -almost completely labeled: every label in $M\cup N - \{k\}$ appears on one side. For fixed $k$ , these vertices and edges form a graph of degree 1 or 2 — hence a disjoint union of paths and cycles. The endpoints of the paths are exactly the completely labeled pairs: the Nash equilibria and the artificial equilibrium.

CorollaryOdd number of equilibria

Since the number of path endpoints is even, a nondegenerate bimatrix game has an odd number of Nash equilibria.

NoteStarting elsewhere, and varying $k$

LH can start at any equilibrium. In the example with $k=2$ , starting at $(d,q)$ merely retraces the path back to $(\mathbf 0,\mathbf 0)$ ; starting at $(a,s)$ gives $(b,s)$ (label 5 duplicate) and then $(b,r)$ — this path cannot reach $(\mathbf 0,\mathbf 0)$ , which is already an endpoint of the other path. So the two LH paths for $k=2$ expose all three equilibria. Varying the missing label also helps: $k=1$ leads to $(a,s)$ , from which $k=2$ finds $(b,r)$ .

WarningSome equilibria are elusive

Not every equilibrium is LH-reachable. In the symmetric $3\times3$ game

$A = B^\top = \begin{bmatrix}3&3&0\\4&0&1\\0&4&5\end{bmatrix}$

every equilibrium is symmetric, with $x = y$ equal to $(0,0,1)$ , $(1/2,1/4,1/4)$ or $(3/4,1/4,0)$ . Only the first is found by LH, for any missing label (by symmetry it suffices to check $k = 1,2,3$ ).

The symmetric case

TheoremReduction to symmetric games

There is a polynomial reduction from NASH to symmetric NASH (given a symmetric game, find a symmetric equilibrium). So the symmetric case is as hard as the general one.

ProofStack the two matrices into one symmetric game

Given $(A,B)$ — WLOG all entries positive, since adding a constant changes nothing — consider the symmetric game

$C = \begin{pmatrix} 0 & A \\ B^\top & 0 \end{pmatrix}$

and let $(x,y)$ be a symmetric equilibrium (with $x$ the first $m$ components). For $(x,y)$ to be a best response to itself, $y$ must be a best response to $x$ and $x$ to $y$ — so $x,y$ is a Nash equilibrium of the original game.

∎

NoteTwo open questions in the neighbourhood

It is not known how hard it is to find any Nash equilibrium in a symmetric game (could be easier than NASH), nor to find a non-symmetric equilibrium in a symmetric game (could be easier or harder).

For a symmetric game the two polytopes collapse into one, $P = \{z : Az \le \mathbf{1},\ z\ge0\}$ , and strategy $i$ is represented at $z$ if $z_i = 0$ or $A_i z = 1$ .

DerivationA fully-represented nonzero vertex is a symmetric equilibrium

Suppose all strategies are represented at a vertex $z \ne 0$ . Then for every $i$ with $z_i > 0$ we must have $A_i z = 1$ . Define $x_i = z_i / \sum_j z_j$ : these are well defined, nonnegative and sum to 1, and every strategy in the support is a best response — the necessary and sufficient condition. So $x$ is a symmetric Nash equilibrium.

For the $3\times3$ game above with $A = \begin{pmatrix}0&3&0\\0&0&3\\2&2&2\end{pmatrix}$ , the only fully represented vertices are $z = (0,0,0)$ and $z = (0,1/6,1/3)$ , the latter normalizing to $x = (0,1/3,2/3)$ .

The single-polytope LH path. Fix strategy $n$ and let $V$ be the vertices where all strategies except possibly $n$ are represented. $V$ contains $(0,0,0)$ ; among its $n$ neighbours exactly one has $z_n\ne0$ and the rest zero, giving $v_1 \in V$ . At $v_1$ some strategy $i<n$ is doubly represented (both $z_i = 0$ and $A_i z = 1$ ), so relaxing either inequality gives two neighbours in $V$ — one is $v_0$ , the other a new $v_2$ — and so on. No vertex repeats (three neighbours via one doubly-represented strategy is impossible) and $P$ is finite, so the path ends at a vertex of $V$ other than 0 with no doubly represented strategy: a symmetric Nash equilibrium.

ImportantThis is the form the complexity argument uses

The section below dissects exactly this single-polytope existence proof: a directed graph on combinatorial objects, every vertex of indegree and outdegree at most one, with a known standard source.

Integer pivoting

LH follows polyhedron edges, implemented algebraically by pivoting as in the simplex method. Storing arbitrary-precision integers gives an implementation with no numerical error.

FormulaSlack form of the polytopes

With nonnegative slacks $s\in\mathbb{R}^N$ and $r\in\mathbb{R}^M$ , $x\in\overline P$ and $y\in\overline Q$ iff

$B^\top x + s = \mathbf{1}, \qquad r + Ay = \mathbf{1}, \qquad x,s,r,y \ge 0$

A binding inequality corresponds to a zero slack variable, so $(x,y)$ is completely labeled iff $x_ir_i = 0$ for all $i$ and $y_js_j = 0$ for all $j$ — the orthogonality (complementarity) condition

$x^\top r = 0, \qquad y^\top s = 0$

DefinitionBasic solutions and pivoting

A basic solution picks $n$ basic columns of $B^\top x + s = \mathbf 1$ and $m$ of $r + Ay = \mathbf 1$ , setting the other (nonbasic) variables to zero. A basic feasible solution defines a vertex, and its labels are the nonbasic columns. Pivoting exchanges one nonbasic (entering) and one basic (leaving) variable while preserving feasibility.

DerivationWorked pivots along the edges

\mathbf 0 \to c \to d

The system $B^\top x + s = \mathbf 1$ for the running example is

$3x_1 + 2x_2 + 3x_3 + s_4 \phantom{{}+s_5} = 1$ $2x_1 + \boxed{6}x_2 + \phantom{3}x_3 \phantom{{}+s_4} + s_5 = 1$

with basic variables $s_4 = s_5 = 1$ (the basic columns form the identity, so the basic solution is just the right-hand side).

Dropping label 2 makes $x_2$ enter. Increasing it gives $s_4 = 1-2x_2$ and $s_5 = 1-6x_2$ , nonnegative only while $x_2 \le 1/6$ . That $1/6$ is the minimum ratio over rows with positive coefficient of the entering variable, of right-hand side over coefficient. (Only positive coefficients bound the increase, and at least one exists since $\overline P$ is bounded.) So $s_5$ leaves — giving the label 5 that is picked up — and the boxed 6 is the pivot element.

Integer pivoting. Multiply every non-pivot row by the pivot element:

$18x_1 + 12x_2 + 18x_3 + 6s_4 = 6, \qquad 2x_1 + 6x_2 + x_3 + s_5 = 1$

then subtract multiples of the pivot row to clear the pivot column:

$14x_1 \phantom{{}+96x_2} + \boxed{16}x_3 + 6s_4 - 2s_5 = 4$ $2x_1 + 6x_2 + \phantom{16}x_3 \phantom{{}+6s_4} + s_5 = 1$

The basic columns now form the identity times 6, the pivot element just used, and all entries are integers.

Next step. In the other system $y_5$ enters and $r_3$ leaves (duplicate label 3), so $x_3$ enters here. The ratio test — using only multiplications, no divisions — compares $6s_4 = 4 - 16x_3 \ge 0$ against $6x_2 = 1 - x_3 \ge 0$ ; the former is tighter, so $s_4$ leaves, with pivot element 16. Multiplying and subtracting gives

$14x_1 + 16x_3 + 6s_4 - 2s_5 = 4, \qquad 18x_1 + 96x_2 - 6s_4 + 18s_5 = 12$

The key feature: the second row’s coefficients are all divisible by the previous pivot element 6, and dividing gives

$14x_1 + 16x_3 + 6s_4 - 2s_5 = 4, \qquad 3x_1 + 16x_2 - s_4 + 3s_5 = 2$

This is the final system: the duplicate label 4 (the departed $s_4$ ) is dropped in $\overline Q$ , where the missing label 2 is picked up. The basic solution is vertex $d$ with $x_3 = 4/16$ , $x_2 = 2/16$ and labels 1, 4, 5.

ImportantWhy integer pivoting is exact and efficient

The maintained tableau is always an equivalent integer system

$CB^\top x + Cs = C\mathbf{1}$

where $C$ is the inverse of the basis matrix times its determinant — i.e. the matrix of integer cofactors (a cofactor being the determinant with that element’s row and column deleted). Each entry has a bounded number of digits — at most a factor $n\log n$ more than the original — so integer pivoting is polynomial time.

It is superior to rational arithmetic, whose cancellation requires gcd computations that consume the bulk of the running time. Only the final fractions, like $x_3 = 4/16$ , may need cancelling.

Degenerate games

LH path uniqueness requires nondegeneracy. In a degenerate game a vertex may carry more than $m$ labels, which as a basic feasible solution means some basic variable is also zero — the result of a pivot where the leaving variable was not unique.

ExampleWhere LH breaks

Modify the running example to $b_{15} = 3$ :

$A = \begin{bmatrix}3&3\\2&5\\0&6\end{bmatrix}, \qquad B = \begin{bmatrix}3&3\\2&6\\3&1\end{bmatrix}$

$\overline Q$ is unchanged, but in $\overline P$ vertex $b$ has merged with $a$ , so $a$ now carries the four labels 2, 3, 4, 5.

With missing label 1, the first step goes from $(\mathbf 0,\mathbf 0)$ to $(a,\mathbf 0)$ picking up both 4 and 5. Dropping 4 in $\overline Q$ happens to find the equilibrium $(a,s)$ — no problem. But dropping 5 moves to $(a,p)$ , picking up 3; and neither of the two edges of $\overline P$ leaving the facet labelled 3 (from $a$ to $d$ , and $a$ to $e$ ) is 1-almost completely labeled together with $p$ . The algorithm fails there.

ImportantLexicographic perturbation

Resolve degeneracy as in linear programming: perturb $B^\top x + s = \mathbf 1$ to $B^\top x + s = \mathbf 1 + (\varepsilon^1,\ldots,\varepsilon^n)^\top$ . After any number of pivots the system reads

$CB^\top x + Cs = C\mathbf{1} + C(\varepsilon^1,\ldots,\varepsilon^n)^\top$

A basic variable that is zero in the unperturbed solution (a zero row of $C\mathbf 1$ ) is positive for small enough $\varepsilon$ iff the first nonzero entry of that row of $C$ is positive — the invariant maintained by a lexico-minimum ratio test.

No actual perturbation is required: $C$ is already stored in the tableau as the matrix of coefficients of $s$ .

WarningDegenerate games can have infinite equilibrium sets

In the modified example, vertex $a$ of $\overline P$ (the pure strategy $(1,0,0)$ ) together with the entire edge of $\overline Q$ joining $r$ and $s$ forms a component of equilibria, with player 2 playing $(y_4, 1-y_4)$ for any $2/3 \le y_4 \le 1$ . But this component is just the convex combination of the extreme equilibria $(a,r)$ and $(a,s)$ .

TheoremEquilibria of a general bimatrix game

Let $(x,y) \in \overline P\times\overline Q$ . Then $(x,y)$ rescaled is a Nash equilibrium iff there are sets $U$ of vertices of $\overline P - \{\mathbf 0\}$ and $V$ of vertices of $\overline Q-\{\mathbf 0\}$ with $x \in \operatorname{conv}U$ , $y\in\operatorname{conv}V$ , and every $(u,v)\in U\times V$ completely labeled.

NoteWhy, and what it gives

Labels are preserved under convex combinations, and every face of $\overline P$ or $\overline Q$ carries the labels of its vertices, which are vertices of the whole polytope.

The resulting complete description: build a bipartite graph on the vertices of $\overline P - \{\mathbf 0\}$ and $\overline Q - \{\mathbf 0\}$ whose edges are the completely labeled pairs. Its cliques (maximal complete bipartite subgraphs) $U\times V$ give sets $\operatorname{conv}U\times\operatorname{conv}V$ whose union is the set of all Nash equilibria — the maximal Nash subsets. These may overlap; their connected unions are the (topological) components of Nash equilibria.

Extensive games and the sequence form

The problem. A game in strategic form is a static description in which players act simultaneously. An extensive game is the detailed dynamic description — the fundamental model of dynamic interactions, generalizing repeated games, multistage games, and games of incomplete information.

DefinitionExtensive game

A directed tree. Nodes are game states — trees rather than general graphs, so that a state encodes the full history of play. Exactly one player moves at each state, along an outgoing edge. Play starts at the root and ends at a leaf, where each player receives a payoff; non-terminal nodes are decision nodes, whose outgoing edges are the available moves.

Decision nodes are partitioned into information sets: all nodes in one belong to the same player and offer the same moves. When a player moves he knows only the information set, not which node he is at. In a game of perfect information all information sets are singletons. Write $H_i$ for player $i$ ‘s information sets, $h$ for one of them, and $C_h$ for its move set.

flowchart TD
  root(( )) -->|L| n2(( ))
  root -->|R| leafR["3, 3"]
  n2 -->|l| n3(( ))
  n2 -->|r| n4(( ))
  n3 -->|S| l1["2, 2"]
  n3 -->|T| l2["0, 3"]
  n4 -->|S| l3["5, 6"]
  n4 -->|T| l4["6, 1"]

ExampleThe running extensive game

Player 1’s two information sets have move sets $\{L,R\}$ and $\{S,T\}$ ; player 2’s has $\{l,r\}$ . A play might be $L$ , then $r$ , then $S$ , giving payoffs 5 and 6. By definition move $S$ is the same move whether player 2 chose $l$ or $r$ , because player 1 does not know the state in his second information set — which is exactly what the oval around those two nodes means.

DefinitionChance, behavior and pure strategies

Chance is an additional player 0, receiving no payoff and playing a known behavior strategy; its information sets are singletons.

A behavior strategy of player $i$ gives a probability distribution on $C_h$ for every $h \in H_i$ . A pure strategy picks each move deterministically, so it is a tuple $\langle c_h\rangle_{h\in H_i} \in \prod_{h\in H_i}C_h$ — e.g. $\langle L, S\rangle$ for player 1 above.

Tabulating all pure strategies and the resulting expected payoffs gives the strategic form of the extensive game.

IntuitionMixed versus behavior strategies

A mixed strategy draws a complete plan of action up front and plays it. A behavior strategy “delays” each random choice until the information set is actually reached. A behavior strategy is a special mixed strategy, one in which the moves at different information sets are chosen independently.

WarningThe strategic form is exponential in the tree

This is why we need better representations. Three successive reductions follow: subgames (which help only when players are often informed), the reduced strategic form (smaller, still possibly exponential), and the sequence form (linear in the tree size).

Subgames and subgame perfection

DefinitionSubgame

A subtree of the game tree that includes all information sets containing any of its nodes. In the example there is a subgame rooted at player 2’s decision node; the nodes of player 1’s second information set are not roots of subgames, since player 1 does not know he is in the respective subtree.

ExampleSolving the example by subgames

That subgame has player 2 moving first without player 1 learning the move — so it is equivalent to a $2\times2$ simultaneous-move game. (Conversely, this is how any strategic-form game is represented in extensive form.) Its unique equilibrium mixes $T$ and $r$ with probability $2/3$ each, with payoffs $4$ and $8/3$ .

Replacing the subgame by $(4, 8/3)$ leaves a trivial game where $L$ is optimal. So player 1 playing $\langle L,S\rangle, \langle L,T\rangle$ with probabilities $1/3, 2/3$ and player 2 playing $(1/3,2/3)$ is the game’s unique subgame perfect equilibrium — one inducing a Nash equilibrium in every subgame.

AlgorithmSubgame perfect equilibrium

Input: an extensive game. Output: a subgame perfect equilibrium.

Consider each subgame in increasing order of inclusion; find a Nash equilibrium of it; replace the subgame by a new terminal node carrying the equilibrium payoffs.

ImportantThe perfect-information special case

With perfect information every node roots a subgame, so the algorithm becomes the well-known linear-time backward induction (sometimes “Zermelo’s algorithm”). Each subgame then involves only one player, for whom a deterministic move is optimal — proving that every perfect-information game has a subgame perfect equilibrium in pure strategies. With imperfect information, mixing may be required, as the example shows.

The reduced strategic form

ExampleOverspecified plans

Not all games have nontrivial subgames, and one may want non-subgame-perfect equilibria too. In the example, $(\langle R,S\rangle, l)$ is a pure equilibrium: after $R$ , player 2 never moves and receives constant payoff 3, so she is indifferent. It is not subgame perfect, since $l$ is not optimal against $S$ if her information set were reached. In fact she may randomize, and as long as $l$ has probability at least $2/3$ , $\langle R,S\rangle$ remains a best response.

The pure strategies $\langle R,S\rangle$ and $\langle R,T\rangle$ are overspecific: after $R$ , player 1’s second information set is unreachable, so the two payoff rows are identical for both players.

DefinitionReduced strategic form

Moves at information sets unreachable because of the player’s own earlier move are identified. Here that yields $\langle R, *\rangle$ with $*$ an arbitrary move.

NoteTwo consequences

It is degenerate by construction. The reduced strategic form of the example is exactly the degenerate bimatrix game of the previous section (with $\langle R,*\rangle$ as top row) — degenerate even though the extensive payoffs are generic, because player 2 receives constant payoff 3 against $\langle R,*\rangle$ .

It cannot express subgame perfection. One cannot say whether $(\langle R,*\rangle, l)$ is subgame perfect, since player 1’s behavior at his second information set is unspecified. But splitting probability between two payoff-identical rows of the full form is computationally arbitrary, so there is no point running an algorithm on the unreduced form. If you want subgame perfection, use the algorithm above — at each of its stages the game has no further subgames, and its equilibria can be found via the reduced strategic or sequence form.

WarningStill exponential

A player may have parallel information sets not distinguished by his own earlier moves — these arise when he receives information about another player’s move. Combinations of moves at parallel information sets cannot be reduced, giving multiplicative growth. The reduced strategic form can still be exponential in the tree size.

Sequences and realization plans

DefinitionSequences and perfect recall

A sequence $\sigma_i(t)$ is player $i$ ‘s moves (ignoring other players’) on the unique path from the root to node $t$ ; the empty sequence is $\emptyset$ . For the leftmost leaf above, that is $LS$ for player 1 and $l$ for player 2.

Player $i$ has perfect recall iff $\sigma_i(s) = \sigma_i(t)$ for all $s,t \in h$ , $h\in H_i$ — he gains no extra information about his position by remembering his own earlier moves. Then the sequence leading to any node of $h$ is written $\sigma_h$ . We assume perfect recall throughout.

Every $\sigma \in S_i$ is either $\emptyset$ or uniquely $\sigma_h c$ for its last move $c$ at $h$ , so

$S_i = \{\emptyset\}\cup\{\sigma_h c \mid h \in H_i,\ c\in C_h\}, \qquad |S_i| = 1 + \sum_{h\in H_i}|C_h|$

which is linear in the size of the game tree.

FormulaRealization probabilities

Under behavior strategy $\beta_i$ (with $\sum_{c\in C_h}\beta_i(c) = 1$ , $\beta_i(c)\ge0$ ), the realization probability of a sequence is

$\beta_i[\sigma] = \prod_{c \text{ in } \sigma}\beta_i(c)$

An information set $h$ is relevant under $\beta_i$ if $\beta_i[\sigma_h] > 0$ , otherwise irrelevant — agreeing with the irrelevant sets of the reduced strategic form.

WarningWhy we cannot just optimize over behavior probabilities

The expected payoff to player 1 is

$\sum_{\text{leaves } t} a(t)\,\beta_0[\sigma_0(t)]\,\beta_1[\sigma_1(t)]\,\beta_2[\sigma_2(t)]$

which is nonlinear in the $\beta_i(c)$ , since each $\beta_i[\sigma]$ is a product. The fix is to treat the realization probabilities themselves as the variables.

DefinitionRealization plan

For a mixed strategy $\mu_i$ (choosing pure strategy $\pi_i$ with probability $\mu_i(\pi_i)$ ), the realization probability of $\sigma$ is

$\mu_i[\sigma] = \sum_{\pi_i}\mu_i(\pi_i)\,\pi_i[\sigma]$

where $\pi_i[\sigma]$ is 1 if $\pi_i$ prescribes all moves in $\sigma$ and 0 otherwise. The map $x(\sigma) = \mu_1[\sigma]$ on $S_1$ is the realization plan of $\mu_1$ ; similarly $y$ for player 2.

TheoremCharacterization of realization plans

A realization plan of a mixed strategy of player 1 satisfies $x(\sigma)\ge0$ and

$x(\emptyset) = 1, \qquad \sum_{c\in C_h} x(\sigma_h c) = x(\sigma_h) \quad \text{for all } h\in H_1$

Conversely any $x : S_1 \to \mathbb{R}$ with these properties is the realization plan of a behavior strategy, unique except at irrelevant information sets.

TheoremRealization equivalence

Two mixed strategies of player $i$ are realization equivalent — they reach every node with the same probability, against any strategy of the other player — iff they have the same realization plan.

CorollaryKuhn’s theorem

For a player with perfect recall, any mixed strategy is realization equivalent to a behavior strategy.

ImportantWhat the compression achieves

A realization plan carries all the strategically relevant information of a mixed strategy, via the linear map above. The simplex of mixed strategies is mapped onto the polytope of realization plans; its vertices are the plans of pure strategies and may be exponentially many, but the number of defining inequalities and the dimension are linear in the tree: for player $i$ the dimension is $|S_i| - (1 + |H_i|) = \sum_{h\in H_i}(|C_h| - 1)$ .

A pure realization plan (values 0 or 1) is exactly as specific as a reduced pure strategy.

FormulaConstraint matrices

Write the constraints as

$Ex = e,\ x \ge 0 \qquad\text{and}\qquad Fy = f,\ y\ge0$

$E$ has $1 + |H_1|$ rows and $|S_1|$ columns: the first row is $x(\emptyset)=1$ , and the row for $h$ is $-x(\sigma_h) + \sum_{c\in C_h}x(\sigma_hc) = 0$ . For the example, with $S_1 = \{\emptyset, L, R, LS, LT\}$ and $S_2 = \{\emptyset, l, r\}$ ,

$E = \begin{bmatrix}1&&&&\\-1&1&1&&\\&-1&&1&1\end{bmatrix},\quad e = \begin{bmatrix}1\\0\\0\end{bmatrix},\quad F = \begin{bmatrix}1&&\\-1&1&1\end{bmatrix},\quad f = \begin{bmatrix}1\\0\end{bmatrix}$

Each sequence appears exactly once on the left-hand side, accounting for the single $1$ in every column.

FormulaSequence form payoff matrices

$A$ and $B$ of dimension $|S_1|\times|S_2|$ , with

$a_{\sigma\tau} = \sum_{\text{leaves } t\,:\, \sigma_1(t)=\sigma,\ \sigma_2(t)=\tau} a(t)\,\beta_0[\sigma_0(t)]$

and likewise $b_{\sigma\tau}$ . These are sparse: the entry is the empty sum — zero — whenever the two sequences do not lead to a leaf; otherwise it is the payoff there, weighted by chance probabilities if there are chance moves. The expected payoffs are then just $x^\top Ay$ and $x^\top By$ .

Computing equilibria with the sequence form

Realization plans take the role of mixed strategies; mixed strategies are the special case where $E$ and $F$ are single rows $\mathbf{1}^\top$ with $e = f = 1$ .

DerivationBest response as a linear program, and its dual

Against a fixed $y$ , a best response $x$ solves

$\max\ x^\top(Ay) \quad \text{s.t.}\quad Ex = e,\ x\ge0$

whose dual has an unconstrained vector $u$ of dimension $1+|H_1|$ :

$\min\ e^\top u \quad\text{s.t.}\quad E^\top u \ge Ay$

Both are feasible, so by strong duality they share an optimal value.

DerivationThe zero-sum case

With $B = -A$ , player 2 choosing $y$ must assume player 1 maximizes $x^\top Ay$ — whose value equals the dual optimum $e^\top u$ . She wants to minimize it, and the dual constraints are linear in $u$ and $y$ jointly, so a minmax realization plan solves

$\min_{u,y}\ e^\top u \quad\text{s.t.}\quad Fy = f,\ E^\top u - Ay \ge 0,\ y \ge 0$

whose dual, with variables $v$ and $x$ ,

$\max_{v,x}\ f^\top v \quad\text{s.t.}\quad Ex = e,\ F^\top v - A^\top x \le 0,\ x\ge0$

is the maxmin problem for player 1.

TheoremZero-sum extensive games are solvable by linear programming

The equilibria of a two-person zero-sum extensive game with perfect recall are the solutions of the LP above, with the sparse sequence form payoff matrix $A$ and constraint matrices $E, F$ . The size of this LP is linear in the size of the game tree.

ImportantComplementary slackness is the best response condition

For general-sum games, a feasible $x$ is optimal iff there is a dual $u$ with $E^\top u \ge Ay$ and $x^\top(Ay) = e^\top u$ , i.e.

$x^\top\big(E^\top u - Ay\big) = 0$

Since both vectors are nonnegative, they are complementary — never both positive in the same position. For the strategic form this condition is precisely the best response condition from the start of the note. Symmetrically for player 2, $y^\top(F^\top v - B^\top x) = 0$ .

TheoremEquilibria of the sequence form

$(x,y)$ is an equilibrium iff there are $u, v$ with

$Ex = e,\ x\ge0, \qquad Fy = f,\ y \ge 0$ $E^\top u - Ay \ge 0, \qquad F^\top v - B^\top x \ge 0$

together with the two complementarity conditions. All matrices have size linear in the game tree.

NoteLinear complementarity, and Lemke’s algorithm

These conditions define a linear complementarity problem (LCP) — as do the slack-form conditions for strategic-form games, to which LH finds one solution.

LH cannot be applied here, because $u$ and $v$ are not scalar dual variables that can be eliminated. Instead one uses Lemke’s algorithm: introduce an extra column and a variable $z_0$ , initially nonzero, permitting an initial feasible solution with $x = 0$ , $y = 0$ . A binding inequality then lets a basic slack $r_\sigma$ (or $s_\tau$ ) leave while $x_\sigma$ (or $y_\tau$ ) enters, preserving complementarity. As in LH this complementary pivoting rule continues until an equilibrium is found — here, when $z_0$ leaves the basis.

NotePractice and open problems

Existing software packages are prototypes that are not easy to use; better implementations should reveal which games practitioners actually care about. For discretized economic games, enumerating all equilibria soon hits the size barrier of these exponential algorithms — so LH may instead be used to indicate whether the game has a unique equilibrium, or Lemke’s method with varying start. Whether LH or Lemke’s algorithm has expected polynomial running time under suitable probabilistic assumptions, as is known for the simplex method, is open.

Any incremental or divide-and-conquer approach must generalize the equilibrium condition, since equilibria typically do not arise from equilibria of games with fewer strategies — and must not maintain the whole equilibrium set, since questions about that set (uniqueness, for instance) are typically NP-hard.

The class PPAD

Dissect the existence proof above. It creates a graph whose vertices are a finite set of easily recognizable combinatorial objects, in which every vertex has indegree and outdegree at most one — so the graph is a set of paths and cycles — and in which one endpoint is known.

flowchart LR
  SS["standard source (all-zero vertex)"] --> a1[ ] --> a2[ ] --> SK["sink = Nash equilibrium"]
  b1[ ] --> b2[ ] --> b3["other sink"]
  c1["nonstandard source (also a solution)"] --> c2[ ]

NoteThe paths are directed

At each vertex we can assign directions to its incident edges — at most one in, at most one out — consistently from vertex to vertex. In the three-dimensional example the rule is simple: travelling along the arrow, keep a face all of whose vertices are labelled 3 on the right and a face labelled 1 on the left. In higher dimensions there is a similar but more algebraic orientation rule.

DefinitionPPAD

The class of all problems whose solution space can be set up as the set of all sinks and all nonstandard sources of a directed graph such that:

the graph is on a finite but exponentially large vertex set;
each vertex has indegree and outdegree at most one;
given a string it is computationally easy to (a) tell whether it is a vertex, (b) find its one or two neighbours, and (c) tell which is predecessor and which successor;
there is one known standard source (a vertex with no incoming edge).

(The name stands for “polynomial parity argument, directed case.”)

ImportantThe parity argument

Since the standard source has an outgoing edge and no incoming one, there must be a sink — a Nash equilibrium. Note also that a source other than the standard one is a solution too, since all strategies are represented there as well.

WarningThe obvious algorithm is exponential

Any such proof suggests: start at the standard source and follow the path to a sink. This is not efficient, since the vertex set is exponentially large — and for two-player NASH there are games in which these paths are exponentially long (Savani and von Stengel 2004).

NoteOther members

Finding an approximate Brouwer fixpoint. Ham sandwich: given $n$ sets of $2n$ points each in $n$ dimensions, find a hyperplane leaving $n$ points of each set on each side. Borsuk–Ulam fixpoints, Arrow–Debreu market equilibria, and many others. For none of these do we know a polynomial algorithm.

IntuitionPPAD versus NP

Solving a PPAD problem means telescoping the long path to arrive at a sink fast and without rote traversal — just as solving an NP problem means narrowing to a solution among exponentially many candidates without exhaustive search. We know neither feat is possible in general; we do know the latter implies the former, since $\text{P} = \text{NP} \Rightarrow \text{PPAD} = \text{P}$ (PPAD is essentially a subset of NP: a solution can be certified quickly if found).

DefinitionPPAD-completeness

A problem is PPAD-complete if all problems in PPAD reduce to it — so it is efficiently solvable iff they all are.

Is PPAD-completeness good evidence of hardness?

WarningWeaker than NP-completeness, but compelling

It could be that $\text{PPAD} = \text{P} = \text{NP}$ . Yet if a PPAD-complete problem were polynomial:

every PPAD problem — Brouwer, Borsuk–Ulam, ham sandwich, Arrow–Debreu, many of which have resisted decades of scrutiny — would fall;
any local combinatorial description of a deterministic simplex pivoting rule would yield a novel polynomial algorithm for linear programming;
since any black-box algorithm for Brouwer fixpoints must be exponential (Hirsch et al. 1989), there would have to be a way of finding them by delving into the detailed properties of the function — quite counterintuitive;
the algorithm would have to defeat the constructed oracles giving computational universes in which $\text{PPAD} \ne \text{P}$ , hence be extremely sophisticated in a specific sense.

It remains a reasonable working hypothesis that PPAD-completeness establishes intractability.

Succinct representations of games

WarningThe input-size problem, stated sharply

Describing an $n$ -player game in strategic form with $s$ strategies each requires $ns^n$ numbers. For $n$ in the hundreds or thousands — a modest range for Internet applications — no user can supply this input and no algorithm can handle it.

Worse, the astronomical input trivializes complexity: for fixed small $s$ , “try all combinations of supports” runs in $(2^s)^n$ time, which is polynomial in the input length $ns^n$ . The algorithm is “efficient” only because the input is absurd.

Conclusion: the study of NASH must focus on games with many players, and only succinctly representable multiplayer games are of relevance.

DefinitionGraphical games (Kearns et al. 2001)

A directed graph on the players, with $(i,j)$ an edge only if $j$ ‘s utility depends on $i$ ‘s strategy. Formally, for profiles $s, s'$ with $s_j = s_j'$ and $s_i = s_i'$ for all $(i,j)\in E$ , we have $u_j(s) = u_j(s')$ . Played on a graph with $n$ nodes, indegree at most $d$ , and $s$ choices per player, a graphical game needs only $ns^{d+1}$ numbers — a huge saving over $ns^n$ for modest $d$ . See graphical-games.

ExampleA cycle of 20 players

Take a directed cycle on 20 players where each player’s utility is $A_{ij}$ from the $3\times3$ matrix above, with $i$ his own strategy and $j$ his predecessor’s. Ordinarily this needs $20\times3^{20}$ numbers; the graph structure reduces it to a few bytes. (Exercise: find a Nash equilibrium.)

Representation	Idea	Size
Sparse games	Few of the $ns^n$ utilities are nonzero	Graphical games are the special case where the sparsity pattern is a graph on players
Symmetric games	All players identical; only how many play each strategy matters	$s\binom{n+s-1}{s-1}$
Anonymous games	Players differ but cannot distinguish the others	$sn\binom{n+s-1}{s-1}$
Extensive form games	Explicit game trees; a strategy picks a move at each information set where the player has the initiative; utility is that of the leaf reached	tree size
Congestion games	Strategies are sets of paths over edges $E$ ; with load $\ell_e(P) = \lvert\{i : e\in P_i\}\rvert$ , player $i$ ‘s utility is $\sum_{e\in P_i} c_e(\ell_e(P))$	congestion functions
Network congestion games	Even more succinct: $E$ is an actual graph, each player gets two vertices, strategies are all simple paths between them	the graph
Local effect games	Generalizations of congestion games	—
Facility location games	See network-formation-games	—
Multimatrix games	An $m\times m$ matrix $A^{ij}$ per ordered pair; utility $\sum_{j\ne i}A^{ij}_{s_i,s_j}$ — each player collects the sum of pairwise interactions	$n^2m^2$

The reduction: NASH is PPAD-complete

The starting point

DefinitionBROUWER (discrete, stylized)

A function $\varphi$ from the three-dimensional unit cube to itself. Subdivide the cube into $2^{3n}$ cubelets of side $\epsilon = 2^{-n}$ ; $\varphi$ need only be described at cubelet centers, where it takes one of four values $x + \delta_i$ with

$\delta_1 = (\epsilon,0,0),\quad \delta_2 = (0,\epsilon,0),\quad \delta_3 = (0,0,\epsilon),\quad \delta_0 = (-\epsilon,-\epsilon,-\epsilon)$

(boundary cubelets need an easy check so $\varphi(x)$ does not leave the cube). A fixpoint is an internal cubelet corner such that among its eight adjacent cubelets all four displacements appear.

$\varphi$ is represented by a Boolean circuit with $3n$ input bits (the cubelet) and 2 output bits (which displacement). Given the circuit, find a fixpoint. This problem is PPAD-complete.

The plan

Reduce BROUWER to a graphical game with many players, each with two strategies $\{0,1\}$ — so a mixed strategy is a number in $[0,1]$ , the probability of playing 1.

ImportantThe loop to be closed

Three players (the leaders) choose numbers that are the coordinates of a point in the cube. Others analyze those coordinates to identify the containing cubelet, then simulate the circuit to compute the displacements at that cubelet and its neighbours. Their choices then incentivize the three leaders to move — unless the point is a fixpoint of $\varphi$ , in which case the leaders do not change and the game is at a Nash equilibrium.

The gadgets

We need small graphical games whose output player’s mixed strategy stands in a prescribed arithmetic or logical relation to the input players’.

ExampleThe multiplication gadget

Four players: inputs $a,b$ , output $c$ , middle $d$ , with edges $(a,d), (b,d), (c,d), (d,c)$ . All have two strategies, so each is a number in $[0,1]$ . Utilities:

Middle player $d$ : playing 1 gives utility 1 if both inputs play 1 and 0 otherwise — so his expected utility from playing 1 is exactly $a\cdot b$ . Playing 0 gives utility 1 if the output player plays 1, else 0 — expected utility $c$ .
Output player $c$ : utility 1 if $d$ plays 1, and $-1$ if $d$ plays 0.

So $c$ wants to play 1 with probability as high as possible to keep $d$ playing 1 — but not so high that $d$ prefers 0, which happens whenever $c > a\cdot b$ . At equilibrium $c = a\cdot b$ .

NoteWhy the inputs’ utilities are irrelevant

The inputs have no incoming edges, so their utilities never need specifying — which is crucial: it lets the same inputs be reused in many gadgets without one use influencing another.

Similar gadgets add and subtract (within $[0,1]$ ), and perform AND, OR, NOT on Boolean (pure-strategy) inputs. A trivial two-node gadget compares: $y = 1$ if $x > \tfrac12$ and $y = 0$ if $x < \tfrac12$ .

WarningComparators are necessarily brittle

Note the comparator’s output is undetermined at exactly $x = 1/2$ . This is of necessity: non-brittle comparators (behaving deterministically at half) cannot exist — with them one could construct a graphical game with no Nash equilibrium at all.

Assembling the graphical game

Three leaders whose mixed strategies give a point $(x,y,z)$ ; they feed a series of comparators and subtractors that extract, one by one, the $n$ most significant bits of each coordinate, identifying the cubelet; logical gadgets then compute the circuit’s outputs on those $3n$ bits, repeat for neighbouring cubelets, and decide whether we are at a fixpoint.

WarningThe brittleness must be smoothed away

Because comparators are indeterminate at half, the computation is imprecise, and unpredictably so, when $(x,y,z)$ lies exactly on a cubelet boundary — which creates spurious equilibria.

The fix: compute $\varphi$ not at the single point but over a large, very fine grid of points around it, averaging all results. Once the average displacement $\Delta(x,y,z)$ is computed, its components are added back to the three leaders, closing the loop so the leaders — who had no incoming edges — are finally affected, very indirectly, by their own choices. One then shows the Nash equilibria correspond exactly to points of zero average displacement, and that this happens iff we are near a fixpoint.

ImportantFirst milestone

Finding a Nash equilibrium in a graphical game is PPAD-complete — and the underlying graph, despite its size, is strikingly simple: bipartite, with all indegrees at most three. Bipartite because every gadget is (inputs and outputs on one side, middle nodes on the other, with logical gadgets redesigned to have middle nodes), and the middle nodes are the ones of maximum indegree, three.

From many players to two

DefinitionConflict graph

Undirected, on the vertices of the graphical game, with an edge between $u$ and $v$ if either (a) there is an edge between them in the graphical game, in either direction, or (b) both have edges to the same node $w$ . Both eventualities make it hard for one player to represent both.

ImportantLawyers and clients

Assign to each player (“lawyer”) an entire colour class of the conflict graph (“clients”). The lawyer’s strategy set is the union of his clients’ sets, and he represents them fairly by playing the average of their mixed strategies. Coming from a colour class, there is no conflict of interest — he never represents two players who play against each other, nor two who both play against a third.

The crucial observation: the conflict graph of the constructed game is four-colourable, giving a four-player simulation.

WarningThe neglected-client problem, and the fix

A lawyer might neglect clients with small payoffs and over-weight the lucrative ones. This is handled by having the lawyers play, on the side and at very high stakes, a generalization of rock–paper–scissors — a game known to force players to distribute probability evenly, so all clients are fairly represented.

Result	Method
4 players (Goldberg–Papadimitriou; Daskalakis et al., Oct 2005)	four-colourable conflict graph + lawyers
3 players (Daskalakis–Papadimitriou)	local: modify gadgets so the conflict graph becomes three-colourable — this approach had reached its limit, since the conflict graph must contain triangles for the game to work
3 players (Chen–Deng)	ad hoc and non-local, hence more open-ended and promising
2 players (Chen–Deng, a month later)	many “conflicts of interest” of type (b) are unproblematic here: the two input nodes of a gadget cannot effectively conspire, so one carefully programmed lawyer can represent both. Only two lawyers are needed, one per side of the bipartite game — and the construction is direct, with no graphical game: *the two players are built ab initio, gadgets and side game included*

ImportantThe theorem

NASH is PPAD-complete, even for two players. So two-player games are not, in any significant sense, easier than the general problem — and it was conjectured at both the 4-player and 3-player stages that the two-player case would be in P.

Approximate equilibria

Definition $\epsilon$ -approximate Nash equilibrium

A mixed strategy profile such that no other strategy improves any player’s payoff by more than an additive $\epsilon$ . (Note: such a profile may or may not be near a true Nash equilibrium.)

ImportantApproximation is not optional in the proof

The side rock–paper–scissors game only guarantees that lawyers approximately balance their clients’ interests, so the entire reduction must be carried out in terms of $\epsilon$ -approximate equilibria. In retrospect this is inherently needed: two-player games always have rational equilibria while games with more players may have only irrational ones, so any simulation of the latter by the former must involve approximation.

Result	Statement
Hardness	PPAD-complete for exponentially small $\epsilon$ (below the cubelet side, $2^{-cn}$ )
Strengthened	PPAD-complete up to inverse polynomial $\epsilon = \Theta(n^{-c})$ , starting from an $n$ -dimensional Brouwer
Easy case	$\tfrac12$ -approximate equilibria are very easy for two-player games
Subexponential	An $\epsilon$ -approximate equilibrium in arbitrary games in time $n^{\frac{\log n}{\epsilon^2}}$

NoteThe open problem

Polynomial algorithms for $\epsilon$ -approximate Nash equilibria for $\epsilon$ between these values — possibly for arbitrarily small constant $\epsilon>0$ — remain an important open problem.

Correlated equilibria: the computationally benign generalization

ExampleChicken

Symmetric game with payoff matrix (strategy 1 = stop, 2 = go):

$\begin{pmatrix} 4 & 1 \\ 5 & 0 \end{pmatrix}$

Two macho drivers speed toward an intersection. Two pure equilibria (me and you) and the symmetric mixed one $(1/2,1/2)$ , giving three distributions over profiles:

$\begin{pmatrix}0&0\\1&0\end{pmatrix}, \qquad \begin{pmatrix}0&1\\0&0\end{pmatrix}, \qquad \begin{pmatrix}1/4&1/4\\1/4&1/4\end{pmatrix}$

Now consider instead $\begin{pmatrix}0&1/2\\1/2&0\end{pmatrix}$ . This is not a Nash equilibrium — no pair of mixed strategies generates it, since the matrix is not of rank one. But it is a rational outcome in a more sophisticated sense: a trusted third party draws from it and privately recommends a strategy to each player. (In the drivers’ story, randomizing between (stop, go) and (go, stop) is a traffic signal.) The distribution is self-enforcing: assuming the other follows the recommendation, each player’s best bet is to follow his own.

DerivationThe CE inequalities for chicken, and their shape

Writing the definition out for this game:

$(4-5)p_{11} + (1-0)p_{12} \ge 0, \qquad (5-4)p_{21} + (0-1)p_{22}\ge0$ $(4-5)p_{11} + (1-0)p_{21} \ge 0, \qquad (5-4)p_{12} + (0-1)p_{22}\ge0$

The crucial observation: these are linear in the unknowns $\{p_s\}$ .

ImportantNash as a special case, and what that costs

If $p^i$ are mixed strategies inducing $p_s = \prod_i p^i_{s_i}$ , the CE inequalities say exactly that these constitute a mixed Nash equilibrium: for each $i,j,j'$ , if $j$ is in $i$ ‘s support, dividing through by its probability says $j$ is a best response; if not, the inequality degenerates to $0\ge0$ .

So every Nash equilibrium is a correlated equilibrium, and Nash is the special case in which the $p_s$ come from a product distribution. It is this single additional constraint — apparently a very nonconvex one, a curved surface touching the CE polytope — that makes NASH so much harder.

TheoremComputing correlated equilibria

The (CE) system is a set of linear inequalities, so it can always be solved by linear programming, and we know it has a solution: the Nash equilibrium guaranteed by Nash’s theorem. Moreover we can find the correlated equilibrium optimizing any linear function of the $p_s$ .

ExampleThe optimal traffic light

Maximizing the expected sum of utilities in chicken means maximizing $8p_{11} + 6p_{12} + 6p_{21}$ over the CE polytope. The optimum is

$\begin{pmatrix}1/3 & 1/3\\ 1/3 & 0\end{pmatrix}$

a traffic light that is red for both one third of the time — beating every Nash equilibrium of the game.

TheoremNash equilibria are vertices of the CE polytope

In any nondegenerate two-player game, the Nash equilibria are vertices of the (CE) polytope.

RemarkWhat that implies, and where it fails

Not all vertices are Nash, but at least one is. So in two-player games every Nash equilibrium is the optimum correlated equilibrium for some linear objective — unfortunately, guessing that objective is apparently not easy. For three or more players there are games where Nash equilibria are not vertices: any game with integer utilities whose only equilibria are irrational must be of this sort.

Correlated equilibria in succinct games

WarningThe same input-size caveat applies

Polynomial-time algorithms whose input is the game — such as the LP above — make a mockery of complexity theory when the number of players is high. So: can we find correlated equilibria efficiently when the game is represented succinctly?

NoteWhat learning gives, and what it does not

Natural regret-minimizing learning algorithms approximate correlated equilibria by simulating repeated play, with players changing strategies according to how much they regret previous decisions. Reaching distance $\epsilon$ from the CE polytope takes $\tfrac{1}{\epsilon^c}$ iterations for a small constant $c$ . But that is approximation — can we find an exact point of the polytope in polynomial time? See learning-and-regret-minimization.

DefinitionPolynomial type and the expected utility problem

A succinctly representable game is of polynomial type if the number of players and the number of strategies per player are bounded by a polynomial in the description length $n$ . Its expected utility problem is: given a mixed strategy $p^i$ for each player, compute each player’s expected utility.

TheoremPapadimitriou (2005)

In any succinctly representable game of polynomial type for which the expected utility problem is polynomial-time solvable, finding a correlated equilibrium is polynomial-time solvable too. Consequently there is a polynomial algorithm for sparse, symmetric, anonymous, graphical, congestion, local effect, facility location, and multimatrix games, among many others.

TheoremPapadimitriou and Roughgarden (2005)

Optimizing a linear function over correlated equilibria is polynomial for symmetric, anonymous, and bounded-treewidth graphical games. In contrast, it is NP-hard to find the optimum correlated equilibrium in general graphical games and congestion games, among others.

ImportantThe whole picture in one line

Finding a correlated equilibrium is easy almost everywhere; finding the best one is often hard; finding a Nash equilibrium is PPAD-complete even for two players.

Concluding remarks

WarningThe obvious objection

The PPAD-completeness proof only shows that it is hard to find a Nash equilibrium in some far-fetched, artificial games that happen to encode Brouwer functions. Of what relevance is that to economic practice?

ImportantThe answer, by analogy with NP-completeness

The same was said in the early days about the NP-completeness of the travelling salesman problem, and the answer is the same. PPAD-completeness suggests that

any approach to finding Nash equilibria that aspires to be efficient, and any proposal to use the concept in an applied setting, must explicitly exploit computationally beneficial special properties of the games at hand, by proving positive algorithmic results for interesting classes;
the completeness proofs will themselves be refined to cover simpler and more realistic classes of games — as has already begun — after which researchers will strive to identify simpler classes still.

An intractability result is most usefully seen as the opening move in an interesting game.

Quick reference

Concept	Definition	Computational status
Dominant strategy	$u_i(s_i, s'_{-i}) \ge u_i(s_i', s'_{-i})$ for all $i, s'$	Trivial when it exists; rare
Pure Nash	$u_i(s_i,s_{-i}) \ge u_i(s_i',s_{-i})$	May not exist
Mixed Nash	Same, over distributions	Always exists (finite game); PPAD-complete, even for 2 players
Best response condition	$x_i > 0 \Rightarrow (Ay)_i = \max_k (Ay)_k$	Turns NASH into a search for supports
Completely labeled pair	Every label in $M\cup N$ on one side	Equivalent to Nash equilibrium
Support enumeration	Test all $(I,J)$ of equal size	$\approx 4^n$ support pairs
Vertex enumeration	Test all vertex pairs of $\overline P\times\overline Q$	$< 2.6^n$ vertices (upper bound theorem); lrs
Lemke–Howson	Follow $k$ -almost completely labeled path from $(\mathbf 0,\mathbf 0)$	Finds one equilibrium; exponential in the worst case
Integer pivoting	Tableau $CB^\top x + Cs = C\mathbf 1$ , $C$ = cofactor matrix	Exact, polynomial, beats rational arithmetic
Degenerate games	Some support size $k$ has $>k$ best responses	Lexicographic ratio test; equilibria as maximal Nash subsets
$\epsilon$ -approximate Nash	No deviation gains more than additive $\epsilon$	PPAD-complete for $\epsilon$ inverse-polynomial; $n^{\log n/\epsilon^2}$ in general
Correlated	$\sum_{s_{-i}} p(s_i,s_{-i})[u_i(s_i,s_{-i}) - u_i(s_i',s_{-i})]\ge0$	Polynomial by LP; also for many succinct games; optimizing it often NP-hard
Zero-sum Nash	$v_r = v^* = v_c$	Polynomial by LP (a dual pair)
Subgame perfect	Nash after every prefix of play	Backward induction; linear time under perfect information
Reduced strategic form	Identify moves after an own move that makes them unreachable	Smaller, but still possibly exponential
Sequence form	Realization plans $Ex=e$ , $Fy=f$ with sparse $A,B$	Linear in the tree; zero-sum by LP, general-sum by Lemke
Bayesian Nash	Best response given beliefs about others’ types	i.i.d. first price: bid $\mathbb{E}[\text{second value}\mid v_i \text{ max}]$
Strong Nash	No coalition has a joint deviation	Rare; exists for stable marriage
Core	$\sum_{i\in A}x_i \le c(A)$ for all $A$ , with $\sum_N x_i = c(N)$	May be empty; emptiness testing studied per game
Shapley value	Expected marginal cost over a random order	Always exists; may miss the core

Facts to keep to hand:

Standard form is $ns^n$ numbers, so complexity statements are only meaningful for succinct representations — otherwise brute force over supports is “polynomial” in a ridiculous input.
Two players are tractable because payoffs are linear in the opponent’s probabilities, giving polyhedra; three or more give polynomial systems needing different methods.
Nondegeneracy does three jobs at once: equal support sizes, at most $m$ (resp. $n$ ) labels per point, and uniqueness of the next vertex on an LH path.
A nondegenerate bimatrix game has an odd number of equilibria — the parity argument that later becomes PPAD.
LH finds one equilibrium and some equilibria are elusive to it for every missing label; varying $k$ and restarting from found equilibria helps but is not complete.
Complementary slackness in the sequence form is the best response condition, restated for the LP dual.
The reason NASH is not NP-complete is guaranteed existence; twist the problem to remove that guarantee and NP-completeness returns immediately (Gilboa–Zemel).
Every hardness argument here routes through Brouwer: Nash’s existence proof uses it, and the reduction goes back the other way.
Two players versus three is a real dividing line for rationality of the solution — which is exactly why the simulation of many players by few must be approximate.
The gadget trick that makes everything work: input players have no incoming edges, so their utilities are unconstrained and they can be reused freely.
Comparators must be brittle at $1/2$ ; non-brittle ones would let you build a game with no equilibrium. The averaging-over-a-fine-grid construction exists solely to smooth this.
Nash = correlated + product distribution. That one nonconvex constraint separates LP-easy from PPAD-complete.

References

[[lit/algorithmic-game-theory|Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory]] — chapters 1 (Tardos & Vazirani), 2 (Papadimitriou) and 3 (von Stengel)