# Revelation Gap for Pricing from Samples

Yiding Feng Department of Computer Science, Northwestern University. Email:
<EMAIL_ADDRESS>Jason D. Hartline Department of Computer
Science, Northwestern University. Email<EMAIL_ADDRESS>Yingkai Li
Department of Computer Science, Northwestern University. Email:
<EMAIL_ADDRESS>
###### Abstract

This paper considers prior-independent mechanism design, in which a single
mechanism is designed to achieve approximately optimal performance on every
prior distribution from a given class. Most results in this literature focus
on mechanisms with truthtelling equilibria, a.k.a., truthful mechanisms. Feng
and Hartline [2018] introduce the revelation gap to quantify the loss of the
restriction to truthful mechanisms. We solve a main open question left in Feng
and Hartline [2018]; namely, we identify a non-trivial revelation gap for
revenue maximization.

Our analysis focuses on the canonical problem of selling a single item to a
single agent with only access to a single sample from the agent’s valuation
distribution. We identify the sample-bid mechanism (a simple non-truthful
mechanism) and upper-bound its prior-independent approximation ratio by 1.835
(resp. 1.296) for regular (resp. MHR) distributions. We further prove that no
truthful mechanism can achieve prior-independent approximation ratio better
than 1.957 (resp. 1.543) for regular (resp. MHR) distributions. Thus, a non-
trivial revelation gap is shown as the sample-bid mechanism outperforms the
optimal prior-independent truthful mechanism. On the hardness side, we prove
that no (possibly non-truthful) mechanism can achieve prior-independent
approximation ratio better than 1.073 even for uniform distributions.

##  1 Introduction

One important research direction in modern computer science focuses on multi-
party computation. Two fundamental concerns in this area are (i) who should be
doing what part of the computation; and (i) what are their incentives to do it
correctly. The second concern has been studied extensively in the economics
field of mechanism design. For the first concern, however, the system design
field and the mechanism design field have different high-level guidelines. The
end-to-end argument [cf. Saltzer, Reed, and Clark, 1984] – a long-standing
principle in system design – suggests that the computation should be done
where the data is, i.e., in a decentralized fashion. On the other hand, due to
revelation principle (see next paragraph), the mechanism design literature
favors systems where the entire computation is done by a center with other
participants truthfully reporting their portion of the input data to the
optimization. Addressing this discrepancy, in this paper, we argue that such
decentralization idea from the system design field is beneficial even in
purely economic terms when robust mechanisms are desired.

Revelation principle, a seminal observation in mechanism design suggests that
if there is a mechanism with good equilibrium outcome, there is a mechanism
which achieves the same outcome in a truthtelling equilibrium. This
constructed mechanism asks agents to report true preferences, simulates the
agent strategies in the original mechanism, and outputs the outcome of the
simulation. Due to this guiding principle, a vast number of studies in
mechanism design focus on truthful mechanisms (i.e., ones where revealing
preferences truthfully forms an equilibria). However, successful applications
– e.g., first-price auction, generalized second-price auction for advertisers
in sponsored search – suggest a great practical impact for non-truthful
mechanisms. From the view of multi-party computation, the mechanism itself as
well as the participating agents can be thought as different parties in the
system, where agents have their private preference as their input data.
Truthful mechanisms correspond to systems where the optimization is done by
the center (i.e. mechanism) and other parties (i.e. agents) only truthfully
report their preference. Non-truthful mechanisms correspond to systems
recommended by the end-to-end argument [Saltzer, Reed, and Clark, 1984], where
agents are also perform some of the computation (i.e. computing their
strategies).

To provide a theoretical understanding of the potential inadequacy of
revelation principle and advantages of non-truthful mechanisms, we consider
questions from prior-independent mechanism design, in which a mechanism is
designed for agents with preferences drawn from an unknown distributions
(a.k.a. prior). The goal is to identify robust mechanisms – ones with good
(multiplicative) prior-independent approximation to the optimal mechanism that
is tailored to the distribution of preferences. In prior-independent mechanism
design, it is not generally without loss to restrict to truthful mechanisms –
the equilibrium strategies for Bayesian agents in non-truthful mechanisms are
a function of their prior and thus the construction of truthful mechanism via
revelation principle is no longer prior-independent. Nonetheless, similar to
other lines of research in mechanism design, most results in prior-independent
mechanism design focus, with loss of generality, on truthful mechanisms. To
understand the loss of the restriction to truthful mechanisms, Feng and
Hartline [2018] introduce revelation gap, a quantification of optimal prior-
independent approximation ratio among all truthful mechanisms vs. the optimal
prior-independent approximation ratio among all (possibly non-truthful)
mechanisms. They identify a non-trivial revelation gap for welfare-
maximization. A main open question left in Feng and Hartline [2018] it to
identify a non-trivial revelation gap in any canonical model for revenue
maximization, which is another important and presumably technically more
challenging objective in mechanism design.

### Main Results

In this paper, we focus on revenue maximization in a canonical single-item
environment for a single agent with a single sample access, i.e., the agent’s
value is drawn from an unknown distribution but the mechanism can access a
single sample (independent to agent’s value) from that distribution [cf.
Dhangwatnotai, Roughgarden, and Yan, 2015, Allouah and Besbes, 2019]. The
agent knows her private valuation and the distribution for valuation, but she
does not know the sample of the mechanism. Our main theorem identifies a non-
trivial revelation gap for revenue maximization in this model. This theorem
follows from three results. First, we introduce the (non-truthful) sample-bid
mechanism and obtain an upper bound of its prior-independent approximation
ratio. Second, we obtain a lower bound of the optimal prior-independent
approximation ratio among all possible mechanisms. Third, we show that any
truthful mechanism111We impose a technical assumption (i.e. scale-invariant)
to the class of truthful mechanisms, which is common in prior-independent
mechanism design [Allouah and Besbes, 2018, 2019, Hartline, Johnsen, and Li,
2020].  is equivalent to a sampled-based pricing mechanism introduced by
Allouah and Besbes [2019] where the authors lower-bound and upper-bound the
optimal prior-independent approximation ratio among all sample-based pricing
mechanisms. See Table 1 for a summary of all three results. Since the prior-
independent approximation ratio of the sample-bid mechanism is strictly better
than the optimal prior-independent approximation ratio among all truthful
mechanisms, we immediately get our non-trivial revelation gap for revenue
maximization.

Table 1: Prior-independent approximation factor of single-agent revenue-
maximization with single-sample access. Two class of distributions (i.e.
regular, MHR – standard assumptions in mechanism design) are considered, where
MHR distributions is a subclass of regular distributions. We impose a
technical assumption (i.e. scale-invariant, Definition 7.1) to the class of
truthful mechanisms.

|  Class of truthful mechanisms |  Class of all mechanisms
---|---|---
| Regular dists. | MHR dists. | Regular dists. | MHR dists.
Upper bound |  1.99611footnotemark: 1 |  1.57511footnotemark: 1 |  1.83555footnotemark: 5 |  1.29633footnotemark: 3
Lower bound |  1.95711footnotemark: 1 |  1.54311footnotemark: 1 |  1.07344footnotemark: 4

11footnotemark: 1

Allouah and Besbes [2019] and Lemma 7.2;

55footnotemark: 5

Theorem 4.1; 33footnotemark: 3 Theorem 5.1; 44footnotemark: 4 Theorem 6.1.

In the model of a single agent with single-sample access, the class of non-
truthful mechanisms is rich, which includes fairly complicated mechanisms. For
example, mechanisms can ask agents to reports both her value and prior; or
include multiple rounds of communication between seller and agent who
sequentially reveal their private information.222Recall that the agent knows
the distribution of the sample but does not know its realization.
Nonetheless, our upper bound of the optimal prior-independent approximation
ratio is attained by a simple non-truthful mechanism – _sample-bid mechanism_
defined as follow.

  * •

Sample-bid mechanism: Given parameter $\alpha$ and sample $s$, the sample-bid
mechanism solicits a non-negative bid $b\geq 0$, charges the agent
$\alpha\cdot\min\\{b,s\\}$, and allocates the item to the agent if $b\geq s$.

From the agent’s perspective, she reports a bid to compete for the item
against a random sample realized from the same valuation distribution; and
regardless of whether she wins or loses, she will always be charged
$\alpha\cdot\min\\{b,s\\}$. In fact, the agent’s optimal bidding strategy
could be overbidding or underbidding, depending on the value as well as the
distribution. The sample-bid mechanism has the similar format as the
Becker–DeGroot–Marschak method [Becker, DeGroot, and Marschak, 1964] which has
been studied and implemented in experimental economics for understanding
agents’ perception of the random event.

In order to beat the optimal prior-independent approximation ratio among all
truthful mechanisms, we need to show the approximation for the sample-bid
mechanism is strictly better than $1.957<2$ for regular distributions, and
$1.543<\nicefrac{{e}}{{(e-1)}}$ for MHR distributions. However, most
approximation techniques and results for non-truthful mechanisms in the
literature only provide similar or or larger constants – for instance,
smoothness property, permeability, and revenue covering property in price of
anarchy [cf. Roughgarden, Syrgkanis, and Tardos, 2017, Dütting and Kesselheim,
2015, Hartline, 2016, see more discussion in related work].333 Feng and
Hartline [2018] bypass this challenge in their revelation gap for welfare
maximization by considering a model where the all-pay auction [cf. Maskin,
2000] achieves prior-independent approximation ratio 1, i.e., it is indeed the
Bayesian optimal mechanism.  One the other hand, analyzing the approximation
of truthful mechanisms is relatively easier. In revenue maximization, one
analysis approach used extensively for truthful mechanisms is the revenue
curve reduction (see next paragraph). This approach has lead to tight or
nearly tight results in both prior-independent approximation [Allouah and
Besbes, 2018, 2019, Hartline, Johnsen, and Li, 2020] and Bayesian
approximation [Alaei, Hartline, Niazadeh, Pountourakis, and Yuan, 2019, Jin,
Lu, Tang, and Xiao, 2020, 2019].

Revenue curves [cf. Bulow and Roberts, 1989] give an equivalent representation
of agent’s valuation distribution and enable clean characterizations of the
revenue of any mechanism [see e.g. Myerson, 1981, Bulow and Roberts, 1989,
Alaei, Fu, Haghpanah, and Hartline, 2013]. The high-level goal of revenue
curve reduction is to identify a subclass of revenue curves that has closed
form and over which the worst approximation guarantee is attained. The main
argument is to design a (problem or mechanism) specific modification to the
revenue curve (converting an arbitrary revenue curve into a revenue curve from
the subclass) and analyze the impact of revenue from the modification on the
given mechanism. Note that revenue is the expected payment of the agents when
they bid optimally. For truthful mechanisms, after the modification has been
designed, it is sufficient to study how payment changes for every bid in the
modification, since agents are bidding truthfully (i.e. bids equal values).
However, for non-truthful mechanisms, converting a revenue curve to another
one will lead to changes in both the payment for each bid and the optimal
bidding strategy of each agent. This makes the revenue curve reduction
approach more difficult for non-truthful mechanisms, and thus, results of non-
truthful mechanisms in the literature rarely uses this technique. In this
paper, due to the simplicity of our model and the sample-bid mechanism, we are
able to apply this technique by carefully (but relatively loosely)
disentangling these two impacts and then analyzing them separately.

Our final result for the single-agent pricing from samples model provides a
lower bound on the optimal prior-independent approximation ratio among the
class of all mechanisms. This result contrasts with multi-agent models where
there there exists complicated and arguably impractical non-truthful mechanism
whose prior-independent approximation is arbitrarily close to 1.444Such
mechanisms are designed and analyzed in non-parametric implementation theory –
a line of research in economics, see the survey of Jackson [2001] and further
discussion in the related work section. The crucial observation for proving
this lower bound is that for pointmass distributions, the agent perfectly
knows the seller’s sample. Thus, she can strategically imitate the behavior of
the values in other distributions. This restricts the seller’s ability to
extract revenue from the agent, which leads to a prior-independent
approximation ratio at least 1.073 even on the restricted subclass of MHR
distributions (in fact, even on uniform distributions). Our lower bound also
suggests that it will be non-trivial to identify the non-truthful mechanism
which attains the optimal prior-independent approximation ratio.

It should be noted that our better-performing non-truthful prior-independent
mechanisms do not come without drawbacks relative to truthful prior-
independent mechanisms. Elegantly, truthful prior-independent mechanisms do
not require prior knowledge by any party. In contrast, non-truthful prior-
independent mechanisms generally require some knowledge of the prior on the
part of the agents. From this perspective, our results show that a seller is
able to extract strictly higher revenue from the agent by taking advantage of
information that the agent possesses and is able to strategize with respect
to.

### Important Directions

Despite the practical importance of non-truthful mechanisms, the literature on
mechanism design almost exclusively considers the design of truthful
mechanisms. Thus, the most general direction from this paper is to
systematically build a theory for the design of non-truthful mechanisms with
good performance guarantee. Some recent works on this topic are equilibrium
analysis of i.i.d. rank-based mechanism [Chawla and Hartline, 2013], robust
analysis of welfare and revenue for classic mechanisms in practice (i.e. price
of anarchy, see discussion in related work), estimating revenue and welfare in
a mechanism from equilibrium bids in another mechanism [Chawla, Hartline, and
Nekipelov, 2014b, 2016], and the sample complexity of non-truthful mechanisms
in asymmetric environments [Hartline and Taggart, 2019].

Though Feng and Hartline [2018] and this paper demonstrate non-trivial
revelation gap for both welfare-maximization and revenue maximization, both
gaps are constant. Thus, one interesting open question left is to identify a
superconstant revelation gap in a canonical model where simple non-truthful
mechanisms are sufficient to beat the optimal prior-independent truthful
mechanisms, and we conjecture that the single-agent with single-sample access
model without any regularity assumption on distributions might be a good
candidate to answer this question.

Prior-independent mechanism design for a single item with symmetric agents is
an extensively studied model [Bulow and Klemperer, 1996, Devanur et al., 2015,
Fu et al., 2015]. The fundamental difficulty is to pin down the optimal prior-
independent approximation ratio even for the two-agent setting. Recently,
Allouah and Besbes [2018] obtain the tight bounds of optimal prior-independent
truthful mechanism for MHR distributions, and Hartline, Johnsen, and Li [2020]
generalize it to regular distributions. In both works, the main technique is
the revenue curve reduction. An open question here is to identify simple non-
truthful mechanism which outperforms the optimal prior-independent truthful
mechanism in this canonical single-item two-agents model.

In this work, we apply the revenue curve reduction approach – a powerful
technique of approximation analysis for truthful mechanisms – to a non-
truthful mechanism. Our argument is not as general as ones for truthful
mechanisms and thus there are gaps between the lower bound and upper bound.
Besides sharpening these bounds as an open question, an important open
question is to design general analysis framework on revenue curves for non-
truthful mechanisms.

### Related Work

Prior-independent mechanism design, as a standard framework for understanding
the robustness of mechanisms, has been applied to single-dimensional mechanism
design (Dhangwatnotai et al., 2015, citealpRTY-12, Fu et al., 2015,Allouah and
Besbes, 2018,Feng and Hartline, 2018, Hartline et al., 2020), multi-
dimensional mechanism design (Devanur et al., 2011,Roughgarden et al.,
2020,Goldner and Karlin, 2016), makespan minimization [Chawla, Hartline,
Malec, and Sivan, 2013], mechanism design for risk-averse agents [Fu,
Hartline, and Hoy, 2013], and mechanism design for agents with interdependent
values [Chawla, Fu, and Karlin, 2014a]. Except Fu, Hartline, and Hoy [2013]
and Feng and Hartline [2018], all other results focus on truthful mechanisms.

There is a significant area of research studying mechanism design with sample
access from the distribution of agents’ preference, which has two regimes –
small number of samples, and large number of samples. In the former regime,
literature studies the approximation of mechanisms with a single-sample access
[Azar, Kleinberg, and Weinberg, 2014, Dhangwatnotai, Roughgarden, and Yan,
2015, Allouah and Besbes, 2019, Feng, Hartline, and Li, 2019, Correa, Dütting,
Fischer, and Schewior, 2019, Dütting, Fusco, Lazos, Leonardi, and
Reiffenhäuser, 2020, Correa, Cristi, Epstein, and Soto, 2020], and mechanisms
with two-sample access [Babaioff, Gonczarowski, Mansour, and Moran, 2018,
Daskalakis and Zampetakis, 2020]. In the latter regime, the goal is to
minimize the sample complexity, i.e., number of sample to achieve
$(1-\epsilon)$-approximation [e.g. Cole and Roughgarden, 2014, Morgenstern and
Roughgarden, 2015, Huang et al., 2018, Gonczarowski and Weinberg, 2018, Guo et
al., 2019, Hartline and Taggart, 2019]. Except Hartline and Taggart [2019],
all other results focus on truthful mechanisms.

Price of anarchy studies how classic non-truthful mechanisms (e.g. first-price
auction, all-pay auction) approximate the optimal welfare. Syrgkanis and
Tardos [2013] introduce a smoothness property defined on mechanisms and give
an analysis framework based on this property. With this smoothness framework,
the authors upper-bound the welfare-approximation of the first-price auction
by $\nicefrac{{e}}{{(e-1)}}$, and the welfare-approximation of the all-pay
auction by 2. These two results are later tightened by Christodoulou,
Sgouritsa, and Tang [2015] for the all-pay auction and Hoy, Taggart, and Wang
[2018] for the first-price auction using some mechanism-specific arguments.
Hartline, Hoy, and Taggart [2014] introduce a geometric framework for
analyzing the price of anarchy for both welfare and revenue. As the
instantiations of the framework, authors upper-bound the revenue approximation
of the first-price auction with individual monopoly reserve by
$\nicefrac{{2e}}{{(e-1)}}$. Dütting and Kesselheim [2015] show that bounds
from these analysis frameworks are tight up to constant factors.

