The Value of Recall in Extensive-Form Games
Journal:
arXiv
Published Date:
Dec 27, 2024
Abstract
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.
