@inproceedings{b332a9ac18064cb183b58f8dac02dbe6,
title = "Regret based dynamics: Convergence in weakly acyclic games",
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.",
keywords = "Cooperative distributed problem solving, Emergent behavior, Game theory, Learning algorithms, Multiagent learning",
author = "Marden, {Jason R.} and G{\"u}rdal Arslan and Shamma, {Jeff S.}",
year = "2007",
doi = "10.1145/1329125.1329175",
language = "English (US)",
isbn = "9788190426275",
series = "Proceedings of the International Conference on Autonomous Agents",
pages = "194--201",
booktitle = "AAMAS'07 - Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems",
note = "6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS'07 ; Conference date: 14-05-2008 Through 18-05-2008",
}