The literature on non-parametric implementation theory considers the same
question as prior-independent mechanism design but allows mechanisms where
agents cross-report their beliefs on other agents’ values [e.g., Jackson,
2001]. Caillaud and Robert [2005] introduce a dynamic auction for single-item
multi-agent settings which is able to implement the Bayesian revenue optimal
auction [Myerson, 1981] without the knowledge of agents’ distribution.
Dasgupta and Maskin [2000] introduce a generalization of VCG auction for
multi-agent interdependent value settings.555In general, there is no incentive
compatible mechanism which outputs the welfare-optimal outcomes in
interdependent value settings. In this auction, agents are asked to submit a
function that gives a bid for every possible valuation of the other agents.
Though this auction requires no knowledge of agents’ distributions, Dasgupta
and Maskin [2000] show that it is Bayesian welfare-optimal under mild
assumptions. Azar et al. [2012] study how to use scoring rules to learn
agents’ distribution and implement the auction based on this learned
distribution. All results above suggest that in the multi-agent settings,
there exist complicated and arguably impractical non-truthful mechanisms whose
prior-independent approximation equal or are arbitrarily close to 1. However,
as we mentioned earlier, in the model of a single-agent with single-sample
access, we provide a lower bound on the optimal prior-independent
approximation without any restriction on mechanisms.

##  2 Preliminaries

#### Model

This paper focuses on the single-item revenue-maximization problem with a
single agent. The agent has a private value $v$ drawn from a valuation
distribution (a.k.a. prior) $F$ supported on $[\underline{v},\overline{v}]$.
we assume that distribution $F$ has positive density $f$ every where in the
support. Given allocation $x$ and payment $p$, the utility of the agent is
$vx-p$.

We consider the prior-independent mechanism design with a single sample
access. Namely, the seller does not know the valuation distribution $F$, but
has a single sample $s$ drawn from $F$. The agent knows the valuation
distribution $F$ but does not observe the sample $s$, and the value $v$ of the
agent is independent of the sample $s$. A mechanism ${\cal
M}=(\tilde{x},\tilde{p})$ includes an allocation rule
$\tilde{x}:\mathbb{R}\times\mathbb{R}\rightarrow[0,1]$ mapping from the
agent’s bid $b$ and the sample $s$ to the allocation probability of the item;
and a payment rule
$\tilde{p}:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}_{+}$ mapping from
the agent’s bid $b$ and the sample $s$ to the payment charged from the agent.
Let $\tilde{x}(b,F)=\text{\bf E}_{s\sim F}\\!\left[{\tilde{x}(b,s)}\right]$,
$\tilde{p}(b,F)=\text{\bf E}_{s\sim F}\\!\left[{\tilde{p}(b,s)}\right]$ be the
expected allocation and payment over the randomness of the sample $s$ drawn
from distribution $F$. The seller first announce the mechanism ${\cal
M}=(\tilde{x},\tilde{p})$ to the buyer, and then the sample $s$ and value $v$
are realized from distribution $F$. The agent report a bid $b$ based on her
private value $v$, and the seller implements the mechanism ${\cal M}$ with
input $b$ and sample $s$. We assume that the seller has full commitment power
on implementing the mechanism.

Given a mechanism $(\tilde{x},\tilde{p})$ and distribution $F$, the _best
response_ of the agent is $b(\cdot,F):\mathbb{R}\rightarrow\mathbb{R}$ which
maximizes her expected utility, i.e., for every value $v$,
$b(v,F)\in\operatorname{argmax}_{b}v\cdot\tilde{x}(b,F)-\tilde{p}(b,F)$.666When
there are multiple bids maximizing the utility of the agent, we allow the
agent to choose any bid maximizing her utility. The revenue guarantee we
obtained in this paper holds even when the agent can break tie and choose the
bid minimizing the revenue of the seller.  A mechanism $(\tilde{x},\tilde{p})$
is _incentive compatible (IC)_ if reporting the agent’s value truthfully is
her best response, i.e., $b(v,F)=v$ for all $v$ and $F$. A mechanism
$(\tilde{x},\tilde{p})$ is _individual rational (IR)_ if the agent’s utility
under her best response is non-negative, i.e,
$\max_{b}v\cdot\tilde{x}(b,F)-\tilde{p}(b,F)\geq 0$ for all $v$ and
$F$.777Note that the utility of the agent can be negative for some realization
of the sample $s$, but in expectation it must be non-negative.

For any mechanism $(\tilde{x},\tilde{p})$, let $x(v,F,s)=\tilde{x}(b(v,F),s)$
be the interim allocation of value $v$ given distribution $F$ and sample $s$
when the agent follows her best response, and let
$p(v,F,s)=\tilde{x}(b(v,F),s)$ be the interim payment. Moreover, denote
$x(v,F)=\text{\bf E}_{s\sim F}\\!\left[{x(v,F,s)}\right]$ and
$p(v,F)=\text{\bf E}_{s\sim F}\\!\left[{p(v,F,s)}\right]$ as the expected
interim allocation and payment. We often omit $F$ in the notation if it is
clear from the context.

The revenue $\text{\bf Rev}_{F}\\!\left[{{\cal M}}\right]$ of a mechanism
${\cal M}=(x,p)$ on distribution $F$ is the expected payment when the agent
plays her best response, i.e., $\text{\bf E}_{v\sim
F}\\!\left[{p(v,F)}\right]$. We evaluate mechanisms by the prior-independent
approximation ratio.

######  Definition 2.1.

The _prior-independent approximation ratio_ of a mechanism ${\cal M}$ over a
class of distributions DISTS is defined as

$\displaystyle\Gamma({\cal
M},\text{DISTS})\triangleq\max_{F\in\text{DISTS}}\frac{\text{\bf
Rev}_{F}\\!\left[{\operatorname{OPT}_{F}}\right]}{\text{\bf
Rev}_{F}\\!\left[{{\cal M}}\right]}$

where $\text{\bf
Rev}_{F}\\!\left[{\operatorname{OPT}_{F}}\right]\triangleq\max\limits_{p}\;(1-F(p))\,p$
is the optimal revenue for distribution $F$ [cf. Myerson, 1981].

#### Revenue Curve

For any distribution $F$, let $q(v,F)=1-F(v)$ be the quantile for the
distribution, and $v(q,F)$ be the value $v$ such that $q=1-F(v)$. Here we
introduce the revenue curve in quantile space [cf. Bulow and Roberts, 1989],
which is a useful tool in the revenue analysis.

######  Definition 2.2.

For any valuation distribution $F$, the revenue curve $R(q,F)$ of the agent is
a mapping from any $q\in[0,1]$ to the optimal revenue from an agent with value
drawn from $F$ subject to the constraint that the item is allocated with ex
ante probability $q$.

In the later analysis in the paper, when $F$ is clear from the context, we
omit it in the notation and only use $R(q)$ to represent the revenue curve and
$q(v)$ to represent the quantile of value $v$. Let
$\phi(v)=v-\frac{1-F(v)}{f(v)}$ be the virtual value of the agent.

######  Definition 2.3.

An valuation distribution $F$ is regular if the virtual value of the agent is
weakly increasing.

######  Theorem 2.1 (Myerson, 1981).

A distribution $F$ is regular if and only if the corresponding revenue curve
$R(q,F)$ is concave.

######  Theorem 2.2 (Myerson, 1981).

For any distribution $F$ and any mechanism with interim allocation and payment
rule $x(v),p(v)$, the expected revenue of the seller equals the expected
virtual value of the agent plus the payment of the lowest value
$\underline{v}$, i.e., $\text{\bf E}_{v\sim F}\\!\left[{p(v)}\right]=\text{\bf
E}_{v\sim F}\\!\left[{x(v)\phi(v)}\right]+p(\underline{v})$.

Finally, we define the monopoly reserve and monopoly quantile of the agent
given the revenue curve $R$.

######  Definition 2.4.

The monopoly quantile of the agent is
$q_{m}=\operatorname{argmax}_{q}R(q)$,888In this paper, we break tie in favor
of smaller quantile. Note that all the results are not affected by the tie
breaking rule. and the monopoly reserve of the agent is
$v_{m}=\nicefrac{{R(q_{m})}}{{q_{m}}}$.

##  3 The Sample-bid Mechanism

In this section, we introduce the main mechanism considered in this paper, the
sample-bid mechanism.

######  Definition 3.1 (sample-bid mechanism).

Given parameter $\alpha$ and sample $s$, the _sample-bid mechanism_ solicits a
non-negative bid $b\geq 0$, charges the agent $\alpha\cdot\min\\{b,s\\}$, and
allocates the item to the agent if $b\geq s$.

In the sample-bid mechanism, the agent reports her bid without knowing the
realization of the sample. From her perspective, the utility $u(v,b,F)$ for
her who has value $v$, reports bid $b$, and competes with sample $s\sim F$ is

$\displaystyle u(v,b,F)=v\cdot\underbrace{F(b)}_{\text{\bf Pr}_{s\sim
F}\\!\left[{s\leq b}\right]}-\underbrace{\alpha b\cdot(1-F(b))}_{\text{payment
when $s\geq
b$}}-\underbrace{\alpha\int_{\small\underline{v}}^{\max\\{b,\small{\underline{v}}\\}}tdF(t)}_{\text{payment
when $s\leq b$}}$

Note that reporting bid equal to zero, the utility of agent is zero. Thus,
sample-bid mechanismis individually rational.

######  Lemma 3.1.

The sample-bid mechanism is individually rational.

On the other hand, reporting bid equal to agent’s value is not the best
response in general. We provide a characterization of agent’s optimal bid as
follows.

######  Lemma 3.2.

In the sample-bid mechanism, given any parameter $\alpha$ and distribution
$F$, the optimal bid $b(v,F)$ for the agent with value $v$ satisfies the
constraint that

$\displaystyle v=\alpha\cdot\frac{1-F(b(v,F))}{f(b(v,F))},$ (1)

or $b(v,F)\in\\{0,\infty\\}$. Ties are broken according to the utility of the
agent.

###### Proof.

The agent’s utility from reporting bid $b$ is

$\displaystyle u(v,b,F)=v\cdot{F(b)}-{\alpha
b(1-F(b))}-{\alpha\int_{\small\underline{v}}^{\max\\{b,\small{\underline{v}}\\}}tdF(t)}$

Consider the first order condition with respect to bid $b$, if the optimal bid
is obtained in the interior, we have

$\displaystyle f(b)\left(v-\alpha\cdot\frac{1-F(b)}{f(b)}\right)=0$

as a necessary condition for the optimality of the bid $b$. Otherwise, the
optimal bid is obtained on the boundary, where $b(v,F)\in\\{0,\infty\\}$. ∎

Note that there might exist multiple bids $b$ that satisfies the constraint
(1) in Lemma 3.2. In that case, the agent chooses the bid which satisfies (1)
and maximizes her utility. Another observation (Lemma 3.3) of the sample-bid
mechanism is that the expected revenue of the seller scales linearly with the
valuation distribution. Since the optimal revenue scales linearly with the
valuation distribution as well, to analyze the prior-independent approximation
ratio of the sample-bid mechanism, we can focus on the valuation distributions
such that the optimal revenue is normalized to 1.

######  Lemma 3.3.

Denote by $r$ the revenue of the sample-bid mechanism with any parameter
$\alpha$ and any valuation distribution $F^{\dagger}$. For any $\rho>0$ and
distribution $F^{\ddagger}$ such that $F^{\ddagger}$ is $F^{\dagger}$ scaled
by $\rho$, i.e., $F^{\dagger}(v)=F^{\ddagger}(\rho v)$ for all $v$, the
revenue of the sample-bid mechanism with parameter $\alpha$ and distribution
$F^{\ddagger}$ is $\rho r$.

###### Proof.

First we show that for any value $v$, the bid of value $v$ given distribution
$F^{\dagger}$ is equivalent to the bid of value $\rho v$ given distribution
$F^{\ddagger}$ scaled by $\rho$. The reason is that
$F^{\dagger}(v)=F^{\ddagger}(\rho v)$ and $f^{\dagger}(v)=\rho
f^{\ddagger}(\rho v)$. Therefore, by Lemma 3.2, the first order condition
implies that the optimal bid satisfies $b(\rho v,F^{\ddagger})=\rho\cdot
b(v,F^{\dagger})$. Moreover, the payment satisfies

