Convex-Concave Min-Max Stackelberg Games
Year: 2022

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.

heading: 1 Introduction
text: Min-max optimization problems have attracted a great deal of attention recently because of their applicability to a wide range of machine learning problems. Examples of settings in which min-max optimization problems arise include, but are not limited to, reinforcement learning [15], generative adversarial networks [66], fairness in machine learning [14, 23, 48, 68, 82], adversarial learning [72], generative adversarial imitation learning [11, 32], and statistical learning (e.g., learning parameters of exponential families) [14]. These applications often require solving a constrained min-max optimization problem (with independent feasible sets): i.e., minx2X maxy2Y f(x,y), where f : X ⇥ Y ! R is continuous, and X ⇢ Rn and Y ⇢ Rm are non-empty and compact. A convex-concave constrained min-max optimization problem is one in which f is convex in x and concave in y. In the special case of convex-concave objective functions, the seminal minimax theorem holds: i.e., minx2X maxy2Y f(x,y) = maxy2Y minx2X f(x,y) [55]. This theorem guarantees the existence of a saddle point (i.e., a point that is simultaneously a minimum of f in the x-direction and a maximum of f in the y-direction), and allows us to interpret the optimization problem as a simultaneous-move, zero-sum game, where y⇤ (resp. x⇤) is a best-response of the outer (resp. inner) player to their opponent’s strategy x⇤ (resp. y⇤), in which case a saddle point is also called a minimax point or a Nash equilibrium. In this paper, we show that the computation of competitive equilibria in Fisher markets [10], a central solution concept for one 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 (NeurIPS 2021).
feasible sets. We define a constrained min-max optimization problem with dependent feasible sets as an optimization problem of the following form: minx2X maxy2Y :g(x,y) 0 f(x,y), where f : X ⇥ Y ! R is continuous, X ⇢ Rn and Y ⇢ Rm are non-empty and compact, and g(x,y) = (g1(x,y), . . . , gK(x,y))
T with gk : X ⇥ Y ! R.1 Unfortunately, certain desirable properties of standard convex-concave min-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 feasible sets: minx2[ 1,1] maxy2[ 1,1]:x+y0 x2 + y + 1. The optimum is x⇤ = 1/2, y⇤ = 1/2, with value 3/4. Now, consider the same problem, with the order of the min and the max reversed: maxy2[ 1,1] minx2[ 1,1]:x+y0 x 2 + y + 1. The optimum is now x⇤ = 1, y⇤ = 1, with value 3.
Without a minimax theorem, constrained min-max optimization problems with dependent feasible sets are more appropriately viewed as two-player sequential, i.e., Stackelberg, games where the outer player chooses x 2 X before the inner player responds with their choice of y(x) 2 Y s.t. g(x,y(x)) 0. The relevant equilibrium concept is then a Stackelberg [78] equilibrium,2 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 function3 V : X ! R is defined as V (x) = maxy2Y :g(x,y) 0 f(x,y). This function represents the outer player’s loss, assuming the inner player chooses a feasible 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⇤) 2 X ⇥ Y to be a Stackelberg equilibrium in a convexconcave min-max Stackelberg game are given by the KKT stationarity conditions for the two players’ optimization problems, namely minx2X V (x) for the outer player, and maxy2Y :g(x,y) 0 f(x,y) for the inner player.
In the independent strategy setting, Danskin’s theorem [17] states that rxV (x) = rxf(x,y⇤), where y⇤ 2 argmaxy2Y 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 a tuple (x⇤,y⇤) to be an (interior) saddle point are for it to be a stationary point of f (i.e., rxf(x⇤,y⇤) = ryf(x⇤,y⇤) = 0). It is therefore logical for players in the independent/simultaneous-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. Example 1.2. Consider, once again, the problem posed in Example 1.1, and recall Jin, Netrapalli, and Jordan’s gradient descent with max-oracle algorithm [41]: x(t+1) = x(t) ⌘rxf xt,y⇤(x(t)) , where y⇤(x(t)) 2 argmaxy2Y :g(x(t),y) 0 f(x(t),y) for ⌘ > 0. Applied to this sample problem, with ⌘ = 1, this algorithm yields the following update rule: x(t+1) = x(t) 2x(t) = x(t). Thus, letting x(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 a Stackelberg equilibrium, as the Stackelberg equilibrium of this game is x⇤ = 1/2, y⇤ = 1/2.
Now consider an algorithm that updates based not on gradient of the objective function, but of the value function, namely x(t+1) = x(t) ⌘rxV (xt). The value function is V (x) = maxy2[ 1,1]:x+y0 x
2+y+1 = x2 x+1, with gradient V 0(x) = 2x 1. Thus, when ⌘ = 1, this algorithm yields the following update rule: x(t+1) = x(t) V 0(x(t)) = x(t) 2x(t)+1 = x(t)+1. If we run this algorithm from initial point x(0) = 1/8, we get x(1) = 1/8+1 = 7/8, x(2) = 7/8+1 = 1/8, and so on. The average of the iterates 1/8, 7/8, 1/8, . . . converges to x⇤ = 1/2 (1/8 + 7/8) = 1/2, and correspondingly y⇤ = 1/2, which is indeed the Stackelberg equilibrium.
1Although notationally similar, we note that this model is more general than that of Daskalakis, Skoulakis, and Zampetakis [18]. The authors state that under the assumptions of the minimax theorem [55], a Nash equilibrium is guaranteed to exist in their model. When there is dependence among the players’ feasible sets, however, this claim does not hold (see Example 1.1).
2In constrained convex-concave min-max optimization problems with independent feasible sets, the notions 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.
3Note that this use of the term value function in economics is distinct from its use in reinforcement learning.
In this paper, we introduce two first-order (subgradient) methods that solve min-max Stackelberg games—to our knowledge the first such methods. Our approach relies on a new generalization of a series of fundamental results in mathematical economics known as envelope theorems [1, 50]. Envelope theorems generalize aspects of Danskin’s 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.
Our first algorithm follows Jin, Netrapalli, and Jordan [41], assuming access to a max-oracle that returns y⇤ 2 argmaxy2Y :g(x,y) 0 f(x,y), given x 2 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 to a Stackelberg equilibrium of any convex-concave min-max Stackelberg game with nonempty, compact and convex dependent strategy sets. In Table 1, we summarize the iteration complexities of our algorithms, i.e., the number of iterations required to achieve an "-approximate equilibrium, where " is the desired precision.
Finally, we apply our results to the computation of competitive equilibria in Fisher markets. In this context, our method for solving a min-max Stackelberg game reduces to solving the market in a decentralized manner using a 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—specifically, 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 to 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, a fundamental framework in operations research for which many methods have been proposed [6, 56, 61]. Shimizu and Aiyoshi [70, 71] proposed the first algorithm to solve min-max Stackelberg games via a relaxation to a 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 a simple and efficient manner.
Extensive-form 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 Iannelli [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.
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 a 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 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 architecture called RegretNet that represents optimal auctions, and train their networks using Algorithm 3.4. Optimal auction design problems can be seen as min-max Stackelberg games; however, as their objectives are non-convex-concave in general, our guarantees do not apply.
In this paper, we 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 a polynomial-time method for the case of linear utilities. Jain, Vazirani, and Ye [40] subsequently showed that a 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 a detailed discussion of recent progress on solving min-max Stackelberg games, both in the convex-concave case and the non-convex-concave case.

heading: 2 Preliminaries
text: Notation We use Roman uppercase letters to denote sets (e.g., X), bold uppercase letters to denote matrices (e.g., X), bold lowercase letters to denote vectors (e.g., p), and Roman lowercase letters to denote scalar quantities, (e.g., c). We denote the ith row vector of a matrix (e.g., X) by the corresponding bold lowercase letter with subscript i (e.g., xi). Similarly, we denote the jth entry of a vector (e.g., p or xi) by the corresponding Roman lowercase letter with subscript j (e.g., pj or xij). We denote the set of integers {1, . . . , n} by [n], the set of natural numbers by N, the set of real numbers by R, the set of non-negative real numbers by R+. We denote by ⇧Y the Euclidean projection operator onto the set Y ⇢ Rm: i.e., ⇧Y (y) = argminz2Y ky zk2. A min-max Stackelberg game, denoted (X,Y, f, g), is a two-player, zero-sum game, where one player, who we call the x-player (resp. the y-player), is trying to minimize their loss (resp. maximize their gain), defined by a continuous objective function f : X ⇥ Y ! R, by choosing a strategy from a compact strategy set X ⇢ Rn (resp. Y ⇢ Rm), and s.t. g(x,y) 0 where g(x,y) = (g1(x,y), . . . , gK(x,y))
T with gk : X ⇥ Y ! R . A strategy profile (x,y) 2 X ⇥ Y is said to be feasible iff for all k 2 [K], gk(x,y) 0. The function f maps a pair of feasible strategies taken by the players (x,y) 2 X ⇥ Y to a real value (i.e., a payoff), which represents the loss (resp. the gain) of the x-player (resp. y-player). A min-max game is said to be convex-concave if 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, g). A strategy profile (x⇤,y⇤) 2 X ⇥ Y such that g(x⇤,y⇤) 0 is a (", )-Stackelberg equilibrium if maxy2Y :g(x⇤,y) 0 f (x ⇤ ,y)  f (x⇤,y⇤)  minx2X maxy2Y :g(x,y) 0 f (x,y) + ".
Intuitively, a (", )-Stackelberg equilibrium is a point at which the x-player’s (resp. y-player’s) payoff is no more than " (resp. ) away from its optimum. By Proposition B.2, a (0, 0)-Stackelberg equilibrium is guaranteed to exist in min-max Stackelberg, its value is unique, and by Proposition B.3 the set of Stackelberg equilibria is compact and convex.
Finally, we define several concepts that are needed in our convergence proofs. Given A ⇢ Rn, the function f : A ! R is said to be `f -Lipschitz-continuous iff 8x1,x2 2 X, kf(x1) f(x2)k  `f kx1 x2k. If the gradient of f , rf , is `rf -Lipschitz-continuous, we then refer to f as `rf -Lipschitz-smooth. A function f : A ! R is µ-strongly convex if f(x1) f(x2) + hrxf(x2),x1 x2i+ µ/2 kx1 x1k 2, and µ-strongly concave if f is µ-strongly convex.

heading: 3 First-Order Methods via an Envelope Theorem
text: 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 [1] 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, g1, . . . , gK are continuous and convex-concave; 2. rxf,rxg1, . . . ,rxgK are continuous; and 3. (Slater’s condition) 8x 2 X, 9by 2 Y s.t. gk(x, by) > 0, for all k = 1, . . . ,K.
Milgrom and Segal’s [50] envelope theorem provides an explicit formula for the gradient of the value function. When strategy sets are independent, under mild assumptions, this function is guaranteed to be differentiable [58]. When strategy sets are dependent, however, it is not necessarily differentiable, as seen in Example C.2. As a remedy, we present a subdifferential envelope theorem for nondifferentiable value functions: Theorem 3.2 (Subdifferential Envelope Theorem). Consider the value function V (x) = maxy2Y :g(x,y) 0 f(x,y). Let Y ⇤(x) = argmaxy2Y :g(x,y) 0 f(x,y) and suppose Assumption 3.1 holds. Then, at any point bx 2 X , @xV (bx) =
conv
0 @ [
y⇤(bx)2Y ⇤(bx)
[
⇤k(bx,y⇤(bx))2⇤⇤(bx,y⇤(bx))
( rxf (bx,y⇤(bx)) + KX
k=1
⇤ k(bx,y⇤(bx))rxgk (bx,y⇤(bx))
)1
A ,
(1)
where conv is the convex hull operator and ⇤(bx,y⇤(bx)) = ( ⇤1(bx,y⇤(bx)), . . . , ⇤K(bx,y⇤(bx))) T 2 ⇤⇤(bx,y⇤(bx)) are the optimal KKT multipliers associated with y⇤(bx) 2 Y ⇤(bx).
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, our subdifferential envelope theorem states that every subgradient of the value function, V (x) = maxy2Y :g(x,y) 0 f(x,y) is a convex combination of the values of the gradient of the Lagrangian evaluated at the optimal solutions (y⇤(x), ⇤(x,y⇤(x))) 2 Y ⇤(x)⇥ ⇤⇤(x,y⇤(x)).
With our envelope theorem in hand, we are now ready to present two gradient-descent/ascent-type 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], assumes access to a max-oracle, which given x 2 X , returns a -maximum of the inner player’s value function. That is, for all x 2 X , the max-oracle returns by 2 Y s.t. g(x, by) 0 and f(x, by) maxy2Y :g(x,y) 0 f(x,y) . It then runs (sub)gradient descent on the outer player’s value function, using Theorem 3.2 to compute the requisite subgradients. Inspired by the multistep gradient-descent algorithm of Nouiehed et al. [58], our second algorithm, nested gradientdescent/ascent (see Appendix E), computes both x⇤ and y⇤ explicitly, without oracle access. We simply replace the max-oracle in our max-oracle gradient-descent algorithm by a projected gradientascent procedure, which again computes a -maximum of the inner player’s value function.
Once by is found at iteration t, one can compute optimal KKT multipliers ⇤1(x(t), by(x(t))), . . ., ⇤ K(x (t) , by(x(t))) 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 optimal, namely (x(t), by(x(t))), or by running gradient descent on the Lagrangian for the dual variables. Additionally, most algorithms solving convex programs will return ⇤(x(t), by(x(t))) = ( ⇤1(x (t) , by(x(t))), . . . , ⇤K(x(t), by(x(t)))) together with the optimal by(x(t))) without incurring any additional computational expense. As a result, we assume that the optimal KKT multipliers ⇤(x(t), by(x(t))) associated with a solution by(x(t))) can be computed in 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 x. More precisely, the objective function f is `f -Lipschitz in x, where `f = max(bx,by)2X⇥Y krxf(bx, by)k.4 As f is `f -Lipschitz continuous in x, the value function is
4This max norm is well-defined since rxf is continuous and the constraint set is non-empty and compact.
Algorithm 1 Max-Oracle Gradient Descent Inputs: X,Y, f, g,⌘ , T,x(0) Output: (x⇤,y⇤)
1: for t = 1, . . . , T do 2: Find y(t 1) 2 Y s.t. f(x(t 1),y(t 1)) V (x(t 1)) & g(x(t 1),y(t 1)) 0 3: Set (t 1) = ⇤(x(t 1),y(t 1)) 4: Set x(t) = ⇧X ⇣ x(t 1) ⌘t h rxf(x(t 1),y(t 1)) + PK k=1 (t 1) k rxgk(x (t 1) ,y(t 1)) i⌘ 5: end for 6: Find y(T ) 2 Y s.t. f(x(T ),y(T )) V (x(T )) & g(x(T ),y(T )) 0 7: return (x(T ),y(T ))
also `f -Lipschitz.5 This fact suggests that an (", ")-Stackelberg equilibrium should be computable in O(" 2) iterations by our max-oracle gradient descent algorithm (Algorithm 1), since our method is a subgradient method. Theorem 3.3. Consider a convex-concave min-max Stackelberg game, (X,Y, f, g), where X is convex, and (x⇤,y⇤) is a (0, )-Stackelberg equilibrium, and suppose Assumption 3.1 holds. If Algorithm 1 is run for T iterations, with step sizes ⌘t s.t. PT k=1 ⌘ 2 k  1, PT k=1 ⌘k = 1, and if (x(t)best,y (t) best) 2 argmin(x(k),y(k)):k2[t] f(x (k) ,y(k)), it holds that limT!1 f(x (T ) best,x (T ) best) = f(x⇤,y⇤). Furthermore, for " 2 (0, 1), if we choose T NT (") 2 O(" 2), then there exists an iteration T ⇤  T s.t. (x(T
⇤) best ,y (T⇤) best ) is an (", )-Stackelberg equilibrium.
As is expected, the O(" 2) iteration complexity can be improved to O(" 1), if additionally, f is strongly convex in x. (See Appendix E, Theorem E.2). Combining the convergence results for our max-oracle gradient descent algorithm with convergence results for gradient descent [8], we obtain the following convergence rates for the nested gradient descent-ascent algorithm (Algorithm 2, Appendix E). We include the formal proof and statement for the case when Assumption 3.1 holds and f is Lipschitz-smooth in Appendix E (Theorem E.3). The other results follow similarly. Theorem 3.4. Consider a convex-concave min-max Stackelberg game, (X,Y, f, g), with X and Y convex. Suppose that Assumption 3.1 holds. Then, under standard assumptions on the step sizes, the iteration complexities given below hold for the computation of a (", ")-Stackelberg equilibrium:
f is `rf -smooth f is `rf -smooth + f Strongly Concave in y
Assumption 3.1 O(" 3) O " 2 log(" 1)
Assumption 3.1 + f Strongly Convex in x O(" 2) O(" 1 log(" 1))
Since the value function in the convex-concave dependent setting is not 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 1, we assume only that the objective function is continuously differentiable, which leads to a more widely applicable, albeit slower, convergence rate. Note, however, that we assume Lipschitz-smoothness 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 a slower convergence rate.

heading: 4 An Economic Application: Fisher Markets
text: 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. In this section, we argue that a competitive equilibrium in Fisher markets can be understood a Stackelberg
5A formal statement of this claim can be found in Appendix E (Lemma E.1).
equilibrium of a convex-concave min-max Stackelberg game. We then apply our first-order methods to compute these equilibria in various Fisher markets.
A Fisher market consists of n buyers and m divisible goods [10]. Each buyer i 2 [n] has a budget bi 2 R+ and a utility function ui : Rm+ ! 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 a tuple (n,m,U, b), where U = {u1, . . . , un} is a set of utility functions, one per buyer, and b 2 Rn+ is the vector of buyer budgets. We abbreviate as (U, b) when n and m are clear from context.
An allocation X = (x1, . . . ,xn)T 2 Rn⇥m+ is a map from goods to buyers, represented as a matrix, s.t. xij 0 denotes the amount of good j 2 [m] allocated to buyer i 2 [n]. Goods are assigned prices p = (p1, . . . , pm)T 2 Rm+ . A tuple (p⇤,X⇤) is said to be a competitive (or Walrasian) equilibrium of Fisher market (U, b) if 1. buyers are utility maximizing, constrained by their budget, i.e., 8i 2 [n],x⇤i 2 argmaxx:x·p⇤bi ui(x); and 2. the market clears, i.e., 8j 2 [m], p ⇤ j > 0 )P
i2[n] x ⇤ ij = 1 and p⇤j = 0 ) P i2[n] x ⇤ ij  1.
We now formulate the problem of computing a competitive equilibrium (p⇤,X⇤) of a Fisher market (U, b), where U is a set of continuous, concave, and homogeneous6 utility functions, as a convexconcave min-max Stackelberg game, a perspective which has not been taken before. Fisher markets can by solved via the Eisenberg-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 [31], namely
min p 0
X
j2[m]
pj + X
i2[n]
bi log
✓ max
xi 0:xi·pbi ui(xi)
◆ . (2)
Rearranging, we obtain the following convex-concave min-max Stackelberg game:
min p 0 max X 0:Xpb
X
j2[m]
pj + X
i2[n]
bi log (ui(xi)) . (3)
This min-max game is played by a fictitious (Walrasian) auctioneer and a set of buyers, who effectively play as a 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, we cannot use existing first-order methods to solve this problem. However, we can use Algorithms 1 and 2.
Starting from Equation (3), define the auctioneer’s value function V (p) = maxX 0:Xpb P j2[m] pj + P i2[n] bi log (ui(xi)), and buyer i’s demand set X ⇤ i (p, b) = argmaxxi 0:xipb ui(xi). Theorem 3.2 then provides the relevant subgradients so that we can run Algorithms 1 and 2, namely @pV (p) = 1m P i2[n] X ⇤ i (p, b) and
rxi ⇣P j2[m] pj + P i2[n] bi log (ui(xi)) ⌘ = biui(xi)rxiui(xi), using the Minkowski sum to add set-valued quantities, where 1m is the vector of ones of size m.7
Cheung, Cole, and Devanur [12] observed that solving the dual of the Eisenberg-Gale program (Equation 2) via (sub)gradient descent [20] is equivalent to solving for a competitive equilibrium in a Fisher market using an auction-like economic price adjustment process named tâtonnement 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 n p(t 1) + ⌘t ⇣P i2[n] x ⇤ i (p(t), b) 1 ⌘ , 0 o
for p(0) 2 Rm+ , where x⇤i (p(t), bi) 2 X
⇤ i (p(t), bi) = argmaxxi 0:xip(t)bi ui(xi) is the demand set of buyer i. The max-oracle algorithm applied to Equation (3) is then equivalent to a tâtonnemement process where the buyers report a -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
6A function f : Rm ! R is said to be homogeneous of degree k if 8x 2 Rm, > 0, f( x) = kf(x). Unless otherwise indicated, a homogeneous function is assumed to be homogeneous of degree 1.
7We include detailed descriptions of the algorithms applied to Fisher markets in Appendix F.
the entropic tâtonnement process [31].8 Assume that the step sizes ⌘t satisfy the usual conditions:PT k=1 ⌘ 2 k  1 and PT k=1 ⌘k = 1. If p (t) best 2 argminp(k):k2[t] V (p (k)), then limk!1 V (p (k) best) = V (p⇤). Additionally, tâtonnement converges to an "-competitive equilibrium in O(" 2) iterations.
If we also apply the nested gradient-descent-ascent algorithm to Equation (3), we arrive at an 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 a decentralized manner. The nested tâtonnement algorithm essentially describes a two-step trial-anderror (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 are 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.
Experiments In order to better understand, the iteration complexity of Algorithms 1 and 2 (Appendix E), we ran a series of experiments on Fisher markets with three different classes of utility functions.9 Each utility structure endows Equation (3) with different smoothness properties, which allows us to compare the efficiency of the algorithms under varying conditions.
Let vi 2 Rm be a vector of parameters for the utility function of buyer i 2 [n]. We have the following utility function classes: Linear: ui(xi) = P j2[m] vijxij , Cobb-Douglas: ui(xi) = Q j2[m] x vij ij , Leontief: ui(xi) = minj2[m] n xij vij o . Equation (3) satisfies the smoothness properties listed in Table 2 when U is one of these three classes. Our goals are two-fold. First, we want to understand how the empirical convergence rates of Algorithms 1 and 2 (which, when applied to Equation (3) give rise to Algorithms 3 and 4 in Appendix F, 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 F.
Figure 1 describes the empirical convergence rates of Algorithms 1 and 2 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(1/pT) for linear utilities, which seems plausible, as the value function is not differentiable assuming linear utilities, and hence we are unlikely to achieve a better convergence rate. On the other hand, for Cobb-Douglas utilities, both the value and the objective function are differentiable; in fact, they are both twice continuously differentiable, making them both Lipschitz-smooth. These factors combined seem to provide a much faster convergence rate than O(1/pT).
Fisher markets with Leontief utilities, in which the objective function is not differentiable, are 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 (3) is locally Lipschitz: i.e., any subgradient computed by the algorithm will be bounded. Overall, our theory suggests that differentiability of the value function is not essential to guarantee convergence of first-order methods in convex-concave games, while our
8The 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.
9Our code can be found at https://github.com/denizalp/min-max-fisher.git.
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 to investigate whether the outputs of Algorithm 1, which uses an exact max-oracle (i.e., 0-max-oracle) are more precise than those of Algorithm 2, we solved 500 randomly initialized markets with both algorithms. We then ran a James’ first-order test [2, 36] on the mean output of both algorithms to see if their difference was statistically significant. Our calculations produced p-values of 0.69, 0, 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 can 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.

heading: 5 Conclusion
text: In this paper, we proposed two first-order methods to solve a class of constrained convex-concave min-max optimization problems, which we call min-max Stackelberg games. As such games do not afford Nash equilibria in general, we focused on the computation of their Stackelberg equilibria. To solve for Stackelberg equilibria, we introduced a novel subdifferential envelope theorem, which formed the heart of two subgradient methods with polynomial-time iteration complexity that converge to Stackelberg equilibria. Finally, we 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-concave min-max Stackelberg games more generally is whether gradient-descent-ascent (GDA) converges in the dependent strategy set setting as it does in the independent strategy setting [45]. GDA dynamics for Fisher markets correspond to myopic best-response dynamics (see, for example, [52]). We would expect such a result to be of computational as well as economic interest.
Acknowledgments and Disclosure of Funding
We would like to thank Dustin Morrill for his feedback on an early draft of this paper. This work was partially supported by NSF Grant CMMI-1761546.

Review summaries:
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. 

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. 

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.   Contributions: 1) 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 2) Convergence guarantees for the proposed algorithms 3) Adaptation of the general algorithms to the Fisher market domain 4) Empirical analysis of the proposed algorithms on problems from either side of the boundary designated by the algorithmic assumptions