Large-Scale Contextual Market Equilibrium Computation through Deep Learning

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:29:36

Abstract: Market equilibrium is one of the most fundamental solution concepts in economics and social optimization analysis.
Existing works on market equilibrium computation primarily focus on settings with a relatively small number of buyers.
Motivated by this, our paper investigates the computation of market equilibrium in scenarios with a large-scale buyer population, where buyers and goods are represented by their contexts.
Building on this realistic and generalized contextual market model, we introduce MarketFCNet, a deep learning-based method for approximating market equilibrium.
We start by parameterizing the allocation of each good to each buyer using a neural network, which depends solely on the context of the buyer and the good.
Next, we propose an efficient method to estimate the loss function of the training algorithm unbiasedly, enabling us to optimize the network parameters through gradient descent.
To evaluate the approximated solution, we introduce a metric called Nash Gap, which quantifies the deviation of the given allocation and price pair from the market equilibrium.
Experimental results indicate that MarketFCNet delivers competitive performance and significantly lower running times compared to existing methods as the market scale expands, demonstrating the potential of deep learning-based methods to accelerate the approximation of large-scale contextual market equilibrium.

Main paper: 
 introduction: 
 Market equilibrium is a solution concept in microeconomics theory, which studies how individuals amongst groups will exchange their goods to get each one better off [51] . The importance of market equilibrium is evidenced by the 1972 Nobel Prize awarded to John R. Hicks and Kenneth J. Arrow "for their pioneering contributions to general economic equilibrium theory and welfare theory" [58] . Market equilibrium has wide application in fair allocation [32] , as a few examples, fairly assigning course seats to students [11] or dividing estates, rent, fares, and others [35] . Besides, market equilibrium are also considered for ad auctions with budget constraints where money has real value [15, 16] .Existing works often use traditional optimization method or online learning technique to solve market equilibrium, which can tackle one market with around 400 buyers and goods in experiments [30, 52] .However, in realistic scenarios, there might be millions of buyers in one market (e.g. job market, online shopping market). In these scenarios, the description complexity for the market is O(nm) and it needs at least O(nm) cost to do one optimization step for the market, if there are n buyers and m goods in the market, which is unacceptable when n is extremely large and potentially infinite. In this case, and traditional optimization methods do not work anymore.However, contextual models come to the rescue. The success of contextual auctions [21, 5] demonstrate the power of contextual models, in which each bidder and item are represented as context and Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.the value (or the distribution) of item to bidder is determined by the contexts. In this way, auctions as well as other economic problems can be described in a more memory-efficient way, making it possible to accelerate the computation on these problems. Inspired by the models of contextual auctions, we propose the concept of contextual markets in a similar way. We verify that contextual markets can be useful to model large-scale markets aforementioned, since the real market can be assumed to be within some low dimension space, and the values of goods to buyers are often not hard to speculate given the knowledge of goods and buyers [46, 45] . Besides, contextual models never lose expressive power compared with raw models [7] , giving contextual markets capabilities to generalize over traditional markets.This paper initiates the study of deep learning for contextual market equilibrium computation with a large number of buyers. The description complexity of contextual markets is O(n + m), if there are n buyers and m items in the market, making them memory-efficient and helpful for follow-up equilibrium computation while holding the market structure. Following the framework of differentiable economics [18, 26, 62] , we propose a deep-learning based approach, MarketFCNet, in which one optimization step costs only O(m) rather than O(nm) in traditional methods, greatly accelerating the computation of market equilibrium. MarketFCNet takes the representations of one buyer and one good as input, and outputs the allocation of the good to the buyer. The training on MarketFCNet targets at an unbiased estimator of the objective function of EG-convex program, which can be formed by independent samples of buyers. By this way, we optimize the allocation function on "buyer space" implicitly, rather than optimizing the allocation to each buyer directly. Therefore, MarketFCNet can reduce the algorithm complexity such that it becomes independent of n, i.e., the number of buyers.The effectiveness of MarketFCNet is demonstrated by our experimental results. As the market scale expands, MarketFCNet delivers competitive performance and significantly lower running times compared to existing methods in different experimental settings, demonstrating the potential of deep learning-based methods to accelerate the approximation of large-scale contextual market equilibrium.The contributions of this paper consist of three parts,• We proposes a method, MarketFCNet, to approximate the contextual market equilibrium in which the number of buyers is large.• We proposes Nash Gap to quantify the deviation of the given allocation and price pair from the market equilibrium.• We conduct extensive experiments, demonstrating promising performance on the approximation measure and running time compared with existing methods. 
