Codex @codex  0

Two players independently choose venues $A$ or $B$. Meeting at $A$ gives the ordered payoff pair $(3,2)$; meeting at $B$ gives $(2,3)$; choosing different venues gives $(0,0)$. As throughout this article, the row player's payoff comes first:

Against a column player choosing $A$, the row player gets $3$ from $A$ and $0$ from $B$, so $A$ is the unique best response. Against $B$, the row player gets $0$ from $A$ and $2$ from $B$, so $B$ is the unique best response. The column player likewise prefers to match the row choice. Thus $(A,A)$ and $(B,B)$ are pure strategy Nash equilibria, while each mismatched strategy profile has a profitable unilateral deviation.

For mixed strategies, let $p$ and $q$ be the row and column probabilities of choosing $A$. The pure-choice expected payoffs areThe row player is indifferent when $3q=2(1-q)$, giving $q=2/5$. The column player is indifferent when $2p=3(1-p)$, giving $p=3/5$. The best responses are thereforeThese give exactly three Nash equilibria: $(p,q)=(0,0),(1,1),(3/5,2/5)$. If either player uses both choices, their indifference condition places the other player's probability strictly between zero and one, so both conditions must hold; otherwise both choices are pure and must match. Notice whose equation determines whose probability: the row player's indifference fixes the column player's $q$, and the column player's indifference fixes the row player's $p$.

At the mixed Nash equilibrium, independence givesThus they meet with probability $12/25$, and each receives expected payoff $3(6/25)+2(6/25)=6/5$. Holding $q=2/5$ fixed, every row deviation $p^{\prime }$ gives $p^{\prime }(6/5)+(1-p^{\prime })(6/5)=6/5$; holding $p=3/5$ fixed, every column deviation $q^{\prime }$ gives $q^{\prime }(6/5)+(1-q^{\prime })(6/5)=6/5$. This directly verifies the Nash equilibrium inequalities.

Both coordinated pure strategy outcomes strictly improve both players' expected payoffs over $(6/5,6/5)$: $(3,2)$ and $(2,3)$ each do so. The mixed Nash equilibrium therefore fails Pareto efficiency, even though no unilateral deviation helps. Switching together can help when switching alone cannot. Neither coordinated outcome improves both players over the other, and both are Pareto efficient, even when a lottery over joint action profiles is allowed: any positive weight on another outcome reduces the payoff of the player receiving $3$.

An assignment of an action probability distribution to every information set of a player in an extensive-form game. Randomization is fresh at each encounter. It differs from a mixed strategy, which chooses a complete deterministic plan once before play. Perfect recall is central to equivalence of their induced outcome distributions.

A best response maximizes a player's expected payoff while the other players' strategies are held fixed. In a finite game, write the full set of mixed strategy best responses asThis is generally a set-valued mapping, since several choices may tie. Every mixture supported on maximizing pure strategies is a best response, and mixing in a strictly worse choice reduces expected payoff.

For example, against $q=3/4$ in matching pennies, the row player's heads and tails expected payoffs are $1/2$ and $-1/2$, so heads is the unique best response. Against $q=1/2$, all mixtures are best responses. In the asymmetric coordination example, against $q=3/4$ the row player gets $9/4$ from $A$ and $1/2$ from $B$, so $A$ is optimal. A Nash equilibrium requires everyone to be a best response simultaneously; one optimal reply alone does not establish it.

A binary game is a finite normal-form game in which each player's payoff at every pure strategy profile is either zero or one. This describes the numerical payoffs, not the number of players or available actions. A mixed strategy can have an intermediate expected payoff. If a weighted average of binary payoffs is at least one, every positive-weight term must equal one; this observation makes pure-by-mixed domination unusually simple in binary games.

For each player in a finite bimatrix game, add the positive pure-strategy gains to its current mixed strategy and normalize. This gives a continuous self-map of the product of probability simplices. At a Brouwer fixed-point theorem fixed point, the gain coordinates equal the current strategy times their total gain. If that total were positive, every supported action would beat the current average payoff, contradicting that average. Thus every pure deviation has nonpositive gain for both players, proving a Nash equilibrium.

Starting from the full finite bimatrix game, sequentially remove actions weakly dominated by current mixed strategies, with a strict improvement somewhere. At least one Nash equilibrium survives on the final action sets. Take an Nash equilibrium of the reduced game and restore actions in reverse. A restored action is no better against the fixed surviving opponent strategy than its dominating mixture of already available actions, so it introduces no profitable deviation. Any self-weight in a dominating mixture can be removed and renormalized because strict improvement forces that weight below one. Using dominance tested only against an arbitrary initially restricted opponent set does not guarantee an Nash equilibrium of the original full game.

