# The Computational Complexity of Single-Player Imperfect-Recall Games

arXiv: https://arxiv.org/abs/2305.17805 · HTML: https://mlsanity.com/paper/2305.17805/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 58 references that are in the map.
- First posted on arXiv 28 May 2023.

## Builds on (most cited first, 5 of 5)

- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Game Theory with Simulation of Other Players](https://mlsanity.com/paper/2305.11261/) (2023)
- [Imperfect-Recall Abstractions with Bounds in Games](https://mlsanity.com/paper/1409.3302/) (2014)
- [A Bridge between Polynomial Optimization and Games with Imperfect Recall](https://mlsanity.com/paper/2002.09941/) (2020)
- [Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy](https://mlsanity.com/paper/2207.08151/) (2022)

## Built on by (most cited first, 5 of 5)

- [Imperfect-Recall Games: Equilibrium Concepts and Their Complexity](https://mlsanity.com/paper/2406.15970/) (2024)
- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)
- [Do LLMs Take Care of Their Own? Similarity Signals Can Induce Cooperation](https://mlsanity.com/paper/2608.12125/) (2026)

## Abstract (arXiv)

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.