The Complexity of Correlated Equilibria in Generalized Games
Authors: Martino Bernasconi
Matteo Castiglioni
Andrea Celli
Gabriele Farina
Venue: NeurIPS 2025 poster ()
Keywords: computational complexity
PPAD
correlated equilibrium
generalized games
equilibrium
game theory
nash
Primary area: theory

Abstract: Correlated equilibria —and their generalization $\Phi$-equilibria— are a fundamental object of study in game theory, offering a more tractable alternative to Nash equilibria in multi-player settings. While computational aspects of equilibrium computation are well-understood in some settings, fundamental questions are still open in _generalized games_, that is, games in which the set of strategies allowed to each player depends on the other players' strategies. These classes of games model fundamental settings in economics and have been a cornerstone of economics research since the seminal paper of Arrow and Debreu [1954].
Recently, there has been growing interest, both in economics and in computer science, in studying correlated equilibria in generalized games. It is known that finding a social welfare maximizing correlated equilibrium in generalized games is NP-hard. However, the existence of efficient algorithms to find _any_ equilibrium remains an important open question. In this paper, we answer this question negatively, showing that this problem is PPAD-complete.

The Complexity of Correlated Equilibria in Generalized Games
Martino Bernasconi
Matteo Castiglioni
Bocconi University
Politecnico di Milano
martino. bernasconi@une www.:oniiiiuiioccooi.io...c
matteo.. castiglion wetelliinnipiiiiiii ipolimi.iiiiii.m imi.it
Andrea Celli
Gabriele Farina Massachusetts Institute of Technology
Bocconi University
andrea. cellielllleee wwwlllli@unnibeecc www.bnccoo.....oo.oomommm....... itt
gfarinašmi t.namiiteddu
Abstract
Correlated equilibria- and their generalizations known æ-equilibria- fun- damental object of study in game theory, offering more tractable alternative to Nash equilibria in multi-player settings. While computational aspects of equilib- rium computation are well-understood in some settings, fundamental questions are still open in generalized games, that is, games in which the set of strategies allowed to each player depends on the other players' strategies. These classes of games model fundamental settings economics, and have been a cornerstone of economics research since the seminal paper of Arrow and Debreu [1954]. Re- cently, there has been growing interest, both in economics and in computer sci- ence, in studying correlated equilibria in generalized games. It is known that finding a social welfare maximizing correlated equilibrium generalized games is Na-hard. However, the existence of efficient algorithms to find any equilibrium remains important open question. this paper, we answer this question in the negative, showing that this problem is PPAD-complete.
Introduction
Game Theory a fundamental tool to study the interaction between rational agents. From an application point of view, it has found important applications such as training GANs [Goodfellow et al., 2020], auctions [Nisan et al., 2007], and superhuman performance in strategic games [Brown and Sandholm, 2019, FAIR et al., 2022]. In series of papers, originating from Papadimitriou [1994] and culminating Daskalakis et al. [2009], Chen et al. [2009], the problem of computing Nash equilibrium in multiplayer games proven to be complete for the complex- ity class PPAD, which contains problems for which no efficient algorithm is known. On the other hand, correlated equilibria [Aumann, 1987], coarse-correlated equilibria [Moulin and Vial, 1978], and their generalization known as Ø-equilibria [Greenwald and Jafari, 2003], are a relaxation of Nash equilibria, and provide computationally tractable alternative Nash in most instances.
The seminal result of Nash [1951] for the existence of equilibrium in non-cooperative games was extended to generalized games (also known as pseudo-games abstract economies) by Arrow and Debreu [1954] and Rosen [1965]. In these games, the set feasible strategies of one player depends on the strategies played by the other players.
Coupled constraints between players model various applications involving finite resources, where consumption depends on the joint actions of the players. For example, generalized games have been applied to dynamic pricing [Adida and Perakis, 2010], electricity markets [Hobbs and Pang, 2007]. and Fisher markets [Brânzei et al., 2014, Conitzer et al., 2022]. A particularly relevant example of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

joint constraints is bidding in repeated auctions under budget constraints, where budget consumption depends on the joint bids of all players. is well known that when all players follow no-regret strate- gies, their average play converges to correlated equilibrium [Cesa-Biande online advertising, where many companies deploy automated bidders that act as "cost-aware" regret minimizers on behalf of advertisers [Balseiro and Gur, 2019, Aggarwal et al., 2019], it becomes par- ticularly important to ask whether similar convergence guarantees hold for "cost-aware" no-regret algorithms (such as the algorithms presented in Mannor et al. [2009], Mahdavi et al. [2012]).
and Lugosi, 2006]. In
Thus, an important and natural question is to determine if there are efficient algorithms that compute correlated equilibria in generalized games. While Bernasconi et al. [2023] proved the computational infeasibility of computing social welfare maximizing correlated equilibrium in generalized games, the complexity of computing any equilibrium remains open (see also Zhang et al. [2025]). In this paper, we resolve this open question.
1.1 Contributions and Overview of Techniques
The main contribution of this paper is to show that the problem of computing an approximate t- equilibrium in generalized games (as formalized in the CONSTRAINED-S B-QUI---RUUUUUUUUU problem in Section 3) is PPAD-complete. The hardness holds for approximation factors that are inverse- polynomial in the instance both in (i) games with two players, and (ii) games with an arbitrary number of players even for constant number of actions and constraints per player. By providing this characterization, our paper puts to recent line of inquiry in the literature [Bernasconi et al., 2023, Zhang et al., 2025].
At a fundamental level, the question of the complexity of correlated equilibria in generalized games boils down to the tension between two opposing forces:
On the one hand, the introduction of correlation as opposed to the independence between the play of different players required by Nash equilibria- is major driver of computa- tional feasibility. For instance, while Nash equilibria are believed to be computationally in- tractable, correlated solution concepts [Aumann, 1987] are typically computable in polynomial time, even in games with exponentially many actions [Papadimitriou and Roughgarden, 2005, Farina and Pipis, 2024, Daskalakis et 2024].
2. On the other hand, the introduction of coupled constraints often has adverse effects on computation [Daskalakis al., 2021, Papadimitriou et al., 2023, Bernasconi al., 2024, Anagnostides et al., 2025], even when the constraints are simple, egg., when they define poly- tope in the joint strategy space.
Thus, a natural and fundamental question that tries resolve this tension is the following:
Which of the two forces prevails? Does correlation remain beneficial in the face of constraints? Or are constraints so detrimental to push the complexity of correlated equilibria in generalized games to the realm of intractability?
We resolve this question by showing that correlation is not sufficient relaxation in the presence of coupled constraints. We prove this result by a reduction from the problem of computing Nash equilibria in polymatrix games. At an intuitive level, could say that the computation of linearly constrained correlated equilibria is indistinguishable from the computation of unconstrained Nash (i.e., independent) equílibria. In other words, the combination of correlation and constraints can simulate independence without constraints.
At the technical level, our main tool is to introduce a "left" and "right" copy of each player in the polymatrix instance, thus creating two teams of players. Each player on one team then plays only with players on the opposing team in team zero-sum game. We then exploit the constraints to couple the players of the left team to the players of the right team by asking that their marginals coincide. This allows us essentially remove the terms that are linear in the correlated strategy and only keep the ones that are linear in the marginals (which now resemble the ones of Nash equilibria).
One additional implication of our result is that the quasi-polynomial time algorithm for computing approximate oeequilibria of Bernasconi et al. [2023] is tight. Indeed, under the Exponential Time Hypothesis for PPAD (introduced by Rubinstein [2017]), we show that the problem of computing

---

