Pith. sign in

REVIEW 4 major objections 4 minor 87 references

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

T0 review · 4 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Imperfect-recall games, long thought intractable, can be solved by semidefinite relaxations: convergence is guaranteed, typically finite, and exact at the first level for a newly defined class.

desk verdict Solid SOS transfer with one real gap: the ℓ+1 exactness for non-absentminded single-player games is the contribution; the genericity-to-LICQ bridge is asserted, not shown. read the letter →

arxiv 2602.21722 v2 pith:Z2BT67UF submitted 2026-02-25 cs.GT

Rui Zheng , Ryann Sim , Antonios Varvitsiotis This is my paper · ORCID
classification cs.GT MSC 91A1890C2290C26
keywords imperfect-recallextensive-formgamesbehavioralstrategiessum-of-squareshierarchymomentrelaxationpolynomialNashequilibriumsemidefiniteprogrammingnon-absentminded
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that the computational hardness of imperfect-recall extensive-form games does not end the search for positive algorithms: because each player's expected utility is a polynomial in behavioral strategies over a product of simplices, the whole apparatus of moment/sum-of-squares relaxations applies. For single-player games, the hierarchy is shown to converge to the ex-ante optimum, to converge finitely for almost all payoff structures, and for non-absentminded games to be exactly tight at a relaxation order equal to the number of information sets plus one. For multi-player games, a select-verify-cut scheme built on first-order optimality conditions converges asymptotically, finitely in the generic case, and in non-absentminded games reduces to a single relaxation that either finds a behavioral Nash equilibrium or certifies that none exists. The paper also isolates SOS-concave and SOS-monotone single-player games, where the first relaxation is already exact, so one semidefinite program computes and certifies a global optimum. If these results hold up, equilibrium computation in a practically relevant class of imperfect-recall games becomes a convex problem rather than an intractable search.

What carries the argument

The load-bearing construction is the translation of an imperfect-recall game's expected utility into a polynomial on a product of simplices, so that computing an ex-ante optimum is maximizing a polynomial over a semi-algebraic set. Onto this the paper lays the Moment-SOS hierarchy — a sequence of convex semidefinite relaxations indexed by degree, whose dual moment matrices tighten bounds until a flatness condition certifies exactness and recovers strategies. For non-absentminded games, utility is blockwise multi-affine, so optimization can be restricted to vertices via the binomial equations μ_{j,a}(μ_{j,a}−1)=0; the key rank-stabilization lemma makes the moment matrix flat once the relaxati

What would settle it

Take any non-absentminded single-player imperfect-recall game with ℓ information sets, compute the global optimum by brute-force vertex enumeration, and solve the degree-(ℓ+1) moment relaxation with a semidefinite program solver; a positive gap between the true optimum and the relaxed bound refutes the exactness claim. The first-level claim can be tested the same way on an SOS-concave or SOS-monotone instance whose SOS-concavity is verified by a separate semidefinite program: the degree-d0 relaxation must match the brute-force optimum.

Watch

Extended reading notes

Core claim

The central discovery is that behavioral equilibrium computation in imperfect-recall games inherits the convergence guarantees of the Moment-SOS hierarchy. The paper proves three layers: general asymptotic convergence; generic finite convergence for almost all games; and structural exactness — at level equal to the number of information sets plus one for non-absentminded single-player games, via flatness of the moment matrix on the vertex-restricted problem, and at the first level for single-player SOS-concave and SOS-monotone games, via a sum-of-squares certificate of optimality. In these exact regimes the relaxation value equals the true ex-ante optimum and the optimizing behavioral strate

Load-bearing premise

The finite-convergence results for 'almost all' games rest on an unproven transfer: that the only property the generic-coefficient assumption provides is linear-independence constraint qualification, so a known finite-variety argument carries over from generic polynomial games to simplex-constrained games; if that transfer fails, those results reduce to asymptotic convergence only.

Editorial extensions