$\displaystyle\tilde{p}(\rho b,F^{\ddagger})$ $\displaystyle=\alpha\rho
b\cdot(1-F^{\ddagger}(\rho b))+\alpha\displaystyle\int_{0}^{\rho
b}t\,{\mathrm{d}}F^{\ddagger}(t)$ $\displaystyle=\rho(\alpha
b\cdot(1-F^{\dagger}(b)+\alpha\displaystyle\int_{0}^{b}t\,{\mathrm{d}}F^{\dagger}(t))=\rho\cdot\tilde{p}(b,F^{\dagger}).$

By taking expectation over the valuation, the expected revenue is scaled by
$\rho$ as well. ∎

We finish this section by providing two simple monotonicity properties of the
sample-bid mechanism and defer other more complicated characterizations
required in our analysis to the later sections.

######  Lemma 3.4.

In the sample-bid mechanism, given any parameter $\alpha$ and distribution
$F$, the expected payment for bid $b$ is monotonically non-decreasing in $b$.

###### Proof.

By definition, the expected payment $\tilde{p}(b,F)$ of bid $b$ over the
randomness of the sample $s\sim F$ is

$\displaystyle\tilde{p}(b,F)=\alpha
b\cdot(1-F(b))+\alpha\displaystyle\int_{\underline{v}}^{\max\\{b,\underline{v}\\}}t\,{\mathrm{d}}F(t)$

Taking the derivative with respect to bid $b$, we have

$\displaystyle\frac{\partial\tilde{p}(b,F)}{\partial b}=\alpha(1-F(b))-\alpha
bf(b)+\alpha bf(b)=\alpha(1-F(b))\geq 0.$

which finishes the proof. ∎

######  Lemma 3.5.

In the sample-bid mechanism, given any parameter $\alpha$ and distribution
$F$, the optimal bid $b(v,F)$ is monotonically non-decreasing in value $v$.

###### Proof.

By Myerson [1981], the equilibrium allocation of the agent is non-decreasing
in value $v$. Moreover, given the auction format, the equilibrium allocation
of the agent is increasing in the bid, and thus the optimal bid $b(v,F)$ is
non-decreasing in the value $v$. ∎

##  4 The Sample-bid Mechanism for MHR Distributions

In this section, we analyze the prior-independent approximation ratio of the
sample-bid mechanism over the class of MHR distributions.

######  Definition 4.1.

A distribution $F$ is MHR if the hazard rate $\frac{f(v)}{1-F(v)}$ is monotone
non-decreasing in $v$.

######  Theorem 4.1.

For the sample-bid mechanism with $\alpha=0.824$, the prior-independent
approximation ratio over the class of MHR distributions is between [1.295,
1.296].

The lower bound in Theorem 4.1 is shown in the following example.

######  Example 4.2.

For the sample-bid mechanism with $\alpha=0.824$, let $F$ be the valuation
distribution such that $F(v)=1-e^{-v}$ for $v\in[0,0.43)$ and $F(v)=1$ for
$v\in[0.43,\infty)$. It is easy to verify that $F$ is MHR. Moreover, the
optimal revenue is $0.2797$ while the expected revenue of the sample-bid
mechanism, which equals the expected revenue of posting a price equal to
$0.824$ fraction of the expected welfare, is $0.2159$. Thus, the prior-
independent approximation ratio of the sample-bid mechanism with
$\alpha=0.824$ is at least $1.295$.

Before the proof of the upper bound in Theorem 4.1, we first introduce a
characterization of the agent’s optimal bid when the sample distribution $F$
is MHR; and a technical property for MHR distributions.

######  Lemma 4.2.

In the sample-bid mechanism, given any parameter $\alpha$ and MHR distribution
$F$, the optimal bid $b(v,F)$ for the agent with value $v$ is

$\displaystyle b(v,F)=\left\\{\begin{array}[]{ll}0&\text{if }v<\alpha\text{\bf
E}_{s\sim F}\\!\left[{s}\right],\\\
\infty&\text{otherwise.}\end{array}\right.$

###### Proof.

By the proof of Lemma 3.2, the derivative of the utility given the bid $b$ is

$\displaystyle f(b)\left(v-\alpha\cdot\frac{1-F(b)}{f(b)}\right),$

where the sign of the above expression flips from negative to positive only
once when the bid $b$ increases from $0$ to infinity since $F$ is MHR. Thus
the utility is a quasi-convex function of the bid, which implies that the
maximum utility is attained at extreme points, i.e., bid $0$ or $\infty$. Note
that the utility for bidding $0$ is always 0, while the utility for bidding
$\infty$ is $u(v,\infty,F)=v-\alpha\text{\bf E}_{s\sim F}\\!\left[{s}\right]$.
Hence, the agent bid $\infty$ if and only her value $v$ is at least
$\alpha\text{\bf E}_{s\sim F}\\!\left[{s}\right]$. ∎

######  Lemma 4.3 (Allouah and Besbes, 2019).

For any MHR distribution with any pair of quantile and values
$(v_{1},q_{1}),(v_{2},q_{2})$ such that $q_{1}=q(v_{1})\leq q_{2}=q(v_{2})$
and $v_{1}\geq v_{2}$. Then for any $v\geq v_{2}$, we have $q(v)\geq
q_{2}\cdot e^{\frac{v-v_{2}}{v_{1}-v_{2}}\cdot\ln(\frac{q_{1}}{q_{2}})}$.

######  Lemma 4.4.

The expected value for any MHR distribution with monopoly quantile $q_{m}$ is
$w\geq\frac{q_{m}-1}{q_{m}\cdot\ln q_{m}}$.

###### Proof.

The expected value of the agent is

$\displaystyle\int_{0}^{\infty}q(v)\,{\mathrm{d}}v\geq\int_{0}^{\frac{1}{q_{m}}}e^{vq_{m}\cdot\ln
q_{m}}\,{\mathrm{d}}v=\frac{1}{q_{m}\cdot\ln q_{m}}(e^{\ln
q_{m}}-e^{0})=\frac{q_{m}-1}{q_{m}\cdot\ln q_{m}},$

where the inequality holds by applying Lemma 4.3 with
$q_{1}=q_{m},v_{1}=\frac{1}{q_{m}}$ and $q_{2}=1,v_{2}=0$. ∎

Now, we are ready to show Theorem 4.1.

###### Proof of the upper bound in Theorem 4.1.

Fix any MHR distribution $F$. Let $w\triangleq\text{\bf E}_{v\sim
F}\\!\left[{v}\right]$. Note that by Lemma 4.2, our mechanism is equivalent to
posting price $\alpha w$ to the agent. Next we analyze the approximation ratio
by considering the cases $\alpha w\geq v_{m}$ and $\alpha w<v_{m}$ and
optimize the parameter $\alpha$ such that the approximation ratio of both
cases coincide. Recall that it is without loss of generality to normalize the
expected revenue of the optimal mechanism to 1, i.e., $q_{m}\cdot v_{m}=1$.

First we consider the case when $\alpha w<v_{m}=\nicefrac{{1}}{{q_{m}}}$. By
Lemma 4.4, we have $w\geq\frac{q_{m}-1}{q_{m}\cdot\ln q_{m}}$ and by combining
Lemma 4.3 with $(v_{1},q_{1})=(v_{m},q_{m})$ and $(v_{2},q_{2})=(0,1)$, we
have $q(\alpha w)\geq e^{\alpha(q_{m}-1)}$. Thus, the expected revenue in this
case is

$\alpha w\cdot q(\alpha w)\geq\frac{\alpha(q_{m}-1)}{q_{m}\cdot\ln q_{m}}\cdot
e^{\alpha(q_{m}-1)}.$

Then we consider the case when $\alpha w\geq v_{m}=\nicefrac{{1}}{{q_{m}}}$.
In this case, combining Lemma 4.3 with $(v_{1},q_{1})=(w,q_{w})$ and
$(v_{2},q_{2})=(v_{m},q_{m})$, where $q_{w}\geq\nicefrac{{1}}{{e}}$ is the
quantile of the welfare [see Barlow and Marshall, 1965], for any value $v\geq
v_{m}$, we have $q(\alpha w)\geq q_{m}\cdot e^{\frac{\alpha
w-v_{m}}{w-v_{m}}\cdot\ln(\frac{q_{w}}{q_{m}})}$. Thus the expected revenue is

$\displaystyle\alpha w\cdot q(\alpha w)\geq\alpha w\cdot q_{m}\cdot
e^{\frac{\alpha w-v_{m}}{w-v_{m}}\cdot\ln(\frac{q_{w}}{q_{m}})}\geq\alpha
w\cdot q_{m}\cdot e^{\frac{\alpha
w-\nicefrac{{1}}{{q_{m}}}}{w-\nicefrac{{1}}{{q_{m}}}}\cdot\ln(\frac{1}{e\cdot
q_{m}})}.$

By setting $\alpha=0.824$ and numerically evaluating the above expressions for
all possible values of $w$ and $q_{m}$ with respective to the given
constraints, we have that the expected revenue in both cases are at least
$0.7717$, which guarantees approximation ratio $1.296$. ∎

##  5 The Sample-bid Mechanism for Regular Distributions

In this section, we analyze the prior-independent approximation of the sample-
bid mechanism over the class of regular distributions.

######  Theorem 5.1.

For the sample-bid mechanism with $\alpha=0.7$, the prior-independent
approximation ratio over the class of regular distributions is between
$[1.628,1.835]$.

The lower bound in Theorem 5.1 is shown in the following example.

######  Example 5.1.

For the sample-bid mechanism with $\alpha=0.7$, let $F$ be the valuation
distribution such that $F(v)=\frac{0.265}{v-0.735}$ for $v\in[1,\infty)$. It
is easy to verify that $F$ is regular. Moreover, the optimal revenue is $1$
while the expected revenue of the sample-bid mechanismis $0.614$. Thus, the
prior-independent approximation ratio of the sample-bid mechanism with
$\alpha=0.7$ is at least $1.628$.

In Section 5.1, we introduce some technical characterizations of the sample-
bid mechanism which will be used in the subsequent analysis. In Sections 5.2
and 5.3, we study the prior-independent approximation ratio of the sample-bid
mechanism over the class of regular distributions with monopoly quantile
$q_{m}\geq 0.62$ and $q_{m}\leq 0.62$ respectively. By Lemma 3.3, without loss
of generality, we restrict our attention to the class of regular valuation
distributions where the optimal revenue for the distributions is exactly 1
(i.e., $v_{m}\cdot q_{m}=1$), and then lower-bound the expected revenue of the
sample-bid mechanism with $\alpha=0.7$.

Here we sketch the high-level approach to lower-bound the expected revenue of
the sample-bid mechanism in both regimes (Sections 5.2 and 5.3). Given a
regular distribution $F$, we define a value threshold $v^{*}(F)$ as the
smallest value whose optimal bid is at least monopoly reserve $v_{m}(F)$,
i.e.,

$\displaystyle v^{*}(F)\triangleq\inf\\{v:b(v,F)\geq v_{m}(F)\\}$

Denote $q(v^{*}(F),F)$ by $q^{*}(F)$. By Lemma 3.4 and Lemma 3.5, the expected
revenue $\text{\bf Rev}_{F}({\rm SB})$ of the sample-bid mechanism ${\rm SB}$
for valuation $F$ can be lower-bounded as follows,

$\displaystyle\text{\bf Rev}_{F}({\rm SB})=\int_{0}^{1}p(v(q,F),F)\,dq\geq
p(v^{*}(F),F)\cdot q^{*}(F)+\int_{q^{*}(F)}^{1}p(v(q,F),F)\,dq.$

where $p(v,F)$ is the expected payment of the agent, with value $v$ and
valuation distribution $F$, in the sample-bid mechanism. We then analyze
$p(v^{*}(F),F)$, $q^{*}(F)$, and $p(v(q,F),F)$ for $q\geq q^{*}(F)$ by
providing lower bounds as the functions of $q_{m}(F)$ and other some
parameters of $F$.999Let $R$ be the revenue curve induced by valuation
distribution $F$. In Section 5.2, we lower-bound the expected revenue as a
function of $q_{m}(F)$ and $R(0)$. In Section 5.2, we lower-bound the expected
revenue as a function of $q_{m}(F)$, $q(\nicefrac{{v_{m}(F)}}{{0.7}},F)$ and
$w\triangleq\int_{q(\nicefrac{{v}}{{0.7}},F)}^{q_{m}(F)}\frac{R(q)}{q}\,dq$.
Finally, by numerically evaluating the value of lower bounds for all possible
possible parameters, we conclude that the expected revenue in the sample-bid
mechanism for all regular distribution (with monopoly revenue 1) is at least
0.545, which implies the prior-independent approximation ratio
$\nicefrac{{1}}{{0.545}}\approx 1.835$ of the sample-bid mechanism in Theorem
5.1. The details for discretizations and numerical evaluations can be found in
Appendix A. Note that the bounds for the approximation ratio of the sample-
based pricing mechanisms in Allouah and Besbes [2019] are also obtained by
numerical analysis, which requires solving a relatively more complicated
dynamic program. In contrast, our numerical analysis only requires brute force
enumeration of a few parameters.

As we discussed in Section 2, every valuation distribution $F$ can be
represented by its induced revenue curve $R$ where $R(q)\triangleq
q\,F^{-1}(1-q)$ for all $q\in[0,1]$. In the remaining of the section, all
statements, notations and analysis (except Lemma 5.3) will be presented in the
language of revenue curves instead of valuation distributions.

###  5.1 Technical Properties of the Sample-bid Mechanism

In this subsection, we introduce some technical characterizations of the
sample-bid mechanism which will be used in the later analysis.

To establish a lower bound on the expected revenue of of a truthful mechanism,
a classic approach – revenue curve reduction – [e.g. Alaei, Hartline,
Niazadeh, Pountourakis, and Yuan, 2019, Allouah and Besbes, 2018] is as
follows: (i) start with an arbitrary revenue curve $R_{1}$, (ii) convert it to
another revenue $R_{2}$ with closed-form formula while the optimal revenue
remains the same, (iii) argue that the expected revenue for $R_{2}$ is at most
the expected revenue for $R_{1}$ while the optimal revenue remains the same,
and finally (iv) evaluate the expected revenue for $R_{2}$ for all possible
parameters. In this section, we want to apply a similar approach to the
sample-bid mechanism because it is a non-truthful mechanism. A new technical
difficulty arises in step (iii). When comparing $R_{1}$ and $R_{2}$, for
truthful mechanisms, it is sufficient to study the change in the expected
payment (i.e. $\tilde{p}(b,R_{1})$ and $\tilde{p}(b,R_{2})$) for each bid $b$.
However, for non-truthful mechanisms (e.g. sample-bid mechanism), the optimal
bid of the agent changes when the revenue curve $R_{1}$ is replaced by
$R_{2}$. In Lemma 5.2, we provide a characterization of optimal bid when we
switch from $R_{1}$ to $R_{2}$ in a specific way (illustrated in Figure 1). We
use it as a building block repeatedly in Section 5.2 and Section 5.3.
Intuitively, the following lemma characterizes the phenomenon that increasing
the revenue curve for high values does not affect the agent’s preference for
low bids.

######  Lemma 5.2.

In the sample-bid mechanism, consider any quantile $q^{\dagger}\in[0,1]$ and
any pair of revenue curves $R_{1},R_{2}$ such that $R_{1}(q)\leq R_{2}(q)$ for
any quantile $q\leq q^{\dagger}$ and $R_{1}(q^{\dagger})=R_{2}(q^{\dagger})$.
Letting $b^{\dagger}=\nicefrac{{R_{1}(q^{\dagger})}}{{q^{\dagger}}}$. For any
value $v$ and any bid $b^{\ddagger}\geq b^{\dagger}$, if an agent with value
$v$ and revenue curve $R_{1}$ prefers bid $b^{\dagger}$ than $b^{\ddagger}$,
i.e., $u(v,b^{\dagger},R_{1})\geq u(v,b^{\ddagger},R_{1})$, then an agent with
value $v$ and revenue curve $R_{2}$ also prefers bid $b^{\dagger}$ than
$b^{\ddagger}$, i.e., $u(v,b^{\dagger},R_{2})\geq u(v,b^{\ddagger},R_{2})$.

###### Proof.

By the construction of our mechanism, the utility of an agent who has value
$v$, revenue curve $R$ and bids $b$ is

$\displaystyle u(v,b,R)$ $\displaystyle=v\cdot(1-q(b,R))-\tilde{p}(b,R)$ and
$\displaystyle\tilde{p}(b,v)$ $\displaystyle=\alpha b\cdot
q(b,R)+\alpha\int_{q(b,R)}^{1}\frac{R(q)}{q}dq.$

By the assumption that $R_{1}(q)\leq R_{2}(q)$ for any quantile $q\leq
q^{\dagger}$ and $b^{\ddagger}\geq b^{\dagger}$, we have
$q(b^{\ddagger},R_{1})\leq q(b^{\ddagger},R_{2})\leq q^{\dagger}$. See Figure
1 for a graphical illustration. Thus,

$\displaystyle\tilde{p}(b^{\ddagger},R_{1})-\tilde{p}(b^{\dagger},R_{1})=\alpha\cdot\left(-b^{\dagger}\cdot
q^{\dagger}+\int_{0}^{q^{\dagger}}\min\left\\{\frac{R_{1}(q)}{q},b^{\ddagger}\right\\}\
dq\right)$ $\displaystyle\leq\ $
$\displaystyle\alpha\cdot\left(-b^{\dagger}\cdot
q^{\dagger}+\int_{0}^{q^{\dagger}}\min\left\\{\frac{R_{2}(q)}{q},b^{\ddagger}\right\\}\
dq\right)=\tilde{p}(b^{\ddagger},R_{2})-\tilde{p}(b^{\dagger},R_{2}).$

Thus,

$\displaystyle
u(b^{\dagger},v,R_{1})-u(b^{\ddagger},v,R_{1})=v\cdot(1-q^{\dagger})-\tilde{p}(b^{\dagger},R_{1})-v\cdot(1-q(b^{\ddagger},R_{1}))+\tilde{p}(b^{\ddagger},R_{1})$
$\displaystyle\leq\ $ $\displaystyle
v\cdot(1-q^{\dagger})-\tilde{p}(b^{\dagger},R_{2})-v\cdot(1-q(b^{\ddagger},R_{2}))+\tilde{p}(b^{\ddagger},R_{2})=u(b^{\dagger},v,R_{2})-u(b^{\ddagger},v,R_{2})$

and hence $u(b^{\dagger},v,R_{1})\geq u(b^{\ddagger},v,R_{1})$ implies
$u(b^{\dagger},v,R_{2})\geq u(b^{\ddagger},v,R_{2})$. ∎

$1$$0$$1$$q^{\dagger}$$b^{\dagger}$$b^{\ddagger}$$q(b^{\ddagger},R_{1})$$q(b^{\ddagger},R_{2})$$R_{2}$$R_{1}$
Figure 1: Graphical illustration for Lemma 5.2. The gray dashed thick (resp.
black solid) curve is revenue curve $R_{1}$ (resp. $R_{2}$). The slopes of two
dotted lines from $(0,0)$ are $b^{\ddagger}$ and $b^{\dagger}$ respectively.

######  Lemma 5.3.

In the sample-bid mechanism with any parameter $\alpha\in[0,1]$, for an agent
with concave revenue curve $R$ and value $v$ greater than the monopoly reserve
$v_{m}$, she weakly prefers the bid $\nicefrac{{v}}{{\alpha}}$ than any bid
$b^{\dagger}\in[v_{m},\nicefrac{{v}}{{\alpha}}]$, i.e.,
$u(v,\nicefrac{{v}}{{\alpha}},R)\geq u(v,b^{\dagger},R)$.

###### Proof.

Let $F$ be a regular distribution. By the definition, the utility of the agent
who has value $v$, valuation distribution $F$ and bids $b$ is

$\displaystyle u(v,b,F)$ $\displaystyle=v\cdot F(b)-\tilde{p}(b,F)$ By
considering the first order condition as in Lemma 3.2, we have
$\displaystyle\frac{\partial u(v,b,F)}{\partial b}$
$\displaystyle=f(b)\left(v-\alpha\cdot\frac{1-F(b)}{f(b)}\right).$

Thus, we can compute the difference between $u(v,\nicefrac{{v}}{{\alpha}},F)$
and $u(v,b,F)$ for any value $v\geq v_{m}$ and bid
$b\in[v_{m},\nicefrac{{v}}{{\alpha}}]$ as follows,

$\displaystyle u(v,\nicefrac{{v}}{{\alpha}},F)-u(v,b,F)$
$\displaystyle=\int_{b}^{\frac{v}{\alpha}}\alpha{f(t)}\left(\frac{v}{\alpha}-\frac{1-F(t)}{f(t)}\right)\,dt$
$\displaystyle\geq\int_{b}^{\frac{v}{\alpha}}\alpha{f(t)}\left(t-\frac{1-F(t)}{f(t)}\right)\,dt$
$\displaystyle\geq 0$

where the last inequality uses the fact that $t-\frac{1-F(t)}{f(t)}\geq 0$ for
all $t\geq v_{m}$ if $F$ is regular. ∎

###  5.2 Regular Distributions with Monopoly Quantile $q_{m}\geq 0.62$

In this subsection, we analyze the approximation ratio of the sample-bid
mechanism over the class of regular distributions with monopoly quantile
$q_{m}\geq 0.62$.

######  Lemma 5.4.

For the sample-bid mechanism with $\alpha=0.7$, the approximation ratio over
the class of regular distributions with monopoly quantile $q_{m}\geq 0.62$ is
at most 1.835.

Fix an arbitrary revenue curve $R$, let

$\displaystyle v^{*}(R)\triangleq\inf\\{v:b(v,R)\geq v_{m}(R)\\}$

be the smallest value whose optimal bid $b(v,R)$ for revenue curve $R$ is at
least the monopoly reserve $v_{m}(R)$. Since Lemma 3.5 guarantees that
$b(v,R)$ is weakly non-decreasing in $v$, $v^{*}(R)$ is well-defined,
$b(v,R)\geq v_{m}(R)$ for all $v\geq v^{*}(R)$, and $b(v,R)<v_{m}(R)$ for all
$v<v^{*}(R)$. Denote $q(v^{*}(R),R)$ by $q^{*}(R)$. We decompose the proof of
Lemma 5.4 by considering the following two subregimes – Lemma 5.5 for revenue
curve $R$ with $v^{*}(R)\leq v_{m}(R)$; and Lemma 5.7 for revenue curve $R$
with $v^{*}(R)\geq v_{m}(R)$.

######  Lemma 5.5.

Given any concave revenue curve $R$ such that $q_{m}(R)\geq 0.62$ and
$v^{*}(R)\leq v_{m}(R)$, the revenue of the sample-bid mechanism with
$\alpha=0.7$ is a $1.835$-approximation of the optimal revenue.

###### Proof.

Fix an arbitrary concave revenue curve $R$ satisfying the requirement in the
lemma statement, i.e., $q_{m}(R)\geq 0.62$ and $v^{*}(R)\leq v_{m}(R)$.
Consider an arbitrary value $v\geq v^{*}(R)$. By Lemma 3.5, the optimal bid of
an agent with value $v$ is at least $v_{m}(R)$. Thus, together with Lemma 3.4,
her expected payment in sample-bid mechanism is at least the expected payment
$\tilde{p}(v_{m}(R),R)$ of bidding $v_{m}(R)$, and

$\displaystyle\tilde{p}(v_{m}(R),R)$
$\displaystyle=0.7v_{m}(R)q_{m}(R)+0.7\int_{q_{m}(R)}^{1}\frac{R(q)}{q}\,dq=0.7+0.7\int_{q_{m}(R)}^{1}\frac{R(q)}{q}\,dq$
$\displaystyle\geq
0.7+0.7\int_{q_{m}(R)}^{1}\frac{\frac{1-q}{1-q_{m}(R)}}{q}\,dq=-\frac{0.7\log(q_{m}(R))}{1-q_{m}(R)}~{}.$

where the inequality uses the fact that (1) $R$ is concave, which implies that
$R(q)\geq\frac{1-q}{1-q_{m}(R)}$ for all $q\geq q_{m}(R)$; and (2)
$v_{m}(R)q_{m}(R)$ is normalized to $1$ for the revenue curve $R$. Since
$v^{*}(R)\leq v_{m}(R)$, each value with quantile smaller than $q_{m}(R)$ has
$\tilde{p}(v_{m}(R),R)$ as a lower bound of its payment in the sample-bid
mechanism. Thus, a lower bound of the expected revenue $\text{\bf
Rev}_{R}({\rm SB})$ for revenue curve $R$ in the sample-bid mechanism is

$\displaystyle\text{\bf Rev}_{R}({\rm SB})$
$\displaystyle=\int_{0}^{1}p(v(q,F),F)\,dq\geq p(v^{*}(R),R)\cdot q^{*}(R)$
$\displaystyle\geq\tilde{p}(v_{m}(R),R)\cdot
q_{m}(R)\geq-\frac{0.7\log(q_{m}(R))q_{m}(R)}{1-q_{m}(R)}$

which is at least 0.545 for all $q_{m}(R)\geq 0.62$. This finishes the proof,
since we (without loss of generality) consider revenue curve $R$ with optimal
revenue equal to $1$, i.e., $v_{m}(R)\cdot q_{m}(R)=1$. ∎

Before diving into the subregime where $v^{*}(R)\geq v_{m}(R)$, we provide a
characterization (Lemma 5.6) of the optimal bid for concave revenue curves
with monopoly quantile greater than $0.62$. Specifically, Lemma 5.6 guarantees
that $b(v,R)=0$ for all value $v<v^{*}(R)$.

$1$$0$$1$$q_{m}(R_{1})$$v_{m}(R_{1})$$b^{\dagger}$$q^{\dagger}$$\hat{q}$$R_{1}$$R_{2}$
Figure 2:  Graphical illustration for Lemma 5.6. The gray dashed (resp. black
solid) curve is revenue curve $R_{1}$ (resp. $R_{2}$). The slopes of two
dotted lines from (0, 0) are $v_{m}(R_{1})$ and $b^{\dagger}$ respectively.

######  Lemma 5.6.

In the sample-bid mechanism with parameter $\alpha=0.7$, given any value $v$
and any concave revenue curve $R$ with $q_{m}(R)\geq 0.62$, the optimal bid
$b(v,R)$ for an agent with value $v$ and revenue curve $R$ satisfies
$b(v,R)\in\\{0\\}\cup[v_{m}(R),\infty).$

###### Proof.

We prove the lemma by contradiction. See Figure 2 for a graphical description
of the following construction. Suppose there exists an agent who has value
$v$, revenue curve $R_{1}$ s.t. $q_{m}(R_{1})\geq 0.62$ and strictly prefers a
bid of $b^{\dagger}\in(0,v_{m}(R_{1}))$ over all other bids. Denote
$q(b^{\dagger},R_{1})$ by $q^{\dagger}$. Let $\hat{q}\triangleq
1-\frac{1-q^{\dagger}}{R_{1}(q^{\dagger})}$. Now consider another revenue
curve $R_{2}$ defined as follows,

$\displaystyle
R_{2}(q)\triangleq\left\\{\begin{array}[]{ll}1&q\in[0,\hat{q}]~{},\\\
\frac{1-q}{1-\hat{q}}&q\in[\hat{q},1]~{}.\end{array}\right.$

By construction, $R_{2}$ is a concave revenue curve s.t. (i) $\hat{q}\geq
0.62$; (ii) $b^{\dagger}\leq\nicefrac{{1}}{{\hat{q}}}$; (iii) $R_{1}(q)\leq
R_{2}(q)$ for all $q\in[0,q^{\dagger}]$; and (iv) $R_{1}(q)\geq R_{2}(q)$ for
all $q\in[q^{\dagger},1]$.

Applying Lemma 5.2 on $R_{1},R_{2},q^{\dagger},v$ and all $b^{\ddagger}\geq
b^{\dagger}$, we conclude that the optimal bid for an agent with value $v$ and
revenue curve $R_{2}$ is in $[0,b^{\dagger}]$. Furthermore, note that
$u(v,b^{\dagger},R_{2})\geq u(v,b^{\dagger},R_{1})>0$ where the first
inequality holds by the construction of $R_{2}$,101010The allocation of
bidding $b^{\dagger}$ is the same for both revenue curves, while the payment
of bidding $b^{\dagger}$ is higher for revenue curve $R_{1}$. and the second
inequality holds by our assumption that $b^{\dagger}$ is strictly preferred
for $R_{1}$. Hence, there exists an optimal bid in $(0,b^{\dagger}]$ that is
strictly preferred to biding zero and weakly preferred to all other bids for
$R_{2}$. Next we argue that this leads to a contradiction by considering
$v\leq\nicefrac{{1}}{{\hat{q}}}$ and $v\geq\nicefrac{{1}}{{\hat{q}}}$
separately.

Case (i) $v\leq\nicefrac{{1}}{{\hat{q}}}$: Note that for any bid
$b\in[0,\nicefrac{{1}}{{\hat{q}}}]$, the utility $u(v,b,R_{2})$ has a closed-
form expression as follows,

$\displaystyle u(v,b,R_{2})$
$\displaystyle=v\frac{b(1-\hat{q})}{b(1-\hat{q})+1}+0.7\log\left(\frac{1}{b(1-\hat{q})+1}\right).$

Considering the first order condition of $u(v,b,R_{2})$ with respect to bid
$b$, after basic simplification, we have

$\displaystyle b=\frac{v}{0.7}-\frac{1}{1-\hat{q}}.$

This leads to a contradiction since for all $\hat{q}\in[0.62,1]$111111Note
that $q_{m}\geq 0.62$ implies that $\hat{q}\geq 0.62$. and
$v\in[0,\nicefrac{{1}}{{\hat{q}}}]$, we have
$\frac{v}{0.7}-\frac{1}{1-\hat{q}}<0$, i.e., bidding 0 is weakly preferred
than any bid $b\in(0,b^{\dagger})$.

Case (ii) $v\geq\nicefrac{{1}}{{\hat{q}}}$: Let
$b^{\ddagger}\triangleq\nicefrac{{v}}{{0.7}}$, and $q^{\ddagger}\triangleq
q(b^{\ddagger},R_{2})=\nicefrac{{0.7}}{{v}}$. Since
$v\geq\nicefrac{{1}}{{\hat{q}}}$, the construction of $R_{2}$ guarantees that
$b^{\ddagger}\cdot q^{\ddagger}=1=R_{2}(q^{\ddagger})$. Note that the utility
$u(v,b^{\ddagger},R_{2})$ has a closed-form expression as follows,

$\displaystyle u(v,b^{\ddagger},R_{2})$
$\displaystyle=v-2vq^{\ddagger}+0.7(1-\hat{q})+0.7\log(\hat{q})$
$\displaystyle\qquad-0.7(\hat{q}-q^{\ddagger})(1-b^{\ddagger}q^{\ddagger})\left(\hat{q}-q^{\ddagger}-q^{\ddagger}\log(\hat{q})+q^{\ddagger}\log(q^{\ddagger})\right).$

This leads to a contradiction since for all $\hat{q}\in[0.62,1]$,
$v\in[\nicefrac{{1}}{{\hat{q}}},\infty)$, and
$\left(\frac{v}{0.7}-\frac{1}{1-\hat{q}}\right)\in[0,\nicefrac{{1}}{{\hat{q}}}]$,
we have $u(v,b^{\ddagger},R_{2})\geq
u\left(v,\frac{v}{0.7}-\frac{1}{1-\hat{q}},R_{2}\right)$,121212By first order
condition, for revenue curve $R_{2}$, if
$\left(\frac{v}{0.7}-\frac{1}{1-\hat{q}}\right)>\nicefrac{{1}}{{\hat{q}}}$,
then bidding $b^{\ddagger}$ already achieves higher utility for the agent
compared to bidding below $b^{\ddagger}$. Thus it is sufficient to compare
$b^{\ddagger}$ with $\left(\frac{v}{0.7}-\frac{1}{1-\hat{q}}\right)$ in the
case that the latter is in $[0,\nicefrac{{1}}{{\hat{q}}}]$. i.e., bidding 0 or
$\nicefrac{{v}}{{0.7}}$ is weakly preferred than any bid
$b\in(0,b^{\dagger})$. ∎

Now, we provide the approximation guarantee for revenue curve $R$ with
$v^{*}(R)\geq v_{m}(R)$.

$1$$0$$1$$q_{m}$ (a)  The gray dashed (resp. black solid) curve is the revenue
curve $R_{1}$ (resp. $R_{2}$). By construction, $q_{m}(R_{1})=q_{m}(R_{2})$.

$1$$0$$1$$v^{*}(R_{2}^{(i)})$$v^{*}(R_{2}^{(i+1)})$ (b) The gray dashed (resp.
black solid) curve is revenue curve $R_{2}^{(i)}$ (resp. $R_{2}^{(i+1)}$). The
slopes of two dotted lines from (0, 0) are $v^{*}(R_{2}^{(i+1)})$ and
$v^{*}(R_{2}^{(i)})$ respectively. By construction, $v^{*}(R_{2}^{(i+1)})\geq
v^{*}(R_{2}^{(i)})$.

$1$$0$$1$$v^{*}(R_{3})$ (c) The gray dashed (resp. black solid) curve is
revenue curve $R_{2}$ (resp. $R_{3}$). The slope of the dotted line from (0,
0) is $v^{*}(R_{3})$.

$1$$\bar{r}_{0}$$\underline{r}_{0}$$0$$1$$b^{\ddagger}$$q^{\ddagger}$ (d) The
gray dashed (resp. black solid, black dashed) curve is revenue curve $R_{3}$
(resp. $R_{4}^{(\bar{r}_{0})}$, $R_{4}^{(\underline{r}_{0})}$). The slope of
the dotted line from (0, 0) is $b^{\ddagger}$, i.e., the optimal bid for an
agent with value $v^{*}(R_{3})$ and revenue curve $R_{3}$. By construction,
$v^{*}(R_{4}^{(\underline{r}_{0})})\leq v^{*}(R_{3}))\leq
v^{*}(R_{4}^{(\bar{r}_{0})})$.

$1$$\underline{r}_{0}$$0$$1$$b^{\ddagger}$$b^{\dagger}$$v^{*}$ (e)  The gray
dashed (resp. black solid, black dashed) curve is revenue curve $R_{3}$ (resp.
$R_{4}$, $R_{4}^{(\underline{r}_{0})}$). By construction,
$v^{*}(R_{3})=v^{*}(R_{4})~{}(\triangleq v^{*})$. The slope of three dotted
lines from (0, 0) are $b^{\ddagger}$, $b^{\dagger}$ and $v^{*}$, where
$b^{\ddagger}$ (resp. $b^{\dagger}$) is the optimal bid for an agent with
value $v^{*}$ and revenue curve $R_{3}$ (resp. $R_{4}$). By Lemma 3.2,
$b^{\dagger}\leq b^{\ddagger}$.

Figure 3:  Graphical illustration for Lemma 5.7.

######  Lemma 5.7.

Given any concave revenue curve $R$ such that $q_{m}(R)\geq 0.62$ and
$v^{*}(R)\geq v_{m}(R)$, the revenue of the sample-bid mechanism with
$\alpha=0.7$ is a $1.835$-approximation of the optimal revenue.

###### Proof.

The proof is done in four major steps:

#### Step 1- flattening the revenue curve for all quantile $q\geq
q_{m}(R_{1})$

Fix an arbitrary revenue curve $R_{1}$ satisfying the requirements in the
lemma statement, i.e., $q_{m}(R)\geq 0.62$ and $v^{*}(R)\geq v_{m}(R)$.
Consider another revenue curve $R_{2}$ defined as follows (see Figure 3a for a
graphical illustration)

$\displaystyle
R_{2}(q)\triangleq\left\\{\begin{array}[]{ll}R_{1}(q)&q\in[0,q_{m}(R_{1})]~{},\\\
1&q\in[q_{m}(R_{1}),1]~{}.\end{array}\right.$

We claim that the expected revenue of the sample-bid mechanism with
$\alpha=0.7$ for revenue curve $R_{2}$ is at most that of revenue curve
$R_{1}$. To see this, consider the virtual surplus for both revenue curves. By
our assumption that $v^{*}(R_{1})\geq v_{m}(R_{1})$, every quantile
$q>q_{m}(R_{1})$ has negative virtual value $R_{1}^{\prime}(q)$ in $R_{1}$,
bids zero (Lemma 5.6) and gains zero virtual surplus while their virtual value
$R_{2}^{\prime}(q)$ becomes zero in $R_{2}$ and thus gains zero virtual
surplus as well. On the other side, every quantile $q\leq q_{m}(R_{1})$ has
identical virtual value by construction. We claim that the allocation for each
of these quantiles weakly decreases. To see this, note that the allocation of
bidding any bid $b\geq v_{m}(R_{1})=v_{m}(R_{2})$ is the same for both revenue
curves $R_{1}$ and $R_{2}$, and the expected payment increases by a constant
when the revenue curve $R_{1}$ is replace by $R_{2}$. Thus the agent’s
preference among all bids $b\geq v_{m}(R_{1})$ is the same in both revenue
curves $R_{1}$ and $R_{2}$. However, the utility of bidding $b\geq
v_{m}(R_{2})$ is lower when the revenue curve is $R_{2}$, which implies that
there may exist value $v$ such that the agent may prefer bidding $0$ to
bidding above the monopoly reserve in $R_{2}$, while strictly prefer bidding
above the monopoly reserve in $R_{1}$. By Lemma 5.6, the optimal bid for any
value $v$ is not in $(0,v_{m}(R_{2}))$. Thus, we conclude that
$q^{*}(R_{2})\leq q^{*}(R_{1})$ and (1) the optimal bid (as well as the
allocation) for every quantile $q\leq q^{*}(R_{2})$ in both $R_{1}$ and
$R_{2}$ remains the same; and (2) for every quantile
$q\in[q^{*}(R_{2}),q^{*}(R_{1}))$, the optimal bid quantile $q$ is $0$ when
the revenue curve is $R_{2}$. This guarantees that the virtual surplus for
every quantile $q\leq q_{m}(R_{1})$ weakly decreases since the virtual value
is non-negative while the allocation decreases. Note that in sample-bid
mechanism, the payment for lowest type is always 0, i.e., $p(0)=0$. By Theorem
2.2, the expected revenue (a.k.a. virtual surplus) for $R_{2}$ is at most the
expected revenue (a.k.a. virtual surplus) for $R_{1}$.

#### Step 2- flattening the revenue curve for all quantiles $q\geq q^{*}$

In this step, we start with revenue curve $R_{2}$ constructed in step 1, and
consider a sequence of revenue curves $R_{2}^{(0)},R_{2}^{(1)},\dots$ where
$R_{2}^{(0)}\triangleq R_{2}$ and $R_{2}^{(i+1)}$ is recursively defined on
$R_{2}^{(i)}$ as follows,

$\displaystyle
R_{2}^{(i+1)}(q)\triangleq\left\\{\begin{array}[]{ll}\vspace{5pt}R_{2}^{(i)}(q)&q\in\left[0,q^{*}(R_{2}^{(i)})\right]~{},\\\
\vspace{5pt}R_{2}^{(i)\prime}(q^{*}(R_{2}^{(i)}))\cdot(q-q^{*}(R_{2}^{(i)}))+R_{2}^{(i)}(q^{*}(R_{2}^{(i)}))&q\in\left[q^{*}(R_{2}^{(i)}),\frac{1-R_{2}^{(i)}(q^{*}(R_{2}^{(i)}))}{R_{2}^{(i)\prime}(q^{*}(R_{2}^{(i)}))}+q^{*}(R_{2}^{(i)})\right]~{},\\\
1&q\in\left[\frac{1-R_{2}^{(i)}(q^{*}(R_{2}^{(i)}))}{R_{2}^{(i)\prime}(q^{*}(R_{2}^{(i)}))}+q^{*}(R_{2}^{(i)}),1\right]~{}.\end{array}\right.$

where $R_{2}^{(i)\prime}(q^{*}(R_{2}^{(i)}))$ is the right-hand derivative of
$R_{2}^{(i)}(q)$ at $q=q^{*}(R_{2}^{(i)})$. See Figure 3b for a graphical
illustration. Invoking Lemma 5.3 and Lemma 5.6, with the same argument for
values with positive virtual values in step 1, we can conclude that
$q^{*}(R_{2}^{(i)})$ and the expected revenue for $R_{2}^{(i)}$ in the sample-
bid mechanism is weakly decreasing in $i$.

Note that by construction, the sequence of revenue curves
$R_{2}^{(0)},R_{2}^{(1)},\dots$ converges to a revenue curve $R_{3}$ whose
expected revenue in the sample-bid mechanism is at most the revenue for
$R_{2}$, and satisfying the following characterization,

$\displaystyle
R_{3}(q)\triangleq\left\\{\begin{array}[]{ll}\vspace{5pt}R_{2}(q)&q\in\left[0,q^{*}(R_{3})\right]~{},\\\
\vspace{5pt}R_{2}^{\prime}(q^{*}(R_{3}))\cdot(q-q^{*}(R_{3}))+R_{2}(q^{*}(R_{3}))&q\in\left[q^{*}(R_{3}),\frac{1-R_{2}(q^{*}(R_{3}))}{R_{2}^{\prime}(q^{*}(R_{3}))}+q^{*}(R_{3})\right]~{},\\\
1&q\in\left[\frac{1-R_{2}(q^{*}(R_{3}))}{R_{2}^{\prime}(q^{*}(R_{3}))}+q^{*}(R_{3}),1\right]~{}.\end{array}\right.$

See Figure 3c for a graphical illustration.

#### Step 3- flattening the revenue curve for all quantile $q\leq
q_{m}(R_{3})$

For any revenue curve $R$, let $p(v^{*}(R),R)$ be the expected payment in the
sample-bid mechanism of an agent with value $v^{*}(R)$ and revenue curve $R$.
Due to Lemma 3.4 and Lemma 3.5, $p(v^{*}(R),R)\cdot q^{*}(R)$ is a valid lower
bound of the expected revenue in the sample-bid mechanism for an agent with
revenue curve $R$. In this step, instead of analyzing the expected revenue, we
argue that we can convert any revenue curve $R_{3}$ (constructed in step 2)
into another revenue curve $R_{4}$, such that (i)
$v^{*}(R_{4})=v^{*}(R_{3})~{}(\triangleq v^{*})$; (ii) $q^{*}(R_{4})\leq
q^{*}(R_{3})$; and (iii) $p(v^{*},R_{4})\leq p(v^{*},R_{3})$. Finally, by
showing that $p(v^{*}(R_{4}),R_{4})\cdot q^{*}(R_{4})\geq 0.545$, we finish
the proof of the lemma.

Given the revenue curve $R_{3}$ constructed in step 2, for any
$r_{0}\in[0,1]$, we define a revenue curve $R_{4}^{(r_{0})}$ as follows,

$\displaystyle
R_{4}^{(r_{0})}\triangleq\left\\{\begin{array}[]{ll}r_{0}+(1-r_{0})\frac{q}{q_{m}(R_{3})}&q\in\left[0,q_{m}(R_{3})\right]~{},\\\
1&q\in\left[q_{m}(R_{3}),1\right]~{}.\end{array}\right.$

See the black curves in Figure 3d as an example. We claim that there exists
$r_{0}^{*}\in[0,1]$ s.t. $R_{4}^{(r0)}~{}(\triangleq R_{4})$ satisfies
properties (i) (ii) (iii) mentioned above. To see this, consider the argument
as follows.

By construction, for all every value $v$, every bid $b$, the utility
$u(v,b,R_{4}^{(r_{0})})$ is decreasing continuously in $r_{0}$. Thus,
$v^{*}(R_{4}^{(r_{0})})$ is decreasing continuously in $r_{0}$. Let
$b^{\ddagger}$ be the optimal bid of an agent with value $v^{*}(R_{3})$ and
revenue curve $R_{3}$. Denote $q(b^{\ddagger},R_{3})$ by $q^{\ddagger}$.
Consider revenue curve $R_{4}^{(\underline{r}_{0})}$ where
$\underline{r}_{0}\triangleq
1-\frac{q_{m}(R_{3})}{q_{m}(R_{3})-q^{\ddagger}}(1-R_{3}(q^{\ddagger}))$. By
construction, $R_{4}^{(\underline{r}_{0})}(q)\geq R_{3}(q)$ for all $q\leq
q^{\ddagger}$, and $R_{4}^{(\underline{r}_{0})}(q)\leq R_{3}(q)$ for all
$q\geq q^{\ddagger}$. See Figure 3d for a graphical illustration. Note that by
construction,

$\displaystyle u(v^{*}(R_{3}),b^{\ddagger},R_{4}^{(\underline{r}_{0})})$
$\displaystyle=v^{*}(R_{3})\cdot(1-q^{\ddagger})-\alpha b^{\ddagger}\cdot
q^{\ddagger}-\alpha\int_{q^{\ddagger}}^{1}\frac{R_{4}^{(\underline{r}_{0})}(q)}{q}~{}dq$
$\displaystyle\geq v^{*}(R_{3})\cdot(1-q^{\ddagger})-\alpha b^{\ddagger}\cdot
q^{\ddagger}-\alpha\int_{q^{\ddagger}}^{1}\frac{R_{3}(q)}{q}~{}dq=u(v^{*}(R_{3}),b^{\ddagger},R_{3})=0$

Thus, $v^{*}(R_{4}^{(\underline{r}_{0})})\leq v^{*}(R_{3})$. Next, consider
revenue curve $R_{4}^{(\bar{r}_{0})}$ where $\bar{r}_{0}\triangleq
1-\frac{q_{m}(R_{3})}{q_{m}(R_{3})-q^{*}(R_{3})}(1-R_{3}(q^{*}(R_{3}))$. By
construction, $R_{4}^{(\bar{r}_{0})}(q)\geq R_{3}(q)$ for all $q\in[0,1]$. See
Figure 3d for a graphical illustration. Thus,
$v^{*}(R_{4}^{(\bar{r}_{0})})\geq v^{*}(R_{3})$ with the similar argument for
$R_{4}^{(\underline{r}_{0})}$ Therefore, we know that there exists
$r_{0}^{*}\in[\underline{r}_{0},\bar{r}_{0}]$ such that
$v^{*}(R_{4}^{(r_{0}^{*})})=v^{*}(R_{3})$. We denote $R_{4}^{(r_{0}^{*})}$ by
$R_{4}$ and show that $R_{4}$ satisfies properties (ii) $q^{*}(R_{4})\leq
q^{*}(R_{3})$ and (iii) $p(v^{*},R_{4})\leq p(v^{*},R_{3})$ with the argument
below.

Lemma 5.3 implies that $b^{\ddagger}>v^{*}(R_{3})$. Combining with the fact
that $r_{0}^{*}\geq\underline{r}_{0}$, we know that property (ii)
$q^{*}(R_{4})\leq q^{*}(R_{3})$ is satisfied. See Figure 3e for a graphical
illustration.

Combining the first order condition in Lemma 3.2 and construction of $R_{4}$,
it is guaranteed that the optimal bid $b^{\dagger}$ of value $v^{*}$ for
revenue curve $R_{4}$ is at most $b^{\ddagger}$. Furthermore,
$q(b^{\dagger},R_{4})\geq q(b^{\ddagger},R_{4})\geq
q(b^{\ddagger},R_{3})=q^{\ddagger}$ by construction. By the definition, the
optimal utility of value $v^{*}(R)$ for any revenue curve $R$ is zero. Thus,
$p(v^{*},R_{3})=v^{*}\cdot(1-q^{\ddagger})\geq
v^{*}\cdot(1-q(b^{\dagger},R_{4}))=p(v^{*},R_{4})$.

#### Step 4- lower-bounding the expected revenue on $R_{4}$

So far, we have shown that for an arbitrary revenue curve satisfying the
assumptions in lemma statement, its expected revenue in the sample-bid
mechanism is lower-bounded by $p(v^{*}(R_{4}),R_{4})\cdot q^{*}(R_{4})$ for
$R_{4}$ pinned down by some $(r_{0},q_{m})$ as follows,

$\displaystyle
R_{4}\triangleq\left\\{\begin{array}[]{ll}r_{0}+(1-r_{0})\frac{q}{q_{m}}&q\in\left[0,q_{m}\right]~{},\\\
1&q\in\left[q_{m},1\right]~{}.\end{array}\right.$

By numerically verifying $p(v^{*}(R_{4}),R_{4})\cdot q^{*}(R_{4})\geq 0.545$
for all $(r_{0},q_{m})\in[0,1]^{2}$, we finish the proof. The details of this
numerical evaluation is elaborated on in Appendix A. ∎

###  5.3 Regular Distributions with Monopoly Quantile $q_{m}\leq 0.62$

In this subsection, we analyze the prior-independent approximation ratio of
the sample-bid mechanism over the class of regular distributions with monopoly
quantile $q_{m}\leq 0.62$.

######  Lemma 5.8.

For the sample-bid mechanism with $\alpha=0.7$, the prior-independent
approximation ratio over the class of regular distributions with monopoly
quantile $q_{m}\leq 0.62$ is at most $1.835$.

Fix an arbitrary revenue curve $R$, let

$\displaystyle v^{*}(R)\triangleq\inf\\{v:b(v,R)\geq v_{m}(R)\\}$

be the smallest value whose optimal bid $b(v,R)$ for revenue curve $R$ is at
least $v_{m}(R)$. Since Lemma 3.5 guarantees that $b(v,R)$ is weakly non-
decreasing in $v$, $v^{*}(R)$ is well-defined, $b(v,R)\geq v_{m}(R)$ for all
$v\geq v^{*}(R)$. Furthermore, by Lemma 5.3, we know that
$b(v,R)\geq\nicefrac{{v_{m}(R)}}{{0.7}}$ for all
$v\geq\max\\{v^{*}(R),v_{m}(R)\\}$. Denote $q(v^{*}(R),R)$ by $q^{*}(R)$. By
Lemma 3.4 and Lemma 3.5, the expected revenue $\text{\bf Rev}_{R}({\rm SB})$
of the sample-bid mechanism for revenue curve $R$ can be lower-bounded as
follows,

$\displaystyle\text{\bf Rev}_{R}({\rm SB})=$
$\displaystyle\int_{0}^{1}p(v(q,R),R)\,dq$ $\displaystyle=$
$\displaystyle\int_{0}^{\min\\{q^{*}(R),q_{m}(R)\\}}p(v(q,R),R)\,dq+\int_{\min\\{q^{*}(R),q_{m}(R)\\}}^{q^{*}(R)}p(v(q,R),R)\,dq$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\int_{q^{*}(R)}^{1}p(v(q,R),R)\,dq$
$\displaystyle\geq$
$\displaystyle~{}\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)\cdot\min\\{q^{*}(R),q_{m}(R)\\}+\tilde{p}(v_{m}(R),R)\cdot\max\\{0,q^{*}(R)-q_{m}(R)\\}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\int_{q^{*}(R)}^{1}p(v(q,R),R)\,dq.$

Denote $q(\nicefrac{{v_{m}(R)}}{{0.7}},R)$ by $q^{\ddagger}(R)$, and
$\int_{q^{\ddagger}(R)}^{q_{m}(R)}\frac{R(q)}{q}~{}dq$ by $w(R)$. In Lemma
5.9, we lower-bound the expected payment
$\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)$ and $\tilde{p}(v_{m}(R),R)$ as the
function of $q_{m}(R)$, $q^{\ddagger}(R)$, $w(R)$ and $v^{*}(R)$. In Lemma
5.10, we lower-bound $q^{*}(R)$ as the function of $q_{m}(R)$,
$q^{\ddagger}(R)$ and $v^{*}(R)$. In Lemma 5.11, we upper-bound of $v^{*}(R)$
as the function of $q_{m}(R)$, $q^{\ddagger}(R)$ and $w(R)$. In Lemma 5.12, we
lower-bound $p(v(q,R),R)$ as a function of $q_{m}(R)$ for all quantile
$q\in[q_{m}(R),1]$. Putting all pieces together, we show Lemma 5.8 by
providing a lower bound of expected revenue in the sample-bid mechanism as a
function of $q_{m}(R)$, $q^{\ddagger}(R)$ and $w(R)$, and numerically
evaluating its value for all possible parameters. The details of the numerical
evaluations in this section are similar to those of Lemma 5.7, which are
elaborated on in Appendix A.

$1$$0$$1$$q_{m}$$q$$\frac{1-q}{1-q_{m}}$ Figure 4:  Graphical illustration for
Lemma 5.9. The gray dashed (resp. black solid) curve is revenue curve $R$
(resp. lower bound of $R$).

######  Lemma 5.9.

For the sample-bid mechanism with $\alpha=0.7$, given any concave revenue
curve $R$, the expected payment $\tilde{p}(b,R)$ of bidding $b\in[0,v_{m}(R)]$
is at least

$\tilde{p}(b,R)\geq\frac{0.7\log(b\cdot(1-q_{m}(R))+1)}{1-q_{m}(R)};$

and the expected payment $\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)$ of
bidding $\nicefrac{{v_{m}(R)}}{{0.7}}$ is at least

$\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)\geq\left(\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)-\frac{0.7\log(q_{m}(R)))}{1-q_{m}(R)}\right).$

###### Proof.

By definition, for any $b\in[0,v_{m}(R)]$,

$\displaystyle\tilde{p}(b,R)$ $\displaystyle=0.7b\cdot
q(b,R)+0.7\int_{q(b,R)}^{1}\frac{R(q)}{q}\,dq$ $\displaystyle\geq 0.7b\cdot
q(b,R)+0.7\int_{q(b,R)}^{1}\frac{\frac{1-q}{1-q_{m}(R)}}{q}\,dq$
$\displaystyle=0.7b\cdot
q(b,R)-0.7\frac{1-q(b,R)}{1-q_{m}(R)}-\frac{0.7\log(q(b,R))}{1-q_{m}(R)}$
$\displaystyle\geq\frac{0.7\log(b\cdot(1-q_{m}(R))+1)}{1-q_{m}(R)}$

where the first inequality uses the fact that $R(q)\geq\frac{1-q}{1-q_{m}(R)}$
for all $q\geq q_{m}(R)$ from the regularity of $R$, and the second inequality
use the fact that $b\cdot q(b,R)\geq\frac{1-q(b,R)}{1-q_{m}(R)}$, and
$q(b,R)\leq(b\cdot(1-q_{m}(R))+1)^{-1}$ from the regularity of $R$. See Figure
4 for a graphical illustration.

Similarly,

$\displaystyle\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)$
$\displaystyle=0.7\frac{v_{m}(R)}{0.7}q^{\ddagger}(R)+0.7\int_{q^{\ddagger}(R)}^{1}\frac{R(q)}{q}\,dq$
$\displaystyle=\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)+0.7\int_{q_{m}(R)}^{1}\frac{R(q)}{q}\,dq$
$\displaystyle\geq\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)-\frac{0.7\log(q_{m}(R))}{1-q_{m}(R)}~{}.\qed$

