Fictitious play is a learning process in game theory in which each player, at every period of a repeated game, best responds to the empirical frequency distribution of the opponent’s past actions. The method was introduced by G.W. Brown in 1951 as a way to model how rational players might adapt their strategies over time based on observed behavior.
Definition
Consider a finite normal‑form game with a set of players $i = 1,\dots, n$, each possessing a finite set of pure strategies $S_i$. In fictitious play, each player $i$ maintains a belief $\hat{\sigma}_{-i}^t$ about the mixed strategy of the opponents, computed as the average of the opponents’ pure strategies up to period $t$:
$$ \hat{\sigma}{-i}^t(s{-i}) = \frac{1}{t}\sum_{\tau=1}^{t} \mathbf{1}{s_{-i}^\tau = s_{-i}}, $$
where $\mathbf{1}{\cdot}$ is the indicator function and $s_{-i}^\tau$ denotes the opponents’ joint pure‑strategy profile at period $\tau$. Player $i$ then selects a pure strategy $s_i^{t+1}$ that maximizes expected payoff against $\hat{\sigma}_{-i}^t$. If multiple best responses exist, a tie‑breaking rule (e.g., random selection) is applied.
Key Properties
-
Convergence in Certain Classes of Games –
- Two‑player zero‑sum games: Fictitious play converges to a Nash equilibrium (Brown, 1951; Robinson, 1951).
- Potential games: Convergence to pure‑strategy Nash equilibria has been proved (Monderer & Shapley, 1996).
- Super‑modular games: Convergence to a monotone equilibrium is guaranteed under standard assumptions.
-
Non‑convergence in General – Counterexamples demonstrate that fictitious play may fail to converge in some three‑player or non‑zero‑sum games (Shapley, 1964). The limiting behavior can include cycles or chaotic trajectories.
-
Relation to Other Dynamics – Fictitious play is a discrete‑time analogue of continuous‑time best‑response dynamics. It is distinct from, but related to, reinforcement learning, regret‑matching, and Bayesian learning models.
Historical Development
- 1951 – G.W. Brown publishes “Iterative Solution of Games by Means of Differential Equations,” introducing fictitious play and proving convergence for two‑player zero‑sum games.
- 1951 – R. J. Aumann and G. L. Shapley expand on the concept, exploring its implications for equilibrium selection.
- 1964 – L. S. Shapley provides a classic example (the “Shapley polygon”) where fictitious play does not converge.
- 1990s – Formal connections to stochastic approximation and differential inclusions are established (e.g., Benaïm & Hirsch, 1999).
- 2000s – Computational studies examine the speed of convergence and the impact of tie‑breaking rules.
Applications
Fictitious play serves as a benchmark for algorithms in:
- Economic modeling – Modeling boundedly rational agents in markets and auctions.
- Artificial intelligence – Training agents in repeated or multi‑agent environments where opponents’ strategies evolve.
- Evolutionary game theory – Interpreted as a deterministic limit of certain evolutionary processes.
Related Concepts
- Best‑response dynamics
- Replicator dynamics
- Regret minimization
- Learning in games (e.g., reinforcement learning, Bayesian learning)
References (selected)
- Brown, G. W. (1951). Iterative solution of games by means of differential equations. Contributions to the Theory of Games, 2, 73–90.
- Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54(2), 296–301.
- Shapley, L. S. (1964). Some topics in game theory. Proceedings of the International Congress of Mathematicians, 3, 707–718.
- Monderer, D., & Shapley, L. S. (1996). Potential games. Games and Economic Behavior, 14(1), 124–143.
- Benaïm, M., & Hirsch, M. W. (1999). Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 37(5), 1441–1466.