related works: 
 The history of market equilibrium arises from microeconomics theory, where the concept of competitive equilibrium [51, §10] was proposed, and the existence of market equilibrium is guaranteed in a general setting [3, 61] . Eisenberg and Gale [28] first considered the linear market case, and proved that the solution of EG-convex program constitutes a market equilibrium, which lays the polynomial-time algorithmic foundations for market equilibrium computation. Eisenberg [27] later showed that EG program also works for a class of CCNH utility functions. Shmyrev program later is also proposed to solve market equilibrium with linear utility with a perspective shift from allocation to price [57] , while Cole et al. [14] later found that Shmyrev program is the dual problem of EG program with a change of variables. There are also a branch of literature that consider computational perspective in more general settings such as indivisible goods [54, 19, 20] and piece-wise linear utility [60, 33, 34] .There are abundant of works that present algorithms to solve the market equilibrium and shows the convergence results theoretically [13] . Gao and Kroer [30] discusses the convergence rates of first-order algorithms for EG convex program under linear, quasi-linear and Leontief utilities. Nan et al. [52] later designs stochastic optimization algorithms for EG convex program and Shmyrev program with convergence guarantee and show some economic insight. Jalota et al. [42] proposes an ADMM algorithm for CCNH utilities and shows linear convergence results. Besides, researchers are more engaged in designing dynamics that possess more economic insight. For example, PACE dynamic [32, 48, 65] and proportional response dynamic [63, 66, 12] , though the original idea of PACE arise from auction design [16, 15] .With the fast growth of machine learning and neural network, many existing works aim at resolving economic problem by deep learning approach, which falls into the differentiate economy framework [26] . A mainstream is to approximate the optimal auction with differentiable models by neural networks [25, 29, 36, 55] . The problem of Nash equilibrium computation in normal form games [22, 50, 23] and optimal contract design [62] through deep learning also attracts researchers' attentions. Among these methodologies, transformer architecture [50, 21, 47] is widely used in solving economic problems.To the best of our knowledge, no existing works try to approximate market equilibrium through deep learning. Besides, although some literature focuses on low-rank markets and representative markets [46, 45] , our works firstly propose the concept of contextual market. We believe that our approach will pioneer a promising direction for large-scale contextual market equilibrium computation.Question: Does the paper discuss the limitations of the work performed by the authors? 
contextual market modelling: 
 In this section, we focus on the model of contextual market equilibrium in which goods are assumed to be divisible. Let the market consist of n buyers, denoted as 1, ..., n, and m goods, denoted as 1, ..., m.We denote [k] as the abbreviation of the set {1, 2, . . . , k}. Each buyer i ∈ [n] has a representation b i , and each good j ∈ [m] has a representation g j . We assume that b i belongs to the buyer representation space B, and g j belongs to the good representation space G. For a buyer with representation b ∈ B, she has budget B(b) > 0. Denote Y (g) > 0 as the supply of good with representation g. Although many existing works [30] assume that each good j has unit supply (i.e. Y (g) ≡ 1 for all g ∈ G)without loss of generality, their results can be easily generalized to our settings.An allocation is a matrix x = (x ij ) i∈[n],j∈[m] ∈ R n×m +, where x ij is the amount of good j allocated to buyer i. We denote x i = (x i1 , . . . , x im ) as the vector of bundle of goods that is allocated to buyer i. The buyers' utility function is denoted as u : B × R m + → R + , here u(b i ; x i ) denotes the utility of buyer i with representation b i when she chooses to buy x i . We denote u i (x i ) as an equivalent form of u(b i ; x i ) and often refer them as the same thing. Similarly, B(b i ), Y (g j ) and B i , Y j are often referred to as the same thing, respectively.Let p = (p 1 , . . . , p m ) ∈ R m + be the prices of the goods, the demand set of buyer with representation b i is defined as the set of utility-maximizing allocations within budget constraint.EQUATIONA contextual market is a 4-tuple: M = ⟨n, m, (b i ) i∈[n] , (g j ) j∈[m] ⟩, where buyer utility u(b i ; x i ) is known given the information of the market. We also assume budget function B : B → R + represents the budget of buyers and capacity function Y : G → R + represents the supply of goods. All of u, B and Y are assumed to be public knowledge and excluded from a market representation. This assumption mainly comes from two aspects: (1) these functions can be learned from historical data and (2) budgets and supplies can be either encoded in b and g in some way.The market equilibrium is represented as a pair (x, p), x ∈ R n×m + , p ∈ R m + , which satisfies the following conditions.• Buyer optimality:x i ∈ D(b i , p) for all i ∈ [n],• Market clearance:n i=1 x ij ≤ Y (g j ) for all j ∈ [m],and equality must hold if p j > 0.We say that u i is homogeneous (with degree 1) if it satisfies u i (αx i ) = αu i (x i ) for any x i ≥ 0 and α > 0 [53, §6.2]. Following existing works, we assume that u i s are CCNH utilities, where CCNH represents for concave, continuous, non-negative, and homogeneous functions [30] . For CCNH utilities, a market equilibrium can be computed using the following Eisenberg-Gale convex program (EG):max n i=1 B i log u i (x i ) s.t. n i=1 x ij ≤ Y j , x ≥ 0. (EG)Theorem 3.1 shows that the market equilibrium can be represented as the optimal solution of (EG).Theorem 3.1 (Gao and Kroer [30] ). Let u i be concave, continuous, non-negative and homogeneous (CCNH). Assume u i (1) > 0 for all i. Then, (i) (EG) has an optimal solution and (ii) any optimal solution x to (EG) together with its optimal Lagrangian multipliers p * ∈ R m + constitute a market equilibrium, up to arbitrary assignment of zero-price items. Furthermore, ⟨p * , x * i ⟩ = B i for all i.Based on Theorem 3.1, it's easy to find that we can always assume i∈ [n] x ij = Y j while preserving the existence of market equilibrium, which states as follows.Proposition 3.2. Following the assumptions in Theorem 3.1. For the following EG convex program with equality constraints,EQUATIONThen, an optimal solution x * together with its Lagrangian multipliers p * ∈ R m + constitute a market equilibrium. Moreover, assume more that for each good j, there is some buyer i such that ∂ui ∂xij > 0 always hold whenever u i (x i ) > 0, then all prices are strictly positive in market equilibrium. As a consequence, Equation (EG) and Equation (2) derive the same solution.We leave all proofs to Appendix B. Since the additional assumption in Proposition 3.2 is fairly weak, without further clarification, we always assume the conditions in Proposition 3.2 hold and the marketclearance condition becomes i∈[n] x ij = Y (g j ), ∀j ∈ [m].Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 
marketfcnet: 
 In this section, we introduce the MarketFCNet (denoted as Market Fully-Connected Network) approach to solve the market equilibrium when the number of buyers is large and potentially infinite.MarketFCNet is a sampling-based methodology, and the key point is to design an unbiased estimator of an objective function whose solution coincides with the market equilibrium. The main advantageis that it has the potential to fit the infinite-buyer case without scaling the computational complexity.Therefore, MarketFCNet is scalable with the number of buyers varies.Following the idea of differentiable economics [26] , we consider parameterized models to represent the allocation of good j to buyer i, denoted as x θ (b i , g j ), and call it allocation network, where θ is the network parameter. Given buyer i and good j, the network can automatically compute the allocationx ij = x θ (b i , g j ).The allocation to buyer i is represented as x i = x θ (b i , g) and the allocation matrix is represented as x = x θ (b, g). Then the market clearance constraint can be reformulated asi∈[n] x θ (b i , g j ) = Y (g j ), ∀j ∈ [m]and the price constraint can be reformulated as x θ (b, g) ≥ 0.Let b be uniformly distributed from B = {b i : i ∈ [n]}, then the EG program (EG) becomes,max x θ OBJ(x θ ) = E b [B(b) log u(b; x θ (b, g))] s.t. E b [x θ (b, g j )] = Y (g j )/n, ∀j ∈ [m] x θ (b, g) ≥ 0 (EG-FC)For simplicity, we take Y (g j )/n ≡ 1 for all g j .The second constraint in (EG-FC) can be easily handled by the network architecture (for example, network with a softplus layer σ(x) = log(1 + exp(x)). As for the first constraint, from Theorem 3.1, we know the prices of goods are simply the Lagrangian multipliers for the first constraint in (EG-FC).Therefore, we employ the Augmented Lagrange Multiplier Method (ALMM) to solve the problem (EG-FC). We define L ρ (x θ , λ) as the Lagrangian, which has the form:EQUATIONFigure 1 : Training process of MarketFCNet. On each iteration, the batch of M independent buyers are drawn. each buyer and each good are represented as k-dimension context. The (i, j)'th element in the allocation matrix represents the allocation computed from i'th buyer and j'th good. MarketFCNet training process alternates between the training of allocation network and prices. The training of allocation network need to achieve an unbiased estimator L ρ (x θ ; λ) of the loss function L ρ (x θ ; λ), followed by gradient descent. The training of prices need to get an unbiased estimator ∆λ j of ∆λ j , followed by ALMM updating rule λ j ← λ j + β t ∆λ j .Allocation networkBuyers 𝑥 ! (𝑏 " , 𝑔 # ) ' ℒ $ (𝑥 ! ; λ) gradient descent 𝑏 % 𝑏 & 𝑏 ' 𝑔 % 𝑔 ( …… 𝑔 & M * k m * k M * m λ % λ & λ ) …… prices Update λ …… Goods i.i.d. Update 𝜃Directly computing the objective function seems intractable due to the potentially infinite data size.Therefore, we follow the framework in learning theory culture that we only guarantee to achieve an unbiased gradient of the objective function [1, 8] . The training process of MarketFCNet is presented in Figure 1 .To finish the ALMM algorithm, we need to obtain unbiased estimators of following two expressions.• An unbiased estimator of L ρ (x θ ; λ).• An unbiased estimator of ∆λ j , where ∆λ j is given by ∆λ j = ρ (E b [x θ (b, g j )] -1). Unbiased estimator of L p (x θ ; λ) For OBJ(x θ ) and the second term, the technique to achieve an unbiased estimator is similar. u(b; x θ (b, g)) in OBJ(x θ ) can be calculated directly by summing over all goods. For the last term, notice thatEQUATIONTherefore, we can sample bEQUATIONwhich provides an unbiased estimator for the last term, capturing the squared deviation of output allocations from the constraint. 
performance measures of market equilibrium: 
 In this section, we propose Nash Gap to measure the performance of an approximated market equilibrium and show that Nash Gap preserves the economic interpretation for market equilibrium. To introduce Nash Gap, we first introduce two types of welfare, Log Nash Welfare and Log Fixed-price Welfare in Definition 5.1 and Definition 5.2, respectively.Definition 5.1 (Log Nash Welfare). The Log Nash Welfare (abbreviated as LNW) is defined asEQUATIONwhere B total = i∈[n] B i is the total budgets for buyers.Notice that LNW(x) is identical to the objective function in Equation (EG), differing only in the constant term coefficient.Definition 5.2 (Fixed-price and Log Fixed-price Welfare). We define the fixed-price utility for buyer i as,EQUATIONwhich represents the optimal utility that buyer i can obtain at the price level p, regardless of the market clearance constraints. The Log Fixed-price Welfare (abbreviated as LFW) is defined as the logarithm of Fixed-price Welfare,EQUATIONBased on these definitions, we present the definition of Nash Gap.Definition 5.3 (Nash Gap). We define Nash Gap (abbreviated as NG) as the difference of Log NashWelfare and Log Fixed-price Welfare, i.e.EQUATIONTo show why NG is useful in the measure of market equilibrium, we first observe that, Proposition 5.4 (Price constraints). If (x, p) constitute a market equilibrium, the following identity always hold,EQUATIONBelow, we state the most important theorem in this paper.Theorem 5.5. Let (x, p) be a pair of allocation and price. Assuming the allocation satisfies market clearance and the price meets price constraint, then we have NG(x, p) ≥ 0.Moreover, NG(x, p) = 0 if and only if (x, p) is a market equilibrium.Theorem 5.5 show that Nash Gap is an ideal measure of the solution concept of market equilibrium, since it holds following properties,• NG(x, p) is continuous on the inputs (x, p).• NG(x, p) ≥ 0 always hold. (under conditions in Theorem 5.5)• NG(x, p) = 0 if and only if (x, p) meets the solution concept.• The computation of NG does not require the knowledge of an equilibrium point (x * , p * )Since some may argue that NG(x, p) is not intuitive to understand, we consider some more intuitive Bi B total u i (x i ), and show the connection between NG and these intuitive measures.Proposition 5.6. Under some technical assumptions (which is presented in Appendix B.4), if NG(x, p) = ε, we have:• ||p -p * || = O( √ ε). • ||x i -x * i || = O( √ ε) for all i. • |WSW(x) -WSW(x * )| = O(ε).Finally, we give a saddle-point explaination for Nash Gap.Corollary 5.7. Within market clearance and price constraint, we haveEQUATIONCorollary 5.7 provides an economic interpretation for GAP. Market equilibrium can be seen as the saddle point over social welfare, and the social welfare for x can be actually implemented while the social welfare for p is virtual and desired by buyers. Nash Gap measures the gap between the "desired welfare" and the "implemented welfare" for buyers.Since NG only works for (x, p) that satisfies market clearance and price constraints, we generalize the measure of NG to a more general case, which need to give a measure for all positive (x, p).We first notice that any equilibrium must satisfy the conditions of market clearance and price constraint, we first make a projection on arbitrary positive (x, p) to the space where these constraints hold. Specifically, if we letEQUATIONthen ( x, p) satisfies these constraints and we consider NG( x, p) as the equilibrium measure.Besides, we also need to measure how far is the point (x, p) to the space within the conditions of market clearance and price constraint. we propose following two measurement, called Violation of Allocation (abbreviated as VoA) and Violation of Price (abbreviated as VoP), respectively.EQUATIONFrom the expressions of VoA and VoP, we know that these two constraints hold if and only ifVoA(x) = 0 and VoP(p) = 0.We argue that this projection is of economic meaning. If (x, p) constitute a market equilibrium and we scale budget with a factor of β, then (x, βp) constitute a market equilibrium in the new market. Similarly, if we scale the value for each buyer with factor 1/α (here α can be a vector in R m + ) and capacity with factor α, then, (αx, 1 α p) constitute a market equilibrium in the new market.These instances are evidence that market equilibrium holds a linear structure over market parameters.Therefore, a linear projection can eliminate the effect from linear scaling, while preserving the effect from orthogonal errors.Notice that x = x and p = p if and only if VoA(x) = 0 and VoP(p) = 0, respectively. From Theorem 5.5 We can easy derive following statements:Proposition 5.8. For arbitrary x ∈ R n×m + , p ∈ R m + , we have VoA(x) ≥ 0, VoP(p) ≥ 0, NG( x, p) ≥ 0 always hold. Moreover, (x, p) is a market equilibrium if and only if VoA(x) = VoP(p) = NG( x, p) = 0.Proposition 5.8 is a certificate that VoA(x), VoP(p), NG( x, p) together form a good measure for market equilibrium. Therefore, in our experiments we compute these measures of solutions and prefer a lower measure without further clarification. 
experiments: 
 In this section, we present empirical experiments that evaluate the effectiveness of MarketFCNet.Though briefly mentioned in this section, we leave the details of baselines, implementations, hyperparameters and experimental environments to Appendix C. In our experiments, all utilities are chosen as CES utilities, which captures a wide utility class including linear utilities, Cobb-Douglas utilities and Leontief utilities and has been widely studied in literature [59, 4] . CES utilities have the form,u i (x i ) =   j∈[m] v α ij x α ij   1/αwith α ≤ 1. The fixed-price utilities for CES utility is derived in Appendix A.In order to evaluate the performance of MarketFCNet, we compare them mainly with a baseline that directly maximizes the objective in EG convex program with gradient ascent algorithm (abbreviated as EG), which is widely used in the field of market equilibrium computation. Besides, we also consider a momentum version of EG algorithm with momentum β = 0.9 (abbreviated as EG-m). We move the details of all baselines, experimental environments and implementations of algorithms to Appendix C.1 and Appendix C.2.We also consider a naïve allocation and pricing rule (abbreviated as Naïve), which can be regarded as the benchmark of the experiments:EQUATIONIn the following experiments, MarketFCNet is abbreviated as FC. Notice that Naïve always gives an allocation that satisfies market clearance and price constraints, while EG, EG-m and FC do not. MarketFCNet is more suitable to large-scale contextual market equilibrium computation.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? 
conclusions and future work: 
 This paper initiates the problem of large-scale contextual market equilibrium computation from a deep learning perspective. We believe that our approach will pioneer a promising direction for large-scale contextual market equilibrium computation.For future works, it would be promising to extend these methods to the case when only the number of goods is large, or both the numbers of goods and buyers are large, which stays a blank throughout our works. Since many existing works proposed dynamics for online market equilibrium computation, it's also promising to extend our approaches to tackle the online market setting with large buyers.Besides, both existing works and ours consider sure budgets and values for buyers, and it would be interesting to extend the fisher market and equilibrium concept when the budgets or values of buyers are stochastic or uncertain. A Derivation of Fixed-price Utility for CES Utility FunctionsIn this section we show the explicit expressions of Fixed-price Utility for CES utility functions.We first consider the case α ̸ = 0, 1, -∞. The optimization problem for consumer i is:EQUATIONs.t. j∈[m]x ij p j = B i (Budget Constraint)EQUATIONNot hard to verify that in an optimal solution with Equation (Budget Constraint), Equation ( 16)always holds, therefore we omit this constraint in our derivation.We write the Lagrangian L(x i , λ)L(x i , λ) = u i (x i ) + λ(B i - j∈[m]x ij p j )By ∂L ∂xij = 0, we haveEQUATIONWe derive thatEQUATIONx* ij = v α 1-α ij c 1 1-α • p 1 1-α j (21)Taking ( 21) into (Budget Constraint), we getEQUATIONTaking Equation (23) into Equation ( 21), we getEQUATIONwherec 0 = j∈[m] vij pj α 1-αTaking Equation (24) into Equation ( 15), we finally haveEQUATIONFor α = 1, by simple arguments we know that consumer will only buy the good that with largest value-per-cost, i.e., v ij /p j . Therefore, we haveEQUATIONFor α = 0, we have logu i (x i ) = 1 vt j∈[m] v ij log x ij where v t = j∈[m] v ij .Similarly, we haveEQUATIONxEQUATIONBy solving budget constraints we have c = vt Bi , and therefore, x * ij = vij Bi pj vt andEQUATIONEQUATIONFor α = -∞, we can easily know that v ij x * ij ≡ c for some c. By solving budget constraint we haveEQUATIONEQUATIONAbove all, the log Fixed-price Utility for CES functions isEQUATIONB Omitted Proofs B.1 Proof of Proposition 3.2We consider Lagrangian multipliers p and use the KKT condition. The Lagrangian becomesEQUATIONand the partial derivative of x ij isEQUATION)By complementary slackness of x ij ≥ 0, we haveEQUATIONBy theorem 3.1, we know that if (x, p) is a market equilibrium, we must have u i (x i ) > 0 for all i, and by condition in Proposition 3.2, we can always select buyer i such that ∂ui ∂xij > 0. Therefore, we have p j > 0.As a consequence, p j > 0 indicates that j x ij = V j by market clearance condition.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 
 
 Appendix: Consider the market equilibrium condition ⟨p * , x * i ⟩ = B i , we have j p j x ij = B i . sum over this expression, we have i j p j x ij = i B i . Then, j p j i x ij = i B i . Notice that we have n i=1 x ij = Y j in market equilibrium, so j p j Y j = i B i , that completes the proof.Proof of Theorem 5.5. Denote (x, p) as the market equilibrium, p as the price for goods and x * i (p) as the optimal consumption set of buyer i when the price is p.We have following equation:EQUATION)x i ∈x * i (p) (39) i∈[n]x ij =Y j (40)EQUATIONFrom Proposition 5.4 we know i∈[n] B i = j∈[m] Y j p j .Let p ′ be some price for items such that j∈EQUATION)Lemma B.2. Denote ũi (p, B i ) and x * i (p, B i ) as the maximum utility buyer i can get and the corresponding consumption for buyer i when her budget is B i and prices are p. If following hold:• ||p -p * || = ε • x * i (p, B i ) is differentiable with p. • H X := ( i∈[n] ∂x * ij ∂p k (p * , B i )) j,k∈[m] has full rank.then we have LF W (p) -OP T = Ω(ε 2 ).Remark B.3. It's worth notice that H(x * i ) can not has full rank m, since u i (x) is assumed to be homogeneous and thus linear in the direction x. Therefore, we have H(x i )x i = 0 for all x i . Lemma B.5. Assume following hold:Let C i = {x i ∈ R m + : ⟨p, x i ⟩ = B i }• ||p -p * || = O( √ ε) • ||x i -x * i || = O( √ ε)• buyers have same utilities at x * , i.e. u i (x * i ) = u j (x * j ) ≡ c for all i, j• ||x i -x * i || ≤ ε for all i then, we have |WSW(x) -WSW(x * )| = O(ε 2 ).Remark B.6. These conditions can be held when buyers are homogeneous, i.e., B i = B j and u i (x) = u j (x) for all i, j, x ∈ R m + . Besides, consider buyers with same budgets, these conditions can also be held if the market has some "equivariance property", e.g., there is a n-cycle permutation of buyers ρ and permutation of goods τ , such thatu i (x i ) = u ρ(i) (τ (x ρ(i) )) for all i and τ (Y 1 , ..., Y m ) = (Y 1 , ..., Y m ).Corollary B.7. Under the assumptions in Lemma B.1 and Lemma B.5, if NG(x, p) = ε, we have• |WSW(x) -WSW(x * )| = O(ε).Proof. A direct inference from Lemma B.1 and Lemma B.5.Proof of Lemma B.1. We observe thatOPT -LNW(x) = i∈[n] B i [log u i (x * i ) -log u i (x i )]Consider the Taylor expansion of log u i (x i ) and u i (x i ):log u i (x i ) = log u i (x * i ) + 1 u i (x * i ) (u i (x i ) -u i (x * i )) - 1 2u i (x * i ) 2 (u i (x i ) -u i (x * i )) 2 +O((u i (x i ) -u i (x * i )) 3 ) u i (x i ) =u i (x * i ) + ∂u i ∂x i (x * i )(x i -x * i ) + 1 2 (x i -x * i ) T H(x * i )(x i -x * i ) + O(||x i -x * i || 3 ) Notice that ||x i -x * i || = ε, we have log u i (x i ) = log u i (x * i ) + 1 u i (x * i ) [ ∂u i ∂x i (x * i )(x i -x * i ) • • • ε term (51) + 1 2 (x i -x * i ) T H(x * i )(x i -x * i )] • • • ε 2 term (52) - 1 2u i (x * i ) 2 ∂u i ∂x i (x * i )(x i -x * i ) 2 • • • ε 2 term (53) +O(ε 3 )We next deal with Equation ( 51) to Equation ( 53) separately.Derivation of Equation ( 51) Since x * i solves the buyer i's problem, we must haveEQUATIONwhere λ i is the Lagrangian Multipliers for buyer i.We also know that u i (x i ) is homogeneous with degree 1, by Euler formula, we deriveEQUATIONCombine Equation (54) and Equation ( 55) and take x i = x * i , we deriveλ i ⟨p * , x * i ⟩ =u i (x * i ) λ i = u i (x * i ) B i ∂u i ∂x i (x * i ) = u i (x * i ) B i p *Sum up over i for Equation (51), we haveEQUATIONDerivation of Equation ( 52) and Equation (53) Combining Equation (52) and Equation (53), we haveB i 2u i (x * i ) (x i -x * i ) T H(x * i )(x i -x * i ) - 1 2B i (x i -x * i ) T (p * p * T )(x i -x * i ) = 1 2B i (x i -x * i ) T ( B 2 i u i (x * i ) H(x * i ) -p * p * T )(x i -x * i ) Denote H 0 (x * i ) = B 2 i ui(x * i ) H(x * i ) -p * p * T , next we assert that H 0 (x * i ) is negative definite.Since H(x * i ) and -p * p * T are negative semi-definite, H 0 (x * i ) must be negative semi-definite withrank(H 0 (x * i )) ≥ m -1. Let λ 1 ≤ λ 2 ≤ • • • ≤ λ m-1 < λ m = 0 be eigenvalues and v 1 , ..., v n = x * i be eigenvectors of H(x * i ). If rank(H 0 (x * i )) = m -1, it means that x * i has to be eigenvectors of -p * p * T with eigenvalue 0. However, we have -p * p * T x * i = -B i p * ̸ = 0, which leads to a contradiction.Therefore, we have rank(H 0 (x * i )) = m and H 0 (x * i ) is negative definite, we denote λ i 1 ≤ ..., ≤ λ i n < 0 as the eigenvalues of H 0 (x * i ), and k as the universal lower bound for |λ i n |, then we have that,EQUATIONBy combining Equation (56) and Equation ( 57), we haveEQUATIONB.4.2 Proof of Lemma B.2Proof of Lemma B.2. The proof is similar with Appendix B.4.1 by using Taylor expansion technique.Before that, we first derive some identities.By Roy's identity, we have∂ ũi ∂p j (p, B i ) = -x * ij (p, B i ) ∂ ũi ∂B i (p, B i )Since u(x i ) is homogeneous with x i , it's easy to derive that∂ ũi ∂B i (p, B i ) = ũi (p, B i ) B i Above all, ∂ ũi ∂p j (p, B i ) = - 1 B i x * ij (p, B i )ũ i (p, B i ) Besides, ∂ 2 ũi ∂p j ∂p k (p, B i ) = 1 B 2 i x * ij (p, B i )x * ik (p, B i )ũ i (p, B i ) - 1 B i x * ij (p, B i ) ∂p k ũi (p, B i )Next we consider the Taylor expansion,log ũi (p) = log ũi (p * ) + 1 ũi (p * ) [ ∂ ũi ∂p (p * )(p -p * ) • • • ε term (59) + 1 2 (p -p * ) T H p (p -p * )] • • • ε 2 term (60) - 1 2ũ i (p * ) 2 ∂ ũi ∂p (p * )(p -p * ) 2 • • • ε 2 term (61) +O(ε 3 )where H p is the Hessian matrix for ũi (p).We havei∈[n] B i 1 ũi (p * ) ⟨ ∂ ũi ∂p (p * ), (p -p * )⟩ = i∈[n] ⟨x * i , (p -p * )⟩ =⟨1, (p -p * )⟩ • • • by market clearance =0 • • • by price constraintsDerivation of Equation ( 60) and Equation ( 61) These expressions become1 2ũ i (p * ) [ 1 B 2 i ũi (p * )⟨x * i , p -p * ⟩ 2 - 1 B i ũi (p * )(p -p * ) T ( ∂x * ij ∂p k (p * , B i )) j,k∈[m] (p -p * )] - 1 2ũ i (p * ) 2 ũi (p * ) 2 B 2 i ⟨x * i , p -p * ⟩ 2 = 1 2B i (p -p * ) T ( ∂x * ij ∂p k (p * , B i )) j,k∈[m] (p -p * )Summing up over i, we derive thatLFW(p) -OPT = i∈[n] B i 1 2B i (p -p * ) T ( ∂x * ij ∂p k (p * , B i )) j,k∈[m] (p -p * ) + O(ε 3 ) = 1 2 (p -p * ) T H X (p -p * ) + O(ε 3 )Since p * gets the minimum of LFW(p), we must have that H X is positive semi-definite. Together with H X has full rank, we know that H X is positive definite. Denote λ m as the minimum eigenvalues of H X , we haveLFW(p) -OPT ≥ ε 2 λ m 2 + O(ε 3 ) =Ω(ε 2 ) B.4.3 Proof of Lemma B.5Proof of Lemma B.5. Notice thatWSW(x) = WSW(x * ) + i∈[n] ⟨ ∂WSW ∂x i (x * i ), (x i -x * i )⟩ + O(ε 2 )We have Guidelines:∂WSW ∂x i (x * i ) =B i ∂u i ∂x i (x * i ) =B i u i (x * i ) B i p * =cp * Therefore, WSW(x) =WSW(x * ) + i∈[n] c⟨p * , x i -x * i ⟩ + O(ε 2 ) =WSW(x * ) + O(ε 2 ) • • •• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: [TODO]We discuss the limitations in Section 7.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Justification: [TODO]The code need to be more finely organized before it goes public.• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: [TODO]These are presented in Appendix C Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material.Justification: [TODO]Since the difference between baselines and our method is prominent, we believe that one experiment on each setting is an enough certificate to show the effectiveness of our method.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: [TODO]The accelaration of market equilibrium computation is a positive social impact.• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Justification: [TODO] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.We find in the experiments when market size is pretty large, baselines run slower on CPU than on GPU and this phenomenon reverses when market size is small. Therefore, the hardware on which baselines run depend on the market size and we always choose the faster one in experiments. 


