Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sandholm, Paul Goldberg, Vincent Conitzer
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 extensiveform 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, ΣP 2, R, and R. |
| Researcher Affiliation | Collaboration | 1Carnegie Mellon University 2Yale University 3University of Oxford 4Foundations of Cooperative AI Lab (FOCAL) 5Strategic Machine, Inc., 6Strategy Robot, Inc., 7Optimized Markets, Inc. |
| Pseudocode | No | The paper contains mathematical definitions, propositions, theorems, and proofs, but no pseudocode or algorithm blocks are present. |
| Open Source Code | No | The paper does not mention releasing code, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity analysis. It does not involve datasets, training, or empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation, dataset splits (training/validation/test), or cross-validation details. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments or any specific hardware used for computations. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe implementations or experiments that would require listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments. Therefore, no experimental setup details such as hyperparameters or training configurations are provided. |