Expected Variational Inequalities
Authors: Brian Hu Zhang
Ioannis Anagnostides
Emanuel Tewolde
Ratip Emin Berker
Gabriele Farina
Vincent Conitzer
Tuomas Sandholm
Venue: ICML 2025 oral (2025)
Keywords: variational inequalities
correlated equilibria
game theory
Primary area: theory->optimization
TL;DR: We introduce a computationally tractable relaxation of variational inequalities.

Abstract: *Variational inequalities (VIs)* encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—which we refer to as *expected variational inequalities (EVIs)*—where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.

Expected Variational Inequalities
Brian Hu Zhang"
loannis Anagnostides 1 Emanuel Tewolde"s 12 Ratip Emin Berker" Gabriele Farina"
Vincent Conitzer 124 Tuomas Sandholm 1567
Abstract
problems- the steady-state a congested net- work wherein users compete for its resources (Dafermos, 1980); frictional contact problems in mechanical engineer- ing (Capatina, 2014); and pricing options, foundational problem in financial economics (Black & Scholes, 1973).
Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engincering economics and machine learn- ing. However, their considerable expressivity comes at the cost of computational intractabil- ity. In this paper, we introduce and analyze a natural relaxation-whie we refer to as expected variational inequalities (EVIs) where the goal is to find a distribution that satisfies the VI con- straint expectation. By adapting recent tech- niques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.
Formally, in general form, VI can be defined as follows.'
Definition 1.1. Let X be convex and compact subset of Rd and F X -> Rd bounded map. The variational inequality (VI) problem asks for point E X' such that
(F(m), x)) 2 0 Val E X.
(1)
For computational purposes, it is common to consider the c-approximate VI problem, wherein the right-hand side of (I) is replaced by -e for some precision parameter e 0.
Definition 1.1 abstracts the description of F and X. As concrete example, when gradient of differentiable function : X' + R, the solu- tions to (1) are points that satisfy the first-order optimality conditions for maximizing u (Boyd & Vandenberghe, 2004),
+ Vu((x) is the negative
1. Introduction
Unfortunately, the considerable expressivity of VIs comes at the expense of intractability: even when linear and is absolute constant, identifying an e-approximate VI solution is computationally hard; this follows readily from the intractability of Nash equilibria-undee plexity assumptions (Daskalakis et al., 2008; Chen et al., 2009; Rubinstein, 2016). Unconditional, query-complexity lower bounds have also been established (Hirsch et al., 1989; Babichenko, 2016); of. Milionis et al. (2023) and Hart (2003) for other pertinent impossibility results.
Variational inequalities (Vls) provide a unifying framework for analyzing a wide range of optimization and equilib- rium problems. They have host of important applica- tions in engineering and economics (Facchinei & Pang, 2003), including identifying stationary points in constrained optimization; computing Nash equilibria in multi-player games (Nash, 1951), such as Cournot's 's classical model of oligopoly (Cournot, 1838): predicting economic activity- commodity prices and consumer consumption-in a closed, competitive economy (Arrow & Debreu, 1954), which is at the heart of general equilibrium theory; traffic equilibrium
plausible com-
This bleak realization has shifted the focus of contemporary research primarily to characterizing specific subclasses of VIs that elude those complexity barriers, with the ensuing line of work flourishing in recent years. Some notable exam- ples include the classical Minty property (Facchinei & Pang, 2003; Mertikopoulos Zhou, 2019), as well as certain re- laxations thereof (Diakonikolas al., 2021; Böhm, 2023; Bauschke al., 2021; Combettes & Pennanen, 2004; Gor- bunov al., 2023; Cai et al., 2024b; Alacaoglu et al., 2023;
Equual contribution 'Carnegic Mellon University Foundations of Cooperative AI Lab (FOCAL) 'Massachusetts Institute of Tech- nology Uniierritty of Oxford 'Strategy Robot, Inc. "Strategic Ma- chine, Inc. 'Optimized Markets, Inc. Correspondence to: Brian Hu Zhang <bhzhang edw..uuu.,uuuuemmmm.......i....e Ioannis Anagnostides <ianag- nos @ @cc.cmu.edu>>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
As is standard, VI throughout this paper refers to the Stam- pacchia (SVI) (Kinderlehrer & Stampacchia, 2000).

---

Expected Variational Incqualities
Pethick al., 2022; Lee & Kim, 2021; Patris & Panageas, 2024; Choudhury et al., 2024; Anagnostides et al., 2024).
that when & contains only linear maps, LLIN Φ-EVIs can be solved in time polynomial in the dimension d and log(1 /c) (Theorem 4.1), establishing the promised computational property that separates EVIs from VIs. This result is based on ellipsoid against hope (EAH), the seminal algorithm of Pa- padimitriou & Roughgarden (2008) developed for comput- ing correlated equilibria in multi-player games. (Section 2.1 gives self-contained overview of EAH.) In doing so, we extend the scope of that algorithm to a much broader class of problems well beyond the realm of game theory. No- tably, Theorem 4. 1 applies even when X' is given implicitly through membership oracle; this extension makes use of the recent technical approach of Daskalakis et al. (2025), discussed in more detail in Section 4.
Despite these important advances, the scope of such results is severely restricted. In this paper, we pursue differ- ent, orthogonal avenue. Instead of restricting the class of problems to achieve computational tractability, we relax the underlying solution concept. Our main research question is:
Are there meaningful relaxations of the VI problem that can always be solved efficiently?
When specialized to games, this question can be seen as part of the research agenda recently outlined by Daskalakis (2022) in his address at the Nobel symposium about equi- librium computation in nonconcave games-4 a major, new frontier in the interface of game theory and optimization.
One limitation of Theorem 4.1 is that it relies on the EAH algorithm, which is slow in practice. We address this by also establishing more scalable algorithms that use convex quadratic optimization (Theorem 4.3) instead of the ellip- soid algorithm. As a byproduct, we obtain the best-known algorithm for linear-swap regret minimization over explic- itly represented polytopes, improving on Daskalakis et al. (2025) by reducing the per-iteration complexity.
1.1. Our Contribution: The Expected VI Problem
To make progress on that central question, we introduce a natural relaxation of VIs (in the context of Definition 1.1).
Definition 1.2. Given a set of deviations & Xx², the c-approximate @-expected variational inequality (#-EVI) problem asks for distribution μ E ((x) such that
In addition their more favorable computational properties, we further show that E-EVIs admit (approximate) solutions under more general conditions than their associated VIs- namely, without F being contimuous (Theorem 3.1); Sec- tion documents further interesting aspects on existence.
E (F(z). a--
x) 2 - V &.
(The above definition does not specify how X, F, T. and 1 should be represented for computational purposes, but we will be explicit about representation whenever it is relevant.)
Connection to other solution concepts As we have al- luded to. 4-EVIs generalize (Examples 5.1 and 5.2) the sem- inal concept of a (coarse) correlated equilibrium à la Au- mann (1974) and Moulin & Vial (1978) in finite games, and more generally t-equilibria (Greenwald & Jafari, 2003; Stoltz & Lugosi, 2007; Gordon al., 2008) of concave games. What is more surprising is that L refine CEs even in normal-form games; we give illustrative exam- ples, together with an interpretation, in Section 5. We also note that 4-EVIs can be used even in games with noncon- cave utilitics (Daskalakis, 2022; Cai et al., 2024a) or noncon- tinuous gradients (as in nonsmooth optimization), as well as in (pseudo-)gamen with coupled constraints (cf. Bernasconi et al., 2023 and Appendix A for related work).
In words, Definition 1.2 only imposes (approximate) non- negativity in expectation for points drawn from μ E A(x). It certainly relaxes Definition 1.1: if x satisfies (I), then the distribution that always outputs x is also a --EVI solution. &-EVIs are thus no harder than VIs (assuming that solutions exist). However, as we shall see, the primary justification of --EVIs is that they can be easier than VIs.
Definition 1.2 is crucially parameterized by Φ; the larger the set of deviations & the tighter the set of solutions. As will become clear, Definition 1.2 is intimately connected with notions of correlated equilibrium (CE) from game theory (e.g., Aumann, 1974). The more permissive case where t comprises only constant functions, & = &COON = (oz= : x E X where d. (x") x for all x' E X, is perhaps the most basic relaxation of Definition 1.1; we call the ccoN-EVi problem simply the EVI problem.
Further properties As further motivation, we show that for certain structured problems, such as (quasar-)concave optimization and polymatrix zero-sum games, EVIs essen- tially coincide with VIs (Propositions 6.1 and 6.3).
Jconcave
Algorithms and complexity for Φ-EVIs As it turns out, imposing no constraints on & results in an impasse: 4-EVIs are in general tantamount to regular VIs- thereby being PPAD-hard (Corollaries 3.7 and 3.9). On the other hand, unlike general VIs, one of our key contributions is to show
Finally, in certain applications, one might be interested in a VI solution mainly insofar as it provides guarantees in terms of an underlying objective, such as misclassification error or social welfare. Through that prism, the question is whether performance guarantees for VIs can be translated
2

---

Expected Variational Incqualities
Result
Description
Reference
Existence of (e-approx.) solutions
Under Lipschitz cont. for & and bounded F
Theorem 3.1
Complexity with nonlinear +
PPAD-hardness with linear F and (1)
Corollaries 3.7 and 3,9
Algorithms for linear +
poly(d, log(1/e)) -timee via EAH
Theorem 4.1
poly (d, 1/e)-time via Ø-regret minimization
Theorem 4.3
Equivalence between Vis-EVIs
Quasar-concave functions (Definition 6.2)
Proposition 6.3
x + (F(x),, x' - z) concave for all x'
Proposition 6.1
Performance guarantees for EVIs
Under smoothness (Definition 7.1)
Theorem 7.4
Table 1. Our main results concerning 4-EVIs (Definition 1.2).
EVTs well. In Section we establish framework for accomplishing that (Definition 7.1) by extending the celebrated smoothness framework of Roughgarden (2015), and provide interesting examples beyond game theory.
interior; this is standard regularity condition that ensures X' is geometrically well-behaved, which can be met by bringing X' into isotropic position (Appendix B). Under this assumption, the three oracles listed above are polynomially equivalent (Grötschel et al., 1993; 1981). As a result, we may assume that is given implicitly via a (poly(d) -time) membership oracle, which suffices for Theorem 4.1.
Taken together, these properties provide compelling justi- fication for +-EVIs as solution concept in place of VIs. Table gathers our main results. (Proofs in Appendix C.)
All our positive results with respect the set of linear endo- morphisms LLNN readily carry over to affine endomorphisms as well.
2. Preliminaries
This section provides some basic notation and background together with an overview of the EAH algorithm. Additional preliminaries, which are not necessary for the main body, are given later in Appendix B.
2.1. Ellipsoid Against Hope
This ellipsoid against hope (EAH) algorithm was famously introduced by Papadimitriou & Roughgarden (2008) to com- pute correlated equilibria in multi-player games. We pro- ceed with an overview of EAH, and particular a general- ized version thereof, crystallized by Farina & Pipis (2024).
Notation We use boldface, lowercase letters, such as æ and y, to denote vectors in Euclidean space. Capital, boldface letters, such as A, represent matrices. For æ,, x' e Rd, we use (ar, x²) denote their inner product. ||>||| /(z,z) is the Euclidean norm of æ. (x) is the (closed) Euclidean ball centered at with radius > 0. conv(-) represents the convex hull. An endomorphism on X' is a function mapping& X' to X.
Consider an arbitrary optimization problem of the form
find / E A(2) s.t. E (y. G(x)) 2 0 A e
where ) C Rm and G X is an arbitrary function. Suppose that we are given an evaluation oracle for G and a separation oracle for y. Assume further that we are given good-enough--response (GER) oracle, which, given any y E y, returns x E X' such that G(x)) 2 0. The upshot is that EAH enables us to solve (2) with just the above tools. Indeed, consider the following problem, which is an e-approximate version of the dual of (2).
Returning to Definition 1.2, for computational purposes, we assume throughout that has an explicit polynomial rep- resentation, that F(x)) RRd can be evaluated in (dly time. Further, there exists B 0 such that [[=( < B for all æ E X. We will also restrict the support (u of to be poly(d, 1/e), unless stated otherwise. With regard to X, we assume that we have oracle access. In particular, we consider the following three types of oracle access.
find y E y s.t. (yx)())) I - VI X.
(3)
Membership: given Rd. decide whether X. Separation: given Rdd, decide whether X:; if not, return a hyperplane that separates æ from X.
Since GER oracle exists, (3) is infeasible. What is more, certificate of infeasibility of (3) yields an e-approximate solution to (2). It thus suffices to run the ellipsoid algorithm on (3) and extract a certificate of infeasibility; in nutshell, this is what EAH does (cf. Algorithm in Appendix C).
Linear optimization: Given E Rd, return vector in argmax (xc u).
In addition, we will assume that X' C (0) for some R S poly(d) and contains ball of radius in its relative
Theorem 2.1 (Generalized form of EAH; Farina & Pipis, 2024). Given GER oracle and a separation oracle (SEP)
3

---

Expected Variational Incqualities
for y; EAH runs in time poly(d, m, log(1/e)) and returns an c-approximate solution to (2).
Theorem 3.5. Suppose that
& is finit-dimensional, that is, there exists k N and a kernel map m : X + RR such that every o E &b can be expressed as (m( for some K E Baxk; and
One of our main results (Theorem 4.1) crucially hinges on strengthening of Theorem 2.1 due to Daskalakis et al.
(2025), discussed further in Section 4 and Appendix C.3.
2. every
+ admits fixed point, that is, point X a x FP(Ø) such that ((x)
3. Existence and Complexity Barriers
Perhaps the most basic question about Φ-EVIs concerns their totality-the existence of solutions. If one is willing to tolerate an arbitrarily small imprecision e > O, we show that solutions exist under very broad conditions.
Then, the &-EVI problem admits an 6-approximate solution with support size at most 1 + dk for every > 0.
Notably, this theorem guarantees the existence of solutions with finite support; the proof makes use of the minimax the- orem (egg. Sion, 1958) in conjunction with Carathéodory's theorem on convex hulls (Carathéodory, 1911).
Theorem 3.1. Suppose that F: + Rd measurable and there exists such that every & E 4 is L-Lipschitz con- tinuous. Then, for any >> 0, there exists an e-approximate solution to the --EVI problem.
Complexity Having established some basic existence properties, now turn to the complexity of 4-EVIs. Let us define the VI gap function VIGap(x) == min (F(x), x' - x). which is nonnegative, If we place no restrictions on Φb it turns out that 4-EVIs are tan- tamount to regular VIs:
In particular, our existence proof does not rest on F be- ing continuous. Instead, we consider the continuous func- tion F that maps + (E,))(, F()) (Claim C.I), where (x) is the Euclidean ball centered at a with radius = d(e). It then suffices to invoke Brouwer's fixed-point theorem for the gradient mapping + lx F())), where 1Ix is the Euclidean projection with respect to X.
Proposition 3.6. If d contains all measurable functions from X to X, then any solution μ. +(X) to the c- approximate --EVI problem satisfies
Theorem 3.1 implies that a 4-EVI can have approximate solutions even when the associated VI problem does not.?
E VIGap(x) S.. 2014
(4)
Corollary 3.2. There exists a VI problem that does not admit approximate solutions when e = (11,, but the corre- sponding e-approximate --EVI is total for any e > O.
In proof, it suffices to consider a è that maps x E X to an appropriate point in ar (F(x), x' x)) When i must be given explicitly, Proposition 3.6 immediately implies that Φ-EVIs are computationally hard, because (4) implies that VIGap(æx) S for some in the support of p. and such point can be identified in polynomial time.
In the proof, we set F to be the sign function (Example C.2). By contrast, if one insists on exact solutions, EVIs do not necessarily admit solutions.
Proposition 3.3. When F is not continuous, there exists an EVI problem with no solutions.
Corollary 3.7. The c-approximate --EVI problem is PPAD- hard even when is an absolute constant and F is linear.
Furthermore, Theorem 3.1 raises the question of whether it is enough to instead assume that every & E & is continuous. Our next result dispels any such hopes.
Coupled with Proposition 3.6, this follows from the hard- ness result of Rubinstein (2015) concerning Nash equilib- ria in (multi-player) polymatrix games (for binary-action, graphical games, Deligkas et al., 2023 recently showed persists up
Theorem 3.4. There are 4- EVE instances that do not admit c-approximate solutions even when = =1)), is piece- wise constant, and & contains only continuous functions.
< 1/2). Corollary 3.7 notwithstanding, it is easy to see that the set of solutions to h-EVIs is convex for any $ C x
that
Our final result on existence complements Theorems 3.1 and 3.4 by showing that when & is finite-dimensional, it is enough if every o & admits a fixed point (this holds, for example, when o continuous by Brouwer's 's theorem).
Remark 3.8. Let X = X2 x... X,, as in an n-player game. Whether Corollary 3.7 applies under deviations that can be decomposed as 6 : x -> ((x)) = ( (d1))..., &n (R.)) is major open question in the regime where << 1 (cf. Dagan et al., 2024; Peng & Rubinstein, 2024).
Nonncontiuuity of F manifests itself prominently in nonsmooth optimization (e.g.. Zhang et al., 2020; Davis et al., 2022; Tian et al., 2022; Jordan et al., 2023a); recent research there focuses on Gold- stein stationary points (Goldstein, 1977), which conceptually related to EVIs.
"This argument carries over without restricting the support of 14, by assuming instead access to sampling oracle from μc: standard Chernoff bound implies that the empirical distribution (w.rt, a large enough sample size) approximately satisfies (4).
4

---

Expected Variational Incqualities
Viewed differently, special case of the Φ-EVI problem arises when Tb } and F(æ)) fixed map Φ X' + X. In this case, the 2-EVI problem reduces to finding a E ((2) such that
y E I,", it either returns a hyperplane separating y from y or a good-enough--espons x E X. They showed that Theo- rem 2.1 can be extended under this weaker oracle (in place of GER and SEP); the formal version is given in Theorem C.4.
<(æ;), for some
1d(x) ==1² 2 -E. (5) EE (F(x), 0(x) x) = E zm1 zm1
In our setting, we consider the feasibility problem
find Φ E &LIN s.t.
(6)
As a result, je must contain in its support an c-approximate fixed point of ø, problem which is PPAD-hard already for quadratic functions (Zhang et al., 2024a).
(F()), - x) S - Vx X.
Equivalently,
Corollary 39. The e-approximate &-EVI problem PPAD- hard even when e an absolute constant, F is quadratic, and 4 } for a quadratic map o X X X.
find K Raxd s.t. (F(æ)), Kr xx) S -e V X, K Vx E X.
also worth noting that, unlike Corollary 3.7, in the corollary above contains only continuous functions.
This program is infeasible since, for any & E LLNN the fixed point of é makes the left-hand side of the constraint O. And a certificate of infeasibility is an e-approximate -LIN-EVI solution. Thus, it suffices to show how to run the ellipsoid algorithm on (6). By Theorem C.4, it suffices if for any K E Rdxd, we can compute efficiently either
It also follows from (5) that for 0, Φ-EVIs capture exact fixed points. The complexity class FIXP characterizes such problems (Etessami & Yannakakis, 2007).
Corollary 3.10. The &-VV problem is FIXP-hard, assum- ing that supp(u) S poly(d).
some æ E X such that Kæ x (GER), some hyperplane separating K from LLN (SEP).
Exponential lower bounds in terms of the number of func- tion evaluations of also follow from Hirsch et al. (1989).
This is precisely the semi-separation oracle solved by Daskalakis et al. (2025, Lemma 4.1), stated below.
On a positive note, the next section establishes polynomial- time algorithms when & contains only linear endomor- phisms.
Lemma 4.2 (Daskalakis al., 2025). There an algorithm that takes K E Raxd, runs in poly(d) time, makes poly (d) oracle queries to X, and either returns a fixed point X e x = Kx, or hyperplane separating K from LIN-
4. Efficient Computation with Linear Maps
On a separate note, Theorem 4.1 only accounts for approxi- mate solutions. We cannot hope to improve that in the sense that exact solutions might be supported only on irrational points even in concave maximization (cf. Proposition 6.3).
The hardness results of the previous section highlight the need to restrict the set & in order to make meaningful progress. Our main result here establishes a polynomial- time algorithm when & contains only linear endomorphisms.
4.1. Regret Minimization for EVIs on Polytopes
Theorem 4.1. If & contains only linear endomorphisms, the e-approximate &-EVI problem can be solved in time poly(d, (B(c) given a membership oracle for X.
One caveat of Theorem 4. 1 is that it relies on the impractical EAH algorithm. To address this limitation, we will show that 4-EVIs are also amenable to the more scalable approach of regret cimmizzation-abell with an inferior complexity growing as poly(1/e).
The proof relies on the ellipsoid against hope (EAH), and in particular, recent generalization by Daskalakis et al. (2025). In a nutshell, the main deficiency in the framework covered earlier in Section 2.1 is that one needs separation oracle for y (Theorem 2),,, where y' for us is the set of deviations Φ. Unlike some applications, in which ) has an explicit, polynomial representation (Papadimitriou & Roughgarden, 2008), that assumption needs to be relaxed to account for LLN (Daskalakis et al., 2025, Theorem 3.4).
Specifically, in our context, the regret minimization frame- work can be applied as follows. At any time t E N, we think of "learner" selecting point (t()) E X, whereupon F ()) is given as feedback from the "environment." so that the utility at time i reads - (t) F(x(())). ø-regret is a measure of performance in online learning, defined as
Daskalakis et al. (2025) address this by considering in- stead the SEPOrGER oracle. As the name suggests, for any
T Σ
R-Reg (T) == max ΦEO
(F(x (t) ((x -x(1)))) (1)).
WWe do not distinguish between affine and linear maps because we always X +- X x {1), in which case affine and linear maps coincide.
The uniform distribution μ on (x(()) ,..., (T)} is clearly (T) (TT//aapprooxi E-EVI solution.
5

---

Expected Variational Incqualities
In what follows, we will assume that X' is polytope given explicitly by linear constraints, L..,
Now, consider an e-approximate EVI solution f of the prob- lem defined by
X = for E R Ax S b}:
F= 21 U1()),
Va, 20 "n (z)))
where A E Qmmad and b E Q are given as input.
Such ja satisfies, by coneavity, Ei= 6e S G; it is not nec- essarily an e-approximate CCE since it is possible that for some i E [ri], all deviations strictly decrease i's utility (so that ô, in (7) is negative) is technically an average CCE in the parlance of Nadav & Roughgarden (2010). To capture CCE via 4-EVIs, one can instead consider a richer set of de- viations of the form (ZI...., In.) + (Zi...., 2.y..... In)
To minimize #-regret, we will make use of the template by Gordon et al. (2008), which comprises two components. The first is fixed-point oracle, which takes as input func- tion á E LLN and returns a point E A' with x ((=); given that o is linear, it can be implemented efficiently via linear programming. The second component is an algorithm for minimizing (external) regret over the set LLIN- In Theo- rem D.I, we devise a polynomial representation for PLIN:
for all i E [m] and x¹ E X.
Theorem 4.3. For an arbitrary polytope X given by explicis linear constraints, there is explicit representation of PuN as a polytope with (d + m²) variables and constraints.
A canonical example of the above formalism is a normal- form game, in which each constraint set X, is the probability simplex A (Ai) over a finite set of actions A,, and each utility u, is a multilinear function.
As a consequence, we can instantiate the regret minimizer operating over O LiN with projected gradient descent.
Example 5.2 (LCE). A distribution E A(X) is an e- linear correlated equilibrium (LCE) if for any E [x]]
Corollary 4.4. There is a deterministic algorithm that (T) S e after poly(d, poly(d,m)fe rounds, guarantees LLIN-Reg
max E u,(d((z;)), A waya
x-1) E (((x) S e, aryp
and requires solving a convex quadratic program with Odd + m²) variables and constraints in each iteration.
where D contains all linear functions from X; to X, To capture LCE via &-EVIs, it suffices to consider deviations of the form (#1...., m..) + (a11..-., (x.)), ....)................... Fn for all E [ri] and Φ, E ②,
An additional benefit of Corollary 4.4 compared to using EAH is that the former is more suitable in a decentralized environment- for example, in multi-player games (ef. Ex- ample 5.1). There, Corollary 4.4 corresponds to each player running their own independent no-regret learning algorithm. Even in this setting, our algorithms actually yield an im- provement over the best-known algorithms for minimizing rein-regret over sxplicitly-rerreeeeete
For normal-form games, LCEs amount to the usual notion of CEs (Aumann, 1974). LCEs were introduced in the context of extensive-form games (Farina & Pipis, 2023; 2024).
polytopes: the previ- ous state of the art, due to Daskalakis et al. (2025), requires running the ellipsoid algorithm each iteration, which is slower than quadratic programming (Appendix D).
Refining correlated equilibria In fact, and more surpris- ingly, -LIN-EII solutions can be a strict subset of LCEs. 5 This separation can already be appreciated in the setting of normal-fore games, and manifests itself in at least two distinct ways. First, there exist games for which a CE need not be solution to the - In this sense, - yield a computationally tractable superset of Nash equilib- ria that is tighter than CEs. Second, computation suggests that the set of solutions of the LIN--VI for the game need not be a polyhedron, unlike the set of CEs. We provide a graphical depiction of this phenomenon in Figure 1. The figure depicts the set of - solutions "Bach or Stravinsky" game, in which the players receive payoffss (3, 2) if they both pick Bach, (2, 3) if they both pick Stravinsky, and (0, 0) otherwise.
5. Game Theory Applications of EVIs
A major motivation for studying e-EVIs lies in a strong connection to (C)CEs (Aumann, 1974; Moulin & Vial, 1978) in games. Indeed, we begin this section by pointing out that d-EVIs capture (C)CEs for specific choices of +.
We will mostly consider n-player concave games. Here, each player i E [n] selects a strategy æ; E X; from some convex and compact set X, and its utility is given by u4 : (æ),..., ) + R. We assume that u, u,(æ; x=4) is differen- tiable and concave in 2; for any x-5, and that the gradients V a. u,, x)) are bounded. We let X := Xi x x Xn. Example 5.1 (CCE). A distribution l E A(2)) is an coarse correlated equilibrium (CCE) (Moulin & Vial, 1978) for any player E [n].
simple
'The example of Seref Ahunbay (2025, Example 1) already implies that certain CEs can be excluded from the set of -Vi-EE which, incidentally, could have implications for last-iterate conver- gence in some classes of games, as discussed by that author. Our example in Figure goes much further, revealing that -VN- can yield significantly different utilities for each player compared to C.S.
8, = max E ua -I) - E (((x) S. E
(7)
6

---

Expected Variational Incqualities
Interpretation The reason for this separation is that, for map : X' + X, each player's mapped strategy o(x:); can also depend (linearly) on other players' strategies --i-
Probability of Player 2's first actioon (Bach)
0.9
Currelated equil.
Pun-EVI solutions
0.8
VI sol. (Nash eq.)
Indeed, the EVI formulation of a game does not take into account the identities of the players. For this reason, we will call the set of LIN--VI solutions in a concave game anonymous linear correlated equilibria, or ALCE for short. We give two game-theoretic interpretations of ALCEs.
0.7
0.6
0.5
0.4
First, the ALCEs of game I are the symmetric LCEs of the "symmetrized" game in which the players are randomly shuffled before the game begins. That is, consider the n- player game pam defined as follows. Each player's strategy set is X. For strategy profile (x' (t'....,,")) x") E X", the utility to player i given by
0.3
0.2
0.1
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Probability of Player I's first action (Bach)
u; (x""
Σ GEB.
(2) (1)
F
(m)
Figure I. Marginals of the set of correlated equilibria (CE) and of the set of solutions to PLiNEVI in the simple 2 x 2 game "Bach Stravinsky." The and y-axes show the probability with which the two players select the first action (Bach). The of marginals of dILN-EVI solutions appears have curved boundary corresponding, we helieve, to the hyperbola 10x? 25xy + 10y² 6z + 11y
n!
where G, is the set of permutations a [n] + [n]. The following result then follows almost by definition.
Proposition 5.3. For a given distribution μ E (XX), define the distribution n² A(X") by sampling x P and oututting (I..... (2....,]] x) E X". Then, is ALCE of if and only if pn is LCE of 1
Definition 5.4. Given an n- n-player pseudo game with con- cave, differentiable utilities and joint constraints X, a distri- bution μ E ((x) an e-ACCE
Second, for normal-form games, the ALCEs are the distri- butions/ μ E (X)) such that no player i has a profitable deviation of the following form. The correlation device first samples x ~ μl, and samples recommendations 0j ~ æj for each player j. Then, the player selects another player j (possibly j i) whose recommendation it wishes see. The player then observes sample dj Zj that is inde- pendently sampled from a,. Finally, the player chooses an action af E A,, and each player gets reward uy (a,, a-i). Thus, players are allowed (modulo the independent sam- pling) to spy on each others' recommendations.
n
max E Φ 1
u,(o(z)
Σ (;(2) Se.
By virtue of our main result (Theorem 4.1), such an equilib- rium can be computed in polynomial time.
Noncontinuous gradients In fact, our results do not rest the usual assumption that each player's gradient is con- tinuous function, thereby significantly expanding the scope of prior known results even in games. For example, we refer to Dasgupta & Maskin (1986); Bichler et al. (2021); Martin & Sandholm (2024) for pointers to some applications.
Further discussion about ALCES and formal proofs of the claims in this section are deferred to Appendix F.
Coupled constraints Continuing from Examples 5.1 and 5.2, we observe that (VLis-)EVIs can be used even in "pseudo-games." in which X does not necessarily decom- pose into Xi x... X,; this means that æ; E (x))))). As we discuss in Appendix A, most prior work in such settings has focused on generalized Nash equilibria, with the ex- ception of Bernasconi et al. (2023). (fLiN)EEVIs induce an interesting notion of LCE/CCE in pseudo-games albeit not directly comparable to the one put forward by Bernasconi al. (2023). It worth noting that Bernasconi et al. (2023) left open whether efficient algorithms for computing their notion of (coarse) correlated equilibria exist.
Nonconcave games Last but not least, 4-EVIs give rise to a notion of local d-equilibrium (Definition G.1) in non- concave games. It turns out that this captures recent results by Cai et al. (2024a) and Şeref Ahunbay (2025), but our framework has certain important advantages. First, we give poly(d, log(1/c))--inn) algorithm (Theorem 4.1), while theirs scale polynomially in 1/e. Second, our results do not assume continuity of the gradients. And finally, our algorithms are polynomial even when O contains all lin- car endomorphisms (Theorem 4.1). Appendix G elaborates further on those points.
Thiis independence is erucial: without it, μ would actually need to be a distribution over pure Nash equilibria!
7

---

Expected Variational Incqualities
6. Problems Where EVIs Coincide with VIs
Any reasonable solution concept for such problems should place all mass on global maxima; EVIs pass this litmus test:
We saw earlier, in Proposition 3.6, that when & comprises all functions from X' to X, the Φ-EVI problem is tantamount to the associated VI problem. However, if one restricts the functions contained in C are there still structured VIs where we retain this equivalence? In this section, we consider certain structured VIs, and show their equivalence to the corresponding EVIS (that is, Pcon-EVis). Unlike general VIs, the ones we examine below are tractable.
Proposition 6.3. Let F = -Vu for a "-quasar-coneave and differentiable function X - R. Then, for any solution μ E A(X) to the EVI problem.
E
u(x) 2 max u(z).
xEA
Thus. P Fa>p|u((=) = u(x)] = for x' E argmax, u(x).
6.1. Polymatrix Zero-Sum Games and Beyond
Indeed, by Definition 6.2, 0 I (Vul() a - x²) <
Ty Eezz [u(x)) u [I] for any EVI solution E A
The first important class of VIs we consider is described by a condition given below.
Thus, under quasar-concavity, VIs basically reduce to EVIs.
Proposition 6.1. Suppose that any x' E Ex, the function
7. Performance Guarantees for EVIS
g : x + (F(x), x' - x) is concave. Then, if μ E A(X) is an e-approximate solution to the EVI, Eawny x is an e- approximate solution to the VI.
In many settings, a VI solution is used proxy to ap- proximately maximize some underlying objective function; machine learning offers many such applications. The ques- tion is whether performance guarantees pertaining to VIs can be extended extended-polentiallyy with some small degradation- to EVIs as well. The purpose of this section is to provide a framework for achieving that based on the following notion.
The proof follows directly from Jensen's 's inequality.
The precondition of Proposition 6.1 is satisfied, e.g., when: (i (F(x). z)) 0 for all æ E X, and (ii) F is linear map. In the context of rt-player games, the first condition amounts to the zero-sum property: Σ (z(xz) = O for all æ. Of course, this property is not enough to enable efficient compu- tation of Nash equilibria, for every two-player (general-sum) game can be converted into 3-player zero-sum sum game. This where the second condition comes into play: F is linear that is, each player's gradient must be linear in the joint strategy. Those two conditions are satisfied in polyma- trix zero-sum games (Cai et al., 2016); in such games, the conclusion of Proposition 6.1 is a well-known fact.
Definition 7.1. An EVI problem is (A, --smooh, for À > 0, > -1, W.r.t. W : X + IR and x= E argmax, W (ax if
(F(x), xx)) S - (W()))+(
Va E X.
Example 7.2. When the underlying problem corresponds to a multi-player game and W is the (utilitarian) social wel- fare, Definition 7.1 coincides with the celebrated notion of smoothness à la Roughgarden (2015); this is a consequence of multilinearity, which implies that W (x) = - -(x F(w)) and (x* F())) = - Σ uz(x", xx-) for all æ E X We also refer to the recent treatment of smoothness by Şeref Ahumbay (2025) in the context of nonconeave games, which builds on the primal-dual framework of Nadav & Roughgar- den (2010).
6.2. Quasar-Concave Functions
We next consider the problem of maximizing (single) func- tion that satisfies giaasr-ccncavviy-11 natural generaliza- tion of concavity that has received significant interest (Hardt et al., 2018; Fu et al., 2023; Hinder et al., 2020; Gower et al., 2021: Guminov et al., 2023; Caramanis et al., 2024).?
Definition 7.1 an extension of the more general notion of "local smoothness," introduced by Roughgarden & Schopp- mann (2015) in the context of splittable congestion games. However, it goes beyond games. Indeed, the following def- inition we introduce generalizes Definition 6.2, making a new connection between smoothness and quasar-concavity.
Definition 6.2 Quasar-concavitt). Let E [0,1] and x* E X' be a maximizer of differentiable function u X - IR. We say that u is y-quasar-conean with respect to x= if
1 u(x') S u(x) + ?
(Vu(z), x² - x) Va E X.
Definition 7.3 (Extension of quasar-concavitty. Let x² e (8)
X' be a maximizer of a differentiable function : X + R. We say that u is (A, (X,v)- "-smooth with respect to x= if
In particular, in the special case where 7 = 1, (8) is equiv- alent to star-concavity (Nesterov & Polyak, 2006). If in addition (8) holds for all x= E X' (not merely w.r.t a global maximizer), it captures the usual notion of concavity.
(Vu(x), xt xx) 2 >u(x=*) (v + 1))(x))
Vx E X.
Prrior literature mostly uses the term quasar-converity which is equivalent to quasar-concavity for the opposite function -u.
In particular, when À := y and v == - 1, the above definition captures 7-qqasar-coneavitty Appendix E, we
8

---

Expected Variational Incqualities
provide an example of polynomial that satisfies Defini- tion 7.3 without being quasar-concave. Now, the key prop- erty of Definition 7.1 is that any EVI solution approximates the underlying objective- by factor of p := A/2+v.
cial support. E.T. and R.E.B. also supported in part by the Cooperative AI PhD Fellowship. G.F is supported by the National Science Foundation grant CCF-2443068. We are grateful to Mete Şeref Ahunbay for his helpful feedback. We also thank Andrea Celli and Martino Bernasconi for discussions regarding P-equilibria in games with coupled constraints.
Theorem 7.4. Lei E ((X) be an e-approximate solution to a (A, -moooh EVI problem w.r.. W : :X + R. Then,
(() 2 m~p
E
max (x) FE
1+
1 1+
References
The proof follows directly from Definition 7.1, using that Ba-x(F(x), x) 2 c and linearity of expectation.
Alacaoglu, A., Böhm, A., and Malitsky, Y. Beyond the golden ratio for variational inequality algorithms. Journal of Machine Learning Research, 24:172:
2023.
8. Conclusions and Future Research
Aliprantis, C. D. and Border, K. C. Infinite Dimensional Analysis: Hitchhiker's Guide. Springer, 2006.
In summary, our main contribution was to introduce and examine a natural relaxation of VIs, which we refer to as ex- pected VIs. Unlike VIs, which are marred by computational intractabilityy, we showed that EVIs can be solved efficiently under minimal assumptions. We also uncovered many other intriguing properties of EVIs (cf. Table 1).
Anagnostides. I., Panageas, I., Farina, G., and Sandholm, T. Optimistic policy gradient in multi-player Markov games with single controller: Convergence beyond the Minty property. In Conference on Artificial Intelligence (AAAT), 2024.
There are many promising avenues for future work. VIs enjoy a great reach a wide range of applications, some of which were discussed earlier in our introduction. It would be interesting to explore in more detail how EVIs fare in such settings compared to VIs. In particular, given that EVIs relax VIs, in addition to their more favorable computational properties, it is likely that they unlock new, more desirable solutions not present under VIs. For example, it is well known (e.g., Ashlagi et al., 2005) that CEs can achieve better welfare than Nash equílibria in games. In light of the prominence of correlated equilibria in the rich setting of multi-player games, we anticipate EVIs solidify their place also in other application areas beyond the realm of game theory.
Ardagna, D., Panicucci, B., and Passacantando, M. General- ized Nash equilibria for the service provisioning problem in cloud systems. IEEE Transactions on Services Com- puting, 6(4):4294442, 2012.
Arrow, K. J. and Debreu, G. Existence of an equilibrium for a competitive economy. Econometrica, 22(3):265-290, 1954.
Ashlagi, I., Monderer, D.,, and Tennenholtz, M. On the value of correlation. In Conference in Uncertainty in Artificial Intelligence (UAI), 2005.
Aumann, R. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96. 1974.
Impact Statement
Babichenko, Y. Query complexity of approximate Nash equilibria. Journal of the ACM, 63(4):36:11366) 2016.
This paper presents work whose goal advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bauschke, H. H., Moursi, W. M., and Wang, X. General- ized monotone operators and their averaged resolvents. Mathematical Programming, 189(1):55-74, 2021.
Bernasconi, M., Castiglioni, M., Marchesi, A., Trovò, F., and Gatti, N. Constrained Phi-equilibria. In International Conference on Machine Learning (ICML), 2023.
Acknowledgments
T.S. is supported by the Vannevar Bush Faculty Fellow- ship ONR N00014-23-1-2876. National Science Foun- dation grants RI-2312342 and RI-1901403, ARO award W911NF2210266, and NIH award A240108S001. B.H.Z. is supported by the CMU Computer Science Department Hans Berliner PhD Student Fellowship. E.T, R.E.B., and V.C. thank the Cooperative AI Foundation, Polaris Ventures (formerly the Center for Emerging Risk Research) and Jaan Tallinn's ' advored fund at Founders Pledge for finan-
Bernasconi, M., Castiglioni, M., Celli, A., and Farina, G. On the role of constraints in the complexity of min-max optimization. arXiv:2411.03244 2024.
Bichler, M., Fichtl, M., Heidekrüger, S., Kohring, N., and Sutterer, P. Learning equilibria in symmetric auction games using artificial neural networks. Nature Machine Intelligence, 3(8):687-695, 2021.

---

Expected Variational Incqualities
Billingsley, Convergence of Probability Measures. Wi- ley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, second edition, 1999.
Courno, A. A. Recherches sur les principes mathématiques de la théorie des richesses (Researches into the Mathe- matical Principles of the Theory of Wealth). Hachette, Paris, 1838.
Black, F. and Scholes, M. The pricing of options and cor- porate liabilities. Journal of Political Economy, 81(3): 637-654, 1973.
Dafermos, S. Traffic equilibrium and variational inequalities. Transporlution Science, 14(1):42-54, 1980.
Böhm, A. Solving nonconvex cow.neecanncccccveeeee min-max prob- lems exhibiting weak Minty solutions. Transactions on Machine Learning Research, 2023.
Dagan, Y., Daskalakis, C., Fishelson, M., and Golowich, N. From external to swap regret 2.0: An efficient reduction for large action spaces. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2024.
Boyd, S. and Vandenberghe, L. Conver Optinization. Cam- bridge University Press, 2004.
Dasgupta, P. and Maskin, E. The existence of equilibrium in discontinuous economic games 1: Theory. Review of Economic Studies, 13:1-26, 1986.
Cai, Y., Candogan, O., Daskalakis, C., and Papadimitriou, C. H. Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2): 648 655, 2016.
Daskalakis, C. Non-concave games: A challenge for game theory's 's next 100 years, 2022.
Daskalakis, C., Goldberg, P., and Papadimitriou, C. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 2008.
Cai, Y., Daskalakis, C., Luo, H., Wei, C.,, and Zheng, W. On tractable D-equilibria in non-concave games. In Proceed- ings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2024a.
Daskalakis, C., Skoulakis, S., and Zampetakis, M. The com- plexity of constrained min-max optimization. In Proceed- ings of the Annual Symposium on Theory of Computing (STOC), 2021.
Cai, Y., Oikonomou, A., and Zheng, W. Accelerated algo- rithms for constrained conconvex-noncomcaal min-max optimization and comonotone inclusion. In International Conference on Machine Learning (ICML), 2024b.
Daskalakis, C., Farina, G., Golowich, N., Sandholm, T., and Zhang, B. H. A lower bound on swap regret in extensive- form games. arXiv:2406. 101::240..1311,, 2024.
Capatina, A. Variational inequalities and frictional contact problems, volume 31. Springer, 2014.
Daskalakis, C., Farina, G., Fishelson, M., Pipis. C., and Schneider, J. Efficient learning and computation of lin- ear correlated equilibrium general convex games. In Proceedings of the Annual Symposium on Theory of Com- puting (STOC), 2025.
Caramanis, C., Fotakis, D., Kalavasis, A., Kontonis, V., and Tzamos, C. Optimizing solution-samplers for combinato- rial problems: the landscape of volicy-gradics methods. In Proceedings of the Annual Conference Neural In- formation Processing Systems (NeurIPS), 2024.
Davis, D.,, Drusvyatskiy, D., Lee, Y. T., Padmanabhan, S., and Ye. A gradient sampling method with complex- ity guarantees for Lipschitz functions in high and low dimensions. In Proceedings of the Anmual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Carathéodory, C.
Uber den Variaec der Fourier' schen Konstanten von positiven harmonischen Funktionen. Rendiconti del Circolo Matematico de Palermo, 32:193-217, 1911.
Chen, X., Deng, X., and Teng, S.-H. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 2009.
Deligkas, A., Fearnley, J., Hollender, A., and Melissour- gos, T. Tight inapproximability for graphical games. In Conference on Artificial Intelligence (AAAI), 2023.
Choudhury. S., Gorbunov, E., and Loizou, N. Single- call stochastic extragradient methods for structured non- monotone variational inequalities: Improved analysis un- der weaker conditions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurlPS), 2024.
Diakonikolas, J., Daskalakis, C., and Jordan, M. I. Efficient methods for structured nonconvex-nonccomaav min-max optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS). 2021.
Domingo-Enrich, C., Jelassi, S., Mensch, A., Rotskoff, G. M. and Bruna, J. A mean-field analysis of two- player zero-sum games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020. 2020.
Combettes, P. L. and Pennanen, T. Proximal methods for cohypomonotone operators. SIAM Journal on Control and Optimization, 43(2):331-742, 2004.
10

---

Expected Variational Incqualities
Etessami, K. and Yannakakis, M. On the complexity of Nash equilibria and other fixed points. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2007.
Gordon, G. J., Greenwald, A., and Marks, C. No-regret
learning in convex games. In International Conference Machine Learming (ICML), 2008.
Gower, R. M., Sebbouh, O., and Loizou, N. SGD for struc- tured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference Artifi- cial Intelligence and Statistics (AISTATS), 2021.
Facchinei, F. and Kanzow, C. Generalized Nash equilibrium problems. Annals of Operations Research, 175(1):177- 211, 2010.
Greenwald, and Jafari, A. A general class of no-regret learning algorithms and game-theoretic equilibria. In Conference on Learning Theory (COLT), 2003.
Facchinei, F. and Pang, J.-S. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
Grötschel, M., Lovász, L.,, and Schrijver, The ellipsoid method and its consequences in combinatorial optimiza- tion. Combinatorica, 1:169-197, 1981.
Facchinei, F., Fischer, A., and Piccialli, V. Generalized Nash equilibrium problems and Newton methods. Math- ematical Programming, 117(1):163-19)))) 194, 2009.
Grötschel, M., Lovász, L.., and Schrijver, A. Geometric algorithmss and combinatorial optimization. Springer, 1993.
Farina, G. and Pipis, C. Polynomial -ietommmll--emeeeeeeee linear-swap regret minimization in imperfect-information sequential games. In Proceedings of the Annual Conference on Neural In- formation Processing Systems (NeurIPS), 2023.
Guminov, S., Gasnikov, A. V., and Kuruzov, A. Accel- erated methods for bookkl-qquss-conee optimization problems. Computational Management Science, 20(1): 36, 2023.
Farina, G. and Pipis, C. Polynomial-time time computation ex- act Phi-equilibria polyhedral games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Hardt, M., Ma, T., and Recht, Gradient descent learns
linear dynamical systems. Journal of Machine Learning Research, 19(1):1025- 1068, 2018.
Farina, G., Celli, A., Marchesi, A., and Gatti, N. Simple un- coupled no-regret learning dynamics for extensive-form correlated equilibrium. Journal of the ACM, 69(6)41:1- 41:41, 2022.
Hart, S. and Mas-Colell, A. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 33:1830-1835 2003.
Fischer, A., Herrich, M., and Schönefeld, K. Generalized Nash equilibrium problems-recent advances and chal- lenges. Pesquisa Operacional, 34(3):521-5566 2014.
Hazan, E. Introduction to online convex optimization.
Foundations and Trends Optimization, 2(3-4))1577325, 2016.
Fu. Q., Xu, D., and Wilson, A. C. Accelerated stochastic optimization methods under quasar-convexity. In Interna- tional Conference on Machine Learning (ICML), 2023.
Hinder, O., Sidford, A., and Sohoni, N. S. Near-optimal methods for minimizing star-convex functions and be- yond. In Conference on Learning Theory (COLT), 2020.
Hirsch, M. D., Papadimitriou, C. H., and Vavasis, S. A.
Fujii, K. Bayes correlated equilibria and no-regret dynamics. arXiv:2304.05000, 2023.
Exponential lower bounds for finding Brouwer fix points. Journal of Complexity, 5(4):379 1989.
Goktas, D. and Greenwald, A. Exploitability minimization in games and beyond. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Hsich, Y., Liu, C., and Cevher, V. Finding mixed Nash equi- libria of generative adversarial networks. In International Conference on Machine Learning (ICML), 2019.
Huang, W. and von Stengel, B. Computing an extensive- form correlated equilibrium in polynomial time. In Inter- national Workshop On Internet And Network Economics (WINE), 2008
Goldstein, A. Optimization of Lipschitz continuous func- tions. Mathematical Programming, 13:14-22, 1977.
Gorbunov, E., Taylor, A. B., Horváth, S., and Gidel, G. Con- vergence of proximal point and extragradient- based meth- ods beyond monotonicity: the case of negative comono- tonicity. In International Conference on Machine Learn- ing (ICML), 2023.
Jordan, M. I., Kornowski, G., Lin, T., Shamir, O., and Zam- petakis, M. Deterministic nonsmooth nonconvex opti- mization. In Conference on Learning Theory (COLT), 2023a.

