Liao and Kroer

Statistical Inference in Market Equilibrium

Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions

Luofeng Liao
Department of Industrial Engineering and Operations Research, Columbia University,
Christian Kroer
Department of Industrial Engineering and Operations Research, Columbia University,

We initiate the study of statistical inference and A/B testing for two market equilibrium models: linear Fisher market (LFM) equilibrium and first-price pacing equilibrium (FPPE). LFM arises from fair resource allocation systems such as allocation of food to food banks and notification opportunities to different types of notifications. For LFM, we assume that the data observed is captured by the classical finite-dimensional Fisher market equilibrium, and its steady-state behavior is modeled by a continuous limit Fisher market. The second type of equilibrium we study, FPPE, arises from internet advertising where advertisers are constrained by budgets and advertising opportunities are sold via first-price auctions.  For platforms that use pacing-based methods to smooth out the spending of advertisers, FPPE provides a hindsight-optimal configuration of the pacing method. We propose a statistical framework for the FPPE model, in which a continuous limit FPPE models the steady-state behavior of the auction platform, and a finite FPPE provides the data to estimate primitives of the limit FPPE. Both LFM and FPPE have an Eisenberg-Gale convex program characterization, the pillar upon which we derive our statistical theory. We start by deriving basic convergence results for the finite market to the limit market. We then derive asymptotic distributions, and construct confidence intervals. Furthermore, we establish the asymptotic local minimax optimality of estimation based on finite markets. We then show that the theory can be used for conducting statistically valid A/B testing on auction platforms. Synthetic and semi-synthetic experiments verify the validity and practicality of our theory.

first-price auctions, Fisher market equilibrium, statistical inference, A/B testing

§.§ Related Works

A/B testing in two-sided markets.
Empirical studies by
<cit.> demonstrate bias in experiments due to marketplace interference.
<cit.> study the bias and variance of treatment effects under two randomization schemes for auction experiments.
<cit.> study the estimation of causal quantities in time series experiments.
Some recent state-of-the-art designs are the multiple randomization designs <cit.> and the switch-back designs
The surveys by
<cit.> contain detailed accounts of A/B testing in internet markets.

See <cit.> for an extensive survey on statistical challenges in A/B testing.
Compared to these papers, our paper is the first to focus on A/B testing with equilibrium effects.

Pacing equilibrium.
Pacing and throttling are two prevalent budget-management methods on ad auction platforms.
Here we focus on pacing methods since that is our setting.
In the first-price setting,
<cit.> study first price auctions with budget constraints in a perturbed model, whose limit prices converge to those of an FPPE.
Building on the work of <cit.>, <cit.> introduce the FPPE model and discover several properties of FPPE such as shill-proofness and monotonicity in buyers, budgets and goods.
There it is also established that FPPE is closely related to the quasilinear Fisher market equilibrium <cit.>.
<cit.> propose an infinite-dimensional variant of the quasilinear Fisher market, which lays the probability foundation of the current paper.
<cit.> study online computation of the infinite-dimensional Fisher market equilibrium.
In the second-price setting,
<cit.> investigate budget-management in second-price auctions through a fluid mean-field approximation;
<cit.> study adaptive pacing strategy from buyers' perspective in a stochastic continuous setting;
<cit.> study several budget smoothing methods including multiplicative pacing in a stochastic context;
<cit.> study second price pacing equilibrium, and shows that the equilibria exist under fractional allocations.

$M$-estimation when the parameter is on the boundary
There is a long literature on the statistical properties of
$M$-estimators when the parameter is on the boundary <cit.>.
Some recent works on the statistical inference theory for constrained $M$-estimation include <cit.>.
Our work leverages <cit.>, which develops a general set of conditions
for central limit theorems (CLT) of constrained $M$-estimators when the objective function is nonsmooth.
Working under the specific model of FPPE, we build on and go beyond these
contributions by deriving sufficient condition for asymptotic normality in FPPE, establishing local asymptotic minimax theory and developing valid inferential procedures.

Statistical learning and inference with equilibrium effects
take a mean-field game modeling approach and perform policy learning with a gradient descent method.

Statistical learning and inference
has been investigated for other equilibrium models, such as
general exchange economy <cit.> and
matching markets <cit.>.
Our work is also related to the rich literature of inference under interference <cit.>.
In the FPPE model, the interference among buyers is caused by the supply and budget constraint and the
revenue-maximizing incentive of the platform.
In the economic literature, researchers have studied how to estimate auction market primitives from bid data; see <cit.> for a survey.

Closely related to our work is the one by <cit.>, and we discuss it here.
They consider a potential outcome framework where the outcome of an agent depends on the treatments of all agents, but only through the equilibrium price. The equilibrium price is attained by a market clearance condition.
Although both their work and our work consider a mean-field market equilibrium, there are differences. First,
<cit.> send the number of agents to infinity while we consider the asymptotics where the number of items grows.
Second, <cit.> present a rather general
market equilibrium framework that requires abstract regularity conditions, while we focus on equilibria arising from resource allocation systems and auction pacing systems, and consequently we are able to present low-level conditions that facilitate statistical inference.

This paper builds upon two preliminary papers <cit.>. This paper gives a more unified presentation, and provides some additional results on the statistical theory of Fisher markets and FPPE.
Perhaps most importantly, this paper conducts two semisynthetic experiments based on an ad auction dataset <cit.> and an Instagram notification dataset <cit.>, demonstrating the practicality of the proposed theory.
This paper also provides strong consistency and convergence rate for FPPE, minimax optimality results for LFM, and a novel closed-form expression for the Hessian matrix of the population EG objective (<ref>) using results from differential geometry <cit.>.
Building on the preliminary versions of the present paper, <cit.> extends the FPPE statistical theory to the cases where degenerate buyers are present and develops bootstrap inference methods.

§.§ Notations

Let $e_i$ be the $i$-th basis vector in $\Rn$.
Furthermore, we let $A\pinv $ be the Moore-Penrose pseudo inverse of a matrix $A$.

Let $\diff \t$ denote the Lebesgue measure in $\R^D$.
For a measurable space $(\Theta, \diff \theta)$, we let $L^p$ (and $L^p_+$, resp.) denote the set of (nonnegative, resp.) $L^p$ functions on $\Theta$ w.r.t the integrating measure $\diff \theta $ for any $p\in [1, \infty]$ (including $p=\infty$).
We treat all functions that agree on all but a measure-zero set as the same.
For a sequence of random variables $\{X_n\}$, we say $X_n = O_p(1)$ if for any $\epsilon > 0$ there exists a finite $M_\epsilon$ and a finite $N_\epsilon$ such that $\P(|X_n| > M_\epsilon) < \epsilon$ for all $n\geq N_\epsilon$. We say $X_n = o_p(1)$ if $X_n$ converges to zero in probability.
We say $X_n = O_p(a_n)$ (resp. $o_p(a_n)$) if $X_n/a_n = O_p(1)$ (resp. $o_p(1)$).
The subscript $i$ is for indexing buyers and superscript $\tau$ is for items.

§ LINEAR FISHER MARKET AND FIRST-PRICE PACING EQUILIBRIUM

In this section we introduce the Fisher market equilibrium and the first-price pacing equilibrium, and review their properties. We start by presenting components that are common to both models, and then introduce each equilibrium concept.
In both LFM and FPPE, we have a set of $n$ buyers and a set of items, and the goal is to find market-clearing prices for the items.
The items are represented by a set $\Theta \in \R^D$, a compact set with $\int \indi (\Theta) \diff \t > 0$.
Clearly the measure sapce $(\Theta,\dt)$ is atomless.

Both LFM and FPPE require the following elements; see <ref> for an illustration.

Budgets, values and supply.

* The budget $b_i$ of buyer $i$. Let $b = (b_1,\dots, b_n)$.

* The valuation for buyer $i$ is a function $v_i \in L^1_+$. Buyer $i$ has valuation $v_i(\theta)$ (per unit supply) of item $\theta\in \Theta$. Let $v: \Theta \to \Rn$, $v(\theta) = [v_1(\theta),\dots, v_n(\theta)]$. We assume $\vbar = \max _i \sup_\theta  v_i(\theta)< \infty $.
Also let $\nu_i = \int v_i s\diff \t$ be the monopolistic utility of buyer $i$, and $\nubar = \max_i \nu_i$.

* The supplies of items are given by a function  $ s \in L^\infty_+$, i.e., item $\theta\in \Theta$ has $s(\theta)$ units of supply.
Without loss of generality, we assume a unit total supply $\int_\Theta s \diff \theta = 1$, which makes $s$ a probability measure.
Let $\P$ denote the probability measure induced by $s$, i.e.,
$\P (A) = \int_A s\dt$  for a measurable set $A$.
Given $g:\Theta \to \R$, we let $\E[g] = \int g(\theta)s(\theta)\diff \theta$ and $\var[g] = \E[g\sq] - (\E[g])\sq$.
Given  $t$ i.i.d. draws $\{ \theta^1,\dots, \theta^t\}$
from $s$, let $P_t g(\cd) = \frac1t \sumtau g(\thetau)$.
Let $\vitau = v_i(\thetau)$.

Equilibria in both LFM and FPPE are characterized by a particular type of convex program known as an Eisenberg-Gale (EG) convex program. For statistical inference purposes, we will focus on the duals of these EG programs, which is a convex optimization problem over the space of pacing multipliers $\beta \in \Rnp$ (these pacing multipliers turn out to represent the price-per-utility of buyers in equilibrium).
In both cases, the dual EG objective separates into per-item convex terms

\begin{align}
\label{eq:def:F}
F (\t, \b) = f(\t,\b)-  \sumiton b_i \log \beta_i \;,\;\; f(\t,\b)=\max_{i\in[n]} \beta_i v_i(\theta)  \;.
\end{align}

and the population and sample EG objectives are

\begin{align}
\label{eq:def_pop_eg}
H(\beta) = \E[F(\t,\b)] \; , \;\; H_t(\beta) = P_t F(\cd, \beta) \; .
\end{align}

The reason we focus on the duals is that they can be cast as sample average approximations of the limit convex programs. This interpretation is not possible for the original primal EG programs.

§.§ Linear Fisher Markets (LFM)

The LFM model has two primary uses. Its original intent is as a model of competition, and how prices are determined in a competitive market.
An additional, and practically important, use of LFM is as a tool for fair and efficient resource allocation (with the items being the resources).
If every individual in a resource allocation problem is given one unit of faux currency, then the resulting LFM equilibrium allocation is known to be both Pareto efficient and satisfy the fairness desiderata of envy-freeness and proportionality <cit.>. This fair allocation approach is known as competitive equilibrium from equal incomes (CEEI) <cit.>.

We now describe the competitive equilibrium concept.
Imagine there is a central policymaker that sets
prices $p(\cdot)$ for the items $\Theta$. Upon observing the prices, buyer $i$
maximizes their utility subject to their budget.
Their demand set is the set of bundles that are optimal under the prices:

\[ D_i (p) := \argmax_{x_i \in L^\infty_+(\Theta)} \bigg\{ \int v_i x_i s \diff \t :  \int p x_i s\diff \t \leq b_i\bigg\} \; .\]

Of course, due to the supply constraints, if prices are too low, there will be a supply shortage. On the other hand, if prices are too high, a surplus occurs. A competitive equilibrium is a set of prices and bundles such that all items are sold exactly at their supply (or have price zero).
We call such an equilibrium the limit LFM equilibrium for the supply function $s$ <cit.>.

The limit equilibrium, denoted $\LFM (b,v,s, \Theta)$, is an allocation-price tuple $(x,p(\cd))$ such that the following holds.

* (Supply feasibility and market clearance) $\sum_i x_i \leq 1$ and $\int p (1 - \sum_i x_i) s \diff \t= 0$.

* (Buyer optimality) $x_i \in D_i (p)$ all $i$.

<cit.> show that an equilibrium of a limit LFM must exist, and that when the measure space $(\Theta,\dt)$ is atomless, a pure equilibrium allocation [An allocation $x$ is pure if $x_i(\t) \in \{0,1\}$.] must exist.
Given an equilibrium $(\xst, \pst)$, let

\begin{align*}
\usti = \int \vi s \xsti \diff \t \;, \quad \betasti = b_i / \usti  \;,\quad \NSWst = \sumiton b_i \log(\usti )
\end{align*}

be buyer $i$' utility, her inverse bang-per-buck, and the (log) Nash social welfare of the whole market.
The inverse bang-per-buck $\beta_i^*$ can also be seen as the price-per-utility of buyer $i$ in equilibrium.
In a general LFM, the equilibrium allocation may not be unique, but the equilibrium quantities $\pst,\betast,\ust$ are unique.
In order to facilitate statistical inference, we will impose certain
differentiability condition, which turn out to imply uniqueness and purity of the equilibrium allocation $\xst$.

Next we introduce the finite LFM, which models the data we observe in a market.
The finite LFM equilibrium is nothing but a limit LFM equilibrium where the item set $\Theta$ is the finite set of observed items $\gamma$.
Let $\gam = \{ \theta^1,\dots, \theta^t\}$ be $t$ i.i.d. samples from the supply distribution $s$, each with supply $\sigma \in \Rp$.

The finite observed LFM, denoted $\oLFM(b,v,\sigma, \gamma)$, is a allocation-price tuple $({x}, p) \in \R^{t\times n}_+ \times \Rnp $ such that the following hold:

* (Supply feasibility and market clearance) $\sumi\xtaui \leq 1 $ and  $\sum_\tau \ptau (1- \sumi \xitau)  = 0$.

* (Buyer optimality) $x_i \in D_i (p) = \argmax_{x_i} \{ \sum_\tau \xitau \vitau : \sigma \sum_\tau \xitau \ptau \leq b_i , \xitau \geq 0\}$, the demand set given the prices.

Let  $(\xgam, \pgam) \in \oLFM(b,v,\sigma = 1/t, \gamma)$ [We use $\in$ since the equilibrium allocation may not be unique.],
$\xgam = (\xitau )_{i,\tau}$ and price $\pgam = [p^1,\dots, p^t]$. Buyer $i$'s utility is $\ugam_i=\sigma \sumtau \vitau \xtaui = \frac1t \sumtau \vitau \xtaui  $, and the inverse bang-per-buck is $\betagami = b_i / \ugami$. The (log) Nash social welfare is $\NSWgam = \sumi b_i \log (\ugami)$.

We now introduce several properties of LFM:  natural bounds on $\b$, fairness and efficiency as a resource allocation mechanism,
and the convex program characterization.

There exists natural bounds on $$ in limit LFM. Recall $ν_i =∫v_i s$ is the expected value of buyer~$i$.
By \citet{gao2022infinite},
we know that
$b_i / ν_i ≤≤(∑_i' b_i') / (min_i' ν_i')$.
We define
\begin{align}
\label{eq:def_C_LFM}
C_\LFM = \prod_{i=1}^{n}
\bigg[ \frac{b_i}{2\nu_i},  \frac{ 2 \sum_{i'} b_{i'}}{\min_{i'} \nu_{i'}}\bigg] \subset \Rnp
\end{align}
to be the region whose interior $$ must lie in.

A major use case for LFM is fair and efficient allocation of resources.
Similar to the classical finite LFM, the infinite LFM enjoys fairness and efficiency properties~\citep{gao2022infinite}. Let $$ be an equilibrium allocation.
First, this allocation is \textit{Pareto optimal}, meaning there does not exist an $x̃ ∈(L_+^∞) ^ n$, $x̃_i ≤1$, such that $∫v_i x̃ _i s≥∫v_i s$ for all $i$ and one of the inequalities is strict.
The allocation $$ is \textit{envy-free} in a budget-weighted sense, meaning $∫v_i s/ b_i ≥∫v_j _j  s/ b_j$ for all $i≠j$.
Finally, it is \textit{proportional}: $∫v_i s≥∫v_i s ·(b_i / ∑_i'b_i') $, that is, each buyer gets at least the utility of its proportional share allocation.

LFM enjoys certain scale-invariance properties.
First, buyers cannot change the equilibrium by scaling their value functions.
Suppose $α_1,…, α_n$
are positive scalars, and that
$(x,p)$ are the equilibrium allocations and prices in $(b,v,s,Θ)$.
Then $(x,p)$ will also be the equilibrium quantities in $(b,(α_1 v_1,
…,α_n v_n), s, Θ)$.
% This is also obvious once we view LFM as an allocation mechanism; an individual should not be able change the allocation by unilaterally inflating their values.
% CK: I commented out the above; it's a bit tricky because an individual CAN change the allocation if they misreport, just not via uniform scaling
This is easily seen by the fact that valuation scaling does not change the demand function.
Second, if all buyers' budgets are scaled by the same factor, or the supply is scaled by the same factor, the equilibrium does not change. That is, if $α_1,α_2$ are two positive scalars, and $(x,p) = (b,v,s,Θ)$, then $(x, (α_1  / α_2) p) = (α_1 b, v, α_ 2 s, Θ)$.
These scale-invariances hold for finite LFM as well \footnote{
That is,
$(\xgam,\pgam) \in \oLFM (b,v,\sigma, \gam)$ implies
$  (\xgam,\pgam)\in \oLFM ( b, (\alpha_i v_i), \sigma, \gam)$,
$(x, (\alpha_1/\alpha_2) p) \in \oLFM(\alpha_1 b, v, \alpha_2 \sigma, \gam)$
Based on the invariance, we impose the normalization that
$b_i = 1$ and that all buyers' expected values are 1, i.e.,
$∫v_i () s()= 1$.
Then in the limit LMF, the budge-supply ratio is
$b_i / ∫s = 1$.
With the normalization, we have $C_= ∏_i=1^n [b_i/2, 2]$.
In order for the budget-to-supply ratio to match in the sampled finite LFM and the limit LFM, we
use supplies of $1/t$ for each item in the finite LFM.
Thus we study finite LFM of the form $(b,v, 1/t, γ)$.

It is well-known~\citep{eisenberg1959consensus,cole2017convex,gao2022infinite}
that the equilibrium inverse bang-per-buck in a limit (resp.\ finite) LFM uniquely solves
the population (resp.\ sample) dual EG program
\begin{align}
\label{eq:pop_deg_lfm}
\betast = \argmin_{\beta \in \Rnp}
H(\beta) \; , \;
\betagam = \argmin_{\b\in \Rnp} H_t(\b) \; .
\end{align}

\subsection{First-Price Pacing Equilibrium (FPPE)}
\label{sec:fppe_review}
The FPPE setting~\citep{conitzer2022pacing} models an economy that typically occurs on internet advertising platforms: the buyers (advertisers in the internet advertising setting) are subject to budget constraints, and must participate in a set of first-price auctions, each of which sells a single item.
Each buyer is assigned a \emph{pacing multiplier} $β_i ∈[0,1]$ by the platform to scale down their bids in the auctions, and submits bids of the form $β_i v_i(θ)$ for each item $θ$.  From the platform's perspective, the goal of choosing $β_i$ is to ensure there is \emph{no unnecessary pacing}, i.e., buyers spend their budget exactly, or they spend less than their budget but they do not scale down their bids.
In the FPPE model, all auctions occur simultaneously, and thus the buyers choose a single $β_i$ that determines their bid in all auctions.
The utility of a buyer in FPPE is quasilinear: it is the sum of their value received from items plus their leftover budget (this is equivalent for decision-making purposes to the utility being the value received from items minus the payments).

\begin{definition}[Limit FPPE, \citet{gao2022infinite}]
\label{def:limit_fppe}
A limit FPPE, denoted $\FPPE(b,v,s, \Theta)$, is the unique tuple $(\beta, p(\cd)) \in [0,1]^n \times L^1_+ (\Theta)$ such that there exist $x_i : \Theta \to [0,1]$, $i\in[n]$ satisfying
\begin{enumerate}[series = tobecont,itemjoin = \quad]
\item (First-price)
Prices are determined by first-price auctions:
for all items $\theta \in \Theta$, $p(\theta) = \max_i \betai v_i(\theta)$.
Only the highest bidders win:
for all $i$ and~$\theta$, $x_i(\theta) > 0$ implies $\betai \vithe =\max_k \beta_k v_k (\theta)$
\label{it:def:first_price}
\item (Feasibility, market clearing)
Let $\pay_i = \int x_i(\theta) p(\theta) s(\theta)\diff \theta $ be the expenditure of buyer $i$.
Buyers satisfy budgets:
for all~$i$, $\pay_i  \leq b_i$.
There is no overselling:
for all $\theta$, $\sumiton x_i (\theta) \leq 1$.
\label{it:def:supply_and_budget}
All items are fully allocated:
for all~$\theta$, $p(\theta) > 0$ implies $ \sumiton x_i(\theta) = 1$.
\item (No unnecessary pacing) For all $i$, $\pay_i < b_i$ implies $\betai = 1$.
\label{it:def:rev_max}
\end{enumerate}
\end{definition}

FPPE is a hindsight and static solution concept for internet ad auctions.
Suppose the platform knows all the items that are going to show up on a platform.
FPPE describes how the platform could configure the $$'s in a way that ensures that all buyers satisfy their budgets, while maintaining their expressed valuation ratios between items.
In practice, the $$'s are learned by an online algorithm that is run by the platform~\citep{balseiro2019learning,conitzer2022pacing}.
FPPE has many nice properties, such as the fact that it is a competitive equilibrium, it is revenue-maximizing, revenue-monotone, shill-proof, has a unique set of prices, and so on~\citep{conitzer2022pacing}.
We refer readers to \citet{conitzer2022pacing,kroer2022market} for more context about the use of FPPE in internet ad auctions.

\citet{gao2022infinite} show that
a limit FPPE always exists and is unique, and when the item space is atomless, a pure allocation exists.
Let $$ and $$ be the unique FPPE equilibrium multipliers and prices.
Revenue in the limit FPPE is
\begin{align}
\REVst \defeq \int \pst(\theta) s(\theta)\diff \theta \; .
\end{align}
It is also easy to see that $= _i$.
Although the equilibrium allocation $$ may not be unique in general, for statistical inference we will impose certain differentiability assumption which imply uniqueness of $$.
When $$ is unique, we let $b_i - _i$ be the leftover budget.

In an FPPE, based on the pacing multiplier and the budget expenditure,
we can categorize buyers in terms of how they satisfy the no unnecessary pacing condition.
As we will see later, the statistical behavior of pacing multipliers varies by category.
\begin{itemize}
\item Paced buyers ($\betasti < 1$).
We use $I^c = \{i : \betasti < 1\}$ to denote them.
Due to the budget constraints, they are not able to bid their value in the auctions at equilibrium, and by the no unnecessary pacing condition in \cref{def:limit_fppe}, their budgets are fully exhausted, i.e. $\deltasti = 0$.

\item Unpaced buyers ($\betasti = 1$).
We use $I = \{i : \betasti = 1\}$ to denote them.
They can be further divided according to their budget expenditure.
\begin{itemize}
\item Buyers who have leftover budgets ($\betasti=1, 0< \deltasti \leq b_i$), denoted $I_+$.
Note this category also includes buyers who dot not win any items ($\betasti = 1, \deltasti = b_i$).

\item  Degenerate buyers ($\betasti = 1, \deltasti = 0 $), denoted $I_0$.
They are the edge-cases in the FPPE model. If these buyers were given more budgets, they would become $I_+$-type buyers at equilibrium.
For the FPPE statistical theory developed in this paper, we assume absence of such buyers (\cref{as:scs}).
In follow-up work to the conference version of the present paper, \citet{liao2024bootstrap} give some results for the case where degenerate buyers exist.
\end{itemize}
\end{itemize}

We let $= { θ^1,…, θ^t}$ be $t$ i.i.d.\ draws from $s$, each with supply $σ=1/t$. They represent the items observed in an auction market.
The definition of a finite FPPE is parallel to that of a limit FPPE, except that we change the supply function to be a discrete distribution supported on $γ$.

\begin{definition}[Finite FPPE, \citet{conitzer2022pacing}]
\label{def:finite_fppe}
The finite observed FPPE, $\oFPPE(b,v, \sigma , \gamma)$, is the unique tuple
$(\beta,p) \in [0,1]^n \times \R^t_+ $
such that there exists $x_i^\tau \in [0,1]$ satisfying:
\begin{enumerate}
\item
(First-price) For all $\tau$, $\ptau = \max_i \betai \vitau$. For all $i$ and $\tau$, $\xitau > 0$ implies $\betai \vitau =\max_k \beta_k v_k^\tau$.
\item
(Supply and budget feasible)  For all $i$, $ \sigma \sum_\tau \xitau \ptau  \leq b_i$. For all $\tau$, $\sumi\xitau \leq 1$.
\item
(Market clearing)  For all $\tau$, $\ptau > 0$ implies $ \sumi\xitau = 1 $.
\item
(No unnecessary pacing) For all $i$, $ \sigma \sum_\tau \xitau \ptau  < b_i$ implies $\betai = 1$.
\end{enumerate}
\end{definition}

Let $(, ) = (b,v,σ= 1/t,γ)$.
Given the equilibrium price $= [p^1,…, p^t]$, the revenue in a finite FPPE is $σ= 1/t $.

FPPE has some of the same scale-invariance properties as LFM.
In particular, scaling the budget and supply at the same time does not change the market equilibrium. That is, given a positive scalar $α$, if $(β,p)$ are the equilibrium pacing multiplier and prices in the market $(b,v,s,Θ)$, then
$(β,   p)$ are
the equilibrium quantities in the market $ (αb,  v, αs, Θ)$.
The same scale-invariance holds for the finite FPPE, i.e.,
if $(β, p) = (b,v,σ, γ)$, then $(,̱ p) = (αb, v, ασ, γ)$.
Given the invariance,
we can see that in order for the budget-supply ratio to match the limit market $(b,v,s,Θ)$, the finite market should be configured as either $(tb,v, 1, γ)$
or $(b,v,1/t, γ)$. We will study the latter, and simply refer to it as the finite FPPE.
Unlike LFM, FPPE does not enjoy invariance to valuation scaling, because buyers have a pacing multiplier of at most one in FPPE.

It is well-known \citep{cole2017convex,conitzer2022pacing,gao2022infinite}
that $β$ in a limit (resp.\ finite) FPPE uniquely solves
the population (resp.\ sample) dual EG program
\begin{align}
\label{eq:pop_deg}
\betast =  \argmin_{\beta \in (0, 1]^{n}}
H(\beta) \;, \;
\betagam = \argmin_{\b\in(0,1]^n} H_t(\b)  \;,
\end{align}
where the objectives $H$ and $H_t$ are the same as in \cref{eq:pop_deg_lfm}. The difference between the LFM and FPPE convex programs is that for FPPE we impose the constraint $ (0,1]^n$.

The EG program and certain quantities of the FPPE are related as follows.
\begin{lemma} \label{lm:fppe_relation}
Suppose $H$ is twice continuously differentiable at $\betast$, the equilibrium pacing multiplier.
% Define utilities from items: b
% $\mubarst = \int [\xst_1 v_1, \dots, \xst_n v_n]\tp s \dt \in \Rnp$.
Then $\nabla H (\betast) = - \deltast$, and $\nabla\sq H(\betast) \betast = [b_1/\betast_1, \dots, b_n / \betast_n]\tp$.
\end{lemma}

\textit{Proof sketch}
The first equality follows from the fact that
leftover budgets are the Lagrange multipliers corresponding to the constraint $β≤1 ∈$.
The second equality follows from the first-order homogeneity of $f(,)̱=max_i $ in \cref{eq:def:F}. See \cref{sec:techlemma_fppe} for details.

\section{Differentiability of EG Objective}
\label{sec:analytical_properties_of_dual_obj}
This section is dedicated to describing the differentiability properties of the EG objective $H$ in \cref{eq:def_pop_eg}. The second part of $H$ is clearly a nice function, and so we focus on its first part $()̱ = [f(,)̱]$.
Differentiability of the EG objective is important because the following assumption is needed when deriving the asymptotic distribution of LFM and FPPE.

\begin{assumption}[\textsf{\scriptsize{SMO}}]
\label{as:smo}
Let $\betast$ denote the equilibrium inverse bang-per-buck in LFM, or the equilibrium pacing multiplier in FPPE.
Assume the map $\beta \mapsto \fbar(\b)= \E_s[\max_i \betai \vithe ]$ is $C^2$ in a neighborhood of $\betast$. We let $\cH\defeq \nabla\sq H (\betast)$.
\end{assumption}

We start with the differential structure of $f(,)̱=max_i $.
The function $f(, )̱$ is a convex function of $$̱ and its subdifferential $\partial_\b f(\t, \b)$ is the convex hull of $\{ v_i e_i \in \Rnp: \text{index $i$ such that $\betai\vithe = \max_k \betak v_k(\t)$}  \}$, with $e_i$ being the base vector in $\Rn$.
When $\max_i \betai v_i(\t)$ is attained by a unique $i^*$, the function $f$ is differentiable. In that case, the $i$-th entry of $\nabla_\b f(\t,\b)$ is $v_i(\t)$ for $i=i^*$ and zero otherwise.

§.§ First-order Differentiability

We introduce notation for characterizing
first-order differentiability
of $\fbar (\b) = \E_s[f(\t, \b)]$.
Define the gap between the highest and the second-highest bid under pacing multiplier $\beta$ by

\begin{align}
\bidgap(\beta,\theta) \defeq \max \{\betai \vithe  \} - \operatorname{secondmax}\{ \betai \vithe \} \;,\end{align}

here $\operatorname{secondmax}$ is the second-highest entry; e.g., $\operatornamewithlimits{secondmax}([1,1,2]) = 1$.
When there is a tie for an item $\theta$, we have $\bidgap(\beta,\theta) = 0$.
When there is no tie for an item $\theta$, the gap $\bidgap(\beta,\theta)$ is strictly positive.
The gap function characterizes smoothness of $f$:
$f(\cdot, \theta)$ is differentiable at $
\beta$
iff $\bidgap(\beta,\theta)$ is strictly positive.

The following are equivalent.
(i) The dual objective $H$ is differentiable at a point $\beta$.
(ii) The function $\t \mapsto \bidgap(\beta,\theta)$ is strictly positive $s$-almost surely:

\begin{align} \label{eq:as:notie}
\P(\t: \bidgap(\beta,\theta) > 0 ) = 1
\;.
\end{align}

The set of items that incur ties under pacing profile $\b$ is $s$-measure zero:
$(θ∈Θ: = v_k(θ) for some $i\neq k$) = 0 $.

When one and thus all of the above conditions hold for some $$̱,
the gradient $\nabla_\b f(\t, \b)$ is well-defined for $s$-almost every $\t$, and
$\nabla \fbar (\beta) = \E[\nabla f(\t, \b)]$.
Proof and further technical remarks given in <ref>.

§.§ Second-order Differentiability

Given the neat characterization of differentiability of the dual objective via the
gap function $\bidgap(\beta,\theta)$,
it is natural to explore higher-order smoothness, which is needed for some of our asymptotic normality results.
<ref> in the appendix
is one where <ref> holds at a point, say $\b$, and $$ is differentiable in a neighborhood of $$̱, and yet $\fbar$ is not twice differentiable at $\b$.
We now provide three sufficient conditions that imply twice differentiability of objective $H$.

\begin{theorem}[Second-order differentiability, informal]
\label{thm:second_order_informal}
If any of the following conditions hold, then $\fbar$ and thus $H$ are $C^2$ at a point $\beta$. (i) A stronger form of \cref{eq:as:notie} holds: $\E[\bidgap(\beta,\t)\inv] < \infty$. (ii) The angular component of the random vector $v=(v_1,\dots,v_n):\Theta \to \Rnp$ is smoothly distributed.
(iii) $\Theta = [0,1]$, $s$ is the Lebesgue measure, the valuations $v_i(\cdot)$'s are linear functions, and $\b$ is the equilibrium inverse bang-per-buck in LFM.
See Appendix~\ref{sec:analytical_formal} for formal statements.
\end{theorem}
We show in Appendix~\ref{sec:closedformhessian} that when $H$ is twice differentiable, the Hessian matrix of $H$ has a closed-form expression.

\section{Statistical Results for Linear Fisher Markets}
We now turn to investigating the statistical convergence properties of finite LFMs to the limit LFM.
Suppose we sample an LFM ($\oLFM(b,v,1/t, \gamma)$), where $\gamma$ consists of $t$ i.i.d.\ samples from $s$.
We will study how such finite LFMs are distributed around the limit LFM ($\LFM(b,v,s,\Theta)$) as $t$ grows.
In LFM we focus on convergence of the following quantities: individual utilities, (log) Nash social welfare (NSW), and the pacing multiplier vector $\b$ (which characterizes the equilibrium, as shown in \cref{eq:pop_deg_lfm}).
% Since LFM is characterized by the convex program \cref{eq:pop_deg_lfm}, where the variable is the inverse bang-per-buck $\b$, we also present results for $\b$.
\cref{sec:lfm_basic} presents strong consistency and convergence rate results.
\cref{sec:lfm_asym} presents asymptotic distributions for the quantities of interest,
and a local minimax theory based on \citet{le2000asymptotics}, showing that the finite LFM provides an optimal estimate for the limit LFM in a local asymptotic sense.
\cref{sec:lfm_inference} discusses estimation of asymptotic variance of NSW.
% Recall from \cref{sec:lfm_review} that we assume
% WLOG. that the expected values of all buyers are 1 and
% that buyers' budgets sum to 1.

\subsection{Basic Convergence Properties}
\label{sec:lfm_basic}
In this section we show that we can treat observed quantities in the finite LFM as consistent estimators of their counterparts in the limit LFM.
% quantities observed in the finite LFM ($\b,u,\NSW$) satisfy both consistency and high-probability bounds.
Below we state the consistency results; the formal versions can be found in \cref{sec:consistency}.
We say an estimator sequence $\{ \hat a_t\}$ is strongly consistent for $a$ if $\P(\lim_{t \to \infty} \hat a_t = a) = 1$.

\begin{theorem}[Strong Consistency]
The NSW, pacing multiplier vector, and utility vectors in the finite LFM are strongly consistent estimators of their counterparts in the limit LFM.
\end{theorem}

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 multipliers will then be derived from the latter result.

\begin{theorem} \label{thm:lnsw_concentration}
For any failure probability $0< \eta < 1$, let $t \geq 2 {\vbarsq {\log(4n/\eta)}}$. Then with probability greater than $1-\eta$, we have $
|\LNSW^\gam - \LNSW^* |
\leq O(1) {\vbar \big(\sqrt{n\log ((n+\vbar)t)} +  \sqrt{\log(1/\eta)} \big)}{ t^{-1/2}},
where $O(1)$ hides only constants.
Proof in Appendix~\ref{sec:proof:thm:lnsw_concentration}.

\end{theorem}

\cref{thm:lnsw_concentration} establishes a convergence rate $|\LNSW^\gam - \LNSW^* | = \tilde O _p(\vbar \sqrt n t^{-1/2})$. The proof proceeds by first establishing a pointwise concentration inequality and then applies a discretization argument.

To state the result for the pacing multipliers $\b$,
we define approximate market equilibria (which we define in terms of approximately optimal pacing multiplier vectors $\beta$).
% 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(\betagam)$, and $u$ is the equilibrium utility vector if and only if $H_t(\beta_u) = H_t(\betagam)$.
\begin{align}
\cB^\gam(\epsilon)  \defeq \{ \beta \in \Rnpp: H_t(\beta) \leq \inf_\beta H_t(\beta) + \epsilon \}
, \;
\cB^*(\epsilon)  \defeq \{ \beta \in \Rnpp: H(\beta) \leq \inf_\beta H(\beta) + \epsilon \}
\label{eq:def:cBstar}
\;.
\end{align}
be the sets of $\epsilon$-approximate solutions to the sample and the population EG programs, respectively.
The next theorem shows that the set of $\epsilon/2$-approximate solutions to the sample EG program is contained in the set of $\epsilon$-approximate solutions to the population EG program with high probability.

\begin{theorem}[Convergence of Approximate Market Equilibrium] \label{thm:high_prob_containment}
Let $\eps > 0$ be a tolerance parameter and $\alpha \in (0,1)$ be a failure probability. Then for any $0\leq \delta \leq \eps/2$, to ensure
$ \P \big(
C_\LFM\cap \cBgam(\delta)
\subset
C_\LFM\cap \cBst(\epsilon)
\big) \geq 1 -2 \alpha$
it suffices to set
\begin{align}
\label{eq:t_condition}
t \geq O(1)\vbarsq \min\bigg\{  \frac{1}{
\ubar{b}\epsilon} , \frac{1}{\epsilon\sq} \bigg\}\bigg(n \log\Big(\tfrac{16(2n+\vbar)}{\eps - \delta}\Big) + \log\tfrac{1}{\alpha}\bigg)
% ,\quad \vbarsq {\log(4n/\alpha)}
\;,
\end{align}
the set
$C_\LFM$, defined in
\cref{eq:def_C_LFM}, is the natural region in which $\betast$ must lie, and $O(1)$ hides absolute constants.
Proof in Appendix~\ref{sec:proof:thm:high_prob_containment}.

\end{theorem}

By construction of $C_\LFM$ we know $\betast \in C_\LFM$ holds, and so $C_\LFM\cap \cBst(\epsilon)$ is not empty.
In the appendix, \cref{lm:value_concentration} shows that for $t$ sufficiently large, $\betagam \in C_\LFM$ with high probability, in which case the set
$C_\LFM\cap \cBgam(\delta)$ is not empty.
By simply taking $\delta = 0$ in \cref{thm:high_prob_containment} we obtain the corollary below.

\begin{corollary}
\label{cor:H_concentration}
Let $t$ satisfy \cref{eq:t_condition}. Then with probability $\geq 1 - 2 \alpha$ it holds $H(\betagam) \leq H(\betast) + \epsilon$.
\end{corollary}

More importantly, it establishes the fast statistical rate
$    H(\betagam ) - H(\betast) = \tilde{O}_p (t\inv )
for $t$ sufficiently large, where we use $\tilde{O}_p$ to ignore logarithmic factors.
In words: the limit LFM objective value of the \emph{finite} LFM solution $\betagam$ converges to the optimal limit LFM objective value with a rate $1/t$.
% This is in contrast to the usual $1/\sqrt{t}$ rate obtained in \cref{thm:lnsw_concentration}, where $\betagam$ is measured in the sample dual objective. There the $1/\sqrt{t}$ rate is the best obtainable.

By the strong convexity of the dual objective, the containment result can be translated to high-probability convergence of the pacing multipliers and the utility vector.

\begin{corollary}
\label{cor:beta_u_concentration}
Let $t$ satisfy \cref{eq:t_condition}. Then with probability at least $1 - 2 \alpha$ we have
$\| \betagam - \betast \|_2 \leq \sqrt{\frac{8\epsilon }{ \ubar{b}}}$ and $\| \ugam - \ust \|_2 \leq \frac{4}{\ubar{b}}\sqrt{8\epsilon / \ubar{b}}$.
\end{corollary}

We compare the above corollary with Theorem~9 from~\citet{gao2022infinite} which establishes the convergence rate of the stochastic approximation estimator based on the dual averaging algorithm~\citep{xiao2010dual}.
In particular, they show that the average of the iterates, denoted $\beta_{\mathrm{DA}}$, enjoys a convergence rate of
$\| \beta_{\mathrm{DA}} - \betast\|_2^2 = \tilde O_p \big(\frac{\vbar\sq }{ \ubar{b}\sq} \frac{1}{t}\big)$,
where $t$ is the number of sampled items.
The rate achieved in \cref{cor:beta_u_concentration} is
$\|\betagam - \betast\|_2 \sq = \tilde O_p \big(\frac{n \vbarsq}{\ubar{b}\sq} \frac{1}{t} \big)$.
We see that our rate is worse off by a factor of $n$. We conjecture that it can be removed by using the more involved localization arguments \citep{Bartlett2005}.
And yet our estimates are 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 the values $v_i(\theta)$ is required, while again $\betagam$ can be just observed naturally.

\subsection{Asymptotics of Linear Fisher Market}

\label{sec:lfm_asym}

In this section we derive asymptotic normality results for Nash
social welfare, utilities and pacing multipliers.
As we will see, a central limit theorem 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$ at optimality, with a nonsingular Hessian matrix.
We present CLT results under such a premise; \cref{thm:second_order_informal} gave three quite general settings under which these conditions hold.
% \ck{I added a reference to \cref{thm:second_order_informal} here. Is this the right reference though? Right now \cref{thm:second_order_informal} only covers twice differentiability, but not nonsingular Hessian. LF: I think it is correct reference. If the first part has a hessian, then the whole EG will have a nonsingular Hessian.}

\begin{theorem}[Asymptotic Normality of Nash Social Welfare]\label{thm:normality}
It holds that
\begin{align}  \label{it:thm:normality:1}
\sqrt{t}(\NSW^\gam - \NSW^*) \tod \cN
(0, \sigma\sq_{\NSW})
\;,
\end{align}
where $ \sigma\sq_{\NSW}
= \var(\pst)
=\int(p^*)\sq s \dt  -(\int p^* s \dt )\sq $.
Proof in Appendix~\ref{sec:proof:thm:normality}.
\end{theorem}

As stated previously, our asymptotic results for $\beta$ and $u$ require that $H$ is twice-continuously differentiable at $\betast$.
When this differentiability holds, by \cref{thm:first_differentiability}, the set of items that incur ties is $s$-measure zero, and thus the equilibrium allocation $\xst$ in the limit LFM is unique and must be pure.
Now we define a map $\must: \Theta \to \Rnp$, which represents the utility all buyers obtain from the item $\t$ at equilibrium. Formally,
\begin{align}
\must(\t) = [\xst_1 (\t) v_1 (\t), \dots, \xst_n(\t) v_n(\t)]\tp.
\end{align}
Since $\xst$ is pure, only one entry of $\must(\t)$ is nonzero.
Clearly $\int \must s \diff \t = [\ust_1,\dots, \ust_n]\tp$.
% Let $\Theta_i (\beta) \defeq \{\theta \in \Theta: v_i(\theta)\betai \geq v_k(\theta)\beta_k, \forall k\neq i \}$, i.e., the \emph{potential} winning set of buyer $i$ when the pacing multiplier are $\beta$. Let $\Theta_i^* \defeq \Theta_i(\betast)$.
% We will see later that if the dual objective is sufficiently smooth at $\betast$, then the winning sets,
% $\Theta_i^*$, $i\in [n]$, will be disjoint (up to a measure-zero set).
% Define the \emph{variance of winning values} for buyer $i$ as follows
% $$\Omega_i\sq = \int _{\Theta_i^*} v_i \sq (\theta) \diff S(\theta) - \bigg(\int _{\Theta_i^*} v_i (\theta) \diff S(\theta)\bigg)\sq \;. $$

\begin{theorem}[Asymptotic Normality of Pacing Multipliers and Utilities] \label{thm:clt_beta_u}
Let \cref{as:smo} hold with non-singular Hessian matrix $\cH=\nabla \sq H(\betast)$.
\begin{align}
\sqrt{t} (\beta^\gam - \beta^*) \tod \allowbreak\cN \big(0,
\Sigma_\beta
\big), \quad
\sqrt{t}(u^\gam - u^*) \tod \allowbreak\cN\big
\Sigma_u
\big) ,
\end{align}
$\Sigma_\beta = \cH\inv\allowbreak
\cov(\must)
\cH\inv $
$\Sigma_u =
\Diag(-b_i/(\betasti)\sq )\allowbreak
\cH\inv\allowbreak
\cov(\must) \allowbreak
\cH\inv\allowbreak
\Diag(-b_i/(\betasti)\sq ) .$
Proof in Appendix~\ref{sec:proof:thm:normality}.

