Repeated Games

Definition and motivation

A repeated game arises when a base (stage) game G is played multiple times by the same players, with each play called a period. Two canonical settings are:

• •Finitely repeated game: G is played for a known number T of periods.
• •Infinitely repeated game: G is played indefinitely (or with a constant-probability continuation each period). Often modeled with a common discount factor $\delta \in [0,1)$.

Why care? Many real-world strategic interactions are repeated: firms set prices across many periods, countries engage in sequential diplomacy, or sellers build reputations. Repetition changes incentives because the future consequences of today's actions can be used as leverage.

Formal setup

Let the stage game G have players i=1,...,n, action sets $A_i$, and payoff functions $u_i(a)$ for action profile $a=(a_1,...,a_n)$. A repeated game with discount factor $\delta$ gives total payoff to player i the discounted sum

where the $(1-\delta)$ normalization is conventional (it makes the infinite sum comparable to a per-period payoff); if you prefer undiscounted present value use $\sum_{t=0}^\infty \delta^t u_i(a^t)$. Concrete numeric example: Suppose the stage payoff from mutual cooperation is $R=3$ every period and $\delta=0.9$. Then the normalized discounted value of perpetual cooperation is

Relation to prerequisites

In "Nash Equilibrium" we learned to analyze one-shot games by checking unilateral profitable deviations. In repeated games, we use that concept period-by-period but also condition on future strategies. In "Dynamic Programming" we learned to think in terms of continuation values and Bellman equations; that viewpoint is essential when proving that certain strategy profiles are subgame-perfect equilibria (SPE) by the one-deviation principle or via recursive incentive constraints.

Basic intuition: horizon matters

• •Finitely repeated games often reduce (by backward induction) to playing a stage-game Nash equilibrium every period when the stage game has a unique Nash equilibrium. Example: Prisoner’s Dilemma (PD) with unique stage NE (Defect, Defect) yields universal defection in every period for finite T.

• •Infinitely repeated games can sustain outcomes that are not stage-game Nash equilibria because future punishments (or rewards) change the payoff calculus of deviations. The classic vehicle is a trigger strategy: cooperate as long as history shows cooperation, but if someone defects, switch to a punishment phase.

Concrete stage-game example used throughout

Use the symmetric Prisoner’s Dilemma with payoffs: Temptation $T=5$, Reward $R=3$, Punishment $P=1$, Sucker $S=0$ with ordering $T>R>P>S$. The one-shot Nash equilibrium is (D,D) giving both players payoff 1. Yet in repeated play, cooperative payoff $R=3$ per period may be achievable if players are patient enough (i.e., $\delta$ large).

Finitely repeated games: backward induction

In a finitely repeated game with known horizon T, the standard solution concept is subgame-perfect equilibrium (SPE). We obtain SPE by backward induction (a dynamic programming idea): analyze the last period as a one-shot game, then use the resulting equilibrium payoffs as continuation values for the penultimate period, and iterate backward.

If the stage game has a unique Nash equilibrium (NE), that NE is played in every period of any finite repetition by backward induction. Reason: in the last period, players play the stage-game NE. Knowing play in the last period is independent of earlier choices, there is no future to reward or punish, so in the penultimate period players again have no incentives to deviate from the stage NE, and so on.

Concrete numeric example (T=2, Prisoner’s Dilemma)

Stage game PD: payoffs as before $(T,R,P,S)=(5,3,1,0)$. The unique stage NE is (D,D) giving payoff $P=1$ each. Let T=2 (two periods). Backward induction proceeds:

1. 1)Period 2 (last period): play stage NE (D,D). No future punishment exists.
2. 2)Period 1: anticipating (D,D) in period 2, any attempt to cooperate in period 1 cannot be sustained by future punishment (because period 2 is the last). Therefore, in period 1 players again play D.

Thus SPE: (D,D) in both periods. If the stage game had multiple Nash equilibria, more interesting patterns can occur: cooperation may be supported by choosing a Pareto-superior Nash equilibrium in the last period and sustaining it earlier by threats to switch to a worse Nash in case of deviation.

