fictitious play
{{More footnotes|date=July 2023}}
In game theory, fictitious play is a learning rule that describes how players might learn over time in repeated strategic interactions. In fictitious play, each player assumes that opponents are using stationary (possibly mixed) strategies, and responds optimally to the historical empirical distribution of their opponents' past actions. Specifically, at each round, a player calculates the empirical frequency of each strategy their opponents have played in previous rounds and selects their own best response to these frequencies.
This approach provides a simple model of bounded rationality in which players gradually learn about their strategic environment through repeated observation. Fictitious play converges to Nash equilibrium in several important classes of games, including zero-sum games, potential games, and games with dominant strategies. However, the method has notable limitations when opponents employ non-stationary or adaptive strategies. For example, if an opponent conditions their play on the fictitious player's recent moves or deliberately exploits the predictable nature of the best-response pattern, the fictitious play approach may fail to converge or may be systematically exploited.
It was first introduced by mathematician George W. Brown in 1951.{{cite journal |last=Brown |first=George W. |year=1951 |title=Iterative solution of games by fictitious play |journal=Activity Analysis of Production and Allocation |pages=374–376}}
History
Brown first introduced fictitious play as an explanation for Nash equilibrium play. He imagined that a player would "simulate" play of the game in their mind and update their future play based on this simulation; hence the name fictitious play. In terms of current use, the name is a bit of a misnomer, since each play of the game actually occurs. The play is not exactly fictitious.
Convergence properties
In fictitious play, strict Nash equilibria are absorbing states. That is, if at any time period all the players play a Nash equilibrium, then they will do so for all subsequent rounds. (Fudenberg and Levine 1998, Proposition 2.1) In addition, if fictitious play converges to any distribution, those probabilities correspond to a Nash equilibrium of the underlying game. (Proposition 2.2)
| class="wikitable" align=right style="margin: 1em 1em 1em 1em; font-size: 95%; text-align:center;"
|+ align=bottom|Generalized Rock Paper Scissors | ! A ! B ! C |
| a
| 0, 0 | 2, 1 | 1, 2 |
|---|
| b
| 1, 2 | 0, 0 | 2, 1 |
| c
| 2, 1 | 1, 2 | 0, 0 |
Therefore, the interesting question is, under what circumstances does fictitious play converge? The process will converge for a 2-person game if:
- Both players have only a finite number of strategies and the game is zero sum (Robinson 1951)
- The game is solvable by iterated elimination of strictly dominated strategies (Nachbar 1990)
- The game is a potential game (Monderer and Shapley 1996-a,1996-b)
- The game has generic payoffs and is 2 × N (Berger 2005)
Fictitious play does not always converge, however. Shapley (1964) proved that in the game pictured here (a nonzero-sum version of Rock, Paper, Scissors), if the players start by choosing (a, B), the play will cycle indefinitely.
Terminology
Berger (2007) states that "what modern game theorists describe as 'fictitious play' is not the learning process that George W. Brown defined in his 1951 paper": Brown's "original version differs in a subtle detail..." in that modern usage involves the players updating their beliefs simultaneously, whereas Brown described the players updating alternatingly. Berger then uses Brown's original form to present a simple and intuitive proof of convergence in the case of two-player nondegenerate ordinal potential games.
The term "fictitious" had earlier been given another meaning in game theory. Von Neumann and Morgenstern [1944] defined a "fictitious player" as a player with only one strategy, added to an n-player game to turn it into a (n + 1)-player zero-sum game.
References
{{Reflist}}
- Berger, U. (2005) "Fictitious Play in 2xN Games", Journal of Economic Theory 120, 139–154.
- Berger, U. (2007) "[http://epub.wu.ac.at/5588/1/2007_JET.pdf Brown's original fictitious play]", Journal of Economic Theory 135:572–578
- Brown, G.W. (1951) "Iterative Solutions of Games by Fictitious Play" In Activity Analysis of Production and Allocation, T. C. Koopmans (Ed.), New York: Wiley.
- Fudenberg, D. and D.K. Levine (1998) [https://books.google.com/books?id=G6vTQFluxuEC&q=%22fictitious+play%22 The Theory of Learning in Games] Cambridge: MIT Press.
- Monderer, D., and Shapley, L.S. (1996-a) "[https://web.archive.org/web/20190717150637/https://pdfs.semanticscholar.org/0f5c/d47408dd93ad33eea7e167a498f4322d525c.pdf Potential Games]", Games and Economic Behavior 14, 124-143.
- Monderer, D., and Shapley, L.S. (1996-b) "[http://ie.technion.ac.il/~dov/fictitious%20play%20property--monderer-shapley.pdf Fictitious Play Property for Games with Identical Interests] {{Webarchive|url=https://web.archive.org/web/20210513055647/https://ie.technion.ac.il/~dov/fictitious%20play%20property--monderer-shapley.pdf |date=2021-05-13 }}", Journal of Economic Theory 68, 258–265.
- Nachbar, J. (1990) "[https://link.springer.com/article/10.1007/BF01753708 Evolutionary Selection Dynamics in Games: Convergence and Limit Properties]", International Journal of Game Theory 19, 59–89.
- von Neumann and Morgenstern (1944), [https://web.archive.org/web/20200210212055/https://pdfs.semanticscholar.org/0375/379194a6f34b818962ea947bff153adf621c.pdf Theory of Games and Economic Behavior], Princeton and Woodstock: Princeton University Press.
- Robinson, J. (1951) "[http://www.dklevine.com/archive/refs4422.pdf An Iterative Method of Solving a Game]", Annals of Mathematics 54, 296–301.
- Shapley L. (1964) "[https://web.archive.org/web/20190717150450/https://apps.dtic.mil/dtic/tr/fulltext/u2/407345.pdf Some Topics in Two-Person Games]" In Advances in Game Theory M. Dresher, L.S. Shapley, and A.W. Tucker (Eds.), Princeton: Princeton University Press.
External links
- [http://www.dudziak.com/poker.php Game-Theoretic Solution to Poker Using Fictitious Play]
{{Game theory}}