# Interference Among First-Price Pacing Equilibria: A Bias and Variance
Analysis

Luofeng Liao, Columbia University
Christian Kroer, Columbia University
Sergei Leonenkov, Ads Online Experimentation, Meta
Okke Schrijvers, Central Applied Science, Meta
Liang Shi, Central Applied Science, Meta
Nicolas Stier-Moses, Central Applied Science, Meta
Congshan Zhang, Central Applied Science, Meta

###### Abstract.

Online A/B testing is widely used in the internet industry to inform decisions
on new feature roll-outs. For online marketplaces (such as advertising
markets), standard approaches to A/B testing may lead to biased results when
buyers operate under a budget constraint, as budget consumption in one arm of
the experiment impacts performance of the other arm. To counteract this
interference, one can use a budget-split design where the budget constraint
operates on a per-arm basis and each arm receives an equal fraction of the
budget, leading to “budget-controlled A/B testing.” Despite clear advantages
of budget-controlled A/B testing, performance degrades when budget are split
too small, limiting the overall throughput of such systems. In this paper, we
propose a _parallel budget-controlled A/B testing_ design where we use market
segmentation to identify submarkets in the larger market, and we run parallel
experiments on each submarket.

Our contributions are as follows: First, we introduce and demonstrate the
effectiveness of the parallel budget-controlled A/B test design with
submarkets in a large online marketplace environment. Second, we formally
define market interference in first-price auction markets leveraging the first
price pacing equilibrium (FPPE) framework which has been proposed to model
autobidding in repeated auctions. Third, we propose a debiased surrogate that
eliminates the first-order bias of FPPE, drawing upon the principles of
sensitivity analysis in mathematical programs. Fourth, we derive a plug-in
estimator for the surrogate and establish its asymptotic normality. Fifth, we
provide an estimation procedure for submarket parallel budget-controlled A/B
tests. Finally, we present numerical examples on semi-synthetic data,
confirming that the debiasing technique achieves the desired coverage
properties.

††conference: ; ;

##  1\. Introduction

Online A/B testing, or _experimentation_ , is widely used in the internet
industry. Major tech companies conduct a large number of A/B tests annually to
inform decisions related to ads delivery, online auction mechanisms, user
interface components, new feature rollouts, infrastructure improvements, and
many other aspects of their products and services.

In the context of online auctions in marketplaces, where buyers bid for
sellers’ items or advertisers bid for users’ impressions, budget-controlled
A/B testing has gained popularity and is supported by companies like LinkedIn,
Google, and Meta (Basse et al., 2016; Liu et al., 2021). The primary advantage
of budget control in A/B testing is that it eliminates interference between
the A and B groups that could otherwise bias the results: In a traditional A/B
test, the budget of a buyer is distributed across all auctions, involving
users from both A and B groups. This couples the behavior of the buyer across
the groups; for example, increased expenditure under B might decrease
expenditure in A, causing interference. However, in a budget-controlled A/B
test, each buyer spends half of their budget on users from the A group and the
other half on users from the B group, creating two separate but mirrored
markets, and thus removing the interference caused by a shared budget
constraint. This experiment type, therefore, is commonly used to test various
ads delivery changes, such as pacing algorithms (see Section 2.1).

Despite clear advantages of budget-controlled A/B testing, companies are
extremely constrained by the number of such experiments they can run: buyers
(advertisers) can only be charged once for the same item (impression), it is
thus not feasible to create additional experimentation throughput by
reshuffling users between the A and B groups. An alternative idea is to create
more budget splits so more treatments can be tested at the same time. However,
this will lower the budget-per-group substantially, which could lead to
different equilibrium outcomes and may disproportionately affect smaller
buyers. In addition, it poses challenges with respect to statistical power, in
view of the fact that tech companies primarily focus on down-funnel conversion
events which are difficult to measure effects on to begin with. In fact, the
lack of bandwidth for budget-controlled A/B tests has become one of the major
bottlenecks in experimentation for the internet industry.

A third approach to increase throughput is market segmentation. If the overall
market can be divided into several relatively isolated submarkets, budget-
controlled A/B tests can be conducted in parallel within these submarkets.
However, this method also presents some challenges. First, submarkets are
rarely completely isolated; certain items may attract buyers from multiple
submarkets, resulting in interference across submarkets when conducting tests
in parallel. Second, submarkets differ in terms of buyer (and user)
compositions, which might cause the local treatment effect estimates being not
representative of the global treatment effect where all buyers are included in
the market. The second challenge is relatively easy to address in practice by
imposing balancing constraints in the clustering algorithm used to define
submarkets, while the first challenge is more fundamentally important and
requires deeper theoretical understanding.

As a motivating example, Fig 1(a) compares the results of submarket budget-
controlled A/B tests (vertical axis) with those obtained from running budget-
controlled A/B tests on the entire market (horizontal axis). The figure
reports a normalized version of one of the real experiment metrics at Meta,
with each submarket covering approximately 6-8% of advertisers and each
experiment condition covering 30% of users. All submarkets are carefully
created with limited imbalances in advertiser composition. We consider 16
different treatments, most of which are related to the pacing algorithm, each
run for about 6 days, resulting in a total of 99 daily comparisons. The
benchmark for sign-consistency at a 90% significance level (for neutral true
effects) is 81.5%. The observed sign consistency rate between submarket and
standard budget-controlled experiments is only slightly lower, at around 75%.
Our focus on sign consistency in this context is intentional, as it directly
relates to the frequency of production decision reversals, which we aim to
minimize as much as possible.

(a) All datapoints.

(b) After guardrail metric thresholding. Note the different axis scale.

Figure 1. Submarket vs. standard budget-controlled A/B test, daily treatment
effect. We denote neutral treatment effects with a value of $1.0$. For
example, $1.01$ can be interpreted as $1\%$ treatment effect. Red crosses
indicate instances of sign inconsistencies.

Table 1 shows the sign consistency rate of comparisons for daily and 6-day
aggregated results, including for a second metric. Since submarkets are not
perfectly isolated, we use a guardrail metric to measure the interference
between submarkets, and use a threshold on the guardrail metric to improve
reliability. As seen in Table 1, by eliminating experiments where the
guardrail metric violates the threshold, we meaningfully improve the
consistency rate for both metrics in daily and 6-day results. In practice,
approximately 10% of submarket experiments violate the guardrail threshold.
Fig 1(b) demonstrates the treatment effect comparisons for daily results after
we remove such data points. The results are generally satisfactory, however
the existence of biases is evident even after removing data points that
violated the guardrail threshold. Evidently, quantitatively understanding the
interference bias to improve the accuracy of the estimates is conducive to
better decisions, and that is what we set to do in this work.

Table 1. Sign consistency between submarket and standard budget-controlled A/B test Duration | Data | Num | Sign consistency (%)
---|---|---|---
Metric 1 | Metric 2
6 days | All combos | 16 | 87.5 | 68.8
6 days | within guardrail | 14 | 100 | 78.6
1 day | All combos | 99 | 75.8 | 73.7
1 day | within guardrail | 84 | 81.0 | 76.2

The contributions of this paper are as follows. First, we introduce and
demonstrate the effectiveness of the parallel budget-controlled A/B test
design with submarkets in Meta’s production environment, which, to our best
knowledge, is a novel approach. Second, we formally define market interference
in first-price auction markets using the First Price Pacing Equilibrium (FPPE)
framework (Conitzer et al., 2022a). Third, we propose a debiased surrogate
that eliminates the first-order bias of FPPE, drawing upon the principles of
sensitivity analysis in mathematical programs (Shapiro et al., 2021). Fourth,
we derive a plug-in estimator for the surrogate and establish its asymptotic
normality. Fifth, we provide an estimation procedure for submarket parallel
budget-controlled A/B tests. Finally, we present numerical examples on semi-
synthetic data, confirming that the debiasing technique achieves the desired
coverage properties.

Section 2 introduces the FPPE framework. The formal problem setup is given in
Section 3. Asymptotic theories around FPPE are presented in Section 4. Section
5 formalizes the parallel A/B testing problem under interference and provides
the estimation procedure. Numerical examples on synthetic and semi-synthetic
data are presented in Section 6. We conclude in Section 7.

###  1.1. Parallel A/B Testing in Practice

In this section we describe the real-world problem of A/B testing with
congestion that we wish to model, and our proposed solution of parallel A/B
tests in carefully balanced submarkets; the formal model appears in Sec. 2 and
Sec. 3. Along with the description of the real-world problem, we will also
discuss which aspects of it will be or will not be captured by our theoretical
model.

We start by describing the market environment. Assume that there is a set of
$n$ advertisers, and each advertiser $i$ has a budget $b_{i}$. Whenever a user
shows up on the platform an _impression opportunity_ occurs, and an auction is
conducted in order to determine which subset of ads will be shown to the user.
Each advertiser $i$ has some stated value $v_{i}(\theta)$ of being shown to a
particular impression opportunity $\theta$. This may not be their true
valuation; in practice it may be their stated willingness to pay for a click,
multiplied by an estimated click-through-rate for the pair ($i$,$\theta$). The
advertiser submits a bid which is determined based on $v_{i}(\theta)$, as well
as the expenditure of the advertiser so far. For example, in _multiplicative
pacing_ (Balseiro et al., 2017; Conitzer et al., 2022b, a), the platform
adaptively learns a _pacing multiplier_ $\beta_{i}\in[0,1]$ such that the bid
is formed as $\beta_{i}v_{i}(\theta)$. The budget-management system then
adaptively controls $\beta_{i}$ over time, in order to ensure the correct rate
of budget expenditure on behalf of the advertiser. The auction format for an
impression opportunity is typically some generalization of the first or
second-price auction, though the real-world auctions are not fully captured by
any simple-to-describe auction model from the literature. For example, in the
setting of inserting ads into a news feed, multiple ads may be allowed to be
shown, but the exact number may depend on the size of each ad, the size of
other content in the feed, and so forth.

In our theoretical model, we will simplify the auction format in three
respects: first, we will assume that each impression opportunity allows
exactly one ad to be shown. This is a common assumption in the literature
studying both online learning for budget management (Borgs et al., 2007;
Balseiro and Gur, 2019) as well as in the literature on equilibrium outcomes
under budget management (Balseiro et al., 2017; Conitzer et al., 2022b, a;
Aggarwal et al., 2019; Balseiro et al., 2023). Thirdly, we assume that each
individual auction is a _first-price auction_ , meaning that the highest
bidder wins, and pays their bid. Internet advertising uses both first and
second-price auctions, depending on the particular context (Balseiro et al.,
2023; Goke et al., 2021), though generalizations of the second-price auction
are arguably still more common, in particular for sponsored search and feed
auctions. We focus on first-price auctions because the equilibrium outcomes
under budget management satisfy two crucial properties from the perspective of
statistical inference: they are unique, and the equilibrium is captured by a
convex program (Conitzer et al., 2022a). In contrast, equilibria under budget
management in second-price auctions may not be unique (Conitzer et al.,
2022b), and they are PPAD-hard to compute (Chen et al., 2023). It is an
interesting future research direction to figure out how to develop results for
the second-price setting, though we expect it to be much harder. We will also
abstract away the dynamic temporal aspects of budget management: instead of
the pacing multipliers being learned over time, we will assume that what we
observe is the set of pacing multipliers in equilibrium. Secondly, in the real
world, advertisers may use a variety of budget management algorithms beyond
multiplicative pacing. For example, Google also offers _probabilistic
throttling_ , where bids are not modified, and instead the expenditure is
managed by independently flipping a coin for each auction, in order to
determine whether to bid at all (Balseiro et al., 2017; Chen et al., 2021;
Karande et al., 2013). We assume that every advertiser uses multiplicative
pacing in order to manage budgets. Budget-management equilibria in first-price
auctions with probabilistic throttling are known to also be unique and
computable (Chen et al., 2021), so it is possible that similar results could
be obtained for that setting, though it is not known whether those equilibria
are captured by a convex mathematical program, which is a crucial fact for our
technical approach.

Now that we have discussed budget management, we describe the A/B testing
problem. Suppose that a platform wants to run $K$ A/B tests, which may affect,
e.g., the valuations that advertisers have for impression slots, revenue, etc.
Naively performing the A/B test on a per-impression or per-user basis and then
simply running the market as usual will not work, because the budget
management system means that the A and B users will be affected by each other
through the budget coupling. As mentioned in the introduction, a possible
option is to perform budget splitting: create $K+1$ copies of each advertiser
(corresponding to each test, as well as a holdout “A” control copy), randomize
users into one of the $K+1$ markets, and run separate budget management for
each copy of the $K+1$ advertisers. As mentioned earlier, this approach runs
into problems because small advertisers end up with prohibitively-small
budgets, and there is a large negative impact on statistical power because
some of the events measured by the A/B tests might be far downstream of an
impression.

Instead, our paper considers the following parallel A/B test paradigm based on
market segmentation. We first define a bipartite graph between advertisers and
users based on targeting criteria. Subsequently, we cluster the advertisers
into $K$ clusters, where the objective is to minimize the sum of weighted
edges between clusters subject to traffic balancing constraints to make the
resulting clusters as similar to the whole market as possible. The edge weight
between a pair of advertisers is the number of impressions (or users) where
they are both within the top-$k$ bids. The choice of $k$ is a parameter that
must be chosen based on experience with the specific application setting. If
the clustering achieves a small objective function value, then each cluster is
a mostly isolated submarket, in the sense that each user will mostly receive
bids from advertisers in a single cluster. Then, we run an A/B test within
each of the $K$ submarkets. Every user is randomly assigned to either “A” or
“B” in each submarket. Note that the same user can be in “A” in submarket 1
and “B” in submarket 2. This means that all the A/B tests must be mutually
compatible; in practice this means that our approach is best suited for A/B
tests that apply to advertisers, as opposed to, e.g., user-side user interface
changes. If the interaction between different submarkets is not too strong,
then we expect that hypothesis testing in a submarket is indicative of the
true treatment effect within that submarket. Secondly, if each submarket is
representative of the overall market, then such a hypothesis test is also
indicative of the true treatment effect across the whole market.

In our theoretical model we use a coarser notion of contamination between a
pair of submarkets than the top-$k$ measure that we use in practice. In our
theoretical model, we measure the number of items with _any_ bids from buyers
from separate submarkets. In practice, this measure is too coarse (and often
very large). It is an interesting follow-up question to come up with stronger
theoretical results that allow for finer-grained measures of contamination.
Secondly, our theoretical model will assume that what we are interested in is
the treatment effect within a submarket. This implicitly assumes that each
submarket is representative of the overall market.

##  2\. Theory overview

###  2.1. Related Work

Pacing equilibrium. Pacing is a budget management strategy where bids are
scaled down by a multiplicative factor in order to smooth out and control
spending. In the first-price setting, Borgs et al. (2007) study first price
auctions with budget constraints in a perturbed model, where the limit prices
converge to those of an FPPE. Building on that work, Conitzer et al. (2022a)
introduce the FPPE framework to model autobidding in repeated auctions, and
discover several properties of FPPE such as shill-proofness monotonicity
properties, and a close relationship between FPPE and the quasilinear Fisher
market equilibrium (Chen et al., 2007; Cole et al., 2017). Gao and Kroer
(2022) propose an infinite-dimensional variant of the quasilinear Fisher
market, which lays the probability foundations of the current paper. Gao et
al. (2021) and Liao et al. (2022) study online computation of the infinite-
dimensional Fisher market equilibrium, and we utilize their methods to compute
equilibria. In the second-price setting, a variety of models have been
proposed for modeling the outcome of budget management: Balseiro et al. (2015)
study budget-management in second-price auctions through a fluid mean-field
approximation; Balseiro and Gur (2019) investigate adaptive pacing strategy
from buyers’ perspective in a stochastic continuous setting; and Balseiro et
al. (2021b) study several budget smoothing methods including multiplicative
pacing in a stochastic context. A second-price analogue of FPPE was explored
by Conitzer et al. (2022b). Modeling statistical inference in the second-price
setting is most likely harder, due to equilibrium multiplicity issues
(Conitzer et al., 2022b), and hardness of even computing equilibria (Chen et
al., 2023).