$1$$\nicefrac{{v_{m}}}{{0.7}}$$0$$1$$q_{m}$$q^{\ddagger}$ Figure 5:  Graphical
illustration for Lemma 5.10. The gray dashed (resp. black solid) curve is
revenue curve $R_{1}$ (resp. $R_{2}$). The slope of the dotted line from (0,
0) is $\nicefrac{{v_{m}(R_{1})}}{{0.7}}$.

######  Lemma 5.10.

For any concave revenue curve $R$, the quantile $q(v,R)$ for value $v\leq
v_{m}(R)$ is at least

$q(v,R)\geq\frac{1}{1+v\cdot(1-q_{m}(R))};$

and the quantile $q(v,R)$ for value
$v\in[v_{m}(R),\nicefrac{{v_{m}(R)}}{{0.7}}]$ is at least

$q(v,R)\geq\frac{2q_{m}(R)-q^{\ddagger}(R)\cdot(1+\nicefrac{{1}}{{0.7}})}{1+v\cdot(1-q_{m}(R))}.$

###### Proof.

Given any concave revenue curve $R_{1}$, consider another revenue curve
$R_{2}$ defined as follows,

$\displaystyle
R_{2}(q)\triangleq\left\\{\begin{array}[]{ll}R_{1}(q)&q\in[0,q^{\ddagger}(R_{1})]~{},\\\
R_{1}(q^{\ddagger}(R_{1}))+\frac{q-q^{\ddagger}(R_{1})}{q_{m}(R_{1})-q^{\ddagger}(R_{1})}(1-R_{1}(q^{\ddagger}(R_{1})))&q\in[q^{\ddagger}(R_{1}),q_{m}(R_{1})]~{},\\\
\frac{1-q}{1-q_{m}(R_{1})}&q\in[q_{m}(R_{1}),1]~{}.\end{array}\right.$

Since $R_{1}$ is regular, we have $R_{2}(q)\leq R_{1}(q)$ for all $q\in[0,1]$
by construction. See Figure 5 for graphical illustration. Thus, for any value
$v\leq v_{m}{R_{1}}$, we have

$q(v,R_{1})\geq q(v,R_{2})=\frac{1}{1+v\cdot(1-q_{m}(R_{1}))}.$

Moreover, for any value $v\in[v_{m}(R_{1}),\nicefrac{{v_{m}(R_{1})}}{{0.7}}]$,
we have

$q(v,R_{1})\geq
q(v,R_{2})=\frac{2q_{m}(R_{1})-q_{1}(R_{1})\cdot(1+\nicefrac{{1}}{{0.7}})}{1+v\cdot(1-q_{m}(R_{1}))}.\qed$

$1$$0$$1$$\hat{q}$$q_{m}$$q^{\dagger}$$b^{\dagger}$ Figure 6:  Graphical
illustration for Lemma 5.11. The gray dashed (resp. black solid) curve is
revenue curve $R_{1}$ (resp. $R_{2}$). The slope of the dotted line from (0,
0) is $b^{\dagger}$.

######  Lemma 5.11.

In the sample-bid mechanism with parameter $\alpha=0.7$, given any value $v$
and any concave revenue curve $R$, the optimal bid $b(v,R)$ for an agent with
value $v$ and revenue curve $R$ is at least $v_{m}(R)$ if for all
$\hat{q}\in[q_{m}(R),1]$,

$\displaystyle\begin{split}v\cdot(1-q^{\ddagger}(R))-v_{m}(R)\cdot
q^{\ddagger}(R)-0.7\left(w(R)+\log\left(\frac{\hat{q}}{q_{m}(R)}\right)\right.&\left.-\frac{\ln(\hat{q})}{1-\hat{q}}\right)\\\
&\geq v(1-\tilde{q})+\frac{0.7\log(\tilde{q})}{1-\hat{q}}\end{split}$ (2)

where
$\tilde{q}\triangleq\left({1+\min\\{\nicefrac{{1}}{{\hat{q}}},\max\\{0,\frac{v}{0.7}-\frac{1}{1-\hat{q}}\\}\\}\cdot(1-\hat{q})}\right)^{-1}$.

###### Proof.

Fix an arbitrary concave revenue curve $R$. We show that inequality (2) in the
lemma statement is a sufficient condition that bidding
$\nicefrac{{v_{m}(R)}}{{0.7}}$ is weakly preferred than bidding any bids in
$[0,v_{m}(R)]$. The argument is similar to Lemma 5.6.

We prove by contradiction, suppose there exists an revenue curve $R_{1}$, and
value $v$ such that inequality (2) in the lemma statement is satisfied but the
optimal bid of an agent with value $v$ and revenue curve $R_{1}$ is
$b^{\dagger}\in[0,v_{m}(R_{1}))$. Denote $q(b^{\dagger},R_{1})$ by
$q^{\dagger}$. Let $\hat{q}\triangleq
1-\frac{1-q^{\dagger}}{R_{1}(q^{\dagger})}$. By construction, $\hat{q}\geq
q_{m}(R_{1})$. Now consider another revenue curve $R_{2}$ defined as follows,

$\displaystyle
R_{2}(q)\triangleq\left\\{\begin{array}[]{ll}R_{1}(q)&q\in[0,q_{m}(R_{1})]~{},\\\
1&q\in[q_{m}(R_{1}),\hat{q}]~{},\\\
\frac{1-q}{1-\hat{q}}&q\in[\hat{q},1]~{}.\end{array}\right.$

By construction, $R_{2}$ is a concave revenue curve s.t. (i)
$R_{1}(q)=R_{2}(q)$ for all $q\in[0,q_{m}(R_{1})]$; (ii) $R_{1}(q)\leq
R_{2}(q)$ for all $q\in[q_{m}(R_{1}),q^{\dagger}]$; and (iii) $R_{1}(q)\geq
R_{2}(q)$ for all $q\in[q^{\dagger},1]$; See Figure 6 for a graphical
illustration.

Applying Lemma 5.2 on $R_{1},R_{2},q^{\dagger},v$ and all $b^{\ddagger}\geq
b^{\dagger}$, we conclude that the optimal bid for an agent with value $v$ and
revenue curve $R_{2}$ is in $[0,b^{\dagger}]$.

Note that for any bid $b\in[0,\nicefrac{{1}}{{\hat{q}}}]$, the utility
$u(v,b,R_{2})$ has a closed-form expression as follows,

$\displaystyle u(v,b,R_{2})$
$\displaystyle=v\cdot\frac{b(1-\hat{q})}{b(1-\hat{q})+1}+0.7\log\left(\frac{1}{b(1-\hat{q})+1}\right).$

Considering the first order condition of $u(v,b,R_{2})$ with respect to bid
$b$, after basic simplification, we have

$\displaystyle b=\frac{v}{0.7}-\frac{1}{1-\hat{q}}.$

Thus, the optimal bid in $[0,\nicefrac{{1}}{{\hat{q}}}]$ for revenue curve
$R_{2}$ is
$\tilde{b}\triangleq\min\\{\nicefrac{{1}}{{\hat{q}}},\max\\{0,\frac{v}{0.7}-\frac{1}{1-\hat{q}}\\}\\}$.
Plugging $u(v,b,R_{2})$ with $b=\tilde{b}$, we get

$\displaystyle v(1-\tilde{q})+\frac{0.7\log(\tilde{q})}{1-\hat{q}},$

i.e., the right hand side of inequality (2).

Moreover, note that the utility $u(v,\nicefrac{{v_{m}(R_{1})}}{{0.7}},R_{2})$
has a closed-form expression as follows,

$\displaystyle v\cdot(1-q^{\ddagger}(R))-v_{m}(R)\cdot
q^{\ddagger}(R)-0.7\left(w(R)+\log\left(\frac{\hat{q}}{q_{m}(R)}\right)-\frac{\ln(\hat{q})}{1-\hat{q}}\right)$

i.e., the left hand side of inequality (2). This leads to a contradiction,
which finishes the proof. ∎

######  Definition 5.2.

A _pentagon revenue curve $R$_ parameterized by the quantile
$q_{k}\in[q_{m}(R),1]$ of kink and the revenue
$r_{k}\in\left[\frac{1-q_{k}}{1-q_{m}(R)},1\right]$ on this kink is defined as
follows

$\displaystyle
R(q)\triangleq\left\\{\begin{array}[]{ll}1&q\in[0,q_{m}(R)]~{},\\\
r_{k}+\frac{q-q_{m}(R)}{q_{k}-q_{m}(R)}(1-r_{k})&q\in[q_{m}(R),q_{k}]~{},\\\
\frac{1-q}{1-q_{k}}\cdot r_{k}&q\in[q_{k},1]~{}.\end{array}\right.$

An example of a pentagon revenue curve is illustrated as the solid curve in
Figure 7a as the solid line.

$1$$0$$1$$q_{m}(R_{2})$$q_{m}(R_{1})$$q_{k}$$q^{\dagger}$$\tilde{q}$$b^{\dagger}$
(a)  Case (i) $b^{\dagger}\leq\tilde{v}$.

$1$$0$$1$$\tilde{q}$$q_{m}(R_{1})$$q_{m}(R_{3})$$q^{\dagger}$${b^{\dagger}}$
(b) Case (ii) $b^{\dagger}\geq\tilde{v}$.

Figure 7:  Graphical illustration for Lemma 5.12. The gray dashed (resp. black
solid) curve is revenue curve $R_{1}$ (resp. $R_{2}$ in (a) and $R_{3}$ in
(b)). The slope of the dotted line from (0, 0) is $b^{\dagger}$.

######  Lemma 5.12.

In the sample-bid mechanism, given any quantile $\hat{q}\in[0,1]$, quantile
$\tilde{q}\in[\hat{q},1]$, and bid $b\in[0,\nicefrac{{1}}{{\hat{q}}}]$, if for
all pentagon revenue curves $R_{\text{P}}$ with
$q_{m}(R_{\text{P}})\geq\hat{q}$, the optimal bid of an agent with value
$v(\tilde{q},R_{\text{P}})$ and revenue curve $R_{\text{P}}$ is at least $b$;
then for all concave revenue curves $R$ with $q_{m}(R)=\hat{q}$, the optimal
bid of an agent with value $v(\tilde{q},R)$ and revenue curve $R$ is at least
$b$ as well.

###### Proof.

Fix arbitrary $\hat{q}\in[0,1]$, $\tilde{q}\in[\hat{q},1]$, and concave
revenue curve $R_{1}$ with $q_{m}(R_{1})=\hat{q}$. Let $b^{\dagger}$ be the
optimal bid for an agent with value
$v(\tilde{q},R_{1})~{}(\triangleq\tilde{v})$ and revenue curve $R_{1}$. To
show this lemma, it is sufficient to assume
$b^{\dagger}\leq\nicefrac{{1}}{{q_{m}(R_{1})}}$. Now we consider two cases,
i.e., $b^{\dagger}\leq\tilde{v}$ and $b^{\dagger}\geq\tilde{v}$ separately.

Case (i) $b^{\dagger}\leq\tilde{v}$: Consider the pentagon revenue curve
$R_{2}$ with

$\displaystyle\begin{gathered}q_{m}(R_{2})=\tilde{q}+\frac{1-R_{1}(\tilde{q})}{R_{1}^{\prime}(\tilde{q})},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}q_{k}=\frac{\tilde{q}R_{1}^{\prime}(\tilde{q})-R_{1}(\tilde{q})+\frac{R_{1}(q^{\dagger})}{1-q^{\dagger}}}{R_{1}^{\prime}(\tilde{q})+\frac{R_{1}(q^{\dagger})}{1-q^{\dagger}}},\\\
r_{k}=\frac{1-q_{k}}{1-q^{\dagger}}R_{1}(q^{\dagger}).\end{gathered}$

where $R_{1}^{\prime}(\tilde{q})$ is the right-hand derivative of $R_{1}(q)$
at $q=\tilde{q}$. By construction, we have (i)
$R_{2}(\tilde{q})=R_{1}(\tilde{q})$ and thus
$v(\tilde{q},R_{2})=v(\tilde{q},R_{1})=\tilde{v}$; (ii)
$R_{2}(q^{\dagger})=R_{1}(q^{\dagger})$; and (iii) $R_{2}(q)\geq R_{1}(q)$ for
all $q\in[0,q^{\dagger}]$. See Figure 7a for a graphical illustration.

Applying Lemma 5.2 on $R_{1}$, $R_{2}$, $q^{\dagger}$, $\tilde{v}$ and all
$b^{\ddagger}\geq b^{\dagger}$, we conclude that the optimal bid for value
$\tilde{v}$ is weakly smaller than $b^{\dagger}$. Thus, for any bid
$b\in[0,\nicefrac{{1}}{{\hat{q}}}]$, if the optimal bid for value
$v(\tilde{q},R_{2})$ in revenue curve $R_{2}$ is at least $b$, then the
optimal bid $b^{\dagger}$ for value $v(\tilde{q},R_{1})$ in revenue curve
$R_{1}$ is at least $b$ as well.

Case (ii) $b^{\dagger}\geq\tilde{v}$: Consider the pentagon revenue curve
$R_{3}$ with

$\displaystyle\begin{gathered}q_{m}(R_{3})=1-\frac{1-q^{\dagger}}{R_{1}(q^{\dagger})},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}q_{k}=q_{m}(R_{3}),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}r_{k}=1.\end{gathered}$