Connection with "Nash Equilibrium" and limitations

In "Nash Equilibrium" we checked unilateral deviations for a single play. Backward induction applies the same logic recursively to every subgame. The limitation: the finiteness removes the effective enforcement by future punishment because the future eventually ends; this is the classic reason why long-term cooperation can fail when the horizon is known.

Finitely repeated games with incomplete information or with an unknown horizon can sustain cooperation. Example: if players do not know the exact final period (e.g., the game ends each period with small probability), the game becomes strategically akin to the infinite horizon case because there is always some chance of future interaction.

Worked mini-derivation (compact)

Let stage-game unique NE give payoff $u^*$ to each player. In period T, equilibrium payoff is $u^*$. In period T-1, no action can change future beyond what is determined by period T strategies; hence the unique best response in period T-1 equals the stage NE action and the continuation value is $u^*$. Inductively, every period uses stage NE actions. This is the dynamic-programming style backward induction argument familiar from "Dynamic Programming".

Numeric check: If you guessed cooperating in period 1 with payoff 3 and feared defection giving one-time Temptation 5 in period 1 but punishment 1 in period 2, you might check whether 5 (gain) plus 1 (period 2 punishment) beats cooperative path 3+3. But because the last period can't be credibly punished (no future), cooperation unravels: you cannot design a credible threat for the second-to-last period because the punishments themselves would rely on future incentives that don't exist in period T.

Practical consequence

For firms or agents facing a known, short horizon, explicit contracts or external enforcement are necessary to sustain cooperation. If horizon is long or uncertain, repeated-game incentives can be powerful.

Infinite horizon and discounting

In infinitely repeated games, the present value of a stream of per-period payoffs $x$ is $\sum_{t=0}^\infty \delta^t x = x/(1-\delta)$ (without the $(1-\delta)$ normalization). With normalization $(1-\delta)\sum \delta^t x = x$, you can think in per-period terms. The key parameter is the discount factor $\delta$ (or equivalently the patience of players).

Trigger strategies: idea and types

Trigger strategies condition current play on past histories. Two canonical triggers:

• •Grim trigger: Start by cooperating. If any player ever defects, play the worst Nash-equilibrium action profile (the Nash-punishment) forever thereafter.
• •Finite-length (N-period) trigger: Cooperate until defection; after defection, punish for N periods (playing the punishment profile), then return to cooperation.

Both exploit the threat of future loss to deter one-shot deviations. The one-deviation principle (from "Dynamic Programming") simplifies SPE verification: it suffices to check that no player has a profitable one-shot deviation from the planned strategy at any history.

Derive condition for grim-trigger sustainability in two-player PD

Consider symmetric PD with stage payoffs $(T,R,P,S)$ where $T>R>P>S$. Suppose both players follow grim trigger: cooperate every period unless someone has defected previously; upon any defection switch permanently to (D,D) giving payoff $P$ forever. A unilateral defection in a period gives the deviator immediate payoff $T$ that period instead of $R$, and then from next period on receives $P$ instead of $R$.

Write the present value (no normalization) of cooperating forever as

If you deviate in period 0 (one-shot), you get $T$ today plus the present value of punishment from period 1 onward:

No profitable deviation requires $V_C \ge V_D$, i.e.

Multiply both sides by $1-\delta$ and rearrange:

Equivalently

Concrete numeric example: With $(T,R,P,S)=(5,3,1,0)$, the threshold is

Thus if players are sufficiently patient ($\delta\ge0.5$), grim trigger makes mutual cooperation an SPE. If $\delta<0.5$, a player prefers to defect.

N-period punishment thresholds

If punishment is only N periods long (N-period trigger) the deviation's future loss is limited. Suppose a defector gets $T$ in the deviation period, then receives $P$ for N periods (periods 1..N) and returns to cooperation thereafter. The incentive inequality becomes

Simplify the loss from punishment part: the discounted loss relative to cooperation equals

So the inequality simplifies to

Concrete numeric example: take $(T,R,P,S)=(5,3,1,0)$ and N=2. The right-hand side becomes