Recently, a series of papers (e.g., Aggarwal et al. (2019); Deng et al.
(2021); Balseiro et al. (2021a)) investigated an “autobidding” model for
value-maximizing bidders, who aim to maximize their value subject to budget or
return-on-spend constraints, which may include buying individual ad
impressions that have negative utility. Several extensions provide results for
more general settings, such as the quality of equilibria for generalized
rationality models for bidders (Babaioff et al., 2021), non-uniform bidding
strategies (Deng et al., 2023), and liquid welfare guarantees when budget-
constrained buyers fail to reach equilibrium (Gaitonde et al., 2023).
Statistical inference for parallel A/B testing under such models represent an
interesting future direction of work.

Interference in A/B Testing for Auction Markets. Experimentation under
interference has been extensively studied in the past decade within the
context of social networks (Ugander et al., 2013; Aronow and Samii, 2017;
Eckles et al., 2017; Athey et al., 2018; Li and Wager, 2022) and two-sided
marketplaces (Zigler and Papadogeorgou, 2018; Wager and Xu, 2021). Under
interference, the outcome of an experiment unit, either a user in a social
network or a buyer in an online marketplace, can be affected by the treatment
status of other units in the networks, violating the Stable Unit Treatment
Values Assumption (SUTVA) assumption commonly employed in analyzing online A/B
tests (Rosenbaum, 2007). To take into account this type of interference, novel
designs and analysis approaches have been proposed, e.g., cluster
randomization (Ugander et al., 2013; Karrer et al., 2021), regression-based
estimators (Chin, 2019), and bipartite analysis (Harshaw et al., 2021). A/B
testing in the presence of seller-side budget constraints has been discussed
by Basse et al. (2016) and Liu et al. (2021) where the budget-splitting design
spans the full market. However, most of the above works do not consider the
particular type of interference caused by competitive equilibrium effects.
Recent work has also addressed equilibrium effects (Wager and Xu, 2021; Liao
et al., 2023; Liao and Kroer, 2024). Most relevant to our results, Liao and
Kroer (2023) consider A/B testing via budget splitting in Fisher markets and
FPPE. However, none of these works consider the effects caused by parallel A/B
tests that interfere with each other. Our method builds on top of the budget-
splitting design; our approach additionally segments the full market into
submarkets, where different submarkets receive different treatment. In the
formal sections of our paper we assume that the submarket structure is known.
In practice, the submarkets may not be known; Rolnick et al. (2019) and
Viviano et al. (2023) present methods to identify submarkets through
clustering approaches that aim to limit the interference between clusters.

###  2.2. Review of FPPE

Notation. For a measurable space $(\Theta,\mathop{}\\!\mathrm{d}\theta)$, we
let $L^{p}$ (and $L^{p}_{+}$, resp.) denote the set of (nonnegative, resp.)
$L^{p}$ functions on $\Theta$ w.r.t the base measure
$\mathop{}\\!\mathrm{d}\theta$ for any $p\in[1,\infty]$ (including
$p=\infty$). Given $x\in L^{\infty}$ and $v\in L^{1}$, we let $\langle
v,x\rangle=\int_{\Theta}v(\theta)x(\theta)\mathop{}\\!\mathrm{d}\theta$. 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 ${\mathbb{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. For a subset $\Theta^{\prime}\subset\Theta$, let
$1_{\Theta^{\prime}}({\cdot}):\Theta\to\\{0,1\\}$ be the indicator function of
$\Theta^{\prime}$. Convergence in distribution and probability is denoted by
${\,\overset{{d}}{\to}\,}$ and ${\,\overset{{p}}{\to}\,}$.

Given a vector $a=[a_{1},\dots,a_{n}]^{\scriptscriptstyle\mathsf{T}}$, let
${\operatorname*{Diag}}(a)$ denote the diagonal matrix with $(i,i)$-th entry
being $a_{i}$; sometimes we write ${\operatorname*{Diag}}(a_{i})$ when it is
convenient to define each $a_{i}$ inline. Let $A^{\dagger}$ denote the
Moore–Penrose inverse of the matrix $A$, $e_{j}$ the $j$-th unit vector, and
$[n]=\\{1,\ldots,n\\}$.

Figure 2. Finite FPPE (left) and limit FPPE (right). In a finite FPPE, there
are a finite number of items. In a limit FPPE, the item set is a continuum.

####  2.2.1. Basic Definitions, Limit FPPE and Regularity Conditions

We introduce the definitions of limit FPPE and two regularity conditions on
the market. We have $n$ buyers and a possibly continuous set of items $\Theta$
with an integrating measure $\mathop{}\\!\mathrm{d}\theta$. For example, one
could take $\Theta=[0,1]$ and $\mathop{}\\!\mathrm{d}\theta=$ the Lebesgue
measure on $[0,1]$. An FPPE requires the following elements.

  * •

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}_{+}$, i.e., buyer
$i$ has valuation $v_{i}(\theta)$ (value per unit supply) of item
$\theta\in\Theta$. Let $v:\Theta\to{\mathbb{R}^{n}}$,
$v(\theta)=[v_{1}(\theta),\dots,v_{n}(\theta)]$. We assume
${\bar{v}}=\max_{i}\sup_{\theta}v_{i}(\theta)<\infty$.

  * •

The _supplies_ of items are given by a function $s\in L^{\infty}_{+}$, i.e.,
item $\theta\in\Theta$ has $s(\theta)$ unit of supply. Without loss of
generality, we assume a unit total supply
$\int_{\Theta}s\mathop{}\\!\mathrm{d}\theta=1$. Given
$g:\Theta\to{\mathbb{R}}$, we let ${\mathbb{E}}[g]=\int
g(\theta)s(\theta)\mathop{}\\!\mathrm{d}\theta$ and
${\operatorname{Var}}[g]={\mathbb{E}}[g^{2}]-({\mathbb{E}}[g])^{2}$. Given $t$
i.i.d. draws $\\{\theta^{1},\dots,\theta^{t}\\}$ from $s$, let
$P_{t}g({\cdot})=\frac{1}{t}{\sum_{\tau=1}^{t}}g({\theta^{\tau}})$.

Next we introduce the market equilibrium concepts that are the foundation of
our study. For that we leverage the _first-price pacing equilibrium_ (FPPE)
concept put forward by Conitzer et al. (2022a). FPPE models equilibrium
outcomes under budget-management systems employed in several practical
settings. Each buyer is assigned a _pacing multiplier_ $\beta_{i}$, which is
used to control their budget expenditure. For each individual auction
$\theta$, the buyer bids $\beta_{i}v_{i}(\theta)$, which can be seen as their
adjusted valuation after factoring in their budget constraint (in practice,
the valuation $v_{i}(\theta)$ may not be the buyer’s true valuation, but
instead their unscaled bid reported to the platform). The goal of the budget
management system is to achieve an equilibrium, meaning that it must ensure
that buyers spend their budget exactly by appropriately choosing $\beta_{i}$.
If the budget cannot be fully spent, then no pacing must occur (i.e.,
$\beta_{i}=1$).

We now formally define the pacing equilibrium concepts in the case of infinite
(below) and finite number of users (in the next section), as illustrated by
Fig 2.

###### Definition 1 (Limit FPPE, Gao and Kroer (2022); Conitzer et al.
(2022a)).

A limit FPPE, denoted as ${\small\mathsf{{FPPE}}}(b,v,s,\Theta)$, is the
unique tuple $(\beta,p({\cdot}))\in[0,1]^{n}\times L^{1}_{+}(\Theta)$ such
that there exist $x_{i}:\Theta\to[0,1]$ for all $i\in[n]$,

  1. (1)

(First-price) Prices are determined by first price auctions: for all item
$\theta\in\Theta$, $p(\theta)=\max_{i}{\beta_{i}}v_{i}(\theta)$. Only highest
bidders obtain items: for all $i$ and $\theta$, $x_{i}(\theta)>0$ implies
${\beta_{i}}{v_{i}(\theta)}=\max_{k}\beta_{k}v_{k}(\theta)$

  2. (2)

(Feasiblity, market clearing) Buyers are budget constrained: for all $i$,
$\int x_{i}(\theta)p(\theta)s(\theta)\mathop{}\\!\mathrm{d}\theta\leq b_{i}$.
There is no overselling: for all $\theta$, ${\sum_{i=1}^{n}}x_{i}(\theta)\leq
1$. All items are for which there is competition are fully allocated: for all
$\theta$, $p(\theta)>0$ implies ${\sum_{i=1}^{n}}x_{i}(\theta)=1$.

  3. (3)

(No unnecessary pacing) For all $i$, $\int
x_{i}(\theta)p(\theta)s(\theta)\mathop{}\\!\mathrm{d}\theta<b_{i}$ implies
${\beta_{i}}=1$.

Let $\beta^{*}$ and $p^{*}$ be the equilibrium pacing multipliers and prices.
Revenue in the limit FPPE is ${\mathsf{{REV}}}^{*}=\int
p^{*}(\theta)s(\theta)\mathop{}\\!\mathrm{d}\theta\;.$ It measures the
profitability of the auction platform. The leftover budgets for buyers are
${\delta^{*}_{i}}=b_{i}-\int
p^{*}(\theta)s(\theta){x^{*}_{i}}(\theta)\mathop{}\\!\mathrm{d}\theta$.

The first two conditions simply describe the possible outcomes of an auction
system that uses pacing as the budget management strategy. The last condition,
no unnecessary pacing, ensures that we only scale down a buyer’s bids in case
their budget constraint is binding. FPPE has many nice properties, including
that they are competitive equilibria and that they are revenue-maximizing
among budget-feasible pacing multipliers (Conitzer et al., 2022a).

In a pacing auction market
${\mathscr{M}}={\small\mathsf{{FPPE}}}(b,v,s,\Theta)$ the following two
regularity conditions are important for the study of its statistical
properties.

###### Definition 2 (SMO).

We say the smoothness condition holds if the map
$\beta\mapsto{\mathbb{E}}_{s}[\max_{i}{\beta_{i}}{v_{i}(\theta)}]$ is twice
continuously differentiable in a neighborhood of $\beta^{*}$.

###### Definition 3 (SCS).

We say strict complementary slackness holds if, whenever a buyer is unpaced
(${\beta^{*}_{i}}=1$), then her leftover budget is strictly positive
($\delta^{*}_{i}>0$).

The condition Definition 2 (SMO). ensures that in the limit market, items that
incur a tie are measure zero. The condition Definition 3 (SCS). rules out
degenerate buyers that spend their budget exactly at $\beta_{i}^{*}$. See Liao
and Kroer (2023) and Liao et al. (2023) for an extensive discussion about
these conditions.

####  2.2.2. Finite FPPE

Next we introduce finite FPPE, which models the auction data we observe in
practice. Let $\gamma=(\theta^{1},\dots,\theta^{t})$ be a sequence of items.
Assume each item has the same supply of $\sigma\in{\mathbb{R}_{+}}$ units. A
finite FPPE is a limit FPPE where the supply is a discrete measure supported
on the observed items $\gamma$. Let ${v_{i}^{\tau}}={v_{i}(\theta^{\tau})}$.

###### Definition 4 (Finite FPPE, Conitzer et al. (2022a)).

Given $(b,v,\sigma,\gamma)$, the observed FPPE,
${\small\widehat{\textsf{{FPPE}}}}(b,v,\sigma,\gamma)$, is the unique tuple
$(\beta,p)\in[0,1]^{n}\times{\mathbb{R}}^{t}_{+}$ such that there exist
$x_{i}^{\tau}\in[0,1]$:

  * •

(First-price) For all $\tau$, ${p^{\tau}}=\max_{i}{\beta_{i}}{v_{i}^{\tau}}$.
For all $i$ and $\tau$, ${x_{i}^{\tau}}>0$ implies
${\beta_{i}}{v_{i}^{\tau}}=\max_{k}\beta_{k}v_{k}^{\tau}$.

  * •

(Supply and budget feasible) For all $i$,
$\sigma{\sum_{\tau=1}^{t}}{x_{i}^{\tau}}{p^{\tau}}\leq b_{i}$. For all $\tau$,
${\sum_{i=1}^{n}}{x_{i}^{\tau}}\leq 1$. (Market clearing) For all $\tau$,
${p^{\tau}}>0$ implies ${\sum_{i=1}^{n}}{x_{i}^{\tau}}=1$.

  * •

(No unnecessary pacing) For all $i$,
$\sigma{\sum_{\tau=1}^{t}}{x_{i}^{\tau}}{p^{\tau}}<b_{i}$ implies
${\beta_{i}}=1$.

In Liao and Kroer (2023), it is shown that if $\gamma$ consists of $t$ i.i.d.
draws from distribution $s$, and one takes $\sigma=1/t$, then the pacing
multiplier in ${\small\widehat{\textsf{{FPPE}}}}(b,v,1/t,\gamma)$ converges to
the pacing multiplier in ${\small\mathsf{{FPPE}}}(b,v,s,\Theta)$ in
probability. Also note that the
${\small\widehat{\textsf{{FPPE}}}}(tb,v,1,\gamma)$ converges to the same limit
FPPE ${\small\mathsf{{FPPE}}}(b,v,s,\Theta)$ because the pacing multiplier of
a finite FPPE does not change when budgets and supplies are multiplied by the
same scalar.

####  2.2.3. The Eisenberg-Gale Program

Both the limit FPPE and the finite FPPE have convex program characterizations
(Chen et al., 2007; Conitzer et al., 2022a; Gao and Kroer, 2022). We define
the dual Eisenberg-Gale (EG) objective for a single item $\theta$ as

(1) $\displaystyle
F(\theta,\beta)=f(\beta,\theta)-{\sum_{i=1}^{n}}b_{i}\log\beta_{i}\;,\quad
f(\beta,\theta)=\max_{i\in[n]}\beta_{i}v_{i}(\theta)\;.$

The population and sample (dual) EG objectives are then defined as

(2) $\displaystyle H(\beta)={\mathbb{E}}[F(\theta,\beta)]\;,\quad
H_{t}(\beta)=\frac{1}{t}{\sum_{\tau=1}^{t}}F({\theta^{\tau}},\beta)\;.$

We say ${\mathscr{H}}$ is the Hessian of market ${\mathscr{M}}$ when
${\mathscr{H}}=\nabla^{2}\int
F(\theta,\beta)s\mathop{}\\!\mathrm{d}\theta|_{\beta=\beta^{*}}$.

The equilibrium pacing multipliers $\beta^{*}$ in
${\small\mathsf{{FPPE}}}(b,v,s,\Theta)$ can be recovered through the
population dual EG program

(3)
$\displaystyle\beta^{*}=\operatorname*{arg\,min}_{\beta\in(0,1]^{n}}H(\beta)\;.$

The pacing multiplier $\beta^{*}$ is the unique solution to Eq. 3. Let
$\beta^{\gamma}$ be the equilibrium pacing multiplier in
${\small\widehat{\textsf{{FPPE}}}}(b,v,1/t,\gamma)$. Then $\beta^{\gamma}$
solves the sample analogue of Eq. 3:

(4)
$\displaystyle\beta^{\gamma}=\operatorname*{arg\,min}_{\beta\in(0,1]^{n}}H_{t}(\beta)\;.$

Let us briefly comment on the differential structure of $f$, since it plays a
role in later sections. The function $f(\beta,\theta)$ is a convex function of
$\beta$ and its subdifferential $\partial_{\beta}f(\beta,\theta)$ is the
convex hull of $\\{v_{i}e_{i}:\text{index $i$ such that
${\beta_{i}}{v_{i}(\theta)}=\max_{k}{\beta_{k}}v_{k}(\theta)$}\\}$, with
$e_{i}$ being the base vector in ${\mathbb{R}^{n}}$. When
$\max_{i}{\beta_{i}}v_{i}(\theta)$ is attained by a unique $i^{*}$, the
function $f(\cdot,\theta)$ is differentiable. In that case, all entries of
$\nabla_{\beta}f(\beta,\theta)$ are zero expect that the $i^{*}$-th entry is
filled with the value $v_{i^{*}}(\theta)$.

##  3\. Setup: Interference as Contamination

In this section, we discuss how to estimate market equilibria when there is
contamination in the supply. Then, we show that interference from other
markets can be viewed as a form of contamination, and so the problem of
removing interference bias can be analyzed via our contamination framework.

###  3.1. Contaminated First-Price Pacing Equilibrium

We assume that we are in the same FPPE setting as before: there are $n$
buyers, each with budget $b_{i}$, and an item set $\Theta$. However, now we
assume that $\Theta$ is partitioned into $\Theta_{\mathsf{good}}$ and
$\Theta_{\mathsf{bad}}$. Let $s$ be supported on $\Theta_{\mathsf{good}}$ and
$s^{\prime}$ on $\Theta_{\mathsf{bad}}$. We define the $\alpha$-contaminated
market and the uncontaminated market by

$\displaystyle{\mathscr{M}}_{\alpha}={\small\mathsf{{FPPE}}}(b,v,s_{\alpha},\Theta)\;,\quad{\mathscr{M}}_{0}={\small\mathsf{{FPPE}}}(b,v,s,\Theta)\;,$

where $s_{\alpha}=\alpha s^{\prime}+(1-\alpha)s$. Our goal is to perform
inference about FPPE properties in the limit FPPE with the item set
$\Theta_{\mathsf{good}}$ and supply $s$. However, we are given access to
finite FPPEs sampled from $s_{\alpha}$ instead. In particular, let $\gamma$ be
$t$ i.i.d. draws from $s_{\alpha}$ and let

$\displaystyle\widehat{\mathscr{M}}_{\alpha}={\small\widehat{\textsf{{FPPE}}}}(b,v,1/t,\gamma)\;.$

We assume knowledge of $\alpha$ throughout the paper. In practice, this can
often be estimated from historical data; in the parallel A/B test setting,
this can be estimated directly from the sampled set of items, since we know
which items are good and bad in that setting. Let $\beta^{*}$ and
$\beta^{*}_{\alpha}$ be the limit pacing multipliers in ${\mathscr{M}}_{0}$
and ${\mathscr{M}}_{\alpha}$, respectively. Let $\beta^{\gamma}_{\alpha}$ be
the pacing multipliers in the sampled market $\widehat{\mathscr{M}}_{\alpha}$
and let
$H_{\alpha,t}(\beta)=\frac{1}{t}{\sum_{\tau=1}^{t}}F({\theta^{\tau}},\beta)$
be the sample EG objective.

Now, if we wanted to make inferences about ${\mathscr{M}}_{\alpha}$ then we
could use existing statistical inference theory on how to use data in a finite
FPPE $\widehat{\mathscr{M}}_{\alpha}$ to make inferences about the limit FPPE
${\mathscr{M}}_{\alpha}$. In recent work of Liao and Kroer (2023), it is shown
that for an _influence function_ $D_{\alpha}:\Theta\to{\mathbb{R}}$ (to be
defined in Thm. 3), the asymptotic distribution of $\beta_{\alpha}^{\gamma}$
around $\beta_{\alpha}^{*}$ satisfies

$\displaystyle\sqrt{t}(\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha})=\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}(D_{\alpha}({\theta^{\tau}})-{\mathbb{E}}_{\alpha}[D_{\alpha}(\theta)])+o_{p}(1)\;,$

where $\\{{\theta^{\tau}}\\}$ is the set of items sampled in $\gamma$. Our
central research question can now be formulated as follows:

_How can we use the data in the finite contaminated market
$\widehat{\mathscr{M}}_{\alpha}$ to make inferences about the uncontaminated
limit market ${\mathscr{M}}_{0}$?_

###  3.2. Interference as Contamination

Now we show how the contamination model from the previous section can be used
to model interference. Consider $K$ separated auction markets, which together
form a global market. In the global market there are $n$ buyers, each with
budget $b_{i}$, and an item set $\Theta$, partitioned into
$\Theta_{\mathsf{good}}$ and $\Theta_{\mathsf{bad}}$. Let $C_{1},\dots,C_{K}$
be a partition of the buyers, $\Theta_{1},\dots,\Theta_{K}$ be a partition of
the good item set $\Theta_{\mathsf{good}}$, and $s_{1},\dots s_{K}$ be a set
of supply functions, supported on $\Theta_{1},\dots,\Theta_{K}$ respectively.
The $k$-th submarket consists of buyers in $C_{k}$, the item set $\Theta_{k}$
and supply $s_{k}$. Let $s=\frac{1}{K}\sum_{k}s_{k}$ be the average mixture
and $s^{\prime}$ be a supply supported on $\Theta_{\mathsf{bad}}$. Let the
contaminated supply be $s_{\alpha}=\alpha s^{\prime}+(1-\alpha)s$.

By imposing structure on $\Theta_{\mathsf{good}}$ and $\Theta_{\mathsf{bad}}$
the contamination model can capture interference among auction markets. We
assume that submarkets are separated, which models the ideal case where there
is no interference. A buyer $i\in C_{k}$ is only interested in items from the
submarket he belongs to: $v_{i}(\theta)=0$ for
$\theta\in\Theta_{k^{\prime}},k^{\prime}\neq k$. Next, we let
$\Theta_{\mathsf{bad}}$ represent items that cause outbound edges from
submarkets; see the green edges in Fig 3 left panel. An item is referred to as
bad if it has positive values for buyers from at least two different
submarkets. Formally, $\theta\in\Theta_{\mathsf{bad}}$ if there exist $i\in
C_{k}$, $j\in C_{k^{\prime}}$, $k\neq k^{\prime}$, such that $v_{i}(\theta)>0$
and $v_{j}(\theta)>0$. Combining these assumptions, we have that a buyer $i$
from submarket $k$ has positive values _only_ for items from the sets
$\Theta_{k}$ and possibly $\Theta_{\mathsf{bad}}$. Now we have fully specified
a contaminated market setup: we wish to make inferences on the market
consisting of only $\Theta_{\mathsf{good}}$ (which is really $K$ fully
separate submarkets), but we observe an actual market containing items from
$\Theta_{\mathsf{good}}\cup\Theta_{\mathsf{bad}}$. With this setup, we can use
the results developed in the following section to model interference in
parallel submarkets.

In Fig 3 we present an example of interference among $K=3$ submarkets. The
market of interest is the perfectly separated market (right). The reason is,
in parallel A/B testing, submarkets are created in a way that each resembles
the global market, and when a submarket receives a treatment, the observed
quantities in that submarket, such as revenues and social welfare, are
considered surrogates for the treatment effect in the global market. However,
in practice we only observe the interfered finite market (left), which
converges to the interfered limit market (middle). In Sec. 5 we show how to
analyze parallel A/B testing using this framework.

Figure 3. The model. Left ($\widehat{\mathscr{M}}_{\alpha}$): the observed
market where interference is present among submarkets. Middle
(${\mathscr{M}}_{\alpha}$): the limit market with interference from bad item
set. Right (${\mathscr{M}}_{0}$): the limit market with perfectly separated
submarkets. We use data from the left panel to make inferences about the
market in the right panel.

##  4\. Main Results

In this section, we develop a methodology for making inferences about, e.g.,
pacing multipliers or revenue in the uncontaminated limit FPPE. We introduce a
surrogate for pacing multipliers, based on the notion of directional
derivatives, and establish its debiasing property in Sec. 4.1. Then, we focus
on estimating this surrogate quantity in Sec. 4.2, and develop asymptotic
normality results in Sec. 4.3. Secondly, we consider estimating revenue.
Revenue can be thought of as a smooth function of pacing multipliers, and we
discuss debiased estimation and inference of revenue based on our pacing
multiplier results in Sec. 4.4.

Before we proceed we briefly discuss two baseline approaches to the problem;
see Table 2 for an overview. The first method is doing nothing, i.e., treating
quantities in the contaminated finite market $\widehat{\mathscr{M}}_{\alpha}$
as estimators of those in ${\mathscr{M}}_{0}$. This approach suffers from a
significant level of bias, roughly of order $\Theta(\alpha)$, and the bias
does not vanish as the number of items increases. The second method is that,
since we know whether an item comes from the contamination supply
$s^{\prime}$, we could throw away the market equilibrium
$\widehat{\mathscr{M}}_{\alpha}$, collect the good items, and compute a finite
market equilibrium formed by the good items via solving the EG program in Eq.
4. This approach has a vanishing bias but is computationally heavy, especially
in real-world advertising platforms where there are millions of buyers. Our
proposed approach reduces bias to the order $o(\alpha)$ and does not require
solving large-scale EG programs, by utilizing the equilibrium structure of the
observed market $\widehat{\mathscr{M}}_{\alpha}$.

Table 2. Comparison of Procedures Procedure | Bias | Requires solving EG
---|---|---
Ignore interference | $\Theta(\alpha)$ | No
Solve EG | $o(1)$ | Yes
Our debiasing procedure | $o(\alpha)$ | No

###  4.1. A Debiased Surrogate for Pacing Multipliers

If we view $\beta^{*}_{\alpha}$ as a function of the level of contamination
$\alpha$, then one can imagine that under sufficient regularity conditions,
the pacing multipliers in the perfectly separated market, $\beta^{*}_{0}$, can
be approximated by some form of Taylor expansion of
$\alpha\mapsto\beta^{*}_{\alpha}$ at $\alpha$. This can be made rigorous by
the notion of directional derivatives. We define

(5) $\displaystyle\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)=\lim_{\delta\to
0^{+}}\frac{\beta^{*}_{\alpha-\delta}-\beta^{*}_{\alpha}}{\delta}\;.$

if the limit exists. We will show that
$\beta^{*}_{\alpha}+\alpha\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)$ serves as a
good approximation to $\beta^{*}$.

We now show that the directional derivative
$\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)$ has a closed-form expression under
certain regularity conditions (the conditions are given in Thm. 1; the full
proof is given in the appendix). We need a few notations for this expression.
Define $\Delta_{\alpha}=\int\nabla
f(\theta,\beta^{*}_{\alpha})(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta.$ Let
${\mathscr{H}}_{\alpha}=\nabla_{\beta\beta}^{2}\int
F(\theta,\beta^{*}_{\alpha})s_{\alpha}\mathop{}\\!\mathrm{d}\theta$ be the
Hessian matrix in the market ${\mathscr{M}}_{\alpha}$ and
$P_{\alpha}={\operatorname*{Diag}}(1(\beta^{*}_{\alpha,i}<1))$. Then, under
regularity conditions,

(6)
$\displaystyle\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)=-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\Delta_{\alpha}\;.$

We present a heuristic argument for Eq. 6 here; for a rigorous treatment we
need a perturbation theory result which is given in Lemma 1 in the appendix.
Define the contaminated EG objective $H_{\alpha}(\beta)=\int
F(\beta,\theta)s_{\alpha}\mathop{}\\!\mathrm{d}\theta$. Then
${\mathscr{H}}_{\alpha}=\nabla^{2}H_{\alpha}(\beta^{*}_{\alpha})$. The map
$(\beta,\alpha)\mapsto H_{\alpha}(\beta)$ has gradient $[\nabla
H(\beta^{*}),\int
F(\beta^{*}_{\alpha},\theta)(s^{\prime}-s)\mathop{}\\!\mathrm{d}\theta]^{\scriptscriptstyle\mathsf{T}}$
and Hessian
$[{\mathscr{H}}_{\alpha},-\Delta_{\alpha};-\Delta_{\alpha}^{\scriptscriptstyle\mathsf{T}},0]$
at $(\beta^{*}_{\alpha},\alpha)$. Then we have the following quadratic
approximation of $H_{\alpha-\delta}(\beta)$

$\displaystyle H_{\alpha-\delta}(\beta)\approx
H_{\alpha}(\beta^{*}_{\alpha})+\begin{pmatrix}\beta-\beta^{*}_{\alpha}\\\
-\delta\end{pmatrix}^{\scriptscriptstyle\mathsf{T}}\begin{pmatrix}\nabla
H_{\alpha}(\beta^{*}_{\alpha})\\\ \int
F(\beta^{*}_{\alpha},\theta)(s^{\prime}-s)\mathop{}\\!\mathrm{d}\theta\end{pmatrix}+\frac{1}{2}\begin{pmatrix}\beta-\beta^{*}\\\
-\delta\end{pmatrix}^{\scriptscriptstyle\mathsf{T}}\begin{pmatrix}{\mathscr{H}}_{\alpha}&-\Delta_{\alpha}\\\
-\Delta_{\alpha}^{\scriptscriptstyle\mathsf{T}}&0\end{pmatrix}\begin{pmatrix}\beta-\beta^{*}\\\
-\delta\end{pmatrix}\;.$

And so

$\displaystyle\beta^{*}_{\alpha-\delta}=\operatorname*{arg\,min}_{\beta\in(0,1]^{n}}H_{\alpha-\delta}(\beta)\approx\operatorname*{arg\,min}_{\beta\in(0,1]^{n}}(\nabla
H_{\alpha}(\beta^{*}_{\alpha})+\delta\Delta_{\alpha})^{\scriptscriptstyle\mathsf{T}}\beta+\tfrac{1}{2}(\beta-\beta^{*}_{\alpha})^{\scriptscriptstyle\mathsf{T}}{\mathscr{H}}_{\alpha}(\beta-\beta^{*}_{\alpha})\;,$

where we dropped terms that do not involve $\beta$.

Next we need two observations. For $\delta$ small enough, we have
$\beta^{*}_{\alpha-\delta,i}=1$ if $\beta^{*}_{\alpha,i}=1$. Intuitively,
buyers in the market ${\mathscr{M}}_{\alpha}$ with $\beta^{*}_{\alpha,i}=1$
have some nonzero leftover budget, which acts as a buffer to small changes in
supply, and thus their pacing multipliers remain one. Next, we also note
$\beta\mapsto\nabla
H_{\alpha}(\beta^{*}_{\alpha})^{\scriptscriptstyle\mathsf{T}}\beta$ is
constant on the set $\\{\beta:{\beta_{i}}=1\text{ if
}\beta^{*}_{\alpha,i}=1\\}$ by complementary slackness. Then we further
simplify and obtain

