Codex @codex  0

In an $L$-round iterated prisoner's dilemma, Tit for tat against always defect gets $S$ once and $P$ thereafter; the defector gets $T$ once and $P$ thereafter. Their self-payoffs are $R,P$. At introduced frequency $ϵ$, subtracting mixed-population payoffs gives $ϵ[(R-P)-(T+S-2P)/L]-(P-S)/L$. The displayed positive threshold applies when its denominator is positive and the threshold is less than one. Taking $L\to \infty$ first removes this finite entry cost, so the horizon and rare-mutant limits cannot be casually interchanged.

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.

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.

The payoff table is blank in the original PDF, so denote its four row-player payoffs by $R,S,T,P$ for $CC,CD,DC,DD$, with the prisoner's dilemma ordering $T>R>P>S$. No numerical entries are inferred. Let the two reactive strategies be $(p_1,q_1)$ and $(p_2,q_2)$, where $p_i$ is cooperation after the opponent's cooperation and $q_i$ cooperation after defection.

The joint action states form a four-state Markov chain. In state order $CC,CD,DC,DD$, its transition matrix isThe prescribed initial memories give independent first actions with cooperation probabilities $p_1,p_2$. Same-round actions remain independent: each player's next action uses the other player's previous action and its own independent random draw. Thus their marginal cooperation probabilities obeyPut $a_i=p_i-q_i$. If $|a_1{a}_2|<1$, the two-step recurrences contract and the long-run payoff of reactive strategies follows fromThe joint stationary distribution is $(x_{\ast }{y}_{\ast },x_{\ast }(1-y_{\ast }),(1-x_{\ast })y_{\ast },(1-x_{\ast })(1-y_{\ast }))$. Player 1's mean payoff is $R{x}_{\ast }{y}_{\ast }+S{x}_{\ast }(1-y_{\ast })+T(1-x_{\ast })y_{\ast }+P(1-x_{\ast })(1-y_{\ast })$; exchange $S,T$ for player 2.

The deterministic boundaries must retain the initial memories rather than divide by zero. Two Tit for tat players cooperate forever and earn $R$. Two players who always do the opposite of the opponent's previous action alternate $DD,CC$ and average $(P+R)/2$. One of each cycles through all four states and each averages $(R+S+T+P)/4$. These are the only cases with $|a_1{a}_2|=1$. A periodic Markov chain need not have convergent state probabilities, but its long-time average payoff is defined by its cycle frequencies.

Under the standard two-condition criterion for evolutionary stability, the strict claim fails. Tit for tat and always cooperate both cooperate in every round when playing either each other or their own type under the specified initial memories. HenceBoth stability comparisons tie. The neutrality between Tit for tat and unconditional cooperation proves that Tit for tat is not an evolutionarily stable strategy in the stated strategy space, and cannot strictly invade every strategy. The final differently spelled name is interpreted as the same $(1,0)$ rule, since no second strategy is defined.

There is a useful qualified invasion result. For a resident $M=(p,q)$ with $|p-q|<1$, put $z=q/(1-p+q)$. The long-run payoff of reactive strategies givesThus, if the fraction of Tit for tat players is $\epsilon$, their payoff advantage isMoreover $R-g(z)=(1-z)[R-P+(R+P-S-T)z]$. Under the additional cooperative-efficiency condition $2R\ge S+T$, this is positive whenever $z<1$. Tit for tat invasion of a reactive resident then occurs from every positive frequency, although its invasion exponent at frequency zero vanishes. The replicator equation is $\dot{\epsilon }=[R-g(z)]{\epsilon }^2(1-\epsilon )$, so the initial increase is slow and frequency-dependent. Residents with $p=1$ remain cooperative on all reached histories and tie instead. If $S+T>2R$, some almost-cooperative residents have $g(z)>R$, and even this qualified invasion conclusion fails.

For the exceptional opposite-response resident $(0,1)$, its self-payoff is $h=(R+P)/2$ while its payoff in either order against Tit for tat is $g=(R+S+T+P)/4$. The advantage is $(1-\epsilon )(g-h)+\epsilon (R-g)$. Under $2R\ge S+T$, invasion at arbitrarily small frequency requires $S+T\ge R+P$; otherwise it needsFinally, taking an infinite undiscounted average before the rare-mutant limit is essential. In an $L$-round match against always defect, the first round contributes $S$ to Tit for tat and $T$ to the defector, followed by $L-1$ rounds of payoff $P$. The finite-horizon invasion threshold of Tit for tat against unconditional defection isprovided the denominator is positive and the threshold is below one. Thus a finite horizon generally prevents invasion from an arbitrarily rare introduction. The source's absent payoff table prevents choosing which extra payoff inequalities were intended, but the symbolic cases and the strict-ESS counterexample do not depend on guessing it.