---

Expected Variational Incqualities
Jordan, M. I., Lin, T., and Zampetakis, M. First-order algorithms for nonlinear generalized Nash equilibrium problems. Journal of Machine Learning Research, 24: 38:1-38:46, 2023b.
Nash, J. Non-cooperative games. Annals of Malhematics, 54:289-295, 1951.
Nesterov, Y. and Polyak, B. Cubic regularization of newton method and its global performance. Mathematical programming, 108(1):177-20) 2006.
Kapron, B. M. and Samieefar, K. The computational com- plexity of variational inequalities and applications in game theory. arXiv:2411.04392 2024.
Papadimitriou, C. H. and Roughgarden, T. Computing cor- related equilibria in multi-player games. Journal of the ACM, (::33):4:11144:: 2008.
Kinderlehrer, D. and Stampacchia, G. An introduction to variational inequalities and their applications. SIAM, 2000.
Patris, N. and Panageas, I. Learning Nash equilibria in rank-1 1 games. In International Conference on Learning Representations (ICLR), 2024.
Kuhn, H. W. Extensive games and the problem of infor- mation. In Contributions to the Theory of Games, vol- ume of Annals of Mathematics Studies, 28, pp. 193-216. Princeton University Press, 1953.
Peng, B. and Rubinstein, A. Fast swap regret minimiza- tion and applications approximate correlated equilibria. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2024.
Lee, S. and Kim, D. Fast extra gradient methods for smooth structured nonnonvvvv minimax problems. In Proceedings of the Annual Conference on Neural Infor-
mation Processing Systems (NeurIPS), 2021.
Pethick, T., Latafat, P., Patrinos, P., Fercoq, O., and Cevher, V. Escaping limit cycles: Global convergence for con- strained nonconvex-nonconcat minimax problems. In International Conference on Learning Representations (ICLR), 2022.
Lovász, L. and Vempala, S. S. Simulated annealing in con- vex bodies and an O" (n*) volume algorithm. J. Comput. Syst. Sci., 72(2):392 2006.
Martin, C. and Sandholm, T. Noint-perturbation simultane- ous pseudo-gradient. arXiv:2408, 09306, 2024.
Roughgarden, T. Intrinsic robustness of the price of anarchy. Journal of the ACM, 62(5):32:1-32:44, 2015.
Mertikopoulos, P. and Zhou, 7. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, (73(1-2):465-50) 2019.
Roughgarden, T. and Schoppmann, F. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317-342, 2015.
2019.
Milionis, J., Papadimitriou, C., Piliouras, G., and Spendlove, K. An impossibility theorem in game dynamics. Pro- ceedings of the National Academy of Sciences, 120(41), 2023.
Roughgarden, T., Syrgkamis, V., and Tardos, É. The price anarchy in auctions. Journal of Artificial Intelligence Research, 59:59-101, 2017.
Morrill, D., D'Orazio, R., Lanctot, M., Wright, J. R., Bowl- ing, M., and Greenwald, A. R. Efficient deviation types and learning for hindsight rationality in extensive-form games. In International Conference Machine Learning (ICML), 20
Rubinstein, A. Inapproximability of Nash equilibrium. In Proceedings of the Annual Symposium on Theory of Com- puting (STOC), 2015.
Rubinstein, A. Settling the complexity of computing ap- proximate two-player Nash equilibria. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2016.
Morrill, D., D'Orazio, R., Sarfati, R., Lanctot, M., Wright, J. R., Greenwald, A. R., and Bowling, M. Hindsight and sequential rationality of correlated play. In Conference on Artificial Intelligence (AAAI). 2021b.
Sion, M. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171 176, 1958.
Moulin, H. and Vial, J.PP. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 733-4):201-2211 1978.
Stoltz, G. and Lugosi, G. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, (91):18772008 2007.
Nadav, U. and Roughgarden, T. The limits of smoothness: A primal-dual framework for price of anarchy bounds. In International Workshop On Internet And Network Eco- nomics (WINE), 2010.
Tatarenko, T. and Kamgarpour, M. Learning generalized Nash equilibria in a class of convex games. IEEE Trans- actions on Automatic Control,
2018.
12

---

Expected Variational Incqualities
Tian, L., Zhou, K., and So, A. M. On the finite-time com- plexity and practical computation of approximate station- arity concepts of lipschitz functions. In International Conference on Machine Learning (ICML), 2022.
Villani, C. Optimal transport: old and new, volume 338.
Springer, 2009.
Zhang, B. H., Anagnostides, I., Farina, G., and Sandholm, Efficient f-rregret minimization with low- oewreegee swap deviations in extensive-form games. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2024a.
Zhang, B. H., Farina, G., and Sandholm, T. Mediator in- terpretation and faster learning algorithms for linear cor- related equilibria in general extensive-form games. In International Conference Learning Representations (ICLR), 2024b.
Zhang, B. H., Anagnostides, Tewolde, E.,, Berker, E., Farina, G., Conitzer, V., and Sandholm, Learning and computation of @-equilibria the frontier of tractability. In Proceedings of the ACM Conference on Economics and Computation (EC), 2025.
Zhang, J., Lin, H., Jegelka, S., Sra, S., and Jadbabaic, A. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference Machine Learning (ICML), 2020.
Seref Ahunbay, M. First-order (coarse) correlated equilibria in non-concave games. /8/744 2025.
13

---

Expected Variational Incqualities
A. Further Related Work
We have seen that Definition 1.2 is strongly connected with the notion of Q-equilibria. In extensive-form games, the question of characterizing the set of deviations & that enables efficient saaming-witting the no-regret framework- computation has attracted considerable attention. In particular, efficient algorithms have been established for extensive-form correlated equilibria (EFCEs) (Huang & von Stengel, 2008; Farina et al., 2022; Morrill et al., a0)];;b), and more broadly, when & contains solely linear functions (Farina & Pipis, 2024; (023))_corresponding to linear correlated equilibria (LCEss, Recently, Daskalakis et al. (2025) strengthened those results beyond extensive-fore form games whenever there is a separation oracle for the constraint set; we rely on their approach for some of our positive results. Moreover, Zhang et al. (2024a; 2025) established certain positive results even when @ contains low-degres polynomials; by contrast, in our setting, 4-EVIs are hard even when & contains only quadratic polynomials (Corollary 3.9).
Besides encompassing correlated equilibria in games, wherein the constraint set X' can be decomposed as Cartesian product over the constraint set of each player (reflecting the fact that players select strategies independently), our positive results pertaining to Definition 1.2 do not rest on such assumptions and apply even in the presence of joint constraint sets, There is a long history in game theory, optimization, and economics pertaining to such sometiesss referred to as "pseudo-games" in the literature (Goktas & Greenwald, 2022; Arrow & Debreu, 1954; Facchinei & Kanzow, 2010; Fischer et al., 2014; Facchinei et al., 2009; Ardagna et al., 2012: Tatarenko & Kamgarpour, 2018; Jordan et al., 2023b; Daskalakis et al., 2021). The notion of generalized Nash equilibria- the natural counterpart of Nash's 's solution concept in the presence of coupled constraints-has dominated that line of work, with the recent paper of Bernasconi al. (2023) being the notable exception.
Responding to the call of Daskalakis (2022), Cai et al. (2024a) and Şeref Ahunbay (2025) recently proposed several tractable solution concepts in games with nonconcave utilities. In particular, when specialized to games, Φ-EVIs are closely related to notion proposed by Şeref Ahunbay (2025, Definition 6). One of our key results, Theorem 1,1, establishes a poly(d, log(l/)))-time algorithm, while the algorithms of Cai et al. (2024b) and Şeref Ahunbay (2025) scale polynomially in 1/c. Also, Theorem 4.1 1 applies even when & contains all linear endomorphisms (Theorem 4.1). From a more conceptual vantage point, a significant part of our contribution is extend the scope of such results beyond games, as we have already highlighted.
Kapron & Samicefar (2024) and Bernasconi et al. (2024) recently studied the computational complexity of VIs, and generalizations thereof-namell quasi VIs, establishing PPAD-completeness under mild assumptions. Whether our framework can be extended to encompass quasi VIs is left as an interesting direction for the future.
Finally, it would be remiss not to point out that our VI relaxation is in the spirit of "lifting," a standard technique whereby the original problem lifted to a higher-dimensional space to gain more analytical and computational leverage; a concrete example, in the context of optimal transport theory, is Kantorovich's 's relaxation of Monge's 's formulation (Villani, 2009). Such techniques have been fruitful in the context of min-max optimization (Hsieh et al., 2019; Domingo-Enrich et al., 2020).
B. Additional Preliminaries
In order to define the distributions A (x)) over X' precisely, we recall here some basic concepts from probability theory. We refer to Billingsley (1999, Chapter and 2) and Aliprantis & Border (2006, Chapter 15) for detailed treatments. We assume throughout the paper that the set X' C Rd is Borel measurable. Let (xx) be the set of Borel probability measures μ on X, that is. measures μu: (X, B(x)) + (RR (R)) with μ(x²) 1, where B(X) and B(R) denote the respective alaeebra of Borel sets. We simply call fæ a distribution. For any Borel measurable function f + R henceforth just measurable- we can then take the integral Eg [xx)] == fx f(xx (x)). In particular, for Ex ( (F(x),
Revisiting Definition 1.2
æ)) in Definition 1.2 to be well-defined, we assume throughout this paper that F and each & E t are measurable functions.
For our computational results (Section 4), we are making a standard assumption regarding the geometry of X (Section 2); this can be met by bringing X' into isotropic position. In particular, there is a polynomial-time algorithm that computes an affine transformation to accomplish that (Lovász& & Vempala, 2006), and minimizing linear-swap regret reduces to minimizing linear-swap regret to the transformed instance (Daskalakis et al., 2025, Lemma A.1).
14

