# fisher_markets_with_social_influence__f7a9f1d4.pdf

Fisher Markets with Social Influence

Jiayi Zhao1, Denizalp Goktas2, Amy Greenwald2

1 Department of Computer Science, Pomona College 2 Department of Computer Science, Brown University jzae2019@mymail.pomona.edu, denizalp goktas@brown.edu, amy greenwald@brown.edu

A Fisher market is an economic model of buyer and seller interactions in which each buyer s utility depends only on the bundle of goods she obtains. Many people s interests, however, are affected by their social interactions with others. In this paper, we introduce a generalization of Fisher markets, namely influence Fisher markets, which captures the impact of social influence on buyers utilities. We show that competitive equilibria in influence Fisher markets correspond to generalized Nash equilibria in an associated pseudo-game, which implies the existence of competitive equilibria in all influence Fisher markets with continuous and concave utility functions. We then construct a monotone pseudo-game, whose variational equilibria and their duals together characterize competitive equilibria in influence Fisher markets with continuous, jointly concave, and homogeneous utility functions. This observation implies that competitive equilibria in these markets can be computed in polynomial time under standard smoothness assumptions on the utility functions. The dual of this second pseudo-game enables us to interpret the competitive equilibria of influence CCH Fisher markets as the solutions to a system of simultaneous Stackelberg games. Finally, we derive a novel first-order method that solves this Stackelberg system in polynomial time, prove that it is equivalent to computing competitive equilibrium prices via tˆatonnement, and run experiments that confirm our theoretical results.

Introduction The branch of mathematical economics that attempts to explain the behavioral relationship among supply, demand, and prices via equilibria dates back to the work of French economist (Walras 1896), and today is known as general equilibrium theory (Mas-Colell, Whinston, and Green 1995). One of the seminal achievements in this area is the proof of existence of competitive equilibrium prices in Arrow-Debreu markets (1954). In such a market, traders seek to purchase goods from others, by exchanging a part of their endowment of goods for various other goods. A competitive equilibrium comprises an allocation of goods to traders together with good prices such that traders maximize their preferences over goods while ensuring that their spending does not exceed the value of their endowment, and the market clears: i.e., no more goods are allocated than the

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

market supply and Walras law holds, meaning the value of demand equals the value of supply. In much of mainstream consumer theory (Mas-Colell, Whinston, and Green 1995), and in Arrow-Debreu markets, each trader s preference depends only on its own consumption. Such models fail to capture the influence of social interactions on traders interests. For example, the more friends one has who own an i Phone, the more one might prefer an i Phone. Likewise, if a celebrity, e.g., Beyonce, wears a particular brand of bag, e.g., Telfar, then one s preference for that brand of bag might increase. In an age of densifying social networks, it is becoming more and more essential that our economic models capture the effects of social interactions on individuals preferences. To try to better understand the implications of social networks on market equilibria, Chen and Teng (2011) recently proposed an extension of the Arrow-Debreu market model in which each trader s preference is influenced by the goods her neighbors obtains: the Arrow-Debreu market with social influence. Formally, Chen and Teng s model augments an Arrow-Debreu market with a social network connecting the traders, and then embeds this network s structure in each trader s utility function, thus inducing a preference relation over allocations of goods that depends both on the trader s and its neighbors allocations. The authors then study a modest generalization of competitive equilibrium in which traders maximize their utility, assuming the allocations of the other traders in the market, including their neighbors, are fixed. Chen and Teng analyze their model under two specific types of utilities: linear and threshold influence functions. They prove existence of competitive equilibrium in their setting, when the graph underlying the economy is strongly connected and the utility functions parameters guarantee non-satiation of the preferences they represent. Under additional assumptions on the topology of the network, they also provide polynomial-time methods for computing competitive equilibria. As the computation of competitive equilibrium in Arrow Debreu markets is believed to be intractable, i.e., it is PPADcomplete (Chen and Deng 2006; Chen and Teng 2009), it seems unlikely that we can obtain positive computational results in such a broad setting. In the last two decades, however, Fisher markets have emerged as an interesting special

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

case of Arrow-Debreu markets in which competitive equilibria can be efficiently computed. The Fisher market is a one-sided Arrow-Debreu market comprising one seller and multiple buyers, the latter of whom are endowed with an artificial currency called their budget, rather than an endowment of goods. During the last two decades, a wide array of polynomialtime computability results have been established for Fisher markets (Devanur et al. 2002; Jain, Vazirani, and Ye 2005; Gao and Kroer 2020; Goktas and Greenwald 2021). One of the most interesting findings is the observation that the primal and dual solutions, respectively, to the Eisenberg Gale convex program (Eisenberg and Gale 1959), constitute competitive equilibrium allocations and prices in Fisher markets, and are computable in polynomial time assuming buyers with continuous, concave, and homogeneous utility functions representing locally non-satiated preferences (Devanur et al. 2002; Devanur et al. 2008; Jain, Vazirani, and Ye 2005). Moreover, Cheung, Cole, and Devanur show that solving the dual of the Eisenberg-Gale program via (sub)gradient descent amounts to solving the market via tˆatonnement, an economic price-adjustment process dating back to Walras (1896), in which a fictional auctioneer increases (resp. decreases) the prices of goods that are overdemanded (resp. underdemanded) (Cheung, Cole, and Devanur 2013). Furthermore, Goktas and Greenwald (2021) show that the dual of the Eisenberg-Gale program corresponds to a zero-sum Stackelberg game, in which tˆatonnement surfaces as a no-regret learning dynamic for the auctioneer (Goktas, Zhao, and Greenwald 2022). With the aim of obtaining stronger results on the existence and computation of competitive equilibrium in markets with social influence, we introduce a special case of the Arrow Debreu market with social influence and a generalization of Fisher markets (Brainard, Scarf et al. 2000), which we call Fisher markets with social influence, or influence Fisher markets for short. An influence Fisher market, as the name suggests, is a Fisher market in which buyers utility functions depend not only on their own allocation, but also on their neighbors . In this paper, we provide existence and polynomial-time computability results for competitive equilibrium in influence Fisher markets. We first extend Arrow and Debreu s competitive equilibrium existence argument using their theory of pseudo-games to prove that a competitive equilibrium exists in all influence Fisher markets with continuous utility functions that are concave in each buyer s allocation. Contrary to Chen and Teng, our existence result makes no assumptions about the topology of the network. Next, for all influence Fisher markets with continuous and homogeneous utilities, we construct a similar pseudogame with jointly convex constraints whose variational equilibria correspond to competitive equilibrium allocations. This pseudo-game is monotone assuming the buyers utility functions are jointly-concave); thus, we can solve for its variational equilibria as a variational inequality problem (Facchinei, Fischer, and Piccialli 2007). This approach yields a polynomial-time algorithm that computes competitive equilibrium allocations in influence Fisher markets. Moreover, as the pseudo-game comprises n different opti-