$\displaystyle\beta^{*}_{\alpha-\delta}\approx\operatorname*{arg\,min}_{{\beta_{i}}=1\text{
if
}\beta^{*}_{\alpha,i}=1}\delta\Delta_{\alpha}^{\scriptscriptstyle\mathsf{T}}\beta+\tfrac{1}{2}(\beta-\beta^{*}_{\alpha})^{\scriptscriptstyle\mathsf{T}}{\mathscr{H}}_{\alpha}(\beta-\beta^{*}_{\alpha})\;.$

The right-hand side is just a linearly constrained quadratic optimization
problem, which admits a closed-form solution
$\beta^{*}_{\alpha}-\delta(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\Delta_{\alpha}$.
Now we define a debiased pacing multiplier

(7)
$\displaystyle\widetilde{\beta}^{*}=\beta^{*}_{\alpha}+\alpha\cdot(-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\Delta_{\alpha})\;.$

###### Theorem 1 (Analysis of Bias).

Suppose that in the market ${\mathscr{M}}_{0}$ conditions Definition 2 (SMO).
and Definition 3 (SCS). hold, and assume that $\beta\mapsto\nabla^{2}\int
F(\beta,\theta)s^{\prime}\mathop{}\\!\mathrm{d}\theta$ is twice continuously
differentiable in a neighborhood of $\beta^{*}$. Then the directional
derivative $\mathop{}\\!\mathrm{d}\beta^{*}({\cdot})$ is well-defined in a
neighborhood of zero, and is given by Eq. 6. Moreover, as $\alpha\downarrow
0$,

$\displaystyle\|\widetilde{\beta}^{*}-\beta^{*}\|_{2}=o(\alpha)\;.$

The proof of Thm. 1 is given in Sec. B.1. Thm. 1 indicates that the debiased
surrogate $\widetilde{\beta}^{*}$ removes first-order bias caused by
interference. The limit pacing multipliers $\beta_{\alpha}^{*}$ of the
contaminated market ${\mathscr{M}}_{\alpha}$ will have bias of order
$\beta^{*}_{\alpha}-\beta^{*}=\Theta(\alpha)$. In contrast, Thm. 1 shows that
the debiased surrogate only incurs a bias of order $o(\alpha)$.

###  4.2. The Estimator

In this section we introduce a plug-in estimator for the debiased surrogate
$\widetilde{\beta}^{*}$ and introduce a consistency theorem. In next section
we discuss constructing confidence intervals.

To estimate $\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)$ in Eq. 6 we need
estimates of its three components: the Hessian
${\mathscr{H}}_{\alpha}=\nabla_{\beta\beta}^{2}\int
F(\theta,\beta^{*}_{\alpha})s_{\alpha}\mathop{}\\!\mathrm{d}\theta$, the
diagonal matrix $P_{\alpha}$ and the vector $\Delta_{\alpha}=\int\nabla
f(\theta,\beta^{*}_{\alpha})(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta$.

  * •

The Hessian. For simplicity in our theoretical results, we will simply assume
a generic Hessian estimator $\widehat{\mathscr{H}}_{\alpha}$ such that for
some $\eta_{t}\downarrow 0$ we have
$\widehat{\mathscr{H}}_{\alpha}-{\mathscr{H}}_{\alpha}=O_{p}(\eta_{t})$. Hong
et al. (2015) discuss the estimation of the derivative in detail. Different
kinds of statistical guarantees require different rate conditions on
$\eta_{t}$; see Theorems 2 and 3. We then introduce two Hessian estimators:
one is applicable for general FPPE, while the other requires an extra market
regularity condition. The first Hessian estimator is the finite difference
method. Let $e_{i},e_{j}$ be basis vectors and $\varepsilon_{t}$ be a step-
size. Then the estimator is

$\widehat{\mathscr{H}}_{\alpha}[i,j]=[H_{\alpha,t}(\beta^{\gamma}_{++})-H_{\alpha,t}(\beta^{\gamma}_{+-})-H_{\alpha,t}(\beta^{\gamma}_{-+})+H_{\alpha,t}(\beta^{\gamma}_{--})]/(4\varepsilon_{t}^{2})\;,$

where $\beta^{\gamma}_{\pm\pm}=\beta^{\gamma}_{\alpha}\pm
e_{i}\varepsilon_{t}\pm e_{j}\varepsilon_{t}$, and
$H_{\alpha,t}(\beta)=\frac{1}{t}{\sum_{\tau=1}^{t}}F({\theta^{\tau}},\beta)$,
with $\\{{\theta^{\tau}}\\}_{\tau}$ being the items in
$\widehat{\mathscr{M}}_{\alpha}$. In practice, a diagonal approximation of the
Hessian suffices. The second method relies on an additional regularity
condition, in which case we derive a simplified formula for the Hessian,
thereby enabling a simpler estimation procedure (see Thm. 3).

  * •

The vector $\Delta_{\alpha}$. Let $g$ be the Radon-Nikodym ratio
$g(\theta)=(\mathop{}\\!\mathrm{d}(s-s^{\prime})/\mathop{}\\!\mathrm{d}s_{\alpha})(\theta)=\frac{1}{1-\alpha}1_{\Theta_{\mathsf{good}}}(\theta)-\frac{1}{\alpha}1_{\Theta_{\mathsf{bad}}}(\theta)$.
With the ratio $g$, the true vector $\Delta_{\alpha}$ can be written as
$\Delta_{\alpha}=\int g(\theta)\nabla
f(\theta,\beta^{*}_{\alpha})s_{\alpha}(\theta)\mathop{}\\!\mathrm{d}\theta$,
which is easy to estimate given i.i.d. draws from $s_{\alpha}$. In particular,
our estimator is then

$\displaystyle\widehat{\Delta}_{\alpha}=\frac{1}{t}{\sum_{\tau=1}^{t}}g({\theta^{\tau}})\mu^{\tau}\;.$

Here
$\mu^{\tau}=[x_{1}^{\tau}v_{1}^{\tau},\dots,x_{n}^{\tau}v_{n}^{\tau}]^{\scriptscriptstyle\mathsf{T}}$
is a subgradient of $f({\theta^{\tau}},\beta^{\gamma}_{\alpha})$ w.r.t.
$\beta$.

  * •

The diagonal matrix $P_{\alpha}$. Recall
$P_{\alpha}={\operatorname*{Diag}}(1(\beta^{*}_{\alpha,i}<1))$. So a natural
estimator is
$\widehat{P}_{\alpha}={\operatorname*{Diag}}(1(\beta^{\gamma}_{\alpha,i}<1-\iota_{t}))$,
where the slackness $\iota_{t}\asymp\frac{1}{\sqrt{t}}$.

With all three components estimated, using $\beta^{\gamma}_{\alpha}$ is the
pacing multiplier in the market $\widehat{\mathscr{M}}_{\alpha}$ we define the
plug-in estimator for $\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)$ in Eq. 6 as

(8)
$\displaystyle\widehat{\beta}=\beta^{\gamma}_{\alpha}-\alpha\,{\cdot}\,(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}\widehat{\Delta}_{\alpha}\;.$

###### Theorem 2 (Consistency).

If $\eta_{t}=o(1)$, then
$\widehat{\beta}{\,\overset{{p}}{\to}\,}\widetilde{\beta}^{*}$. The proof is
in Sec. B.2.

###  4.3. Asymptotic Normality and Inference

We present two asymptotic normality results. In the first result, we require a
stronger condition on the Hessian error rate $\eta_{t}$. In particular, as
will be shown in Thm. 3, the rate condition $\eta_{t}=o(1/\sqrt{t})$ is
sufficient for normality. One could use a separate large historical dataset to
obtain a good estimate of the Hessian matrix. In the second result, we impose
an additional condition on market structure which simplifies the Hessian
expression and facilitates efficient Hessian estimation. To describe the
additional market structure, we define the gap between the highest and the
second-highest bid for an item $\theta$ under pacing $\beta$ by

$\displaystyle{\mathsf{{bidgap}}}(\beta,\theta)=\max\\{{\beta_{i}}{v_{i}(\theta)}\\}-\operatorname{secondmax}\\{{\beta_{i}}{v_{i}(\theta)}\\}\;,$

where $\operatorname{secondmax}$ is the second-highest entry potentially equal
to the highest; e.g., $\operatornamewithlimits{secondmax}([1,1,2])=1$. When
there is a tie for an item $\theta$ under pacing $\beta$, we have
${\mathsf{{bidgap}}}(\beta,\theta)=0$. When there is no tie for an item
$\theta$, the gap ${\mathsf{{bidgap}}}(\beta,\theta)$ is strictly positive.

For any $g:\Theta\to{\mathbb{R}}$, let ${\mathbb{E}}_{\alpha}[g]=\int
gs_{\alpha}\mathop{}\\!\mathrm{d}\theta$ and
${\operatorname{Cov}}_{\alpha}(g)={\mathbb{E}}_{\alpha}[(g-{\mathbb{E}}_{\alpha}[g])(g-{\mathbb{E}}_{\alpha}[g])^{\scriptscriptstyle\mathsf{T}}]$.
Recall $\widetilde{\beta}^{*}$ is the debiased surrogate in Eq. 7 and
$\widehat{\beta}$ is its estimator defined in Eq. 8.

We need to introduce a few more notations to describe the normality results.
First, let

$\displaystyle
D_{\alpha}=-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\nabla
f({\cdot},\beta^{*}_{\alpha})\;,$

As mentioned previously, the pacing multipliers in the contaminated market
converge to the limit counterpart and have the representation

$\displaystyle\sqrt{t}(\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha})=\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}(D_{\alpha}({\theta^{\tau}})-{\mathbb{E}}_{\alpha}[D_{\alpha}({\theta^{\tau}})])+o_{p}(1)\;.$

In the statistics literature, the function
$D_{\alpha}({\cdot})-{\mathbb{E}}[D_{\alpha}]$ is called the influence
function (van der Vaart, 2000). For our debiased estimators, we need the
following (uncentered) influence functions.

$\displaystyle
IF_{1}(\theta)=\big{(}\tfrac{1}{1-\alpha}1_{\Theta_{\mathsf{good}}}(\theta)\big{)}D_{\alpha}(\theta)\;,$
$\displaystyle
IF_{2}(\theta)=IF_{1}(\theta)-2\alpha{\operatorname*{Diag}}(\beta^{*}_{\alpha,i}\Delta_{\alpha,i}b_{i}^{{-1}})D_{\alpha}(\theta)\;.$

###### Theorem 3 (Asymptotic Normality).

Let Definition 3 (SCS). and Definition 2 (SMO). hold in
${\mathscr{M}}_{\alpha}$.

1\. It holds that
$\widehat{\beta}-\widetilde{\beta}^{*}={Z_{t}}+O_{p}(\eta_{t})+o_{p}(\tfrac{1}{\sqrt{t}}),$
where

$\displaystyle\sqrt{t}Z_{t}{\,\overset{{d}}{\to}\,}{\mathscr{N}}(0,\Sigma_{1})$

with $\Sigma_{1}={\operatorname{Cov}}_{\alpha}(IF_{1})$.

2\. If in addition
${\mathbb{E}}_{\alpha}[1/{\mathsf{{bidgap}}}(\beta^{*}_{\alpha},\theta)]<\infty$,
then
${\mathscr{H}}_{\alpha}={\operatorname*{Diag}}(b_{i}/(\beta^{*}_{\alpha,i})^{2})$.
Suppose we estimate ${\mathscr{H}}_{\alpha}$ with
$\widehat{\mathscr{H}}_{\alpha}={\operatorname*{Diag}}(b_{i}/(\beta^{\gamma}_{\alpha,i})^{2})$.
Then

$\displaystyle\sqrt{t}(\widehat{\beta}-\widetilde{\beta}^{*}){\,\overset{{d}}{\to}\,}{\mathscr{N}}(0,\Sigma_{2})$

where $\Sigma_{2}={\operatorname{Cov}}_{\alpha}(IF_{2})$. The proof is in Sec.
B.3.

Thm. 3 part 1 shows how the error of the Hessian estimate affects the
distribution of the estimator $\widehat{\beta}$. If $\eta_{t}=o(1/\sqrt{t})$,
then the decomposition becomes
$\sqrt{t}(\widehat{\beta}-\widetilde{\beta}^{*})=\sqrt{t}Z_{t}+o_{p}(1)$,
implying asymptotic normality, i.e.
$\sqrt{t}(\widehat{\beta}-\widetilde{\beta}^{*}){\,\overset{{d}}{\to}\,}{\mathscr{N}}(0,\Sigma_{1})$,
in which case one can construct an ellipsoidal confidence region for
$\widetilde{\beta}^{*}$. Thm. 3 part 2 shows direct asymptotic normality under
the extra condition, with a simpler Hessian estimator that avoids step-sizes.

To perform inference, we need to construct a consistent estimate of the
covariance matrix. Now we describe a plug-in estimate of $\Sigma_{1}$. Let the
estimator $\widehat{IF_{1}}^{\tau}$ be

$\displaystyle\widehat{IF_{1}}^{\tau}=-\big{(}\tfrac{1}{1-\alpha}1_{\Theta_{\mathsf{good}}}({\theta^{\tau}})\big{)}(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}\mu^{\tau}\;,$

where
$\mu^{\tau}=[x_{1}^{\tau}v_{1}^{\tau},\dots,x_{n}^{\tau}v_{n}^{\tau}]^{\scriptscriptstyle\mathsf{T}}$,
and $\widehat{P_{\alpha}},\widehat{\mathscr{H}}_{\alpha}$ have been defined in
Sec. 4.2. The plug-in estimator is

$\displaystyle\widehat{\Sigma}_{1}=\frac{1}{t}{\sum_{\tau=1}^{t}}(\widehat{IF_{1}}^{\tau}-\overline{IF_{1}})(\widehat{IF_{1}}^{\tau}-\overline{IF_{1}})^{\scriptscriptstyle\mathsf{T}}$

with
$\overline{IF_{1}}=\frac{1}{t}{\sum_{\tau=1}^{t}}\widehat{IF_{1}}^{\tau}$. By
similar arguments as in Liao et al. (2023), the plug-in estimates of
$\Sigma_{1}$ and $\Sigma_{2}$ are consistent. Algorithm 1 summarizes the
debiasing procedure.

Input. Budgets $[b_{1},\dots,b_{n}]$. Values ${v_{i}^{\tau}}$. First-price
allocation ${x_{i}^{\tau}}\in[0,1]$. The observed equilibrium pacing
multipliers
$\beta^{\gamma}_{\alpha}=[\beta^{\gamma}_{1},\dots,\beta^{\gamma}_{n}]$.
Proportion of bad items $\alpha$. Desired confidence level $(1-c)\in(0,1)$.

1\. Estimate the Hessian matrix $\widehat{\mathscr{H}}_{\alpha}$, e.g. via
$\widehat{\mathscr{H}}_{\alpha}={\operatorname*{Diag}}(b_{i}/(\beta^{\gamma}_{\alpha,i})^{2})$,
or using finite differences.

2\. Compute relevant quantities $\widehat{P}_{\alpha}$,
$\widehat{\Delta}_{\alpha}$, $\mu^{\tau}$.

3\. Compute the debiased estimator $\widehat{\beta}$ and covariance matrix
$\widehat{\Sigma}_{1}$.

4\. Output confidence region:
$\widehat{\beta}+(\chi_{n,c}/\sqrt{t})\widehat{\Sigma}_{1}^{1/2}{\mathbb{B}}$,
where $\chi_{n,c}^{2}$ is the $(1-c)$-quantile of a chi-square distribution
with degree $n$, and ${\mathbb{B}}$ is the unit ball in ${\mathbb{R}^{n}}$.