---

Expected Variational Incqualities
C. Omitted Proofs
This section contains the proofs omitted from the main body.
C.1. Existence of 4-EVI solutions
We begin with Theorem 3.1.
Theorem 3.1. Suppose that F X Rd is measurable and there exists L such that every + is L-Lipschitz
continuous. Then, for any 0, there exists an e-approximate solution to the --EVI problem.
Proof. We define function :s: + R
J
Fs
F())dv());
BB(x))
Bi(a)n
this is rescaled Lebesgue integral, which represents multivariate local average. Above,
8 > 0 is a sufficiently small parameter, to be defined shortly;
Bx(x)) C Rd is the (closed) Euclidean ball radius 5 centered at æ; and
-1- denotes the set's Borel measure.
Given that F is assumed be bounded, we can define B E IR such that max [[())]] suffice to set 5 : B))
S B. For the proof below, it will
We first observe that F3 is continuous.
Claim C.1. Fg is continuous.
Proof. We will show that for any X' and é' > 0, we choose 8' = 8''')) such that for any x' E X with || x'll < 8,
(x)))) Pa(x')) <
By the triangle inequality, the difference [[x) (xx'll be decomposed the sum of
= [B5(x) nx (s(x')) n x 1/ Bi(a)nx
1
[F())]ldv(2)
and
F(Z)du(()
JBs d())
[Bx(x') nx
Bi(a)nxx
Now, A can be bounded
Bx(xx) n X1|
1
H B
S Z
[B((x') 0 nX
where we selected 8' small enough so that
(1 (1-B) 1-13)1B(C)) (x((')) n xI (3) x
1+ B
|Bs(x') nx
Moreover, by selecting 8' small enough that
(x) nx)) (144)))))n1))))1114444))))1)1111
(B())))) < (B(''())) nx),
2B
we have
Veleaxx F())du(i)
1 J ) F())du(@)
{ /BBle)n0001BB (z)) I J:BuG))nneneeeaerrm [F
1 _ BB(('') nx ()) n (((((2)))) (B, (x)
15

---

Expected Variational Incqualities
where the last inequality uses (9). As result, have shown that A e', thereby implying that (((())))((2)))) s This completes the proof.
Having established that Fs is continuous, where recall that 1Ix denotes the Euclidean projection onto X. This implies that there is point A such that = 1x - Fz(z)). Moreover, such point satisfies the VI constraint with respect to Fg:
now apply Brouwer's s fixed point theorem the map + Ixx Fa()))
(Fs (x). x' σ)) 2 0
x' E E
for example, see Kinderlehrer & Stampacchia (2000, Section for the derivation. Finally, we define μ e A(X) be the uniform distribution over (x) X. Then, for any Φ E 4,
(Fo(z). x) (F 6(z) x)
z-
E. (F(#), x)) + E (F()) (()))
E (F(3), 8)
(10)
Bmp
m~p
The first term in (10) can be bounded
E (F(0) <
E Kmp
[[
E amuje
| æ112 < EB,
(11)
where we used the Beuchy-Sehware inequality, the fact that |F())] support of p. Similarly, the second term in (10) can be bounded
B for all & e and || æll S 8 for all T in the
E (F()), <(x)) <())) S Trup
E amp
F())|12
E Bruje
((2))
V
L
E km1
[F(T)
- 21 < 8BL, Km
E
(12)
V
where we additionally used the assumption that o is I.-Lipschitz continuous. Combining (11) and (12) with (10), have
(( T) 2 - ( - 1)B + (Fo(z), ((x) - x)) 2 -5((. + 1)
and this holds for any & E क. Setting 5 f/(1+1)) completes the proof.
We next proceed with Corollary 3.2 and Proposition 3.3, which restated below.
Corollary 3.2. There exists VI problem that does admit approximate solutions when (()), but the corresponding c-approximate &-EVI is total for any >> O.
Proposition 3.3. When F is not continuous, there exists an EVI problem with no solutions.
We provide an example that will establish both of those claims.
Example C.2 (Discontinuous F; ef. Corollary 3.2 and Proposition 3.3). Let F(x)) be the sign function,
-1 if < otherwise,
F(x) sgn(2))
and X' = []. We first claim that there no c-approximate VI solution for c < 1. Indeed, = x) for any x 2 0. picking x' 1 ensures (F'(z) 2)
for any x < 0, picking x' ensures (F(x), x'
=
There is also exact EVI solution to this problem. Indeed, consider any lt A(X).
If P [x = 0] = 1, then taking r' = 1 ensures (F)))F(()),'' x) (F(0), x²) -1. Otherwise, taking x' = O, we have
E (F(x), amp
-x) E E <.
16

---

Expected Variational Incqualities
On the other hand, for any O, there exists an e-approximate EVI solution (as promised by Theorem 3.1). In particular, suppose that y uniformly picks between and c. Then, for any x' E E
1 (x' - = 1 (a' +c)+ E x)
2
worth pointing out that above example can be slightly modified so that exact EVI solutions do exist, as we explain below.
Example C.3 (Modification of Example C.2 with exact VI), We define F(x) identically to Example C.2, except F(1/2) =
-1. We claim that there is no solution for < 3/2: any æ + 1/2 by Example C.2, and æ = 1/2 is not solution since y ensures (F(x). x' 2) 1/2..
However, there is exact EVI solution: fix any x² E [0, 1/2) and consider f that uniformly mixes between x= and 1/2. Then, for any x' E X,
1 7(( x²) E (F(x), Tmp
2 x
2) 2 x²
>
Our next result reveals that the precondition of Theorem 3.1 with respect & cannot be relaxed to continuity.
Theorem 3.4. There are 4-EVI instances that do not admit e-approximate solutions even when O F is piecewise constant, and t contains only continuous functions.
Proof. As before, let Fxx) be the sign function.
F(x) = sgg(x)) = -1 if <<0, otherwise,
and μ E A[]-1,1) be any distribution. For d > O, let Ø8 [-1,1] + [-1, 1] be given by
I << -6,
(z)x) (xr 5)/8
if 20 < x S 0,
if r >>>> 0.
Further, let do(x)) := sgn(x). Every ds (with > 0) is continuous, by construction. Now, note that Φs -> Φu pointwise when 8 0, and every ds is bounded. As result, by the dominated convergence theorem, we have
lim EE [F(x)(os(z) - x)1 = E [F(z)( - z)] 8-0
きーッ 1-1 F(z) x] 55-1,
where the last line uses the fact that ((x))o(x) - sgn 1 and F(x) sgn x -
|z|| for all Thus, for any < 1, there must be some > for which (()(() -r)] < c, so l cannot be e-approximate EVI solution.
Continuing Section 3, next provide the proof of Theorem 3.5. Theorem 3.5. Suppose that
1. & is finite-dimensionall, that is, there exists k E N and a kernel map m X - I& such that every o E & can be expressed as Km(x) (x) for some K E Bdxk, and
2. every à 4 admits fixed point, that is, a point X a x = FP( such that o(x) = x.
Then, the EVE problem admits an 6-approximate solution with support size most + dl for every e > 0.
17

---

Expected Variational Incqualities
Proof. We assume, without loss of generality, that (as functions) the coordinates m. : X IR for S i S A are linearly independent. We further assume that is bounded, again without loss of generality. (Indeed, if for example my is unbounded, then column of K must contain all zeros, or else (x(x)) := Km(x) would be unbounded; we can thus freely remove such coordinates m:.)
Now, let K. == conv ( : ΦK E } be the set of matrices corresponding to maps in Φ; we can assume that IC closed. We can now rewrite the Ø-EVI problem as
find ME A(2)
s.t. E (F(x))(())) K 1) 2 mmp
for all K E K, where above is the identity matrix and the inner product the usual Frobenius inner product of matrices." X}. Then, the 4-EVI problem can be in turn expressed as
Further, let A (onv(F(x))l()
find AEA s.t. (A - 20
for all K K. Since and m are bounded, by assumption, so is A. Moreover, since the coordinates my are linearly independent, IC is also bounded. Thus, letting A denote the closure of A, the max-min problem
max min (A, K I)
(13)
AEA KER
satisfies the conditions of the minimax theorem. Moreover, for any K E K., the fixed point æ == FP((k) satisfies
(F(x)m(x)) K
ox )x(xx)
x) = 0,
so the zero-sum game (13) has nonnegative value; that is, there exists A A such that minker (A, K - 2 0. Thus, for every > 0, there exists A E A such that minkeX(A, (A, - I) 2 -c. Moreover, by Carathéodory" 's theorem, A can be expressed as a convex combination of at most 1 + dk matrices of the form F(x) Fm)) This convex combination is thus an e-approximate EVI solution.
The only reason the above proof breaks when 0 is that A may not be closed. Indeed, this issue is fundamental: there are instances where no exact EVI solutions exist even when á contains only constant functions (Proposition 3.3).
C.2. Complexity of d-EVIs
With regard to the complexity of computing 4-EVI solutions, the key observation is that, when & contains all (measurable) maps, B-EVIs are essentially equivalent to Vis; this immediately implies number of hardness results, which were covered earlier in Section 3. We provide the formal proof of Proposition 3.6 below.
Proposition 3.6. If t contains all measarable functions from X X, then any solution μ E A(X) to the c-approximate &-EVI problem satisfies
VIGap(æ) S.. Zr-p
(4)
Proof. We can define a measurable map Φ: + X' such that d(x) is an element selected from argmin (rx x' x) by utilizing the measurable maximum theorem (Aliprantis & Border, 2006, Theorem 18). To satisfy the conditions of this theorem, we need define-using Aliprantis & Border's notation- the weakly measurable set-valued function X - X' as (xx) X' and the (Carathéodory) function f X x X + R as f(x, x') - (F((x) x' - x). Due to this map σ. a 4-EVI solution μ ( must then, in particular, satisfy
E (F(x), xx) amp x'EX'
E argmin ( F(x), x' - x) 2
Therefore, there must exist xx X' with argmingrex(F(=")rrr x²) 0, that is, VI solution x". If p has finite support, then such x² exists within that support. The e-approximation case follows analogously.
"To avoid measurability issues, it enough consider here only distributions with finite support.
18

---

Expected Variational Incqualities
C.3. Proof of Theorem 4.1
To establish Theorem 4.1, we will use the recent framework of Daskalakis al. (2025), which refines Theorem 2.1 in the context of Section 2.1, ultimately summarized in Theorem C.4. Coupled with the "semi "semi-separattion oracle" of Lemma 4.2, will thus arrive at Theorem 4.1.
Let X' C Rd and y C _ be convex and compact sets, The goal is to solve the convex program
find μ EE s.t.
min Ay) 2 0,
(14)
yEy
where ( S RM and A I MMx;; we think of M as being potentially exponentially large, so A is not given explicitly; -LiN-EVIs can be expressed as (14), assuming that ja has finite support (ef. Theorem 3.5). The target is to solve (14) with
complexity polynomial in d and m (and other parameters of the problem, except M). As we saw earlier in Section 2.1, the EAH algorithm accomplishes that given access to a GER oracle, which, for any y E V, returns x E X' such that (u(x), Ay) 2 0, where A(X) 9 p(z) places all probability on æ. Assuming that such an oracle exists, the convex program
find y E R5oY
s.t.
max (M, Ay) S (ED(X)
(15)
is infeasible, where RyoD : {cy e applying the ellipsoid algorithm on (15) this is where the name "ellipsoid against hope" comes from. In doing so, the ellipsoid will eventually shrink to an area with negligible volume (denoted by vol), at which point one can extract certificate of infeasibility for (15) as follows. The execution of the ellipsoid will have produced a sequence of T E N such that for any y E y, it holds that (u(x(()), Ag) 2 0 for some E [7]] (up to
0} is the conic hull V. Despite its infeasibility, EAH proceeds by
x7) ,e(")..., numerical imprecision). In turn, this implies that there is a mixture μ over (x(').... ...,, xT) that guarantees (μ, Ay) 2 O for every y E y. Such a fa can be computed in polynomial time by solving a smaller program, which simply searches over the mixing coefficients.
good-enough-responsse
So far, have elaborated on the framework presented in Section 2.1. To solve LIN EVIs, is necessary to relax the oracle assumed above. In particular, the SEPorCER oracle, introduced by Daskalakis et al. (2024), proceeds as follows. It takes as input a point E IT (not necessarily in ))), and must either return a good-enough-response æ E X, or a hyperplane separating y from y. The idea now is to again run ellipsoid on (15), but by replacing y with convex "shell set"; every time the SEPorGER oracle returns a separating hyperplane, the shell set restricts further. At the end of this process, once the ellipsoid has shrank enough, one can work with the induced shell set y and proceed by identifying a mixture among the good-enough-responss (xx(1), ..... (T) } that approximately solves (14). The overall scheme is given in Algorithm 1.
Below, we state the main guarantee of Algorithm 1 shown by Daskalakis et al. (2025); in its statement, we have made certain slight adjustments in accordance with our setting.
Theorem C.4 (Daskalakis et al., 2025). Suppose that the following conditions hold.
for some B 2 1; 1. A E Mxm such that for any μ A(X), ||TT <
2. y is convex and compact, and satisfies Br, E C BR, and
3. there exists a SEPorGER oracle: for every point y E BR, (0). it runs in poly(d, m) time, and either returns a hyperplane separating y from y or a good-enough- æ E X.
Then, Algorithm 1 runs in poly(d, m, IB)()))) time and computes μ. E A(X) such that
min(p, Ay) -E. yEy
That the second precondition (Item 2) is satisfied follows from Daskalakis et al. (2025, Lemma 2.3). The third precondition, Item 3, is satisfied by virtue of Lemma 4.2. Consequently. Theorem 4.1 follows from Theorem C.4.
Remark C.5 (Weak oracles and finite precision). Since we are working with general convex sets, the oracles posited in Section 2 (namely, membership, separation, and linear optimization) can return irrational outputs. This can be addressed by employing weak versions of those oracles, which relax the output by allowing some small slackness e (Grötschel et al., 1993). Theorem 4.1 I can be readily extended under those weaker oracles; see Daskalakis et al. (2025, Appendices E and F).
19

---

Expected Variational Incqualities
Algorithm 1 Elliissoi against hope (EAH) under SEPorGER oracle (Daskalakis al., 2025)
input Parameters Ry Ty > 0 such that Bry (-) C C BR, (0)
precision parameter e >>
constant B 1 such that || T A I B for all ja E (())
SEPorGER oracle
output A sparse, e-approximate solution μ A(X) of (14)
1: Initialize the ellipsoid & := BR,
2: Initialize ) == B BR (0)
3: while vol 2 vol (ol(B.,B()) do
4: Query the SEPorGER oracle the center of
5: if it returns a good-ennugh--espposs
X' then
6:
Update & to the minimum volume ellipsoid containing E ( E (v. AT u(())) 50} 7: else
8: Let H be the halfspace that separates y from y
9: Update the minimum volume ellipsoid containing n H
Update y -
11: end if
12: end while
13: Let (+) xx()) be the GER oracle responses produced in the process above
14: Define X == [u(z(!)) .... I [(x((T) and compute X T A E RT
15: Compute a solution Ả to the convex program
find AEAT s.t.
min A Al
yEy
16: return A(X) 3 j Et 1 ((0)(())))))
D. Characterizing Linear Endomorphisms for Polytopes
In this section, we answer the following question. Given a nonempty polytope X' = (xx E Rd: Ax S bb where A E R and b E R,,, we wish to characterize the set of (affine) linear maps ø X - X. That is, we wish to understand the set of pairs (K, c) E Rdddd x Rd such that Kæ + c E X' for all æ E X. The following result provides an explicit polynomial representation for that set, establishing Theorem 4.3.
Theorem D.I. Kæ cC X for all a E X if and only if there is matrix V E mm satisfying the constraints
VA AK, Vb< Ac, V 0.
Proof. Let K E gdxd and E Rd, and let a. x S b, be the ith constraint that defines X. Then, the claim that a. (Kæ + c) S by for every æ E X' equivalent the claim that the linear program
max a. Kæ s.t. b b has value most b, a. c. By strong duality, (16) has the same value
(16)
min
b bJ
s.t.
A A v;
= K
aj
v 2 0.
The theorem follows by setting V
Uk
Furthermore, assuming that (0) C X C (0) with R < poly(d), it follows that || 2|, VV|2 poly(d), where || ll2 denotes the spectral norm. Indeed, to begin with, ||e|| < R since K 0 E X C (0). For | [|2, take any æ E IRd with ||ж||| 1. Since B, (0) C X. we have E X' in turn implying that K + c E X. As a result, K - ||||| < K + c/| S (dly from which follows that | K||2 S pdly Further, one can take each a, and b, to
be such that S b, I (dly(d) and ||a = 1, and so the bound V 2|22 < poly(d) follows from the fact that Vb S - Ac
and V 2 0.
20

---

Expected Variational Incqualities
Combining these bounds with Theorem D.I, and as we saw earlier in Corollary 4.4, are able to standard techniques for minimizing regret over PLIN-Such as projected gradient descent.
For comparison, let us point out the approach of Daskalakis et al. (2025) for the case where X' is given explicitly. To do so, we recall the following definition.
Definition D.2. We say that polytope X' has an H-representation of size if is given as the intersection of m halfspaces: X' {ar E Rd Ax b) for some A E Qmma and b E Qmh It has V-representation of size if it is given as the convex hull of m vertices: X' conv([v1,... ( for U1....,,,, Um E Q
In this context, they make the following crucial observation (Daskalakis et al., 2025, Lemmas 3.1 and 3.2). Lemma D.3 (Daskalakis et al., 2025). If X has either -rreprrsentattin of size m or V V-representution of size m, there is poly(d, m)-time membership oracle for LIN-
Using a membership oracle for LIN, it is also possible to construct linear optimization oracle (Grötschel et al., 1993). As result, coupled with Lemma D.3, standard algorithms- -scch as thr-owttth--ertubeeeeee applied to minimize regret over LIN- However, the main limitation is that constructing linear optimization oracle using membership oracle relies on the ellipsoid algorithm, which is impractical. In contrast, Theorem D.1 allows us to bypass using the ellipsoid algorithm, resulting in a more practical approach.
(Hazan, 2016)- can be
also worth noting that one can extend Theorem 4.3 using only a membership oracle for X' (even when X' is not an explicitly represented polytope) using techniques from Daskalakis et al. (2025), although the resulting algorithm is more elaborate and requires running the ellipsoid algorithm on every iteration to compute the next strategies.
E. An Illustrative Example of Definition 7.3
In Section 7, we introduced a generalized notion of smoothness (Definition 7.1) that captures Roughgarden's notion in the context of multi-player games. As a result, there are numerous interesting examples that fall under Definition 7.1; for example, Roughgarden et al. (2017) provide a survey in the context of auctions. Our goal here is to provide a single function that satisfies Definition 7.3, but without being quasar-concave (in the sense of Definition 6.2).
Example E.1. We consider the polynomial function
3 4 p2 + pa, + 1,
x
(17)
where p E (0, 8). a has global maximum at 1, with value p/4.. It also admits VI solution (in fact, saddle point) x = This implies that u is not requasar-concand for any y E (0, 1]. On the other hand, is not hard verify the following claim.
Claim E.2. u is (1, 1/4)- (Definition for any p E (0,8).
A graphical illustration of u for various values of p is given in Figure 2. Coupled with Theorem 7.4, Claim E.2 implies that any solution y to the induced EVI problem satisfies
1
E zmp
u(x)
I+P max w(x)) 1.
This guarantee is tight, since x = 0, with v(0) = 1, is a solution to the (E)VI problem.
Remark E.3. Definition 7.1, to which Definition 7.3 is a special case, is generalization of smoothness in the sense of Roughgarden & Schoppmann (2015). While our bound applies to any EVI solution (Theorem 7.4), Roughgarden & Schoppmann (2015) gave a counter-example that excludes CCEs; this is not a contradiction because they define CCEs without lincarizing the utilities (as in Example 5.1), while EVIs always operate over the linearized utilities.
F. Omitted Details from Section 5
In this section and the next, we will use the notation LLNN( denote the of linear maps o: X' + y.
In this section. let I' be concave game. For each player i let X; Rd be its (convex, compact) strategy set, and let p C X.X We assume u.(,, x_,) is differentiable in æ; for all i.9 Without loss of generality we assume that the projection
By C C + differentiable" when is closed, we mean that f is defined and differentiable on an open set ć
21

---

Expected Variational Incqualities
0.5
Figure 2. Function u, defined (17), for E (1,2,4,8).
function (x) 2; is in 4,, and that D; is convex. Crucially for this section and departing to our knowledge from all prior work on T-equilibria in games, functions d; E o; are allowed to depend not just on æ; but also on other x-,8. We first generalize the examples Section to arbitrary 4.
Definition F.1. An e-approximate (4,) -equliibruii of I' is distribution A(X) such that
E mmp
(o)) u.(x))] Sc
for all players i and deviations di 4;
As discussed in Section 5, several special cases of Φ; well-studied and interesting:
When º contains the set of constant functions and the projection T. the set of (P:) are the CCEs.
When 4 consists of linear functions depending only on 2;, i.e., functions of the form + Ax; for matrices A. -quiliia- are LCEs, which correspond to CEs in the special case normal-form games.
When i consists of all functions X' + X;
are Nash equilibria.
Now let X X1 x Nr C Idd where Σ, dz, and define +b x be the of all functions the form
x - ( (x)) x,,))
for players and functions 6, E T.. We will abuse notation and also call these functions Φ; X X. Moreover, let F X + RE,4 di be given by F(x)= - -V un (æ),.... Va, un (x)).
Proposition F.2. If p is e-approximate &-EVI solution of F, then j e-approximate ( T. The converse holds for 0.
Proof. Suppose first that μ ((X) is e-approximate Ø-EVI solution of F. Then, for any player and deviation di D
we have
E [1((0(2)) (x(x))]
E (V (.)) æ~n
x.) E (-F(x) a~n
x) Se,
where the first inequality is concavity and the second is the definition of Φ-EVI. Conversely, suppose that μ is an (exact)
( rqquiliiii I', For X E IR let o² Ao; + (1 A)T, Let [0, 1] x X + R be defined by
g(),x)
(x)
22

---

Expected Variational Incqualities
Then, 9 differentiable in À for any fixed a, and g is bounded. Let G(A) Exo f(,, Then G(O) and by the Leibniz rule, G is differentiable with derivative
(0) = E (x)
2 A (o) - -xi)
1
Ve,ui(a
lim
E V (.) (1 - x;))
E (-F()), x),
where we use the chain rule, then the definition of dº and finally the definition of F. But if Ea=u(-F(2x), di(x)) m>>0. 0. then by definition of derivative, there is some X 0 for which G(A) > 0, contradicting the definition of (#1) equilibrium.
We now prove the following generalization of Proposition 5.3.
Proposition F.3. For a given distribution E ( define the distribution je" E A(X") by sampling x ~ and
outputting (z...., x) X", Then the (QI...., -e)-llbiiiibia of I' are precisely the (f...., , 1 - of 1
Proof. μ² is an e-approximate (Q....,))-equuiill)), -qquiliba of 1 if and only if, for every player and linear map Φ X - X, we have
0 2 n!.
E (a1 ............................. (()))()))) ,.., uo (o-1())(a0]
am-
1 Σ
E (T ,()),...,)........ an) -uy(x)}
n
jE(m]
But this holds if and only if
..) E (1)((),..., (..)...... u,y( zmp
for every player and every oj E 3 which precisely the definition of an (#1,..., p -qquiiiiii of
Proposition 5.3 follows by combining Proposition F.3 and Proposition F22 the special case when Φ; = -FLIN X.).
F.1. Anonymous linear correlated equilibria
For the special case where Φ; = (X, Xz), we have coined the resulting ( equillirium notion an anonymous linear correlated equilibrium (ALCE). We now compare ALCEs and LCEs in concave games. We now point out some intriguing properties of ALCEs, especially compared to LCEs and CEs.
In normal-form games I, LCEs and CEs coincide, and ALCEs lie strictly between LCEs and Nash equilibria, can be seen in Figure 1. We now elaborate on the normal-form specific game-theoretic interpretation of ALCES by giving an augmented gase- definition. For any fixed E A(X',, consider the augmented game I'M that proceeds as follows.
1. A correlation device samples x Ja.
2. Each player chooses player (possibly not itself) and observes a sample aj æy,, independently from the samples of other players. (In particular, if multiple players choose the same player j. then they get independent samples from x.)).
3. Each player selects an action a; E A, and gets utility u; (a))...,an.)
Proposition E.4. A distribution μ E ( is a ALCE of if and only if the strategy profile in which every player requests an action for iself and then plays that action a Nash equilibrium of TH.
The proof will use critically the following characterization of linear maps.
23

---

Expected Variational Incqualities
Lemma F.5 (Fujii, 2023). Lei == X x... Xn where each X; is a simplex X, (m,)). Then every linear map X Xg is a convex combination of linear maps 63 X X; that only depend on single æ.j.
Proof of Proposition F.4 Fix some 14 (X) and suppose that it is not AL,CE, that is, there is some profitable deviation 6 X' Xr for some player i. By Lemma F.5, it suffices to assume that only depends Moreover, a linear map Ø X3 + X' can be represented as 2 + Az, where A E it suffices to assume that & is a vertex of the set of colunn-stochastic matrices, that is, A has exactly one 1 in each column. Now player& i's deviation benefit under deviation Φ is given by
one player's 's strategy Z), is column- column-stochastic. Again,
E (u(6)(())) u. (x))) 2i1p
E
E aswa,
u((oyld)), -u(a)
zmp a
where the equality uses multilinearity a. This is precisely the deviation benefit of the strategy in T for player i which player chooses to sample df and then plays an action according to 0₃ : [my] + [m,]. The proposition now follows by observing that these are precisely the possible pure strategy deviations of player in TV.
We make several more observations about the relationship between ALCESs and other notions of equilibrium in games.
Proposition F.4 generalizes beyond normal-form games, but needs be modified. For example, for (single-step) Bayesian games where each X; is itself product of simplices, it follows from similar proof that, in the augmented game I?, player should be allowed to observe its own type first, and then select both another player j and type 0j of that player at which to ask for recommendation. (Another way to see this is that the EVI formulation does not distinguish Bayesian games from their agent form (Kuhn, 1953), where each player-type pair is treated as a separate player.)
Even more generally, for extensive-form games, we can generalize ALCEs using a characterization of the linear maps X' + X, due to Zhang et al. (2024b): in Ie, player first may observe its first recommendation at any time of its choosing, and may delay its choice of which player to observe until that point.
In normal-fome -form games, CEs can be without loss of generality defined as distributions over pure action profiles A= X x..x x An instead of distributions over mixed strategy profiles X' = Xi x x... X X, (Aumann, 1974). By without loss of generality here, we mean the following: given any μ E A(X), define μ' (AA) by sampling æ ~ p. then ag ~ x; for each Then μ is correlated equilibrium if and only if p' is.
This phenomenon is not true for ALCEs. Indeed, for two-player games. if μ E (AA) is ALCE, then in fact pl is a distribution over pure Nash equilibria, which in general may not even exist! It is thus critical in our definition that l be allowed to be distribution over mixed strategy profiles, not not just pure strategy profiles.
We have shown that there is an efficient algorithm for computing one (approximate) ALCE. We leave as an open question the complexity of computing an optimal (e.g., relfare-maximizing ALCE (when the number of players is constant). Optimal CEs can be computed efficiently in this setting, because the set of CEs μ ((A) is bounded by small number of linear constraints; however, this fails for ALCES because, as above, we need to optimize over μ E (A²).
G. Local Eqquilibia in Nonconcave Games
This section connects d-EVIs with solution concept recently put forward by Cai et al. (2024a) (see also Şeref Ahunbay 2025) in the context of nonconcave games (Proposition G.4).
Nonconcave games Consider an replayer game in which each player E [m]] has convex and compact strategy set X. and a differentiable utility function u; X, x x... x X, + R. Crucially, there is now no assumption that u, is concave. In this setting, our framework suggests the following definition.
Definition G.1. Given sets of functions & C x an e-approximate local
in an n-player nonconcave
game is a distribution μ E A(X2 X ... x Xx) such that for any player i E [m] and deviation Φ; E $,,
E V u,(x), (1(z:) x) S
24

---

Expected Variational Incqualities
Theorem 4.1 immediately implies the following result when $; =LLIN X;): as before, in what follows, we assume membership oracle for each Xg. Corollary G.2. Suppose [[)](())] < B for every player [ni] and profile E X1 x ... Xx. Then, there is
poly(d, (og(l//))))o))o -teme algorithm that outputs an e-approximate local
Similarly, the existence of linear swap-regret minimizers for arbitrary polytopes X; (Daskalakis et al., 2025) immediately implies the following.
Corollary G.3. There an independent no-regret learning algorithm that computes e-approximate local (9:)==-equllibia in poly(d, (d, 1/e) rounds and poly(d, 1/c) per-round runtime.
Cai et al. (2024a) also studied the problem of computing local (#;) -qquiibiia in nonconcave games. They defined e-local ( instead by restricting the magnitudes of the deviations to the "first-order" regime where local deviations cannot change the gradients by too much. In particular, they assume that utility functions u, are smooth, the sense that
Va: uz x)) - Vx, (, (f,,, -1lll I L| - a!!ll Vz,, x E X, Vx- E X Xe,
8
where L > O is a constant. Then, they restrict deviations to only slightly perturb the strategies, that is, for a given set # C P.K. they define a set
(5) == {AØ; + (1- Φ; E p, X o/D;),
where Id X' - X' is the identity function and D; is the ky-diameter of X, i..., || x' e'll, - D, for all x, x' E X, With this restriction, they show (Cai et al., 2024a, Lemma and Theorem 10) that 6-regret minimizers converge to & (6)-eqqili,,ia, in the sense that
8 ReRe
TT)
L
E (2;),, - -u; (x(x)) -
T
2
where &-Reg, is the P,-regret of Player E [n]. for all players and deviations o, E 2,(6). Our results imply theirs, in the following sense. Proposition G.4. Any e-approximate local (4,) -qqulibruuu μ (per Definition G.1) satisfies
dc 8
E (x;) x-1) u,(x)] S
+
D; 2
for any player i [m] and deviation 6, (6).
Proof. Write Φ; Aσ; + (1 2) for some of F.. Then,
I.
(Va, uz (1)), 2;)) + 8
u:(o;( (x;) (x) & (Va, (x),, 6i (x;) - n.) +
2 (1)) - 2:112 =
D;
2
where the last inequality uses the fact that X < 8/D, and therefore (ax)) - 2xi12 S A|| (a:) 2z1l2 S AD; < 8. Taking expectations over μ and applying the definition of e-approximate local requiiiruqi completes the proof. 0
However, our results improve on theirs in several ways:
We believe that the formulation of local (#.) using gradients directly instead of restricting to small perturbations is more natural and more directly conveys what it means for distribution to be local -equiiibrui without introducing too many hyperparameters; one of the notions proposed by Şeref Ahunbay (2025, Definition 6) also shares this advantage.
Our results do not require the smoothness of the utility functions u4.
We have an ellipsoid-based algorithm that computes local (0.) with convergence rate depending on log(1/e), whereas no-regret algorithms only achieve poly(1 (1/e) convergence rate.
Although we do not explicitly state it here, Definition G. and Corollary G.2 extend directly to the case where Φ = PLN (L,, X.) (instead of PLN (X,, X.)). Per Appendix F, this can yicld an even smaller set of equilibria.
25


Reviews:
[{"review_id": "cRGcm8lDP3", "reviewer": "Reviewer_UNCg", "summary": "The paper studies the Variational Inequality (VI) problem, a well-known problem used in various optimisation problems, often in settings where equilibria need to be computed. The general problem is intractable, so there is a wide literature identifying subclasses of the VI problem for which it is tractable.\n\nThis paper proposes an alternative approach: relaxing the definition of the solution to the problem. Instead of requiring a single point in a convex space that should satisfy the central variational inequality, the *expected* variational inequality (EVI) problem asks to find a *distribution* of points that *in expectation* satisfy the inequality.\n\nThis problem is parametrised by the size of the set of deviations ($\\Phi$) from the convex space for which the inequality must hold. The larger the set of deviations, the smaller the found distribution will be.\n\nThe paper considers different types of maps $\\Phi$, including constant and linear map. A key contribution is a complexity result for when $\\Phi$ contains only linear maps. In this case, the $\\Phi$-EVI problem can be solved in time polynomial in dimension $d$ of the problem space and logarithm of the inverse of the precision parameter $\\epsilon$. Since this result relies on the ellipsoid against hope (EAH) algorithm, which is slow in practice, the paper proposes an alternative algorithm that improves upon the state of the art in terms of the per-iteration complexity.\n\nFurthermore, the paper presents equivalence and performance results, and identifies applications of (constant-$\\Phi$) EVIs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and service. \n\nWe are happy to adjust the writing style and follow any other suggestions for the revision. Regarding the bibliography, we follow the convention that page numbers are omitted for conference publications, which explains why some references have page numbers and others don’t. We are happy to change that if the reviewer finds it inconsistent.", "claims_and_evidence": "I honestly do not have the background to be an accurate judge of this. I am unfamiliar with many of the concepts discussed in this paper, and Wikipedia can only get you so far. I have no obvious reasons to doubt any of the claims that are made.", "methods_and_evaluation_criteria": "The main claims are theoretical and are supported by proofs in the appendix. That seems appropriate to me.", "theoretical_claims": "I read through some of the proofs, but do not have the expertise to confidently assess their correctness.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "To a layperson like me, at least, it seems like the paper positions the main contributions well in relation to the existing literature. In doing so, it covers applications and theoretical results spanning several decades. The appendix contains more details on the relationship between EVIs and different game theory concepts.", "essential_references_not_discussed": "I do not consider myself knowledgable enough to judge this.", "other_strengths_and_weaknesses": "I really appreciate the efforts to make the paper somewhat standalone by including a recap of the ellipsoids against hope (EAH) algorithm. I also find that the paper is well-written in terms of structure and signposting. The writing is clean, with hardly any typos. The paragraph labelling and subsection labelling is inconsistent and confusing to me.\n\nThe main research direction and contribution seem valuable and interesting to me. I also like the efforts made by the authors to connect their results to different fields, and their discussion of their finding's implications for game-theoretic questions.\n\nI personally dislike the writing style. Take the second sentence of the introduction. It spans 14 lines: almost a quarter page. I would've preferred that to be split up in a few sentences, organised by application category or something. Elsewhere in the paper there's also needlessly lavish prose. Why write \"in lieu of\" when \"instead of\" is right there? Going for the simpler option would even have saved the authors an `{\\it }`. I personally believe that scientific writing should be as accessible as possible. Hence, I wish that the authors would have kept the language more simple.", "other_comments_or_suggestions": "- The bibliography is a bit sloppy and inconsistent. For some entries the full name of the venue is given, for others just an abbreviation. Many entries seem to be missing page numbers.", "questions_for_authors": "I do not feel like I have the expertise to formulate questions whose answers would make a difference in my judgement.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DRy3oitPyh", "reviewer": "Reviewer_GSQj", "summary": "The authors relax VI to a new notion of EVI. They then take a game-theoretic approach to design polynomial-time approximation algorithms for EVIs.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and service.\n\n*“It would be helpful if the authors could compare the strength of VI to EVI in terms of modeling power. For example, are there still many VI problems for which EVI suffices? Furthermore, are there any problems where EVI is actually more natural of a model than VI?”*\n\nThis is a great question. If we look at the special case of games, $\\Phi$-EVIs (which subsume correlated equilibria) are in many ways more natural than VIs (that is, Nash equilibria). Indeed, they often lead to better outcomes in terms of welfare as they enable correlation between the players, which in many applications is more reasonable than assuming that players are acting independently (a traffic light is a common example of a correlation device). This shows that there are problems in which EVIs are, in many ways, more natural than VIs. Furthermore, given how expressive games are from an optimization standpoint, we argue that this already makes a compelling case for EVIs compared to VIs. That being said, we believe that further understanding the power of EVIs and how they compare against VIs is an important question for follow-up work.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "VIs are a general way to capture many important problems across different fields. This paper addresses the complexity issues of VI problems by introducing a new notion that retains the key flavor of VI while making them computationally tractable. As such this work has the potential to lead to further insights to make VI problems more efficiently solvable, and out of the box gives efficient methods that could be promising heuristics to known VI problems. Overall, I believe this paper has the potential to have significant impact on the literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper seems well written and not only introduces a reasonable relaxation of a known useful framework, but also presents provable approximation algorithms for the relaxed problem. The only weakness I can see is whether EVI is too great of a relaxation. Considering it brings a known hard problem down to polynomial time complexity, there must be some loss in modeling power or guarantees that result. Either way, I believe the insights are still meaningful even if EVI is too much of a relaxation.", "other_comments_or_suggestions": "It would be helpful if the authors could compare the strength of VI to EVI in terms of modeling power. For example, are there still many VI problems for which EVI suffices? Furthermore, are there any problems where EVI is actually more natural of a model than VI?", "questions_for_authors": "See my suggestions above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cbksnN5OsI", "reviewer": "Reviewer_7Vec", "summary": "This paper considers a relaxation of the variational inequality problem (VIP), the $\\phi$-Expected Variational Inequality problem (EVI) (see Def. 1.2). This definition relaxes the 'classical' definition of the VIP in three ways: (1) the objective is to find a distribution $\\mu$ such that the inequality holds in expectation, (2) the comparator is not wrt any $x \\in X$, but with respect to $\\phi(x)$ where $\\phi:X \\rightarrow X$ is a map (which is assumed to be linear for most results) and (3) the inequality is relaxed to hold wrt $-\\epsilon$. \nThe authors provide complexity results (PPAD hardness for non-linear $\\phi$), a polynomial bound if $\\phi$ is linear (Thm 4.1), a regret bound and give application examples for games. Further, they give some conditions under which an $\\epsilon$ solution for a EVI is also an $\\epsilon$ solution for a VI.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and service.\n\n*\"To the best of my understanding, if  $\\Phi$ contains all functions [...] EVIs would correspond to VIs if $\\mu$  is restricted to Dirac measures.\"*\n\nWe clarify that this equivalence holds without any restriction on $\\mu$; it doesn’t have to be a Dirac measure.\n\n*\"Thus I am not yet convinced of the relevance of the solution concept\"*\n\nOur main positive result captures the setting where $\\Phi$ contains all linear functions, which we argue is a strong solution concept. Even in the special case of normal-form games, it is tighter (that is, closer to Nash equilibria) than the usual notion of a correlated equilibrium (see Figure 1). Moreover, our hardness results preclude efficient computation when $\\Phi$ contains even quadratic functions; as a result, there is a fundamental sense in which our solution concept is the best one can hope for using efficient algorithms.\n\n*\"In the setting of games: Is there a clear relation to the $\\Phi$-equilibria considered in Cai et al.?\"*\n\nIn the special case of nonconcave games, our solution captures the one considered by Cai et al., as we show and discuss in Appendix G. In fact, when $\\Phi$ contains all linear functions, our solution concept is tighter (see Figure 1). We also argue that our definition is more natural and simple, while also applying to any variational inequality problem. Besides those points, we provide significant algorithmic improvements compared to Cai et al., as we point out in Appendix G.\n\n*\"Is there a similar solution concept in optimization to which you can relate?\"*\n\nTo the best of our knowledge, there is no existing solution concept in optimization that directly relates to $\\Phi$-EVIs, except in more specific classes of problems (see Section 6). Given how natural this concept is, we believe that introducing it to the optimization community is an important contribution.", "claims_and_evidence": "This is theoretical work, all claims are supported by proofs.", "methods_and_evaluation_criteria": "This is theoretical work, thus benchmarks etc do not apply.", "theoretical_claims": "I did check some, but not all.", "experimental_designs_or_analyses": "No experiments are provided. (but this is fine since this is theoretical work)", "relation_to_broader_scientific_literature": "To the best of my understanding, the paper follows a similar idea as in Cai et. al. 2024 and (to some extent) generalizes this to VIP. Further, it falls into the brought area of 'local (cc) equilibria/first order optimality' for non-concave games and approaches this from the VIP perspective.", "essential_references_not_discussed": "To the best of my knowledge, all relevant references are discussed.", "other_strengths_and_weaknesses": "The paper is well written. I like the versatility of the proofs and results. \n\n I am a bit unsure about the relevance of the solution concept of $\\phi$-EVI. To the best of my understanding, if $\\Phi$ contains all functions mapping into $X$, EVIs would correspond to VIs if $\\mu$ is restricted to Dirac measures. However, the class of mappings $\\Phi$ is quite restrictive. Thus I am not yet convinced of the relevance of the solution concept, but I may also miss something.  Thus I am happy to revise my evaluation. \n\nAlso see my questions.", "other_comments_or_suggestions": "none.", "questions_for_authors": "I am a bit confused regarding the interpretation of the solution for $\\phi$-EVIs. For example, in the setting of games: Is there a clear relation to the $\\phi$-equilibria considered in Cai et al.? \nIs there a similar solution concept in optimization to which you can relate $\\phi$-EVIs (as VIs relate to convex optimization)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Summary: The paper introduces and analyzes a natural relaxation of VIs, namely expected variational inequalities (EVIs), where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, it shows that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators.

On Reviews: All reviewers really enjoy reading this paper. It is well written with clear contributions. Excellent work from the authors. 

The ideas presented in the paper are novel and worth exploring further in the future, especially their impact on a wide range of applications.
I advise the authors to incorporate the feedback they received into the updated version of their work. I recommend acceptance.
Decision: Accept (oral)