\end{theorem}
\cref{thm:normality} can also be derived from \cref{thm:clt_beta_u} using the delta method, since $\NSWst = \sumiton b_i \log (\usti) = \sumi b_i \log (b_i / \betasti)$ is a smooth function of $\betast$.

We will show that the asymptotic variances in \cref{thm:clt_beta_u} are the best achievable, in an asymptotic local minimax sense. To make this precise, we need to introduce ``supply neighborhoods'' obtained through perturbing the original supply~$s$.

\subsubsection{Perturbed Supply}
\label{sec:perturb_supply}
First we introduce notation to parametrize neighborhoods of the supply $s$.
Let $g\in G_d = \{g:\Theta \to \R^d: \E[g]=0, \E[\|g\|\sq]<\infty\}$ be a direction along which we wish to perturb the supply $s$.
Given a vector $\alpha \in \R^d $ signifying the magnitude of perturbation,
we want to scale the original supply of item $\theta$ by  $\exp(\alpha\tp g(\theta))$ and then obtain a perturbed supply distribution by appropriate normalization.
To do this we define the perturbed supply by
\footnote{
In \citet{duchi2021asymptotic} they allow more general classes of perturbations, we specialize their results for our purposes.
%of the form $s_{\alpha,g,h} (\theta) = C \inv [{1 + h(\alpha\tp g(\theta))}] s(\theta) $ where $h:\R \to [-1,1]$ is any three-times continuously differentiable function with $h(t) = t$ on $[-\frac12, \frac12]$, and the derivative $h'\geq 0$ is nonnegative, and the first three derivatives of $h$ are bounded. For simplicity, we fix $h(t) = t$ on $\R$.
\begin{align}
\label{eq:perturbed_is_roughly_expo}
s_{\alpha,g} (\theta) \defeq C \inv [{1 + \alpha\tp g(\theta)}] s(\theta)
\end{align}
with a normalizing constant $C = 1 + \int \alpha\tp g(\theta) s(\theta)\diff\theta$.
As $\alpha\to 0$, the perturbed supply $s_{\alpha,g}$ effectively approximates
s_{\alpha,g} (\theta) \propto \exp(\alpha\tp g(\theta)) s(\theta)

We let $\betast_{\alpha,g}$, $\ust_{\alpha,g}$ and $\NSWst_{\alpha,g}$ be the limit inverse bang-per-buck, price and revenue in $\LFM(b,v,s_{\alpha,g}, \Theta)$.
Clearly $\betast = \betast_{0,g}$ for any $g$ and similarly for $\ust_{0,g}$ and $\NSW_{0, g}$.

\subsubsection{Asymptotic Local Minimax Optimality}

Given the asymptotic normality of observed LFM, it is desirable to understand the best possible statistical procedure for estimating the limit LFM.
One way to discuss the optimality is to measure the difficulty of estimating the limit LFM when the supply distribution varies over small neighborhoods of the true supply $s$, asymptotically. When an estimator achieves the best worst-case risk over these small neighborhoods, we say it is asymptotically locally minimax optimal. For general references, see \citet{vaart1996weak,le2000asymptotics}. More recently \citet[Sec.\ 3.2]{duchi2021asymptotic} develop asymptotic local minimax theory for constrained convex optimization, and we rely on their results.

Let $L:\Rn \to \R$ be any symmetric quasi-convex loss \footnote{A function is quasi-convex if its sublevel sets are convex.}.
In asymptotic local minimax theory we are interested in the local asymptotic risk: given a sequence of estimators $\{ \hat \beta_t: \Theta^t \to \Rn \}_t$,
\begin{align*}
\LAR_\beta (\{\hat \beta_t\}_t )  \defeq
{\sup_{ g\in G_d, d\in \mathbb{N}}
\lim_{c\to \infty}
\liminf_{t \to \infty}
\sup_{\|\alpha\|_2\leq \frac{c}{\sqrt t}}
\E_{s_{\alpha,g}^{\otimes t}}[L(\sqrt{t} (\hat \beta_t - \betast_{\alpha,g} ))] } \;.
\end{align*}
If we ignore the limits and consider a fixed $t$, then $\LAR_\beta$ roughly measures the
worst-case risk for the estimators $\{\hat \beta_t\}$.
Note that $\alpha$ is a $d$-vector, and thus the shrinking norm-balls depend on $d$, and the expectation is taken w.r.t.\ the $t$-fold product of the perturbed supply.

Similarly, define the risk for utility $u$ (resp. Nash social welfare $\NSW$)
given an estimator sequence $\{ \hat u _t\}$ (resp. $\{  \widehat \NSW_t\}$):
\begin{align*}
&\LAR_u(\{\hat u_t\}_t ) =
{\sup_{ g\in G_d, d\in \mathbb{N}}
\lim_{c\to \infty}
\liminf_{t \to \infty}
\sup_{\|\alpha\|_2\leq \frac{c}{\sqrt t}}
\E_{s_{\alpha,g}^{\otimes t}}[L(\sqrt{t} (\hat u_t - u^*_{\alpha,g} ))] } \;,
\\
& \LAR_\NSW(\{\widehat \NSW_t\}_t ) =
{\sup_{ g\in G_d, d\in \mathbb{N}}
\lim_{c\to \infty}
\liminf_{t \to \infty}
\sup_{\|\alpha\|_2\leq \frac{c}{\sqrt t}}
\E_{s_{\alpha,g}^{\otimes t}}[L(\sqrt{t} (\widehat \NSW_t - \NSW^*_{\alpha,g} ))] } \;.
\end{align*}

\begin{theorem} \label{thm:nsw_aym_risk}
Let \cref{as:smo} hold.
\begin{align*}
& \inf_{\hat \beta_t} \LAR_\b (\{ \hat \beta_t \})
\geq
\E[L(\cN(0, \Sigma_\b))] \;,
\\
& \inf_{\hat u_t} \LAR_u ( \{ \hat u_t \})
\geq
\E[L(\cN(0, \Sigma_u))]
\;,
\\
& \inf_{\widehat \NSW_t} \LAR_\NSW ( \{ \widehat \NSW_t \} )
\geq
\E[L(\cN(0, \sigma^2_\NSW))]
\;,
\end{align*}
where $\sigma\sq_\NSW$ is defined in \cref{thm:normality}, and $\Sigma_\b, \Sigma_u$ in \cref{thm:clt_beta_u}.
Proof in \cref{sec:proof:thm:nsw_aym_risk}
\end{theorem}
\subsection{Variance Estimation and Inference}\label{sec:lfm_inference}
In this section we show how to construct confidence intervals for Nash social welfare.
We will show how to construct confidence intervals for pacing multipliers and utilities in the FPPE section. The procedure is similar for LFM, and thus we omit it here.

First, regarding inference, it is interesting to note that
the observed NSW ($\LNSW^\gam$) is a negatively-biased estimate of the limit NSW ($\LNSW^*$), i.e., $ \E[\LNSW^\gam] - \LNSW^* \leq 0$.\footnote{Note
$ \E[\LNSW^\gam] - \LNSW^* = \E[\min_\beta H_t(\beta)] - H(\betast) \leq \min_\beta \E[H_t(\beta)]  - H(\betast)  = 0.$}
Moreover, it can be shown that, when the items are i.i.d.\ $\E[\min H_t] \leq \E[\min H_{t+1}]$  by a simple argument from Proposition~16 from~\citet{shapiro2003monte}. Monotonicity tells us that increasing the market size produces, on average, less biased estimates of the limit NSW.

To construct confidence intervals for Nash social welfare, one needs to estimate the asymptotic variance.
Let $\ptau$ be the price of item $\thetau$ in the finite market, and $\bar p = \frac1t \sumtau \ptau$.
The variance estimator is then
\begin{align}
\hat\sigma_{\NSW}\sq \defeq \frac{1}{t} \sumtau\big( \ptau - \bar p\big)\sq
\; .
\end{align}
We emphasize that in the computation of the variance estimator $ \hat\sigma_{\NSW}\sq$ one does not need knowledge of the valuations $\{\vithetau\}_{i,\tau}$.
All that is needed is the equilibrium prices $\pgam = (p^{1},\dots, p^{t})$ for the items.
Given the variance estimator, we
construct the confidence interval
$ \big[ \LNSW^\gam \pm z_{\alpha/2}  \frac{\hat \sigma_{\NSW}}{\sqrt t}\big]$,
where $z_\alpha$ is the $\alpha$-th quantile of a standard normal.
The next theorem establishes validity of the variance estimator.
\begin{theorem} \label{thm:ci_lnsw}
It holds that $\hat \sigma ^2_{\NSW} \toprob \sigma_{\NSW}\sq$.
Given $0< \alpha < 1$, it holds that
\lim_{t\to\infty} \P\big( \NSW^* \in [ \NSW^\gam \pm z_{\alpha/2}  \hat \sigma_{\NSW}/\sqrt t \,] \big)
$.  Proof in Appendix~\ref{sec:proof_var_est}.

\end{theorem}

% 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 objective 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.
% In \cref{sec:hessian_estimation}
% we provide a brief discussion of variance estimation under the following two simplified scenarios. First, in the case where $\E [\bidgap(\beta, \theta)\inv ]< \infty$ holds in a neighborhood of $\betast$, which we recall is a stronger form \cref{eq:as:notie}, we prove that a plug-in type variance estimator is valid.
% % This is achieved using a result due to \citet{shapiro1989asymptotic} which shows uniform concentration of subgradient of random functions.
% Second, if we have knowledge of $\{\vithetau\}_{i,\tau}$, then we give a numerical difference estimator for the Hessian which is consistent.

% \section{Conclusion}
% We developed the first statistical inference framework for Fisher market equilibria. Several problems remain open. (1) Obtain sharp finite sample bound for $\betagam$ in \cref{cor:beta_u_concentration}. We conjecture
% that the bound $\| \betagam - \betast\|_2^2 = O_p(\frac{\vbar \sq}{\ubar{b} t})$ could be achieved by using the peeling argument and localized Rademacher complexity methods \citep{sridharan2008fast, bartlett2005local}.
% (2) Develop asymptotics for a broader class of Fisher markets. In the current paper we provide a rich class of Fisher markets with $C_\LFM^2$ dual objective.
% To improve existing results, one could potentially identify richer classes of Fisher markets with $C_\LFM^2$ dual objective, or develop asymptotics without the twice differentiability in the first place.
% (3) Investigate asymptotics of quasilinear Fisher markets. As mentioned previously, the solution of the Eisenberg-Gale program for QME may lie on the boundary of the constraint set, adding significant technical difficulties.

\section{Statistical Results for FPPE}

Next we study statistical inference questions for the FPPE model.
Since FPPE is characterized by an EG-style program similar to that of LFM, many of the results for FPPE are similar to those for LFM. However, an important difference is that the FPPE model has constraints on the pacing multipliers, which makes the asymptotic theory more involved.
As for LFM, we assume that we observe a finite auction
market $\oFPPE(b,v,1/t, \gamma)$ with $\gamma$ being $t$ i.i.d. draws from $s(\cdot)$, and we use it to estimate quantities from the limit market $\FPPE(b,v,s,\Theta)$.
In FPPE we mainly focus on the revenue of the limit market, and for the same reason as in LFM, since FPPE is characterized by EG program with optimizing variable being the pacing multiplier, we also present results for $\b$.
Similarly to the LFM case, one could use results for $\b$ to derive estimators for buyer utilities.
% In \cref{sec:fppe_basic}
% we provide strong consistency and convergence rates for revenue and $\b$.
% In \cref{sec:fppe_asym} we present asymptotic distributions.
% Compared with LFM, the asymptotic theory for FPPE is more involved due the present of constraints in its EG program.
% In \cref{sec:fppe_inference} we estimate the asymptotic variances.

\subsection{Basic Convergence Properties}
\label{sec:fppe_basic}
Since FPPE has a similar convex program characterization as LFM, strong consistency and convergence rate results can be derived using similar ideas.

\begin{theorem}\label{thm:fppe_as_convergence}
We have $\betagam \toas \betast$,
and $\REVgam \toas \REVst$. Proof in Appendix~\ref{sec:proof:thm:fppe_as_convergence}.
\end{theorem}

We complement the strong consistency result with the following rate results. They are derived using a discretization argument.
\begin{theorem}
\label{thm:rev_convergence}
It holds that
$ \| \betagam - \betast\|_2
= \tilde O_p(\frac{\sqrt{n} (\vbar + 2\nubar n + 1)}{\ubar{b} \sqrt t})
$ | \REV^\gam - \REV^* | =
\tilde{O}_p
(\frac{\vbar \sqrt{n} (\vbar + 2\nubar n + 1 ) }{ \ubar{b} }\frac{1}{\sqrt{t}}).$
Proof in Appendix~\ref{sec:proof:thm:rev_convergence}.
\end{theorem}

The above bounds hold for a broad class of limit FPPE models and may be loose for a particular model.
In \cref{sec:fppe_asym}, we show that for buyers $i \in \{ i:\betasti = 1\}$, their pacing multipliers converge at a rate faster than $ \tilde O_p(1/\sqrt t)$.

\subsection{Asymptotics of FPPE}
\label{sec:fppe_asym}

As in LFM, our statistical inference results require the limit market to behave smoothly around the optimal pacing multipliers $\betast$.
To that end, we will assume \cref{as:smo} as in LFM.
Similar to LFM, under \cref{as:smo}, the equilibrium allocation $\xst$ is unique and must be pure.
Again we can define
\begin{align}
\label{eq:def:must}
\must (\t) = [x^*_1(\t) v_1(\t), \dots, x^*_n(\t) v_n (\t)]\tp\; .
\end{align}
Under \cref{as:smo}, the equilibrium allocation $\xst$ is unique, so $\must(\cdot)$ is also unique.
Moreover, $\must(\t) = \nabla f(\t, \betast)$,
and $ (\betast) \tp \must(\t) = \pst(\t)$ (the set of nondifferentiable points has measure zero, and thus we can ignore such points).
% CK: the below was already defined in the previous sentence.
Also let
\begin{align}
\label{eq:def:mubarst}
\mubarst = \int \must s \dt \in \Rnp
\end{align}
to denote the utility from items.
Note that in the FPPE model, buyers' utility consists of two parts: utility from items and leftover budgets.
In FPPE, the pacing multipliers relate budgets and utilities via \citep{conitzer2022pacing}
\begin{align}
\mubarsti + \deltasti = b_i/ \betasti \;.
\end{align}

In the unconstrained case, classical $M$-estimation theory says that, under regularity conditions, an $M$-estimator is asymptotically normal with covariance matrix $\cH\inv  \var(\text{gradient}) \cH\inv$ \citep[Chap.\ 5]{van2000asymptotic}. However, in the case of FPPE which is characterized by a constrained convex problem, the Hessian matrix needs to be adjusted to take into account the geometry of the constraint set $B=(0,1]^n$ at the optimum $\betast$.
We let $\cP \defeq \Diag( \indi( \betasti < 1) )$ be an ``indicator matrix'' of buyers whose $\betasti < 1$, and define the projected Hessian
\begin{align}
\label{def:cHB}
\cH_B \defeq \cP \cH \cP \;.
\end{align}
It will be shown that the asymptotic variance of $\betagam$ is $\cH_B\pinv \var(\text{gradient}) \cH_B\pinv$ and the ``gradient" is exactly $\must$.

\begin{assumption}[\textsf{\scriptsize{SCS}}]
\label{as:scs} Strict complementary slackness holds:
$\betasti = 1$ implies  $\delta^*_i  > 0$.
\end{assumption}

\cref{as:scs} can be viewed as a non-degeneracy condition from a convex programming perspective, since $\delta_i$ corresponds to a Lagrange multiplier on $\beta_i \leq 1$.
From a market perpective, \cref{as:scs} requires that if a buyer's bids are not paced ($\betasti = 1$), then their leftover budget $\delta^* _i$ must be strictly positive.
This can again be seen as a market-based non-degeneracy condition: if $\deltasti=0$ then the budget constraint of buyer $i$ is binding, yet $\betasti=1$ would imply that they have no use for additional budget.
% This is a mild requirement; the only way for it to be violated would be if
% if one bids exactly how much he values the item without scaling them down, it shows that her budget is superfluous for winning her desired items through the sequence of auctions. The situation where such a buyer happens to have no budget left is an edge case.
If \cref{as:scs} fails, one could slightly increase the budgets of buyers for which \cref{as:scs} fails, i.e., those who do not pace yet have exactly zero leftover budget, and obtain a market instance with the same equilibrium, but where \cref{as:scs} holds.

From a technical viewpoint, \cref{as:scs} is a stronger form of first-order optimality.
Note $\nabla H(\betast) = -\deltast$ (cf.\ \cref{lm:fppe_relation}).
The usual first-order optimality condition is
\begin{align}
- \nabla H(\betast) \in \cN_B(\betast) \;,
\label{eq:usual_foc}
\end{align}
where $\cN_B(\beta) = \prod_{i=1}^n J_i(\beta)$ is the normal cone with $J_i (\beta)= [0,\infty)$
if $\betai = 1$ and $J_i (\beta)= \{0\}$ if $\betai < 1$ for $\beta \in \Rnpp$.
Then \cref{eq:usual_foc} translates to the condition that $\betasti = 1$ implies $\deltasti \geq 0$.
On the other hand, when written in terms of the normal cone,
\cref{as:scs} is equivalent to $$- \nabla H(\betast) \in \relint ( \cN_B(\betast) ) \; .
\footnote{
The relative interior of a set is $\relint(S)\defeq\{x \in S:$ there exists $\epsilon>0$ such that $N_\epsilon(x) \cap \operatorname{aff}(S) \subseteq S \}$ where $\operatorname{aff}(S)$ is the affine hull of $S$, and $N_\epsilon(x)$ is a ball of radius $\epsilon$ centered on $x$. %For example, the interior of a line segment on $\R^2$ is empty, but its relative interior is the line segment without its endpoints.
Given that $ \relint ( \cN_B(\betast) ) \subset \cN_B(\betast) $, \cref{as:scs} is obviously a stronger form of first-order condition. The \cref{as:scs} condition is commonly seen in the study of statistical properties of constrained $M$-estimators (\citealt[Assumption B]{duchi2021asymptotic} and \citealt{shapiro1989asymptotic}). In the proof of \cref{thm:clt}, \cref{as:scs} forces the critical cone to reduce to a hyperplane and thus ensures asymptotic normality of the estimates.
Without \cref{as:scs}, the asymptotic distribution of $\betagam$ could be non-normal.
% \ck{critical cone is only defined in appendix. Not sure if it's possible to give a high-level idea of what it is here?}

\subsubsection{Central Limit Theorems}
We now show that the observed pacing multipliers $\betagam$ and the observed revenue $\REV^\gamma$ are asymptotically normal.
Define the \emph{influence functions}
\begin{equation} \label{eq:def_inf_func}
\begin{aligned}
D_\beta(\theta) & \defeq - (\cH_B)^\dagger (\must(\theta) - \mubarst) ,
\\
D_\REV(\theta) & \defeq \pst(\theta) - \REV^* + (\mubarst) \tp D_\beta(\theta).
\end{aligned}
\end{equation}
Recall $\must$ is defined in \cref{eq:def:must}, $\mubarst$ in \cref{eq:def:mubarst}, $\cH_B$ in \cref{def:cHB}.
And note $\E[D_\beta] = 0$ and $\E[D_\REV] = 0$.

\begin{theorem}
\label{thm:clt}
\cref{as:smo,as:scs} hold, then
\begin{align*}
&\sqrt{t}(\betagam - \betast) =  \frac1\roott \sumtau D_\beta (\thetau) + o_p(1) \; ,
\\
&\sqrt{t} (\REV^\gam - \REV^*) = \frac1\roott \sumtau D_\REV(\thetau) + o_p(1)  \;.
\end{align*}
Consequently, $ \sqrt{t}(\betagam - \betast )$ and $\sqrt {t} (\REV^\gamma - \REV^*) $
are asymptotically normal with means zero and variances $\Sigma_\beta\defeq \E[D_\beta D_\beta\tp ] =  (\cH_B)\pinv \var(\must) (\cH_B)\pinv$ and $\sigma^2_\REV \defeq \E[D_\REV (\theta)^2]$.
Proof in Appendix~\ref{sec:proof:thm:clt}.
\end{theorem}

The functions $D_\beta$ and $D_\REV$ are called the {influence functions} of the estimates $\betagam$ and $\REV^\gam$ because they measure the change in the estimates caused by adding a new item to the market (asymptotically).

\cref{thm:clt} implies fast convergence rate of $\betagami$ for $i \in \{ \betasti =1\}$.
To see this, we
suppose wlog.\ that $I = [k]$, i.e. the  first $k$ buyers are the ones with $\beta_i=1$.
Then the pseudo-inverse of the projected Hessian $(\cH_B )\pinv = \Diag(0_{k\times k} , (\cH_{\Ic \Ic})\inv )$ where $\cH_{\Ic \Ic}$ is the lower right $(n-k)\times(n-k)$ block of $\cH $.
Consequently, the upper $k$ diagonal entries of $\Sigma_\beta$ are zeros.
This result shows that the constraint set $B$ ``improves'' the covariance by zeroing out the entries corresponding to the active constraints $I$.
$ \sqrt{t} (\betagami - \betasti)$ and $\sqrt t (\ugami - \usti)$ are of order $o_p(1)$ for $i \in I$, and thus converging faster than the usual $O_p(1)$ rate.
The fast rate phenomenon is empirically investigated in \cref{sec:exp_fast_rate}.

The practical implication is the following.
By \cref{as:scs} we have $I = \{i: \betasti = 1\}= \{ i: \deltasti > 0\}$, i.e., $I$ is the set of buyers who are not budget constrained, and $\Ic = \{i:\betasti < 1\} = \{ i: \deltasti = 0\} $, i.e., $\Ic\,$ is the set of buyers who exhaust their budgets. \footnote{Without \cref{as:scs}, it only holds $ \{i:\betasti < 1\} \subset \{i:\deltasti = 0\}$ and $\{i:\deltasti > 0 \}\subset \{i:\betasti = 1\}$ by complementary slackness.}
In the context of first-price auctions,
the fast rate $o_p(t^{-1/2})$ implies that the platform can identify  which buyers are budget constrained even when the finite market is small.

The proof of \cref{thm:clt} proceeds by showing that FPPE satisfy a set of regularity conditions that are sufficient for asymptotic normality~\citep[Theorem 3.3]{shapiro1989asymptotic}; the conditions are stated in \cref{thm:the_shapiro_thm} in the appendix. Maybe the hardest condition to verify is the so called stochastic equicontinuity condition (\cref{it:stoc_equic}), which we establish with tools from the empirical process literature.
In particular, we show that the class of functions, parameterized by a pacing multiplier vector $\beta$, that map each item to its corresponding first-price auction allocation under the given $\beta$, is a VC-subgraph class. This in turn implies stochastic equicontinuity.
\cref{as:scs} is used to ensure normality of the limit distribution.

Finally, we remark that the CLT result for revenue holds true
even if $I = \emptyset$, i.e., $\betasti < 1$ for all $i$.
If $\betagami < 1$ for all $i$, then all buyers' budgets are exhausted in the observed FPPE, and so we have
\REVgam = \REVst = \sumiton b_i$.
By the convergence $\betagam \toprob \betast$, we know that
$\REVgam = \REVst$ with high probability for all large~$t$ if $I=\emptyset$.
In that case, it must be that the asymptotic variance of revenue equals zero.
Our result covers this case because one can show $\sigma\sq_\REV = 0$ using $\cH \betast = \mubarst$ if $I = \emptyset$ (\cref{lm:fppe_relation}), and $(\betast)\tp \must(\t) = \pst(\t)$.

In an FPPE individual utilities and Nash social welfare can be similarly defined.
By applying the delta method and the results in \cref{thm:clt}, we can derive asymptotic distributions for individual utilities $\ugam$, leftover budget $\deltagam$ and Nash social welfare, since they are smooth functions of $\beta$. See \cref{sec:full:cor:clt_u_and_nsw} for more details.

% \begin{corollary}
%     \label{cor:clt_u_and_nsw}
%     Under the same conditions as \cref{thm:clt},
%        $\sqrt{t} (\ugam - \ust) $, $\sqrt t(\deltagam - \deltast)$ and $\sqrt{t}(\NSW^\gam - \NSW^*) $
%        are asymptotically normal with means zero and
% (co)variances defined in \cref{sec:full:cor:clt_u_and_nsw}.
% \end{corollary}

\subsubsection{Asymptotic Local Minimax Optimality}

Given the asymptotic distributions for $\beta, u, \NSW$ and $\REV$, we will show that the observed FPPE estimates are optimal in an asymptotic local minimax sense.
Recall in \cref{sec:perturb_supply} we have defined the perturbed supply family $G_d$ of dimension $d$ with perturbation $(\alpha,g)$.

\paragraph{Asymptotic local minimax optimality for $\beta$.}
We first focus on estimation of pacing multipliers.\
For a given perturbation ${(\alpha,g)}$, we let $\betast_{\alpha,g}$, $\pst_{\alpha,g}$ and $\REVst_{\alpha,g}$ be the limit FPPE pacing multiplier, price and revenue under supply distribution $s_{\alpha,g}$.
Clearly $\betast = \betast_{0,g}$ for any $g$ and similarly for $\pst_{\alpha,g}$ and $\REV_{\alpha, g}$.
Let $L:\Rn \to \R$ be any symmetric quasi-convex loss.
\footnote{A function is quasi-convex if its sublevel sets are convex.}
In asymptotic local minimax theory we are interested in the local asymptotic risk: given a sequence of estimators $\{ \hat \beta_t: \Theta^t \to \Rn \}_t$,

\begin{equation*}
\LAR_\beta (\{\hat \beta_t\}_t )  \defeq
{\sup_{ g\in G_d, d\in \mathbb{N}}
\lim_{c\to \infty}
\liminf_{t \to \infty}
\sup_{\|\alpha\|_2\leq \frac{c}{\sqrt t}}
\E_{s_{\alpha,g}^{\otimes t}}[L(\sqrt{t} (\hat \beta_t - \betast_{\alpha,g} ))] } \;.
\end{equation*}
As an immediate application of Theorem 1 from \citet{duchi2021asymptotic}, it holds that
\begin{align*}
\inf_{ \{\hat \beta_t\}_t }  {\small \textsc{{LAR}}}_\beta (\{\hat \beta_t\}_t )  \geq \E[L(\cN( 0, (\cH_B)\pinv \var(\must) (\cH_B)\pinv))] \; .
\end{align*}
where the expectation is taken w.r.t.\ a normal specified above.
Moreover, the lower bound is achieved by the observed FPPE pacing multipliers $\betagam$ according to the CLT result in \cref{thm:clt}.

\paragraph{Asymptotic local minimax optimality for revenue estimation.}
For pacing multipliers, the result is a direct application of the perturbation result from \citet{duchi2021asymptotic}. The result for revenue estimation is more involved.
Given a symmetric quasi-convex loss $L:\R\to\R$, we define the local asymptotic risk for any procedure $\{\hat r _t : \Theta^t \to \R\}$ that aims to estimate the revenue:
\begin{align*} \hspace{-.2cm}
\LAR_\REV ( \{\hat r_t \}) \defeq
\sup_{ g\in G_d, d\in \mathbb{N}}
\lim_{c\to \infty}
\liminf_{t \to \infty}
\sup_{\|\alpha\|_2\leq \frac{c}{\sqrt t}}
\E_{s_{\alpha,g} ^{\otimes t}}[L(\sqrt{t} (\hat r_t  - \REVst_{\alpha,g} ))] \;.
\end{align*}
\begin{theorem}[Asymptotic local minimaxity for revenue]
\label{thm:rev_localopt}
If \cref{as:smo,as:scs} hold, then
\begin{align*}
\inf_{ \{\hat r_t\}} \LAR_\REV ( \{\hat r_t \}) \geq \E[L(\cN(0, \sigma\sq_\REV))] \;.
\end{align*}
\end{theorem}

Proof in Appendix~\ref{sec:proof:rev_local_asym_risk}. In the proof we calculate the derivative
of revenue w.r.t.\ $\alpha$, which in turn uses
a perturbation result for constrained convex programs from \citet{duchi2021asymptotic,shapiro1989asymptotic}.
Again, the lower bound is achieved by the observed FPPE revenue $\REVgam$ according to the CLT result in \cref{thm:clt}.
Similar optimality statements can be made for $u$ and $\NSW$ by finding the corresponding derivative expressions.

\subsection{Variance Estimation and Inference}
\label{sec:fppe_inference}

In order to perform inference, we need to construct estimators for the influence functions \cref{eq:def_inf_func}. In turn, this requires estimators for
the projected Hessian $\cH_B$ (\cref{def:cHB}) and the variance of the utility map $\must$ (\cref{eq:def:must}).

\textbf{The Hessian.}
Given a sequence of smoothing parameters $\varepsilon_t = o(1)$, we estimate the projection matrix $\cP$ by
\hat \cP \defeq \Diag(\indi(\betagami < 1 - \varepsilon_t )) \;.
For the same sequence $\varepsilon_t$, we introduce a numerical difference estimator $\hat \cH$ for the Hessian matrix $\cH$, whose $(i,j)$-th entry is
\begin{align}
\label{eq:def:hessian_estimate}
\hat{\cH}_{i j}\defeq[H_t(\betagam_{++})-H_t(\betagam_{+-})
+H_t(\betagam_{--})] / 4 \varepsilon_t^2
\end{align}
$\betagam_{\pm \pm} \defeq  \betagam \pm e_i \varepsilon_t \pm e_j \varepsilon_t$,
and $H_t$ is defined in \cref{eq:def_pop_eg}. Finally, $\hat \cH_B = \hat \cP \hat \cH \hat \cP$ is the estimator of $\cH_B$.

\textbf{The term $\cov(\must)$.}
Let $\xgam = (\xitau)_{i,\tau}$ and price $\pgam = [p^1, \dots, p ^ t ] \tp $ be the allocation and prices in the finite FPPE.
Mimicking \cref{eq:def:must,eq:def:mubarst}, define the finite sample analogues
\begin{align}
\mu^\tau = [x_1^{\tau} v_1^\tau, \dots, x_n^{\tau} v_n^\tau]\tp, \;\quad \bar \mu= \frac1t \sumtau \mutau \;.
\end{align}
Recall $\REVgam = \frac1t \sumtau \ptau$.
Then we define the following influence function estimators
\begin{align*}
\hat D_\beta^\tau  \defeq - (\hat \cH_B)\pinv (\mutau- \mubar) \;,
\quad
\hat D _\REV ^\tau \defeq \ptau - \REV^\gamma + (\mubar) \tp\hat D_\beta^\tau \;.
\end{align*}
% which estiamte the influence functions $D_\beta$ and $D_\REV$ evaluated at item $\thetau$.
Given that the asymptotic variance of $\betagam$ (resp.\ $\REVgam$) is
$\E[D_\beta D_\beta \tp]$ (resp.\ $\E[D_\REV\sq]$), plug-in estimators for the (co)variance are naturally
\begin{align}
\hat \Sigma_\beta \defeq \frac{1}{t} \sumtau \hat D_\beta^\tau  (\hat D_\beta^\tau )\tp \; , \;\;
\hat \sigma \sq_\REV \defeq \frac{1}{t} \sumtau (\hat D_\REV ^\tau)\sq \; .
\label{eq:plugin variance}
\end{align}
For any $\alpha \in (0,1)$, the $(1-\alpha)$-confidence regions for $\betast$ and $\REVst$ are
\begin{align}
& \CR_\beta\defeq \betagam + (\chi_{n, \alpha} / \sqrt{t})\hat \Sigma_\beta^{1/2} \B \; ,\label{eq:beta CI}
\\
& \CI_\REV \defeq\Big[\REVgam\pm z_{\alpha/2}  \hat \sigma_{\REV}/\sqrt t\Big] \; .
\label{eq:rev_variance}
\end{align}
where $\chi_{n,\alpha}$ is the $(1-\alpha)$-th quantile of a chi-square distribution with degree $n$, $\B$ is the unit ball in $\Rn$, and $z_{\alpha/2}$ is the $(1-\frac{\alpha}{2})$-th quantile of a standard normal distribution.
The coverage rate of $\CI_\REV$ is empirically verified in \cref{sec:exp_rev_coverage}.
\begin{theorem}
\label{thm:variance_estimation}
Under the conditions of \cref{thm:clt},
let $\varepsilon_t \sqrt{t}\to \infty$ and $\varepsilon_t = o(1)$.
Then $\hat \Sigma_\beta \toprob \Sigma_\beta$ and $\hat \sigma_\REV \sq \toprob \sigma_\REV \sq$.
Consequently, for any $\alpha \in (0,1)$,
$\P (\betast \in \CR_\beta ) \to 1-\alpha$ and $\P(\REVst \in \CI_\REV ) \to 1-\alpha$.
Proof in Appendix~\ref{sec:proof:thm:variance_estimation}.
\end{theorem}
The theorem suggests choosing smoothing parameter $\varepsilon_t = t^{- d}$ for $0 < d < \frac12$. \cref{sec:exp_hessain} studies how the choice of $d$ affects the Hessian estimation numerically.
% Variance estimators for $u$, $\delta$ and $\NSW$ can be constructed similarly.
% $
%      \hat \Sigma_u \defeq \allowbreak \Diag{({b_i}/({\betagami})\sq)} \allowbreak \hat  \Sigma_\beta  \allowbreak    \Diag({b_i}/({\betagami})\sq) \text{ and }
%      \hat \sigma^2_\NSW\defeq\Vec(b_i/\betagami)\tp \allowbreak \hat\Sigma_\beta \allowbreak\Vec(b_i / \betagami) \;.
% $
% Their consistency is ensured by Slutsky's theorem. The corresponding confidence region/interval are $ \CR_u \defeq \ugam + (\chi_{n, \alpha} / \sqrt{t})\hat \Sigma_u^{1/2} \B$ and
% $ \CI_\NSW \defeq[\NSWgam\pm z_{\alpha/2}  \hat \sigma_{\NSW}/\sqrt t] $.
\subsection{Application: A/B Testing in First-Price Auction Platforms}
\label{sec:ab testing}

Consider an auction market with $n$ buyers with a continuum of items $\Theta$ with supply function $s$.
Now suppose that we are interested in the effect of deploying some new technology (e.g. new machine learning models for estimating click-through rates in the ad auction setting).
To model treatment application we introduce the \emph{potential value functions}
$$ \hspace{-.2cm} v(0) \defeq (v_1(0,\cdot),\dots, v_n(0,\cdot)),\;v(1)\defeq (v_1(1,\cdot),\dots, v_n(1,\cdot)).$$
If item $\theta$ is exposed to treatment $w \in \{0,1\}$, then its value to buyer $i$ will be $v_i(w,\theta)$. %Let $s$ is the supply distribution of items.

Suppose we are interested in estimating the change in the auction market when treatment 1 is deployed to the entire item set $\Theta$.
In this section we describe how to do this using A/B testing, specifically for estimating the treatment effect on revenue. %Analogous results can be readily developed for pacing multipliers using \cref{eq:beta CI}.
Formally, we wish to look at the difference in revenues between the markets
\FPPE(b, v(0), s) \text{ and }  \FPPE(b,v(1), s),
where $\FPPE(b, v(0), s)$ is the market with treatment 1, and $\FPPE(b,v(1), s)$ is the one with treatment 0. %, both defined in \cref{def:limit_fppe}.
The treatment effects on revenue is defined as $$\tau_{\REV} \defeq \REVst(1) - \REVst(0)\;,$$
where $\REVst(w)$ is revenue in the equilibrium $\FPPE(b,v(w), s)$.

We will refer to the experiment design as \emph{budget splitting with item randomization}.
The design works in two steps, and closely mirrors how A/B testing is conducted at large tech companies.

\textbf{Step 1. Budget splitting.}
We create two markets, and every buyer is replicated in each market.
For each buyer $i$ we allocate $\pi b_i$ of their budget to the market with treatment $w=1$, and the remaining budget, $(1-\pi)b_i$, to the market with treatment $w=0$.
Each buyer's budget is managed separately in each market.

\textbf{Step 2. Item randomization.}
Let $(\theta^1,\theta^2,\dots)$ be i.i.d.\ draws from the supply distribution $s$.
For each sampled item, it is applied treatment $1$ with probability $\pi$ and treatment $0$ with probability $1-\pi$.
The total A/B testing horizon is $t$. When the end of the horizon is reached, two observed FPPEs are formed. Each item has a supply of $\pi/t_1$ in the 1-treated market and $(1-\pi)/t_0$ in the 0-treated market. The $1/t_1$ is the scaling required for our CLTs and the $\pi$ factor ensures the budget-supply ratio agrees with the limit market;
due to FPPE scale-invariance, we could equivalently rescale budgets.

Let $t_0$ be the number of $0$-treated items, and $t_1$ be the number of $1$-treated items. Conditional on the total number of items $t=t_1 + t_0$, the random variable $t_1$ is a binomial random variable with mean $\pi t$. Let $\gamma(0) = (\theta^{1,1},\dots, \theta^{1,t_1})$ be the set of $0$-treated items, and similarly $\gamma(1) = (\theta^{0,1},\dots, \theta^{0,t_0})$.
The total item set $\gamma = \gamma(0) \cup \gamma(1)$.
The observables in the described A/B testing experiment are
$$ \hspace{-.1cm}
\oFPPE \big(\pi b, v(1), \tfrac{\pi}{t_1}, \gamma(1)  \big),\;
\oFPPE \big( (1-\pi ) b,  v(0), \tfrac{1-\pi}{t_0}, \gamma(0)\big ), $$
both defined in \cref{def:finite_fppe}.
Let $\REVgam(w)$ denote the observed revenue in the $w$-treated market.
The estimator of the treatment effect on revenue is
\hat \tau_{\REV} \defeq \REVgam(1) - \REVgam(0).$$

For fixed $(b, s)$, the variance $\sigma\sq_\REV$ in \cref{thm:clt} is a functional of the value functions. We will use $\sigma\sq_\REV(w)$ to represent the revenue variance in the equilibrium $\FPPE(b,v(w), s)$.
Each variance can be estimated using \cref{eq:plugin variance}.

\begin{theorem}[Revenue treatment effects CLT]
\label{thm:clt_ab_testing}
Suppose \cref{as:smo} and \cref{as:scs} hold in the limit markets $\FPPE(b,v(1),s)$ and $\FPPE(b,v(0),s)$. Then
$\sqrt{t} (\hat \tau_\REV - \tau_\REV) \tod\cN\allowbreak \big(0, \frac{ \sigma\sq_\REV(1)}{\pi} \allowbreak + \allowbreak\frac{ \sigma\sq_\REV(0)}{(1-\pi)} \big) .$
Proof in Appendix~\ref{sec:proof:thm:clt_ab_testing}.
\end{theorem}

Based on the theorem, an A/B testing procedure is the following.
Compute the revenue variance as \cref{eq:plugin variance} for each market, obtaining $ \hat \sigma\sq_\REV(1)$ and $ \hat \sigma\sq_\REV(0)$, and form the confidence interval
\begin{align}
\hat \tau_\REV \pm z_{\alpha/2} \bigg( \frac{ \hat \sigma\sq_\REV(1)}{\pi} \allowbreak + \allowbreak\frac{ \hat \sigma\sq_\REV(0)}{(1-\pi)}  \bigg).
\label{eq:ab_rev_ci}
\end{align}
If zero is on the left (resp.\ right) of the CI, we conclude that the new feature increases (resp.\ decreases) revenue with $(1-\alpha)\times 100\%$ confidence.
If zero is in the interval, the effect is undecided.
See \cref{sec:experiment_abtest} for a semi-synthetic study verifying the validity of this procedure.

\section{Experiment}

\subsection{Synthetic Experiment}

\subsubsection{Hessian Estimation}
\label{sec:exp_hessain}
Recall that a key component in the variance estimator is the Hessian matrix, which
we estimate by the finite-difference method in \cref{eq:def:hessian_estimate}.
Finite difference estimation requires the smoothing parameter $\varepsilon_t$. The smoothing $\varepsilon_t$ is used to (1) estimate the active constraints and (2) construct the numerical difference estimator $\hat \cH$.
\cref{thm:variance_estimation} suggests a choice of
$\varepsilon_t = t^{-d}$ for some $0 < d < \tfrac12$.
In \cref{app:hessian_estimation}, we investigate the effect of $d$ numerically. Here we give high-level take-aways.
We find that $d$ represents a bias-variance trade-off. For small $d$, the variance of the estimated value $\hat \cH_{ii}$ is small and yet bias is large. For a large $d$ variance is large and yet the bias is small (the estimates are stationary around some point). Our experiments suggest using $d \in (0.32, 0.47)$.

\subsubsection{Visualization of the FPPE Distribution}
\label{sec:exp_fast_rate}
Next we look at how the FPPE distribution behaves in a simple setting.
We choose the FPPE instances as follows.
Consider a finite FPPE with $n=25$ buyers and $t = 1000$ items. Let $U_i$ be i.i.d.\ uniform random variables on $[0,1]$.
Buyers' budgets are generated by $b_i = U_i + 1$ for $i=1,\dots, 5$ and $b_i = U_i$ for $i= 6, \dots, 25$. The extra budgets are to ensure we observe $\betasti = 1$ for the first few buyers.
The valuations $\{ v_1, \cdots, v_n\}$ i.i.d. uniform, exponential, or truncated standard normal distributions.
Under each configuration we form 100 observed FPPEs, and plot the histogram of each $\sqrt{t}( \betagami - \betasti)$.
The population EG \cref{eq:pop_deg} is a constrained stochastic program and can be solved with stochastic gradient based methods. The true value $\betast$ is computed by the dual averaging algorithm \citep{xiao2010dual}. The mean square error decays as $\E[\| \beta^{\text{da}, t} - \betast\|\sq] = O (t \inv) $ with $t$ being the number of iterations, and so if we choose $t$ large enough, we should still observe asymptotic normality for the quantities $\sqrt t(\beta^{\text{da}, t} - \betagam)$.

\textit{Results.}
\begin{figure}
\centering
\includegraphics[scale=.3]{compressed-finite-sample.png}
\caption{Finite sample distributions of $\sqrt t (\betagami - \betasti)$ of 5 buyers in an FPPE.
We see that for buyer 25, its finite-sample pacing multiplier is exactly 1 for most of the time.
For buyer 21, its limit pacing multiplier is very close to 1 and so its distribution is not normal for small samples. For buyers 22 -- 24, their finite sample distribution is close to normal distributions.
The full figure is in \cref{fig:nonnormality_unif}.}
\label{fig:nonnormality_normal_compressed}
\end{figure}
\cref{fig:nonnormality_normal_compressed} shows five out of 25 distributions for pacing multipliers.
Full plots for all three distributions are given in \cref{fig:nonnormality_unif,fig:nonnormality_expo,fig:nonnormality_normal}.
We see that (i) if $\betasti < 1$ then the finite sample distribution is close to a normal distribution, and (ii) if $\betasti = 1$ (or very close to $1$, such as $\beta_{14, 21}$ in the uniform value plots, $\beta_{20, 23}$ in exponential), the finite sample distribution puts most of the probability mass at 1.
For cases where $\betasti$ is close, but not very close, to 1, we need to further increase the number of items to observe normality.

\subsection{Semi-real Experiment: Nash Social Welfare Estimation in Instagram Notification System}
\label{sec:exp_instagram}

Notifications are important in enhancing the user experience
and user engagement in mobile apps.
Nevertheless, an excessive barrage of notifications can be disruptive for users. Typically, a mobile application has various notification types, overseen by separate teams, each with potentially conflicting objectives. And so it is necessary to regulate notifications and send only those of most value to users.
\citet{instagramdata} propose to use Fisher market equilibrium-based methods to efficiently send notifications, where they treat the opportunity to send a user a notification as an item, and different types of notifications as buyers.
In this section, we use the inference method developed in \cref{sec:lfm_inference} to quantify uncertainty in equilibrium-based notification allocation methods.

\textit{The data.}
The dataset released by \citet{instagramdata}
about $400,000$ generated notifications of four types for a subset of about $60,000$ Instagram users from September 14--23, 2022.
The four types of notifications (buyers) are
daily digest of stories,
feed suite organic campaign (notification about new
posts on the user's feed),
and comments subscribed.
The value $v_i(\theta)$ of a notification type~$i$ to a user~$\theta$ at a specific time is predicted by the platform's algorithm and available in the dataset as a numerical value in $[0,1]$.
The budgets of notification types are also given.
For a user-notification type pair, we average over the whole time window and use the average to represent $v_i(\theta)$, resulting in a user-notification type matrix.
However, even after aggregation over time, there are lots of missing values, i.e., many users do not have every notification type generate a potential notification.

\textit{Value imputation and simulation by the Gaussian copula.}
We assume the values in the notification system admit the following representation.
There exists unique monotone functions $f_i:\R \to [0,1]$, such that $(v_1, \dots, v_4) = (f_1(Z_1), \dots, f_4 (Z_4))$, where $Z = [Z_1, \dots, Z_4]$ follows a multivariate Gaussian distribution with standard normal marginals. Such an assumption is equivalent to assuming the value distribution possesses a Gaussian copula (\citealt[Lemma 1]{zhao2020missing} and \citealt[Lemma 1]{liu2009nonparanormal}).
Given this representation, we propose a two-step simulation method. In the first step, we learn the monotone functions by matching the quantiles of values with the quantiles of a standard normal.
We use isotonic regression to learn the monotone functions.
Second, given the learned functions $\hat f_i$ and inverses  $\hat f_i \inv : [0,1] \to \R$, we transform $v_i$ to $\hat f_i \inv(v_i)$, and compute the covariance matrix of $\hat f_i \inv(v_i)$, denoted $\hat \Sigma$.
Even though some values are missing, the covariance $\Sigma$ can still be estimated by $\hat \Sigma$ if values are missing at random.
Now to simulate a new item for buyers,
we draw $Z \sim N(0, \hat \Sigma)$, and return $[\hat f_1 (Z_1),\dots, \hat f_4 (Z_4)] \tp $ as the value.
There are multiple advantages to this method. First, the dependence structure of the available dataset is preserved. Second, the generated values are within the range $[0,1]$ as the original data are. Third, the marginal distribution of values are also preserved in the simulated data.

As a final step to mimic realistic data, since some users may turn off notifications of certain types, the values of those notifications will be zero. We simulate this by setting certain values to zero
according to the sparsity pattern in the original dataset.
See \cref{fig:fair_noti_data} for a comparison between original dataset and simulated data.

\begin{figure}
\centering
\begin{minipage}{.45\textwidth}
\centering
\includegraphics[width=\linewidth]{fig_original_insta_data.png}
\label{fig:test1}
\end{minipage}%
\hspace{1cm}
\begin{minipage}{.45\textwidth}
\centering
\includegraphics[width=\linewidth]{fig_simulated_insta_data.png}
\label{fig:test2}
\end{minipage}
\caption{The fair notification allocation data. Left: original data with missing values. Right: simulated data.}
\label{fig:fair_noti_data}
\end{figure}

\textit{Setup and results.}
We apply the confidence interval in \cref{thm:ci_lnsw} and study the coverage properties.
The nominal coverage rate is set to 95\%.
First, we do see that even for a small sample size of 100, the nominal coverage rate is achieved. And as we increase the size of markets $t$, the coverage maintains at around 95\% and the width of the CI shrinks roughly at the rate $1/\sqrt t$.
\begin{table}
\centering
\begin{tabular}{l|r}
\toprule
items & (coverage rate, width of CI) \\
\midrule
100 & (0.94, 0.88) \\
200 & (0.95, 0.63) \\
400 & (0.93, 0.43) \\
600 & (0.97, 0.35) \\
\bottomrule
\end{tabular}
\caption{Coverage rate of log Nash social welfare in fair notification allocation. To help interpret the CI width, the log Nash social welfare in the limit market is around -16.}
\label{tbl:nsw}
\end{table}

\subsection{Semi-real Experiment: A/B Testing of Revenue in First-Price Auction Platforms}
\label{sec:exp_ipinyou}
In this section we apply our revenue estimation method to a real-world dataset, the iPinYou dataset \citep{liao2014ipinyou}.
The iPinYou dataset \citep{liao2014ipinyou} contains raw log data of the bid, impression, click, and conversion history on the iPinYou platform
in the weeks of
March 11--17,
June 8--15
and October 19--27.
We use the impression and click data of 5 advertisers on June 8, 2013, containing a total of 1.8 million impressions and 1,200 clicks.
As in the main text, let $i \in \{1,2,3,4,5\}$ index advertisers (buyers) and let $\tau$ index impressions/users (items in FPPE terminology).
The five advertiser are labeled by number and their categories are given: 1459 (Chinese e-commerce), 3358 (software), 3386 (international e-commerce) and 3476 (tire).
From the raw log data, the following dataset can be extracted.
The response variable is a binary variable $ \click_i^\tau \in \{0,1\}$ that indicates whether the user clicked the ad or not.
The relevant predictors include
a categorical variable $\AE$ of three levels that records from which ad-exchange the impression
was generated, a categorical variable $\RG$ of 35 levels indicating provinces of user IPs, and finally 44 boolean variables, each a $\TG$, indicating whether a user belongs to certain user groups  defined based on
demographic, geographic and other information.
We select the top-10 most frequent user tags and denote them by $\TG_1,\dots,\TG_{10} \in \{0,1\}$.
Both $\AE$ and $\TG$ are masked, and we do not know their real-world meaning.

\textit{Simulate advertisers with logistic regression.}
The raw data contains only five advertisers. In order to simulate new realistic advertiser, we logistic regression and then perturb the fitted coefficients to generate more advertisers.
We posit the following logistic regression model for click-through rates (CTRs).
For a user $\tau$ that saw the ad of advertiser $i$, the click process is governed by
\begin{align*}
& \CTR_i^\tau = \P(\click_i^\tau = 1 \given \thetau) =
\frac{1}{1+\exp (w_i\tp \theta^\tau)},
\\
&\theta^\tau = [1, \AE_2, \AE_3, \RG_2,\dots, \RG_{35}, \TG_1, \dots, \TG_{10}]\in \{1\} \times \{0,1\}^{46}
\end{align*}
where the weight vectors $w_i \in \R^{47}$ are the coefficients to be estimated from the data.
Note that $\AE_1$ and $\RG_1$ are absorbed in the intercept.
By running 5 logistic regressions, we obtain regression coefficients $w_1, w_2, \dots, w_5$.
To visualize the fitted regression, in \cref{fig:real} we show the estimated click-through rate distributions of the five advertisers. The diagonal plots are the histogram of CTRs, and the off-diagonal panels are the pair-wise scatter plots of CTRs.
To generate more advertisers, we take a convex combination of the coefficients $w_i$'s, add uniform noise, and obtain a new parameter, say $w'$. Given an item, the CTR of the newly generated advertisers will be $\frac{1}{1 + \exp(\theta \tp w')}$.
The value distribution is the historical distribution of the simulated advertisers' predicted CTRs of the 1.8 million impressions.

\subsubsection{Revenue Coverage}
\label{sec:exp_rev_coverage}
\textit{Setup.}
In this section we aim to produce confidence interval of the revenue with
the CI constructed from \cref{eq:rev_variance}.
Firstly, the sum equals $n$ times the average price-per-utility of advertisers, a measure of efficiency of the system. Secondly, since most quantities in FPPE, such as revenue and social welfare, are smooth functions of \pmrs, being able to perform inference about a linear combination of $\beta$'s indicates the ability to infer first-order estimates of those quantities.

An experiment has parameters $(t,n, d, \alpha)$.
Here $t \in \{ 100, 300, 500 \}$ is the number of items and $n \in \{ 10, 20, 30, 50 \}$ the number of advertisers.
Parameter $d$ is the exponent of the finite-difference stepsize $\varepsilon_t$ in \cref{eq:def:hessian_estimate}, i.e,  $\varepsilon_t= t ^{-d}$.
We try $d$ over the grid $\{ 0.4, 0.3, 0.2, 0.1, 0.05 \}$.
Finally, $\alpha \in \{0.1, 0.3, 0.5 \}$ is the proportion of advertisers that are not budget-constrained (i.e., $\beta = 1$).
To control $\alpha$ in the experiments, we select budgets as follows. Give infinite budgets to the first $\lfloor \alpha n \rfloor $ advertisers. Initialize the rest of the advertisers' budgets randomly, and keep decreasing their budgets until their \pmrs are strictly less than 1.
In the experiment $(t,n, d, \alpha)$, we first compute the \pmr in the limit market using dual averaging \citep{xiao2010dual,gao2021online,liao2022dualaveraging}.
Then we sample one FPPE by drawing values from the synthetic value distribution obtained previously.
Now given one FPPE, apply the formula in \cref{eq:rev_variance}
to construct CI and record
The reported coverage rate for an experiment with parameters $ (t,n, d, \alpha)$ is averaged over 100 FPPEs.

\textit{Results.}
Representative results are presented in \cref{tbl:rev_coverage}; we present the full table in \cref{tbl:rev_coverage_full}. As the number of item increases, we observe the empirical coverage rate achieving the nominal 90\% coverage rate, while the width of confidence interval is narrowing.
We also observe that the confidence interval is robust against the Hessian estimation and the proportion of unpaced buyers; for different choices of
exponent in the differencing stepsize ($\varepsilon_t$ in \cref{eq:def:hessian_estimate}) and proportion of unpaced buyers ($\alpha$), the coverage performance remains similar.

\begin{figure}[ht]
\centering
\includegraphics[scale = 0.6]{fig_real_value_dist.pdf}
\caption{Click-through rate (in basis points, i.e. 0.01\%) distributions from logistic regression. }
\label{fig:real}
\end{figure}

\input{tbl_rev_coverage_short.tex}
% \input{tbl_rev_coverage_with_naive.tex}

\subsubsection{Treatment Effect Coverage}
\label{sec:experiment_abtest}
\textit{Setup.}
In this experiment, we fix the differencing stepsize in Hessian estimation to be
$\varepsilon_t = t^{-0.4}$ and the proportion of unpaced buyers to be 30\%, which
is a realistic number for real-world auction platforms.

An experiment has parameters $(t,n, \pi)$, where $t$ is the number of
items, $n$ the number of users, and $\pi$ the treatment probability (see \cref{sec:ab testing}). To model treatment application, we use the shift of value distribution. Choose two sets of logistic regression parameters, $\{ w_i(0) \}_i$
and $\{w_i (1)\}$. Then if a user $\t$ is applied treatment $\omega \in \{0,1\}$, then its value to buyer $i$ will be $ 1 / (1 + \exp(w_i(\omega) \tp \theta))$, $i\in[n]$.
In an experiment,
the limit revenues in the two limit markets $\FPPE(b,v(0),s,\Theta)$ and $\FPPE(b,v(1), s,\Theta)$, and the limit treatment effect will be calculated first.
Then we perform the a/b test experiments 100 times, and construct 100 CIs for the treatment effect.
We report coverage rates and widths of CIs.

\textit{Results.} Representative results are presented in \cref{tbl:abtest}; in \cref{tbl:abtest_full} we present the full results.
First, the overall coverage rates across different market setups and treatment probabilities $\pi$ are around the nominal 90\%, and the width of confidence interval shrinks as sample size grows.
Second, when the number of items is sufficiently large (say over 400), we observe
a $U$-shape relationship between the width of CI and treatment probability $\pi$; the CI widths are wider when $\pi$ is close to the extreme points (say 0.1 and 0.9) than when $\pi$ stays away from the extreme points.
This is explained by the treatment effect variance formula in \cref{thm:clt_ab_testing}. Holding the two variances fixed, the treatment effect variance tends to infinity if we send $\pi \to 0$ or $1$.

\input{tbl_abtest_short.tex}

\section{Conclusion}

We introduced a theory of statistical inference for Fisher markets, resource allocation systems that deploy the CEEI mechanism, and first-price auction platforms.
We showed that quantities observed in the finite market equilibrium observed from these systems are good estimators of their corresponding limit market values.
We presented convergence rate results, asymptotic distribution characterizations, local minimax optimality results, and constructed confidence interval tools.
Finally, we showed how to use these tools to develop a theory of statistical inference in A/B testing under competition effects.

A few open questions remain.
In practice, the item arrival process exhibits nonstationarity and seasonality. A set of statistical theory for LFM and FPPE that incorporates temporal dependence is desirable.
It would also be desirable to design a notion of online confidence intervals for the limit market, since, in practice, items arrive on the system sequentially.
For FPPE we assumed the absence of degenerate buyers in \cref{as:scs}.
A fully general asymptotic and inferential theory for FPPE is also interesting.
Finally, we restricted our attention to the first-price setting. In practice, second-price auctions are also widespread. A theory of statistical inference for second-price auctions is also desirable, though we expect it to be significantly weaker, due to computational complexity barriers, as well as non-uniqueness issues.

\ACKNOWLEDGMENT{This research was supported by the Office of Naval Research awards N00014-22-1-2530 and N00014-23-1-2374, and the National Science Foundation awards IIS-2147361 and IIS-2238960.
This work has been presented in
Conference on Neural Information Processing Systems (2022),
International Conference on Machine Learning (2023),
Sequential Markets and Mechanism Design session in INFORMS annual meeting (2023)
Stanford Rising Star Workshop (2024),
Workshop on Marketplace Innovation (2024) for helpful discussion, and invited for presentation by the Ads Experimentation team at Meta. We thank attendees of these workshops and conferences for many helpful discussions.}

\bibliographystyle{informs2014}
\bibliography{refs.bib}
%% Here starts the e-companion (EC)
\ECSwitch

%%% Main head for the e-companion

\begin{APPENDICES}
\renewcommand{\theHsection}{A\arabic{section}}

% \crefalias{section}{appsec}
% \appendix
% \crefalias{subsection}{appsec}
\input{fisher_market_app.tex}
\input{fppe_app.tex}
\section{Experiments}

\subsection{Hessian Estimation}
\label{app:hessian_estimation}
\textit{Setup.}
We look at the following configuration of markets and the smoothing parameter $d$.
Note we will be evaluating Hessian at a prespecified point and do not need to form any market equilibria in this experiment.
We consider $n=9$ buyers. The item size $t$ ranges from 200 to 5000, at a log scale.
% Concretely, we choose $t\in$ [199,  223,  249,  279,  311,  348,  389,  434,  486,  543,  606, 678,  757,  846,  946, 1057, 1181, 1319, 1474, 1647, 1841, 2057, 2298, 2568, 2870, 3207, 3583, 4004, 4474, 5000]
Budget does not need to be specified.
Buyers' values are drawn from uniform, exponential, or truncated standard normal distributions.
The smoothing parameter $d $ is chosen from the grid [0.10, 0.17, 0.25, 0.32, 0.40, 0.47, 0.55, 0.62, 0.70].
We evaluate the Hessian $\nabla\sq H$ at a pre-specified point $\beta = [0.200, 0.333, 0.467, 0.600, 0.733, 0.867, 1.000]$, and plot the estimated diagonal values, $\hat \cH_{ii}$ for $i \in [7]$, against the number of items $t$.
Under each configuration we repeat for 10 trials.

\textit{Results.}
\cref{fig:smooth_uniform,fig:smooth_exponential,fig:smooth_normal}.
We see that $d$ represents a bias-variance trade-off. For a small $d$ (0.10, 0.17, 0.25), the variance of the estimated value $\hat \cH_{ii}$ is small and yet bias is large (since the plots seem to be trending to some point as number of item increases). For a large $d$ (0.55, 0.62, 0.70) variance is large and yet the bias is small (the estimates are stationary around some point). It is suggested to use $d \in (0.32, 0.47)$.

\begin{figure}[h!]
\center
\includegraphics[scale=.45]{exp_hessian_uniform.pdf}
\caption{Effect of smoothing parameter on numerical difference estimation of Hessian. Each curve represents the estimated value of $\cH_{ii}$. Uniform values.}
\label{fig:smooth_uniform}
\end{figure}

\begin{figure}[h!]
\center
\includegraphics[scale=.45]{exp_hessian_exponential.pdf}
\caption{Effect of smoothing parameter on numerical difference estimation of Hessian. Each curve represents the estimated value of $\cH_{ii}$. Exponential values.}
\label{fig:smooth_exponential}
\end{figure}

\begin{figure}[h!]
\center
\includegraphics[scale=.45]{exp_hessian_normal.pdf}
\caption{Effect of smoothing parameter on numerical difference estimation of Hessian. Each curve represents the estimated value of $\cH_{ii}$. Truncated normal values.}
\label{fig:smooth_normal}
\end{figure}

\subsection{Visualization of FPPE Distribution}

\begin{figure}[h!]
\center
\includegraphics[scale=.7]{exp_M_est_clt_uniform_value.pdf}
\caption{Distribution of $\sqrt t{(\betagami - \betasti)}$ for all $i \in [n]$.
Non-normality and fast convergence for buyers with $\betasti = 1$. Uniform values.}
\label{fig:nonnormality_unif}
\end{figure}

\begin{figure}[h!]
\center
\includegraphics[scale=.7]{exp_M_est_clt_exponential_value.pdf}
\caption{Distribution of $\sqrt t{(\betagami - \betasti)}$ for all $i \in [n]$.
Non-normality and fast convergence for buyers with $\betasti = 1$. Exponential values.}
\label{fig:nonnormality_expo}
\end{figure}

\begin{figure}[h!]
\center
\includegraphics[scale=.7]{exp_M_est_clt_normal_value.pdf}
\caption{
Distribution of $\sqrt t({\betagami - \betasti})$ for all $i \in [n]$.
Non-normality and fast convergence for buyers with $\betasti = 1$. Truncated normal values.}
\label{fig:nonnormality_normal}
\end{figure}

\subsection{Full Version of \cref{tbl:abtest}}
\input{tbl_abtest.tex}

\subsection{Full Version of \cref{tbl:rev_coverage}}
\input{tbl_rev_coverage.tex}
\end{APPENDICES}
% Appendix here
% Options are (1) APPENDIX (with or without general title) or
%             (2) APPENDICES (if it has more than one unrelated sections)
% Outcomment the appropriate case if necessary
% \begin{APPENDIX}{<Title of the Appendix>}
% \end{APPENDIX}
%   or
% \begin{APPENDICES}
% \section{<Title of Section A>}
% \section{<Title of Section B>}
% etc
% \end{APPENDICES}

% Acknowledgments here

% References here (outcomment the appropriate case)
% CASE 1: BiBTeX used to constantly update the references
%   (while the paper is being written).
% outcomment this and next line in Case 1
% \bibliography{refs.bib} % if more than one, comma separated

% CASE 2: BiBTeX used to generate mypaper.bbl (to be further fine tuned)
%\input{mypaper.bbl} % outcomment this line in Case 2

%If you don't use BiBTex, you can manually itemize references as shown below.
\end{document}