Fictitious play
In game theory, fictitious play is a learning rule first introduced by George W. Brown. In it, each player presumes that the opponents are playing stationary (possibly mixed) strategies. At each round, each player thus best responds to the empirical frequency of play of their opponent. Such a method is of course adequate if the opponent indeed uses a stationary strategy, while it is flawed if the opponent's strategy is non-stationary. The opponent's strategy may for example be conditioned on the fictitious player's last move.
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)
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
- Berger, U. (2005) "Fictitious Play in 2xN Games", Journal of Economic Theory 120, 139–154.
- Berger, U. (2007) "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) The Theory of Learning in Games Cambridge: MIT Press.
- Monderer, D., and Shapley, L.S. (1996-a) "Potential Games", Games and Economic Behavior 14, 124-143.
- Monderer, D., and Shapley, L.S. (1996-b) "Fictitious Play Property for Games with Identical Interests Archived 2021-05-13 at the Wayback Machine", Journal of Economic Theory 68, 258–265.
- Nachbar, J. (1990) "Evolutionary Selection Dynamics in Games: Convergence and Limit Properties", International Journal of Game Theory 19, 59–89.
- von Neumann and Morgenstern (1944), Theory of Games and Economic Behavior, Princeton and Woodstock: Princeton University Press.
- Robinson, J. (1951) "An Iterative Method of Solving a Game", Annals of Mathematics 54, 296–301.
- Shapley L. (1964) "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
- Game-Theoretic Solution to Poker Using Fictitious Play
- v
- t
- e
- Congestion game
- Cooperative game
- Determinacy
- Escalation of commitment
- Extensive-form game
- First-player and second-player win
- Game complexity
- Graphical game
- Hierarchy of beliefs
- Information set
- Normal-form game
- Preference
- Sequential game
- Simultaneous game
- Simultaneous action selection
- Solved game
- Succinct game
- Mechanism design
concepts
- Bayes correlated equilibrium
- Bayesian Nash equilibrium
- Berge equilibrium
- Core
- Correlated equilibrium
- Coalition-proof Nash equilibrium
- Epsilon-equilibrium
- Evolutionarily stable strategy
- Gibbs equilibrium
- Mertens-stable equilibrium
- Markov perfect equilibrium
- Nash equilibrium
- Pareto efficiency
- Perfect Bayesian equilibrium
- Proper equilibrium
- Quantal response equilibrium
- Quasi-perfect equilibrium
- Risk dominance
- Satisfaction equilibrium
- Self-confirming equilibrium
- Sequential equilibrium
- Shapley value
- Strong Nash equilibrium
- Subgame perfection
- Trembling hand equilibrium
of games
- Go
- Chess
- Infinite chess
- Checkers
- All-pay auction
- Prisoner's dilemma
- Gift-exchange game
- Optional prisoner's dilemma
- Traveler's dilemma
- Coordination game
- Chicken
- Centipede game
- Lewis signaling game
- Volunteer's dilemma
- Dollar auction
- Battle of the sexes
- Stag hunt
- Matching pennies
- Ultimatum game
- Electronic mail game
- Rock paper scissors
- Pirate game
- Dictator game
- Public goods game
- Blotto game
- War of attrition
- El Farol Bar problem
- Fair division
- Fair cake-cutting
- Bertrand competition
- Cournot competition
- Stackelberg competition
- Deadlock
- Diner's dilemma
- Guess 2/3 of the average
- Kuhn poker
- Nash bargaining game
- Induction puzzles
- Trust game
- Princess and monster game
- Rendezvous problem
- Aumann's agreement theorem
- Folk theorem
- Minimax theorem
- Nash's theorem
- Negamax theorem
- Purification theorem
- Revelation principle
- Sprague–Grundy theorem
- Zermelo's theorem
figures
- Albert W. Tucker
- Amos Tversky
- Antoine Augustin Cournot
- Ariel Rubinstein
- Claude Shannon
- Daniel Kahneman
- David K. Levine
- David M. Kreps
- Donald B. Gillies
- Drew Fudenberg
- Eric Maskin
- Harold W. Kuhn
- Herbert Simon
- Hervé Moulin
- John Conway
- Jean Tirole
- Jean-François Mertens
- Jennifer Tour Chayes
- John Harsanyi
- John Maynard Smith
- John Nash
- John von Neumann
- Kenneth Arrow
- Kenneth Binmore
- Leonid Hurwicz
- Lloyd Shapley
- Melvin Dresher
- Merrill M. Flood
- Olga Bondareva
- Oskar Morgenstern
- Paul Milgrom
- Peyton Young
- Reinhard Selten
- Robert Axelrod
- Robert Aumann
- Robert B. Wilson
- Roger Myerson
- Samuel Bowles
- Suzanne Scotchmer
- Thomas Schelling
- William Vickrey