# Pricing Query Complexity of Revenue Maximization

Renato Paes Leme
Google Research
<EMAIL_ADDRESS>Balasubramanian Sivan
Google Research
<EMAIL_ADDRESS>Yifeng Teng
Google Research
<EMAIL_ADDRESS>Pratik Worah
Google Research
<EMAIL_ADDRESS>
###### Abstract

The common way to optimize auction and pricing systems is to set aside a small
fraction of the traffic to run experiments. This leads to the question: how
can we learn the most with the smallest amount of data? For truthful auctions,
this is the _sample complexity_ problem. For posted price auctions, we no
longer have access to samples. Instead, the algorithm is allowed to choose a
price $p_{t}$; then for a fresh sample $v_{t}\sim\mathcal{D}$ we learn the
sign $s_{t}=\textsf{sign}(p_{t}-v_{t})\in\\{-1,+1\\}$. How many pricing
queries are needed to estimate a given parameter of the underlying
distribution?

We give tight upper and lower bounds on the number of pricing queries required
to find an approximately optimal reserve price for general, regular and MHR
distributions. Interestingly, for regular distributions, the pricing query and
sample complexities match. But for general and MHR distributions, we show a
strict separation between them.

All known results on sample complexity for revenue optimization follow from a
variant of using the optimal reserve price of the empirical distribution. In
the pricing query complexity setting, we show that learning the entire
distribution within an error of $\epsilon$ in Levy distance requires strictly
more pricing queries than to estimate the reserve. Instead, our algorithm uses
a new property we identify called _relative flatness_ to quickly zoom into the
right region of the distribution to get the optimal pricing query complexity.

##  1 Introduction

An important question in the intersection of economics and statistics is to
estimate properties of a buyer’s willingness-to-pay (a.k.a. value) from
samples. Samples typically come from buyer’s bids in a truthful auction. In
various economic setups though, collecting samples of true value is quite hard
or impossible. For example, in many settings auction is not an option; often,
posting prices is the only option. And the seller therefore has access only to
a buyer’s decision to buy or not at a given price. This is also true for
auctions with very few buyers (not too uncommon in digital auctions as
targeting becomes increasingly narrow and focused): if a buyer is the sole
competitor, they may decide to bid just above the reserve price that is sent
to them, or to not bid at all when their value is below the reserve price, in
order to conceal information about their valuation. Likewise in non-truthful
auctions, we don’t have access to true value samples; we just have access to
past bids. One thing we do have in all these scenarios is whether or not the
true value exceeded a (reserve) price. Our goal in this paper to compare the
power of _value samples_ (namely, samples from the buyer’s value distribution)
to that of _pricing queries_ (namely, a price $p$ and a response to whether or
not the buyer’s value is at least $p$).

What can we do with a single value sample? Dhangwatnotai et al. [6] say that
we can do a lot: we can price the buyer using that sample to extract _half of
the expected optimal revenue_ achievable with full knowledge of the regular
value distribution. Similarly a single value sample acts as an unbiased
estimator of the mean of the distribution. Now consider a single pricing
query. It is not possible to extract _any non-zero fraction of the optimal
revenue_ from a single pricing query. Likewise there is nothing meaningful to
estimate about the mean using a single pricing query. Both of these hold
regardless of our choice of the price $p$. The contrast between the power of a
single value sample and that of a single pricing query cannot be more stark.
The question we investigate in this paper is what happens when we have a large
number of pricing queries. How do the number of value samples required to get
a $1-\epsilon$ approximation of the optimal revenue, or to estimate the mean
within $\epsilon$ compare with the number of pricing queries required?

Let $\mathcal{C}$ be a class of distributions over $\mathbb{R}$ and
$\theta:\mathcal{C}\rightarrow\mathbb{R}$ a parameter (such as the mean, the
variance or the monopoly price). Let
$\mathcal{L}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ be a loss function
estimating the error in the parameter estimator111The loss can implicitly
depend on the distribution $\mathcal{D}\in\mathcal{C}$.. We will consider the
following parameters and respective losses:

  * •

_Median:_ $\theta(\mathcal{D})=\text{median}(\mathcal{D})$ with loss
$\mathcal{L}(\theta;\hat{\theta})=|F_{\mathcal{D}}(\theta)-F_{\mathcal{D}}(\hat{\theta})|$,
where $F_{\mathcal{D}}$ is the c.d.f.

  * •

_Mean:_ $\theta(\mathcal{D})=\mathbb{E}_{v\sim\mathcal{D}}[v]$ with loss
$\mathcal{L}(\theta;\hat{\theta})=|\theta-\hat{\theta}|$.

  * •

_Monopoly price:_
$\theta(\mathcal{D})=\text{argmax}_{p}\textsc{Rev}_{\mathcal{D}}(p):=\mathbb{E}_{v\sim\mathcal{D}}[p\cdot\mathbf{1}\\{v\geq
p\\}]$ with the loss that compares the revenue at the optimal and estimated
point:
$\mathcal{L}(\theta;\hat{\theta})=|\textsc{Rev}_{\mathcal{D}}(\theta)-\textsc{Rev}_{\mathcal{D}}(\hat{\theta})|$.

In our last example, the parameter is a function rather than a real number:

  * •

_CDF:_ $\theta(\mathcal{D})=F_{\mathcal{D}}(\cdot)$ with loss
$\mathcal{L}(F_{\mathcal{D}};\hat{F})=\textsf{LevyDistance}(F_{\mathcal{D}};\hat{F})$
which corresponds to the infimum over $\epsilon>0$ such that
$F_{\mathcal{D}}(v-\epsilon)-\epsilon\leq\hat{F}(v)\leq
F_{\mathcal{D}}(v+\epsilon)+\epsilon$ for all $v\in\mathbb{R}$.

A pricing estimator with $m$ queries consists of an algorithm that posts $m$
prices222We allow both values $v_{t}$ and prices $p_{t}$ to be negative. A
negative value means that the buyer has a disutility for the good, while a
negative price means that the buyer is compensated for acquiring the good.
Negative values are allowed for convenience to obtain cleaner algorithms. The
same results can be obtained for non-negative values by dealing with the
corner cases around zero. $p_{1},p_{2},\ldots,p_{m}\in\mathbb{R}$. For each
price $p_{t}$ posted the algorithm observes if a buyer with a freshly drawn
value buys or not at that price. In other words, we observe
$s_{t}=\textsf{sign}(v_{t}-p_{t})\in\\{-1,+1\\}$ for some
$v_{t}\sim\mathcal{D}$. The prices can be computed adaptively. Finally, the
algorithm outputs an estimate $\hat{\theta}(s_{1},\ldots,s_{m})$. An
$(\epsilon,\delta)$-pricing-query-estimator is an algorithm such that:

$\mathbb{P}_{v_{1},\ldots,v_{m}\sim\mathcal{D}}\left(\mathcal{L}(\theta(\mathcal{D});\hat{\theta}(s_{1},\ldots,s_{m}))\leq\epsilon\right)\geq
1-\delta,\quad\forall\mathcal{D}\in\mathcal{C}$

Given a class $\mathcal{C}$ and parameter $\theta$ and loss $\mathcal{L}$ we
define the _pricing query complexity_
$\textsc{PriceCplx}_{\mathcal{C},\theta}(\epsilon)$ to be the minimum $m$ such
that there exists a $(\epsilon,1/2)$-pricing-query-estimator for
$\mathcal{C}$, $\mathcal{L}$ and $\delta$.

It is useful to compare with traditional estimators and sample complexity. A
traditional $(\epsilon,\delta)$-estimator is an algorithm that processes the
samples $v_{1},\ldots,v_{m}$ directly and produces an estimator
$\hat{\theta}(v_{1},\ldots,v_{m})$ such that:

$\mathbb{P}_{v_{1},\ldots,v_{m}\sim\mathcal{D}}\left(\mathcal{L}(\theta(\mathcal{D});\hat{\theta}(v_{1},\ldots,v_{m}))\leq\epsilon\right)\geq
1-\delta,\quad\forall\mathcal{D}\in\mathcal{C}$

Similarly, we can define the sample complexity as
$\textsc{SampleCplx}_{\mathcal{C},\theta}(\epsilon)$ as the minimum $m$ such
that there exists a $(\epsilon,1/2)$-traditional-estimator for $\mathcal{C}$
and $\delta$. Since one can simulate a pricing estimator from a traditional
estimator we have:

$\textsc{PriceCplx}_{\mathcal{C},\theta}(\epsilon)\geq\textsc{SampleCplx}_{\mathcal{C},\theta}(\epsilon)$
(1)

The main question we ask is how big is this gap? I.e. how much harder is it to
estimate a parameter from pricing queries as compared to samples.

#### Practical Motivation and Relation to Bandits

In practice auctions are optimized by using a small fraction of traffic (say
1%) to run experiments and the remaining 99% runs the deployed production
auction. After a period (say a few days) we use what we learned in the
experimental slice to deploy in the main slice. Typically one does not care
about the revenue in the experimental slice, but we do care about making that
slice as small as possible. This translates directly to the goal of pricing
query complexity: how to learn the most with the fewest possible queries?

The alternative to run a small experimental slice to collect data in order to
optimize the main mechanism is to apply a bandit algorithm on the full
traffic. This may be appealing in theory, but it is not viable in practice
where upper bounds on experimental traffic is a reality. For one, bandit
algorithms would lead to a more unstable system for the bidders. Furthermore,
only learning in a small (typically random) experimental slice minimizes
incentives for bidders to strategize against the learning algorithm, since any
given query will only be used to learn a price for the next day with a very
small probability.

This practical difference also explains how our objectives and guarantees
differ from those of bandit learning for revenue optimization. While the
bandit approach focuses on optimizing average revenue while learning, the
sample/pricing complexity approach provides a guarantee on the loss of the
final estimator with high probability, but doesn’t care about the actual
revenue obtained during the learning phase. This is very much in line with the
literature on sample complexity.

#### Our Results

We give matching upper and lower bounds (up to $\text{polylog}(1/\epsilon)$
factors) for the pricing complexity of various parameters and classes of
distributions. Our results are summarized in Table 1. For each row of the
table, we assume for the pricing complexity bounds that the parameter being
estimated is in the range $[0,1]$. Since pricing queries only receive binary
feedback, we need an initial range to be able to return any meaningful
guarantee.

It is interesting to compare our bounds with the sample complexity for the
same regime. Interestingly in many important cases, such as estimating the
mean of a normal distribution or the monopoly price of a regular distribution,
pricing queries don’t pose any significant handicap when one looks at the
asymptotic regime. This is however not always the case: when computing the
monopoly price of an MHR distribution, we establish a clear demarcation: we
show a tight bound of $\widetilde{O}(1/\epsilon^{2})$ for pricing complexity
which is asymptotically higher than the known bound of
$\widetilde{O}(1/\epsilon^{3/2})$ for sample complexity by Huang et al [15].
We also show a gap for computing the monopoly price for general distributions,
while $\Omega(1/\epsilon^{3})$ is required for pricing queries,
$\widetilde{O}(1/\epsilon^{2})$ is sufficient for value samples.

Parameter | Distribution | Pricing Complexity | Sample Complexity
---|---|---|---
Median | General |  $\tilde{O}(1/\epsilon^{2})$, $\Omega(1/\epsilon^{2})$ |  $O(1/\epsilon^{2})$,$\Omega(1/\epsilon^{2})$
Mean | Normal |  ${O}(\sigma^{2}/\epsilon^{2})$, $\Omega(\sigma^{2}/\epsilon^{2})$ |  $O(\sigma^{2}/\epsilon^{2})$, $\Omega(\sigma^{2}/\epsilon^{2})$
CDF | General |  $\tilde{O}(1/\epsilon^{3})$, $\Omega(1/\epsilon^{3})$ |  $\tilde{O}(1/\epsilon^{2})$, $\Omega(1/\epsilon^{2})$
CDF | Regular |  $\tilde{O}(1/\epsilon^{3})$, $\Omega(1/\epsilon^{2.5})$ | $\tilde{O}(1/\epsilon^{2})$
Monopoly Price | MHR | $\tilde{O}(1/\epsilon^{2}),\Omega(1/\epsilon^{2})$ | $\tilde{O}(1/\epsilon^{1.5}),\Omega(1/\epsilon^{1.5})$
Monopoly Price | Regular |  $\tilde{O}(1/\epsilon^{2})$ , $\Omega(1/\epsilon^{2})$ | $\tilde{O}(1/\epsilon^{2})$
Monopoly Price | General |  $\tilde{O}(1/\epsilon^{3})$, $\Omega(1/\epsilon^{3})$ |  $\tilde{O}(1/\epsilon^{2})$, $\Omega(1/\epsilon^{2})$
Table 1: Our upper and lower bounds for various estimators and comparison with
sample complexity. In each case, the pricing complexity bounds assume that the
parameter being estimated is in $[0,1]$. $\sigma$ is the standard deviation of
the normal distribution.

#### Techniques: Mean and Median

As a warm up, we first study how to estimate the median of a distribution
using pricing queries. The algorithm is a hybrid of binary search and the UCB
algorithm. The algorithm both keeps a range $[\ell,r]$ that contains the
median (as in binary search) and builds a confidence interval (like the UCB
algorithm) to estimate the quantile of $p=(\ell+r)/2$. Whenever the confidence
bound can safely separate the quantile of $p$ from $1/2$, a binary search step
is performed. The algorithm requires very few queries to perform a binary
search step that is far from the median, but starts requiring more and more as
we approach the median.

The algorithm is agnostic to $\epsilon$ and works in the streaming model: it
keeps an estimate of the median through the execution that gets better as it
receives more pricing query opportunities. Surprisingly, its performance
matches what one could obtain from value samples.

We then use the algorithm to estimate the mean of a normal distribution.
Remarkably, we obtain the same guarantee of $O(\sigma^{2}/\epsilon^{2})$ (up
to constant factors) as the optimal algorithm that has access to sample
values. We obtain a guarantee of $\tilde{O}(\sigma^{2}/\epsilon^{2})$ without
needing to know $\sigma$ at all. To obtain a bound of
$O(\sigma^{2}/\epsilon^{2})$ the algorithm needs to know $\sigma$; or if the
algorithm knows only an upper bound $\bar{\sigma}$ on $\sigma$, we can obtain
a guarantee of $O(\bar{\sigma}^{2}/\epsilon^{2})$.

#### Techniques: Monopoly Price

For the monopoly price our techniques are significantly more involved. At the
heart of the analysis is a new property of regular distributions called
_relative flatness_ , which is of potential independent interest. It says that
if the revenue curve has roughly the same value at $4$ different equidistant
points, it can’t hide a point with very high revenue point in between those
four points. This is not just a consequence of a single-peaked curve, as such
curves can easily hide a high revenue point between four points of equal
revenue. The concavity of the revenue curve in the quantile space is well
known for regular distributions. The novelty is in finding the right property
in the _value space_ to be used.

Using this property we design an algorithm that keeps a list of subintervals
of $[0,1]$ to explore. Unlike binary search we are not able to keep a single
interval. Once the algorithm explores an interval it may discard it, but it
may also break it into multiple subintervals and add them to the list. The
relative flatness is put to use in efficiently discarding intervals that don’t
contain the monopoly price. We design a potential function to control the
number of sub-intervals to guarantee we explore a small number of them. The
argument is delicate: even the next subinterval to pick needs care; picking an
arbitrary subinterval to process does not yield the desired bound. This
algorithm obtains a bound of $\tilde{O}(1/\epsilon^{2})$ for regular
distributions.

We then turn our attention to MHR distributions. For value samples, it is
known that learning the monopoly price for MHR distribution is easier than
learning the monopoly price of regular distributions. Surprisingly, this is no
longer the case for pricing complexity. To prove this fact, we design two
distributions such that no price is an $\epsilon$-approximation simultaneously
for both distributions even though the distributions have very close c.d.f.
and quantiles. We then use an information-theoretic argument to show that the
sequence of bits obtained by the pricing queries for both distributions will
be indistinguishable with fewer than $\Omega(1/\epsilon^{2})$ queries. We do
so by bounding the KL-divergence between the distribution of bits observed by
running any algorithm on both distributions.

#### Why Not Learn the CDF of the Whole Distribution?

Known results on sample complexity for revenue maximization typically use a
variant of optimal reserve price of the empirical distribution. In the case of
pricing queries, first, there is no clear notion of what the empirical
distribution is. Second, even if one is tempted to learn the CDF of the entire
distribution within an $\epsilon$ distance in Levy metric, we show that this
is provably inferior (see Table 1 for CDF Parameter) to the tight bounds we
get. Our technique of quickly zooming into the right region of the
distribution using the notion of relative flatness is crucial for getting
tight bounds.

#### Related Work

The work that is closest to ours is the sample complexity of single buyer,
single item revenue maximization by Huang et al. [15]. Surprisingly Huang et
al. [15] show that the number of samples required to estimate the monopoly
price to obtain a $1-\epsilon$ approximation to revenue is even smaller than
the number of samples required to estimate the optimal revenue. Our detailed
comparison of pricing query complexity with the sample complexity of Huang et
al. has already been presented, and, the pricing complexity often matches the
already surprisingly small sample complexity.

The literature on sample complexity has seen a lot of activity in the past
decade. Particularly, in the single-parameter setting, starting with Elkind’s
work [7] on finite support auctions, there has been a lot of progress. Cole
and Roughgarden [4] study the sample complexity of revenue maximization in
single item settings with independent non-identical distributions, where a
“sample” is an $n$-tuple when there are $n$ bidders in the auction. They give
sample complexity as a polynomial in $n$ and $1/\epsilon$ when seeking to
obtain a $1-\epsilon$ approximation to the optimal revenue. With this
definition, in many settings the number of samples is not even a function of
$n$. When one seeks a $1/4$ approximation, based on a generalization of Bulow
and Klemperer’s result [3] by Hartline and Roughgarden [12], just a single
sample would do. Fu et al. [9] shows that the revenue guarantees can be
improved with randomization. When the distributions of the $n$ bidders are
i.i.d., Dhangwatnotai et al. [6] showed that poly($\epsilon$) samples are
enough to get a $1-\epsilon$ approximation, and so is it in the case of
unlimited supply (digital goods) setting as that can be boiled down to a
single agent setting. Devanur et al. [5] consider the single parameter setting
where the buyer distributions are not in discrete categories, but in a
continuum, represented as a signal in the hands of the auctioneer. The line of
literature for single-parameter settings culminates with the work of Guo et
al. [11] which provides tight sample complexity for buyers with regular, MHR,
or bounded values. [14] further studies a targeting sample complexity model
where for each buyer distribution, it is allowed to specify a fixed size of
quantile range to sample from. Sample complexity results in multi-parameter
settings are comparatively fewer. Morgenstern and Roughgarden [16] and Vasilis
Syrgkanis [17] study the sample complexity of learning simple auctions (item
pricing, bundle pricing etc.) in multi-parameter settings via pseudo-
dimension. Gonczarowski and Weinberg [10] obtains a polynomial sample
complexity for up to $\epsilon$-optimal multi-item auctions for additive
buyers with independent item values. Brustle et al. [2] further extends the
result to buyers with some specific types of correlated item values. Sample
complexity of revenue-optimal item pricings was explored earlier by Balcan et
al. [1]. Sample complexity of welfare-optimal item pricings was explored by
Feldman et al. [8] and Hsu et al. [13].

Finally, we also note that pricing query complexity is different from sample
complexity in PAC learning using threshold concepts i.e, the literature
following the work of [18], despite the resemblance in definitions. In PAC
learning, the same concept may be used as a test on different samples.
However, this is not the case in pricing complexity, here we never explicitly
observe any sample. This means that the techniques and bounds for PAC learning
are going to be closer to usual sample complexity results than to pricing
complexity, as is borne out from the lower bounds.

##  2 Warmup: Estimating the Median and the Mean

Before going to the technically more involved Section 3, we begin with the
estimation of the median and mean of distributions as a warmup. While the
results in Section 3 are our main results, there are some nuances in this
Section 2 as well, including the removal of log factor in Theorem 2.2.

###  2.1 Median of a General Distribution

We start with one of the most basic problems in statistics: estimating the
median of a distribution. Let $C$ be the class of all distributions with
finite variance and median in $[0,1]$. When we are estimating the median of a
distribution $\mathcal{D}$ with cdf $F$, a natural loss function is
$\mathcal{L}(\theta,\hat{\theta})=|F(\theta)-F(\hat{\theta})|$. Then we can
bound the pricing query complexity as follows:

######  Theorem 2.1.

Let $\mathcal{C}$ be a class of distributions over $\mathbb{R}$ with median in
$[0,1]$. Define:

$a_{F}:=\sup_{F\in\mathcal{C}}\log{\textstyle|F^{-1}(\frac{1}{2}+\frac{\epsilon}{3})-F^{-1}(\frac{1}{2}-\frac{\epsilon}{3})|^{-1}}.$

We have

$\textsc{PriceCplx}_{\mathcal{C},\theta}(\epsilon)\leq\tilde{O}(1/\epsilon^{2})a_{F}\log
a_{F}.$

Observe that the bound depends on a parameter $a_{F}$ which measures how
concentrated the function is around the median. For example, if there is an
$O(\epsilon)$ probability mass exactly at the median then $a_{F}=\infty$. In
such case, in order to obtain $\mathcal{L}(\theta,\hat{\theta})\leq
O(\epsilon)$ we would need to find the the median _exactly_ which is
impossible only using pricing queries. Thus the dependence on $a_{F}$.

The bound in Theorem 2.1 is achieved by a combination of binary search and the
UCB algorithm, described in Algorithm 1. The algorithm starts with a range
$[0,1]$ of the potential median, and repeatedly prices at the middle point $p$
of the range. Since the algorithm obtains only binary feedback, it needs to
keep sending pricing queries at this point until it has enough information to
decide with high probability whether $Q(p)=1-F(p)<1/2$ or $Q(p)>1/2$. To do
that we keep an estimate of the quantile $Q(p)$ based on the binary feedback
together with a confidence interval for this estimate. Once $1/2$ leaves this
confidence interval we know with high probability on which side of $p$ the
median is, and we can do a binary search step. After the binary search step,
we restart the UCB step.

Initialize $\ell=0$, $r=1$, $p=1/2$; $n=0$, $k=0$, $p^{*}=1/2$,
$\epsilon^{*}=1$;

for  _t=1,2,3… (each new arriving query)_ do

Increment number of samples $n=n+1$ ;

Price at $p$, if sold, increment $k=k+1$ ;

If $\epsilon_{p}=18\sqrt{\log(t/\delta)/n}<\epsilon^{*}$ update
$p^{*}=p,\epsilon^{*}=\epsilon_{p}$ ;

if  _$|1/2-k/n| >12\sqrt{\log(t/\delta)/n}$ (i.e. $1/2$ is outside the
confidence bound)_ then

If $k/n<1/2$, update $r=p$. Otherwise, $\ell=p$;

Update $k=n=0$ (reset the counters) and set $p=(\ell+r)/2$;

end if

Return $p^{*}$ if $\epsilon^{*}\leq\epsilon$;

end for

ALGORITHM 1 Binary search algorithm that returns $p^{*}$ with
$|Q(p^{*})-\frac{1}{2}|\leq\epsilon$ with prob $1-\delta$

One important feature of our algorithm is that it uses no information about
$\epsilon$ other than as a stopping condition. In fact, one can think of the
algorithm in the _streaming model_ : it processes a stream of ‘pricing
opportunities’ and updates a constant-size set of parameters in each step. At
each point in time, the algorithm keeps an estimate $p^{*}$ together with a
confidence bound $\epsilon^{*}$, that keeps getting better as the algorithm
receives more data. The analysis of the pricing complexity is deferred to
Section A.1.

###  2.2 Mean of a Normal Distribution

We now apply this idea to estimate the mean of a normal distribution using
pricing queries. The idea can be extended to other families of parametric
distributions, but we focus here on normals to allow a crisp comparison with
sample complexity. Our main result is the following price complexity upper
bound, which exactly matches the well known sample complexity lower bound of
$\Omega(\sigma^{2}/\epsilon^{2})$:

######  Theorem 2.2.

Let $\mathcal{C}_{\sigma}=\left\\{\mathcal{N}(\mu,\sigma)\text{ s.t.
}\mu\in[0,1]\right\\}$ be the class of normal distributions with variance
$\sigma^{2}$ with the loss
$\mathcal{L}(\theta,\hat{\theta})=|\theta-\hat{\theta}|$. Then the pricing
complexity of computing the mean is:

$\textsc{PriceCplx}_{\mathcal{C}_{\sigma},\mu}(\epsilon)=O(\sigma^{2}/\epsilon^{2}).$

###### Proof.

A direct application of Theorem 2.1 leads to an algorithm with
$\tilde{O}(\sigma^{2}/\epsilon^{2})$ pricing query complexity. To estimate a
point $\hat{\theta}$ such that $|\hat{\theta}-\mu|\leq\epsilon$ for a
distribution with mean $\mu$, it is enough to find a point $\hat{\theta}$ such
that $|F(\hat{\theta})-F(\mu)|\leq\epsilon/\sigma$. For a normal distribution
the parameter $a_{F}$ in Theorem 2.1 is $a_{F}=O(\log
1/(\epsilon\cdot\sigma))$. If $\sigma\geq\epsilon$, the statement of the
theorem directly yields a $\tilde{O}(\sigma^{2}/\epsilon^{2})$. If
$\sigma<\epsilon$ on the other hand, all the points
$p\notin[\mu-\epsilon,\mu+\epsilon]$ are such that $|Q(p)-1/2|=\Omega(1)$ and
hence the UCB step in Algorithm 1 takes a constant number of queries at each
of those points. Hence in $O(\log(1/\epsilon))$ we query a point that is
$\epsilon$-close to the mean. This algorithm is robust in the sense that it
doesn’t require us to know the variance as it is only used in the analysis.

Assume for now that we know exactly what the variance $\sigma^{2}$ is. If we
allow the algorithm to use the exact value of the variance $\sigma^{2}$, we
can improve the guarantee from $\tilde{O}(\sigma^{2}/\epsilon^{2})$ to
$O(\sigma^{2}/\epsilon^{2})$. We can apply the following procedure:

  * •

Use Algorithm 1 with $\epsilon=1/4$ to find a point $p$ with quantile
$Q_{\mu,\sigma}(p)\in[1/4,3/4]$.

  * •

Using $O(\sigma^{2}/\epsilon^{2})$ pricing queries, find an estimate $\hat{q}$
such that $|\hat{q}-Q_{\mu,\sigma}(p)|\leq\epsilon/\sigma$.

  * •

Solve the equation $\hat{q}=Q_{\hat{\mu},\sigma}(p)$ to find an estimate
$\hat{\mu}$ for the mean.

Note that since $Q_{\hat{\mu},\sigma}(p)=Q_{0,1}(\frac{p-\mu}{\sigma})$ where
$Q_{0,1}$ is the quantile function for the standard Gaussian, the solution to
the equation in last step is:

$\hat{\mu}=p-\sigma\cdot Q_{0,1}^{-1}(\hat{q})$

Since the derivatives of $Q_{0,1}^{-1}$ are bounded in $[1/4,3/4]$ an error of
$\epsilon/\sigma$ in the estimation $\hat{q}$ leads to an error of
$O(\epsilon/\sigma)$ in $Q_{0,1}^{-1}(\hat{q})$. Hence $|\mu-\hat{\mu}|\leq
O(\epsilon)$.
∎

We can relax the assumption that we know $\sigma$ exactly and assume we only
know an upper bound $\bar{\sigma}$. The proof is deferred to Section A.2.

######  Corollary 2.3.

Let $\bar{\mathcal{C}}_{\bar{\sigma}}=\left\\{\mathcal{N}(\mu,\sigma)\text{
s.t. }\mu\in[0,1],\ \sigma\leq\bar{\sigma}\right\\}$ be the class of normal
distributions with variance at most $\bar{\sigma}^{2}$ with the loss
$\mathcal{L}(\theta,\hat{\theta})=|\theta-\hat{\theta}|$. Then the pricing
complexity of computing the mean is:

$\textsc{PriceCplx}_{\bar{\mathcal{C}}_{\bar{\sigma}},\mu}(\epsilon)=O(\bar{\sigma}^{2}/\epsilon^{2}).$

##  3 Estimating the Monopoly Price

In this section, we focus on estimating the monopoly price (i.e., the revenue
optimal price or the Myerson price) and measure our loss via the natural
metric of the revenue gap between the true revenue and that obtained by our
estimated price:
$\mathcal{L}(\theta;\hat{\theta})=|\textsc{Rev}_{\mathcal{D}}(\theta)-\textsc{Rev}_{\mathcal{D}}(\hat{\theta})|,\text{
where
}\textsc{Rev}_{\mathcal{D}}(p):=\mathbb{E}_{v\sim\mathcal{D}}[p\cdot\mathbf{1}\\{v\geq
p\\}]$, where $\theta$ and $\hat{\theta}$ are the true and estimated monopoly
prices.

An important tool in this section is the following lemma, which shows that to
estimate the quantile $Q(p)=1-F(p)$ of price $p$ with additive error
$\epsilon$, it suffices to use $\tilde{O}(\frac{1}{\epsilon^{2}})$ pricing
queries on $p$. The proof is relatively standard, and is deferred to Section
B.

######  Lemma 3.1.

For any value distribution $F$ supported in $[0,1]$ and value $p$, there is an
algorithm $\textsf{EQ}_{F}(p,\epsilon,\delta)$ that makes
$m=\tilde{O}(\frac{1}{\epsilon^{2}}\log\frac{1}{\delta})$ pricing queries and
with probability $>1-\delta$ returns an estimate $\hat{q}$ for the quantile
$Q(p)=1-F(p)$ such that $|\hat{q}-Q(p)|<\epsilon$.

###  3.1 Regular Distributions

Firstly we study the class of regular distributions
$\mathcal{C}_{\textsc{REG}}$, supported on $[0,1]$. Regular distributions are
the class of distributions for which the revenue curve in quantile space
$\hat{R}(q)=q\cdot F^{-1}(1-q)$ is concave. This in particular implies that
the revenue curve in the space of values/prices $\textsc{Rev}(p)=p(1-F(p))$ is
single-peaked. This class includes many important distributions such as
uniform, exponential and all log-concave distributions.

In the heart of our algorithm will be the following lemma on regular
distributions:

######  Lemma 3.2 (Relative Flatness of Regular Distributions).

Let Rev be the revenue curve of a regular distribution. Consider four
equidistant333In the sense that $p_{i}=(p_{4}i+p_{1}(3-i))/3$ for $i=2,3$.
values $p_{1}<p_{2}<p_{3}<p_{4}=cp_{1}$ in $[0,1]$ and let
$\textsc{Rev}_{\max}$ and $\textsc{Rev}_{\min}$ be the maximum and minimum
value of the revenue curve at those four points. Then if
$\textsc{Rev}_{\min}\geq\textsc{Rev}_{\max}-\epsilon$, for some $\epsilon>0$,
then for any $p\in[p_{1},p_{4}]$,
$\textsc{Rev}(p)\leq\textsc{Rev}_{\max}+O(c\epsilon)$.

The geometric intuition is that is the curve is reasonably flat at four
equidistant points, then it should be reasonably flat within most of that
interval. Note that this is not generally true for any single-peaked function,
as the peak could be easily hiding between any of those points. See Figure 1.
The proof (deferred to Section B.1) will strongly use the fact that the
revenue curve is concave when looked at in the quantile space. From this point
on, the only two facts we will use about regular distributions is the fact it
is single-peaked and the relative flatness lemma.

Figure 1: The relative flatness lemma shows that the revenue curve of a
regular distribution can’t hide a very high revenue point in a region that
appears flat when measured with respect to $4$ equidistant points. For
example, the curve in the figure can’t be the revenue curve of a regular
distribution in the value space.

With that we can prove our main result:

######  Theorem 3.3.

Let $\mathcal{C}_{\textsc{REG}}$ be the class of regular distributions
supported in $[0,1]$ and let $\theta$ be the monopoly price. Then,

$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{REG}},\theta}(\epsilon)=\tilde{O}(1/\epsilon^{2}).$

In the next section we will show this is tight even for the subclass of MHR
distributions.

Now we describe the algorithm achieving that bound. The main data structure
the algorithm will keep is a list $L$ which will contain intervals with
disjoint interiors in the revenue curve that still need to be explored. For
each of the endpoints of those intervals, we will keep an
$\pm\epsilon$-estimate $\hat{q}(p)$ of its quantile $Q(p)=1-F(p)$ obtained by
the algorithm in Lemma 3.1 with success probability $\delta=\epsilon^{2}$
together with a revenue estimate:

$\widetilde{\textsc{Rev}}(p)=p\cdot\hat{q}(p).$

In the algorithm, we will show that we only price at $\tilde{O}(1)$ different
prices, thus by union bound the overall success probability is at least
$\frac{2}{3}$ for small $\epsilon$.

We initialize the algorithm with $L=\\{[0,1]\\}$. While the list is non-empty,
we will process it by removing an interval from it and analyzing it. In the
process of analyzing it, we will query some of its points. Depending on the
the outcome of those queries, we may decide to add subintervals of $L$ back to
the list for further analysis. We stop whenever the list is empty. At that
point, we return the point queried in the process with largest estimated
revenue.

We now describe how to process each interval. At every round, we remove the
second leftmost interval $[\ell,r]$ from the list whenever the list has more
than one interval. If not, we remove the only interval from the list. We
process this interval by dividing it in $4$ pieces of the same length and
querying the breakpoints $p_{i}=(i\ell+(4-i)r)/4$ for $i=1,2,3$ for the
approximate quantile and construct a revenue estimate
$\widetilde{\textsc{Rev}}$ for each. We define the following quantities for
the interval:

$\textsc{Rev}_{\max}=\max_{p\in\\{\ell,p_{1},p_{2},p_{3},r\\}}\textsc{Rev}(p),\qquad\widetilde{\textsc{Rev}}_{\max}=\max_{p\in\\{\ell,p_{1},p_{2},p_{3},r\\}}\widetilde{\textsc{Rev}}(p)$

Now we proceed according to one of seven cases:

_Case 1:_ If $r-\ell<\epsilon$ we discard the interval.

In that case, we don’t need to further analyze the interval since no point
$p\in[\ell,r]$ can generate much better revenue than just pricing at $\ell$
since:

$\textsc{Rev}(\ell)=\ell Q(\ell)\geq\ell Q(p)\geq(p-\epsilon)Q(p)\geq
pQ(p)-\epsilon=\textsc{Rev}(p)-\epsilon.$

_Case 2:_ If
$\min_{p\in\\{\ell,p_{1},p_{2},p_{3},r\\}}\widetilde{\textsc{Rev}}(p)\geq\widetilde{\textsc{Rev}}_{\max}-2\epsilon$.
In that case, we add $[\ell,p_{1}]$ to the list. At this point, since $r\leq
4p_{1}$, the relative flatness lemma guarantees us that no point in
$[p_{1},\ell]$ can be much better than the points that were already queried.

_Case 3:_ If
$\min_{p\in\\{p_{1},p_{2},p_{3},r\\}}\widetilde{\textsc{Rev}}(p)\geq\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
but $\widetilde{\textsc{Rev}}(\ell)<\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
we remove all intervals to the left of $\ell$ from the list and add
$[\ell,p_{1}]$ and $[p_{1},r]$.

In this case, we know that:

$\textsc{Rev}(\ell)\leq\widetilde{\textsc{Rev}}(\ell)+\epsilon<\widetilde{\textsc{Rev}}_{\max}-\epsilon\leq\textsc{Rev}_{\max}$

and hence the revenue in $\ell$ is suboptimal and the optimal point $p^{*}$ is
to the right of $\ell$. Here we are only using the fact that the revenue
function is single-peaked.

All the remaining cases follow from similar arguments based on the single-
peakedness of the revenue function:

_Case 4:_ If
$\min_{p\in\\{\ell,p_{1},p_{2},p_{3}\\}}\widetilde{\textsc{Rev}}(p)\geq\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
but $\widetilde{\textsc{Rev}}(r)<\widetilde{\textsc{Rev}}_{\max}-2\epsilon$ we
remove all intervals to the right of $r$ from the list and add $[\ell,p_{3}]$
and $[p_{3},r]$.

_Case 5:_ If
$\min_{p\in\\{p_{1},p_{2},p_{3}\\}}\widetilde{\textsc{Rev}}(p)\geq\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
but
$\widetilde{\textsc{Rev}}(\ell),\widetilde{\textsc{Rev}}(r)<\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
then remove all intervals from the list and add back $[\ell,p_{1}]$,
$[p_{1},p_{3}]$ and $[p_{3},r]$.

_Case 6:_ If
$\widetilde{\textsc{Rev}}(\ell),\widetilde{\textsc{Rev}}(p_{1})<\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
we remove all intervals to the left of $\ell$ from the list and add
$[p_{1},r]$ to the list.

_Case 7:_ If
$\widetilde{\textsc{Rev}}(r),\widetilde{\textsc{Rev}}(p_{3})<\widetilde{\textsc{Rev}}_{\max}-2\epsilon$
we remove all intervals to the right of $r$ from the list and add
$[\ell,p_{3}]$ to the list.

Observe that by single-peakedness those are the only possible cases. The
algorithm always finishes since it replaces intervals by other intervals that
are smaller by at least a constant factor and once intervals become of size
$\epsilon$, they are discarded. What remains to be done is to analyze the
query complexity of the algorithm:

###### Proof of Theorem 3.3.

Now we argue the algorithm described performs at most
$\tilde{O}(1/\epsilon^{2})$ queries. To see that, we first claim that there
are at most three intervals in the candidate list at any given time. We prove
this claim by induction over the number of iterations. Suppose that after the
$t$-th iteration there are $k\leq 3$ intervals in $list$. We argue that after
the $(t+1)$-th iteration, there are still at most $3$ intervals in the list.
Observe that in Case 1, 2, 6, 7, the number of intervals does not increase. In
Case 5, the number of intervals become 3 no matter how many intervals were in
the list. In Case 3 or 4, the number of intervals increase by at most 1, so
the number of intervals in the list becomes at most $3$ if $k\leq 2$. The only
remaining case is that the algorithm runs through Case 3 or 4, with $list$
containing $k=3$ intervals at the beginning of the iteration. Since the
algorithm picks the second leftmost interval from $list$, the algorithm picks
the middle one of the intervals (sorted according to the left boundary).
Notice that in Case 3, the leftmost interval is also removed in this
iteration; in Case 4, the rightmost interval is also removed in this
iteration. Thus after the algorithm runs through Case 3 and Case 4, no matter
how many intervals are in the list at the beginning of the iteration, at most
3 intervals remain in the list after the iteration. This finishes the proof of
the claim.

