# convexconcave_minmax_stackelberg_games__899f7382.pdf

Convex-Concave Min-Max Stackelberg Games

Denizalp Goktas Department of Computer Science

Brown University Providence, RI 02912 denizalp_goktas@brown.edu

Amy Greenwald Department of Computer Science

Brown University Providence, RI 02912 amy_greenwald@brown.edu

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.

1 Introduction

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 (Neur IPS 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), . . . , g K(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+y 0 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+y 0 x2 + 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 rx V (x) = rxf(x, y ), where y 2 arg maxy2Y 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 arg maxy2Y :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) rx V (xt). The value function is V (x) = maxy2[ 1,1]:x+y 0 x2 +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 arg maxy2Y :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.

Table 1: Iteration complexities of Algorithms 1 and 2 for min-max Stackelberg games. Here, µx and µy are strong convexity/concavity parameters.

Properties of f Iteration Complexity Algorithm 1 Algorithm 2 µx-Strongly-Convex-µy-Strongly-Concave O

" 1" O(" 1) µx-Strongly-Convex-Concave O(" 2)

Convex-µy-Strongly-Concave O

" 2" O(" 2) Convex-Concave O(" 3)

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 Regret Net 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.

2 Preliminaries

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) = arg minz2Y 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), . . . , g K(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 x1k2, and µ-strongly concave if f is µ-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 [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, . . . , g K are continuous and convex-concave; 2. rxf, rxg1, . . . , rxg K 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) = arg maxy2Y :g(x,y) 0 f(x, y) and suppose Assumption 3.1 holds. Then, at any point bx 2 X, @x V (bx) =

y (bx)2Y (bx)

k(bx,y (bx))2 (bx,y (bx))

rxf (bx, y (bx)) +

k(bx, y (bx))rxgk (bx, y (bx))

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

rxf(x(t 1), y(t 1)) + PK

k rxgk(x(t 1), y(t 1))

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 k = 1, and if (x(t)

best) 2 arg min(x(k),y(k)):k2[t] f(x(k), y(k)), it holds that lim T !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.

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. 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 arg maxx:x p bi ui(x); and 2. the market clears, i.e., 8j 2 [m], p

ij = 1 and p

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 convex-

concave 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

max xi 0:xi p bi ui(xi)

Rearranging, we obtain the following convex-concave min-max Stackelberg game:

min p 0 max X 0:Xp b

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) = max X 0:Xp b

j2[m] pj + P

i2[n] bi log (ui(xi)), and buyer i s demand set X

i (p, b) = arg maxxi 0:xip b ui(xi). Theorem 3.2 then provides the relevant subgradients so that we can run Algorithms 1 and 2, namely @p V (p) = 1m P

i (p, b) and

j2[m] pj + P

i2[n] bi log (ui(xi))

