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.
99,232 characters · 22 sections · 73 citation commands
\thispagestyle{empty} \setcounter{page}{0} \setcounter{footnote}{0} \\
\makebox[\textwidth][c]{
} \setcounter{footnote}{1}\footnotetext{ \setstretch{1} Department of Economics, University College London; \hyperlink{mailto:[email removed]}{\color{black}[email removed]}. } \setcounter{footnote}{2}\footnotetext{ \setstretch{1} Department of Economics, Royal Holloway University of London; \hyperlink{mailto:[email removed]}{\color{black}[email removed]}. } \begingroup\renewcommand\arabic{footnote}\footnote{ We are grateful to Yeon-Koo Che, Tim Christensen, Mark Dean, Navin Kartik, Elliot Lipnowski, and Michael Woodford for their comments and suggestions.\\ First posted draft: 25 May 2020. This draft: \DDMonthYYYY\today. }\addtocounter{footnote}{-1}\endgroup
\setcounter{footnote}{0}
\makebox[\textwidth][c]{
}
Pricing and revenue projections are crucial elements of any firm's business plan. However, uncertainty about consumer willingness to pay makes both tasks challenging. While firms desire revenue guarantees, they also rely on future revenue projections for budgeting, inventory management, and capital investment decisions. These needs require reliable estimates of expected profits with confidence bounds. This is especially true in the analogous setting of government procurement, where the procurement process may be subject to administrative rules and regulations, while at the same time having an influence on the overall government budget. In such cases, having reliable projections of procurement results is crucial for planning and execution of public policy.
This paper proposes a novel data-based approach to address these challenges simultaneously. We consider a scenario where a firm faces uncertainty about the true distribution of consumer types, building on the classic framework of MaskinRiley1984RAND. We allow the firm to design mechanisms (menus of price-quantity pairs) while acknowledging limitations in real-world information access.
Unlike many existing robust mechanism design approaches, we assume the firm observes only a finite sample drawn from the unknown distribution. This is a natural assumption insofar as it approximates the type of information that organizations tend to have at their disposal in practice, often as the result of market research LuskShogren2007Book. Accordingly, there has been growing interest in analyzing mechanism design with random samples, as exemplified by notable recent papers including \citetalias{FU2021105230}, Allouah2022, and XieZhuShishkin2023WP.
Our contribution to this literature is twofold. First, we provide a class of simple mechanisms with robust finite-sample revenue guarantees: empirically optimal mechanisms. Second, we develop a toolkit to perform statistical inference on the profit obtained for any arbitrary mechanism, including the empirically optimal one. This enables a data-driven approach to the evaluation and comparison of different pricing strategies.
Empirically optimal mechanisms are remarkably simple to implement and boast notable revenue guarantees and robustness properties. Specifically, empirically optimal mechanisms simply involve consistently estimating the true distribution from a sample and implementing the mechanism that would be optimal for that estimated distribution. This gives rise to a data-based mechanism that is not only asymptotically optimal, but also strongly robust to small perturbations of the estimated distribution, owing to profit being Lipschitz continuous in the estimate of the distribution. Furthermore, they induce finite-sample, exponential bounds for profit and regret (the difference to the optimal profit).
Equally important is the fact that that empirically optimal mechanisms serve as a tool for estimating and conducting inference on the profit obtained with any mechanism, including the optimal one. This allows the principal to obtain reliable confidence intervals for profits achievable with any mechanism, to compare and test profits and regret arising from different feasible pricing strategies, and also estimate the maximum achievable profit, which can be of interest to estimate the expected return to an investment or long-run profitability, as better information about the type distribution becomes available. In the analogous case of procurement from a firm, the ability to obtain reliable expenditure projections from any specific policy is particularly valuable, as the procurement process may be subject to idiosyncratic administrative constraints. Methodologically, we prove a novel envelope theorem to establish consistency and asymptotic normality of our proposed estimator via a functional delta method. We then demonstrate the effectiveness of bootstrap implementations for conducting inference through Monte Carlo simulations, which suggest that the empirical coverage of our estimators approximates well the associated confidence intervals, even with relatively few samples.
Finally, we illustrate how our results on empirically optimal mechanisms extend to an auction setting. We consider the case where the firm auctions a single item to a finite number of risk-neutral bidders with independent private values drawn from the same distribution. In particular, analogue versions of asymptotic optimality and profit and regret guarantees are shown to hold in this setting as well.
Empirically optimal mechanisms correspond to one of the simplest forms of statistically informed mechanism design: observing a sample, estimating a distribution, and implementing a mechanism that is optimal for the estimated distribution. As we demonstrate, this extremely simple approach boasts sound revenue guarantees and allows practitioners to estimate the maximum profit attainable. Our results on expected profit estimation enable confidence interval construction and hypothesis testing, valuable tools for practitioners and researchers. We believe this data-driven perspective on robust mechanism design holds promise for the broader study of mechanism design under model uncertainty.
The most directly related literature studies robust mechanism design with a monopolist who does not form a prior about consumers' willingness to pay, but has access to a random sample from this distribution. Relatively recent papers with this set-up include ColeRoughgarden2014STOC14, DHANGWATNOTAI2015318, HuangMansourRoughgarden2018SIAMJComput, GuoHuangZhang2020ACM, FU2021105230, Allouah2022, and XieZhuShishkin2023WP. Most of the work in this body of literature is concerned with either providing revenue guarantees based on a sample, or leveraging the sample to design a mechanism that maximizes profits conditional on the limited information available.
A sizeable literature has been dedicated to providing sample-based revenue guarantees in auctions. For example, HuangMansourRoughgarden2018SIAMJComput give polynomial upper an lower bounds on the number of samples required to achieve a share $1 - \varepsilon$ of the optimal profit, assuming a single buyer with value drawn from a distribution with the monotone hazard rate property. ColeRoughgarden2014STOC14 provide a similar characterization of the sample complexity of optimal mechanisms, but for multiple bidders. GuoHuangZhang2020ACM improved on the results of the previous paper by providing upper and lower bounds that differ by at most a poly-logarithmic factor.
XieZhuShishkin2023WP consider a different setting, where a monopolist has access to a random sample of data on buyers' valuations and covariates, and uses it to conduct third-degree price discrimination or to determine an uniform price. They provide a lower bound on regret, measured as the minimax difference in expected revenue, for any sample-based strategy as a function of the sample size. Moreover, they provide pricing strategies that attain this lower bound for both the third-degree price discrimination and uniform pricing regimes, and thus have the fastest possible rate of convergence to the optimal profit as the sample size increases.
Our first set of results is very close to this literature, as it provides revenue guarantees for the empirically optimal mechanism as a function of the sample size. Naturally, such results can also be inverted to obtain the number of samples that is needed to achieve a given share of the optimal profit with high probability. On the other hand, we significantly diverge from the papers cited above in the results concerning inference for any given mechanism. In a sense, the simplicity of the empirically optimal mechanism allows us to use it as an econometric tool to generate statistical analyses from the sample that are more detailed than simply providing bounds on regret.
Another strand of the literature is concerned with designing a mechanism that makes optimal use of the information contained in a sample of consumers' valuations. Early work by Segal2003AER and BaligaVohra+2003 study a setting where samples are elicited from buyers' bids themselves, under different assumptions about the underlying distribution of valuations. They both propose mechanisms which induce consumers to reveal their own type, while simultaneously allowing the firm to use others' bids to infer the distribution and design the mechanism accordingly. DHANGWATNOTAI2015318 follow BaligaVohra+2003 in designing a mechanism with a random reserve price drawn from the empirical distribution function of buyers' bids, and show that their Single Sample mechanism approximates that of an optimal auction. FuHaghpanahHartlineKleinberg2020WP posit that the possible distributions of bidders' types belongs to a finite set, and determine the minimum number of samples that an auctioneer needs to extract the full surplus without prior knowledge of the true distribution.
We are not concerned with making optimal use of the data to extract surplus. Rather, we study a particular mechanism and focus on providing a toolkit for conducting valid non-parametric inference in the mechanism design setting. Nevertheless, in \hyref{section:eom:rev}[Section] we quantify the extent to which the empirically optimal mechanism can be improved upon in terms of profit by any sample-based mechanism, and find that the scope for such improvements quickly vanishes as the sample size increases.
More generally, the present paper fits into the broader literature on mechanism design when the principal has perfect knowledge not about the whole distribution, as in the more standard models MaskinRiley1984RAND, but only about some features of this distribution. With such information, the firm can then narrow down the set of possible distributions to consider and adopt a pricing strategy that maximizes the worst-case profit or minimizes the worst-case regret. This approach tries to address the concern that the optimal mechanism is not robust to the firm having less than exact information on the distribution of consumers' willingness-to-pay, in line with the general research program of robust mechanism design.
In this broader literature, the papers which are closest to ours are BergemannSchlag2008JEEA BergemannSchlag2008JEEA, BergemannSchlag2011JET and CarrascoLuzKosMessnerMonteiroMoreira2018JET. These papers model a firm that does not know the distribution of consumer types, but has access to imperfect information that allows it to refine the set of possible distributions. Focusing on a linear specification, they assume the firm acts as if it faces an adversarial nature that chooses a distribution to maximize regret.\footnote{ BergemannSchlag2011JET also consider the case where nature minimizes profit and show the firm chooses a deterministic uniform pricing rule. } BergemannSchlag2008JEEA assume that the firm knows only an upper bound for the support; BergemannSchlag2011JET study the case where the firm also knows that the true distribution of consumers' willingness-to-pay is in a given neighbourhood of a given target distribution; CarrascoLuzKosMessnerMonteiroMoreira2018JET posits that the firm knows either the first moment and an upper bound for the support of the distribution,\footnote{ This is also the case in a closely related paper, CarrascoLuzMonteiroMoreira2018ET, which relaxes the assumptions that consumers' utility function is linear in quantity and that the firm's cost is also linear. } or the first two or three moments of the distribution. These papers then characterize the regret-minimizing mechanisms, whereby the firm hedges against uncertainty by randomizing over prices. Our analysis shows that, in addition to its other desirable properties, the empirically optimal mechanism generates nearly minimal worst-case regret in the sense of these papers.
In another related paper, MadaraszPrat2017REStud allow for a firm that is uncertain over both the distribution of types and the functional form of consumers' utility functions, while at the same time endowing the firm with a possibly misspecified benchmark model of consumer demand. They provide a uniform bound on regret that depends on the distance between the firm's benchmark model and the truth, where the measure of distance between models is related to the largest absolute value of the difference of willingness-to-pay across all possible types and quantities. Instead of looking at the worst-case scenario solution, the authors show that adjusting the pricing strategy that is optimal for the misspecified model in a specific manner involving this distance leads to a deterministic uniform bound on regret, similar to the probabilistic bound provided by the empirically optimal mechanism.
A brief outline of the paper is as follows. \hyref{section:setup}[Section] introduces the main theoretical framework. In \hyref{section:eom}[Section], we define our class of empirically optimal mechanisms and examine some of their main properties: asymptotic optimality and profit guarantees. After exploring this particular class of mechanisms, in \hyref{section:inference}[Section] we turn to the question of providing a statistical toolkit to estimate and conduct inference on profit, including optimal expected profit. \hyref{section:auctions}[Section] illustrates an extension of our results to the auction setting with independent private values. Finally, we conclude with a discussion of specific suggestions for further work in \hyref{section:conclusion}[Section]. All omitted proofs are included in the \hyref{section:appendix:proofs}.
Let $\Theta:=[\underline \theta, \overline \theta]\subset \mathbb R$, denote the set of feasible consumer types, which are distributed according to the cumulative distribution $F_0 \in \mathcal F$. Denote by $\mathcal F$ the set of all distributions on $\Theta$ endowed with the supremum-norm ${\|\cdot\|}_\infty$, i.e., ${\|F\|}_\infty := \sup_{t \in \mathbb R} |F(t)|$ for all $F \in \mathcal F$. Consumers' utility is given by $u(\theta,x,p)=v(\theta,x) - p$, where $\theta$ is the consumer's type, $x \in X:=[0, \overline x]$ denotes quantity, and $p\in \mathbb R_+$ price. We assume that $v$ is twice continuously differentiable, concave in $x$, supermodular, $v(\underline \theta,x)=v(\theta,0)=0$ for all $\theta$ and $x$, increasing in both arguments, and, wherever positive, strictly so.
The firm can choose a menu or mechanism $M$ from the set $\mathcal M$ of all compact menus $M' \subset X \times \mathbb R_+$ containing the element $(0,0)$. These comprise pairs of quantity and prices that the consumers can choose, with the option of consuming nothing being always available. We impose the further restriction that if $(x,0) \in M'$, then $x=0$; that is, the firm does not give away strictly positive quantities of the good for free.\footnote{ This restriction facilitates \hyref{section:inference}[Section]'s inference exercise for an arbitrary fixed menu and is without loss of revenue from the firms' perspective. } The firm incurs a twice differentiable, convex, and strictly increasing cost for quantity sold, $c: X\to \mathbb R$, where $c(0)=0$. When choosing menu $M\in \mathcal M$ and facing a distribution of consumer types $F \in \mathcal F$, the firm's expected profit $\pi(M,F)$ is given by
for some $(x(\theta),p(\theta)) \in \operatorname*{arg\,max}_{(x,p) \in M} u(\theta,x,p)$, with ties broken in favor of the firm.
Our setup encompasses many of the variations in the literature, being mostly the same as that in the one buyer version of Myerson1981MOR and MaskinRiley1984RAND, except that there $c$ is assumed to be linear and $\mathcal F$ corresponds to the distributions with a strictly positive density. MussaRosen1978JET, instead, assume that $v(\theta,x)=\theta\cdot x$ and specify $c$ to be strictly convex. In BergemannSchlag2011JET and CarrascoLuzKosMessnerMonteiroMoreira2018JET, $v(\theta,x)=\theta\cdot x$ and $\mathcal F$ is a subset of distributions that satisfy some pre-specified conditions.\footnote{ It does not include, for instance, the case where the firm's cost depends directly on the consumers' type as in Example 4.1 in Toikka2011JET. }
We consider the case where neither the firm nor the consumers know the true distribution of types, $F_0 \in \mathcal F$, which motivates the choice of dominant strategies as our solution concept. Instead, the firm has access to a sample $S^n=\left( \theta_i,\,i=1,...,n\right) \in \Theta^n$, $n \in \mathbb N$, where each $\theta_i$ is independently drawn from $F_0$. As discussed later (\hyref{section:conclusion}[Section]), such a sample can and will often arise from, for instance, market research previously conducted. This gives rise to the problem of selecting a menu depending on the realized sample. Let $\mathcal S$ denote the set of all samples, $\mathcal S:=\bigcup_{n \in \mathbb N}\Theta^n$. A sample-based mechanism is then a mapping $M_S: \mathcal S \to \mathcal M$, which selects a specific menu depending on the realized sample.
The robust mechanisms mentioned earlier can easily be adjusted to incorporate the information in the sample in order to estimate the features of the distribution that they assume to be known. For example, given a particular sample $S^n$, the firm can then estimate the support of the true distribution and implement the mechanism given in BergemannSchlag2008JEEA. Alternatively, it can estimate the first few moments of the true distribution and implement the mechanism in CarrascoLuzKosMessnerMonteiroMoreira2018JET. A natural question is then whether, given sampling uncertainty, these sample-based mechanisms would exhibit probabilistic robustness properties akin to the deterministic ones that hold when these features are perfectly known. This question is relevant in practice since any information about an unknown distribution is usually obtained from finite data. We therefore take a more direct and, arguably, simpler approach that makes full use of the sample itself to “learn” about the underlying true distribution and inform mechanism choice.
In this section, we introduce the class of empirically optimal mechanisms. This class of mechanisms is defined by two elements: an estimator of the true distribution and a mapping that takes each estimated distribution to a menu that would be optimal were the estimate to coincide with the true distribution.\footnote{ Note that, if the seller did have a prior, $\mu \in \Delta (\Delta(\Theta))$, over the set of possible distributions, it would still be sufficient to consider only the expected distribution according to the seller's posterior, $\mathbb E_{\mu}[F|S^n] \in \mathcal F$, in order to determine which mechanism to choose. That is, due to linearity of the profit function on the distribution, $\max_{M \in \mathcal M} \mathbb E_{\mu}[\pi(M,F)|S^n]=\max_{M \in \mathcal M} \pi(M,\mathbb E_{\mu}[F|S^n])$. }
Let $\widehat{\mathcal F}$ denote the set of estimators that are consistent for $F_0$, that is, the set of estimators $\hat F$ such that (i) $\hat F: \mathcal S \to \mathcal F$; and (ii) ${\|\hat F(S^n)-F_0\|}_\infty \overset{p}{\to}0$, for any $F_0$ in $\mathcal F$. Let $M^*:\mathcal F \to \mathcal M$ be a fixed selection from the set of optimal menus for every distribution, that is, $\forall F \in \mathcal F$, $M^*(F) \in \mathcal M^*(F):=\operatorname*{arg\,max}_{M \in \mathcal M}\pi(M,F)$. An empirically optimal mechanism $\hat{M}^*$ is a sample-based mechanism that simply composes together a consistent estimator and a selection from the set of optimal menus, that is, $\hat{M}^*=M^* \circ\hat F$. We refer to the set of empirically optimal mechanisms as ${\widehat{\mathcal M^*}}$.
While extremely simple, nothing ensures us that such a sample-based mechanism is either well-defined in general environments or that it constitutes a reasonable approach to pricing under uncertainty. The purpose of this section is to address these issues and show that this simple approach to pricing delivers several desirable properties including strong probabilistic robustness guarantees.
In order to show that the set of empirically optimal mechanisms ${\widehat{\mathcal M^*}}$ is nonempty, we start by briefly noting that an optimal menu exists for any distribution $F \in \mathcal F$. Formally, we have that $\mathcal M^*(F)\ne \emptyset$ for all $F \in \mathcal F$ --- we include a formal proof of this statement in \hyref{appendix:lemma:existence:proof}. Since this implies that a selection $M^*: \mathcal F \to \mathcal M$ such that $M^*(F) \in \mathcal M^*(F)$ exists, and as there are consistent estimators for any $F_0\in \mathcal F$, the set of empirically optimal mechanisms ${\widehat{\mathcal M^*}}$ is nonempty. An example of a consistent (and unbiased) estimator for $F_0$ is the empirical cumulative distribution, defined as $\hat F(S^n)(\theta)=\frac{1}{n}\sum_{i=1}^n\mathbf 1_{\{\theta_i\leq \theta\}}$. Moreover, for any $F_0 \in \mathcal F$, it has a uniform rate of convergence, that is, ${\|\hat F(S^n)-F_0\|}_\infty\overset{p}{\to}0$ (in fact, by the Glivenko--Cantelli theorem, uniform convergence occurs almost surely).
Note that under some specific conditions, an exact characterization of the set of optimal menus is known. For instance, if $v(\theta,x)=\theta\cdot x$ and $c(x)=\overline c \cdot x$, it is well-known that any optimal mechanism is $F$-almost everywhere equal to an indicator function $\mathbf 1_{\{p^*\geq \theta\}}$, where $p^*\in \operatorname*{arg\,max}_{p \in \operatorname*{supp}(F)}(p-\overline c)\cdot \int \mathbf 1_{\{p\geq \theta\}}\mathop{}\!\mathrm{d} F(\theta)$. Such an explicit solution simplifies the problem of characterizing empirically optimal mechanisms dramatically. When, instead, $v$ is multiplicatively separable, and $F_0$ is absolutely continuous and has convex support, any optimal mechanism is almost everywhere equal to pointwise maximization of the ironed virtual value as shown in Toikka2011JET. Hence, the problem of characterizing empirically optimal mechanisms can be made computationally tractable by ensuring not only consistency, but also absolute continuity and convex support of estimates $\hat F(S^n)$. Although the empirical cumulative distribution fails to be absolutely continuous, one such estimator $\hat F$ can be easily obtained by adopting any smooth interpolation of the empirical cumulative distribution, for example a linear interpolation, a cubic spline, or an interpolation relying on Bernstein polynomials.\footnote{ In \hyref{appendix:other-proofs}, we provide a simple proof for the fact that linear interpolations retain the uniform convergence (and therefore consistency) properties of the empirical distribution. See BabuCantyChaubey2002JSPI and Leblanc2011AnnInstStatMath for details on interpolation of the empirical cumulative distribution using Bernstein polynomials. }
Having defined our class of empirically optimal mechanisms, we establish in this section that they are asymptotically optimal: the realized expected profit given the mechanism converges in probability to the optimal expected profit as the sample size grows.
Such convergence is not guaranteed for arbitrary sample-based mechanisms, even for those that have desirable robustness properties, as it requires that the sample-based mechanism makes full use of the sample. For instance, if the mechanism relies only on statistics such as estimates for a finite number of moments or the support of the distribution, then it is immediate that it will not, in general, converge in probability to the optimal expected profit. Relying on an estimator for the true distribution itself (an infinite-dimensional parameter) is then key to obtaining asymptotic optimality.
We start by making an important observation:
We defer the proof to \hyref{appendix:lemma:profit:lipschitz}, but highlight the main steps here. The proof of \hyref{lemma:profit:lipschitz}[Lemma] first makes use of the revelation principle to focus on the elements of any arbitrary menu that are payoff relevant, as these are given by a bounded non-decreasing function, and hence of bounded variation. Then, we appeal to a result that provides an upper bound on Riemann--Stieltjes integrals of functions of bounded variation to obtain the result. In particular, we find a Lipschitz constant of at most
For every $F \in \mathcal F$, define the firm's value function as \[\Pi(F):=\sup_{M \in \mathcal M}\pi(M,F).\] \hyref{lemma:profit:lipschitz}[Lemma] leads to a further result, this time regarding (Lipschitz) continuity of the value function:
Finally, the desired result of asymptotic optimality of our class of empirically optimal mechanisms follows immediately:
\hyref{proposition:asymptotic-optimality}[Proposition] provides a simple justification for using an empirically optimal mechanism to guide the firm's pricing strategy: as the sample size grows large, such sample-based mechanisms deliver an expected profit close to the optimal one. We stress the minimal informational assumptions made. In particular, this result does not depend on the firm knowing the support of the true distribution $F_0$ ex ante, as the empirically optimal mechanism is defined making use only of the estimated cumulative distribution and there are consistent estimators that require no assumptions on (and in fact, asymptotically learn) the support of $F_0$. Moreover, as $\Pi(F_0)-\pi(\hat{M}^*(S),F_0)\leq 2 L {\|\hat F(S)-F_0\|}_\infty$, we conclude that empirically optimal mechanisms are robust in a sense akin to BergemannSchlag2011JET, since for any $\varepsilon>0$, samples inducing ${\|\hat F(S)-F_0\|}_\infty<\varepsilon$ imply that $\Pi(F_0)-\pi(\hat{M}^*(S^n),F_0)\leq 2 L \varepsilon$.
While some sample-based implementations of existing robust mechanisms would not be asymptotically optimal, it is possible that others would. Thus, an obvious question is: Do empirically optimal mechanisms provide robustness guarantees with finite samples that render them especially appealing? In this section, we argue that this is indeed the case.
Robustness properties of mechanisms regard worst-case scenarios. The existing literature has focused on two main properties. One corresponds to the worst-case profit that the firm can expect given that the true distribution lies in a specific set $A \subseteq \mathcal F$. This is in part motivated by appealing to the characterization of preferences exhibiting ambiguity aversion by GilboaSchmeidler1989JMathEcon, which entails a maxmin representation, whereby the decision-maker (here, the firm) evaluates each act (mechanism) by assuming the worst-case payoff. The robustness of a specific mechanism according to this criterion is then given by the lower bound on expected profit it can attain, $\min_{F \in A}\pi(M,F)$. The second robustness criterion that has been considered in the literature depends on the notion of regret: How much profit the firm may be forgoing by committing to mechanism $M$ when the true distribution is $F_0$, that is, $R(M,F_0):=\Pi(F_0)-\pi(M,F_0)$.
A simple implication of \hyref{lemma:profit:lipschitz}[Lemmas] and (ref) is that we can immediately obtain probabilistic bounds on regret and on how far the realized expected profit may be from the profit the firm expects to obtain given its estimated distribution.
While \hyref{proposition:regretbounds}[Proposition] is a trivial observation, it enables the firm to obtain strong, non-asymptotic probabilistic bounds on both profit and regret whenever basing an empirically optimal mechanism on an estimator $\hat F$ with specific properties. Whenever the firm knows an upper bound $\overline \theta$ for the support of the true distribution, $L$ can be obtained in a way that depends exclusively on known constants and these probabilistic profit and regret guarantees can be computed explicitly. The next two examples illustrate how this result can be applied by focusing on estimators $\hat F$ with well-known properties, such as the empirical cumulative distribution and smooth interpolations of it.
As this next example shows, under some assumptions on the true distribution $F_0$ one can even obtain not only non-asymptotic, but also deterministic (i.e., non-probabilistic) regret and confidence bounds.
Other sample-based mechanisms could potentially yield even stronger robustness properties. However, for any sample-based mechanism $M_S$, one has
As the examples above show, choosing $\hat F$ appropriately ensures that $\mathbb P(R(\hat{M}^*(S^n),F_0)>\delta)$ declines exponentially with $n$. Hence, the gains in profit and regret guarantees from implementing alternative pricing policies are modest at best, in a formal sense.
To conclude this section, we note that \hyref{proposition:regretbounds}[Proposition] can instead be used to determine how many samples the firm requires in order to obtain specific robustness guarantees when relying on empirically optimal mechanisms. That is, another reading of \hyref{proposition:regretbounds}[Proposition] is that the firm only needs at most $N$ samples --- where $N$ is the smallest integer such that $\alpha\geq p(N,\delta/L)$ --- to secure at most $2\delta$ of regret with probability $1-\alpha$. Alternatively, the same $N$ samples provide a (conservative) confidence interval for profit with range $2\delta$ and confidence level of $1-\alpha$. This results in a non-asymptotic sample complexity bound for a specific class of sample-based mechanisms. In contrast to the sample-complexity bounds obtained in HuangMansourRoughgarden2018SIAMJComput, which pertain to the share of the optimal profit that the firm is able to secure, $R(M,F_0)/\Pi(F_0)$, we focus on bounding regret directly and our bounds are not asymptotic, that is, they hold for finite samples.
While the revenue and regret guarantees derived in the previous section are useful, it is often crucial for a firm to to be able to obtain consistent projections for the profit for any given pricing strategy. This consistency is essential for informing various business activities, such as budget planning and inventory management, based on reliable profit estimations. In this section, we show how to obtain consistent and unbiased estimates and conduct inference on the expected profit.
Our results enable unbiased and consistent estimation of and inference on the expected profit not only of empirically optimal mechanisms but of any given mechanism $M \in \mathcal M$. Moreover, we show how empirically optimal mechanisms serve a special purpose, in that they can be used to estimate and conduct inference on the optimal expected profit. With these tools, one can provide confidence intervals for the expected profit with specific asymptotic coverage for any one mechanism, calculate probabilistic bounds for regret, or test whether one mechanism yields a higher expected profit than another.
An immediate consequence of Lipschitz continuity of the firm's profit function with respect to the distribution is that, for any mechanism and any consistent estimator of the distribution of types, one can consistently estimate the expected profit that such a mechanism would generate.
An important aspect of estimation is the ability to conduct inference. For instance, the firm could be interested in using statistical inference in order to compare different mechanisms, that is, to test whether a specific mechanism would deliver a higher expected profit than another. Another possible application would be to obtain valid confidence intervals for the expected profit under a particular mechanism, as it is an arguably crucial tool for the development of routine business activities such as drawing up budgets under different scenarios, with varying degrees of confidence.
While the firm could potentially derive confidence intervals for the expected profit by adjusting \hyref{proposition:regretbounds}[Proposition] and \hyref{example:ecdf}[Example] to the mechanism it is considering, these bounds would exhibit two drawbacks when used for this purpose. First, they require knowledge of $\overline \theta$, the upper bound on the type distribution. Second, and more critically, they generally do not provide the correct asymptotic coverage, that is, they would be exceedingly conservative.
In order to address these drawbacks, we suggest a simple estimation procedure that does yield asymptotically valid inference. First, we focus on the empirical distribution function as our estimator, since it admits a functional central limit theorem (by Donsker's theorem) when properly centered and rescaled. Then, because profit is linear and continuous in the type distribution, it is Fr\'{e}chet differentiable, with derivative given by $\dot \pi_M(\cdot) = \pi(M,\cdot)$.\footnote{ The Fr\'{e}chet derivative $\dot \pi_M$ is defined on the space of functions on $\Theta$ of bounded variation endowed with the supremum-norm. We refer to the appendix for details. } One can thus obtain the asymptotic distribution of our consistent estimator for the expected profit $\pi(M,\hat F(S^n))$ by appealing to a simple functional Delta method result.
\hyref{theorem:profit:asymptotic-normality}[Theorem] states that the distribution of the empirical process, \[ G_n:=\sqrt n\left(\pi(M,\hat F(S^n))-\pi(M,F_0)\right),\] converges weakly to $N(0,\sigma_{M,F_0}^2)$; proof is given in \hyref{appendix:theorem:profit:asymptotic-normality}. A question then arises of how to estimate, in practice, the asymptotic distribution in a consistent manner, as it depends on the unknown distribution $F_0$. We provide two alternatives. One option is the use of a plug-in estimator for $\sigma_{M,F_0}^2$. This can be done directly --- as the functional dependence of $\sigma_{M,F_0}^2$ on $F_0$ is known and a consistent estimate for $F_0$ is readily available --- or by following other plug-in methods as those in Shao1993AnnStat. Another option is to rely on the classical bootstrap to approximate the distribution of $G_n$ by the distribution of $\hat G_n:=\sqrt n\left(\pi(M,\hat F(S^n_B))-\pi(M,\hat F(S^n))\right)$, conditional on $S^n$, where $S^n_B$ denotes the resampling of $n$ observations from $S^n$ with uniform weights. That this approach does in fact consistently estimate the limiting distribution was shown by Parr1985StatProbL.
We note that other bootstrap methods would also yield consistent estimates, such as subsampling (bootstrap without replacement) PolitisRomano1994AnnStat or Jackknife procedures Parr1985JRRS. Moreover, given that the Fr\'{e}chet derivative of profit is sufficiently well-behaved, under some smoothness assumptions on the true distribution $F_0$, smoothed versions of the bootstrap CuevasRomo1997AnnInstStatMath can also be considered.
We now extend our statistical inference results, highlighting how empirically optimal mechanisms can be used to provide a consistent and asymptotically normal estimator for optimal profit.
Given that the firm's value function is Lipschitz continuous in the distribution and that empirically optimal mechanisms attain the optimal profit for a consistent estimate of the true distribution, it is easy to see that one can then use them as a tool to consistently estimate the optimal profit that the firm would obtain, were it to know $F_0$. We formalize this observation as follows:
It is less straightforward that one could take an approach to conducting inference on the optimal profit similar to that derived for fixed mechanisms. Specifically, this would require proving that the firm's value function $\Pi$ is also Fr\'{e}chet differentiable.\footnote{ In fact, the now standard functional Delta method requires only the weaker notion of Hadamard differentiability; see, e.g., VaartWellner1996. However, the stronger notion of Fr\'{e}chet differentiability has the benefit of allowing us to bypass the measurability complications that arise when using weaker notions. } We confirm that indeed such an approach is valid by proving an interesting technical result in this generalized Maskin--Riley setup: an envelope theorem for the firm's value function. In other words, our next result --- for which the proof is given in \hyref{appendix:theorem:optimal-profit:frechet} --- shows that the value function is Fr\'{e}chet differentiable at any distribution $F \in \mathcal F$ and that its Fr\'{e}chet derivative coincides with that of the expected profit at $F$ with the optimal menu for $F$.
The proof can be found in \hyref{appendix:theorem:optimal-profit:frechet}. We note that \hyref{theorem:optimal-profit:frechet}[Theorem] constitutes a much stronger result than the standard envelope theorem.\footnote{ The results in MilgromSegal2002Ecta yield only directional derivatives and are insufficient to deliver asymptotic normality of our estimator. } It is exactly owing to delivering on a stronger notion of differentiability that we obtain asymptotically valid inference. Specifically, defining the empirical process $\hat G_n:=\sqrt n\left(\Pi(\hat F(S^n_B))-\Pi(\hat F(S^n))\right)$, conditional on $S^n$, an adapted version of \hyref{theorem:profit:asymptotic-normality}[Theorem] ensues:
In this case, opposite to the case of inference under a fixed mechanism, we do not have a valid (consistent) plug-in estimator for $\sigma_{F_0}^2$, which depends on $F_0$ and, more problematically, also on an optimal mechanism under the distribution $F_0$, $M_0 \in \mathcal M^*(F_0)$. An important argument in favour of a bootstrap approach to estimating the asymptotic distribution in this case is that it bypasses this issue.
Under some conditions, it may make sense to rely on different estimators. For instance, as discussed in \hyref{example:iecdf}[Example], when $v(\theta,x)$ is multiplicatively separable and $F_0$ is known to be absolutely continuous and with compact and convex support, the functional form of the solution is exactly known. This allows for a drastic simplification of the problem from a computational point of view since it dispenses with the hurdle of finding the optimal mechanism for a given distribution. Especially in the context of implementing a bootstrap approach, the gains can be substantial. However, an estimate of the ironed virtual value depends on a suitable estimate of the density $f$. Therefore, we find it especially relevant that, when $F_0$ is known to be absolutely continuous, one can use as an estimator the simple linear interpolation of the empirical distribution discussed earlier to obtain a bootstrap estimator for the asymptotic distribution. Further, we note that this extremely simple approach is not only consistent for the true distribution $F_0$, but also for its density.
Estimating the optimal expected profit may be relevant for investment decisions, as it provides an upper bound on the return of a given investment. Furthermore, these results can also be used to estimate regret. As regret, $R(M,F)$, is given by $R(M,F)=\Pi(F)-\pi(M,F)$, it is Fr\'{e}chet differentiable at any distribution $F\in \mathcal F$, for any fixed $M \in \mathcal M$, as the sum of Fr\'{e}chet differentiable functionals is itself Fr\'{e}chet differentiable. Then, using similar arguments as those in \hyref{proposition:optimal-profit:consistency}[Proposition] and \hyref{theorem:optimal-profit:asymptotic-normality}[Theorem], one can conduct inference on regret. Consequently, for any mechanism $M \in \mathcal M$, one can not only obtain asymptotically valid probabilistic bounds for expected profit, but also for regret.
To conclude this section, we present empirical evidence on the finite sample properties of our estimators.
\afterpage{
}
We conduct Monte Carlo simulations on the empirical coverage of the confidence intervals for expected profit under a fixed mechanism --- uniform pricing, with the price set at $1/2$ --- and for the optimal expected profit, using empirically optimal mechanisms for the empirical distribution. We use the approximation obtained by classic bootstrapping ($N$ out of $N$), which we have shown to be asymptotically valid. We show simulation results for confidence levels $\alpha \in \left\{.1,.05,.01\right\}$, with varying sample size $N$. For each sample size, we draw $1,000$ samples and, for each sample, we estimate the confidence interval by drawing $1,000$ bootstrap samples from the original sample.
\afterpage{
}
We focus on the case where consumers have quasilinear-linear utility and the unit cost is normalized to zero, as in BergemannSchlag2011JET and CarrascoLuzKosMessnerMonteiroMoreira2018JET. We show results for three different parameterizations of $F_0$ relying on the Beta distribution: Beta(1/4,1/4), Uniform(0,1) and Beta(4,4).\footnote{ The empirical coverage results were consistent across other parameterizations and using Beta mixtures or mixtures with degenerate distributions. }
\afterpage{
}
In \hyref{table:profit-a}[Table] we present evidence for the empirical coverage frequency at sample sizes of 500, 1,000 and 2,500. As is immediate upon inspection of the table, our estimators have extremely good finite sample properties, with the empirical coverage frequencies being very close to the theoretical asymptotic coverage probability, regardless of which of the three distributions is considered. We also investigated the behaviour of our estimators under small samples. As \hyref{figure:profit-a}[Figure] shows, they fare reasonably well for sample sizes between 50 and 300.
We also considered the regret incurred by adopting an empirically optimal mechanism that depends on the empirical distribution with finite samples. As illustrated in \hyref{figure:regret}[Figure], we empirically study the average regret as a share of the optimal expected profit, that is, $\left(\Pi(F_0)-\pi(\hat M^*(S^n), F_0)\right)/\Pi(F_0)$. The average is taken across 1,000 samples of varying size in increments of 10 observations. Even with just 50 observations, the empirically optimal mechanism on average attains regret that is under 4% of the optimal expected profit. For the purpose of comparison, the robust mechanism in CarrascoLuzKosMessnerMonteiroMoreira2018JET, relying on an estimate of the mean and assuming knowledge of the upper bound of the distribution, exhibits average regret no lower than 20% of the optimal expected profit under any of the three distributions we consider.\footnote{ We observe that for the minimax regret distribution derived in CarrascoLuzKosMessnerMonteiroMoreira2018JET, by construction, the empirically optimal mechanism will attain the optimal profit with probability one and regardless of the number of samples, and, therefore, also attain the minimal regret. }
Before concluding, we discuss how to apply some of the insights developed in this paper to the related setting of single-unit auctions. In particular, we show how simple empirically optimal mechanisms in this context exhibit some of the desirable robustness features shown in \hyref{section:eom}[Section].
Suppose that the firm has a single item to auction to $M\geq 2$ bidders. The firm values the item at $c>0$, and each bidder $i=1,...,M$ is risk-neutral and values the item at $\theta_i$, drawn independently from the distribution $F_0$. To make matters simple, we assume that $F_0$ is absolutely continuous with convex and compact support. In such case, it is well-known that revenue equivalence holds and that a second-price auction with a reserve price is optimal for the firm, with bidders disclosing their types. Then, the optimal reserve price when the type distribution $F$ satisfies the same assumptions solves $\displaystyle\max_{r \in \Theta}\pi(r,F)$, where $\pi(r,F)=\int_r^{\overline \theta} \mathop{}\!\mathrm{d} F_{(2;M)}$ and $F_{(2;M)}$ denotes the distribution of the second-highest willingness-to-pay, given a distribution of types $F$ and $M$ bidders. That is, $$F_{(2;M)}(\theta)=M\cdot F(\theta)^{M-1}(1-F(\theta)) + F(\theta)^{M}.$$
Consider the case where the firm has access to a sample of $n$ observations drawn from $F_0$ and the reserve price is set before bids are submitted.\footnote{ The same arguments apply when the reserve price is secret and takes into account the bids submitted, as these would just translate into a larger sample of $n+M$ observations. } Similar to before, denote an empirically optimal reserve price $\hat r^*$ as the composition of a consistent estimator, $\hat F$, of the true distribution ${F_{0}}$, based on the realized sample $S^n$, and a selection from the set of reserve prices that are optimal for $F$, $r^*$.
The next proposition provides an analogue of \hyref{proposition:asymptotic-optimality}[Propositions] and (ref) to this specific setting:
The key insight is that the expected profit is linear in distribution of the second-order statistic and that this in turn is Lipschitz continuous in the distribution of types, $\|F_{(2;M)}-G_{(2;M)}\|_\infty\leq 2M(M-1)\|F-G\|_\infty$. For $\hat r^*$ to be empirically optimal, though, we must have that $\hat F(S^n)$ is absolutely continuous and has convex and compact support. Similarly to \hyref{example:iecdf}[Example], when $\hat F$ is the linearly interpolated empirical distribution we have that $p(n,\delta)=2\exp(-2 n(\delta-1/n)^2)$, delivering regret and confidence bounds.\footnote{ ColeRoughgarden2014STOC14 provide alternative sample-complexity bounds for this problem, characterizing the asymptotic number of samples needed to achieve $(1-\epsilon)$ share of the optimal profit. }
As this application illustrates, our results on the robustness properties of empirically optimal mechanisms extend naturally to auction settings. There is, however, a natural limitation in extending our results on inference: expected profit is linear in the distribution of the second-order statistic, not in the distribution of types themselves.
This paper has studied two separate but related questions. The first is how a firm should price when uncertain about the distribution of consumers' willingness-to-pay. The second is how to conduct inference regarding the expected profit, both under any fixed pricing strategy and for the optimal profit. When the firm has access to a sample of consumers' valuations, we have shown that adopting an extremely simple approach --- estimating the distribution using the sample and then pricing optimally for the estimated distribution --- yields attractive robustness properties, in particular obtaining probabilistic lower bounds both for the expected profit and for regret. On the other hand, we provided a toolkit to conduct inference for the profit. This enables practitioners to obtain confidence intervals not only for expected profit but also, for example, for the difference in profit that two different mechanisms induce. More generally, this allows for a data-based approach to robust mechanism design, where robustness properties are inferred from available data.
One important concern that we have not discussed is how to obtain such a sample. In order to elicit types (i.e., generate a sample), the firm could for instance conduct market research and elicit such a sample by means of a mechanism that induces each type to self-select to a different pair of quantity and price.\footnote{ We are assuming consumers are myopic or that they do not gain from misrepresenting their type. Incentive compatibility regarding dynamic incentives if the firm can preclude surveyed customers from purchasing the item in the future, e.g., by supplying the good, in the case of unit demand. } Indeed, this is common practice: beyond gathering qualitative information about consumers' preferences from surveys, focus groups, or interviews, many consultancy firms also experimentally elicit consumers' types using incentive-compatible mechanisms in what is known in the industry under the umbrella term of `experimental auctions' --- even though sometimes it simply corresponds to the BDM mechanism BeckerDegrootMarschak1964BehaSc.\footnote{ See LuskShogren2007Book for a comprehensive review of their use in marketing and management. In the industry, Kantar, Ipsos, and Nielsen are examples of leading consultancy firms providing these services. } This market research can then lead to the original sample or expand an existing sample --- in which case a cost-benefit analysis on the net value of acquiring additional observations may come into play.
One interesting avenue for future research considers the dynamical choice of information combining sampling and experimentation. While, under some conditions, optimal experimentation also asymptotically attains the optimal profit AghionBoltonHarrisJullien1991REStud, the implied cost is often distinct. Naturally, the interplay between these two sources of information will dictate when and how much market research a firm does to optimise its pricing, compared to learning-by-doing.
{0pt} {\setstretch{1.15}{.0em plus .0ex} }
We first state two results that will prove useful in determining the Lipschitz continuity of $\pi(M,F)$ in $F\in \mathcal F$. Let $\mathcal P:=\left\{P={\theta_0,\ldots,\theta_{n_P}}:\, \underline \theta=\theta_0\leq \theta_1\leq \cdots \leq \theta_{n_P}=\overline \theta\right\}$ and $V(f):=\sup_{P \in \mathcal P}\sum_{i=0}^{n_P-1}|f(\theta_{i+1})-f(\theta_i)|$, where $V(f)$ denotes the total variation of a function $f:\Theta\to \mathbb R$. We have:
The following is a standard result in the mechanism design literature based on Mirrlees1971REStud and MilgromSegal2002Ecta.
For any $F \in \mathcal F$, we can thus rewrite the problem --- with some abuse of notation --- by choosing directly a function $x$ from the set $\mathcal X$, where $\displaystyle\mathcal X:=\left\{x: [\underline \theta,\overline \theta] \to X,\, x\text{ is nondecreasing and } x(\underline \theta)=0\right\},$ in order to maximize profit, given by
Consider the normed vector space $(BV(\Theta), {\|\cdot\|}_\infty)$, where $BV(\Theta) := \{g: \Theta \to \mathbb R \;|\; V(g) < \infty\}$. For any fixed $M \in \mathcal M$, consider its corresponding allocation function $x \in \mathcal X$ and extend the functional $\pi(M,\cdot)$ to $BV(\Theta)$ by defining
Clearly, $\overline \pi(M, F) = \pi(M, F)$ for all $F \in \mathcal F$. Moreover, note that for all $F, G \in BV(\Theta)$,
where $h_1(\theta):=v(\theta,x(\theta))$ and $h_2(\theta):=\int_{\underline \theta}^{\theta}v_1(s,x(s))\mathop{}\!\mathrm{d} s+c(x(\theta))$. As both $v$ and $x$ are nondecreasing, we have that, for any $x(\cdot)$,
As $v$ is supermodular and nondecreasing in $\theta$ and $c$ is increasing and convex,
Moreover, we note that $\inf_{\theta \in \Theta} h_1(\theta)=v(\underline \theta,x(\underline \theta))=0$ and $\inf_{\theta \in \Theta} h_2(\theta)=\int_{\underline \theta}^{\underline \theta}v_1(s,x(s))\mathop{}\!\mathrm{d} s+c(x(\underline \theta))= c(0)=0$. Hence, for $h_i$, with $m_i := \inf_{\theta \in \Theta} h_i(\theta)$, $i=1,2$, and letting $H(\theta)= F(\theta) - G(\theta)$,
Combining the preceding inequalities results in $\displaystyle|\bar\pi(M,F)-\bar\pi(M,G)| \leq 2(L_1 + L_2){\|F - G\|}_\infty$, $\forall F, G \in BV(\Theta), \; M \in \mathcal M$. The result is then obtained by restricting the domain to $\mathcal F$.
Let $\mathcal Y$ be a normed vector space with an open subset $\mathcal A \subseteq \mathcal Y$. As is standard, we denote the dual space of $\mathcal Y$ by $\mathcal Y^*$. Before we prove the main result, let us recall two different notions of differentiability:
Note that if $T$ is Gateaux differentiable at $F \in \mathcal Y$, then its derivative is unique. Moreover, if it is Fr\'{e}chet differentiable at $F \in \mathcal Y$, it is Gateaux differentiable and its derivatives agree.
An important generalization of Gateaux differential for the case of convex and continuous functionals is that of a subdifferential.
Since the normed linear space $(BV(\Theta),\|\cdot\|_\infty)$ is a metric space, and thus $BV(\Theta)$ is open, the following lemma guarantees that $\partial T$ is nonempty:
The next result shows why subdifferentials can be thought of as a generalization of Gateaux differentials.
In what follows, we borrow from the proof strategy of Theorem 2 in BattauzDonnoOrtu2015MathFinEcon, although their conditions do not directly apply to our problem.
First fix $M \in \mathcal M$ and notice that $\overline \pi(M,\cdot): BV(\Theta) \to \mathbb R$ is a linear functional. Therefore, it has a Fr\'{e}chet derivative. In fact, for all $F,H \in BV(\Theta)$,
This implies that the Fr\'{e}chet derivative of $\bar\pi(M,F)$ is independent of $F$ and given by $\dot \pi_M(\cdot) = \bar\pi(M,\cdot)$. Therefore, $\bar\pi(M,\cdot)$ is also Gateaux differentiable, with Gateaux derivative at $F$ given by $\bar\pi(M,\cdot)$.
Define the functional $\overline \Pi: BV(\Theta) \to \mathbb R$ by $\displaystyle\overline \Pi(H) = \sup_{M \in \mathcal M} \overline \pi(M,H)$, $\forall H \in BV(\Theta)$. Since the set $\left\{\overline \pi(M,H) : M \in \mathcal M\right\}$ is bounded for any $H \in BV(\Theta)$, it is clear that $\overline \Pi(H)<\infty$. Furthermore, it is immediate that $\overline \Pi(F) = \Pi(F)$ for all $F \in \mathcal F$.
As $\overline \pi(M,H)$ is linear in $H$ for any $M$, one immediately has that $\bar\Pi$ is convex in $H \in BV(\Theta)$, as the supremum of a family of linear functionals. Moreover, from the proof of \hyref{lemma:optimal-profit:lipschitz}[Lemma], it is easy to see that $\overline \Pi$ remains Lipschitz continuous. Therefore, by \hyref{lemma:subdifferential}[Lemma], $\partial \bar\Pi(H) \ne \emptyset$ for any $H \in BV(\Theta)$.
By \hyref{lemma:existence}[Lemma], $\mathcal M^*(F)\ne \emptyset$ for any $F \in \mathcal F$. Fix any $F \in \mathcal F$. Take any $D \in \partial \bar\Pi(F)$ and any $M_F \in \mathcal M^*(F)$. Note, for any $G \in BV(\Theta)$, that $\bar\pi(M_F,F)-\bar\pi(M_F,G)\geq \bar\Pi(F)-\bar\Pi(G)\geq D(F-G)$, hence $\partial \bar\Pi(F) \subseteq \partial \bar\pi(M_F,F)$ and, as $\bar\pi(M_F,\cdot)$ is continuous and linear, by \hyref{lemma:subdifferential-Gauteaux}[Lemma], $\partial \bar\pi(M_F,F) = \left\{\dot \pi_{M_F}\right\}$. Then, for any $G \in BV(\Theta)$,
By Fr\'{e}chet differentiability of $\bar\pi(M_F,\cdot)$, we then have that $\forall {\{G_n\}}_n$ such that $\|G_n-F\|_\infty\to 0 $,
and, consequently, $\bar\Pi$ is Fr\'{e}chet differentiable at $F \in \mathcal F$. As $F$ was arbitrary, we have that $\bar\Pi$ is Fr\'{e}chet differentiable at any $F \in \mathcal F$.
We will prove \hyref{theorem:optimal-profit:asymptotic-normality}[Theorem]. The proof for \hyref{theorem:profit:asymptotic-normality}[Theorem] is virtually the same.
By \hyref{theorem:optimal-profit:frechet}[Theorem], $\Pi(F)$ is Fr\'{e}chet differentiable at any $F \in \mathcal F$ and, thus, it can be written as $\Pi(F)=\Pi(F_0)+\dot \Pi_{F_0}(F-F_0)+o(\|F-F_0\|_\infty)$. Furthermore, we note that $\hat F$ is an unbiased estimator of $F_0$ and then, by linearity,
where $\delta_{\theta}$ denotes the cumulative distribution function associated with a Dirac delta measure at $\theta$ and $\theta_i$ is the $i$-th observation in the sample $S^n$. Thus,
where $\sigma_{F_0}^2=\mathbb E\left[{\left(\dot\Pi_{F_0}(\delta_{\theta}-F_0)\right)}^2\right]$.
Finally, following Parr1985StatProbL, we have that
where we used Fr\'{e}chet differentiability to obtain a first-order von Mises expansion of $\Pi$ in the second equality, linearity of $\dot\Pi_{F_0}$ in the third and the triangle inequality in the last. As, $\hat F(S^n_B)$ and $\hat F(S^n)$ denote empirical distributions of $\hat F(S^n)$ and $F_0$, by the \citepos{DvoretzkyKieferWolfowitz1956AnnMathStat} inequality, we have that
As $\mathbb E\left[\pi(M^*(F_0),\delta_{\theta_i^B})\mid S^n\right]=\pi(M^*(F_0),\hat F(S^n))$ and $\mathbb E\left[{\left(\pi(M,\hat F(S^n_B))\right)}^2\right]=\sigma_{F_0}^2<\infty$, by the central limit theorem in BickelFreedman1981AnnStat, we have that $\hat G_n \overset{d}{\to} G_0$. Finally, as the limiting distribution is continuous, convergence is uniform.
Let $\hat F^E$ denote the empirical distribution estimator. By \hyref{lemma:optimal-profit:lipschitz}[Lemmas] and (ref), $\Pi(\hat F(S^n))=\Pi(\hat F^E(S^n))+O_p(n^{-1})$. As such, (1) follows from the observation that $\sqrt n\left\{\Pi(\hat F(S^n)) - \Pi(F_0)\right\} \\= \sqrt n\left\{\Pi(\hat F^E(S^n))-\Pi(F_0)\right\} + O_p(n^{-1/2})$, which, together with Slutsky's theorem and \hyref{theorem:optimal-profit:asymptotic-normality}[Theorem] implies $\sqrt n\left\{\Pi(\hat F(S^n))-\Pi(F_0)\right\}\overset{d}{\to}N(0,\sigma^2_{F_0})$. (2) results from the analogous observation that:
For (3), we first prove the following lemmas:
Given that, ${\{\hat F(S^n)\}}_{n\in \mathbb N}$ is absolutely continuous with probability 1 and ${\|\hat F(S^n)-F_0\|}_\infty \overset{a.s.}{\to}0$, the previous lemmas imply that ${\|f_n-f_0\|}_1\overset{p}{\to} 0$, which concludes the proof for (3).
First, we note that $\pi(r,F)$ is Lipschitz continuous in $F$, with a Lipschitz constant that is independent of $r$. Note that
where the first inequality uses the Beesack-Darst-Pollard inequality --- see \hyref{lemma:boundsintegral}[Lemma]. By the same arguments as in \hyref{lemma:optimal-profit:lipschitz}[Lemma], we have that $\Pi(F):=\sup_{r \in \Theta}\pi(r,F)$ is also Lipschitz continuous in $F$ and, by those made in \hyref{proposition:asymptotic-optimality}[Propositions] and (ref), the result follows.
Let the linearly interpolated empirical cumulative distribution be given by
where $\theta_{(k)}$ denotes the $k$-th smallest observation in the sample $S^n$ and $\theta_{(0)}=\underline \theta$. The following holds: