Game Theory
Repeated Games and the Folk Theorem
Airbnb and Uber operate without a central arbitrator - because the game repeats. Airbnb: 4+ million hosts trust strangers. Uber: 5+ million drivers. Neither has a permanent contract. The Folk Theorem explains: at high δ (users plan to travel again), cooperation is a self-enforcing equilibrium.
- **OPEC:** 13 countries have been limiting production without an enforcement mechanism since 1960. Repeated interaction + transparency of supply data = cooperative equilibrium.
- **Airbnb/Uber ratings:** review systems create a 'shadow of the future' - the threat of a bad rating = an instrumentalized Grim Trigger.
- **Open Source:** developers write quality code in public repositories. GitHub reputation = value of δ·future opportunities. Folk theorem in action.
Предварительные знания
Why Airbnb Works Without Police
Airbnb reached $75B valuation without a morality police: strangers sleep in strangers' homes. Uber runs 5M+ daily rides with unknown drivers. Both work because the game repeats. The Folk Theorem proves: when discount factor δ > 0.5, cooperation is stable as a Nash equilibrium of the infinitely repeated game.
In a one-shot prisoner's dilemma, the unique Nash equilibrium is mutual defection, yielding (1,1). But when the same players interact repeatedly with **observable history** - the threat of future punishment makes cooperation rational.
The finite repetition paradox: if T is known, backward induction destroys cooperation. In round T there is no future - both defect. In T-1 both know this - they defect again. Induction back to round 1 - no cooperation ever. An infinite horizon (or unknown T) is the only solution.
**International treaties without courts:** nations comply with WTO, NATO, nuclear agreements without a global enforcement mechanism. Repeated interaction + threat of cascading exit = self-enforcing equilibrium. The Folk Theorem is the mathematical foundation of the international order.
Why does cooperation always unravel in a finitely repeated game with known T through backward induction?
In round T: no future exists, so the stage game's Nash equilibrium (defect) applies. In round T−1: both know T will bring mutual defection regardless - no punishment threat works. Backward induction unravels cooperation all the way to round 1. An unknown horizon or infinite game breaks this logic by eliminating the 'last round'.
Discount Factor: The Mathematics of Patience
The parameter δ ∈ (0,1) is the discount factor. A payoff x in k rounds is worth δᵏ·x today. At δ = 0: only today matters. At δ → 1: the future is almost as important as the present. This captures both impatience and the probability of the game continuing (1-δ = probability of ending).
**Interpretations of δ:** 1) pure time preference (impatience), 2) probability p = 1-δ that the game ends after each round, 3) interest rate r via δ = 1/(1+r). Airbnb: high δ - user plans to travel again. One-off deal: δ ≈ 0 - like a one-shot game.
In OPEC, countries limit production without an enforcement mechanism. What is the critical discount factor δ* for cooperation, and why is real OPEC's δ usually above it?
δ* = (t−π)/(t−p) = (5−3)/(5−1) = 0.5. Real OPEC's δ exceeds this because: meetings have occurred for 30+ years (high probability of future rounds), oil revenues are central to members' economies (long-term horizon), and production data is observable (low information asymmetry strengthens cooperation incentives).
Grim Trigger and Tit-for-Tat: Punishment Strategies
A punishment threat works only if it is **credible**: the opponent must believe punishment will follow. A specific strategy is needed - a plan for every possible history of the game.
Grim Trigger: cooperate until the first defection, then defect forever. Maximum threat. Tit-for-Tat: cooperate in round 1, then copy the opponent's last move. Forgives after one retaliatory D.
**Axelrod's tournaments (1980-1984):** political scientist Robert Axelrod ran computer tournaments - different strategies in repeated prisoner's dilemma. Anatol Rapoport's Tit-for-Tat won. Four properties of the winner: niceness (starts with C), provocability (responds to D), forgiveness (forgives), clarity (strategy is understandable). 'The Evolution of Cooperation' (1984) became the foundation of evolutionary game theory.
Why does Grim Trigger have a lower δ* than Tit-for-Tat, yet Tit-for-Tat wins Axelrod's tournaments?
Grim Trigger uses the harshest possible threat (eternal defection), so cooperation is rational for lower δ - δ* is minimized. However, in Axelrod's tournaments with noise (random errors), one mistaken D triggers permanent retaliation. TfT's forgiveness property (one retaliatory D, then back to C) restores cooperation after errors. In noisy environments, robustness matters more than threat severity.
The Folk Theorem: Any Cooperation Is Possible
The Folk Theorem is one of the deepest results in game theory. As δ → 1, any individually rational and feasible payoff combination is an SPE (subgame perfect equilibrium) of the infinitely repeated game.
**Folk Theorem paradox:** it is simultaneously optimistic (cooperation is possible!) and pessimistic (infinitely many equilibria - which one is realized?). The 'too many equilibria' problem. The theory does not predict a specific equilibrium - additional concepts are needed: focal points, historical coordination, fairness norms.
What does 'individual rationality' mean in the Folk Theorem, and why is it essential for stability of cooperative agreements?
Individual rationality means vᵢ ≥ vᵢ* = minₛ₋ᵢ maxₛᵢ uᵢ(sᵢ, s₋ᵢ) - the minimax payoff player i can guarantee unilaterally. If a cooperative agreement awards player i less than vᵢ*, they rationally exit and play their minimax strategy, making the agreement unstable. The Folk Theorem's feasibility set F* excludes such agreements: only individually rational payoffs can be sustained as SPE.
Key Ideas
- **Repeated game**: same stage game played infinitely by the same players. History is observable - strategies depend on history.
- **δ = discount factor**: V_coop = π/(1-δ) > V_defect = t + δp/(1-δ) when δ ≥ δ* = (t-π)/(t-p)
- **Grim Trigger**: maximum threat (minimum δ*), but not robust to errors
- **Tit-for-Tat**: forgives after one D, robust to errors, won Axelrod's tournaments
- **Folk Theorem**: as δ → 1, any vᵢ ≥ v*ᵢ from conv(V) is sustained by SPE. Too many equilibria.
Related Topics
Repeated games bridge static theory and dynamic reality:
- Nash Equilibrium — Repeated games expand the set of SPE far beyond the one-shot game through punishment threats
- Prisoner's Dilemma — Classic stage game for the Folk Theorem: δ* = 0.5 separates cooperation from defection
- Signaling Games — Reputation in repeated games with asymmetric information - signaling mechanisms in Airbnb/Uber
Вопросы для размышления
- GitHub, Stack Overflow, Wikipedia - reputation systems without enforcement. Which parameter in the repeated game model creates the 'shadow of the future' in these systems? How would behavior change if accounts were anonymous and disposable?
- The Folk Theorem produces 'too many equilibria'. How do real organizations (OPEC, WTO) solve the coordination problem of selecting a specific equilibrium? What plays the role of the 'focal point'?
- Climate negotiations (Paris Agreement) are a repeated game among ~200 countries with very different δ values. How does the low δ of developing countries (high 'impatience' for growth) affect the stability of the cooperative equilibrium?