After each iteration, either one of the interval of length $d$ splits to
multiple intervals of length at most $\frac{3}{4}d$ each, with some other
intervals getting removed; or one of the interval of length $d$ shrinks to a
new interval of length at most $\frac{3}{4}d$ (recall that our five prices
$\ell,p_{1},p_{2},p_{3},r$ chosen in the algorithm are equidistant). Therefore
if we record the lengths of the three intervals to be $d_{1}\geq d_{2}\geq
d_{3}$, then either $d_{1}$ decreases to a fraction of at most
$\frac{\sqrt{3}}{2}$; or $d_{1}$ does not increase, and $d_{2}$ decreases to a
fraction of at most $\frac{\sqrt{3}}{2}$; or $d_{1},d_{2}$ do not increase,
and $d_{3}$ decreases to a fraction of at most $\frac{3}{4}$. For $i=1,2,3$,
let $a_{i}=0$ if $d_{i}=0$, and
$a_{i}=\lceil\log_{2/\sqrt{3}}\frac{d_{i}}{\epsilon}\rceil$ if $d_{i}>0$. Then
at each step, either $a_{1}$ decreases by at least 1; or $a_{2}$ decreases by
at least 1 while $a_{1}$ does not increase; or $a_{3}$ decreases by at least
1. Let $n=1+\lceil\log_{2/\sqrt{3}}\frac{1}{\epsilon}\rceil$, and denote a
potential function $\phi(d_{1},d_{2},d_{3})=n^{2}a_{1}+na_{2}+a_{3}$. Then at
each step, since $a_{i}\leq n-1$, $\phi$ decreases by at least 1. As at the
beginning of the algorithm $\phi(d_{1},d_{2},d_{3})=\phi(1,1,1)\leq n^{3}$, we
have the total number of iterations is at most
$n^{3}=O(\log^{3}\frac{1}{\epsilon})=\tilde{O}(1)$. Since in each iteration
the query complexity is $\tilde{O}(\frac{1}{\epsilon^{2}})$, the total query
complexity of the algorithm is $\tilde{O}(\frac{1}{\epsilon^{2}})$. ∎

###  3.2 MHR Distributions

We complement the above result by providing a lower bound on the pricing
complexity for estimating the monopoly price for MHR distributions.

######  Theorem 3.4.

Let $\mathcal{C}_{\textsc{MHR}}$ be the class of Monotone Hazard Rate
distributions supported in $[0,1]$ and let $\theta$ be the monopoly price.
Then

$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{MHR}},\theta}(\epsilon)=\Omega(1/\epsilon^{2}).$

To prove lower bound results for the pricing complexity for estimating the
monopoly price, a key observation is that for two distributions with almost
identical cumulative density functions, it’s very hard to distinguish them
with pricing queries.

######  Lemma 3.5.

For two value distributions $D$ and $D^{\prime}$, if
$\frac{1}{1+\epsilon}\leq\frac{Q_{D}(v)}{Q_{D^{\prime}}(v)},\frac{F_{D}(v)}{F_{D^{\prime}}(v)}\leq(1+\epsilon)$
for every $v\in[0,1]$, then $\Omega(\frac{1}{\epsilon^{2}})$ pricing queries
are needed to distinguish the two distributions with probability $>1-\delta$.

The proof of the lemma is technically involved, and is deferred to Section
B.2. We first show that the two distributions have small KL-divergence, then
use Pinsker’s inequality from information theory to bound the pricing
complexity. A similar approach was also used in the literature [15].

Thus to prove the lower bound on the pricing complexity of estimating the
monopoly price for MHR distributions, we only need to find two MHR
distributions with close cumulative density functions satisfying the above
lemma. Such distributions indeed exist, and we defer the construction to
Section B.2.

###  3.3 General Distributions

We now provide the pricing complexity for the class of general distributions.

######  Theorem 3.6.

Let $\mathcal{C}_{\textsc{ALL}}$ be the class of all value distributions on
$[0,1]$ and $\theta$ be the monopoly. Then

$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{ALL}},\theta}(\epsilon)=\tilde{\Theta}(1/\epsilon^{3}).$

The proof idea is as follows. On one hand, we can price at all multiples of
$\epsilon$ to get an estimated revenue for each price. We can use
$\tilde{O}(\epsilon^{-2})$ pricing queries to get an $\epsilon$ accuracy at
each price, thus $\tilde{O}(\epsilon^{-3})$ queries can guarantee us a price
that estimates the optimal revenue with error $O(\epsilon)$. On the other
hand, for a distribution with the same revenue on all but one multiples of
$\epsilon$, suppose that pricing at $i\epsilon$ gives a higher revenue than
any $j\epsilon$ with $j\neq i$. Any pricing algorithm needs to price at every
multiple of $\epsilon$ to determine the exact value of $i$, while
$\Omega(\epsilon^{-2})$ queries are needed for accuracy. Thus
$\Omega(\epsilon^{-3})$ queries are necessary for the general class of
distributions. The detailed proof is deferred to Section B.3.

###  3.4 Discussion on Learning the Entire Regular Distribution

The algorithms with optimal sample complexity designed by Huang, Mansour and
Roughgarden [15] work by using the samples to build an empirical distribution
and then choosing the optimal reserve price with respect to the empirical
distribution. We know by the DKW inequality that after
$\tilde{O}(1/\epsilon^{2})$ samples, the empirical distribution will be
$\epsilon$-close to the real distribution in Kolmogorov distance with high
enough probability. Hence for a bounded distribution, there is no asymptotic
gap between the sample complexity of learning the monopoly price and learning
the entire CDF. Is there a similar phenomenon for pricing queries?

In Section 3.1, we discussed how to directly learn the optimal monopoly prices
with $\epsilon$ error for regular distributions using
$\tilde{O}(1/\epsilon^{2})$ pricing queries. Using these many pricing queries,
we may wonder if we can get a full picture of the distribution: is it possible
to learn a distribution within a small distance to the true distribution?
There are multiple metrics measuring the distance of two distributions.
Metrics that are measured by the pointwise difference in cumulative density
functions like Kolmogorov distance444Two distributions with cumulative density
functions $F$ and $G$ are within $\epsilon$ Kolmogorov distance, if
$F(x)-\epsilon\leq G(x)\leq F(x)+\epsilon$ for every $x\in\mathbb{R}$. are
inappropriate when we only have pricing access to the distribution. For
example, if a distribution is defined by a deterministic value in $[0,1]$,
pricing queries cannot determine that specific value. Instead, we measure the
distance of two distributions by Levy distance555Two distributions with
cumulative density functions $F$ and $G$ are within $\epsilon$ Levy distance,
if $F(x-\epsilon)-\epsilon\leq G(x)\leq F(x+\epsilon)+\epsilon$ for every
$x\in\mathbb{R}$..

Observe that if two distributions $F$ and $G$ are within $\epsilon$ Levy
distance, then for any price $p\in[0,1]$,
$\textsc{Rev}_{F}(p-\epsilon)\geq\textsc{Rev}_{G}(p)-O(\epsilon)$. This means
that if $p_{F}$ is the optimal monopoly price for $F$, then $p_{F}-\epsilon$
is a good price for $G$ that achieves near-optimal revenue (with $O(\epsilon)$
revenue loss). Thus, learning a distribution within a small Levy distance is a
harder problem than learning the optimal monopoly price. For a general
distribution in $[0,1]$, the pricing query complexity for learning an
approximate distribution is $\tilde{\Theta}(\epsilon^{-3})$, which is the same
as the complexity for learning the optimal monopoly price, as we can estimate
the quantile of each multiple of $\epsilon$ using $\tilde{O}(\epsilon^{-2})$
pricing queries.

What about regular distributions? Can we also find a regular distribution
within $O(\epsilon)$ Levy distance using only $\tilde{O}(1/\epsilon^{2})$
pricing queries? We answer the question negatively by showing that
$\Omega(1/\epsilon^{2.5})$ pricing queries are required. This in particular
shows that our zooming procedure based on the relative flatness lemma is
necessary to obtain optimal pricing query complexity bounds. This also
provides another scenario (other than learning the monopoly price for an MHR
distribution) where there is an asymptotic gap between the pricing query
complexity and the sample complexity (which is $O(1/\epsilon^{2})$ by DKW
inequality).

######  Theorem 3.7.

Let $\mathcal{C}_{\textsc{REG}}$ be the class of regular distributions
supported in $[0,1]$ and let $\theta$ be the true distribution666The distance
metric $|\theta-\theta^{\prime}|$ of two distributions $\theta$ and
$\theta^{\prime}$ is measured by Levy distance.. Then

$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{REG}},\theta}(\epsilon)=\Omega(1/\epsilon^{2.5}).$

###### Proof.

Let $D^{*}$ be the uniform distribution on $[0,1]$. In other words, the
density function $f$ of $D^{*}$ satisfies $f(v)=1$ for every $v\in[0,1]$. For
any $x\in[0.1,0.9]$, let $D_{x}$ be the distribution with the following
density function $f_{x}$:

