Research map / Learning theory and algorithms / Submodular and game algorithms

Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies

NeurIPS 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Correlated equilibria in sequential games · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows certifying concavity/monotonicity of polynomial games over semialgebraic strategy sets is NP-hard and proposes polynomial-time-per-level SOS hierarchies (SDPs) that certify these properties, with almost all games certified at a finite level.

Problem

Efficiently verifying whether a continuous game is concave or monotone (which guarantee Nash existence, uniqueness and convergence), given polynomial utilities over compact convex basic semialgebraic strategy sets.

Approach

Certify concavity via SOS decompositions of the negative Hessian quadratic form and monotonicity via SOS decompositions of the negative symmetrized Jacobian quadratic form over the domain of strategies times the unit ball; define l-SOS-concave/monotone game classes that are dense in the concave/monotone classes and compute the closest such game via a single SDP.

Key results

• Deciding concavity or monotonicity of polynomial games over compact convex basic semialgebraic sets is strongly NP-hard already for polynomials of degree at least 3 in a player's own action.
• For almost all monotone polynomial games (zero-measure exception set), monotonicity is certified at some finite SOS hierarchy level.
• The closest l-SOS-monotone game to a given polynomial game can be computed by a single SDP.

Surprising findings

• Certifying concavity or monotonicity is strongly NP-hard even though the games are polynomial with compact convex semialgebraic strategy sets.

Limitations

• Size of the SDPs grows with hierarchy level, and the level needed for an arbitrary game may be large.
• Results focus on monotone games; concavity results are stated with modifications.

Experimental setup

Metrics: maximum symmetrized Jacobian eigenvalue bound

Builds on: Putinar Positivstellensatz Rosen's monotone games

Closest papers by meaning

• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
• Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.88)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.88)
• Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.87)
• The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.87)
• On Tractable $\Phi$-Equilibria in Non-Concave Games (NeurIPS 2024 · similarity 0.87)