The Value of Recall in Extensive-Form Games
Authors: Ratip Emin Berker, Emanuel Tewolde, Ioannis Anagnostides, Tuomas Sandholm, Vincent Conitzer
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (Vo R). While Vo R can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with Vo R, and show how to circumvent them. We also study the complexity of computing Vo R, and how to optimally apportion partial recall. Finally, we connect Vo R to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize Vo R in a broad class of games. The results for CDT and EDT are new, further establishing stronger inapproximability; both proofs proceed by reducing from 3SAT, as we elaborate in the appendix. |
| Researcher Affiliation | Collaboration | 1Carnegie Mellon University 2Foundations of Cooperative AI Lab (FOCAL) 3University of Oxford 4Strategic Machine, Inc. 5Strategy Robot, Inc. 6Optimized Markets, Inc. EMAIL |
| Pseudocode | No | The paper does not contain any sections explicitly labeled 'Pseudocode' or 'Algorithm', nor does it present any structured, code-like procedural steps. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide any links to code repositories. |
| Open Datasets | No | The paper is theoretical and does not present experiments relying on specific datasets that would require public access information. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments requiring dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental setups that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe experimental setups that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details on experimental setup, hyperparameters, or training configurations. |