Regret based dynamics: Convergence in weakly acyclic games

Jason R. Marden, Gürdal Arslan, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

43 Scopus citations

Abstract

No-regret algorithms have been proposed to control a wide variety of multi-agent systems. The appeal of no-regret algorithms is that they are easily implementable in large scale multi-agent systems because players make decisions using only retrospective or "regret based" information. Furthermore, there are existing results proving that the collective behavior will asymptotically converge to a set of points of "no-regret" in any game. We illustrate, through a simple example, that no-regret points need not reflect desirable operating conditions for a multi-agent system. Multi-agent systems often exhibit an additional structure (i.e. being "weakly acyclic") that has not been exploited in the context of no-regret algorithms. In this paper, we introduce a modification of the traditional no-regret algorithms by (i) exponentially discounting the memory and (ii) bringing in a notion of inertia in players' decision process. We show how these modifications can lead to an entire class of regret based algorithms that provide almost sure convergence to a pure Nash equilibrium in any weakly acyclic game.

Original languageEnglish (US)
Title of host publicationAAMAS'07 - Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems
Pages194-201
Number of pages8
DOIs
StatePublished - Dec 1 2007
Event6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS'07 - Honolulu, HI, United States
Duration: May 14 2008May 18 2008

Publication series

NameProceedings of the International Conference on Autonomous Agents

Other

Other6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS'07
CountryUnited States
CityHonolulu, HI
Period05/14/0805/18/08

Keywords

  • Cooperative distributed problem solving
  • Emergent behavior
  • Game theory
  • Learning algorithms
  • Multiagent learning

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Computer Networks and Communications
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Regret based dynamics: Convergence in weakly acyclic games'. Together they form a unique fingerprint.

Cite this