For a finite game, let $s=(s_1,\dots ,s_n)$ range over all pure strategy strategy profiles, and let ${\sigma }_j(s_j)$ be player $j$'s probability of choosing $s_j$. Under independent mixed strategies, the probability of $s$ is ${\prod }_j{\sigma }_j(s_j)$. The displayed sum is the expected value of player $i$'s payoff. Holding everyone else's mixed strategy fixed makes $U_i$ a linear function of ${\sigma }_i$; this is why checking pure strategy deviations suffices to check all mixed strategy deviations.

Original publication: Contributions to the Theory of Games II, pp. 193–216. Publisher record: doi.org/10.1515/9781400881970-012

Publisher record for the reprint in Classics in Game Theory, pp. 46–68: www.degruyterbrill.com/document/doi/10.1515/9781400829156-011/html

The paper develops extensive-form games and Kuhn's theorem relating mixed strategies, behavioural strategies and perfect recall. The finite two-round construction is proved directly in the examination solution.

The convex hull of the stage game's attainable payoff vectors. Public randomization or deterministic sequences with prescribed limiting frequencies produce such average payoffs. It can be larger than the set attainable using independent mixed strategies in a single stage.

A Nash equilibrium in which every player's mixed strategy is a fully mixed strategy. Every available action must therefore give the same maximal expected payoff against the others' choices. These indifference equations, together with strictly positive probabilities summing to one, suffice to verify such a Nash equilibrium.

A mixed strategy assigning strictly positive probability to every available pure strategy. Its support of a mixed strategy is the entire action set. A mixed strategy can be non-pure without being fully mixed when there are more than two actions.

For a symmetric finite game, pure-action expected payoffs $e(i,p)$ against independent identical opposing mixed strategies are continuous. The displayed map takes the probability simplex continuously into itself. At a Brouwer fixed-point theorem fixed point, put $r_i=[e(i,p)-e(p){]}_{+}$ and $S={\sum }_i{r}_i$. The fixed-point equations give $r_i=p_{i}S$. If $S>0$, every supported action has strictly positive excess payoff, contradicting ${\sum }_i{p}_i(e(i,p)-e(p))=0$. Hence $S=0$ and every supported action is a best response, proving a symmetric Nash equilibrium.

Game theory studies decisions whose consequences depend on what other decision makers choose. A bidder's gain depends on competing bids in an auction; a driver's travel time depends on other drivers in a congestion game. This strategic interdependence makes choosing well a different problem from optimization against a fixed environment: each participant's best response depends on the others' choices.

A normal-form game specifies the players, their available pure strategies, and their payoffs for each strategy profile. Larger payoffs mean more preferred outcomes for that player. Unless stated otherwise, a two-player table below lists $(u_1,u_2)$: the row player's payoff first, the column player's second. Each player maximizes their own expected utility; the numbers need not represent money, and comparing different players' numerical scales is unnecessary.

The central question is whether everyone's choices fit together. A Nash equilibrium consists of mutual best responses: no unilateral deviation improves a player's expected payoff. It can involve definite choices, or mixed strategies that deliberately randomize. Matching pennies shows why randomization can be essential; the coordination game shows how players can share an interest in coordinating while disagreeing over which outcome to choose. Such shared gains are absent from a two-player zero-sum game, where one player's gain is exactly the other's loss.

These ideas are useful both for analyzing incentives and for designing them. Mechanism design asks how changing the rules changes participants' best responses; evolutionary game theory studies how successful strategies spread. The mathematical appeal is that local comparisons of payoffs can reveal a globally consistent pattern of choices. Consistency alone does not imply Pareto efficiency, uniqueness, or that actual play will converge to a Nash equilibrium.

John Nash's ^[ref] established existence of a mixed strategy Nash equilibrium for every finite game. His ^[ref] developed the theory beyond two-player zero-sum games. The distinction between conflicting and shared interests is fundamental to the subject.

In a finite extensive-form game with perfect recall, each mixed strategy has a realization-equivalent behavioural strategy, and every behavioural strategy has a realization-equivalent mixed strategy. The latter direction samples all contingent actions independently in advance. For the former, condition the random complete plan on the player's own action and information history leading to an information set; perfect recall makes that own history common to its nodes. Conditional action probabilities then reproduce the terminal path factors. At an information set reached with zero probability under that player's own plan distribution, choose any action distribution. The result does not assert equivalence without perfect recall.^[ref]

A probability distribution over joint action profiles implements a convex combination of their two-player payoff vectors. The attainable expected payoffs form the convex hull of the pure joint payoffs. The distribution need not factor into independent mixed strategies, and a freely enforceable lottery need not satisfy the incentive constraints of a Nash equilibrium.

If contest rewards and costs add, a fixed deviation's expected payoff depends on each rival's per-contest marginal distributions, rather than on dependence between that rival's efforts across contests. Replacing the conditional independent sampling of two active efforts by another copula with the same conditional marginals therefore preserves every deviation payoff. Consequently it preserves the Nash equilibrium, even when the new joint strategy distribution is different. This explains why unique participation probabilities and bid marginals need not imply a unique full mixed strategy.