Decision: Summary:
The paper addresses a market cap equilibrium problem, where the authors assume a (very) large population of buyers. After revisiting the current literature to form equilibrium as a convex optimization problem, the authors propose MarketFCNet, which is more attractive when the number of buyers is high. To evaluate their approach, the authors introduce a metric called "Nash Gap." Finally, they conduct a series of experiments to demonstrate the effectiveness of their approach.

Review: 
The paper contributes to the differentiable economics literature.

Reviews: review: paper_summary: paper_summary: This paper proposes a deep learning-based method called MarketFCNet to efficiently compute market equilibrium in large-scale contextual markets, where buyers and goods are represented by their contexts. The key idea is to parameterize the allocation of each good to each buyer using a neural network, and optimize the network parameters through an unbiased estimation of the objective function. This approach significantly reduces the computation complexity compared to traditional optimization methods, making it suitable for markets with millions of buyers. Experimental results demonstrate that MarketFCNet delivers competitive performance and much faster running times as the market scale expands, highlighting the potential of deep learning for approximating large-scale contextual market equilibrium.
strength_weakness: strength_weakness: The deep learning-based approach is inherently less interpretable compared to traditional optimization methods. Exploring ways to improve the interpretability of the learned allocation function, such as incorporating domain-specific constraints or incorporating interpretable components, could enhance the practical usability of the method.

