Research map / Learning theory and algorithms / Submodular and game algorithms
The Value of Recall in Extensive-Form Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines the value of recall (VoR) as the ratio of a player's utility under the coarsest perfect-recall refinement versus the original imperfect-recall game, bounds it via absentmindedness and chance nodes, connects it to smoothness/price of anarchy, and shows hardness results.
Problem
Quantifying how much a player gains (or can lose) from having perfect recall in imperfect-recall extensive-form games under various solution concepts.
Approach
Define VoR as the ratio of a player's utility under the coarsest perfect-recall refinement to that under the original game; parameterize it by absentmindedness coefficients and chance-node branching factors, show these bounds compose, and use the smoothness framework from price-of-anarchy to extend bounds to EDT/CDT equilibria.
Key results
- Shows VoR can be arbitrarily hurtful for all considered solution concepts: in a two-player game, perfect recall for one player drives both players' utilities toward zero ratios (VoR=0 for best/worst CDT/EDT/Nash).
- For single-player games, VoR under optimal play is bounded by max over leaves and chance nodes of branch(h)/am(z), and this bound is tight.
- Computing VoR is NP-hard and, for worst CDT/EDT equilibria, NP-hard to approximate to any multiplicative factor; k-best partial recall refinement is NP-hard.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Give the player perfect recall | Single-player absentminded game with n consecutive rounds · Single-player absentminded game | optimal expected utility: 2^{-n} -> 1 | Helped |
| Give the player perfect recall | Single-player chance game with n equally likely outcomes · Single-player chance game | optimal expected utility: 1/n -> 1 | Helped |
| Refine the player's information sets to give perfect recall, without revealing chance outcomes | Single-player game in Figure [ref] · Single-player game in Figure [ref] | optimal expected utility: 2/3 -> 3/2 | Helped |
| Give Player 1 perfect recall | Two-player investment game · Two-player investment game | Player 1 utility: 2 -> 0 | Hurt |
| Give Player 1 perfect recall | Two-player investment game · Two-player investment game | Player 2 utility: 1 -> \varepsilon | Hurt |
| Give the player perfect recall | Single-player example in Figure [ref] · Single-player game in Figure [ref] | utility under worst EDT equilibrium: 1 -> \varepsilon | Hurt |
| Remove both chance nodes and absentmindedness | Single-player game under optimal play · Single-player games with no chance nodes and no absentmindedness | value of recall: \vor^{\opt}(\Gamma)=1 | No clear effect |
| Use the worst EDT/CDT equilibrium instead of optimal play in a single-player game | Single-player game with perfect recall refinement · Single-player games | utility under equilibrium: 1 -> \varepsilon | Mixed |
Surprising findings
- Giving one player perfect recall can diminish every player's utility, including the player's own, as in an investment-bot trust game.
- Worst EDT/CDT equilibria in single-player games can get worse under perfect recall, a pathology fixed by new EDT-Nash and CDT-Nash refinements.
Limitations
- VoR can be unbounded in general; bounds depend on absentmindedness and chance structure.
- Computing and approximating VoR is NP-hard, even for single-player games.
Experimental setup
Metrics: value of recall (ratio of utilities)
Builds on: extensive-form games with imperfect recall (multiselves approach) smoothness framework (Roughgarden) value of commitment CDT-Nash refinement
Closest papers by meaning
- Solving Imperfect-Recall Games via Sum-of-Squares Optimization (ICML 2026 · similarity 0.90)
- Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games (AAAI 2024 · similarity 0.85)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.85)
- Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.85)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.85)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.