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

47 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
Country/TerritoryUnited 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