Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
Authors: Vincent Leon
Iosif Sakos
Ryann Sim
Antonios Varvitsiotis
Venue: NeurIPS 2025 poster ()
Keywords: concave games
monotone games
sum of squares
verifying convexity
Primary area: theory
TL;DR: We introduce SOS-concave and SOS-monotone games, which are subclasses of concave/monotone games that are verifiable via semidefinite programming.

Abstract: Concavity and its refinements underpin tractability in multiplayer games, where players independently choose actions to maximize their own payoffs which depend on other players’ actions. In *concave* games, where players' strategy sets are compact and convex, and their payoffs are concave in their own actions, strong guarantees follow: Nash equilibria always exist and decentralized algorithms converge to equilibria. If the game is furthermore *monotone*, an even stronger guarantee holds: Nash equilibria are unique under strictness assumptions. Unfortunately, we show that *certifying* concavity or monotonicity is NP-hard, already for games where utilities are multivariate polynomials and compact, convex basic semialgebraic strategy sets—an expressive class that captures extensive-form games with imperfect recall. On the positive side, we develop two hierarchies of sum-of-squares programs that certify concavity and monotonicity of a given game, and each level of the hierarchies can be solved in polynomial time. We show that almost all concave/monotone games are certified at some finite level of the hierarchies. Subsequently, we introduce the classes of SOS-concave/monotone games, which globally approximate concave/monotone games, and show that for any given game we can compute the closest SOS-concave/monotone game in polynomial time. Finally, we apply our techniques to canonical examples of extensive-form games with imperfect recall.

Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
Vincent Leon'
Iosif Sakos²
Ryann Sim?
Antonios Varvitsiotis 2,3,4
UIUC
SUTD
NUS CQT 4 *Archimedes/Athena RC
Leon18@illinois
fiosif _akos, ryann_ sim, [esonios]ssuteee edu.
Abstract
Concavity and its refinements underpin tractability in multiplayer games, where players independently choose actions to maximize their own payoff's which de- pend on other players' actions. In concave games, where players' strategy sets are compact and convex, and their payoffss are concave in their own actions, strong guarantees follow: Nash equilibria always exist and decentralized algorithms con- verge to equilibria. If the game is furthermore monotone, an even stronger guar- antee holds: Nash equilibria are unique under strictness assumptions. Unfortu- nately, we show that certifying concavity or monotonicity is NP-hard, already for games where utilities are multivariate polynomials and compact, convex ba- sic semialgebraic strategy sets-an expressive class that captures extensive-form games with imperfect recall. On the positive side, develop two hierarchies sum-of-squares programs that certify concavity and monotonicity of a given game, and each level of the hierarchics show that almost all concave/monotone games are certified at some finite level the hierarchies. Subsequently, we introduce the classes of COS-concave/monotona games, which globally approximate concave/monotone games, and show that for any given game
be solved in polynomial time. We
compute the closest cOS-concave/monotonr game in poly- nomial time. Finally, we apply our techniques to canonical examples of extensive- form games with imperfect recall.
1 Introduction
Game theory models settings where multiple decksss independently maximize personal objectives that depend on the actions of others. Formally, game with n players modeled by assigning to each player a strategy set X; C R. and utility function u, (ar,, x--), where E X; player i's action and x=; denotes the actions of all other players. The interdependence of players' utilities makes analyzing the collective behavior of such systems both rich and challenging.
The canonical solution concept in game theory is the Nash equilibrium 42]. product distribu- tion over strategies in which no player can unilaterally deviate to improve their utility, given the strategies of the other players. While Nash equilibria are guaranteed to exist in finite normal-form games, several key questions must be addressed in games with continuous, infinite action spaces: Do Nash equilibria always exist? If one exists, is it unique (thereby avoiding the equilibrium selection problem)? And crucially, can it be computed efficiently using distributed algorithms?
Extensive research has identified concavity, and its refinements, key enablers in addressing these fundamental questions. the setting games, this entails assuming that each strategy set X; is compact and convex. Furthermore, concavity of players' utilities manifest in at least two
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

distinct forms. First, we have the class of concave games, where for each player i, the function I, - u, x-4) is continuous and concave for every fixed r-,,. Second, we have the more restric- tive class of monotone games, where utility functions are smooth and the (negative) concatenated gradient map
Un (
is a monotone operator. Every monotone game is concave, but the converse does not necessarily hold. Concave and monotone games were first studied in the seminal work of Rosen [49], who established that Nash equilibria always exist in these class of games, significantly extending the guarantees of classical results such as von Neumann's 's minimax theorem [62] for two-player zero- sum (normal-form) games, Nash's 's aforementioned result for finite normal-form games, and Sion's minimax theorem for two-player convex-concave games [K] Moreover, Rosen showed that strictly monotone games have a unigue Nash equilibrium. At the same time, concave/monotone games have been extensively studied due to their inherent expressibility they have been used to model various fundamental settings in economics and optimization, including but not limited to resource allocation (50, Cournot competition
and robust power management 66
Finally, concave and monotone games have also received considerable attention in the context of equilibrium computation. A substantial body of work has analyzed decentralized dynamics that achieve strong performance guarantees in concave games [17 56 28 57 Most recently, (20] estab- lished a (polylog I') regret bound for uncoupled learning dynamics in general convex games, ex- tending classical results beyond structured settings such as normal-form and extensive-form games. In monotone games, decentralized dynamics have also been shown to converge in the last-iterate sense to Nash equilibria [38] 8 9 [8]. Moreover, in strictly monotone games, one can guaran- tee last-iterate convergence the unique Nash equilibrium [67 7 ST 54] further underscoring the computational tractability of this class.
However, despite their favorable properties, it is not clear how to efficiently verify concavity and monotonicity. For instance, establishing that u, is concave over X; requires checking that the Hes- sian V (=), is negative semidefinite for every x; X; and every x X_i, an infinite family of conditions. In view of this, a fundamental computational challenge arises:
Is possible to efficiently verify that a game is concave or monotone?
Our Techniques and Contributions. Our starting point is to demonstrate that deciding whether game is concave or monotone is computationally hard, cf. Theorem 3.1 We establish this hardness result for the class of polynomial games [14 30 45 in which each player's 's utility is multivariate polynomial and players' strategy sets are compact convex basic semialgebraic sets that is, sets defined by polynomial equality and inequality constraints. This class is highly expressive, captur- ing for instance extensive-form games with imperfect recall [46]. Our hardness result builds on recent advances in polynomial optimization 4 2, which show that unless P = NP, there is no algorithm that can decide whether a multivari-
polynomial-time (or even pseudo-polynomial-time ate polynomial of degree four (or any higher even degree) is globally convex. This result presents a challenge for game theorists. On one hand, concave/monotone games are expressive classes of games that capture many applications and have desirable equilibriation properties. However, veri- fying their concavity/monolooiiiy is hard for the class of polynomial games over convex compact basic semialgebraic sets.
Motivated by this, we next seek to identify tractable sufficient conditions for concavity and mono- tonicity, well special classes of games for which these properties can be efficiently certified. Our approach is based on the observation that, since polynomial games are smooth, these prop- erties can be verified via the positive semidefiniteness of the Hessian and the symmetrized Jaco- bian, respectively. As a concrete example, a polynomial game is concave if, for each player i, the (negative) Hessian of the utility function is positive semidefinite for all x; E X; and x-; E X- By the variational characterization of positive semidefiniteness, this is equivalent to requiring that pi(2, y) == -y V2 u,,,, x x> 2 0, for all E x and y E B, where B _g is the unit ball. Since u, is polynomial and X' is closed basic semialgebraic set, the function pa(x, y) is polynomial over a semialgebraic domain.
Although testing nonnegativity of polynomials is, in general, computationally hard 41 powerful approach from polynomial optimization, pioneered in 45 35), is seek a sum-of-xquares (SOS) decomposition that certifies nonnegativity. This idea has also been recently used to develop certifi-
2

---

cates for the global convexity of polynomials [5]. Searching for an SOS decomposition of bounded degree can be done in polynomial time via semidefinite programming.
In our setting, the application of the SOS framework leads to a hierarchy of increasingly stronger sufficient conditions for certifying concavity or monotonicity, each of which be checked in polynomial time via semidefinite programming. At the é-th level of the hierarchy, we check whether (z, y) admits a degree- SOS decomposition over X B. While the SOS framework does not eliminate the inherent hardness of the problem, it offers a practical trade-off: by relaxing the problem into sequence of SDPs, one obtains a hierarchy of increasingly tight sufficient conditions with provable convergence in the limit. The main limitation is that the size of the resulting SDPs grows with the level of the hierarchy.
Leveraging these ideas, our main contributions are summarized below:
We construct hierarchy of optimization problems that provide increasingly strong certifi- cates of monotonicity/coneavity for polynomial games over compact, convex basic semial- gebraic sets (cf. Theorem 3.2). Furthermore, each level of the hierarchy can be solved in polynomial time via semidefinite programming.
We show that for every strictly monotone/strictly concave game, a certificate is always found at finite level of the hierarchy (cf. Statement in Theorem 3.2). More importantly, we show that for almost all monotone/concave games, such a certificate can be obtained at some finite level of the hierarchy (cf. Theorem 3.3).
We define subclasses of monotone/concav polynomial games over compact, convex ba- sic semialgebraic sets, called monotonicity (resp. concavity) can be certified by the E-th level of the hicrarchy (cf. Defi- nition We show that this class of games globally approximates the class of monotone (resp. concave) games, and importantly, given any polynomial game, the closest E-SOS- monotone (resp. -S-n-ccceeeee) game can be computed by solving single SDP (cf. The- orem 4.3)
(resp. E-SOS-concave) games, for which
We apply our proposed methods to several canonical and new examples of extensive-form games with imperfect recall (cf. Section 6 We show examples of how our hierarchies can be used to verify monotonicity/concane in these games, as well as to find the closest -.SOS-monntone (resp.
game with respect an appropriate norm.
2 Preliminaries
2.1 Polynomial Games over Semialgebraie Sets
We consider an n-player continuous game denoted by & [[n], u). For each player E [n]] we denote their set of actions by X; C Rm and their payoff function by uy: X' > IR where x the set of joint actions X' def X1
x Xn is compact, convex set. Each player i selects an
action I; E X. We denote by x def (.i...., Fn) the joint action profile of all players, and by X del X1 X Xn C RT (uI....,u.) the ensemble of the players' payoff functions.
their joint action space, where m der mi +...+ mn. We also denote by
In this work, we focus games 9 where u1...., Un are polynomial functions, and X is a basic semialgebraic set. In particular, we assume that
g5(x) 2 0, j E [mgl=] hy(z)= 0, [mm]] S
X =
E Immi X x m
where 91..... Im,, hi,...,
hms E R(x].
We refer to d max (rxxdde((1); ... deg( (un), deg(g)), ... deg(gn (gm,)) deg(hh)) ... deg(ti (Nm,,) }} as the degree of the game. For each n, E N, we use ((m.d)) to denote the set of n-player, d-degree polynomial games over X.
G(n,) is isomorphic R where M del n (m+t)). In particular, we define the isomorphism
g
r vec(w))) Vg E ((nd))
(2)
3

---

where vec(u;) is the coefficient vector of for each i E [n]] Throughout the paper, we also consider the topology on (n,a) induced by the norm
| max (u) 1E m
When necessary, we use the convention v (z,, -i)) to distinguish the action of player i in joint action X' from the actions of the rest of the players. In a similar vein, we use X-; to denote the joint action space of all players except player i.
A fundamental equilibrium concept in game theory is the Nash equilibrium (NE) 42 strategy profiles from which players have no incentive to unilaterally deviate. Concretely, a joint action profile x² X is NE of game & if
which
ui(x*) 2 (TI,,,
Va, E X; i E
(4)
2.2 Sum-of-Squares Optimization
Given a closed basic semialgebraic set X as in ①T. the quadratic module Q(X) of X is set of functions defined as
(xx) def
00
ma
9j
m.
hyps
0o
Um E E[x]
(5)
Pl....
Pma E R[
j=1
==1
[x]]] is the of sun-of-squares (SOS) polynomials on variables x, i.e., the set of all polynomials of the form
where [(x]
K
(x))
(x),
Vo E RT
where
C...... 9K E R[x].
(6)
Furthermore, for all O, we define Qa(x)) as the restriction of Q(X) to Putinar-type decomposi- tions of degree most 2d given by deg(go),-. ...., )
deg(pm,) < 2d.
As part of the analysis Section 3.1
we require that the quadratic module Q(X) is Archimedean, property formally given for completeness in the following definition.
Definition 2.1. A quadratic module Q(*) is called Archimedean if there exists N E N such that
N
r E Q(X).
2.3 Concave Monotone Games
In this section, we introduce two important subclasses of continuous games, concave games and monotone games, both defined in [49]. These classes are partieularly significant due their impli- cations for the existence and uniqueness of Nash equilibria.
Definition 2.2 (Concave Games). game S concave if, for all players [n]], the function is concave for every fixed æ=; E X_,, Furthermore, if & is polynomial then it is concave if and only if the Hessian matrices of the payoff functions u1, Un with respect to ø1, Ens respectively, are negative semidefinite, i.e.,
T; +
H (x) def V2 (x) O,
V E [m]
Rosen 49 proved that a Nash equilibrium exists in every concave game, thereby extending Nash's equilibrium existence result to broad class of continuous games. He also identified important subclass of concave games with additional structural properties, which are now typically referred to as monotone games (38).
Definition 2.3 (Monotone Games). A game & is monotone if the negative of its concatenated gra- dient mapping, referred to by Rosen as the pseudogradient,
r (xx)
(VI u1 (x)...... VT uh (x:)
(9)

---

is a monotone operator on A' i.e.,
(o(z) - u(x),, x =)))
Va, x' E
(10)
Furthermore, y is polynomial, it is well-known that (cf. 48 Proposition 12.3]) it is monotone if and only if the symmetrized Jacobian matrix with respect to v(x) is negative semidefinite, i.e.,
! 2 (J(z)) = 0,
SJ
Vo E X,
(11)
where, for all X. (x) the Jacobian matrix of v(x) (see Appendix B for definition of (z)).
It is easy to verify that if game y is monotone, then it is also concave; however, the converse does hold. We now turn our attention the strict versions of these definitions.
Definition 2.4 (Strictly Concave/Monotone Games). Consider polynomial game y over a basic semialgebraic set X. Then, is strictly concave over
Hu, (a) x 0, Yo X, i [n]]
(12)
Furthermore, & is strictly monotone over X if SJ is negative definite on X, i.e.,
SJ(r) < O,
E X.
(13)
Finally, Rosen 49 also studied the class of diagonally strictly concave games, defined as those for which equality in (T)) holds and only if x =
Several important connections and inclusions between the aforementioned game classes study are summarized in Figure [ The proofs for these inclusions follow directly from the definitions of the games and standard results from 48 Of particular interest us is the fact that, if y is strictly monotone (i.e., it satisfies (I3)) then I is both diagonally strictly concave and strictly concave. Moreover, [49 also proved that diagonally strictly concave games admit unique Nash equilibrium.
Concave Games
Diagonally Strietly Concave
Strietly Monotone Games
Strietly Concave Games
Monotone Games
Games
Figure 1: Connections and inclusions among the game classes study,
3 Certifying Concavity and Monotonicity in Polynomial Games
As discussed in the introduction, concave and monotone games are highly expressive and have strong theoretical properties, including the existence of Nash equilibria, uniqueness under strictness conditions, and convergence of distributed dynamics to equilibrium. Given these favorable features, natural question arises: can concavity/monotonicity be efficiently certified? In this section, investigate this question in the setting of polynomial games with semialgebraic strategy sets.
To investigate hardness of deciding comcavity/monotonicity polynomial optimization, particularly recent works on the complexity of certifying convexity of polynomials. Specifically, it has been shown in [4] that deciding whether quartic (multivariate) polynomial is globally convex Na-hard. Subsequently, [2] demonstrated that determining whether cubic polynomial is convex over box is also ha-hard. Building these results, the starting point of this work is the observation that verifying whether a polynomial game belongs to the class of concave monotone games is also NP-hard. This result given below, and proven in Appendix C.1
leverage recent breakthroughs in
Theorem 3.1. Let E [[m] [m].2] X, u) be polynomial game over compact convex basic semialgebraic set. If for some player Wy a polynomial of degree least with respect to T4; Xs, verifying whether 3f is concave monotone is strongly NP-hard.
5

---

Motivated by the hardness result, it is crucial to identify tractable sufficient conditions for concavity and monotonicity, which gives rise non non-trivial subclasses of concave and monotone games. This can be achieved by using the technique of sum-of-sque
optimization, together with the positive semidefiniteness of the Hessian or the symmetrized Jacobian matrix of the game. Throughout the remainder of the paper, for brevity we focus only on the class of monotone games. Analogous results hold for concave games with minor modifications, and we describe them in Section
3.1 Sum-of-Squares Certificates for Concavity & Monotonicity
We introduce hierarchy of increasingly strong sufficient conditions for certifying concavity and monotonicity, based on SOS certificates for the associated quadratie forms defined by the Hessian and the symmetrized Jacobian matrices of y. The starting point for this observation is that, for any fixed z X, and considering the symmetrized Jacobian, we have
SJ(x) = 0 if and only if Consequently, using the Rayleigh Ritz theorem, it follows that & is monotone if and only if
Amax (SJ(z)) S 0.
(14)
Ritz
max Mmx (SJ(x)) max y SJ(z) xEX
(15)
aex
yEB
where def {y R v'v 1}. The crucial observation here is that the function y)
y (Jry polynomial in æ; y, since the Jacobian matrix SJ(x)) is polynomial in æ. Moreover, X and B compact basic semialgebraic sets. Therefore, max Amax (SJ(z) can be written as the solution to the following polynomial maximization problem:
max Amax (s)( maximize 2.
y SJJ(r)y
(16)
xEX
subject to
I ZE
Finally, although polynomial optimization is in general NP-hard, the solution a polynomial opti- mization problem, i.e., maxzex Amax (S)( can be approximated via the SOS framework. This is formally stated in the main theorem of this section, the proof of which is given Appendix C.2
Theorem 3.2. Let & [[n], X, u) be a polynomial game over a compact, convex basic semialgebraic set X. Assume the quadratic module Q(X)) is Archimedean. For any & E N consider the hierarchy of SOS optimization problems:
SOS,
dd minimize XER
(17)
subject to
X SJ((()) Qe(X' x B),
where Qe(X x B) denotes the restriction of Q(X B) to polynomials of degree at most f. Then, the following statements are true:
1) For all we have that SOS, ( 2 max Amar (z))
2) The sequence (SOS (
E2O is nonincreasing.
3) limz-4o SOS, = maxxex Amar (SJJ.(S (x))-
4) l is strictly monotone if, and only if. there exists some finite level such that SOS 0.
5) For any level é, the program in and solved in polynomial time.
17 can be formulated as an semidefinite program (SDP)
Theorem 3.2 shows how sequence of SDPs, which can be solved efficiently (Statement 5 can be used to approximate max Amax (z)())). and therefore certify whether 3 is monotone. In particular, Statements to guarantee that SSS) for 2 O, gives progressively tighter up- per bounds for max Amaa (SJ(x)). If for any finite we obtain SOS;(SJ) < 0, it follows that maxzex Ama (z)()) < 0, and therefore 3 is monotone. Additionally, if at some & we get (SJ) 0, it follows that max Amax (x)) 0. and therefore & is strictly monotone.

---

Importantly. Statement 3 guarantees that whenever H is monotone, even if no finite exists such that (SJ) I O, the sequence (SOS,(SJ)) t20 nonetheless converges (asymptotically) non-positive value. Moreover, whenever 3 is not only monotone but also strietly monotone, by 4
Statement we are guaranteed the existence of finite &. In fact, it turns out that generic monotone polynomial games over compact, convex semialgebraic sets are almost always strictly monotone. In particular, in the following theorem show that for all I of degree least 2, the set of polynomial monotone games that are not strictly monotone form a set with zero Lebesgue measure.
Theorem 3.3. For almost all monotone games, monotonicity can be certified at a finite level & of the SOS hierarchy (17), i.e., SO S O. Concretely, for all d Z 2, the set of monotone polynomial games of degree d over compact basic semialgebraic set X that are not strictly monotone has zero Lebesgue measure.
The proof of this result is given in Appendix Ahis point, we have shown that the monotonicity of almost all polynomial monotone games 4 over a compact, convex semialgebraic set can be certi- fied by solution SOS (SJ) at some finite level by of the SOS hierarchy (17). However, for an arbitrary game I, the required level fyr may be large. Thus, in practice, certifying the monotonicity of & via the SOS hierarchy in (17) may be computationally infeasible. To reflect this limitation, in the following section, we introduce and study subclass of monotone games called f-SOS monotoooe games, for which monotonicity can be certified in polynomial time via semidefinite programming.
4 SOS-Concave & SOS-Monotone Games
Motivated by the convergence guarantees of the SOS hierarchy established in Theorem 3.2 in this section, we define and analyze a subclass of polynomial monotone games over a compact, convex basic semialgebraic set for which monotonicity can be certified at some fixed level & of the SOS hierarchy. These are games whose monotonicity can be verified in polynomial time with respect to the level f. We refer to such games
Definition 4.1 (e-SOS-Monotone Game). Consider polynomial game & (m, over compact, convex basic semialgebraic set X. For all 2 0, we say that I is E-SOS- SSS-mmonoooee if
y (J(y Qe(K x B).
(18)
We denote the set of E-SOS-monoton games by Gsomm(n Furthermore, we say that & SOS- monotone if there exists e E N such that & is --SOS-monotone.
The following theorem is an immediate consequence of Statement in Theorem 3.2 and the measure-theoretie result Theorem 3.3
Theorem 4.2. For all d 2 2, the set of monotone polynomial games of degree over a compact, convex basic semialgebraic set X that are not SOS- COS-monotone has zero Lebesgue measure.
Next, we show that for every 2 O, the set of E-SOS-monotone games is a global approximator to the set of monotone games, i.e., SOS-monotone games are dense in monotone games. In particular, given some polynomial game 3 over a convex, compact basic semialgebraic set, we can compute the closest (-SOS-monotone game E in polynomial time. Moreover, since SOS-monotone games are dense in monotone games, as E + co, the projections & of 3 in the set of E-SOS-monotone games converge to the closest monotone game to S not just the closest SOS- monotone game. The proof of the following theorem can be found in Appendix C.4
Theorem 4.3. For all d 2 2, the set of SOS COS-monotone games of degree d over compact basic semialgebraie set X dense in the set of monotone games of degree over X. Furthermore, given any polynomial game 8 E (m,d) over X, and any fixed E. ' O, we can compute the closest E-SOS- monotone game to 8 by the program
minimize DE9(..a)
1 9
(19)
subject 9 Gsosm(v..d.))
which can be formulated as an SDP.
7

---

In Theorem 4.3 and throughout our experiments, distance between games is measured via the norm |I-I1 in Eq. (3). Beyond the aforementioned norm, the optimization framework in Theorem 4.3 ex- tends naturally to any function ||-I1 that measures deviations on (n,d). whose epigraph is semidefi nite representable and for which 11% 91 + 0 as k + Jo, for all monotone games y and some sequence of SOS-monotone games.
For example, we give another example of a valid deviation operator. Let gruad ([vx]], X, uquad) be the SOS-monotone game with the payoff functions u, uquad (x) = - l for all i E [n]]. The gange given by
( (1n]] X, x,) def min 2 0 9 + gruad E 99nsm (v.,,))
(20)
where for all E 2 0, 9 + E grquad denotes the polynomial game I'[[]] 2, u') with the payoff functions (x) = (1) + u quad (z). Furthermore, the corresponding SDP is given by the f-th level of the SOS hierarchy in Theorem 3.2
Modifications for the Certification of Concavity
The results in Sections 3.1 and be equivalently stated in relation concave polynomial games over a compact, convex basic semialgebraic set, subject to minor modifications. By definition, a polynomial game S over compact, convex basic semialgebraic set X' is concave if and only if the Hessian matrices Hu. (æ:) are negative semidefinite, for all I E X and E [n]] Furthermore, I is strictly concave and only if H.,, (x) are all negative definite. For each i, consider the SOS hierarchy (SOS,,e(9)) E20 given in Eq. where substitute SJ(x) with H., (x)). Then, the SOS-based hierarchy
(=) E20
(21)
provides analogous guarantees as in the case monotone games. In particular, Theorem 3.2 and Theorem 4.3) well as Definition 4.1 can be written analogously with respect to the SOS-based hicrarchy in Eq. (2T). Meanwhile, Theorems 3.3 and 4.2 can be written for concave games directly without further modifications. For completeness, we provide the definition of T-SOS-Concaae games here:
Definition 5.1 (4-SOS-Concav) Game), Consider a polynomial game & E G(n,d) d) over a compact, convex basic semialgebraic set X. For all 2 O, we say that & is L-SOS-concaye if
TH (x)y E Qx B), Vi [m]
(22)
Application: Extensive-Form Games with Imperfect Recall
As described concisely in [20 the class of concave games has many modern applications. Similarly, monotone games have been studied extensively due to their desirable equilibrium properties (see e.g. [38 19 9 and references therein). In this section, we highlight extensive-form games (EFGs) with imperfect recall, leveraging the fact that they can be viewed as polynomial games over compact, convex basic semialgebraic sets. We also utilize theoretical results and proposed game classes to study canonical examples of these games. We will defer further discussion on applications to economic markets to Appendix [F]
The study of extensive-form or sequential games arguably as classical as that of normal-form games. The reader is referred to 44 Sections II and III] for a review of standard concepts. Moreover, for the sake of notational brevity and readability, we defer formal definitions of EFGs and related concepts to Appendix D One of the most important results in extensive-form games is Kuhn's theorem [33, which establishes a connection between mixed strategies and behavioral strategies in EFGs with perfect recall (wherein players effectively never forget the history of information sets visited and actions played). Relaxing the perfect recall assumption results in games where players can forget prior information, which introduces additional computational challenges.
The canonical example of an imperfect recall game that of the absent-minded taxi driver (Fig- ure 3). introduced in [46]. Furthermore, [46] showed that the expected utility of any player in an EFG with imperfect recall can written as a polynomial, where each variable is associated with an information set (i.e., collection of decision nodes which player cannot distinguish between). In
8

---

P1
Pl
PI
P1
C
E
02
R
P1
P2
P2
P2
P2
E
1,-1
-1,1-5,5
5, 5,5-5,5
5,5
5,5-1,1
1,-1
Figure 2: A Game with No Nash Equilibria
Figure 3: The Absent-minded Taxi Driver
particular, these utilities define an n-variable polynomial game $ ([n]. clarity, we derive the corresponding polynomial utility function of the game in Figure 3 Since the player has imperfect recall and cannot remember they are in the first or second decision node, they will select distribution over {C, E to be applied to both decision nodes. If the player selects C with probability 2 and E with probability 22, then their expected payoff given by 2? 42,
X, over the simplex. For
In general, though, Nash equilibrium might not exist in EFGs with imperfect recall. For instance, the game in Figure was introduced by (64) and does have Nash equilibrium. Several recent works have further established hardness results for deciding the existence of or computing NE in EFGs with imperfect recall [31 59 60 23). Theorem C.I additionally guarantees the hardness of verifying concavity/monotooicity of EFGs with imperfect recall over simplex action sets.
6.1 Experimental Methodology Results
Our results in Sections 3.1 and motivate two lines of investigation: verifying monotonic- ity/concavity and computing the closest -0s-mmoooo//oocccaee game.
Examples & 2. First, we use the SDP hierarchy in Eq. 17 to certify JOS-monotonicity of the absent-minded taxi driver game Figure g Next, we use program in Eq. (19) find an SOS- monotone game 3 which is closest to the zero-sum game in Figure (which does not have NE in behavioral strategies), in the sense of the norm defined Eq. (3). By further enforcing that the new game has to be zero-sum and the monomial basis of the game is maintained, we are able to obtain closest monooonee game G' given by:
u/ T2. v) = -8r1 Sr2y 16x1 1622 12y - 9,
and u/ = -w The distance between the two games is 19 l'll = 10, and since the modified game is SOS-monotong has NE in behavioral strategies.
The above examples are applied to canonical EFGs with imperfect recall recall-going forward, we utilize framework to study larger EFGs and aim to study the scalability of our approach. For brevity, full experimental details are deferred to Appendix
Example 3: A degree-4 strictly monotone general-sum game.
4 Theorem 2.3] introduces
method construct (strictly) convex polynomials of degree 4. Using this method, we construct two-player game with degree-4 polynomial utility functions that is strictly concave. P1 and P2 choose their actions (I1, x22 and (y1, 1/2 from a wwo-dimensional simplex respectively. By running our hierarchy of SOS optimization problems in Eq. (17) for monotonicity, we obtain an objective value -I at level 4, thus certifying that the game is strictly monotone and also SOS-monotone.
Example 4: A degree-5 zero-sum game. We create a two-player zero-sum EFG with imperfect recall as shown in Figure E.4 where the payoffs on each leaf are for Pl. In this example, makes four moves before P2 makes a move, and P1 is minded. By letting r denote the probability that P1 chooses and y denote the probability that chooses 1, we obtain the payoffs for P1 and P2 as follows:
(z. v) = -16x4y 25x + 74.r2 39x 89x2y y + 49x 45xy 19r 8y + 3.

---

and Ug = -1. We run our program in Eq. (9) to find the closest SOS- monootnne game. Two additional constraints are imposed to retain the properties of the original EFG: The modified game has to be zero-sum, and the information structure of the original EFG has to be preserved. To preserve the information structure of the game, we select the monomial basis for the new payoff' functions to be precisely the monomial basis that can appear in the original game. The following modified payoff functions are found:
u/{ (zz, y) = -5.6x" y 6x + +33.8x y - 22.9x - 75.1x² y - 4xy - 68x - 57y - -66,
and U/2 = -u with | 8'1l = 49.
Example A degree-8 general-sum game. We construct a two-player EFG with imperfect recall where P1 makes six moves before P2 makes two moves. There is one information set for P1 and one information set for P2. P1 has three actions to choose from with probability #1, I2, and respectively. P2 also has three actions to choose from with probability y1, 3/2, and 1 - 5/1 1/2, respectively. Hence, the game tree has nine layers, including the root and the leaves, and the payoff functions are degree-8 polynomials with monomial basis
21 2/2
[x] 222 22 2i rlag J 22 1122 12 11, 2/,
5 2/ xi 2i 1 22 21. 2/22, 2/02.
21 22 a 22, 21 2r. 27. 22, on 11 x2 1] [vi y1 v2 y1 y2, 1],
where is the tensor product. The size of the monomial basis is 168. We do not restrict the EFG to be zero-sum, but instead randomly generate the payoff functions for P1 and P2 by independently sampling the coefficient of each monomial in the basis from uniform distribution on 1].
We run our program in Eq. (19) to find the closest SOS- momoooot game with the additional con- straint that the information structure of the original EFG has to be preserved, i.c. the new payoff functions have to be polynomials with the same monomial basis. As in Example 3, we defer the full payoff functions of the game Appendix E
On Scalability. A natural limitation of our framework is acalability-whil SDPs can be solved with arbitrary accuracy in polynomial time using interior point methods, they are among the most expensive convex relaxations to solve. In practice, "SOS problems involving degree-4 or 6 polyno- mials are currently limited, roughly speaking, to a handful or a dozen variables" [3]. We compare the compute times of our proposed hierarchies when applied to the larger-scale examples above. In- deed, while the SOS hierarchies in Examples and 4 can be solved in Rs 0.052 and as 0.009 seconds respectively, the much larger program for Example 5 took 2 37.53 seconds to solve using stan- dard, off-the-shelf solver. This further motivates future work on scaling our approach using existing methods in the literature 3 37 166 39 27). Our code is implemented using the SumOrSquares
package for Julia 336 63 and run on MacBook Air with 16 GB RAM.
7 Discussion
In this paper, we have shown that verifying concavity and monotonicity in polynomial games is in general NP-hard. For polynomial games over compact, convex basic semialgebraic sets, we utilize SOS techniques to construct SDP hierarchies that can certify concavity and monotonicity. Moreover, we show that almost all concave/monotone games are strict, and thus can be certified at finite level of the respective hierarchy. Finally. we introduced f-SOS-come Con-ccnncvee and e-SOS monooone games, which are certified at some fixed level l of the respective SOS hierarchy. This leads an application for EFGs of imperfect recall, where we are able to find the closest (in terms of an appropriate norm) JDS-concave/moontone game to a canonical EFG which has no Nash equilibria. In addition, light of the experiments in Section 6. our work motivates the design of application-specin programs which can find close concave/monoton games while also maintaining structural properties of the original game.
Broader Impact. While our results are primarily theoretical, we acknowledge that there could be potential societal consequences of our work, none of which we feel must be specifically highlighted.
'Code used to generate the experiments in Section can be found in our github repo
10

---

Acknowledgements This work is supported by the MOE Tier Grant SM0E-T2EP20223-002 Ministry of Education Singapore (SRG ESD 2024 174). the CQT++ Core Research Funding Grant (SUTD) (RS-NRCQT-0O0N)) oratories under the AT Singapore Programme (Award Number: AISG2-RP-2000-0166 and partially by Project MIS 5154714 of the National Recovery and Resilience Plan, Greece 2.0, funded by the European Union under the NexIGenerationEU Program. The authors also thank anonymous review- ers for their insightful feedback during the review process.
the National Research Foundation Singapore and DSO National Lab-
References
[1] Lukáš Adam, Rostislav Horčík, Tomáš Kasl, and Tomás Kroupa. Double oracle algorithm for computing equilibria in continuous games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5070-5077, 2021.
[2] Amir Ali Ahmadi and Georgina Hall. On the complexity of detecting convexity over a box. Mathematical Programming, (82(1))429-445) 2020.
[3] Amir Ali Ahmadi and Anirudha Majumdar. DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefiitt optimization. SIAM Journal on Applied Algebra and Geometry, 3(2):193-22) -30,, 2019.
[4] 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:453 476, 2013.
[5] Amir Ali Ahmadi and Pablo A Parrilo. On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials. In 49th IEEE Conference on Decision and Control (CDC), pages 3343-3348. IEEE, 2010.
[6] Kenneth J. Arrow and Gerard Debreu. Existence of an equilibrium for a competitive economy. Econometrica, 22(3):265- 290, 1954.
[7] 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.
[8] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games, Advances in Neural Information Processing Systems, 35:33904 33919, 2022.
[9] Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. In International Conference Machine Learning, pages 3507-3524. PMLR, 2023.
[10] Xi Chen and Shang-Hua Teng. Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria. In International Symposium on Algorithms and Computation, pages 647-656. Springer, 2009.
[11) Mandar Datar. On stability and learning of competitive equilibrium in generalized Fisher market models: variational inequality approach. arXiv preprint arXiv:2501.07265, 2025.
[12] Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Market cquilibrium via a primal-dual-tye algorithm. In The 43rd Annual IEEE Symposium on Foun- dations of Computer Science, 2002. Proceedings., pages 389 395. IEEF, 2002.
[13] Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Market equilibrium via a primal-dual algorithm for a convex program. Journal of the ACM (JACM), 55(5):1-18, 2008
[14] Melvin Dresher, Samuel Karlin, and Lloyd Shapley. Polynomial games. Contributions to the Theory of Games 1, 24:161-180, 1950.
[15] Edmund Eisenberg. Aggregation of utility functions. Management Science, 7(4):337-350
1961.

