Exploitability Minimization in Games and Beyond
Authors: Denizalp Goktas
Amy Greenwald
Venue: NeurIPS 2022 Accept (2022)
Keywords: Pseudo-games
exploitability minimization
equilibrium computation

Abstract: Pseudo-games are a natural and well-known generalization of normal-form games, in which the actions taken by each player affect not only the other players' payoffs, as in games, but also the other players' strategy sets. The solution concept par excellence for pseudo-games is the generalized Nash equilibrium (GNE), i.e., a strategy profile at which each player's strategy is feasible and no player can improve their payoffs by unilaterally deviating to another strategy in the strategy set determined by the other players' strategies. The computation of GNE in pseudo-games has long been a problem of interest, due to applications in a wide variety of fields, from environmental protection to logistics to telecommunications. Although computing GNE is PPAD-hard in general, it is still of interest to try to compute them in restricted classes of pseudo-games. One approach is to search for a strategy profile that minimizes exploitability, i.e., the sum of the regrets across all players. As exploitability is nondifferentiable in general, developing efficient first-order methods that minimize it might not seem possible at first glance. We observe, however, that the exploitability-minimization problem can be recast as a min-max optimization problem, and thereby obtain polynomial-time first-order methods to compute a refinement of GNE, namely the variational equilibria (VE), in convex-concave cumulative regret pseudo-games with jointly convex constraints. More generally, we also show that our methods find the stationary points of the exploitability  in polynomial time in Lipschitz-smooth pseudo-games with jointly convex constraints. Finally, we demonstrate in experiments that our methods not only outperform known algorithms, but that even in pseudo-games where they are not guaranteed to converge to a GNE, they may do so nonetheless, with proper initialization.