mization problems, one per buyer, there are correspondingly n duals. Surprisingly, the solutions to all of these duals yield the same competitive equilibrium prices! Finally, following Goktas and Greenwald (2021), who reformulate the dual of the Eisenberg-Gale program as a zerosum Stackelberg game, we likewise reformulate the n duals of our pseudo-game as a system of n simultaneous zerosum Stackelberg games. In Goktas and Greenwald s dual, the leader is a fictitious auctioneer who sets prices, while the followers are a set of buyers who effectively play as a team; in our n duals, each leader is again a fictitious auctioneer, but each follower is an individual buyer who best responds to the auctioneer s prices, given the other buyers allocations. Thus, the buyers in this system play a Nash equilibrium. Also following Goktas and Greenwald, we show that running subgradient descent on each leader s value function, i.e., the leader s utility function assuming the follower bestresponds, amounts to solving the market via tˆatonnement in polynomial-time, as in (standard) Fisher markets. The main difference between our algorithm and theirs is that ours requires a Nash-equilibrium oracle, so that, given prices and the other buyers allocations, buyers can play best responses to one another.

Related Work Gao and Kroer (2020) 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; such methods can be more efficient when markets are large. Following Arrow and Debreu s introduction of GNE, Rosen (1965) initiated the study of the mathematical and computational properties of GNE in pseudo-games with jointly convex constraints, proposing a projected gradient method to compute GNE. Thirty years later, Uryas ev and Rubinstein (1994) developed the first relaxation methods for finding GNEs, which were improved upon in subsequent works (Krawczyk and Uryasev 2000; Heusinger and Kanzow 2009). Two other types of algorithms were also introduced to the literature: Newton-style methods (Facchinei, Fischer, and Piccialli 2009; Dreves 2017; von Heusinger, Kanzow, and Fukushima 2012; Izmailov and Solodov 2014; Fischer et al. 2016; Dreves et al. 2013) and interior-point potential methods (Dreves et al. 2013). Many of these approaches are based on minimizing the exploitability of the pseudo-game, but others use variational inequality (Facchinei, Fischer, and Piccialli 2007; Nabetani, Tseng, and Fukushima 2011) and Lemke methods (Schiro, Pang, and Shanbhag 2013). Recently, this literature has established convergence guarantees for exploitability minimization (Goktas and Greenwald 2022) and relaxation (Jordan, Lin, and Zampetakis 2023) methods.

Preliminaries

In this section, we define our main modeling tool, pseudogames, and then we introduce our object of study, Fisher markets with social influence, as a particular pseudo-game.

Notation We use caligraphic uppercase letters to denote sets and set correspondences (e.g., X); bold lowercase letters to denote vectors (e.g., p, π); bold uppercase letters to denote matrices and vector-valued random variables (e.g., X, Γ); lowercase letters to denote scalar quantities (e.g., x, γ); and uppercase letters to denote scalar-valued random variables (e.g., X, Γ). 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 lowercase letter with subscript j (e.g., pj or xij). Lowercase letters also denote functions: e.g., f if the function is scalar valued, and f if the function is vector valued. We denote the vector of ones of size n by 1n, the set of integers {1, . . . , n} by [n], the set of natural numbers by N, the set of real numbers by R, and the postive and strictly positive elements of a set by a + and ++ subscript, respectively, e.g., R+ and R++. Finally, we denote the orthogonal projection operator onto a set C by ΠC, i.e., ΠC(x) = arg miny C x y 2.

Pseudo-games A (concave) pseudo-game (Arrow and Debreu 1954) G .= (n, A, X, g, F) comprises n N+ players, each i [n] of whom chooses an action ai Ai Rm, with the players joint action space A = i [n] Ai. Each player i aims to maximize their continuous utility fi : A R, which is concave in ai, by choosing a feasible action from a set of actions Xi(a i) Ai determined by the actions a i A i R(n 1)m of the other players, where Xi : A i Ai is a non-empty, continuous, compactand convex-valued action correspondence. We represent each such correspondence as a set Xi(a i) = {ai Ai | gik(ai, a i) 0, for all k [d]}, where gik is a continuous and concave function in ai that defines the constraints. Additionally, overloading notation, we define the the joint action correspondence X is simply a set of jointly feasible action profiles, namely {a A | g(a) 0}, where g = (g1, . . . , gn). If gik : A R is also concave in a A, then we say that the pseudo-game has jointly convex constraints, in which case, X is simply a convex set. A pseudo-game is called monotone1 if for all x, y A, P i [n] aifi(x) aifi(y) T (xi yi) 0. Finally, a (concave) game (Nash 1950) is a pseudo-game where, for all players i [n], Xi is a constant correspondence, i.e., for all players i [n], Xi(a i) = Xi(b i), for all a, b A. Given a pseudo-game G, an ε-generalized Nash equilibrium (GNE) is an action profile a X(a ) s.t. for all i [n] and ai Xi(a i), fi(a ) fi(ai, a i) ε. An εvariational equilibrium (VE) (or ϵ-normalized GNE) of a pseudo-game with joint constraints is an action profile a X s.t. for all i [n] and a X, fi(a ) fi(ai, a i) ε. A GNE (VE) is an ε-GNE (VE) with ε = 0. While GNE

1We call a pseudo-game monotone if ( a1u1, . . . , anun) is a monotone operator. Such pseudo-games are also sometimes called dissipative, since ( a1u1, . . . , anun) is called a dissipative operator if ( a1u1, . . . , anun) is a monotone operator.

are guaranteed to exist in all pseudo-games under standard assumptions (see Theorem 16), VE are only guaranteed to exist in pseudo-games with jointly convex constraints (see Theorem 17) (Arrow and Debreu 1954).

Fisher Markets with Social Influence

In this paper, we study a model of Fisher markets with social influence, in which a buyer s utility may be influenced by the goods allocated to her neighbors. A Fisher market with social influence, or an influence Fisher market for short, comprises n N+ buyers and m N+ divisible goods. Without loss of generality, we assume that exactly one unit of each good j [m] is available. The buyers are connected through a directed social influence graph G = (V, E), where V = [n] is the set of buyers, and for any i, i [n], there is an edge from i to i iff the utility of i is influenced by the allocation xi of i . We let NG(i) = {i | (i , i) E} be the (incoming, and hence influential) neighbors of a buyer i, and we define ki = |NG(i)|, for all i [n]. Each buyer i [n] has a budget bi R+ and a utility function ui : R(ki+1) m + R that depends on not only her own allocation, but also her neighbors . An instance of an influence Fisher market is thus given by a tuple (n, m, G, U, b), where G is the social network, U = {u1, . . . , un} is a set of utility functions, one per buyer, and b Rn + is a vector of buyer budgets. When n and m are clear from context, we denote influence Fisher markets simply by (G, U, b). Given an influence Fisher market (G, U, b), an allocation X = (x1, . . . , xn)T Rn m + is a map from goods to buyers, represented as a matrix, s.t. xij 0 denotes the amount of good j [m] allocated to buyer i [n]. Likewise, we denote by x NG(i) = (xi )T i NG(i) Rki m + the matrix representing the bundles of goods obtained by buyer i s neighbors. A utility function is locally non-satiated if for all xi Rm +, x NG(i) Rki m + , and ε > 0, there exists an x i Rm + with x i xi ε such that ui(x i, x NG(i)) > ui(xi, x NG(i)). Related, a utility function satisfies no saturation if xi Rm + and x NG(i) Rki m + , there exists an x i Rm + such that ui(x i, x NG(i)) > ui(xi, x NG(i)). Note that if ui is quasi-concave in xi and satisfies no saturation, then it is locally non-satiated (Arrow and Debreu 1954). Feasibility asserts that no more of any good j is allocated than its available supply, i.e., j [m], P i [n] x ij 1. Walras law states that, if a good j is not fully allocated, then its price must be zero; equivalently, if a good s price is positive, then it must be fully allocated. Mathematically, P j [m] p j(P i [n] x ij 1) = 0. A tuple (X , p ), which consists of an allocation X and prices p = (p 1 . . . , p m)T Rm +, is a competitive equilibrium (CE) in an influence Fisher market (G, U, b) if (1) fixing other buyers allocations, buyers maximize their utilities constrained by their budget, i.e., i [n], x i arg maxxi Rm + :xi p bi ui(xi, x NG(i)), and (2) feasibility and Walras law hold.

A Fisher market is a special influence Fisher market (G, U, b) where G = (V, E) satisfies E = . In other words, each buyer i is isolated, so her utility ui : Rm + R+ depends only on her own allocation. As G is simply a graph with n vertices and no edges, we can denote a Fisher market by the tuple (U, b). When U is a set of specific utility functions, we refer to the influence Fisher market (G, U, b) by the name of the utility function: e.g., if U is a set of linear utility functions then (G, U, b) is a linear influence Fisher market.

Existence of Competitive Equilibrium via Pseudo-Games

