Personality-Based Representations of Imperfect-Recall Games

Games with imperfect recall are a powerful model of strategic interactions that allows agents to forget less important details of the past. Nevertheless, the computational treatment of imperfectrecall games is largely unexplored so far, and no efficient strategy representation for this setting is known. In this paper, we focus on general imperfect-recall games without absentmindedness, and we study how to produce a perfect-recall representation of these games using personalities. In particular, a valid personality assignment is a decomposition of an imperfect-recall player such that she does not exhibit memory losses within the same personality. Given a valid personality assignment, we can build an auxiliary team game where a team of perfect-recall players-sharing the same objectivesreplaces a player with imperfect recall. Our primary goal is the construction of a compact representation in terms of number of personalities. We study the (iterated) inflation operation as a way to simplify the information structure of a game with imperfect recall. We show that the complete (i.e., maximal) inflation of a game can be found in polynomial time. We also show that finding the valid personality assignment minimizing the number of personalities is NP-hard, and also hard to approximate, unless P = NP, even in a completely inflated game.