{ "id": "ep534jn8fm", "slug": "fictitious-play", "title": "Fictitious play", "updated": "2026-09-30", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" } ], "geo": [ { "id": "geo.nongeo.t1946.physical.math", "label": "Non-geographic · 1946 to 2000: Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" } ] } ], "excerpt": "Fictitious play is an iterative game-theory process in which each player best-responds to opponents' past play frequencies, used to model learning and compute Nash equilibria.", "snippet": "Fictitious play is an iterative game-theory process in which each player best-responds to opponents' past play frequencies, used to model learning and compute Nash equilibria.", "node": "physical.math", "markdown": "# Fictitious play\n\nFictitious play is an iterative process in game theory in which each player repeatedly plays a best response to the empirical frequency distribution of the opponents' past strategies. It serves two purposes: as a model of how players might learn to coordinate, and as an algorithm for computing Nash equilibria, originally the value of a two-person zero-sum game. The name reflects the original interpretation: players were imagined to run the process as a thought experiment, computing and coordinating on an equilibrium without actually playing the game, hence \"fictitious\" play.[1](http://lev1101.dklevine.com/papers/annals38.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Update rule | Each player best-responds to the empirical frequencies of opponents' past play[2](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf) |\n| Origin | Brown, unpublished RAND Report P-78 (1949) and 1951 publication; alternating belief updates in both[3](https://research.wu.ac.at/ws/files/19793331/2007_JET.pdf) |\n| First convergence proof | Robinson (1951), two-player zero-sum games[4](https://doi.org/10.2307/1969530) |\n| Classical rate | \\( O(t^{-1/(m+n-2)}) \\) in an \\( m \\times n \\) zero-sum game; \\( O(1/t) \\) in continuous time[5](https://ar5iv.labs.arxiv.org/html/1412.4840) • [6](https://cris.maastrichtuniversity.nl/ws/files/841750/guid-5ac076d9-7c27-41f9-b346-9f25db08b65b-ASSET1.0.pdf) |\n| Classic failure | Shapley's 1964 3×3 game, where play cycles with exponentially growing run lengths[7](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture7_2007.pdf) |\n| Smoothed variant | Stochastic fictitious play, introduced by Fudenberg and Kreps (1993)[8](https://doi.org/10.1006/game.1993.1021) |\n| Memory footprint | \\( O(n) \\) for the row player and \\( O(m) \\) for the column player, so the dynamic is amenable to distributed computation[9](https://ar5iv.labs.arxiv.org/html/1911.08418) |\n\n## How it works\n\nEach player maintains a belief, a mixed strategy assigned to each opponent, and plays a best response to it. The belief is the empirical frequency of past actions: the empirical frequency of player \\( i \\)'s own action \\( s_i \\) after \\( n \\) rounds is \\( \\sigma_{i,n}(s_i) = (1/n) \\sum_{k=1}^{n} \\mathbf{1}\\{t_{i,k} = s_i\\} \\), and player \\( i \\)'s belief about its opponents is \\( \\sigma_{-i,n} \\), the next action being chosen from \\( \\mathrm{BR}_i(\\sigma_{-i,n}) \\).[10](https://adityam.github.io/multi-agent-systems/static-games/fictitious-play.html) The frequency update has a Bayesian reading: players act as if they are Bayesians facing a fixed but unknown mixed strategy, and adding one to a strategy's weight each time it is played corresponds exactly to [Bayesian inference](https://www.edgepedia.org/bayesian-inference) with a Dirichlet prior over that unknown distribution.[1](http://lev1101.dklevine.com/papers/annals38.pdf)\n\n## How it is done\n\nIn the standard discrete-time version, each player best-responds to the product of the marginal empirical distributions of the opponents' previous play; the literature almost universally uses simultaneous moves, though alternating moves is the other convention.[2](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf) In a matrix game with payoff matrices \\( P \\) and \\( Q \\), the recursion adds one unit of mass to the chosen action each round: \\( x_{k+1} = x_k + u_i \\) where \\( i \\) maximizes a component of \\( P \\cdot y_k \\), and \\( y_{k+1} = y_k + v_j \\) where \\( j \\) maximizes a component of \\( x_k \\cdot Q \\).[11](https://pub.dss.in.tum.de/brandt-research/fplay.pdf) Equivalently, the belief recursion is a convex combination, \\( \\sigma_{n+1} = n \\cdot \\sigma_n / (n+1) \\) plus \\( 1/(n+1) \\) on the strategy just played.[10](https://adityam.github.io/multi-agent-systems/static-games/fictitious-play.html) Three main variants are standard: discrete-time fictitious play (DTFP), continuous-time fictitious play (CTFP), a differential inclusion \\( dp_i/dt \\in \\mathrm{BR}(p_{-i}) - p_i \\), and stochastic fictitious play (SFP) with its perturbed continuous-time analog.[2](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf)\n\n## Origin\n\nFictitious play is an algorithm for finding the value of a zero-sum game.[3](https://research.wu.ac.at/ws/files/19793331/2007_JET.pdf) Brown's original 1949 report and 1951 paper had players update their beliefs alternatingly rather than simultaneously, mentioning simultaneous updating only briefly as a minor variant; what modern game theorists call fictitious play is therefore not literally the process Brown defined.[3](https://research.wu.ac.at/ws/files/19793331/2007_JET.pdf) [Julia Robinson](https://www.edgepedia.org/julia-robinson) provided the first convergence proof in 1951 in the [Annals of Mathematics](https://www.edgepedia.org/annals-of-mathematics), shortly afterward.[4](https://doi.org/10.2307/1969530) Brown's original formulation considered both a discrete-time and a continuous-time version, and in 1949 he argued heuristically that the continuous version converges at linear speed to the set of Nash equilibria; rigorous proofs of continuous-time convergence came only with Hofbauer (1994) and Harris (1998).[12](http://www.dklevine.com/archive/refs4417.pdf) • [6](https://cris.maastrichtuniversity.nl/ws/files/841750/guid-5ac076d9-7c27-41f9-b346-9f25db08b65b-ASSET1.0.pdf) The best-response dynamic is a closely related precursor.[2](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf)\n\n## Variants\n\nStochastic fictitious play, introduced by Fudenberg and Kreps in Games and Economic Behavior in 1993 using an approach similar to Harsanyi's purification of [Nash equilibrium](https://www.edgepedia.org/nash-equilibrium), has players observe private payoff shocks; its update is \\( p_{t+1}^i - p_t^i = (C_i(p_{-i}^t) - p_t^i)/(t+1) + \\xi_t^i/(t+1) \\).[2](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf) • [8](https://doi.org/10.1006/game.1993.1021) In SFP players form beliefs as in fictitious play but choose actions according to a stochastic best response; SFP is Hannan-consistent, whereas exact fictitious play is not.[1](http://lev1101.dklevine.com/papers/annals38.pdf) Smooth fictitious play chooses actions maximizing a regularized payoff \\( r_i(\\cdot, x_{-i}^n) + \\varepsilon h_i(\\cdot, x_{-i}^n) \\), and with suitable \\( \\varepsilon \\) has the no-regret property up to \\( \\varepsilon \\).[13](https://proceedings.neurips.cc/paper_files/paper/2022/file/7f7fa581cc8a1970a4332920cdf87395-Paper-Conference.pdf) Derivative-action fictitious play is a variant in which players best-respond to a combination of empirical frequencies and a weighted derivative of those frequencies; this can converge in previously non-convergent situations such as Shapley's game.[14](http://www.professeurs.polymtl.ca/jerome.le-ny/docs/reports/FictitiousPlay.pdf) Fictitious play's iterative best-response design also inspired the double oracle algorithm and policy space response oracle (PSRO) for two-player zero-sum games.[15](https://www.ijcai.org/proceedings/2022/0026.pdf)\n\n## Applications\n\nAs an algorithm, fictitious play is attractive for its simplicity and footprint: the row and column players need only \\( O(n) \\) and \\( O(m) \\) memory respectively, making the dynamic amenable to distributed computation.[9](https://ar5iv.labs.arxiv.org/html/1911.08418) It was originally introduced to approximate the value of constant-sum games, equivalently to compute approximate solutions to linear programs, and it inspired many later algorithms, including smooth fictitious play and the regret-minimization paradigm.[11](https://pub.dss.in.tum.de/brandt-research/fplay.pdf) Heinrich and Silver combined fictitious self-play with deep reinforcement learning in 2015, demonstrating strong performance on Leduc Poker and Limit Texas Hold'em at real-world scale.[15](https://www.ijcai.org/proceedings/2022/0026.pdf) The connection to online optimization is exact: fictitious play can be interpreted as an online Frank-Wolfe method with step size \\( 1/(t+1) \\), a view that enabled extensions to extensive-form games and neural networks, and in zero-sum games it is equivalent to both players using the Follow-the-Leader protocol.[16](https://arxiv.org/pdf/2507.09902) • [17](https://doi.org/10.48550/arxiv.1610.07797) • [18](https://people.csail.mit.edu/costis/6853fa2011/lec4.pdf) A 2024 paper establishes the first explicit convergence rate for fictitious play in general (non-potential) mean-field games, showing that convergence and its rate are controlled by the weighting parameter \\( \\delta_k \\), with linear convergence achievable under a general assumption, and adds acceleration via [backtracking line search](https://www.edgepedia.org/backtracking-line-search) and a hierarchical vanishing-viscosity grid strategy.[19](https://arxiv.org/html/2411.07989v2) For monotone finite-state mean-field games, including finite-horizon and \\( \\gamma \\)-discounted settings with common noise, continuous-time fictitious play's exploitability decreases at rate \\( O(1/t) \\), providing the first converging learning dynamics for mean-field games in the presence of common noise.[20](https://papers.neurips.cc/paper_files/paper/2020/file/995ca733e3657ff9f5f3c823d73371e1-Paper.pdf)\n\n## Limitations and alternatives\n\nRobinson (1951) established that in finite two-player zero-sum games every fictitious-play process converges to the set of equilibria: the empirical strategies satisfy \\( \\lim_{t \\to \\infty} \\max_i e_i^T \\cdot R \\cdot y_t = \\lim_{t \\to \\infty} \\min_j x_t^T \\cdot R \\cdot e_j = v \\), the value of the game.[4](https://doi.org/10.2307/1969530) • [18](https://people.csail.mit.edu/costis/6853fa2011/lec4.pdf) Later results extended convergence to 2×2 games (Miyasawa, dated 1961 in some accounts and 1963 in others), noisy 2×2 games with a unique Nash equilibrium (Fudenberg and Kreps, 1993), identical-interest multiplayer games (Monderer and Shapley, 1996), and 2×n games (Berger, 2005).[12](http://www.dklevine.com/archive/refs4417.pdf) • [21](http://www2.hawaii.edu/~gurdal/TAC04.pdf) • [16](https://arxiv.org/pdf/2507.09902) For general-sum games, convergence is not guaranteed.[16](https://arxiv.org/pdf/2507.09902) On rates, the classical analysis (Robinson 1951; Shapiro 1958) gives \\( O(t^{-1/(m+n-2)}) \\): for all \\( \\varepsilon > 0 \\) and \\( t \\ge (R_{\\max}/\\varepsilon)^{\\Omega(m+n)} \\), the empirical strategies form an \\( \\varepsilon \\)-approximate Nash equilibrium.[16](https://arxiv.org/pdf/2507.09902) • [18](https://people.csail.mit.edu/costis/6853fa2011/lec4.pdf) [Samuel Karlin](https://www.edgepedia.org/samuel-karlin) conjectured in 1959 a faster \\( O(t^{-1/2}) \\) rate; Daskalakis and Pan disproved this in 2014, showing that for the \\( n \\times n \\) identity payoff matrix fictitious play may converge at rate \\( \\Omega(t^{-1/n}) \\) under adversarial tie-breaking.[5](https://ar5iv.labs.arxiv.org/html/1412.4840) • [22](https://doi.org/10.48550/arxiv.1412.4840) A 2025 result gives a 10×10 zero-sum game converging at \\( \\Omega(t^{-1/3}) \\) regardless of tie-breaking, with no ties except at the first step, refuting the weaker form of Karlin's conjecture.[16](https://arxiv.org/pdf/2507.09902) Even in the classes where convergence is known, fictitious play may require an exponential number of rounds before any equilibrium action is played at all.[11](https://pub.dss.in.tum.de/brandt-research/fplay.pdf) Shapley's 1964 3×3 example is the classic counterexample: despite a unique Nash equilibrium, discrete-time fictitious play cycles through action pairs (T,M) → (T,R) → (M,R) → (M,L) → (B,L) → (B,M) → (T,M), spending an exponentially increasing amount of time in each pair, so the empirical distributions never converge.[7](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture7_2007.pdf) • [12](http://www.dklevine.com/archive/refs4417.pdf) Krishna and Sjöström showed that for almost all games, continuous-time fictitious play cannot converge cyclically to a mixed equilibrium using more than two pure strategies per player, so Shapley-type behavior is generic.[12](http://www.dklevine.com/archive/refs4417.pdf) The multiplicative-weights-update method is an alternative with better guarantees in some settings.[18](https://people.csail.mit.edu/costis/6853fa2011/lec4.pdf)\n\n## References\n\n1. [Learning and Equilibrium (Fudenberg & Levine)](http://lev1101.dklevine.com/papers/annals38.pdf)\n2. [MS&E 336 Lecture 6: Variants of fictitious play (DTFP, CTFP, SFP, PCTFP) (R. Johari, Stanford)](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf)\n3. [Brown's Original Fictitious Play (U. Berger, Journal of Economic Theory 135, 2007)](https://research.wu.ac.at/ws/files/19793331/2007_JET.pdf)\n4. [Julia Robinson (1951). An Iterative Method of Solving a Game. Annals of Mathematics.](https://doi.org/10.2307/1969530)\n5. [A Counter-Example to Karlin's Strong Conjecture for Fictitious Play (Daskalakis & Pan, FOCS 2014)](https://ar5iv.labs.arxiv.org/html/1412.4840)\n6. [Continuous fictitious play in zero-sum games (Maastricht University CRIS)](https://cris.maastrichtuniversity.nl/ws/files/841750/guid-5ac076d9-7c27-41f9-b346-9f25db08b65b-ASSET1.0.pdf)\n7. [MS&E 336 Lecture 7: Fictitious play examples and convergence results (Stanford course notes)](http://web.stanford.edu/~rjohari/teaching/notes/336_lecture7_2007.pdf)\n8. [Drew Fudenberg, David M. Kreps (1993). Learning Mixed Equilibria. Games and Economic Behavior.](https://doi.org/10.1006/game.1993.1021)\n9. [Fast Convergence of Fictitious Play for Diagonal Payoff Matrices (Abernethy, Lai, Wibisono, SODA 2021)](https://ar5iv.labs.arxiv.org/html/1911.08418)\n10. [Fictitious Play – Multi-Agent Systems (A. Mahajan)](https://adityam.github.io/multi-agent-systems/static-games/fictitious-play.html)\n11. [On the Convergence Rate of Fictitious Play (Brandt, Fischer, Harrenstein)](https://pub.dss.in.tum.de/brandt-research/fplay.pdf)\n12. [On the Convergence of Fictitious Play (Krishna & Sjöström, Mathematics of Operations Research 1998)](http://www.dklevine.com/archive/refs4417.pdf)\n13. [Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions (NeurIPS 2022)](https://proceedings.neurips.cc/paper_files/paper/2022/file/7f7fa581cc8a1970a4332920cdf87395-Paper-Conference.pdf)\n14. [On Some Extensions of Fictitious Play (J. Le Ny, technical report/survey)](http://www.professeurs.polymtl.ca/jerome.le-ny/docs/reports/FictitiousPlay.pdf)\n15. [On the Convergence of Fictitious Play: A Decomposition Approach (IJCAI 2022)](https://www.ijcai.org/proceedings/2022/0026.pdf)\n16. [Tie-breaking Agnostic Lower Bound for Fictitious Play (arXiv, 2025)](https://arxiv.org/pdf/2507.09902)\n17. [Gidel, Gauthier, Jebara, Tony, Lacoste-Julien, Simon (2016). Frank-Wolfe Algorithms for Saddle Point Problems. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1610.07797)\n18. [Lecture 4: Fictitious Play (MIT 6.853, C. Daskalakis)](https://people.csail.mit.edu/costis/6853fa2011/lec4.pdf)\n19. [Convergence Analysis and Acceleration of Fictitious Play for General Mean-Field Games via the Best Response (arXiv, November 2024)](https://arxiv.org/html/2411.07989v2)\n20. [Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications (Perrin et al., NeurIPS 2020)](https://papers.neurips.cc/paper_files/paper/2020/file/995ca733e3657ff9f5f3c823d73371e1-Paper.pdf)\n21. [Unified Convergence Proofs of Continuous-Time Fictitious Play (IEEE TAC 2004)](http://www2.hawaii.edu/~gurdal/TAC04.pdf)\n22. [Daskalakis, Constantinos, Pan, Qinxuan (2014). A Counter-Example to Karlin's Strong Conjecture for Fictitious Play. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1412.4840)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "http://web.stanford.edu/~rjohari/teaching/notes/336_lecture6_2007.pdf", "http://web.stanford.edu/~rjohari/teaching/notes/336_lecture7_2007.pdf", "http://www2.hawaii.edu/~gurdal/TAC04.pdf" ], "url": "https://www.edgepedia.org/fictitious-play", "markdown_url": "https://www.edgepedia.org/fictitious-play.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Fictitious play\", Edgepedia (EdgeChat), https://www.edgepedia.org/fictitious-play. Edgepedia Community License 1.0.", "credit_md": "\"[Fictitious play](https://www.edgepedia.org/fictitious-play)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/fictitious-play](https://www.edgepedia.org/fictitious-play). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Fictitious play\", Edgepedia (EdgeChat), https://www.edgepedia.org/fictitious-play. Edgepedia Community License 1.0.", "speakable": "Fictitious play is an iterative game-theory process in which each player best-responds to opponents' past play frequencies, used to model learning and compute Nash equilibria." }