In this section, we investigate the properties of competitive equilibrium in Fisher markets with social influence. Our main tool is the pseudo-game (or abstract economy) model introduced by Arrow and Debreu, as both a generalization of the standard normal-form game in game theory and of the Arrow-Debreu market in microeconomics (Arrow and Debreu 1954). We provide a proof of existence of competitive equilibrium in influence Fisher markets, using methods similar to those employed by Arrow and Debreu in their seminal proof of the existence of competitive equilibria in Arrow Debreu economies. Following Arrow and Debreu, we define a pseudo-game with an auctioneer who sets prices. Our pseudo-game then both generalizes and specializes theirs. While in theirs, each trader s utility depends only on their own allocations, ours captures social influence through augmented utility functions. While in theirs, buyers are constrained by their endowment, in ours, buyers are constrained by budgets. Specifically, we construct an auctioneer-buyer pseudogame comprising a single auctioneer and n individual buyers in which the auctioneer sets the good prices, while the buyers choose their allocations. Given an allocation X Rn m, let z = P i [n] xi 1m be the vector of excess demands, i.e., the total amount by which the demand for each good exceeds its supply. In our auctioneerbuyer pseudo-game, each buyer i chooses allocations xi that maximize her utility subject to her budget constraint, given prices p determined by the auctioneer, the auctioneer chooses prices that maximize her total profit, i.e., p z, fixing the allocation X, subject to Walras law. More specifically, we assume a numeraire (i.e., a good whose price we normalize to 1), and we view the buyers budgets as quantities of this numeraire, in which case Walras law can be restated as the sum of the prices being equal to the sum of the budgets: i.e., P j [m] pj = P i [n] bi. In what follows, we show that the set of GNE in this auctioneer-buyer pseudo-game corresponds to the set of CE in an influence Fisher market; existence of a CE thus follows from existence of GNE. Importantly, in this pseudo-game we require the auctioneer to choose prices whose sum is equal to the sum of the budgets, because the budgets correspond are a numeraire good, i.e., their price is set to 1 (this is without loss of generality since in any Arrow-Debreu market only the propor-

tions of the prices to one another matters), hence the prices of every other good have to be scaled appropriately, i.e., by the sum of the budget, so as to preserve the internal consistency of the Arrow-Debreu price system that emerges at the competitive equilibrium prices (since Arrow-Debreu assume wlog that prices are in the unit simplex).

Assumption 1. An influence Fisher market (G, U, b) satisfies, for all buyers i [n], ui is 1. continuous in (xi, x NG(i)), 2. concave in xi, and 3. satisfies no saturation.

Definition 2 (Auctioneer-Buyer Pseudo-game). Let (G, U, b) be an influence Fisher market. The corresponding auctioneer-buyer pseudo-game G = (n + 1, A, X, g, F) is defined by

an auctioneer and n buyers. Each buyer chooses an allocation xi Ai = Rm +, while the auctioneer chooses prices p An+1 = Rm +. For all buyers i [n], the feasible action set given the actions of other players is Xi(x i, p) = {xi Ai | g(xi, x i, p) = bi xi p 0}. For the auctioneer, the feasible action set is the fixed set Xn+1 = {p An+1 | p 1m = b 1n}. For all players i [n + 1], i maximizes her utility fi : i [n+1] Ai R, defined by fi(X, p) = ui(xi, x NG(i)), for the buyers i [n], and fn+1(X, p) = p z for the auctioneer.

Next, we prove the existence of CE in influence Fisher markets that satisfy Assumption 1.2

Theorem 3. The set of competitive equilibria of any influence Fisher market (G, U, b) that satisfies Assumption 1 is equal to the set of generalized Nash equilibria of the associated auctioneer-buyer pseudo-game G = (n + 1, A, X, g, F).

Existence of a CE in an influence Fisher market now follows immediately from existence of GNE in pseudo-games:

Corollary 4. There exists a CE (X , p ) in all influence Fisher markets (G, U, b) satisfying Assumption 1.

Computation of Competitive Equilibrium via Pseudo-Games Although we have established the existence of competitive equilibrium in all influence Fisher markets with continuous and concave utility functions, the proof itself provides little insight into equilibrium computation, as computing a GNE is PPAD-hard in general (Daskalakis, Goldberg, and Papadimitriou 2009). In order to gain further computational insights, we focus on a subset of influence Fisher markets in which each buyer s utility function is also homogeneous in its own allocation. A utility function ui is homogeneous in xi Rm + if ui(xi, x NG(i)) is homogeneous for all x NG(i) Rki m + , i.e., ui(λxi, x NG(i)) = λui(xi, x NG(i)), for all λ 0. As above, we also assume continuity and concavity. We call

2Proofs of all theorems appear in the appendix.

utility functions that satisfy all three of these assumptions CCH utility functions, and Fisher markets inhabited by buyers with such utility functions CCH Fisher markets. We can compute competitive equilibria in CCH Fisher markets (without social influence) via the Eisenberg-Gale convex program and its dual (Eisenberg and Gale 1959). To generalize this convex program to CCH influence Fisher markets, we propose another pseudo-game, which we call the buyer (only) pseudo-game, that is jointly convex, and whose variational equilibria correspond to CE allocations. Moreover, we observe that the dual of this pseudo-game simultaneously characterizes CE prices. In other words, while the auctioneer-buyer pseudo-game explicitly models an auctioneer who updates prices in response to the buyers behavior, in the buyer (only) pseudo-game, the auctioneer is fictitious, as it is implicit in the dual. If (U, b) is a CCH Fisher market, then an optimal solution X to the Eisenberg-Gale program (Eq. 1) constitutes a CE allocation, and an optimal solution to the Lagrangian that represents the feasibility constraints (Eq. 1a) are the corresponding equilibrium prices (Devanur et al. 2002; Jain, Vazirani, and Ye 2005).

max X Rn m +

i [n] bi log(ui(xi)) (1)

subject to j [m], X

i [n] xij 1 (1a)

In Fisher markets (without social influence), each buyer s utility maximization problem is independent of the others , as each depends only on the buyer s own allocation. The Eisenberg-Gale program takes advantage of this independence. It takes an aggregate perspective, maximizing the sum of the buyers utilities subject to their feasibility constraints, and nonetheless computes an optimal allocation that maximizes each buyer s individual utility. In influence Fisher markets, however, where this independence assumption does not hold, we can no longer compute CE from this aggregate perspective. In our solution CE as the VE of a jointly-convex pseudo-game each buyer maximizes her own utility, subject to a shared feasibility constraint. Note that the only players in this buyer pseudo-game are the n buyers; there is no auctioneer updating prices based on the buyers behavior.

