= Solution
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 give
$$
\begin{array}{c|c|c|c}
a_{t-1}&a_t&u(a_t,a_{t-1})&3+h(a_t)-h(a_{t-1})\\\hline
C&C&3&3\\
C&D&6&6\\
D&C&0&0\\
D&D&1&3
\end{array}
$$
Thus 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>:
$$
\sum_{t=0}^{T-1}u(a_t,a_{t-1})\le3T+h(a_{T-1})-h(C)\le3T+3.
$$
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 \b[$(\mathrm{TFT},\mathrm{TFT})$ is a <Nash equilibrium>].
Another pair is \b[$(\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>.
Back to article page