$f_{x}(v)=\left\\{\begin{array}[]{lr}1,&\text{if
}v\in[0,x)\cup(x+4\sqrt{\epsilon},1];\\\ v-x+1,&\text{if
}v\in[x,x+\sqrt{\epsilon}];\\\ -v+x+1+2\sqrt{\epsilon},&\text{if
}v\in(x+\sqrt{\epsilon},x+3\sqrt{\epsilon});\\\
v-x-4\sqrt{\epsilon}+1,&\text{if
}v\in[x+3\sqrt{\epsilon},x+4\sqrt{\epsilon}].\\\ \end{array}\right.$

Intuitively, $D_{x}$ is obtained by perturbing the uniform distribution
$D^{*}$ in a small interval $[x,x+4\sqrt{\epsilon}]$. In that interval,
$f_{x}(v)$ linearly increases from $1$ to $1+\sqrt{\epsilon}$, then decreases
gradually to $1-\sqrt{\epsilon}$, finally back to $1$.

Observe that distribution $D_{x}$ is regular since Myerson’s virtual value
$\phi_{x}(v)=v-\frac{1-F_{x}(v)}{f_{x}(v)}$ is increasing even when $f_{x}(v)$
decreases. Note: the derivative of $\phi_{x}$ is
$\phi_{x}’(v)=2+\frac{(1-F_{x}(v))f_{x}’(v)}{f_{x}^{2}(v)}$. The density of
$D_{x}$ satisfies $1-\sqrt{\epsilon}\leq f_{x}(v)\leq 1+\sqrt{\epsilon}$ and
$-1\leq f_{x}’(v)\leq 1$, thus $\phi_{x}’(v)>0$ when $\epsilon$ is small
enough, which means $\phi_{x}(v)$ is monotone increasing. Now we analyze the
number of pricing queries needed for distinguishing $D^{*}$ and $D_{x}$.

The cumulative density function of $D_{x}$ is

$F_{x}(v)=\left\\{\begin{array}[]{lr}v,&\text{if
}v\in[0,x)\cup(x+4\sqrt{\epsilon},1];\\\ v+\frac{(v-x)^{2}}{2},&\text{if
}v\in[x,x+\sqrt{\epsilon}];\\\
v+\epsilon-\frac{(x+2\sqrt{\epsilon}-v)^{2}}{2},&\text{if
}v\in(x+\sqrt{\epsilon},x+2\sqrt{\epsilon});\\\
v+\epsilon-\frac{(v-x-2\sqrt{\epsilon})^{2}}{2},&\text{if
}v\in[x+2\sqrt{\epsilon},x+3\sqrt{\epsilon});\\\
F(v)=v+\frac{(x+4\sqrt{\epsilon}-v)^{2}}{2},&\text{if
}v\in[x+3\sqrt{\epsilon},x+4\sqrt{\epsilon}].\\\ \end{array}\right.$

Observe that for any $v\in[x,x+4\sqrt{\epsilon}]$, $v\leq F_{x}(v)\leq
v+\epsilon$; for any $v\in[0,x)\cup(x+4\sqrt{\epsilon},1]$, $F_{x}(v)=v$. This
means that the cdf $F_{x}$ of distribution $D_{x}$ differs from the cdf
$F^{*}$ of uniform distribution $D^{*}$ by at most an additive $\epsilon$ in
value range $[x,x+4\sqrt{\epsilon}]$; for $v$ being out of the range,
$F_{x}(v)=F^{*}(v)=v$. Thus for $x\in[0.1,0.9]$,
$\frac{F_{x}(v)}{F^{*}(v)}=1+O(\epsilon)$ for every $v\in[0,1]$. For quantile
functions $Q_{x}(v)=1-F_{x}(v)$ and $Q^{*}(v)=1-F^{*}(v)$, similar results
hold: $\frac{Q_{x}(v)}{Q^{*}(v)}=1-O(\epsilon)$ for every $v\in[0,1]$. Thus
$\Omega(\epsilon^{-2})$ pricing queries are necessary due to Lemma 3.5.
Furthermore, the queries must be in $[x,x+4\sqrt{\epsilon}]$, as $Q_{D_{x}}$
and $Q_{D^{*}}$ are identical outside of $[x,x+4\sqrt{\epsilon}]$, which means
querying outside of $[x,x+4\sqrt{\epsilon}]$ gives no information.

For any $x\in[0.1,0.9]$, to distinguish $D_{x}$ and $D^{*}$,
$\Omega(\epsilon^{-2})$ pricing queries in $[x,x+4\sqrt{\epsilon}]$ are
necessary due to Lemma 3.5. Now consider the following
$\Omega(\epsilon^{-0.5})$ distributions: $D^{*}$, $D_{0.1}$,
$D_{0.1+4\sqrt{\epsilon}}$, $D_{0.1+8\sqrt{\epsilon}}$, $\cdots$,
$D_{0.9-8\sqrt{\epsilon}}$, $D_{0.9-4\sqrt{\epsilon}}$. To distinguish all
these distributions, $\Omega(\epsilon^{-2})$ queries are necessary in every
interval $[x,x+4\sqrt{\epsilon}]$, thus $\Omega(\epsilon^{-2.5})$ queries in
total are necessary. Notice that any two distributions $D_{x}$ and $D^{*}$ are
at least $\frac{\epsilon}{2}$-far apart in Levy distance because,
$F_{x}(x+2\sqrt{\epsilon})=x+2\sqrt{\epsilon}+\epsilon=F^{*}(x+2\sqrt{\epsilon}+\epsilon/2)+\epsilon/2$.
To learn a distribution that is within $\frac{\epsilon}{4}$ Levy distance from
the true distribution, we need to be able to distinguish all those
distributions. To summarize, even in the class of regular distributions,
$\Omega(\epsilon^{-2.5})$ pricing queries are necessary for learning a
distribution within $\frac{\epsilon}{4}$ Levy distance (thus also $\epsilon$
Levy distance).

∎

## References

  * Balcan et al. [2008] Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, and Yishay Mansour.  Reducing mechanism design to algorithm design via machine learning.  _J. Comput. Syst. Sci._ , 74(8):1245–1270, 2008\.
  * Brustle et al. [2020] Johannes Brustle, Yang Cai, and Constantinos Daskalakis.  Multi-item mechanisms without item-independence: Learnability via robustness.  In _Proceedings of the 21st ACM Conference on Economics and Computation_ , pages 715–761, 2020.
  * Bulow and Klemperer [1996] Jeremy Bulow and Paul Klemperer.  Auctions versus negotiations.  _The American Economic Review_ , 86(1):180–194, 1996.
  * Cole and Roughgarden [2014] Richard Cole and Tim Roughgarden.  The sample complexity of revenue maximization.  In David B. Shmoys, editor, _Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014_ , pages 243–252. ACM, 2014.
  * Devanur et al. [2016] Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas.  The sample complexity of auctions with side information.  In Daniel Wichs and Yishay Mansour, editors, _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , pages 426–439. ACM, 2016.
  * Dhangwatnotai et al. [2015] Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan.  Revenue maximization with a single sample.  _Games Econ. Behav._ , 91:318–333, 2015.
  * Elkind [2007] Edith Elkind.  Designing and learning optimal finite support auctions.  In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007_ , pages 736–745. SIAM, 2007.
  * Feldman et al. [2015] Michal Feldman, Nick Gravin, and Brendan Lucier.  Combinatorial auctions via posted prices.  In Piotr Indyk, editor, _Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015_ , pages 123–135. SIAM, 2015.
  * Fu et al. [2015] Hu Fu, Nicole Immorlica, Brendan Lucier, and Philipp Strack.  Randomization beats second price as a prior-independent auction.  In _Proceedings of the Sixteenth ACM Conference on Economics and Computation_ , pages 323–323, 2015.
  * Gonczarowski and Weinberg [2018] Yannai A Gonczarowski and S Matthew Weinberg.  The sample complexity of up-to-$\varepsilon$ multi-dimensional revenue maximization.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 416–426. IEEE, 2018.
  * Guo et al. [2019] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang.  Settling the sample complexity of single-parameter revenue maximization.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 662–673, 2019.
  * Hartline and Roughgarden [2009] Jason D. Hartline and Tim Roughgarden.  Simple versus optimal mechanisms.  In John Chuang, Lance Fortnow, and Pearl Pu, editors, _Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6–10, 2009_ , pages 225–234. ACM, 2009.
  * Hsu et al. [2016] Justin Hsu, Jamie Morgenstern, Ryan M. Rogers, Aaron Roth, and Rakesh Vohra.  Do prices coordinate markets?  In Daniel Wichs and Yishay Mansour, editors, _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , pages 440–453. ACM, 2016.
  * Hu et al. [2021] Yihang Hu, Zhiyi Huang, Yiheng Shen, and Xiangning Wang.  Targeting makes sample efficiency in auction design.  _arXiv preprint arXiv:2105.05123_ , 2021.
  * Huang et al. [2018] Zhiyi Huang, Yishay Mansour, and Tim Roughgarden.  Making the most of your samples.  _SIAM J. Comput._ , 47(3):651–674, 2018.
  * Morgenstern and Roughgarden [2016] Jamie Morgenstern and Tim Roughgarden.  Learning simple auctions.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, _Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016_ , volume 49 of _JMLR Workshop and Conference Proceedings_ , pages 1298–1318. JMLR.org, 2016.
  * Syrgkanis [2017] Vasilis Syrgkanis.  A sample complexity measure with applications to learning optimal auctions.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 5358–5365, 2017.
  * Valiant [1984] Leslie Valiant.  A theory of the learnable.  _ACM STOC_ , pages 436–445, 1984.

##  Appendix A Missing Proofs from Section 2

###  A.1 Missing proofs from Section 2.1

######  Theorem 2.1.

Let $\mathcal{C}$ be a class of distributions over $\mathbb{R}$ with median in
$[0,1]$. Define:

$a_{F}:=\sup_{F\in\mathcal{C}}\log{\textstyle|F^{-1}(\frac{1}{2}+\frac{\epsilon}{3})-F^{-1}(\frac{1}{2}-\frac{\epsilon}{3})|^{-1}}.$

We have

$\textsc{PriceCplx}_{\mathcal{C},\theta}(\epsilon)\leq\tilde{O}(1/\epsilon^{2})a_{F}\log
a_{F}.$

###### Proof of Theorem 2.1.

Algorithm 1 searches for a price $p^{*}$ with
$F(p^{*})\in[\frac{1}{2}-\epsilon,\frac{1}{2}+\epsilon]$. The algorithm starts
with a range $[0,1]$ of the potential median, and repeatedly price at the
middle point $p=\frac{1}{2}$ of the range. After $n$ queries, if the current
acceptance rate of the price $p$ is $\bar{q}$, then the true quantile
$q=Q(p)=1-F(p)$ is bounded in a confidence interval
$[\bar{q}-\tilde{O}(n^{-1/2}),\bar{q}+\tilde{O}(n^{-1/2})]$ with high
probability by Chernoff bound. If $\frac{1}{2}$ is outside the confidence
interval after $n$ steps, assume that
$\frac{1}{2}>\bar{q}+\tilde{O}(n^{-1/2})$, then with high probability
$q=Q(p)<\frac{1}{2}$, and $|\frac{1}{2}-q|=\Omega(n^{-1/2})$. The algorithm
proceeds with a new range $[\frac{1}{2},1]$, and repeat the binary search
process until it finds a price $p$ with $\Omega(n^{-1/2})<\epsilon$.

Consider any iteration with price $p$ and corresponding quantile
$q=Q(p):=1-F(p)$. Assume that $q<\frac{1}{2}$, the case where $q>\frac{1}{2}$
is similar. Let $\alpha=6\sqrt{\log(t/\delta)/n}$. By Chernoff bound, after
$n$ pricing queries on $p$, the probability that the selling rate
$\bar{q}=\frac{k}{n}\not\in[q-\alpha,q+\alpha]$ is

$\displaystyle\Pr[\bar{q}\not\in[q-\alpha,q+\alpha]]\leq
2\exp\left(-\frac{1}{2}n\alpha^{2}\right)=\frac{2\delta^{3}}{t^{3}}<\frac{\delta}{2t^{3}}$

when $\delta\leq\frac{1}{2}$. Thus by union bound, the probability that at any
time the true quantile $q\in[\bar{q}-\alpha,\bar{q}+\alpha]$ is
$>1-\sum_{t}\frac{\delta}{t^{2}}>1-\delta$. Thus with probability $1-\delta$,
the algorithm never falsely searches a range $[\ell,r]$ that does not contain
$p^{*}$.

When $\bar{q}$ is not out of the confidence interval, we have
$|\frac{1}{2}-\bar{q}|\leq 2\alpha$, while $|\bar{q}-q|\leq\alpha$ with
probability $1-\delta$. Thus with probability $1-\delta$,
$\epsilon_{p}=3\alpha\geq|\frac{1}{2}-q|$. Therefore $\epsilon_{p}$ is indeed
an upper bound of $|\frac{1}{2}-q|$.

Now we analyze the pricing complexity of the algorithm. When the algorithm
prices at $p$ with $q=Q(p)$ such that
$|q-\frac{1}{2}|\leq\frac{1}{3}\epsilon$, we show that the algorithm always
returns with this price. Consider the following two cases. If the algorithm
observes $|\frac{1}{2}-\bar{q}|>2\alpha$, then since with probability
$1-\delta$ $|\bar{q}-q|\leq\alpha$, we have $|\frac{1}{2}-q|>\alpha$. Then
$\epsilon_{p}=3\alpha<3|\frac{1}{2}-q|\leq\epsilon$, which means the algorithm
returns the current price $p$. Otherwise the algorithm observes
$\epsilon_{p}\leq\epsilon$ and returns. Thus if the algorithm sets some price
$p$ with $q=Q(p)$ satisfying $|q-\frac{1}{2}|\leq\frac{1}{3}\epsilon$, then
the algorithm would always return with this price.

Since the algorithm always finds a price $p$ with
$|Q(p)-\frac{1}{2}|\leq\frac{1}{3}\epsilon$ in
$a_{F}=\log\frac{1}{F^{-1}(\frac{1}{2}+\frac{\epsilon}{3})-F^{-1}(\frac{1}{2}-\frac{\epsilon}{3})}$
rounds of different prices. Let $n$ be the number of queries in the last round
of pricing. Then $t\leq a_{F}n$, and
$18\sqrt{\frac{\log(a_{F}n/\delta)}{n}}<\epsilon$. Therefore
$n=\tilde{O}(\frac{1}{\epsilon^{2}})\log\frac{a}{\delta}$, which means the
query complexity of the algorithm is at most
$a\tilde{O}(\frac{1}{\epsilon^{2}})\log\frac{a_{F}}{\delta}$.

∎

###  A.2 Missing proofs from Section 2.2

######  Corollary 2.3.

Let $\bar{\mathcal{C}}_{\bar{\sigma}}=\left\\{\mathcal{N}(\mu,\sigma)\text{
s.t. }\mu\in[0,1],\ \sigma\leq\bar{\sigma}\right\\}$ be the class of normal
distributions with variance at most $\bar{\sigma}^{2}$ with the loss
$\mathcal{L}(\theta,\hat{\theta})=|\theta-\hat{\theta}|$. Then the pricing
complexity of computing the mean is:

$\textsc{PriceCplx}_{\bar{\mathcal{C}}_{\bar{\sigma}},\mu}(\epsilon)=O(\bar{\sigma}^{2}/\epsilon^{2}).$

###### Proof of Corollary 2.3.

use the following variant of the algorithm for Theorem 2.2:

  * •

Use Algorithm 1 with $\epsilon=\frac{1}{12}$ to find $p_{1}$ and $p_{2}$ with
$Q(p_{1})\in[1/6,2/6]$ and $Q(p_{2})\in[4/6,5/6]$,

  * •

Using $O(\bar{\sigma}^{2}/\epsilon^{2})$ pricing queries, find estimates
$\hat{q}_{i}$ such that
$|\hat{q}_{i}-Q_{\mu,\sigma}(p_{i})|\leq\epsilon/\bar{\sigma}$.

  * •

Solve the system of equations $\hat{q}_{1}=Q_{\hat{\mu},\hat{\sigma}}(p_{1})$
and $\hat{q}_{2}=Q_{\hat{\mu},\hat{\sigma}}(p_{2})$ to find estimates of
$\hat{\mu},\hat{\sigma}$.

By the same argument as in the proof of Theorem 2.2, the equations above can
be re-written in linear form:

$\hat{\mu}+\hat{\sigma}\cdot
Q_{0,1}^{-1}(\hat{q}_{1})=p_{1}\qquad\hat{\mu}+\hat{\sigma}\cdot
Q_{0,1}^{-1}(\hat{q}_{2})=p_{2}$

The actual mean and variance are solutions to the same equation with exact
quantiles:

$\mu+\sigma\cdot Q_{0,1}^{-1}(q_{1})=p_{1}\qquad\mu+\sigma\cdot
Q_{0,1}^{-1}(q_{2})=p_{2}$

Comparing those equations we can observe the following (we omit the details of
the calculations as they are quite standard):

$|\mu-\hat{\mu}|\leq
O\left(\sigma|p_{1}-p_{2}|\cdot\max_{i}|Q_{0,1}^{-1}(\hat{q}_{i})-q_{i}|\right)=O\left(\sigma\cdot\frac{\epsilon}{\bar{\sigma}}\right)=O(\epsilon)$

This leads to an algorithm with $O(\bar{\sigma}^{2}/\epsilon^{2})$ pricing
queries that only requires knowledge of a _variance upper bound_.

∎

##  Appendix B Missing Proofs from Section 3

######  Lemma 3.1.

For any value distribution $F$ and value $p$, let $Q(p)=1-F(p)$ be the
probability that a random sample from $F$ is at least $p$. Then if we make
$m=\tilde{O}(\frac{1}{\epsilon^{2}}\log\frac{1}{\delta})$ pricing queries with
price $p$, then with probability $>1-\delta$ the price is accepted
$m(Q(p)\pm\epsilon)$ times.

###### Proof of Lemma 3.1.

Let $q^{*}=Q(p)$ be the probability that $v\sim F$ is at least $p$. For any
$m$ queries of price $p$, suppose that there are $t$ queries with signal
“$v\geq p$”. By Chernoff bound,

$\displaystyle\Pr\left(t\not\in[m(q^{*}-\epsilon)]\right)\leq
2\exp\left(-\frac{\epsilon^{2}m}{2q^{*}}\right)\leq
2\exp\left(-\frac{\epsilon^{2}m}{2}\right).$

When
$m=2\frac{1}{\epsilon^{2}}\log\frac{2}{\delta}=\Theta(\frac{1}{\epsilon^{2}}\log\frac{1}{\delta})$,
the right hand side of the above inequality be at most $\delta$. Thus if
$q^{*}\not\in[q-\epsilon,q+\epsilon]$ for some probability $q$, after
$m=\Theta(\frac{1}{\epsilon^{2}}\log\frac{1}{\delta})$ pricing queries on $p$,
with probability $<\delta$ the number of queries with signal “$v\geq p$” is in
$[m(q^{*}-\epsilon),m(q^{*}+\epsilon)]$. ∎

###  B.1 Missing proofs from Section 3.1

######  Lemma 3.2 (Relative Flatness of Regular Distributions).

Let Rev be the revenue curve of a regular distribution. Consider four
equidistant values $p_{1}<p_{2}<p_{3}<p_{4}=cp_{1}$ in $[0,1]$ and let
$\textsc{Rev}_{\max}$ and $\textsc{Rev}_{\min}$ be the maximum and minimum
value of the revenue curve at those four points. Then if
$\textsc{Rev}_{\min}\geq\textsc{Rev}_{\max}-\epsilon$, for some $\epsilon>0$,
then for any $p\in[p_{1},p_{4}]$,
$\textsc{Rev}(p)\leq\textsc{Rev}_{\max}+O(c\epsilon)$.

###### Proof of Lemma 3.2.

For each $i=1,2,3,4$, let $q_{i}=Q(p_{i})$. Denote $q=Q(p)$. Since
$p_{1}-\ell=p_{2}-p_{1}=p_{3}-p_{2}=p_{4}-p_{3}$, we have
$p_{1}<p_{4}=cp_{1}$. If $\textsc{Rev}_{\max}<2\epsilon$, then for any
$p\in[p_{1},p_{4}]$, $\textsc{Rev}(p)=pQ(p)\leq
p_{4}Q(p_{1})=cp_{1}Q(p_{1})\leq c\textsc{Rev}_{\max}=O(c\epsilon)$, thus
$\textsc{Rev}(p)\leq\textsc{Rev}_{\max}+O(c\epsilon)$. Therefore we assume
$\textsc{Rev}_{\max}\geq 2\epsilon$, then
$\textsc{Rev}(p_{1}),\textsc{Rev}(p_{2}),\textsc{Rev}(p_{3}),\textsc{Rev}(p_{4})\geq\frac{1}{2}\textsc{Rev}_{\max}$.
Thus $q_{1}=\frac{1}{p_{1}}\textsc{Rev}(p_{1})\leq\frac{c}{p_{4}}\cdot
2\textsc{Rev}(p_{4})=2cq_{4}$, in other words, all $q\in[q_{4},q_{1}]$ are
within a constant factor of $2c$.

Since Rev is the revenue curve of a regular distribution, it is a concave
function in quantile space. Consider the following two cases:

_Case 1:_ $p\geq Q^{-1}(\frac{q_{2}+q_{3}}{2})$. We can express $q_{2}$ as a
linear combination of $q_{1}$ and $q$ by
$q_{2}=\frac{q_{2}-q}{q_{1}-q}q+\frac{q_{1}-q_{2}}{q_{1}-q}q_{1}$, thus

$\textsc{Rev}(p_{2})\geq\frac{q_{2}-q}{q_{1}-q}\textsc{Rev}(p)+\frac{q_{1}-q_{2}}{q_{1}-q}\textsc{Rev}(p_{1}).$

Then

$\displaystyle\textsc{Rev}(p)$ $\displaystyle\leq$
$\displaystyle\frac{(q_{1}-q)\textsc{Rev}(p_{2})-(q_{1}-q_{2})\textsc{Rev}(p_{1})}{q_{2}-q}\leq\frac{(q_{1}-q)(\textsc{Rev}(p_{1})+\epsilon)-(q_{1}-q_{2})\textsc{Rev}(p_{1})}{q_{2}-q}$
(2) $\displaystyle=$
$\displaystyle\textsc{Rev}(p_{1})+\frac{q_{1}-q}{q_{2}-q}\epsilon=\textsc{Rev}(p_{1})+\frac{q_{1}-q_{2}}{q_{2}-q}\epsilon+\epsilon\leq\textsc{Rev}(p_{1})+\frac{q_{1}-q_{2}}{q_{2}-q_{3}}2\epsilon+\epsilon.$

Here the last inequality is by $q\leq\frac{q_{2}+q_{3}}{2}$.

If $\epsilon>\frac{1}{2}q_{3}(p_{3}-p_{2})$, then

$\epsilon>\frac{1}{2}q_{3}(p_{3}-p_{2})\geq\frac{1}{2}\cdot\frac{1}{2c}q\cdot\frac{1}{2}(p-p_{2})\geq\frac{1}{8c}(qp-
q_{2}p_{2})=\frac{1}{8c}(\textsc{Rev}(p)-\textsc{Rev}(p_{2})).$

Here the second inequality is by $q\geq\frac{1}{2c}q_{3}$, and $p-p_{2}\leq
p_{4}-p_{2}=2(p_{3}-p_{2})$; the third inequality is by $q\leq q_{2}$.
Therefore
$\textsc{Rev}(p)\leq\textsc{Rev}(p_{2})+O(c\epsilon)=\textsc{Rev}_{\max}+O(c\epsilon)$
if $\epsilon>\frac{1}{2}q_{3}(p_{3}-p_{2})$.

Now we assume that $\epsilon\leq\frac{1}{2}q_{3}(p_{3}-p_{2})$. Since
$\textsc{Rev}(p_{1})\leq\textsc{Rev}(p_{2})+\epsilon$, we have $p_{1}q_{1}\leq
p_{2}q_{2}+\epsilon$, then
$q_{1}-q_{2}\leq\frac{q_{1}(p_{2}-p_{1})+\epsilon}{p_{1}}$. At the same time,
$\textsc{Rev}(p_{2})\geq\textsc{Rev}(p_{3})-\epsilon$, we have $p_{2}q_{2}\geq
p_{3}q_{3}-\epsilon$, then
$q_{2}-q_{3}\geq\frac{q_{3}(p_{3}-p_{2})-\epsilon}{p_{2}}$. Thus

$\displaystyle\frac{q_{1}-q_{2}}{q_{2}-q_{3}}$ $\displaystyle\leq$
$\displaystyle\frac{p_{2}(q_{1}(p_{2}-p_{1})+\epsilon)}{p_{1}(q_{3}(p_{3}-p_{2})-\epsilon)}\leq\frac{p_{2}(q_{1}(p_{2}-p_{1})+\frac{1}{2}q_{3}(p_{3}-p_{2}))}{p_{1}(q_{3}(p_{3}-p_{2})-\frac{1}{2}q_{3}(p_{3}-p_{2}))}$
$\displaystyle\leq$
$\displaystyle\frac{2(q_{1}+\frac{1}{2}q_{3})}{(q_{3}-\frac{1}{2}q_{3})}=2+\frac{4q_{1}}{q_{3}}\leq
2+8c=O(c).$

Here the second inequality is by $\epsilon\leq\frac{1}{2}q_{3}(p_{3}-p_{2})$;
the third inequality is by $p_{2}\leq 2p_{1}$ and $p_{3}-p_{2}=p_{2}-p_{1}$;
the last inequality is by $q_{1}\leq 2cq_{3}$. By (2) we have
$\textsc{Rev}(p)\leq\textsc{Rev}_{\max}+O(c\epsilon)$.

_Case 2:_ $p<Q^{-1}(\frac{q_{2}+q_{3}}{2})$. We can express $q_{3}$ as a
linear combination of $q$ and $q_{4}$ by
$q_{3}=\frac{q-q_{3}}{q-q_{4}}q+\frac{q_{3}-p_{4}}{q-q_{4}}q_{4}$. Thus by
concavity of Rev in the quantile space,

$\textsc{Rev}(p_{3})\geq\frac{q-q_{3}}{q-q_{4}}\textsc{Rev}(p)+\frac{q_{3}-q_{4}}{q-q_{4}}\textsc{Rev}(p_{4}).$

Then

$\displaystyle\textsc{Rev}(p)$ $\displaystyle\leq$
$\displaystyle\frac{(q-q_{4})\textsc{Rev}(p_{3})-(q_{3}-q_{4})\textsc{Rev}(p_{4})}{q-q_{3}}\leq\frac{(q-q_{4})(\textsc{Rev}(p_{4})+\epsilon)-(q_{3}-q_{4})\textsc{Rev}(p_{4})}{q-q_{3}}$
(3) $\displaystyle=$
$\displaystyle\textsc{Rev}(p_{4})+\frac{q-q_{4}}{q-q_{3}}\epsilon=\textsc{Rev}(p_{4})+\frac{q_{3}-q_{4}}{q-q_{3}}\epsilon+\epsilon<\textsc{Rev}(p_{4})+\frac{q_{3}-q_{4}}{q_{2}-q_{3}}2\epsilon+\epsilon.$

Here the last inequality is by $q>\frac{q_{2}+q_{3}}{2}$.

If $\epsilon>\frac{1}{2}q_{3}(p_{3}-p_{2})$, then as we have reasoned in Case
1, $\textsc{Rev}(p)\leq\textsc{Rev}_{\max}+O(c\epsilon)$. Now we assume that
$\epsilon\geq\frac{1}{2}q_{3}(p_{3}-p_{2})$. Since
$\textsc{Rev}(p_{3})\leq\textsc{Rev}(p_{4})+\epsilon$, we have $p_{3}q_{3}\leq
p_{4}q_{4}+\epsilon$, then
$q_{3}-q_{4}\leq\frac{(p_{4}-p_{3})q_{4}+\epsilon}{p_{3}}$. At the same time,
as we have shown in Case 1,
$q_{2}-q_{3}\geq\frac{q_{1}(p_{3}-p_{2})-\epsilon}{p_{2}}$. Thus

$\displaystyle\frac{q_{3}-q_{4}}{q_{2}-q_{3}}$ $\displaystyle\leq$
$\displaystyle\frac{p_{2}(q_{4}(p_{4}-p_{3})+\epsilon)}{p_{3}(q_{3}(p_{3}-p_{2})-\epsilon)}\leq\frac{p_{2}(q_{4}(p_{4}-p_{3})+\frac{1}{2}q_{3}(p_{3}-p_{2}))}{p_{3}(q_{3}(p_{3}-p_{2})-\frac{1}{2}q_{3}(p_{3}-p_{2}))}$
$\displaystyle\leq$
$\displaystyle\frac{q_{4}+\frac{1}{2}q_{3}}{q_{3}-\frac{1}{2}q_{3}}=1+\frac{2q_{4}}{q_{3}}\leq
1+2=3.$

Here the second inequality is by $\epsilon\leq\frac{1}{2}q_{3}(p_{3}-p_{2})$;
the third inequality is by $p_{2}\leq p_{3}$ and $p_{3}-p_{2}=p_{4}-p_{3}$;
the last inequality is by $q_{4}\leq q_{3}$. By (3) we have
$\textsc{Rev}(p)\leq\textsc{Rev}_{\max}+O(c\epsilon)$.

∎

###  B.2 Mission proofs from Section 3.2

In this section, we prove the pricing query complexity for estimating the
monopoly price of MHR distributions.

######  Theorem 3.4.

Let $\mathcal{C}_{\textsc{MHR}}$ be the class of Monotone Hazard Rate
distributions supported in $[0,1]$ and let $\theta$ be the monopoly price.
Then

$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{MHR}},\theta}(\epsilon)=\Omega(1/\epsilon^{2}).$

Before proving the theorem, we start with a technical lemma bounding the KL-
divergence of two Bernoulli variables.

######  Lemma B.1.

For any $\epsilon<\frac{\sqrt{2}}{2}$ and two Bernoulli variables $X,Y$ with
$\frac{1}{1+\epsilon}\leq\frac{\Pr[X=1]}{\Pr[Y=1]},\frac{\Pr[X=0]}{\Pr[Y=0]}\leq
1+\epsilon$, $D_{\textrm{KL}}(X\|Y)<\epsilon^{2}$.

###### Proof of Lemma B.1.

Let $q=\Pr[X=1]$, $q^{\prime}=\Pr[Y=1]$. Without loss of generality assume
$q\leq\frac{1}{2}$ (otherwise just set $q\leftarrow 1-q$ and
$q^{\prime}\leftarrow 1-q^{\prime}$). Let
$f(q,q^{\prime})=D_{\textrm{KL}}(X\|Y)$. Then

$f(q,q^{\prime})=D_{\textrm{KL}}(X\|Y)=q\ln\frac{q}{q^{\prime}}+(1-q)\ln\frac{1-q}{1-q^{\prime}}=q\ln
q-q\ln q^{\prime}+(1-q)\ln(1-q)-(1-q)\ln(1-q^{\prime}).$

