Generalizing Better Response Paths and Weakly Acyclic Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929291210522624 |
|---|---|
| author | Yongacoglu, Bora Arslan, Gürdal Pavel, Lacra Yüksel, Serdar |
| author_facet | Yongacoglu, Bora Arslan, Gürdal Pavel, Lacra Yüksel, Serdar |
| contents | Weakly acyclic games generalize potential games and are fundamental to the study of game theoretic control. In this paper, we present a generalization of weakly acyclic games, and we observe 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 generalization is defined using a generalized better response graph. We provide sufficient conditions for this notion of generalized weak acyclicity in both two-player games and $n$-player games. To demonstrate that our generalization is not trivial, we provide examples of games admitting a pure Nash equilibrium that are not generalized weakly acyclic. The generalization presented in this work is closely related to the recent theory of satisficing paths, and the counterexamples presented here constitute the first negative results in that theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18086 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalizing Better Response Paths and Weakly Acyclic Games Yongacoglu, Bora Arslan, Gürdal Pavel, Lacra Yüksel, Serdar Computer Science and Game Theory Theoretical Economics Weakly acyclic games generalize potential games and are fundamental to the study of game theoretic control. In this paper, we present a generalization of weakly acyclic games, and we observe 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 generalization is defined using a generalized better response graph. We provide sufficient conditions for this notion of generalized weak acyclicity in both two-player games and $n$-player games. To demonstrate that our generalization is not trivial, we provide examples of games admitting a pure Nash equilibrium that are not generalized weakly acyclic. The generalization presented in this work is closely related to the recent theory of satisficing paths, and the counterexamples presented here constitute the first negative results in that theory. |
| title | Generalizing Better Response Paths and Weakly Acyclic Games |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2403.18086 |