Repeated Games, Folk Theorems, and Stochastic Games¶
Job: develop the repeated games (discount \(\delta\), folk), the stochastic games (Shapley, MDP), the SPNE / trigger, and the APS recursive — with the repeated PD / folk as the worked example.
Core¶
The repeated games and the folk¶
| Repeated / \(\delta\) / folk | Description |
|---|---|
| Repeated game | \(\delta\) the discount, the repeated interaction (the dynamical systems) |
| Folk theorem | \(\delta\to1\) the patient \(\Rightarrow\) cooperative payoffs as SPNE (the dynamical systems) |
The stochastic / the MDP¶
| Stochastic / Shapley / MDP | Description |
|---|---|
| Stochastic game | Shapley: state-dependent, transitions (the dynamical systems) |
| MDP | single-player stochastic (the dynamical systems) |
The SPNE and the trigger¶
| SPNE / trigger / grim | Description |
|---|---|
| SPNE | subgame perfect NE (the dynamical systems) |
| Grim trigger | any defect \(\to\) defect forever (the dynamical systems) |
The APS and the recursive¶
| APS / Abreu–Pearce–Stacchetti / recursive | Description |
|---|---|
| APS | Abreu–Pearce–Stacchetti: the recursive formulation (the dynamical systems) |
| Recursive | the value set the fixed point (the dynamical systems) |
See it¶
Repeated prisoner's dilemma and the folk theorem / grim trigger. The repeated PD: the \(\delta\) the discount, the \(\mathrm{cooperate}\) the cooperative, the grim trigger (the any defect \(\to\) defect forever, the dynamical systems). The folk: the \(\delta\to1\) the patient the cooperative (the folk, the dynamical systems). The key point: the repeated PD the grim, the folk the patient.
Check¶
Explain the folk theorem and the grim trigger, and the discount.
The folk: the \(\delta\to1\) the patient \(\Rightarrow\) the cooperative payoffs the SPNE (the any feasible individually rational payoff, the dynamical systems). The grim: the any defect \(\to\) defect forever (the grim trigger, the \(\delta\ge\delta^*\) the threshold, the dynamical systems). The discount: the \(\sum\delta^t u_t\) the discounted, the \(\delta\to1\) the patient. So the folk the patient, the grim the threshold.
Explain the stochastic game and the APS recursive.
The stochastic: the Shapley the state-dependent (the \(G(\omega)\), the transition \(\omega'=\phi(\omega,a)\), the Shapley equation \(V(\omega)=\mathrm{val}_a\sum_r u(\omega,a)+\delta V(\omega')\), the dynamical systems). The APS: the Abreu–Pearce–Stacchetti the recursive (the value set \(V\) the fixed point, the \(V=B(V)\) the self-generating, the dynamical systems). So the stochastic the Shapley, the APS the recursive.
Pitfalls¶
- The folk the patient (\(\delta\to1\), the dynamical systems) — the folk the patient, the \(\delta<1\) the non-cooperative.
- The grim the threshold (\(\delta\ge\delta^*\), the dynamical systems) — the grim the trigger, the \(\delta^*\) the threshold.
- The stochastic the Shapley (the state, the dynamical systems) — the stochastic the Shapley, the MDP the single-player.
- The APS the recursive (the \(V=B(V)\), the dynamical systems) — the APS the self-generating, the recursive.
Refs¶
- Fudenberg–Tirole, Game Theory (1991); the repeated / the folk
- Abreu–Pearce–Stacchetti, "Toward a theory of discounted repeated games" (1986); the APS
- Shapley, "Stochastic games" (1953); the stochastic
- Mailath–Samuelson, Repeated Games and Reputations (2006); the folk / the SPNE
Next¶
GT index · Foundations · Mechanism Design · Learning & No-Regret · Cooperative & Combinatorial · Dynamical systems