Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910499077095424 |
|---|---|
| author | Tewolde, Emanuel Zhang, Brian Hu Oesterheld, Caspar Zampetakis, Manolis Sandholm, Tuomas Goldberg, Paul W. Conitzer, Vincent |
| author_facet | Tewolde, Emanuel Zhang, Brian Hu Oesterheld, Caspar Zampetakis, Manolis Sandholm, Tuomas Goldberg, Paul W. Conitzer, Vincent |
| contents | We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes P, PPAD, PLS, $Σ_2^P$ , $\exists$R, and $\exists \forall$R. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15970 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Imperfect-Recall Games: Equilibrium Concepts and Their Complexity Tewolde, Emanuel Zhang, Brian Hu Oesterheld, Caspar Zampetakis, Manolis Sandholm, Tuomas Goldberg, Paul W. Conitzer, Vincent Computer Science and Game Theory Artificial Intelligence Computational Complexity 91A05, 91A06, 91A10, 91A11, 91A18, 91A35, 91A68, 68T37, 68Q17, 68Q25 I.2; J.4; F.2 We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes P, PPAD, PLS, $Σ_2^P$ , $\exists$R, and $\exists \forall$R. |
| title | Imperfect-Recall Games: Equilibrium Concepts and Their Complexity |
| topic | Computer Science and Game Theory Artificial Intelligence Computational Complexity 91A05, 91A06, 91A10, 91A11, 91A18, 91A35, 91A68, 68T37, 68Q17, 68Q25 I.2; J.4; F.2 |
| url | https://arxiv.org/abs/2406.15970 |