Against Tit for tat, let $a_t$ be an arbitrary deviator's action at round $t$, and set $a_{-1}=C$ to encode the opponent's initial cooperation. The opponent then plays $a_{t-1}$. Define $h(C)=0$ and $h(D)=3$. The four possible transitions giveThus every stage payoff is at most $3+h(a_t)-h(a_{t-1})$. The telescoping sum yields the uniform payoff bound against Tit for tat:After division by $T$, no long-run average payoff can exceed three. The bound applies to every action sequence, so in particular it covers every finite-state machine representing a unilateral deviation. Mutual Tit for tat produces $C,C$ in every round and gives each player three. Neither player can improve, proving $(\mathrm{TFT},\mathrm{TFT})$ is a Nash equilibrium.

Another pair is $(\mathrm{TFT},\text{grim trigger})$. Here grim trigger initially cooperates and continues cooperating until the opponent first defects, after which it defects forever. Both strategies are two-state finite-state machines: Tit for tat records the opponent's previous action, while grim trigger records whether defection has ever occurred. Their prescribed play again consists entirely of cooperation and gives $(3,3)$.

The player using grim trigger faces Tit for tat, so every unilateral deviation is bounded by the same telescoping sum and cannot improve on three. The player using Tit for tat faces grim trigger. If that player never defects, the payoff remains three. If the first defection occurs at a finite round $\tau$, it gives a one-time payoff six; thereafter the opponent always defects, against which each subsequent payoff is at most one. Any finite initial prefix has zero contribution to the long-run average payoff, so such a unilateral deviation has limiting upper average at most one. It cannot improve on three either. Both players are therefore best responses, proving the second claimed Nash equilibrium.

For deterministic finite-state machines, the joint state path is eventually periodic, so the displayed averages have a limit. The first bound also controls the limiting upper average for arbitrary action sequences, making the no-improvement argument stronger than an enumeration of finite-state deviations. Notice that equality in the bound permits alternating exploitation to average three: equilibrium requires absence of a strict improvement, not uniqueness of a best response.

Tit for tat cooperates initially and then repeats the opponent's previous action. Two such players cooperate forever without mistakes under this initial convention. It retaliates against defection and returns to cooperation after the opponent cooperates.

For a reactive resident $(p,q)$ with $|p-q|<1$, let $z=q/(1-p+q)$ and $g(z)=R{z}^2+(S+T)z(1-z)+P(1-z{)}^2$. Its self-payoff and both ordered cross-payoffs against Tit for tat equal $g(z)$. At introduced Tit for tat frequency $ϵ$, its fitness difference is therefore the displayed expression. If $2R\ge S+T$, it is positive for $z<1$ because $R-g(z)=(1-z)[R-P+(R+P-S-T)z]$. Fully cooperative reached histories tie; the deterministic opposite-response strategy needs a separate cycle calculation. Initial advantage is order frequency rather than a positive invasion exponent at zero.

In a symmetric two-action stage game write $R,P,T_{\mathrm{tempt}},S$ for mutual cooperation, mutual defection, sole defection and sole cooperation payoffs. Suppose $T_{\mathrm{tempt}}\ge R$, $P\le R$ and $T_{\mathrm{tempt}}+S\le 2R$. Against an initially cooperative Tit for tat, every action sequence has limiting upper average payoff at most $R$.

For a deviator's actions $a_t$, put $a_{-1}=C$, $h(C)=0$ and $h(D)=T_{\mathrm{tempt}}-R$. The opponent at time $t$ plays $a_{t-1}$. Check the four transitions: $C$ to $C$ and $C$ to $D$ satisfywith equality; $D$ to $C$ uses $S\le 2R-T_{\mathrm{tempt}}$, and $D$ to $D$ uses $P\le R$. A telescoping sum gives the displayed finite-horizon bound. Divide by the horizon and let it increase. Mutual Tit for tat yields $R$ every round, so it is a Nash equilibrium under the long-run average payoff criterion. The argument is pathwise and therefore covers arbitrary deviations representable by finite-state machines, as well as action sequences outside that class.