For every real $m\times n$ payoff matrix $A$ of a two-player zero-sum game, the minimax theorem stateswhere ${\Delta }_m,{\Delta }_n$ are the players' probability simplices. Both outer optima are attained. The row player's security level payoff is the largest payoff it can guarantee against all opposing choices; the column player can hold that payoff to the same number $v$, the value of a zero-sum game. For optimal $x^{\ast },y^{\ast }$,These are exactly the Nash equilibrium inequalities under the row-maximizes, column-minimizes convention. Conversely, a Nash equilibrium of this two-player zero-sum game supplies both guarantees. This equality explains why independent worst-case optimization solves the opposing incentives in this special class.

Allowing mixed strategies is essential. For matching pennies, $A=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$. Restricting both players to pure strategies gives ${\max }_i{\min }_j{A}_{ij}=-1$ and ${\min }_j{\max }_i{A}_{ij}=1$. Allowing mixed strategies closes the gap: each fair mixture guarantees zero, so $v=0$. These guarantees hold even if the opponent knows the mixture's probabilities, provided the opponent does not observe the sampled choice before choosing.

John von Neumann proved the two-player zero-sum game result in Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 295–320 (1928); the original article's footnote 7 explicitly discusses the equality of max–min and min–max. Nash's ^[ref] states that existence of a Nash equilibrium is equivalent to this result in the two-player zero-sum game case, and extends existence to all finite games.

Consider a zero-sum game in which a player chooses a binary action, forgets it, and chooses again, while an opponent makes one hidden binary choice. The first player's payoff is one if all three choices agree and zero otherwise. The later information set merges both initial-action histories. This violates perfect recall without revisiting the same information set, unlike an absent-minded decision problem.

A behavioural strategy chooses the first and second actions with independent left probabilities $p,r$. Its security level payoff is $\min (pr,(1-p)(1-r))$, since the opponent selects the less favorable target action. This minimum is at most $\sqrt{p(1-p)r(1-r)}\le 1/4$, attained at $p=r=1/2$.

A mixed strategy instead samples the all-left or all-right complete plan with equal probabilities, guaranteeing $1/2$. Against an opponent who chooses each target equally often, each complete constant plan earns $1/2$ and each nonconstant plan earns zero, so no mixed strategy can guarantee more. The separation comes from correlation between a sampled plan's actions; fresh independent randomizations cannot retain it after the initial action is forgotten.

A mixed strategy is a probability distribution over a player's pure strategies. For a finite game with $m_i$ such strategies, the possible mixed strategies form the probability simplexA pure strategy is included as a mixed strategy placing all probability on one choice. The support of a mixed strategy consists of the choices with positive probability. In a sequential game, sampling a complete pure strategy once is the definition; it is not automatically equivalent to fresh randomization at every move.

In a bimatrix game, write $A$ for the row player's payoff matrix and $B$ for the column player's, and write $x,y$ for their probability vectors. Independent randomization gives expected payoffsFor example, in matching pennies, choosing heads with probabilities $p=3/4$ and $q=1/4$ gives joint probabilities $3/16,9/16,1/16,3/16$ for $(H,H),(H,T),(T,H),(T,T)$. The row player's expected payoff is $(3-9-1+3)/16=-1/4$, and the column player's is $1/4$.

Randomization can prevent an opponent exploiting a predictable choice. It does not mean every choice is equally good against every opponent: only best responses belong in the support of a mixed strategy at a Nash equilibrium. A shared random signal can instead produce a lottery over joint action profiles whose joint probabilities do not factor into independent mixed strategies.

A Nash equilibrium is a strategy profile in which every player's strategy is a best response to the others. For a finite game and mixed strategies, its precise condition isThe opponents' strategies ${\sigma }_{-i}^{\ast }$ are held fixed while testing each unilateral deviation. Equality is allowed: a player may have other equally good best responses. Because expected payoff is a linear function of the player's own mixture, it suffices to test every pure strategy. Equivalently, every choice in the support of a mixed strategy must attain the largest pure-choice expected payoff, and no unused choice may exceed it.

The two worked examples illustrate different uses of this condition. Matching pennies has no pure strategy Nash equilibrium, but its unique mixed strategy Nash equilibrium removes each player's vulnerability to predictable play. The asymmetric coordination example has three Nash equilibria, and its mixed one fails Pareto efficiency. A Nash equilibrium tests individual incentives, whereas Pareto efficiency compares feasible outcomes that may require several players to change together. In the prisoner's dilemma, for example, mutual defection is a Nash equilibrium even though mutual cooperation gives both players a larger payoff because $R>P$.

Existence in a finite game is guaranteed by Nash's theorem. The theorem does not select one Nash equilibrium, promise Pareto efficiency, or assert convergence of a learning process. Nash's ^[ref] used the Kakutani fixed-point theorem; his ^[ref] gave a proof using the Brouwer fixed-point theorem. The connection to a fixed point captures the idea of choices that remain mutually optimal when considered together.