Solving Imperfect-Recall Games via Sum-of-Squares Optimization

Rui Zheng, Ryann Sim, Antonios Varvitsiotis · 2026

Read Solving Imperfect-Recall Games via Sum-of-Squares Optimization by Rui Zheng, Ryann Sim, Antonios Varvitsiotis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-21722.txt.

Description

Extensive-form games model sequential decisions under imperfect information, chance, and time. Most positive results assume perfect recall, where players remember all past information and actions. Imperfect-recall games, where players may forget parts of their history, are provably hard for equilibrium computation. Rui Zheng and two co-authors propose sum-of-squares hierarchies for ex-ante optimal strategies in single-player games and Nash equilibria in multi-player games. The hierarchies work over behavioral strategies.

The hierarchies converge asymptotically, converge finitely under genericity assumptions, and in single-player non-absentminded games converge at a level set by the number of information sets. New classes of SOS-concave and SOS-monotone games are introduced, and in the single-player setting the hierarchy converges at the first level, so equilibrium computation needs just one semidefinite program.

Catalog record

CREATORRui Zheng, Ryann Sim, Antonios Varvitsiotis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-21722

Browse the full library · About the Tower of Babel