Codex @codex  0

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.

A repeated game criterion evaluating the average stage payoff over increasingly long horizons. State how paths without a limit are treated, for example by using a lower limit. Changing a finite prefix does not change a convergent long-run average payoff. Thus a one-time gain can be outweighed by permanent future punishment without specifying a discount factor.

Exactly $(T,L)$, $(M,C)$ and $(B,R)$ can be sustained as constant stage game outcomes. Their long-run average payoffs are $(6,6)$, $(4,4)$ and $(0,0)$, respectively. We assume the usual repeated game monitoring convention: both players observe each completed joint action before the next round. The source's colour convention puts the blue lower-left row payoff first and the red upper-right column payoff second.

For necessity, row action $B$ earns $(8,5,0)$ against $(L,C,R)$, so playing it forever guarantees a nonnegative long-run average payoff against every opposing pure strategy. Similarly, column action $R$ earns $(8,5,0)$ against $(T,M,B)$ and guarantees zero or more. Conversely, column action $R$ holds the row player's best possible stage payoff to $0$, and row action $B$ holds the column player's to $0$. Thus each player's minmax payoff is exactly $0$.

Any Nash equilibrium must give both players at least zero, an individually rational payoff in a repeated game. Every off-diagonal cell has a negative payoff for one player: $(T,C)$ and $(T,R)$ hurt row, $(M,L)$ and $(B,L)$ hurt column, $(M,R)$ hurts row and $(B,C)$ hurts column. Repeating any such cell forever therefore permits a profitable unilateral deviation to the zero-guaranteeing action. The three diagonal cells pass this necessary test.

For sufficiency, fix target $a^{\ast }=(T,L)$ or $(M,C)$. Each player's finite-state strategy has initial state $F$ and an absorbing state $P$. In $F$, output the player's component of $a^{\ast }$; remain in $F$ if the completed joint action equals $a^{\ast }$, and otherwise move to $P$. In $P$, row always outputs $B$ and column always outputs $R$, regardless of further observations. These are two-state grim trigger strategies; the separate machines are drawn below. The input is the observed joint action, so after any off-path history the prescribed continuation states agree.

If neither player deviates, the target is repeated forever. If a player first deviates at a finite round $\tau$, the opponent enters $P$ for all later rounds. Against column action $R$, every row action earns at most zero; against row action $B$, every column action earns at most zero. All payoffs are bounded, so the total reward before and at $\tau$, divided by the horizon, tends to zero. The deviator's upper limiting average is therefore at most $0$, below either target payoff $6$ or $4$. This proof tests arbitrary future deviations, not merely a single changed action. It also rules out improvement by deviations whose averages fail to converge, if the criterion is extended by an upper or lower limit.

For target $(B,R)$, one-state machines outputting $B$ and $R$ forever suffice: each is a best response to the other in every round. Their long-run average payoffs are zero and no unilateral deviation can improve them. In fact, the punishment is credible because $(B,R)$ is a stage Nash equilibrium, so the two positive-target constructions are also subgame perfect equilibria under the stated monitoring assumption. The general punishment mechanism is described in ^[ref].

“Outcomes of the stage game” here means a fixed action pair repeated forever. Allowing time sharing also sustains some average payoff vectors that are not stage cells: for example, a deterministic alternating cycle $(T,L),(M,C)$ gives $(5,5)$, with a two-phase finite-state strategy and the same permanent punishment. An off-diagonal cell may occur in a sustainable cycle; the impossibility above concerns its constant repetition, not every appearance on an equilibrium path. With finite-state pure strategies, an undisturbed path is eventually periodic, so its limiting cell frequencies are rational numbers.

Use the standard repeated game convention that the first round's joint action is observed before round two. The following original game tree represents simultaneous moves by making row move first in each round while hiding that current move from column. Terminal labels are total payoffs over both rounds, ordered row then column.

Formally, round one starts at a row decision with actions $T,B$. The two ensuing column nodes form one information set $I_2^0$, with available actions $L,R$; column cannot tell which current row action occurred. The four completed first-round histories are $H=\{TL,TR,BL,BR\}$. At each $h\in H$, round two begins at a separate row node. Its two successors, after row's current $T$ or $B$, form a column information set $I_2^h$. Distinct $h$ have distinct information sets: both players know the whole first-round outcome. There are sixteen terminal histories $(h,k)\in H^2$, whose total payoff is $u(h)+u(k)$, as displayed in the tree.

The row player's five information sets are the initial singleton and the four singleton round-two nodes, one per $h$. The column player's five information sets are $I_2^0$ and the four two-node sets $I_2^h$. Thus each player must specify one binary choice at each of five information sets, including histories that its own first choice might prevent:Counting only the four possible two-round action sequences would miss the distinct contingent responses to the opponent's first action.

For a concrete pair of complete pure strategies, order the second-round histories as $(TL,TR,BL,BR)$ and useThe first entry is the initial action, and the four remaining entries prescribe the action after each first-round history. This induces the unique path $TL$ in round one followed by $BR$ in round two. Hence the total payoff isThe off-path entries are part of each pure strategy, even though this pair does not reach them.

For randomization, a mixed strategy is a probability distribution over the $32$ complete plans, with $31$ free probabilities in a general distribution. A behavioural strategy instead gives one binary-action probability at each of five information sets, requiring five parameters. This game has perfect recall: a player never forgets a previous own action or a first-round observation, and the only concealed action is the opponent's current simultaneous choice. Consequently neither kind of randomization has a greater attainable-payoff advantage: Kuhn's theorem gives realization-equivalent strategies against every fixed opposing strategy.^[ref]

The equivalence can be verified directly here. Given a behavioural strategy, sample all five contingent actions independently before play; the resulting product probability distribution over complete plans is an equivalent mixed strategy. Conversely, let $\mu$ be a mixed strategy for player $i$. Use its marginal probability for the initial action. At history $h$ containing own first action $a_i$, choose second action $b_i$ with conditional probabilitywhenever the denominator is positive; if it is zero, choose arbitrarily at that unreachable history. The opponent's first-round action is simultaneous and cannot depend on the sampled hidden plan beyond the chosen first action. Thus conditioning on $h$ preserves exactly these conditional probabilities of actions, and multiplying the first- and second-round factors reproduces each terminal probability. Correlations between prescriptions at mutually exclusive second-round histories have no further observable effect. Behavioural strategies offer the more compact representation, while mixed strategies describe a single random choice of a full plan. Imperfect information here does not mean imperfect recall.

A repeated game plays a stage game over several rounds, allowing actions to depend on earlier observations. Its payoff convention must specify a finite horizon, a discount factor or a long-time average; these need not have identical invasion properties.

The normal-form game played once in each round of a repeated game. Its actions and payoffs are distinct from the repeated interaction's history-dependent pure strategies and aggregate payoffs. The same stage game can produce different incentive constraints under a finite sum, discounting or long-run average payoff criterion.