Definition 5 (Buyer Pseudo-game). Let (G, U, b) be an influence Fisher market. The corresponding jointly-convex buyer pseudo-game G = (n, A, X, g, F) is defined by

For all buyers i [n], Ai = Rm +. For all buyers i [n], the feasible action set given the actions of other players is Xi(x i) = {xi Ai | g(xi, x i) = 1 P i [n] xi 0}.

For all buyers i [n], i maximizes her utility fi : i [n] Ai R defined by fi(X) = bi log(ui(xi, x NG(i))).

Assumption 6. For each buyer i [n], ui is 1. continuous in (xi, x NG(i)); and 2. concave and homogeneous3 in xi.

Theorem 7. Let (G, U, b) be an influence Fisher market satisfying Assumption 6. Then, X is a CE allocation of (G, U, b) if and only if it is a variational equilibrium (VE) of the corresponding buyer pseudo-game G = (n, A, X, g, F). Moreover, if X is a VE of the buyer pseudo-game, then the corresponding KKT conditions are satisfied with optimal Langrange multipliers λ 1 = . . . = λ n = p , which correspond to CE prices.

The construction of competitive equilibrium via the auctioneer-buyer pseudo-game (Theorem 3) is more general than the construction of competitive equilibrium via the buyer pseudo-game (Theorem 7); however, the existence of the auctioneer precludes monotonicity, and hence polynomial-time computability. To obtain efficient algorithms, we assume the buyers utilities are concave not only in their own allocations but in one another s allocations as well, which implies monotonicity. We also require twicecontinuous differentiability.

Assumption 8. For each buyer i [n], 1. The conditions in Assumption 6, and 2. ui is jointly concave: i.e., concave in (xi, x NG(i)), and 3. and twice-continuously differentiable in (xi, x NG(i)).

Under Assumption 8, an influence Fisher market can be expressed as a monotone variational inequality. There exist methods that converge in last iterates4 to a solution of any monotone variational inequality at a rate of O(1/T) (e.g., Gorbunov, Loizou, and Gidel (2022)). Our next theorem follows from these two assertions:

Theorem 9. There exist methods that converge in last iterates to the CE allocations of influence Fisher markets at a rate of O(1/T) under Assumption 8. In such markets, approximate competitive equilibrium allocations can be computed in polynomial time.

Computation of Competitive Equilibrium via Stackelberg Games

Recently, Cole and Tao (2019) presented a generalization of the Eisenberg-Gale dual for arbitrary CCH utility functions, which accurately characterizes competitive equilibrium prices, but fails to match the optimal objective value of the Eisenberg-Gale primal. Building on their results, Goktas, Viqueira, and Greenwald (2021) derived the exact Eisenberg-Gale dual, for which strong duality holds.

3We note that homogeneity implies no saturation, since for all x Rm + and x NG(i) Rki m + , there exists an allocation (1 + ε)x for some ϵ > 0 s.t. ui((1 + ε)x, x NG(i)) = (1 + ε)ui(x, x NG(i)) > ui(x, x NG(i)). 4Solodov and Svaiter (1999) and Ryu, Yuan, and Yin (2019) also provide methods that guarantee average-iterate convergence with this same rate in monotone variational inequalities.

j [m] pj + X

i [n] bi log (ui(x i )) bi (2)

s.t. i [n], x i arg max xi Rm + :xi p bi ui(xi) (2a)

We begin this section by deriving the duals of our buyer pseudo-game. In the buyer pseudo-game G, each buyer is solving an optimization problem (Equation (3)) in which they maximize their utility function by choosing an optimal action in their feasible action set, given the other buyers VE actions. Based on this observation, we can derive the dual of our buyer pseudo-game; but as our pseudo-game comprises n different optimization problems, one for each buyer i [n], instead of just one dual, we have n duals. Moreover, because any VE of a jointly-convex pseudo-game satisfies the corresponding KKT conditions with optimal Langrange multipliers λ 1 = . . . = λ n (Theorem 19 (Facchinei, Fischer, and Piccialli 2009)), all n duals yield the same CE prices! In other words, just as the dual of Eisenberg-Gale program characterizes the CE prices of a Fisher market, the n duals of our pseudo-game characterize the CE prices of an influence Fisher market (satisfying Assumption 6). Theorem 10. Let (G, U, b) be an influence Fisher market satisfying Assumption 6, and let G be the corresponding buyer pseudo-game G = (n, A, X, g, F). For each buyer i [n], fixing its neighbors allocations x NG(i), the dual of i s optimization problem,

max xi Rm + :xi+P

k =i x k 1 bi log(ui(xi, x NG(i))) (3)

is given by

+ bi log(ui(x i , x NG(i))) bi

(4) s.t. x i arg max xi Rm + :xi p bi ui(xi, x NG(i)) (4a)

Goktas and Greenwald (2021) further show that the dual of the Eisenberg-Gale program can be re-expressed as the solution to the following zero-sum convex-concave Stackelberg game characterizes the CE of any CCH Fisher market:

min p Rm + max X Rn m + :X p b

j [m] pj + X

i [n] bi log(ui(xi)) (5)

The leader in this game is a fictitious auctioneer (i.e., price setter), while the follower represents a set of buyers who effectively play as a team. The objective function is the sum of the auctioneer s welfare (i.e., the sum of the prices) and the buyers Nash social welfare. Goktas and Greenwald also derive a first-order method that solves this game, which, via the aforementioned interpretation, can be understood as computing a competitive equilibrium of a Fisher market via tˆatonnement.

