Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 Β· Repeated and Evolutionary Games

The Folk Theorem and Repeated-Game Equilibria

Understand the folk theorem for repeated games: feasible payoffs, minmax values, average discounted payoffs and why almost any outcome can be sustained. Includes Python checks.

The repeated prisoner's dilemma showed that cooperation can be an equilibrium. A natural question follows: what else can be an equilibrium? The surprising answer is the folk theorem: when players are patient enough, almost any outcome that gives each player more than their worst-case guarantee can be sustained. It is called "folk" because it was known among game theorists long before it was written down in a paper.

This lesson makes the statement precise and checks it numerically on the prisoner's dilemma.

Average discounted payoffs

When games last many rounds, comparing total payoffs is awkward, because the totals can be infinite. A neat trick is to rescale: a stream of payoffs u0, u1, u2, ... with discount factor delta has value

V = (1 - delta) * (u0 + delta * u1 + delta^2 * u2 + ...)

This is the average discounted payoff. Multiplying by (1 - delta) puts it on the same scale as a single-round payoff: if you receive 3 every round, V equals 3 for every delta. This makes it easy to compare a repeated game's outcome with the stage game's payoffs.

Python Average discounted payoff

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Feasible payoffs

If players can coordinate (take turns, mix pure outcomes, or use a public coin), any convex combination of the stage-game payoff vectors can be reached on average. For the prisoner's dilemma, the four outcomes are (3,3), (0,5), (5,0) and (1,1). Their convex hull is a quadrilateral: the set of feasible payoffs. Note that the point (3.5,1.5) lies inside it, although no single outcome gives it.

Minmax: the floor for each player

A player can always protect themselves. The minmax value of player i is the lowest payoff the opponents can force on i when i best-responds: v_i = min over opponents' actions of max over i's actions of i's payoff. In the prisoner's dilemma, if the opponent defects, the best I can do is defect and get 1. So each player's minmax is 1, which equals the one-shot equilibrium payoff. A payoff below the minmax can never be an equilibrium outcome, because the player could deviate to a safe strategy and secure at least the minmax.

A payoff vector is individually rational if every component is at least that player's minmax value.

The folk theorem

Feasible Inside the convex hull of stage payoffs
Individually rational Each player gets at least the minmax
Patient players delta close enough to 1
Any such payoff Is a subgame-perfect equilibrium average

Repetition does not predict one outcome; it permits many.

1 / 2

The theorem

Folk theorem (infinitely repeated games). Take any feasible payoff vector in which every player receives strictly more than their minmax value. Then there is a discount factor delta* < 1 such that, for all delta above it, the vector is the average payoff of a subgame-perfect equilibrium of the repeated game.

The proof idea is a strategy with punishment: play the path that produces the target payoffs; if someone deviates, everyone switches to the punishment (minmax the deviator for a while, then return, or revert to the stage Nash equilibrium forever). With patient players the one-time gain from deviating is small compared with the long-run loss.

Checking the regions numerically

For the prisoner's dilemma the region is: feasible points with both coordinates above 1. The code below tests random points for membership in the convex hull using a Delaunay triangulation.

Python Which payoffs are feasible and individually rational?

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The point (3.5, 1.5) is feasible and above the minmax, so patient players can sustain it: for example, by playing the sequence "D by player 1 while player 2 cooperates" in a cycle with some mutual cooperation. The point (5, 5) is outside the hull. The point (0.8, 3) is feasible but gives player 1 less than 1, so player 1 would rather defect always and guarantee 1.

Building a punishment strategy

To see the mechanism, we test a punishment that is gentler than grim trigger: after a deviation, both players defect for K rounds and then return to cooperation. The code checks, for several K, whether a one-shot deviation from cooperation pays.

Python Finite punishment: how long must it last?

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The longer the punishment, the less patience is needed: with K near infinity the threshold falls to 0.5 (grim trigger). With impatient players, even long punishments fail.

What the folk theorem means, and what it does not

  • Multiplicity. Repetition creates an enormous set of equilibria: cooperation, alternating exploitation, and every stage-game equilibrium repeated. Game theory by itself does not pick one. Selection needs additional ideas (focal points, efficiency, evolution, as the next lessons discuss).
  • Not automatic. The theorem is about what can be sustained, not what will happen. A group stuck in permanent defection is also an equilibrium.
  • Information matters. The simple version assumes that actions are observed. With imperfect monitoring, versions exist but require cleverer strategies.
  • Finite horizons. If the stage game has several Nash equilibria, even a finitely repeated game can sustain cooperation, since the future can reward or punish by choosing between those stage equilibria.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What is a player's minmax value?

    It is what a player can guarantee against the worst the others can do.
  2. 2. In the prisoner's dilemma with payoffs 3, 0, 5, 1, which payoff pair can NOT be an equilibrium outcome of the repeated game?

    player 1 gets 0.8, below their minmax of 1, so they would deviate to always defecting.
  3. 3. What does the folk theorem say about patient players?

    That is the theorem's content: feasible and individually rational payoffs become equilibrium averages when delta is close to 1.
  4. 4. Why is the folk theorem sometimes considered a weakness for prediction?

    Multiplicity means repeated-game theory alone cannot say which outcome will occur.

Summary

  • Average discounted payoffs rescale a repeated game's stream to stage-game units: V = (1 - delta) times the discounted sum.
  • Feasible payoffs are convex combinations of stage outcomes; the minmax value is each player's safe floor.
  • The folk theorem: feasible payoffs above the minmax are sustainable as subgame-perfect equilibria for patient players.
  • Punishment length and patience trade off: longer punishments sustain cooperation with a lower delta.
  • Repetition expands the equilibrium set; selecting among equilibria needs other tools.

Next: Evolutionary Stable Strategies