Convex-Concave Min-Max Stackelberg Games
Authors: Denizalp Goktas
Amy Greenwald
Venue: NeurIPS 2021 Poster (2021)
Keywords: min-max
first order methods
Stackelberg games
zero-sum games
Fisher market
equilibrium
competitive equilibrium

Abstract: Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald’s maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game.  Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.

Convex-Concave Min-Max Stackelberg Games
Denizalp Goktas Department Computer Science Brown University Providence, RI 02912 denizalp_goktassbroowe edu
Amy Greenwald
Department of Computer Science
Brown University Providence, 02912 amy_ mmy_ggrennwaaddbroww edu
Abstract
Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald's maximin model, variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min- max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.
Introduction
Min-max optimization problems have attracted great deal of attention recently because of their applicability wide range of machine learning problems. Examples settings which min-max optimization problems arise include, but are not limited to, reinforcement learning [15] generative
adversarial networks (66). fairness in machine learning [4 23 68 82 adversarial learning (72).
generative adversarial imitation learning [1] 32 and statistical learning (e.g., learning parameters of exponential families) [4]. These applications often require solving a constrained min-max optimization problem (with independent feasible sets): i.e., mingex max f(x y), where f
X x + R is continuous, and C R and Y IT are non-empty and compact.
A convex-concave constrained min-max optimization problem is one in which f is convex in æ and concave y. the special case of convex-concate objective functions, the seminal minimax theorem holds: i.e., min maXyEY fæx y) max miD f(x, y) [55]. This theorem guarantees the existence of saddle point (i.e.. a point that is simultaneously minimum and a maximum of f in the y-direction), and allows us to interpret the optimization problem as simultaneous- move, zero-sum game, where y (resp. x²") best-response of the outer (resp. inner) player to their opponent's ' strategy xx (resp. y" )) in which case saddle point is also called minimax point Nash equilibrium.
the z-direction
In this paper, we show that the computation of competitive equilibria in Fisher markets 10 central solution concept for of the most well-studied market models in algorithmic game theory 57). can be understood as a convex-concave min-max optimization problem, albeit with dependent
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