We argue that competitive equilibria in influence Fisher markets can likewise be characterized via Stackelberg equilibria. This more general setting requires not just one, but a system of n zero-sum convex-concave Stackelberg games (Goktas and Greenwald 2021), one per buyer. In each game, the leader once again is a fictitious auctioneer (i.e., price setter), but the follower is just an individual buyer, not the set of all buyers. Moreover, in each buyer s Stackelberg game, the objective function is the sum of the auctioneer s revenue (i.e., the sum of the good prices, each one discounted by the supply available to buyer i beyond what has been claimed by the others) and the individual buyer s utility. These n Stackelberg games are played simultaneously with the fictitious auctioneer optimizing prices assuming all the buyers simultaneously best respond (i.e., play a Nash equilibrium), and the buyers best respond to the auctioneer s prices, given the other buyers allocations.

Definition 11 (Buyer i s Stackelberg Game). Let (G, U, b) be an influence Fisher market. The corresponding Stackelberg game for buyer i is defined by

min p Rm + max xi Rm + :xi p bi

bi log(ui(xi, x NG(i))) (6)

The following corollary follows from Theorems 7 and 10.

Corollary 12. (X , p ) is a competitive equilibrium of an influence CCH Fisher market (G, U, b) satisfying Assumption 6 iff (x i , p ) is a Stackelberg equilibrium in buyer i s Stackelberg game, for all buyers i [n].

Proof. For all i [n], (x i , p ) is a Stackelberg equilibrium in buyer i s Stackelberg game iff (x i , p ) solves

+ bi log(ui(x i , x NG(i))) bi

s.t. x i arg max xi Rm + :xi p bi ui(xi, x NG(i)) (7)

By Theorem 10, p is a solution to this bi-level optimization problem (Equation (4)) iff x i is a solution to buyer i s optimization problem (Equation (3)) in the buyer pseudogame corresponding to (G, U, b). Finally, by Theorem 7, (X , p ) is a competitive equilibrium of (G, U, b).

Our Stackelberg game formulation of CE in influence Fisher markets enables us to compute CE by solving a system of buyer Stackelberg games: i.e., solving for a Stackelberg equilibrium in each of the buyer Stackelberg games together with a Nash equilibrium among the buyers in the system. Towards that end, for convenience, we define the objective function for buyer i s Stackelberg game:

fi(xi, p) := X

+ bi log(ui(xi, x NG(i)))

and the ith (fictional) auctioneer s value function in buyer i s Stackelberg game:

Vi(p) := max xi Rm + :xi p bi

+ bi log(ui(xi, x NG(i))) (9)

Moreover, while each buyer is playing a Stackelberg game with its fictitious auctioneer, all buyers are also playing an n-buyer simultaneous game with one another, in which each buyer maximizes its objective function fi(xi, p) (Equation (8)), given the prices p set by the auctioneer and the other buyers allocations. We can characterize a Nash equilibrium of this n-buyer game as follows:

x i arg max xi Rm + :xi p bi

+ bi log(ui(xi, x NG(i))) (10)

= arg max xi Rm + :xi p bi ui(xi, x NG(i)) (10a)

As the first summand in Equation 10 and bi are constants (i.e., they do not depend on xi), and log is a monotonic function, buyer i simply seeks to maximize its utility subject to its budget constraint. Using a subdifferential envelope theorem (Goktas and Greenwald 2021), we now derive the subgradient of each auctioneer s value function Vi (Equation (9)). Theorem 13. Given an influence CCH Fisher market (G, U, b), the subdifferential of the ith auctioneer s value function in buyer i s Stackelberg game (Equation (9)) at given prices p is equal to the negative excess demand at p: i.e., p Vi(p) = 1 P i [n] x i .

Interestingly, this subgradient turns out to equal the negative excess demand in the market at the given prices. As excess demand is an aggregate quantity, it is independent of buyer i. Indeed, the subgradients of all the fictional auctioneers are the same; so there is effectively just one auctioneer. Based on this observation, we now present our Nash Equilibrium (NE)-oracle gradient descent algorithm (Algorithm 1), which follows the subgradient of the auctioneer s value function, assuming access to a NE-oracle. Given prices p Rm +, this oracle returns a Nash equilibrium X of the n-buyer concave game specified by Equation (10). The algorithm then runs subgradient descent on the auctioneer s value function. Overall, this approach corresponds to solving for a CE allocation and prices via tˆatonnement, assuming the NE oracle is exact. As NE-oracles are rarely exact, Algorithm 1 assumes a NE-oracle that finds a Nash equilibrium up to some approximation error δ. Finally, under standard assumptions (i.e., Assumption 8), the auctioneer s value function (Equation (9)) is convex and ℓV -Lipschitz continuous in p with ℓV = maxp Rm ++ p V (p) .5 These properties imply that our

5Although p V (p) is not necessarily bounded at p = 0, we can remedy this fact by shifting p by a small constant ε > 0, albeit losing some accuracy.

Algorithm 1: NE-Oracle Tˆatonnement For Influence Fisher Markets Inputs: G, U, b, p(0), η, δ Outputs: X , p

1: for t = 1, . . . , T do 2: Find X Rn m + with X p(t 1) b such that: 3: for all i [n], ui(x i, x NG(i)) ui(xi, x NG(i)) δ, 4: 5: for any xi Rm + satisfying xi p(t 1) bi 6: Set X(t) = X

7: Set p(t) = ΠRm + p(t 1) η(1 P i [n] x(t) i )

8: end for 9: return X(T ), p(T )