(coarse) correlated equilibria in generalized games requires quasi-polynone time, even with constant number of players and constant violation of the incentive compatibility constraints.
Furthermore, we emphasize that although numerous works have established positive convergence guarantees for regret minimization in the unconstrained setting [e.g., Hart and Mas-Colell, 2000], our results demonstrate that no efficient no-regret algorithms can, in general, converge to constrained correlated equilibria. This impossibility has broad implications for systems of constrained no-regret learners, as it precludes convergence unless specific properties of the problem are exploited. A con- crete example that has recently attracted sigmificant theoretical and empirical attention is that of In- ternet advertising platforms, where automated bidding agents are typically operated by the platform itself (see, e.g. [Agarwal et al., 2014, Balseiro and Gur, 2019, Balseiro al., 2021, Paes Leme et al., 2024]). In such environments, convergence to an equilibrium is often desirable since it promotes sta- bility, predictability, and alignment with the advertisers' individual incentives. Our result, however, shows that this goal cannot be achieved in a "black-hox" manner. To design autobidders with con- vergence guarantees, one must develop algorithms that exploit the specific structural properties of the problem, since general-purposs approach can ensure convergence in this setting.
2 Preliminaries
2.1 Multi-player Games and (-equilibrium
We consider an rt-laaeer game. Each player has a set A = [E] of actions, and for each player E [n] and each tuple of actions E A == A", the utility of player is u;(a) [o, 1).' A $- equilibrium is defined on correlated strategies E A(A). In particular, a mediator samples actions = (0.,...., an) ~ 2 and communicates to each player i its own action a,, Conditioned on the action recommendation, each player can now decide how to deviate. In particular, each player can pick a function é E that prescribes its deviation from a set of functions Ø. More specifically, each function & E & maps each action each function & can be represented by & x E-dimensional right stochastic matrix on which each row corresponds to specific action, i.e. o(a. b) is the probability of playing b when the player is recommended action a. By applying a deviation á to a correlated strategy z the i-th player induces distribution d o; z A. Formally, for all a (a,, a -)) E A we let
AA into randomized action ((a) E A(A). Note that
a=)
(o o 2) Ed(h (b, a:) a.).
Morcover, for function F A R and distribution A(A), with abuse of notation we write Fzz) to denote the expected value of F under the distribution z, i.e. ΣaEA F(a)=(a). For instance, we denote the expected utility of player under distribution as u;(z) EneA =())u.(a).
An e-U-equilibrium is a correlated distribution over strategies such that
(=(=) 2 u.(0 o, 2) - Vi E [m]] & $
We call -e-quilibrium 0- 0-0-equilibrium. In Appendix A formally write the of functions PCn and &ecr, which define correlated (CE) and coarse-correlated equilibria (CCE), respectively. Intuitively, CCEs deviations are deviations that cannot depend the recommended action, while CE deviations are a larger set where deviations could be different based on the recommended action.
2.2 Constrained d-equilibria
To model situations in which there are common shared resources, we introduce costs that depend on the joint actions of all players. In particular, each player i E [n]] has costs {C/ (a) [-1, 1| associated with each tuple of action a E A. For any 2 0, we define as Sy the set of correlated strategies that are y-safe (in expectation) for the i-th player, i.e.
S = { A(A) (²) <D
Aj [m].
Intuitively, S guarantees that the expected cost of player i is at most for each of its resources. Moreover, we define the set S Sj as the set of strategies that are v-safe for all players. For
'Given integer i N, denote with the set (I....,
3

---

each 2 E S and player E [n]] we can define the set of safe-deviations, i.e.,
q (2) (6 + (Ø o; 2) E S.)-
To guarantee that the game is well-defined and the existence of solutions, we make the following mild assumption. This assumption requires that all agents always have a deviation that ensures that cost constraints are satisfied. Formally, for all E ((A) and E [n]. it holds that t (z) & 0. This assumption is required to guarantee that players always have safe strategies, and it is common in the literature. Bernasconi et al. [2023] proved existence (but not PPAD-meebership with a stronger notion related to strict feasibility, which was then removed in subsequent works [Boufous et al., 2024, Ni et al., 2025]. This assumption is generally satisfied, as it is reasonable to let players have a void action with zero utility and zero cost, irrespective of other players' strategies. We say that correlated strategy E S" is Constrained (e, ----equiiibrium it holds that uz(z) 2 uy (d)o=)) for all players E [n] and deviations in @ E (z). Intuitively, ignoring the technicalities related to the relaxation v, correlated strategy is constrained e- e-I-equilibrium if is safe for each player and each player cannot carn more than by applying a safe deviation to the correlated strategy z.
2.3 Polymatrix and team games
Polymatrix games are type of multiplayer games in which the n players interact only with a subset of other players and the game between any two players is a bi-matrix game. Formally, we can introduce the following computational problem:
POLYMATRIE
Input: a graph G = EV, matrix A E [0, k0 for each (i,j) E E, and an approxima- tion e > 0.
Output: vectors I2 E ((H)), E V such that:
Σ r. A Z
Σ
AT - Vi V, E ((A)).
JEV:
JEV:(L,)EEE
In a breakthrough result Rubinstein [2015] (later improved by Deligkas al. [2022]) proved con- stant inapproximability of POLYMATRIX for constant number of actions and degree of the graph.
Theorem 2.1 (Rubinstein [2015, Theorem I]). There exists a constant e" such that POLYMATRIX is PPAD-comples even when the graph has degree 3 and each player has 2 actions.
An important subclass of polymatrix games are two-team zero-sum games, in which V can be parti- tioned into two teams such that: (i) each edge between players of different teams is zero-sum game, and (ii) each edge between players of the same team is a coordination game. If one of the teams has no internal coordination edges, these games are called two-team polymatrix zero-sum game with independent adversaries [Hollender et al., 2025]. Here we also consider the case in which there are no coordination games in between both teams, i.e., the graph G is fully bipartite. We call these two- team polymatrix zero-sin game with independent teams. These games are special cases of zero-sum polymatrix games that admit LP-based polynomial-time algorithms [Cai al., 2016].
2.4 PPAD-hardness and Total Problems
The class PPAD is an important subclass of total search problems i.e., TFNP, which includes search problems with solutions that can be checked in polynomial time. PPAD was introduced by Papadimitriou [1994] to capture problems whose totality is guaranteed by parity-like arguments and, equivalently, by fixed-point arguments such as Brouwer's. ccomeccmplete problems are likely to be solvable in polynomial time. This is also supported by several lower bounds based on cryptographic assumptions [Bitansky et al., 2015, Garg al., 2016, Choudhuri et al.. 2019].
Moreover, for ease of presentation, we use a more manageable class of total problems, as we allow for promise problems, i.e., problems whose totality is guaranteed only if the instance satisfies some additional properties (promises) whose validity is not clear how to check in polynomial time."
Formally, to guarantee the totality of our problems we should accept as solutions violation of the promise (see, Fearnley et al. [2020, 2022]. Hollender [2021] for in-depth treatment of promise- preseevingeeee reductions.

---

3
Reduction from POLYMATRIX to SENSTRAINED---EEULLIEE
We define computational search problem associated with constrained @-equilibria.
Input: e' 0, an utility function u, A [0, and m cost functions C.
[-,, j E [m] for each player i, and a set of possible deviations & (given as a list of linear inequalities, defining a polytope of right stochastic matrices) with A E R and E R
Output: vector S" such that (=) 2 ui(d 2) e'' Vi E [n], (f)..
Promise: It is promised that - (z) * for all E A(A) and i e [n].
Formally, to fix representation of the output, we think of z as a mixture of product distributions. Notice that such a representation is essential to guarantee a representation polynomial in the support and independent of [.|].
In the following, we will provide reduction from POLYMATRIX CONSTRAINED-P- EQUILIBRIUM.
Intuitive high-level idea of the proof To give high-level intuition of the reduction, sketch a simplified reduction from the problem of computing Nash equilibria in two-player general-sum can write feasibility LP for coarse
games. Given general-sum game A, B [0, 1] 1] x
correlated equilibria as follows:"
A(2) 2 A ((k))
(Ia)
Find such that:
B(2) 2 B 8) AD A(E))
(1b)
E A(A))²
we were to add a constraint forcing to be a product distribution, i.., == x By then Equation (1) would turn into feasibility problem whose solutions are Nash equilibria of A, B. This (non-linear) constraint is exactly what makes computing Nash equilibria hard. Thus, ideally, we would like to impose constraints to force the correlated strategy to be product distribution. However, the constraints we can employ are linear z, and we cannot follow this idea directly.
By observing Problem 1, we can see that the right-hand sides of the two incentive compatibility (IC) constraints (1a) and (1b), are linear only in the marginals. Thus, it could be convenient to: (i) impose the costs to the player such that the marginal of the player copies the marginal of the player, i.e., 2-1 = z-2 (note that this is linear constraint in 2), (fi) take A -B so to erase the terms linear in when summing the two IC constraints of Equation (1).
It easy to see that, due to (i), we also have that the deviations admissible to the player are just {2-1}. On the other hand, there are no costs on the second player, and thus the deviations ý are free.
Define h 2 2-2. Then summing (la) and (Ib) we obtain
Due to (1i)
h Bh 2 h Bÿ Vğ E ((+)). is easy to choose such that is PPAD-hard find a solution to the right-hand side inequality above. For example,
A(=) + B(=) 2 A(h & h) + B(h @ ū)
A
choose B
for another two-player general-sum game
BT
A, B. This choice introduces two additional players for each player of the original game, essentially
creating two opposing teams playing zero-sum game.
The above construction is informal and skips many of the technical challenges, such as the fact that we are only allowed to use constraints that are satisfied approximately. Also, we derive more general result and broader consequences by reducing from POLYMATRIX instead of computing Nash in two-player games (see Section 3.2). This is indeed one central part of the formal reduction that we will present in the next section.
Given a graph G = (V, E), we denote with deg(G) the maximum degree of graph G. Then, the main result of this section reads as follows:
We denote with 2-; the marginalization of with respect to the i-th player.
Note that A(z @ v) x. Ay.
5

---

Aha
(((Am))
01.
CR
(44.5
A4a
44.6
b
bR
(44e0)
(A
1
C1
CR
Properties of the instance The instance of BUISTRAINED---EEQURE construction has twice many players the original instance, and the same degree number of ac- tions player & as the original instance. Moreover, the CONSTRAINED-94 EANSTRAINDDDQEEUUIIBBBUB EQUILIBRIUM instance (a) Example POLYMATRIX instance with three players V = {a, b.
CONSTRAINED-PP- EQUILIBRIUM with M = {al, by a. and Nr = {ax, by. cx)-
(b) Conresponding
instance
On the edges, reported the matrix corresponding the utilities of the players. Col- ors indicate the row player of the bi-matrix game and the player associated with the utility that is associated with the matrix.
Figure 1:
Theorem 3.1. There is polynomial-time reduction from instances G = (V.E) of POLYMA- TRIX with n players, actions per player, and approximation e to instances of CONSTRAINED- -- D-EQUILIBRIUM with approximation è' O(5) and y O degle and CCE deviations.
3.1 Proof of Theorem 3.1
Construction Given an instance POLYMATRIS with graph G (V, matrices (A (..))E {AA)))E)) and approximation we build an instance of BEASSTRRINEDD--EQUIIBBBERE
as follows:
Set of players N = .N. UR, where Ni. {úL: i V and M = {iR i V};
For each player in / the set of actions = [k]] as in the original POLYMATRIX instance;
For every i E V, the utility of player E Ni., under an action profile E AWV,, is defined as uig (a) = - ( (A (a ajz), while the utility of player iR E NR under action profile a is Wig (a) [H(j)EE A aj,);
The set deviations &CCE (see Appendix A for a definition);
For each player it there are 2k costs. For each j E [2k]] let
21 < k) 2T k)
if aa = mod k and ai + j mod k if aig Hj mod and oz = mod k otherwise
C2 (a)
For more intuition on the construction, we refer to Figure
resulting from this
guarantees that each player has most 2k costs.
The game resulting from the reduction teams. Indeed, we implicitly defined a graph = (N,, E) which has edges only between players NL and Ng. More specifically, an edge is included between it E ML and jR AN if and only there was an edge between and j in the original POLYMATRIX instance. Moreover, the game is zero-sum. Indeed, for each couple players i, ML and JR NRg, the utilities given by payoff matrices hh. - and Á A respectively. Finally, the costs of player is only depend on the actions of player ig.
two-team polymatrix zero-sum game with independent
Summing the utilities of all players each side, get the following lemma:
Lemma 3.2. For each tuple E A, define the utility of the "left team" un.(a) = Eiev Ui (a) and the utility of the "right team" as ug(a) Σiev (a). Then (a(a) = -u((a).
Marginalization Before delving into the correctness of the reduction, we need to introduce some additional notation that helps bridge between correlated equilibria and Nash equilibria. For any

---

subset of players N S N and any tuple of actions a E A, we denote with 4x the actions pertaining players in N. We also denote with -N A \ the complement of A.
Now, we can define the marginalization of the correlated strategy z restricted set of players N by summing over the actions of all other players. Formally, we write
" m = Ea_ REANNI z(ax; a_x))
We then consider m m²x(=) as vector indexed by all the tuples ax A which, clearly, is distribution over A
Effects on the costs We now prove the main properties related costs. Intuitively, every safe strategy guarantees that the marginals of players it are close to the marginals of the players iR for each i E V. In particular, each action j has two associated costs C and C that force the marginal of the first player to mimic the marginal of the second player. Namely,
Lemma 3.3. Given z E S and E V, it holds that |m (2) - mia (=)] S Moreover given a z E ((A and an i E V, the set of safe deviations of player in is (z) = {0i 1 mig (2) I 0), which guarantees $ (z) + 0.
Correctness We recall that k |A| the number of actions of each player and the number of players. Take any S" that is a solution to BESSRRIIEDD---OUUIIRRR combining it with Lemma 3.3, we get that for E V holds:
[V is
Ui (2) 2 Wi, (Ta, & ma)((())) -C' VY,. E A(A): || - mia (2)llo 0O
(2)
and
uin (z) Z Win (Jin @ mn (=)) - Vaig E A(A).
Notice that we can write explicitly the right- side of Equation (2) as
Un (Rrg 2 mmna = Σ (A m (=)a(=)= = Σ
mia m2x()) (z) A Fins
JULEE
We then specialize Equation (2) for Fi, mia (2) and over all i E V. This results in the following inequality (where we also swapped the identity i and j in the last equality):
(2)
Σ
mja(e) A nd' = Σ
mig ( (2) nc'.
(4)
(FJ)ER
(KJER
Similarly, we analyze Equation (3) and use the first statement of Lemma 3.3:
uR(z) 2
Σ
Win (Nin maniia (=)) ne'
VEV
Σ
Finn T
('AWmj m))()))))))))))))))()) - -ne'
(.)EEE
Σ (iJER
ATA (2)
Σ Σ I
A -mja
(z)) -maa()))
ne'
BEV (((jE)ER
Σ (K.)EE
(nkk n( +6') V(igliEv E A(A)".
(5)
Summing Equation (4) and Equation (5), and using the fact that ux(2) -u (2) from Lemma 3.2, we obtain that mig T A N
Σ
A (z) nukk deg(G)+22) Yaughiv E A(A).
(J)EF
(JJEE
Which, for all players E can be specialized to
Σ (2) A A 2 Σ
J A nevl Voi E A(A),
J(AEEE
by setting Jij mjx (z) for all j +i
Thus, taking h; mig (z) for all players E V, and e' c/4n and </(2nk deg(G) we prove that hy is solution of POLYIIARIX with approximation
7

---

3.2 Implications of the PPAD-hardness
The class of deviations used in the reduction of Theorem 3.1 PCCE, which subset of the deviations of ceg. thus, our hardness works also for correlated equilibrium in generalized games.
We now discuss some special cases in which our problem is PPAD-hard. POLYMATRIX is PPAD-hard even when 6, deg (G), k = ((1) (see Theorem 2.1). Thus, Theorem 3.1 implies that CONSTRAINED-Q-EQUTI IRRUM is hard when each player has m ((1) constraints and actions, when the slackness / and approximation e are On=
Moreover, the instances resulting from our reduction form bipartite graph and, more specifically, two-team zero-sum polymatrix game with independent teams, as defined in Section 2.3. Importantly, for this case of two-team zero-sum polymatrix game with constraints, there are known LP-based polynomial-timg -iie algorithms [Cai et al., 2016]. It is an interesting open question whether is possi- ble to prove hardness for constant approximations, arbitrary number of players, constant number of actions per player, and constant number of constraints per player.
We can also consider the bi-matrix instance of POLYMATRI in which we have only 2 players and an arbitrary number actions k. This shows that our problem PPAD-hard even with a constant number of players when é' O1) and O).
Moreover, assuming the Exponential Time Hypothesis for PPAD (namely that solving the canoni- cal problem OND-OOF-HE-LLIEE requires exponential time), Rubinstein [2017] showed that it must take at least glog+==()) time to find constant approximation for any k x le bi-matrix game. This imposes quasi-polynomin lower bound on the stant and po)y(k-1). On the other hand, Bernasconi et al. [2023, Corollary 4.3] provides quasi-polynomial time algorithm for constant approximation and a constant number of players in (log(h) time, thus essentially closing the gap.
problem for con-
4 PPAD- -mAmmemmbrrship
We now introduce a computational problem related to quasi-variational inequalities that will serve as the basis for our membership reduction.
QUASIVI
Inputs: G, L. 0, 0, circuit implementing a G-Lipschitz function RRd د Rdd and two circuits implementing L-Lipschitz continuous matrix valued function A [0, 1] Rnxd and L-Lipschitz continuous vector valued function b R - Id defining the corre- spondence (z) = {a 1] A()) x $ b(2) vla)."
Output: point E (z) such that
- -c, for all ă E Qx()).
Promise:
The correspondence is promised to satisfy Qo(2) + 0 for all x E [0, 1]d, the function F is G-Lipschitz and the correspondence Qu(2) is L-Lipschitz.
"We say that matrix-valued function A [0, 1] + Baxd L-Lipschitz the function <> A(3)² is L-Lipschitz for every [0, 1]" in the fy-norm.
Theorem 4.1 (Bernasconi et al. [2024, Theorem 3.4J). QUASIVI PPAD.
To prove that CONSTRAINED EQUIILIBIIUUMM is total and more specifically in PPAD we reduce it QUASIVI. Our idea is restrict to Nash-like equilibria with CCE deviations, i.e., restrict to product strategies X Ps E A(A)", where P; E (AA). We will show that these are a subset of constrained --equilibria for any of deviations +.
Proposition 4.2. CONSTRAINED - EQUILIBRIUM PPAD.
Proof. The proof hinges on showing that for any instance of CONSTRAINED -- EQUILIBRIUM with CCE deviations: (i) we can build an instance of QUASIVI in polynomial time and (ii) from the solution of QUASIVI, we can build solution to the original instance which a product distribution. We show that considering CCE deviations is enough, since these deviations are the most expressive when applied to product distributions. Indeed, the image

---

of any product distribution under the set of deviations PeCE is superset of the image under any possible set of phi deviations. Formally, given a player E [n], a product distribution p = X seimn] Pi+ a set of deviations ②, and a deviation @ E Q, there exists a marginal ii of the i-th player such that Φ p @ p-i. In particular, we can take p. (AA) such that p:( Enea o(b, ())p:(b) for each a; A. Then, a CCE deviation can replicate the marginal P: by taking & E PCCE such that each row of the stochastic matrix is p.. This also proves that there exists safe CCE deviations for every product distribution, from the existence of a safe deviation of the original set of deviations Q.
Indeed, any instance of CONSTRAINED- --e-------eee EQUILIBRIUM is guaranteed by assumption to have the set of feasible deviations non-empty for each correlated distribution. As a direct consequence of our previous observation, we have that the set of feasible deviations in CCE is not empty when consid- ering only product distributions This can be proven by observing that the strategies obtained by applying deviations from any set & to product distributions form subset of the strategies obtained by applying CCE deviations.
To define an instance of QUASIVI, we define a correspondence Q R = R and an operator : R + IR satisfying the appropriate conditions of the QUASIVI problem. Namely, we need the correspondence (22 to be linear for every 2 and with Lipschitz coefficients, Moreover, we also require that the operator F is Lipschitz."
Construction
Since we only consider product distributions, En numbers suffice to uniquely specify the distribution.
Thus, can "flatten" the product strategies p iie(n] Pi into [p] ... [p,]] (equivalently
is the flattening of p) and consider the correspondence Q(2) = {a E [0. 1) A(2) S b(²) }. that encodes both the costs and the simplex constraints. Formally: A()) = diag (s)..... An()) e
R=(m+2) x In and 6(2) = [62(2)
[2) E Rn)m++2), where (2) is a block matrix (2) =
(3)
Tmm 1
IR (2)x+ 6,(2)
E 1m+ and Dz( E gmxt is such that
-
[0mxe, Di( ... 0mxel= < Om = (p. S sV0 E [m].
The explicit definition of (2 is cumbersome due to the flattening notation and we defer it to Appendix C.I.
It is easy to check that E Q(z) if the corresponding "unflattened" product strategies satisfy the simplex and cost constraints for each player. The next claim shows that the instances created by our reduction satisfy the promises needed by the QUASIVI problem.
Claim 4.3. The functions ā + A(ā)² and 2 + b(2)T& defining the correspondence are L-Lipxchitz for every E [0, 11tT where L has a represenlation polynomial in the size of the instance.
Now, we build the operator F of the QVI by stacking the gradients of the utilities. For any product distribution p = Ssemm Ps and flattening z we define, with slight abuse of notation, F(z) == (-V Un (p) .p.................... ..... - pm. un (p)). The following claims that the operator F satisfies the properties required by the QUASIVI problem. This shows that the constructed instance satisfies all the promises of the QUASIVI problem.
Claim 4.4. The operator F : [0, 11TM polynomial in the size of the instance.
[0, 11 is G-Lipschitz where G has a representation
Correctness For every vector r E [0, 1 define y. = Te((--))..... which effectively divides (and "unflattens") the vector r in components of length E each corresponding to the strategies of the i-th player. We will use this notation to reconstruct a solution to CONSTRAINED - E-UULLBBIUUM from solution z of QUASIVI. Indeed, take solution z of the QUASIVI problem, instantiated with e' and yf later to be defined. We now claim that the renormalization p Eie kp (where
'Crucially, the Lipschitz constants are inputs of the QUASIVI problem, and thus, we need to make sure that they have polynomial representation in the original CONSTRAINED & D-EQUILLBRIUN instance.

---

= >==2\/1<=11) (1) is solution to CONSTRAINED 4- EQUILIBRIUM." The only tricky part is simply handling the fact that all the constraints are only approximately satisfied.
Claim 4.5. Let v/ = m 2: 2n e²) and = {{ - -n/),, then is such that
(p) 2 (i @ p-:) Vp: E 4p(p)
and p E S
This concludes the proof, as it shows that p (which is product distribution) is CONSTRAINED- G-EQUIIIRIUUM for CCE deviations, with approximation and slackness v and thus for any set +b
Acknowledgments
The work of MB and AC was partially funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
MB and AC are supported by an ERC grant (Project 101165466 PLA-STEER) and by MUR PRIN 2022 project 2022R45NBB funded by the Next Generation EU program. MC is partially supported by the FAIR (Future Artificial Intelligence Research) project PF0000013, funded by the NextGenerationEEU program within the PNRR-PEL-I scheme (M4C2, investment 1.3, line Artifi- cial Intelligence) and the EU Horizon project ELIAS (European Lighthouse of AT for Sustainability. No. 101 120237). GF is supported in part by the National Science Foundation award CCF-2443068. ONR grant 2000142512299 and an AI2050 Early Career Fellowship.
The authors also thank Tingting Ni for helpful discussion and suggestions.
References
E. Adida and G. Perakis. Dynamic pricing and inventory control: Uncertainty and competition. Operations Research, 58(2):289-300 2010.
D. Agarwal, S. Ghosh, K. Wei, and S. You. Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1613-1619, 2014.
G. Aggarwal, A. Badanidiyuru, and A. Mchta. Autobidding with constraints. In Web and Internet Economics: 15th International Conference, WINE 2019, pages 17-30. Springer, 2019.
I. Anagnostides, I. Panageas. T. Sandholm, and J. Yan. The complexity of symmetric equilibria in min-mat max optimization and team zero-sum games, arXiv preprint arXhv:2502.08579 2025.
K. Arrow and G. Debreu. Existence of an equilibrium for a competitive economy. Econometrica: Journal of the Econometric Society, pages 265-290, 1954.
R. J. Aumann. Correlated equilibrium as an expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pages 1-18, 1987.
Balseiro, Y. Deng, J. Mao, V. Mirrokni, and S. Zuo. Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34:17777-17788, 2021.
S. R. Balseiro and Y. Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-390 3968, 2019.
M. Bernasconi, M. Castiglioni, A. Marchesi, F. Trovo, and N. Gatti. Constrained phi-equilibria. In International Conference Machine Learning, pages 2184 2205. PMLR, 2023.
Note that p valid probability distribution actions as |pi]a by construction, and Pt (as well as 2') has only positive components since the relaxation > 0 required by the QUASIVI does not relax the hypercuhe constraints.
10

---

M. Bernasconi, M. Castiglioni, A. Celli, and G. Farina. On the role of constraints in the complexity of min-max optimization. arXiv preprint arX.v:2411.03248. 2024.
N. Bitansky, O. Paneth, and A. Rosen, On the cryptographic hardness of finding a nash equilibrium. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1480-1498. IEEE, 2015.
O. Boufous, R. El-Azouzi, M. Touati, E. Altman, and M. Bouhtou. Constrained correlated equilibria. In 2024 60th Annual Allerton Conference on Communication, Control, and Compuling, pages 1-8. IEEE, 2024.
S. Brânzei, Y. Chen, Deng, A. Filos-Ratsikas, S. Frederiksen, and Zhang. The fisher market game: Equilibrium and welfare. In Proceedings of the AAAI Conference Artificial Intelligncce volume 28, 2014.
N. Brown and T. Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456))8855-890, 2019.
Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou. Zero-sum polymatrix games: A general- ization of minmax. Mathematics of Operations Research, 41(2))648 655, 2016.
N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1-57, 2009.
A. R. Choudhuri, P. Hubáčck, C. Kamath, K. Pietrzak, A. Rosen, and G. N. Rothblum. Finding nash equilibrium no easier than breaking fiat-shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1103-1114, 2019.
V. Conitzer, C. Kroer, E. Sodomka, and N. Moses. Multiplicative pacing equilibria in auction markets. Operations Research, 70(2):963 989, 2022.
C. Daskalakis, P. W. Goldberg, and H. Papadimitriou. The complexity of computing nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
C. Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max opti- mization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021.
C. Daskalakis, G. Farina, M. Fishelson, C. Pipis, and J. Schneider, Efficient learning and computa- tion of linear correlated equilibrium in general convex games. arXiv preprint arXiv:2412.20291, 2024.
A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos. Pure-circuit: Strong inapproximability for ppad. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 159-170. IEEE, 2022.
M. F. A. R. T. FAIR, A. Bakhtin, Brown, F. Dinan, G. Farina, C. Flaherty, D. Fried, Goff, J. Gray, H. Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, 378666244;1067-10774 2022.
G. Farina and C. Pipis. Polynomial- computation of exact é-cquilibria in polyhedral games, In Advances in Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024.
J. Fearnley, S. Gordon, R. Mehta, and R. Savani. Unique end of potential line. Journal of Computer and System Sciences, 1 11::1-35, 2020.
Fearnley P. Goldberg, A. Hollender, and R. Savani. The complexity of gradient descent: CLS PPAD n PLS. Journal of the ACM, 70(1):1-74, 2022.
S. Garg, O. Pandey, and Srinivasan. Revisiting the cryptographic hardness of finding nash equilibrium, In Annual International Cryptology Conference, pages 579-604. Springer, 2016.

---

I. Goodfellow. J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and
Y. Bengio. Generative adversarial networks. Communications of the ACM, 63((1):139- 144, 2020.
A. Greenwald and A. Jafari. general class of no-regret learning algorithms and game-theoretic equilibria. In Learning Theory and Kernel Machines: 16th Annual Conference Learning Theory and 7th Kernel Workshop, COLI/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 2-12. Springer, 2003.
S. Hart and A. Mas-Colell. A simple adaptive procedure leading correlated equilibrium. Econo- metrica, (865):1127-1155) 2000.
B. F. Hobbs and J.-S. Pang. Nash-cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints. Operations Research, 55(1):113-127, 2007.
A. Hollender. Structural results for total search complexity classes with applications to game theory and optimisation. PhD thesis, University of Oxford, 2021.
A. Hollender, G. Maystre, and S. G. Nagarajan. The complexity of two-team polymatrix games with independent adversaries. In International Conference on Learning Representations ICLR, 2025.
M. Mahdavi, R. Jin, and T. Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal Machine Learning Research, 13(1):2503,2528, 2012.
Mannor, N. Tsitsiklis, et al. Online learning with sample path constraints. Journal of Machine Learning Research, 10(3), 2009.
H. Moulin and J. P. Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7:201-221, 1978.
Nash. Non-cooperative games. Annuls of Muthematics, 54(2) 1951.
T. Ni, A. Maddux, and M. Kamgarpour, On characterization and existence of a constrained corre- lated equilibria in markov games. arXiv preprint arXiv:2507.03502: 2025.
N. Nisan, I. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
R. Paes Leme, G. Piliouras, J. Schneider, K. Spendlove, and S. Zuo. Complex dynamics in auto- bidding systems. Proceedings of the 25th ACM Conference on Economics and Computation, pages 75-100, 2024.
C. Papadimitriou, E.-V. Mntakis-Giaragkkunnis and M. Zampetakis. The computational complex- ity multi-player concave games and kakutani fixed points. In Proceedings of the 24th ACM Conference Economics and Computation, pages 1045-1045, 2023.
C. H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):98-552,, 1994.
C. H. Papadimitriou and T. Roughgarden. Computing equilibria in multi-player games. In SODA, volume 5, pages 82-9 22-91. Citeseer, 2005.
B. Rosen. Existence and uniqueness of equilibrium points for concave n- n-person games. Econo- metrica: Journal of the Econometric Society, pages 520-534, 1965.
A. Rubinstein. Inapproximability of nash equilibrium. In Proceedings of the serty-seventh annual ACM symposium on Theory of computing, pages 409-418, 2015.
A. Rubinstein. Settling the complexity computing approximate two two-player nash equilibria. ACM SIGecom Exchanges, 15(2):45-9,, 2017.
B. H. Zhang, Anagnostides, E. Tewolde, R. E. Berker, G. Farina, V. Conitzer, and T. Sandholm. Ex- pected variational inequalities. ICML 2025-42st International Conference on Machine Learning. 2025.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The introduction and abstract accurately describe the main results of the paper.
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 contribu- tions made in 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 other settings.
is fine to include aspirational goals as motivation as long as 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]
Justification:
Limitations of the model are discussed in the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to viola- tions of these assumptions (e.g., independence assumptions, noiseless settings, model well- specification, asymptotic approximations only holding locally). The authors 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 a 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 the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken 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 address problems privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a 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 favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
All the claims supported by formal proof.
Guidelines:
13

---

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 theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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 complemented 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
Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: This is mainly theoretical paper, and no experiments are performed.
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 important, regardless of whether the code and data are provided not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. general. releasing code and data often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This is mainly a theoretical paper, and no experiments are performed.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
14

---

Please see the NeurIPS code and data submission guidelines www.ddee/ooeuumiisssiooooo Poooociy for more details.
ptttps:/nnis..co/
While we encourage the release of code and data, we understand that this might not be pos- sible, "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 reproduce the results. See the NeurIPS code and data submission guidelines (https://nips) ctcccc/pp//o http//guddss//ooeeiiieeeeeeeeeee www.iissssiioiyyiico for more details.
The authors should provide instructions 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This is mainly theoretical paper, and experiments performed.
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 appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is mainly a theoretical paper, and no experiments are performed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" results are accompanied by error bars, confidence 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 ex- ample, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates). error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
15

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification: This is mainly theoretical paper, and no experiments performed.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or 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 experi- mental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tppr/////uui.p.../
Answer:
[Yes]
Justification:
The authors conformed with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require a devia- tion from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper diseuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is mainly a theoretical paper, and there are no direct negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance). fairness considerations (e.g., deploy- of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement 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 generic algorithm for optimizing neural networks could enable people to 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
16

---

If there are negative societal impacts, the authors could also discuss possible mitigation strate- gies (e.g.. gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There is model or data released with the paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with neces- sary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to 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 require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly eredited and are the license and terms of use explicitly mentioned and properly respected?
Answer:
[NA]
Justification:
The paper does not use existing assets.
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, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi saperswithcode. thcode. wwt./oom//////eeeeo /atassss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are 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 is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their sub- missions via structured templates. This includes details about training, license, limitations,
The paper should discuss whether and how consent was obtained from people whose asset used.

---

At submission time, remember to anonymize your assets (if applicabll.. You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper in- clude the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with hu- man subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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 an equivalent approval/review based on the requirements your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with hu- man subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if appli- cable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it an important, original, or non- standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: the core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
for what Please refer to our LLM policy fnttps://neur//: wwtpeeewwww.p.peeeeeeeeeeeeeeeee should or should not be described.
18

---

A Examples of P-equilibria
We now introduce two notable examples of sets 4, namely Correlated and Coarse Correlated equi- libria.
Correlated equilibria (CEs) are obtained by considering all possible deviation strategies, i.e.,
PCB { $ [0,
b((a,) =1 Va A
11
Σ
PEA
This set models player that can observe its own recommendation and deviate to any other action with some probability. Another important class of equilibria is Coarse Correlated Equilibria (CCEs) that are defined by the
PCCB = { [0, [0.1] ((a,b) b(d'b) Ya, d' AA
Σ b)a,b) =1 va E A {
This models player whose deviations are forced to be equal for each recommended action A. Intuitively, the player has decide their own deviation strategy before seeing the recommended action a. This greatly simplifies the possible deviation since 6 &CCE can simply be identified with the marginals induces.
B Missing proof from Section (hardness)
Lemma 3.2. For each tuple a A, define the utility of the "left team" as uL(a) Eiev un (a) and the utility of the "right team" ug(aa Eiev Wiy (a). Then ur (a) uR (a).
Proof. The statement follows from straightforward caleulations
ua) Σ
Wi (a)
iEV
Σ
Σ
Aluja(au AjR)
iEV di(td)EE
--
Σ
Σ
(A#2) T apa)
(A = T
iEV H((J)EEE
Σ
Σ
(AtJ) (a air)
(By swapping the sum and the identity and j)
iEV H(LjEEE
=- E
Σ
A ajr)
NEV H(ij)EE
= =- Σ
Σ
Aun (aino ajr)
(Atn.h = Ans)
iEV H(JjEE
Σ Uig (a)
Ug (a)),
concluding the proof.
Lemma 3.3. Given a z E S", and E V, it holds that (m,((2) - mia (2)lloo S Moreover given a z E ((AlN)) and an i i V, the set of safe deviations of player in is (z) = {xa |244 m4 (o) S 0), which guarantees 4. (z) + 0.
19

---

Proof. Consider the case j S k:
Cg = Σ
C (a)=(a)
aEA
Σ
=(a)
Σ
=(a)
a aaLhsiis
z(a)
z(a)
aEAinig-
mi (z]j) min (z]j)
and thus C2 (=) S v, with j v implies that mi, (=(j) mig (=lj) S v. On the other hand C (z) $ with j k implies that mia (z|j) m4 (z|j) - which concludes the statement.
C Missing proofs and additional details from Section 4 (membership)
C.1 Explicit definition of (())
The correspondence Q: [0, 1) = [0, 11 is given by Q(2) {=: A()) S b(2) where
D1(3)
I I
1
-1
I
(2
1
A(2)
E (m=
(2
1
where Dz( Rmxx is matrix such that [0mxé, D.())..... Omxxea Om = pp s OVj E [m]. particular, for each i, only the components 2 corresponding to the strategies the i-th player matter and correspond to the strategy p,. We define g the flattening function which takes product distribution ò Qiejn) P. and returns the corresponding "unflatted" vector while we call
its inverse. Thus, we can write that D((g())pp I Om if and only if C/ (p, 8 p-.) S for all j [m). Notice that p; + C (p. @ p-:) is linear and can be written as C.¹ (p: 87-1) = (p) pt, where (p) & and each component </ (p)a. indexed by a, is given by LacAm (a( II l Pa (ax). Consequently, can take
(b(())))
D2(2)=
E mmxfn
(h()))
C.2 Proof of Claim 4.3 and Claim 4.4 from Proposition 4.2
Claim 4.3. The functions + A(z)= and & + b(²)T= defining the correspondence are L-Lipschitz for every [0, ee where L has a representation polynomial the size of the instance.
Proof. First note that b(ž) does not depend on and thus trivially 0-Lipschitz. Thus, we only need to prove the statement about A(2). We recall the exact definition of A(2) given in Appendix C.I.
20

---

We analyze the Jacobian of the (2) Any entry of D((2) would correspond to cost j of the i-th player (rows) and to an action â A (columns), and any component of would correspond to player i' (possibly different from i) and an action ā É A. Thus, by defining ğ h(ā), we can compute the following
ac (h(2))a
(p) (a)
Oze
Op
dzg
The second term is clearly 1, the function just rearranges the components ž, while the first term easily bounded as follows
Oc; (p)a pp.
Dae Asa, (. Inemmlaeea Pp(e)(
(p
Σ (a)
II
p=(as)
S 8
AE|n], Agp
The following elementary lemma lets us conclude the proof.
Lemma C.1. Let M RK + mxx be matrix valued function such that i E [m], E [m],k: & E [K] then
(M, abk
C for all
(I(M()) M(E))=1 & Cmv/kKla 1/1
for all z 10,
Indeed,
[I(AE)) A(2))=11 (6n) / in n(m + f+ 2)[ 8 2' 2 /m z'1l
and thus poly(E" m, n) concluding the proof.
Claim 4.4. The operator F : [0. 1jen + [0. 10 G-Lipschitz where G has a representation polynomial in the size of the instance.
Proof. We can get simple upper bound on the Lipschitz. constant of F by bounding its gradient. In particular F(z) (-Vp) pı (p),..., ., -V ur (p)). where usual 2 is the unrolling of the product
distribution p X Pt. We can consider any component of F, which will correspond to some
player i [n]] and action à E A, and consider some component of z which will correspond to some
player j E [n]] and some action à E A. The component of F' selected corresponds (u.(p) We
(p:(a)
can then consider the following:
pu:(p)
Σ
ul(a) II px(ax) kyi
Öp, ap)
aEA:;; a.o, a
8 (p))(p)
and thus
< E" The mean value theorem trivially concludes the proof:
(a)dpp)
[F(=) - F(2')I < []r(E)]l -1=-211
for some & on the segment connecting and z'. Now for any matrix M E Rmmx holds that ||M]] /mn- fmm-supp,, [M and thus [| n = G, concluding the proof.
Claim 4.5. Let v/ min(s; 2.) and é (1 nz/), then is such that
(,(p) > u;(p, @ p- :) Vp: E xp(()
and p S"
21

---

Proof. First, observe that if V 2 1 then the costs bear no effects and PPAD-membente can be established by the membership of Nash equilibria. Thus, we can assume w.l.o.g. that S 1.
Step 1: Safety First, we claim that p is v-safe. Indeed, || E i [n],j E [m]] and we directly compute
[1 v' + v/) and for each
(a)
II (aa)
aEAR
JE(n]
then, can divide the left and right hand side by I[jE(M) ||21|1 2 (1 - 1')n and, obtain that:
v/
1/
c((p)= = E (a)
II py(a)) & (1 v1- S - nw Su.
aEAn
JE(N)
where in the last inequality we used v/ S indeed p S"
V for all 2 and n 2 1. This shows that
2n
Ltne
Step 2: Simulating deviations Now we prove that we can simulate safe deviations pt with appro- priate choices of 2.
Take any safe deviation Ds E (A)) (i.e., it holds that Cf @ p-1) S 0), and consider 2 defined as where 전 = pr. By the definition of the correspondence (see Appendix C.J
== ,x' ........""" 2"), for notation and details on the explicit construction of the correspondence Q) we have that غ
(2). Indeed, from the definition of D, in Appendix C.I, we get that
= T
(by construction)
= =E
Σ
(a)
II
(a))
(def. of ({(())))
BEAGEA",ee A
K
Σ (a)
II
* (an)+
aεd",a;
k
00
(C 8 (p:)
Moreover, it is easy to verify that 2 E (1-v for all i E [n]. This shows that ă E Qr
Formally, what proved is that: for any player i E [n]] and for any safe deviation p. such that C. (p: @ p-+) S 0, there exists (z) which "simulates" p.. Moreover, z 2 for all j # and 2 Pi-
Step 3: Equilibrium conditions Now, we also claim that p x iE(xi constraints. Since z is a solution to QUASIVI we have that for all E Qu(()) the following holds:
Oienn Pt satisfies the equilibrium
FE -
ΣΣ Σ
u,(a) II 2 (a, 2 -,
ie
which implies that:
Σ (a((a) II d (a)) (a:)) 2 -t',
a
once we specialize the one built step 2, since ž 2 for all +
Now we can use the exact definition of 전² constructed in step 2, in the above equation, which leads to the following:
Σ ui (a) II (a))))((a))) = Σ u.(a) II 2'(2)) - Σ (a(a) Il jE(n]
(a,)))
-
a
j
aEA
acA
jzi
Rearranging it. obtain
Σ aEA
(((a) II
2 Σ (1(aa II
(ag))r(a))) -
JE(n]
asA
jf1
22

---

We can now divide each term by 7 = =[( ||
which finally leads to
ue(p) 2 ui(ps 20 p()
(
6 7 +
2 uzlfe 20 ppp))
12/111
and since ||>||| 1| E (1 - v. + v/) for all j E [n] this implies that 7 2 (1 - 11)n 2 nu and thus
(p) 2 u. @ p-i) I +//)
Consider the first term
-yy The following inequalities hold:
é' S 2
nw
since e' S 51 nw/).
Moreover, v/ - thus proving that up(p) 2 ui X pp+) - as desired.
C.3
Additional technical lemmas
Lemma C.1. Let M RRK - mgax be a matrix valued function such that
aM,,((8) 88x
S C for all
i [m],] E [m], & E [K] then
[I(M())- - M(E))=]1 S Cmvnk - 1/11 -111
for all z E 1),
Proof. Let {m; [0, 1] + R' be the functions defining the rows of M and h,(ālz) m=(E) With this notation it is easy to check that Vzh,(El=) (2) and thus [V s (M),(())]]l2)) s CVmnK.
By the mean value theorem, we have that for some & in the segment connecting and 8, we have [(m,(E) mi((")) 2| S [[>)( || - -
< CVmnk Kmnk1= -|=== 3'|l
Finally,
I M(5))=11 = Σ -mm)()))m
mx(())) T z)² s C2 2'113
concluding the proof.
23


Reviews:
[{"review_id": "73UtuH0Ie1", "reviewer": "Reviewer_QrtF", "summary": "This paper studies the computational complexity of computing Correlated constrained equilibria in generalized games. Previously, it was shown that constrained-phi-equilibria are PPAD-complete to compute in generalized games, but this kept open the question of whether the introduction of correlation could be a sufficient relaxation to make the problem poly-time computable. This paper resolves this question, showing that correlation is insufficient. The proof proceeds by a reduction to Nash Equilibrium computation in polymatrix games. The result also implies that the quasi-polynomial time algorithm for computing approximate phi-equilibria of Bernasconi et al. [2023] is tight.", "questions": "- What are the practical consequences of this work?\n- Are there other relaxations of constrained equilibria that may be easy to compute?", "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:\n- Resolves a fundamental problem in the complexity of computing equilibria for game theoretic problems, an active and important area of research\n- Proof is technically involved\n- Has broad consequences\n\nWeaknesses:\n- Unclear what the practical consequences are -- are there practical settings where the fact that these equilibria are hard to compute may cause issues? Since this paper has been submitted to NeurIPS, it would be nice to talk about *some* potential practical consequences, even if they are stylized. Are there ways to get around this hardness in practice?", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. The response is divided into two parts: one common section addressing general concerns, followed by answers to specific questions. \n\n***\n\nWe identified the following two points as the main concerns among the reviewers: 1) relevance to the NeurIPS community and 2) the lack of practical consequences of an hardness result. In the following, we address these two points.\n\n## Relevance\n\nFirst, we emphasize that convergence‐to‐equilibrium results in multi‐agent learning occupy a central place in the NeurIPS community and in the broader ML community. Our work delivers a fundamentally negative insight: it rules out the existence of efficient algorithms for computing constrained correlated equilibria, in contrast to wide array of algorithms available in the unconstrained case. In particular, there are many recent works on no-regret algorithms for correlated equilibria, and one could expect the same kind of tools to be applicable in the constrained setting. In contrast, we show that efforts to establish positive convergence guarantees of the form “no-regret algorithms converge to constrained correlated equilibria” are going to fail. We believe it is important to broadcast this impossibility result: by doing so, we can steer the community away from unfruitful directions and toward questions where real progress can be made. The NeurIPS community is precisely where researchers most invested in proving positive convergence results gather, making our impossibility result both timely and highly relevant to their efforts. \n\nWe also highlight that our results answer a known open problem within the ML community (see [1,2]). Prior work explicitly left open the complexity of finding these equilibria. We settle this question definitively in the negative. This hardness result fills a clear gap in the theory: while numerous works have established positive convergence rates for regret minimization in unconstrained settings, the constrained case remained largely open until now. \n\nFinally, it is not new for leading ML venues to publish papers whose main contribution is a hardness result, rather than a positive algorithmic guarantee. This is particularly the case in areas close to game theory. As an example, we mention the recent paper “The Complexity of Two-Team Polymatrix Games with Independent Adversaries” by Hollender et al. [3] that was very well received at ICLR 25. \n\n## Practical relevance\n\nWhile focusing on a general and abstract framework, our model captures important applications in the Internet economy, such as automated bidding systems that power modern digital advertising. Today’s platforms typically deploy autobidders that act on behalf of advertisers during the real-time bidding process. Each autobidder dynamically adjusts bids and usually has to satisfy constraints specified by the advertiser, such as return‐on‐investment, budget, and cost‑per‑acquisition constraints. These autobidding systems have attracted extensive attention in machine learning, originating a rich body of both theoretical and empirical works (see, e.g., [4,5,6,7]).\n\nOne key aspect of these systems is that all autobidders are deployed and run directly by the advertising platform. Therefore, platforms are usually interested in designing autobidding algorithms that converge to equilibrium over time, as this makes the system more stable, predictable, and compatible with the individual incentives of each advertiser. Our impossibility result demonstrates that, in general, convergence cannot be guaranteed. Consequently, to design autobidding platforms with provable convergence guarantees, advertising systems must employ new techniques that exploit the specific structure of their problem, since no general-purpose algorithm will suffice.\n\nDue to space constraints, this point was only briefly mentioned in the current version. We will elaborate on it in the final version of the paper.\n\n\n## References\n\n[1] Zhang, B. H., Anagnostides, I., Tewolde, E., Berker, R. E., Farina, G., Conitzer, V., & Sandholm, T. (2025). Expected variational inequalities. ICML. 2025.\n\n[2] Bernasconi, M., Castiglioni, M., Marchesi, A., Trovo, F., & Gatti, N. (2023, July). Constrained phi-equilibria. In International Conference on Machine Learning (pp. 2184-2205). PMLR.\n\n[3] Hollender, Alexandros, Gilbert Maystre, and Sai Ganesh Nagarajan. \"The Complexity of Two-Team Polymatrix Games with Independent Adversaries.\" ICLR. 2025.\n\n[4] Balseiro, Santiago R., and Yonatan Gur. \"Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.\" Proceedings of the 2017 ACM Conference on Economics and Computation. 2017.\n\n[5] Paes Leme, R., Piliouras, G., Schneider, J., Spendlove, K., & Zuo, S. (2024, July). Complex dynamics in autobidding systems. In Proceedings of the 25th ACM Conference on Economics and Computation (pp. 75-100).\n\n[6] Balseiro, S., Deng, Y., Mao, J., Mirrokni, V., & Zuo, S. (2021). Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34, 17777-17788.\n\n[7] Agarwal, D., Ghosh, S., Wei, K., & You, S. (2014, August). Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1613-1619).\n\n***\n\n## Specific answers\n\nWe thank the reviewer for the positive evaluation of our contributions.\n\n> What are the practical consequences of this work? \n\nFor the practical consequences of our result, we refer to the common answer.\n\n> Are there other relaxations of constrained equilibria that may be easy to compute?\n\nA natural, but significantly weaker, relaxation of our solution concept would be to consider a randomized version of our equilibria, making the set of equilibria a convex set. This seems to align with a recent line of research: [Zhang, Brian Hu, et al. \"Expected Variational Inequalities.\" ICML 2025.]"}, {"review_id": "0Jb6WykVTI", "reviewer": "Reviewer_dM7m", "summary": "This paper studies the complexity of computing correlated equilibria (CE) in generalized games, where players’ strategies are interdependent. While CE is typically easier to compute than Nash equilibria, the authors show that in these settings with coupled constraints, even to approximate CE computation is PPAD-complete. The authors establish it via a reduction from polymatrix games using two-team zero-sum game constructions. The results hold even with small approximation or constraint violations. Under standard assumptions, they further show that the problem likely requires quasi-polynomial time, resolving a key open question. This is a great paper to read overall.", "questions": "Please answer the following questions:\n\n(a) This paper presents deep theoretical insights but lacks experiments or simulations to illustrate practical implications... such as how these hardness results manifest in real-world economic or multi-agent systems? Can you highlight one or two real-life usecases wherein these results are of significant use?\n\n(b) The hardness proofs rely on structured reductions (eg: from polymatrix games) and certain types of deviation sets.. thus, I believe that these results may not generalize easily to broader classes of games as well as different equilibrium refinements... if not, can you please elaborate more on this?\n\n(c) The results in this paper only highlight worst-case intractability.. they do not explore whether practical heuristics or approximation schemes may still be effective in realistic settings (and thereby offering limited guidance for algorithmic design in applied domains)?", "limitations": "(a) This paper presents deep theoretical insights but lacks experiments or simulations to illustrate practical implications... such as how these hardness results manifest in real-world economic or multi-agent systems? Can you highlight one or two real-life usecases wherein these results are of significant use?\n\n(b) The hardness proofs rely on structured reductions (eg: from polymatrix games) and certain types of deviation sets.. thus, I believe that these results may not generalize easily to broader classes of games as well as different equilibrium refinements... if not, can you please elaborate more on this?\n\n(c) The results in this paper only highlight worst-case intractability.. they do not explore whether practical heuristics or approximation schemes may still be effective in realistic settings (and thereby offering limited guidance for algorithmic design in applied domains)?", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Below are my comments on this paper:\n\n(a) This paper presents deep theoretical insights but lacks experiments or simulations to illustrate practical implications... such as how these hardness results manifest in real-world economic or multi-agent systems? Can you highlight one or two real-life usecases wherein these results are of significant use?\n\n(b) The hardness proofs rely on structured reductions (eg: from polymatrix games) and certain types of deviation sets.. thus, I believe that these results may not generalize easily to broader classes of games as well as different equilibrium refinements... if not, can you please elaborate more on this?\n\n(c) The results in this paper only highlight worst-case intractability.. they do not explore whether practical heuristics or approximation schemes may still be effective in realistic settings (and thereby offering limited guidance for algorithmic design in applied domains)?", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. The response is divided into two parts: one common section addressing general concerns, followed by answers to specific questions. \n\n***\n\nWe identified the following two points as the main concerns among the reviewers: 1) relevance to the NeurIPS community and 2) the lack of practical consequences of an hardness result. In the following, we address these two points.\n\n## Relevance\n\nFirst, we emphasize that convergence‐to‐equilibrium results in multi‐agent learning occupy a central place in the NeurIPS community and in the broader ML community. Our work delivers a fundamentally negative insight: it rules out the existence of efficient algorithms for computing constrained correlated equilibria, in contrast to wide array of algorithms available in the unconstrained case. In particular, there are many recent works on no-regret algorithms for correlated equilibria, and one could expect the same kind of tools to be applicable in the constrained setting. In contrast, we show that efforts to establish positive convergence guarantees of the form “no-regret algorithms converge to constrained correlated equilibria” are going to fail. We believe it is important to broadcast this impossibility result: by doing so, we can steer the community away from unfruitful directions and toward questions where real progress can be made. The NeurIPS community is precisely where researchers most invested in proving positive convergence results gather, making our impossibility result both timely and highly relevant to their efforts. \n\nWe also highlight that our results answer a known open problem within the ML community (see [1,2]). Prior work explicitly left open the complexity of finding these equilibria. We settle this question definitively in the negative. This hardness result fills a clear gap in the theory: while numerous works have established positive convergence rates for regret minimization in unconstrained settings, the constrained case remained largely open until now. \n\nFinally, it is not new for leading ML venues to publish papers whose main contribution is a hardness result, rather than a positive algorithmic guarantee. This is particularly the case in areas close to game theory. As an example, we mention the recent paper “The Complexity of Two-Team Polymatrix Games with Independent Adversaries” by Hollender et al. [3] that was very well received at ICLR 25. \n\n## Practical relevance\n\nWhile focusing on a general and abstract framework, our model captures important applications in the Internet economy, such as automated bidding systems that power modern digital advertising. Today’s platforms typically deploy autobidders that act on behalf of advertisers during the real-time bidding process. Each autobidder dynamically adjusts bids and usually has to satisfy constraints specified by the advertiser, such as return‐on‐investment, budget, and cost‑per‑acquisition constraints. These autobidding systems have attracted extensive attention in machine learning, originating a rich body of both theoretical and empirical works (see, e.g., [4,5,6,7]).\n\nOne key aspect of these systems is that all autobidders are deployed and run directly by the advertising platform. Therefore, platforms are usually interested in designing autobidding algorithms that converge to equilibrium over time, as this makes the system more stable, predictable, and compatible with the individual incentives of each advertiser. Our impossibility result demonstrates that, in general, convergence cannot be guaranteed. Consequently, to design autobidding platforms with provable convergence guarantees, advertising systems must employ new techniques that exploit the specific structure of their problem, since no general-purpose algorithm will suffice.\n\nDue to space constraints, this point was only briefly mentioned in the current version. We will elaborate on it in the final version of the paper.\n\n\n## References\n\n[1] Zhang, B. H., Anagnostides, I., Tewolde, E., Berker, R. E., Farina, G., Conitzer, V., & Sandholm, T. (2025). Expected variational inequalities. ICML. 2025.\n\n[2] Bernasconi, M., Castiglioni, M., Marchesi, A., Trovo, F., & Gatti, N. (2023, July). Constrained phi-equilibria. In International Conference on Machine Learning (pp. 2184-2205). PMLR.\n\n[3] Hollender, Alexandros, Gilbert Maystre, and Sai Ganesh Nagarajan. \"The Complexity of Two-Team Polymatrix Games with Independent Adversaries.\" ICLR. 2025.\n\n[4] Balseiro, Santiago R., and Yonatan Gur. \"Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.\" Proceedings of the 2017 ACM Conference on Economics and Computation. 2017.\n\n[5] Paes Leme, R., Piliouras, G., Schneider, J., Spendlove, K., & Zuo, S. (2024, July). Complex dynamics in autobidding systems. In Proceedings of the 25th ACM Conference on Economics and Computation (pp. 75-100).\n\n[6] Balseiro, S., Deng, Y., Mao, J., Mirrokni, V., & Zuo, S. (2021). Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34, 17777-17788.\n\n[7] Agarwal, D., Ghosh, S., Wei, K., & You, S. (2014, August). Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1613-1619).\n\n***\n\n## Specific answers\n\n> (a) This paper presents deep theoretical insights...\n\nFor the practical consequences of our result, please refer to the common answer.\n\n> (b) The hardness proofs rely on structured reductions \n\nWe point out that our reduction reduces both from polymatrix games but also works when applied to bimatrix games, which are very natural. Also, the set of deviations is the set of CCE deviations. Thus, on both these aspects, we view reduction to produce very natural instances.\nNonetheless, reductions, by their nature, rely on carefully built instances. They are intended to serve as a guide to what results are possible to achieve. We prove that, in general, one cannot find polynomial-time algorithms, so if one is interested in giving efficient algorithms for some more specialized problem, they **must** exploit some fundamental characteristic of their problem. \n\n> (c) The results in this paper only highlight worst-case intractability...\n\nWe believe that prior work has already satisfactorily addressed the positive result in this setting. In particular, Bernasconi, et al., [2023], showed that there exists a quasi-polynomial time algorithm in general (running in $O(n^{\\log(n)})$ time for constant approximations which we prove to be tight) and polynomial time algorithms in the case in which the number of actions is small or in the case in which the number of constraints is small."}, {"review_id": "mB9mbwb59o", "reviewer": "Reviewer_KuZX", "summary": "The paper studies the notion of \\Phi-correlated equilibrium in n player games under cost constraints for agents which are emposed on the their joint actions.\nMore precisely, the set \\Phi describes the set of (possibly randomized) deviations each player can make from action a for each action a. The equilibrium notion then restricts the players to use these deviations to deviate from their recommended strategy which is sampled by a mediator who correlates the agents joint actions.\n\nAgents should not want to use any of the allowed deviations.\nMoreover, each agent has an m dimensional cost vector associated with each joint action profile. For each cost dimension each agent has a threshold cost which she does not want to cross in expectation.\nIf this holds for all cost dimensions the correlated action profile is considered safe and one can define the induced set of safe deviations naturally.\n\nBecause safe deviations may not always exist, the authors constrain to a setting where each agent has at least one safe deviation - that is we are promised that an equilibrium exists.\n\nThe paper then shows that finding a constrained \\Phi-correlated equilibrium is PPAD-complete.", "questions": "You mention some applications in the introduction such as repeated auctions/ online advertising. Can you explain how your specific hardness result is relevant for the specific applications you mention?\n\nWhich sets of functions \\Phi are relevant other than CCE and CE? \nCan you name some applications in which other restricted type of deviations would only be feasible?", "limitations": "Lack of directly relevant applications", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is well written, although at times a bit verbose (e.g. 67-69).\nOverall, I think the paper is fine, but do not see the usefulness of the result and further it doesn't seem technically\nchallenging enough to accept it despite this. \n\nAlthough not my main concern, it is not clear why \\Phi equilibrium in its generality is useful, especially since the deviation agents are only not incentivized to deviate in an average sense.\n\n__\n\nMinor errors:\n\nIn Line 201, in the second line and in Line 212 i and j seem to be flipped", "was_revised": true, "final_justification": "The paper is borderline for NeurIPS, the result is good to have, but not surprising and the result does not answer the specific practical motivation mentioned in the introduction.", "rebuttal": "We thank the reviewer for their comments and suggestions. The response is divided into two parts: one common section addressing general concerns, followed by answers to specific questions. \n\n***\n\nWe identified the following two points as the main concerns among the reviewers: 1) relevance to the NeurIPS community and 2) the lack of practical consequences of an hardness result. In the following, we address these two points.\n\n## Relevance\n\nFirst, we emphasize that convergence‐to‐equilibrium results in multi‐agent learning occupy a central place in the NeurIPS community and in the broader ML community. Our work delivers a fundamentally negative insight: it rules out the existence of efficient algorithms for computing constrained correlated equilibria, in contrast to wide array of algorithms available in the unconstrained case. In particular, there are many recent works on no-regret algorithms for correlated equilibria, and one could expect the same kind of tools to be applicable in the constrained setting. In contrast, we show that efforts to establish positive convergence guarantees of the form “no-regret algorithms converge to constrained correlated equilibria” are going to fail. We believe it is important to broadcast this impossibility result: by doing so, we can steer the community away from unfruitful directions and toward questions where real progress can be made. The NeurIPS community is precisely where researchers most invested in proving positive convergence results gather, making our impossibility result both timely and highly relevant to their efforts. \n\nWe also highlight that our results answer a known open problem within the ML community (see [1,2]). Prior work explicitly left open the complexity of finding these equilibria. We settle this question definitively in the negative. This hardness result fills a clear gap in the theory: while numerous works have established positive convergence rates for regret minimization in unconstrained settings, the constrained case remained largely open until now. \n\nFinally, it is not new for leading ML venues to publish papers whose main contribution is a hardness result, rather than a positive algorithmic guarantee. This is particularly the case in areas close to game theory. As an example, we mention the recent paper “The Complexity of Two-Team Polymatrix Games with Independent Adversaries” by Hollender et al. [3] that was very well received at ICLR 25. \n\n## Practical relevance\n\nWhile focusing on a general and abstract framework, our model captures important applications in the Internet economy, such as automated bidding systems that power modern digital advertising. Today’s platforms typically deploy autobidders that act on behalf of advertisers during the real-time bidding process. Each autobidder dynamically adjusts bids and usually has to satisfy constraints specified by the advertiser, such as return‐on‐investment, budget, and cost‑per‑acquisition constraints. These autobidding systems have attracted extensive attention in machine learning, originating a rich body of both theoretical and empirical works (see, e.g., [4,5,6,7]).\n\nOne key aspect of these systems is that all autobidders are deployed and run directly by the advertising platform. Therefore, platforms are usually interested in designing autobidding algorithms that converge to equilibrium over time, as this makes the system more stable, predictable, and compatible with the individual incentives of each advertiser. Our impossibility result demonstrates that, in general, convergence cannot be guaranteed. Consequently, to design autobidding platforms with provable convergence guarantees, advertising systems must employ new techniques that exploit the specific structure of their problem, since no general-purpose algorithm will suffice.\n\nDue to space constraints, this point was only briefly mentioned in the current version. We will elaborate on it in the final version of the paper.\n\n\n## References\n\n[1] Zhang, B. H., Anagnostides, I., Tewolde, E., Berker, R. E., Farina, G., Conitzer, V., & Sandholm, T. (2025). Expected variational inequalities. ICML. 2025.\n\n[2] Bernasconi, M., Castiglioni, M., Marchesi, A., Trovo, F., & Gatti, N. (2023, July). Constrained phi-equilibria. In International Conference on Machine Learning (pp. 2184-2205). PMLR.\n\n[3] Hollender, Alexandros, Gilbert Maystre, and Sai Ganesh Nagarajan. \"The Complexity of Two-Team Polymatrix Games with Independent Adversaries.\" ICLR. 2025.\n\n[4] Balseiro, Santiago R., and Yonatan Gur. \"Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.\" Proceedings of the 2017 ACM Conference on Economics and Computation. 2017.\n\n[5] Paes Leme, R., Piliouras, G., Schneider, J., Spendlove, K., & Zuo, S. (2024, July). Complex dynamics in autobidding systems. In Proceedings of the 25th ACM Conference on Economics and Computation (pp. 75-100).\n\n[6] Balseiro, S., Deng, Y., Mao, J., Mirrokni, V., & Zuo, S. (2021). Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34, 17777-17788.\n\n[7] Agarwal, D., Ghosh, S., Wei, K., & You, S. (2014, August). Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1613-1619).\n\n***\n\n## Specific answers\n\n> You mention some applications in the introduction... \n\nFor the relevance of our result, please refer to the common answer.\n\n> Which sets of functions $\\Phi$ are relevant...\n\nPhi equilibria are an important generalization of equilibria in games, thanks to their deep connection to the level of rationality of the players, and they were pivotal in addressing important results in game theory (for instance [8]). Indeed, Phi deviations not only generalize both CEs and CCEs but also allow for a much more general type of rationality. For example, we could easily envision a setting in which deviation functions are all the possible ones for most of the actions, but when the player is recommended some critical actions, they are not allowed to deviate due, for instance, to safety constraints. Another motivation for considering general sets of deviations is that different sets may result in different properties in terms of manipulability (see, for instance, [9] and references therein).\n\n[8] Celli, Andrea, et al. \"No-regret learning dynamics for extensive-form correlated equilibrium.\" Advances in Neural Information Processing Systems 33 (2020): 7722-7732.\n\n[9] Arunachaleswaran, E. R., Collina, N., Mansour, Y., Mohri, M., Schneider, J., & Sivan, B. (2025, July). Swap Regret and Correlated Equilibria Beyond Normal-Form Games. In Proceedings of the 26th ACM Conference on Economics and Computation (pp. 130-157)."}, {"review_id": "pc4n7oS0LO", "reviewer": "Reviewer_BkuP", "summary": "The paper studies the computational complexity of finding certain constrained approximate $\\Phi$-equilibria in generalized games. It is shown that this search problem is PPAD-complete and thus presumably not solvable in polynomial time. This answers a recent open question from the literature. PPAD-hardness is based on a reduction from the PolyMatrix problem (finding approximate equilibria in polymatrix games) and membership in PPAD is shown via reduction to some problem related to quasi-variational inequalities.", "questions": "1. Since your problem is formulated as a promise problem, do you not need to show for your construction that it satisfies the promise?\n\n2. For the correctness, you only show one direction. Is this enough because we consider total search problems (where existence of a solution is guaranteed)?\n\n3. Are there any interesting special cases which are efficiently solvable?", "limitations": "No limitations are explicitly mentioned.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper settles the complexity status of a seemingly important search problem in (generalized) game theory.\n\nWeakness:\n- The result is purely theoretic and I do not see a direct connection to the NeurIPS community. There is no discussion on possible practical implications of the result.\n- The presentation is not understandable for non-experts in generalized games. Many important notions are not properly explained and defined (e.g. What is $\\Delta(\\mathcal A)$ and $\\Delta(A)$? What is the idea behind the mediator recommendation and deviation? What is correlated distribution?).\n- From a theoretical perspective, since I am not an expert in the field, I am not sure how relevant or surprising the result is.\n- The paper misses a concluding discussion (other directions or open cases).", "was_revised": true, "final_justification": "The paper resolves a relevant theoretical open question. Given that the authors discuss the practical relevance and implications of their result, I find it acceptable.", "rebuttal": "We thank the reviewer for their comments and suggestions. The response is divided into two parts: one common section addressing general concerns, followed by answers to specific questions. \n\n***\n\nWe identified the following two points as the main concerns among the reviewers: 1) relevance to the NeurIPS community and 2) the lack of practical consequences of an hardness result. In the following, we address these two points.\n\n## Relevance\n\nFirst, we emphasize that convergence‐to‐equilibrium results in multi‐agent learning occupy a central place in the NeurIPS community and in the broader ML community. Our work delivers a fundamentally negative insight: it rules out the existence of efficient algorithms for computing constrained correlated equilibria, in contrast to wide array of algorithms available in the unconstrained case. In particular, there are many recent works on no-regret algorithms for correlated equilibria, and one could expect the same kind of tools to be applicable in the constrained setting. In contrast, we show that efforts to establish positive convergence guarantees of the form “no-regret algorithms converge to constrained correlated equilibria” are going to fail. We believe it is important to broadcast this impossibility result: by doing so, we can steer the community away from unfruitful directions and toward questions where real progress can be made. The NeurIPS community is precisely where researchers most invested in proving positive convergence results gather, making our impossibility result both timely and highly relevant to their efforts. \n\nWe also highlight that our results answer a known open problem within the ML community (see [1,2]). Prior work explicitly left open the complexity of finding these equilibria. We settle this question definitively in the negative. This hardness result fills a clear gap in the theory: while numerous works have established positive convergence rates for regret minimization in unconstrained settings, the constrained case remained largely open until now. \n\nFinally, it is not new for leading ML venues to publish papers whose main contribution is a hardness result, rather than a positive algorithmic guarantee. This is particularly the case in areas close to game theory. As an example, we mention the recent paper “The Complexity of Two-Team Polymatrix Games with Independent Adversaries” by Hollender et al. [3] that was very well received at ICLR 25. \n\n## Practical relevance\n\nWhile focusing on a general and abstract framework, our model captures important applications in the Internet economy, such as automated bidding systems that power modern digital advertising. Today’s platforms typically deploy autobidders that act on behalf of advertisers during the real-time bidding process. Each autobidder dynamically adjusts bids and usually has to satisfy constraints specified by the advertiser, such as return‐on‐investment, budget, and cost‑per‑acquisition constraints. These autobidding systems have attracted extensive attention in machine learning, originating a rich body of both theoretical and empirical works (see, e.g., [4,5,6,7]).\n\nOne key aspect of these systems is that all autobidders are deployed and run directly by the advertising platform. Therefore, platforms are usually interested in designing autobidding algorithms that converge to equilibrium over time, as this makes the system more stable, predictable, and compatible with the individual incentives of each advertiser. Our impossibility result demonstrates that, in general, convergence cannot be guaranteed. Consequently, to design autobidding platforms with provable convergence guarantees, advertising systems must employ new techniques that exploit the specific structure of their problem, since no general-purpose algorithm will suffice.\n\nDue to space constraints, this point was only briefly mentioned in the current version. We will elaborate on it in the final version of the paper.\n\n\n## References\n\n[1] Zhang, B. H., Anagnostides, I., Tewolde, E., Berker, R. E., Farina, G., Conitzer, V., & Sandholm, T. (2025). Expected variational inequalities. ICML. 2025.\n\n[2] Bernasconi, M., Castiglioni, M., Marchesi, A., Trovo, F., & Gatti, N. (2023, July). Constrained phi-equilibria. In International Conference on Machine Learning (pp. 2184-2205). PMLR.\n\n[3] Hollender, Alexandros, Gilbert Maystre, and Sai Ganesh Nagarajan. \"The Complexity of Two-Team Polymatrix Games with Independent Adversaries.\" ICLR. 2025.\n\n[4] Balseiro, Santiago R., and Yonatan Gur. \"Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.\" Proceedings of the 2017 ACM Conference on Economics and Computation. 2017.\n\n[5] Paes Leme, R., Piliouras, G., Schneider, J., Spendlove, K., & Zuo, S. (2024, July). Complex dynamics in autobidding systems. In Proceedings of the 25th ACM Conference on Economics and Computation (pp. 75-100).\n\n[6] Balseiro, S., Deng, Y., Mao, J., Mirrokni, V., & Zuo, S. (2021). Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34, 17777-17788.\n\n[7] Agarwal, D., Ghosh, S., Wei, K., & You, S. (2014, August). Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1613-1619).\n\n***\n\n## Specific answers\n\nWe are sorry if the paper was outside of the area of expertise of the reviewer. Nonetheless, we will address the reviewer’s questions thoroughly in the hope that this can help to better reevaluate the significance of our work. \n\n> The result is purely theoretic..\n\nWe refer to the common answer for the practical relevance of our results and their interest in the NeurIPS community.\n\n> The presentation is not understandable for non-experts...\n\nDue to space constraints, we had to cut the explanation of the most standard game-theory concepts and results. For the reviewer's convenience, we will summarize it here. In particular, $\\Delta(A)$, for a finite set $A$ is the set of all categorical distributions on the elements of $A$. A correlated distribution is a distribution over actions that is correlated between the actions of different players, ie, cannot be written as the product of distributions over the actions of single players. In a correlated equilibrium, the object of study is exactly a correlated distribution with some additional properties. Meaning that, when the actions are drawn from the correlated distribution and communicated privately to each player, they (employing Bayesian reasoning on the distribution of play of the other player, after having seen their recommendation), are not incentivised to deviate from the recommendation.\n\n## Answers to the questions\n\n> 1. Since your problem is formulated as a promise problem...\n\nYes, indeed. The only promise that needs to be proved is that the set of deviations is non-empty. This, although not explicitly highlighted, is proven in Lemma 3.3.\n\n> 2. For the correctness, you only show one direction...\n\nYou are right; reductions for TFNP problems behave differently than reductions between NP problems. This is because we only have Yes instances by definition of totality.\n\n> 3. Are there any interesting special cases which are efficiently solvable?\n\nThe cases in which efficient algorithms can be found are discussed in prior works (which left open the question on the computational complexity of finding any equilibria, which we address here). We refer to the answer to review dM7m (answer c) for more details on this."}]

Author rebuttal:

Meta-review: This paper studies the computational complexity of computing Correlated constrained equilibria in generalized games, showing hardness results.

There is general agreement among reviewers that the result is interesting, novel. There are some issues on practical relevance of the results, since the paper is mainly theoretical. Still, this does not undermine the strengths of the paper. Anyway, I would require the authors to explain this point of relevance to ML very clearly – that their results are relevant to learning dynamics, which is a fundamental thing, and explain what precisely is being ruled out (only computationally efficient dynamics, and what type(s) of convergence).
Decision: Accept (poster)