feasible sets. We define a constrained min-max optimization problem with dependent feasible sets as an optimization problem of the following form: m maXyeY:g(z..)) f(z y). where f: x + I. is continuous, X I and Y C In are non-empty and compact, and g( y) (91 (a, y) 9x y)) with gk : X x Y + R. Unfortunately, certain desirable properties of standard
min-mat max optimization problems with independent feasible sets do not carry over to the more general dependent setting. First and foremost, the minimax theorem [55] does not hold, which in turn precludes the existence of Nash equilibrium in general:
Example 1.1. Consider the following constrained min-max optimization problem with dependent x² + y + 1. The optimum is x* = 1/2, = -1/2,
feasible sets: min with value 3/4. Now, consider the same problem, with the order of the min and the max reversed: maX1 [ill= x² + + 1. The optimum is now x² = -1,,, = 1, with value 3.
Without a minimax theorem, constrained min- max optimization problems with dependent feasible sets more appropriately viewed two-player sequential, i.e., Stackelberg, games where the outer player chooses x E X before the inner player responds with their choice of y(x) E Y s.t. g(æ, y 2 0. The relevant equilibrium concept is then a Stackelberg (78 equilibrium in which the outer player optimizes their choice assuming the inner player will best-respond: i.e., optimize their choice in turn. We thus refer to constrained min-max optimization problems with dependent feasible sets as min-max Stackelberg games. In such games, the value function V X + R is defined as (az) Yag.xy:.((..))>>> y)(= fxx, y). This function represents the outer player's loss, assuming the inner player chooses a feasible best best-response, so it is the function the outer player seeks to minimize. The inner player seeks only to maximize the objective function. The first-order necessary and sufficient conditions for a tuple (x", y²) E X x Y to be a Stackelberg equilibrium in a convex- concave min- max Stackelberg game are given by the KKT stationarity conditions for the two players' optimization problems, namely minge x ((z) for the outer player. and maxyeY (m)))(m)))) f(z y) for the inner player.
In the independent strategy setting, Danskin's 's theorem states that V Vax) = V y"), where y" arg max f(x y). In other words, when there is no dependence among the players' strategy sets, the gradient of the value function coincides with that of the objective function. The first-order necessary and sufficient conditions for tuple (æ*, y to be an (interior) saddle point are for it to be a stationary point of f (i.c., V=j(=", y²) )²) players in the anlependentssimuttaeoussn move move setting to follow the gradient of the objective function. In the dependent/sequential setting, however, the direction of steepest descent (resp. ascent) for the outer (resp. inner) player is the gradient of their value function.
V fx" (x",y") =
0). It is therefore logical for
Example 1.2. Consider, once again, the problem posed in Example and recall Jin, Netrapalli, and Jordan's 's gradient descent with max- maxx-raace algorithm 141]: x (((() Vf (x', y (x).))),
where y" (z) E arg max "g("())))))))))))"")))) {xx(t, y) for 1 > O. Applied to this sample problem, with n- = 1, this algorithm yields the following update rule: (+++)) = x²)) (x(()) = (1))) Thus, leting (0))) equal any feasible x, the output cycles between x and -x, so that the average of the iterates converges to x² 0 (with y² 0), which is not Stackelberg equilibrium, as the Stackelberg
equilibrium of this game is x= = 1/2. 3 = 11/2.
Now consider an algorithm that updates based not on gradient of the objective function, but
of the value function, namely (t+11) = (1)
n V V (a'). The value function is V(x))
max +y50 x² +y+1+ +++ x² x with gradient V'(2) = 2x - 1. Thus, when 17 1, this
algorithm yields the following update rule: 1(++1) z(1) (z( (+) 2z((() +1 (()) (1) + 1.
If we run this algorithm from initial point (0) 1/8, we get = -1/-t1-111-- x(2) =T/8+11- =
iss and so on. The average of the iterates l/s, 7/s, 1/8.... converges to x² = (1/s/ 7/8) = =122,
and correspondingly y" = -1/2, which is indeed the Stackelberg equilibrium.
AAthoough notationally similar, we note that this model is more general than that of Daskalakis. Skoulakis, and Zampetakis [8]. The authors state that under the assumptions of the minimax theorem 55 Nash
equilibrium is guaranteed exist in their model. When there is dependence among the players' feasible sets. however, this claim does not hold (see Example [.]].
'n constrained convex-conean of Nash and Stackelberg equilibria coincide. They also coincide in the dependent setting, when Nash equilibria exist, but they do not coincide in general, since Nash equilibria need not exist.
min- max optimization problems with independent feasible sets, the notions
Note that this use of the term value function in economics distinct from its use in reinforcement learning.
2

---

In this paper, we introduce two first-order (subgradient) methods that solve min-mas Stackelberg games- to our knowledge the first such methods. Our approach relies on new generalization of series of fundamental results in mathematical economics known envelope theorems [1 50). Envelope theorems generalize aspects of Danskin's is theorem, by providing explicit formulas for the gradient of the value function in dependent strategy settings, when a derivative is guaranteed to exist. To sidestep the differentiability issue, we introduce a generalized envelope theorem that gives an explicit formula for the subdifferential of the value function in dependent strategy settings.
assuming access to max-oracle that returns y E arg maxye yeY (otpee--gi..aii gg)0 faz y), given I E X. Hence, our first algorithm solves only for an optimal x", while our second algorithm explicitly solves for both x and y". We show that both algorithms converge in polynomial time Stackelberg equilibrium of any convex-concave min-max Stackelberg game with nonempty, compact and convex dependent strategy sets. In Table [] we summarize the iteration complexities of our algorithms, i.c., the number of iterations required to achieve an e-approximate equilibrium, where e is the desired precision.
Our first algorithm follows Jin, Netrapalli, and Jordan
Table I: Iteration complexities of Algorithms D and My are strong convexity/concavin parameters.
for min-max Stackelberg games. Here, Ue and
Iteration Complexity
Properties of f
Algorithm
Algorithm
2
Me www.SrongyyCConeevysySSoonyyyyyn
Ö(E-))
0 (
He StronglyyCCnnve--Conawe
0
Conveer,,,-StooggyyyCoone
Ö(E-2)
O (
Convex-Concave
O
Finally, we apply our results to the computation of competitive equilibria in Fisher markets. In this context, our method for solving min-max Stackelberg game reduces solving the market in a decentralized manner using natural market dynamic called tâtonnement [80]. We demonstrate the efficacy and efficiency of our algorithms in practice by running a series of experiments in which we compute competitive equilibria in Fisher markets with varying utility structures saaucturrss-pecfficccae specificallyy linear, Cobb-Douglas, and Leontief. Although our theoretical results do not apply to all these Fisher markets Leontief utilities, in particular, are not differentiable tâtonnement converges in all our experiments. That said, the rate of convergence does seem to depend on the smoothness characteristics of the utility structures; we observe slower convergence for Leontief utilities, and faster convergence than our theory predicts for Cobb-Douglas utilities, which are not only differentiable, but whose value function is also differentiable.
Related Work Our model of min-max Stackelberg games seems have first been studied by Wald, under the posthumous name of Wald's maximin model (79]. A variant of Wald's maximin model is the main paradigm used in robust optimization, fundamental framework in operations research for which many methods have been proposed 6 56 61]. Shimizu and Aiyoshi (70 71 proposed the constrained optimization problem with infinitely many constraints, which nonetheless seems to perform well in practice. More recently, Segundo, Krohling, and Cosme (69) proposed an evolutionary algorithm for these games, but they provided no guarantees. As pointed out by Postek and Shtern, all prior methods either require oracles and are stochastic in nature (6], or rely on a binary search for the optimal value, which can be computationally complex (56). The algorithms we propose in this paper circumvent the aforementioned issues and can be used to solve a large class of convex robust optimization problems in simple and efficient manner.
first algorithm to solve min-max Stackelberg games via a relaxation
Extensive- games in which players' strategy sets can depend on other players' actions have been studied by Davis, Waugh, and Bowling [19] assuming payoffs are bilinear, and by Farina, Kroer, and
Sandholm (28) for another specific class of convex-concave payoffs. Fabiani et al. [25 and Kebriaei
and lannelli [43 study more general settings than ours, namely non-zero-sum Stackelberg games
with more than two players. Both sets of authors derive convergence guarantees assuming specific payoff structures, but their algorithms do not converge in polynomial time.
3

---

Min-max Stackelberg games naturally model various economic settings. They are related to the abstract economies first studied by Arrow and Debreu 4 however, the solution concept that has been the focus of this literature is generalized Nash equilibrium 26 27 which, like Stackelberg, is weaker solution concept than Nash, but which makes the arguably unreasonable assumption that the players move simultaneously and nonetheless satisfy the constraint dependencies on their strategies imposed by one another's s moves. See Appendix A for a more detailed discussion of generalized Nash equilibria versus Stackelberg equilibria.
Duetting et al. 22 study optimal auction design problems. They propose a neural network architec- ture called RegretNet that represents optimal auctions, and train their networks using Algorithm B.4 Optimal auction design problems can be seen as min-max Stackelberg games; however, as their objectives are non-convex-coneatt in general. our guarantees do not apply.
In this paper, observe that solving for the competitive equilibrium of a Fisher market can also be seen as solving a (convex-concave) min-max Stackelberg game. The study of the computation
of competitive equilibria in Fisher markets was initiated by Devanur et al. [20], who provided
polynomial-time method for the case of linear utilities. Jain, Vazirani, and Ye [40] subsequently
showed that large class of Fisher markets could be solved in polynomial-time using interior point
methods. Recently, Gao and Kroer [29] studied an alternative family of first-order methods for solving Fisher markets (only; not min- max Stackelberg games more generally), assuming linear, quasilinear, and Leontief utilities, as such methods can be more efficient when markets are large.
See Appendix G for detailed discussion of recent progress on solving min-max Stackelherg games,
both in the convex-concave case and the non-convex-concaee case.
2 Preliminaries
Notation We use Roman uppercase letters to denote sets (e.g., X), bold uppercase letters denote matrices (e.g.. X), bold lowercase letters to denote vectors (e.g., p). and Roman lowercase letters to denote scalar quantities, (c.g., c). We denote the ith row vector of matrix (e.g., X) by the corresponding bold lowercase letter with subscript (e.g., æ;). Similarly, we denote the jth entry of a vector (e.g.. p or x;)) by the corresponding Roman lowercase letter with subscript j (e.g., Pj or Ttz).. We denote the set of integers {I..... n. by [n]. the set of natural numbers by N, the set of real numbers by I. the set of non-negative real numbers by RT. We denote by Ily the Euclidean projection operator onto the set Y C Rm: i.e., (y) = arg mingey |yy 2||2-
A min-max Stackelherg game, denoted (,))J is two-player, zero-sum game, where one player, who we call the æ-player (resp. the y-player), is trying to minimize their loss (resp. maximize their gain), defined by continuous objective function f X Y + R. by choosing strategy from a compact strategy set X C I2" (resp. Y C R"),, and s.t. g y) 2 O where g(x, y)
(g1 (x, y).... ......... 9K (x. y)) with 9k X x Y +E R. A strategy profile (x. y) E X x Y is said to be feasible iff for all E K], 9h (z. y) 2 O. The function ff maps a pair of feasible strategies taken by the players (æ, y) E X x Y to real value (i.e., payoff), which represents the loss (resp. the gain) of the æ-player (resp. y-player). A min-max game is said to be convex-concave the objective function f is convex-concave.
The relevant solution concept for Stackelberg games is the Stackelberg equilibrium:
Definition 2.1 (Stackelberg Equilibrium). Consider the min-max Stackelberg game (X, Y. f.f). strategy profile (x", y²) E X x Y such that g(x","" 2 0 is a (s, (ttac--ttcellberg equilibrium if maxyey .2)2 f (x" 3) 8 < (x", mingex max (m))))000 f (xx 8) +
Intuitively, (e, 8) Stackelbbegg equilibrium payoff is no more than ε (resp. ò) away from its optimum. By Proposition B.2 (0, O)-Stackelberg equilibrium is guaranteed exist in min-max Stackelberg. its value is unique, and by Proposition B.3 the set of Stackelberg equilibria is compact and convex.
point which the x-player's (resp. y-player's)
Finally, we define several concepts that needed in our convergence proofs. Given A R. the function f + IR is said to be E j-LLipcchitz-coniimoon
iff Yz1, x22 E X, [[ - f(x2) < then refer to as - Loshhhttttssoo A function f A + R is j-sttrongly convex if f(x)) 2 f(z)) +
Ey ||: 222 If the gradient of f. f. is & -iipschhhizzzonntinne
(V (x2), 21 x22) + 1/2 || 21 21, and p-strongly concave if -f p-strongly convex.

---

3 First-Order Methods via an Envelope Theorem
The envelope theorems, popular tools in mathematical economics, allow for explicit formulas for the gradient of the value function in min-max games, even when the strategy sets are dependent. Afriat I appears to have been the first make use of the Lagrangian to differentiate the value function, though his conclusion was later obtained under weaker assumptions by Milgrom and Segal [50]. Our envelope theorem relies on the following assumptions:
Assumption 3.1. 1. f, f.91....,9h are continuous and convex-concave: 2. Vaf. Val... V are continuous; and 3. (Slater's condition) Væ X, Jÿ E Y s.t. 9u (zx ÿ) > O. for all k I,...,k. K.
Milgrom and Segal's ' [50 envelope theorem provides an explicit formula for the gradient of the value function. When strategy sets independent, under mild assumptions, this function is guaranteed to be differentiable (58) When strategy sets are dependent, however, it is not necessarily differentiable, seen in Example differentiable value functions:
As a remedy, we present a subdifferential envelope theorem for non-
Theorem 3.2 (Subdifferential Envelope Theorem). Consider the value function V(x) maxyeY (a a2200)2 I (xx y). Ler Ler) = arg max yeY g( fxx y) and suppose Assumption 3.1 holds. Then, at any point E E X, 0g (Z)
K
conv U
U N" (T) (e) (B)EM
Vas v
+
(1 (z) ae (2, (a))
(1)
where conv is the convex hull operator and X (क. y (x)) (2, y (i))...... X (2, y (x)))
e
A A² (ā)) are the optimal KKT multipliers associated with y (z) E (ū).
The envelope theorem states that the gradient of a differentiable value function is the gradient of the Lagrangian evaluated at the optimal solution. Generalizing this fact, subdifferential envelope theorem states that every subgradient of the value function, V(x) maxyeY :().))))) f(, y) is a convex combination of the values of the gradient of the Lagrangian evaluated at the optimal solutions (x)), X (xx y" (z))) E (xr) x A (ax, y (x)).
With our envelope theorem in hand, we now ready to present two mendient-descen//ssseetty algorithms for min-max Stackelberg games, which follow the gradient of the value function.
Our first algorithm, max-oracle gradient-descent, following Jin, Netrapalli, and Jordan 41 as- sumes access mox-oracle, which given x E X, returns 6-maximum of the inner player's value function. That is, for all x E X, the max-oracle returns ğ E Y s.t. g(x, 9) 2 0 and f(x y) - 5. then runs (sub)gradient descent on the outer player's
(xx 4) 2 maxyey value function, using Theorem 3.2 to compute the requisite subgradients. Inspired by the multi- step gradient-descent algorithm of Nouiehed et al. (58). our second algorithm, nested gradient- descent/ascent (see Appendix + computes both x." and y² explicitly, without oracle access. We simply replace the max-oracle in our max-oracle wradient-descen algorithm by a projected gradient- ascent procedure, which again computes a 6-maximum of the inner player's value function.
Once ① is found at iteration L, one can compute optimal KKT multipliers (x(((()) ())),
Xig (x) ((x(1)) for the outer player's value function, either via a system of linear equations using the complementary slackness conditions and the value of the objective function at the opti- mal, namely (z))), ÿ (x)))) or by running gradient descent the Lagrangian for the dual vari- ables. Additionally, most algorithms solving convex programs will return X (*( ((x(t))
(x((1), (z) ................... (x) (()())) together with the optimal (x)())) without incurring any additional computational expense. As a result, we assume that the optimal KKT multipliers A (x)((), ())) associated with a solution ())( can be computed constant time.
Having explained our two procedures, our next task is to derive their convergence rates. It turns out that under very mild assumptions, i.e., when Assumption 3.1 holds, the outer player's value function is Lipschitz continuous in æ. More precisely. the objective function f is É Lipischhitzz in æ, where As f is Li-ischhitzz continuous in æ, the value function is
l, = m xxX x V (ā f
'This max norm is well-defined since Va f is continuous and the constraint set non-empty and compact.
5

---

Algorithm Max-Oracle Gradient Descent
Inputs:
9, a())))
Output:
(x" (3")"")
for mort=1..... T do
Find ((-i)) E Y s.t. f(x((-1), (((-1)) 2 V(x(1-1)) - (x(11)))) y 2
2:
3:
Set (t X (z(((1)) (1(1-11
4: Set se) = 1xx (x(1-1) - 110 Val(aoll (2(((-(), + Σボ= \/2 ((-1) Valn ,00,))),,(1))) y
5: end for
6: Find y EY s.t. ((x(T)y(()) 2 v(x - 8 & g(x ,y( 20
7: return (el,)
also LLiisschitz This fact suggests that an (e,ee)-Stckelberr equilibrium should be computable in O( 2) iterations by our max-oracle gradient descent algorithm (Algorithm) Dp. since our method is a subgradient method.
Theorem 3.3. Consider a convex-concave min-max Stackelberg game, (X,Y,f.9) where X is convex, and (x*, "y" ) (0, 8)-ttackelberrg equilibrium, and suppose Assumption 3.1 holds. Algorithm is run for iterations, with step sizes ni s.t. Σ Th S 00, Ek= T/g cc. and (e)
if hestt D best.) arg (w (00)))))) -0kt):kkl(] (xx(k) yy (k)), it holds that lim la Best) f(x", yy"). Furthermore, for a EE (0, 1), if we choose T 2 Nr(e) E O(E-2), then there exists an iteration T <T T s.t. (2") (I")) is ( Stackelberg equilibrium.
As is expected, the O( iteration complexity can be improved to O(s-1), if additionally, f is strongly convex in æ. (See Appendix E Theorem E22
Combining the convergence results for
max-oracle gradient descent algorithm with convergence results for gradient descent [8]
obtain the following convergence rates for the nested gradient descent-ascees algorithm (Algorithm 2 Appendix E. We include the formal proof and statement for the case when Assumption 3.1 holds and f is Lipschitz-snin smooth in Appendix (Theorem
The other results follow similarly.
Theorem 3.4. Consider convex-concate min-max Stackelberg game, X.Y.f.g) with X and Y convex. Suppose that Assumption 3.7 holds. Then, under standard assumptions on the step sizes, the iteration complexities given below hold for the computation of a
( Stackk-eac equilibrium:
f is l9 ssmooth
f is f-moothh
+ f Strongly Concave in
Assumption 3.1
0 ((=-2)
0 (e "oog(e
Assumption 3.1 f Strongly Convex in
0( log[o=
Since the value function in the convex-concave dependent setting is guaranteed to be differentiable (see Example C.2). we cannot ensure that the objective function is Lipschitz-smooth in general. Thus, unlike previous results for the independent setting that required this latter assumption to achieve faster convergence (e.g., (58). in our analysis of Algorithm [ we assume only that the objective function is continuously differentiable, which leads more widely applicable, albeit slower, convergence rate. Note, however, that we assume Lipschitt-smmootnnes in our analysis of Algorithm 2 as it allows for faster convergence to the inner player's optimal strategy, but this assumption could also be done away with again, at the cost of slower convergence rate.
4 An Economic Application: Fisher Markets
The Fisher market model, attributed to Irving Fisher (10), has received a great deal of attention recently, in particular by computer scientists, as its applications to fair division and mechanism design have proven useful for the design of automated markets in many online marketplaces. this section, we argue that a competitive equilibrium in Fisher markets can be understood a Stackelberg
A formal statement of this claim can be found in Appendix
E (Lemma E.I

---

equilibrium of a coweeve min-max Stackelberg game. We then apply our first-order methods to compute these equilibria in various Fisher markets.
Fisher market consists of n buyers and m. divisible goods 10 Each buyer E [n]] has a budget b, E 4R, and utility function uq -RT R. As is standard in the literature, we assume that there is one divisible unit of each good in the market (57). An instance of a Fisher market is given by tuple
(ni, m, U, b), where U {ui,..., ..,, J vector of buyer budgets. We abbreviate as (U, b) when and m are clear from context.
is set of utility functions, one per buyer, and R is the
An allocation X = (a1,...,
E R is map from goods to buyers, represented as matrix, s.t. Faj 2 denotes the amount of good j E [m] allocated buyer i [n]]. Goods are assigned prices (Pi,...,PPo .P....,Pm)) Pmm) E IRT. A tuple .*) is said to be competitive (or Walrasian) equilibrium of Fisher market (U,b) if 1. buyers are utility maximizing, constrained by their budget, i.c. Vi E [n], x E arg max Lb, (.(x;; and 2. the market clears, i.c., Vj E [m]. P3 > 0 + Eieno Fig and pj = 0 + Iien Fij I 1.
ITn) ,t.)
We now formulate the problem of computing competitive equilibrium , of a Fisher market (U, b), where U is a set of continuous, concave, and homogeneous utility functions, as a convex- concave min-max Stackelberg game, perspective which has not been taken before. Fisher markets
can by solved via the Eisenberg-Gain Gale convex program [24]. Recently, Cole and Tao [13] derived a
convex program, which is intimately related to the dual of the Eisenberg-Gale program
[1], namely
min Σ P20
Pj +
Σ by log iE(m)
max u; ui(ax:)
2:2002.
JE[m]
Rearranging, we obtain the following convex-concave min-max Stackelberg game:
min
max
Σ P jELm]
Σ by log (u:(2::) iE|m]
(3)
P20
This min-m max game is played by fictitious (Walrasian) auctioneer and a set of buyers, who effectively play as team. The objective function in this game is then the sum of the auctioneer's welfare (i.e.,
the sum of the prices) and the Nash social welfare of buyers (i.e., the second summation). As the buyer's strategy set is dependent on the price vector p selected by the auctioneer, cannot existing first-order methods to solve this problem. However, we can use Algorithms and
Starting from Equation maxx20:XX0 Ejemm Pj +
3
define the auctioneer's value function V(p)
Lijn by log (w, and buyer i's demand set X: b) =
arg m0:...00..ps. 20:0.ppb (x(x))
Theorem 3.2 then provides the relevant subgradients so D and 2 namely V, = 1m - >iejn)) (p, and [a(,;, V w. (x,), using the Minkowski sum to add set-valued quantities, where 1mm is the vector of ones of size m
that we can run Algorithms
Ve, [Ee(m) Py + Eve log (v,()))
Cheung, Cole, and Devanur 12 observed that solving the dual of the Fisenberg-Gale program (Equation 2 via (sub)gradient descent [20] is equivalent solving for a competitive equilib- rium in a Fisher market using an auction-like economic price adjustment process named tâton- nement that was first proposed by Léon Walras in the 1870s [80). The tâtonnement process increases the prices of goods that are overdemanded and decreases the prices of goods that are underdemanded. Mathematically, the (vanilla) tâtonnement process (5) 80 is defined as
p(t) max {p(t - 11) + 7) (Zre(n) 2t (p(t), b) - -1). .0) for p(0) E RT, where x; (p(t), 6:) e X; (p((), 6.) = arg max (tt us (2x)) is the demand set of buyer i. The max-oracle algo- rithm applied to Equation (3) is then equivalent to a tâtonnemement process where the buyers report 8-utility maximizing demand. Further, we have the following corollary of Theorem 3.3
Corollary 4.1. Let (U, b) be a Fisher market with equilibrium price vector p', where U is a set of continuous, concave, homogeneous, and continuously differentiable utility functions. Consider
function f : R + said to be homogeneous of degree k Vf E. X > 0, f(xx) X f(x).
Unless otherwise indicated, a homogeneous function is assumed to be homogeneous of degree 1.
We include detailed descriptions of the algorithms applied to Fisher markets in Appendix
7

---

the entropic tâtonnement process 131 Assume that the step sizes nr satisfy the usual conditions: Ek nh I oo and Σk= 122 = 3c. If Poest E arg aargmnptwsssuu V(p then lim V(Pbest = V(p'). Additionally, lâtonnement converges to an e-competitive equilibrium in O) iterations.
If we also apply the nested mudiient-desent-aae algorithm that is arguably more descriptive of market dynamics than tâtonnement itself, as it also includes the demand-side market dynamics of buyers optimizing their demands, potentially in decentralized manner. The nested tâtonnement algorithm essentially describes a two-step trial-and- error (i.e., tâtonnement) process, where first the buyers try to discover their optimal demand by increasing their demand for goods in proportion to the marginal utility the goods provide, and then the seller/auctioneer adjusts market prices by decreasing the prices of goods that underdemanded and increasing the prices of goods that are overdemanded. As buyers can calculate their demands in a decentralized fashion, the nested tâtonnement algorithm offers a more complete picture of market dynamics then the classic tâtonnement process.
algorithm to Equation
arrive at an
Experiments In order to better understand, the iteration complexity of Algorithms and 2 (Ap- pendix E) we ran a series of experiments on Fisher markets with three different classes of utility functions Each utility structure endows Equation (3) with different smoothness properties, which allows us to compare the efficiency of the algorithms under varying conditions.
Let U2 E R.Th be a vector of parameters for the utility function of buyer E [ni]. We have the following utility function classes: Linear: u, (2,))) ΣjE(m VijWajj Cobb-Douglas: u,(x;) = [I "G
[mi Leontief: (x,)), minje[m] { May f Equation (3) satisfies the smoothness properties listed in
Table U is one of these three classes. Our goals are two-fold. First, we want to understand (which, when applied Equation + give rise to Algorithms and in Appendix E respectively) compare to their theoretical guarantees under different utility structures. Second, we want to understand the extent to which the convergence rates of these two algorithms differ in practice. We include a more detailed description of our experimental setup in Appendix
how the empirical convergence rates of Algorithms and 2
Table 2: Smoothness properties satisfied by Equation 3 assuming different utility functions. Note that Assumption B.1 does not hold for Leontief utilities, because they are not differentiable.
V is differentiable
Assumption
3. holds
Linear
Cobb-Douglas
Leontief
Figure describes the empirical convergence rates of Algorithms 1 and for linear, Cobb-Douglas, and Leontief utilities. We observe that convergence is fastest in Fisher markets with Cobb-Douglas utilities, followed by linear, and then Leontief. We seem to obtain a tight convergence rate of O for linear utilities, which seems plausible, as the value function is not differentiable assuming linear utilities, and hence we are unlikely achieve better convergence rate. On the other hand, for Cobb-Doughe utilities, both the value and the objective function are differentiable; in fact, they are both twice continuously differentiable, making them both Lipschitz-smonn smooth. These factors combined seem to provide much faster convergence rate than O(1/TT).
Fisher markets with Leontief utilities, in which the objective function is not differentiable, the hardest markets of the three for our algorithms to solve. Indeed, our theory does not even predict convergence. Still, convergence is not entirely surprising, as Cheung, Cole, and Devanur [12] have shown that buyer demand throughout tâtonnement is bounded for Leontief utilities, which means that the objective function of Equation ( is locally Lipschitz: i.c., any subgradient computed by the algorithm will be bounded. Overall, our theory suggests that diffcrentiaaility of the value function is not essential to guarantee convergence of first-order methods in concave games, while our
$ 'The entropic tâtonnement process ensures that prices remain bounded away from zero so that excess demand is likewise bounded and Assumption 3.1 is satisfied.
Our code can be found at attpst::///// /ttp//ggtttaaatt con/ www.////wniiaaa/iin.o.e

---

Linear Market
Cobb- Soubllss Market
Leontief Market
Objective Value
Linear Market
Cobb-Douglas Market
Leontief Market
Objective Value
200 400
200
200 400
Iteration Number
Iteration Number
Iteration Number
Figure 1: The first row describes the average trajectory of the value of the objective function for randomly initialized market on each iteration of both Algorithm (in blue) and Algorithm (in orange) when the starting prices high, while the second row describes the average trajectory of the objective function when starting prices are low for linear, Cobb- Sobb-Douglas, and Leontief Fisher markets respectively. The dashed red line represents convergence rate of O(/vT), which corresponds to an iteration complexity of ((12).
experiments seem to suggest that differentiability of the objective function is more important than differentiability of the value function in regards to the convergence rate.
In order investigate whether the outputs of Algorithm I which uses exact max-oracle (i.e.,
O-max-oracle) are more precise than those of Algorithm 2 we solved 500 randomly initialized markets with both algorithms. We then algorithms to see their difference was statistically significant. Our calculations produced p-values of 0.69, and 1.06 10-18, for Fisher markets with linear, Cobb-Douglas, and Leontief utilities, respectively. At a significance level of 0.05, these results are not statistically significant for linear utilities only. This result be attributed to the fact that the value function is not differentiable in the linear case, which makes the nested gradient descent/ascent algorithm less precise.
James' first-order test ( 36 the mean output of both
5 Conclusion
In this paper, we proposed two first-order methods to solve a class of constrained convex-concane min-max optimization problems, which we call min-max Stackelberg games. As such games do afford Nash equilibria general, we focused on the computation of their Stackelberg equilibria. To solve for Stackelberg equilibria, introduced novel subdifferential envelope theorem, which formed the heart of two subgradient methods with polynomial-tin to Stackelberg equilibria. Finally, applied our theory to the computation of competitive equilibria in Fisher markets. This application yielded a new variant of the classic tâtonnement process, where, in addition to the auctioneer iteratively adjusting prices, the buyers iteratively compute their demands. A further question of interest both for Fisher market dynamics and convex- concceve max Stackelberg games more generally is whether cradient-descent-asee ascent (GDA) converges in the dependent strategy set setting as does the independent strategy setting (45). GDA dynamics for Fisher markets
iteration complexity that converge
correspond myopic best-response dynamics (see, for example, 5 ) We would expect such result to be of computational as well as economic interest.
Acknowledgments and Disclosure of Funding
We would like thank Dustin Morrill for his feedback on an early draft of this paper. This work was partially supported by NSF Grant CMMI-1761546.

---

References
[1] S. N. Afriat. "Theory of Maxima and the Method of Lagrange". In: SIAM Journal on Applied Mathematics 20.3 (1971), pp. 343-357. ISSN: 00361399, URL: http::/www.
org/
s stable/2099955
[2] James Algina, T. C. Oshima, and Wen- Ying Lin. "Type I Error Rates for Welch's Test and James's Second-Order Test under Nonnormality and Inequality of Variance When There are Two Groups". . In: Journal of Educational and Behavioral Statistics 19.3 (1994), pp. 275-291. ISSN: 10769986, 19351054. CRL: http::tttt//tt..... www. istor. org. 2ator..rgg/staale/112222
[3] Mohammad Alkousa et al. Accelerated methods for composite non-bilinear saddle point
problem. 2020. arXiv: 1906. 03620 [math. [C]
[4] Kenneth Arrow and Gerard Debreu. "Existence of an equilibrium for a competitive economy".
In: Econometrica: Journal of the Econometric Society (1954), pp. 265-290.
[5]
Kenneth J. Arrow and Leonid Hurwicz. "On the Stability of the Competitive Equilibrium,
In: Econometrica 26.4 (1958), pp. 522-552. ISSN: 00129682, 14680262. URL.: http
77 /ww. jstor. org/ eestable/ie 907515
[6]
Aharon Ben-Tal et al. "Oracle- robust optimization via online learning". In: Operations
Research 63.3 (2015), pp. 238.638.
[7] Claude Berge. Topological Spaces: including treatment of multi-valued functions, vector spaces, and convexity. Courier Corporation, 1997.
[8] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[9] Stephen Boyd and Lieven Vandenberghe. Subgradients. Apr. 2018.
[10] William C Brainard, Herbert E Scarf, et al. How compute equilibrium prices in 1891. Citeseer, 2000.
[11] Qi Cai al. On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator. 2019. arxiv: 1901.03674 [cs LG]
[12] Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. "Tatonnement beyond Gross Sub- stitutes? Gradient Descent to the Rescue". In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. STOC '13. Palo Alto, California, USA: Association
for Computing Machinery, 2013. pp. 100.200. ISBN: 9781450320290. DOr: 10 1145/ 2488633
2488508 2438633 URL: https: / doi
[13] Richard Cole and Yixin Tao. Balancing the Robustness and Convergence of Tatonnement. 2019. arxiv: 1908. 00844 [os [GT]
[14] Bo Dai et al. "Kernel Exponential Family Estimation via Doubly Dual Embedding". In: Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. Ed. by Kamalika Chaudhuri and Masashi Sugiyama. Vol. 89. Proceedings Machine
Learning Research. PMLR, Apr. 2019, pp. 2321-2330. URL: pttp:://procceeenggss mlr
(oess/v89/dal.1
[15] Bo Dai et al. "SBEED: Convergent Reinforcement Learning with Nonlinear Function Approx- imation" " In: Proceedings of the 35th International Conference on Machine Learning. Ed. by Jennifer Dy and Andreas Krause. Vol. 80. Proceedings of Machine Learning Research. PMLR, July 2018, pp. 1125-1134, html
mlr wttppp/ssssssssseeeeeee URL: http::://.occeeaaiaiaaaa http://ccceeeaonoooooooeeeeeee//
[16] Yu-Hong Dai and Liwei Zhang. Optimality Conditions for Constrained Minimax Optimization. 2020. arXiv: 2 004 70730 [math.oc]
[17] John M. Danskin. "The Theory of Max-Min, with Applications" " In: SIAM Journal on Applied Mathematics 14.4 (1966), pp. 641-664. Stable/2946122
ISSN: 00361399. URL.: http::/ /www www.jstor.org
[18] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The Complexity of Constrained Min-Max Optimization. 2020. arXiv: 2009. 09623 [cs. [cs.CC]
[19] Trevor Davis, Kevin Waugh, and Michael Bowling Solving Large Extensive-Fon Games with Strategy Constraints. 2019. arXiv: [809. 07893 [cs. CT]
[20] N. R. Devanur et al. "Market equilibrium via a -ramal-dual-type algorithm". In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002, pp. 389-395. DOI: 10. 15.1109/SFCS 2002 210....9932221119933
10

---

[21] Steven Diamond and Stephen Boyd. "CVXPY: A Python-embedder embedded modeling language for convex optimization". In: Journal of Machine Learning Research 17.83 (2016). pp. 1-5.
[22] Paul Duetting et al. "Optimal auctions through deep learning". In: International Conference Machine Learning. PMLR. 2019, pp. 1706-1715.
[23] Harrison Edwards and Amos Storkey. Censoring Representations with an Adversary. 2016.
arXiv:
[24] Edmund Eisenberg and David Gale. "Consensus of subjective probabilities: The pari-mutuel method". In: The Annals of Mathematical Statistics 30.1 (1959), pp. 165-168.
[25] Filippo Fabiani et al. "Local Stackelberg equilibrium seeking in generalized aggregative games". In: IEEE Transactions on Automatic Control (2021).
[26] Francisco Facchinei and Christian Kanzow, "Generalized Nash equilibrium problems". In: 40r
5.3 (2007). pp. 173-210.
[27] Francisco Facchinei and Christian Kanzow. "Generalized Nash equilibrium problems". In:
Annals of Operations Research 175.1 (2010), pp. 177-211.
[28] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret Circuits: Composability of Regret Minimizers. 2019. Xrvi:: [ 02540 [cs. . [G]]]]
[29] Yuan Gao and Christian Kroer. "First-Order Methods for Large-Scale Market Equilibrium Com- putation". In: Advances in Neurul Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 12, 2020, virtual. Ed.
by Hugo Larochelle et al. 2020. URL: httpt::::pppocceedd.e ngs. nwwrinuuppp...m ccc wccpppppr/
[30] Gauthier Gidel et al. A Variational Inequality Perspective on Generative Adversarial Networks.
2020. arXiv: 1 1802. 10551 ccs LG]
[31] Denizalp Goktas, Enrique Areyan Viqueira, and Amy Greenwald. "A Consumer-Theoretis Characterization of Fisher Market Equilibria". In: Proceedings of the Conference on Web and Internet Economics, ( (WINE). 2021.
[32] E. Yazdandoost Hamedani et al. Iteration Complexity of Randomized Primal- Methods for Convex- Conreve- Saddle Point Problems. 2018. arXiv: 1806. 04118 [math. [C]
[33] Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. "A primal-dual algorithm for general convex-concave saddle point problems". In: arXiv preprint arXiv: 01401 2 (2018). [34] Charles R. Harris et al. "Array programming with NumPy". In: Nature 585 (2020), pp. 357-
362. DO1: [0. 10 s 41 586- 020-00002220000 2649-2
[35] R Henrion. "On constraint qualifications". In: Journal of optimization theory and applications
72.1 (1992), pp. 187-197.
[36] Freddy Hernandez et stests: Package with useful statistical tests. R package version 0.1.0.
2021. URL.: http:: htt///eraana rnanb. gig.titthhh. i wt/oo///esss ststtt
[37] J. D. Hunter. "Matplotlib: A 2D graphics environment". In: Computing in Science & Engineer-
ing 9.3 (2007), pp. 90-95. Do1: 11..1.11/MM..... 2007.52
[38] Adam Ibrahim et al. "Lower bounds and conditioning of differentiable games". In: arXiv preprint arXiv: 07300 (2019).
[39] Tatsuro Ichiishi. "4- - Noncooperative Behavior and Equilibrium". In: Game Theory for Eco- nomic Analysis. Ed. by Tatsuro Ichiishi. Economic Theory, Econometrics, and Mathemat- ical Economics. San Diego: Academic Press, 1983 pp. 55-76. ISBN: 978-0-12-370188 0. DOI: https : doi org / 10. 1016 / B978 0 12 370180 0 50009
3
URL: https : : www. sciencedirect com/ / science article pii
B978012 2 701 800500093
[40]
Kamal Jain, Vijay V Vazirani, and Yinyu Ye. "Market equilibria for homothetic, quasi-concave utilities and economies of scale in production". In: SODA. Vol. 5. 2005, pp. 63-71.
[41] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What is Local Optimality in Nonconvex- Nonconcave Minimax Optimizution? 2020. arXiv: 1 1902. 00618 [cs LG]
[42] 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.
[43] Hamed Kebriaci and Luigi lannelli. "Discrete-tine robust hierarchical linear-quadratie dynamic games". In: IEEE Transactions on Automatic Control 63.3 (2017). pp. 902-909.

---

[44]
HW Kuhn and AW Tucker. Proceedings of 2nd berkeley symposium. 1951.
[45]
Tianyi Lin, Chi Jin, and Michael Jordan. "On gradient descent ascent for nonconvex-coneave minimax problems". In: International Conference on Machine Learning. PMLR. 2020, pp. 6083-6093
[46]
Tianyi Lin, Chi Jin, and Michael Jordan. "Near-optimal algorithms for minimax optimization". In: Conference on Learning Theory. PMLR. 2020, pp. 2738-2779
[47] Songtao Lu, Ioannis Tsaknakis, and Mingyi Hong. "Block alternating optimization for non- convex min-max problems: algorithms and applications in signal processing and communi- cations". In: ICASSP 2019-2013 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2019, pp.
[48]
David Madras et al. Learning Adversarially Fair and Transferable Representations. 2018.
arXiv: I802.06309 cs LG]
[49] Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic Theory. OUP Catalogue 9780195102680 Oxford University Press, 1995. ISBN: ARRAY(0X4 URL:
https://ideas: repec org/brrgg//oo // http//books/// 9780/77811999 100191100 95102680..
[50] Paul Milgrom and Ilya Segal. "Envelope theorems for arbitrary choice sets". In: Econometrica
70.2 (2002). pp. 583-601.
[51] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence Rate of O(1/k) for Optimistic Gradient and Extra-gradier Methods in Smooth Convex-Concave Saddle Point Problems. 2020. arviv: 1906. 01115 [math.OC]
[52] Dov Monderer and Lloyd S Shapley. "Potential games". In: Games and economic behavior 14.1 (1996), pp. 124-143.
[53] Arkadi Nemirovski. "Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems". In: SIAM Journal on Optimization 15.1 (2004), pp. 229-251..
[54] Yurii Nesterov. "Dual extrapolation and its applications to solving variational inequalities and related problems". In: Mathematical Programming 109.2 (2007), pp. 319-344.
[55] J v Neumann. "Zur theorie der gesellschafttspielee" In: Mathematische annalen 100.1 (1928),
pp. 295-320.
[56] Nam Ho-Nguyen and Fatma Kiline-Karzan. "Online first-order framework for robust convex optimization". In: Operations Research 66.6 (2018), pp. 1670-1692.
[57] Noam Nissan and Tim Roughgarden. Algorithmic Game Theory. Cambridge University Press,
2007. DOI: 10. 111.1111//C//0000 11TT///89901111000000 100000
[58] Maher Nouiehed al. "Solving a class of non-convex min-max games using iterative first order methods". In: arXiv preprini arXiv: 1 /902.08297 (2019).
[59] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. "Efficient search of first- smooth min-max problems". In: arXiv preprint
order nash equilibria in nonconvex-conee
arXiv:2002.077 09991 (2020).
[60] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. 2018. arviv: 8808 02901 [math. OC]
[61] Krzysztof Postek and Shimrit Shtern. First-order algorithms for robust optimization problems via convex-concave saddle- -poitt Lagrangian reformulation. 2021.
arXiv: 2101. 02669
[math. [C]]
[62] Murray H Protter, B Charles Jr, et al. A first course in real analysis. Springer Science & Business Media, 2012.
[63] R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing. Vienna, Austria, 2013. URL.: /ttp::/ wwwp::/wwww........ooommoo .org/
[64] Hassan Rafique et al. Non Non-Convex Min-Max Optimization: Provable Algorithms and Applica- tions in Machine Learning. 2019, Xrv: 1810. 02060 [math. OC]]
[65] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis. Vol. 317. Springer Science & Business Media, 2009.
[66] Maziar Sanjabi et al. On the Convergence and Robustness of Training GANs with Regularized Optimal Transport. 2018. arXiv: 1802. 08249 [cs. LG]
12

---

[67]
Maziar Sanjabi et al. "On the Convergence and Robustness of Training GANs with Regular- ized Optimal Transport". In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS' 18. Montréal, Canada: Curran Associates Inc., 2018, pp. 7091-7101.
[68]
Prasanna Sattigeri et al. Fairness GAN. 2018. arXiv: 1805. 09910 [stat. .ML]
[69] Gilberto A.S. Segundo, Renato A. Krohling, and Rodrigo C. Cosme. "A differential evolution
approach for solving constrained min-max optimization problems", In: Expert Systems with Applications 39.18 (2012), pp. 13440-13450, ISSN: 0957-4174. Dol: https://doi.orz
10.1016/: eswa 2012 05. 059 URL: bttps: www. sciencedirect. com/
[70] K. Shimizu and E. Aiyoshi. "A new computational method for Stackelberg and min-max problems by use of penalty method". In: IEEE Transactions on Automatic Control 26.2
(1981), pp. 460-466. DO1: 11. TAC 1991.1111000 981.1702607,
[71] K. Shimizu and E. Aiyoshi. "Necessary conditions for min-max problems and algorithms relaxation procedure". In: IEEE Transactions on Automatic Control 25.1 (1980), pp. 62-66.
D01: 10..90.110//00 TACC 1980 1102226,
[72]
Aman Sinha et al. Certifying Some Distributional Robustness with Principled Adversarial Training. 2020. arXiv: I710. 10571 Istat. .ML]
[73]
The pandas development team. pandas- Pandas. Version latest. Feb. 2020. DOI:
10 5281 www/deeodo... 3509134
URI. //
5281 zenodo
3509134
[74]
Kiran Koshy Thekumparampil et al. Efficient Algorithms for Smooth Minimax Optimization.
2019. arXiv: 1 907. 01543 [math.00 OC]
[75]
Paul Tseng. "On accelerated proximal gradient methods for convex-concave optimization", In: submitted to SIAM Journal on Optimization 1 (2008).
[76]
Paul Tseng. "On linear convergence of iterative methods for the variational inequality problem". In: Journal of Computational and Applied Mathematiccs 60.1 (1995). Proceedings of the
International Meeting on Lincar/Nonlinear Iterative Methods and Verification of Solution.
pp. 237-252,
ISSN: 0377-0427, DOE: htt http:tttss///ba...o////.01///111
00094-8 URL: https: / www. SC wttpce/eeee..ccooccceee//e/errre
0377042794000922
[77] Guido Van Rossum and Fred L Drake Jr. Python tutorial. Centrum voor Wiskunde en Infor- matica Amsterdam, The Netherlands, 1995.
[78]
Heinrich Von Stackelberg. Marktform und gleichgewicht. springer, 1934.
[79]
Abraham Wald. "Statistical Decision Functions Which Minimize the Maximum Risk". In: Annals of Mathematics 46.2 (1945), pp. 265-280. ISSN: 0003486X. URL: http://www
[80] Léon Walras. Elements of Pure Economics: or, The Theory of Social Wealth. Translated by William Jaffé. Vol. Orion Editions, 1969, pp. 457-458.
[81] Hadley Wickham et "Welcome the tidyverse", In: Journal of Open Source Software 4.43
(2019), P. 1686. DOI: [0. 2tl.21115//oss 01 686
[82] Depeng Xu et al. FairGAN Fairness-aware Generative Adversarial Networks. 2018. arXiv:
1805. 11202 [cs. LG]
[83] Laura Scrimali Yurii Nesterov, "Solving strongly monotone variational and quasi-variational
inequalities". In: Discrete & Continuous Dynamical Systems 31.4 (201 I), pp. 1383-1396.
[84] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On Lower Iteration Complexity Bounds for the Saddle Point Problems. 2020. arXiv: 1912. 07481 [math. [c]]
[85] Renbo Zhao. A Primal Dual Smoothing Framework for tion. 2020. arXiv: 2003. 0437 75 [math. CC]]
Nonconvex Optimiza-
[86] Renbo Zhao. "Optimal algorithms for stochastic three-composite convex-concave saddle point problems". In: arXiv preprint arXiv: 1903:019030188 (2019).
13


Reviews:
[{"review_id": "wh5qy7wfNO", "reviewer": "Reviewer_CPGS", "summary": "This paper studies the minmax problem where the second player's (follower) action set depends on the action of the first player. Naturally, Stackelberg equilibrium is the concept to study here. The authors use a sub-gradient formulation of the known envelope theorem to solve the problem and experiment on Fisher market set-up.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "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": "In my reading of the paper, the work felt incremental because of\n1) The algorithm as such is exactly (for Alg 1) or mostly (for Alg 2) in the style of Jin et al. (or actually, papers before that also) with the difference being that the sub-gradient is used. Hence, the convergence proof also mostly follows standard sub-gradient convergence proofs.\n2) Fisher market and the Eisenberg Gale convex form has already been shown to admit first order methods on the direct EG form in Gao and Kroer. So, not sure why the same problem needs to be solved in a different way and is there any advantage of this first order form over that? The authors leave this future work but this comparison should be done for this work.\n3) More details on experiments (how the utility defining parameters were chosen instead of just higher and lower values as in Fig.1 ) needs to be in the main paper\n\nWriting:\nEasy to read, short simple examples given to assist the readers in understanding the problem with and without dependent sets. \nThe introduction is just too long, suggest breaking it up into more sections.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "bztqMczk99", "reviewer": "Reviewer_4ud8", "summary": "This work introduces two first order (subgradient) methods (1 requiring an oracle) to solve convex-concave min-max problems with convex dependent feasible sets. The convergence of both algorithms is analyzed, and their performance is demonstrated on computing Stackleberg equilibria of a family of Fisher market models.\n\n\nContributions:\n1) A subgradient algorithm assuming access to an oracle plus a nested subgradient algorithm (paired with explicit Fisher market counterparts) for computing Stackleberg equilibria in min-max problems with feasible sets\n2) Convergence guarantees for the proposed algorithms\n3) Adaptation of the general algorithms to the Fisher market domain\n4) Empirical analysis of the proposed algorithms on problems from either side of the boundary designated by the algorithmic assumptions", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "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": "Originality:\nTo my knowledge, these are the first subgradient algorithms for convex-concave min-max problems with convex dependent feasible sets.\n\nQuality:\nThe paper is of high quality.\n\nClarity:\nThe paper is written very clearly. I only had one question around Theorem 3.3 below.\n\nSignificance:\nThe computation of equilibria in min-max games is generally important and connections to Fisher markets in economist are made. It’s possible additional connections to robust optimization could increase the paper’s significance.\n\n\nOverall, I think the paper is well written and comprehensive. I think the paper could benefit from a few changes\n1) A discussion of uniqueness of the solutions to the min-max problems.\n2) Baselines and experiments\n3) Potentially add robust optimization to related work\n\n\n- [1] “Theory and Applications of Robust Optimization” Bertsimas et al. 2011\n- [2] “Online first-order framework for robust convex optimization” Ho-Nguyen and Kılınç-Karzan. 2016\n\n\n1) Uniqueness:\nOne part of Theorem 3.3 appears suspect. It is claimed that Algorithm 1 converges asymptotically to $(x^*, y^*)$ which is a $(0, \\delta)$-Stackleberg equilibrium, but is $(x^*, y^*)$ a unique equilibrium? I would assume there are many such $(0, \\delta)$-equilibria. Can you please address this and add a discussion around uniqueness of solutions for these minmax problems with dependent feasible sets? Maybe you meant to say that Algorithm 1 converges to one of the many $(0, \\delta)$-equilibria, not a specific one.\n\n\n2) Baselines and Experiments:\n- After reading the related work section, I was expecting an empirical comparison to the interior point methods of Ye [33] and first-order methods of Gao & Kroer [23]. Is there a reason you did not compare to them? The paper would benefit from having baselines to compare against.\n- Didn’t you need to set a value for $\\epsilon$ or $\\delta$ for the inner loop? Ah, I see you opted for number of iterations $T_X$ instead. I’d be interested to know the ratio of $T_X / T_p$ used in the experiment. Also, I would like to see a sweep over this parameter, which could provide further insight into understanding at which point GDA might fail (low values of the ratio move Alg 4 closer to alternating ascent descent which is closer to GDA).\n\n\n3) Robust Optimization:\nAt first glance, the min-max problem with dependent feasible sets seems related to robust optimization. Briefly, see https://en.wikipedia.org/wiki/Robust_optimization, https://en.wikipedia.org/wiki/Wald%27s_maximin_model or [1] and [2] for first-order online approaches.\n\n\nMinor:\n- Are the $g_i$ required to be concave so that the intersection with $Y$ forms a convex set? Is this the most general setting?\n- A figure illustrating how taking a step changes the feasible set and hence presents problems for GDA could be enlightening and convince the reader of the difficulty of the problem\n- line 60: After a double-take, I understand what you’re saying but saying $V(x)$ is $y$’s problem is confusing as $y$ doesn't appear as an argument. It’s probably better to write out \"player $y$'s problem is $\\max_{y \\in Y}:g(x,y) \\ge 0 f(x,y) = V(x)$\" again.\n- line 98: does $\\epsilon$-approximation refer to error in the strategy space or value function space or both? It appears value function space (Def 2.1). It would help the reader if you mentioned this around line 98.\n- Table 2, strongly concave case — I didn’t check the proof, but shouldn’t $\\log(\\epsilon)$ be $\\log(\\frac{1}{\\epsilon})$? Seems like a typo.\n- Figure 1 - maybe refer to the algorithms with a description as well since they are not included in the main body, e.g., Algorithm 3 (oracle, in blue) and Algorithm 4 (nested, in orange). Also, why not plot on a log scale?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention the connection of their work to fairness and adequately address any possible negative impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Rf1baYXroT6", "reviewer": "Reviewer_Krbq", "summary": "The paper studies min-max optimization problems with dependent strategy sets, and introduces a first-order method that solves a large class of convex-concave min-max games with dependent strategy sets. In doing so, the authors provide a suitable envelope theorem which generalizes known results to the case of dependent strategies. That result is used to build two algorithms: max-oracle gradient-descent (which returns an approximation of the inner player's value function), and nested gradient-descent/ascent (which computes both players' strategies explicitly). The algorithms are shown to converge in polynomial time, and  they are experimentally evaluated through the computation of competitive equilibria in Fisher markets with varying utility structures. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "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": "The paper is well written and mostly clear. The general problem of minmax games with dependent strategy sets is well motivated by applications such as computing equilibria in Fisher markets. The set of techniques presented may be a good starting point for future works on other related problems. \n\nI'd be interested in hearing more about how the method proposed by the authors compares (in the Fisher markets setting) to other recent works such as Gao and Kroer [23]. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Kqo-FFmqBUV", "reviewer": "Reviewer_gWmB", "summary": "The authors study sequential (aka Stackelberg) games, where the actions of the follower are subjects to constraints depending on the leader's action.\nThey derive a formula for the subgradient of leader's utility (under optimal action of the follower) and use it to derive subgradient descent algorithms with convergence guarantees.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "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": "The authors study minimization problems of the form $\\min \\limits_{x} V(x) = \\min \\limits_{x} \\max \\limits_{y: g(x, y) \\geq 0} f(x,y)$\nfor f convex-concave and g component-wise concave.\nThe convex function $V(x)$ is convex but in general only subdifferentiable.\nIf $V$ is differentiable in $x$, recent results by Milgrom and Segal allow to express its gradient in terms of the optimal solution $y, \\lambda$ of the inner loop, where $\\lambda\n$ is a lagrange multiplier associated to the constraint.\nThe authors extend this results to a characterization of the subgradient of $V(x)$ in arbitrary points, and derive rates for the resulting first order methods, accounting also fo\nr the solution of the inner loop.\nThey furthermore test their algorithms on a series of Fisher markets.\n\nThis appears to be solid work, although I am not sure about the relevance of the author's results to the rest of the NeurIPS community.\nThe authors do not provide any explanation to this effect, with the exception of line 376, which is fairly vague (in which GAN model do dependent strategy sets arise?).\nVenues more focused on economics or convex optimization might also be better positioned to appreciate the theoretical contribution of the Subdifferential Envelope Theorem.\n\nI am therefore somewhat on the fence about this paper, maybe slightly leaning towards rejection but open to being convinced otherwise in the rebuttal.\n\nComments to authors: As illustrated in the paper, convex games with dependent strategy sets do not satisfy a minimax theorem in general. \nHowever, they can also be interpreted as simultaneous (non-\\{sequential/stackelberg\\}) non-zero-sum games (with rewards attaining $-\\infty$).\nI might be helpful to change the title and possibly introduction to clarify that the paper deals with sequential games.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a class of min-max games where each player's actions are subject to coupled constraints, i.e., the actions avaible to one player depend on the action chosen by the other, and vice versa. The authors examine two sequential algorithms for solving the game - one based on best responses and another based on a nested version of gradient descent - and they derive a series of polynomial complexity guarantees for the algorithms under study.

The reviewers appreciated the contributions of the paper and were initially positive. However, during the discussion phase, it became clear that the paper is ignoring an extensive literature on generalized Nash equilibrium problems. This literature dates back at least to Debreu's seminal 1952 paper and it treats essentially the same problem as the authors: in particular, there is a series of asymptotic convergence results (for different classes of games) that should be discussed by the authors. More precisely, even though the literature on learning in generalized Nash equilibrium problems does not provide rates of convergence, the results provided therein prove the convergence of the actual sequence of play (something which does not seem possible with the authors' approach and techniques).

Another - more minor - concern had to do with the relevance of such models for the ML/AI community, but this was partially addressed by the authors.

Overall, the paper definitely has merits: to the best of the committee's knowledge, this is the first polynomial complexity result of its kind in the class of games with coupled constraints (which is perhaps not surprising since the literature on generalized Nash equilibrium problems otherwise focuses on the convergence of the actual sequence of play, not the "best" or "time-averaged" iterate). However, the lack of proper positioning is a major issue that has to be fixed for the camera-ready version; specifically, the committee has the following expectations:
1. The authors should provide adequate pointers to the literature on generalized Nash equilibrium problems, especially on early work by Facchinei and co-authors, as well as more recent contributions by Grammatico and co-authors - e.g., the recent preprint by Fabiani et al., "Local Stackelberg equilibrium seeking in generalized aggregative games" should be discussed in detail. [Certain references were already provided during the discussion phase, and the authors would be expected to expand on those]
2. The authors should present in detail the notion of generalized Nash equilibria in the paper (during the discussion phase, there seemed to be some confusion on this point by the authors, but it was eventually cleared up). In particular, the committe expects the authors to provide an in-depth comparison to the model of Fabiani et al. - not in regard to the _class of games_ considered, but as to the _notion of equilibrium_ under study. Put simply, now that the authors are aware of the literature on the problem, the committee would expect an in-depth and balanced treatment.
3. The algorithms studied by the authors should be incorporated in the main text - otherwise, the statements of the authors' theorems are impossible to parse.

Modulo the above, I am happy to recommend acceptance.
Decision: Accept (Poster)