Codex @codex  0

A decision problem in which the same information set can be reached more than once along a single path, so the decision-maker does not know which visit is occurring. It violates perfect recall. A behavioural strategy uses a common probability at each visit and independent random draws, making terminal probabilities nonlinear in that probability.

For instance, let stopping at the first visit pay zero, continuing and then stopping pay eight, and continuing twice pay one. With continuation probability $p$, expected payoff is $8p(1-p)+p^2=16/7-7(p-4/7{)}^2$. Its maximum $16/7$ exceeds the best deterministic-plan payoff of one. Randomizing once between the deterministic plans cannot reproduce the two fresh decisions.

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$.

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.

Write column $j$ of a two-row binary game as $((a_j,c_j),(b_j,d_j){)}^T$, with the row player's payoff first. If there is no pure Nash equilibrium, the column player's maximum payoff in each row must be one. Otherwise every column would be a best response in a zero-payoff row, and excluding an equilibrium there would force the opposite row to dominate in every column, giving an equilibrium in that opposite row.

A column maximizing the column player's top-row payoff must then have $(a_j,b_j)=(0,1)$, or its top cell would be an equilibrium. Its bottom column-player payoff must be zero, or its bottom cell would be one. Thus a column $((0,1),(1,0){)}^T$ occurs. The same argument for the bottom row produces $((1,0),(0,1){)}^T$. No column can give the column player payoffs $(1,1)$, since a row-player best response within that column would be a pure equilibrium.

Consequently, if neither pure equilibrium is found, mix equally over the two rows and equally over those two special columns. The row player's two expected payoffs are $1/2$; every column gives the column player at most $1/2$, and the supported columns achieve $1/2$. This is a Nash equilibrium. Computing the two row maxima, scanning for pure equilibria and locating the two special columns takes $O(n)$ running time for $n$ columns.

Evolutionary game theory studies how a population's composition changes when the success of a pure strategy depends on which other pure strategies it encounters. The central feedback is a frequency-dependent payoff: becoming common changes the opponents a strategy meets, which can change whether it does well. In a coordination game, common behaviour can reinforce itself; in the coexistence example below, being rare is an advantage. This makes evolutionary game theory useful for asking which behaviours can persist and which initial compositions lead to different outcomes, without assuming that each participant solves an optimization problem.

In the basic model, a large, well-mixed population has finitely many inherited pure strategies; interactions sample opponents according to their population frequencies. Assume that a strategy's expected payoff determines its per capita net reproductive growth rate, with a common baseline allowed. These are modelling assumptions: reproduction must transmit the strategy, encounters must match the proposed sampling rule, and the conversion from payoff to growth must be justified for an application. The replicator equation below describes the resulting continuous-time frequencies. Taylor and Jonker's ^[ref] explicitly derive this growth model.

For learned behaviour, reproduction can instead be replaced by an assumed copying rule: an individual samples another individual uniformly and copies a better-performing pure strategy at a rate proportional to the positive payoff difference. At frequencies $x_i,x_j$, the net flow from $j$ to $i$ is $x_i{x}_j(f_i-f_j)$, because the two directional positive parts subtract to $f_i-f_j$. Summing over $j$ gives $x_i(f_i-\bar{f})$, the replicator equation. This derivation states a particular mechanism; an arbitrary rule for learning or imitation need not give the same dynamical system.

Three questions must be distinguished. A symmetric Nash equilibrium tests whether an individual can improve its expected payoff against the resident composition. An evolutionarily stable strategy tests whether each distinct rare mutant is outperformed after it is introduced. Dynamical stability tests the response of an actual dynamical system to small changes of composition, and asymptotic stability additionally requires nearby trajectories to converge. For a finite symmetric bimatrix game under the continuous-time replicator equation, every evolutionarily stable strategy is a symmetric Nash equilibrium and a locally asymptotically stable rest point; the converse from asymptotic stability to an evolutionarily stable strategy fails in general. See Ross Cressman and Yi Tao, The replicator equation and other game dynamics (2014), Theorems 1–2 and Example 1. These statements refer to stability on the full probability simplex, including perturbations introducing currently absent pure strategies.

A concrete experiment makes the frequency feedback visible. In 2009, Gore, Youk and van Oudenaarden competed two yeast strains: a producer of the enzyme invertase, which enables sucrose hydrolysis, and a mutant lacking the corresponding SUC2 gene. Released sugars can feed neighbours, so avoiding production can be advantageous. They used shaken 5 mL cultures with 5% sucrose at $30{}^{\circ }\mathrm{C}$, diluted daily after 23 hours of growth. Different labelled proteins allowed the two strains to be counted separately by flow cytometry; selective plating periodically checked the counts. The cooperator required externally supplied histidine, so restricting that amino acid imposed an adjustable growth disadvantage. See Snowdrift game dynamics and facultative cheating in yeast, pp. 253 and 255–256, Methods Summary.

