|
In game theory, fictitious play is a learning rule first introduced by G.W. Brown (1951). In it, each player presumes that her opponents are playing stable (possibly mixed) strategies. Each player starts with some initial beliefs and choose a best response to those beliefs as a strategy in this round. Then, after observing their opponents' actions, the players update their beliefs according to some learning rule (e.g. reinforcement learning or Bayes' rule). The process is then repeated. Game theory is a branch of applied mathematics that studies strategic situations where players choose different actions in an attempt to maximize their returns. ...
A mixed strategy is used in game theory economics to describe a strategy comprising possible moves and a probability distribution which corresponds to how frequently each move is chosen. ...
In game theory, the best response is the strategy in a single period that creates the most favorable immediate outcome for the current player, taking other players strategies as given. ...
// The reinforcement learning problem A class of problems in machine learning which postulate an agent exploring an environment in which the agent perceives its current state and takes actions. ...
Bayes theorem is a result in probability theory, which gives the conditional probability distribution of a random variable A given B in terms of the conditional probability distribution of variable B given A and the marginal probability distribution of A alone. ...
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. In game theory, the Nash equilibrium (named after John Nash who proposed it) is a kind of optimal collective strategy in a game involving two or more players, where no player has anything to gain by changing only his or her own strategy. ...
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) In game theory, the Nash equilibrium (named after John Nash) is a kind of optimal strategy for games involving two or more players, whereby the players reach an outcome to mutual advantage. ...
An interesting game | 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 if: - The game has generic payoffs and is 2x2 (Miyasawa 1961)
- The game is zero sum (Robinson 1951)
- The game is solvable by iterated elimination of strictly dominated strategies (Nachbar 1990)
Fictitious play does not always converge, however. Consider the game pictured here. Shapley (1964) proved if the players start by choosing (a, B), the play will cycle indefinitely. Zero-sum describes a situation in which a participants gain (or loss) is exactly balanced by the losses (or gains) of the other participant(s). ...
In game theory, dominance occurs when one strategy is better or worse than another regardless of the strategies of a players opponents. ...
References - 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.
- Miyasawa, K. (1961) "On the Convergence of Learning Processes in a 2x2 Non-Zero-Person Game," Research Memo 33. Princeton University.
- Nachbar, J. (1990) "'Evolutionary Selection Dynamics in Games: Convergence and Limit Properties," International Journal of Game Theory. 19:59-89.
- Robinson, J. (1951) "A Iterative Method of Solving a Game" Annals in Mathematics. 54: 296-301.
- Shapley L. (1964) "Some Topics in Two-Person Games" Advance in Game Theory M. Drescher, L.S. Shapley, and A.W. Tucker (Eds.). Princeton: Princeton University Press.
|
Feeds |
Contact