By construction, we have (i) $q(\tilde{v},R_{3})\leq q(\tilde{v},R_{1})$ and
thus $v(\tilde{q},R_{3})\leq v(\tilde{q},R_{1})$; (ii)
$R_{3}(q^{\dagger})=R_{1}(q^{\dagger})$; and (iii) $R_{3}(q)\geq R_{1}(q)$ for
all $q\in[0,q^{\dagger}]$. See Figure 7b for a graphical illustration.

Applying Lemma 5.2 on $R_{1}$, $R_{3}$, $q^{\dagger}$, $\tilde{v}$ and all
$b^{\ddagger}\geq b^{\dagger}$, we conclude that the optimal bid for value
$\tilde{v}$ is weakly smaller than $b^{\dagger}$. Thus, for any bid
$b\in[0,\nicefrac{{1}}{{\hat{q}}}]$, if the optimal bid for value
$v(\tilde{q},R_{3})$ in revenue curve $R_{3}$ is at least $b$, then combining
with Lemma 3.5, the optimal bid $b^{\dagger}$ for value $v(\tilde{q},R_{1})$
in revenue curve $R_{1}$ is at least $b$ as well. ∎

Now we are ready to prove Lemma 5.8.

###### Proof of Lemma 5.8.

Fix an arbitrary concave revenue curve $R$ with $q_{m}(R)\leq 0.62$. We
consider $v^{*}(R)\leq v_{m}(R)$, $v_{m}(R)\leq
v^{*}(R)\leq\nicefrac{{v_{m}(R)}}{{0.7}}$, and
$v^{*}(R)\geq\nicefrac{{v_{m}(R)}}{{0.7}}$ separately.

Case (i) $v^{*}(R)\leq v_{m}(R)$: By Lemma 3.4 and Lemma 3.5, the expected
revenue $\text{\bf Rev}_{R}({\rm SB})$ of the sample-bid mechanism for revenue
curve $R$ can be lower-bounded as follows,

$\displaystyle\text{\bf Rev}_{R}({\rm SB})=$
$\displaystyle\int_{0}^{1}p(v(q,R),R)\,dq$ $\displaystyle=$
$\displaystyle\int_{0}^{q_{m}(R)}p(v(q,R),R)\,dq+\int_{q_{m}(R)}^{q^{*}(R)}p(v(q,R),R)\,dq+\int_{q^{*}(R)}^{1}p(v(q,R),R)\,dq$
$\displaystyle\geq$
$\displaystyle~{}\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)\cdot
q_{m}(R)+\tilde{p}(v_{m}(R),R)\cdot(q^{*}(R)-q_{m}(R))+\int_{q^{*}(R)}^{1}p(v(q,R),R)\,dq.$
Invoking Lemma 5.9 and Lemma 5.10, we can rewrite the lower bound of
$\text{\bf Rev}\\!\left[{R}\right]$ as $\displaystyle\geq$
$\displaystyle\left(\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)-\frac{0.7\log(q_{m}(R)))}{1-q_{m}(R)}\right)\cdot
q_{m}(R)$
$\displaystyle~{}~{}~{}-\frac{0.7\log(q_{m}(R))}{1-q_{m}(R)}\cdot\left(\frac{1}{1-v^{*}(R)\cdot(1+q_{m}(R))}-q_{m}(R)\right)+\int_{q^{*}(R)}^{1}p(v(q,R),R)\,dq.$
Note that this lower bound is weakly decreasing in $v^{*}(R)$ while holding
everything else fixed. Let $v^{*}(q_{m}(R),q^{\ddagger}(R),w(R))$ be the upper
bound of $v^{*}(R)$ as the function of $q_{m}(R),q^{\ddagger}(R),w(R)$
established in Lemma 5.11. From Lemma 5.10, we can lower bound
$v^{*}(q_{m}(R),q^{\ddagger}(R),w(R)))$ by
$q^{*}(q_{m}(R),q^{\ddagger}(R),w(R))\triangleq\left({1-v^{*}(q_{m}(R),q^{\ddagger}(R),w(R))\cdot(1+q_{m}(R))}\right)^{-1}$.
Let $b(q,q_{m}(R))$ be the lower bound of the optimal bid for an agent with
value $v(q,R)$ and revenue curve $R$ as the function of $q,q_{m}(R)$
established in Lemma 5.12. Then, we can further rewrite the lower bound of
$\text{\bf Rev}\\!\left[{R}\right]$ as $\displaystyle\geq$
$\displaystyle\left(\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)-\frac{0.7\log(q_{m}(R)))}{1-q_{m}(R)}\right)\cdot
q_{m}(R)$
$\displaystyle~{}~{}~{}-\frac{0.7\log(q_{m}(R))}{1-q_{m}(R)}\cdot\left(q^{*}(q_{m}(R),q^{\ddagger}(R),w(R))-q_{m}(R)\right)$
$\displaystyle~{}~{}~{}+\int_{q^{*}(q_{m}(R),q^{\ddagger}(R),w(R))}^{1}\frac{0.7\log(b(q,q_{m}(R))\cdot(1-q_{m}(R))+1)}{1-q_{m}(R)}\,dq.$

where the bid $b(q,q_{m}(R))$ in the last term can be lower-bounded using
Lemma 5.9.

Therefore, we lower-bound $\text{\bf Rev}_{R}({\rm SB})$ as the function of
$q_{m}(R),q^{\ddagger}(R),w(R)$. By numerically enumerating all possible
parameters, we conclude that $\text{\bf Rev}_{R}({\rm SB})\geq 0.545$ in this
case.

Case (ii) $v_{m}(R)\leq v^{*}(R)\leq\nicefrac{{v_{m}(R)}}{{0.7}}$: The
analysis is similar to case (i). By Lemma 3.4 and Lemma 3.5, the expected
revenue $\text{\bf Rev}_{R}({\rm SB})$ of the sample-bid mechanism for revenue
curve $R$ can be lower-bounded as follows,

$\displaystyle\text{\bf Rev}_{R}({\rm SB})=$
$\displaystyle\int_{0}^{1}p(v(q,R),R)\,dq$ $\displaystyle\geq$
$\displaystyle\int_{0}^{q^{*}(R)}p(v(q,R),R)\,dq+\int_{q_{m}(R)}^{1}p(v(q,R),R)\,dq$
$\displaystyle\geq$
$\displaystyle~{}\tilde{p}(\nicefrac{{v_{m}(R)}}{{0.7}},R)\cdot
q^{*}(R)+\int_{q_{m}(R)}^{1}p(v(q,R),R)\,dq.$ Invoking Lemma 5.9 and Lemma
5.10, we can rewrite the lower bound of $\text{\bf Rev}\\!\left[{R}\right]$ as
$\displaystyle\geq$
$\displaystyle\left(\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)-\frac{0.7\log(q_{m}(R)))}{1-q_{m}(R)}\right)\cdot\frac{2q_{m}(R)-q^{\ddagger}(R)\cdot(1+\nicefrac{{1}}{{0.7}})}{1+v^{*}(R)\cdot(1-q_{m}(R))}$
$\displaystyle~{}~{}~{}+\int_{q_{m}(R)}^{1}p(v(q,R),R)\,dq.$ Note that this
lower bound is weakly decreasing in $v^{*}(R)$ while holding everything else
fixed. Let $v^{*}(q_{m}(R),q^{\ddagger}(R),w(R))$ be the upper bound of
$v^{*}(R)$ established in Lemma 5.11. Let $b(q,q_{m}(R))$ be the lower bound
of the optimal bid for an agent with value $v(q,R)$ and revenue curve $R$
established in Lemma 5.12. Then, we can further rewrite the lower bound as
$\displaystyle\geq$
$\displaystyle\left(\frac{q^{\ddagger}(R)}{q_{m}(R)}+0.7w(R)-\frac{0.7\log(q_{m}(R)))}{1-q_{m}(R)}\right)\cdot\frac{2q_{m}(R)-q^{\ddagger}(R)\cdot(1+\nicefrac{{1}}{{0.7}})}{1+v^{*}(q_{m}(R),q^{\ddagger}(R),w(R))\cdot(1-q_{m}(R))}$
$\displaystyle~{}~{}~{}+\int_{q_{m}(R)}^{1}\frac{0.7\log(b(q,q_{m}(R))\cdot(1-q_{m}(R))+1)}{1-q_{m}(R)}\,dq.$

where the bid $b(q,q_{m}(R))$ in the last term can be lower-bounded using
Lemma 5.9.

Therefore, we lower-bound $\text{\bf Rev}_{R}({\rm SB})$ as the function of
$q_{m}(R),q^{\ddagger}(R),w(R)$. By numerically enumerating all possible
parameters, we conclude that $\text{\bf Rev}_{R}({\rm SB})\geq 0.545$ in this
case.

Case (iii) $v^{*}(R)\geq\nicefrac{{v_{m}(R)}}{{0.7}}$: Lemma 5.11 upper-bounds
$v^{*}(R)$ as the function of $q_{m}(R)$, $q^{\ddagger}(R)$ and $w(R)$. By
numerically enumerating all possible parameters, we conclude that
$v^{*}(R)\geq\nicefrac{{v_{m}(R)}}{{0.7}}$ is not possible for any revenue
curve $R$ with $q_{m}(R)\leq 0.62$. ∎

##  6 Prior-independent Approximation Lower Bound

In this section, we show that no mechanism can achieve prior-independent
approximation better than $1.07$ even when the class of distributions are
uniform distributions. Note that point mass distributions are special cases of
the uniform distributions. The lower bound we will prove in this section holds
for more general families of mechanisms than the single-round mechanisms that
we introduced in Section 2. Here we will show that even when the agent and the
seller have multiple rounds of communication in general messages spaces, no
mechanism can achieve prior-independent approximation better than $1.07$.
However, since our analysis does not hinge on the exact format of the
mechanism, we will not formally introduce the model for multi-rounds of
communication.

######  Theorem 6.1.

For a single item, a single uniformly distributed agent, and a single
valuation sample, the prior-independent approximation ratio for revenue
maximization is at least $1.07$.

The main idea for proving Theorem 6.1 is as follows. Consider two scenarios
where the valuation distribution of the agent is either uniform between
$[1,2]$ or a pointmass with some value $v\in[1,2]$. Note that the optimal
mechanism for an agent with value from the uniform distribution $\rm{U}[1,2]$
is to always allocate the item with expected payment $1$. Thus if the
mechanism is optimal for this setting, when the valuation distribution for the
agent is actually a pointmass with some value $v\in[1,2]$, the agent can
always imitate the type in a uniform distribution $U[1,2]$ to win the item and
pay at most 1 in expectation. This indicates that the optimal prior-
independent approximation ratio is strictly above 1. By leveraging the
approximation ratio in those two cases, we show that the optimal ratio is at
least 1.07.

Before the proof of Theorem 6.1, we first introduce several notations and
present several properties for non-truthful mechanisms ${\cal M}$ with prior-
independent approximation ratio $\beta$.

######  Lemma 6.2.

For single item, single agent, any distribution $F$ with support
$[\underline{v},\overline{v}]$, for non-truthful mechanism with prior-
independent approximation ratio $\beta$, the interim allocation for agent with
highest value $\overline{v}$ is $x(\overline{v},F)\geq\frac{1}{\beta}$.

###### Proof.

Suppose the interim allocation for agent with value $\overline{v}$ is
$x(\overline{v},F)<\frac{1}{\beta}$. Since the interim allocation is monotone,
the maximum expected virtual welfare for mechanism under distribution $F$ is
less than $\nicefrac{{1}}{{\beta}}$ of the optimal expected virtual welfare,
which implies the revenue is less than $\nicefrac{{1}}{{\beta}}$ of the
optimal revenue and the approximation ratio for distribution $F$ is higher
than $\beta$, a contradiction. ∎

######  Lemma 6.3.

For single item, single agent, and any uniform distribution $F$ with support
$[\underline{v},\overline{v}]$ such that $2\underline{v}\geq\overline{v}$, for
a non-truthful mechanism with prior-independent approximation ratio $\beta$,
the interim utility for agent with highest value $\overline{v}$ is
$u(\overline{v},F)\geq\frac{1}{2}\left(\overline{v}-\sqrt{\overline{v}^{2}-\frac{4\underline{v}}{\beta}}(\overline{v}-\underline{v})\right)$.

###### Proof.

For uniform distribution $F$ with support $[\underline{v},\overline{v}]$ such
that $2\underline{v}\geq\overline{v}$, the optimal mechanism
$\operatorname{OPT}_{F}$ is to post price $\underline{v}$ with expected
revenue $\underline{v}$. Suppose the utility for agent with value
$\overline{v}$ is
$u(\overline{v},F)<\frac{1}{2}\left(\overline{v}-\sqrt{\overline{v}^{2}-\frac{4\underline{v}}{\beta}}(\overline{v}-\underline{v})\right)$,
the optimal mechanism subject to this constraint is to post price
$\overline{v}-u(\overline{v},F)$, with expected revenue
$\frac{u(\overline{v},F)}{\overline{v}-\underline{v}}\cdot(\overline{v}-u(\overline{v},F))<\frac{\underline{v}}{\beta}$,
a contradiction. ∎

######  Lemma 6.4.

For single item, single agent, any point mass distribution $F$ with support
$\overline{v}$, for non-truthful mechanism with prior-independent
approximation ratio $\beta$, the interim utility for agent with value
$\overline{v}$ is
$u(\overline{v},F)\leq\overline{v}(1-\nicefrac{{1}}{{\beta}})$.

###### Proof.

Suppose the interim utility in this case is
$u(\overline{v},F)>\overline{v}(1-\nicefrac{{1}}{{\beta}})$, the expected
revenue is at most the social welfare minus the expected utility, which is at
most $\overline{v}-u(\overline{v},F)<\frac{\overline{v}}{\beta}$,
contradicting the fact that mechanism ${\cal M}$ achieves prior-independent
approximation ratio $\beta$. ∎

###### Proof of Theorem 6.1.

Suppose mechanism ${\cal M}$ inducing interim allocation and payment rule $x$
and $p$ achieves prior-independent approximation ratio $\beta$. Consider
uniform distribution $F$ with support $[1,2]$. By Lemma 6.2 and 6.3, we have
$x(2,F)\geq\frac{1}{\beta}$, and $u(2,F)\geq
1-\sqrt{1-\nicefrac{{1}}{{\beta}}})$. For any sample $s\in[1,2]$, the expected
allocation and payment of agent with value $2$ given the sample $s$ satisfies
the constraint that

$\displaystyle s\cdot x(2,F,s)-p(2,F,s)\leq s\left(1-\frac{1}{\beta}\right)$
(3)

otherwise for distribution $F_{s}$ with point mass on $s$, an agent with value
$s$ can imitate the behavior of an agent with value $2$ in uniform
distribution to achieve utility strictly higher than
$s\left(1-\nicefrac{{1}}{{\beta}}\right)$, and by Lemma 6.4, this contradicts
to the assumption that mechanism ${\cal M}$ achieves prior-independent
approximation ratio $\beta$. Taking expectation over sample $s$ for the left
hand side of equation (3), we have

$\displaystyle\text{\bf E}_{s}\\!\left[{s\cdot
x(2,F,s)-p(2,F,s)}\right]\geq\text{\bf E}_{s}\\!\left[{s\cdot
x(2,F,s)}\right]-(2-u(2,F))\geq\int_{1}^{1+\nicefrac{{1}}{{\beta}}}s\
ds-(2-u(2,F))$

where the last inequality holds because $x(2,F)\geq\frac{1}{\beta}$ and the
worst case happens when $x(2,F,s)=0$ for any sample $s\geq
1+\nicefrac{{1}}{{\beta}}$. Taking expectation over sample $s$ for the right
hand side of equation (3), we have

$\displaystyle\text{\bf
E}_{s}\\!\left[{s\left(1-\frac{1}{\beta}\right)}\right]=\frac{3}{2}\left(1-\frac{1}{\beta}\right).$

Combining the inequalities, we have

$\displaystyle\frac{1}{2}\left(1+\frac{1}{\beta}\right)^{2}-\frac{1}{2}-(1+\sqrt{1-\nicefrac{{1}}{{\beta}}})\leq\frac{3}{2}\left(1-\frac{1}{\beta}\right).$

By solving the inequality, we have $\beta\geq 1.0737$. ∎

##  7 Revelation Gap

Feng and Hartline [2018] proposed the _revelation gap_ to quantify the
difference between the worst case performance of the optimal truthful
mechanism and the optimal non-truthful mechanism in prior-independent
mechanism design. They showed that a non-trivial revelation gap exists for the
welfare maximization problem for agents with budgets. In this section, we show
that a revelation gap also exists for the revenue maximization problem when
considering the single-item single-agent setting with single-sample access.

Let $\mathbb{M}_{r}$ be the family of truthful mechanisms, the family of
mechanisms such that the agent maximizes her utility by truthfully revealing
her valuation to the seller, i.e., $b^{*}(v,F)=v$ for all value $v$ and
valuation distributions $F$. Let $\mathbb{M}$ be the family of all mechanisms.
We define

$\displaystyle\beta(\text{MECHS},\text{DISTS})\triangleq\min_{{\cal
M}\in\text{MECHS}}\Gamma({\cal M},\text{DISTS})$

as the optimal prior-independent approximation ratio among the family of
mechanisms MECHS. The revelation gap for a family of distributions DISTS is
then defined as the ratio
$\frac{\beta(\mathbb{M}_{r},\text{DISTS})}{\beta(\mathbb{M},\text{DISTS})}$.

######  Definition 7.1.

A mechanism is _scale-invariant_ if the interim allocation is invariant of the
scale, i.e., $x(\alpha v,\alpha F)=x(v,F)$ for any distribution $F$, valuation
$v$ and any $\alpha>0$.

Allouah and Besbes [2019] characterized the prior-independent approximation
ratio of the truthful mechanisms under the assumption of scale-invariance for
sample-based pricing mechanisms. Note that in contrast, our lower bound result
shown in Theorem 6.1 does not require the assumption on scale-invariance. Here
is the formal definition of sample-based pricing mechanisms.

######  Definition 7.2.

Given function $\alpha:{\mathbb{R}}\to\Delta({\mathbb{R}})$ mapping from the
sample to the randomized price, for sample $s$, the _sample-based pricing
mechanism_ solicits a non-negative bid $b\geq 0$, allocates the item to the
agent if $b\geq\alpha(s)$, and charges the agent
$\alpha(s)\cdot\mathbbm{1}\\{b\geq\alpha(s)\\}$.

It can be observed that the bid allocation rules of both sample-bid mechanism
and sample-based pricing are similar (i.e. competing against the sample), and
the difference is the payment semantics.

######  Theorem 7.1 (Allouah and Besbes, 2019).

Under the assumption of scale-invariance, for single-item setting with regular
valuation distribution, when seller has access to a single sample, the prior-
independent approximation ratio of the optimal sample-based pricing mechanism
is bounded in $[1.957,1.996]$. Moreover, when the valuation distribution is
MHR, the prior-independent approximation ratio is bounded in $[1.543,1.575]$.

Given an arbitrary valuation distribution and any mechanism that is incentive
compatible only for the given valuation distribution, the mechanism may not be
equivalent to any sample-based pricing mechanism. The is because the agent
only maximizes her utility by taking expectation over the sample. However, we
can show that if the mechanism is incentive compatible for all possible prior
distributions, then it is equivalent to consider posting a randomized price to
the agent based on the realization of the sample, i.e., a sample-based pricing
mechanism.

######  Lemma 7.2.

For any mechanism with allocation $\tilde{x}$ and payment $\tilde{p}$ that is
incentive compatible and individual rational for all valuation distributions,
there exists a sample-based pricing mechanism that generates the same expected
allocation and payment pointwise for any valuation of the agent and any
realization of the sample.

###### Proof.

First we claim that, for any truthful mechanism with allocation $\tilde{x}$
and payment $\tilde{p}$, the induced allocation rule $\tilde{x}(\cdot,s)$ and
payment rule $\tilde{p}(\cdot,s)$ are incentive compatible and individual
rational given any realization of the sample $s$.

First we prove the incentive compatibility. Suppose by contradiction, there
exists constant $\epsilon>0$, sample $s$ and value $v,v^{\prime}$ such that

$\displaystyle v\tilde{x}(v^{\prime},s)-\tilde{p}(v^{\prime},s)\geq
v\tilde{x}(v,s)-\tilde{p}(v,s)+\epsilon.$

Let $F$ be an arbitrary distribution with positive density everywhere on the
support $[0,\infty)$. Define $H\triangleq u(v,v,F)-u(v,v^{\prime},F)$ as the
utility loss for value $v$ to misreport $v^{\prime}$ when the distribution is
$F$. Given constant $\delta>0$, let $F^{\prime}$ be the distribution such that
with probability $1-\delta$, the value of the agent is $s$ and with
probability $\delta$, the value is drawn from distribution $F$. It is easy to
verify that both $v$ and $v^{\prime}$ are in the support of distribution
$F^{\prime}$. Moreover, the utility loss for misreporting $v^{\prime}$ is

$\displaystyle
u(v,v,F^{\prime})-u(v,v^{\prime},F^{\prime})\geq(1-\delta)\epsilon+\delta H$

where $(1-\delta)\epsilon+\delta H>0$ for sufficiently small $\delta$. This
implies that the mechanism is not incentive compatible for distribution
$F^{\prime}$, a contradiction.

Similarly, for individual rationality, if there exists constant $\epsilon>0$,
sample $s$ and value $v,v^{\prime}$ such that

$\displaystyle v\tilde{x}(v,s)-\tilde{p}(v,s)\leq-\epsilon,$

there exists a distribution $F^{\prime}$ supported on $[0,\infty)$ such that
agent with value $v$ is not individual rational given distribution
$F^{\prime}$.

Finally, since for any sample $s$, the induced mechanism is incentive
compatible, the allocation $\tilde{x}(v,s)$ is monotone in $v$ for any sample
$s$. Moreover, individual rationality implies that the payment of the agent is
$0$ if she does not win the item. Thus the mechanism can be implemented as
sample-based pricing mechanism for any realized sample. ∎

Lemma 7.2 suggest that under the assumption of scale invariance, the bounds on
prior-independent approximation ratio of sample-based pricing in Theorem 7.1
carry over to truthful mechanisms. Then combining it with Theorem 5.1 and 6.1,
we have the following corollary characterizing the revelation gap under the
assumption of scale-invariance.

######  Corollary 7.3.

Under the assumption of scale-invariance, for single-item setting with regular
valuation distribution, when seller has access to a single sample, the
revelation gap is bounded in $[1.066,1.859]$. Moreover, when the valuation
distribution is MHR, the revelation gap is bounded in $[1.190,1.467]$.