= bi ui(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

i (p(t), b) 1

for p(0) 2 Rm

i (p(t), bi) 2

i (p(t), bi) = arg maxxi 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 k = 1. If p(t)

best 2 arg minp(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

Leontief: ui(xi) = minj2[m]

. 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.

Table 2: Smoothness properties satisfied by Equation (3) assuming different utility functions. Note that Assumption 3.1 does not hold for Leontief utilities, because they are not differentiable.

V is differentiable Assumption 3.1 holds Linear X Cobb-Douglas X X Leontief X

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/

T) 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/

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.

Figure 1: The first row describes the average trajectory of the value of the objective function for a randomly initialized market on each iteration of both Algorithm 3 (in blue) and Algorithm 4 (in orange) when the starting prices are high, while the second row describes the average trajectory of the objective function when starting prices are low for linear, Cobb-Douglas, and Leontief Fisher markets respectively. The dashed red line represents a convergence rate of O(1/

T), which corresponds to an iteration complexity of O(1/ 2).

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.

5 Conclusion

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.

[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.jstor.org/ 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. URL: http://www.jstor.org/stable/1165297. [3] Mohammad Alkousa et al. Accelerated methods for composite non-bilinear saddle point problem. 2020. ar Xiv: 1906.03620 [math.OC]. [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, I . In: Econometrica 26.4 (1958), pp. 522 552. ISSN: 00129682, 14680262. URL: http: //www.jstor.org/stable/1907515. [6] Aharon Ben-Tal et al. Oracle-based robust optimization via online learning . In: Operations Research 63.3 (2015), pp. 628 638. [7] Claude Berge. Topological Spaces: including a 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 to compute equilibrium prices in 1891. Citeseer, 2000. [11] Qi Cai et al. On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator. 2019. ar Xiv: 1901.03674 [cs.LG]. [12] Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Tatonnement beyond Gross Substitutes? 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. 191 200. ISBN: 9781450320290. DOI: 10.1145/ 2488608.2488633. URL: https://doi.org/10.1145/2488608.2488633. [13] Richard Cole and Yixin Tao. Balancing the Robustness and Convergence of Tatonnement. 2019. ar Xiv: 1908.00844 [cs.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 of Machine Learning Research. PMLR, Apr. 2019, pp. 2321 2330. URL: http://proceedings.mlr. press/v89/dai19a.html. [15] Bo Dai et al. SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation . 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. URL: http://proceedings.mlr.press/v80/dai18c. html. [16] Yu-Hong Dai and Liwei Zhang. Optimality Conditions for Constrained Minimax Optimization. 2020. ar Xiv: 2004.09730 [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. ISSN: 00361399. URL: http://www.jstor.org/ stable/2946123. [18] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The Complexity of Constrained Min-Max Optimization. 2020. ar Xiv: 2009.09623 [cs.CC]. [19] Trevor Davis, Kevin Waugh, and Michael Bowling. Solving Large Extensive-Form Games with Strategy Constraints. 2019. ar Xiv: 1809.07893 [cs.GT]. [20] N. R. Devanur et al. Market equilibrium via a primal-dual-type algorithm . In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002,

pp. 389 395. DOI: 10.1109/SFCS.2002.1181963.

[21] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization . In: Journal of Machine Learning Research 17.83 (2016), pp. 1 5. [22] Paul Duetting et al. Optimal auctions through deep learning . In: International Conference on Machine Learning. PMLR. 2019, pp. 1706 1715. [23] Harrison Edwards and Amos Storkey. Censoring Representations with an Adversary. 2016. ar Xiv: 1511.05897 [cs.LG]. [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: 4or 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. ar Xiv: 1811.02540 [cs.LG]. [29] Yuan Gao and Christian Kroer. First-Order Methods for Large-Scale Market Equilibrium Computation . In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, Neur IPS 2020, December 6-12, 2020, virtual. Ed. by Hugo Larochelle et al. 2020. URL: https://proceedings.neurips.cc/paper/ 2020/hash/f75526659f31040afeb61cb7133e4e6d-Abstract.html. [30] Gauthier Gidel et al. A Variational Inequality Perspective on Generative Adversarial Networks. 2020. ar Xiv: 1802.10551 [cs.LG]. [31] Denizalp Goktas, Enrique Areyan Viqueira, and Amy Greenwald. A Consumer-Theoretic 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-Dual Methods for Convex-Concave Saddle Point Problems. 2018. ar Xiv: 1806.04118 [math.OC]. [33] Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm for general convex-concave saddle point problems . In: ar Xiv preprint ar Xiv:1803.01401 2 (2018). [34] Charles R. Harris et al. Array programming with Num Py . In: Nature 585 (2020), pp. 357 362. DOI: 10.1038/s41586-020-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 al. stests: Package with useful statistical tests. R package version 0.1.0. 2021. URL: https://fhernanb.github.io/stests. [37] J. D. Hunter. Matplotlib: A 2D graphics environment . In: Computing in Science & Engineering 9.3 (2007), pp. 90 95. DOI: 10.1109/MCSE.2007.55. [38] Adam Ibrahim et al. Lower bounds and conditioning of differentiable games . In: ar Xiv preprint ar Xiv:1906.07300 (2019). [39] Tatsuro Ichiishi. 4 - Noncooperative Behavior and Equilibrium . In: Game Theory for Economic Analysis. Ed. by Tatsuro Ichiishi. Economic Theory, Econometrics, and Mathematical Economics. San Diego: Academic Press, 1983, pp. 55 76. ISBN: 978-0-12-3701800. DOI: https : / / doi . org / 10 . 1016 / B978 - 0 - 12 - 370180 - 0 . 50009 - 3. URL: https : / / www . sciencedirect . com / science / article / pii / B9780123701800500093. [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 Optimization? 2020. ar Xiv: 1902.00618 [cs.LG]. [42] Anatoli Juditsky, Arkadi Nemirovski, et al. First order methods for nonsmooth convex largescale optimization, ii: utilizing problems structure . In: Optimization for Machine Learning 30.9 (2011), pp. 149 183. [43] Hamed Kebriaei and Luigi Iannelli. Discrete-time robust hierarchical linear-quadratic 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-concave minimax problems . In: International Conference on Machine Learning. PMLR. 2020, pp. 6083 6093. [46] Tianyi Lin, Chi Jin, and Michael I 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 nonconvex min-max problems: algorithms and applications in signal processing and communications . In: ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2019, pp. 4754 4758. [48] David Madras et al. Learning Adversarially Fair and Transferable Representations. 2018. ar Xiv: 1802.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(0x4cf9c5c0). URL: https://ideas.repec.org/b/oxp/obooks/9780195102680.html. [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-gradient Methods in Smooth Convex-Concave Saddle Point Problems. 2020. ar Xiv: 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 gesellschaftsspiele . In: Mathematische annalen 100.1 (1928), pp. 295 320. [56] Nam Ho-Nguyen and Fatma Kilinc-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.1017/CBO9780511800481. [58] Maher Nouiehed et al. Solving a class of non-convex min-max games using iterative first order methods . In: ar Xiv preprint ar Xiv:1902.08297 (2019). [59] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of firstorder nash equilibria in nonconvex-concave smooth min-max problems . In: ar Xiv preprint ar Xiv:2002.07919 (2020). [60] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. 2018. ar Xiv: 1808.02901 [math.OC]. [61] Krzysztof Postek and Shimrit Shtern. First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation. 2021. ar Xiv: 2101.02669 [math.OC]. [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: http://www.R-project.org/. [64] Hassan Rafique et al. Non-Convex Min-Max Optimization: Provable Algorithms and Applications in Machine Learning. 2019. ar Xiv: 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. ar Xiv: 1802.08249 [cs.LG].

[67] Maziar Sanjabi et al. On the Convergence and Robustness of Training GANs with Regularized 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. ar Xiv: 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. DOI: https://doi.org/ 10.1016/j.eswa.2012.05.059. URL: https://www.sciencedirect.com/ science/article/pii/S0957417412007750. [70] K. Shimizu and E. Aiyoshi. A new computational method for Stackelberg and min-max problems by use of a penalty method . In: IEEE Transactions on Automatic Control 26.2 (1981), pp. 460 466. DOI: 10.1109/TAC.1981.1102607. [71] K. Shimizu and E. Aiyoshi. Necessary conditions for min-max problems and algorithms by a relaxation procedure . In: IEEE Transactions on Automatic Control 25.1 (1980), pp. 62 66. DOI: 10.1109/TAC.1980.1102226. [72] Aman Sinha et al. Certifying Some Distributional Robustness with Principled Adversarial Training. 2020. ar Xiv: 1710.10571 [stat.ML]. [73] The pandas development team. pandas-dev/pandas: Pandas. Version latest. Feb. 2020. DOI: 10.5281/zenodo.3509134. URL: https://doi.org/10.5281/zenodo. 3509134. [74] Kiran Koshy Thekumparampil et al. Efficient Algorithms for Smooth Minimax Optimization. 2019. ar Xiv: 1907.01543 [math.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 Mathematics 60.1 (1995). Proceedings of the International Meeting on Linear/Nonlinear Iterative Methods and Verification of Solution, pp. 237 252. ISSN: 0377-0427. DOI: https://doi.org/10.1016/0377-0427(94) 00094-H. URL: https://www.sciencedirect.com/science/article/pii/ 037704279400094H. [77] Guido Van Rossum and Fred L Drake Jr. Python tutorial. Centrum voor Wiskunde en Informatica Amsterdam, The Netherlands, 1995. [78] Heinrich Von Stackelberg. Marktform und gleichgewicht. J. 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.

jstor.org/stable/1969022. [80] Léon Walras. Elements of Pure Economics; or, The Theory of Social Wealth. Translated by William Jaffé. Vol. 2. Orion Editions, 1969, pp. 457 458. [81] Hadley Wickham et al. Welcome to the tidyverse . In: Journal of Open Source Software 4.43 (2019), p. 1686. DOI: 10.21105/joss.01686. [82] Depeng Xu et al. Fair GAN: Fairness-aware Generative Adversarial Networks. 2018. ar Xiv: 1805.11202 [cs.LG]. [83] Laura Scrimali Yurii Nesterov. Solving strongly monotone variational and quasi-variational inequalities . In: Discrete & Continuous Dynamical Systems 31.4 (2011), pp. 1383 1396. [84] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On Lower Iteration Complexity Bounds for the Saddle Point Problems. 2020. ar Xiv: 1912.07481 [math.OC]. [85] Renbo Zhao. A Primal Dual Smoothing Framework for Max-Structured Nonconvex Optimization. 2020. ar Xiv: 2003.04375 [math.OC]. [86] Renbo Zhao. Optimal algorithms for stochastic three-composite convex-concave saddle point problems . In: ar Xiv preprint ar Xiv:1903.01687 (2019).