Exploitability Minimization in Games and Beyond
Denizalp Goktas
Amy Greenwald
Department of Computer Science
Brown University Providence, RI 02906, USA amy_greennwaldebrown.cc
Brown University Providence, RI 02906, USA denizalp_gokkas@brrom edu
Abstract
Pseudo-games games are natural and well-known generalization of normal-form games, in which the actions taken by each player affect not only the other players' payoffs, in games, but also the other players' strategy sets. The solution concept par excellence for
games is the generalized Nash equilibrium (GNE), i.e., a strategy profile at which each player's s strategy is feasible and no player can improve their payoffs by unilaterally deviating to another strategy in the strategy set determined by the other players' strategies. The computation of GNE pseudo-gand games has long been a problem of interest, due to applications in a wide variety of fields, from environmental protection logistics to telecommunications. Although computing GNE is PPAD PPAD-hard in general, it is still of interest to try to compute them in restricted classes of pscudo-games. One approach is to search for strategy profile that minimizes exploitability, i.., the sum of the regrets across all players. As exploitability is nondifferentiable in general, developing efficient first-order methods that minimize might not seem possible at first glance. We observe, however, that the cooitaablity-miimizatiii min-max optimization problem, and thereby obtain polynomial-time first- order methods to compute refinement of GNE, namely the variational equilibria (VE), in convex-concave cumulative regret pseudo- games with jointly convex constraints. More generally, we also show that our methods find the stationary points of the exploitability in polynomial time in Lipschitz-smooth pseudo-gamed gamees with jointly convex constraints. Finally, we demonsirate in experiments that our methods not only outperform known algorithms, but that even in pseudo-gama -ammes where they are not guaranteed to converge to a GNE, they may do so nonetheless, with proper initialization.
problem can be recast
Introduction
Nash equilibrium is the canonical solution concept used to predict the outcome of models of rational agents known games. A game comprises set of players, each of whom simultaneously chooses a strategy (or action) from a strategy set, and then receives payoff based on all the players' choices. A Nash equilibrium (NE) is strategy profile, i.e., collection of strategies, player, from which no player can improve their payoff via a unilateral deviation.
per
Recently, the literature on NE has expanded beyond classic economic applications to the question of its computation, a problem known as the Nash equilibrium problem (NEP) 22 3. Unfortunatcly, it is unlikely that there exists an efficient algorithm to compute NE, NEP is PPAD-complett i.c. NEP is equivalent to the problem of computing solutions class of fixed-point problems known PPAD which are believed to be computationally intractable [5 6 7 Nonetheless, there has been a great deal of recent progress developing efficient algorithms to compute NE in special classes
of games, such two-player zero-sum
10
12
13
15
16
18
20
21
22
23
24
25
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

26 27
and monotone (or, more generally, variationally stable) Interest in two-player zero-sum games, for example, stems in part from emerging applic applications in machine learning, e.g., the training of GANs 42 43
28
29
30
31
potential 32
33 34
games 35
36
37
38
39
40
41
A natural generalization of games pseudo -aamess-amesse or abstract economies, first introduced by Arrow and Debreu [4]] in the context of markets, in which the actions taken by each player affect not only the other players' payofts, as in games, but also the other players' strategy sets. In other words, players (simultaneously) take actions that can restrict the other players' strategy sets. Such a model not technically a game, giving rise to the greudo-game terminology. -seudo-games generalize games, and hence are even more widely applicable. Some recently studied applications include adversarial classification
46]. energy resource allocation (4 48 environmental protection [49
50 cloud computing 51 52 adversarial classification, ride sharing services 53
transportation
[4| wireless and network communication
[55 56
The solution concept par excellence for pseudo-gane -ammees is the generalized Nash equilibrium (GNE)
14 57 58 i... strategy profile at which each player's strategy feasible and no player can
improve their payoffs by unilaterally deviating to another strategy in the strategy set determined by the other players' strategies. The aforementioned applications speak the importance of developing algorithms that can approximate GNEs efficiently in the largest class of pseudo-gand games possible. Work in this direction, on the generalized Nash equilibrium problem (GNEP), is
progressing; see, for example, Nonetheless, there are still few, if any 78 GNE GNE-finding a algorithms with computational guarantees.
59 57 60 61 62
63
64
65
66
67
68
69
70
7 72
73 74
75 76 77
even for restricted classes of pseudo-games games.
Exploitability, or the Nikoida-Isoda potential 79 is defined as the sum of the players' payoff- maximizing unilateral deviations w.r.t. a given strategy profile. Minimizing exploitability is logical approach to computing GNE, especially in cases where exploitability is convex, such as in the pseudo-games games that result from replacing each player's payoff function in a monotone pseudo-game by a second-order Taylor approximation (80]. When the players' payoffs are also Lipschitz-smoolh and strongly concave (in their own action), this approximation can be quite good, because the error in the approximation will be bounded by the Lipschitz-smoothnes smoothness and strong concavity constant. Minimizing exploitability can thus be an effective way of finding GNEs in pseudo-games; however, to our knowledge, no convergence rates for this approach are known, and few methods have been proposed for pseudo-gama whose exploitability is non-convex.
In this paper, we develop efficient exploitability minimization algorithms that converge to variational equilibrium (VE), a refinement of GNE, exactly in large class of pseudo-gamed -aauees with jointly convex constraints (which includes, but is not limited to, two-player zero-sum, n--layer pairwise zero-sum, and a large class of monotone and bilinear pseudo-game games, as well as Cournot oligopoly games); and pseudo-games with jointly convex constraints, where exact
spplotaallitymmiiiiiatooon
approximately, in popschitz-smootii computation is intractable. Our algorithms apply not only to games with discrete action spaces but also to games with continuous action spaces; previous poooitaallit-mmmimizaati algorithms
concern only finite games 31 82
The cumulative regret of two strategy profiles is defined as the sum, across all players, of the change in utility due to unilateral deviations from one strategy profile to the other. Our algorithms and their analysis rely on the following key insights: assuming jointly convex constraints (i.e., symmetric and convex-valued joint constraint correspondences) the apploiabillty-mmiimiaaaiiii problem is equivalent to solving cumulative regret min-max optimization problem, which although eircconvex-concve in general can nonetheless be solved by gradient descent ascent (GDA) m [25
85 using a parametric variant of Moreau's envelope theorem that we introduce 4.1) We apply this logic to develop two algorithms for Lipschitz- smoohh pseudo- -amees with jointly convex constraints. To the best of our knowledge, this makes ours the first exploitability- minimization methods with convergence rate guarantees in this class of pseudo-gama -ames......
(Theorem
The first (EDA; Algorithm i is an extragradient method that converges in average iterates to an e-VE, and hence an e- s-GNE, in O(1/s) iterations in ggeudo-games with convex-concand cumulative regret, where e is the exploitability of the game (Theorem 3.4). This class of pseudo-gamed includes zero-sum, potential, Cournot, a large class of monotone pseudo-games and a class of bilinear
When the objective function is convex-coneave, a saddle point is guaranteed to exist, in which case this
optimization problem can be solved using Simuttanous-GDA--tee algorithms (e.g.. 21 83 84
2

---

pseudo-ganan games, namely those with convex second-order approximations. Our second algorithm (ADA; A a nested GDA algorithm, whose best iterate converges more generally to a stationary point of (regularized) exploitability in all Lipschitz-smooth convex constraints at the slightly slower rate of (loo(()))/)) (Theorem 4.2) When the (regularized) exploitability is additionally invex, our method also converges to GNE in best iterates at the same rate. This convergence can be strengthened to convergence in last iterates in (log(Y/)) iterations in strongly-cone cronvx exploitability aseudo-game and in certain class of gpeudo-gamee with non- exploitability (Theorem 4.3)
-eeudssgames with jointly
Pseudo-games games with jointly convex constraints are of interest in decentralized resource allocation problems with feasibility (e.g., supply) constraints. Feasibility constraints are almost always joint, and often also jointly convex, since we generally require the sum of the allocations to be less than or equal to the supply. One of the many examples of such pseudo-gamd -aamees wireless and network communication, where agents communicate packets across shared network, with limited capacities [55]. The experiments we run in this paper suggest that our algorithms have the potential to yield improved solutions to such secudo-games compared to other known approaches, and thus open up avenues for practical applications of our work in the future.
Related Work Following Arrow and Debreu's introduction of GNE, Rosen 86 initiated the study of the mathematical and computational properties of GNE in geoudo-games with jointly convex constraints, proposing projected gradient method to compute GNE. Thirty years later, Uryas'ev and Rubinstein 87 developed the first relaxation methods for finding GNEs, which were improved upon subsequent works
88 89
Two other types of algorithms were also introduced
to the literature: Newlon-style methods
90] and interior-point potential methods [90]. Many of these approaches are based on minimizing the exploitability of the aseudo-gama but
59 64
68
69
70
others use variational inequality 91 92] and Lemke methods
93
More recently, novel methods that transform GNEP to NEP were analyzed. These models take the form of either exact penalization methods, which lift the constraints into the objective function via a penalty term 772 73 76
77 94 or augmented Lagrangian methods 71 74 76 95), which do the same, augmented by dual Lagrangian variables. Using these methods, Jordan, Lin, and Zampetakis 78 provide the first convergence rates to a E-GNE monotone (resp. strongly monotone) pseudo- games with jointly affine constraints in ((Ye) (Ō(YVE) iterations. These algorithms, despite being highly efficient in theory, are numerically unstable in practice (78). Nearly all of the aforementioned approaches concerned pseudo-games games with jointly convex constraints.
Exploitability minimization has also been valuable tool in multi-agent reinforcement learning; algorithms in this literature that aim to minimize exploitability are known as exploitability descent algorithms [1). Lockhart et al. [81] analyzed exploitability descent in two-player, zero-sum, extensive-form games with finite action spaces. Variants of exploitabllit-deseem have also been combined with entropic regularization and homotopy methods to solve for NE in large games 82
Preliminaries
Notation We use caligraphic uppercase letters to denote sets (e.g.. X); bold lowercase letters to denote vectors (e.g. p, T); bold uppercase letters to denote matrices (e.g.. X) and lowercase letters to denote scalar quantities (e.g., xr, 6). We denote the ith row vector of a matrix (e.g., X) by the corresponding bold lowercase letter with subscript (e.g. æ;). Similarly, we denote the jth entry of vector (c.g.. p or æ:) by the corresponding Roman lowercase letter with subscript j (e.g. Pj or T.y)). We denote functions by a letter determined by the value of the function, e.g. / if the mapping is scalar-valued, if the mapping is vector-valued, and F if the mapping set-valued. We denote the set of integers {1....,n) n) by [n], the set of natural numbers by N, the set of real numbers by E. and the positive and strictly positive elements of a set by a + and ++ subscript. respectively, e.g.. R., and R.... We define the gradient V. (2) + (2') as the operator which takes as input functional f X - IR, and outputs a vector-valued function consisting of the partial derivatives of w.r.t. æ. We denote the orthogonal projection onto set C' by Ic. i... (o) = arg minyee ||xe y1(2 Finally, we write 1x(a) to denote the indicator function of the set X, ie. Ix(x) = 0 if æ E and lx(x) = oo if x & X.
3

---

A pseudo-gama game G
An, h. u) comprises n E NN players, each i E [m]] of whom chooses an a, from an action space A. We denote the players' joint action space by A= = Xie|nl A, Each player i aims to maximize their continuous utility u, : A + R, which is concave in a, by choosing a feasible action from a set of actions (; S A, determined by the actions a- E A_; C R.mh of the other players, where X; : AA= A, is non-emply, continuous, compact- and convex-valued action correspondence, which for convenience we represent as (; = {a, E A, hss (q,aa_) 2 0, for all & E [.]]. where for all i E [m], and k E [d]. h is a continuous and concave function in ag which defines the constraints. We denote the product of the feasible action correspondences of all players by X(a) = Xiejm (;(a_ which we note is guaranteed to be non-empty, continuous, and compact-valued, but not necessarily convex- valued. Additionally, overloading notation, we define the set of jointly feasible strategy profiles X' = {a E A (a) 2 0, for all i [ni] k [d]].
44
A two player pseudo-game is called zero-sum if for all a E A, u1(a) = uuy()) (a). A pseudo-gama
is called monotone if for all a EiEn (Va, d:(a) Va, a.(b)) (a b) $ 0. A pseudo- game is said to have joint constraints if there exists a function A - Rd s.t. g - h1 If additionally, for all k E [d], gi (a) is concave in a, then we say that the pseudo-game -ame has jointly convex constraints, as this assumption implies that X' is a convex set. A game [1] is pscudo- game where, for all players E [n)] X; is a constant correspondence, i.e., for all players i [n], ,))a = (b=;), for all a, b E A. Moreover, while X((a) is convex, for all action profiles a E A. is not guaranteed to be convex unless one assumes joint convexity.
ha-
Given pseudo-game 9, an e-generalized Nash equilibrium (GNE) is strategy profile a' E x(a)) An e-variational equilibrium
s.t. for all E [n] and a; E =aaa"")), ua(a") 2 u,(a, a=,)) (VE) (or normalized GNE) of a pseudo-game is a strategy profile a' E X(aa") s.t. for all i E [n] We note that in the above definitions, one could just as
and E X, u,(a") 2 u, a² well write a" E X(aa) as a E X, as any fixed point of the joint action correspondence is also a jointly feasible action profile, and vice versa. GNE (VE) an &-GNE (VE) with 0. Under our assumptions, while GNE are guaranteed to exist in all pseudo-games by Arrow and Debreu's s lemma on abstract economies [4]. VE are only guaranteed to exist in pseudo- gamees with jointly convex constraints 655 Note that the set of E-VE of a pseudo-game game is subset of the set of the e-GNE, as X(aa) S X, for all a which are GNE of G. The converse, however, is not true, unless A S X. Further, when G is game, GNE and VE coincide; we refer to this set simply as NE.
Mathematical Preliminaries Finally, we define several mathematical concepts that are relevant to our convergence proofs. Given A C R", the function / : A - IR is said to be Ly-Lipschitz- continuous iff væn, 22 E X, (xx,) - [(x2))] < E || 2221- If the gradient of f is / Lipschitz-oontinnous, we then refer to f as l - LLipschitzz-mmotti A function f X' + R is said to be invex w.r.t a function : X' x X' + X if f(x) f(y) 2 h(x.y) V fzy), for all æ, y X. A function f: X + IR is convex if it is invex w.r.t h( = x - and concave if -f is convex. function f X - IR is p-strongly convex (SC) f(1) 2 f(x22) + (V. 21 x2) +
#/2 1/2||z] - x1ll ?1 and j-strongly concave if ff is p-strongly convex.
From Exploitability Minimization To Min-Max Optimization
In this section, we reformulate the exploitability minimization problem as min-max optimization problem. This reformulation is a consequence of the following observation, which is key to our analysis: In peeudo-games/ for which a VE exists, e.g. useudo-games with jointly convex constraints, the quasi-optimizationn problem of minimizing exploitability, whose solutions characterize the set of GNEs, reduces to the reduces to standard min-max optimization problem (with independent constraint sets), which characterizes the set of VEs, a subset of the GNEs. This new perspective allows us immediate
to efficiently solve GNEP by computing VEs in large class of greudo-games consequence of known results on the computation of saddle points in convex-concave min-max optimization problems.
Given pseudo-gams -ame G, we define the regret felt by any player i E [n] for an action a as compared to another action b, given the action profile a_, of other players, follows: Regret, (a,, a_,) = u,(b,, a a_) - uu a _z)). Additionally, the cumulative regret, or the Nikaida-Isen Isoda function, sb A A + R between two action profiles a X and b e x
4

---

