Fictitious Play Property for Games with Identical Interests

By Dov Monderer, Lloyd S. Shapley. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Empirically Evaluating Multiagent Learning Algorithms (2014, background): “ts own payoffs. Fictitious play is guaranteed to converge to a Nash equilibrium in self play for a restricted set of games. These games are said to have the ﬁctitious play property (see, for instance Monderer and Shapley (1996); for an example of a simple 2 × 2 game without this property see Mondere”
Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016, background): “two-player zero-sum and manyplayer potential games (Robinson, 1951; Monderer and Shapley, 1996).”
A survey and critique of multiagent deep reinforcement learning (2018, neutral): “, two-player zero-sum and potential games [222].”
The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems (1998, background): “This simple adaptive strategy will converge to an equilibrium in our simple cooperative games assuming that agents randomize when multiple best responses exist [12], and can be made to converge to an optimal equilibrium if appropriate mechanisms are adopted [1]; that is, the probability of coordinat”
On the Rate of Convergence of Fictitious Play (2010, methodology): “Since every non-degenerate 2×2 game is best-response equivalent to either a constant-sum game or a common payoff game [22], the result of Miyasawa follows more easily by combining those of Robinson [26] and Monderer and Shapley [22].”
Cooperative Control and Potential Games (2009, background): “2 The connection between cooperative control problems and potential games is important because learning algorithms for potential games have been studied extensively in the game theory literature [13, 12, 14, 15, 16].”
Stable solutions in potential mean field game systems (2016, methodology): “Following ideas of Monderer and Shapley [15], it was proved in [7] that the family (u,m) is compact in C × C and that any converging subsequence is a solution of the MFG system.”
Stochastic Approximations and Differential Inclusions (2005, result): “Here we generalize the result of Monderer and Shapley [25].”
Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria (2005, background): “A brief timeline of results that establish convergence of FP is as follows: 1951, two-player/zero-sum games [37]; 1961, two-player/two-move games [35]; 1993, noisy two-player/two-move games with a unique Nash equilibrium [20]; 1996, multiplayer games with identical player utilities [36]; 1999, noisy”
A survey of random processes with reinforcement (2006, background): “h dichotomous strategies but three players). There are, however, subclasses of non-zero-sum games for which ﬁctitious play has been shown to converge to Nash equilibria. These include potential games [MS96] (every player receives the same payoﬀ), super-modular games [MR90] (the payoﬀ matrix is super”
Autonomous Vehicle-Target Assignment: A Game-Theoretical Formulation (2007, background): “One appealing property of FP is that the empirical frequencies generated by FP converge to the set of Nash equilibria in potential games (cid:1) 7,16 (cid:2) .”
A Fictitious Play Approach to Large-Scale Optimization (2005, methodology): “The system-optimal traffic assignment problem with flow dependent costs has been studied extensively; see, for example, Potts and Oliver (1972) for an early survey.”
Sequential Optimality and Coordination in Multiagent Systems (1999, background): “For fully cooperative games, FP converges to an optimal joint action if attention is restricted to PIO-actions and agents randomize over tied best responses [2] [12].”
Federated Residual Learning (2020, background): “In general, fictitious play takes the learner an exponentially long time to converge (Monderer & Shapley, 1996; Brandt et al., 2010).”
Potential Games (1994, background): “In Monderer and Shapley (1996) we prove that the Fictitious Play process converges to the equilibrium set in a class of games that contains the finite (weighted) potential games.”