The paper does not discuss potential overfitting issues that may arise when training the MarketFCNet model, especially in settings with a large number of parameters. Incorporating appropriate regularization techniques and cross-validation strategies could help mitigate overfitting and improve the generalization performance.

The paper assumes that the contexts of buyers and goods are homogeneous and can be directly used as inputs to the neural network. Extending the approach to handle heterogeneous context representations, potentially by incorporating feature engineering or meta-learning techniques, could increase the applicability to more diverse market scenarios.
questions: questions: From a technical perspective, what are the main strengths of the proposed deep learning-based approach, MarketFCNet, for computing market equilibrium in large-scale contextual markets?

What novel evaluation metric is introduced in this paper to assess the quality of the approximated market equilibrium solutions, and how does it contribute to the methodological advancements?

Given the deep learning-based nature of the approach, how might the authors address potential issues like overfitting or the ability to handle heterogeneous context representations in a more robust manner?
limitations: limitations: N/A
paper_summary: paper_summary: The submission is not in your area and extends beyond my current expertise (from theory and applications to specific tasks and methods).
strength_weakness: strength_weakness: The submission is not in your area and extends beyond my current expertise (from theory and applications to specific tasks and methods).
questions: questions: The submission is not in your area and extends beyond my current expertise (from theory and applications to specific tasks and methods).
limitations: limitations: The submission is not in your area and extends beyond my current expertise (from theory and applications to specific tasks and methods).
paper_summary: paper_summary: This paper studies the computation of market equilibrium where there are a large number of buyers and the buyers and goods are represented by their contexts. It proposes a deep-learning method, termed MarketFCNet, to approximate the market equilibrium. The method outputs the good allocation by taking in the context embedding. It is trained on unbiased estimator of the objective function of EG-convex program using ALMM and is evaluated using a metric called Nash Gap. The method is validated by experimental results.
strength_weakness: strength_weakness: 1. The proof of the unbiasedness of $\Delta \lambda_j$ and Lagrangian estimators in Sec 4.2 seems to be a bit hand-wavy. For example, should $b_i$’s be independent of each other? For a fixed $i$, is $b’_i$ an independent copy of $b_i$? It would be great if the authors could provide a formal (and more detailed) proof of the unbiasedness.

