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.
169,736 characters · 43 sections · 112 citation commands
Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions
\RUNAUTHOR{Liao and Kroer}
\RUNTITLE{Statistical Inference in Market Equilibrium}
\TITLE{ Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions }
\ARTICLEAUTHORS{ \AUTHOR{Luofeng Liao} \AFF{Department of Industrial Engineering and Operations Research, Columbia University, \EMAIL{[email removed]}} \AUTHOR{Christian Kroer} \AFF{Department of Industrial Engineering and Operations Research, Columbia University, \EMAIL{[email removed]}} }
\ABSTRACT{ {\color{black}{ We initiate the study of statistical inference and A/B testing for two market equilibrium models: linear Fisher market (LFM) equilibrium and first-price pacing equilibrium (FPPE). LFM arises from fair resource allocation systems such as allocation of food to food banks. }\color{black}} For LFM, we assume that the observed data is captured by the classical finite-dimensional Fisher market equilibrium, and its steady-state behavior is modeled by a continuous limit Fisher market. {\color{black}{The FPPE model arises from internet advertising where advertisers are constrained by budgets and advertising opportunities are sold via first-price auctions. }\color{black}} We propose a statistical framework for the FPPE model, in which a continuous limit FPPE models the steady-state behavior of the auction platform, and a finite FPPE provides the data to estimate primitives of the limit FPPE. Both LFM and FPPE have an Eisenberg-Gale convex program characterization, the pillar upon which we derive our statistical theory. We start by deriving basic convergence results for the finite market to the limit market. We then derive asymptotic distributions, and construct confidence intervals. Furthermore, we establish the asymptotic local minimax optimality of estimation based on finite markets. We then show that the theory can be used for conducting statistically valid A/B testing on auction platforms. Synthetic and semi-synthetic experiments verify the validity and practicality of our theory. }
Statistical inference is a crucial tool for measuring and improving a variety of real-world systems with multiple agents, including large-scale systems such as internet advertising platforms and resource allocation systems. However, statistical interference is a crucial issue in such systems. Past work has often focused on interference such as networks effects, which may arise due to user interactions on social media platforms. In this paper, we focus on a different type of interference: interference effects arising from competition between agents on a platform. To be concrete, consider the case of A/B testing for internet advertising: budgets are prevalent among advertisers on such platforms, and these budgets mean that the actions of one advertiser can affect the actions of another. Often, in such systems, randomization is performed e.g. at the user level and then budget-splitting is used to clone advertisers into the A and B treatment. However, budget interactions may cause all users in e.g. the A or B treatment to be related to each other, and thus it is not at all clear that one can apply standard statistical methods that treat each user as an independent sample. Instead, a theory of equilibrium interference is needed, and we need to understand how statistical interference can be performed when such interference is present. We study statistical inference and A/B testing in two closely-related equilibrium models: First, we study one of the most classical competitive equilibrium models: the linear Fisher market (LFM) equilibrium. Second, we study the first-price pacing equilibrium (FPPE) conitzer2022pacing, which is a model that captures the budget-management tools often employed on internet advertising platforms.
In a Fisher market, there is a set of $n$ budget-constrained buyers and $m$ goods. A market equilibrium (ME) is an allocation of the goods and a corresponding set of prices on the goods such that the market clears, meaning that demand equals supply. In a linear Fisher market, a buyers' utility is linear in their allocation. Beyond being a classical model of price formation, the Fisher market equilibrium arises in resource allocation systems via the the competitive equilibrium from equal incomes (CEEI) mechanism varian1974equity,budish2011combinatorial. In CEEI, each individual is given an endowment of faux currency and reports her valuation for the goods; then, a market equilibrium is computed, and the goods are allocated accordingly. The resulting allocation has many desirable properties such as Pareto optimality, envy-freeness and proportionality. Below we list examples of allocation systems where a Fisher market equilibrium naturally arises.
The second type of equilibrium model we study is the FPPE model, which arises in internet advertising. First, we review how impressions are sold in internet advertising, where first or second-price auction generalizations are used. When a user shows up on a platform, an auction is run in order to determine which ads to show, before the page is returned to the user. Such an auction must run extremely fast. This is typically achieved by having each advertiser specify the following ahead of time: their target audience, their willingness-to-pay for an impression (or values per click, which are then multiplied by platform-supplied click-through-rate estimates), and a budget. Then, the bidding for individual impressions is managed by a proxy bidder controlled by the platform. As a concrete example, to create an ad campaign on Meta Ads Manager, advertisers need to specify the following parameters: (1) the conversion location (say website, apps, Messenger and so on), (2) optimization and delivery (target your ads to users with specific behavior patterns, such as those who are more likely to view the ad or click the ad link), (3) audience (age, gender, demographics, interests and behaviors), and (4) how much money do you want to spend (budget). Given the above parameters reported by the advertiser, the (algorithmic) proxy bidder supplied by the platform is then responsible for bidding in individual auctions to maximize advertiser utility, while respecting the budget constraint.
{\color{black}{An important role of these proxy bidders is to ensure smooth budget expenditure. Pacing is a budget management method that modifies the advertiser's bids by applying a shading factor, known as a (multiplicative) pacing multiplier, to the advertiser's bid.}\color{black}} Tuning the pacing multiplier changes the spending rate: the larger the pacing multiplier, the more aggressive the bids. The goal of the proxy bidder is to choose this pacing multiplier such that the advertiser exactly exhausts their budget (or alternatively use a multiplier of one in the case where their budget is not exhausted by using unmodified bids). In this paper we focus on pacing-based budget management systems.
First-price pacing equilibrium conitzer2022pacing is a market-equilibrium-like model that captures the steady-state outcome of a system where all buyers employ a proxy bidder that uses multiplicative pacing. conitzer2022pacing showed that an FPPE always exists and is unique. Moreover, as a pacing configuration method, FPPE enjoys 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). The FPPE model specifically captures the setting where each auction is a first-price auction. First and second-price auctions are both prevalent in practice, but equilibrium models for second-price auctions are much less tractable (in fact, even finding one is computationally hard chen2023complexity). To that end, we focus on the first-price auction setting in this paper; the second-price setting is interesting, but we expect that it will be much harder to give satisfying statistical inference results for it.
Quantifying uncertainty in pacing systems is an important task on online advertising platforms. Basic statistical tasks, such as the prediction of the bidding behavior of advertisers or the revenue of the whole platform, require a statistical theory to model the intricacies of the bidding process. A/B testing, a method that seeks to understand the effect of rolling out a new feature, also requires a rigorous theoretical treatment to handle equilibrium effects. {\color{black}{ What a platform would typically like to do, is to treat each item in A and B as a separate unit and measure e.g., the price of the item as an independent observation. However, interference occurs due to the optimizing behavior of each buyer, where they end up buying a bundle in their demand set (on a platform that runs ad auctions, this would typically occur through the proxy bidder that performs pacing). This optimization combined with the budget constraints causes interference both between different buyers and different items. Consequently, one has to treat the entire market as the observed “unit.” }\color{black}} To the best of our knowledge, our results are the first to provide a statistical theory that captures such competitive interference effects that one would expect on an internet advertising platform.
Although LFM and FPPE have seemingly very different use cases, they each have an Eisenberg-Gale convex program characterization eisenberg1959consensus,eisenberg1961aggregation. This is the unifying theme that allows us to study these two models using similar tools. In particular, this allows us to reduce inference about market equilibrium to inference about stochastic programs, where many classical tools from mathematical programming shapiro2021lectures and empirical processes theory vaart1996weak can be applied.
\paragraph{Statistical models for resource allocation systems and first-price pacing auction platforms. } We leverage the infinite-dimensional Fisher market model of gao2022infinite in order to propose a statistical model for resource allocation systems and FPPE platforms. In this model, we observe market equilibria formed with a finite number of items that are i.i.d.\ draws from some distribution, and aim to make inferences about several primitives of the limit market, such as revenue, Nash social welfare (a fair metric of efficiency), and other quantities of interest; see (ref). Importantly, this lays the theoretical foundation for A/B testing in resource allocation systems and auction markets, which is a difficult statistical problem because buyers interfere with each other through the supply and the budget constraints. With the presence of equilibrium effects, traditional statistical approaches which rely on the i.i.d.\ assumption or SUTVA (stable unit treatment value assumption, imbens2015causal) fail. The key lever we use to approach this problem is a convex program characterization of the equilibria, called the Eisenberg-Gale (EG) program. With the EG program, the inference problem reduces to an $M$-estimation problem shapiro2021lectures,van2000asymptotic on a constrained non-smooth convex optimization problem.
\paragraph{Convergence and inference results for LFM and FPPE.} We show that the finite market, which represents the observed data, is a good estimator for the limit market by showing a hierarchy of results: strong consistency, convergence rates, and asymptotic normality. We also establish that the observed market is an optimal estimator of the limit market in the asymptotic local minimax sense van2000asymptotic,le2000asymptotics,duchi2021asymptotic. Finally, we provide consistent variance estimators, whose consistency is proved by a uniform law-of-large-numbers over certain function classes. A shared challenge for developing statistical theory for both LFM and FPPE is nonsmoothness: The objective function in the EG convex program (for a sampled finite market) is non-differentiable {\color{black}{on ${\mathbb R^n}$}\color{black}} almost surely, since it involves the max operator. { {\color{black}{ Even so, we will see that in our limit market model, the expectation operator, which becomes an integral, smooths out the non-differentiability issues under relatively mild conditions. We explore sufficient conditions for differentiability in (ref). }\color{black}} } For FPPE, there is a more prominent issue: the parameter-on-boundary issue, which means that the optimal population solution might be on the boundary of the constraint set. Here we briefly discuss how we handle the two issues when deriving asymptotic distribution results for FPPE, which is one of the more difficult results in the paper. First, asymptotic distribution results for $M$-estimation are known to hold under certain regularity conditions on stochastic programs shapiro1989asymptotic. One such condition concerns the differentiability of the population objective. We provide low-level sufficient conditions for differentiability, and show they have natural interpretations from an economic perspective ((ref)). Another important condition to verify is stochastic equicontinuity ((ref)), which we establish by leveraging empirical process theory vaart1996weak,kosorok2008introduction.
\paragraph{Statistically reliable A/B testing in resource allocation systems and FPPE platforms.} Applying our theory, we {\color{black}{formalize and analyze}\color{black}} a budget-split A/B testing design for item-side randomization that resembles real-world A/B testing methodology in markets with budgets. In the budget-split design, treatment and control markets are formed independently, and buyer's budgets are split proportionally between them, while items are randomly assigned to treatment or control markets. Then, based on the equilibrium outcomes in the A and B markets, we construct estimators and confidence intervals that enable statistical inference.
{\color{black}{
As described above, the fundamental quantity of interest in our model is the limit market, whether for LFM or FPPE. We now provide some discussion and motivation for our use of this limit market.
Suppose a practitioner faces the following prediction task: given data arising from a finite market, what can we say about future finite markets that are created under similar conditions? In the case of the allocation systems we study in the paper, this can be interpreted as follows: suppose we observe the behavior of the system for one week (represented by the finite market), and the allocation system is operating in equilibrium. Can we now make statistical inferences about next week's market, assuming that the generated items follow a similar pattern? Similarly, A/B testing a system under a budget-split design requires us to make statistical statements about each arm.
To address questions such as these, we study the statistical behavior of finite markets sampled from a limit market where the item set is continuous, and the supply becomes a distribution on the item set; see (ref) for an illustration. Limit markets are formally introduced in (ref).
The limit market serves as a conceptual model through which we derive prediction intervals for future finite markets. We focus on deriving confidence intervals for the limit market, i.e., an interval $I$ constructed from the data so that the probability ${\mathbb P}(\text{quantities in the limit market lie in } I)$ is high. One can then easily construct prediction intervals for a future market. Take FPPE as an example. Let $\beta^\gamma$ be the observed multiplier, and $\beta^*$ be the limit one. Suppose $\beta^{new}$ is the multiplier in a future market, independent of the observed market. We will show that the observed multiplier concentrates around the limit multiplier: $\sqrt t (\beta^\gamma - \beta^*) { \,\overset{{\,d\,\,}}{\rightarrow}\, } N(0, \Sigma_\beta)$ for some matrix $\Sigma_\beta$. Then
by independence between $\beta^\gamma$ and $\beta^{new}$. Given an estimator of $\Sigma_\beta$, a prediction interval for $\beta^{new}$ can thus be constructed.
Of course, if the goal is to make predictions about future finite markets, one might wonder if there is a way to give a formal model of predicting future finite markets directly from observed finite markets, without going through the limit market. For some quantities it is easy to impose a simple statistical model and develop a prediction theory while ignoring the equilibrium structure in the data; for other quantities, it is more difficult to even put a statistical model on them. In either case, ignoring the equilibrium structure casts doubt on the validity of such approaches.
}\color{black}}y of such approaches.
}
A/B testing in two-sided markets. Empirical studies by blake2014marketplace,fradkin2019simulation demonstrate bias in experiments due to marketplace interference. basse2016randomization study the bias and variance of treatment effects under two randomization schemes for auction experiments. bojinov2019time study the estimation of causal quantities in time series experiments. Some recent state-of-the-art designs are the multiple randomization designs liu2021trustworthy,johari2022experimental,bajari2021multiple and the switch-back designs sneider2018experiment,hu2022switchback,li2022interference,bojinov2022design,NEURIPS2020_abd98725. The surveys by kohavi2017surprising,bojinov2022online contain detailed accounts of A/B testing in internet markets. See larsen2022statistical for an extensive survey on statistical challenges in A/B testing. Compared to these papers, our paper is the first to focus on A/B testing with equilibrium effects.
{\color{black}{ The budget-split design we study is similar to one studied by liu2021trustworthy: buyer's budgets are split proportionally, creating two sets of identical buyers, and then items are assigned to either group of buyers at random. However, we differ in the theory to analyze such experiments. The main difference between our paper and theirs is that they did not consider equilibrium effects, while we do. In particular, liu2021trustworthy assume that pacing and other strategic effects are fixed across treatments. In turn, this means that any strategic behavior or budget-optimizing behavior ignores the A/B assignment. On a related note, we consider randomness of both the item (impression) arrivals and the treatment assignment, while Liu et al.\ only consider the latter. Second, we provide an exact variance formula for many quantities in the ad auction systems, such as pacing multipliers and revenues, while Liu et al.\ do not.
}\color{black}} Pacing equilibrium. Pacing is a prevalent budget-management methods on ad auction platforms. In the first-price setting, borgs2007dynamics study first price auctions with budget constraints in a perturbed model, whose limit prices converge to those of an FPPE. Building on the work of borgs2007dynamics, conitzer2022pacing introduce the FPPE model and discover several properties of FPPE such as shill-proofness and monotonicity in buyers, budgets and goods. There it is also established that FPPE is closely related to the quasilinear Fisher market equilibrium chen2007note,cole2017convex. gao2022infinite propose an infinite-dimensional variant of the quasilinear Fisher market, which lays the probability foundation of the current paper. gao2021online,liao2022dualaveraging study online computation of the infinite-dimensional Fisher market equilibrium. In the second-price setting, balseiro2015repeated investigate budget-management in second-price auctions through a fluid mean-field approximation; balseiro2019learning study adaptive pacing strategy from buyers' perspective in a stochastic continuous setting; balseiro2021budget study several budget smoothing methods including multiplicative pacing in a stochastic context; conitzer2022multiplicative study second price pacing equilibrium, and shows that the equilibria exist under fractional allocations.
$M$-estimation when the parameter is on the boundary There is a long literature on the statistical properties of $M$-estimators when the parameter is on the boundary geyer1994asymptotics,shapiro1990differential,shapiro1988sensitivity,shapiro1989asymptotic,shapiro1991asymptotic,shapiro1993asymptotic,shapiro2000asymptotics,andrews1999estimation,andrews2001testing,knight1999epi,knight2001limiting,knight2006asymptotic,knight2010asymptotic,dupacova1988asymptotic,dupavcova1991non,self1987asymptotic. Some recent works on the statistical inference theory for constrained $M$-estimation include li2022proximal,hong2020numerical,hsieh2022inference. Our work leverages shapiro1989asymptotic, which develops a general set of conditions for asymptotic normality of constrained $M$-estimators when the objective function is nonsmooth. Working under the specific model of FPPE, we build on and go beyond these contributions by deriving sufficient condition for asymptotic normality in FPPE, establishing local asymptotic minimax theory and developing valid inferential procedures.
Statistical learning and inference with equilibrium effects Online learning approaches, which are related to statistical learning, have been investigated for other equilibrium models, such as general exchange economy guo2021online,liu2022welfare and matching markets cen2022regret,dai2021learning,liu2021bandit,jagadeesan2021learning,min2022learn. Our work is also related to the rich literature of inference under interference hudgens2008toward,aronow2017estimating,athey2018exact,leung2020treatment,hu2022average,li2022random. In the economic literature, researchers have studied how to estimate auction market primitives from bid data; see athey2007nonparametric for a survey.
Closely related to our work is a recent preprint by munro2021treatment. They consider a potential outcomes framework where the outcome of an agent depends on the treatments of all agents, but only through the equilibrium price. The equilibrium price is attained by a market clearance condition. Although both their work and our work consider a limit market equilibrium (in their case a mean-field equilibrium), there are significant differences. First, munro2021treatment send the number of agents to infinity while we consider the asymptotics where the number of items grows. Second, munro2021treatment present a very general market equilibrium framework that requires abstract regularity conditions (which do not hold in our setting), while we focus on equilibria arising from resource allocation systems and auction pacing systems, and consequently we are able to present low-level conditions that facilitate statistical inference. Third, their model works with a single market where buyers are randomly exposed to treatment or control. {\color{black}{ Consequently, munro2021treatment focuses on estimating direct effects and spillover effects when buyers in a single market are randomly assigned to either treatment or control. In contrast, our work is focused on interventions that affect the entire valuation distribution, and we study separated markets when we apply our theory to A/B testing. }\color{black}} For this reason, an A/B testing framework such as the one we develop is necessary. Wager2021,sahoo2022policy also consider a mean-field game modeling approach and perform policy learning with a gradient descent method.
\ifanon \else This paper builds upon two preliminary conference papers liao2023fisher,liao2023stat. The present paper gives a more unified presentation, and provides some additional results on the statistical theory of Fisher markets and FPPE. Perhaps most importantly, this paper conducts two semisynthetic experiments based on an ad auction dataset liao2014ipinyou and an Instagram notification dataset instagramdata, demonstrating the practicality of the proposed theory. This paper also provides strong consistency and convergence rate for FPPE, minimax optimality results for LFM, and a novel closed-form expression for the Hessian matrix of the population EG objective ((ref)) using results from differential geometry kim1990cube. Building on the preliminary versions of the present paper, liao2024bootstrap extends the FPPE statistical theory to the cases where degenerate buyers are present and develops bootstrap inference methods, and liao2024interference studies interference among FPPEs. \fi
Let $e_i$ be the $i$-th basis vector in ${\mathbb R^n}$. Furthermore, we let $A^{\dagger} $ be the Moore-Penrose pseudo inverse of a matrix $A$. Let $\mathop{}\!\mathrm{d} \theta$ denote the Lebesgue measure in ${\mathbb R}^D$. 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 integrating measure $\mathop{}\!\mathrm{d} \theta $ for any $p\in [1, \infty]$ (including $p=\infty$). We treat all functions that agree on all but a measure-zero set as the same. For a sequence of random variables $\{X_n\}$, we say $X_n = O_p(1)$ if $\lim_{K\to \infty} \limsup_n {\mathbb P}(|X_n| > K) = 0$. We say $X_n = o_p(1)$ if $X_n$ converges to zero in probability. We say $X_n = O_p(a_n)$ (resp.\ $o_p(a_n)$) if $X_n/a_n = O_p(1)$ (resp.\ $o_p(1)$). The subscript $i$ is for indexing buyers and superscript $\tau$ is for items.
{\color{black}{In this section we introduce the Fisher market equilibrium and the first-price pacing equilibrium.}\color{black}} We start by presenting components that are common to both models, and then introduce each equilibrium concept. In both LFM and FPPE, we have a set of $n$ buyers and a set of items, and the goal is to find market-clearing prices for the items. The items are represented by a set $\Theta \in {\mathbb R}^D$, a compact set with $\int { \mathds{1} } (\Theta) \mathop{}\!\mathrm{d} \theta > 0$. Clearly the measure {\color{black}{space}\color{black}} $(\Theta,{\mathop{}\!\mathrm{d} \theta})$ is atomless.
Both LFM and FPPE require the following elements; see (ref) for an illustration.
(1) The budget $b_i$ of buyer $i$. Let $b = (b_1,\dots, b_n)$. {\color{black}{The smallest budget is denoted by $\ubar b = \min_i b_i$.}\color{black}} (2) The valuation for buyer $i$ is a function $v_i \in L^1_+$. Buyer $i$ has valuation $v_i(\theta)$ (per unit supply) of item $\theta\in \Theta$. Let $v: \Theta \to {\mathbb R^n}$, $v(\theta) = [v_1(\theta),\dots, v_n(\theta)] ^{\top}$. We assume ${ \bar v } = \max _i \sup_\theta v_i(\theta)< \infty $. (3) The supplies of items are given by a function $ s \in L^\infty_+$, i.e., item $\theta\in \Theta$ has $s(\theta)$ units of supply.
Without loss of generality, we assume a unit total supply $\int_\Theta s \mathop{}\!\mathrm{d} \theta = 1$, which makes $s$ a probability measure. Let ${\mathbb P}$ denote the probability measure induced by $s$, i.e., ${\mathbb P} (A) = \int_A s{\mathop{}\!\mathrm{d} \theta}$ for a measurable set $A$. 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}$. {\color{black}{ Also let $\nu_i = \int v_i s\mathop{}\!\mathrm{d} \theta = {\mathbb E}[ v_i]$ be the monopolistic utility of buyer $i$, and ${ \bar\nu} = \max_i \nu_i$. }\color{black}} Given $t$ i.i.d.\ draws $\{ \theta^1,\dots, \theta^t\}$ from $s$, let $P_t g({ \cdot }) = \frac1t {\sum_{\tau=1}^{t}} g({ \theta^\tau })$. Let ${ v_i^\tau } = v_i({ \theta^\tau })$.
Equilibria in both LFM and FPPE are characterized by a particular type of convex program known as an Eisenberg-Gale (EG) convex program. For statistical inference purposes, we will focus on the duals of these EG programs, which is a convex optimization problem over the space of pacing multipliers $\beta \in {\mathbb R^n_+}$ (these pacing multipliers turn out to represent the price-per-utility of buyers in equilibrium). In both cases, the dual EG objective separates into per-item convex terms
and the population and sample EG objectives are
The reason we focus on the duals is that they can be cast as sample average approximations of the limit convex programs. This interpretation is not possible for the original primal EG programs.
The LFM model has two primary uses. Its original intent is as a model of competition, and price formation in a competitive market. An additional, and practically important, use of LFM is as a tool for fair and efficient resource allocation (with the items being the resources). If every individual in a resource allocation problem is given one unit of faux currency, then the resulting LFM equilibrium allocation is known to be both Pareto efficient and satisfy the fairness desiderata of envy-freeness and proportionality nisan2007algorithmic. This fair allocation approach is known as competitive equilibrium from equal incomes (CEEI) varian1974equity.
We now describe the competitive equilibrium concept. Imagine there is a central policymaker that sets prices $p(\cdot)$ for the items $\Theta$. Upon observing the prices, buyer $i$ maximizes their utility subject to their budget. Their demand set is the set of bundles that are optimal under the prices: \[ D_i (p) := \argmax_{x_i \in L^\infty_+(\Theta)} \bigg\{ \int v_i x_i s \mathop{}\!\mathrm{d} \theta : \int p x_i s\mathop{}\!\mathrm{d} \theta \leq b_i\bigg\} \; .\] Of course, due to the supply constraints, if prices are too low, there will be a supply shortage. On the other hand, if prices are too high, a surplus occurs. A competitive equilibrium is a set of prices and bundles such that all items are sold exactly at their supply (or have price zero). We call such an equilibrium the limit LFM equilibrium for the supply function $s$ gao2022infinite.
gao2022infinite show that an equilibrium of a limit LFM must exist, and that when the measure space $(\Theta,{\mathop{}\!\mathrm{d} \theta})$ is atomless, a pure equilibrium allocation \footnote{An allocation $x$ is pure if $x_i(\theta) \in \{0,1\}$.} must exist. Given an equilibrium $(x^*, p^*)$, let
be buyer $i$' utility, her inverse bang-per-buck, and the (log) Nash social welfare of the whole market. The inverse bang-per-buck $\beta_i^*$ can also be seen as the price-per-utility of buyer $i$. In a general LFM, the equilibrium allocation may not be unique, but the equilibrium quantities $p^*,\beta^*, u^* $ are unique. In order to facilitate statistical inference, we will impose certain differentiability conditions, which turn out to imply uniqueness and purity of the equilibrium allocation $x^*$.
Next we introduce the finite LFM, which models the data we observe in a market. The finite LFM equilibrium is nothing but a limit LFM equilibrium where the item set $\Theta$ is the finite set of observed items $\gamma$. Let ${ \gamma } = \{ \theta^1,\dots, \theta^t\}$ be $t$ i.i.d. samples from the supply distribution $s$, each with supply $\sigma \in {\mathbb R _+}$.
Let $( x^{\gamma} , { p ^ {\gamma} }) \in { \widehat{ \mathsf{{LFM}} } }(b,v,\sigma = 1/t, \gamma)$ \footnote{We use $\in$ since the equilibrium allocation may not be unique; equilibrium prices are unique.}, where $ x^{\gamma} = ({x_i^\tau} )_{i,\tau}$ and price ${ p ^ {\gamma} } = [p^1,\dots, p^t]$. We study this form of finite LFM due a scale-invariant property of LFM, {\color{black}{and this ensures that for all market sizes, the “buyer size” is comparable to the “item size” of the market}\color{black}} (see (ref)). Buyer $i$'s utility is $ u^\gamma _i=\sigma {\sum_{\tau=1}^{t}} { v_i^\tau } { x^\tau_i } = \frac1t {\sum_{\tau=1}^{t}} { v_i^\tau } { x^\tau_i } $, and the inverse bang-per-buck is $\beta^\gamma_i = b_i / u^\gamma_i $. The (log) Nash social welfare is ${ \mathsf{{NSW}}}^\gamma = { \sum_{i} } b_i \log ( u^\gamma_i )$.
There exists natural bounds on $\beta^*$ in a limit LFM. Recall $\nu_i =\int v_i s{\mathop{}\!\mathrm{d} \theta} $ is the expected value of buyer $i$. By gao2022infinite, we know that $b_i / \nu_i \leq {\beta^*_i} \leq (\sum_{i'} b_{i'}) / (\min_{i'} \nu_{i'})$. We define
to be the region whose interior $\beta^*$ must lie in.
It is well-known eisenberg1959consensus,cole2017convex,gao2022infinite that the equilibrium inverse bang-per-buck in a limit (resp.\ finite) LFM uniquely solves the population (resp.\ sample) dual EG program
{\color{black}{ We review other properties of LFM, such as scale-invariance and mechanism design properties, including fairness and efficiency, in (ref). }\color{black}}
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 is assigned a pacing multiplier $\beta_i \in [0,1]$ by the platform to scale down their bids in the auctions, and submits bids of the form $\beta_i v_i(\theta)$ for each item $\theta$. {\color{black}{From the platform's perspective, the goal of choosing $\beta_i$ is to ensure that there is no unnecessary pacing: A buyer's budget constraint must be satisfied, but if $\beta_i < 1$ then the buyer exhausts their budget exactly.}\color{black}} In the FPPE model, all auctions occur simultaneously, and thus the buyers choose a single $\beta_i$ that determines their bid in all auctions. The utility of a buyer in FPPE is quasilinear: it is the sum of their value received from items plus their leftover budget (this is equivalent for decision-making purposes to the utility being the value received from items minus payments).
FPPE is a hindsight and static solution concept for internet ad auctions. Suppose the platform knows all the items that are going to show up on a platform. Then FPPE describes how the platform 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. In practice, the $\beta_i$'s are learned by an online algorithm that is run by the platform balseiro2019learning,conitzer2022pacing, {\color{black}{and FPPE captures the hindsight solution that these learning algorithms should converge to.}\color{black}} 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,kroer2022market for more context about the use of FPPE in internet ad auctions.
gao2022infinite show that a limit FPPE always exists and is unique, and when the item space is atomless, a pure allocation exists. Let $\beta^*$ and $p^*$ be the unique FPPE equilibrium multipliers and prices. Revenue in the limit FPPE is
It is also easy to see that ${ \mathsf{{REV}} }^* = { \sum_{i} } { \small \textsf{{pay}}}_i$. As with LFM, we will impose differentiability assumptions which imply uniqueness of $x^*$. When $x^*$ is unique, we let ${\delta^*_i} = b_i - { \small \textsf{{pay}}}_i$ be the leftover budget.
In an FPPE, based on the pacing multiplier and the budget expenditure, we can categorize buyers in terms of how they satisfy the no unnecessary pacing condition. As we will see later, the statistical behavior of pacing multipliers varies by category.
We let ${ \gamma } = \{ \theta^1,\dots, \theta^t\}$ be $t$ i.i.d.\ draws from $s$, each with supply $\sigma=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 $\gamma$.
Let $(\beta^\gamma, { p ^ {\gamma} }) = { \widehat{ \textsf{{FPPE}}}}(b,v,\sigma = 1/t,\gamma)$. {\color{black}{ As for LFM, decreasing supply per item ensures that for all market sizes, the “buyer size” is comparable to the “item size” of the market (see (ref)). }\color{black}} Given the equilibrium price ${ p ^ {\gamma} } = [p^1,\dots, p^t]^{\top}$, the revenue in a finite FPPE is ${ \mathsf{{REV}} }^ \gamma = \sigma {\sum_{\tau=1}^{t}} { p ^ \tau } = \frac1t {\sum_{\tau=1}^{t}} { p ^ \tau }$.
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$ are the same as in (ref). The difference between the LFM and FPPE convex programs is that for FPPE we impose the constraint $\beta\in (0,1]^n$.
The EG program and certain quantities of the FPPE are related as follows.
Proof sketch The first equality follows from the fact that leftover budgets are the Lagrange multipliers corresponding to the constraint $\beta \leq 1 \in {\mathbb R^n}$. The second equality follows from the first-order homogeneity of $f(\theta,\beta)=\max_i \beta_i { v_i(\theta) }$ in (ref). Appendix (ref) for details.
{\color{black}{ As previously explained, our statistical theory will be founded on M-estimation theory. In $M$-estimation, twice differentiability is usually required in order to establish asymptotic normality, and we will similarly impose it on the EG objective ((ref)) for our asymptotic normality results in LFM ((ref)) and FPPE ((ref)), and the statement of minimax lower bounds ((ref)) in later sections. We will revisit differentiability and derive sufficient conditions on market primitives in (ref), after we present the main statistical results for LFM and FPPE. }\color{black}}
We now turn to investigating the statistical convergence properties of finite LFMs to the limit LFM. Suppose we sample an LFM (${ \widehat{ \mathsf{{LFM}} } }(b,v,1/t, \gamma)$), where $\gamma$ consists of $t$ i.i.d.\ samples from $s$. We will study how such finite LFMs are distributed around the limit LFM (${ \mathsf{{LFM}}}(b,v,s,\Theta)$) as $t$ grows. We focus on convergence of the following quantities: individual utilities, (log) Nash social welfare (NSW), and the pacing multiplier vector $\beta$ (which characterizes the equilibrium, as shown in (ref)). (ref) presents strong consistency and convergence rate results. (ref) presents asymptotic distributions for the quantities of interest, and a local minimax theory based on le2000asymptotics, showing that the finite LFM provides an optimal estimate for the limit LFM in a local asymptotic sense. (ref) discusses estimation of asymptotic variance of NSW.
In this section we show that we can treat observed quantities in the finite LFM as consistent estimators of their counterparts in the limit LFM. Below we state the consistency results; the formal versions can be found in (ref). We say an estimator sequence $\{ \hat a_t\}$ is strongly consistent for $a$ if ${\mathbb P}(\lim_{t \to \infty} \hat a_t = a) = 1$.
Next, we refine the consistency results and provide finite sample guarantees. We start by focusing on Nash social welfare and the set of approximate market equilibria. The convergence of utilities and pacing multipliers will then be derived from the latter result.
In more intuitive wording, (ref) establishes a high-probability convergence rate $|{ \mathsf{{NSW}}}^{ \gamma } - { \mathsf{{NSW}}}^* | = \tilde O _p({ \bar v } \sqrt n t^{-1/2})$. The proof proceeds by first establishing a pointwise concentration inequality and then applies a discretization argument.
To state the result for the pacing multipliers $\beta$, we define approximate market equilibria (which we define in terms of approximately optimal pacing multiplier vectors $\beta$). Let
be the sets of $\epsilon$-approximate solutions to the sample and the population EG programs, respectively. The next theorem shows that the set of $\epsilon/2$-approximate solutions to the sample EG program is contained in the set of $\epsilon$-approximate solutions to the population EG program with high probability.
By construction of $C_{ \mathsf{{LFM}}}$ we know $\beta^* \in C_{ \mathsf{{LFM}}}$ holds, and so $C_{ \mathsf{{LFM}}}\cap { \mathcal{B}^*}(\epsilon)$ is not empty. In the appendix, (ref) shows that for $t$ sufficiently large, $\beta^\gamma \in C_{ \mathsf{{LFM}}}$ with high probability, in which case the set $C_{ \mathsf{{LFM}}}\cap { \mathcal{B}^\gamma}(\delta)$ is not empty. Setting $\delta = 0$ in (ref) we obtain the corollary below.
More importantly, it establishes the fast statistical rate $ H(\beta^\gamma ) - H(\beta^*) = {\color{black}{\tilde{O}_p ( n { \bar v }^{2} / \ubar b \cdot t^{-1} )}\color{black}} $ for $t$ sufficiently large, where we use $\tilde{O}_p$ to ignore logarithmic factors. In words: the limit LFM objective value of the finite solution $\beta^\gamma$ converges to the optimal limit LFM objective value at a $1/t$ rate.
By strong convexity of the dual objective, the containment result can be translated to high-probability convergence of the pacing multipliers and the utility vector.
We compare the above corollary with Theorem 9 from gao2022infinite which establishes a convergence rate of the stochastic approximation estimator based on the dual averaging algorithm xiao2010dual. In particular, they show that the average of the iterates, denoted $\beta_{\mathrm{DA}}$, enjoys a convergence rate of $\| \beta_{\mathrm{DA}} - \beta^*\|_2^2 = \tilde O_p \big(\frac{{ \bar v }^{2} }{ \underaccent{\bar}{b}^{2}} \frac{1}{t}\big)$, where $t$ is the number of sampled items. The rate achieved in (ref) is $\|\beta^\gamma - \beta^*\|_2 ^{2} = \tilde O_p \big(\frac{n { \bar v ^2 }}{\underaccent{\bar}{b}^{2}} \frac{1}{t} \big)$. We see that our rate is worse off by a factor of $n$. We conjecture that it can be removed by using the more involved localization arguments Bartlett2005. \footnote{ {\color{black}{ A recent work by liu2024metric shows the dimension dependence can be improved using a stability argument. }\color{black}} } {\color{black}{On the positive side, our estimates are produced by the strategic behavior of the agents without any extra computation, and can be observed directly from $\beta^\gamma$. In contrast, the computation of the dual averaging estimator requires knowledge of the values $v_i(\theta)$.}\color{black}}
In this section we derive asymptotic normality results for Nash social welfare, utilities and pacing multipliers. As we will see, a central limit theorem for Nash social welfare holds under basically no additional assumptions. However, the CLTs of pacing multipliers and utilities will require twice continuous differentiability of the population dual objective $H$ at optimality, with a nonsingular Hessian matrix. We present CLT results under such a premise; (ref) gives three quite general settings under which these conditions hold.
As stated previously, our asymptotic results for $\beta$ and $u$ require that $H$ is twice-continuously differentiable at $\beta^*$. When this differentiability holds the set of items that incur ties is $s$-measure zero (see (ref)), and thus the equilibrium allocation $x^*$ in the limit LFM is unique and must be pure. Now we define a map ${\mu^*}: \Theta \to {\mathbb R^n_+}$, which represents the utility all buyers obtain from the item $\theta$ at equilibrium. Formally,
Since $x^*$ is pure, only one entry of ${\mu^*}(\theta)$ is nonzero. Clearly $\int {\mu^*} s \mathop{}\!\mathrm{d} \theta = [ u^* _1,\dots, u^* _n]^{\top}$.
(ref) can also be derived from (ref) using the delta method, since ${ \mathsf{{NSW}}}^* = { \sum_{i=1}^n } b_i \log ({ u^*_i }) = { \sum_{i} } b_i \log (b_i / {\beta^*_i})$ is a smooth function of $\beta^*$.
We will show that the asymptotic variances in (ref) are the best achievable, in an asymptotic local minimax sense. To make this precise, we need to introduce “supply neighborhoods” obtained through perturbing the original supply $s$.
First we introduce notation to parametrize neighborhoods of the supply $s$. Let $g\in G_d = \{g:\Theta \to {\mathbb R}^d: {\mathbb E}[g]=0, {\mathbb E}[\|g\|^{2}]<\infty\}$ be a direction along which we wish to perturb the supply $s$. Given a vector $\alpha \in {\mathbb R}^d $ signifying the magnitude of perturbation, we want to scale the original supply of item $\theta$ by $\exp(\alpha^{\top} g(\theta))$ and then obtain a perturbed supply distribution by appropriate normalization. To do this we define the perturbed supply by \footnote{ In duchi2021asymptotic they allow more general classes of perturbations, we specialize their results for our purposes. }
with a normalizing constant $C = 1 + \int \alpha^{\top} g(\theta) s(\theta)\mathop{}\!\mathrm{d}\theta$. As $\alpha\to 0$, the perturbed supply $s_{\alpha,g}$ effectively approximates $ s_{\alpha,g} (\theta) \propto \exp(\alpha^{\top} g(\theta)) s(\theta) .$
We let $\beta^*_{\alpha,g}$, $ u^* _{\alpha,g}$ and ${ \mathsf{{NSW}}}^*_{\alpha,g}$ be the limit inverse bang-per-buck, price and revenue in ${ \mathsf{{LFM}}}(b,v,s_{\alpha,g}, \Theta)$. Clearly $\beta^* = \beta^*_{0,g}$ for any $g$ and similarly for $ u^* _{0,g}$ and ${ \mathsf{{NSW}}}_{0, g}$.
Given the asymptotic normality of observed LFM, it is desirable to understand the best possible statistical procedure for estimating the limit LFM. One way to discuss the optimality is to measure the difficulty of estimating the limit LFM when the supply distribution varies over small neighborhoods of the true supply $s$, asymptotically. When an estimator achieves the best worst-case risk over these small neighborhoods, we say it is asymptotically locally minimax optimal. For general references, see vaart1996weak,le2000asymptotics. More recently duchi2021asymptotic develop asymptotic local minimax theory for constrained convex optimization, and we rely on their results.
Let $L:{\mathbb R^n} \to {\mathbb R}$ be any symmetric quasi-convex loss \footnote{A function is quasi-convex if its sublevel sets are convex.}. In asymptotic local minimax theory we are interested in the local asymptotic risk: given a sequence of estimators $\{ \hat \beta_t: \Theta^t \to {\mathbb R^n} \}_t$,
If we ignore the limits and consider a fixed $t$, then ${ \mathsf{{LAR}}}_\beta$ roughly measures the worst-case risk for the estimators $\{\hat \beta_t\}$. Note that $\alpha$ is a $d$-vector, and thus the shrinking norm-balls depend on $d$, and the expectation is taken w.r.t.\ the $t$-fold product of the perturbed supply.
Similarly, define the risk for utility $u$ (resp. Nash social welfare ${ \mathsf{{NSW}}}$) given an estimator sequence $\{ \hat u _t\}$ (resp. $\{ \widehat { \mathsf{{NSW}}}_t\}$):
In this section we show how to construct confidence intervals for Nash social welfare. We will show how to construct confidence intervals for pacing multipliers and utilities in the FPPE section. The procedure is similar for LFM, and thus we omit it here.
First, regarding inference, it is interesting to note that the observed NSW (${ \mathsf{{NSW}}}^{ \gamma }$) is a negatively-biased estimate of the limit NSW (${ \mathsf{{NSW}}}^*$), i.e., $ {\mathbb E}[{ \mathsf{{NSW}}}^{ \gamma }] - { \mathsf{{NSW}}}^* \leq 0$.\footnote{Note $ {\mathbb E}[{ \mathsf{{NSW}}}^{ \gamma }] - { \mathsf{{NSW}}}^* = {\mathbb E}[\min_\beta H_t(\beta)] - H(\beta^*) \leq \min_\beta {\mathbb E}[H_t(\beta)] - H(\beta^*) = 0.$} Moreover, it can be shown that, when the items are i.i.d.\ ${\mathbb E}[\min H_t] \leq {\mathbb E}[\min H_{t+1}]$ by a simple argument from Proposition 16 from shapiro2003monte. Monotonicity tells us that increasing the market size produces, on average, less biased estimates of the limit NSW.
To construct confidence intervals for Nash social welfare, one needs to estimate the asymptotic variance. Let ${ p ^ \tau }$ be the price of item ${ \theta^\tau }$ in the finite market, and $\bar p = \frac1t {\sum_{\tau=1}^{t}} { p ^ \tau }$. The variance estimator is then
We emphasize that in the computation of the variance estimator $ \hat\sigma_{{ \mathsf{{NSW}}}}^{2}$ one does not need knowledge of the valuations $\{{ v_i(\theta^\tau) }\}_{i,\tau}$. All that is needed is the equilibrium prices ${ p ^ {\gamma} } = (p^{1},\dots, p^{t})$ for the items. Given the variance estimator, we construct the confidence interval $ \big[ { \mathsf{{NSW}}}^{ \gamma } \pm z_{\alpha/2} \frac{\hat \sigma_{{ \mathsf{{NSW}}}}}{\sqrt t}\big]$, where $z_\alpha$ is the $\alpha$-th quantile of a standard normal. The next theorem establishes validity of the variance estimator.
Next we study statistical inference questions for the FPPE model. Since FPPE is characterized by an EG-style program similar to that of LFM, many of the results for FPPE are similar to those for LFM. However, an important difference is that the FPPE model has constraints on the pacing multipliers, which makes the asymptotic theory more involved. As for LFM, we assume that we observe a finite auction market ${ \widehat{ \textsf{{FPPE}}}}(b,v,1/t, \gamma)$ with $\gamma$ being $t$ i.i.d. draws from $s(\cdot)$, and we use it to estimate quantities from the limit market ${ \textsf{{FPPE}}}(b,v,s,\Theta)$. In FPPE we mainly focus on the revenue of the limit market, and for the same reason as in LFM, since FPPE is characterized by an EG program with pacing multiplier as the variables, we also present results for $\beta$. Similarly to the LFM case, one can use results for $\beta$ to derive estimators for buyer utilities.
Since FPPE has a similar convex program characterization as LFM, strong consistency and convergence rate results can be derived using similar ideas.
We complement the strong consistency result with the following rate results. They are derived using a discretization argument similar to the one for LFM.
The above bounds hold for a broad class of limit FPPE models and may be loose for a particular model. In (ref), we show that for buyers $i \in \{ i:{\beta^*_i} = 1\}$, their pacing multipliers converge at a rate faster than $ \tilde O_p(1/\sqrt t)$.
As in LFM, our statistical inference results require the limit market to behave smoothly around the optimal pacing multipliers $\beta^*$. To that end, we will make (ref), as in LFM. Similar to LFM, under (ref), the equilibrium allocation $x^*$ is unique and must be pure. Again we can define
Under (ref), the equilibrium allocation $x^*$ is unique, so ${\mu^*}(\cdot)$ is also unique. Moreover, ${\mu^*}(\theta) = \nabla f(\theta, \beta^*)$, and $ (\beta^*) ^{\top} {\mu^*}(\theta) = p^*(\theta)$ (the set of nondifferentiable points has measure zero, and thus we can ignore such points). Also let ${\bar \mu^*}$ denote the utility from items:
Note that in the FPPE model, buyers' utility consists of two parts: utility from items and leftover budgets. In FPPE, the pacing multipliers relate budgets and utilities via conitzer2022pacing
In the unconstrained case, classical $M$-estimation theory says that, under regularity conditions, an $M$-estimator is asymptotically normal with covariance matrix ${\mathcal{H}}^{-1} { \operatorname {Var} }(\text{gradient}) {\mathcal{H}}^{-1}$ van2000asymptotic. However, in the case of FPPE, which is characterized by a constrained convex problem, the Hessian matrix needs to be adjusted to take into account the geometry of the constraint set $B=(0,1]^n$ at the optimum $\beta^*$. We let ${\mathcal{P}} = { \operatorname*{diag}}( { \mathds{1} }( {\beta^*_i} < 1) )$ be an “indicator matrix” of buyers whose ${\beta^*_i} < 1$, and define the projected Hessian nocedal2006numerical
It will be shown that the asymptotic variance of $\beta^\gamma$ is ${\mathcal{H}}_B^{\dagger} { \operatorname {Var} }(\text{gradient}) {\mathcal{H}}_B^{\dagger}$ and the “gradient" is exactly ${\mu^*}$.
(ref) can be viewed as a non-degeneracy condition from a convex programming perspective, since $\delta_i$ corresponds to a Lagrange multiplier on $\beta_i \leq 1$. From a market perpective, (ref) requires that if a buyer's bids are not paced (${\beta^*_i} = 1$), then their leftover budget $\delta^* _i$ must be strictly positive. This can again be seen as a market-based non-degeneracy condition: if ${\delta^*_i}=0$ then the budget constraint of buyer $i$ is binding, yet ${\beta^*_i}=1$ would imply that they have no use for additional budget. If (ref) fails, one could slightly increase the budgets of buyers for which (ref) fails, i.e., those who do not pace yet have exactly zero leftover budget, and obtain a market instance with the same equilibrium, but where (ref) holds.
From a technical viewpoint, (ref) is a stronger form of first-order optimality. Note $\nabla H(\beta^*) = -{\delta^*}$ (cf.\ (ref)). The usual first-order optimality condition is
where ${\mathcal{N}}_B(\beta) = \prod_{i=1}^n J_i(\beta)$ is the normal cone with $J_i (\beta)= [0,\infty)$ if $\beta_i = 1$ and $J_i (\beta)= \{0\}$ if $\beta_i < 1$ for $\beta \in {\mathbb R^n_{++}}$. Then (ref) translates to the condition that ${\beta^*_i} = 1$ implies ${\delta^*_i} \geq 0$. On the other hand, when written in terms of the normal cone, (ref) is equivalent to $$- \nabla H(\beta^*) \in { \operatorname*{relint}} ( {\mathcal{N}}_B(\beta^*) ) \; , \footnote{ The relative interior of a set is ${ \operatorname*{relint}}(S)=\{x \in S:$ there exists $\epsilon>0$ such that $N_\epsilon(x) \cap \operatorname{aff}(S) \subseteq S \}$ where $\operatorname{aff}(S)$ is the affine hull of $S$, and $N_\epsilon(x)$ is a ball of radius $\epsilon$ centered on $x$. }$$ equivalent to the condition ${\beta^*_i} = 1$ implies ${\delta^*_i} > 0$. Given that $ { \operatorname*{relint}} ( {\mathcal{N}}_B(\beta^*) ) \subset {\mathcal{N}}_B(\beta^*) $, (ref) is obviously a stronger form of first-order condition. Conditions like (ref) are commonly seen in the study of statistical properties of constrained $M$-estimators (duchi2021asymptotic and shapiro1989asymptotic). In the proof of (ref), (ref) forces the critical cone to reduce to a hyperplane and thus ensures asymptotic normality of the estimates. Without (ref), the asymptotic distribution of $\beta^\gamma$ could be non-normal.
We now show that the observed pacing multipliers $\beta^\gamma$ and the observed revenue ${ \mathsf{{REV}}}^\gamma$ are asymptotically normal. Define the influence functions
Recall ${\mu^*}$ is defined in (ref), ${\bar \mu^*}$ in (ref), ${\mathcal{H}}_B$ in (ref). And note ${\mathbb E}[D_\beta] = 0$ and ${\mathbb E}[D_{ \mathsf{{REV}}}] = 0$.
The functions $D_\beta$ and $D_{ \mathsf{{REV}}}$ are called the {influence functions} of the estimates $\beta^\gamma$ and ${ \mathsf{{REV}}}^{ \gamma }$ because they measure the change in the estimates caused by adding a new item to the market (asymptotically).
{\color{black}{ (ref) can be simplified if $I_= = [k]$, i.e., the first $k$ buyers are the ones with $\beta_i=1$. Let $\beta^*_<$ and $\beta^\gamma_<$ denote the subvectors corresponding to $I_<$, and define $\beta^*_=$ and $\beta^\gamma_=$ similarly. Let ${\mathcal{H}}_{<}$ denote the lower right $(n-k)\times(n-k)$ block of ${\mathcal{H}} $ corresponding to $I_<$. (ref) then gives $\sqrt t (\beta^\gamma_< - \beta^*_<) { \,\overset{{\,d\,\,}}{\rightarrow}\, } {\mathcal{N}}(0, \Sigma_{\beta, <})$ and $\sqrt t (\beta^\gamma_= - \beta^*_=) = o_p (1)$ for some positive semi-definite matrix $\Sigma_{\beta, <}$ \footnote{If $I_=$ (resp. $I_<$) is empty, we disregard the statement for $\beta^\gamma_=$ (resp. $\beta^\gamma_<$).}. To see this, note the pseudo-inverse of the projected Hessian $({\mathcal{H}}_B )^{\dagger} = { \operatorname*{diag}}(0_{k\times k} , ({\mathcal{H}}_{<})^{-1} )$. Consequently, $ \sqrt{t} (\beta^\gamma_i - {\beta^*_i})$ is of order $o_p(1)$ for $i \in I_=$, and thus converging faster than the usual $O_p(1)$ rate. In fact, one can show ${\mathbb P}(\beta^\gamma_i = 1) \to 1$ for all $i \in I_=$; see (ref). The fast rate phenomenon is empirically investigated in (ref).
A practical implication of (ref) is the identification of budget constrained buyers in the limit market. By (ref) we have $I_= = \{i: {\beta^*_i} = 1\}= \{ i: {\delta^*_i} > 0\}$, i.e., $I_=$ is the set of buyers who are not budget constrained, and ${I_<} = \{i:{\beta^*_i} < 1\} = \{ i: {\delta^*_i} = 0\} $ is the set of buyers that exhaust their budget. \footnote{Without (ref) we only have $ \{i:{\beta^*_i} < 1\} \subset \{i:{\delta^*_i} = 0\}$ and $\{i:{\delta^*_i} > 0 \}\subset \{i:{\beta^*_i} = 1\}$ by complementary slackness.} The fast rate $o_p(t^{-1/2})$ implies that the platform can identify which buyers are budget constrained with high confidence.
Finally, (ref) implies fast revenue convergence if $I_= = \emptyset$. In this case, the influence function $D_{ \mathsf{{REV}}}(\theta) = 0$ for all $\theta$ because ${\mathcal{H}} \beta^* = {\bar \mu^*}$ if $I_= = \emptyset$ ((ref)), and $(\beta^*)^{\top} {\mu^*}(\theta) = p^*(\theta)$. Then (ref) gives $\sqrt t ({ \mathsf{{REV}} }^ \gamma - { \mathsf{{REV}} }^* ) = o_p(1)$. Intuitively, if $\beta^\gamma_i < 1$ for all $i$, then all buyers' budgets are exhausted in the observed FPPE, and so we have $ { \mathsf{{REV}} }^ \gamma = { \sum_{i=1}^n } b_i$. By the convergence $\beta^\gamma { \,\overset{{p}}{\to}\, } \beta^*$ and that ${\beta^*_i} < 1$ for all $i$, we know that for large $t$ with high probability, $\beta^\gamma_i <1 $ for all $i$, and thus ${ \mathsf{{REV}} }^ \gamma ={ \sum_{i=1}^n } b_i ={ \mathsf{{REV}} }^* $. In that case, it must be that the asymptotic variance of revenue equals zero. }\color{black}}
In an FPPE, individual utilities and Nash social welfare can be similarly defined. By applying the delta method and (ref) we can derive asymptotic distributions for these quantities, using the fact that they are smooth functions of $\beta$. See Appendix (ref) for more details.
Given the asymptotic distributions for $\beta$ and ${ \mathsf{{REV}}}$, we will show that the observed FPPE estimates are optimal in an asymptotic local minimax sense. Recall in (ref) we have defined the perturbed supply family $G_d$ of dimension $d$ with perturbation $(\alpha,g)$.
\paragraph{Asymptotic local minimax optimality for $\beta$.} We first focus on estimation of pacing multipliers.\ For a given perturbation ${(\alpha,g)}$, we let $\beta^*_{\alpha,g}$, $p^*_{\alpha,g}$ and ${ \mathsf{{REV}} }^* _{\alpha,g}$ be the limit FPPE pacing multiplier, price and revenue under supply distribution $s_{\alpha,g}$. Clearly $\beta^* = \beta^*_{0,g}$ for any $g$ and similarly for $p^*_{\alpha,g}$ and ${ \mathsf{{REV}}}_{\alpha, g}$. Let $L:{\mathbb R^n} \to {\mathbb R}$ be any symmetric quasi-convex loss. \footnote{A function is quasi-convex if its sublevel sets are convex.} In asymptotic local minimax theory we are interested in the local asymptotic risk: given a sequence of estimators $\{ \hat \beta_t: \Theta^t \to {\mathbb R^n} \}_t$,
As an immediate application of Theorem 1 from duchi2021asymptotic, it holds that
where the expectation is taken w.r.t.\ a normal specified above. Moreover, the lower bound is achieved by the observed FPPE pacing multipliers $\beta^\gamma$ according to the normality result in (ref).
\paragraph{Asymptotic local minimax optimality for revenue estimation.} For pacing multipliers, the result is a direct application of the perturbation result from duchi2021asymptotic. The result for revenue estimation is more involved. Given a symmetric quasi-convex loss $L:{\mathbb R}\to{\mathbb R}$, we define the local asymptotic risk for any procedure $\{\hat r _t : \Theta^t \to {\mathbb R}\}$ that aims to estimate the revenue:
Proof in Appendix (ref). In the proof we calculate the derivative of revenue w.r.t.\ $\alpha$, which in turn uses a perturbation result for constrained convex programs from shapiro1989asymptotic. Again, the lower bound is achieved by the observed FPPE revenue ${ \mathsf{{REV}} }^ \gamma $ according to the normality result in (ref). Similar optimality statements can be made for $u$ and ${ \mathsf{{NSW}}}$ by finding the corresponding derivative expressions.
To perform inference on $\beta^*$, we construct estimators for the influence functions (ref). In turn, this requires estimators for the projected Hessian ${\mathcal{H}}_B$ ((ref)) and the variance of the utility map ${\mu^*}$ ((ref)). First, given a sequence of smoothing parameters $\varepsilon_{{\mathcal{P}},t} = o(1)$ and $\varepsilon_{{\mathcal{P}},t} \sqrt t \to c \in (0,\infty]$, we estimate the projection matrix ${\mathcal{P}}$ by $ \hat {\mathcal{P}} = { \operatorname*{diag}}({ \mathds{1} }(\beta^\gamma_i < 1 - \varepsilon_{{\mathcal{P}},t} )) \;. $ For another sequence $\varepsilon_{{\mathcal{H}},t} = o(1)$ with $\varepsilon_{{\mathcal{H}},t} \sqrt t \to \infty$, we introduce a numerical difference estimator $\hat {\mathcal{H}}$ for the Hessian matrix ${\mathcal{H}}$, whose $(i,j)$-th entry is
with $\beta^\gamma_{\pm \pm} = \beta^\gamma \pm e_i \varepsilon_{{\mathcal{H}},t} \pm e_j \varepsilon_{{\mathcal{H}},t}$, and $H_t$ is defined in (ref). Finally, $\hat {\mathcal{H}}_B = \hat {\mathcal{P}} \hat {\mathcal{H}} \hat {\mathcal{P}}$ is the estimator of ${\mathcal{H}}_B$. Next, recall $ x^{\gamma} = ({x_i^\tau})_{i,\tau}$ and $({ v_i^\tau })_{i,\tau}$ are the allocation and values in the finite FPPE. Mimicking ${\mu^*}$ in (ref), ${\bar \mu^*}$ in (ref) and ${ \operatorname {Cov} }({\mu^*})$, define the finite sample analogues
With all the new notations, we define the estimators of influence functions in (ref)
Given that the asymptotic variances of $\beta^\gamma$ and ${ \mathsf{{REV}} }^ \gamma $ are ${\mathbb E}[D_\beta D_\beta ^{\top}]$ and ${\mathbb E}[D_{ \mathsf{{REV}}}^{2}]$, respectively, plug-in estimators for the (co)variance are naturally
For any $\alpha \in (0,1)$, the $(1-\alpha)$-confidence regions for $\beta^*$ and ${ \mathsf{{REV}} }^* $ are
where $\chi_{n,\alpha}$ is the $(1-\alpha)$-th quantile of a chi-square distribution with degree $n$, ${\mathbb B}$ is the unit ball in ${\mathbb R^n}$, and $z_{\alpha/2}$ is the $(1-\frac{\alpha}{2})$-th quantile of a standard normal distribution. The coverage rate of ${ \mathsf{{CI}}}_{ \mathsf{{REV}}}$ is empirically verified in (ref).
The rate condition on $\varepsilon_{{\mathcal{H}},t}$ suggests choosing $\varepsilon_{{\mathcal{H}},t} = t^{- d}$ for $0 < d < \frac12$. (ref) studies how the choice of $d$ affects the Hessian estimation numerically.
{\color{black}{ We now show that the Hessian estimation can be avoided if there is sufficient separation between the highest and second-highest bids. Define the gap between the highest and the second-highest bids under pacing multiplier $\beta$ by
here $\operatorname{secondmax}$ is the second-highest entry; e.g., $\operatornamewithlimits{secondmax}([1,1,2]) = 1$. The condition will require integrability of the inverse of the bid gap, i.e., ${\mathbb E}[{ \mathsf{{bidgap}}}(\beta,\theta)^{-1}] < \infty$. We introduce a new price function as follows. If $I_= \neq \emptyset$, we define
If $I_= = \emptyset$, then we define $\tilde p ^*(\theta) = 0$. The new price function $\tilde p ^{*}$ preserves the price of an item $\theta$ if it is won by a buyer in $I_=$, and $\tilde p ^{*}$ sets the price to $0$ otherwise. For the simplified revenue variance estimator we need an estimator of $I_=$, which naturally is $\hat I_= = \{i: \beta^\gamma_i \geq 1 - \varepsilon_{{\mathcal{P}}, t} \}$. Recall revenue ${ \mathsf{{REV}} }^ \gamma = \frac1t {\sum_{\tau=1}^{t}} { p ^ \tau }$ and price ${ p ^ {\gamma} } = [p^1, \dots, p ^ t ] ^{\top} $. Define $\tilde p ^\tau = { p ^ \tau } { \mathds{1} } \{ \max_{i \in \hat I_=} \beta^\gamma_i { v_i^\tau } = \max_{i \in [n]} \beta^\gamma_i { v_i^\tau } \} $, $\bar {\tilde p} = \frac1t {\sum_{\tau=1}^{t}} \tilde p ^\tau$. Define the simplified variance estimators (neither of which requires Hessian estimation):
}\color{black}}
Consider an auction market with $n$ buyers with a continuum of items $\Theta$ with supply function $s$. Now suppose that we are interested in the effect of deploying some new technology (e.g. new machine learning models for estimating click-through rates in the ad auction setting). To model treatment application we introduce the potential value functions $$ \hspace{-.2cm} 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)$.
Suppose we are interested in estimating the change in the auction market when treatment 1 is deployed to the entire item set $\Theta$. In this section we describe how to do this using A/B testing, specifically for estimating the treatment effect on revenue. Formally, we wish to look at the difference in revenues between the markets $$ { \textsf{{FPPE}}}(b, v(0), s) \text{ and } { \textsf{{FPPE}}}(b,v(1), s), $$ where ${ \textsf{{FPPE}}}(b, v(0), s)$ is the market with treatment 1, and ${ \textsf{{FPPE}}}(b,v(1), s)$ is the one with treatment 0. The treatment effects on revenue is defined as $$\tau_{{ \mathsf{{REV}}}} = { \mathsf{{REV}} }^* (1) - { \mathsf{{REV}} }^* (0)\;,$$ where ${ \mathsf{{REV}} }^* (w)$ is revenue in the equilibrium ${ \textsf{{FPPE}}}(b,v(w), s)$.
{\color{black}{ The A/B test framework we put forward above is rather general. This formalism is able to model treatments which ultimately affect the market via shifting the value distribution. We list several examples below.
}\color{black}}
We will refer to the experiment design as budget splitting with item randomization. The design works in two steps, and closely mirrors how A/B testing is conducted at large tech companies.
Step 1. Budget splitting. We create two markets, and every buyer is replicated in each market. For each buyer $i$ we allocate $\pi b_i$ of their budget to the market with treatment $w=1$, and the remaining budget, $(1-\pi)b_i$, to the market with treatment $w=0$. Each buyer's budget is managed separately in each market.
Step 2. Item randomization. Let $(\theta^1,\theta^2,\dots)$ be i.i.d.\ draws from the supply distribution $s$. For each sampled item, it is applied treatment $1$ with probability $\pi$ and treatment $0$ with probability $1-\pi$. The total A/B testing horizon is $t$. When the end of the horizon is reached, two observed FPPEs are formed. Each item has a supply of $\pi/t_1$ in the 1-treated market and $(1-\pi)/t_0$ in the 0-treated market. The $1/t_1$ is the scaling required for our CLTs and the $\pi$ factor ensures the budget-supply ratio agrees with the limit market; due to FPPE scale-invariance, we could equivalently rescale budgets.
Let $t_0$ be the number of $0$-treated items, and $t_1$ be the number of $1$-treated items. Conditional on the total number of items $t=t_1 + t_0$, the random variable $t_1$ is a binomial random variable with mean $\pi t$. Let $\gamma(0) = (\theta^{1,1},\dots, \theta^{1,t_1})$ be the set of $0$-treated items, and similarly $\gamma(1) = (\theta^{0,1},\dots, \theta^{0,t_0})$. The total item set $\gamma = \gamma(0) \cup \gamma(1)$. The observables in the described A/B testing experiment are $$ \hspace{-.1cm} { \widehat{ \textsf{{FPPE}}}} \big(\pi b, v(1), \tfrac{\pi}{t_1}, \gamma(1) \big),\; { \widehat{ \textsf{{FPPE}}}} \big( (1-\pi ) b, v(0), \tfrac{1-\pi}{t_0}, \gamma(0)\big ), $$ both defined in (ref). Let ${ \mathsf{{REV}} }^ \gamma (w)$ denote the observed revenue in the $w$-treated market. The estimator of the treatment effect on revenue is $$ \hat \tau_{{ \mathsf{{REV}}}} = { \mathsf{{REV}} }^ \gamma (1) - { \mathsf{{REV}} }^ \gamma (0).$$
For fixed $(b, s)$, the variance $\sigma^{2}_{ \mathsf{{REV}}}$ in (ref) is a functional of the value functions. We will use $\sigma^{2}_{ \mathsf{{REV}}}(w)$ to represent the revenue variance in the equilibrium ${ \textsf{{FPPE}}}(b,v(w), s)$. Each variance can be estimated using (ref).
Based on the theorem, an A/B testing procedure is the following. Compute the revenue variance as (ref) for each market, obtaining $ \hat \sigma^{2}_{ \mathsf{{REV}}}(1)$ and $ \hat \sigma^{2}_{ \mathsf{{REV}}}(0)$, and form the confidence interval
If zero is on the left (resp.\ right) of the CI, we conclude that the new feature increases (resp.\ decreases) revenue with $(1-\alpha)\times 100\%$ confidence. If zero is in the interval, the effect is undecided. See (ref) for a semi-synthetic study verifying the validity of this procedure.
In this section, we provide lower-level conditions on the market's primitives and equilibrium such that (ref) is implied.
We start with the differential structure of $f(\theta,\beta)=\max_i \beta_i{ v_i(\theta) }$. The function $f(\theta, \beta)$ is a convex function of $\beta$ and its subdifferential $\partial_\beta f(\theta, \beta)$ is the convex hull of $\{ v_i e_i \in {\mathbb R^n_+}: \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.
The ${ \mathsf{{bidgap}}}$ function in (ref) is useful for characterizing first-order differentiability of ${\bar f} (\beta) = {\mathbb E}_s[f(\theta, \beta)]$. When there is a tie for an item $\theta$, 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. The gap function characterizes smoothness of $f$: $f(\cdot, \theta)$ is differentiable at $ \beta$ iff ${ \mathsf{{bidgap}}}(\beta,\theta)$ is strictly positive.
Given the neat characterization of differentiability of the dual objective via the gap function ${ \mathsf{{bidgap}}}(\beta,\theta)$, it is natural to explore higher-order smoothness, which is needed for some of our asymptotic normality results. {\color{black}{On the negative side, Appendix (ref) gives an example where (ref) holds at a point $\beta$ and ${\bar f}$ is differentiable in a neighborhood of $\beta$, yet ${\bar f}$ is not twice differentiable at $\beta$.}\color{black}} We now provide sufficient conditions that imply twice differentiability of $H$.
{\color{black}{ We briefly comment on the inverse bid gap integrability condition. By (ref) we already know a necessary and sufficient condition for first-order differentiability is that for all items (up to a measure-zero set) there is a positive bid gap. The integrability condition essentially guarantees that for most items, the bid gap is sufficiently positive. We prove sufficiency for twice differentiability by first showing that the bid gap is a Lipschitz constant for the gradient of the EG objective, and then apply the dominated convergence theorem. }\color{black}}
We show in Appendix (ref) that when $H$ is twice differentiable, the Hessian matrix of $H$ has a closed-form expression.
Recall that a key component in the variance estimator is the Hessian matrix, which we estimate by the finite-difference method in (ref). Finite difference estimation requires the smoothing parameter $\varepsilon_t$. The smoothing $\varepsilon_t$ is used to (1) estimate the active constraints and (2) construct the numerical difference estimator $\hat {\mathcal{H}}$. (ref) suggests a choice of $\varepsilon_t = t^{-d}$ for some $0 < d < \tfrac12$. In (ref), we investigate the effect of $d$ numerically. Here we give high-level take-aways. We find that $d$ represents a bias-variance trade-off. For small $d$, the variance of the estimated value $\hat {\mathcal{H}}_{ii}$ is small and yet bias is large. For a large $d$ variance is large and yet the bias is small (the estimates are stationary around some point). Our experiments suggest using $d \in (0.32, 0.47)$.
Next we look at how the FPPE distribution behaves in a simple setting. We choose the FPPE instances as follows. Consider a finite FPPE with $n=25$ buyers and $t = 1000$ items. Let $U_i$ be i.i.d.\ uniform random variables on $[0,1]$. Buyers' budgets are generated by $b_i = U_i + 1$ for $i=1,\dots, 5$ and $b_i = U_i$ for $i= 6, \dots, 25$. The extra budgets are to ensure we observe ${\beta^*_i} = 1$ for the first few buyers. The valuations $\{ v_1, \cdots, v_n\}$ i.i.d. uniform, exponential, or truncated standard normal distributions. Under each configuration we form 100 observed FPPEs, and plot the histogram of each $\sqrt{t}( \beta^\gamma_i - {\beta^*_i})$. The population EG (ref) is a constrained stochastic program and can be solved with stochastic gradient based methods. The true value $\beta^*$ is computed by the dual averaging algorithm xiao2010dual. The mean square error decays as ${\mathbb E}[\| \beta^{\text{da}, t} - \beta^*\|^{2}] = O (t ^{-1}) $ with $t$ being the number of iterations, and so if we choose $t$ large enough, we should still observe asymptotic normality for the quantities $\sqrt t(\beta^{\text{da}, t} - \beta^\gamma)$.
Results.
(ref) shows five out of 25 distributions for pacing multipliers. Full plots for all three distributions are given in (ref). We see that (i) if ${\beta^*_i} < 1$ then the finite sample distribution is close to a normal distribution, and (ii) if ${\beta^*_i} = 1$ (or very close to $1$, such as $\beta_{14, 21}$ in the uniform value plots, $\beta_{20, 23}$ in exponential), the finite sample distribution puts most of the probability mass at 1. For cases where ${\beta^*_i}$ is close, but not very close, to 1, we need to further increase the number of items to observe normality.
Notifications are important in enhancing the user experience and user engagement in mobile apps. Nevertheless, an excessive barrage of notifications can be disruptive for users. Typically, a mobile application has various notification types, overseen by separate teams, each with potentially conflicting objectives. And so it is necessary to regulate notifications and send only those of most value to users. instagramdata propose to use Fisher market equilibrium-based methods to efficiently send notifications, where they treat the opportunity to send a user a notification as an item, and different types of notifications as buyers. In this section, we use the inference method developed in (ref) to quantify uncertainty in equilibrium-based notification allocation methods.
The data. The dataset released by instagramdata contains about $400,000$ generated notifications of four types for a subset of about $60,000$ Instagram users from September 14--23, 2022. The four types of notifications (buyers) are likes, daily digest of stories, feed suite organic campaign (notification about new posts on the user's feed), and comments subscribed. The value $v_i(\theta)$ of a notification type $i$ to a user $\theta$ at a specific time is predicted by the platform's algorithm and available in the dataset as a numerical value in $[0,1]$. The budgets of notification types are also given. For a user-notification type pair, we average over the whole time window and use the average to represent $v_i(\theta)$, resulting in a user-notification type matrix. However, even after aggregation over time, there are lots of missing values, i.e., many users do not have every notification type generate a potential notification.
Value imputation and simulation by the Gaussian copula. We assume the values in the notification system admit the following representation. There exists unique monotone functions $f_i:{\mathbb R} \to [0,1]$, such that $(v_1, \dots, v_4) = (f_1(Z_1), \dots, f_4 (Z_4))$, where $Z = [Z_1, \dots, Z_4]$ follows a multivariate Gaussian distribution with standard normal marginals. Such an assumption is equivalent to assuming the value distribution possesses a Gaussian copula (zhao2020missing and liu2009nonparanormal). Given this representation, we propose a two-step simulation method. In the first step, we learn the monotone functions by matching the quantiles of values with the quantiles of a standard normal. We use isotonic regression to learn the monotone functions. Second, given the learned functions $\hat f_i$ and inverses $\hat f_i ^{-1} : [0,1] \to {\mathbb R}$, we transform $v_i$ to $\hat f_i ^{-1}(v_i)$, and compute the covariance matrix of $\hat f_i ^{-1}(v_i)$, denoted $\hat \Sigma$. Even though some values are missing, the covariance $\Sigma$ can still be estimated by $\hat \Sigma$ if values are missing completely at random. \footnote{ {\color{black}{ The validity of the copula imputation method relies on the missing completely at random assumption (MCAR) zhao2020missing, i.e., values and missingness are independent. Unfortunately, we cannot determine whether this is true unless accessing the missing data. MCAR will be assumed in this experiment. }\color{black}} } Now to simulate a new item for buyers, we draw $Z \sim N(0, \hat \Sigma)$, and return $[\hat f_1 (Z_1),\dots, \hat f_4 (Z_4)] ^{\top} $ as the value. There are multiple advantages to this method. First, the dependence structure of the available dataset is preserved. Second, the generated values are within the range $[0,1]$ as the original data are. Third, the marginal distribution of values are also preserved in the simulated data.
As a final step to mimic realistic data, since some users may turn off notifications of certain types, the values of those notifications will be zero. We simulate this by setting certain values to zero according to the sparsity pattern in the original dataset. See (ref) for a comparison between original dataset and simulated data.
Setup and results. We apply the confidence interval in (ref) and study the coverage properties. The nominal coverage rate is set to 95%. First, we do see that even for a small sample size of 100, the nominal coverage rate is achieved. And as we increase the size of markets $t$, the coverage maintains at around 95% and the width of the CI shrinks roughly at the rate $1/\sqrt t$.
In this section we apply our revenue estimation method to a real-world dataset, the iPinYou dataset liao2014ipinyou. The iPinYou dataset liao2014ipinyou contains raw log data of the bid, impression, click, and conversion history on the iPinYou platform in the weeks of March 11--17, June 8--15 and October 19--27. We use the impression and click data of 5 advertisers on June 8, 2013, containing a total of 1.8 million impressions and 1,200 clicks. As in the main text, let $i \in \{1,2,3,4,5\}$ index advertisers (buyers) and let $\tau$ index impressions/users (items in FPPE terminology). The five advertiser are labeled by number and their categories are given: 1459 (Chinese e-commerce), 3358 (software), 3386 (international e-commerce) and 3476 (tire). From the raw log data, the following dataset can be extracted. The response variable is a binary variable $ { \small \textsc{{click}}}_i^\tau \in \{0,1\}$ that indicates whether the user clicked the ad or not. The relevant predictors include a categorical variable ${ \small \textsc{{Adexchange}}}$ of three levels that records from which ad-exchange the impression was generated, a categorical variable ${ \small \textsc{{Region}}}$ of 35 levels indicating provinces of user IPs, and finally 44 boolean variables, each a ${ \small \textsc{{Usertag}}}$, indicating whether a user belongs to certain user groups defined based on demographic, geographic and other information. We select the top-10 most frequent user tags and denote them by ${ \small \textsc{{Usertag}}}_1,\dots,{ \small \textsc{{Usertag}}}_{10} \in \{0,1\}$. Both ${ \small \textsc{{Adexchange}}}$ and ${ \small \textsc{{Usertag}}}$ are masked, and we do not know their real-world meaning.
Simulate advertisers with logistic regression. The raw data contains only five advertisers. In order to simulate new realistic advertiser, we fit a logistic regression and then perturb the fitted coefficients to generate more advertisers. We posit the following logistic regression model for click-through rates (CTRs). For a user $\tau$ that saw the ad of advertiser $i$, the click process is governed by
where the weight vectors $w_i \in {\mathbb R}^{47}$ are the coefficients to be estimated from the data. Note that ${ \small \textsc{{Adexchange}}}_1$ and ${ \small \textsc{{Region}}}_1$ are absorbed in the intercept. By running 5 logistic regressions, we obtain regression coefficients $w_1, w_2, \dots, w_5$. To visualize the fitted regression, in (ref) we show the estimated click-through rate distributions of the five advertisers. The diagonal plots are the histogram of CTRs, and the off-diagonal panels are the pair-wise scatter plots of CTRs. To generate more advertisers, we take a convex combination of the coefficients $w_i$'s, add uniform noise, and obtain a new parameter, say $w'$. Given an item, the CTR of the newly generated advertisers will be $\frac{1}{1 + \exp(\theta ^{\top} w')}$. The value distribution is the historical distribution of the simulated advertisers' predicted CTRs of the 1.8 million impressions.
In this section we aim to produce confidence interval of the revenue with the CI constructed from (ref), with a focus on the effect of Hessian estimation on the coverage. Firstly, the sum equals $n$ times the average price-per-utility of advertisers, a measure of efficiency of the system. Secondly, since most quantities in FPPE, such as revenue and social welfare, are smooth functions of pacing multipliers\,, being able to perform inference about a linear combination of $\beta$'s indicates the ability to infer first-order estimates of those quantities.
Setup. An experiment has parameters $(t,n, d, \alpha)$. Here $t$ is the number of items, $n$ the number of advertisers, and $\alpha$ is the proportion of advertisers that are not budget-constrained (i.e., $\beta = 1$). Parameter $d$ is a tuning parameter of the revenue variance estimator. It is the exponent of the finite-difference stepsize $\varepsilon_t$ in (ref), i.e, $\varepsilon_{{\mathcal{H}}, t}= t ^{-d}$. To control $\alpha$ in the experiments, we select budgets as follows. Give infinite budgets to the first $\lfloor \alpha n \rfloor $ advertisers. Initialize the rest of the advertisers' budgets randomly, and keep decreasing their budgets until their pacing multipliers\, are strictly less than 1. In the experiment $(t,n, d, \alpha)$, we first compute the pacing multiplier\, in the limit market using dual averaging xiao2010dual,gao2021online,liao2022dualaveraging. Then we sample one FPPE by drawing values from the synthetic value distribution obtained previously. Now given one FPPE, apply the formula in (ref) to construct CI and record coverage. The reported coverage rate for an experiment with parameters $ (t,n, d, \alpha)$ is averaged over 100 FPPEs.
Results. Representative results are presented in (ref); we present the full table in (ref). As the number of item increases, we observe the empirical coverage rate achieving the nominal 90% coverage rate, while the width of confidence interval is narrowing. We also observe that the confidence interval is robust against the Hessian estimation and the proportion of unpaced buyers; for different choices of exponent in the differencing stepsize ($\varepsilon_{{\mathcal{H}}, t}$ in (ref)) and proportion of unpaced buyers ($\alpha$), the coverage performance remains similar.
{\color{black}{
In this section we compare the Hessian-based revenue variance estimator in (ref) with $\varepsilon_{{\mathcal{H}},t} = t^{-0.4}$, the Hessian-free version in (ref), and a baseline estimator based on an i.i.d.\ price model.
The baseline variance estimator is $\hat \sigma ^{2} _{\text{naive}} = \frac1t {\sum_{\tau=1}^{t}} ({ p ^ \tau } - \bar p) ^{2} $, where $\bar p = \frac1t {\sum_{\tau=1}^{t}} { p ^ \tau }$. The limit of this estimator is $ \sigma_{\text{naive}} ^{2} = { \operatorname {Var} }(p^*(\theta)) $. The statistical model behind this method would be to assume that $\{ p^1,\dots, p^t\}$ are iid draws from some distribution, while totally ignoring the auction mechanism and the bidding behavior of the buyers. This is in contrast to the correct formula ${ \operatorname {Var} }(\tilde p ^*)$ in (ref) when a bid-gap condition holds. We note that this assumption is not correct, since the pacing multipliers change as a function of which items are sampled. Nonetheless, it has the following intuitive appeal: if we assume that the pacing multipliers are fixed, then this estimator does correctly estimate the price variance, regardless of market size (though note that revenue variance is not the same as price variance). Moreover, our results do show that the pacing multipliers, while not fixed, do concentrate around the limit pacing multipliers as the market grows.
We compare the confidence interval of the revenue with the CI constructed from (ref) against the naive CI described above. The reported coverage rate is over 500 FPPEs.
Results. Representative results are presented in (ref). We present the full table in (ref). We see that (1) the Hessian-free method is significantly better in the market where all buyers are budget exhausted ($I_= = \emptyset$, $\alpha = 0$ in the table). The Hessian-free method is able to determine that all the budgets will be exhausted, and thus the revenue equals the sum of budgets deterministically, while the naive method ignores this simple fact and puts an unnecessary interval on revenue. Note that the three methods will coincide when $\alpha = 1$ in large samples. (2) Although overall the three methods achieve the nominal coverage rate, the Hessian-based method is theoretically valid under mild assumptions on the FPPE, while the Hessian-free method is valid under an additional bid-gap assumption but is computationally cheaper since it does not need Hessian estimation.
}\color{black}}r} \end{table}
}
Setup. In this experiment, we fix the differencing stepsize in Hessian estimation to be $\varepsilon_{{\mathcal{H}},t} = t^{-0.4}$ and the proportion of unpaced buyers to be 30%, which is a realistic number for real-world auction platforms.
An experiment has parameters $(t,n, \pi)$, where $t$ is the number of items, $n$ the number of users, and $\pi$ the treatment probability (see (ref)). To model treatment application, we use the shift of value distribution. Choose two sets of logistic regression parameters, $\{ w_i(0) \}_i$ and $\{w_i (1)\}$. Then if a user $\theta$ is applied treatment $\omega \in \{0,1\}$, then its value to buyer $i$ will be $ 1 / (1 + \exp(w_i(\omega) ^{\top} \theta))$, $i\in[n]$. In an experiment, the limit revenues in the two limit markets ${ \textsf{{FPPE}}}(b,v(0),s,\Theta)$ and ${ \textsf{{FPPE}}}(b,v(1), s,\Theta)$, and the limit treatment effect will be calculated first. Then we perform the a/b test experiments 100 times, and construct 100 CIs for the treatment effect. We report coverage rates and widths of CIs.
Results. Representative results are presented in (ref); in (ref) we present the full results. First, the overall coverage rates across different market setups and treatment probabilities $\pi$ are around the nominal 90%, and the width of confidence interval shrinks as sample size grows. Second, when the number of items is sufficiently large (say over 400), we observe a $U$-shape relationship between the width of CI and treatment probability $\pi$; the CI widths are wider when $\pi$ is close to the extreme points (say 0.1 and 0.9) than when $\pi$ stays away from the extreme points. This is explained by the treatment effect variance formula in (ref). Holding the two variances fixed, the treatment effect variance tends to infinity if we send $\pi \to 0$ or $1$.
We introduced a theory of statistical inference for Fisher markets, resource allocation systems that deploy the CEEI mechanism, and first-price auction platforms. We showed that quantities observed in the finite market equilibrium observed from these systems are good estimators of their corresponding limit market values. We presented convergence rate results, asymptotic distribution characterizations, local minimax optimality results, and constructed confidence interval tools. Finally, we showed how to use these tools to develop a theory of statistical inference in A/B testing under competition effects.
A few open questions remain. In practice, the item arrival process exhibits nonstationarity and seasonality. A statistical theory for LFM and FPPE that incorporates temporal dependence is desirable. It would also be desirable to design a notion of online confidence intervals for the limit market, since, in practice, items typically arrive on platforms sequentially. For FPPE we assumed the absence of degenerate buyers in (ref); lifting this assumption would be interesting. Finally, we restricted our attention to the first-price setting for FPPE. In practice, second-price auctions are also widespread. A theory of statistical inference for second-price auctions is also desirable, though we expect it to be significantly weaker, due to computational complexity barriers, as well as non-uniqueness issues.
{\color{black}{ Beyond linear Fisher markets and FPPE, it would be interesting to investigate whether our proof techniques apply to other equilibrium models captured by mathematical programs. The Eisenberg-Gale convex program is known to work for several utility classes beyond linear utilities (as we study) including Leontief, constant-elasticity-of-substitution (CES), and Cobb-Douglas utilities nisan2007algorithmic. Later work has also showed that convex program variants exist for e.g. spending-restricted and utility-restricted versions of Fisher markets cole2017convex. In all these cases, it is possible to derive dual programs similar to the one we leverage, and they have a sum over prices in the objective cole2017convex, which may lend itself to our stochastic approximation approach (SAA). Several different convex programs are known for the Arrow-Debreu exchange model as well, see e.g. devanur2016rational.
A/B testing using one market is interesting. When both treatments are applied to the same market, the market equilibrium can still be described, and inferences about it can be made, using our theory. However, under this design, there are two layers of interference: (1) treatments 1 and 0 interfere with each other now that they are in the same market, and (2) the interference induced by market equilibrium. In this new setting, there are many fundamental questions that would need to be answered, such as what is the correct notion of treatment effect, and whether a given treatment effect can be estimated from observation of a single market. We believe this is a very interesting problem, and many of our tools can probably be used to analyze this problem in an FPPE framework. But the first step would be to formulate the types of treatment effects one would even work with, and we think this is a whole new paper worth of material to work out.
Buyer-side treatments, such as modifications to the advertiser UI for specifying auction parameters like target audiences and return-on-investment, are also of interest. However, since ad campaigns are typically configured only once, the budget-split design is not a natural fit for studying these treatments unless all buyers are required to use both the treatment and control UIs twice. }\color{black}}
\ACKNOWLEDGMENT{This research was supported by the Office of Naval Research awards N00014-22-1-2530 and N00014-23-1-2374, and the National Science Foundation awards IIS-2147361 and IIS-2238960. This work has been presented at Conference on Neural Information Processing Systems (2022), International Conference on Machine Learning (2023), INFORMS annual meeting (2023) Stanford Rising Star Workshop (2024), Workshop on Marketplace Innovation (2024), and the Ads Experimentation team at Meta. We thank attendees of all these talks for many helpful discussions.}
\ECSwitch
Based on our differentiability characterization, it is natural to search for a stronger form of (ref) and hope that such a refinement could lead to second-order differentiability. {\color{black}{(ref) provided three sufficient conditions for second-order differentiability. Condition (i) gives two such refinements of (ref). }\color{black}} Condition (ii) is motivated by the idea that the expectation operator tends to produce smooth functions. The exact smoothness requirement is presented in the appendix, which we show is easy to verify for several common distributions. Finally, Condition (iii) considers the linear-valuations setting of gao2022infinite, where the authors provide tractable convex programs for computing the infinite-dimensional equilibrium. Here we give another interesting properties of this setup by showing that the dual objective is $C^2$. Generalization to piecewise linear value functions will also be discussed at the end.
The tied buyers for an item will be useful for later discussions. Let $I(\beta, \theta) = \argmax_i{\beta_i v_i(\theta)}$ be the set of maximizing indices, which could be non-unique. We say there is no tie for item $\theta$ at $\beta$ if $I(\beta,\theta)$ is single-valued, in which case we use $i(\beta,\theta)$ to denote the unique maximizing index. Moreover, by Theorem 3.50 from beck2017first, the subgradient $\partial_\beta f(\theta, \beta)$ is the convex hull of the set $\{v_ie_i, i\in I(\beta,\theta) \}$. When $I(\beta,\theta)$ is single-valued, the subgradient set is a singleton, and thus $f$ is differentiable.
A natural idea is to search for a stronger form of (ref) and hope that such a refinement could lead to second-order differentiability. In particular, this section is concerned with statement (i) of (ref). First we show the condition based on the expectation.
We compare the integrability condition in the above theorem with (ref). Both (ref) and (ref) can be interpreted as a form of robustness of the market equilibrium. The quantity ${ \mathsf{{bidgap}}}(\beta,\theta)$ measures the advantage the winner of item $\theta$ has over other losing bidders. The larger ${ \mathsf{{bidgap}}}(\beta,\theta)$ is, the more slack there is in terms of perturbing the pacing multiplier before affecting the allocation at $\theta$. In contrast to (ref) which only imposes an item-wise requirement on the winning margin, the above assumption requires the margin exists in a stronger sense. Concretely, such a moment condition on the margin function ${ \mathsf{{bidgap}}}$ represents a balance between how small the margin could be and the size of item sets for which there is a small winning margin.
Second we consider the condition based on the essential supremum. For any buyer $i$ and her winning set $\Theta_i^*$, there exists a positive constant ${ \epsilon }_i > 0$ such that
It requires that the buyer wins the items without tying bids uniformly over the winning item set. The existence of a constant $K<\infty$ such that $1/{ \mathsf{{bidgap}}}(\beta,\theta) < K$ for almost all items makes a stronger requirement than (ref). From a practical perspective, it is also evidently a very strong assumption: for example, it won't occur with many natural continuous valuation functions. Instead, the condition requires the valuation functions to be discontinuous at the points in $\Theta$ where the allocation changes. Empirically, since $\beta^\gamma$ is a good approximation of $\beta^*$ for a market of sufficiently large size, (ref) can be approximately verified by replacing $\beta^*$ with $\beta^\gamma$. As a trade-off, (ref) is a weaker condition than (ref) but is harder to verify in practical application.
Below we present two examples where (ref) holds.
Now we consider the condition (iii) of (ref): linear valuations. We adopt the setup in Section 4 from gao2022infinite where we impose an extra normalization on the values; the reasoning extends to the cases where at any point there are at most two lines intersecting at that point. Suppose the item space is $\Theta = [0,1]$ with supply $s(\theta) = 1$. The valuation of each buyer $i$ is linear and nonnegative: $v_i(\theta) = c_i \theta + d_i\geq 0$. Moreover, assume the valuations are normalized so that $\int_{[0,1]}v_i\mathop{}\!\mathrm{d} \theta = 1 \Leftrightarrow c_i/2 + d_i = 1$. Assume the intercepts of $v_i$ are ordered such that $2 \geq d_{1}>\cdots>d_{n} \geq 0$.
We briefly review the structure of equilibrium allocation in this setting. By Lemma 5 from gao2022infinite, there is a unique partition $0 = a^*_0 < a_1^*<\cdots<a_n^*=1$ such that buyer $i$ receives $\Theta_i=\left[a_{i-1}^*, a_i^*\right]$. In words, the item set $[0,1]$ will be partitioned into $n$ segments and assigned to buyers $1$ to $n$ one by one starting from the leftmost segments. Intuitively, buyer 1 values items on the left of the interval more than those on the right, which explains the allocation structure. Moreover, the equilibrium prices $p^*(\cdot)$ are convex piecewise linear with exactly $n$ linear pieces, corresponding to intervals that are the pure equilibrium allocations to the buyers.
The above result also extends to most cases of piecewise linear (PWL) valuations discussed in Section 4.3 of gao2022infinite). In the PWL setup there is a partition of $[0,1]$, $A_{0}=0 \leq A_{1} \leq \cdots \leq A_{K-1} \leq A_{K}=1$, such that all $v_{i}(\theta)$'s are linear on $ [A_{k-1}, A_{k}]$. At the equilibrium of a market with PWL valuations, we call an item $\theta$ an allocation breakpoint if there is a tie, i.e., $I(\beta^*, \theta)= \argmax _i \beta_i { v_i(\theta) }$ is multivalued. Now suppose the following two conditions hold: (i) none of the allocation breakpoints coincide with any of the valuation breakpoints $\{A_k\}$, and (ii) at any allocation breakpoint there are exactly two buyers in a tie. Under these two conditions, one can show that in a small enough neighborhood of the optimal pacing multiplier $\beta^*$, the allocation breakpoints are differentiable functions of the pacing multiplier. This in turn implies twice differentiability of the dual objective by repeating the argument in the proof of (ref). {\color{black}{Intuitively, this occurs because under the two conditions, the PWL case behaves like the linear case in a sufficiently-small neighborhood around the equilibrium.}\color{black}} However, if either condition (i) or (ii) mentioned above breaks, the dual objective is not twice differentiable.
We first use a change of variable, and let $z = v / \|v \|_2 $ be the projection of $v$ onto the unit sphere. It represents the angular component of the vector $v$. Let $f(v, \beta) = \max_i \beta_i{ v_i(\theta) }$. Using a change of variable $z = v/\|v\|_2$ and $r =\|v\|_2$ and homogeneity of $f$, the integral $\int f( v, \beta) f_v \mathop{}\!\mathrm{d} v$ can be written as
where $\mathop{}\!\mathrm{d} z$ is the surface measure on the unit ball $S_n$ in ${\mathbb R^n}$. From this representation, it is not unreasonable to say that if $\int_0^\infty r^{n} f_v(rz) \mathop{}\!\mathrm{d} r$ is a smooth function of the angular component $z$, then ${\bar f}(\beta)$ will also be a smooth function of $\beta$. Taking $v_i = r z_i$, $v_k = z_k/z_i$, and so $ \int_0^\infty r^{n} f_v(rz) \mathop{}\!\mathrm{d} r =\int_0^\infty v_i^n f_v(v_iv_1, v_iv_2,\dots, v_i, \dots, v_iv_n) \mathop{}\!\mathrm{d} v_i/ (z_i)^n$. So equivalently we require smoothness of $v_{-i} \mapsto \int_0^\infty v_i^n f_v(v_iv_1, v_iv_2,\dots, v_i, \dots, v_iv_n) \mathop{}\!\mathrm{d} v_i$.
Now we make this precise. First we introduce some extra notations. For each $i\in[n]$, define the map $\sigma_i: {\mathbb R^n_+} \to {\mathbb R^n_+}$, $$\sigma_i(v) = [v_1v_i,\, \dots,\,v_{i-1}v_i,\, v_i,\, v_{i+1}v_i,\, \dots,\, v_nv_i ] ^{\top} $$ for $i\in[n]$, which multiplies all except the $i$-th entry of $v$ by $v_i$.
The above regularity conditions are easy to verify when the values are i.i.d.\ draws from a distribution. In that case, many smooth distributions supported on the positive reals fall under the umbrella of the described regularity. Below we examine three cases: the truncated Gaussian distribution, the exponential distribution and the uniform distribution.
When values are i.i.d.\ truncated standard Gaussians, the joint density $f(v) =c_1 \prod_{i=1}^n \exp(- v_i^{2} / 2)$ and $h_i (v_{-i}) = c_1 \int_{\mathbb R _+} v_i^n \exp ({- \frac12 v_i^{2} ( 1 + \sum_{k \neq i} v_k^{2})}) \mathop{}\!\mathrm{d} v_i = c_2 (\sum_{k \neq i} v_k^{2})^{-n/2},$ which are regular. Here $c_i$, $i=1,2$, are appropriate constants. Similarly, for the i.i.d.\ exponential case with the rate parameter equal to one, the density $f(v) = \prod_{i=1}^n \exp(- v_i)$ and $h_i (v_{-i}) = (\sum_{k\neq i} v_k)^{-n}$ satisfy the required continuity conditions. Finally, suppose the values are i.i.d.\ uniforms on $[0,1]$. The joint density is $f(v) = \prod_{i=1}^n { \mathds{1} }\{0<v_i < 1\}$ and for example, if $i=1$, $h_1(v_{-1}) = (\min\{1, v_2^{-1}, \dots, v_n^{-1} \})^{n+1}/(n+1)$, which also satisfies the required continuity conditions.
In this section we derive a closed form expression for $\nabla ^{2} {\bar f} (\beta)$ for some $\beta \in {\mathbb R^n_+}$ using tools from differential geometry. Let $f_v(v)$ be the density of values w.r.t.\ the Lebesgue measure on ${\mathbb R^n}$. Let ${\mathcal{K}} = \nabla^{2} {\bar f}(\beta)$. Then $\nabla^{2} H(\beta)= {\mathcal{K}} + { \operatorname*{diag}}(b_i / (\beta_i)^{2})$. Fix a buyer $k$. Now we derive ${\mathcal{K}}_{k,h}$ for $h\in [n]$. We need to introduce a few sets. Let
The cone $V$, which we call the winning cone of buyer $k$, is the set of valuation vectors such that buyer $k$ wins under the pacing profile $\beta$. The set $S_h$ is a face of $V$, which represents the values for which there is a tie between buyers $k$ and $h$. It is clear $\Pi_h$ is the projection of $S_h$ onto $\{v \in {\mathbb R^n}: v_h = 0 \}$. In (ref) we present an illustration of these sets.
We will show that the Hessian $\mathcal K$ can be characterized as
The formulae indicate that only the value of $f_v$ on the faces $S_h$, $h\neq k$ matters for the Hessian.
Let $\Delta = \beta_k e_k - \beta_h e_h$ and $\Delta_u = \beta_k e_k - u e_h$ for a scalar $u$. The $k$-th entry of $\nabla {\bar f} (\beta)$ is $\int { \mathds{1} }(V(\beta)) v_k f_v \mathop{}\!\mathrm{d} v$ and so the second-order derivative of ${\bar f}$ can be written as
Define the rotation matrix
The map $T_u$ is a diffeomorphism that maps $\{v: \Delta ^{\top} v \geq 0\}$ to the region $\{v: \Delta_u ^{\top} v \geq 0\}$. It can be seen that $T_u (\Delta / \|\Delta\|_2) = \Delta_u / \|\Delta_u\|_2$ and $T_{\beta_h} = I_n$. Notice that if we increase $\beta_h$, $h\neq k$, the face $S_h$ rotates inward in $V$, pivoting at the origin. By a result from Section 5 in kim1990cube, the derivative of the volume of a parametrized region can be written as a surface integral on the boundary of the region. Concretely, in our case, we have that
where $n(v)$ is the normal vector of $S_h$ pointing inside the winning cone $V$, and $\mathop{}\!\mathrm{d} \sigma_h$ is the surface measure on $S_h$. Now plug in
and obtain
Now we investigate ${\mathcal{K}}_{k,k}$. Notice that if we increase $\beta_k$, all $n-1$ faces, $\{S_h\}_{h\neq k}$, of the winning cone $V$ rotate outward, pivoting at the origin. And so we could again use the results from kim1990cube. However, we show a simpler approach to deriving ${\mathcal{K}}_{k,k}$ using first-order homogeneity of the function ${\bar f}(\beta)={\mathbb E}[\max_i \beta_i { v_i(\theta) }]$. By Euler's homogenous function theorem, we have ${\bar f}(\beta) = { \sum_{i=1}^n } \beta_i (\partial / \partial \beta_i) {\bar f}(\beta)$. Taking $(\partial / \partial \beta_k)$ on both sides we obtain $$\frac{\partial }{ \partial \beta_k } {\bar f}(\beta) = \frac{ \partial }{\partial \beta_k } {\bar f}(\beta) + \beta_k {\mathcal{K}}_{k,k} + \sum_{h\neq k} \beta_h {\mathcal{K}}_{k,h} \;,$$ and thus $ {\mathcal{K}}_{k,k} = -\sum_{h\neq k} \beta_h {\mathcal{K}}_{k,h} / \beta_k$.
\ECHead{Proofs of Fisher Market Results}