In
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, 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
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
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
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
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)
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
Zero-sum game is a mathematical representation in game theory and economic theory of a situation which involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is e ...
(Robinson 1951)
# The game is solvable by iterated elimination of
strictly dominated strategies (Nachbar 1990)
# The game is a
potential game
In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and ...
(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
Rock paper scissors (also known by other orderings of the three items, with "rock" sometimes being called "stone," or as Rochambeau, roshambo, or ro-sham-bo) is a hand game originating in China, usually played between two people, in which each ...
), 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 game
In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and ...
s.
The term "fictitious" had earlier been given another meaning in game theory. Von Neumann and Morgenstern
944defined 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, ''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
{{Game theory
Game theory