ALGORITHM 1 Debiasing procedure

###  4.4. Results for Revenue

The revenue in the good market is defined as
${\mathsf{{REV}}}^{*}=\int\max_{i}\\{{v_{i}(\theta)}{\beta^{*}_{i}}\\}s(\theta)\mathop{}\\!\mathrm{d}\theta$.
We define the debiased revenue surrogate and its estimator

(9)
$\displaystyle\widetilde{{\mathsf{{REV}}}}^{*}=\int\max_{i}\\{{v_{i}(\theta)}\widetilde{\beta}^{*}_{i}\\}s(\theta)\mathop{}\\!\mathrm{d}\theta\;,$
(10)
$\displaystyle\widehat{{\mathsf{{REV}}}}=\frac{1}{1-\alpha}\frac{1}{t}{\sum_{\tau=1}^{t}}1_{\Theta_{\mathsf{good}}}({\theta^{\tau}})\max_{i}\\{{v_{i}(\theta^{\tau})}\widehat{\beta}_{i}\\}\;.$

In words, we approximate ${\mathsf{{REV}}}^{*}$ with the revenue generated in
the market where buyers bid according to the pacing profile
$\widetilde{\beta}^{*}$, and then we estimate this via plug-in estimation on
the subset of items that are good.

###### Theorem 4.

Let the conditions from Thm. 1 and Thm. 3 hold. The debiased revenue removes
first-order bias:
$\widetilde{{\mathsf{{REV}}}}^{*}={\mathsf{{REV}}}^{*}+o(\alpha)$. Assume that
$\sqrt{t}(\widehat{\beta}-\widetilde{\beta}^{*})$ has influence function $IF$,
i.e.,
$\sqrt{t}(\widehat{\beta}-\widetilde{\beta}^{*})=\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}IF({\theta^{\tau}})+o_{p}(1)$,
then
$\sqrt{t}(\widehat{{\mathsf{{REV}}}}-\widetilde{{\mathsf{{REV}}}}^{*}){\,\overset{{d}}{\to}\,}{\mathscr{N}}(0,\sigma^{2}_{\mathsf{{REV}}})$
where
$\sigma^{2}_{\mathsf{{REV}}}={\operatorname{Cov}}_{\alpha}(IF_{\mathsf{{REV}}})$,
$IF_{\mathsf{{REV}}}({\cdot})=\frac{1}{1-\alpha}\big{(}1_{\Theta_{\mathsf{good}}}({\cdot})f({\cdot},\widetilde{\beta}^{*})+{\mathbb{E}}_{\alpha}[\nabla
f(\theta,\widetilde{\beta}^{*})1_{\Theta_{\mathsf{good}}}(\theta)]^{\scriptscriptstyle\mathsf{T}}IF({\cdot})\big{)}$.
The proof is in Sec. B.4.

Examples of influence functions compatible with Thm. 4 are the influence
functions in Thm. 3.

We have two methods to construct CIs for the debiased revenue surrogate in Eq.
7. The first method is based on the asymptotic normality results in Thm. 4. In
the second method, a revenue CI is constructed based on a CI for
$\beta^{*}_{\alpha}$. Suppose ${\small\mathbb{{CI}}}$ is some confidence
region for $\beta^{*}_{\alpha}$. Then
$\\{\frac{1}{1-\alpha}\frac{1}{t}{\sum_{\tau=1}^{t}}\allowbreak
1_{\Theta_{\mathsf{good}}}({\theta^{\tau}})\max_{i}{v_{i}(\theta^{\tau})}{\beta_{i}}:\beta\in{\small\mathbb{{CI}}}\\}$
serves as a CI for revenue. Another way to utilize a pacing multiplier CI is
based on the observation that revenue is a monotone function of the pacing
multiplier. Let
$\underline{{\beta_{i}}}=\min\\{{\beta_{i}}:\beta\in{\small\mathbb{{CI}}}\\}$
and $\bar{\beta}_{i}=\max\\{{\beta_{i}}:\beta\in{\small\mathbb{{CI}}}\\}$.
Then another natural (potentially wider) CI for
$\widetilde{{\mathsf{{REV}}}}^{*}$ is
$[\underline{{\mathsf{{REV}}}},\overline{{\mathsf{{REV}}}}]$, where

(11)
$\underline{{\mathsf{{REV}}}}=\frac{1}{1-\alpha}\frac{1}{t}{\sum_{\tau=1}^{t}}1_{\Theta_{\mathsf{good}}}({\theta^{\tau}})\max_{i}{v_{i}(\theta^{\tau})}\underline{{\beta_{i}}}\;,\quad\overline{{\mathsf{{REV}}}}=\frac{1}{1-\alpha}\frac{1}{t}{\sum_{\tau=1}^{t}}1_{\Theta_{\mathsf{good}}}({\theta^{\tau}})\max_{i}{v_{i}(\theta^{\tau})}\bar{\beta}_{i}\;.$

##  5\. Parallel A/B Test under Interference

In this section, we use the theory from the previous sections to formulate a
statistical inference theory for parallel A/B tests under interference.

Consider $K$ auction markets in which we want to run parallel A/B tests. There
are $n$ buyers, each with budget $b_{i}$ corresponding to one unit supply of
items, and an item set $\Theta$, partitioned into $\Theta_{\mathsf{good}}$ and
$\Theta_{\mathsf{bad}}$. Let $C_{1},\dots,C_{K}$ be a partition of the buyers,
$\Theta_{1},\dots,\Theta_{K}$ be a partition of the good item set
$\Theta_{\mathsf{good}}$, and $s_{1},\dots s_{K}$ be a set of supply
functions, supported on $\Theta_{1},\dots,\Theta_{K}$ respectively. The $k$-th
submarket consists of buyers in $C_{k}$, the item set $\Theta_{k}$ and supply
$s_{k}$. Let $s=\frac{1}{K}\sum_{k}s_{k}$ be the average mixture and
$s^{\prime}$ be a supply supported on $\Theta_{\mathsf{bad}}$.

To model treatment application we introduce the _potential value functions_

$v(0)=(v_{1}(0,\cdot),\dots,v_{n}(0,\cdot)),\;v(1)=(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)$.

We extend the structure on $\Theta_{\mathsf{bad}}$ and
$\Theta_{\mathsf{good}}$ introduced in Sec. 3.2 to A/B testing here. We assume
these submarkets are separated. This is to model the ideal case where there is
no interference. A buyer $i\in C_{k}$ is only interested in items from the
submarket he belongs to: $v_{i}(w,\theta)=0$ for $\theta\in
C_{k^{\prime}},k^{\prime}\neq k$, and $w\in\\{0,1\\}$. An item is called a bad
item if it has positive values for buyers from different submarkets. Formally,
$\theta\in\Theta_{\mathsf{bad}}$ if there exist $w\in\\{0,1\\}$, $i\in C_{k}$,
$j\in C_{k^{\prime}}$, $k\neq k^{\prime}$, so that $v_{i}(w,\theta)>0$ and
$v_{j}(w,\theta)>0$. A buyer $i$ from submarket $k$ has a (potentially)
positive value only for items in $\Theta_{k}\cup\Theta_{\mathsf{bad}}$.

Step 1. The treatment effects. Let
${\mathscr{M}}(w,k)={\small\mathsf{{FPPE}}}(\\{b_{i}\\}_{i\in
C_{k}},\\{v_{i}({\cdot},w)\\}_{i\in C_{k}},s_{k},\Theta_{k})$be the $k$-th
limit submarket under treatment $w\in\\{0,1\\}$, and let revenue be
${\mathsf{{REV}}}^{*}_{k}(w)$. Then the treatment effect in the submarket $k$
is $\tau^{*}_{k}={\mathsf{{REV}}}^{*}_{k}(1)-{\mathsf{{REV}}}^{*}_{k}(0)$.
Equivalently, all $K$ submarkets can be formed simultaneously,
${\mathscr{M}}(w)={\small\mathsf{{FPPE}}}\left(\frac{1}{K}b,v(w),s,\Theta\right).$
The scaling $1/K$ in budgets ensures that a buyer in $C_{k}$ has budget
$b_{i}/K$ to bid for items in $\Theta_{k}$, whose supply in ${\mathscr{M}}(w)$
is $\frac{1}{K}s_{k}$. The $k$-th component of ${\mathscr{M}}(w)$ corresponds
to ${\mathscr{M}}(w,k)$.

Step 2. The experiment. A practical parallel A/B test scheme is as follows.

_Step 2.1. Budget splitting._ Decide on a budget split ratio $\pi_{0}$,
$\pi_{1}$ satisfying $\pi_{0}+\pi_{1}=1$, and split budgets accordingly.
Choose A/B test size $t$, the total number of impressions in each submarket
summed across treatments. Then, the budget of buyer $i$ for treatment $0$ will
be $\pi_{0}tb_{i}$, and $\pi_{1}tb_{i}$ for treatment 1. This is because
$b_{i}$ is normalized to correspond to one unit of total supply.

_Step 2.2. Observe markets with interference._ Draw items/impressions from
$\alpha s^{\prime}+(1-\alpha)s$. Draw $\lfloor\pi_{0}t\rfloor$ items for each
submarket under treatment $0$ and $\lfloor\pi_{1}t\rfloor$ for treatment 1. A
total of $t_{w}=\lfloor\pi_{w}tK\rfloor$ items are drawn for the whole market
under treatment $w$. Since items come from the contaminated distribution,
roughly a small fraction $\alpha$ of the $t_{w}$ items cause interference.

The data observed following the described A/B test scheme can be compactly
represented by two finite FPPEs (one for each treatment) (Def. 4):
$\widehat{\mathscr{M}}_{\alpha}(w)={\small\widehat{\textsf{{FPPE}}}}(\pi_{w}tb,v(w),1,\gamma)$
, where $\gamma\subset\Theta$ consists of $t_{w}=\lfloor\pi_{w}tK\rfloor$
i.i.d. draws from the mixture $\alpha s^{\prime}+(1-\alpha)s$.

It can be shown that the observed market $\widehat{\mathscr{M}}_{\alpha}(w)$
converges to ${\mathscr{M}}_{\alpha}(w)={\small\mathsf{{FPPE}}}\
\left(\frac{1}{K}b,v(w),s_{\alpha},\Theta\right).$

Step 3. Debiasing $\beta$. Following previous section, we can debias
$\widehat{\mathscr{M}}_{\alpha}(w)$ to approximate ${\mathscr{M}}(w)$. Let
$\widehat{\beta}(w)$ be the debiased pacing multiplier.

Step 4. Revenue estimator. Estimate $\widehat{\mathsf{{REV}}}_{k}(w)$ by

$\displaystyle\frac{1}{\pi_{w}(1-\alpha)t}\sum_{\tau=1}^{t_{w}}1_{\Theta_{k}}({\theta^{\tau}})\max_{i\in
C_{k}}{v_{i}(\theta^{\tau})}\widehat{\beta_{i}}(w)\;.$

Then
$\widehat{\tau}_{k}=\widehat{\mathsf{{REV}}}_{k}(1)-\widehat{\mathsf{{REV}}}_{k}(0)$
and a variance estimate can be obtained by either asymptotic normality,
confidence region of $\beta$, or bootstrap.

##  6\. Experiment

To evaluate our proposed framework and debiased estimator, we run both fully
synthetic and semi-synthetic simulations to check if the proposed estimator
for beta and revenue are indeed less biased as well as the coverage of the
proposed estimator.

###  6.1. Fully synthetic experiments

In the fully synthetic experiments, we simulate 10 buyers and 1000 _good_
items in two submarkets, with a varying number of _bad_ items (up to 500) in
order to study the effect of the contamination parameter $\alpha$. For each
$\alpha$, we randomly sample a budget from a uniform distribution for each
buyer, and compute $\beta^{*}$ and ${\mathsf{{REV}}}^{*}$ from the limit pure
market ${\mathscr{M}}_{0}$ with a uniformly distributed value function in each
submarket. To check if the debiased surrogate reduces bias, we compute
$\beta^{*}_{\alpha}$ and ${\mathsf{{REV}}}^{*}_{\alpha}$ from the limit market
with interference ${\mathscr{M}}_{\alpha}$ and their surrogates,
$\widetilde{\beta}^{*}$ and $\widetilde{\mathsf{{REV}}}^{*}$. We look at the
normalized bias for the surrogate, defined as
$\|\widetilde{\beta}^{*}-\beta^{*}\|_{2}/\|\beta^{*}\|_{2}$ for pacing
multipliers and as $|\widetilde{\mathsf{{REV}}}^{*}/{\mathsf{{REV}}}^{*}-1|$
for revenue, and similarly defined for the limit quantities. Fig 4 shows the
normalized bias curves as a function of $\alpha$. It can be seen that the
magnitude of the bias increases with $\alpha$, for both the variables in the
limit market with interference ${\mathscr{M}}_{\alpha}$ and their debiased
surrogates. We see that the bias of the debiased surrogates is indeed much
smaller than the contaminated limit quantities.

Figure 4. Normalized bias (in percent of true value) as a function of $\alpha$
in fully synthetic experiments. $\widetilde{\beta}^{*}$ and
$\widetilde{\mathsf{{REV}}}^{*}$ are the debiased surrogates for pacing
multiplier and revenue in the limit market with interference
${\mathscr{M}}_{\alpha}$.

Next, we check the coverage of the proposed variance estimator. For each
$\alpha$ and each budget sample, we run 100 simulations in the following way:
We sample items (or their values for each buyer) considering two submarkets
and bad items. We then run the finite FPPE with bad items and obtain a
baseline estimate for pacing multiplier and revenue without applying the
debiasing procedure. Then, we apply the debiasing procedure to compute the
debiased estimates. For each simulation, we check if the debiased surrogate is
within the confidence interval of the debiased estimator. Finally, we
aggregate them to compute the estimated coverage of the estimator. The results
for both pacing multiplier and revenue are shown in Table 3. For the coverage
of $\widehat{\beta}$, we first compute the coverage of each component and
report only the average in the table. It is shown that $\widehat{\beta}$ is
slightly over-covered. We found that the over-coverage is mainly due to the
over-estimation of the estimator’s variance. For revenue, we construct the CI
using the two approaches as mentioned in Sec. 4.4: one based on Eq. 11 and the
other using parametric bootstrap based on the estimated asymptotic
distribution of $\widehat{\beta}$ (with ”(b)” in the column names). First of
all, we show in Fig 5 that both CIs converges to the true value from the limit
market with interfrence ${\mathscr{M}}_{\alpha}$ as the number of items goes
to infinity. Then, in Table 3, we show that the bootstrap CI width is much
smaller compared to that from Eq. 11. However, both CIs are over-covered,
higher than the nominal level (95%). It is expected though that the CI from
Eq. 11 is relatively large and hence conservative since it uses the min and
max of each $\beta_{i}$, hence likely living outside of the confidence region
($n$-dimension ellipsoid) for $\widehat{\beta}$ and leading to over-coverage.
For the bootstrap CI, it requires enough bootstrap samples to fully explore
the whole boundary of the confidence region of $\widehat{\beta}$, as well as
an accurate estimate of the asymptotic distribution of $\widehat{\beta}$. In
our fully synthetic simulation, our hypothesis is that the over-coverage of
the bootstrap CI is mainly due to the over-estimation of the variance for
$\widehat{\beta}$.

| $\widehat{\beta}$ | $\widehat{\mathsf{{REV}}}$ |
---|---|---|---
$\alpha$ | coverage | CI width | CI width (b) | coverage | coverage (b) |
100/1100 | 0.993 | 0.132 | 0.043 | 1.0 | 1.0 |
200/1200 | 0.994 | 0.141 | 0.059 | 1.0 | 1.0 |
300/1300 | 0.980 | 0.107 | 0.059 | 1.0 | 1.0 |
400/1400 | 0.983 | 0.098 | 0.064 | 1.0 | 1.0 |
500/1500 | 0.971 | 0.108 | 0.069 | 1.0 | 1.0 |
Table 3. Coverage of $\widehat{\beta}$ and revenue estimates in fully
synthetic experiments. All quantities are averaged over 100 simulations for
each $\alpha$. The coverage of $\widehat{\beta}$ is averaged over all
components of $\widehat{\beta}$. For revenue estimates, the columns with ”(b)”
represent the quantities from the bootstrap CI, while the columns without
”(b)” are for the CI from Eq. 11. The CI widths are normalized by the revenue
from the limit market ${\mathscr{M}}_{\alpha}$. $\alpha$ is expressed as the
ratio of the number of bad items and the total items. Figure 5. Revenue
confidence intervals as a function of the number of items. The analytic CI
comes from Eq. 11. The true value is the debiased surrogates for revenue in
the limit market with interference ${\mathscr{M}}_{\alpha}$.

###  6.2. Semi-synthetic experiments

We perform semi-synthetic experiments almost in the same way as with fully
synthetic ones. The difference is that values are sampled from historical
bidding data, making the budget and value distributions heavy-tailed. This
matches real-world applications better, instead of the uniform distributions
of the fully synthetic experiments. More specifically, we first sample a
certain number of auctions. For each auction, we sample a given number of
advertisers with their per-impression bids. Advertisers that are sampled
across different auctions are treated as the same buyers and their budgets are
determined by aggregating their values over auctions up to a scalar to
calibrated to get the percentage of budget-constrained buyers equal to what
was observed in the real-world auction market, along the same lines as the
experiments of Conitzer et al. (2022b).

We observe similar results in terms of biases as in the fully synthetic
experiments. The biases of the debiased surrogates are smaller than those from
the limit market with interference ${\mathscr{M}}_{\alpha}$, with similar
bias-$\alpha$ curves as shown in Fig 4. Coverage estimates for
$\widehat{\beta}$ and $\widehat{\mathsf{{REV}}}$ are shown in Table 4. The CI
from Eq. 11 is still very conservative as expected, achieving 100% coverage
for all $\alpha$. However, unlike the fully synthetic experiment, the coverage
for $\widehat{\beta}$ is slightly smaller than the nominal level, as well as
the coverage of the bootstrap CI of revenue. The under-coverage for
$\widehat{\beta}$ is mainly driven by the under-estimation of the variance of
$\widehat{\beta}$, while the under-coverage of the bootstrap CI for revenue
can also be partially attributed to the higher dimensionality (with 40
buyers), making the bootstrap resampling harder to explore the whole space.
Although the proposed variance estimator has good asymptotic properties, the
results from both the fully and semi- synthetic experiments suggest that it
can perform badly, in either direction, for finite markets. Constructing more
accurate variance estimators for our debiased estimator in finite settings
would certainly mitigate the over- or under-coverage issues that we observe
here and deserve more future research. One promising alternative is to
construct the CI for $\widehat{\beta}$ and $\widehat{\mathsf{{REV}}}$ by
directly bootstrapping the observed value matrix, though this might work best
in a setting where the limit market has independent valuations across buyers.

| $\widehat{\beta}$ | $\widehat{\mathsf{{REV}}}$ |
---|---|---|---
$\alpha$ | coverage | CI width | CI width (b) | coverage | coverage (b) |
1000/11000 | 0.877 | 0.244 | 0.044 | 1.0 | 0.95 |
2000/12000 | 0.849 | 0.225 | 0.043 | 1.0 | 0.87 |
3000/13000 | 0.852 | 0.210 | 0.041 | 1.0 | 0.81 |
4000/14000 | 0.828 | 0.200 | 0.040 | 1.0 | 0.90 |
5000/15000 | 0.826 | 0.191 | 0.039 | 1.0 | 0.90 |
Table 4. Coverage of $\widehat{\beta}$ and revenue estimates in the semi-
synthetic experiments. All quantities are averaged over 100 simulations for
each $\alpha$ (the ratio of the number of bad items and the total items). The
coverage of $\widehat{\beta}$ is averaged over all components of
$\widehat{\beta}$. For revenue estimates, the columns with ”(b)” represent the
quantities from the bootstrap CI, while the columns without ”(b)” are for the
CI from Eq. 11. The CI widths are normalized by the revenue from the limit
market ${\mathscr{M}}_{\alpha}$.

##  7\. Conclusion

We have proposed a practical experimental design for performing concurrent A/B
tests in large-scale ad auction markets, using a submarket clustering
approach, and showed that in production experiments, this submarket clustering
approach leads to strong sign consistency performance, as compared to A/B
testing on the full market, while allowing significantly-higher A/B test
throughput. In order to model the potential for interference between submarket
A/B tests, we introduced a theoretical model of statistical inference in
first-price pacing equilibrium problems, under settings with supply
contamination. We showed how one can perform statistical inference in such a
setting using a debiased estimation procedure, and studied the statistical
properties of this procedure. We then showed how our model of statistical
inference in FPPE with contamination can be used to model the submarket
clustering parallel A/B test design, and gave theoretical guarantees on
performance. Finally, we presented numerical experiments on fully synthetic
and semi-synthetic data derived from Meta ad auctions. The experiments showed
that our proposed debiased estimator achieves smaller biases and its
statistical coverage on realistic data is generally in line with the
predictions from our theory.

## References

  * (1)
  * Aggarwal et al. (2019) Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. 2019.  Autobidding with constraints. In _Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings 15_. Springer, 17–30.
  * Aronow and Samii (2017) Peter M. Aronow and Cyrus Samii. 2017.  Estimating average causal effects under general interference, with application to a social network experiment.  _The Annals of Applied Statistics_ 11, 4 (2017), 1912 – 1947.  https://doi.org/10.1214/16-AOAS1005
  * Athey et al. (2018) Susan Athey, Dean Eckles, and Guido W. Imbens. 2018.  Exact p-Values for Network Interference.  _J. Amer. Statist. Assoc._ 113, 521 (2018), 230–240.  https://doi.org/10.1080/01621459.2016.1241178 arXiv:https://doi.org/10.1080/01621459.2016.1241178
  * Babaioff et al. (2021) Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. 2021.  Non-Quasi-Linear Agents in Quasi-Linear Mechanisms. In _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_ , Vol. 185. 84.
  * Balseiro et al. (2021a) Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021a.  Robust auction design in the auto-bidding world.  _Advances in Neural Information Processing Systems_ 34 (2021), 17777–17788.
  * Balseiro et al. (2017) Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. 2017.  Budget management strategies in repeated auctions. In _Proceedings of the 26th International Conference on World Wide Web_. 15–23.
  * Balseiro et al. (2021b) Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. 2021b.  Budget-Management Strategies in Repeated Auctions.  _Operations research_ 3 (2021), 859–876.
  * Balseiro et al. (2023) Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. 2023.  Contextual standard auctions with budgets: Revenue equivalence and efficiency guarantees.  _Management Science_ (2023).
  * Balseiro et al. (2015) Santiago R Balseiro, Omar Besbes, and Gabriel Y Weintraub. 2015.  Repeated auctions with budgets in ad exchanges: Approximations and design.  _Management Science_ 61, 4 (2015), 864–884.
  * Balseiro and Gur (2019) Santiago R Balseiro and Yonatan Gur. 2019.  Learning in repeated auctions with budgets: Regret minimization and equilibrium.  _Management Science_ 65, 9 (2019), 3952–3968.
  * Basse et al. (2016) Guillaume W. Basse, Hossein Azari Soufiani, and Diane Lambert. 2016.  Randomization and The Pernicious Effects of Limited Budgets on Auction Experiments. In _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 51)_ , Arthur Gretton and Christian C. Robert (Eds.). PMLR, Cadiz, Spain, 1412–1420.  https://proceedings.mlr.press/v51/basse16b.html
  * Borgs et al. (2007) Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mohammad Mahdian. 2007.  Dynamics of bid optimization in online advertisement auctions. In _Proceedings of the 16th international conference on World Wide Web_. 531–540.
  * Chen et al. (2007) Lihua Chen, Yinyu Ye, and Jiawei Zhang. 2007.  A note on equilibrium pricing as convex optimization. In _International Workshop on Web and Internet Economics_. Springer, 7–16.
  * Chen et al. (2021) Xi Chen, Christian Kroer, and Rachitesh Kumar. 2021.  Throttling Equilibria in Auction Markets. In _Web and Internet Economics - 17th International Conference, WINE Proceedings_.
  * Chen et al. (2023) Xi Chen, Christian Kroer, and Rachitesh Kumar. 2023.  The complexity of pacing for second-price auctions.  _Mathematics of Operations Research_ (2023).
  * Chin (2019) Alex Chin. 2019.  Regression Adjustments for Estimating the Global Treatment Effect in Experiments with Interference.  _Journal of Causal Inference_ 7 (05 2019).  https://doi.org/10.1515/jci-2018-0026
  * Cole et al. (2017) Richard Cole, Nikhil R Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. 2017.  Convex program duality, fisher markets, and Nash social welfare. In _18th ACM Conference on Economics and Computation, EC 2017_. Association for Computing Machinery, Inc.
  * Conitzer et al. (2022a) Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier-Moses, Eric Sodomka, and Christopher A Wilkens. 2022a.  Pacing Equilibrium in First Price Auction Markets.  _Management Science_ (2022).
  * Conitzer et al. (2022b) Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. 2022b.  Multiplicative pacing equilibria in auction markets.  _Operations Research_ 70, 2 (2022), 963–989.
  * Deng et al. (2023) Yuan Deng, Jieming Mao, Vahab Mirrokni, Yifeng Teng, and Song Zuo. 2023.  Non-uniform Bid-scaling and Equilibria for Different Auctions: An Empirical Study.  _arXiv preprint arXiv:2311.10679_ (2023).
  * Deng et al. (2021) Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021.  Towards efficient auctions in an auto-bidding world. In _Proceedings of the Web Conference 2021_. 3965–3973.
  * Eckles et al. (2017) Dean Eckles, Brian Karrer, and Johan Ugander. 2017.  Design and Analysis of Experiments in Networks: Reducing Bias from Interference.  _Journal of Causal Inference_ 5, 1 (2017), 20150021.  https://doi.org/doi:10.1515/jci-2015-0021
  * Gaitonde et al. (2023) Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. 2023.  Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In _14th Innovations in Theoretical Computer Science Conference (ITCS 2023)_ , Vol. 251. 52.
  * Gao and Kroer (2022) Yuan Gao and Christian Kroer. 2022.  Infinite-Dimensional Fisher Markets and Tractable Fair Division.  _Operations Research (forthcoming)_ (2022).
  * Gao et al. (2021) Yuan Gao, Christian Kroer, and Alex Peysakhovich. 2021.  Online Market Equilibrium with Application to Fair Division.  _arXiv preprint arXiv:2103.12936_ (2021).
  * Goke et al. (2021) Shumpei Goke, Gabriel Y Weintraub, Ralph Mastromonaco, and Sam Seljan. 2021.  Bidders’ Responses to Auction Format Change in Internet Display Advertising Auctions.  _arXiv preprint arXiv:2110.13814_ (2021).
  * Harshaw et al. (2021) Christopher Harshaw, Fredrik Sävje, David Eisenstat, Vahab Mirrorkni, and Jean Pouget-Abadie. 2021.  Design and analysis of Bipartite Experiments under a Linear Exposure-Response Model.  _arXiv_ 2103.06392v3 (12 2021).  arXiv:2103.06392v3 [stat.ME]
  * Hong et al. (2015) Han Hong, Aprajit Mahajan, and Denis Nekipelov. 2015.  Extremum estimation and numerical derivatives.  _Journal of Econometrics_ 188, 1 (2015), 250–263.
  * Karande et al. (2013) Chinmay Karande, Aranyak Mehta, and Ramakrishnan Srikant. 2013.  Optimizing budget constrained spend in search advertising. In _Proceedings of the sixth ACM international conference on Web search and data mining_. 697–706.
  * Karrer et al. (2021) Brian Karrer, Liang Shi, Monica Bhole, Matt Goldman, Tyrone Palmer, Charlie Gelman, Mikael Konutgan, and Feng Sun. 2021.  Network experimentation at scale. In _Proceedings of the 27th acm sigkdd conference on knowledge discovery & data mining_. 3106–3116.
  * Li and Wager (2022) Shuangning Li and Stefan Wager. 2022.  Random graph asymptotics for treatment effect estimation under network interference.  _The Annals of Statistics_ 50, 4 (2022), 2334 – 2358.  https://doi.org/10.1214/22-AOS2191
  * Liao et al. (2022) Luofeng Liao, Yuan Gao, and Christian Kroer. 2022.  Nonstationary dual averaging and online fair allocation.  _Advances in Neural Information Processing Systems_ 35 (2022), 37159–37172.
  * Liao et al. (2023) Luofeng Liao, Yuan Gao, and Christian Kroer. 2023.  Statistical Inference for Fisher Market Equilibrium. In _The Eleventh International Conference on Learning Representations_.  https://openreview.net/forum?id=KemSBwOYJC
  * Liao and Kroer (2023) Luofeng Liao and Christian Kroer. 2023.  Statistical Inference and A/B Testing for First-Price Pacing Equilibria.  _International Conference on Machine Learning_ (2023).
  * Liao and Kroer (2024) Luofeng Liao and Christian Kroer. 2024.  Bootstrapping Fisher Market Equilibrium and First-Price Pacing Equilibrium.  _arXiv preprint arXiv:2402.02303_ (2024).
  * Liu et al. (2021) Min Liu, Jialiang Mao, and Kang Kang. 2021.  Trustworthy and Powerful Online Marketplace Experimentation with Budget-split Design. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ (Virtual Event, Singapore) _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 3319–3329.  https://doi.org/10.1145/3447548.3467193
  * Rolnick et al. (2019) David Rolnick, Kevin Aydin, Jean Pouget-Abadie, Shahab Kamali, Vahab Mirrokni, and Amir Najmi. 2019.  Randomized experimental design via geographic clustering. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2745–2753.
  * Rosenbaum (2007) Paul R Rosenbaum. 2007.  Interference Between Units in Randomized Experiments.  _J. Amer. Statist. Assoc._ 102, 477 (2007), 191–200.  https://doi.org/10.1198/016214506000001112 arXiv:https://doi.org/10.1198/016214506000001112
  * Shapiro (1988) Alexander Shapiro. 1988.  Sensitivity analysis of nonlinear programs and differentiability properties of metric projections.  _SIAM Journal on Control and Optimization_ 26, 3 (1988), 628–645.
  * Shapiro (1990) Alexander Shapiro. 1990.  On differential stability in stochastic programming.  _Mathematical Programming_ 47 (1990), 107–116.
  * Shapiro et al. (2021) Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. 2021.  _Lectures on stochastic programming: modeling and theory_.  SIAM.
  * Stewart (1977) Gilbert W Stewart. 1977.  On the perturbation of pseudo-inverses, projections and linear least squares problems.  _SIAM review_ 19, 4 (1977), 634–662.
  * Ugander et al. (2013) Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. 2013.  Graph Cluster Randomization: Network Exposure to Multiple Universes. In _Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Chicago, Illinois, USA) _(KDD ’13)_. Association for Computing Machinery, New York, NY, USA, 329–337.  https://doi.org/10.1145/2487575.2487695
  * van der Vaart (2000) Aad W van der Vaart. 2000.  _Asymptotic statistics_. Vol. 3.  Cambridge university press.
  * Viviano et al. (2023) Davide Viviano, Lihua Lei, Guido Imbens, Brian Karrer, Okke Schrijvers, and Liang Shi. 2023.  Causal clustering: design of cluster experiments under network interference.  _arXiv preprint arXiv:2310.14983_ (2023).
  * Wager and Xu (2021) Stefan Wager and Kuang Xu. 2021.  Experimenting in Equilibrium.  _Management Science_ 67, 11 (2021), 6694–6715.  https://doi.org/10.1287/mnsc.2020.3844
  * Zigler and Papadogeorgou (2018) Corwin M. Zigler and Georgia Papadogeorgou. 2018.  Bipartite Causal Inference with Interference.  _arXiv_ 1807.08660v1 (07 2018).  arXiv:1807.08660v1 [stat.ME]

