Solving Imperfect-Recall Games via Sum-of-Squares Optimization
For researchers and practitioners in game theory and AI, this provides a new theoretical framework for solving a class of games that was previously intractable, though the results are largely theoretical and not yet demonstrated empirically.
The paper addresses the problem of computing optimal strategies and Nash equilibria in imperfect-recall extensive-form games, which are computationally hard. It proposes sum-of-squares hierarchies that converge asymptotically, with finite convergence under genericity assumptions, and for single-player non-absentminded games convergence at a level determined by the number of information sets.
Extensive-form games (EFGs) provide a powerful framework for modeling sequential decision making, capturing strategic interaction under imperfect information, chance events, and temporal structure. Most positive algorithmic and theoretical results for EFGs assume perfect recall, where players remember all past information and actions. We study the increasingly relevant setting of imperfect-recall EFGs (IREFGs), where players may forget parts of their history or previously acquired information, and where equilibrium computation is provably hard. We propose sum-of-squares (SOS) hierarchies for computing ex-ante optimal strategies in single-player IREFGs and Nash equilibria in multi-player IREFGs, working over behavioral strategies. Our theoretical results show that (i) these hierarchies converge asymptotically, (ii) under genericity assumptions, the convergence is finite, and (iii) in single-player non-absentminded IREFGs, convergence occurs at a finite level determined by the number of information sets. Finally, we introduce the new classes of (SOS)-concave and (SOS)-monotone IREFGs, and show that in the single-player setting the SOS hierarchy converges at the first level, enabling equilibrium computation with a single semidefinite program (SDP).