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
| CREATOR | Rui Zheng, Ryann Sim, Antonios Varvitsiotis |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-21722