Fictitious play
From Wikipedia, the free encyclopedia
In game theory, fictitious play is a learning rule first introduced by G.W. Brown (1951). In it, each player presumes that her/his opponents are playing stationary (possibly mixed) strategies. At each round, each player thus best responds to the empirical frequency of play of his 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.
Contents |
[edit] 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 his mind and update his 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.
[edit] Convergence properties
In fictitious play 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 | 1, 0 | 0, 1 |
| b | 0, 1 | 0, 0 | 1, 0 |
| c | 1, 0 | 0, 1 | 0, 0 |
Therefore, the interesting question is, under what circumstances does fictitious play converge? The process will converge for a 2-person game if:
- 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 2xN (Berger 2005)
Fictitious play does not always converge, however. Shapley (1964) proved that in the game pictured here (a limit case of generalized Rock, Paper, Scissors games), if the players start by choosing (a, B), the play will cycle indefinitely.
[edit] References
- Berger, U. (2005) "Fictitious Play in 2xN Games", Journal of Economic Theory 120, 139-154.
- 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", 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.
- 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. Drescher, L.S. Shapley, and A.W. Tucker (Eds.), Princeton: Princeton University Press.
[edit] External links
|
||||||||||||||||||||
