mlsanityData to 7 Oct 2026

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

arXiv 2406.15970 ↗First posted 23 Jun 2024cs.GT cs.AI cs.CCcited by 4

Not on the map. Why?

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.

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

Builds on

10 of 59 references.

References · 10

  1. 2017Computational Results for Extensive-Form Adversarial Team Gamescited by 18
  2. 2020The Complexity of Gradient Descent: CLS = PPAD cap PLScited by 17
  3. 2023Game Theory with Simulation of Other Playerscited by 12
  4. 2022Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Gamescited by 6
  5. 2022For Learning in Symmetric Teams, Local Optima are Global Nash Equilibriacited by 6
  6. 2023The Computational Complexity of Single-Player Imperfect-Recall Gamescited by 5
  7. 2020A Bridge between Polynomial Optimization and Games with Imperfect Recallcited by 4
  8. 2021Game Transformations That Preserve Nash Equilibria or Best-Response Setscited by 4
  9. 2022Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimizationcited by 4
  10. 2024Recursive Joint Simulation in Gamescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Computing Game Symmetries and Equilibria That Respect Themcited by 3
  2. 2026Decision Making under Imperfect Recall: Algorithms and Benchmarkscited by 0
  3. 2026Extrapolating Volition with Recursive Information Marketscited by 0
  4. 2026Do LLMs Take Care of Their Own? Similarity Signals Can Induce Cooperationcited by 0