NE-oracle gradient descent algorithm converges to competitive equilibrium at a rate of O(1/

T). We include a more detailed statement of the following theorem in the appendix. Theorem 14. Algorithm 1 (i.e., tˆatonnement) converges to a competitive equilibrium in any influence CCH Fisher market (G, U, b) satisfying Assumption 8 at a rate of O(1/

T). Remark 15. We can implement an approximate NE oracle by computing the buyers equilibrium allocations via extragradient ascent (Gorbunov, Loizou, and Gidel 2022), which is guaranteed to converge to a Nash equilibrium at a rate of O(1/T), as the n-buyer concave game defined by Equation (10) is monotone. This observation gives rise to Algorithm 2 (see Appendix), which computes a competitive equilibrium in influence CCH Fisher markets in polynomial time.

Experiments We ran a series of experiments6 to see how the empirical convergence rates of Algorithm 1 compare to its theoretical guarantees under various utility structures. We considered three standard utility functions: linear, in which buyers practice utilitarian social welfare in their neighborhoods; Cobb-Douglas, in which practice Nash social welfare in their neighborhoods; and Leontief, in which practice egalitarian social welfare in their neighborhoods. Each utility structure endows the objective function (Equation (8)) and the value functions (Equation (9)) with different smoothness properties, which in turn varies the convergence properties of our algorithms. Let θi Rm be a vector of parameters that describes the utility function fi : Rm + R+ of buyer i [n]. We consider the following (standard) utility functions: for all i [n], 1. Linear: ui(xi, x NG(i)) = P k i NG(i) fk(xk), where fi(xi) = P j [m] θijxij 2. Cobb-Douglas: ui(xi, x NG(i)) = Q

k {i} NG(i) fk(xk), where fi(xi) = Q

j [m] xθij ij 3. Leontief: ui(xi, x NG(i)) = mink {i} NG(i) fk(xk),

where fi(xi) = minj [m] n xij θij

6We include a detailed description of our experimental setup in the Appendix.

Figure 1: In blue, we depict a trajectory of average value of the objective function across experiments (Equation (8)), for Algorithm 1 with EG as the NE-oracle, in randomly initialized linear, Cobb-Douglas, and Leontief Fisher markets with social influence. In red, we plot an arbitrary O(1/

T) function.

Assuming any of these three utility functions, we can solve for a Nash equilibrium among buyers by formulating a monotone variational inequality problem, and solving it via the extragradient method (EG) in O(1/T) iterations (Gorbunov, Loizou, and Gidel 2022). Then, by using EG as the NE-oracle, we can efficiently compute an optimal X (p) for any given p, which yields Algorithm 2 (see Appendix), a specific implementation of Algorithm 1. Figure 1 depicts the empirical convergence of Algorithm 1 with EG as the NE-oracle. We observe that convergence is fastest in influence Fisher markets with Cobb Douglas utilities, followed by linear, and then Leontief. For influence Fisher markets with 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 lead to a faster convergence rate than O(1/

T). On the other hand, for influence Fisher markets with linear utilities, we seem to obtain a tight convergence rate of O(1/

T), which seems plausible, as the value function is not differentiable assuming linear utilities, and hence we are unlikely to achieve a better convergence rate. Finally, influence Fisher markets with Leontief utilities, in which the objective function is not differentiable, are the hardest markets for our algorithm to solve. Nonetheless, we still observe a decent convergence rate, one that appears only slightly slower than O(1/

Conclusion In this paper, we studied a special case of Arrow-Debreu markets with social influence, which we call Fisher markets with social influence, or influence Fisher markets for short. First, we extended known results on the existence of competitive equilibrium in markets with social influence to a larger more natural class of markets. Our proof proceeds by reducing an influence Fisher market to an auctioneer-buyer pseudo-game such that every generalized Nash equilibrium in the pseudo-game is a competitive equilibrium of the influence Fisher market. The existence of generalized Nash

equilibrium in pseudo-games thus implies the existence of competitive equilibrium in influence Fisher markets. We then introduced a monotone jointly convex buyeronly pseudo-game as a generalization of the Eisenberg Gale program, whose variational equilibria correspond to the competitive equilibria in influence Fisher markets. In this pseudo-game, the duals of the individual buyers utilitymaximization problems constrained by the supply constraint comprise a system of n simultaneously-played zero-sum Stackelberg games, which simultaneously characterize the competitive equilibrium prices of the influence Fisher market. We then show that running gradient descent on the leaders /auctioneers value functions in these games is equivalent to solving the market via a variant of tˆatonnement, where in addition to the auctioneers iteratively adjusting prices, the buyers iteratively learn a Nash equilibrium in response to these prices. Our results pave the way for future work developing methods to compute competitive equilibria in more general types of influence markets beyond those considered in this paper (Chen and Teng 2011), and other market models with graphical structure, such as graphical economies (Kakade, Kearns, and Ortiz 2004).

Acknowledgments

This work was supported by NSF Grant CMMI-1761546.

Arrow, K. J.; and Debreu, G. 1954. Existence of an equilibrium for a competitive economy. Econometrica: Journal of the Econometric Society, 265 290.

Brainard, W. C.; Scarf, H. E.; et al. 2000. How to compute equilibrium prices in 1891. Citeseer.

Chen, X.; and Deng, X. 2006. Settling the complexity of two-player Nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 06), 261 272. IEEE.