If this is right

  • In any non-absentminded single-player imperfect-recall game with ℓ information sets, the ex-ante optimal strategy can be obtained with a global optimality certificate by solving one semidefinite relaxation of order ℓ+1.
  • For single-player SOS-concave and SOS-monotone games, the hierarchy stops at its first step: one semidefinite program returns the global optimum, and the optimal strategy is read directly from the first moments without an extraction pass.
  • For almost all single-player imperfect-recall games, the KKT-based relaxation converges exactly at some finite order, giving a finite algorithm rather than a limiting guarantee.
  • For multi-player imperfect-recall games, the select-verify-cut scheme is a decision procedure that either certifies a behavioral Nash equilibrium or certifies nonexistence; under genericity it terminates in finitely many iterations, and in non-absentminded games a single vertex-restricted relaxation suffices.
  • Because SOS-concavity is itself checkable by one semidefinite program, the class of games solved at the first level is algorithmically recognizable, not just theoretically defined.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exactness-at-ℓ+1 bound suggests a parameterized view of hardness: for a fixed number of information sets, non-absentminded single-player games may be solvable in polynomial time in the rest of the description, with the exponential cost shifted entirely into the size of the degree-(ℓ+1) moment matrix.
  • A natural stress test is whether the paper's empirical observation that convergence often occurs below the worst-case level ℓ+1 persists for larger games; if so, lower-order relaxations could serve as fast certified heuristics.
  • The same machinery that certifies SOS-concavity could plausibly be combined with the multi-player KKT formulation to obtain first-level exactness for multi-player SOS-concave games; the paper proves first-level exactness only in the single-player setting, but the convexity structure makes the multi-player analogue a promising open direction.
  • The paper's absentminded examples exhibit non-vertex optimal strategies, suggesting a qualitative boundary: information-set recurrence forces continuous solutions, which is likely why the clean exactness results are restricted to non-absentminded games.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper develops sum-of-squares/moment hierarchies for solving imperfect-recall extensive-form games (IREFGs) in behavioral strategies. It builds on the folklore reduction from IREFGs to polynomial games over products of simplices and applies Lasserre-style relaxations. For single-player IREFGs it claims: (i) asymptotic convergence of the hierarchy; (ii) finite convergence for generic utilities via a KKT-based formulation, transferring a theorem of Nie–Tang; and (iii) exactness at degree ℓ+1 for non-absentminded games via a vertex-restricted formulation, where ℓ is the number of information sets. For multi-player IREFGs it adapts the select-verify-cut framework, claiming asymptotic exactness, finite convergence under genericity, and a one-shot vertex-restricted SDP in the non-absentminded case. It also introduces SOS-concave/SOS-monotone IREFGs and claims first-level exactness in the single-player case. The paper includes proofs, a construction from polynomials to IREFGs, and small numerical experiments.

Significance. If the main theorems hold, this is a valuable contribution: it gives a unified polynomial-optimization treatment of IREFGs, provides explicit finite-level exactness for non-absentminded single-player games, and identifies new tractable subclasses with first-level SOS convergence. The polynomial-game reduction and the moment-SOS formulations are clearly presented, and the central ideas are promising. The strongest and most original parts are Theorem 4.1(iii) and Theorem 6.3(ii), which do not depend on the contested genericity transfer. However, several load-bearing points need repair: the transfer of the Nie–Tang genericity theorem to fixed simplex constraints is asserted without proof, the proof of Lemma G.1 omits the required truncated ideal-membership argument, and the proof of Theorem 6.3(i) uses a false uniform positive-definiteness claim. These issues do not appear to be fatal to the overall framework, but they must be fixed before the paper can be accepted.

major comments (4)
  1. [§3, paragraph after (KKT)] The bridge from [52, Thm. A.1] is asserted rather than proved. The sentence "genericity is used there only to imply LICQ" is the sole support for the finite-convergence claims in Theorems 4.1(ii), 5.1(ii), and the finite-order part of 5.1(iii). LICQ is a local full-rank condition on active constraint gradients; it does not by itself imply that the KKT system defines a zero-dimensional complex variety. Moreover, genericity for IREFGs must be stated in the space of leaf payoffs for a fixed game tree, not in the ambient coefficient space of arbitrary polynomials; the map from leaf payoffs to the KKT polynomial system may have positive-dimensional fibers. Please provide a proof that for fixed simplex constraints the KKT system in Eq. (41) has finitely many complex solutions for almost all payoff vectors, or explicitly downgrade the "almost all games converge finitely" statements to asymptoti
  2. [§G.2, Lemma G.1] The proof that a column indexed by a monomial m containing two variables from the same block is zero uses only the statement that the clipped polynomial vanishes on the vertex set. But the moment constraints in Eq. (33) only enforce vanishing on the truncated ideal generated by h_j and b_j^a; they do not enforce all polynomials that vanish on S_vr. The needed ideal membership x_a x_a' ∈ (h_j, {b_j^a}) must be proved explicitly, with multipliers and degree bounds. Similarly, the reduction of a monomial m to its clipped form must be shown to use only relations of degree at most 2s, since the constraints are imposed only up to degree 2s. Without this degree bookkeeping, Theorem 4.1(iii) is not established.
  3. [§G.4, proof of Theorem 6.3(i)] The proof claims that strict concavity of u on S plus compactness yields δ > 0 with −∇²u(µ) ⪰ δI for all µ ∈ S. This is false: u(x) = −x^4 on [−1,1] is strictly concave but ∇²u(0) = 0. The subsequent matrix-Putinar argument requires a positive definite matrix F(µ, µ*) on S, and the pointwise Hessian bound does not provide it. The theorem may be true, but the proof needs a correct certificate, for example using the integral form of convexity with a positive-definite integral kernel, or a statement restricted to SOS-concave or strongly concave utilities.
  4. [§G.3, proof of Theorem 5.1(i)] The asymptotic exactness of the select-verify-cut procedure is asserted more than proved. The selector changes after each cut, and moment relaxations give converging values, not automatically converging points. Please specify the extraction step in the limit: show that flatness occurs at increasing orders, extracted atoms converge (subsequentially) to a point feasible for the exact selector with all accumulated cuts, and that infeasibility detection for the selector is guaranteed at high enough order. This is needed to support the claim that the loop returns an NE or certifies nonexistence asymptotically.
