Codex @codex  0

A history-dependent pure strategy represented by a finite-state machine with an initial automaton state, an action output for each state, and an automaton transition after each observed completed joint action. A grim trigger strategy uses a following state and an absorbing punishment state. Two such deterministic machines jointly form a finite deterministic state system, so their action path is eventually periodic. Its long-run average payoffs are the averages over the eventual cycle; a finite initial prefix has vanishing weight.

A family of results describing the large set of Nash equilibrium payoffs available in indefinitely repeated interaction. For a finite game with observed past play, the discounted Nash version supports any feasible, strictly individually rational payoff in a repeated game when players are sufficiently patient.^[ref]

The mechanism is to prescribe a path and punish the first deviator by holding that player's future payoff to its minmax payoff. With long-run average payoffs, a finite gain disappears from the average; with discounting, the promised future loss must outweigh the gain. Weak boundary points require care when a stated theorem assumes strict inequalities. A construction proving a Nash equilibrium need not prove a subgame perfect equilibrium, because the punishers' continuation incentives may fail.

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.

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.

Measure all payoffs in millions of dollars, in the order (Ann, Bob). Since both players maximize expected money, those numbers are already their expected utility scale.

In the extensive-form game, Ann moves first. Staying out terminates at $(2,6)$. Entering leads to Bob's observed decision between fighting, with terminal payoffs $(1,1)$, and acquiescing, with terminal payoffs $(3,3)$. Each decision node is its own information set, so this is a perfect-information game.

The corresponding normal-form game gives Ann the pure strategies $O$ (stay out) and $E$ (enter), and Bob the complete contingent pure strategies $F$ (fight if entry occurs) and $A$ (acquiesce if entry occurs). The payoff matrix isThe pure strategy Nash equilibria are $(O,F)$ and $(E,A)$. Against $F$, Ann prefers $O$; against $A$, Ann prefers $E$. When Ann stays out, Bob's contingent response does not affect his payoff, so $F$ is a best response there.

There is exactly one subgame perfect equilibrium, $(E,A)$. In the subgame following entry, Bob strictly prefers $3$ to $1$, so backward induction selects acquiescence; Ann then strictly prefers entering for $3$ to staying out for $2$. The threat supporting $(O,F)$ is not optimal in that one-shot subgame.

For infinite repetition, the paper specifies no discount factor. First take the long-run average payoff convention, with all past actions observed. The feasible payoff set is the convex hullAnn can guarantee $2$ in every stage by staying out; Bob can guarantee at least $3$ in every stage by acquiescing whenever entry occurs. These guarantees are also their minmax payoffs: fighting holds Ann's best possible stage payoff to $2$, and entering holds Bob's best possible stage payoff to $3$.

Therefore the sustainable Nash equilibrium average payoffs are exactly the feasible, weakly individually rational payoffs in a repeated game:This is the closed triangle with vertices $(2,3),(2,6),(3,3)$.

Here is a direct sufficiency argument for this particular game. Choose a publicly known sequence of stage outcomes whose frequencies give the target point. Before any observed deviation, follow that sequence. After an Ann deviation, Bob fights forever, so Ann can thereafter obtain at most $2$ per stage. After a Bob deviation, Ann enters forever, so Bob can thereafter obtain at most $3$ per stage. A finite prefix has no effect on long-run average payoff, so no unilateral deviation improves a target with $a\ge 2,b\ge 3$. Rational frequencies can be implemented periodically; arbitrary real frequencies can be implemented by a deterministic sequence with convergent frequencies. Thus even the weak boundary is covered here. In particular, staying out forever and entry followed by acquiescence forever are sustainable; fighting forever is not.

For discounted payoffs $(1-\delta ){\sum }_{t\ge 0}{\delta }^t{u}_i^t$, the folk theorem for repeated games instead gives the usual patience qualification: every feasible point with $a>2,b>3$ can be sustained for all sufficiently large $\delta <1$. It does not classify the whole region for an unspecified fixed $\delta$. The two one-shot Nash equilibrium outcomes remain sustainable for every $\delta$.^[ref]

Finally consider the particular history-dependent pair in the paper. Initially Bob has never acquiesced, so Ann stays out. That preserves the same condition forever, giving payoffs $(2,6)$. The pair is a Nash equilibrium. Holding Bob's strategy fixed, Ann cannot induce an acquiescence: he fights whenever she enters, and his rule never changes unless he has previously acquiesced. Every entry would give her $1$ instead of $2$, so no unilateral deviation helps. Holding Ann's strategy fixed, Bob never reaches a decision node because she stays out; changing his strategy alone cannot create a history in which he actually acquiesces. Hence he also cannot improve.

This direct argument works for both discounted and long-run average payoffs. The outcome gives Ann exactly her minmax payoff and Bob more than his, so it is compatible with the folk theorem for repeated games. A version requiring strict gains above both minmax payoffs is a sufficient condition, and cannot be used to rule out this boundary example.

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.

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.