We require

Solving gives $\delta \ge (\sqrt{5}-1)/2 \approx 0.618$. So a 2-period punishment requires $\delta\gtrsim0.618$ here, which is stricter than the grim-trigger threshold 0.5. This illustrates the power of permanent punishment: longer punishments relax the patience requirement.

Folk Theorem (informal statement)

The Folk Theorem says that for infinitely repeated games, if players are sufficiently patient ($\delta$ close to 1), then any feasible and individually rational payoff vector can be sustained as a subgame-perfect equilibrium payoff. "Feasible" means achievable via convex combinations of stage-payoff profiles; "individually rational" means each player's payoff is at least her minmax (security) value.

Sketch of proof idea

Construct strategies that implement a target payoff by cycling through stage-action profiles and use threats to revert to minmax punishments for deviations. Make punishments severe enough (play the minmax strategy) so the future loss outweighs any short-term gain. Use the one-deviation principle and choose $\delta$ close enough to 1 so the inequality holds. (This construction is standard and leverages the same discounted-present-value arithmetic as the PD examples.)

Connection to "Dynamic Programming"

Verifying SPE uses continuation values like value functions in dynamic programming: at any history, the continuation payoff must be consistent with incentives, and the one-deviation principle reduces verification to checking one-period deviations against continuation-plan payoffs.

Economic and practical applications

1) Collusion in oligopoly: Firms can sustain supra-competitive prices by implicitly colluding with trigger strategies that punish price deviations. Example: two firms that would earn monopoly profit by cooperating can sustain that profit flow if they are sufficiently patient; the math parallels the PD analysis where temptation is the one-shot gain from undercutting.

Numeric illustration: two symmetric firms that get monopoly profit $\pi_C=100$ when both keep prices high, and competitive profit $\pi_N=30$ if both price low; a deviator gets $\pi_T=140$ that period if she undercuts. Grim-trigger sustainability requires

So moderate patience suffices.

2) Reputation and online markets: Sellers with repeated transactions use reputation as a trigger: a bad review triggers fewer future sales (an endogenous punishment). The repeated-game framework and Folk Theorem explain how even anonymous markets can sustain cooperation when matching is long-lived or search friction gives weight to future trade.

3) Enforcement without a central authority: Smart contracts or decentralized systems use repeated-interaction logic to enforce behavior: validators who misbehave can be blacklisted (permanent punishment) which discourages deviation if future payoffs are valuable.

Connections to more advanced theory (what this enables)

• •Mechanism Design & Dynamic Mechanism Design: Repeated-game incentives underlie many dynamic mechanism-design problems where agents' private information and future incentives matter.
• •Stochastic Games: When the stage game payoffs depend on a state evolving with actions, repeated-game ideas extend to stochastic games; Folk-like theorems exist with state dependence.
• •Evolutionary Game Theory: Long-run dynamics and stable cooperation are often interpreted through repeated-interaction payoffs.

Downstream technical prerequisites that require repeated games

• •Repeated-game Folk Theorem is used in dynamic contract theory and in proving existence of long-run collusion equilibria in industrial organization.
• •Techniques such as automaton strategies and self-generating sets (Abreu, Pearce, Stacchetti) build on repeated-game foundations; understanding these is necessary for advanced analysis of dynamic oligopoly and bargaining problems.

Limitations and refinements

• •The Folk Theorem is existential: it shows many payoffs can be supported, but it does not select among them. Refinements (e.g., renegotiation-proofness, bounded complexity of strategies, or computational cost) are used to pick more plausible equilibria.
• •In finitely repeated games or when discounting is severe (small $\delta$), repeated-game enforcement may fail, requiring external institutions.

Summary

Repeated games show how the shadow of the future reshapes incentives. The key mechanics are discounting, continuation values, and credible punishments encoded in trigger strategies. The Folk Theorem demonstrates the theoretical richness of feasible equilibria when players are patient, and the explicit threshold calculations (as in the PD) reveal when cooperation is feasible in concrete settings.