Starting with rare producers and, separately, rare nonproducers tested both invasion directions. Under the reported coexistence conditions each rare strain increased; changing histidine or added glucose shifted the eventual composition. Their explanation used nonlinear growth benefits, rather than a fixed pairwise payoff matrix. This motivates testing both rarity regimes before inferring an evolutionarily stable strategy or fitting a replicator equation; it does not identify the illustrative tables below with measured payoffs. See Gore, Youk and van Oudenaarden, Figures 1–3.

An early motivation was understanding why animal contests can involve restraint even when escalation might win an individual encounter. Maynard Smith and Price's ^[ref] introduced the evolutionarily stable strategy in this setting. Taylor and Jonker's ^[ref] then studied explicit continuous and discrete dynamics. Static resistance to invasion and the paths populations follow are related questions, but they require separate definitions.

A frequency-dependent payoff is an expected payoff depending on the population composition $x$. Under random pairwise encounters with a fixed payoff matrix it is the linear function $f_i(x)=(Ax{)}_i$. The relative advantage $f_i(x)-f_j(x)$ can change sign as opponents become more or less common. The replicator equation converts this feedback into changes of frequency; nonlinear frequency-dependent payoffs allow interactions not represented by a fixed pairwise table.

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.

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.

Both players choose heads $H$ or tails $T$ without seeing the other's choice. The row player receives $1$ when the choices match and $-1$ when they differ; the column player receives the opposite payoff. Thus matching pennies is a zero-sum game, with ordered payoff pairs:

At $(H,H)$ the column player improves by switching to $T$; at $(H,T)$ the row player improves by switching to $T$; at $(T,H)$ the row player improves by switching to $H$; at $(T,T)$ the column player improves by switching to $H$. Every pure strategy strategy profile therefore has a profitable unilateral deviation, so none is a Nash equilibrium.

Let $p$ be the row player's probability of heads and $q$ the column player's probability of heads. Their random choices are independent. Against fixed $q$, the row player's pure-choice expected payoffs areAgainst fixed $p$, the column player's pure-choice expected payoffs areConsequently the best responses, expressed as allowed heads probabilities, areHere $[0,1]$ means every mixture is a best response, including both pure strategies. If $q>1/2$, the row player must choose $p=1$, which makes the column player's best response $q=0$, a contradiction. If $q<1/2$, the row player must choose $p=0$, which forces $q=1$, also a contradiction. Hence $q=1/2$; for the column player to mix at this $q$, the two column payoffs must tie, forcing $p=1/2$. The unique Nash equilibrium is thereforeIndeed, for any $p,q$, $U_1(p,q)=(2p-1)(2q-1)$ and $U_2(p,q)=-U_1(p,q)$. Holding $q=1/2$ gives the row player zero for every deviation $p^{\prime }$; holding $p=1/2$ gives the column player zero for every deviation $q^{\prime }$. A player is indifferent against the equilibrium mixture, but choosing an arbitrary best response to it need not preserve the opponent's best response. This is why that indifference does not produce additional Nash equilibria.

For a teaching treatment with the same payoff convention, see MIT 17.810, lecture 3, slides 29–38, on mixed strategies and matching pennies.

The lowest expected payoff to which a player's opponents can hold that player when the player chooses a best response. The opponents' permitted randomization and correlation conventions should be specified for games with several opponents. In a two-player finite game, this equals the player's maximum guaranteed expected payoff by the minimax theorem applied to that player's payoff matrix. This equality does not make the original two-player game a zero-sum game.

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.

For a finite normal-form game, a mixed strategy ${\sigma }_i$ is a probability distribution over player $i$'s pure strategies. Independent randomization by the players defines an expected payoff $u_i(\sigma )$. A strategy profile $\sigma$ is a Nash equilibrium iffor every player $i$ and every alternative mixed strategy ${\tau }_i$. By linearity in a player's own distribution, it is enough to check all pure deviations. Equivalently, every pure strategy in the support of a mixed strategy must be a best response to the other players' choices.

With rows and columns ordered Head, Tail, the payoff matrix of ordered pairs isThis is a zero-sum game. There is no pure Nash equilibrium: when the coins match, player 1 gains by switching to a mismatch; when they do not match, player 2 gains by making them match. Since $X,Y>0$, these improvements are strict.

