# Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 59 references that are in the map.
- First posted on arXiv 23 Jun 2024.

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

- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [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)
- [Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games](https://mlsanity.com/paper/2206.15395/) (2022)
- [For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria](https://mlsanity.com/paper/2207.03470/) (2022)
- [Game Transformations That Preserve Nash Equilibria or Best-Response Sets](https://mlsanity.com/paper/2111.00076/) (2021)
- [Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization](https://mlsanity.com/paper/2202.00789/) (2022)
- [The Computational Complexity of Single-Player Imperfect-Recall Games](https://mlsanity.com/paper/2305.17805/) (2023)
- [A Bridge between Polynomial Optimization and Games with Imperfect Recall](https://mlsanity.com/paper/2002.09941/) (2020)
- [Recursive Joint Simulation in Games](https://mlsanity.com/paper/2402.08128/) (2024)

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

- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)
- [Extrapolating Volition with Recursive Information Markets](https://mlsanity.com/paper/2604.08606/) (2026)
- [Do LLMs Take Care of Their Own? Similarity Signals Can Induce Cooperation](https://mlsanity.com/paper/2608.12125/) (2026)

## Abstract (arXiv)

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, Sigma2P , existsR, and exists forallR.