The Computational Complexity of Single-Player Imperfect-Recall Games
Authors: Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. Goldberg
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study single-player extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absentminded Driver game. For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality. Our findings relate those three solution concepts of a game to solution concepts of a polynomial maximization problem: global optima, optimal points with respect to subsets of variables and Karush Kuhn Tucker (KKT) points. Based on these correspondences, we are able to settle various complexity-theoretic questions on the computation of such strategies. For ex-ante optimality and (EDT,GDH)-equilibria, we obtain NP-hardness and inapproximability, and for (CDT,GT)-equilibria we obtain CLS-completeness results. |
| Researcher Affiliation | Academia | 1 Foundations of Cooperative AI Lab (FOCAL), Carnegie Mellon University 2 University of Oxford emanueltewolde@cmu.edu, oesterheld@cmu.edu, conitzer@cs.cmu.edu, paul.goldberg@cs.ox.ac.uk |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing concrete access to source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on computational complexity and does not use or reference empirical datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | This is a theoretical paper; therefore, no hardware specifications for running experiments are provided. |
| Software Dependencies | No | The paper does not provide specific software dependencies (e.g., library or solver names with version numbers) needed to replicate any experiments. |
| Experiment Setup | No | This is a theoretical paper and does not include details about an experimental setup, hyperparameters, or training settings for empirical experiments. |