The Value of Recall in Extensive-Form Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913627716452352 |
|---|---|
| author | Berker, Ratip Emin Tewolde, Emanuel Anagnostides, Ioannis Sandholm, Tuomas Conitzer, Vincent |
| author_facet | Berker, Ratip Emin Tewolde, Emanuel Anagnostides, Ioannis Sandholm, Tuomas Conitzer, Vincent |
| contents | Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR 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 VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR 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 VoR in a broad class of games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19659 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Value of Recall in Extensive-Form Games Berker, Ratip Emin Tewolde, Emanuel Anagnostides, Ioannis Sandholm, Tuomas Conitzer, Vincent Computer Science and Game Theory 91A05, 91A06, 91A10, 91A11, 91A18, 91A35, 91A68, 68T37, 68Q17, 68Q25 F.2; I.2; J.4 Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR 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 VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR 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 VoR in a broad class of games. |
| title | The Value of Recall in Extensive-Form Games |
| topic | Computer Science and Game Theory 91A05, 91A06, 91A10, 91A11, 91A18, 91A35, 91A68, 68T37, 68Q17, 68Q25 F.2; I.2; J.4 |
| url | https://arxiv.org/abs/2412.19659 |