The Computational Complexity of Single-Player Imperfect-Recall Games
This addresses foundational complexity questions for decision theory and game theory, with implications for AI and economics, though it is incremental in extending known computational results to new equilibrium concepts.
The paper tackles the computational complexity of finding equilibrium strategies in single-player imperfect-recall games, establishing NP-hardness and inapproximability for ex-ante optimality and (EDT,GDH)-equilibria, and CLS-completeness for (CDT,GT)-equilibria.
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. One equilibrium concept uses generalized double halving (GDH) as a belief system and evidential decision theory (EDT), and another one uses generalized thirding (GT) as a belief system and causal decision theory (CDT). 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.