1 What is Fictitious Play?
Fictitious play is a classical learning model in game theory where players repeatedly play a finite game, updating beliefs about opponent strategies based on empirical frequencies and responding myopically to those beliefs. The process models adaptive learning without assuming sophisticated strategic reasoning.
In a two-player game: 1. Players maintain beliefs about opponent strategy = empirical frequency of opponent’s past play 2. Each round: each player plays a pure strategy best response to current belief 3. Beliefs update as new play is observed
If beliefs converge to a distribution σ, then σ must be a Nash equilibrium (not necessarily pure).
2 Historical Development
- Brown (1951): Introduced fictitious play as an algorithm for solving zero-sum games
- Robinson (1951): Proved convergence holds for zero-sum games
- Miyazawa (1961): Extended to 2×2 games
- Shapley (1964): Famous 3×3 counterexample showing convergence fails generally
- Post-Shapley era: Extensive literature identifying classes of games with convergence
3 Convergence Results
3.1 Guaranteed Convergence
- Zero-sum games: Always converges (Robinson 1951)
- 2×2 games: Always converges (Miyazawa 1961)
- Weighted potential games: Converges to equilibrium set (Monderer & Shapley 1996)
- Special case: Congestion games (Rosenthal)
- Games with strategic complementarities: Various conditions (Krishna 1992, Hahn 1999)
3.2 Non-Convergence Examples
- Shapley’s 3×3 game (1964): Beliefs cycle persistently in a limit cycle
- Coordination games: Can exhibit permanent miscoordination (Foster & Young
- Various other examples: Cowan (1992), Jordan (1993), Gaunersdorfer & Hofbauer
3.3 Open/Partial Results
- Ordinal potential games: Convergence proved for certain variants (Berger 2007 on alternating updating); status unclear for standard simultaneous updating
- General classification: No complete characterization of which games converge
4 Key Concepts
4.1 Potential Games
Games where there exists a function Φ : (strategy profile) → ℝ such that improvements in payoff align with improvements in Φ. - Stronger form (weighted potential): Convergence fully proven - Weaker form (ordinal potential): Convergence properties less clear
4.2 Beliefs vs. Play Convergence
- Beliefs converge: Empirical frequencies stabilize on a limit distribution
- Play converges: Actual strategy choices become constant
- Belief convergence ⟹ limit is Nash equilibrium, but play need not converge (e.g., cycling)
4.3 Finite Improvement Property
A game has no cycles where payoffs strictly increase around a loop. Equivalent to having an ordinal potential.
5 Why FP Matters Theoretically
- Bounded rationality model: Agents learn without assuming full rationality or equilibrium play
- Predictive power: Tells us which equilibria are “stable” under learning
- Baseline for comparison: Helps identify which game structures enable convergence
- Simplicity: Intuitive and easy to analyze compared to more complex learning models
6 Variants & Extensions
- Continuous-time FP: Differential equation version (Brown, Fudenberg & Levine)
- Noisy FP: With error/noise in best response (Benaïm & Hirsch 1999+)
- n-player FP: Extension beyond 2-player games (more complex analysis)
- Alternating vs simultaneous updating: Different updating orders affect convergence (Berger 2007)
7 Outstanding Questions
- Does fictitious play converge in all ordinal potential games?
- Characterization of game classes guaranteeing convergence
- Rate of convergence when it does occur
- Robustness to noise, trembles, and misspecification
8 Major References
- Robinson (1951): “An iterative method of solving a game” — foundational
- Monderer & Shapley (1996): “Potential games” — defines key game classes
- Fudenberg & Levine (1998): The Theory of Learning in Games — comprehensive treatment
- Krishna & Sjöström (1997): “Learning in games: fictitious play dynamics” — overview chapter
- Hofbauer & Sigmund (2003): “Evolutionary game dynamics” — broader learning dynamics perspective
- Berger (2007): “Brown’s original fictitious play” — revisits convergence via alternating updating