Statistical Inference for Fisher Market Equilibrium
Authors: Luofeng Liao
Yuan Gao
Christian Kroer
Venue: ICLR 2023 poster (2023)
Keywords: Fisher market equilibrium
first-price auction
statistical inference under interference
revenue management

Abstract: Statistical inference under market equilibrium effects has attracted increasing attention recently. In this paper we focus on the specific case of linear Fisher markets. They have been widely use in fair resource allocation of food/blood donations and budget management in large-scale Internet ad auctions. In resource allocation, it is crucial to quantify the variability of the resource received by the agents (such as blood banks and food banks) in addition to fairness and efficiency properties of the systems. For ad auction markets, it is important to establish statistical properties of the platform's revenues in addition to their expected values. To this end, we propose a statistical framework based on the concept of infinite-dimensional Fisher markets. In our framework, we observe a market formed by a finite number of items sampled from an underlying distribution (the ``observed market'') and aim to infer several important equilibrium quantities of the underlying long-run market. These equilibrium quantities include individual utilities, social welfare, and pacing multipliers. Through the lens of sample average approximation (SSA), we derive a collection of statistical results and show that the observed market provides useful statistical information of the long-run market. In other words, the equilibrium quantities of the observed market converge to the true ones of the long-run market with strong statistical guarantees. These include consistency, finite sample bounds, asymptotics, and confidence. As an extension, we discuss revenue inference in quasilinear Fisher markets.

Published as a conference paper at ICLR 2023
STATISTICAL INFERENCE FOR FISHER MARKET EQUI- LIBRIUM
Luofeng Liao, Yuan Gao, Christian Kroer
Department of Industrial Engineering and Operations Research Columbia University (113530, yg2541, christian. kro.k) umbii ambia
ABSTRACT
Statistical inference under market equilibrium effects has attracted increasing at- tention recently In this paper we focus the specific case of linear Fisher mar- kets. They have been widely use in fair resource allocation of food/blood do- nations and budget management allocation, it is crucial to quantify the variability of the resource received by the agents (such as blood banks and food banks) addition to fairness and efficiency properties of the systems. For ad auction markets, it is important to establish sta- tistical properties of the platform's revenues addition their expected values. To this end, we propose a statistical framework based the concept of infinite- dimensional Fisher markets. In our framework, we observe a market formed by finite number of items sampled from underlying distribution (the "observed market") and aim to infer several important equilibrium quantities of the under- lying long-run market. These equilibrium quantities include individual utilities, social welfare, and pacing multipliers. Through the lens of sample average ap- proximation (SAA), we derive a collection of statistical results and show that the observed market provides useful statistical information of the long-run market. In other words, the equilibrium quantities of the observed market converge the true ones of the long-run run market with strong statistical guarantees. These include consistency, finite sample bounds, asymptotics, and confidence. As an extension we discuss revenue inference in quasilinear Fisher markets.
large-scale Internet ad auctions.
resource
INTRODUCTION
In a Fisher market there is a set of n buyers that are interested in buying goods from a distinct seller. A market equilibrium (ME) is then a set of prices for the goods, along with corresponding allocation, such that demand equals supply.
One important application of market equilibrium (ME) is fair allocation using the competitive equi- librium from equal incomes (CEEI) mechanism (Varian, 1974). In CEEI, each individual is given an endowment of faux currency and reports her valuations for items; then, market equilibrium is computed, and the items are allocated accordingly. The resulting allocation has many desirable properties such as Pareto optimality, envy-freeness and proportionality. For example, Fisher market equilibrium has been used for fair work allocation, impressions allocation in certain recommender systems, course seat allocation and scarce computing resources allocation; see Appendix for an extensive overview.
Despite numerous algorithmic results available for computing Fisher market equilibria, to the best of our knowledge, no statistical results were available for quantifying the randomness of market cquilibrium. Given that CEEI is a fair and efficient mechanism, such statistical results are useful for quantifying variability in CEEI-based resource allocation. For example, for systems that assign blood donation to hospitals and blood banks (McElfresh et al., 2020), or donated food to charities in different neighborhoods (Aleksandrov et al., 2015; Sinclair al., 2022), it is crucial to quantify the variability of the amount of resources (blood or food donation) received by the participants (hospitals charities) of these systems well the variability of faimnsss and efficiency metries of interest

---

Published as a conference paper at ICLR 2023
Buyers
Items
Buyers
Items
(B)
1. strong consistency
2. finite-sample bound
3. asymptotic normality
Social welfare
4. confidence interval
Social welfare
Utility
Utility
Pacing Multiplier
Pacing Multiplier
Revenue (quasilinear markets)
Revenue (quasilinear markets)
Our contributions. Left panel: a Fisher market with a finite number of items. Right panel: a Fisher market with continuum of items. Middle arrow: this paper provides various forms of statistical guarantees to characterize the convergence of observed finite Fisher market (left) to the long-run market (right) when the items are drawn from distribution corresponding the supply function the long-run market.
Figure 1:
the long run. Making statistical statements about these metrics is crucial for both evaluating and improving these systems.
In addition to fair resource allocation, statistical results for Fisher markets can also be used in rev- enue inference in Internet ad auction markets. While much of the existing literature uses expected revenue as performance metrics, statistical inference on revenue challenging due to the complex interaction among bidders under coupled supply constraints and common price signals. As shown by Conitzer et al. (2022a), in budget management through repeated first-price auctions with pacing, the optimal pacing multipliers correspond to the "prices-per-utiltty" of buyers in a quasilinear Fisher market at equilibrium. Given the close connection between various solution concepts in Fisher mar- ket models and first-price auctions, statistical framework enables to quantify the variability in long-run revenue of an advertising platform. Furthermore, a statistical framework would also help answer other statistical questions such as the study of counterfactuals and theoretical guarantees for A/B testing in Internet ad auction markets.
For a detailed survey on related work in the areas of statistical inference, applications of Fisher market models, and equilibrium computation algorithms, see Appendix A.
Our contributions are as follows.
A statistical Fisher market model. We formulate a statistical estimation problem for Fisher mar- kets based on the continuous-item model of Gao and Kroer (2022). We show that when a finite set of goods are sampled from the continuous model, the observed ME is good approximation of the long-run market. In particular, we develop consistency results, finite-sample bounds, central limit theorems, and asymptotically valid confidence interval for various quantities of interests, such as individual utility, Nash social welfare, pacing multipliers, and revenue (for quasilinear Fisher markets).
Technical challenges. developing central limit theorems for pacing multipliers and utilities in Fisher markets (Theorem 5), note that the dual objective is potentially twice differentiable. This is required condition, which common in the sample average approximation or M-estimation literature. We discover three types of market where such differentiability is guaranteed. Moreover, the sample function is not differentiable, which requires us to verify set of stochastic differentia- bility conditions the proofs for central limit theorems. Finally, we achieve a fast statistical rate of the empirical pacing multiplier to the population pacing multiplier measured in the dual objective by exploiting the local strong convexity of the sample function.
For a sequence of events A, we define the set limit by lim inf, An U 0,2n Ag = (A, eventually] and lim sup A, = - A₁ = {A, i.o.). Let [n] = .......).. We use 1, to denote the vector of ones of length t and ej to denote the vec- tor with one in the j-th entry and zeros in the others. For sequence of random variables (Xn), say X,, = (1) if for any > there exists a finite M, and finite N, such that P([X,]] > M,) < for all N.. We say X, Op(a,) if X,/an Sn/a, (1).). We subscript for indexing buyers
Notation.
2

---

Published as a conference paper at ICLR 2023
and superscript for items. If function f is twice continuously differentiable point say is C² at x.
PROBLEM SETUP
2.1 THE ESTIMANDS
Following Gao and Kroer (2022), we consider Fisher market with buyers (individuals), each having a budget b; > 0 and (possibly continuous) set of items @. We let T (and 14 resp.) denote the set of (nonnegative, resp.) L functions on θ w.r.t the integrating measure μ for any p E [1, oo| (including = oo). For example, one could take θ = [0. and j = the Lebesgue measure on [0, 1]. The item supplies are given by function s E L i... item θ has supply s(0). The valuation for buyer is function 24 E L4, i.e., buyer i has valuation (+( for item E θ For buyer an allocation of items E T.7 gives a utility of
u,(2,) = (1,, m.) = / v:
where the angle brackets are based on the notation of applying a bounded linear functional 2; to vector e; in the Banach space L and the integral is the usual Lebesgue integral. We will use (LQ))" to denote the aggregate allocation of items to all buyers, i.e., the concatenation of all buyers' allocations. The prices of items are modeled as E L1. The price of item 0 E e is p(0). Without loss of generality, we assume unit total supply Se s dj = 1. We let S(A) == J s(0) dj((0) be the probability measure induced by the supply
Imagine there is a central policymaker that sets the prices p(-) of items O. Upon receiving the price signal, the buyer maximizes his utility (u;, subject the budget constraint (p, v4)) S b, He would demand a bundle of items coming from his demand set
Dx(p) == arg max (14, v.)) E L (p, S b.).
Of course, due the supply constraint, if prices are too low, there will be shortage in supply. On the other hand, if prices are too high, surplus occurs. Market equilibrium is the case when items are sold out exactly.
Definition 1 (The long-run market equilibrium). The market equilibrium (ME) M (b, v, is an iiiecattoo-utiitty-re
tuple (x", uu ,,,p"") (L " x Rn x L such that the following holds. (i) Supply feasibility and market clearance: Σ z and (p" Σ, x = 0. (ii Buyer optimality: x E D,(p") and un = (1s, 2x) (xx)) for all
Linear Fisher market equilibrium can be characterized by convex programs. We state the following result from Gao and Kroer (2022) which establishes existence and uniqueness of market equilibrium, and more importantly the convex program formulation of the equilibrium. We define the Eisenberg- Gale (EG) convex programs which as we will see are dual to each other.
NSW(U)
Σd by log(u:) us 20) Vi E [n],
Σ oi 0
(P-EG)
LE (0)
/ max (();(0) S(dØ) vE(M
min 850
H(B)
V by log B,
(P-DEG)
Concretely, the optimal primal variables in Eq. (P-EG) corresponds to the set of equilibrium al- locations x" and the unique equilibrium utilities u², and the unique optimal dual variable 5* of Eq. (P-DEG) relates to the equilibrium through
4. = b./ (0) = max 87 (0). 20) > 0 only if i E arg max 8 (0)
We call 3 the pacing multiplier. Note equilibrium allocations might not be unique but equilibrium utilities and prices are unique. Given the above equivalence result, we use (x* u²) to denote both the equilibrium and the optimal variables. Another feature of linear Fisher market is full budget extraction: p dS Ei= by; discuss quasilinear model in Appendix F.
3

---

Published as a conference paper at ICLR 2023
We formally state the first-order conditions of aafnite-dimensional EG programs and its relation to first-price auctions in Fact in appendix. Also, we remark that there are two ways to specify the valuation component in this model: the functional form of v,(+), or the distribution of values v: θ - F when view as a random vector. More on this in Appendix E.
We interested in estimating the following quantities of the long-run market equilibrium. (1) In- dividual utilities at equilibrium, ug. (2) Pacing multipliers 8 = /./ Pacing multiplier has a two-fold interpretation. Second, through the equation p" p²(0) - max; S7 (O),,, B can also be inter- preted as the pacing policy' employed by the buyers in first-price auctions. In our context, buyer i produces a bid for item by multiplying the value by 3,. then the item price is determined via a first- price auction. This connection is made precise in Conitzer al. (2022a) from game-theoretic point of view. The pacing multiplier / serves as the bridge between Fisher market equilibrium and first price pacing equilibria in auction games (Conitzer al., 2022a) and has important usage in budget management in online auctions. (3) The (logarithm of) Nash social welfare (NSW) at equilibrium NSW : xw")"")). NSW measures total utility of the buyers and, when used as an optimization objective, is able to promote faimess better than the social welfare, that is, the sum of buyer utilities (Caragiannis et al., 2019). Intuitively, NSW incentivizes more balancing of buyer utilities. Revenue inference for quasilinear model is discussed in Appendix F2.
Mapping model concrete applications. It is well-know that Fisher market is useful mecha- nism for fair and efficient resource allocation. More recently, it is also shown to be intimately related to first-price auctions (Conitzer et al., 2022a). When modeling ad auction platforms, buyers' individ- ual utilities reflect, for example, the values generated to advertisers, measured in terms of click rates, conversion rates, or other revenue metrics. A confidence interval on this quantity can be provided by the ad platform to the advertisers to better inform advertisers' as the ratio between the bid and the value of items, reflects the advertisers' bidding strategy. A con- fidence interval on this quantity could help the ad platform predict its clients bidding behavior and suggest budget management strategy to clients. Finally, Nash social welfare measures the efficiency and fairness of the whole ad platform. We can also use Fisher market to model resource allocation systems in internet companies. For example, in a job recommendation platform, we can model it as a market where we distribute viewer's attention to job post creators. In this context, social welfare measures generally the efficiency of the job recommendation system. Individual utilities track how satisfied the job post creators are with the extent to which their job posts are being recommended.
maasiin..maiig.... Pacing multiplier,
2.2 THE DATA
Assume we are able to observe a market formed by a finite number of items. We let 7y (0......0.} 0.} c Ot be a set of items sampled i.idd from the supply distribution S. We let (1(7) (v,(0)), ),... (.(")) denote the valuation for agent of items in the set 7. For agent i, let = (z)..... ..f.......)......... Re denote the fraction of items given to agent With this notation, the total utility of agent i is (z,, (x()). Similar to the long-run market, we assume the observed market is at equilibrium, which we now define.
Definition (Observed Market Equilibrium). The market equilibrium M8 (b, v, 5) given the item set 7 and the supply vector E IRC, is an allocation allocation-utitliyy -trice tuple (x u,",u,, ,pppp") E (RL )m x RT x BC such that the following holds. (i) Supply feasibility and market clearance: ΣT 27 < O. (ii) Buyer optimality: af E De(p") and uf = (v:(7), for all i, where (overloading notations)
and 1p",1,-> -1-E
De(p) = arg max (12(7),)))) : IG 2 O, (p. S b.)
2:
is the demand set given the prices and the buyer's 's budget.
'In the online budget management literature, pacing means buyers produce bids for items via multiplying his value by a constant.
2 In a linear Fisher market the budgets are extracted fully, i.c., f p" ds = h, in the long-run market and Ex=p"" = b,,, in the observed market (see Appendix E), and therefore there is nothing to infer about revenue in this case. However, in the quasilinear utility model where buyer's utility function is ui(x) (I - p, vz), buyers have the incentive to retain money and therefore one needs to study the statistical properties of revenues.
4

---

Published as a conference paper at ICLR 2023
Assume we have access (x", (t) along with the budget vector b, where (2 u², p²) (b,,b, v, 11) is the market equilibrium (we explain the scaling of 1/t in Appendix E). Note the budget vector b and value functions emphasize two high-lights this model of observation.
(u,(+) are the same those in the long-run ME. We
No convex program solving. The quantities observed are natural estimators of their counterparts in the long-run market, and so we do not need to perform iterative updates or solve optimization problems. One interpretation of this is that the actual computation is done when equilibrium is reached via the utility maximizing property of buyers; the work of computation has thus implicitly been delegated the buyers.
For finite- dimeesinnnn Fisher market, it is well-known that the observed market equilibrium Ml (b, v, 1 Le) can be captured by the following sample EG programs.
max =20,020
NSW(u) u, S (v;(7), xi) Vi, Σ
r. S 1 VT
(S-EG)
==1
min H+(3) = Σ max Bru; (00;(07 (07) ke(n)
be log Bs
(S-DEG)
We list the KKT conditions in Appendix E. Completely parallel to the long-run market, opti- mal solutions Eq. (S-EG) correspond to the equilibrium allocations and utilities, and the opti- mal variable 87 to Eq. (S-DEG) relates to equilibrium prices and utilities through u," = 1,/97. p max; 37 ((T) and 27"" > 0 only if i arg max; (07). By the equivalence between market cquilibrium and EG programs, we use u² and x² to denote the equilibrium and the opti- mal variables. Let NSW == NSW(u)) Ei= by log un All budgets in the observed market is extracted, i.e., Σt=1e" Em.
2.3
DUAL PROGRAMS: BRIDGING DATA AND THE ESTIMANDS
Given the convex program characterization, natural idea is study the concentration behavior of observed market equilibria through these convex programs. We focus on the dual programs Eqs. (S- DRG) and (P-DEG) because they defined in fixed dimension, and that the constraint is also fixed.
Define the sample function F = V, where S(3,0) mu and V by log 3;; the function f is the source of non-smoothness, while Vr provides local strong convexity. Our approach studying concentration of the convex programs in the sense that as grows
1
min H²(3) 6>0
= Σ FF(,0') " " " min H(3) B[F B>0
The local strong convexity of the dual objective motivates us to do the analysis work in the neighbor- hood of the optimal solution S*, In particular, the function x + llo x not strongly convex on the positive reals, but it is on any compact subset. By working on compact subset, we can exploit strong convexity of the dual objective and obtain better theoretical results. is known (Fact 1) that 8: < 3 < B where B, = bi/ v; dS and 3 = Σiibi/ min; J 0; dS. Define the compact set IR",, which must be neighborhood of 3". Moreover, for large-enough we further have B E C with high probability (c.f. Lemma 1).
C= IT_ 12 29
Blanket assumptions. Recall the total supply the long-run market one: f sd = Assume the total item set produce one unit of utility total, i.e., U;s du 1. Suppose budges of all buyers sum to one, i... b 1. Let b min, b, Note the previous budget normalization implies b < 1/n. Finally, for easy of exposition, we assume the values are bounded supe v(()) < 8, for all By the normalization of values and budgets, we know 3r b, and B 1.
5

---

Published as a conference paper at ICLR 2023
3 CONSISTENCY AND FINITE-SAMPAR BOUNDS
In this section we introduce several natural empirical estimators based on the observed market equi- librium, and show that they satisfy both consistency and sih-probabilityy bounds. Below state the consistency results; the formal version can be found in Appendix B.
Theorem (Consistency, informal). The Nash social welfare, pacing multiplier and approximate equilibria in the observed market are strongly consistent estimators of their counterparts in the long-run market.
High Probability Bounds Next, we refine the consistency results and provide finite sample guar- antees. We start by focusing on Nash social welfare and the set of approximate market equilibria. The convergence utilities and pacing multiplier will then be derived from the latter result.
Theorem 2. For any failure probability 0 < 7 1, let t > 20 log (n/n)) Then with probablity greater than 1 1 7,, it holds NNW NSW* I ( logo(nn + t)t) + /log((/n)))=> where ((1) hides only constants. Proof in Appendix I.
Theorem 2 establishes a convergence rate NSW7 - NSW* ( The proof proceeds by first establishing a pointwise concentration inequality and then applies a discretization argument.
Theorem 3 (Concentration of Approximate Market Equilibrium). Let > 0 be tolerance pa- rameter and a E 10,1) failure probability. Then for any 0 S 8 S e/2, to ensure ((C c C B (c)) 21 20 suffices to set
{1 1 (nlog bE e
t O(1 min
26(22+8) c-o
log 2
where the set C - and O(1) hides only absolute constants. Proof in Appendix J.
By construction of C we know 8r E C holds, and so C' know that for t sufficiently large, 8r C with high probability, in which case the set C n 2 (8) is not empty.
Cn. (c) is not empty. By Lemma 1 we
Corollary 1. Let l satisfy Eq. (1). Then with probability 2 1 2o it holds H(8)) < H(3*) +
By simply taking 5 = 0 in Theorem we obtain the above corollary. More importantly. it establishes the fast statistical rate ( - H(8)) = (p(t")) for t sufficiently large, where we use Öp to ignore logarithmic factors. In words, when measured in the population dual objective where take expectation w.r.t. the item supply, 3 converges to 3 with the fast rate 1/1. /.. This is in contrast to the usual 1/V2 rate obtained in Theorem 2, where 87 is measured in the sample dual objective. There the 1/ l/vl rate is the best obtainable.
By the strong-convexity of dual objective, the containment result be translated high- probability convergence of the pacing multipliers and the utility vector.
Corollary 2. Let t satisfy Eq. (1). Then with probability 1-20 2a holds 1 -8 S / ||u" w" ll < /8/bb.
|8 and
We compare the above corollary with Theorem 9 from Gao and Kroer (2022) which establishes the convergence rate of the stochastic approximation estimator based on dual averaging algorithm (Xiao, 2010). In particular, they show that the average of the iterates, denoted ÍDA, enjoys convergence rate of [ADAA~ 3 12 Ö
82 1), where is the number of sampled items. The rate achieved (
= O, (F for sufficiently large. We see that our rate is worse off by factor of n. And yet estimates produced by the strategic behavior of the agents without any extra computation at all. Moreover, the computation of the dual averaging estimator the knowledge of values (0) is required, while again ( can be just observed naturally.
in Corollary 2 is 1

---

Published as a conference paper at ICLR 2023
4 ASYMPTOTICS AND INFERENCE
4.1 ASYMPTOTICS AND ANALYTICAL PROPERTIES OF THE DUAL OBJECTIVE
In this section derive asymptotic normality results for Nash social welfare, utilities and pacing multipliers. As we will see, a central limit theorem (CLT) for Nash social welfare holds under basically no additional assumptions. However, the CLTs of pacing multipliers and utilities will require twice continuous differentiability of the population dual objective H, with a nonsingular Hessian matrix. We present CLT results under such premise, and then provide three sufficient conditions under which H is C² at the optimum.
Theorem (Asymptotic Normality of Nash Social Welfare). holds that
Vi(NSW> - NSW*) SM (0,
where Rsw (o - (So (6'' ds(o) Proof in Appendix K.
To present asymptotics for and u we need bit more notation. Let (,(3) = {0 E θ (0) en 8R vk * i}. i.e., the potential winning set of buyer i when the pacing multiplier are B. Let O (3*). We will see later that if the dual objective is sufficiently smooth at 8 then the winning sets, 0 97,ic [ni. will be disjoint (up to measure-7ero set). Define the variance of winning values for buyer as follows
22 - /0g ((0))s(() (l/ (0)) ((())s(()))
Theorem 5 (Asymptotie Normality of Individual Behavior). Assume H is C² 8 with non- singular Hessian matrix H (8*). Then vi(0n - 3*) 4 N E3) and Vilw - -u")= 4 N M( (0, E.). where Eg . 1 Diag( (0) and Σ,, Diag( b,/((B)))) (Dag)((( Diag( (B7))) Proof Appendix K.
In Theorem we require a strong regularity condition: twice differentiability H, which seems hard to interpret at first sight. Next we derive a set of simpler sufficient conditions for the twice dif- ferentiability of the dual objective. Intuitively, the expectation operator will smooth out the kinks in the piecewise linear function [( 0); even if f non-smooth, is reasonable to hope the expectation counterpart f is smooth, facilitating statistical analysis.
First we introduce notation for characterizing smoothness of Define the gap between the highest and the second -highest bid under pacing multiplier 3 by
(3,0) 0) == max max(B (0), - secondmax (3)o((0)} =sccondmax(3x0(()))
here secondmax is the second -high-t entry: c.g., secondmax([1, 1,2) = 1. When there a tie for item 0, have c(3,,) 0)
O. When there is no tie for item 0. the gap c(3, A) strictly positive. Let G(B, 0) E @f3,0) 0) be an element in the subgradient set. The gap function characterizes smoothness of f: f(-,0)
0) is differentiable at + <(3,0) is strietly posi- tive, in which case G(3,0) = a 0) (x(3.0) with e; being the i-th unit vector and i(B, 8) = arg max, (8). When f(..0) is differentiable at B a.s., the potential winning sets (3)); disjoint (up to a measure-zero set).
Theorem (First-order differentiability). The dual objective H is differentiable at a point B if and only if
c(3,0) co, for S-almost every 0.
(NO-TIE)
When Eq. (NO-TIE) holds, f((3) = E E(G(B, 0).. Proof and further technical remarks in Appendix L.
Given the neat characterization of differentiability of dual objective via the gap function eB, 0), it is then natural to explore higher-order smoothness, which was needed for some asymptotic normality results. We provide three classes of markets whose dual objective H enjoys twice differentiabilityy Theorem 7 (Second-order differentiabilityy Informal). If any one of the following holds, then H is C2 at Sr. (i) A stronger form of Eq. (NO-TIE) holds, e.g., Eje(B,e) "1 ess supa (c(3, -)13 is finite in a neighborhood of 3+. (ii) The distribution of v = (Vi...., v.) - R" is smooth enough. (üi) O = [0, 1] and the valuations vz(.)² are linear functions.
7

---

Published as a conference paper at ICLR 2023
4.2 INFERENCE
In this section we discuss constructing confidence intervals for Nash social welfare, the pacing multipliers, and the utilities. We remark that the observed NSW, NSW?, is a regatively-biaser estimate of the NSW, NSW", of the long-run ME, i.e., E|NSW>] - NSW* < 0.3 Moreover, can be shown that, when the items are i..d. Emmin H,] I Elmin H++1 using Proposition 16 from Shapiro (2003). Monotonicity tells us that increasing the size of market produces on average less biased estimates of the long-run NSW.
To construct a confidence interval for Nash social welfare one needs to estimate the asymptotic vari- + 0T) H)( (+ (p².T)²) 1. where p is
ance. We let Nsw the price of item d" in the observed market. We emphasize that in the computation of the variance estimator 2ww one does not need knowledge of values (())))) All that is needed is the equi- librium prices pd (p>:1 ,........> ,...,,"... p,..)) of the items. Given the variance estimator, we construct the CNew
confidence interval [NSW" + 2a/2 vt where 2a is the a-th quantile of standard normal. The next theorem establishes validity of the variance estimator.
Theorem 8. It holds that ŌNSW 2+ sssw- Given O < a < 1, it holds that lim P(NSW* E Proof in Appendix M.
INST + 2./22/ss//// /it)
Estimation of the variance matrices for B and more complicated. The main difficulty lies in estimating the inverse Hessian matrix. Due to the non-smoothness of the sample function, we cannot exchange the twice differential operator and expectation, and thus the plug-in estimator, i.e., the sample average Hessian, is biased estimator for the Hessian of the population function in general. In Appendix D we provide brief discussion of variance estimation under the following two simplified scenarios. First, in the case where E[e(3, 0}1 < co holds in neighborhood of 3". which we recall is a stronger form Eq. (NO-TIE), we prove that plug-in type variance estimator is valid. Second, if we have knowledge of {v.(fT)).. then give numerical difference estimator for the Hessian which consistent.
GUIDE TO PRACTITIONERS
We close our theoretical development with practical instructions on how to construct confidence interval with results presented so far. Revenue inference is only well-defined in the context of quasilinear market, which we explore in Appendix
Inference on NSW. Recall b, is the budget of agent i and let uf be the observed utility. Let NSW? Ei_nb, log u be the NSW in the observed market. This will be a good estiamte of the limit NSW and as the number of items grows, it converges quickly at a rate of 1/VE. To construct a CI we need to estimate the asymptotic variance. Let 2sw = the price of item 0² and pd is the average price. In words, 2 is the variance of prices. Then a (1 a) CI for the NSW in the long-run market will be [NSWT + Za/2ōNsW/ Vt]. where za is the (1 11-a] ath quantile of a standard normal.
+ - -')² where pas is
Inference on 3 and n": simplified inference with bid-gap condition. Suppose in the ad auction platform one observes that for each item the winning bid is always higher than the swe- cond bid by some amount, then we could use the following inference procedure. For precise statement of the condition see Theorem 10. When such a condition holds, the variance expression in Theorem simplifies. Let Ω be the variance of item utility that are allocated to buyer i, i.e., 2 := [tu? ? where u??T = u,?T,,(('' (,(0") is the utility buyer i obtains from item 0r. Define the asymptotic variance estimators Σn Diag( ($7)(*7/666)) and E. Diag (f?)). The confidence regions for 8 and u* are ellipsoids that center around 8 and u². Concretely, CR3 8 + (Xn,a/ v and the confidence region for u" is CR, u" + (xna/Vi) Et) where X is the (1 -h quantile of chi-square with degree i and B is the unit ball RR..
Inference on 8" and u²: robust approach. Under fairly general setting, which is justified in Section 4.1, the following inference procedure is valid. Choose a smoothing level n, to be
Note E[NSW"] NSW* E[ming H.()) H(8*) S mins (3)) H(8") 0.
8

---

Published as a conference paper at ICLR 2023
chosen roughly of order 1nt = w(1/vt), construct the following matrix H whose (i. (.tj)tth entry is (1 = zng (1 + (e(e + ej)) H, + (r(-,, + e,)) He + Te e₁)) + H, + =n(_;; - 0,))). This will be an estimate of the Hessian matrix of the dual objective. Here H; defined in Eq. (S-EG) needs only values of the realized items but not the value functions v:(s)s. Let Σ.g = H DDag (()) (=)))==----- and Σ. = Diag (( (())) Diag (0:/ ()) be the estimated covariance matrices. We can then construct confidence regions CR3 and CR2 as above.
Bootstrap. Though not studied in this paper, bootstrap inference is a valuable alternative. In a bootstrap procedure, one samples the items with replacement and solve the EG programs (S-EG) or (S-DEG). By repeating this we obtain sequence of estimates say , ,....,, where B is the number of bootstrap batches. Then a confidence interval is constructed by the sample quantiles of the sequence ( )e([B)-
6 EXPERIMENTS
We conduct experiments to validate the theoretical findings, namely, the convergence of NSW? to NSW (Theorem 9) and CLT (Eq. (2)). All figures can be found in Appendix O.
Verify convergence of NSW to its infinite-dimmnniooall counterpart in a linear Fisher market. First, we generate an infiniteddimensional market Mi of 50 buyers each having a linear valu- ation (f) = 0,8 + C; on θ = [0, 1]. with randomly generated a; and C such that (,) 2 on [0, 1]. Their budgets b; also randomly generated. We solve for NSW* using the tractable con- vex conic formulation described in Gao and Kroer (2022, Section 4). Then, following Section 2.2, for the j-th (j E [k]) sampled market of size t, we randomly sample {0',7 JrejH uniformly and independently from [o, 1] and obtain markets with n buyers and items, with individual valuations (=()"") = a.09.- + Cr. J E [t]. We take i = 100,200, 200, 5000 and = 10. We compute their equilibrium Nash social welfare, i.e., NSW", and their means and standard errors over l repeats across all t. As can be seen from Fig. 2, NSW7 values quickly approach NSW", which align with the a.s. convergence of NSW7 in Theorem 9. Moreover, NSW? values increase as / increase, which align with the monotonicity observation in the beginning of Section 4.2.
Verify asymptotic normality of NSW in a linear Fisher market. Next, for the same infinite- dimensional market My, we set 5000, sample k 50 markets of items analogously, and compute their respective NSW7 values. We plot the enpirical distribution of VE(NSW" - - and the probability density of N (0, NNww). where &sw is defined in Theorem 4.4 Theorem
shows that VF(NSW> - NSW*) $.4(0. (o..). As can be seen in Fig. 5, the empirical distribu- tion is close to the limiting normal distribution. A simple Bolmogorov-Sminno test shows that the empirical distribution appears normal, that is, the alternative hypothesis of it not being a normal distribution is not statistically significant. This is further corroborated by the Q-Q plot in Fig. 4, as the plots of the quantiles of VE(NSWT-NSWV values against theoretical quantiles of N (O, k appear to be a straight line.
Verify NSW convergence in multidimensional linear Fisher market. Finally, consider an infinite-dimensionall market Me with multidimensional linear valuations (0) = a. 0 + er ag IR: We similarly sample markets of sizes / 100, 200, .... 5000 from Mr, where the items g¹. j E [k] are sampled uniformly and independently from [0, 10 As can be seen from Fig. 2, NSW? values increase and converge to fixed value around 11995. In this case, the underlying true value NSW* (which should be around -1.995) cannot be captured by tractable optimization formulation.
"To compute s'sw: use the fact that p² max, 8 (8) is piecewise lincar function, since are linear. Following (Gao and Kroer, 2022, Section 4), we can find the breakpoints of the pure equilibrium alloca- tion 0 = ao 01 < <... < @so and the corresponding interval of each buyer i. Then, So (p" (0))))asss))) amounts to integrals of quadratic functions on intervals.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research was supported by the Office of Naval Research Young Investigator Program under grant N00014-22-1-2530, and the National Science Foundation award IIS-2147361.
REFERENCES
Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: Analysing food bank problem. arXiv preprint arXiv: 152.00777,. 2015.
Amine Allouah, Christian Kroer, Xuan Zhang, Vashist Avadhanula, Anil Dania, Caner Goemen, Sergey Pupyrev, Parikshit Shah, and Nicolas Stier. Robust and fair work allocation, 2022. URL https: arxiv.iii.v.///.v org/ als 2202222222222 05194.
Peter Aronow and Cyrus Samii. Estimating average causal effects under general interference, with application to a social network experiment. The Annals of Applied Statistics, 11(4))1912- 1947, 2017.
Susan Athey, Dean Eckles, and Guido W Imbens. Exact p-values for network interference. Journal of the American Statistical Association, 113(521):230-265 240, 2018.
Yossi Azar, Niv Buchbinder, and Kamal Jain. How to allocate goods in online market? Algorith- mica, 74(2):589-600 601, 2016.
Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19. SIAM, 2022.
Heinz H Bauschke, Patrick L Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
Amir Beck. First-Order Methods Optimization, volume 25. SIAM, 2017.
Xiaohui Bei, Jugal Garg, and Martin Hoefer. Ascending-pria price algorithms for unknown markets. ACM Transactions on Algoritims (TALG), 15(3):1-33, 2019a.
Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Earning and utility limits in fisher
markets. ACM Transactions on Economics and Computation (TEAC), 7-2): 2019b.
Dimitri Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Jour- nal of Optimization Theory and Applications, 12(2):218 211-1,,,, 1973.
Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao. Distributed algorithms via gradient descent for fisher markets. In Proceedings of the 12th ACM Conference on Electronic Commerce, pages 127-136. ACM, 2011.
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mohammad Mahdian. Dynamics of bid optimization in online advertisement auctions. In Proceedings of the 16th international conference on World Wide Web, pages 531-540, 2007.
Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 11666):061-11100 2011.
Eric Budish, Gérard P Cachon, Judd B Kessler, and Abraham Othman. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314 2016.
Joannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 2016 ACM Conference Economics and Computation, pages 305-322. ACM, 2016.
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1-32, 2019.
10

---

Published as a conference paper at ICLR 2023
Sarah H. Cen and Devavrat Shah. Regret, stability & faimess in matching markets with bandit learners. In International Conference on Artificial Intelligence and Statistics, pages 8938-28 8968. PMLR, 2022.
Lihua Chen, Yinyu Ye, and Jiawei Zhang. A note on equilibrium pricing convex optimization. In International Workshop on Web and Internet Economics, pages 7-16. Springer, 2007.
Yun Kuen Cheung, Richard Cole, and Nikhil R Devanur. Tatonnement beyond gross substitutes? Gradient descent the rescue. Games and Economic Behavior, 123:295-322 2020.
Richard Cole and Lisa Fleischer. Fast-converging tatonnement algorithms for one-time and ongoing market problems. In Proceedings of the fortieth anmual ACM symposium Theory of computing, pages 315-324, 2008.
Richard Cole and Vasilis Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM Journal on Computing, 47(3):1211-12366 2018.
Richard Cole, Nikhil R Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex program duality, fisher markets, and Nash social welfare. In 18th ACM Conference on Economics and Computation, EC 2017. Association for Computing Machinery, Inc, 2017.
Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier-Moses, Eric Sodomka, and Christopher Wilkens. Pacing equilibrium in first price auction markets. Management Science, 2022a.
Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Moser. Multiplicative pacing equilibria in auction markets. Operations Research, 702))963-989, 2022b.
Xiaowu Dai and Michael Jordan. Learning in multi-stage decentralized matching markets. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 12798- 12809. Curran As- sociates, Inc., 2021. URL https: htt.tts::/ppccceeinggg.oooo neurips....... httpp.ccp/paaae wwtpcppppppppp.eeeeec. pttpppppee/22///11e..e/ 22211/f1ee 6a571 (e5 8a 2 ba
pdf..
Xiaotie Deng, Christos Papadimitriou, and Shmuel Safra. On the complexity of price equilibria. Journal of Computer and System Sciences, 67(2):311-324, 2003.
Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Competitive equilibrium via primal-dual algorithm for convex program. Journal of the ACM (JACM), 55 (5):1-18, 2008.
Nikhil R Devanur, Jugal Garg, Ruta Mehta, Vijay V Vaziranb, and Sadra Yazdanbod. A new class of combinatorial markets with covering constraints: Algorithms and applications. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2311-2325. SIAM, 2018.
Edmund Eisenberg. Aggregation of utility functions. Management Science, 7(4):337-350, 1961.
Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statisties, 30(1):165-16) 168, 1959.
Yuan Gao and Christian Kroer. First-order methods for large-scale market equilibrium computation. In Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
Yuan Gao and Christian Kroer. Infinite-dimensinn fisher markets and tractable fair division. Op- eration Research, Forthcoming, 2022.
Yuan Gao, Christian Kroer, and Alex Peysakhovich. Online market equilibrium with application to fair division. arXiv preprint arXiv:2103. 2021.
Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and lon Stoica. Dominant resource faimess: Fair allocation multiple resource types. Nsdi, volume 11, pages 24 24, 2011.
11

---

Published as a conference paper at ICLR 2023
Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. The remarkable robustness of the repeated fisher market. Available at SSRN 1444, 2019.
Wenshuo Guo, Kirthevasan Kandasamy, Joseph E Gonzalez, Michael Jordan, and lon Stoica. On- line learning of competitive equilibria in exchange economies. arXiv preprini arXiv:2106. 11X6662006.06616. 2021.
Nils Lid Hjort and David Pollard. Asymptotics for minimisers of convex processes. arXiv preprint arXiv: 107.331077 2011.
Yuchen Hu, Shuangning Li, and Stefan Wager. Average direct and indirect causal effects under interference. Biometrika, 2022.
Michael G Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the American Statistical Association, 103(482):832-844 842, 2008.
Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. Journal of the ACM (JACM), 65(1):1-33, 2017.
Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. Learning equilibria in matching markets from bandit feedback. Advances in Neural Information Processing Systems, 34:3323-3335, 2021.
Kamal Jain. A polynomial time algorithm for computing an arrow-debreu market equilibrium for linear utilities. SIAM Journal on Computing, 37 2007.
Ian Kash, Ariel D Procaccia, and Nisarg Shah. No agent left behind: Dynamic fair division of multiple resources. Journal of Artificial Intelligence Research, 51:579-603, 2014.
Sujin Kim, Raghu Pasupathy, and Shane G. Henderson, Guide to Sample Average Approximation, pages 207-243. Springer New York, New York, NY, 2015. doi: 11007/978-1-49383 1-4939-1384-88 8.
Christian Kroer and Alexander Peysakhovich. Scalable fair division for 'at most one" preferences. arXiv preprint arXiv: htt.:1999..192.... 2019.
Christian Kroer and Nicolas Stier-Moses. Market equilibrium models in large-scale internet mar- kets. Innovative Technology at the Interface of Finance and Operations. Springer Series in Supply Chain Management. Springer Natures, Forthcoming, 2022.
Christian Kroer, Alexander Peysakhovich, Eric Sodomka, and Nicolas E Stier-Moses. Computing large competitive equilibria using abstractions. Operations Research, 2021.
Michael Leung. Treatment and spillover effects under network interference. Review of Economics and Statistics, 102(2):368-385) 2020.
Shuangning Li and Stefan Wager. Random graph asymptotics for treatment effect estimation under network interference. The Annals of Statistics, 50(4):2334-233 22054222381111 2022.
Luofeng Liao, Yuan Gao, and Christian Kroer. Nonstationary dual averaging and online fair alloca- tion. arXiv preprini arXiv:2202.1 1614v1, 2022.
Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. J. Mach. Learn. Res., 22:211-1, 2021.
Zhihan Liu, Miao Lu, Zhaoran Wang, Michael Jordan, and Zhuoran Yang. Welfare maximization in competitive equilibrium: Reinforcement learning for markov exchange economy. In International Conference on Machine Learning, pages 13870-13911. PMLR, 2022.
Duncan McElfresh, Christian Kroer, Sergey Pupyrev, Eric Sodomka, Karthik Abinav Sankarara- man, Zack Chauvin, Neil Dexter, and John P Dickerson. Matching algorithms for blood donation. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 463-464, 2020.
12

---

Published as a conference paper at ICLR 2023
Yifei Min, Tianhao Wang, Ruitu Xu, Zhaoran Wang, Michael Jordan, and Zhuoran Yang. Learn to match with no regret: Reinforcement learning in markov matching markets. arXiv preprint arXiv:2203.03684, 2022.
Evan Munro, Stefan Wager, and Kuang Xu. Treatment effects market equilibrium. arXiv preprint arXiv:2109.16647 2021.
Riley Murray, Christian Kroer, Alex Peysakhovich, and Parikshit Shah. Robust market equilbrria with uncertain preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020a.
volume 34, pages hoam://g222/////ooommmnarreellee
Riley Murray, Christian
Kroer, Alex https://resaarch. http:://eeearr....ccom//o/////// preferences/, Sep 2020b.
Peysakhovich, and Parikshit Shah. hon---o-mmodl--nneetti------a-e
Yurii Nesterov and Vladimir Shikhman. Computation of fisher-gale equilibrium by auction. Journal of the Operations Research Society of China, 6(3):399-38)) 2018.
Whitney Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Hand- book of econometrics, 4:211 1-2245, 1994.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge University Press, 2007.
Abraham Othman, Tuomas Sandholm, and Eric Budish. Finding approximate competitive equilibria: efficient and fair course allocation. In AAMAS, volume 10, pages 873 880, 2010.
Abraham Othman, Christos Papadimitriou, and Aviad Rubinstein. The complexity of fairness through equilibrium. ACM Transactions Economics and Computation (TEAC), 4(4):1-19, 2016.
David Parkes, Ariel D Procaccia, and Nisarg Shah. Beyond dominant resource faimess: Ex- tensions, limitations, and indivisibilities. ACM Transactions Economies and Computation (TEAC), 2015.
Alexander Peysakhovich and Christian Kroer. Fair division without disparate impact. Mechanism Design for Social Good, 2019.
Tyrrell Rockafellar. Convex analysis, volume 18. Princeton university press, 1970.
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Roshai Sahoo and Stefan Wager. Policy learning with competing agents. arXiv preprint arXiv:2204.01884, 2022.
Alexander Shapiro. Asymptotic properties of statistical estimators in stochastic programming. The Annals of Statistics, 17(2):841-858 1989.
Alexander Shapiro. Monte carlo sampling methods. Handbooks in operations research and man- agement science, 10:353-425, 2003.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic program- ming: modeling and theory. SIAM, 2021.
Vadim Shmyrev. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3(4):505, 2009.
Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve. In Abstracts of the 2022 SIGMETRICS/Peffrmmmnc Joint International Conference Measurement and Modeling of Computer Systems, 2022.
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1)633-9, 1974.
13

---

Published as a conference paper at ICLR 2023
Vijay V. Vazirani. Combinatorial Algorithms for Market Equilibria, pages 103-134, Cambridge University Press, 2007. doi: 10.1017/CB09780511 1800481.007.
Stefan Wager and Kuang Xu. Experimenting in equilibrium. Management Science, 67(16)66
6715, November 2021. doi: 10.1287/mmsc22020.355 URL
wtw.eei................ooooooeee 10.17277
mnsc. mnsc.2020..0 3844.
Jinde Wang. Distribution sensitivity analysis for stochastic programs with complete recourse. Math- ematical Programming, 31(3):286- 297, 1985.
Fang Wu and Li Zhang. Proportional response dynamics leads to market t equilibrium. Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pages 354-363, 2007.
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-2596, 2010.
Yinyu Ye. A path to the arrow debreu competitive market equilibrium. Mathematical Programming, 11(())315-348, 2008
Li Zhang. Proportional response dynamics in the fisher farket. Theoretical Computer Science, 412 (24):2691-2688, 2011.
14


Reviews:
[{"review_id": "qlArwTb4Tud", "reviewer": "Reviewer_CZ5S", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers statistical inference in linear Fisher markets. In their framework, a market formed by a finite number of items sampled from an underlying distribution is observed and their goal is to infer several important equilibrium quantities (individual utilities, pacing multipliers, and social welfare) of the underlying long-run market. \n\n", "summary_of_the_review": "This paper considers statistical inference in linear Fisher markets. Finite-sample bounds, CLT, and statistical inference of a few metrics are derived. The technical contribution is strong as the inference for Fisher markets is non-trivial. However, there are a few major concerns listed in the weakness part. If the authors can nicely address these weakness parts, I am willing to increase my rating later. \n\n", "strength_and_weaknesses": "Strength:\n\n1. Despite numerous algorithmic results available for computing Fisher market equilibria, limited statistical inference result was available for quantifying the randomness of market equilibrium. \n\n2. These statistical inference results (CLT and confidence intervals) are highly non-trivial. One technical challenge is that the dual objective is potentially not twice differentiable and hence it requires new technical tools. So the technical novelty is strong.\n\n\nWeaknesses:\n\n\n1. Writing: The writing of the paper can be further improved. \n\n(1) The current version assumes that readers have good knowledges of Fisher markets and market equilibrium. However, this may not be the case for general ICLR readers. It would be helpful to add some background on these topics and provide some real examples of Fisher markets. In addition, some parts of Gao and Kroer (2022) can be included in the appendix of this paper. \n\n(2) The whole paper is very technical and is hard to follow. It would be helpful to check if some of the math notation and math definition can be simplified or moved to the Appendix. The theoretical results include consistency, finite-sample bounds, CLT, and finally variance estimation for constructing confidence intervals. In my personal opinion, the most interesting part is the CLT and confidence interval parts, followed by the finite-sample bounds. The consistency result is of less interests and can be inferred from the finite-sample bounds. It might be helpful to list key theoretical results in the main paper to save space for additional explanations. In addition, the whole Section 5 on the extension to quasilinear fisher market can be moved to the appendix. This section could also be added in a journal version. On the other hand, some of the numerical experiments in Section M of the appendix may be moved to the main paper. \n\n\n2. Motivation. It would be helpful to add more justifications on why the statistical inference for linear Fisher market equilibrium is useful. There are two concerns. \n\n(1) The authors claimed in the Introduction that statistical inference can be used to \"quantify the variability of the resources/fairness/efficiency metrics of interest in the long run\". But why do we want to quantify the variability of these metrics in the long run? The example of Internet ad auction markets used in the Introduction did not fully answer this question. Why should an internet company care about the statistical inference of these metrics considered in this paper?\n\n(2) This paper considers a linear Fisher markets where the valuation for each buyer is linear. Although this helps the theoretical developments, such assumptions might be restrictive in practice. Interestingly, the ad auction markets example (Conitzer et al., 2022a) provided in the Introduction of this paper actually corresponds to a quasilinear Fisher market. More justifications on the linear fisher markets would be needed. \n\n\n3. Real data analysis. This is related to the previous comment. It would be more convincing if a real data study is added. \n\n\n4. Constructing confidence intervals for the pacing multipliers and the utilities. In Section 4.3 Inference, Theorem 8 only contains the inference result for Nash social welfare because the estimation of the variance for $\\beta$ and $u$ is more complicated. In the later case, the plug-in estimator is no longer suitable. Can we use Bootstrap method to estimate the variance? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "qCGwHcm9X9S", "reviewer": "Reviewer_8p3H", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThe paper proposes a statistical framework to estimate linear Fisher markets with a continuum distribution over items from observed markets with finitely many items drawn from the distribution. A linear Fisher market consists of a continuum set of items with predetermined supplies and a finite set of buyers (each with a potentially different budget and different valuations for items). The market outcome is an allocation of items to buyers along with prices. The goal is to estimate certain quantities at equilibrium in the continuum market: (1) individual utilities received by buyers, (2) pacing multipliers (defined by the budget divided by the utility), and (3) Nash social welfare. The paper examines the statistical properties of equilibrium market quantities from the observed market with finitely many items as estimators for the corresponding quantities of the continuum market. The main results are showing the following: (A) consistency of these estimators and finite sample bounds for the Nash social welfare, the individual utilities, and the pacing multipliers, (B) convergence of approximate market equilibria, and (C)  asymptotic normality of the Nash social welfare. ", "summary_of_the_review": "The paper investigates statistical considerations that arise in linear Fisher markets and contributes to an emerging line of work bridging statistics and market equilibria. The main weakness is the motivation for how the observed quantities are set up in this paper. Despite this weakness, the paper offers a number of informative insights about the convergence guarantees of linear Fisher markets. ", "strength_and_weaknesses": "Strengths\n- The paper bridges linear Fisher markets with statistical inference in an interesting manner. The results on fundamental statistical properties—consistency and asymptotic normality—in the context of a classical market are insightful. \n- The technical results in the paper—especially the consistency results and finite sample bounds as well as asymptotic normality—are mathematically clean and clearly explained. \n\nWeaknesses\n- The main weakness of this paper is in the motivation for the setup. In particular, the paper assumes the observed data comes from a market equilibrium from a finite item sample of the underlying continuum market. However, the paper does not provide much motivation for this modeling choice. Why it is not more natural for the learner to have data from a noisy version of the continuum item market, e.g. the equilibria formed under random perturbations in the values of agents? \n- What are the statistical properties of other measures of social welfare besides Nash social welfare? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WWjaXHX_4Vm", "reviewer": "Reviewer_PJb7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors have proposed a statistical framework based on the concept of infinite dimensional Fischer markets. This study attempted a marked formed by the finite number of items sampled from an distribution to infer several equilibrium quantities such as individual utilities, social welfare, and pacing multipliers of the underlying long-run market. ", "summary_of_the_review": "This paper provides good readability but it has gone in depth to analyze/explain the theoretical algorithm in detail on the fisher market equilibrium.\nThis article is an incremental work of Gao and Kroer (2022) and extended the Fischer market model and proposed a statistical model based on their infinite-dimensional Fischer Market. ", "strength_and_weaknesses": "Strengths\nThe article is well written with sufficient support from literature; the proposed method and its limitations are well written and gives good readability. \nResults and conclusion adhere to the style of writing and provides better readability and clarity.\nDetailed theoretical and empirical evaluation \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster