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

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.

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.

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.

A grim trigger is a history-dependent pure strategy in a repeated game that switches permanently to punishment after a trigger event. In the iterated prisoner's dilemma above, the trigger is any player's observed defection, and punishment is always defect. Unlike Tit for tat, grim trigger never restores cooperation after the opponent cooperates again. Whether mutual grim trigger is a subgame perfect equilibrium depends on the stage payoffs, discount factor, and monitoring assumptions; it is not an unconditional property of the rule. See Ozdaglar, lecture 15, slides 12–15.

The iterated prisoner's dilemma is a repeated game with a prisoner's dilemma at each round. Earlier choices can change later best responses: a present gain from defection may be outweighed by lost future cooperation. A pure strategy now specifies an action after every possible observed history, including histories that its own prescribed play would never reach. The horizon, observations, initial actions, and payoff convention must be specified before assessing a Nash equilibrium or subgame perfect equilibrium.

For the following worked example, repeat the prisoner's dilemma above infinitely at rounds $t=0,1,\dots$. Assume public perfect monitoring: after each round both players observe both actions exactly, without error. They share a discount factor $0\le \delta <1$ and evaluate a path of stage payoffs $u_i(t)$ using the normalized discounted payoffThe round-zero weight is one before normalization, including when $\delta =0$. A larger discount factor gives future payoffs more weight; the geometric series makes a constant stage payoff have the same normalized value. These assumptions and normalization follow ^[ref]. The numerical payoffs here are our $3,5,0,1$ example; the lecture uses a different table.

Suppose both players use grim trigger: play $C$ initially and while every past action of both players was $C$; after any observed $D$, play $D$ forever. With no unilateral deviation, each gets normalized payoff $3$. A first unilateral deviation to $D$ earns $5$ now, then at most $1$ each round because the opponent switches permanently to always defect. The deviator attains that continuation payoff by choosing $D$ thereafter. At any history of mutual cooperation, the comparison is thereforeCooperation is a best response precisely whenEquivalently, without normalization the geometric series givesMultiplying both unnormalized payoffs by the same positive factor $1-\delta$ leaves the best response comparison unchanged.

For example, with discount factor $\delta =1/4$, the first unilateral deviation gives normalized payoff $4>3$, so mutual grim trigger is not a Nash equilibrium. At $\delta =3/4$, it gives $2<3$, so cooperation is preferable. At $\delta =1/2$ the two payoffs tie: the incentive to cooperate is weak, which is sufficient for a subgame perfect equilibrium.

The punishment is credible after every history containing a defection: the opponent's pure strategy then prescribes $D$ forever, and $D$ remains the stage best response, earning $1$ rather than $0$. Together with the cooperative-history comparison, this establishes mutual grim trigger as a subgame perfect equilibrium for $1/2\le \delta <1$. Delaying the first unilateral deviation merely delays the same gain or loss; further cooperation during punishment only lowers the deviator's payoff. Mutual always defect also remains a subgame perfect equilibrium, so patience permits cooperation without making it inevitable.

This calculation assumes an infinite horizon and $\delta <1$; it does not define a discounted payoff at $\delta =1$. With a finite, commonly known final round and positive weight on each round, backward induction instead gives mutual defection in every round of this stage game. Observational errors change the model too: one mistaken defection permanently activates grim trigger. Historical dependence, initial memories, and the payoff time convention also affect whether a cooperative rule resists or invades other pure strategies; the existing reactive strategy and Tit for tat discussions concern those additional questions.