Chen, X.; and Teng, S.-H. 2009. Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria. In International Symposium on Algorithms and Computation, 647 656. Springer. Chen, X.; and Teng, S.-H. 2011. A Complexity View of Markets with Social Influence. Ar Xiv, abs/1009.0309. Cheung, Y. K.; Cole, R.; and Devanur, N. 2013. Tatonnement beyond Gross Substitutes? Gradient Descent to the Rescue. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 13, 191 200. New York, NY, USA: Association for Computing Machinery. ISBN 9781450320290. Cole, R.; and Tao, Y. 2019. Balancing the Robustness and Convergence of Tatonnement. ar Xiv:1908.00844. Daskalakis, C.; Goldberg, P. W.; and Papadimitriou, C. H. 2009. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1): 195 259. Devanur, N. R.; Papadimitriou, C. H.; Saberi, A.; and Vazirani, V. V. 2002. Market equilibrium via a primal-dual-type algorithm. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 389 395. Devanur, N. R.; Papadimitriou, C. H.; Saberi, A.; and Vazirani, V. V. 2008. Market equilibrium via a primal dual algorithm for a convex program. Journal of the ACM (JACM), 55(5): 1 18. Dreves, A. 2017. Computing all solutions of linear generalized Nash equilibrium problems. Mathematical Methods of Operations Research, 85(2): 207 221. Dreves, A.; Heusinger, A.; Kanzow, C.; and Fukushima, M. 2013. A Globalized Newton Method for the Computation of Normalized Nash Equilibria. J. of Global Optimization, 56(2): 327 340. Eisenberg, E.; and Gale, D. 1959. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1): 165 168. Facchinei, F.; Fischer, A.; and Piccialli, V. 2007. On generalized Nash games and variational inequalities. Operations Research Letters, 35(2): 159 164. Facchinei, F.; Fischer, A.; and Piccialli, V. 2009. Generalized Nash equilibrium problems and Newton methods. Mathematical Programming, 117(1): 163 194. Fischer, A.; Herrich, M.; Izmailov, A. F.; and Solodov, M. V. 2016. A globally convergent LP-Newton method. SIAM Journal on Optimization, 26(4): 2012 2033. Gao, Y.; and Kroer, C. 2020. First-Order Methods for Large Scale Market Equilibrium Computation. In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, Neur IPS 2020, December 6-12, 2020, virtual. Goktas, D.; and Greenwald, A. 2021. Convex-Concave Min Max Stackelberg Games. Advances in Neural Information Processing Systems, 34. Goktas, D.; and Greenwald, A. 2022. Exploitability Minimization in Games and Beyond. ar Xiv preprint ar Xiv:2210.10207.

Goktas, D.; Viqueira, E. A.; and Greenwald, A. 2021. A Consumer-Theoretic Characterization of Fisher Market Equilibria. In Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14 17, 2021, Proceedings, 334 351. Berlin, Heidelberg: Springer-Verlag. ISBN 978-3-030-94675-3. Goktas, D.; Zhao, J.; and Greenwald, A. 2022. Robust no-regret learning in min-max Stackelberg games. ar Xiv preprint ar Xiv:2203.14126. Gorbunov, E.; Loizou, N.; and Gidel, G. 2022. Extragradient method: O (1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, 366 402. PMLR. Heusinger, A.; and Kanzow, C. 2009. Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search. Journal of Optimization Theory and Applications, 143(1): 159 183. Izmailov, A. F.; and Solodov, M. V. 2014. On error bounds and Newton-type methods for generalized Nash equilibrium problems. Computational Optimization and Applications, 59(1): 201 218. Jain, K.; Vazirani, V. V.; and Ye, Y. 2005. Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. In SODA, volume 5, 63 71. Jordan, M. I.; Lin, T.; and Zampetakis, M. 2023. First Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems. Journal of Machine Learning Research, 24(38): 1 46. Kakade, S. M.; Kearns, M.; and Ortiz, L. E. 2004. Graphical Economics. In Annual Conference Computational Learning Theory. Krawczyk, J. B.; and Uryasev, S. 2000. Relaxation algorithms to find Nash equilibria with economic applications. Environmental Modeling & Assessment, 5(1): 63 73. This revised version was published online in July 2006 with corrections to the Cover Date. Mas-Colell, A.; Whinston, M. D.; and Green, J. R. 1995. Microeconomic Theory. Number 9780195102680 in OUP Catalogue. Oxford University Press. ISBN ARRAY(0x4cf9c5c0). Nabetani, K.; Tseng, P.; and Fukushima, M. 2011. Parametrized Variational Inequality Approaches to Generalized Nash Equilibrium Problems with Shared Constraints. Comput. Optim. Appl., 48(3): 423 452. Nash, J. F. 1950. Equilibrium points in i n /i -person games. Proceedings of the National Academy of Sciences, 36(1): 48 49. Rosen, J. B. 1965. Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. Econometrica, 33(3): 520 534. Ryu, E. K.; Yuan, K.; and Yin, W. 2019. ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs. Ar Xiv, abs/1905.10899. Schiro, D. A.; Pang, J.-S.; and Shanbhag, U. V. 2013. On the solution of affine generalized Nash equilibrium problems

with shared constraints by Lemke s method. Mathematical Programming, 142(1-2): 1 46. This work was based on research partially supported by the National Science Foundation under grant CMMI-0969600 and the Department of Energy under grant DOE DE-SC0003879. Solodov, M.; and Svaiter, B. 1999. A Hybrid Approximate Extragradient-Proximal Point Algorithm Using The Enlargement Of A Maximal Monotone Operator. Set-Valued Analysis, 7: 323 345. Uryas ev, S.; and Rubinstein, R. 1994. On relaxation algorithms in computation of noncooperative equilibria. IEEE Transactions on Automatic Control, 39(6): 1263 1267. von Heusinger, A.; Kanzow, C.; and Fukushima, M. 2012. Newton s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation. Mathematical Programming, 132(1): 99 123. Walras, L. 1896. Elements de l economie politique pure, ou, Theorie de la richesse sociale. F. Rouge.