minor comments (4)
  1. [§3 and Appendix F, Eq. (41)] The sign convention in the KKT system is inconsistent. Section 3 writes w_j^i + ν_j^i 1 + λ_j^i = 0 and then gives λ_j^i = w_j^i − ν_j^i 1, which makes the stationarity equation reduce to 2w_j^i = 0. Appendix F uses w_j^i − ν_j^i 1 − λ_j^i = 0. Please reconcile the signs and the multiplier expressions.
  2. [Example C.4] In the verification expansion, the last term is written as "1/4 x12 x2_21 ·16"; it should be (1/4) x21^2 · 16. The earlier monomial list correctly includes x21^2.
  3. [§G.4, proof of Theorem 6.3(i)] The proof introduces d = max{...}+1 and then says the tuple is feasible for the degree-d0 program; it should say degree d. Also, F(µ−µ*) and F(µ, µ*) are used interchangeably; please standardize the notation.
  4. [§G.3, proof of Theorem 5.1(iii)] The text writes S_i,rm, which should be S_i,vr (the vertex-restricted set).

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central convergence theorems are derived from external polynomial-optimization results; the only self-citation is auxiliary and not load-bearing.

full rationale

I walked the derivation chain from IREFGs to polynomial games (Theorem 3.1, credited to folklore/[56]) through the Lasserre/Moment-SOS machinery (Putinar, flat extension, [52]'s SVC method). The paper contains no fitted parameters renamed as predictions and no quantity defined in terms of the result it is used to prove. The exactness claims in Theorem 4.1(i) and (iii) come from standard Archimedean quadratic-module convergence and a rank-stabilization/flatness argument over the vertex-restricted set, not from an assumed conclusion. The first-level exactness in Theorem 6.3(ii) is built on an SOS-matrix Taylor certificate via [43, Thm. 3.9], an external theorem. The only author-overlapping citation is [47], which supplies terminology and hardness facts concerning SOS-concavity/monotonicity, but does not carry the convergence proofs; that citation is not load-bearing. The main genuine weakness is the transfer of [52, Thm. A.1] to fixed simplex constraints in Section 3: the paper asserts that LICQ is 'the only property required' and that genericity is used 'only to imply LICQ,' without proving that transfer. That is a correctness risk for the 'almost all games converge finitely' claims (Theorems 4.1(ii), 5.1(ii)), but it is not circular: [52] is external work and the transfer is an independent mathematical assertion, not an input that has been rebuilt as an output. Accordingly, no circular step is established by the quoted evidence, and the score is 1 rather than 0 only to reflect the minor, non-load-bearing self-citation and the unsupported-but-not-circular transfer assertion.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard SOS/Lasserre theorems and on domain assumptions about genericity and non-absentmindedness. No free parameters are fitted. The only invented notions are the new game classes (SOS-concave/monotone), which are properties, not entities.

assumptions (5)
  • standard math Putinar's Positivstellensatz and Lasserre's asymptotic convergence theorem for Archimedean quadratic modules.
    Used to prove asymptotic convergence in Theorem 4.1(i) and 5.1(i) (Section E).
  • standard math Flat extension / Curto-Fialkow theorem: rank-stabilized truncated moment sequences have atomic representing measures.
    Used to extract optima and in Theorem 4.1(iii) proof.
  • domain assumption [52, Theorem A.1]: for generic polynomial games the KKT equations have finitely many complex solutions, implying finite convergence.
    The paper extends this to simplices by asserting LICQ replaces genericity; the transfer is not proved (Section 3).
  • domain assumption Genericity of utility coefficients: for almost all payoff assignments, the utility polynomial is generic in coefficient space.
    Underpins Theorems 4.1(ii) and 5.1(ii); the set of achievable polynomial coefficients from IREFGs is assumed full-dimensional.
  • domain assumption Non-absentmindedness: each infoset is visited at most once on any history, making the utility multi-affine in behavioral blocks (Proposition 3.2).
    Defines the NAM subclass; used for vertex-restricted hierarchy and Theorem 4.1(iii).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Solving Imperfect-Recall Games via Sum-of-Squares Optimization." pith.science (2026). https://pith.science/paper/Z2BT67UF

@misc{pith2026260221722,
  author       = {Pith},
  title        = {Pith review of: Solving Imperfect-Recall Games via Sum-of-Squares Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z2BT67UF}},
  note         = {Machine review of arXiv:2602.21722}
}
read the original abstract

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).