Then

$\frac{\partial}{\partial q}f(q,q^{\prime})=\ln q-\ln
q^{\prime}-\ln(1-q)+\ln(1-q^{\prime})=\ln\frac{q}{q^{\prime}}-\ln\frac{1-q}{1-q^{\prime}}$

has unique zero point $q=q^{\prime}$, which means $f(q,q^{\prime})$ increases
when $q>q^{\prime}$, and decreases when $q<q^{\prime}$. Therefore, to upper
bound $f(q,q^{\prime})$, it suffices to bound it for
$q=(1+\epsilon)q^{\prime}$ and $q=(1-\epsilon)q^{\prime}$.

#### Case 1.

When $q=(1+\epsilon)q^{\prime}$,

$\displaystyle f(q,q^{\prime})$ $\displaystyle=$ $\displaystyle
q\ln\frac{q}{q^{\prime}}+(1-q)\ln\frac{1-q}{1-q^{\prime}}$ $\displaystyle=$
$\displaystyle
q\ln(1+\epsilon)+(1-q)\ln(1-q)-(1-q)\ln\left(1-\frac{q}{1+\epsilon}\right).$

Take the derivative of the right hand side with respect to $q$, we have

$\displaystyle\frac{\partial}{\partial q}f\left(q,\frac{q}{1+\epsilon}\right)$
$\displaystyle=$
$\displaystyle\ln(1+\epsilon)-1-\ln(1-q)+\ln\left(1-\frac{q}{1+\epsilon}\right)+(1-q)\frac{1}{1+\epsilon}\frac{1}{1-\frac{q}{1+\epsilon}}$
$\displaystyle=$
$\displaystyle(\ln(1+\epsilon)-1)+\ln\frac{1-\frac{q}{1+\epsilon}}{1-q}+\frac{1-q}{1+\epsilon-q}>0.$

The inequality is true since each term in the sum is non-negative. Thus
$f(q,\frac{q}{1+\epsilon})$ is maximized when $q=\frac{1}{2}$, and

$\displaystyle f\left(q,\frac{q}{1+\epsilon}\right)\leq
f\left(\frac{1}{2},\frac{1}{2+2\epsilon}\right)=\frac{1}{2}\ln(1+\epsilon)+\frac{1}{2}\ln\frac{\frac{1}{2}}{1-\frac{1}{2+2\epsilon}}=\frac{1}{2}\ln\frac{(1+\epsilon)^{2}}{1+2\epsilon}<\frac{1}{2}\frac{\epsilon^{2}}{1+2\epsilon}<\epsilon^{2},$

here the second inequality is by $\ln(1+x)<x$ for any $x>0$.

#### Case 2.

When $q=\frac{1}{1+\epsilon}q^{\prime}$,

$\displaystyle f(q,q^{\prime})$ $\displaystyle=$ $\displaystyle
q\ln\frac{q}{q^{\prime}}+(1-q)\ln\frac{1-q}{1-q^{\prime}}$ $\displaystyle=$
$\displaystyle-q\ln(1+\epsilon)+(1-q)\ln(1-q)-(1-q)\ln\left(1-(1+\epsilon)q\right).$

Take the derivative of the right hand side with respect to $q$, we have

$\displaystyle\frac{\partial}{\partial q}f\left(q,(1+\epsilon)q\right)$
$\displaystyle=$
$\displaystyle-\ln(1+\epsilon)-1-\ln(1-q)+\ln\left(1-(1+\epsilon)q\right)+(1-q)(1+\epsilon)\frac{1}{1-(1+\epsilon)q}$
$\displaystyle=$
$\displaystyle-\ln\frac{(1-q)(1+\epsilon)}{1-(1+\epsilon)q}-1+\frac{(1-q)(1+\epsilon)}{1-(1+\epsilon)q}\geq
0.$

The inequality follows from $-\ln x-1+x\geq 0$ for any $x\geq 0$. Thus
$f\left(q,(1+\epsilon)q\right)$ is maximized when $q=\frac{1}{2}$, and

$\displaystyle f\left(q,(1+\epsilon)q\right)\leq
f\left(\frac{1}{2},\frac{1+\epsilon}{2}\right)=-\frac{1}{2}\ln(1+\epsilon)+\frac{1}{2}\ln\frac{\frac{1}{2}}{1-\frac{1}{2}(1+\epsilon)}=\frac{1}{2}\ln\frac{1}{1-\epsilon^{2}}<\frac{1}{2}\frac{\epsilon^{2}}{1-\epsilon^{2}}<x^{2},$

here the second inequality is by $\ln(1+x)<x$ for any $x>0$, and the last
inequality is by $\epsilon>\frac{\sqrt{2}}{2}$.

∎

The lemma is then used to give a lower bound on the pricing query complexity
of distinguishing two distributions whose c.d.f. $F(p)$ and quantiles
$Q(p)=1-F(p)$ are both within $1\pm\epsilon$ of each other.

######  Lemma 3.5.

For two value distributions $D$ and $D^{\prime}$, if
$\frac{1}{1+\epsilon}\leq\frac{Q_{D}(v)}{Q_{D^{\prime}}(v)},\frac{F_{D}(v)}{F_{D^{\prime}}(v)}\leq(1+\epsilon)$
for every $v\in[0,1]$, then $\Omega(\frac{1}{\epsilon^{2}})$ pricing queries
are needed to distinguish the two distributions with probability $>1-\delta$.

The proof idea of Lemma 3.5 is as follows. For two such distributions $D$ and
$D^{\prime}$, and any pricing algorithm $\mathcal{A}$, let $X_{i}$ and
$X^{\prime}_{i}$ be the bit each algorithm receives from the $i$-th pricing
query. To show that $\mathcal{A}$ needs $m=\Omega(\epsilon^{-2})$ queries to
distinguish the two distribution, it suffices to show that
$(X_{1},\cdots,X_{m})$ and $(X^{\prime}_{1},\cdots,X_{m})$ has $\Omega(1)$
statistical distance (thus KL-divergence $\Omega(1)$) only if
$\Omega(\epsilon^{-2})$. By Lemma B.1 the gain of relative entropy from each
query is at most $\epsilon^{2}$, thus $\Omega(\epsilon^{-2})$ queries are
needed for the KL-divergence to become $\Omega(1)$.

###### Proof of Lemma 3.5.

Consider any algorithm $\mathcal{A}$ that adaptively sets a pricing query in
each step. For every $i\geq 1$, let $X_{i}$ be a boolean random variable that
denotes whether the $i$-th sampled value $v_{i}\sim D$ is at least the price
$p_{i,D}$ at the $i$-th step in algorithm $\mathcal{A}$ for value distribution
$D$. In other words, $X_{i}=\mathbf{1}[v_{i}\geq p_{i,D}]$. Similarly, define
$X^{\prime}_{i}$ to be a boolean random variable that denotes whether the
$i$-th sampled value $v^{\prime}_{i}\sim D^{\prime}$ is at least the price
$p_{i,D^{\prime}}$ at the $i$-th step in algorithm $\mathcal{A}$ for value
distribution $D^{\prime}$. For each $n\geq 1$, denote $\mathbf{X}_{\leq
n}=(X_{1},X_{2},\cdots,X_{n})$ and $\mathbf{X}^{\prime}_{\leq
n}=(X^{\prime}_{1},X^{\prime}_{2},\cdots,X^{\prime}_{n})$.

For any price $p\in[0,1]$, random values $v\sim D$ and $v^{\prime}\sim
D^{\prime}$, and random variables $X=\mathbf{1}[v\geq p]$ and
$Y=\mathbf{1}[v^{\prime}\geq p]$, let $q=\Pr[X=1]$ and $q^{\prime}=\Pr[Y=1]$.
The Kullback–Leibler divergence of $X$ and $Y$ can be bounded by Lemma B.1.

Then for any fixed $(x_{1},\cdots,x_{m-1})\in\\{0,1\\}^{m-1}$, conditioned on
$(X_{1},\cdots,X_{m-1})=(x_{1},\cdots,x_{m-1})$ algorithm $\mathcal{A}$ sets a
random price $p$; $X_{m}$ is a Bernoulli variable with probability
$q=\mathbb{E}_{p}[\Pr_{v\sim D}[v\geq p]]=\mathbb{E}_{p}[Q_{D}(p)]$ being 1;
$X^{\prime}_{m}$ is a Bernoulli variable with probability
$q^{\prime}=\mathbb{E}_{p}[\Pr_{v\sim D^{\prime}}[v\geq
p]]=\mathbb{E}_{p}[Q_{D^{\prime}}(p)]$ being 1. By the condition of Lemma 3.5,
$\frac{1}{1+\epsilon}<\frac{q}{q^{\prime}},\frac{1-q}{1-q^{\prime}}<1+\epsilon$.
Thus by Lemma B.1,

$D_{\textrm{KL}}\bigg{(}X_{m}|_{\mathbf{X}_{\leq
m-1}=(x_{1},\cdots,x_{m-1})}\bigg{\|}X^{\prime}_{m}|_{\mathbf{X}^{\prime}_{\leq
m-1}=(x_{1},\cdots,x_{m-1})}\bigg{)}<\epsilon^{2}.$

For any $n\geq 1$, let $\mathbf{x}_{\leq n}=(x_{1},x_{2},\cdots,x_{n})$. Then
by the chain rule of KL divergence,

$\displaystyle D_{\textrm{KL}}(X_{\leq m}\|X^{\prime}_{\leq m})$
$\displaystyle=$ $\displaystyle D_{\textrm{KL}}(X_{\leq m-1}\|X^{\prime}_{\leq
m-1})+\mathbb{E}_{\mathbf{X}_{\leq
m-1}}D_{\textrm{KL}}\bigg{(}X_{m}|_{\mathbf{X}_{\leq m-1}=\mathbf{x}_{\leq
m-1}}\bigg{\|}X^{\prime}_{m}|_{\mathbf{X}^{\prime}_{\leq m-1}=\mathbf{x}_{\leq
m-1}}\bigg{)}$ $\displaystyle<$ $\displaystyle D_{\textrm{KL}}(X_{\leq
m-1}\|X^{\prime}_{\leq m-1})+\epsilon^{2}<D_{\textrm{KL}}(X_{\leq
m-2}\|X^{\prime}_{\leq m-2})+2\epsilon^{2}<\cdots<m\epsilon^{2}.$