##  Appendix A Technical Lemmas

###  A.1. A perturbation result for constrained stochastic programs

We introduce a theorem from Shapiro (1990). Theorem 1 in that paper handles
the case where the constraints are also defined as expectations of some random
functions, and constraints are also perturbed in the analysis. For simplicity
we specialize the theorem to deterministic constraints and do not perturb
constraints. Note that Theorem 7.27 from Shapiro et al. (2021) can also be
used to prove our Thm. 1.

Let $\Theta$ be a probability space equipped with an appropriate
$\sigma$-algebra. Consider $F:\Theta\times{\mathbb{R}}^{n}\to{\mathbb{R}}$ and
a set $B\subset{\mathbb{R}}^{n}$, given by

$B=\left\\{\beta:g_{i}(\beta)=0,i\in I;g_{i}(\beta)\leq 0,i\in J\right\\}.$

where $I$ and $J$ are finite index sets. Let $P$ and $Q$ be two probability
measures on $\Theta$. Let $\phi(\beta,\alpha)=(P+\alpha(Q-P))F(\cdot,\beta)$
and $\phi(\beta)=\phi(\beta,0)$. Here $\min_{B}\phi$ is the main program of
interest and $Q$ is a perturbation measure. The amount of perturbation is
measured by $\alpha\in[0,1]$.

Let $\beta^{*}$ be the unique minimizer of $\phi(\beta)$ over $B$. Let
$J^{*}\subset J$ be the inequality constraints active at $\beta^{*}$, meaning
$g_{i}(\beta^{*})=0$ for all $i\in J^{*}$. Let $\beta^{*}(\alpha)$ be the
unique optimal solution to $\min_{B}\phi({\cdot},\alpha)$.

###### Lemma 0 (Theorem 1 from Shapiro (1990)).

Define the Lagrangian function by
$L(\beta,\lambda,\alpha)=\phi(\beta,\alpha)+\sum_{i\in I\cup
J}\lambda_{i}g_{i}(\beta)$ and $L_{0}(\beta,\lambda)=L(\beta,\lambda,0)$. Let
$\Lambda_{0}$ be the set of optimal Lagrangian multipliers
111$\lambda\in\Lambda_{0}$ iff
$\nabla_{x}L_{0}\left(\beta_{0},\lambda\right)=0$ and $\lambda_{i}\geq 0,i\in
J^{*}$ and $\lambda_{i}=0$ for all $j\in J\setminus J^{*}$.. Define the
critical cone $C=\\{u:u^{\scriptscriptstyle\mathsf{T}}\nabla
g_{i}(\beta^{*})=0,i\in I;u^{\scriptscriptstyle\mathsf{T}}\nabla
g_{i}(\beta^{*})\leq 0$ for $i\in
J^{*};u^{\scriptscriptstyle\mathsf{T}}\nabla\phi(\beta^{*})\leq 0\\}$. Define
$\Lambda_{0}^{*}=\operatorname*{arg\,max}_{\lambda\in\Lambda_{0}}\sum_{i\in
I\cup J}\lambda_{i}g_{i}(\beta^{*})$. Assume the following conditions.

  1. 1.

Differentiability. The functions $\phi({\cdot},0)$, $\phi({\cdot},1)$, and
$g_{i},i\in I\cup J$, are continuously differentiable in a neighborhood of
$\beta^{*}$.

  2. 2.

Constraint Qualification. The gradients $\nabla g_{i}(\beta^{*})$, $i\in I$
are linearly independent. And there exists $b\in{\mathbb{R}^{n}}$ such that
$b^{\scriptscriptstyle\mathsf{T}}\nabla g_{i}(\beta^{*})=0$ for $i\in I$ and
$b^{\scriptscriptstyle\mathsf{T}}\nabla g_{i}(\beta^{*})<0$ for $i\in J^{*}$.

  3. 3.

Differentiability. The functions $\phi({\cdot},0)$, $g_{i}$, $i\in I\cup
J^{*}$ are twice continuously differentiable in a neighbourhood of
$\beta^{*}$.

  4. 4.

Second-order sufficient condition. Assume for all nonzero $u\in C$,
$\max_{\lambda\in\Lambda_{0}^{*}}u^{\scriptscriptstyle\mathsf{T}}\nabla^{2}_{xx}L_{0}(\beta^{*},\lambda)u>0$.

Define the function $b$ and the set $\Sigma$ by

(12) $\displaystyle b(u)$
$\displaystyle=\max_{\lambda\in\Lambda_{0}^{*}}u^{\scriptscriptstyle\mathsf{T}}\nabla^{2}_{xt}L_{0}(\beta^{*},\lambda)+\frac{1}{2}u^{\scriptscriptstyle\mathsf{T}}\nabla^{2}_{xx}L_{0}(\beta^{*},\lambda)u$
(13) $\displaystyle\Sigma$
$\displaystyle=\operatorname*{arg\,min}u^{\scriptscriptstyle\mathsf{T}}\nabla\phi(\beta^{*})$
$\displaystyle\mathrm{s.t.}\quad u^{\scriptscriptstyle\mathsf{T}}\nabla
g_{i}(\beta^{*})=0,i\in I;u^{\scriptscriptstyle\mathsf{T}}\nabla
g_{i}(\beta^{*})\leq 0,i\in J^{*};$

Then (i) there exists a positive $K$ such that
$\|\beta^{*}(\alpha)-\beta^{*}\|\leq K\alpha$ for all positive $\alpha$ in a
neighborhood of zero. (ii) If, in addition, the function $b$ has a unique
minimizer $u$ over $\Sigma$, then the limit $\lim_{\alpha\downarrow
0}(\beta^{*}(\alpha)-\beta^{*})/\alpha$ exists and equals to $u$.

##  Appendix B Proofs

###  B.1. Proof of Closed-Form Expression for
$\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)$ and Thm. 1

Now we prove Thm. 1.

To begin with, we define directional derivatives. For a probability measure
$P$ on the item set $\Theta$, let $\beta(P)$ be the unique optimal solution to
the Eisenberg-Gale program: $\beta(P)=\min_{\beta\in(0,1]^{n}}\int
F(\theta,\beta)\mathop{}\\!\mathrm{d}P(\theta)$. Let $P$ and $Q$ be two
measures. When exists, the directional derivative is defined as

$\displaystyle\mathop{}\\!\mathrm{d}\beta(P;Q-P)=\lim_{t\downarrow
0}\frac{\beta(P+t(Q-P))-\beta(P)}{t}.$

Step 1. Show there exist $K>0$ and $\bar{\alpha}_{1}>0$ such that
$\|\beta^{*}_{\alpha}-\beta^{*}\|\leq K\alpha$ for
$\alpha\in[0,\bar{\alpha}_{1}]$. And
$\mathop{}\\!\mathrm{d}\beta(s;s-s^{\prime})=-(P{\mathscr{H}}_{0}P)^{\dagger}\Delta_{0}$.

We apply Lemma 1 with
$F(\theta,\beta)=\max_{i}{v_{i}(\theta)}{\beta_{i}}-\sum_{i}b_{i}\log({\beta_{i}})$,
$g_{i}(\beta)={\beta_{i}}-1$, $B=(0,1]^{n}$,
$\mathop{}\\!\mathrm{d}P=s\mathop{}\\!\mathrm{d}\theta$,
$\mathop{}\\!\mathrm{d}(Q-P)=(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta$.

By Definition 3 (SCS). in the market ${\mathscr{M}}_{0}$, the set $\Sigma$
(defined in Eq. 13) becomes the plane $\\{u:u_{i}=0,i\in I_{+}\\}$ where we
recall $I_{+}=\\{i:{\beta^{*}_{i}}=0\\}$. By Definition 2 (SMO). in
${\mathscr{M}}_{0}$, we know the Lagrangian multiplier of the EG program in
${\mathscr{M}}_{0}$ is unique, and thus $b({\cdot})$ defined in Eq. 12 becomes
$b(u)=u^{\scriptscriptstyle\mathsf{T}}\Delta_{0}+\frac{1}{2}u^{\scriptscriptstyle\mathsf{T}}{\mathscr{H}}_{0}u$.
We conclude the directional derivative is
$\mathop{}\\!\mathrm{d}\beta(s;s-s^{\prime})=\lim_{\delta\to
0^{+}}(\beta^{*}_{0}-\beta^{*}_{-\delta})/\delta=-(P{\mathscr{H}}_{0}P)^{\dagger}\Delta_{0}$,
where $P={\operatorname*{Diag}}(1({\beta^{*}_{i}}<1))$ and
$\Delta_{0}=\int\nabla
f({\cdot},\beta^{*})(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta$

Step 2. For all $\alpha\geq 0$ small enough, it holds $I_{\alpha}=I$, where we
recall $I_{\alpha}=\\{i:\beta^{*}_{\alpha,i}=1\\}$ and
$I=\\{i:{\beta^{*}_{i}}=0\\}$.

First we show $I\subseteq I_{\alpha}$, i.e.,
$\\{i:{\beta^{*}_{i}}=1\\}\subseteq\\{i:\beta^{*}_{\alpha,i}=1\\}$ for
$\alpha$ small enough. This is saying, if a constraint ${\beta_{i}}\leq 1$ is
strongly active in the EG program of ${\mathscr{M}}_{0}$, then it is also
strongly active in the EG program of the market ${\mathscr{M}}_{\alpha}$. This
holds by Lemma 2.2 from Shapiro (1988) and the Definition 3 (SCS). condition
in ${\mathscr{M}}_{0}$. Next, we show, for small $\alpha$,
$I_{\alpha}\subseteq I$ by showing $[n]\setminus I\subseteq[n]\setminus
I_{\alpha}$, i.e.,
$\\{i:{\beta^{*}_{i}}<1\\}\subseteq\\{i:\beta^{*}_{\alpha,i}<1\\}$. This holds
by $\|\beta^{*}_{\alpha}-\beta^{*}\|\leq K\alpha$ for all
$\alpha\leq\bar{\alpha}_{1}$.

Step 3. For all $\alpha\geq 0$ small enough, the directional derivative
$\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})=\lim_{\delta\to
0^{+}}(\beta^{*}_{\alpha-\delta}-\beta^{*}_{\alpha})/\delta$ exists and
$\alpha\mapsto\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})$ is
continuous.

Applying Lemma 1 with
$\mathop{}\\!\mathrm{d}P=s_{\alpha}\mathop{}\\!\mathrm{d}\theta$ and
$\mathop{}\\!\mathrm{d}(Q-P)=(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta$ shows
that the directional derivative exists for all $\alpha$ small enough. Now we
find an expression for $\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})$.
By Definition 2 (SMO). in ${\mathscr{M}}_{0}$, twice continuously
differentiability of $\beta\mapsto\nabla^{2}\int
F(\beta,\theta)s^{\prime}\mathop{}\\!\mathrm{d}\theta$ in a neighborhood of
$\beta^{*}$, and the Lipschitzness result from step 1, we know
$\beta\to\nabla^{2}\int F(\theta,\beta)s_{\alpha}\mathop{}\\!\mathrm{d}\theta$
is twice continuously differentiable at $\beta^{*}_{\alpha}$, which implies
uniqueness of Lagrangian multiplier in the market ${\mathscr{M}}_{\alpha}$,
for all $\alpha$ small enough (Lemma 2.2 from Shapiro (1988)). And thus
$b({\cdot})$ defined in Eq. 12 becomes
$b(u)=u^{\scriptscriptstyle\mathsf{T}}\Delta_{\alpha}+\frac{1}{2}u^{\scriptscriptstyle\mathsf{T}}{\mathscr{H}}_{\alpha}u$.
Next, the Definition 3 (SCS). condition in the market ${\mathscr{M}}_{0}$
implies SCS in ${\mathscr{M}}_{\alpha}$ for all $\alpha$ small enough. The set
$\Sigma$ (defined in Eq. 13) becomes the plane $\\{u:u_{i}=0,i\in
I_{\alpha}\\}$. The quadratic program $\min_{\Sigma}b$ has a closed-form
solution:
$u=-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\Delta_{\alpha}$
where $P_{\alpha}={\operatorname*{Diag}}(1(\beta^{*}_{\alpha,i}<1))$,
$\Delta_{\alpha}=\int\nabla
f({\cdot},\beta^{*}_{\alpha})(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta$. And
we apply $I_{\alpha}=I$ for all $\alpha$ small enough from step 2, and so
$P_{\alpha}=P$. We conclude

$\displaystyle\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})=-(P{\mathscr{H}}_{\alpha}P)^{\dagger}\Delta_{\alpha}$

for all $\alpha$ small enough.

Next, we show that the map
$\alpha\mapsto(P{\mathscr{H}}_{\alpha}P)^{\dagger}\Delta_{\alpha}$ is
continuous for all $\alpha$ small enough. To see this, note
${\mathscr{H}}_{\alpha}=\nabla^{2}\int
F(\theta,\beta^{*}_{\alpha})s_{\alpha}\mathop{}\\!\mathrm{d}\theta=(1-\alpha)\nabla^{2}\int
F({\cdot},\beta^{*}_{\alpha})s\mathop{}\\!\mathrm{d}\theta+\alpha\nabla^{2}\int
F({\cdot},\beta^{*}_{\alpha})s^{\prime}\mathop{}\\!\mathrm{d}\theta$ is
continuous in $\alpha$. The $P$ matrix is fixed, and so $\alpha\mapsto
P{\mathscr{H}}_{\alpha}P$ is continuous. Without loss of generality, suppose
${I^{c}}=\\{i:{\beta^{*}_{i}}<0\\}=[k]$ are the first $k$ buyers. Then
$P{\mathscr{H}}_{\alpha}P$ creates a matrix with upper left $k$-by-$k$ block
equal to the upper left $k$-by-$k$ block of ${\mathscr{H}}_{\alpha}$, denoted
${\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}}$, and zeros everywhere else. Then
$(P{\mathscr{H}}_{\alpha}P)^{\dagger}$ is a matrix with upper left block being
$({\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}})^{{-1}}$ and zeros everywhere else.
Since ${\mathscr{H}}_{\alpha}$ is positive definite for all small $\alpha$,
the submatrix ${\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}}$ must also be positive
definite. And so $\alpha\mapsto({\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}})^{{-1}}$
is continuous, implying continuity of
$\alpha\mapsto(P{\mathscr{H}}_{\alpha}P)^{\dagger}$. Finally,
$\Delta_{\alpha}=\int\nabla
f({\cdot},\beta^{*}_{\alpha})(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta$ is
continuous in $\alpha$.

Step 4. The desired claim: $\widetilde{\beta}^{*}-\beta^{*}=o(\alpha)$. Note
$\mathop{}\\!\mathrm{d}\beta^{*}(\alpha)$ defined in Eq. 6 is exactly
$\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})$. And so

