*** Welcome to piglix ***

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.

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.

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)

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 nonzero-sum version of Rock, Paper, Scissors), if the players start by choosing (a, B), the play will cycle indefinitely.

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 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.


...
Wikipedia

...