## References

  * Alaei et al. [2013] Saeed Alaei, Hu Fu, Nima Haghpanah, and Jason Hartline.  The simple economics of approximately optimal auctions.  In _Proc. 54th IEEE Symp. on Foundations of Computer Science_ , pages 628–637. IEEE, 2013.
  * Alaei et al. [2019] Saeed Alaei, Jason Hartline, Rad Niazadeh, Emmanouil Pountourakis, and Yang Yuan.  Optimal auctions vs. anonymous pricing.  _Games and Economic Behavior_ , 118:494–510, 2019.
  * Allouah and Besbes [2018] Amine Allouah and Omar Besbes.  Prior-independent optimal auctions.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , pages 503–503. ACM, 2018.
  * Allouah and Besbes [2019] Amine Allouah and Omar Besbes.  Sample-based optimal pricing.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 391–391. ACM, 2019.
  * Azar et al. [2012] Pablo Azar, Jing Chen, and Silvio Micali.  Crowdsourced bayesian auctions.  In _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ , pages 236–248, 2012.
  * Azar et al. [2014] Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg.  Prophet inequalities with limited information.  In _Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1358–1377. SIAM, 2014.
  * Babaioff et al. [2018] Moshe Babaioff, Yannai A Gonczarowski, Yishay Mansour, and Shay Moran.  Are two (samples) really better than one?  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , pages 175–175, 2018.
  * Barlow and Marshall [1965] Richard E Barlow and Albert W Marshall.  Tables of bounds for distributions with monotone hazard rate.  _Journal of the American Statistical Association_ , 60(311):872–890, 1965.
  * Becker et al. [1964] Gordon M Becker, Morris H DeGroot, and Jacob Marschak.  Measuring utility by a single-response sequential method.  _Behavioral science_ , 9(3):226–232, 1964.
  * Bulow and Klemperer [1996] Jeremy Bulow and Paul Klemperer.  Auctions versus negotiations.  _The American Economic Review_ , 86(1):180–194, 1996.
  * Bulow and Roberts [1989] Jeremy Bulow and John Roberts.  The simple economics of optimal auctions.  _The Journal of Political Economy_ , 97:1060–90, 1989.
  * Caillaud and Robert [2005] Bernard Caillaud and Jacques Robert.  Implementation of the revenue-maximizing auction by an ignorant seller.  _Review of Economic Design_ , 9(2):127–143, 2005\.
  * Chawla and Hartline [2013] Shuchi Chawla and Jason Hartline.  Auctions with unique equilbria.  In _Proc. 14th ACM Conf. on Electronic Commerce_ , pages 181–196, 2013.
  * Chawla et al. [2013] Shuchi Chawla, Jason D Hartline, David Malec, and Balasubramanian Sivan.  Prior-independent mechanisms for scheduling.  In _Proceedings of the forty-fifth annual ACM Symposium on Theory of Computing_ , pages 51–60. ACM, 2013.
  * Chawla et al. [2014a] Shuchi Chawla, Hu Fu, and Anna Karlin.  Approximate revenue maximization in interdependent value settings.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , pages 277–294. ACM, 2014a.
  * Chawla et al. [2014b] Shuchi Chawla, Jason Hartline, and Denis Nekipelov.  Mechanism design for data science.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , pages 711–712. ACM, 2014b.
  * Chawla et al. [2016] Shuchi Chawla, Jason Hartline, and Denis Nekipelov.  A/b testing of auctions.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , pages 19–20. ACM, 2016.
  * Christodoulou et al. [2015] George Christodoulou, Alkmini Sgouritsa, and Bo Tang.  On the efficiency of all-pay mechanisms.  In _Algorithms-ESA 2015_ , pages 349–360. Springer, 2015.
  * Cole and Roughgarden [2014] Richard Cole and Tim Roughgarden.  The sample complexity of revenue maximization.  In _Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing_ , pages 243–252, 2014.
  * Correa et al. [2019] José Correa, Paul Dütting, Felix Fischer, and Kevin Schewior.  Prophet inequalities for iid random variables from an unknown distribution.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 3–17, 2019.
  * Correa et al. [2020] José R Correa, Andrés Cristi, Boris Epstein, and José A Soto.  The two-sided game of googol and sample-based prophet inequalities.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2066–2081. SIAM, 2020.
  * Dasgupta and Maskin [2000] Partha Dasgupta and Eric Maskin.  Efficient auctions.  _The Quarterly Journal of Economics_ , 115(2):341–388, 2000.
  * Daskalakis and Zampetakis [2020] Constantinos Daskalakis and Manolis Zampetakis.  More revenue from two samples via factor revealing sdps.  In _Proceedings of the 21st ACM Conference on Economics and Computation_ , pages 257–272, 2020.
  * Devanur et al. [2011] Nikhil R Devanur, Jason D Hartline, Anna R Karlin, and C Thach Nguyen.  Prior-independent multi-parameter mechanism design.  In _WINE_ , pages 122–133. Springer, 2011.
  * Devanur et al. [2015] Nikhil R Devanur, Jason D Hartline, and Qiqi Yan.  Envy freedom and prior-free mechanism design.  _Journal of Economic Theory_ , 156:103–143, 2015.
  * Dhangwatnotai et al. [2015] Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan.  Revenue maximization with a single sample.  _Games and Economic Behavior_ , 91:318–333, 2015.
  * Dütting and Kesselheim [2015] Paul Dütting and Thomas Kesselheim.  Algorithms against anarchy: Understanding non-truthful mechanisms.  In _Proceedings of the Sixteenth ACM Conference on Economics and Computation_ , pages 239–255. ACM, 2015.
  * Dütting et al. [2020] Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser.  Efficient two-sided markets with limited information.  _arXiv preprint arXiv:2003.07503_ , 2020.
  * Feng and Hartline [2018] Yiding Feng and Jason D Hartline.  An end-to-end argument in mechanism design (prior-independent auctions for budgeted agents).  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 404–415. IEEE, 2018.
  * Feng et al. [2019] Yiding Feng, Jason D Hartline, and Yingkai Li.  Optimal auctions vs. anonymous pricing: Beyond linear utility.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 885–886. ACM, 2019.
  * Fu et al. [2013] Hu Fu, Jason Hartline, and Darrell Hoy.  Prior-independent auctions for risk-averse agents.  In _Proceedings of the fourteenth ACM conference on Electronic commerce_ , pages 471–488, 2013.
  * 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. ACM, 2015.
  * Goldner and Karlin [2016] Kira Goldner and Anna R Karlin.  A prior-independent revenue-maximizing auction for multiple additive bidders.  In _International Conference on Web and Internet Economics_ , pages 160–173. Springer, 2016.
  * 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 Symposium on Theory of Computing_ , pages 662–673, 2019.
  * Hartline and Taggart [2019] Jason Hartline and Samuel Taggart.  Sample complexity for non-truthful mechanisms.  In _Proc. 20th ACM Conf. on Economics and Computation_ , pages 399–416, 2019.
  * Hartline et al. [2014] Jason Hartline, Darrell Hoy, and Sam Taggart.  Price of anarchy for auction revenue.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , pages 693–710, 2014.
  * Hartline et al. [2020] Jason Hartline, Aleck Johnsen, and Yingkai Li.  Benchmark design and prior-independent optimization.  In _61st Annual Symposium on Foundations of Computer Science, to appear_ , 2020.
  * Hartline [2016] Jason D Hartline.  Mechanism design and approximation.  2016\.
  * Hoy et al. [2018] Darrell Hoy, Samuel Taggart, and Zihe Wang.  A tighter welfare guarantee for first-price auctions.  In _Proceedings of the 50th Annual ACM Symposium on Theory of Computing_ , pages 132–137, 2018.
  * Huang et al. [2018] Zhiyi Huang, Yishay Mansour, and Tim Roughgarden.  Making the most of your samples.  _SIAM Journal on Computing_ , 47(3):651–674, 2018\.
  * Jackson [2001] Matthew O Jackson.  A crash course in implementation theory.  _Social choice and welfare_ , 18(4):655–708, 2001\.
  * Jin et al. [2019] Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao.  Tight approximation ratio of anonymous pricing.  In _Proceedings of the 51st Annual ACM Symposium on Theory of Computing_ , pages 674–685, 2019.
  * Jin et al. [2020] Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao.  Tight revenue gaps among simple mechanisms.  _SIAM Journal on Computing_ , 49(5):927–958, 2020\.
  * Maskin [2000] Eric Maskin.  Auctions, development, and privatization: Efficient auctions with liquidity-constrained buyers.  _European Economic Review_ , 44(4–6):667–681, 2000.
  * Morgenstern and Roughgarden [2015] Jamie H Morgenstern and Tim Roughgarden.  On the pseudo-dimension of nearly optimal auctions.  In _Advances in Neural Information Processing Systems_ , pages 136–144, 2015.
  * Myerson [1981] R. Myerson.  Optimal auction design.  _Mathematics of Operations Research_ , 6:58–73, 1981.
  * Roughgarden et al. [2012] Tim Roughgarden, Inbal Talgam-Cohen, and Qiqi Yan.  Supply-limiting mechanisms.  In _Proceedings of the 13th ACM Conference on Electronic Commerce_ , pages 844–861. ACM, 2012.
  * Roughgarden et al. [2017] Tim Roughgarden, Vasilis Syrgkanis, and Eva Tardos.  The price of anarchy in auctions.  _Journal of Artificial Intelligence Research_ , 59:59–101, 2017.
  * Roughgarden et al. [2020] Tim Roughgarden, Inbal Talgam-Cohen, and Qiqi Yan.  Robust auctions for revenue via enhanced competition.  _Operations Research_ , 68(4):1074–1094, 2020\.
  * Saltzer et al. [1984] Jerome H Saltzer, David P Reed, and David D Clark.  End-to-end arguments in system design.  _ACM Transactions on Computer Systems (TOCS)_ , 2(4):277–288, 1984.
  * Syrgkanis and Tardos [2013] Vasilis Syrgkanis and Eva Tardos.  Composable and efficient mechanisms.  In _Proceedings of the forty-fifth annual ACM Symposium on Theory of Computing_ , pages 211–220, 2013.

##  Appendix A Numerical Analysis

In Section 5, we bound the prior-independent approximation ratio of the
sample-bid mechanism by enumerating the possible choices of given parameters.
One concern is that the parameters are selected from a continuous interval,
and the revenue for valuation distributions with parameters that are not
evaluated on discretized points may be far from the revenue on discretized
points. In this section, we formally show that this is not the case for our
analysis. To provide a theoretical lower bound on all possible distributions,
we will present a unified lower bound on the revenue for distributions with
parameters between discretized points. We will formalize this approach for the
numerical calculation for Lemma 5.7, and the numerical calculation for other
lemmas and theorems hold similarly.

By the proof of Lemma 5.7, for any revenue curve $R$ in Figure 3e
parameterized by monopoly quantile
$q_{m}\in[\underaccent{\bar}{\quant}_{m},\bar{q}_{m}]$ and revenue
$r_{0}\in[\underaccent{\bar}{r}_{0},\bar{r}_{0}]$ for quantile $0$, the
revenue of the seller is lower bounded by $p(v^{*}(R),R)\cdot q^{*}(R)$ where
$v^{*}(R)$ is the critical value with bid above monopoly price and $q^{*}(R)$
is the quantile for critical value. Note that it is sufficient for us to
consider revenue curves $R$ such that $v^{*}(R)$ is at least the monopoly
price. Next we show how to provide bounds on parameters
$\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0}$,
as well as lower bounds on $p(v^{*}(R),R)$ and $q^{*}(R)$ using parameters
$\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0}$.

######  Lemma A.1.

There exists efficiently computed set $S\subseteq{\mathbb{R}}^{4}$ and
function $\tau:{\mathbb{R}}^{4}\to{\mathbb{R}}$ such that for any revenue
curve $R$ in Figure 3e parameterized by monopoly quantile
$q_{m}\in[\underaccent{\bar}{\quant}_{m},\bar{q}_{m}]$ and revenue
$r_{0}\in[\underaccent{\bar}{r}_{0},\bar{r}_{0}]$ for quantile $0$, we have

  1. 1.

$v^{*}(R)\geq v_{m}(R)$ only if
$(\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0})\in
S$;

  2. 2.

$p(v^{*}(R),R)\cdot
q^{*}(R)\geq\tau(\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0})$
if
$(\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0})\in
S$.

###### Proof.

First we illustrate how to find the desirable set $S$ by numerical
calculation. Note that the requirement is such that the critical value for
bidding above the monopoly price is above monopoly price, i.e., $v^{*}(R)\geq
v_{m}(R)$. By Lemma 5.6, it is sufficient to verify that the optimal utility
of value $v_{m}(R)$ for bidding above $v_{m}(R)$ is positive. Note that by
Lemma 3.2, the optimal bid above the monopoly price is
$b=\frac{v_{m}}{\alpha}+\frac{1-r_{0}}{1-q_{m}}$, with expected utility

$\displaystyle u(v_{m},b)=\frac{1}{q_{m}}\cdot(1-q_{b})-\alpha\left(b\cdot
q_{b}+r_{0}\log(\frac{q_{m}}{q_{b}})+\frac{(1-r_{0})(q_{m}-q_{b})}{q_{m}}-\log
q_{m}\right)$

where $q_{b}=\frac{r_{0}}{b-\frac{1-r_{0}}{q_{m}}}$. Since
$q_{m}\in[\underaccent{\bar}{\quant}_{m},\bar{q}_{m}]$ and
$r_{0}\in[\underaccent{\bar}{r}_{0},\bar{r}_{0}]$, a sufficient condition for
$u(v_{m},b)>0$ is that

$\displaystyle\frac{1}{\bar{q}_{m}}\cdot(1-\bar{q}_{b})-\alpha\left(\bar{b}\cdot\bar{q}_{b}+\bar{r}_{0}\log(\frac{\bar{q}_{m}}{\underaccent{\bar}{\quant}_{b}})+\frac{(1-\underaccent{\bar}{r}_{0})(\bar{q}_{m}-\underaccent{\bar}{\quant}_{b})}{\underaccent{\bar}{\quant}_{m}}-\log\underaccent{\bar}{\quant}_{m}\right)>0,$

where
$\bar{b}=\frac{1}{\alpha\underaccent{\bar}{\quant}_{m}}+\frac{1-\underaccent{\bar}{r}_{0}}{1-\bar{q}_{m}}$,
$\bar{q}_{b}=\frac{\alpha\bar{r}_{0}\bar{q}_{m}(1-\underaccent{\bar}{\quant}_{m})}{1-\bar{q}_{m}+\alpha(1-\bar{r}_{0})}$
and
$\underaccent{\bar}{\quant}_{b}=\frac{\alpha\underaccent{\bar}{r}_{0}\underaccent{\bar}{\quant}_{m}(1-\bar{q}_{m})}{1-\underaccent{\bar}{\quant}_{m}+\alpha(1-\underaccent{\bar}{r}_{0})}$.
Note that the above inequality can be easily verified on discretized points.

Next we construct the function
$\tau(\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0})$
lower bound the revenue $p(v^{*}(R),R)\cdot q^{*}(R)$. First note that we can
enumerate the value above monopoly price and find the minimum value that the
interim utility is strictly positive. That is, given value $v\geq v_{m}$, the
optimal bid above the monopoly price is
$b=\frac{v}{\alpha}+\frac{1-r_{0}}{1-q_{m}}$, with expected utility

$\displaystyle u(v,b)$ $\displaystyle=v\cdot(1-q_{b})-\alpha\left(b\cdot
q_{b}+r_{0}\log(\frac{q_{m}}{q_{b}})+\frac{(1-r_{0})(q_{m}-q_{b})}{q_{m}}-\log
q_{m}\right)$ $\displaystyle\geq
v\cdot(1-\bar{q}_{b})-\alpha\left(\bar{b}\cdot\bar{q}_{b}+\bar{r}_{0}\log(\frac{\bar{q}_{m}}{\underaccent{\bar}{\quant}_{b}})+\frac{(1-\underaccent{\bar}{r}_{0})(\bar{q}_{m}-\underaccent{\bar}{\quant}_{b})}{\underaccent{\bar}{\quant}_{m}}-\log\underaccent{\bar}{\quant}_{m}\right)>0,$

where
$\bar{b}=\frac{v}{\alpha}+\frac{1-\underaccent{\bar}{r}_{0}}{1-\bar{q}_{m}}$,
$\bar{q}_{b}=\frac{\alpha\bar{r}_{0}\bar{q}_{m}(1-\underaccent{\bar}{\quant}_{m})}{v\underaccent{\bar}{\quant}_{m}(1-\bar{q}_{m})+\alpha(1-\bar{r}_{0})}$
and
$\underaccent{\bar}{\quant}_{b}=\frac{\alpha\underaccent{\bar}{r}_{0}\underaccent{\bar}{\quant}_{m}(1-\bar{q}_{m})}{v\bar{q}_{m}(1-\underaccent{\bar}{\quant}_{m})+\alpha(1-\underaccent{\bar}{r}_{0})}$.
Let $v^{*}$ be the minimum value that satisfies the above inequality. Then we
have $v^{*}\geq v^{*}(R)$, and hence

$\displaystyle q^{*}(R)\geq q(v^{*},R)=\frac{\alpha
r_{0}q_{m}(1-q_{m})}{vq_{m}(1-q_{m})+\alpha(1-r_{0})}\geq\frac{\alpha\underaccent{\bar}{r}_{0}\underaccent{\bar}{\quant}_{m}(1-\bar{q}_{m})}{v\bar{q}_{m}(1-\underaccent{\bar}{\quant}_{m})+\alpha(1-\underaccent{\bar}{r}_{0})}.$

Moreover, we can similar construct an upper bound on the utility $u(v,b)$ and
let $\underaccent{\bar}{\val}^{*}$ be the largest value such that the upper
bound on the utility is at most 0. Thus, we have
$v^{*}(R)\geq\underaccent{\bar}{\val}^{*}$ and hence

$\displaystyle p(v^{*}(R),R)\geq p(\underaccent{\bar}{\val}^{*},R)$
$\displaystyle=\alpha\left(b\cdot
q_{b}+r_{0}\log(\frac{q_{m}}{q_{b}})+\frac{(1-r_{0})(q_{m}-q_{b})}{q_{m}}-\log
q_{m}\right)$
$\displaystyle\geq\alpha\left(\underaccent{\bar}{\bid}\cdot\underaccent{\bar}{\quant}_{b}+\underaccent{\bar}{r}_{0}\log(\frac{\underaccent{\bar}{\quant}_{m}}{\bar{q}_{b}})+\frac{(1-\bar{r}_{0})(\underaccent{\bar}{\quant}_{m}-\bar{q}_{b})}{\bar{q}_{m}}-\log\bar{q}_{m}\right)$

where
$\underaccent{\bar}{\bid}=\frac{\underaccent{\bar}{\val}^{*}}{\alpha}+\frac{1-\bar{r}_{0}}{1-\underaccent{\bar}{\quant}_{m}}$,
$\bar{q}_{b}=\frac{\alpha\bar{r}_{0}\bar{q}_{m}(1-\underaccent{\bar}{\quant}_{m})}{\underaccent{\bar}{\val}^{*}\underaccent{\bar}{\quant}_{m}(1-\bar{q}_{m})+\alpha(1-\bar{r}_{0})}$
and
$\underaccent{\bar}{\quant}_{b}=\frac{\alpha\underaccent{\bar}{r}_{0}\underaccent{\bar}{\quant}_{m}(1-\bar{q}_{m})}{\underaccent{\bar}{\val}^{*}\bar{q}_{m}(1-\underaccent{\bar}{\quant}_{m})+\alpha(1-\underaccent{\bar}{r}_{0})}$.
By combining the inequalities, we have an lower bound on $p(v^{*}(R),R)\cdot
q^{*}(R)$ as a function of
$(\underaccent{\bar}{\quant}_{m},\bar{q}_{m},\underaccent{\bar}{r}_{0},\bar{r}_{0})$.
By discretizing the feasible set and enumerating for all discretized points,
we have a unified lower bound on revenue for all possible distributions. ∎