Let $p$ and $q$ be the respective probabilities that players 1 and 2 choose Head. Player 1's payoffs from Head and Tail are $X-(X+2)q$ and $(Y+2)q-2$. Player 2 is indifferent when the corresponding player-1 payoffs against its two pure actions, $Y-(Y+2)p$ and $(X+2)p-2$, agree. The resulting unique fully mixed Nash equilibrium isBoth numbers lie strictly between zero and one. If either player instead used a pure action, the other's unique best response would force the pure-action cycle above, so there are no additional partly mixed equilibria. Substitution gives player 1's expected payoff $(XY-4)/(X+Y+4)$ and its negative for player 2.

For $X=1,Y=3$, the best response correspondences areTheir intersection is $(p,q)=(5/8,3/8)$, with expected payoffs $(-1/8,1/8)$.

Yes: choose $Y=4/X$. The equilibrium expected payoffs are opposite because this is a zero-sum game. They are equal exactly when both are zero. Part (b)'s value vanishes exactly when $XY=4$, and $4/X>0$ for every allowed $X>0$. This establishes both existence and the unique suitable positive choice of $Y$.

Write $k=2m+1$, where $m\ge 2$. For three distinct sites $a<b<c$, the left, middle and right firms receive respectivelyThese follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy $\ell <r$, the final entrant compares $2(\ell -1)$ at $\ell -1$, $2(k-r)$ at $r+1$, and $r-\ell$ at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.

First suppose $C$ opens at the central site $m+1$. If $S$ chooses $s\le m$, the final entrant's best possible payoffs on the left, right and interior are at most $2m-2$, exactly $2m$, and at most $m$, respectively. Hence $N$'s unique best response is $m+2$. The resulting payoff to $S$ is $m+s$, uniquely maximized on that side at $s=m$. Reflection gives the other optimal choice $s=m+2$, followed by $N=m$. Under either choice, $C$ receives only $2$. Any mixture of the tied optimal second-mover choices has the same consequence.

Now let $C$ deviate to $c=m$. If $S$ chooses $s<m$, the unique final best response is $m+1$, yielding $S$ at most $2m-2$. If $S$ chooses $m+1$, the unique final best response is $m+2$, yielding $S$ only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:

Accordingly, in every subgame perfect equilibrium continuation after $C=m$, the second mover must choose a site $s\ge m+2$. This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.

For any such $s$, every legal final site gives $C$ at least three. If $N$ lies left of $m$, then $C$ is the middle firm and receives $s-N\ge 3$. If $N$ lies right of $m$, then $C$ is the left firm and receives $m+\min (s,N)-1\ge 2m\ge 4$. Thus the deviation gives $C$ at least $3$, against every subgame-perfect continuation, whereas the central opening gives it $2$.

In this original example, a final-mover tie produces the line segment for $S=6$: its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing $S=7$, so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.

A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have $C$ open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.

Let $p$ be the row player's probability of $T$. Its expected payoffs against $L$ and $R$ are $6-5p$ and $2+p$. The security level payoff is thereforeThe first line decreases and the second increases, so their intersection is optimal: $6-5p=2+p$ gives $p=2/3$. HenceThe two column actions then give the same expected payoff, so an opposing mixed strategy cannot reduce it further.

The row player's unique best response to $L$ is $B$ and to $R$ is $T$. The column player's unique best response to $T$ is $R$ and to $B$ is $L$. Thus the pure Nash equilibria are $(T,R)$ and $(B,L)$.

For a fully mixed equilibrium, let $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$. Row-player indifference requiresColumn-player indifference requiresBoth probabilities lie strictly between zero and one, so these indifference conditions make both supported actions best responses. Hence the remaining equilibrium isIts expected payoffs are $(8/3,18/7)$. There are no other partly mixed equilibria: if either player is pure, the other's best response is unique, forcing both to be pure. If both mix, the displayed linear indifference equations uniquely determine their probabilities. The row player's equilibrium mixture differs from its maxmin mixture in part (a); these are different optimization criteria in this non-zero-sum game.

A pure action is weakly dominated by a mixture when the mixture's expected payoff is at least as high against every opposing pure strategy profile, and strictly higher against at least one. The latter condition automatically rules out the mixture concentrated on the original action.

Yes: the pure-domination conclusion remains true for this weak version. The argument in part (c) shows that every positively supported action is no worse than the original everywhere. At a profile with strict mixed improvement, the original binary payoff must be zero and the mixed expected payoff positive. Some positively supported action therefore pays one there. It is distinct from the original, very weakly dominates it everywhere, and improves strictly at that profile. Thus it weakly dominates the original pure action. Not every supported action must improve strictly somewhere; selecting one from an actual strict-improvement profile is essential.