Satisficing Paths to Equilibrium, Generalized Weakly Acyclic Games, and Learning

Bora Yongacoglu, Gwendolen Hickey, G\"urdal Arslan, Lacra Pavel and Serdar Y\"uksel

Papers from arXiv.org

Abstract: Weakly acyclic games generalize potential games and have shown to be fundamental in the study of multi-agent learning as they allow for convergence to an equilibrium via best-responding under inertia. In this paper, we present a generalization of weakly acyclic games, and we demonstrate its importance in multi-agent learning when agents employ experimental strategy updates in periods where they fail to best respond. While weak acyclicity is defined in terms of path connectivity properties of a game's better response graph, our concept is defined using a generalized better response graph under revision dynamics termed as satisficing. We refer to this class of games as generalized weakly acyclic games (GenWAGs). We provide sufficient conditions for this notion of generalized weak acyclicity in both two-player games and n-player games in normal form, including static and dynamic games. Several graph theoretic characterizations of such games are presented together with sufficiency conditions, examples, and counterexamples. Finally, implications on learning via policy revision processes are presented.

Date: 2024-03, Revised 2026-07
New Economics Papers: this item is included in nep-gth, nep-inv and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2403.18086 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2403.18086

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().