Fictitious play
Encyclopedia
In game theory
, fictitious play is a learning rule first introduced by G.W. Brown (1951). 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 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.
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.
Therefore, the interesting question is, under what circumstances does fictitious play converge? The process will converge for a 2-person game if:
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.
s.
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.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, fictitious play is a learning rule first introduced by G.W. Brown (1951). 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 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.
History
Brown first introduced fictitious play as an explanation for Nash equilibriumNash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
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.
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:
- 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 strategiesDominance (game theory)In game theory, strategic dominance occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play...
(Nachbar 1990) - The game is a potential gamePotential gameA game in game theory is considered a potential game if the incentive of all players to change their strategy can be expressed in one global function, the potential function. The concept was proposed by Dov Monderer and Lloyd Shapley. Games can be either ordinal or cardinal potential games...
(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
Rock, Paper, Scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
games), 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..." and points out that modern usage involves the players updating their beliefs simultaneously. Berger goes on to say that Brown clearly states that the players update alternatingly. Berger then uses Brown's original form to present a simple and intuitive proof of convergence in the case of nondegenerate ordinal potential gamePotential game
A game in game theory is considered a potential game if the incentive of all players to change their strategy can be expressed in one global function, the potential function. The concept was proposed by Dov Monderer and Lloyd Shapley. Games can be either ordinal or cardinal potential games...
s.
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.