Figures

Figures reproduced from arXiv: 2602.21722 by the authors.

Figure 1
Figure 1. (a) A two-player zero-sum IREFG with no NE; (b) the single-player absentminded taxi driver [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Constructed Single-Player Imperfect-Recall Game for [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

87 extracted references · 3 linked inside Pith

  1. [52]

    Nash equilibrium problems of polynomials.Mathematics of Operations Research, 49(2):1065–1090, 2024

    Jiawang Nie and Xindong Tang. Nash equilibrium problems of polynomials.Mathematics of Operations Research, 49(2):1065–1090, 2024

    2024

  2. [1]

    cuhallar: A gpu accelerated low-rank augmented lagrangian method for large-scale semidefinite programming.arXiv preprint arXiv:2505.13719, 2025

    Jacob M Aguirre, Diego Cifuentes, Vincent Guigues, Renato DC Monteiro, Victor Hugo Nasci- mento, and Arnesh Sujanani. cuhallar: A gpu accelerated low-rank augmented lagrangian method for large-scale semidefinite programming.arXiv preprint arXiv:2505.13719, 2025

    arXiv 2025

  3. [2]

    DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization.SIAM Journal on Applied Algebra and Geometry, 3(2):193–230, 2019

    Amir Ali Ahmadi and Anirudha Majumdar. DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization.SIAM Journal on Applied Algebra and Geometry, 3(2):193–230, 2019

    2019

  4. [3]

    NP-hardness of deciding convexity of quartic polynomials and related problems.Mathematical programming, 137(1):453–476, 2013

    Amir Ali Ahmadi, Alex Olshevsky, Pablo A Parrilo, and John N Tsitsiklis. NP-hardness of deciding convexity of quartic polynomials and related problems.Mathematical programming, 137(1):453–476, 2013

    2013

  5. [4]

    A convex polynomial that is not sos-convex.Mathematical Programming, 135(1):275–292, 2012

    Amir Ali Ahmadi and Pablo A Parrilo. A convex polynomial that is not sos-convex.Mathematical Programming, 135(1):275–292, 2012

    2012

  6. [5]

    On the complexity of finding a local minimizer of a quadratic function over a polytope.Mathematical Programming, 195(1):783–792, 2022

    Amir Ali Ahmadi and Jeffrey Zhang. On the complexity of finding a local minimizer of a quadratic function over a polytope.Mathematical Programming, 195(1):783–792, 2022

    2022

  7. [6]

    Doubly optimal no-regret online learning in strongly monotone games with bandit feedback.Operations Research, 2025

    Wenjia Ba, Tianyi Lin, Jiawei Zhang, and Zhengyuan Zhou. Doubly optimal no-regret online learning in strongly monotone games with bandit feedback.Operations Research, 2025

    2025

  8. [7]

    Sum-of-squares relaxations for polynomial min–max problems over simple sets

    Francis Bach. Sum-of-squares relaxations for polynomial min–max problems over simple sets. Mathematical Programming, 209(1):475–501, 2025

    2025

Show all 87 references
  1. [8]

    Human-level play in the game of diplomacy by combining language models with strategic reasoning.Science, 378(6624):1067–1074, 2022

    Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning.Science, 378(6624):1067–1074, 2022

    2022

  2. [9]

    Computing maxmin strate- gies in extensive-form zero-sum games with imperfect recall.arXiv preprint arXiv:1608.01510, 2016

    Branislav Bosansky, Jiri Cermak, Karel Horak, and Michal Pechoucek. Computing maxmin strate- gies in extensive-form zero-sum games with imperfect recall.arXiv preprint arXiv:1608.01510, 2016

    2016 arXiv

  3. [10]

    Heads-up limit hold’em poker is solved.Science, 347(6218):145–149, 2015

    Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold’em poker is solved.Science, 347(6218):145–149, 2015. 13 Solving Imperfect-Recall Games via Sum-of-Squares Optimization

    2015

  4. [11]

    Hierarchical abstraction, distributed equilibrium computation, and post-processing, with application to a champion no-limit Texas hold’em agent

    Noam Brown, Sam Ganzfried, and Tuomas Sandholm. Hierarchical abstraction, distributed equilibrium computation, and post-processing, with application to a champion no-limit Texas hold’em agent. InAAAI Workshop: Computer Poker and Imperfect Information, volume 15, page 07, 2015

    2015

  5. [12]

    Superhuman ai for heads-up no-limit poker: Libratus beats top professionals.Science, 359(6374):418–424, 2018

    Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals.Science, 359(6374):418–424, 2018

    2018

  6. [13]

    Doubly optimal no-regret learning in monotone games

    Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. In International Conference on Machine Learning, pages 3507–3524. PMLR, 2023

    2023

  7. [14]

    Computational results for extensive-form adversarial team games

    Andrea Celli and Nicola Gatti. Computational results for extensive-form adversarial team games. InProceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018

    2018

  8. [15]

    PhD thesis, Czech Technical University, 2018

    Jiˇrí ˇCermák.Solving Extensive-Form Games Using Imperfect Recall Abstraction. PhD thesis, Czech Technical University, 2018

    2018

  9. [16]

    Approximat- ing maxmin strategies in imperfect recall games using a-loss recall property.International Journal of Approximate Reasoning, 93:290–326, 2018

    Jiˇrí ˇCermák, Branislav Bošansk`y, Karel Horák, Viliam Lis`y, and Michal Pˇechouˇcek. Approximat- ing maxmin strategies in imperfect recall games using a-loss recall property.International Journal of Approximate Reasoning, 93:290–326, 2018

    2018

  10. [17]

    An algorithm for constructing and solving im- perfect recall abstractions of large extensive-form games

    Jiˇrí ˇCermák, Branislav Bošansky, and Viliam Lisy. An algorithm for constructing and solving im- perfect recall abstractions of large extensive-form games. InProceedings of the 26th International Joint Conference on Artificial Intelligence, pages 936–942, 2017

    2017

  11. [18]

    Combining incremental strategy gener- ation and branch and bound search for computing maxmin strategies in imperfect recall games

    Jiˇri ˇCermák, Branislav Bošansk`y, and Michal Pˇechouˇcek. Combining incremental strategy gener- ation and branch and bound search for computing maxmin strategies in imperfect recall games. InProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, page...

    2017

  12. [19]

    Designing preferences, beliefs, and identities for artificial intelligence

    Vincent Conitzer. Designing preferences, beliefs, and identities for artificial intelligence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9755–9759, 2019

    2019

  13. [20]

    Foundations of cooperative AI

    Vincent Conitzer and Caspar Oesterheld. Foundations of cooperative AI. InProceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15359–15367, 2023

    2023

  14. [21]

    The truncated complex k-moment problem.Transactions of the American Mathematical Society, 352(6):2825–2855, 2000

    Raúl Curto and Lawrence Fialkow. The truncated complex k-moment problem.Transactions of the American Mathematical Society, 352(6):2825–2855, 2000

    2000

  15. [22]

    American Mathematical Soc., 1996

    Raúl E Curto and Lawrence A Fialkow.Solution of the truncated complex moment problem for flat data, volume 568. American Mathematical Soc., 1996

    1996

  16. [23]

    Polynomial games.Contributions to the Theory of Games I, 24:161–180, 1950

    Melvin Dresher, Samuel Karlin, and Lloyd S Shapley. Polynomial games.Contributions to the Theory of Games I, 24:161–180, 1950

    1950

  17. [24]

    MIT press, 1991

    Drew Fudenberg and Jean Tirole.Game theory. MIT press, 1991

    1991

  18. [25]

    Potential-aware imperfect-recall abstraction with earth mover’s distance in imperfect-information games

    Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-recall abstraction with earth mover’s distance in imperfect-information games. InProceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014

    2014

  19. [26]

    Srivathsan

    Hugo Gimbert, Soumyajit Paul, and B. Srivathsan. A bridge between polynomial optimization and games with imperfect recall. InAAMAS ’20, page 456–464. International Foundation for Autonomous Agents and Multiagent Systems, 2020

    2020

  20. [27]

    Srivathsan

    Hugo Gimbert, Soumyajit Paul, and B. Srivathsan. Simplifying imperfect recall games. InAAMAS ’25, page 895–903. International Foundation for Autonomous Agents and Multiagent Systems, 2025. 14 Solving Imperfect-Recall Games via Sum-of-Squares Optimization

    2025

  21. [28]

    A low-rank ADMM splitting approach for semidefinite programming.INFORMS Journal on Computing, 2025

    Qiushi Han, Chenxi Li, Zhenwei Lin, Caihua Chen, Qi Deng, Dongdong Ge, Huikang Liu, and Yinyu Ye. A low-rank ADMM splitting approach for semidefinite programming.INFORMS Journal on Computing, 2025

    2025

  22. [29]

    Accelerating low-rank factorization-based semidefinite programming algorithms on gpu.arXiv preprint arXiv:2407.15049, 2024

    Qiushi Han, Zhenwei Lin, Hanwen Liu, Caihua Chen, Qi Deng, Dongdong Ge, and Yinyu Ye. Accelerating low-rank factorization-based semidefinite programming algorithms on gpu.arXiv preprint arXiv:2407.15049, 2024

    2024 arXiv

  23. [30]

    Semidefinite representation of convex sets.Mathematical Programming, 122(1):21–64, 2010

    J William Helton and Jiawang Nie. Semidefinite representation of convex sets.Mathematical Programming, 122(1):21–64, 2010

    2010

  24. [31]

    Detecting global optimality and extracting solutions in GloptiPoly

    Didier Henrion and Jean-Bernard Lasserre. Detecting global optimality and extracting solutions in GloptiPoly. InPositive Polynomials in Control, pages 293–310. Springer, 2005

    2005

  25. [32]

    Behavior strategies, mixed strategies and perfect recall

    Mamoru Kaneko and J Jude Kline. Behavior strategies, mixed strategies and perfect recall. International Journal of Game Theory, 24:127–145, 1995

    1995

  26. [33]

    Minimum memory for equivalence between ex ante optimality and time-consistency

    J Jude Kline. Minimum memory for equivalence between ex ante optimality and time-consistency. Games and Economic Behavior, 38(2):278–305, 2002

    2002

  27. [34]

    The complexity of two-person zero-sum games in extensive form.Games and Economic behavior, 4(4):528–552, 1992

    Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in extensive form.Games and Economic behavior, 4(4):528–552, 1992

    1992

  28. [35]

    Imperfect-recall abstractions with bounds in games

    Christian Kroer and Tuomas Sandholm. Imperfect-recall abstractions with bounds in games. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 459–476, 2016

    2016

  29. [36]

    Extensive games and the problem of information.Contributions to the Theory of Games, 2(28):193–216, 1953

    Harold W Kuhn. Extensive games and the problem of information.Contributions to the Theory of Games, 2(28):193–216, 1953

    1953

  30. [37]

    On equilibria in games with imperfect recall.Games and Economic Behavior, 113:164–185, 2019

    Nicolas S Lambert, Adrian Marple, and Yoav Shoham. On equilibria in games with imperfect recall.Games and Economic Behavior, 113:164–185, 2019

    2019

  31. [38]

    No-regret learning in extensive-form games with imperfect recall

    Marc Lanctot, Richard Gibson, Neil Burch, Martin Zinkevich, and Michael Bowling. No-regret learning in extensive-form games with imperfect recall. InProceedings of the 29th International Coference on International Conference on Machine Learning, pages 1035–1042, 2012

    2012

  32. [39]

    Semidefinite programming for min–max problems and games.Mathematical Programming, 131(1):305–332, 2012

    Rida Laraki and Jean Bernard Lasserre. Semidefinite programming for min–max problems and games.Mathematical Programming, 131(1):305–332, 2012

    2012

  33. [40]

    Global optimization with polynomials and the problem of moments.SIAM Journal on Optimization, 11(3):796–817, 2001

    Jean Bernard Lasserre. Global optimization with polynomials and the problem of moments.SIAM Journal on Optimization, 11(3):796–817, 2001

    2001

  34. [41]

    Convexity in semialgebraic geometry and polynomial optimization.SIAM Journal on Optimization, 19(4):1995–2014, 2009

    Jean Bernard Lasserre. Convexity in semialgebraic geometry and polynomial optimization.SIAM Journal on Optimization, 19(4):1995–2014, 2009

    1995

  35. [42]

    World Scientific, 2009

    Jean Bernard Lasserre.Moments, positive polynomials and their applications, volume 1. World Scientific, 2009

    2009

  36. [43]

    The Moment-SOS hierarchy: Applications and related topics.Acta Numerica, 33:841–908, 2024

    Jean Bernard Lasserre. The Moment-SOS hierarchy: Applications and related topics.Acta Numerica, 33:841–908, 2024

    2024

  37. [44]

    Semidefinite characterization and computation of zero-dimensional real radical ideals.Foundations of Computational Mathematics, 8(5):607–647, 2008

    Jean Bernard Lasserre, Monique Laurent, and Philipp Rostalski. Semidefinite characterization and computation of zero-dimensional real radical ideals.Foundations of Computational Mathematics, 8(5):607–647, 2008

    2008

  38. [45]

    Sums of squares, moment matrices and optimization over polynomials

    Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry, pages 157–270. Springer, 2008

    2008

  39. [46]

    Sum-of-squares optimization in Julia

    Benoît Legat, Chris Coey, Robin Deits, Joey Huchette, and Amelia Perry. Sum-of-squares optimization in Julia. InThe First Annual JuMP-dev Workshop, 2017. 15 Solving Imperfect-Recall Games via Sum-of-Squares Optimization

    2017

  40. [47]

    Certifying concavity and monotonicity in games via sum-of-squares hierarchies.Advances in Neural Information Processing Systems, 38, 2025

    Vincent Leon, Iosif Sakos, Ryann Sim, and Antonios Varvitsiotis. Certifying concavity and monotonicity in games via sum-of-squares hierarchies.Advances in Neural Information Processing Systems, 38, 2025

    2025

  41. [48]

    A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach

    Renato DC Monteiro, Arnesh Sujanani, and Diego Cifuentes. A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach. arXiv preprint arXiv:2401.12490, 2024

    2024 arXiv

  42. [49]

    Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.Science, 356(6337):508–513, 2017

    Matej Moravˇcík, Martin Schmid, Neil Burch, Viliam Lis `y, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.Science, 356(6337):508–513, 2017

    2017

  43. [50]

    Maxima for graphs and a new proof of a theorem of turán.Canadian Journal of Mathematics, 17:533–540, 1965

    Theodore S Motzkin and Ernst G Straus. Maxima for graphs and a new proof of a theorem of turán.Canadian Journal of Mathematics, 17:533–540, 1965

    1965

  44. [51]

    Convex generalized Nash equilibrium problems and polynomial optimization.Mathematical Programming, 198(2):1485–1518, 2023

    Jiawang Nie and Xindong Tang. Convex generalized Nash equilibrium problems and polynomial optimization.Mathematical Programming, 198(2):1485–1518, 2023

    2023

  45. [53]

    MIT press, 1994

    Martin J Osborne and Ariel Rubinstein.A course in game theory. MIT press, 1994

    1994

  46. [54]

    California Institute of Technology, 2000

    Pablo A Parrilo.Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000

    2000

  47. [55]

    Polynomial games and sum of squares optimization

    Pablo A Parrilo. Polynomial games and sum of squares optimization. InProceedings of the 45th IEEE Conference on Decision and Control, pages 2855–2860. IEEE, 2006

    2006

  48. [56]

    On the interpretation of decision problems with imperfect recall.Games and Economic Behavior, 20(1):3–24, 1997

    Michele Piccione and Ariel Rubinstein. On the interpretation of decision problems with imperfect recall.Games and Economic Behavior, 20(1):3–24, 1997

    1997

  49. [57]

    Positive polynomials on compact semi-algebraic sets.Indiana University Mathe- matics Journal, 42(3):969–984, 1993

    Mihai Putinar. Positive polynomials on compact semi-algebraic sets.Indiana University Mathe- matics Journal, 42(3):969–984, 1993

    1993

  50. [58]

    Springer, 1998

    R Tyrrell Rockafellar and Roger JB Wets.Variational Analysis. Springer, 1998

    1998

  51. [59]

    Existence and uniqueness of equilibrium points for concave n-person games

    J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pages 520–534, 1965

    1965

  52. [60]

    Separable and low-rank continuous games

    Noah D Stein, Asuman Ozdaglar, and Pablo A Parrilo. Separable and low-rank continuous games. International Journal of Game Theory, 37(4):475–504, 2008

    2008

  53. [61]

    The computa- tional complexity of single-player imperfect-recall games

    Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, and Paul W Goldberg. The computa- tional complexity of single-player imperfect-recall games. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2878–2887, 2023

    2023

  54. [62]

    Imperfect-recall games: Equilibrium concepts and their complexity

    Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sandholm, Paul Goldberg, and Vincent Conitzer. Imperfect-recall games: Equilibrium concepts and their complexity. InProceedings of the Thirty-Third International Joint Conference on Artificial Intel...

    2024

  55. [63]

    Team-maxmin equilibria.Games and Economic Behavior, 21(1-2):309–321, 1997

    Bernhard V on Stengel and Daphne Koller. Team-maxmin equilibria.Games and Economic Behavior, 21(1-2):309–321, 1997

    1997

  56. [64]

    Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations

    Martin J Wainwright and Michael I Jordan. Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations. Technical report, Technical Report 671, University of California, Berkeley, 2004

    2004

  57. [65]

    A practical use of imperfect recall

    Kevin Waugh, Martin Zinkevich, Michael Johanson, Morgan Kan, David Schnizlein, and Michael H Bowling. A practical use of imperfect recall. InSARA, 2009. 16 Solving Imperfect-Recall Games via Sum-of-Squares Optimization

    2009

  58. [66]

    Polynomial and moment optimization in Julia and JuMP

    Tillmann Weisser, Benoît Legat, Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. Polynomial and moment optimization in Julia and JuMP. InJuliaCon, 2019

    2019

  59. [67]

    Existence of Nash equilibria in finite extensive form games with imperfect recall: A counterexample.Games and Economic Behavior, 63(1):366–369, 2008

    Philipp C Wichardt. Existence of Nash equilibria in finite extensive form games with imperfect recall: A counterexample.Games and Economic Behavior, 63(1):366–369, 2008

    2008

  60. [68]

    Subgame solving in adversarial team games.Advances in Neural Information Processing Systems, 35:26686–26697, 2022

    Brian Zhang, Luca Carminati, Federico Cacciamani, Gabriele Farina, Pierriccardo Olivieri, Nicola Gatti, and Tuomas Sandholm. Subgame solving in adversarial team games.Advances in Neural Information Processing Systems, 35:26686–26697, 2022

    2022

  61. [69]

    Team belief DAG: generalizing the sequence form to team games for fast computation of correlated team max-min equilibria via regret minimization

    Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief DAG: generalizing the sequence form to team games for fast computation of correlated team max-min equilibria via regret minimization. InInternational Conference on Machine Learning, pages 40996–41018. PMLR, 2023

    2023

  62. [70]

    team vs. nature

    Brian Hu Zhang and Tuomas Sandholm. Team correlated equilibria in zero-sum extensive-form games via tree decompositions. InProceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5252–5259, 2022. 17 Solving Imperfect-Recall Games via Sum-of-Squares Opti...

    2022

  63. [71]

    Subsequently, [62] extended this result to a set of polynomials, and multi-player IREFGs

    also recently established that any polynomial can be transformed into a single-player IREFG. Subsequently, [62] extended this result to a set of polynomials, and multi-player IREFGs. We report the single-player variant of the theorem below, and provide a concrete example to ai...

  64. [72]

    With this convention, supp(p) = D(0) =0, D (1) = (1,0,1,0), D (2) = (0,1,0,1), D (3) = (0,0,2,0) so|supp(p)|= 4and the lexicographic order isD (0) ≺D (1) ≺D (2) ≺D (3)

    For each D, order the multiset supp(D)ms by listing the pairs(j, a)in lexicographic order with multiplicity. With this convention, supp(p) = D(0) =0, D (1) = (1,0,1,0), D (2) = (0,1,0,1), D (3) = (0,0,2,0) so|supp(p)|= 4and the lexicographic order isD (0) ≺D (1) ≺D (2) ≺D (3)....

  65. [73]

    NP-hardness and conditional inapproximability hold even if the game has no chance nodes, a tree depth of 2, and a single information set

    Unless P=N P , no FPTAS exists. NP-hardness and conditional inapproximability hold even if the game has no chance nodes, a tree depth of 2, and a single information set

  66. [74]

    NP-hardness and conditional inapproximability hold even if the game has a tree depth of 3 and a single information set

    Unless N P=ZP P, no FPTAS exists. NP-hardness and conditional inapproximability hold even if the game has a tree depth of 3 and a single information set

  67. [75]

    NP-hardness holds even without absentmindedness, with tree depth 4 and two actions per information set

  68. [76]

    virtual laws

    NP-hardness holds even without absentmindedness, with tree depth 3 and three actions per information set. Proof. To prove statement 1, we note that since any global optimum is in particular a local optimum, finding a global maximum must be at least as hard as finding a local o...

  69. [77]

    Solve the order-dmoment SDP; obtain optimaly d and upper boundu mom d =L yd(u)

  70. [78]

    , d, test the rank condition in Equation (34)

    For s=d 0, . . . , d, test the rank condition in Equation (34). If it holds for some s,terminate: the relaxation is exact and one can extract the global maximizers fromM s(yd)using Algorithm 1

  71. [79]

    no profitable deviation by i

    Otherwise, increase the relaxation order:d←d+ 1and go back to Step 1. For single-player NAM-IREFGs, Lemma G.1 shows that rankM s(y) = rankM ℓ(y)∀s > ℓ, and Statement (iii) of Theorem 4.1 gives exactness at degree ℓ+1: umom,vr ℓ+1 =u sos,vr ℓ+1 =u ∗. Hence the flatness test in ...

  72. [80]

    = (1,0) and (x∗ 21, x∗

  73. [81]

    This gives objective value p(x∗) = 9

    = (1,0) . This gives objective value p(x∗) = 9. The compute time required to solve this example was 0.02 seconds. 36 Solving Imperfect-Recall Games via Sum-of-Squares Optimization Randomly Generated NAM-IREFG.We also create a procedure to randomly generate single-player IREFGs...

  74. [82]

    = (0,1) , and (z∗ 1, z∗

  75. [83]

    The compute time required to solve this game was 0.06 seconds

    = (0,1) with optimal value 1. The compute time required to solve this game was 0.06 seconds. Randomly Generated Absentminded IREFG.As another example, we show that in a randomly generated absentminded game, the hierarchies empirically converge at ‘reasonable’ levels. Consider ...

  76. [84]

    = (0.5,0,0.5) and (y∗ 1, y∗ 2, y∗

  77. [85]

    Notice that unlike the NAM case, the optimal solution is not a vertex

    = (0.134,0.594,0.272) , giving optimal value 1. Notice that unlike the NAM case, the optimal solution is not a vertex. The total compute time required to solve this example was 0.41 seconds. SOS-Monotone Example.We show experimental corroboration for Statement (ii) of Theorem ...

  78. [86]

    = (0,1) and (y∗ 1, y∗

  79. [87]

    The compute time was<0.001seconds

    = (0,1) , with value 19.9. The compute time was<0.001seconds. 37

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.