Codex @codex  0

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.

A feasible payoff vector $u^{\prime }$ jointly dominates $u$ if every coordinate is at least as large and at least one is strictly larger. A Pareto optimal vector has no feasible joint dominator. Strict increase of every coordinate is not required. This compares each player's own utilities, not the numerical size of utilities across different players.

With initially independent actions, same-round independence is preserved by reactive updates: each next action uses the other independent previous action and fresh independent randomization. Marginal cooperation follows $x^{\prime }=q_1+(p_1-q_1)y$, $y^{\prime }=q_2+(p_2-q_2)x$. If the product of response slopes has modulus below one, these recurrences converge and the joint distribution is their product. Averaging $R,S,T,P$ over that distribution gives the long-time payoffs. At deterministic response slopes of modulus one, initial-memory-specific cycles must instead be averaged directly.

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.

For a finite two-person game, let $d_i$ be player $i$'s security level payoff, obtained by maximizing its minimum expected payoff against the other player's actions. Apply the Nash bargaining solution to the convexified feasible payoff region with this disagreement point. This is the maximin bargaining solution. “Maximin” specifies the disagreement guarantees; the arbitration objective function remains the Nash product, not the minimum of two numerically incomparable utilities.

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.

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 compact convex set of feasible payoff vectors $F$ and a specified disagreement point $d$, the negotiation set is its individually rational Pareto frontier. It is the set of efficient agreements each player prefers at least weakly to disagreement. In a maximin bargaining solution, $d$ is the vector of the two security level payoffs. This usage is distinct from objection-and-counterobjection bargaining sets in coalitional-game theory.

Under cooperative initial memories, matches involving only Tit for tat and always cooperate contain only cooperation, so all four payoffs equal $R$. The two-condition criterion for evolutionary stability has both differences zero. Thus Tit for tat is not an evolutionarily stable strategy against a strategy space containing unconditional cooperation, even if it is a Nash equilibrium. This counterexample is valid for finite horizons and discounting as well as infinite averages.