Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
47,956 characters · 11 sections · 23 citation commands
Statistical Inference for Fisher Market Equilibrium
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 a corresponding allocation, such that demand equals supply.
One important application of market equilibrium (ME) is fair allocation using the competitive equilibrium from equal incomes (CEEI) mechanism varian1974equity. In CEEI, each individual is given an endowment of faux currency and reports her valuations for items; then, a 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 (ref) 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 equilibrium. 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 mcelfresh2020matching, or donated food to charities in different neighborhoods aleksandrov2015online,sinclair2021fairness, it is crucial to quantify the variability of the amount of resources (blood or food donation) received by the participants (hospitals or charities) of these systems as well as the variability of fairness and efficiency metrics of interest in 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 revenue inference in Internet ad auction markets. While much of the existing literature uses expected revenue as performance metrics, statistical inference on revenue is challenging due to the complex interaction among bidders under coupled supply constraints and common price signals. As shown by conitzer2022pacing, in budget management through repeated first-price auctions with pacing, the optimal pacing multipliers correspond to the “prices-per-utility” of buyers in a quasilinear Fisher market at equilibrium. Given the close connection between various solution concepts in Fisher market models and first-price auctions, a statistical framework enables us 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 (ref).
Our contributions are as follows.
A statistical Fisher market model. We formulate a statistical estimation problem for Fisher markets based on the continuous-item model of gao2022infinite. We show that when a finite set of goods are sampled from the continuous model, the observed ME is a 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. In developing central limit theorems for pacing multipliers and utilities in Fisher markets ((ref)), we note that the dual objective is potentially not twice differentiable. This is a required condition, which is 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 a set of stochastic differentiability conditions in 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.
\noindentNotation. For a sequence of events $A_n$ we define the set limit by $ \liminf _{n \rightarrow \infty} A_{n}=\bigcup_{n \geq 1} \bigcap_{j \geq n} A_{j} =\{ A_t \text{ eventually}\}$ and $\limsup_{n \to \infty } A_{n}=\bigcap_{n \geq 1} \bigcup_{j \geq n} A_{j} = \{ A_t \text{ i.o.}\}$. For vector $a,b\in {\mathbb R^n}$ we let $a{\cdot} b$ be the elementwise product and let $a_{-i} \in {\mathbb R}^{n-1}$ be the vector $a$ with the $i$-th entry removed. For vector $a$ we let $[a_{(1)},\dots, a_{(n)}]$ denote the sorted entries of $a$ from greatest to least. Let $[n] = \{1,\dots, n\}$. We use $1_t$ to denote the vector of ones of length $t$ and $e_j$ to denote the vector with one in the $j$-th entry and zeros in the others. For a sequence of random variables $\{X_n\}$, we say $X_n = O_p(1)$ if for any $\epsilon > $ there exists a finite $M_\epsilon$ and a finite $N_\epsilon$ such that ${\mathbb P}(|X_n| > M_\epsilon) < \epsilon$ for all $n\geq N_\epsilon$. We say $X_n = O_p(a_n)$ if $X_n/a_n = O_p(1)$. We use subscript for indexing buyers and superscript for items. If a function $f$ is twice continuously differentiable at a point $x$, we say $f$ is $C^2$ at $x$.
Following gao2022infinite, we consider a Fisher market with $n$ buyers (individuals), each having a budget $b_i>0$ and a (possibly continuous) set of items $\Theta$. We let $L^p$ (and $L^p_+$, resp.) denote the set of (nonnegative, resp.) $L^p$ functions on $\Theta$ for any $p\in [1, \infty]$ (including $p=\infty$). The item supplies are given by a function $ s \in L^\infty_+$, i.e., item $\theta\in \Theta$ has supply $s(\theta)$. The valuation for buyer $i$ is a function $v_i \in L^1_+$, i.e., buyer $i$ has valuation $v_i(\theta)$ for item $\theta\in \Theta$. For buyer $i$, an allocation of items $x_i \in L^\infty_+$ gives a utility of \[ u_i(x_i) := \langle v_i, x_i \rangle := \int_\Theta v_i(\theta) x_i(\theta) \mathop{}\!\mathrm{d} \mu(\theta),\] where the angle brackets are based on the notation of applying a bounded linear functional $x_i$ to a vector $v_i$ in the Banach space $L^1$ and the integral is the usual Lebesgue integral. We will use $x\in (L^\infty_+)^n$ 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 $p\in L^1_+$. The price of item $\theta\in \Theta$ is $p(\theta)$. Without loss of generality, we assume a unit total supply $\int_\Theta s \mathop{}\!\mathrm{d} \mu = 1$. We let $S(A) \vcentcolon= \int_A s(\theta)\mathop{}\!\mathrm{d} \mu(\theta)$ be the probability measure induced by the supply $s$.
Linear Fisher market equilibrium can be characterized by convex programs. We state the following result from gao2022infinite 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.
Concretely, the optimal primal variables in (ref) corresponds to the set of equilibrium allocations $x^*$ and the unique equilibrium utilities ${ u^* }$, and the unique optimal dual variable ${\beta^*}$ of (ref) relates to the equilibrium utilities and prices through
We call ${\beta^*}$ 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: $\int {p^*} \mathop{}\!\mathrm{d} S = { \sum_{i=1}^n } b_i$; we discuss quasilinear model in (ref).
We formally state the first-order conditions of infinite-dimensional EG programs and its relation to first-price auctions in (ref) in appendix. Also, we remark that there are two ways to specify the valuation component in this model: the functional form of $v_i(\cdot)$, or the distribution of values $v:\Theta \to {\mathbb R^n_+}$ when view as a random vector. More on this in (ref).
We are interested in estimating the following quantities of the long-run market equilibrium. (1) Individual utilities at equilibrium, $u^*_i$. It directly reflects how much a buyer benefits from the market. (2) Pacing multipliers ${\beta^*_i} = b_i/ { u^*_i }$. From an optimization perspective, it is simply the optimal dual variable of the EG program (ref). However, its role deserves more explanation. Pacing multiplier has a two-fold interpretation. First, through the equation ${\beta^*_i} = b_i/{ u^*_i }$ it measures the price-per-utility that a buyer receives. Second, through the equation ${p^*}(\theta) = \max_i {\beta^*_i} { v_i(\theta) }$, $\beta$ can also be interpreted as the pacing policy\footnote{In the online budget management literature, pacing means buyers produce bids for items via multiplying his value by a constant.} employed by the buyers in first-price auctions. In our context, buyer $i$ produces a bid for item $\theta$ by multiplying the value by $\beta_i$, then the item is allocated via a first-price auction. This connection is made precise in conitzer2022pacing from a game-theoretic point of view. The pacing multiplier $\beta$ serves as the bridge between Fisher market equilibrium and first price pacing equilibria and has important usage in online ad auction for characterizing the strategic behavior of advertisers. (3) The (logarithm of) Nash social welfare (NSW) at equilibrium
NSW measures total utility of the buyers in a way that is more fair than the usual social welfare, which measures the sum of buyer utilities, because NSW incentivizes more balancing of buyer utilities. (4) The revenue. Linear Fisher market extract the budges fully, i.e., $ \int {p^*} \mathop{}\!\mathrm{d} S = { \sum_{i} } b_i$ in the long-run market and ${\sum_{\tau=1}^{t}} { p ^ {\gamma, \tau} } = { \sum_{i} } b_i$ in the observed market (see (ref)), and therefore there is nothing to infer about revenue in this case. However, in the quasilinear utility model where buyer's utility function is $u_i(x) = {\langle} x - p, v_i{\rangle}$, buyers have the incentive to retain money and therefore one needs to study the statistical properties of revenues. This is discussed in (ref).
As we will see later, their counterparts in the observed market (to be introduced next) will be good estimators for these quantities.
Assume we are able to observe a market formed by a finite number of items. We let ${ \gamma } = \{ \theta_1,\dots, \theta_t\} \subset \Theta^t$ be a set of items sampled i.i.d.\ from the supply distribution $S$. We let $v_i(\gamma) = \big(v_i (\theta^1), \dots, v_i(\theta^t)\big)$ denote the valuation for agent $i$ of items in the set $\gamma$. For agent $i$, let $x_i = (x^1_i,\dots, x^t_i) \in {\mathbb R}^t$ denote the fraction of items given to agent $i$. With this notation, the total utility of agent $i$ is $\langle x_i , v_i(\gamma) \rangle$.
Similar to the long-run market, we assume the observed market is at equilibrium, which we now define.
Assume we have access to $({ x^{\gamma} }, u^\gamma ,{ p ^ {\gamma} })$ along with the bid vector $b$, where $({ x^{\gamma} }, u^\gamma ,{ p ^ {\gamma} })={ \mathcal{ME}^\gamma} (b, v, \frac1t 1_t)$ is the market equilibrium (we explain the scaling of $1/t$ in (ref)). Note the budget vector $b$ and value functions $v=\{v_i(\cdot)\}_i$ are the same as those in the long-run ME. We emphasize two high-lights in this model of observation.
Dependency on realized values $\{{ v_i(\theta^\tau) }\}_{i,\tau}$ and value functions $v_i(\cdot)$. In contrast to several online methods for computing long-run market equilibrium with convex optimization methods gao2021online,liao2022dualaveraging,azar2016allocate where one needs knowledge of the values of items from buyers to produce an estimate of ${\beta^*}$, here we only need to observe the equilibrium allocation, utilities and prices.
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 to the buyers.
For finite-dimensional Fisher market, it is well-known that the observed market equilibrium ${ \mathcal{ME}^\gamma}(b,v,\frac1t 1_t)$ can be captured by the following sample EG programs.
We list the KKT conditions in (ref). Completely parallel to the long-run market, optimal solutions to (ref) correspond to the equilibrium allocations and utilities, and the optimal variable $\beta^\gamma$ to (ref) relates to equilibrium prices and utilities through $ u^\gamma_i = b_i/\beta^\gamma_i$ and ${ p ^ {\gamma, \tau} } = \max_i \beta^\gamma_i { v_i(\theta^\tau) }$. By the equivalence between market equilibrium and EG programs, we use $u^{ \gamma }$ and $x^{ \gamma }$ to denote the equilibrium and the optimal variables. Let
All budgets in the observed market is extracted, i.e., ${\sum_{\tau=1}^{t}} { p ^ {\gamma, \tau} } = { \sum_{i=1}^n } b_i$.
Given the convex program characterization, a natural idea is to study the concentration behavior of observed market equilibria through these convex programs. Such an approach is closely related to M-estimation in the statistics literature (see, e.g., van2000asymptotic,newey1994large) and sample average approximation (SSA) in the stochastic programming literature (see, e.g., shapiro2021lectures, shapiro2003monte and Kim2015). However, for the primal program (ref), the dimension of the optimization variables is changing as the market grows, and therefore it is harder to use existing tools. On the other hand, the dual programs (ref) are defined in a fixed dimension, and moreover the constraint set is also fixed.
Define the sample function $F = f + \Psi$, where $f(\beta,\theta)=\max_i\{ v_i(\theta) {\beta_i} \}$, and $\Psi(\beta) = -{ \sum_{i=1}^n } b_i \log \beta_i$; the function $f$ is the source of non-smoothness, while $\Psi$ provides local strong convexity. Then the sample dual objective in (ref) can be expressed as $H_t(\beta) = \frac1t {\sum_{\tau=1}^{t}} F(\beta,{ \theta^\tau })$ and the population dual objective (ref) can be compactly written as $H = {\mathbb E}[F(\beta,\theta)] = {\bar f} + \Psi$ where ${\bar f}(\beta) = {\mathbb E}[f(\beta,\theta)]$ is the expectation of $f$. We call $\beta_i v_i(\theta)$ the bid of buyer $i$ for item $\theta$. The rest of the paper is devoted to studying concentration of the convex programs in the sense that as $t$ grows
The local strong convexity of the dual objective motivates us to do the analysis work in the neighborhood of the optimal solution ${\beta^*}$. In particular, the function $x \mapsto -\log x$ is not strongly convex on the positive reals, but it is on any compact subset. By working on a compact subset, we can exploit strong convexity of the dual objective and obtain better theoretical results. Recall that ${\ubar\beta_i} \leq {\beta^*_i} \leq \bar \beta$ where ${\ubar\beta_i} = b_i/ \int v_i \mathop{}\!\mathrm{d} S$ and $\bar \beta = { \sum_{i=1}^n } b_i /\min_i \int v_i \mathop{}\!\mathrm{d} S$. Define the compact set $ C \vcentcolon= \prod_{i=1}^n \big[{\ubar\beta_i}/2, 2\bar \beta\big] \subset {\mathbb R}^n, $ which must be a neighborhood of ${\beta^*}$. Moreover, for large-enough $t$ we further have $\beta^\gamma \in C$ with high probability.
We will also be interested in concentration of approximate market equilibria. For any utility vector $u$ achieved by a feasible allocation, we define $\beta_u = [\frac{b_1}{u_1},\dots, \frac{b_n}{u_n}]$. We say that a utility vector $u$ is an $\epsilon$-approximate equilibrium utility vector if $H_t(\beta_u) \leq \inf_\beta H_t(\beta)+\epsilon$. It can be shown that for any feasible utilities $u$, we have $H_t(\beta_u)\geq H_t(\beta^\gamma)$, and $u$ is the equilibrium utility vector if and only if $H_t(\beta_u) = H_t(\beta^\gamma)$. To that end, let
be the sets of $\epsilon$-approximate solutions to (ref), respectively.
Blanket assumptions. Recall the total supply in the long-run market is one: $\int s \mathop{}\!\mathrm{d} \mu= 1$. Assume the total item set produce one unit of utility in total, i.e., $\int v_i s \mathop{}\!\mathrm{d} \mu =1$. Suppose budges of all buyers sum to one, i.e., ${ \sum_{i=1}^n } b_i = 1$. Let $\underaccent{\bar}{b}\vcentcolon=\min_i b_i$. Note the previous budget normalization implies $\underaccent{\bar}{b} \leq 1/n$. Finally, for easy of exposition, we assume the values are bounded $\sup_\Theta v_i (\theta) < { \bar v }$, for all $i$. By the normalization of values and budgets, we know ${\ubar\beta_i} = b_i /2 $ and $\bar \beta = 2$.
In this section we introduce several natural empirical estimators based on the observed market equilibrium, and show that they satisfy both consistency and high-probability bounds.
\paragraph{Consistency}
Thanks to the convexity of the dual objectives $H$ and $H_t$, we can provide a set of consistency results based on the theory of epi-convergence rockafellar2009variational.
We briefly comment on (ref). The set limit result can be interpreted from a set distance point of view. We define the inclusion distance from a set $A$ to a set $B$ by $d_\subset(A,B ) \vcentcolon= \inf _\epsilon\{\epsilon \geq 0: A \subset\{y: \operatorname{dist}(y, B) \leq \epsilon\}\}$ where $\operatorname{dist}(y, B) \vcentcolon= \inf\{\|y - b\| : b\in B \}$. Intuitively, $d_\subset(A,B )$ measures how much one should enlarge $B$ such that it covers $A$. Then for any sequence $\epsilon_n \downarrow 0$, by the second claim in (ref), we know $d_\subset({\mathcal{B}}^{ \gamma }(\epsilon_t), \{{\beta^*}\}) \to 0$. This shows that the set of approximate solutions of $H_t$ with increasing accuracy centers around ${\beta^*}$ as market size grows.
\paragraph{High Probability Bounds} Next, we refine the consistency results and provide finite sample guarantees. We start by focusing on Nash social welfare and the set of approximate market equilibria. The convergence of utilities and pacing multiplier will then be derived from the latter result.
(ref) establishes a convergence rate $|{\small \mathrm{{NSW}}}^{ \gamma } - {\small \mathrm{{NSW}}}^* | = \tilde O _p({ \bar v } \sqrt n t^{-1/2})$. The proof proceeds by first establishing a pointwise concentration inequality and then applies a discretization argument.
By construction of $C$ we know ${\beta^*} \in C$ holds, and so $C\cap { \mathcal{B}^*}(\epsilon)$ is not empty. By (ref) we know that for $t$ sufficiently large, $\beta^\gamma \in C$ with high probability, in which case the set $C\cap { \mathcal{B}^\gamma}(\delta)$ is not empty.
By simply taking $\delta = 0$ in (ref) we obtain the above corollary. More importantly, it establishes the fast statistical rate $ H(\beta^\gamma ) - H({\beta^*}) = \tilde{O}_p (t^{-1} ) $ for $t$ sufficiently large, where we use $\tilde{O}_p$ to ignore logarithmic factors. In words, when measured in the population dual objective where we take expectation w.r.t.\ the item supply, $\beta^\gamma$ converges to ${\beta^*}$ with the fast rate $1/t$. This is in contrast to the usual $1/\sqrt{t}$ rate obtained in (ref), where $\beta^\gamma$ is measured in the sample dual objective. There the $1/\sqrt{t}$ rate is the best obtainable.
By the strong-convexity of dual objective, the containment result can be translated to high-probability convergence of the pacing multipliers and the utility vector.
We compare the above corollary with Theorem 9 from gao2022infinite which establishes the convergence rate of the stochastic approximation estimator based on dual averaging algorithm xiao2010dual. In particular, they show that the average of the iterates, denoted $\beta_{\mathrm{DA}}$, enjoys a convergence rate of $\| \beta_{\mathrm{DA}} - {\beta^*}\|_2^2 = \tilde O_p \big(\frac{{ \bar v }^{2} }{ \underaccent{\bar}{b}^{2}} \frac{1}{t}\big)$, where $t$ is the number of sampled items. The rate achieved in (ref) is $\|\beta^\gamma - {\beta^*}\|_2 ^{2} = \tilde O_p \big(\frac{n(n^2 + { \bar v } ^{2})}{\underaccent{\bar}{b}^{2}} \frac{1}{t} \big)$ for $t$ sufficiently large. Noting $n \leq \underaccent{\bar}{b}^{-1}$ due to the normalization ${ \sum_{i=1}^n } b_i = 1$, we see that our rate is worse off by a factor of $n(1+\frac{n^{2}}{{ \bar v } ^{2}})$. And yet our estimates is produced by the strategic behavior of the agents without any extra computation at all. Moreover, in the computation of the dual averaging estimator the knowledge of values $v_i(\theta)$ is required, while again $\beta^\gamma$ can be just observed naturally.
In this section we 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 a premise, and then provide three sufficient conditions under which $H$ is $C^2$ at the optimum.
To present asymptotics for $\beta$ and $u$ we need a bit more notation. Let $\Theta_i (\beta) \vcentcolon= \{\theta \in \Theta: v_i(\theta){\beta_i} \geq v_k(\theta)\beta_k, \forall k\neq i \}$, i.e., the potential winning set of buyer $i$ when the pacing multiplier are $\beta$. Let $\Theta_i^* \vcentcolon= \Theta_i({\beta^*})$. We will see later that if the dual objective is sufficiently smooth at ${\beta^*}$, then the winning sets, $\Theta_i^*$, $i\in [n]$, will be disjoint (up to a measure-zero set). Now we define a map $\mu^*: \Theta \to {\mathbb R^n_+}$, which represents the utility all buyers obtain from the item $\theta$ at equilibrium. Formally,
Since $x^*$ is pure, only one entry of $\mu^*(\theta)$ is nonzero.
In (ref) we require a strong regularity condition: twice differentiability of $H$, which seems hard to interpret at first sight. In the next section we derive a set of simpler sufficient conditions for the twice differentiability of the dual objective.
Intuitively, the expectation operator will smooth out the kinks in the piecewise linear function $f(\cdot, \theta)$; even if $f$ is non-smooth, it is reasonable to hope the expectation counterpart ${\bar f}$ is smooth, facilitating statistical analysis. First we introduce notation for characterizing smoothness of ${\bar f}$.
Define the gap between the highest and the second-highest bid under pacing multiplier $\beta$ by
here $ v(\theta) {\cdot} \beta$ is the elementwise product of $v(\theta)$ and $\beta$, and $(v(\theta) {\cdot} \beta)_{(1)}$ and $(v(\theta) {\cdot} \beta)_{(2)}$ are the greatest and second-greatest entries of $ v(\theta) {\cdot} \beta$, respectively. When there is a tie for an item $\theta$, we have $\textsf{bidgap}(\beta,\theta) = 0$. When there is no tie for an item $\theta$, the gap $\textsf{bidgap}(\beta,\theta)$ is strictly positive. Let $G(\beta,\theta) \in \partial f(\beta,\theta)$ be an element in the subgradient set. The gap function characterizes smoothness of $f$: $f(\cdot, \theta)$ is differentiable at $ \beta$ $\Leftrightarrow$ $\textsf{bidgap}(\beta,\theta)$ is strictly positive, in which case $G(\beta,\theta) = \nabla_\beta f(\beta,\theta) = e_{i(\beta,\theta)}v_{i{(\beta,\theta)}}$ with $e_i$ being the $i$-th unit vector and $i(\beta,\theta) = \operatorname*{arg\,max}_i {\beta_i}{ v_i(\theta) }$. When $f(\cdot, \theta)$ is differentiable at $\beta$ a.s., the potential winning sets $\{\Theta_i(\beta) \}_i$ are disjoint (up to a measure-zero set).
Given the neat characterization of differentiability of dual objective via the gap function $\textsf{bidgap}(\beta,\theta)$, 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 differentiability.
We briefly comment on the three candidate sufficient conditions; for a rigorous statement we refer readers to (ref). Based on the differentiability characterization, it is natural to search for a stronger form of (ref) and hope that such a refinement could lead to second-order differentiability. Condition (i) gives two such refinements. Condition (ii) is motivated by the idea that expectation operator tends to produce smooth functions. Given that the dual objective $H$ is the expectation of the non-smooth function $f$ (plus a smooth term $\Psi$), we expect under certain conditions on the expectation operator $H$ is twice differentiable. The exact smoothness requirement is presented in the appendix, which we show is easy to verify for several common distributions. Finally, Condition (iii) considers the linear-valuations setting of gao2022infinite, where the authors provide tractable convex programs for computing the infinite-dimensional equilibrium. Here we give another interesting properties of this setup by showing that the dual objective is $C^2$. We also discuss how this can be extended to piecewise linear value functions in the appendix.
In this section we discuss constructing confidence intervals for Nash social welfare, the pacing multipliers, and the utilities. We remark that the observed NSW, ${\small \mathrm{{NSW}}}^{ \gamma }$, is a negatively-biased estimate of the NSW, ${\small \mathrm{{NSW}}}^*$, of the long-run ME, i.e., $ {\mathbb E}[{\small \mathrm{{NSW}}}^{ \gamma }] - {\small \mathrm{{NSW}}}^* \leq 0$.\footnote{Note $ {\mathbb E}[{\small \mathrm{{NSW}}}^{ \gamma }] - {\small \mathrm{{NSW}}}^* = {\mathbb E}[\min_\beta H_t(\beta)] - H({\beta^*}) \leq \min_\beta {\mathbb E}[H_t(\beta)] - H({\beta^*}) = 0.$} Moreover, it can be shown that, when the items are i.i.d.\ ${\mathbb E}[\min H_t] \leq {\mathbb E}[\min H_{t+1}]$ using Proposition 16 from shapiro2003monte. 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 variance. We let $ \hat\sigma_{{ \scriptscriptstyle \mathrm{{N}}}}^{2} \vcentcolon= \frac{1}{t} {\sum_{\tau=1}^{t}}\big( F(\beta^\gamma, { \theta^\tau }) - H_t(\beta^{ \gamma })\big)^{2} =\big( \frac{1}{t}{\sum_{\tau=1}^{t}} (p^{{ \gamma },\tau})^{2} \big)- 1. $ where $p^{{ \gamma },\tau}$ is the price of item $\theta^\tau$ in the observed market. We emphasize that in the computation of the variance estimator $ \hat\sigma_{{ \scriptscriptstyle \mathrm{{N}}}}^{2}$ one does not need knowledge of values $\{{ v_i(\theta^\tau) }\}_{i,\tau}$. All that is needed is the equilibrium prices ${ p ^ {\gamma} } = (p^{{ \gamma },1},\dots, p^{{ \gamma },t})$ of the items. Given the variance estimator, we construct the confidence interval $ [ {\small \mathrm{{NSW}}}^{ \gamma } \pm z_{\alpha/2} \frac{\hat \sigma_{{ \scriptscriptstyle \mathrm{{N}}}}}{\sqrt t}]$, where $z_\alpha$ is the $\alpha$-th quantile of a standard normal. The next theorem establishes validity of the variance estimator.
Estimation of the variance matrices for $\beta$ and $u$ is 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 a biased estimator for the Hessian of the population function in general.
We provide a brief discussion of variance estimation under the following two simplified scenarios in (ref). First, in the case where ${\mathbb E} [\textsf{bidgap}(\beta, \theta)^{-1} ]< \infty$ holds in a neighborhood of ${\beta^*}$, which we recall is a stronger form (ref), we prove that a plug-in type variance estimator is valid. Second, if we have knowledge of $\{{ v_i(\theta^\tau) }\}_{i,\tau}$, then we give a numerical difference estimator for the Hessian which is consistent.
As we mentioned previously, in a linear Fisher market all buyer budgets are extracted, i.e., ${\sum_{\tau=1}^{t}} { p ^ {\gamma, \tau} }$ equals ${ \sum_{i=1}^n } b_i$ in the observed market (and similarly for the underlying market), and there is thus nothing to infer about revenue if we know the budgets of each buyer. A quasilinear (QL) utility is one such that the cost of purchasing goods is deducted from the utility, i.e., $u_i(x) = {\langle} x - p, v_i {\rangle}$. This may give buyers an incentive to leave some budget unspent. In the finite-dimensional case, chen2007note and cole2017convex show that there is an variant of EG program that captures the market equilibrium with QL utility. Furthermore, conitzer2022pacing showed that budget management in ad auctions with first-price auctions can be computed by Fisher markets with QL utilities. A QL variant of infinite-dimensional markets and an EG program are given by gao2022infinite.
Quaislinear market equilibria (QME) are defined analogously to the linear variant via market clearance conditions and buyer optimality; we present the formal finite and infinite-dimensional definitions in (ref). The demand sets are $\operatorname*{arg\,max} \{ \langle v_i - p, x_i \rangle : x_i \in L^\infty_+,\, \langle p, x_i\rangle \leq b_i \}$ in the long-run QME and $ \operatorname*{arg\,max} \{ \langle {{v}}_i({ \gamma }) - p , {x}_i \rangle : {x}_i \geq 0,\, \langle p, {x}_i\rangle \leq b_i \}$ in the observed QME. QME has several distinctions from the linear ME. First, in QME we cannot normalize both valuations and budgets, since buyers' budgets have value outside the current market. Second, budgets are not fully extracted in QME, which motivates the need for statistical analysis. Third, the pacing multipliers are restricted to $\beta \leq 1$, and may lie on the resulting boundary.
Define the revenues from the observed and the long-run market as follows: $ {\small \mathrm{{REV}}}^{ \gamma } \vcentcolon= \frac1t {\sum_{\tau=1}^{t}} { p ^ {\gamma, \tau} } , {\small \mathrm{{REV}}}^* \vcentcolon= \int_\Theta {p^*} \mathop{}\!\mathrm{d} S(\theta). $ Assume ${ \sum_{i=1}^n } b_i = 1$ and unit supply $\int s\mathop{}\!\mathrm{d} \mu = 1$. Let ${ \nu_i} \vcentcolon= \int v_i\mathop{}\!\mathrm{d} S $ be the average value of buyer $i$. Let ${ \bar\nu} = \max_i { \nu_i}$. Assume we observe the market ${ \mathcal{QME}^{ \gamma }}(b,v,\tfrac1t 1_t) = ({ x^{\gamma} }, u^\gamma ,{ p ^ {\gamma} })$. Then we show that consistency and high-probability bounds hold for the revenue estimator.
We leave CLT results for revenue estimates in quasilinear markets as an open problem. The main challenge compared to the linear case is that the optimal pacing multipliers can lie on the boundary of the constraint set. More precisely, if the equilibrium pacing multiplier of a buyer is in the interior, then his budget is fully extracted. On the other hand, if it is on the boundary, the buyer retains a portion of his budget at equilibrium. When the optimum of the expectation function lies on the boundary of the constraint set, the asymptotic variance of the sample average optimum takes on a complicated expression shapiro1989asymptotic, which makes variance estimation difficult.