---

[16] Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30 1959.
[17] Eyal Even-Dar, Yishay Mansour, and Uni Nadav. On the convergence of regret minimization dynamics in concave games. In Proceedings of the Forty-First Anmual ACM Symposium on Theory of Computing, pages 523-532, 2009.
[18] Francisco Facchinei and Christian Kanzow. Generalized Nash equilibrium problems. Annals of Operations Research, 175():117-2211,2)) 2010.
[19] Francisco Facchinei and Jong-Shi Shi Pang. plementarity problems. Springer, 2003.
variational inequalities and com-
[20] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung- Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. Ad- vances in Neural Information Prucessing Systems, 35:39076-39089, 2022.
[21] Yuan Gao and Christian Kroer. First-order methods for large-scale market equilibrium compu- tation. Advances in Neural Information Processing Systems, 33:21738 7770--500 2020.
[22] Yuan Gao and Christian Kroer. Infiniteddimensional Fisher markets and tractable fair division. Operations Research, (2()6688-707, 2023.
[23] Hugo Gimbert, Soumyajit Paul, and Srivathsan. A bridge between polynomial optimization and games with imperfect recall. In AAMAS '20, page 456-4666 464. International Foundation for Autonomous Agents and Multiagent Systems, 2020.
[24] Denizalp Goktas and Amy Greenwald. Convex-concave min-max max Stackelberg games. Ad- vances in Neural Information Processing Systems, 34:2991-3003, 2021.
[25] Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning multi-player games. Advances Neural Information Processing Systems, 13:20766-20778, 2020.
[26] Baining Guo. On the difficulty of deciding the convexity of polynomials over simplexes. International Journal of Computational Geometry & Applications, 6(02):227-229, 1996.
[27] 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. arXiv preprint arXiv:2403.09113: 2024.
[28] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In Conference on Learning Theory, pages 2388-2422. PMLR, 2021.
[29] Kamal Jain, Vijay Vazirani, and Yinyu Ye. Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. In Proceedings of the Sixteenth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA '05, page 63-71, USA, 2005. Society for Industrial and Applied Mathematics.
[30] Samuel Karlin. Mathematical Methods and Theory in Games, Programming and Economics.
Vol. 2: The Theory of Infinite Games. Addison- -eeiiey Publishing Company, 1959.
[31] Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in ex- tensive form. Games and Economic Behavior, 4(4):528-552, 1992.
[32] Tomáš Kroupa and Tomá Votroubek. Multiple oracle algorithm to solve continuous games. In International Conference on Decision and Game Theory for Security, pages 149-167. Springer, 2022.
[33] Harold W Kuhn. Extensive games and the problem of information. Contributions to the Theory of Games, (128):193-216 1953.
[34] Rida Laraki and Jean Lasserre. Semidefinite programming for min-max problems and games. Mathematical Programming, 131:305-332, 2012.
12

---

[35] Jean Bernard Lasserre. Moments, Positive Polynomials and Their Applications. Imperial Col- lege Press, 2009.
[36] Benoît Legat, Chris Coey, Robin Deits, Joey Huchette, and Amelia Perry. Sum-of-squares optimization in Julia. In The First Annual JuMP-dev Workshop, 2017.
[37] Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Annual Review of Control, Robotics, and Autonomous Systems, 3(1):331-360, 2020.
[38] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173:465-500 2019.
[39] 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 urXiv:2401.12499 2024.
[40] Theodore Motzkin and Ernst G Straus. Maxima for graphs and new proof of theorem of Turán. Canadian Journal of Mathematics, 17:533-540, 1965.
[41] Katta G. Murty and Santosh N. Kabadi. Some NP-complete problems in quadratic and nonlin- ear programming. Mathematical Programmingg 39(2):11-122,, June 1987.
[42] John Nash. Non-cooperative games. The Annals of Mathematics, 54(2):286-29) 295, September 1951.
[43] Jiawang Nic and Xindong Tang. Nash equilibrium problems of polynomials. Mathematics of Operations Research, 49(2):0065-1090, 2024.
[44] Martin Osbore and Ariel Rubinstein. course in game theory. MIT press, 1994.
[45] Pablo A Parrilo. Polynomial games and sum of squares optimization. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 2855-2860. IEEE, 2006.
[46] Michele Piccione and Ariel Rubinstein. On the interpretation of decision problems with im- perfect recall. Games and Economic Behavior, 20(1):3-24, 1997.
[47] R. Tyrelll Rockafellar. Convex Analysis. Princeton University Press, 1970.
[48] Tyrrell Rockafellar and Roger J-B Wets. Variational Analysis. Springer Berlin, Heidelberg, 1998.
[49] J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pages 520-534, 1965.
[50] Tim Roughgarden and Florian Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317-342, 2015.
[51] William H Sandholm. Population games and deterministic evolutionary dynamics. In Hand- book of Game Theory with Economic Applications, volume 4, pages 703-778. Elsevier, 2015.
[52] Abraham Seidenberg. A new decision method for elementary algebra. Annals of Mathematics, 60(2):365-374, 1954.
[53] Maurice Sion. On general minimax theorems. Puc. J. Math., 8:171-176, 1958.
[54] Sylvain Sorin and Cheng Wan. Finite composite games: Equilibria and dynamics. Journal of Dynamics and Games, 3(1):101-120, 2016.
[55] 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.
[56] Noah D Stein, Pablo A Parrilo, and Asuman Ozdaglar. Correlated equilibria in continuous games: Characterization and computation. Games and Economic Behavior, 71(2):43-455,, 2011.
13

---

[57] Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 59(1):177-208, 2007.
Alfred Tarski. A decision method for elementary algebra and geometry. Journal of Symbolic [58]
Logic, 17(3), 1952.
[59] Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, and Paul W Goldberg. The computa- tional complexity of single-player imperfect-recall games. In Proceedings of the Thirty-Second International Joint Conference Artificial Intelligence, pages 2878 288-2887744 2023.
[60] Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sand- holm, Paul Goldberg, and Vincent Conitzer. Imperfect-recal games: Equilibrium concepts and their complexity. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages
2024.
[61] Lou Van den Dries. Tame topology and o-minimal structures, volume 248. Cambridge Uni- versity Press, 1998.
[62] John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100(1):295- 320, 1928.
[63] Tillmann Weisser, Benoît Legat, Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. Poly- nomial and moment optimization in Julia and JuMP. In JuliaCon, 2019.
[64] Philipp C Wichardt. Existence of Nash equilirria in finite extensive form games with imperfect recall: counterexample. Games and Economic Behavior, 63(1):366-366 369, 2008.
[65] Jiayi Zhao, Denizalp Goktas, and Amy Greenwald. Fisher markets with social influence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5900-5909, 2023.
[66] Yang Zheng. Giovanni Fantuzzi, and Antonis Papachristodoulou. Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse poly- nomials. In 20/9 American Control Conference (ACC), pages 5513-5518, IEEE, 2019.
[67] Zhengyuan Zhou, Panayotis Mertikopoulos, Aris Moustakas, Nicholas Bambos, and Pe- ter Glynn. Robust power management via learning and game design. Operations Rexearch, 69(13331-3445 2021.
14

---

A Additional Related Work
Polynomial Games and Semidefinite Programming. Initially introduced and studied by [14]. polynomial games were viewed as bridge between finite and continuous games. Although 14
characterized and proved the existence of equilibria in these games, providing computational guar-
antees for general polynomial games has proven to be a challenging task. [45 34 used semidefinite
programming methods find the value of two-player zero-sum polynomial games. and similar tech- niques apply to separable games (where utilities take a sum-of-products form) [55]. Recently, [43] also used semidefinite programming techniques solve for Nash equilibria in r--player polynomial games, or otherwise detect the nonexistence of equilibria. Beyond polynomial games, oracle-based methods have been used to approximately solve continuous games 32
B Additional Preliminaries
Given game & with utility functions ui (x),, the standard Jacobian defined as follows:
H (x)
V V (x)
VI (V un (x))
V V 22 (2)
H (x)
VT (V u2 (x)
((x) def
(A23)
V
un (x)
V (V,,
n. un)
H (x)
21
C Omitted Proofs from Main Text
C.1 Proof of Theorem 3.1
As mentioned earlier, several works have studied the hardness of verifying convexity in multivariate polynomials 4 22. We state the main theorem for hardness of verifying convexity over box here for completeness:
Theorem C.1 ((2, Theorem 2.3]). Deciding whether a polynomial of degree at least 3 is conver over a box D (x R"
04 S x S 3r i for a, 6,8 IR,, is strongly NP- Na-hard.
Using this result, polynomial games.
able prove NP-hardness of verifying concavity and monotonicity in
Theorem 3.1. Let [[n], X, be polynomial game over compact convex basic semialgebraic set. If for some player us is a polynomial of degree at least with respect to K; E X, verifying whether 3 is concave monotone is strongly Na-hard.
Proof. To prove the statement concave games, let p: Rm + R be a polynomial of degree 3 or higher, and let 'D def {ar E R aj S I, S B jE [m]] for B E R" and aj S Bj, be a box over T Consider two-player polynomial game ([ D x D, u), where in u)(x) = p(x1), ) and w2(x)) 0 for all æ E D x D. Then, since u2 is concave over D, the game 3 is concave if and only p is concave over D. Thus, from Theorem C. it follows that verifying whether is concave strongly NP-hard.
To prove the statement for monotone games, let p: RT + E be a polynomial of degree higher, and let ' = {ir E Rn ay < 22 S 3, j E [m]] }. for a, 8 E R. and aj < By. be a box over R" Note that the description of D satisfies Eq. [Tp. and hence D a convex and compact semialgebraic
set. Define X1 [a1, 31] x ... X [, mm. 1]. and X [alm 3m]. Clearly, X1 x 2/2 D.
Consider two-player polynomial game I ([2), X1 X X2, u), where u1(z) = uz(x) p(x) for all
X. Then, the game & is monotone if and only if the operator (-Vz, U1 (z), V (2)))
-p(xx) is monotone over Xi X2, or cquivalently is concave over D. Thus, from Theorem follows that verifying whether o is a monotone game is strongly NP-hard.
As direct consequence of the hardness of verifying the concavity of degree-4 polynomials over the simplex 26 4, we can obtain the following NP-hardness result for verifying concav- ity/monotonicity in polynomial games with simplex action sets.
15

---

Theorem C.2. Let ([n]], X, be polynomial game where X; E A If for some player u, is a polynomial of degree least 4 with respect to 2; Nr then verifying whether & is concave/monotone is strongly NP-hard.
u)
Proof. We provide similar construction to the proof of Theorem 3.1
Here we show hardness for verifying concavity the proof for hardness of verifying monotonicity is similar. Let R + I
Eigma 2; 1, 2 for i be the mn-dimensional simplex. Consider a two-player polynomial game [[2], A x u.), where иn (x) p(a1)). ), and (2(x)) 0 for all x E A A. u2 is concave over A, the game y is concave if and only if p is concave over A. Thus, from 4 Theorem 2.1] ]] (and as indirectly
be a polynomial of degree or higher, and let A del {a I
1, I,...,m} ,
argued in [26] utilizing [40] Theorem 1]), it follows that verifying whether z is concave is strongly NP-hard.
C.2 Proof of Theorem 3.2
Theorem 3.2. Let & ([n], X, u) be polynomial game over compact, convex basic semialgebraic set X. Assume the quadratic module Q(x)) is Archimedean. For any E N consider the hierarchy of SOS optimization problems:
SO)
minimize XER
(17)
subject to X SJJ(( Qe(ā x B),
where Qe(A' x B) denotes the restriction of Q(X x B) to polynomials of degree at most Then, the following statements true:
1) For all we have that SOS, 2 max Amar (s)).
2) The sequence (SOS;(9) E20 is nonincreasing.
3) limg-+oc SOS)(9) maX Amas (z)..
4) I is strictly monotone if. and only if. there exists some finite level such that SOS, 0.
5) For any level f, the program in 17 can be formulated an SDP and solved in polynomial time.
Proof. To prove Statement 1 start by considering
arbitrary 8 0. Observe that, if the
program in (17) is infeasible, then (SJ: = oo, and therefore SSJ) 2 Amax (SJ(z)) for all E X. On the other hand, if the program in (17 is feasible, SOS,(SJ) y SJ (x)y E Qe(A' x B), Σ[x] and ph ... Pmng R[x] such that
i... there exist .i....,o Jm,
mg
m
(OS of +)+ g (1)
Σ 1=1
v)
hy (x)))) (x. Va, R..
(A24)
In particular, since (x) = -... Nms (x) = 0 for all E X: and y 0 for all y E B, by the above we also have that
my
Σ SOS; (J(())) = v) 9 (x)o (2.9) 20
Yo X, y B, (A25)
where the last inequality follows because (x) 0 for all x X, and oo ....... om, E Elr,y) Furthermore, since SJ is symmetric, the maximum eigenvalue of SJ (J is given
Amax (SJ (z))
der
max y SJ(J) (SJ,, yEB
AWA
Va X.
(A26)
Alas, we have established that, (SS) 2 Amax (SJ(x)) for all X and E 0.
To prove Statement 2 observe that as increases, the feasible of the minimization program in 17 is expanding, and therefore (SOS:(S.)) r20 is nonincreasing.
16

---

To prove Statement 3 we. first, prove that limg- (SJ) exists, i.e.. the sequence (SOS;(ST)) 120 converges. In particular, observe that, since the quadratic module Q is Archimedean, the set X is compact, and thus, the maximum max Amax (2)) exists. Then, by Statement I it follows that
max max (x)) & SOS, #
34 1 0.
(A27)
Consequently, the sequence (SOS, (SJ)) 220 nonincreasing (Statement 2 and bounded from be- low by (Equation A277). ) and therefore it converges.
max Amax (SJ(x) if for every > 0, there exists to 2 0 such that (SJS((SS) maX Amax (SJ())) Positivstellensatz to show that for every e such an to exists.
Now, recall that lime-+o SOS;
for all / 2 lo- We going to use Putinar's
First, observe that X' x B is a basic semialgebraic set. In particular, we have that
(a(, def g,(x) 2 0, j E [my]
X x B = (I,1) ER x IR h6(r, del 1 1- yyy
0,
(A28)
(x, def h2 0, j E [mm]]
Furthermore, it is not difficult to show that the quadratic module Q B) is Archimedean.
Indeed, since (22) is Archimedean, there exists N N such that N E xt E Q(x). There- fore, there exist 0u, ................................ m [[x]], and Pl..... Pmas E R[[x] such that
ma
N
2 (xx Σ (1)
Σ hy(c)ps((),
Ve E R
(A29)
Define the polynomial functions og...., o'm Po: ........ "......PP,.."
R" x R"
R given by
df v) (1) j= 0,..... mg
pb(z,v)
Vz, y E CRT
(A30)
p (z. Pz(x))
j
mp
and observe that, since do. ... Jm, E E[x], it follows that o ................................ o' E[r Moreover, observe that
my
mA
N +
Σ 2 dx(x) + Σ ()(=))((0) + > (x()))(()),
V (A31)
and therefore, N
+
Σ
x
Σ m yi E Q( x B). Thus, we conclude that Q(X x B) is
Archimedean.
Next, observe that, by definition, maxxex Amax (a)())) = max y (SJ())y, which also implics that
WEB
max Arnax (SJ(x)) - SJ] 2 0, Vo E yEB EE
(A32)
Therefore, the polynomial
(x, y) max Amax (SJ (z) y SJ(Yy +c =xX
(A33)
positive over X' for e 0. Thus, by Putinar's Positivstellensatz, follows that qe (z, y) Q x B), i.e., there exist .o...., Jn E E(r, v), and pa, ...... PPm R y] such that
max Amax (SJ())) +e) TJJJ(x) qe (2, REX
m2
= =o((xn)) + Σ 1=1
g (,)
Vx, y E R".
ma
+ (1 of Fuupoo v) + >
h (5()));(
(A34)
17

---

Let to max (do) ..... deg(am deg(po).... ..... deg(pm,)))
0 be the smallest number such that 26o
2
Then, follows
that
mmaxxex Amax (z)) + e, E, a solution to the SOS program Thus, by the optimality of SO (SJ), and since the sequence (SOS,(ST)) 120
17 where Eo-
is nonincreasing
(Statement I it follows that
SSS) & SOS,, < max Amax (SJ())) te, aEx
34 2 to.
(A35)
Alas, by A27 we conclude that
SOS; (SJ)
max Amax (SJ())) (SS) max Amax (SJ(z)) S, #EX
44 lo.
(A36)
#EX
To prove Statement 4 recall that a polynomial game strictly monotone if, and only if.
max Amax (s)( < 0. ZEX
(A37)
First, suppose that g is not strictly monotone. Then, by the above, we have that max,ex Amax (SJ(x)) 2 0. Thus, by Statement it follows that
(SJ, Z max Amax (SJ(z)) 2 0,
A4 2 0.
(A38)
ZE
Next, suppose instead that & is strietly monotone. Then, maxzex Amaa (SJ(x:)) and therefore, exists e > such that maX Amax (SJ(x)) + c < O. Moreover, by Statement we also have that
lim (SS)(SS) = max Amax (SJ(z)) E-000
(A39)
=EX
Therefore, by definition, there exists to 2 0 such that [SOSt, (SJ) max Amas (SJ [z)) S 6, and thus
SOSE, (SJ) ) < max Amax (SJ()) +
(A40)
=ex
Statement fooloww from standard results in semidefinite programming.
C.3 Proof of Theorem
Theorem 3.3. For almost all monotone games, monotonicity can be certified at a finite level & of the SOS hierarchy (17), i.e., SOS,(9) S O. Concretely, for all d 2 2, the set of monotone polynomial games of degree d over compuct basic semialgebraic set X that are not strictly monotone has zero Lebesgue measure.
Proof. Let Gm((,a)) and Gam(n,d) denote the sets of n-player, d-degree polynomial monotone and strictly monotone games, respectively.
are going to show that given a compact, convex ba- sic semialgebraic set X' of joint actions, the set (m(n,d) Gam(n.d) has zero Lebesgue mea- sure. In particular, define μ the canonical dim(9m(nna) ) Lebesgue measure on (G (Gm)), i.e., the affine hull of Im(n.d)- First, we show that Gminnd) is p-measurable and there- fore the restriction of μ to Gm(n,d) (denoted by μ lmm)n..)) ) is dell-de Then, we show that a (omen... (Gm(n.d) \ (sm(n.e)) = O.
aff
To begin with, observe that by definition:
Gm((nd)) = { E ((n.d) (z)
(x) 2 Vz E X})
(A41)
where for each 3 E &mm(n,d) SJg is the symmetrized Jacobian matrix of the pseudo-gradient by of G. Next, observe that the map ($ + SJy(r) is polynomial in & and Moreover, the determinant A + del(A) is also polynomial in A. Therefore, for all 9 E (m(n,d) and x E X, the principal minors fr: (9,x) + det (SJ (SSSIJs1200 (z)), I E 2lm], of SJ (x) are polynomial in & and x. Thus, by Sylvester's Criterion:
Sm((n,)) {9 E ((n.d) fi x) 2 0, VI E m E X3.
(A42)
18

---

It follows by the Tarski- Seisk--Siddeberg theorem 18 52 that (m( is basic semialgebraic set, and therefore Borel set. Thus, (m(ndd) y-mmesuurall.
Next, observe that (m(n,d) is convex. Indeed, for all x E X, define
Sx
(9 E (n.d) SJ (x) ž 0}.
(A43)
Observe that the map J,: & + SJ (a:) linear. Since (n,d)) is vector space, S = Ja (9( is vector subspace, and therefore convex. Thus,
(m(n.))
in Sx
(A44)
xE
the (uncountable) intersection of convex sets, and therefore it is convex. Note that since the empty set is convex, the statement in Eq. (A44) remains valid even if the intersection is empty.
Let us now consider the set
(am(n,d)
{9 E ((n,d) Jz)(z) > O, Vz E E
(A45)
Observe that for all d 2 O, Gam(n,d) is non-empty as the game 3' with payoff functions u, x H || [2 for all i E [[x]]] is strictly monotone. We show that Gam(n.d) 2 in,(a))),a)) with respect to the relative topology.
Let 90 E int(Gm(,.a))) and suppose 9o & Gam(n,d) Then, by definition, there exists E X such that SJ (xx) y O, i.e., it exists a vector IR \ {0} such that w SJS, (zg)u 0. Define L: S ~ u. S. (un)u. Since J.n is linear map, it follows that I. linear functional. In particular, O. Moreover, since by definition SJy (x) ł for all & E (m(n..) and E X, we also have that ((Gm(n,a)) 2 O. Finally, since (smmn,.d) non-empty, by definition we have that [(Gsm(n.at) > O, and therefore L is non-trivial, i.e., L # O. Thus, L describes non-trivial supporting hyperplane (m(n.d) containing (3)). Then, by version of the Separating Hyperplane theorem [47] Theorem 11.6, p. 100], we may conclude that So $ int (nm(Gm().)) which contradiction. Thus, 9n E (n)(n, and therefore it follows that 9sm (n,d) 2 int int(9m(n.a))
we have that (.)))
Using & to denote the boundary of set, we conclude that, (m,)),) \ Gam (n. C ((Gm(n.d)) Moreover as established before, 9mn(n.d) is a basic semialgebraic set. Thus, by 66 Theorem 1.8, 67], it follows that
dim((m((nd)) \ (9m((.a)) & dim (8(9m(n) < dim((mm(n.d),,
(A46)
which, since 9m (n.d) is jummasurrbll, allows us to conclude that / (em (Am(n (am(n,d)) = 0.
C.4 Proof of Theorem
Theorem 4.3. For all 2 2, the set of SOS-monotone games of degree d over a compact basic semialgebraic set X is dense in the of monotone games of degree over X. Furthermore, given any polynomial game 'g* E (( over X, and any fixed 2 O, we can compute the closest t-SOS- monotone game to " by the program
minimize DES(n.a)
19 g
(19)
subject
② Goomm(n.d.f))
which can be formulated as an SDP.
Proof. Let Gm((nd)) denote the set of r-plaaer, d-degree polynomial monotone games, First, we show that (sosm(n,d)) is dense in Gm(n,.). i.e.,
claatn.ds Goosm Gm
(A47)
Let G Gm(nn))- Furthermore, for each k N, define Sa as the n-player, d-degree polynomial game over X' with utility functions uk,1, Uk,n : X' - IR given by
Uk (2) u.(x) 2k |1
Wa E x
ie [n]]
(A48)
19

---

Then, the pseudo-gradient of 99x is given by
2x, uR (x)
V (1) - - -01
Uk (x) =
Vx E X,
(A49)
V zn Mk,n (2)
V xn (2) - k
and the symmetrized Jacobian matrix SJ& of un is given by
SJ& (2) = (x)
k I,
Va E X.
(A50)
Moreover, since y is monotone, it follows
1 < < 0, (A51)
max Amx (SJ+(z)) = max Amaa (SJ(r) - I) = max Amax (SJ(x)) - xEX
x
and therefore Sg is strictly monotone. Subsequently, it follows that G. is SOS-monotone, i.e.. 9x E (Snss((n,))
Now, consider the sequence (9)) of SOS-monotone games. Observe that
lim 9 Bell lim max [vec(u)) ulk, 1) lim 0. 1
(A52)
2k
In other words, (5) converges to 3. Thus, by definition, clgm(n...) Gsoam Gsosm (n,d) dense in (m(nd))
(m i.c.
Next, we show that the program Poly(E)). where "[[[]], u*) E (n.d)- and 2 0.
19 may formulated as a SDP and solved O (log(
First, by Definition 4.1 the program in 19 is equivalent to
minimize #E9(n.4)
| I
(A53)
subject to y SJ() E Qi x B).
where (z) is the (symmetrized) Jacobian matrix of the pseudo-gradient of [[n]] X, x). Define the map f: (vec(u),.... vec(u,), v) + -J"SJ(z)y Now, observe that (ro(uu))...,ve(((((
SJ(x) is an affine map, and therefore f is affine in (vec(u)),.... vec(un)), and polynomial in (I,
Next, by the definition of ||-|/, we have that
|
max voc(u:) voc(u;)llo.. rE[n]
(A54)
Thus, the program (533) equivalent
minimize
A (.ve
subject
z max mvc((u) vec(u;))loo iE[m]
(A55)
f(vec(uz)..... voc(un), x, x. E Qe(E' x B)
Moreover, the condition À 2 maxic [m] (vec(u))) vec(u lo is equivalent to
my + d
Wi [n]] j A 2 vec(us)) vec(u));,
(A56a)
mm + d
A voc(u,)) - vec(ui)i.
Vi E [n]] j
(A56b)
20

---

Thus, the program in A55
is also equivalent to
minimize
A, vecc(ur)...,ve((uuu.
mi d
subject to
2 veo(ue); - veo(u]); vi [n]] j E
(A57)
2 voo(u;); voc(us)j vi [r]] j
mi
f (vec(ui),... ve((uu) 2. E Qc x B)
Finally, observe that, f is affine in vec(u1), vec(u,), all the constraints of the program in (A5)) are affine in X, voc(u)). .... vec(u.). Then, by definition, the program in (A57) is a SOS minimization program, and therefore it may be reformulated SDP.
D
Extensive-Form Games with Imperfect Recall
D.1 EFG Preliminaries
For completeness, we provide the necessary notation for EFGs with imperfect recall and their con- nection to polynomial optimization. First, we note that in standard game theory, strategies for EFGs lie in the simplex.
Definition D.1. An n-player extensive form game I is tuple r = (H, A, 2, where:
The set H denotes the states of the game which are decision points for the players. The states & E H form a tree rooted at an initial state r E H.
Each state & E H is associated with set of available actions A(h).
The set / = fl..... n. c} denotes the set of players of the game. Each state H admits a label Label(h) E N which denotes the acting player at state h. The letter denotes special player called a chance player. Each state E with Label(h) = is additionally associated with function on AA(h) + [0, 1] where (a(a) denotes the probability that the chance player selects action E A(h) at state h. E.EA(R) (a) = 1.
Next(a, h) denotes the state h' == Next(a, a, h) which is reached when player == Label(h) takes action a E A(h) at state h. H, S denotes the states h E H. with Label(h) = i.
denotes the terminal states of the game corresponding to the leafs of the tree. At each z E Z no further action can be chosen, so A(z) Ø for all 2. Each terminal state z E 2 is associated with value u(z), where u 2 - called the utility function the game.
The game states H are further partitioned into information sets ascribed to each player, namely I, E II,). Each information set E I, encodes groups of nodes that the acting player cannot distinguish between, and thus the available actions within each infoset must be the same. Moreover, the player must play the same strategy in all nodes of the infoset. Formally, if f1, hy E I, then A(h₁) = A(h2). With slight abuse of notation, we can consider A(T) to be the set of shared available actions for the player infoset
For notational convenience, we ascribe singleton information set each chance node and define I. as the collection of these chance node information sets. For each non-terminal node h E H Z, thus define In. (II, . II.) I, to be its infoset.
The standard assumption in the literature is that of perfect recall, wherein no player ever forgets their past history (i.e. their past information sets and actions taken in those information sets) or any information acquired. Formally, for any infoset E I, and for any two nodes h1 h2 I, the sequence of Player i's actions from to hy and from to h2 must coincide, otherwise they would be able to distinguish between nodes. Finally, the game called perfect recall if all players have perfect recall. Otherwise, the game is said to have the imperfect recall property. The notion of perfect recall has been crucial to establishing convergence results to pure Nash equilibria in extensive-fom games, primarily via the concept of behavioral strategies:
21

---

Definition D.2 (Behavioral Strategy). Consider the infosets belonging to player i, denoted I E I Let ((A(T)) denote the set of probability distributions on the simplex over actions in A(T). The set of behavioral strategies of player is denoted by 0; I. - Usez, A (A(T)). In particular, at each of their infosets player i selects a probability distribution over their available actions at the infoset, (.(T)) E A(A(T)) Finally, the joint behavioral strategy for all players is denoted o == (o.)e
Similarly, mixed strategies can be defined in the following way:
Definition D.3 (Mixed Strategy in Extensive-Fomn Games). Denote by S; the set of all possible actions across all game states H for player i in r. Then, for all pure actions in the game 8 S Player i's mixed strategy μ4 is given by the probability distribution defined by the probabilities (s) of playing strategy
Intuitively, one can view behavioral strategies as players randomizing between their possible actions between each information set, and mixed strategies as players randomizing over their strategy se- quences prior to playing the game (i.e. ex ante). Kuhn's 's theorem provides meaningful connection between behavioral strategies and mixed strategies in EFGs with perfect recall:
Theorem D.4 (Kuhn's Theorem (33). player in an extensive form game has perfect recall, then for any mixed strategy μ of player there exists equivalent behavioral strategy a of player i.
Moreover, computing behavioral strategies in two-player zero-sum games of perfect recall is possi- ble in polynomial time (31). However, once the assumption of perfect recall relaxed (i.e. when players have imperfect recall), Kuhn's theorem no longer holds and finding a solution even in the two-player zero-sum case becomes NP-complete 3T
D.2 Imperfect Recall Games
64 introduced an example of game with no Nash equilibria in behavioral strategies (Figure 2 Subsequently, a variation of the original game called the forgetful penalty shoot-out game was intro- duced in [60] and proceeds as follows: Player decides whether to kick a ball Left or Right before the whistle is blown, then decides again right before kicking the ball. At the second decision node, the player has forgotten their previous decision. If the decisions the two nodes match, Player manages to aim at the goal, during which Player 2 has to decide to dive Left or Right to stop the ball. Otherwise, the shot goes wide. This game also has no Nash equilibria in behavioral strategies.
When studying imperfect recall games, a key question to ask is whether one should consider mixed strategies or behavioral strategies. In particular, Kuhn's Theorem no longer holds and the conve- nient sequence form representation is not well-defined. Indeed, mixed strategies require players to select actions according to a distribution over all possible strategy sequences. For instance, mixed strategy for Player I in the forgetful penalty shoot-out game (Figure 2 could look something like: Kick Left twice in a row with probability 0.5, and kick Right twice in a row with probability 0.5. However, this requires the players to have some memory of their previous actions. In contrast, be- havioral strategies are more natural in imperfect recall games they do necessitate a memory requirement, a point which is argued for in Kuhn's 's original treatment of perfect recall games (33].
Following the work of 46 159, we show construction from imperfect recall EFGs to polynomial utilities via behavioral strategies. First, let P('||a, h) denote the realization probability of reaching h given that players using strategy a reachable from h) then the probability is O. Intuitively, the realization probability given a behav- ioral strategy is just the product of choice probabilities along the path from h to h'. In order to formally define P(h'lo la, h), we will need some additional notation. First, any node h E H uniquely corresponds to a history hist(h) from root r to h.
state h. Note that if h hist(h') (i.e., if N' is not
Function 6(h): H + N denotes the depth of the game tree starting from node h E H.
Function v(h,d) H. x N + H. identifies the node ancestor at depth d S 5 from node h.
Function a(h,d) H x N U(hh identifies the action ancestor at depth d < from node h.
Together, the sequence (u(h, 0), v(h, 1),... v(h, 8(h)) uniquely identifies the history of nodes from to h. Likewise, the sequence (a(h, 0), (h, 1),....,((( 0(h) 1)) uniquely identifies the
22

---

history of actions taken from to h. Then, the realization probability of node h from h if the players use joint strategy profile is given by: Definition D.5 (Realization Probability).
6(h)-1 II
P(N h))
a(a( ((a((, if h E hist(!(". j=b(he
Definition D.6 (Expected Utility for Player i). For player at node h E H. 2. if strategy profile is played, their expected utility is given by (,(a 1h) Exez (P(zla, h) uz(2)). In its complete
form, we can write the expected utility for each player as follows:
6(z)-1 II
Ui(o)
= ZEZ
a(((2, ux(2)
With some abuse of notation, we can write P(hlo)= = P(hla, r) where is the root node, and simi- larly (:) == U:(alr). Notice that by definition, the expected utility of each player is polynomial function. In particular, P(zlo, h) (z) is a monomial a multiplied by a scalar.
Going forward, we establish several results connecting EFGs with imperfect recall and polynomial games, utilizing some additional notation.
1 denotes the number of infosets of player i, i.e. & == [Za|- Moreover, fix an ordering (R.....,1 I
of infosets Iç-
mi denotes the number of actions in given infoset 1/ I, of player i, m² |A(E))
Moreover, fix ordering (a!.....af" aa)) of actions in A(
The strategy set of a player in information set I is defined on the simplex AIA(T)11,, where A {o R" z Vk, Σ 2* =1}.
Subsequently, the strategy set of player over all of their infosets can be written as a Carte-
sian product of simplices: S, == X A Moreover, the strategy set over all players Am/-1.
is S = X
A joint strategy E S for the players can hence be uniquely written as vector (oi)) xX j- A A
RT
Firstly, note that each infoset belonging to a player an EFG with imperfect recall induces an additional variable in the expected utility function. Clearly, the resultant polynomial utilities can themselves be viewed as a polynomial game in the sense of 14, 45 55 (and also falling in our definition of polynomial games 9), with the following definition of Nash equilibrium in behavioral strategies:
Definition D.7 (Nash Equilibrium in Behavioral Strategies). joint behavioral strategy o²
A m1 is called a Nash equilibrium if for all players i e AV:
Uz(a") 2 Ut(a,, Va; E
i.c. no player has incentive deviate from the behavioral strategy a* in any of their information sets.
Remark D.8. The definition of Nash equilibria in our setting directly implies that any solution of the corresponding polynomial game defined using the polynomial utility functions is also solution to the original EFG. In particular, the constructed polynomial utilities can be viewed as a generic polynomial game with utilities (z)). Here, x denotes the joint action profile of all players (see Section 2). Here, the number of variables in æ is equal to the total number of infosets over all players, ΣiEN E,. A joint state x² is called Nash equilibrium if the following holds for all players i N: (xx"") 2 w2(2,, x", Var; E St. At Nash equilibrium in the polynomial game, no player has incentive to unilaterally deviate in any of the variables they control. This is precisely the definition of Nash equilibrium in behavioral strategies for the original EFG.
23

---

E Additional Experimental Details
Example 1:
The absent-minded taxi driver in Figure In the case the game in Figure 3 we
let denote the probability of choosing C and - z be the probability of choosing E. We use the
SDP hierarchy in Eq. (7) to certify SOS-monotoniccty of the polynomial u(x) -3x 2 + 4z. We
select 2 and obtain SOS₂ ( = -6 < O. Then, by Statement of Theorem 3.2 the game is
strictly monotone. This additionally guarantees that the solution of the game is unique 49
Next, it follows as consequence of Theorem 4.3 that we can use the program Eq. (19) to find an SOS-monotone game y which is closest to the zero-sum game in Figure in the sense of the norm defined in Eq. 33. By letting denote the probability that PI selects L at information set {ai I2 denote the probability that
Example 2: A game with no Nash equilibria in Figure 2
selects L at information set {az, az), and denote the probability that P2 selects we obtain the payoff functions for and P2 as follows:
U1 (I1, 22. 22 10x122 + 2 + 202y 6x
622
2y + 1,
and Ui 1--- u1, respectively. Recall from [64] that this two two-player zero-sum EFG does not have NE and that the game is neither concave nor monotone. We first run our hierarchy of SOS optimization problems in Eq. (17) at level 2. and attain objective value of SOS₂(1)
10 > 0. Then, we run our program in Eq. (19) with additional constraints that & has to be zero-sum and that the information structure of the EFG has be preserved. To preserve the information structure of the game, we select the monomial basis for the new payoff functions to be precisely the monomial basis that can appear in the original game. We obtain the closest SOS-monotone game G' given by:
w/4 (I1, 22. v) = -rry 8x2y 16x 1622 12y 9,
and tzy = -n The distance between the two games, | ('' which is defined in Eq. 33. is in this case simply [[vec(u]) vec(u() Il and equals 10. On the other hand, the payoff function of this game is multilinear and indeed the zero-sum game is monotone if and only if the term 22 has coefficient symmetrized Jacobian matrix and is, thus, negative semidefinite. Moreover, since the modified game is SOS-monotee monotone,, has a NE in behavioral strategies.
This is line with the experimental results. The modified game Ge has zero
Example 3. We generate two-player polynomial game with the following payoff functions:
un (21, 22, yı. u2) 0.5y2 0.5y/ - 0.5z3 0.5z 9.365y2 9.365yfv2 9.365yi 1.17L.Ev3 0.087982 0.938522.1 9.36542 0. (..725211225
0.5177711 0.5465xm
0.1310 0.1630afv192
0.1308zfv 9.365afa -
9.3652
and
22,11,22,31.000 = 0.5y2 0.5y - 0.5 6. 6.82 - 6.828yf 6.828
0.8335.132 0.8631 0. 0.5324r3u 6.828x 1.091x12295
- 1 0. 0.3886x7v2 - 0.9771x7V122
0.6141xf27 0-8--28.222222 6.828z
P1 and P2 choose their actions (z1, 22) and (31. 32) from a two-dimensional simplex respectively. This game is certified strictly monotone and SOS-monotone, as we run our hierarchy of SOS opti- mization problems in Eq. (17) and obtain objective value -1 at level 4.
Example The game which was constructed is given in Figure
24

---

T.
P1
R
P1
P1
L
R
L
R
P1
P1
P1
P1
L
R
L
L
R
R
PI
P1
PI
PI
PI
P1
PI
P1
L
R
L
R
L
R
L
R
L
R
R
L
R
L
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
P2
r
r
r
r
l
1
r
r
T
1
1
1
r
r
6
6
6
0
6
2
-2
2
4
Figure E.4: Another Zero-sum Game with No Nash Equilibria
Example 5. We construct two-player EFG with imperfect recall where Pl makes six moves before P2 makes two moves. The utility functions for both players are degree-8 polynomials with variables, and we do not restrict the game be zero-sum. The size of the monomial basis is 168, and we randomly generate the payoff functions for P1 and P2 by independently sampling the coefficient of each monomial in the basis from uniform distribution on [-1, 1]. After rounding the coefficients to 2 s.f. for brevity, the payoff function for P1 is:
"1 = otgag:eeee.....g.igogo.oa/aaaaa0
org.://............../.../aaanaa 0.03229/
0,412,0yy
0.93z/1/
0.322ju/y2
0.35z
0bb.rcchhhh0ffciooo--ooloooog110 -0332/22 0.342 +
0.800
0.72x "| +0.22
0.602
0.69 2. 1.g
0.49 orw.
Similarly, the payoff function for P2 is:
25

---

u2(x,
+
0,84:,22//
org. + 0.812/1-
0.94zfm
0.58x14311 + +.600ff333²
-
+0600
+.790 +
0.452fr232 bn 0.59 +.330
0.95% 1i + 0.68272225
0.50 - -2.0 + +.600r
0.800x
0.222 +
1.00x +
+
+ 0.32
0.562 2f +.612 + - -.23xffag1112 -
2 + - - -03 0. 0.19 420l
+000 +.09
3 - -fg_::/000000..00000000000011100
We run our program in Eq. (19) at level 8 of the hierarchy to find the closest SOS-monotone game with an additional constraint that the information structure of the original EFG (i.e., the monomial basis) has to be preserved. This results in a modified game with the following payoff functions:
= 0rgg00000..000000000000000000000 +
0.762201- orgeah/....................nnaan
0.29a
+
0.602/1
+
- -.18:,22-1 -
0.592]22y) - -0.22 -
0.22 + 01 - +
- - -02::111000000177:00000000111110
-0.4c/1222 +
+ 00M0::000000000r0000000000000000 - -.44rr
0.28 - -003::/:.00200333...... -
+.412
-
0 0.430 - 033
0.28 +.552 - -
0. hww.a//wwww..na........o....aaaa
26

---

and
-
+ "1
0.34z
0.262 +0 -
0.262]z]y1 h22.4:141h...0...000000000000010
022:::a.....0....gee..0r02g22222 +.38
002 -0.34
+.12
0.52z +
0.19g
0.562/0 -041m - -
-
0.04x +0 hutp::/:w00000000000000000000000
+008 -.188fff +
0.23x 228
F
Application: Economic Markets
Fisher markets are a special case of Arrow-Debreu markets (6) where competitive equilibria can be efficiently computed for specific classes of utility functions. In particular, Fisher markets are markets with n buyers and m divisible goods, and a certain amount of each good j the market, denoted Cj > O. Each buyer i comes to the market with a budget w/ > O, and their objective is to obtain a bundle goods b, E RT that maximizes their utility function u, : Rmm + R...
Computing competitive equilibria in Fisher markets is known to be PPAD-complete [10] but the works of Eisenberg and Gale 16) showed that equilibrium computation efficient the buyers' utilities are continuous, concave and homogeneous. In recent years, many works have also lever- aged techniques from algorithmic game theory to design algorithms that can compute competitive equilibria in Fisher markets in decentralized fashion [12 [2 13, 21
24). A majority of these prior works focus on Fisher markets where buyers' utilities are linear, quasilinear or Leontief.
In an effort to model more complex utility structures in markets, 22 initiated the first study on linear Fisher markets with a continuum of items. Subsequently, (65] introduced variant of Fisher markets which captures the impact of social influence on buyers' utilities, showing that these markets can be viewed as axeudo-games. a construction from 6 which led directly to Rosen's definition of concave games. [11 also utilized a variational inequality approach to study monotone variants of these games, and presented decentralized algorithms that converge to equilibria. Indeed, SOS- concave and (OS-monotone games allow the study of Fisher markets with social influence for which conoovitymmonotoniciyy is verifiable. particular, an economist who is constructing a model for a market use our proposed methods in two ways. First, they can use the hierarchy in Eq. (17) to verify whether a game is concave or monotone. They can also use the hierarchy in Eq. (19) to search within the class of SOS-concave/monntonn games in order to ensure that their market model satisfies equilibrium existence and even uniqueness.
27

---

NeurIPS Paper Checklist
1) Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
Our claims are proven rigorously, and all assumptions are clearly provided.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2) Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We provide a discussion section that outlines the limitations of the proposed techniques, particularly scalability.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3) Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
Each theoretical result has corresponding proof, either in the main text or in the appendix. Where appropriate, we have also included high-level proof sketches.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4) Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the full code used to obtain our experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specifie model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
model (e.g., large language model), then there should
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5) Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Yes, the code utilizes standard packages and is provided fully.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines bnttps://nips.. cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
haalps.cc/ubliicguuieee SodeeSumeeeieeeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6) Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are given in the main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7) Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification:
The experiments are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
30

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard emror of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should careful not show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8) Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
The code can be run with minimal compute, and details are given in the main text.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g.. preliminary or failed experiments that didn't 't make it into the paper).
9) Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The work is primarily theoretical and the experiments do not have a human
element.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10) Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The work is primarily theoretical, but we mention potential broader impacts of our work in the discussion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
31

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11) Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The results and code in the paper have almost no potential risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12) Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The SumOîSquares package used for our experiments are appropriately cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
32

---

For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13) New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
Our codebase is documented and provided alongside the relevant scripts.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14) Crowdsourcing and research with human subjects Question:
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not utilize any crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15) Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [No]
Justification:
The paper is theoretical in nature and thus has no human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
33

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16) Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core method development (i.e. theoretical results/proofs and experi- ments) of this work did not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, ntn-standard components.
Please refer to our LLM policy (nttps://neurris. cc/Coonfereeccc//222//LL for what should or should not be described.
34


Reviews:
[{"review_id": "d29Ztur5p2", "reviewer": "Reviewer_o8ht", "summary": "This paper investigates the computational tractability of verifying two key structural properties of games: **concavity** and **monotonicity**. These properties are fundamental in algorithmic game theory as they enable the existence and efficient computation of Nash equilibria and underpin favorable convergence guarantees for learning algorithms. The authors establish that checking whether a game is concave or monotone is NP-hard, when the utilities are polynomial functions. Despite this negative result, the authors propose a hierarchy of semidefinite programming (SDP) relaxations (Theorem 3.2) based on the sum-of-squares (SOS) paradigm that can serve as certificates for concavity or monotonicity. They show that almost all (Theorem 3.3) concave or monotone games can be certified at some finite level of this hierarchy. Additionally, they define subclasses (Section 4) of SOS-concave and SOS-monotone games and show that one can efficiently compute the closest such game (in a certain norm) to any given polynomial game. Finally, some of techniques are applied to extensive-form games with imperfect recall.", "questions": "As I explained in the above section, this paper is mainly a theoretical contribution within the specific setting of polynomial programming and sum-of-squares methods. Because of this focus, many broader questions (for example, whether the authors have considered non-polynomial utility functions) are likely to fall outside the scope of the work and would not be particularly meaningful to ask.\n\nAlso, in line 66 “campact” should be “compact.”", "limitations": "Yes. The paper focuses on theoretical contributions and proof-of-concept experiments, and I did not identify significant unaddressed limitations or societal impacts.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is motivated by a clear and relevant question in game theory and optimization. Overall, the presentation is quite clear, and the authors include sufficient technical details to understand the approach. One concern is that parts of the results feel somewhat incremental. Given that the utilities are polynomial functions, the hardness of deciding concavity and monotonicity seems to follow rather directly from existing hardness results on polynomial nonnegativity and convexity. Similarly, the construction of the SDP hierarchy appears to be a natural application of known techniques from the sum-of-squares literature; the idea is simply to use the Rayleigh–Ritz theorem to express the problem of the largest eigenvalue as a maximization problem over a polynomial, which is a well-known result in linear algebra. Overall, the main result (Theorem 3.2) is mostly an adaptation of existing ideas to this setting and does not introduce fundamentally new techniques beyond this adaptation. That said, the work does a good job of tying these concepts together in the context of games, and the examples involving imperfect recall illustrate that the method can have practical implications in cases that are otherwise challenging to analyze.", "was_revised": true, "final_justification": "Overall, I believe the paper presents a meaningful storyline and offers a clear and perspective on the problem. The reason I am maintaining my current score is that, in my opinion, a clear accept would require the introduction of genuinely new ideas and techniques. In contrast, the *majority* of the results in this work rely on known methods, with only minor (or at most moderate) adjustments.", "rebuttal": "We are grateful to the reviewer for the thoughtful comments and questions, and for taking the time to carefully read our paper. We will respond to each of your concerns separately below.\n\n> **Comment 1: The results feel somewhat incremental, and do not introduce fundamentally new techniques.**\n\nFirstly, regarding our hardness result (Theorem 3.1), it builds upon recent work by Ahmadi et al. on the hardness of deciding polynomial convexity. However, their results do not cover monotonicity, and as such, appropriate modifications were required to handle this distinct property. Our goal with this result is not to claim novelty in the specific reduction technique, but to emphasize a foundational computational barrier for the game theory community: although concavity and monotonicity are highly desirable properties for games, determining whether a game satisfies them is computationally hard. Given the centrality of these properties to equilibrium analysis we believe it is crucial to make this hardness explicit before developing efficient certification methods.\n\nSecondly, while prior work on SOS-convexity (e.g., Ahmadi et al. 2013) focused on *unconstrained* settings, our setting involves *constrained* action sets, as is natural in games. Certifying concavity or monotonicity in such cases requires extending the SOS-convexity framework to constrained, semialgebraic domains. To our knowledge, there is no prior work that defines or analyzes SOS-based convexity or monotonicity in this setting, making our extension both necessary and novel.\n\nThirdly, a key theoretical contribution of our paper is the result, proved using non-standard topological arguments, that for almost all monotone games, monotonicity can be certified at a finite level of the SOS hierarchy. This insight is central to our work: it opens a promising path toward tractable and certifiable analysis of games and positions our hierarchy not merely as an adaptation, but as a meaningful tool to navigate the geometric structure of game-theoretic solution spaces.\n\nFinally, our application of this framework to equilibrium computation/approximation in extensive-form games with imperfect recall constitutes a significant contribution in its own right. This class of games is notoriously challenging, with limited tools available for equilibrium computation. Our approach provides a novel and non-trivial bridge between optimization techniques and game-theoretic equilibrium analysis, potentially broadening the applicability of SOS methods in strategic settings.\n\n> **Question 1: Regarding continuous games with non-polynomial utilities.**\n\nWe would like to reiterate that although the polynomial game setup may initially seem restrictive, it is in fact highly expressive and already supports significant applications, particularly due to its connection to extensive-form games, as discussed in the paper. Our proposed toolbox provides a new framework for equilibrium computation and game approximation in a class of problems that are both meaningful for applications and computationally challenging.\n\nWhile we do not explicitly address non-polynomial games in this work, we note that, by the Stone–Weierstrass approximation theorem [1], polynomials are universal approximators of continuous functions. As such, polynomial games form a natural and foundational subclass of continuous games and can serve as surrogates for approximating more general settings. Extending our toolbox to accommodate non-polynomial utilities, in conjunction with approximation results like Stone–Weierstrass, is a promising direction we are currently exploring.\n\n\n*[1] Stone, Marshall H. \"The generalized Weierstrass approximation theorem.\" Mathematics Magazine 21.5 (1948): 237-254.*\n\n\nIf the reviewer is satisfied with our response and their concerns have been addressed, we would greatly appreciate it if they would consider raising their score."}, {"review_id": "0YILJQxOey", "reviewer": "Reviewer_HE7B", "summary": "The paper begins by asking whether it is possible to efficiently verify concavity and monotonicity of polynomial games with semialgebraic strategy sets. To that end, it states and proves a theorem that verifying concavity and monotonicity of polynomial games of degree at least three is NP-hard and proceeds to identify a tractable hierarchy of increasingly strong sufficient conditions for concavity and monotonicity using the techniques of sum-of-squares optimization. Lastly, it applies this hierarchy to extensive-form games with imperfect recall.", "questions": "Theorem 3.3 states that **almost** all monotone games can be certified at a finite level. Do you have any examples or intuition for monotone games that cannot be certified at a finite level?\n\nDo you have any preliminary results on the scalability of the approach to larger EFGs with imperfect recall?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper proves that verifying concavity and monotonicity is NP-hard which is a significant and important result and provides a possible solution to the intractability in the form of hierarchy of sufficient conditions.\nThe proved results apply to a general class of n-player polynomial games which include important class of extensive-form games with imperfect recall.\nThe experiments demonstrate the use of the theoretical framework on a small imperfect-recall game.\n\nWeaknesses:\nThe preliminary section could provide a better introduction to sum-of-squares optimization for readers unfamiliar with the topic.\nThe experiments were limited to a single small imperfect recall game and given the scalability limitations of semidefinite programming, the applicability of the proposed approach to larger imperfect recall games remains unknown.\nWhile the paper is well-written, rigorous and with a clear structure, given the complexity of the concepts discussed, it would benefit from a couple of illustrative examples.", "was_revised": true, "final_justification": "I was already positive on the paper, and I would like to keep my score \"accept\"", "rebuttal": "We are grateful to the reviewer for their support of our paper, and for the insightful feedback and questions. We will respond to each of your comments separately below.\n\n> **Comment 1: SOS preliminaries for unfamiliar readers.**\n\nWe are happy to include a more comprehensive introduction to the SOS techniques in the preliminary section, which should hopefully make the paper self-contained for readers with a game-theory background.\n\n> **Comment 2: Regarding additional, larger experiments.**\n\nWe have carried out three more experiments of larger scale examples, namely Examples 3–5. Example 3 is designed to be a strictly monotone game. Examples 4 and 5 are based on different canonical examples of EFGs with imperfect recall.\n\n**Example 3:** We generate a two-player polynomial game with the following payoff functions: \n\n$$\n\\begin{align} \nu_1(x_1, x_2, y_1, y_2) &= -0.5 y_2^2 - 0.5 y_1^2 - 0.5 x_2^2 - 0.5 x_1^2 - 9.365 y_2^4 - 9.365 y_1^2 y_2^2 - 9.365 y_1^4 - 1.171 x_2^2 y_2^2 + 0.08798 x_2^2 y_1 y_2 - 0.9385 x_2^2*y_1^2 - 9.3654 x_2^4 \\\\\\\\ &\\qquad + 0.7825 x_1 x_2 y_2^2 + 0.5177 x_1 x_2 y_1 y_2 - 0.5465 x_1 x_2 y_1^2 - 0.1310 x_1^2 y_2^2 - 0.1630 x_1^2 y_1 y_2 - 0.1308 x_1^2 y_1^2 - 9.365 x_1^2 x_2^2 - 9.365 x_1^4,\n\\end{align}\n$$\nand \n\t$$ \n\\begin{align}\nu_2(x_1, x_2, y_1, y_2) &= -0.5 y_2^2 - 0.5 y_1^2 - 0.5 x_2^2 - 0.5 x_1^2 - 6.828 y_2^4 - 6.828 y_1^2 y_2^2 - 6.828 y_1^4 - 0.8535 x_2^2 y_2^2 - 0.8631 x_2^2 y_1 y_2 - 0.5324 x_2^2 y_1^2 - 6.828 x_2^4 \\\\\\\\ &\\qquad - 1.091 x_1 x_2 y_2^2 - 1.699 x_1 x_2 y_1 y_2 - 0.4118 x_1 x_2 y_1^2 - 0.3886 x_1^2 y_2^2 - 0.9771 x_1^2 y_1 y_2 - 0.6141 x_1^2 y_1^2 - 6.828 x_1^2 x_2^2 - 6.828 x_1^4. \n\\end{align}$$\nP1 and P2 choose their actions $(x_1, x_2)$ and $(y_1, y_2)$ from a two-dimensional simplex respectively. This game is certified strictly monotone and SOS-monotone, as we run our hierarchy of SOS optimization problems in Eq. (17) and obtain an objective value -1 at level 4. The SDP solving time at level 4 of the SOS hierarchy is 0.05225 seconds on an M3 MacBook Air with 16GB RAM.\n\n**Example 4:** While we are not allowed to add a figure to this response, we construct a two-player zero-sum EFG with imperfect recall which is a larger version of the game in Figure 2. In this game, P1 makes four moves before P2 makes one move. There is only one information set for P1 and one information set for P2. P1 has two actions to choose with probability $x$ and $1 - x$, respectively. P2 also has two actions to choose with probability $y$ and $1 - y$, respectively. Hence, the game tree has six layers including the root and the leaves (outcomes), and the payoff functions are degree-5 polynomials with monomial basis $[x^4 y, x^4, x^3 y, x^3, x^2 y, x^2, x y, x, y, 1]$. After we assign the payoff to each outcome in the game tree, the payoff function for P1 is obtained and given as follows: \n\t$$ u_1(x, y) = - 16 x^4 y + 25 x^4 + 74 x^3 y - 59 x^3 - 89 x^2 y + 49 x^2 + 45 x y - 19 x - 8 y + 3. $$\nA figure of the game tree will be added to future versions of the paper. \n\nWe run our program in Eq. (19) at level 5 of the hierarchy to find the closest SOS-monotone game. Two additional constraints are imposed to retain the properties of the original EFG: a) the modified game has to be zero-sum, and b) the information structure of the original EFG has to be preserved. To preserve the information structure of the game, we select the monomial basis for the new payoff functions to be precisely that of the original game. The following modified payoff function is found, and the new EFG is SOS-monotone: \n$$  u_1'(x, y) = - 5.6 x^4 y - 6 x^4 + 32.8 x^3 y - 22.9 x^3 - 75.1 x^2 y - 4 x y - 68 x - 57 y - 46. $$\nThe SDP solving time for the program in Eq. (19) is 0.008975 seconds on the same MacBook Air.\n\n**Example 5:** We construct a two-player EFG with imperfect recall where P1 makes six moves before P2 makes two moves. The utility functions for both players are degree-8 polynomials with 4 variables, and we do not restrict the game to be zero-sum. The size of the monomial basis is 168, and we randomly generate the payoff functions for P1 and P2 by independently sampling the coefficient of each monomial in the basis from a uniform distribution on $[-1, 1]$. Due to limited space, we will include a full specification of the experiment in future versions of the paper.\n\nWe run our program in Eq. (19) at level 8 of the hierarchy to find the closest SOS-monotone game with an additional constraint that the information structure of the original EFG (i.e. the monomial basis) has to be preserved. We will include the new utility functions in future versions of the paper. The SDP solving time for the program in Eq. (19) is 37.53 seconds, a significant increase from the smaller examples. This further motivates potential future work on scalability (see below).\n\nIn the camera ready version of the paper, we further aim to a) enhance the reusability, modularity and readability of our code to cover a broader range of games with different structures, b) perform new experiments on larger EFG examples with different game tree structures, and c) report code execution times for each experiment in a table, which will include the number of variables and constraints in the SDP. \n\n> **Comment 3: Regarding future work on scalability.**\n\nImproving scalability is a highly active subarea of research in semidefinite/polynomial programming, with many directions proposed in recent years. As mentioned in the paper, DSOS and SDSOS [1] trade off compute for solution quality in SOS optimization. Separately, recent work has utilized low-rank approaches to improve empirical runtimes for SDPs [2-5]. While these more empirical results are not the focus of the present work, we agree with the reviewers that applying these ideas in large-scale games (concretely, even imperfect recall variants of well-studied large EFGs like poker and bridge) would be exciting future work.\n\n*[1] Ahmadi, Amir Ali, 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 (2019): 193-230.*\n\n*[2] Monteiro, Renato DC, 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).*\n\n*[3] Han, Qiushi, et al. \"A low-rank ADMM splitting approach for semidefinite programming.\" arXiv preprint arXiv:2403.09133 (2024).*\n\n*[4] Han, Qiushi, et al. \"Accelerating low-rank factorization-based semidefinite programming algorithms on GPU.\" arXiv preprint arXiv:2407.15049 (2024).*\n\n*[5] Aguirre, Jacob M., et al. \"cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming.\" arXiv preprint arXiv:2505.13719 (2025).*\n\n\n> **Question 1: On Theorem 3.3 and examples of concave/monotone games that cannot be certified at a finite level.**\n\nNote that since all strict concave/monotone games have an SOS certificate at some finite level, these examples can only arise in non-strictly concave/monotone games. Topologically, these games lie on the boundary of the set of concave/monotone polynomial games. However, even small perturbations of the Hessians/Jacobian of a game can bring it into the interior, so in practice (and assuming approximation is allowed), one could perturb the game slightly to ensure strictness, thus guaranteeing finite convergence of the hierarchy. \n\nThere has been a line of work [6-9] studying learning in ‘merely monotone’ games, which are precisely games that are not-strictly monotone and thus cannot provably be certified at a finite level of our SOS hierarchy. The cited works contain several examples, and notably the presence of coupling constraints (see e.g., [7] and references therein) on the players’ joint action set leads to non-strictly monotone utility functions. Clearly, these games are of interest, and it would be crucial to study certification methods with finite time guarantees for this class.\n\n*[6] Grammatico, Sergio. \"Comments on “Distributed robust adaptive equilibrium computation for generalized convex games”[Automatica 63 (2016) 82–91].\" Automatica 97 (2018): 186-188.*\n\n*[7] Tatarenko, Tatiana, and Maryam Kamgarpour. \"Learning generalized Nash equilibria in a class of convex games.\" IEEE Transactions on Automatic Control 64.4 (2018): 1426-1439.*\n\n*[8] Tatarenko, Tatiana, and Maryam Kamgarpour. \"Learning Nash equilibria in monotone games.\" 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.*\n\n*[9] Tatarenko, Tatiana, and Maryam Kamgarpour. \"Bandit learning in convex non-strictly monotone games.\" arXiv preprint arXiv:2009.04258 (2020).*"}, {"review_id": "8zELBRzLmA", "reviewer": "Reviewer_888D", "summary": "The paper proposes hierarchies of sum-of-squares (SOS, a type of SDP) programs that certify concavity (which ensures the existence of Nash equilibria) and monotonicity (wihch ensures unicity) of an input game, where, for each level, the certification problem can be solved in polynomial time. It shows that most (i.e., excluding only a zero-measure set) concave/monotone games can be certified at some level of the hierarchy. It then shows how to approximate a given game with a SOS concave/monotone games in polytime. A case study on extensive-form games with imperfect recall is reported.", "questions": "- Can the authors comment a bit more of how their code can be used?\n\n- Can the authors provide some information on the computing times of their certification/approximation algorithms, possibly w.r.t. the size of the input game and the level of the hierarchy the certification is taking place at? This would be very interesting.\n\n- Regarding Thm 3.3: I just wonder whether some practically relevant games may not be captured due to belonging to the 0-measure set. Are there cases of practically relevant games which are isolated points in this space?", "limitations": "Yes (none to report).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "With this said, I found the paper extremely well written and its results of clear interest. The appendices are also well written, and the last section (market application) is rather nice, albeit a little stylized. The authors indicated that their code is provided as a supplementary file, but didn't comment much (if at all) on this code in the paper, besides (I believe) using it in Sec. 6.1. I wonder if they could tell us a bit more of how their code can be used in practice. Also, no indication of the computing times is reported, besides a (reasonable) comment on the fact that SDPs are easy to solve in theory but not so much in practice). Some extra information on this would be very valuable.", "was_revised": true, "final_justification": "The authors' responses are satisfying.", "rebuttal": "We are grateful to the reviewer for the thoughtful comments and questions, and for taking the time to carefully read our paper. We will respond to each of your concerns separately below.\n\n> **Comment 1: Better explanations of code in paper, and compute time for experiments.**\n\nWe are happy to add more explanations of how the code can be used within the paper itself, including code snippets and accompanying descriptions for ease of use. To give an idea of how the computation time might scale, we have carried out three more experiments of larger scale examples, namely Examples 3–5. Example 3 is designed to be a strictly monotone game. Examples 4 and 5 are based on different canonical examples of EFGs with imperfect recall.\n\n**Example 3:** We generate a two-player polynomial game with the following payoff functions: \n$$\n\\begin{align} \nu_1(x_1, x_2, y_1, y_2) &= -0.5 y_2^2 - 0.5 y_1^2 - 0.5 x_2^2 - 0.5 x_1^2 - 9.365 y_2^4 - 9.365 y_1^2 y_2^2 - 9.365 y_1^4 - 1.171 x_2^2 y_2^2 + 0.08798 x_2^2 y_1 y_2 - 0.9385 x_2^2*y_1^2 - 9.3654 x_2^4 \\\\\\\\ &\\qquad + 0.7825 x_1 x_2 y_2^2 + 0.5177 x_1 x_2 y_1 y_2 - 0.5465 x_1 x_2 y_1^2 - 0.1310 x_1^2 y_2^2 - 0.1630 x_1^2 y_1 y_2 - 0.1308 x_1^2 y_1^2 - 9.365 x_1^2 x_2^2 - 9.365 x_1^4,\n\\end{align}\n$$\t\nand\n\t$$ \n\\begin{align}\nu_2(x_1, x_2, y_1, y_2) &= -0.5 y_2^2 - 0.5 y_1^2 - 0.5 x_2^2 - 0.5 x_1^2 - 6.828 y_2^4 - 6.828 y_1^2 y_2^2 - 6.828 y_1^4 - 0.8535 x_2^2 y_2^2 - 0.8631 x_2^2 y_1 y_2 - 0.5324 x_2^2 y_1^2 - 6.828 x_2^4 \\\\\\\\ &\\qquad - 1.091 x_1 x_2 y_2^2 - 1.699 x_1 x_2 y_1 y_2 - 0.4118 x_1 x_2 y_1^2 - 0.3886 x_1^2 y_2^2 - 0.9771 x_1^2 y_1 y_2 - 0.6141 x_1^2 y_1^2 - 6.828 x_1^2 x_2^2 - 6.828 x_1^4. \n\\end{align}$$\nP1 and P2 choose their actions $(x_1, x_2)$ and $(y_1, y_2)$ from a two-dimensional simplex respectively. This game is certified strictly monotone and SOS-monotone, as we run our hierarchy of SOS optimization problems in Eq. (17) and obtain an objective value -1 at level 4. The SDP solving time at level 4 of the SOS hierarchy is 0.05225 seconds on an M3 MacBook Air with 16GB RAM.\n\n**Example 4:** While we are not allowed to add a figure to this response, we construct a two-player zero-sum EFG with imperfect recall which is a larger version of the game in Figure 2. In this game, P1 makes four moves before P2 makes one move. There is only one information set for P1 and one information set for P2. P1 has two actions to choose with probability $x$ and $1 - x$, respectively. P2 also has two actions to choose with probability $y$ and $1 - y$, respectively. Hence, the game tree has six layers including the root and the leaves (outcomes), and the payoff functions are degree-5 polynomials with monomial basis $[x^4 y, x^4, x^3 y, x^3, x^2 y, x^2, x y, x, y, 1]$. After we assign the payoff to each outcome in the game tree, the payoff function for P1 is obtained and given as follows: \n\t$$ u_1(x, y) = - 16 x^4 y + 25 x^4 + 74 x^3 y - 59 x^3 - 89 x^2 y + 49 x^2 + 45 x y - 19 x - 8 y + 3. $$\nA figure of the game tree will be added to future versions of the paper. \n\nWe run our program in Eq. (19) at level 5 of the hierarchy to find the closest SOS-monotone game. Two additional constraints are imposed to retain the properties of the original EFG: a) the modified game has to be zero-sum, and b) the information structure of the original EFG has to be preserved. To preserve the information structure of the game, we select the monomial basis for the new payoff functions to be precisely that of the original game. The following modified payoff function is found, making the new EFG SOS-monotone: \n$$  u_1'(x, y) = - 5.6 x^4 y - 6 x^4 + 32.8 x^3 y - 22.9 x^3 - 75.1 x^2 y - 4 x y - 68 x - 57 y - 46. $$\nThe SDP solving time for the program in Eq. (19) is 0.008975 seconds on the same MacBook Air.\n\n**Example 5:** We construct a two-player EFG with imperfect recall where P1 makes six moves before P2 makes two moves. The utility functions for both players are degree-8 polynomials with 4 variables, and we do not restrict the game to be zero-sum. The size of the monomial basis is 168, and we randomly generate the payoff functions for P1 and P2 by independently sampling the coefficient of each monomial in the basis from a uniform distribution on $[-1, 1]$. Due to limited space, we will include a full specification of the experiment in future versions of the paper.\n\nWe run our program in Eq. (19) at level 8 of the hierarchy to find the closest SOS-monotone game with an additional constraint that the information structure of the original EFG has to be preserved. We will include the new utility functions in future versions of the paper. The SDP solving time for the program in Eq. (19) is 37.53 seconds, a significant increase from the smaller examples. This further motivates future work to improve scalability in large games (see our discussion of potential techniques in the response to Reviewer HE7B).\n\nIn the camera ready version of the paper, we further aim to a) enhance the reusability, modularity and readability of our code to cover a broader range of games with different structures, b) perform new experiments on larger EFG examples with different game tree structures, and c) report code execution times for each experiment in a table, which will include the number of variables and constraints in the SDP. \n\n\n> **Question 1: On Theorem 3.3 and examples of concave/monotone games that belong on the measure-zero set.**\n\nNote that since all strict concave/monotone games have an SOS certificate at some finite level, these examples can only arise in non-strictly concave/monotone games. Topologically, these games lie on the boundary of the set of concave/monotone polynomial games. However, even small perturbations of the Hessians/Jacobian of a game can bring it into the interior, so in practice (and assuming approximation is allowed), one could perturb the game slightly to ensure strictness, thus guaranteeing finite convergence of the hierarchy. \n\nNevertheless, there has been a line of work [1-4] studying learning in ‘merely monotone’ games, which are precisely games that are not-strictly monotone and thus cannot provably be certified at a finite level of our SOS hierarchy. The cited works contain several concrete examples, and notably the presence of coupling constraints (see e.g., [2] and references therein) on the players’ joint action set leads to non-strictly monotone utility functions. Clearly, these games are of interest, and it would be crucial to study certification methods with finite time guarantees for this class.\n\n*[1] Grammatico, Sergio. \"Comments on “Distributed robust adaptive equilibrium computation for generalized convex games”[Automatica 63 (2016) 82–91].\" Automatica 97 (2018): 186-188.*\n\n*[2] Tatarenko, Tatiana, and Maryam Kamgarpour. \"Learning generalized Nash equilibria in a class of convex games.\" IEEE Transactions on Automatic Control 64.4 (2018): 1426-1439.*\n\n*[3] Tatarenko, Tatiana, and Maryam Kamgarpour. \"Learning Nash equilibria in monotone games.\" 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.*\n\n*[4] Tatarenko, Tatiana, and Maryam Kamgarpour. \"Bandit learning in convex non-strictly monotone games.\" arXiv preprint arXiv:2009.04258 (2020).*\n\nIf the reviewer is satisfied with our response and their concerns have been addressed, we would greatly appreciate it if they would consider raising their score."}, {"review_id": "GBi6dCEllf", "reviewer": "Reviewer_sBN1", "summary": "The work aims to certify concavity and monotonicity in games. First they demonstrate that certification is NP-hard for a class of games with contains imperfect recall EFGs. Then, they develop a SOS hierarchy for certification of concavity of monotonicity, that is polytime solvable. They demonstrate that most games fall into a finite level of this hierarchy, and show how to approximate general games one that falls into this hierarchy, and finally apply this to imperfect recall EFGs (which fall in the NP-hard class).", "questions": "What are some directions that build on top of this work? Is it primarily tackling the scalability of the proposed SDP formulations?", "limitations": "The authors address limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The work is well-written and tackles an important problem, given that tractability of equilibrium computation is largely captured by concavity and monotonicity. Their story for the paper is coherent: they set out to solve certification, demonstrate that certification is not necessarily tractable in polytime (unless $\\mathsf{P} = \\mathsf{NP}$), develop a polytime computable SOS hierarchy, show that this is generic for monotone games, and then demonstrate a sequence of SDPs that correspond to the closest monotone games in levels of the hierarchy, and whose limit corresponds to the closest monotone game (under distances, including norms), and finally they apply this framework to EFGs with imperfect recall.", "was_revised": true, "final_justification": "I maintain my assessment. The authors satisfactorily answered my question about future directions.", "rebuttal": "We are grateful to the reviewer for their support of our paper. We will respond to your question below.\n\n> **Question 1: What are some future directions of our work?**\n\nWe believe that scalability (as described in the responses to other reviewers) is one of the key future directions for this line of study. Another interesting direction is how to utilize the SOS framework for other applications. In EFGs, we are able to capture the information structure of the game (i.e. the monomial basis of the corresponding polynomial game) within the SDP, which allows us to find the closest SOS-concave/monotone game by changing the payoffs but not the game tree. A crucial question is how to perform similar analyses for other game theoretic settings while maintaining the appropriate structural properties.\n\nThere are also several open theoretical questions. Characterizing the measure-zero set of non-strictly concave/monotone polynomial games would be helpful to understand the conditions under which our finite convergence guarantees fail. The proof of Thm 3.3 also relies on topological arguments tailored to polynomial games, and it would be interesting to see if similar results extend to other classes of continuous games. Finally, our techniques open a line of inquiry about the efficient verification of other desirable properties in games."}]

Author rebuttal:

Meta-review: This paper investigates the computational complexity of verifying concavity and monotonicity in games. The authors prove that verifying concavity and monotonicity of polynomial games of degree at least three is NP-hard, and identify a tractable hierarchy of increasingly strong sufficient conditions for concavity and monotonicity using the techniques of sum-of-squares optimization.  They also apply this hierarchy to extensive-form games with imperfect recall.  The reviewers find the results meaningful, and the presentation clear.  It is noted that some results appear to build on existing ideas, but the way these concepts are organized appears insightful.  There's also room for improvement concerning readability by people unfamiliar with the topic.  We encourage the authors to take the constructive comments into consideration and further improve the paper.
Decision: Accept (poster)