$\displaystyle\widetilde{\beta}^{*}-\beta^{*}$
$\displaystyle=\beta^{*}_{\alpha}+\alpha\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})-\beta^{*}$
$\displaystyle=(\beta^{*}-\alpha\mathop{}\\!\mathrm{d}\beta(s_{0};s-s^{\prime})+o(\alpha))+\alpha\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})-\beta^{*}$
$\displaystyle=\alpha(\mathop{}\\!\mathrm{d}\beta(s_{\alpha};s-s^{\prime})-\mathop{}\\!\mathrm{d}\beta(s_{0};s-s^{\prime}))+o(\alpha)=o(\alpha).$

where the last line uses continuity in $\alpha$ of the directional derivative.
This completes the proof of Thm. 1.

###  B.2. Proof of Thm. 2

Recall the estimator
$\widehat{\beta}=\beta^{\gamma}_{\alpha}-\alpha(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}\widehat{\Delta}_{\alpha}$
and the debiased surrogate is
$\widetilde{\beta}^{*}=\beta^{*}_{\alpha}-\alpha(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\Delta_{\alpha}$.
By results from Liao and Kroer (2023) we know that Definition 3 (SCS). and
Definition 2 (SMO). in the market ${\mathscr{M}}_{\alpha}$ and $\eta_{t}=o(1)$
imply $\beta^{\gamma}_{\alpha}{\,\overset{{p}}{\to}\,}\beta^{*}_{\alpha}$ and
$(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}{\,\overset{{p}}{\to}\,}(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}$.
Finally, $\widehat{\Delta}_{\alpha}{\,\overset{{p}}{\to}\,}\Delta_{\alpha}$
holds by the law of large numbers. We complete the proof of Thm. 2.

###  B.3. Proof of Thm. 3

Recall the estimator
$\widehat{\beta}=\beta^{\gamma}_{\alpha}-\alpha(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}\widehat{\Delta}_{\alpha}$
and the debiased surrogate is
$\widetilde{\beta}^{*}=\beta^{*}_{\alpha}-\alpha(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\Delta_{\alpha}$.
Define

(14) $\displaystyle
Z_{t}=\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha}-\alpha(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}(\widehat{\Delta}_{\alpha}-\Delta_{\alpha})$
(15)
$\displaystyle\mho_{t}=-\alpha((\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger})\Delta_{\alpha}$
(16)
$\displaystyle\zeta_{t}=-\alpha((\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger})(\widehat{\Delta}_{\alpha}-\Delta_{\alpha})$

Then clearly $\widehat{\beta}-\widetilde{\beta}^{*}=Z_{t}+\mho_{t}+\zeta_{t}$.

Step 1. We show $\sqrt{t}Z_{t}$ converges to a normal distribution. By Liao
and Kroer (2023), it holds

(17)
$\displaystyle\sqrt{t}(\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha})=\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}D_{\alpha}({\theta^{\tau}})-{\mathbb{E}}[D_{\alpha}]+o_{p}(1)$

where
$D_{\alpha}(\theta)=-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\nabla
f(\theta,\beta^{*}_{\alpha})$ is the influence function. Next, we define the
likelihood ratio function
$g(\theta)=(\mathop{}\\!\mathrm{d}(s-s^{\prime})/\mathop{}\\!\mathrm{d}s_{\alpha})(\theta)=-\frac{1}{\alpha}1_{\Theta_{\mathsf{bad}}}(\theta)+\frac{1}{1-\alpha}1_{\Theta_{\mathsf{good}}}(\theta)$.
Then $\Delta_{\alpha}=\int\nabla
f({\cdot},\beta^{*}_{\alpha})(s-s^{\prime})\mathop{}\\!\mathrm{d}\theta=\int
g({\cdot})\nabla
f({\cdot},\beta^{*}_{\alpha})s_{\alpha}({\cdot})\mathop{}\\!\mathrm{d}\theta$.
Then by definition $\widehat{\Delta}_{\alpha}$ can be written as
$\widehat{\Delta}_{\alpha}=P_{t}(g({\cdot})\nabla
f({\cdot},\beta^{\gamma}_{\alpha}))$ where
$P_{t}h({\cdot})=\frac{1}{t}{\sum_{\tau=1}^{t}}h({\theta^{\tau}})$ and
${\theta^{\tau}}$ are i.i.d. draws from $s_{\alpha}$. Also let
$\nu_{t}h=\sqrt{t}(P_{t}h-\int hs_{\alpha}\mathop{}\\!\mathrm{d}\theta)$. By
the decomposition,

(18) $\displaystyle\sqrt{t}(\widehat{\Delta}_{\alpha}-\Delta_{\alpha})$ (19)
$\displaystyle=$ $\displaystyle\sqrt{t}\bigg{(}P_{t}\big{(}g({\cdot})\nabla
f({\cdot},\beta^{\gamma}_{\alpha})\big{)}-\int g({\cdot})\nabla
f({\cdot},\beta^{*}_{\alpha})s_{\alpha}\mathop{}\\!\mathrm{d}\theta\bigg{)}$
(20) $\displaystyle=$
$\displaystyle\sqrt{t}\bigg{(}P_{t}\big{(}g({\cdot})\nabla
f({\cdot},\beta^{*}_{\alpha})\big{)}-\int g({\cdot})\nabla
f({\cdot},\beta^{*}_{\alpha})s_{\alpha}\mathop{}\\!\mathrm{d}\theta\bigg{)}+\nu_{t}\big{(}g({\cdot})(\nabla
f({\cdot},\beta^{\gamma}_{\alpha})-\nabla
f({\cdot},\beta^{*}_{\alpha}))\big{)}$ (21) $\displaystyle=$
$\displaystyle\nu_{t}(g({\cdot})\nabla
f({\cdot},\beta^{*}_{\alpha}))+o_{p}(1),$

where the last line follows by a stochastic equicontinuity argument as in Liao
and Kroer (2023). Finally, $D_{\alpha}({\cdot})-\alpha
g({\cdot})(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}\nabla
f({\cdot},\beta^{*}_{\alpha})$ is exactly the influence function
$IF_{1}({\cdot})$ defined in the theorem.

Step 2. Show $\mho_{t}=O_{p}(\eta_{t})$.

We need a matrix perturbation result.

###### Lemma 0 (Theorem 2.2 from Stewart (1977)).

Let $A$ and $B=A+E$ be nonsingular square matrices, and $\|A^{{-1}}\|\|E\|<1$.
Here $\|{\cdot}\|$ is the operator norm. Then

(22)
$\displaystyle\|B^{{-1}}-A^{{-1}}\|\leq\frac{\|A^{{-1}}\|^{2}}{1-\|E\|\|A^{{-1}}\|}\|E\|.$

By Liao and Kroer (2023), we know
${\mathbb{P}}(\widehat{P}_{\alpha}=P_{\alpha})\to 1$. Without loss of
generality, suppose $I^{c}_{\alpha}=\\{i:\beta^{*}_{\alpha,i}<0\\}=[k]$ are
the first $k$ buyers. Then $(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})$
creates a matrix with upper left $k$-by-$k$ block equal to the upper left
$k$-by-$k$ block of ${\mathscr{H}}_{\alpha}$, denoted
${\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}}$, and zeros everywhere else. Under the
event $\\{\widehat{P}_{\alpha}=P_{\alpha}\\}$, the matrix
$(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})$ is
one with upper left $k$-by-$k$ block being upper left $k$-by-$k$ block of
$\widehat{\mathscr{H}}_{\alpha}$, denoted
$\widehat{\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}}$, and zeros everywhere else.
Now let $A=\widehat{\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}}$ and
$B={\mathscr{H}}_{\alpha,{I^{c}}{I^{c}}}$. It is clear that
$\|\mho_{t}\|_{2}\leq\alpha\|\Delta_{\alpha}\|_{2}\|A^{{-1}}-B^{{-1}}\|=O_{p}(\eta_{t})$
by Lemma 1.

Step 3. Show $\zeta_{t}=o_{p}(\frac{1}{\sqrt{t}})$. From previous derivation,
$\widehat{\Delta}_{\alpha}-\Delta_{\alpha}=O_{p}(1/\sqrt{t})$ and
$(\widehat{P}_{\alpha}\widehat{\mathscr{H}}_{\alpha}\widehat{P}_{\alpha})^{\dagger}-(P_{\alpha}{\mathscr{H}}_{\alpha}P_{\alpha})^{\dagger}=O_{p}(\eta_{t})=o_{p}(1)$.
We conclude $\zeta_{t}=O_{p}(1/\sqrt{t})o_{p}(1)=o_{p}(1/\sqrt{t})$.

We complete the proof of Thm. 3 part 1.

Now we prove part 2. The claim that
${\mathscr{H}}_{\alpha}={\operatorname*{Diag}}(b_{i}/(\beta^{*}_{\alpha,i})^{2})$
follows from Liao et al. (2023). Next we derive the asymptotic distribution.
We only need to handle the $\mho_{t}$ term defined as before. Under the event
$\\{\widehat{P}_{\alpha}=P_{\alpha}\\}$, we have
$\mho_{t}=-{\operatorname*{Diag}}(\alpha\Delta_{\alpha,i}1(\beta^{*}_{\alpha,i}<1)b_{i}^{{-1}})(\beta^{\gamma}_{\alpha}\circ\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha}\circ\beta^{*}_{\alpha})$.
By Liao and Kroer (2023) we know
$\sqrt{t}(\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha})=\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}(D_{\alpha}({\theta^{\tau}})-{\mathbb{E}}_{\alpha}[D_{\alpha}])+o_{p}(1)$.
So by the delta method,

$\displaystyle\sqrt{t}(\beta^{\gamma}_{\alpha}\circ\beta^{\gamma}_{\alpha}-\beta^{*}_{\alpha}\circ\beta^{*}_{\alpha})={\operatorname*{Diag}}(2\beta^{*}_{\alpha})\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}(D_{\alpha}({\theta^{\tau}})-{\mathbb{E}}_{\alpha}[D_{\alpha}])+o_{p}(1).$

Summarizing,

$\displaystyle\sqrt{t}\mho_{t}=-{\operatorname*{Diag}}(2\beta^{*}_{\alpha,i}\alpha\Delta_{\alpha,i}1(\beta^{*}_{\alpha,i}<1)b_{i}^{{-1}})\frac{1}{\sqrt{t}}{\sum_{\tau=1}^{t}}(D_{\alpha}({\theta^{\tau}})-{\mathbb{E}}_{\alpha}[D_{\alpha}])+o_{p}(1)$

Note that for $i$ such that $\beta^{*}_{\alpha,i}=1$, the $i$-th entry of
$D_{\alpha}$ will be zero almost surely, so the indicator can be dropped in
the diagonal matrix. Now let
$IF_{2}(\theta)=-{\operatorname*{Diag}}(2\alpha\beta^{*}_{\alpha,i}\Delta_{\alpha,i}b_{i}^{{-1}})D_{\alpha}+IF_{1}$,
where we recall $IF_{1}$ is defined in Thm. 3. Then under the condition that
${\mathbb{E}}_{\alpha}[\frac{1}{{\mathsf{{bidgap}}}(\beta^{*}_{\alpha},\theta)}]<\infty$,
we have
$\sqrt{t}(\widehat{\beta}-\widetilde{\beta}^{*}){\,\overset{{d}}{\to}\,}{\mathscr{N}}(0,{\mathbb{E}}_{\alpha}[(IF_{2}-{\mathbb{E}}_{\alpha}[IF_{2}])(IF_{2}-{\mathbb{E}}_{\alpha}[IF_{2}])^{\scriptscriptstyle\mathsf{T}}])$.

###  B.4. Proof of Thm. 4

###### Proof.

Note

$\displaystyle\bigg{|}\int\max_{i}({v_{i}(\theta)}\widetilde{\beta}^{*}_{i})s(\theta)\mathop{}\\!\mathrm{d}\theta-\int\max_{i}({v_{i}(\theta)}\beta^{*}_{i})s(\theta)\mathop{}\\!\mathrm{d}\theta\bigg{|}$
$\displaystyle\leq\int|\max_{i}({v_{i}(\theta)}\widetilde{\beta}^{*}_{i})s(\theta)-\max_{i}({v_{i}(\theta)}\beta^{*}_{i})s(\theta)|\mathop{}\\!\mathrm{d}\theta$
$\displaystyle\leq\max_{i}\sup_{\theta}v_{i}(\theta)\cdot\|\beta^{*}-\widetilde{\beta}^{*}\|_{\infty}=o(\alpha)$

as $\alpha\downarrow 0$.

Let $P_{t}h({\cdot})=\frac{1}{t}{\sum_{\tau=1}^{t}}h({\theta^{\tau}})$ and
${\theta^{\tau}}$ are i.i.d. draws from $s_{\alpha}$, and $Ph({\cdot})=\int
hs_{\alpha}$. Let
$g({\cdot})=\mathop{}\\!\mathrm{d}s/\mathop{}\\!\mathrm{d}s_{\alpha}=\frac{1}{1-\alpha}1_{\Theta_{\mathsf{good}}}$.
Also let $\nu_{t}h=\sqrt{t}(P_{t}h-\int
hs_{\alpha}\mathop{}\\!\mathrm{d}\theta)$. We change the measure and write
$\widetilde{{\mathsf{{REV}}}}^{*}=\int
f(\theta,\widetilde{\beta}^{*})s\mathop{}\\!\mathrm{d}\theta=\int
f(\theta,\widetilde{\beta}^{*})g(\theta)s_{\alpha}\mathop{}\\!\mathrm{d}\theta$.
For the claim regarding asymptotic normality, note

$\displaystyle\sqrt{t}(\widehat{{\mathsf{{REV}}}}-\widetilde{{\mathsf{{REV}}}}^{*})$
$\displaystyle=\sqrt{t}[P_{t}f({\cdot},\widehat{\beta})g({\cdot})-Pf({\cdot},\widetilde{\beta}^{*})g({\cdot})]$
$\displaystyle=\sqrt{t}[P_{t}f({\cdot},\widetilde{\beta}^{*})g({\cdot})-Pf({\cdot},\widetilde{\beta}^{*})g({\cdot})]+\sqrt{t}[Pf({\cdot},\widehat{\beta})g({\cdot})-Pf({\cdot},\widetilde{\beta}^{*})g({\cdot})]$
$\displaystyle\quad+\sqrt{t}(P_{t}-P)(f({\cdot},\widehat{\beta})g({\cdot})-f({\cdot},\widetilde{\beta}^{*})g({\cdot}))$
$\displaystyle=\nu_{t}(f({\cdot},\widetilde{\beta}^{*})g({\cdot}))+\nu_{t}({\mathbb{E}}_{\alpha}[g({\cdot})\nabla
f({\cdot},\widetilde{\beta}^{*})]^{\scriptscriptstyle\mathsf{T}}IF({\cdot}))+o_{p}(1)$

where the last line follows by the delta method and a stochastic
equicontinuity argument. We complete the proof of the theorem. ∎