Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria

By Jeff S. Shamma, Gürdal Arslan. 2005

393 citations recorded by the source corpus.

We consider a continuous-time form of repeated matrix games in which player strategies evolve in reaction to opponent actions. Players observe each other's actions, but do not have access to other player utilities. Strategy evolution may be of the best response sort, as in fictitious play, or a gradient update. Such mechanisms are known to not necessarily converge. We introduce a form of "dynamic" fictitious and gradient play strategy update mechanisms. These mechanisms use derivative action in processing opponent actions and, in some cases, can lead to behavior converging to Nash equilibria in previously nonconvergent situations. We analyze convergence in the case of exact and approximate derivative measurements of the dynamic update mechanisms. In the ideal case of exact derivative measurements, we show that convergence to Nash equilibrium can always be achieved. In the case of approximate derivative measurements, we derive a characterization of local convergence that shows how the dynamic update mechanisms can converge if the traditional static counterparts do not. We primarily discuss two player games, but also outline extensions to multiplayer games. We illustrate these methods with convergent simulations of the well known Shapley and Jordan counterexamples.

Subfields: Management Science and Operations Research, Public Health, Environmental and Occupational Health, Statistical and Nonlinear Physics

How researchers see this paper

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

In Management Science and Operations Research

In Public Health, Environmental and Occupational Health

In Statistical and Nonlinear Physics

Citations in the corpus

Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016, methodology): “Second, it uses anticipatory dynamics (Shamma and Arslan, 2005) to enable each agent to both sample its own best response behaviour and more effectively track changes to opponents’ behaviour.”
Joint Strategy Fictitious Play with Inertia for Potential Games (2005, background): “General convergence issues are discussed in [16], [17], [18].”
Distributed Seeking of Nash Equilibria With Applications to Mobile Sensor Networks (2012, background): “For games with finite action sets, where the players can use mixed strategie s, the convergence of the underlying best response algorithm, called fictitious play, and its modifications have been analy zed intensively (see [12] and references therein).”
Nash Equilibrium Seeking in Noncooperative Games (2012, background): “In more recent work, a dynamic version of fictitious play and gradient response, which also includes an entropy term, is developed in [6] and is shown to converge to a mixed-strategy Nash equilibrium in cases that previously developed algorithms did not converge.”
Consensus and Cooperation in Networked Multi-Agent Systems (2007, background): “This includes basic notions in information consensus and control theoretic methods for convergence and performance analysis of consensus protocols that heavily rely on matrix theory and spectral graph theory.”
Designing games for distributed optimization (2011, background): “…i.e., the number of players is odd; (iii) The communication graph G contains at least two players which have a different number of neighbors, i.e., |N i | = |N j | for some players i, j ∈ N ; Then the state action pair [x, a] = [(v, e), (ˆ v, ˆ e)] is a recurrent state equilibrium in game G if…”
A Passivity-Based Approach to Nash Equilibrium Seeking Over Networks (2017, background): “In a game of perfect information, under Assumption 2(i), a typical gradient-based dynamics [2], [26], [27], [52] can be used for each player i”
Distributed Nash Equilibrium Seeking by a Consensus Based Approach (2016, background): “Dynamic fictitious play and gradient play were exploited in [4] for a continuous-time form of repeated matrix games.”
Learning and Equilibrium (2009, background): “23 It should be noted that Shamma & Arslan (2005) choose the units of time so that 1φ = .”