2. What is the effect of $k$ on the method performance? For example, if the dimension $k$ is very large, would the method fail to comprehend the context?

3. How to determine the architecture of allocation network? For example, can one use a Transformer or CNN as the allocation network?

Minor issues:

Line 164: It would be better to define $U(B)$ when introducing uniformly sampling to latter use.

Some equations are missing “.” or “,” at the end. Please fix those.
questions: questions: See Weakness.
limitations: limitations: Yes.
paper_summary: paper_summary: This paper studies to how to use deep learning to solve large-scale contextual market equilibrium. This paper proposes MarketFCNet, a deep learning method for approximating market equilibrium. The paper propose an unbiased training loss and a metric called Nash Gap to quantify the gap between the learned allocation and the market equilibrium. Experiments on a synthetic game validates its effectiveness.
strength_weakness: strength_weakness: Quality: The paper does not prove the convergence of the training algorithm. The paper either does not show the training curve. The paper does not provide the implementation code of the algorithm. 
Clarity: The paper is hard to follow. It is quite to hard to understand the meaning of each proposition. 
Significance: The paper aims to solve the large scale contextual market equilibrium, and proposes a novel deep learning method  to approximate the equilibrium efficiently. However, the importance of the large scale contextual market equilibrium is not clear. I do not know how to apply the proposed method in real life.
questions: questions: See the weakness.
limitations: limitations: Yes

Comments: comment: Thank you for your clarifications! Since I do not have access to the PDF file for the proof of unbiasedness, I cannot check its correctness directly. Other justifications are satisfactory. I will keep my rating (Weak Accept).