Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
56,091 characters · 17 sections · 65 citation commands
Bootstrapping Fisher Market Equilibrium and First-Price Pacing Equilibrium
\twocolumn[ \icmltitle{Bootstrapping Fisher Market Equilibrium and First-Price Pacing Equilibrium}
\icmlsetsymbol{equal}{*}
\icmlaffiliation{sch}{IEOR, Columbia University}
\icmlcorrespondingauthor{Luofeng Liao}{[email removed]}
\icmlkeywords{First-price auction, pacing equilibria}
\vskip 0.3in ]
\printAffiliationsAndNotice
The bootstrap efron1994introduction,horowitz2001bootstrap is an automatic method for producing confidence intervals in statistical estimation. The theory of bootstrap has been extended to many areas of statistics, such as models with cube-root asymptotics cattaneo2020bootstrap,patra2018consistent, semi-parametric models cheng2010bootstrap,ma2005robust and so on. However, as far as we are concerned, there is no theory of bootstrap for competitive equilibrium settings.
In this paper, we study bootstrap inference in linear Fisher market (LFM) and first-price pacing equilibrium (FPPE). Fisher market equilibrium model has been used in the tech industry, such as the allocation of impressions to content in certain recommender systems robust_blog, robust and fair work allocation in content review allouah2022robust; we refer readers to kroer2022market for a comprehensive review. Outside the tech industry, Fisher market equilibria also have applications to scheduling problems im2017competitive, fair course seat allocation othman2010finding,budish2016course, allocating donations to food banks aleksandrov2015online, sharing scarce compute resources ghodsi2011dominant,parkes2015beyond,kash2014no,devanur2018new, and allocating blood donations to blood banks mcelfresh2020matching.
FPPE is a model for budget management in online advertising platforms. In these platforms, advertisers report advertising parameters, such as target audience, conversion locations, and budgets, and then the platform creates a proxy bidder to bid in individual auctions to maximize advertiser utilities and manage budgets. A common way to manage budgets is pacing, in which the platform modifies the advertiser's bids by applying a shading factor, referred to as multiplicative pacing. In the case where each auction is a first-price auction, FPPE captures the outcomes of pacing-based budget-management systems. conitzer2022pacing introduced the FPPE notion and showed that FPPE always exists and is unique. Moreover, FPPE enjoys lots of nice properties such as being revenue-maximizing among all budget-feasible pacing strategies, shill-proof (the platform does not benefit from adding fake bids under first-price auction mechanism) and revenue-monotone (revenue weakly increases when adding bidders, items or budget).
Given the wide range of applications of LFM and FPPE, an inferential theory for LFM and FPPE is useful. Bootstrap, thanks to its convenience and conceptual simplicity, is a natural candidate as an inferential tool. However, due to the presence of an equilibrium structure in the dataset, the validity of bootstrap requires careful theoretical treatments, and practitioners should be cautious about the use of bootstrap when data arise from market equilibrium. For example, in (ref) we show that in the setting of first-price auction platforms, the traditional multinomial bootstrap may fail to consistently estimate the distribution of interest. Given the simplicity of resampling, it is fair to say bootstrap has been used in auction platforms as an inferential tool. It is thus urgent to develop a statistically valid bootstrap theory that accounts for the equilibrium effect in the data.
Our contributions are threefold.
We characterize the full landscape of the asymptotics of FPPE. The limit distribution of FPPE was studied in liao2023stat under a strict complementarity condition. Combining their results with a result of shapiro1989asymptotic, we complete the characterization of the asymptotics of FPPE without strict complementarity, and show that it is captured by a quadratic program. We derive a new closed-form expression for this quadratic program, and use it to derive structural insights on the limit distribution in some special cases. Characterizing the general case of FPPE asymptotics is necessary in order to derive our bootstrap results, because we need to show that our bootstrapped distribution converges to the asymptotic distribution of FPPE.
We develop bootstrap theory for LFM and FPPE. A crucial fact for LFM and FPPE is that they both have an Eisenberg-Gale (EG) convex program characterization, and our bootstrap procedures rely on this program or its quadratic approximation. For LFM we study three types of bootstrap procedures: exchangeable bootstrap wellner1996bootstrapping, numerical bootstrap li2020numerical and proximal bootstrap li2020numerical. For FPPE the theory is a bit involved. We identify a bootstrap failure when some type of degenerate buyers are present in the market. Then different bootstrap procedures are proposed under certain assumptions on the market structures: full expenditure of budgets ($I_{=>}= \emptyset$), absence of degenerate buyers ($I_{==} =\emptyset$), or fully general FPPE. We summarize the results in (ref).
Numerical experiments demonstrate the validity of the theory. We provide simulations and a semi-synthetic experiment based on a real-time bidding dataset from iPinYou liao2014ipinyou.
Notations. The notation ${\mathcal{N}}(a,\Sigma)$ stands for a multivariate Gaussian distribution with mean $a$ and covariance $\Sigma$.
We use $W = (W_1,\dots, W_t)$ to denote bootstrap weights in the paper. Different distributions imposed on $W$ correspond to different bootstrap resampling schemes. In the standard multinomial bootstrap $W = (W_1,\dots, W_t)$ follows a multinomial with probabilities $(\frac1t, \dots, \frac1t)$. In exchangeable bootstrap $W$ is exchangeable: if for any permutation $\pi=\left(\pi_1, \ldots, \pi_t\right)$ of $(1,2, \ldots, t)$, the joint distribution of $\pi\left(W\right)=$ $\left(W_{ \pi_1}, \ldots, W_{ \pi_t}\right)$ is the same as that of $W$. Given items $({ \theta^\tau })_\tau$, we let $P_t$ be the expectation operator $P_t f =\frac1t {\sum_{\tau=1}^{t}} f({ \theta^\tau }) $. Given multinomial bootstrap weights $W$ and $({ \theta^\tau })_\tau$, define the operator
We write ${P^{\mathsf{ex}, b}_t} f = \frac1t {\sum_{\tau=1}^{t}} W_\tau f({ \theta^\tau })$ for exchangeable bootstrap weights.
\paragraph{Bootstrap Consistency}
Most of our results will be concerned with the consistency of bootstrap procedures. To that end, we introduce the following definition of consistency. Given $t$ data points, a bootstrap estimate $X_t$ is a function of the data $({ \theta^\tau })_{\tau=1}^t $ and bootstrap weights $W$, where the data and weights are assumed to be independent of each other. We say the conditional distribution of $(X_t)_t$ consistently estimates the distribution $L$, denoted $X_t \,{\stackrel{p}{\rightsquigarrow}}\, L$, if
where $\mathrm{BL}_1$ is the space of functions $f: {\mathbb R^n} \to {\mathbb R}$ with $\sup_{x} |f(x)| \leq 1$ and $|f(x) - f(y) | \leq \|x-y\|_2$.
We survey related work in (ref).
Both LFM and FPPE have a set of buyers and a set of items being priced. Here we introduce some components that both models share. We have $n$ buyers and a possibly continuous set of items $\Theta$ with {an} integrating measure $\mathop{}\!\mathrm{d} \theta$. For example, $\Theta = [0,1]$ with $\mathop{}\!\mathrm{d} \theta$ being the Lebesgue measure on $[0,1]$. Both LFM and FPPE require the following elements.
Equilibria in both LFM and FPPE are characterized by an EG convex program. In both cases, the dual EG objective separates into per-item convex terms
and the population and sample EG objectives are
We comment on the differential structure of $f(\theta, \beta )=\max_i {\beta_i}{ v_i(\theta) }$ since it plays a role in later sections. 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$ is differentiable. In that case, the $i$-th entry of $\nabla_ \beta f(\theta, \beta )$ is $v_i(\theta)$ for $i=i^*$ and zero otherwise.
In the LFM model, the goal is to divide items $\Theta$ in a fair and efficient way. It is well known that the competitive equilibrium from equal incomes (CEEI) mechanism produces an allocation that is Pareto efficient, envy-free and proportional nisan2007algorithmic. LFM is also a useful tool for modeling competition in an economy.
We now describe the competitive equilibrium concept. Imagine there is a central policymaker that sets prices $p(\cdot)$ for the items $\Theta$. Upon observing the prices, the buyer $i$ maximizes their utility subject to the budget constraint. Their demand set is the set of bundles that are optimal under the prices: \[ D_i (p) := \operatorname*{arg\,max}_{x_i \in L^\infty_+(\Theta)} \bigg\{ \int v_i x_i s \mathop{}\!\mathrm{d} \theta : \int p x_i s\mathop{}\!\mathrm{d} \theta \leq b_i\bigg\} \; .\] Note that the demand set allows $x_i$ to take values greater than one.
Of course, due to the supply constraint, if prices are too low, there will be a supply shortage. On the other hand, if prices are too high, a surplus occurs. A competitive equilibrium is a set of prices and bundles such that all items are sold exactly at their supply (or have price zero). We call such an equilibrium the limit LFM equilibrium for the supply function $s$ gao2022infinite,liao2023fisher.
Given the equilibrium quantities $(x^*, p^*)$, let ${ u^*_i } = \int {v_i} s {x^*_i} \mathop{}\!\mathrm{d} \theta$ be the buyer $i$ utility, and ${\beta^*_i} = b_i / { u^*_i }$ be the buyer $i$ inverse bang-per-buck. In an LFM, the equilibrium quantities $p^*,\beta^*,{ u^* }$ are unique. Under twice differentiability (\nameref{as:twice_diff}; to be defined), the allocation $x^*$ is also unique.
Next we introduce the finite LFM, which models the data we observe in a market. Let ${ \gamma } = \{ \theta^1,\dots, \theta^t\}$ be $t$ i.i.d. samples from the supply distribution $s$, each with supply $1/t$. See (ref) for a full definition. For a finite LFM, let the equilibrium per-buyer inverse bang-per-bucks be denoted by $\beta^\gamma$.
It is well-known eisenberg1959consensus,gao2022infinite that the equilibrium inverse bang-per-buck $\beta^*$ in an limit (resp.\ finite) LFM uniquely solves the population (resp.\ sample) dual EG program
The asymptotics of LFM were studied in liao2023fisher under twice differentiability (\nameref{as:twice_diff}; to be defined). Let ${\mathscr{H}} = \nabla ^{2} H (\beta^*)$. They show $\sqrt t (\beta^\gamma - \beta^*) { \,\overset{{d}}{\to} \,} {\mathscr{J}}_{ \mathsf{{LFM}}}$, where
The FPPE setting conitzer2022pacing models an economy that typically occurs on internet advertising platforms: the buyers (advertisers in the internet advertising setting) are subject to budget constraints, and must participate in a set of first-price auctions, each of which sells a single item. Each buyer chooses a pacing multiplier $\beta_i \in [0,1]$ that scales down their bids in the auctions, and submits bids of the form $\beta_i v_i(\theta)$ for each item $\theta$, with the goal of choosing $\beta_i$ such that there is no unnecessary pacing, i.e. they spend their budget exactly, or they spend less than their budget but they do not scale down their bids. In the FPPE model, all auctions occur simultaneously, and thus the buyers choose a single $\beta_i$ that determines their bid in all auctions.
FPPE is a hindsight and static solution concept for internet ad auctions. Suppose we know all the items that are going to show up on a platform. FPPE describes how we could configure the ${\beta_i}$'s in a way that ensures that all buyers satisfy their budgets, while maintaining their expressed valuation ratios between items. Typically, the ${\beta_i}$'s are chosen by a pacing algorithm that is run by the platform. FPPE has many nice properties, such as the fact that it is a competitive equilibrium, it is revenue-maximizing, revenue-monotone, shill-proof, has a unique set of prices, and so on conitzer2022pacing. We refer readers to conitzer2022pacing,liao2023stat for more context about the use of FPPE in internet ad auctions.
Let $\beta^*$ and $p^*$ be the unique FPPE equilibrium multipliers and prices. Revenue in the limit FPPE is $ {\small \textsc{{REV}} }^* = \int p^*(\theta) s(\theta)\mathop{}\!\mathrm{d} \theta \; . $ We let the leftover budget be denoted by ${\delta^*_i} = b_i - { \small \textsf{{pay}}}_i$. We say a buyer $i$ is degenerate if ${\beta^*_i} = 1$ and ${\delta^*_i} = 0$.
In FPPE the following regularity condition is important.
This assumption is a strict complementary slackness condition since ${\delta^*_i}$ is the dual variable of ${\beta^*_i}$ in the EG program introduced below. We will study the asymptotics of FPPE without \nameref{as:constraint_qualification}. However, as we will see in (ref), condition \nameref{as:constraint_qualification} is helpful for bootstrap inference.
We let ${ \gamma } = \{ \theta^1,\dots, \theta^t\}$ be $t$ i.i.d.\ draws from $s$, each with supply $1/t $. They represent the items observed in an auction market. The definition of a finite FPPE is parallel to that of a limit FPPE, except that we change the supply function to be a discrete distribution supported on the finite set $\gamma$.
It is well-known cole2017convex,conitzer2022pacing,gao2022infinite that $\beta$ in a limit (resp.\ finite) FPPE uniquely solves the population (resp.\ sample) dual EG program
where the objectives $H$ and $H_t$ is the same as (ref). The difference between the LFM and FPPE convex programs is that for FPPE we impose the constraint $ (0,1]^n$.
The study of the asymptotics of FPPE was initiated by liao2023stat. Let ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ be the limit distribution of $\sqrt t (\beta^\gamma - \beta^*) $, i.e.,
They show that, with the strict complementary slackness assumption \nameref{as:constraint_qualification}, the distribution ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ simplifies to
where ${\mathscr{H}} = \nabla ^{2} H (\beta^*)$ and $P = { \operatorname*{Diag}}(1({\beta^*_i} < 1))$. Note this is a degenerate normal distribution supported on the hyperplane $\{h: h_i = 0, i \in I_{=} = I_{=>}\}$.
We will study the form of ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ assuming only twice differentiability (\nameref{as:twice_diff}) and not \nameref{as:constraint_qualification}. We will characterize ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ by a random quadratic program and provide several examples. Thus, a contribution of our paper is to remove the strict complementarity slackness assumption and characterize the full landscape of FPPE asymptotics.
The following assumption will be made throughout the paper, for both LFM and FPPE.
(ref) implies that the Hessian ${\mathscr{H}} = \nabla^{2} H(\beta^*)$ is positive definite. Here $\beta^*$ is interpreted as the equilibrium inverse bang-per-buck in a limit LFM, and equilibrium pacing multipliers in a FPPE. See liao2023stat,liao2023fisher for discussions of implications and concrete examples of \nameref{as:twice_diff} holding.
Our research goal can now be stated as
Inference on other quantities that are differentiable functions of $\beta^*$ can be achieved by the bootstrap delta method (kosorok2008introduction, vaart2023empirical). For example, utilities ${ u^*_i } = b_i / {\beta^*_i}$ and the Nash social welfare $ { \sum_{i} } b_i \log { u^*_i } = { \sum_{i} } b_i \log (b_i / {\beta^*_i})$ are smooth functions of $\beta^*$. Revenue $ \int \max_i \{ {\beta^*_i} { v_i(\theta) }\} s(\theta) \mathop{}\!\mathrm{d} \theta$ is also a smooth function of $\beta^*$. For this reason, throughout the paper we will focus on inference of $\beta^*$, i.e., the utility prices in LFM and pacing multipliers in FPPE.
In this section we let $\beta^\gamma$ be the observed utility prices in ${ \widehat{ \mathsf{{LFM}} } }(b,v,1/t, \gamma)$, where $\gamma$ consists of $t$ i.i.d.\ draws from supply $s$. As mentioned previously, $\beta^\gamma = \operatorname*{arg\,min}_{{\mathbb R^n_+}} H_t( \beta )$. The target distribution we want to estimate is ${\mathscr{J}}_{ \mathsf{{LFM}}}$ in (ref).
Define the exchangeable bootstrap by
Compared with the convex program for LFM in (ref), the exchangeable bootstrap replaces $P_t$ with ${P^{\mathsf{ex}, b}_t}$. Exchangeable bootstrap is considered a smooth alternative to the traditional multinomial bootstrap (i.e. sampling with replacement) because it allows for a wider class of distributions of bootstrap weights praestgaard1993exchangeably. Concretely, we need the weights in the exchangeable bootstrap to satisfy the following conditions.
Exchangeable bootstrap incorporates many popular forms of resampling as special cases such as the classical sampling with replacement, sampling without replacement, and normalized i.i.d.\ weights; see (ref).
The proof of (ref) is complicated by the fact that the EG objective is nonsmooth due to the $\max$ operation in (ref). Establishing (ref) requires using the exchangeable bootstrap empirical process theory from praestgaard1993exchangeably and wellner1996bootstrapping to establish a form of stochastic differentiability ((ref) in appendix), and applying the Taylor expansion-type analysis for nonsmooth objective functions from pollard1985new.
In practice, approximate LMF equilibrium and bootstrap estimates suffice. (ref) need not be solved exactly; error in the objective up to order $o_p(1/n)$ suffices, i.e., ${P^{\mathsf{ex}, b}_t} F({ \cdot }, \beta ^ b_{\mathsf{ex, LFM}} ) \leq \min_ \beta {P^{\mathsf{ex}, b}_t} F({ \cdot }, \beta)+o_p(1/n)$. And $\beta^\gamma$ only needs to be an approximate Fisher market equilibrium: $P_t F({ \cdot }, \beta^\gamma ) \leq \min_ \beta P_t F({ \cdot }, \beta ) + o_p(1/n)$. The proof of (ref) can be extended to account for the extra error from approximate optimization. In (ref) we briefly review two other valid bootstrap procedures, proximal bootstrap, and numerical bootstrap, and the consistency theory based on li2020numerical and li2023proximal. Proximal bootstrap has the advantage of solving quadratic programs only. However, those two methods converge at a rate slower than $1/\sqrt t$. In contrast, exchangeable bootstrap offers flexibility in choosing bootstrap weights, enjoys a $1/\sqrt t$ rate, and does not need parameter tuning.
In this section we let $\beta^\gamma$ be the pacing multiplier in ${ \widehat{ \mathsf{{FPPE}}}}(b,v,1/t, \gamma)$, where $\gamma$ consists of $t$ i.i.d.\ draws from supply $s$. As mentioned previously, $\beta^\gamma = \operatorname*{arg\,min}_{(0,1]^n} H_t( \beta )$. The target distribution we want to estimate is ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ in (ref), the limit distribution of $\sqrt t(\beta^\gamma - \beta^*)$.
Bootstrapping FPPE is a significantly harder problem due to the presence of constraints in the EG program in (ref). We investigate the full landscape of FPPE asymptotics, i.e., ${\mathscr{J}}_{ \mathsf{{FPPE}}}$, in (ref). In (ref), we show that the standard multinomial bootstrap fails to estimate ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ consistently. This also suggests that estimating ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ in full generality is difficult. Because of this, we divide our study into an easier case and the harder case. In the simpler case, we assume that all buyers exhaust their budget; for this case we show in (ref) that the bootstrap methods from li2020numerical,li2023proximal are valid. A more realistic case is when some buyers do have leftover budgets. We design a bootstrap for this case in (ref), under an additional assumption of strong complementary slackness (\nameref{as:constraint_qualification}). Finally, to complete the picture, we present a bootstrap-based confidence region for fully general FPPE in (ref).
The limit distribution of FPPE was studied in liao2023stat under Assumption \nameref{as:constraint_qualification}. In this section, we characterize the full landscape of the asymptotics of FPPE without strict complementarity. The convex program characterization in this section is a direct corollary of noticing the connection between the results of shapiro1989asymptotic and liao2023stat. Concretely, Theorem 3.3 from shapiro1989asymptotic established asymptotic distribution results for general constrained programs under equicontinuity conditions, and the results of liao2023stat imply those equicontinuity conditions for the EG objective in (ref). This is how we derive the convex program characterization of the asymptotics below. We then derive a new closed-form expression for the convex program, which allows us to analyze the asymptotic structure for several example.
To describe ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ we need to introduce a quadratic program. Let $I_= = \{ i: {\beta^*_i} = 1\}$ be the set of unpaced buyers and ${I_<} = [n] \setminus I$. We further partition $I_=$ into
$I_{=>}$ is the set of buyers with strictly positive leftover budgets, whereas $I_{==}$ are the degenerate buyers. From an optimization perspective, the set $I_{=>}$ corresponds to the strongly active constraints in the program (ref), whose corresponding Lagrange multipliers are strictly positive, while the set $I_{==}$ are the weakly active constraints, whose Lagrange multipliers are zero. With these notations, we note \nameref{as:constraint_qualification} is the same as $I_{==} = \emptyset$, and that the condition that all buyers exhaust their budgets is the same as $I_{=>} = \emptyset$. Define $h:{\mathbb R^n}\to {\mathbb R^n}$,
where $\|a\|_{\mathscr{H}} ^{2} = a^{\scriptscriptstyle\mathsf{T}} {\mathscr{H}} a$. The program (ref) can be interpreted as projecting the vector $-{\mathscr{H}}^{{-1}} \xi$ onto the cone $\{h: h_i=0, i\in I_{=>}; h_i \leq 0, j\in I_{==} \}$ w.r.t.\ the norm $\|{ \cdot }\|_{\mathscr{H}}$. The function $h$ is continuous and positively homogeneous of degree 1, i.e., $h(t \xi) = t h(\xi)$ for $t > 0$, but not necessarily linear. When $I_{==} = \emptyset$, i.e., \nameref{as:constraint_qualification} holds, the function $h(\xi) = - (P{\mathscr{H}} P)^{\dagger} \xi$.
Combining Theorem 3.3 from shapiro1989asymptotic with the equicontinuity results of liao2023stat, we have that under the \nameref{as:twice_diff} assumption, $${\mathscr{J}}_{ \mathsf{{FPPE}}} = h\Big( {\mathcal{N}} \big(0, { \operatorname {Cov} }[\nabla F({ \cdot },\beta^*)] \big) \Big)\;.$$
Note how different buyer types affect the support of ${\mathscr{J}}_{ \mathsf{{FPPE}}}$. The effects of $I_{==}$ and $I_{=>}$ are clear since they appear in the constraints. Buyers who do not win anything ($ {\beta^*_i} = 1, {\delta^*_i} = b_i $) determine the support of ${\mathcal{N}}( 0, { \operatorname {Cov} }[\nabla F({ \cdot },\beta^*)])$, which is $ \{ g\in {\mathbb R^n} : g_i = 0 \text{ if $i$ does not win anything}\}$.
Below and in (ref) we study the form of ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ under some special cases by deriving closed-form expression of the quadratic program (ref).
In the example below, we assume $I_{=>} = \emptyset$ for simplicity. Let $ D = { \operatorname*{Diag}}({\mathscr{H}} ^{{-1}} ) ^{1/2}, \rho = D^{{-1}} {\mathscr{H}}^{{-1}} D^{{-1}}, Z = - D^{{-1}} {\mathscr{H}}^{{-1}} G. $ where $G\sim {\mathcal{N}}(0, { \operatorname {Cov} }[\nabla F({ \cdot },\beta^*)])$. Intuitively, $\rho$ is a normalized version of the inverse of the Hessian. Denote entries of $Z$ by $[Z_1,\dots, Z_n]^{\scriptscriptstyle\mathsf{T}}$.
(ref) and (ref) in appendix illustrate an interesting phenomenon that the limit marginal distribution of the degenerate buyers (those with ${\beta^*_i} = 1$ and ${\delta^*_i} = 0$) is a distribution with some probability weight at $0$ and the rest on the negative reals. This makes sense intuitively since in a finite sample, $\beta^\gamma_i - {\beta^*_i} = \beta^\gamma_i - 1$ is always negative for $i \in I_{==}$. Another feature of ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ is that the limit distribution of $\sqrt{t}(\beta^\gamma_i - 1)$ is degenerate (a point mass at zero) if $i\in I_{=>}$. This also implies $\beta^\gamma_i - 1 = o_p(\frac{1}{\sqrt t})$ if $i \in I_{=>}$.
As described in andrews2000inconsistency, standard multinomial bootstrap might fail in constrained programs. In this section, we show that this is the case for FPPE.
Consider a one-buyer FPPE. Let $b_1 = 1$, ${\mathbb E}[v_1] = \int v_1 s \mathop{}\!\mathrm{d} \theta = 1$ and $s$ is the supply (a probability density). Let $\gamma = \{{ \theta^\tau }\}_\tau$ be i.i.d.\ draws from $s$. Let $\beta^\gamma$ be the pacing multiplier in ${ \widehat{ \mathsf{{FPPE}}}}(b,v,1/t,\gamma)$ and $\beta^*$ be that in ${ \mathsf{{FPPE}}}(b,v,s,\Theta)$.
Given the observed items, let $\{ \theta^{\tau,b}\}_\tau$ be the resampled items (with replacement). For this instance, the bootstrapped FPPE with standard multinomial weights is
In fact, using the same argument in abrevaya2005bootstrap, we can show that in the above example, $\sqrt t(\beta^\gamma - \beta^*) { \,\overset{{d}}{\to} \,} \min\{Z_1, 0\}$, while $ \sqrt t ( \beta ^ b - \beta^\gamma) \,{\stackrel{p}{\rightsquigarrow}}\, \min \{Z_1 + Z_2, 0\} - \min\{ Z_1, 0 \}$ where $Z_1,Z_2$ are independent copies of ${\mathcal{N}}(0, { \operatorname {Var} }(v_1))$.
If FPPE has the additional structure that all buyers exhaust their budgets, i.e., $I_{=>} = \emptyset$, we can apply the numerical bootstrap li2020numerical and the proximal bootstrap li2023proximal. Equivalently, it requires the population EG in (ref) does not have strongly active constraints, $\nabla H(\beta^*) = 0 $, and the unconstrained optimum coincides with the constrained optimum.
Under this additional structure, (ref) becomes
and $G \sim {\mathcal{N}}(0, {\mathbb E}[\nabla F({ \cdot }, \beta^*)\nabla F({ \cdot }, \beta^*)^{\scriptscriptstyle\mathsf{T}}])$. So ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ is a distribution supported on the cone $\{ h \in {\mathbb R^n}: h_i \leq 0 \text{ if } i \in I_{==} \}$, with some probability mass distributed on the faces of the cone.
To obtain numerical bootstrap and proximal bootstrap estimates, we require a smoothing parameter $\epsilon_t \downarrow 0$ such that $\epsilon_t \sqrt{t} \to \infty$. Then, to get $ \beta ^ b_{\mathsf{nu,FPPE}}$ we solve
and to get $ \beta ^ b_\mathsf{pr, FPPE} $ we solve
where
Here $D_F({ \cdot },\beta^\gamma)$ is a deterministic element in the subdifferential $\partial _{ \beta }F ({ \cdot }, \beta^\gamma) $ \footnote{ We avoid writing $\nabla F({ \cdot }, \beta^\gamma)$ because in a finite FPPE there could be ties. And when ties happen for an item $\theta$, EG objective $ \beta \mapsto F(\theta, \beta )$ is not differentiable at $\beta^\gamma$.}. The term $G^b$ estimates the Gaussian random variable $G$ in (ref). The numerical difference estimator is $\widehat {\mathscr{H}}_{k,\ell} = ({\widehat \nabla^{2}_{k\ell,\eta_t}} H_t)(\beta^\gamma)$, where
and $H_t$ is the finite-sample EG objective in (ref). In practice, both (ref) only need to be solved approximately with error in the objective up to $o_p( \epsilon_t ^{2})$. The proximal bootstrap in (ref) is a bootstrap analogue of the distribution in (ref).
The following theorem shows that in the budget-exhaustion case, the numerical bootstrap and proximal bootstrap converge to the correct limit distribution. The proofs can be found in (ref).
The proof proceeds by verifying conditions in li2020numerical and li2023proximal. Stochastic equicontinuity of certain processes is verified using results from liao2023stat.
In real-world auction markets such as those at internet companies, some fraction of buyers do have leftover budgets conitzer2022multiplicative. In this section, we give a bootstrap estimate of ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ under \nameref{as:constraint_qualification}, in which we allow users to have positive leftover budgets, but rule out degenerate buyers. Condition \nameref{as:constraint_qualification} is equivalent to requiring that in the population EG in (ref) there is no weakly active constraints (those whose Lagrangian multipliers are zero). Condition \nameref{as:constraint_qualification}, equivalent to $I_{==} = \emptyset$, is realistic because degenerate buyers are a measure-zero edge case. Note now ${\mathscr{J}}_{ \mathsf{{FPPE}}}$ is a degenerate normal distribution supported on the hyperplane $\{h: h_i = 0, i \in I_{=} = I_{=>}\}$.
Choose two vanishing sequences $ \delta_{t}$ and $ \epsilon_{t}$. Define the estimated unpaced buyers ${ \widehat I _ = }= \{i: \beta^\gamma_i > 1 - \delta_{t}\}$ and the reduced feasible set $\widehat B = \{ \beta \in [0,1]^n: \beta_i = 1 \text{ for } i \in \widehat I_{=} \}$. The proposed bootstrap estimator is
where $G^b $ and $\widehat {\mathscr{H}}$ are defined in (ref). The estimator has a nice geometric interpretation: we add certain appropriate noise to $\beta^\gamma$ and then project back to the reduced feasible set $\widehat B$. We call ${ \epsilon }_t$ the bootstrap stepsize, whose effect is investigated in (ref).
The estimator in (ref) is proposed following ideas from li2023proximal,cattaneo2020bootstrap, where the bootstrap is in fact approximating the random quadratic program (ref). Many existing works geyer1994asymptotics,li2020numerical,li2023proximal require that strongly active constraints do not occur, and are thus not applicable for FPPE with buyers who have leftover budgets. As with proximal bootstrap, our approach requires solving quadratic programs only.
We briefly remark on the techniques used to prove (ref). We combine the theory of weak convergence vaart2023empirical from statistics and epi-convergence theory rockafellar1970convex from optimization. The reason is that weak convergence is a powerful tool to study asymptotics of statistical functionals, such as the $\operatorname*{arg\,min}$ function, and epi-convergence is designed for studying constrained programs. Such an approach dates back to geyer1994asymptotics and molchanov2005theory, and more recently was used by parker2019asymptotic for constrained quantile regression, and li2020numerical and li2023proximal in the context of bootstrap.
Both proximal bootstrap ((ref)) and our proposed bootstrap ((ref)) require a numerical difference estimate of the Hessian ((ref)). We provide a theorem to guide the choice of differencing stepsize.
By setting $\eta_t^{2} = 1/(\eta_t \sqrt t)$ we obtain the optimal choice $\eta_t \asymp t^{-1/6}$. The proof of (ref) uses empirical process theory to handle the nonsmoothness of the EG objective.
In (ref) we assumed either $I_{==}$ or $I_{=>}$ to be empty sets. Now we discuss bootstrap inference without such assumptions. We can construct a confidence region for $\beta^*$ using bootstrap test inversion. Suppose we have a scalar statistic $T(\beta^*, \delta^*, \theta^1,\dots,\theta^t )$, and an upper bound estimate $c \in {\mathbb R}$ of the $(1-\alpha)$-quantile of its limit distribution. Then the region $\{ (\beta,\delta): T(\beta, \delta, \theta^1,\dots,\theta^t ) \leq c \}$ is an asymptotically-valid confidence region for $(\beta^*,\delta^*)$.
First, we introduce a statistic based on the Lagrangian of the EG program. The idea of using the Lagrangian or Karush-Kuhn-Tucker (KKT) system for inference in constrained programs also appears in li2023proximal,hsieh2022inference. Consider the sample Lagrangian $L_t(\beta, \delta) = H_t(\beta) - \delta ^{\scriptscriptstyle\mathsf{T}} (1_n - \beta ) $ for $\beta \in (0,1]^n$ and $0\leq \delta \leq b$. Define the statistic for some $\kappa \in (0, \infty]$:
where ${\mathbb B}_\kappa = \{ h\in {\mathbb R^n}: \|h\|_2 \leq \kappa \}$. The statistic $T^{ \gamma }$ finds the local minimum value of the Lagrangian over a $\frac1{\sqrt t}$-neighborhood of $\beta$.
Next, we introduce the bootstrap $T^b$ to estimate an “upper bound” of the distribution of $T^\gamma(\beta^*,\delta^*)$.
The quadratic function of $\beta$ inside $\inf$ aims to estimate a quadratic expansion of the Lagrangian at $(\beta^*,\delta^*)$.
To see that $T^b$ is an upper bound of $T^\gamma(\beta^*, \delta^*)$, it turns out that $T^\gamma (\beta^*, \delta^*) { \,\overset{{d}}{\to} \,} - \inf_{h \in {\mathbb B}_\kappa} G ^{\scriptscriptstyle\mathsf{T}} h + \frac12 h^{\scriptscriptstyle\mathsf{T}} {\mathscr{H}} h $, while $ T^b \,{\stackrel{p}{\rightsquigarrow}}\, - \inf_{h \in {\mathbb R^n}} G ^{\scriptscriptstyle\mathsf{T}} h + \frac12 h^{\scriptscriptstyle\mathsf{T}} {\mathscr{H}} h$ where $G\sim {\mathcal{N}}(0, { \operatorname {Cov} }(\nabla F({ \cdot }, \beta^*))) $. For the same realization of $G$, the limit distribution of $T^b$ is greater than or equal to that of $T^\gamma(\beta^*,\delta^*)$.
Now we are ready to introduce the confidence region. Given a threshold value $c$, the statistic $T^\gamma$ induces the region
Let $c^b_{1-\alpha}$ be the conditional $(1-\alpha)$-quantile of $T^b$, i.e., $c^b_{1-\alpha} = \inf \{ x: {\mathbb P}(T^b \leq x | \{ { \theta^\tau }\} ) \geq 1-\alpha\}$. Then a confidence region for $(\beta^*, \delta^*)$ is $C ^\gamma(c^b_{1-\alpha})$.
The condition on the continuity of the CDF is mild and commonly seen in the literature beran1984. The cost that comes with the general applicability of the confidence region $C^{ \gamma }(c^b_{1-\alpha})$ is computational. To decide whether a point $( \beta ,\delta)$ is in the region one solves the optimization problem in (ref).
We now conduct experiments to investigate the performance of the bootstrap estimator (ref) in FPPE with \nameref{as:constraint_qualification} conditions. We aim to (1) verify that the bootstrap produces a consistent estimate of the FPPE asymptotic distribution, and (2) study the effect on the bootstrap of the stepsize parameter $ \epsilon_t $ and market parameters, such as the number of items, number of buyers, proportion of budget-constrained buyers, and the value distributions.
Synthetic experiments. In (ref) we consider an ideal scenario where buyers' values are i.i.d.\ draws from some distribution, i.e., $v_1,\dots, v_n \sim_{iid} F_v$. To assess the effect of the tail of the value distributions, we take $F_v$ to be a uniform, exponential, or truncated normal distribution. We visualize and compare two setups: 1) true resampling, where the finite-sample distribution of $\sqrt t (\beta^\gamma - \beta^*)$, obtained by repeatedly drawing independent FPPE instances, and 2) bootstrap: $ \epsilon_t ^{{-1}} ( \beta ^ b - \beta^\gamma)$ as defined in (ref), obtained by bootstrapping only one FPPE instance. We also vary the bootstrap stepsize $\epsilon_t$. Experiments confirm that our bootstrap (ref) is consistent, fairly robust under a wide range of market parameters when bootstrap stepsize is chosen appropriately.
Semi-real experiments. In (ref) we construct realistic instances from real-world auction markets based on the iPinYou dataset liao2014ipinyou. The dataset contains raw log data of the bid, impression, click, and conversion history on the iPinYou platform. From the dataset we estimate the click-through rate of impressions using logistic regression and simulate realistic advertisers' values by perturbing the regression coefficients. We treat the sum of pacing multipliers\, as the target parameter and use percentiles of the bootstrap estimates based on (ref) to construct confidence intervals. We assess the effect on the coverage rate of the number of items, number of advertisers, the bootstrap stepsize $ \epsilon_t $, and the proportion of unpaced buyers. These experiments show that our bootstrap is suitable for realistic auction markets.
A bootstrap theory for FPPE without regularity conditions on either the buyers (e.g. (ref)) or the CDF assumption in (ref) would be desirable. However, we suspect that this will be a difficult task, since bootstrapping completely general constrained convex programs remains an open problem. Secondly, we saw in our experiments that Hessian estimation is important for the performance of our bootstrap methods. Thus, a better understanding of how to perform Hessian estimation for the best performance on real-world problems would be useful. In practice it would also be highly desirable to have a bootstrap theory that has some form of guarantees under nonstationary input data.
This research was supported by the Office of Naval Research awards N00014-22-1-2530 and N00014-23-1-2374, and the National Science Foundation awards IIS-2147361 and IIS-2238960.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.