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

Jeff S. Shamma*, Gürdal Arslan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

216 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)312-327
Number of pages16
JournalIEEE Transactions on Automatic Control
Volume50
Issue number3
DOIs
StatePublished - Mar 1 2005

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Dynamic fictitious play, dynamic gradient play, and distributed convergence to nash equilibria'. Together they form a unique fingerprint.

Cite this