Let $D_{m}$ and $D^{\prime}_{m}$ be the distribution of $\mathbf{X}_{\leq m}$
and $\mathbf{X}^{\prime}_{\leq m}$ respectively. The probability that
algorithm $\mathcal{A}$ can identify the distribution with $m$ samples is at
most $\frac{1+\delta(D_{m},D^{\prime}_{m})}{2}$, here
$\delta(A,B)=\frac{1}{2}\int|f_{A}(x)-f_{B}(x)|dx$ represents the statistical
distance of two distributions $A$ and $B$ with density $f_{A}$ and $f_{B}$
respectively. Thus to identify distribution $D$ and $D^{\prime}$ with
probability $1-\delta$, the number of samples $m$ need to be large enough such
that $\delta(D_{m},D^{\prime}_{m})=\Omega(1)$. By Pinsker’s inequality,

$\delta(D_{m},D^{\prime}_{m})\leq\sqrt{\frac{1}{2}D_{\textrm{KL}}(D_{m},D^{\prime}_{m})}<\sqrt{\frac{m}{2}\epsilon^{2}}.$

Thus when $\delta(D_{m},D^{\prime}_{m})=\Omega(1)$,
$\sqrt{\frac{m}{2}\epsilon^{2}}=\Omega(1)$. Thus
$m=\Omega(\frac{1}{\epsilon^{2}})$ samples are necessary to distinguish $D$
and $D^{\prime}$ with probability $>\frac{2}{3}$ for any (randomized adaptive)
algorithm $\mathcal{A}$. ∎

Finally, we are ready to analyze the pricing query complexity for estimating
the monopoly price for MHR distributions.

###### Proof of Theorem 3.4.

We consider the following MHR distribution $D$ with sample complexity
$\Omega(\epsilon^{-3/2})$ that is modified from an example in Huang et al
[15]. Let $\epsilon_{0}=16\epsilon$, and $f$ be the density of $D$ as follows:

$f_{D}(v)=\begin{cases}0.4&\textrm{ if }0\leq v<\frac{1}{2};\\\
1.6-3.2\sqrt{\epsilon_{0}}&\textrm{ if }\frac{1}{2}\leq
v<\frac{1}{2}+\frac{1}{2}\sqrt{\epsilon_{0}};\\\
1.6+\frac{3.2\epsilon_{0}}{1-\sqrt{\epsilon_{0}}}&\textrm{ if
}\frac{1}{2}+\frac{1}{2}\sqrt{\epsilon_{0}}\leq v\leq 1.\end{cases}$

Let $f_{D^{\prime}}(v)$ be the density of distribution $D^{\prime}$ as
follows:

$f_{D^{\prime}}(v)=\begin{cases}0.4&\textrm{ if }0\leq v<\frac{1}{2};\\\
1.6&\textrm{ if }\frac{1}{2}\leq v\leq 1.\end{cases}$

In other words, distribution $D^{\prime}$ is uniform on $[0,\frac{1}{2}]$ and
$[\frac{1}{2},1]$, while distribution $D$ is a perturbation of $D^{\prime}$ on
$[\frac{1}{2},1]$, with the density of $D^{\prime}$ in
$[\frac{1}{2},\frac{1}{2}+\frac{1}{2}\sqrt{\epsilon_{0}}]$ scaled down by a
factor of $1-2\sqrt{\epsilon_{0}}$, and the density of $D^{\prime}$ in
$[\frac{1}{2}+\frac{1}{2}\sqrt{\epsilon_{0}},1]$ scaled up by a factor of
$1+\frac{2\epsilon_{0}}{1-\sqrt{\epsilon_{0}}}$ in $D$. Let $F_{D}$ and
$F_{D^{\prime}}$ be the cumulative density function of $D$ and $D^{\prime}$
respectively, and let $Q_{D}(v)=1-F_{D}(v)$,
$Q_{D^{\prime}}(v)=1-F_{D^{\prime}}(v)$. Then for any $v\in[0,1]$,
$Q_{D^{\prime}}(v)\leq
Q_{D}(v)\leq\left(1+\frac{2\epsilon_{0}}{1-\sqrt{\epsilon_{0}}}\right)Q_{D^{\prime}}(v)$.
In other words, when setting any pricing query over the two distributions, the
probability that the buyer can afford to purchase the item differs by only a
factor of $1+\frac{2\epsilon_{0}}{1-\sqrt{\epsilon_{0}}}<1+3\epsilon_{0}$ for
small enough $\epsilon_{0}$.

For uniform distribution $D^{\prime}$, the optimal monopoly price is
$p_{D^{\prime}}^{*}=\frac{1}{2}$, with revenue $0.4$. Only prices in $p\leq
p_{0}=\frac{1}{2}+\sqrt{\epsilon}$ would lead to revenue $\geq
0.4-1.6\epsilon$. For uniform distribution $D$, the optimal monopoly price is
$p_{D}^{*}=\frac{1}{2}+\frac{1}{2}\sqrt{\epsilon_{0}}$, with revenue
$0.4+0.4\epsilon_{0}+0.8\epsilon_{0}^{3/2}=0.4+6.4\epsilon+51.2\epsilon^{3/2}>p^{*}_{D^{\prime}}Q_{D^{\prime}}(p^{*}_{D^{\prime}})+\epsilon$.
For $p\leq p_{0}$, the revenue is

$\displaystyle pQ_{D}(p)$ $\displaystyle\leq$ $\displaystyle
p_{0}Q_{D}(p_{0})=(0.5+\sqrt{\epsilon})(0.8-1.6\sqrt{\epsilon}(1-2\sqrt{\epsilon_{0}}))=0.4-1.6\epsilon+1.6\sqrt{\epsilon\epsilon_{0}}+3.2\epsilon\sqrt{\epsilon_{0}}$
$\displaystyle=$ $\displaystyle
0.4+4.8\epsilon+12.8\epsilon^{3/2}<p^{*}_{D}Q_{D}(p^{*}_{D})-\epsilon.$

Thus no price can get $\epsilon$-close to the optimal revenue for both
distribution $D$ and $D^{\prime}$ at the same time.

Consider a distribution that is one of $D$ and $D^{\prime}$. To learn the
optimal monopoly price or the optimal revenue of the distribution, one must be
able to distinguish the two distributions with pricing queries. Observe that
for any $v\leq\frac{1}{2}$, $F_{D}(v)=F_{D^{\prime}}(v)$ and
$Q_{D}(v)=Q_{D^{\prime}}(v)$, thus
$\frac{F_{D}(v)}{F_{D^{\prime}}(v)}=\frac{Q_{D}(v)}{Q_{D^{\prime}}(v)}=1$. For
any $v\in(\frac{1}{2},1]$,

$1\geq\frac{F_{D}(v)}{F_{D^{\prime}}(v)}\geq\frac{F_{D}(\frac{1}{2}+\frac{1}{2}\sqrt{v_{0}})}{F_{D^{\prime}}(\frac{1}{2}+\frac{1}{2}\sqrt{v_{0}})}=1-\frac{1.6\epsilon_{0}}{0.2+0.8\sqrt{\epsilon_{0}}}=\frac{1}{1+O(\epsilon)}$

and

$1\leq\frac{Q_{D}(v)}{Q_{D^{\prime}}(v)}\leq\frac{Q_{D}(\frac{1}{2}+\frac{1}{2}\sqrt{v_{0}})}{Q_{D^{\prime}}(\frac{1}{2}+\frac{1}{2}\sqrt{v_{0}})}=1+\frac{1.6\epsilon_{0}}{0.8-0.8\sqrt{\epsilon_{0}}}=1+O(\epsilon)$

by $\epsilon_{0}=16\epsilon$. Thus for any $v\in[0,1]$,
$\frac{1}{1+O(\epsilon)}\leq\frac{F_{D}(v)}{F_{D^{\prime}}(v)},\frac{Q_{D}(v)}{Q_{D^{\prime}}(v)}\leq
1+O(\epsilon)$. By Lemma 3.5 the number of queries needed to distinguish $D$
and $D^{\prime}$ is $\Omega(\frac{1}{\epsilon^{2}})$, which is also a lower
bound on the pricing complexity of estimating the monopoly price for MHR
distributions.

∎

###  B.3 Missing proofs from Section 3.3

######  Theorem 3.6.

Let $\mathcal{C}_{\textsc{ALL}}$ be the class of all value distributions on
$[0,1]$ and $\theta$ be the monopoly. Then

$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{ALL}},\theta}(\epsilon)=\tilde{\Theta}(1/\epsilon^{3}).$

###### Proof of Theorem 3.6.

Firstly we show that
$\textsc{PriceCplx}_{\mathcal{C}_{\textsc{ALL}},\theta}(\epsilon)=\tilde{O}(1/\epsilon^{3}).$
Actually, consider the following simple algorithm: price at every multiple of
$\epsilon$ in $[0,1]$ for $\tilde{O}(\frac{1}{\epsilon^{2}})$ times such that
for every such price $p$, $Q(p)$ is estimated by $\tilde{Q}(p)\in
Q(p)\pm\epsilon$ (by Lemma 3.1). Notice that for price $p^{*}$ that maximizes
the revenue $\textsc{Rev}(p^{*})=p^{*}Q(p^{*})$, the revenue from price
$p=\epsilon\lfloor\frac{p^{*}}{\epsilon}\rfloor$ is
$\textsc{Rev}(p)=pQ(p)\geq(p^{*}-\epsilon)Q(p^{*})\geq\textsc{Rev}(p^{*})-\epsilon$.
Since the algorithm estimate $Q(p)$ with additive error $\epsilon$, thus
$\widetilde{\textsc{Rev}}(p)\geq\textsc{Rev}(p)-\epsilon\geq\textsc{Rev}(p^{*})-2\epsilon$.
This means that the price $\hat{p}$ being a multiple of $\epsilon$ that
maximizes $\hat{p}\tilde{Q}(\hat{p})$ estimates the optimal revenue with error
$O(\epsilon)$.

Now we show that the $\Omega(\frac{1}{\epsilon^{3}})$ pricing complexity is
unavoidable. Consider the following $m=\frac{1}{16\epsilon}$ distributions
$F_{0},F_{1},\cdots,F_{m}$. Distribution $F_{i}$ has support
$\frac{1}{2}+4\epsilon$, $\frac{1}{2}+8\epsilon$, $\cdots$,
$\frac{3}{4}-4\epsilon$, $\frac{3}{4}$, with the item-pricing revenue and
quantiles satisfying

$\textsc{Rev}_{i}\left(\frac{1}{2}+4k\epsilon\right)=\left(\frac{1}{2}+4k\right)\cdot
Q_{i}\left(\frac{1}{2}+4k\right)=\begin{cases}\frac{1}{4},&\textrm{ if }k\neq
i;\\\ \frac{1}{4}+\epsilon,&\textrm{ if }k=i.\end{cases}$

In other words, for $i\geq 1$, each distribution $F_{i}$ has a unique revenue-
maximizing price $\frac{1}{2}+4i\epsilon$ with revenue $\frac{1}{4}+\epsilon$,
while other prices leads to revenue $\frac{1}{4}$ that is $\epsilon$-far from
the optimal revenue. $F_{0}$ is an equal-revenue distribution with revenue
$\frac{1}{4}$ for every price $\frac{1}{2}+4k\epsilon$. Thus the quantile of
any two distributions $F_{0}$ and $F_{i}$ only differs at one point:
$Q_{i}(\frac{1}{2}+4i\epsilon)=Q_{0}(\frac{1}{2}+4i\epsilon)+\Theta(\epsilon)$.
For any other price $p=\frac{1}{2}+4k\epsilon$ with $k\neq i,j$,
$Q_{i}(p)=Q_{0}(p)$. Then for any $i\in[\frac{m}{3},\frac{2m}{3}]$, since
$Q_{i}(\frac{1}{2}+4i\epsilon)=\Theta(1)$ and
$F_{i}(\frac{1}{2}+4i\epsilon)=\Theta(1)$,
$\frac{1}{1+O(\epsilon)}\leq\frac{Q_{i}(v)}{Q_{0}(v)},\frac{F_{i}(v)}{F_{0}(v)}\leq
1+O(\epsilon)$. By Lemma 3.5, to distinguish $F_{i}$ and $F_{0}$,
$\Omega(\frac{1}{\epsilon^{2}})$ pricing queries on $\frac{1}{2}+4i\epsilon$
are needed.

Consider a setting where the underlying value distribution is $F_{i}$ for $i$
uniformly selected from $[\frac{1}{3}m,\frac{2}{3}m]$ but unknown beforehand.
To find out the optimal revenue and the corresponding price, it is equivalent
to find out the underlying value distribution. To distinguish $F_{0}$ and
$F_{i}$, at least $\Omega(\frac{1}{\epsilon^{2}})$ pricing queries are needed
on price $\frac{1}{2}+4i\epsilon$. Thus to distinguish $F_{0}$ and all other
distributions, at least $\Omega(\frac{1}{\epsilon^{2}})$ pricing queries are
needed on every price $\frac{1}{2}+4i\epsilon$, thus the query complexity is
$\Omega(\frac{1}{\epsilon^{3}})$. ∎