across all players in pseudo-gamd game is given by ((a.b) = Eiejnl Regret, (a, by; a a_,) Further, the exploitability, Nikaido-Isoda potential function, vp A I of an action profile is defined as ((a)= = Cie(n] mlaxb,exic ,) (tegret;(a;, by; a_;) [57 Notice that the max is taken over (;(a_)) since a player can only deviate within the set of available strategies.
A well-known 57 result that any unexploitable strategy profile in a pseedo-gaama gamee is a GNE.
Lemma 3.1. Given a pseudo-game G, for all a E A, p(a) 2 Additionally, a strategy profile a" E A(a") is GNE iff it achieves the lowerbound, i.e., "p(a" 0.
This lemma tells us that we can reformulate GNEP as the quasi-optimizatie problem of minimizing exploitability,, Le., gx(a) ((a). Here, "quasi" refers to the fact that solution to this problem both minimizer of y and fixed point a s.t. a' X'a J Despite this reformulation of GNEP in terms of exploitability, no pnploitablltt-mmiiiiiaatiii guarantees are known. The unexploitability (!) of exploitability may be due to the fact that is not Lipschitz-smotth The key insight that allows us to obtain convergence guarantees is that we treat the GNE problem not as a quasi-minimization problem, but rather as a quasi-min-man max optimization problem, namely x((a) (aa) = (a) maX (((,
algorithms with convergence rate
Observation 3.2. Given a pseudo-game G, for all E A. A.() maxbex(a) viaab) b).
Proof. The per-player maximum operators be pulled out of the sum, the ith player's 's best action in hindsight is independent of the other players' best actions hindsight, since the action profile is fixed:
(p)))
Σ max Regret, by: b,)a b.Edi(a..))
max (EA(()
Σ iE(m)
Regret, b a_;) max (a b) bEX(a)
vE(N)
That is. the optimization problem in the ith summand is independent of the optimization problem in the other summands, e.g., for any y E [0, 1/13. max e(.))a {2131}
(0.)) (2212) max 11 22//2-
If we restrict attention to VEs, subset of GNEs, VE exploitabllity exploitability for short-is conveniently expressed as pfa) = maxbex (a. b). When VE exists, e.g, in pseudo-games with jointly convex constraints, this exploitability is guaranteed achieve the lower bound of 0 for some a E X. In such cases, formulation of exploitability minimization as quasi-min-man max optimization problem reduces to a standard min-max optimization problem, namely millaxx maxbex (a, b), which characterizes VEs.
This problem is well understood when & is convex-concave objective function 21 83 8
96
Furthermore, the cumulative regret ei is indeed convex-concave, i.e, convex in a and concave in b, in many pseudo-gana -aauuessggesss of interest: e.g., two-player zero-sum, n-player pairwise zero-sum, and large class of monotone and bilinear pseudo-games as well as Cournot oligopoly games.
Going forward, we restrict our atlention to pseudo pseudo-games satisfying the following assumptions. sppschitz-smoothness a standard assumption the convex optimization literature (07) while joint convexity is standard assumption in the GNE literature [57]. Furthermore, these are weaker assumptions than ones made to obtain the few known results on convergence rates to GNEs (78).
Assumption 3.3.
The pseudo-game & has joint constraints : A - Red and additionally, 1. (Lipschitz smoothness and concavity) for any player i E [n], their utility function is Ev,, -Lipchitz smooth; (Joint Convexity) g is component-we concave.
Using the simple observation that every VE of pseudo-game game is the solution to a min-max opti- mization problem we introduce our first algorithm (EDA; Algorithm I an extragradient method 83 The algorithm works by interleaving extragradient ascent and descent steps: at iteration t, given (t), it ascends (ta(t), (t)()),, -), thereby generating better response (t+1), and then descends on (., ((++))) thereby decreasing exploitability. We combine several known results about the
Yet hard exploit())
'This problem could also be formulated as minimizing over the set of jointly feasible actions, ie., minaex ((a)): however, without assuming joint convexity, X' is not necessarily convex.
5

---

Algorithm 1 Extragradient descent ascent (EDA)
Inputs: n. u. u. n.,nT.T
T, T (8))(())
Outputs: (a()) )
for t -....,
do
a (1++/22) xIx [a 7, Va Va b(o)]
3: ((t+)/2) 1Ix (b(t) + + [)Vo(a( bb0)]
4: a(++1) =Ixx (tt)) 7 Va Va (2,(((((1)))
5: b(++1) =Ix b(t) + 17 VoVo'aa blt 12))
6: return ((()))(()))
1=
convergence of extragradient descent methods in min-max optimization problems to obtain the following convergence guarantees for EDA in pseudo-games
Theorem 3.4 (Convergence rate EDA). Consider a pseudo-game G with convex-concave
cumulative regret that satisfies Assumption 3.3 Suppose that EDA (Algorithm I is run with
n 1/eves and that doing so generates the sequence of iterates (alt), b(t)) Let a(T)
1/r El= 1 (t)) and b(T) ET= b(t), Then the following convergence rate to VE, i.e., to zero exploitability holds: maxbex (a(T)) ,b) maxaex (a,, S 1/T(d where d = maxx(a,biEXxx [|(aa)) b) (d('),(')>1l"" If. additionally, vb is pustrooggyy-oonveyyyssrrro
concave, and the learning rate = 1/46s, then the following convergence bound also holds: maxbex ((((T),b) maxaex vi(a, ((7)) S (1-1/ue)))
Remark 3.5. If the players' utility functions have Lipschitz third-order derivatives, then convergence in last iterates can be obtained in O(1/2) iterations 98
Since the complexity of two- two-player zero-sum concave games, a special case of our model, is (1/e), the iteration complexity we derive is optimal. The exploitability minimization via EDA is thus an optimal approach to GNEP in since pseudo-gand games generalize games, our results show that the complexity of this class of pseudo- games is the same as that of the corresponding games.
cumulative regret pseudo- seeudo-games.. Additionally,
Pseudo-Games with Jointly Convex Constraints
More generally, the exploitability minimization problem is equivalent to non-convex-concan min-max optimization problem, i.e., cumulative regret is non-convex-conen minimax theorem does not hold, which precludes the existence of saddle point, making the problem much harder. Solving non-conveex-oneee
In such cases, a
min-max optimization problems is NP-hard in general [99] so we instead set as our goal finding a (first-order) stationary point a* E X' of the exploitability yo, i.e., point at which first-order deviations cannot decrease the exploitability, which conooomll--iim... Note that any stationary point a" of the exploitability is a )-GNE of the associated pseudo-game.
we show can be found in
In recent years, variety of methods have been developed that could be applied finding stationary points of the exploitability 19 25 26
27 31]. Using the most efficient these methods, one could obtain convergence an E-statoonary point of the exploitability in O(1/e)) iterations [19] However, as we will see, this rate would be very slow, and the convergence metric, not very strong, e.g., convergence in expected iterates. Instead, we demonstrate how to leverage the structure of the problem to obtain much faster convergence rates.
applolability-miiiizallll
Unfortunately, the exploitability associated with the min-max characterization of pseudo-gamad games with joint constraints is non-dite differentiiable in general. This fact poses an obstacle when trying to design efficient algorithms that find its stationary points. However, by exploiting the structure of cumulative regret, we can regularize it to obtain a smooth objective. Observe the following:
All omitted proofs can be found in Appendix B

---

a' E arg maxbex aa b), then a" E arg max Vaa", b). In other words, b' = a" is solution to the inner maximization problem. As a result, we can penalize exploitability in proportion to the distance between a and b, while still ensuring that this penalized exploitability is minimized at VE. We thus optimize the a-regularized cumulative regret t/ A x A R, defined as da (a, b) = ( b) _ al blβz whose associated a-regularized exploitability Pa : A + I is given by (a(a) = maxbex (a b). Von Heusinger and Kanzow show that a strategy profile a" has no --regularized-expllttaabbbi ie., (a(aa) = 0, iff a is a VE for all a 0
(Theorem 3.3 (65).
To better understand the smoothness properties of the regularized exploitability, we present the parametric Moreau envelope, a Moreau envelope [100] in which the objective function is a function of the point w.r.t. which we regularize the objective function, which in our case is cumulative regret. Our next theorem is a generalization that a-rreularized exploitability is Lipschitz-smooth by allowing us to Pa as a parametrie Moreau envelope for v an observation which to our knowledge has not been made in previous work. This
the Moreau envelope theorem [100], which shows
of Pa gives rise to the possibility of deriving algorithms that converge to a stationary point of Pa., the key idea underlying our second algorithm (ADA; Algorithm 2
Theorem 4.1 (Parameteric Moreau Envelope Theorem). Given a > O. consider the parametric Moreau envelope (a) = maxbex x (; b) - I|a -0 blli] and the associated proximal operator {b" (a)} = arg ba { (baaa) b) / lla b16) where ub is y smooth. Then (a(aa is ( + & -ipschitz-smooth, with gradients V (a) = Vab(a, b" (a)) a(a - bb(
Next, we formalize the definition of stationary point. As the exploitability Pa in general non-convex, and the optimization problem minaeX (a) is constrained, the first-order condition (a)(a) = 0 is not sufficient for stationarity, since a solution on the boundary of the constraint set could also be first-order stationary. As result, we use proximal mappings in our definition. In particular, we reformulate the constrained exploitability minimization problem as the unconstrained minimization problem minaeR".. G. (a) ) + xx(a). In this optimization problem, ya. is continuous and Lipschitz, smooth, while 1x is continuous and convex. Additionally, the set of solutions is non-emply. As a result, one can solve this problem using the proximal gradient method, which, in this case, is equivalent to the projected gradient method 997 101]. This view of the problem as proximal minimization allows us to provide a clear definition of a first-order stationary point.
Define the projected gradient operator of a function 9 A + R for some step size Taa > 0 as
-Ix a "la Va)(a) The projected gradient operator a special case of the gradient mapping operator, and a generalization of the gradient that is projected back onto the feasible set X [101]. The zeros of the projected gradient operator capture stationary points both at the boundary of the set X' and in its interior. Indeed, E A is stationary point of sp if GV (a) o. Note that, for an action profile a E A to be a VE, it is necessary that it is
follows: C. (a)
stationary with respect to the VE exploitability (Proposition 80 Our goal will thus be to achieve convergence to a strategy profile a E X s.t. (a) =0. O.
ADA (Algorithm 2 is nested GDA algorithm, similar to those of Nouiehed et al. 25 and Goktas and Greenwald 85 with the objective function augmented by a smart regularizer. The algorithm is reminiscent of EDA, interleaving gradient ascent and descent steps. The key difference is that whereas EDA runs only a single step of extragradient ascent (to find a better response). ADA runs multiple steps of gradient ascent to approximate best response. Indeed, as Theorem 4.2 shows, ADA's accuracy depends on the accuracy of the best-nesponse found.
To derive convergence rates for ADA, we rely two technical lemmas. The first tells that the inner loop can approximate the gradient of the exploitability to any desired precision. More specifically, we bound the error || Va
- Vava va (t()), b(O)]| S e by providing a lower bound on the number of inner loop iterations T3 necessary to achieve a desired precision e, for all outer loop iterations E [Ta] (Lemma B.3). The second lemma bounds the algorithm's progress at each iteration of the outer loop by relating E and G% (a,) (Lemma B.4. Finally, by telescoping the inequalities in the progress lemma, we obtain our main theorem: The best iterate found by
7

---

Algorithm 2 Augmented Descent Ascent (ADA)
Inputs: n. u, Na ?b Ta. Tb. a ((0)
Outputs: (a b(t)
for 0,.... ................................ Ta 1 do
2: a ((+1) IIx (t)) Ta (Vat(alt) - a(a!)) -b())
0
4: for = 0.... Tb - do
5: IIx b + 4bb (Vos(aa((t)) b) bbi)
6: b(t+1) b
return (a ((t) ((0)
To 1=
ADA, as measured by the norm of the projected gradient operator, converges to an approximate stationary point of the exploitability in all Lipschitz-smooti pseudo-games -amios with jointly convex constraints. We note that if the gradient of the regularized exploitability can be computed exactly, then convergence to exact stationary point can be obtained.
Theorem 4.2 (Convergence to Stationary Point of Exploitability). Suppose that ADA is pseudo-game G which satisfies Assumption 3.3 with learning rates
and
7b Ten
210g Tova
22
for any number of outer loop iterations Ta E N++ and for To 2
total inner loop
log
TTva
iterations where
0. Then the outputs B000 satisfy mitl Oa.., -1
Gg (at)))
S
(0 +e E ((EEV + Be +5)
1
1
+ lyv
10 S/
Ta
Note that the stationary points to which ADA converges are global minima of Pa iff Pa is invex, in which case ADA converges to VE, and hence GNE [102]. We can also obtain faster and last iterate convergence to VE in more restricted class of games. A pseudo-game is said to be a p-PL-pseudo-gane
if the regularized exploitability Pa satisfies the p-projecttion-Polakk Lojasiewiez (PL) condition, i.c. the projected gradient operator associated with Po satisfies
1/2 G+ (a)
(a)(a) minaex Pa. (a)) for all 2 A similar PL-condition for games was recently used by Raghunathan, Cherian, and Jha 104 which they argued is natural.
Theorem 4.3 (PL Exploitability Convergence). Suppose ADA is
PL- PL-pseedo- gamme G
3.3 with learning rates al E [t & f + E
12
which satisfies Assumption
1
2p
and Tbb 1/ew va
for any number of outer loop iterations Ta E N
VVa log( vo.)
2m total inner loop iterations.
and for To (a(t))b(t))
Then the outputs
BTO))T satisfy
Pala
1 + 24
tv +
1 na
(a(a +
((LOV) + Evv
( +5)
Cos +
1 Na
+
E.
We note that this result also implies convergence to a VE in strongly-convex exploitability games in linear time well, since strong convexity implies the PL-condition.
'e note that this is special case of the mroximal-Polyak-Lojnae condition (See Section
103

---

5 Experiments
In this section, we report on experiments that demonstrate the effectiveness of our algorithms as compared to others that were also designed to compute GNE. We present numerical results that were studied empirically in previous work [104]: 1) monotone
on benchmark psuedo-gamd pseudo-games with affine constraints and 2) bilinear pscudo-gan games with jointly convex constraints We compare our algorithms to the accelerated mirror proo quadratic penalty method (AMPQP), the only GNE- ANE-finding algorithm with theoretical convergence guarantees and rates (78 For the AMPQP algorithm, we use the hyperparameter settings derived in theory when available, and otherwise conduct grid search for the best ones. We compare the convergence rates of our algorithms to that of AMPQP, which converges at the same rate as EDA, but slower than ADA, in settings in which it is guaranteed to converge, i.e., in monotone pseudo-games.
In the monotone ADA we use the constant learning rates of 1/4 - 0.02 and T/ = 0.05. These rates approximate the Lipschitz-smootthner parameter of the pseudo-games games. In the bilinear pseudo-games, we use the peaxrettcaaly-groundde (Theorem 3.4) learning rate of 1 = 1/1Q11 for EDA, and 7/ = ||QI|
games, for EDA we use a constant learning rate of 1 = 0.02, while for
+ @Q@l and 1//- = 1//1Q11 for ADA. In both settings, we use regularization of a = 0.1 for ADA, which we found by grid search. Likewise, in our implementation of AMPQP, grid search led us to initialize 3g = 0.01, = 1.05, = 0.2 in both settings S Additionally, because the iterates generated by AMPQP are not necessarily feasible, we projected them onto the feasible set of actions, so as to avoid infinite exploitability. This heuristic improved the convergence rate of AMPQP significantly. The first iterate for all methods was common, and initialized at random.
Monotone Games with Jointly Affine Constraints We begin by experimenting with monotone games with jointly affine constraints, the largest class of pseudo-game for which convergence rates exist for AMPQP. In particular, consider mommiiininization
peeudogamess with payoff [Ee(m) a, -s. for all players i E [n]. and for some randomly initialized
functions (a)))
shifting factors 8,, as well as jointly affine constraints g(a) = = =1- Zja(m) 41 - -ie(m)) G2j. with action spaces A, = [-10, 10j"", for all players i E [n]. Although norm- norm-minimization games are trivial, in the sense that they can be solved in closed form, this is not the case for sreudo-games; on the contrary, they form bedrock example for monotone pseudo-game games
57
Example 1).
In Figure la we observe that all three algorithms converge to a GNE. Interestingly, EDA and ADA find distinct GNEs from AMPQP, which is not entirely surprising, as AMPQP is not an exploitability minimization algorithm. Although all the algorithms eventually find a GNE, exploitability does not decrease monotonically (Figure lb}: on the contrary, it increases before eventually decreasing to zero. Convergence to a GNE is expected for AMPQP, as per the theory. EDA, however, is not guaranteed to converge to a GNE in pscudo-games beyond convex exploitability; yet, we still observe convergence, albeit at a slower rate than AMPQP or ADA, Likewise, ADA converges to a GNE, although it is again not guaranteed, much faster than AMPQP.
Bilinear General-Sum Games with Jointly Convex Constraints Second, we consider the class of two-playee general-sum games with jointly convex constraints with payoff functions T QuQaa uz(a) = a, T TQ2az; (aa) = - |||| A1 = A = [-10 10]m Such games are not monotone, and hence AMPQP is not guaranteed to converge in theory. In Figure ic we see that convergence is not guaranteed empirically either; shown is a sample run in which ADA and EDA converge, while AMPQP exhibits erratic behavior. Non-convergence for AMPQP was
"1 (a) = a,
'We describe additional experiments in the supplemental work, with two-player zero-sum bilinear pseudo- games with jointly affine constraints and two-player zero-sum bilinear pscudo-gen gamess with jointly convex constraints. The results are not qualitatively different than those presented here. All our code can be found on https://githhu cww/ htt//ddnizzalppe wwt.pppexpliitmmiii
We note that we are not reporting on our results with the Accelerated Mirror-Prox Augmented Lagrangian Method (AMPAL). another method studied in the literature with the convergence rates AMPQP, because we found this algorithm be unstable our benchmark pseudo- gamee..
$ As suggested by Jordan, Lin, and Zampetakis (78). we replaced the convergence tolerance parameter d, with the number of iterations for which the accelerated mirror-prox subroutine [105] was run. Then, at each iteration of AMPOP, this parameter was increased by factor of of AMPQP.

---

EDA
432
AUPOP
AMPO?
400
30
Number bentzes
Number of Aetratinns
(a) Phase portrait for (b) Exploitability for a (c) Phase portrait for bilin- (d) Exploitability for 2 player monotone game player monotone game ear general-sum pseudo- bilinear with m =
general-sum pseudo-game; m = 10
with m = 10
game with m =
Figure 1: Convergence monolone and bilinear general-sum pseudo-games.
observed in 93 of the 100 experiments run. In fact, though AMPQP gets very close GNE (Figure Id). i.., zero exploitability, it does not stabilize there. We likewise found that ADA and EDA do not converge to GNE from all random initializations. In such cases, we restarted the algorithms with a new random initialization; this process lead to on average 11 restarts for EDA and 10 restarts for ADA, meaning both algorithms converged to GNE within this window.
Conclusion
In this paper, we provide an affirmative answer to an open question first posed by Flam and Ruszczynski [8]] who suggested that projected gradient methods could be developed to minimize exploitability in pscudo-games. Although some existing methods [57] make use of the exploitability
concept analyze algorithms that take alternative optimization approaches, we know of none that algorithms per se, as exploitability itself is not explicitly minimized. Our main contribution the observation that the exploitability minimization problem can recast as simple and seemingly trivial min-max optimization problem (Observation 3.2). Our analysis effectively extends the class of games which can be solved as potential games, since the exploitability can be seen as potential for any game.
are
We provide definition of stationarity for exploitability via the gradient mapping operator from proximal theory, and we use this definition to characterize the limit points of our algorithms. Our characterization relies on novel proof techniques inspired by recent analyses of algorithms for min-max optimization problems [25], as well as parameterized version of Moreau's envelope theorem, which may be of independent interest. This approach, which takes advantage of the structural properties of exploitability, allows us to rigorously analyze an algorithm that converges stationary points the VE exploitability in all Lipschitz-smooth pseudo-games games with jointly convex constraints, and obtain algorithms which are orders of magnitude faster than known min- max optimization algorithms for similar types problems. known polynomial-time convergence guarantees to VEs, and thus GNEs, to class of pseudo-gamed -aames beyond monotone, and 2. provide a general approach approximate, with convergence guarantees, solutions to Lipschitz-smood pseudo-games with jointly convex constraints.
summarize, our results extend
The design of efficient algorithms for constrained non-convex-concave min-max optimization problems is an open problem. The literature thus far has focused on problems in which only the Our techniques may provide path to solving
variable to be maximized is constrained 25
27 29
non-convex- concave min-max optimization problems in entirely constrained domains, since our algorithms solve non-convex-concav optimization problem where both variables are constrained.
Acknowledgmentss and Disclosure of Funding
The ideas in this paper stemmed from conversations and seminars held during the Learning in Games workshop the Simons Institute for the Theory of Computing. This work also supported by NSF Grant CMMI-1761546.
10

---

References
[1] John F. Nash. "Equilibrium points <i>n=/is-person games" In: Proceedings of the National Academy of Sciences 36.1 (1950), pp. 48-49. Dor: 10. 1073/pnas 36 1. 48 eprint: https
/ //www. pww..org/d.....ooooooo. wwt.oo//////////////////e 1073/pnas 36.
.48 URL: https://wwwt www..pnas.. amas.orgaa.. org/doi/
abs/10. 1073/ pnas 36.
48
[2]
Martin Osborne and Ariel Rubinstein. A course in game theory. MIT press, 1994.
[3] Noam Nissan and Tim Roughgarden. Algorithmic Game Theory. Cambridge University Press, 2007. DoI: 10. 0177/B80980011180044
[4] Christos H Papadimitriou. "On the complexity of the parity argument and other inefficient proofs of existence". In: Journal of Computer and system Sciences 48.3 (1994), pp. 492-532. [5] Xi Chen and Xiaotie Deng. "3-Nash is PPAD-complete". In: Electronic Colloquium on Com- putational Complexity. Vol. 134. Citeseer. 2005, pp. 2-29.
[6] Xi Chen and Xiaotie Deng- "Settling the complexity of two-player Nash equilibrium", In: 2006 47th Annual IEEE Symposium Foundations of Computer Science (FOCS'06). IEEE. 2006, pp. 261-272.
[7] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou, "The complexity of computing Nash equilibrium", In: SIAM Journal on Computing 39.1 (2009), pp. 195-255
[8] Paul Tseng. "On linear convergence of iterative methods for the variational inequality problem". In: Journal of Computational and Applied Mathematics 60.1 (1995). Proceedings of
the International Meeting on Linear/Nonlinear Iterative Methods and Verification of Solution,
pp. 237-252. ISSN: 0377-0427. DOr: http:://ooo..oooo/////1111111111
URT. httph:://www sci sciencedirecttt..ccccccceeeeeeie wtt.
[9] Yurii Nesterov and Laura Scrimali. "Solving strongly monotone variational and quasi- variational inequalities". In: Discrete & Continuous Dynamical Systems 31.4 (2011), pp. 1383-
1396.
[10] Gauthier Gidel et al. A Variational Inequality Perspective on Generative Adversarial Networks. 2020. arXiv: 1802. 10551 [G]
[11] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence Rate of for Optimistic Gradient and Extra- iitraaggadiint Methods in Smooth Convex-Concave Saddle Point Problems. 2020. Xiv: 1906. 01 01115 [math.00 _0C]
[12] Adam Ibrahim et al. "Lower bounds and conditioning of differentiable games". In: arXiv preprint arXiv:1906.00 07300 (2019).
[13] Mingyi Hong, Junyu Zhang. Shuzhong Zhang, et al. On Lower lteration Complexity Bounds for the Saddle Point Problems. 2020. arXiv: 1912. 07481 [math.00, [C]
[14] Tianyi Lin, Chi Jin, and Michael Jordan. "Near-optimal algorithms for minimax optimiza- tion". In: Conference on Learning Theory. PMLR. 2020, pp. 7779.9779.
[15] Mohammad Alkousa et al. Accelerated methods for composite non-bilinear saddle point problem.
2020. arXiv: 1906. 03620 [math. [C]
[16] Anatoli Juditsky, Arkadi Nemirovski, et al. "First order methods for nonsmooth convex large-
scale optimization, ii: utilizing problems structure". In: Optimization for Machine Learning
30.9 (2011), pp. 149-183
[17] Erfan Yazdandoost Hamedani and Needet Serhat Aybat. "A 'Aprimal-dua algorithm for general convex-concave saddle point problems". In: arXiv preprint arXiv:1803.00 110.00000300111111 2 (2018). [18] Zhao Renbo. Optimal algorithms for stochastic three-composite convex-concave saddle point problems. 2019. arXiv: 1903. 01 68687 [math.OC]]
[19] Kiran Koshy Thekumparampi et al. Efficient Algorithms for Smooth Minimax Optimization.
2019. arxiv: 1907_ /997_01543 01543 [mathhoC]]
[20] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. 2018. arXiv: 1808. 02901 [math. [math.oC]
[21] Arkadi Nemirovski. "Prox-methon with rate of convergence (1/t) for variational inequal- ities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems". In: SIAM Journal on Optimization 15.1 (2004), pp. 229-251.
[22] Yurii Nesterov. "Dual extrapolation and its applications to solving variational inequalities and related problems". In: Mathematical Programming 109.2 (2007), pp. 319-344.
11

---

[23]
Paul Tseng. "On accelerated proximal gradient methods for convex-concave optimization". In: submitted SIAM journal on Optimization (2008).
[24] Maziar Sanjabi et al. "On the Convergence and Robustness of Training GANs with Regu- larized Optimal Transport". In: Proceedings of the 32nd International Conference Neural Information Processing Systems. NIPS' 18. Montreal, Canada: Curran Associates Inc., 2018, pp. 7091-7101.
[25] Maher Nouiched al. "Solving a class of non-convex min-max games using iterative first order methods". In: arXiv preprint arXiv:1902.088: 08297 (2019).
[26] Songtao Lu, Ioannis Tsaknakis, and Mingyi Hong. "Block alternating optimization for non-convex min-max -mx problems: algorithms and applications in signal processing and com- munications", In: ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEFF. 2019, Pp. 4754-4758.
[27] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What is Local Optimality in Nonconvex- Nonconcave Minimax Optimization? 2020. arXiv: 1902. 0226100618 18 [C]
[28] Dmitri M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. "Efficient search of first- order nash equilibria in nonconvex-concaye smooth min-max problems". ". In: arXiv preprint arXiv:2002.00 07919 (2020).
[29] Tianyi Lin, Chi Jin and Michael Jordan.
Jordan.. "On gradient descent ascent for nonconvex-concave minimax problems". In: International Conference on Machine Learning. PMLR. 2020, pp. 6083- 6093.
[30] Renbo Zhao A Primal Dual Smoothing Framework for Max-Structturd Nonconvex Optimiza- tion. 2020. arXiv: 20033 04375 [math.OCy
[31] Hassan Rafique et al. Non-Convex Min-Max Optimization: Provable Algorithms and Applica- tions in Machine Learning. 2019. arXiv: 1810. 02060 [math. OC]
[32] Dov Monderer and Lloyd S Shapley. "Potential games". In: Games and economic behavior
14.1 (1996), pp. 143-143.
[33]
William H Sandholm. "Potential games with continuous player sets". In: Journal of Economic theory 97.1 (2001). pp. 81-108.
[34] Stephane Durand and Bruno Gaujal. "Complexity and optimality of the best response algorithm in random potential games". In: International Symposium on Algorithmic Game Theory. Springer. 2016, pp. 40-51.
[35] Yurii Nesterov and Laura Scrimali. "Solving strongly monotone variational and quasi- variational inequalities". In: (2006).
[36] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng, "Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities". In: arXiv preprint arXiv: 09228 (2022).
[37] Yu Malitsky. "Projected reflected gradient methods for monotone variational inequalities".
In: SIAM Journal on Optimization 25.1 (2015), pp. 502-520.
[38] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. "Extragradient method: O (1/K) last-iterate convergence for monotone variational inequalities and connections with coco- ercivity". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 366-402.
[39] Tatiana Tatarenko and Maryam Kamgarpour. "Learning Nash equilibria in monotone games". In: 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE. 2019, pp. 3104-3109,
[40] Bingsheng He et al. "A new inexact alternating directions method for monotone variational inequalities". In: Mathematical Programming 92.1 (2002), pp. 103-118.
[41] Yu V Malitsky and VV Semenov. 'An extragradient algorithm for monotone variational inequalities", In: Cybernetics and Systems Analysis 50.2 (2014), pp. 271-277.
[42] Ian Goodfellow et al. "Generative Adversarial Nets". In: Advances in Neural Infor- mation Processing Systems. Ed. by Z. Ghahramani et al. Vol. 27. Curran Associates, Inc., 2014. URL:: https : / proceedings neur ips . cc paper 2014 file /
[43] Antonia Creswell et al. "Generative Adversarial Networks: An Overview". In: JEEE Signal Processing Magazine 35.1 (2018), pp. 53-65. doI: 10. 1109/M199PPP.. 2017. 2765222
[44] Kenneth Arrow and Gerard Debreu. "Existence of an equilibrium for a competitive economy".
In: Econometrica: Journal of the Econometric Society (1954), pp. 265-290.
12

---

[45] Michael Brückner, Christian Kanzow, and Tobias Scheffer. "Static prediction games for adversarial learning problems". In: J. Mach. Learn. Res. (2012), pp. 2617-2654. URL: http:
//dl. acm. wtt..acm.org/ciaaaaeeee 3
cfm2id=2503326
[46]
Michael Brückner and Tobias Scheffer. "Nash equilibria of static prediction games". In:
Advances in neural information processing systems 22 (2009).
[47]
Equilibria in Electric Power Markets with Piecewise Linear Demand Functions and Joint Constraints". In: Operations Research 55.1 (2007), pp. 113-127. DOI: 10. 10..1.2.111 1w8128887ppee 1060. 0342 eprint: attps://doi.e org / 1287/
Benjamin F. Hobbs and] J. S. Pang.
opre. 1060. 0342 URL: https: org/ 1287 1287/opre...
[48] Wei Jing- Yuan and Yves Smeers. "Spatial Oligopolistic Electricity Models with Cournot Generators and Regulated Transmission Prices' In: Operations Research 47.1 (1999), pp. 102-
112. Dor 10. 1287 /oree.ppeeeeeo. 47 102 eprint: httpps: informs org/ doi/ odf 12 1287/2887/p// 47. 1. 102
URL: https::/ppbssnniine www.bbsooonnnne..ffrross. informs.ommm...... orgg aas//0
1287/opre.. 1.2
[49] Michele Breton, Georges Zaceour, and Mehdi Zahaf. "A game-theoretic formulation joint implementation of environmental projects". . In: Europeun Journal of Operational Research
168.1 (2006), pp. 221-239
[50] Jacek B. Krawezyk. "Coupled constraint Nash equilibria environmental games". ". In: Re- source and Energy Economics 27.2 (2005), pp. 157-181. ISSN: 0928-7655. Dor: https://doi
org/10 1016 www.eeeeee.......e...........w.. 2004 08 001 URL: https:
www. www.://wwwww////../ www.ssececccdeecct.. com/
[51] Danilo Ardagna, Michele Ciavolla, and Mauro Passacantando. "Generalized Nash Equilibria for the Service Provisioning Problem in Multi-Cloud Systems" In: JEFE Transactions on Services Computing 10.3 (2017), pp. 381-395. DOr: 10. 1109/TSC. 2015 2477836
[52] Danilo Ardagna, Barbara Panicucci, and Mauro Passacantando. "A Game Theoretic Formula- tion of the Service PriiceePooooe Provisioning Problem in Cloud Systems". " In: Proceedings of the 20th Inter- national Conference on World Wide Web. WWW '11. Hyderabad, India: Association for Com- puting Machinery, 2011. pp. 177-186. ISBN: 9781450306324, Do1: 10. 0011111163495 1963433 URL.: https:://ooii org/orgg///// /00 145/1963405. 9934333
[53] Xuegang (Jeff) Ban et al. "A general equilibrium model for transportation systems with e- hailing services and flow congestion", In: Transportation Research Purt B: Methodological 129
(2019), 273-304. ISSN: 0191-2615. nor: https: http://ooo..rrg///// 1016/ trb, 2019, 08 012 URL: hhttps://wwet www.sccieeeneeee..ccccc.eo.ceeee
[54] Oliver Stein and Nathan Sudermann
"The noncooperative transportation problem and linear generalized Nash games". In: European Journal of Operational Research 266.2
(2018), pp. 543-553. Dor: 10. 1016 ejor 2017. 10.
URL: https::/ideas. repec.cpee... org/
3/eee/ejorrss/226yy2000 8i28812pp3333 html
[55] Zhu Han et al. Game theory in wireless and communication networks: Theory, models, and applications. English. Vol. 9780521196961 Publisher Copyright: @ Cambridge University Press 2012. United Kingdom: Cambridge University Press, Jan. 2011. ISBN: 9780521196963.
DO1: 101:10.11 1017//B099/ 0118809788511888 88511895543
[56]
Jong Pang et al. "Distributed power allocation with rate constraints in Gaussian parallel interference channels". In: IEEE Transactions on Information Theory 54.8 (2008), pp. 3471- 3489.
[57] Francisco Facchinei and Christian Kanzow. "Generalized Nash equilibrium problems". In: Annals of Operations Research 175.1 (2010), pp. 177-211.
[58] Andreas Fischer, Markus Herrich, and Klaus Schönefeld. "GENERALIZED NASH EQUILIB- RIUM PROBLEMS RECENT ADVANCES AND CHALLENGES", In: Pesquisa Operacional
34 (2014), pp. 521-558.
[59] Francisco Facchinei, Andreas Fischer, and Veronica Piccialli. "Generalized Nash equilibrium problems and Newton methods". In: Mathematical Programming 117.1 (2009), pp. 163-194.
[60] Francisco Facchinei and Simone Sagratella. "On the computation of all solutions of jointly convex generalized Nash equilibrium problems". In: Optimization Letters 5.3 (2011), pp. 531 547.
[61] Dario Paccagnan et al. "Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints", In: 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, 2016, pp. 6123-6128.
13

---

[62] Peng Yi and Lacra Pavel. "A distributed primal-dual algorithm for computation of generalized Nash equilibria via operator splitting methods". In: 2017 JEEE 56th Annual Conference on Decision and Control (CDC). IEEF. 2017, pp. 3841-3846.
[63] Eleftherios Couzoudis and Philipp Renner. *Computing generalized Nash equilibria by polynomial programming" In: Mathematical Methods of Operations Research 77.3 (2013), pp. 459-472.
[64] Axel Dreves. "Computing all solutions of linear generalized Nash equilibrium problems". In: Mathematical Methods of Operations Research 85.2 (2017), pp. 207-221.
[65] Anna Von Heusinger and Christian Kanzow. "Optimization reformulations of the gener- alized Nash equilibrium problem using Mikkido-lsoda-tyrnn functions". In: Computational Optimization and Applications 43.3 (2009), pp. 353-377.
[66]
Tatiana Tatarenko and Maryam Kamgarpour. "Learning generalized Nash equilibria in class of convex games". In: IEFE Transactions on Automatic Control 64.4 (2018), pp. 1426- 1439.
[67]
Axel Dreves and Nathan Sudermann "Solving linear generalized Nash equilibrium problems numerically". In: Optimization Methods and Software 31.5 (2016), pp. 1036-1063.
[68] Anna Heusinger, Christian Kanzow, and Masao Fukushima. "Newton's 's method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation", In: Mathematical Programming 132.1 (2012), pp. 99-123.
[69] Alexey F Izmailov and Mikhail V Solodov. "On error bounds and Newton-type methods for generalized Nash equilibrium problems". In: Computational Optimization and Applications 59.1 (2014), pp. 201-218.
[70] Andreas Fischer al. "A globally convergent LP-Newton method". In: SIAM Journal on Optimization 26.4 (2016), pp. 2012-2033.
[71] Jong-Shi Pang and Masao Fukushima. Squasi-variational inequalities, generalized Nash equilibria, and multi-eaader-followerr games". In: Computational Management Science 2.1 (2005), pp. 21-56.
[72] Francisco Facchinei and Lorenzo Lampariello. "Partial penalization for the solution of generalized Nash equilibrium problems". In: Journal of Global Optimization 50.1 (2011),
pp. 39-57.
[73] Masao Fukushima. "Restricted generalized Nash equilibria and controlled penalty algorithm".
In: Computational Management Science 8.3 (2011), pp. 201-218.
[74]
Christian Kanzow. "On the multiplier- multiplier-penallyy penalty-approade for quasi-variational inequalities".
In: Mathematical Programming 160.1 (2016), pp. 33-63.
[75] Christian Kanzow and Daniel Steck. "Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems". In: SIAM Journal Optimization 26.4 (2016), pp. 2034-2058.
[76] Christian Kanzow and Daniel Steck. "Augmented Lagrangian and exact penalty methods for
quasi-variations inequalities". Computational Optimization and Applications 69.3 (2018),
pp. 801-824.
[77]
Qin Ba and Jong-Si Shi Pang. "Exact penalization of generalized Nash equilibrium problems". In: Operations Research (2020).
[78] Michael I. Jordan, Tianyi Lin, and Manolis Zampetakis. First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems. 2022. DO1: 10. 08550/ARXIV 2204 03132 URL:
https://arxiv org/ werg/abs/2uu abs/ 20002211222222222222222222212222
[79] Hukukane Nikaidó and Kazuo Isoda. "Note non-cooperative convex games". In: Pacific
Journal of Mathematics 5.S1 (1955), pp. 807-815.
[80] Sjur Flam and Andrzej Ruszczynski. Noncooperative Convex Games: Computing Equilibrium By Partial Regularization. Working Papers. International Institute for Applied Systems Analysis, 1994. URL: https:://cooPpppot
www.rrepeccoooo org wwwppppe..org//Peeeroe.e.e. RePPEc:wpp::: 1ts::::wsswwww9w0p000:
[81] Edward Lockhart et al. "Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent". In: CoRR abs/ 100.0/99300 (2019). arXiv: 1103.05614 URL:
http://arxivv org abs//903. 05614
[82] Ian M. Gemp et al. 'Sample-based" Approximation of Nash in Large Many-PPlaer Games via Gradient Descent". In: CoRR abs/2106.012s (2021). arXiv: 2106 01285 URT: https
wwt.xxv.org/abss/// 01285
14

---

[83] Galina M. Korpelevich. "The extragradient method for finding saddle points and other problems". In: Matecon 12 (1976), pp. 747-756.
[84] Angelia Nedic and Asuman Ozdaglar. "Subgradient methods for saddle-point problems". In: Journal of optimization theory and applications 142.1 (2009), pp. 205-228
[85]
Denizalp Goktas and Amy Greenwald. "Convex-Concave Min-Max Stackelberg Games". In: Advances in Neural Information Processing Systems 34 (2021).
[86] J. B. Rosen. "Existence and Uniqueness of Equilibrium Points for Concave N-Person Games".
In: Econometrica 33.3 (1965), pp. 520-534. ISSN: 00129682, 14680262. URL: http: //tp://www
jstor. Sttor.orgg/table///ee 1911 749 (visited on 05/16/2022).
[87] S. Uryas'ev ev and R.Y. Rubinstein, "On relaxation algorithms in computation of noncooperative equilibria". In: IEFE Transactions Automatic Control 39.6 (1994), pp. 1263-1267, nor:
10. 1009/9 293193
[88]
Jacek B. Krawczyk and Stanislav Uryasev. "Relaxation algorithms to find Nash equilibria with economic applications" English. In: Environmental Modeling & Assessment 5.1 (2000). This revised version was published online in July 2006 with corrections to the Cover Date.,
pp. 63-73. Do1: 10. 1023/A: 101 1019097288499
[89] A. Heusinger and C. Kanzow. "Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search". In: Journal of Optimization Theory and Applications
143.1 (2009), pp. 159-183 URL:
143:y: 2009 ; 1: 1 d: 10. 1007 0et.1000711997-000 1957-999-9555--
[90] Axel Dreves et al. "A Globalized Newton Method for the Computation of Normalized Nash
Equilibria". In: J. of Global Optimization 56.2 (June 2013), pp. 327-340 ISSN: 0925-5001. Dor 981-994-999
URL: hittps://don org. 10.
[91] Francisco Facchinei, Andreas Fischer, and Veronica Piccialli. "On generalized Nash games I and variational inequalities". In: Operations Research Letters 35.2 (2007), pp. 159-164. ISSN:
0167-6377. Do1: https: org 10 1016 2006 03 004
URL: https: // www
sciencedirect. wtt.:ecccccooociiiieeeieecc ottpa/nccc.ttttccoo.ocoocoeeeaed
[92] Koichi Nabetani, Paul Tseng, and Masao Fukushima. "Parametrized Variational Inequality Approaches Generalized Nash Equilibrium Problems with Shared Constraints" In: Comput. Optim. Appl. 48.3 (Apr. 2011), pp.
ISSN: 0926-6003, DOT: 10. 1007 10070/105899-009
9256-3
URL: ht org 10. 1007 109-000599999255550
[93]
Dane A. Schiro, Jong-Sh Shi Pang, and Uday V. Shanbhag. "On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke's 'ss method". English. In: Math- ematical Programming 142.1-2 (2013). This work was based on research partially supported by the National Science Foundation under grant CMMI-0969000 and the Department of Energy under grant DOE DE-SC0003879, pp. 1-46. DO1: 10. 0007/s10107-000
[94] Francisco Facchinei and Christian Kanzow. "Penalty Methods for the Solution of Generalized Nash Equilibrium Problems". In: SIAM Journal on Optimizatioon 20.5 (2010), pp. 2228-2253.
DO1: 10. 0 //doi.org/11 1137/09874990
eprint: https:///ol:: /ttp///.......111111//00//000000 0137/ URL: https
[95] Luis Felipe Bueno, Gabriel Haeser, and Frank Navarro Rojas. "Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and Their Practical
Implications". .
In: SIAM Journal on Optimization 29.1 (2019), pp. 31-54. Dor: 10. 1137/ /
17M1162524 eprint: https:
1137/17M1 162524
URL: https: / doi org/
10. 11377/1MM162571
[96] J v Neumann. "Zur theorie der gesellschaftsspiele" In: Mathematische annalen 100.1 (1928),
pp. 295-320.
[97] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[98] Noah Golowich et al. "Last Iterate is Slower than Averaged Iterate in Smooth Convex- Concave Saddle Point Problems". In: CoRR abs/2002.00057 (2020). arXiv: 2002 00057 URL:
https://arxiw.org/bbs////
[99] Ioannis Tsaknakis, Mingyi Hong, and Shuzhong Zhang. "Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods".. In: arXiv
preprint arXiv:2110. 11210 (2021).
[100] Jean-Jacques Moreau. "Proximité et dualité dans un espace hilbertien". In: Bulletin de la
Société mathématique de France 93 (1965), pp. 279-299.
15

---

[101]
Amir Beck. First-order methods in optimization. SIAM, 2017.
[102] Shashi K Mishra and Giorgio Ciorgi. Invexity and optimization. Vol. 88. Springer Science & Business Media, 2008.
[103] Hamed Karimi, Julie Nutini, and Mark Schmidt. "Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewier condition", In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer. 2016,
pp. 795-811.
[104] Arvind Raghunathan, Anoop Cherian, and Devesh Jha. "Game thcoretic optimization via gradient-basee baseet nikaido-isoda function". In: International Conference Machine Learning. PMLR. 2019, pp. 5291-5300.
[105] Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. "Accelerated schemes for a class of variational inequalities". In: Mathematical Programming 165.1 (2017), pp. 113-149.
[106] Guido Van Rossum and Fred L Drake Jr. Python tutorial. Centrum voor Wiskunde en Informatica Amsterdam, The Netherlands, 1995.
[107] Charles R. Harris et al. "Array programming with NumPy". In: Nature 585 (2020), pp. 357-
362. Do1: 1038/ 1000004444 1586-020---21 1225566000-6--2222
[108] Steven Diamond and Stephen Boyd. "CVXPY: A Python-embedded modeling language for convex optimization", In: Journal of Machine Learning Research 17.83 (2016), pp. 1-5.
[109] J. D. Hunter. "Matplotlib: 2D graphics environment"
Computing in Science & Engineer-
ing 9.3 (2007), pp. 90-95. DOr: 10.00 11 109/MCSE.... WWC.E.200....... 2007.55 .55
[110] Gauthier Gidel al. "A variational inequality perspective generative adversarial net- works". " In: arXiv preprint ar0iv:1802. 10551 (2018).
[111] John M. Danskin. "The Theory of Max-Min, with Applications". In: SIAM Journal on Applied Mathematics 14.4 (1966), pp. 641-664. ISSN: 00361399.
URL: ht www jstor org /
stable/2946123
[112] S. N. Afriat. "Theory of Maxima and the Method of Lagrange". In: SIAM Journal Applied Mathematics 20.3 (1971), pp. 343-357. ISSN: 00361399, URL: http / www jstor org/ Gaalle2099935
[113] Paul Milgrom and Ilya Segal. "Envelope theorems for arbitrary choice sets". In: Econometrica 70.2 (2002), pp. 583-601.
[114] Murray H Protter, B Charles Jr, et al. A first course in real analysis. Springer Science & Business Media, 2012.
[115] Haim Brezis and Haim Brézis. Functional analysis, Sobolev spaces and partial differential equations. Vol. 2. 3. Springer, 2011.
[116] Elad Hazan, Karan Singh, and Cyril Zhang. "Efficient regret minimization non-convex games". In: International Conference on Machine Learning. PMLR. 2017, pp. 1433-1441.
16

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Yes, details are discussed in
conclusion, and experiments sections.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes] Assumptions summarized in Assumption 3.3
(b) Did you include complete proofs of all theoretical results? [Yes] Yes, all proofs can be found in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Yes, code repo can found here: https::/gg http//gttttt......e http://githuu.coommniiiiaaaa http://eenzzlppeeloottt-oo
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Details can be found section and Appendix A.
(c) Did you report error bars (e.g.. with respect to the random seed after running ex- periments multiple times)? [Yes] For experiments run multiple times, ie., zero-sum convex constraints, exploitability always reached zero, and there was hence no error to report in all randomly initialized examples.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] Details can be found in Appendix A.
4. If you using existing assets (e.g. code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Details can be found in Appendix
(b) Did you mention the license the assets? [Yes] Details can found Appendix
(c) Did you include any new assets either in the supplemental material or as URL?
[N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'te re using/curating? [N/A]
(c) Did you discuss whether the data you are using/ curating contains personally identifi- able information or offensive content? [N/A]
If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
17


Reviews:
[{"review_id": "mrpnucKqje", "reviewer": "Reviewer_y2D9", "summary": "The paper proposes two algorithms for finding approximate local Nash equilibria in pseudo-games. The algorithms are based on a new function, which roughly measures each player’s regret in some strategy profile a to a strategy in some other strategy profile b. A strategy profile a is an equilibrium if and only if it minimizes the maximum of regret over b to 0. The algorithms are then based on optimizing a and b with gradient ascent/descent. Various technical problems are addressed, e.g., gradient steps taking the solutions out of the feasible sets. The authors show that under convexity/concavity of the regret (and a few other assumptions), the algorithm finds (approximate) local Nash equilibria. They also demonstrate that they algorithms converge faster than existing algorithms in a few experiments.", "questions": "Most of the above questions seem relatively minor, but I’d still be interested in explanations.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper’s contribution seems good as far as I can tell. Unfortunately, I don’t know this literature (pseudo-games, finding equilibria) very well. So I’m not very confident in my judgment.\n\nSome minor comments:\n\nSuperfluous apostrophe in line 140.\n\nLine 148: Are we assuming differentiability?\n\nLine 229: “More generally, cumulative regret can be a non-convex-concave function, in which case a minimax theorem does not hold, which precludes the existence of a NE.“\nI found this sentence hard to understand. I suppose you are talking about the game induced by \\Psi, not the original game?\n\nThe sentence in Line 238ff. is not grammatical, I believe.\n\nLine 262: I assume one of the \\psi_\\alpha should be \\phi_alpha.\n\nLine 270: This is a weird indicator function, especially with the blackboard-bold 1, but okay.\nAlso, how is this indicator function continuous (or convex)? It looks rather discontinuous. Is this just on X?\n\nI don’t understand Line 2 and 3 of Algorithm 2. Why is line 3 performed n times, where n is the number of players?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PYLKPphX04W", "reviewer": "Reviewer_PS8T", "summary": "This paper introduces two algorithms for finding an approximate variational equilbrium in pseudo-games with jointly convex constraints. Both algorithms look at setting up exploitability as a min-max problem with the regret-maxmizing strategy being an optimized variable, rather than a non-smooth max-regret objective. The authors provide theoretical bounds for the algorithms, and compare the performance to an existing algorithm on a three classes of random test problems.\n", "questions": "How is this work providing methods for exact computation of GNEs?  Both algorithms are iterative methods with bounds on solution quality after T iterations.\n\n131: g>=0 iff g_i>=0 for all i?\n\n132: d is some arbitrary, game-specific choice?  Is there intended to be some difference understood between describing it as g(x,y) = (g_1(x,y),...,g_d(x,y))T and g(x,y):XxY -> R^d similar to other functions?\n\n135: min-max SE definition missing text describing leader (x) and follower (y) distinction?  Odd phrasing of definition, with the inequalities.  Those same inequalities make sense in the Goktas and Greenwald paper introducing min-max inequalities, where there are delta and epsilon approximations, but are non-intuitive choice here without the delta,epsilon. max_y f(x*,y) can not be greater than f(x*,y*).\n\n144: is this the same d as on line 132?\n\n150: \"in which case X is simply a set\"\nSome other phrasing? X_i(a) is a common set across all i, but that's a subset of X -- as noted on 159.  Regardless of joint constraints, X(a) is also a set, as is the same {a | a in X(a)} set.  Saying \"simply a set\" seems to imply seem obvious reason to consider this set X, which is at least not obvious to this reader.\n\n173, 178, 195, ...: Psi(b;a) is sometimes Psi(a,b), mostly later in the paper.  Psi(b;a) != Psi(a;b), so consistency here matters.\n\n193: Key insight (also? rather?) is switch to looking at VEs instead of GNEs? Without the issue of a* being within X(a*), finding a VE with joint convex constraints seems to be a standard optimization problem. phi is non-smooth -- but with that switch, wouldn't something like Nesterov smoothing also work, with similar bounds as EDA?\n\n204: What are those assumptions? Should also be included in the text, for contrast.\n\n219: O(1/epsilon^(1/2)), rather than O(1/epsilon^2)?\n\n249: How is b*=a a solution to the inner maximization? Is this max_{b in X} Psi(a,b)? For an arbitrary a, Psi(a,b=a)=0 seems unlikely to be a maximum.  The prior case where b=a* is in the argmax only seems to hold because Psi(a*,b) <= 0.\n\nAlgorithm 2: missing use of i in step 3?\n\nFigure 1b: The scale required to contain the spikes in exploitability makes it hard to tell how close to 0 are things in the tails. Are the different methods notably different, or are they all inconsequentially close to 0?  Possibly solved by including a log-scale version of this plot instead / as well.\n\n352: The paper states EDA has weaker assumptions on line 205, however here at line 353 AMPQP is expected to converge, while EDA is not. How do these two pieces fit together?\n\n\n320: psuedo\n330: we us -> we use a\n349: methodsEDA\n350: objectivesAMPQP\n", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work introduces two new algorithms EDA and ADA, with looser theoretical requirements than an existing algorithm, and the ability to find a stationary point in non-convex games, respectively.  On a set of randomized test problems, EDA is slightly worse and ADA is notably better, while both appear to be more likely to non-deterministically work than the baseline algorithm in situations where convergence isn't guaranteed.\n\nI found the paper to be generally readable, but there were a number of sections that were less clear. One major piece that was less clear was exactly what the contributions of the paper were. Is it theoretical, reducing the bounds of AMPQP by a log factor -- although possibly working in a smaller set of games? Is it finding stationary points in a larger class of games -- why not test that?  Is it the empirical performance -- why introduce EDA then, when it is slightly outperformed on the test games chosen?\n\n\n---- edited after author response\nClarifying the distinction between EDA and ADA,  EDA is a 1/epsilon method for finding a VE (and thus GNE) when regret is convex/concave, and ADA is a log(1/epsilon)/epsilon method for finding a stationary point as long as u is smooth and the feasible set is convex, or a VE if regret is invex.  This is described by lines 73-80.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HKTXCjjp4s", "reviewer": "Reviewer_h6T8", "summary": "This paper discusses Nash equilibrium computation in pseudo-games, which are games in which the players' legal strategy spaces may depend on other players' strategies. The paper reduces the problem to solving a certain min-max problem which is not convex-concave in the general case, and then gives algorithms for computing solutions of that min-max problem. The paper analyzes these algorithms both theoretically and practically, and obtain state of the art results in both.", "questions": "1. Is there any intuition for variational equilibrium? For example: why, in deviations, do we enforce the condition $\\boldsymbol{a} \\in \\mathcal{X}$? That seems to imply to me that somehow, we concern ourselves with ways that *all of the players can collectively deviate* (i.e., the \"joint deviation strategy\" $\\boldsymbol{a}$ must be feasible), yet at the same time we only care about whether each player individually profits from such a deviation when the others are playing equilibrium? This seems extremely weird to me coming from regular game land; the GNE definition seems more principled. \n1. Why does the paper bother to define general pseudo-games, when all the results are seemingly restricted to pseudo-games with joint constraints? That seems like the more natural case anyway, and it simplifies a good amount of notation. \n1. Along those lines, why is Section 4 titled \"Pseudo-games with jointly convex constraints\"? It seems like the entire paper devoted to pseudo-games with jointly convex constraints (by Assumption 3.3). \n1. Does this paper give any new results for normal-form games, or are the results of this paper known for that particular case? It would be nice for such things to be explicitly discussed somewhere - perhaps the results can be framed as an extension of known normal-form results if that is true.\n", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results in the paper are, to my knowledge, new and interesting, though I admit that I am not familiar with pseudo-games. Perhaps to aid readers like myself, I would advise the authors to include some extra intuition for people familiar with regular games but not pseudo-games. In the \"Questions\" section below, I include some questions that I had while reading the paper that would help greatly in that direction. \n\nAlong those lines, the paper generally seems a bit light on intuition. For example, the paper discusses the fact that algorithms are well known when the cumulative regret $\\psi$ is convex-concave, and then introduces Assumption 3.3. How \"far away\" is Assumption 3.3 from convex-concavity? Is the analysis in the paper a straightforward extension of known analyses for convex-concave $\\psi$, or do the weaker conditions introduce new technical problems to be resolved? If the latter, what are they?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-RsGxWrwlQF", "reviewer": "Reviewer_Xmxy", "summary": "The paper proposes methods for finding generalised Nash equilibria (GNE) for pseudo-games, which are a generalisation of classical games. They use a well known reformulation of the GNE problem as a min max problem. Then they show that a Extra-gradient method can be efficently used to find GNE in case in which the min max problem is convex-concave. Later that present a double loop gradient based algorithm to approximate the problem when the min-max reformulation is not convex concave. In this case the solution is a local Stackelberg equilibrium (stationary point of the minimal problem). They complement the theoretical analysis with an experimental evaluation", "questions": "Questions:\n1) Are the results of Section 3 straightforward once one reformulates GNE as a VI problem and can any algorithm that solves VI be used here?\n2) Is the main contribution of Section 4 the original reformulation of non-convex-non-concave pseudo games by means of the projected gradient operator? Can any algorithm that solves non-convex-non-concave min-max problem be used here?\n3) Is the introduction of min max Stackelberg equilibrium necessary to the exposition? \n\nSuggestions (minor):\n3) Introduce early on an example of a pseudo game.\n4) Define only jointly constrained pseudo-games.\n\nSee the Strengths And Weaknesses section for more detailed description of the questions.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Form the point of view of the subject of study, the paper is original as not many papers in AI study pseudo-games. However, in the reviewer opinion, the technical contributions are not clear. \nSection 3 seems straightforward as Th 5 of [57] says that any method adapt to solve Variations Inequalities can be employed to find GNE. The author should maybe clarify such point. \nSection 4 seems more interesting but, again, the reformulation in terms of a min max problem seems to let us conclude that any algorithm that finds approximate stationary points of non-convex non concave min-max games can be used here and regularised exploitability was an already existing concept. However the the reformulation used here seems more involved as it needs to find the zeros the projected gradient operator. The authors should clarify such a point as it is central to the understanding of the contribution of the paper.\n\nThe paper is in general well written and well structured. However, in the reviewer’s opinion clarity could be slighly improved. I would suggest to include in the introduction a small toy example of a pseudo-game with jointly convex constraints. \nThe “min-max Stackelberg game” paragraph does not contribuite to the exposition of the paper. It’s almost never referenced later and I would suggest it to be moved in the appendix (maybe enlarged). \nI would suggest to remove the general definition of a pseudo-game and just expose the case of joint constraint as the more general version is never actually used.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept