text:
\section{Introduction} In this paper we study a traditional Myersonian auction
setting: an auctioneer has an item to sell and he is facing $n$ potential buyers.
Each buyer has a (private) valuation for the item, and these valuations are i.i.d.\
according to some known continuous probability distribution $F$. You can think of
this valuation, as modelling the amount of money that the buyer is willing to spend
in order to get the item. An auction is a mechanism that receives as input a bid
from each buyer, and then decides if the item is going to be sold and to whom, and
for what price. Our goal is to design auctions that maximize the seller's expected
revenue.

We focus only on truthful auctions, that is, selling mechanisms that give no
incentives to the bidders to lie about their true valuation. Such auctions are both
conceptually and practically convenient. This restriction is essentially without
loss for our revenue maximization objective, due to the Revelation
Principle\footnote{In this paper we will avoid discussing such subtler issues as
implementability and truthfulness, since our goal is to study the performance of
specific and very simple pricing mechanisms. The interested reader is pointed to
\citep{Nisan2007a} as a good starting point for a deeper investigation of those
ideas.}.

In general, such an optimal auction can be rather complicated and even randomized
(aka a lottery). However, in his celebrated result, \citet{Myerson1981a} proved that
(under some standard assumptions on the valuations' distribution) revenue
maximization can be achieved by a very simple deterministic mechanism, namely a
second-price auction paired with a reserve value $r$. In such an auction, all buyers
with bids smaller than $r$ are ignored and the item is sold to the highest bidder
for a price equal to the second-highest bid (or $r$, if no other bidder remains).
Equivalently, you can think of this as the seller himself taking part in the
auction, with a  bid equal to $r$, and simply running a standard, Vickrey
second-price auction; if the auctioneer is the winning bidder, then the item stays
with him, that is, it remains unsold. Furthermore, \Citet{Bulow1996} essentially
showed that we can still guarantee a $1-\frac{1}{n}$ fraction of this optimal
revenue, even if we drop the reserve price $r$ completely and use just a standard
second-price auction.

No matter how simple and powerful the above optimal auction seems, it still requires
explicitly soliciting bids from all buyers and using the second-highest as the
``critical payment''; this is essentially a centralized solution, that asks for a
certain degree of coordination. Arguably, there is an even simpler selling mechanism
which, as a matter of fact, is being used extensively in practice, known as
\emph{anonymous pricing}: the seller simply decides on a selling price $p$, and then
the item goes to any buyer that can afford it (breaking ties arbitrarily); that is,
we sell the item to any bidder with a valuation greater or equal to $p$, for a price
of exactly $p$.

The question we investigate in this paper, is how well can such an extremely simple
selling mechanism perform when compared to an arbitrary, optimal auction. We resolve
this in a very positive way proving that, under natural assumptions on the valuation
distribution, as the number of buyers grows large, anonymous pricing achieves
optimal revenue. More precisely, its approximation ratio is $1+O(\ln\ln n/\ln n)$.
Furthermore, we show that in order to get such a near-optimal performance, the
seller does not really need to have full knowledge of the bidders' population; he
just needs to know the expectation of the second-highest order statistic of the
valuation distribution, that is, (a good estimate of) the \emph{expected}
second-highest bid is enough. Finally, we demonstrate how this approximation ratio
deteriorates as we gradually relax our distributional assumptions.

\subsection{Related Work}
\label{sec:related}
The seminal reference in auction theory is the work of \citet{Myerson1981a} who
completely characterized the revenue-maximizing auction in single-item settings with
bidder valuations drawn from independent (but not necessarily identical)
distributions. Under his standard regularity condition (see
\cref{sec:lambdareg-model}), this optimal auction has a very simple description when
the valuation distributions are identical: it is a second-price auction with a
reserve. Furthermore, there is an elegant, closed-form formula that gives the
reserve price (see \cref{sec:model}).

One can achieve good, constant approximations to that optimal revenue by using even
simpler auctions, namely \emph{anonymous pricing} mechanisms. These mechanisms offer
the same take-it-or-leave-it price to all bidders, and the item is sold to someone
who can afford it (breaking ties arbitrarily). An upper bound of $e/(e-1)\approx
1.58$ on the approximation ratio of anonymous pricing can be shown from the work of
\citet{Chawla2010a}.
\citet{Blumrosen2008a} study the asymptotic performance of
pricing when the number of bidders grows large and demonstrate a lower bound on the
approximation ratio of $0.88/0.65=1.37$ for anonymous pricing.
If we allow for non-continuous distributions that have point-masses, then
\citet{Duetting2016} provide a matching lower bound of $e/(e-1)$. Although the class
of MHR distributions (see \cref{sec:lambdareg-model}) is a natural restriction of
Myerson's regularity, that has been extensively studied in optimal auction theory,
mechanism design and complexity to derive powerful positive results (see, e.g.,
\citep{Hartline2009a,Bhattacharya2010a,Dhangwatnotai2014a,babaioff2017posting,Daskalakis2012b,Cai2011b,gkyr2015,gkl2017}),
no better bounds are known for anonymous pricing in this class. This is one of our
goals in this paper.

\Citet{SchweizerSzech2019} propose a quantitative notion of regularity, termed
$\lambda$-regularity (see \cref{sec:lambdareg-model}), that allows for a smooth
interpolation between the general class of regularity à la Myerson and its MHR
restriction. This is essentially equivalent to the notion of $\alpha$-strong
regularity of \citet{Cole2014a} (for $\alpha=\lambda -1$) and $\rho$-concavity of
\citet{Caplin:1991aa} (for $\rho=-\lambda$). These parametrizations have proved very
useful in developing a fruitful and more ``fine-grained'' theory of optimal auctions
(see, e.g., \citep{Cole2017,Ewerhart:2013aa,Mares:2011aa,Mares:2014aa}).

Although not immediately related to our model, an important line of work studies the
performance of ``simple'' auctions, such as pricing and auctions with reserves, for
the more general case where bidders' valuations may be non-identically distributed.
In such settings, the elegance of Myerson's characterization is not in effect any
more, and the optimal auction can be rather complicated. Nevertheless, in an
influential paper, \citet{Hartline2009a} showed that, for regular distributions, a
second-price auction with a single anonymous reserve guarantees a $4$-approximation
to the optimal ratio, and also provided a lower bound of $2$. This upper bound was
subsequently improved to $e\approx 2.72$ by \citet{Alaei2015}, achieved even by the
simpler class of anonymous pricing mechanisms. At the same paper, they also provided
a lower bound of $2.23$ for the approximation ratio of anonymous pricing for
non-i.i.d.\ bidders. This was recently improved to $2.62$~\citep{Jin2018}
and proven to be tight by~\citet{Jin:2019aa}.
For bounds on the approximation ratios between different
pricing and reserve mechanisms, under various assumptions on the underlying
distributions and the order of the bidders' arrival,
see~\citep{Alaei2015,Duetting2016,Jin2018,Chawla2010a} and \citep[Chapter~4]{Hartlinea}.
For anonymous pricing beyond the standard setting of linear utilities see the very recent work of~\citet{Feng:2019aa}.

Finally, we briefly mention that there is a very rich theory about sequential
pricing that deals with dynamically arriving buyers and which is inspired by and
related to secretary-like online problems and the powerful theory of prophet
inequalities. See, e.g.,
\citep{Hajiaghayi2007a,Kleinberg:2012,Alaei2014,Yan2011,Cesa-Bianchi2015,Chawla2010a,Correa:2019aa}. An intriguing equivalence between pricing and threshold stopping rules was recently established by~\citet{Correa_2019}.
In particular, \citet{Correa2017} showed an upper bound of $1.34$ on the approximation ratio of sequential pricing in the i.i.d.\ auction model which translates to the same bound for the i.i.d.\ prophet setting; this resolved a long-standing open question from~\citet{Hill:1982aa}.
Similarly, it is not difficult to see that our setting of regular i.i.d.\ anonymous pricing corresponds to single-threshold rules for the i.i.d.\ prophet model, for which a tight bound of $1.58$ is known~\citep{Hill:1982aa,Ehsani:2018aa}.

\subsection{Our Results}

In this paper we study the performance of anonymous pricing mechanisms in
single-item auction settings with $n$ bidders that have i.i.d.\ valuations from the
same regular distribution $F$. These mechanisms are extremely simple: the seller
simply offers the same take-it-or-leave-it price $p$ to all potential buyers; the
item is then sold to a buyer that can meet this price, that is, has a valuation
greater than or equal to $p$; the winning bidder pays $p$ to the seller. Our benchmark
is the seller's expected revenue (with respect to his incomplete, prior knowledge of
the buyers' bids via distribution $F$) and we compare against the maximum revenue
achievable by any auction. For our particular model, this optimal auction is a
second-price auction with a reserve~\citep{Myerson1981a}.

Our main result (\cref{sec:upper}; see also \cref{fig:approx_upper}) is an explicit,
closed-form upper bound on the approximation ratio of the revenue of anonymous
pricing for MHR distributions. As the number $n$ of buyers grows large, this ratio
tends to the optimal value of $1$, at a rate of $1+O(\ln\ln n/\ln n)$
(\cref{th:main_upper}). Additionally, we design an upper bound that is fine-tuned to
handle also small values of $n$ (\cref{th:main_upper_small}), and using this we
provide a global, worst-case (with respect to $n$) upper bound of $1.35$ on the
approximation ratio. Previously, only an upper bound of $e/(e-1)\approx 1.58$ was
known (for any value of $n$), holding for the entire class of regular distributions.

In \cref{sec:prior_indi} we demonstrate how the aforementioned positive guarantee on
the revenue of anonymous pricing can still be (within an exponentially decreasing
\emph{additive} constant) achieved even if the seller does not have full knowledge
of the prior distribution $F$ (see \cref{fig:approx_lower}). In particular
(\cref{cor:upper_bound_prior_indi}), we give an explicit formula for such a ``good''
pricing rule that only depends on the expectation of the second-highest order
statistic of $F$.

To complete the picture, in \cref{sec:lower} we prove that our upper bound analysis
is essentially tight, by showing that the exponential distribution provides an
(almost) tight gap instance between the revenue of anonymous pricing and that of the
optimal auction (\cref{th:lower_expo}; see also \cref{fig:approx_lower}).

Finally, in~\cref{sec:lambdareg} we relax our MHR assumption, allowing for
$\lambda$-regular valuation distributions. This provides a smooth, parametrized
generalization of the MHR condition ($\lambda=0$), all the way to the entire class
of standard (Myersonian) regularity ($\lambda=1$). Extending our ideas
from~\cref{sec:MHR}, we are able to provide upper (\cref{thm:regularuppfix}) and
lower (\cref{thm:regularlowfix}) bounds on the approximation ratio of anonymous
pricing, for all $\lambda\in[0,1]$ (see also \cref{fig:regupplowbounds}). We
conclude in \cref{sec:lambda_reg_asy}, by looking how these bounds behave in the
limit as the number of bidders grows arbitrarily large; we derive a tight value for
the approximation ratio as a function of $\lambda$, which ranges smoothly from
optimality for MHR distributions ($\lambda=0$) to $e/(e-1)\approx 1.58$ for the most
general case of regular distributions ($\lambda=1$).

We conclude in~\cref{sec:conclusion} with some open questions for future work.

\subsubsection{Techniques}

Our upper bound technique differs from related previous
approaches~\cite{Chawla2010a,Alaei2015} in that we do not use the ex-ante relaxation
of the revenue-maximization objective. Instead, we deploy explicit upper bounds on
the optimal revenue (\cref{sec:bounds_optimal_rev}) that depend on key parameters of
the valuation distribution $F$, namely its order statistics and its monopoly
reserve. Then, we pair these with a range of critical properties of
$\lambda$-regular distributions that we develop in \cref{sec:MHR_props,sec:lambda_reg-props}. We believe
that some of these auxiliary results may be of independent interest, in particular
the order statistics tail-bounds
of~\cref{lemma:bound_tail_orderstats,lemma:bound_tail_regular} and the
reserve-quantile optimal revenue bound of \cref{lem:bounds_reserve_price} for the
special case of MHR distributions.

Our lower bounds are constructed by means of explicitly defining a family of
$\lambda$-regular, continuous valuation distributions
(see~\eqref{eq:pareto_instances}), that act as ``bad'' instances for any $\lambda$.
We achieve this by generalizing an instance by~\citet{Duetting2016} (tailored to the
special case of regular distributions) to work for general $\lambda$'s, while at the
same time ``smoothing it out'' to satisfy continuity.

\section{Model and Notation}
\label{sec:model}

A seller wants to sell a single item to $n\geq 2$ bidders. The valuations of the
bidders for the item are i.i.d.\ from a continuous probability distribution
supported over an interval $D_F\subseteq [0,\infty)$, with cdf $F$ and pdf $f$.
Throughout this paper we will assume that $F$ is $\lambda$-regular, for some real parameter $\lambda\in[0,1]$ (for formal definitions and discussion, see~\cref{sec:lambdareg-model} right below).
For a random variable $X\sim F$ drawn from $F$ and $1\leq k\leq n$, we will use
$\orderstat{X}{k}{n}$ to denote the $k$-th lowest order statistic out of $n$ i.i.d.\
draws from $F$. That is, $\orderstat{X}{1}{n}\leq \orderstat{X}{2}{n}\leq\dots\leq
\orderstat{X}{n}{n}$. For completeness and ease of reference, we discuss some useful
properties of order statistics in \cref{append:prob_basics}.

A pricing mechanism that offers a take-it-or-leave-it price of $p\in D_F$ to all
bidders gives to the seller an expected revenue of
$$
\pricep{F}{n}{p}\equiv p[1-F^n(p)]\;,
$$
since the probability of no bidder being able to afford price $p$ is $F^n(p)$. We
will refer to such a mechanism simply as \emph{(anonymous) pricing}. Thus, the
optimal (maximum) revenue achievable via pricing is
$$
\price{F}{n}\equiv\sup_{p\in D_F}\pricep{F}{n}{p}\;.
$$
On the other hand, as discussed in the introduction, the optimal revenue attainable
by any mechanism may be higher; as a matter of fact, \citet{Myerson1981a} showed
that it is achieved by a second-price auction with a reserve equal to the
\emph{monopoly reserve}\footnote{As will become clearer in the
following~\cref{sec:lambdareg-model}, this quantity is well-defined for all
$\lambda$-regular distributions with $\lambda\in[0,1)$. For the special case of
$\lambda=1$, it might happen that there are multiple maximizers
in~\eqref{eq:monopoly_price}, or even none. To formally deal with such pathological
cases, in the former we can take $r^*=\inf\argmax_{r\in D_F} r(1-F(r))$. In the
latter we can slightly abuse notation and use $r^*=\infty$, which is essentially
equivalent to using an arbitrarily large price to approximate within arbitrary
accuracy the value of $\sup_{r\in D_F} r(1-F(r))$; then, the corresponding reserve
quantile is $q^*=0$ and maximizes the revenue curve in~\eqref{eq:revenue_curve} (for a
more detailed and rigorous discussion of this issue see, e.g., \citep[Appendix~1]{Fu2015}
and \citep[Appendix~C]{gk2014}.) The aforementioned choices do not affect the
validity of any of the results in the rest of our paper.}
\begin{equation}
\label{eq:monopoly_price}
r^*\equiv\argmax_{r\in D_F} r(1-F(r))\;.
\end{equation}
of the valuation
distribution. We denote this optimum revenue by $\myerson{F}{n}$, and it can be
shown that
$$
\myerson{F}{n}\equiv\expect{\max\sset{0,\phi(\orderstat{X}{n}{n})}}\;,
$$
where $\phi(x)=x-\frac{1-F(x)}{f(x)}$ is the (nondecreasing) virtual valuation
function of $F$ (see \cref{sec:lambdareg-model}) and $\orderstat{X}{n}{n}$ its maximum
order statistic. Keep in mind that, due to the monotonicity of $\phi$ and the
definition of the reserve $r^*$, we know that $\phi(x)\geq 0$ for all $x\geq r^*$.

Sometimes it is more convenient to work in quantile space instead of the actual
valuation domain. More precisely, the quantile of distribution $F$ corresponding to
a value $x\in D_F$ is $q(x)=1-F(x)$. Using this, we can define what is known as the
\emph{revenue curve} of distribution $F$, by
\begin{equation}
\label{eq:revenue_curve}
R(q)\equiv F^{-1}(1-q)\cdot q\;.
\end{equation}
In other
words, if $p\in D_F$ is a price and $q$ is its corresponding quantile, then $R(q)$
is the expected revenue of selling the item to a single bidder, using a price $p$.
Thus, the monopoly reserve quantile $q^*$ that corresponds to the monopoly reserve
$r^*$ defined in~\eqref{eq:monopoly_price} is exactly a maximizer of the revenue curve $R(q)$. So, for a
single bidder $(n=1)$: $$\myerson{F}{1}=\price{F}{1}=\sup_{p\in
D_F}p(1-F(p))=\sup_{q\in [0,1]} R(q)=R(q^*)\;.$$ In general though for more players
($n\geq 2$) this is not the case, and our goal in this paper is exactly to study how
well the optimal revenue $\myerson{F}{n}$ can be approximated by pricing
$\price{F}{n}$. That is, we want to bound the following approximation ratio:
$$
\apx{F}{n}\equiv\frac{\myerson{F}{n}}{\price{F}{n}}\;.
$$

Finally, we use $H_n$ to denote the $n$-th
harmonic number $H_n=\sum_{i=1}^n\frac{1}{i}$, $\gamma\approx 0.577$ for the
Euler-Mascheroni constant (see also \cref{lem:harmonic_bounds_sequence}) and $\Gamma$, $\mathrm{B}$ for the standard gamma and beta functions: $\Gamma(x)=\int_0^{\infty}t^{x-1}e^t\,dt$,
$\mathrm{B}(x,y)=\int_0^1 t^{x-1} (1-t)^{y-1}\,dt$.
Recall that $\Gamma(n+1)=n!$ for any nonnegative integer $n$ and $\mathrm{B}(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$  for all reals $x,y>0$ (see, e.g., \citep[Chapter~5]{olveretal:10}).

\subsection{\texorpdfstring{$\lambda$}{lambda}-Regular Distributions}
\label{sec:lambdareg-model}

Consider a continuous distribution $F$ supported over an interval $D_F$ of
nonnegative reals, and a real parameter $\lambda\in[0,1]$. We will say that $F$ is
\emph{$\lambda$-regular} if its \emph{$\lambda$-generalized virtual valuation}
function $$\phi_\lambda(x) \equiv \lambda \cdot x-\frac{1-F(x)}{f(x)}$$ is
monotonically nondecreasing in $D_F$. From~\citet[Proposition~1(iii)]{SchweizerSzech2019}, this can be equivalently restated as
$$
\begin{cases}
[1-F(x)]^{-\lambda}\;\;\text{is convex}, &\text{if}\;\; \lambda\in (0,1]\;,\\
\ln[1-F(x)]\;\;\text{is concave}, &\text{if}\;\;\lambda=0\;.
\end{cases}
$$
We will use $\mathcal{D}_{\lambda}$ to denote the family of all $\lambda$-regular
distributions. It is not difficult to see that, for any $0\leq\lambda \leq
\lambda'\leq 1$, any $\lambda$-regular distribution is also $\lambda'$-regular. In
other words, $\mathcal{D}_{\lambda}\subseteq\mathcal{D}_{\lambda'}$. As a matter of fact, this hierarchy is strict (as demonstrated by the distributions defined in~\eqref{eq:pareto_instances}).

For the special case of $\lambda=1$, the above definition recovers exactly the
standard notion of regularity à la~\citet{Myerson1981a}. Based on this, for
simplicity and consistency, we will feel free in such cases to drop the $\lambda=1$
subscripts and refer to the corresponding distributions simply as \emph{regular} and
to the function $\phi_1(x)=\phi(x)$ as the \emph{virtual valuation}. An equivalent
way of looking at regularity, is that the revenue curve defined
in~\eqref{eq:revenue_curve} must be concave.

On the other extreme of the range, for $\lambda=0$ we get the definition of
\emph{Monotone Hazard Rate (MHR)} distributions.\footnote{A standard reference for
MHR distributions is that from~\citet{Barlow1964}. For an in-depth treatment of the
subject, we refer to the book of~\citet[Chapter~2]{Barlow1996}.} Intuitively, MHR
distributions have exponentially decreasing tails. Although they represent the
strictest class within the $\lambda$-regularity hierarchy, they are still general
enough to give rise to a wide family of natural distributions, like the uniform,
exponential, normal and gamma.

Given the above discussion, $\lambda$-regularity can be seen as a quantitative
measure of the ``regularity'' of the distribution, interpolating smoothly between
MHR ($\lambda=0$) and Myerson-regular ($\lambda=1$) distributions. It will also be
convenient to define, for each $\lambda\in[0,1]$, the worst-case approximation ratio
among all $\lambda$-regular distributions:

\[\apx{n}{\lambda}\equiv\sup_{F\in\mathcal{D}_{\lambda}}\apx{F}{n}=\sup_{F\in\mathcal{D}_{\lambda}}\frac{\myerson{F}{n}}{\price{F}{n}}\;.\]
This will be the main quantity of interest throughout our paper.

\section{Preliminaries}
\subsection{Bounds on the Optimal Revenue}
\label{sec:bounds_optimal_rev}
In this section we collect the bounds on the
optimal revenue $\myerson{F}{n}$ that we will use for our main positive results in
\cref{sec:upper,sec:lambdareg} to bound the approximation ratio of pricing. They rely on the regularity of the valuation distribution. The first one is essentially a refinement of
the well-known Bulow-Klemperer bound \cite{Bulow1996} (see, e.g., \citep[Corollary~5.3]{Hartlinea}), and it was proven by
\citet{Fu2015}:
\begin{lemma}[\citet{Fu2015}]
\label{lemma:opt_bound_Fu_et_al} For $n$ bidders with i.i.d.\ values from a
regular distribution $F$,
$$
\myerson{F}{n}\leq \expectsmall{\orderstat{X}{n-1}{n}} + R(q^*)(1-q^*)^{n-1}\;,
$$
where $X\sim F$ and $R$ is the revenue curve of $F$ and $q^*$ is the quantile
corresponding to the monopoly reserve price $r^*$ of $F$, $q^*=1-F(r^*)$.
\end{lemma}
As an immediate consequence, the bound above holds also for the more restricted classes of
$\lambda$-regular distributions, for any $\lambda\in [0,1]$, and in particular for
MHR distributions (see also the discussion in \cref{sec:model}).

Our second bound on the optimal revenue, designed particularly for MHR
distributions, is a new one and might be of independent interest also for future
work:
\begin{lemma}
\label{lem:opt_bound_2} For every MHR distribution $F$ with monopoly reserve price
$r^*$ and quantile $q^*=1-F(r^*)$, and any positive integer $n$,
$$
\myerson{F}{n} \leq  r^*\int_{0}^{q^*}\frac{1-(1-z)^{n}}{z}\; dz\;.
$$
\end{lemma}
\begin{proof} Fix an MHR distribution $F$, with monopoly reserve price $r^*$ and
corresponding quantile $q^*$. Then, we know that for the virtual valuation (see
\cref{sec:model}) it is $$\phi(r^*)=r^*-\frac{1-F(r^*)}{f(r^*)}\geq 0\;.$$ Also, from
the MHR condition, for any $x\geq r^*$ it must be that $$\frac{f(r^*)}{1-F(r^*)} \leq
\frac{f(x)}{1-F(x)}\;.$$ Combining the above we get that, for all $x\geq r^*$,
\begin{equation}
\label{eq:helper_bound_reserve} 1-F(x)\leq f(x)\cdot \frac{1-F(r^*)}{f(r^*)} \leq
r^* f(x)\;.
\end{equation}
Fix also a positive integer $n$, and let $X\sim F$. Then (see also
\cref{append:prob_basics}) the maximum order statistic $\orderstat{X}{n}{n}$ is
distributed according to $F^n$. Observe that (see also \cref{sec:model})
$$
\frac{\partial\, \pricep{F}{n}{x}}{\partial\, x}=\frac{\partial\,
x(1-F^n(x))}{\partial\, x}=1-F^n(x)-nxF^{n-1}(x)f(x)
$$
and thus
\begin{align*}
\myerson{F}{n}
    &= \expect{\max\sset{0,\phi(\orderstat{X}{n}{n})}}\\
    &= \int_{r^*}^{\infty} \phi(x)\, dF^n(x)\\
    &= \int_{r^*}^{\infty} \left(x-\frac{1-F(x)}{f(x)}\right)n F^{n-1}(x) f(x)\, dx\\
    &= \int_{r^*}^{\infty} nxF^{n-1}(x)f(x)-n(1-F(x))F^{n-1}(x)  \, dx\\
    &= \int_{r^*}^{\infty} - \frac{\partial\, \pricep{F}{n}{x}}{\partial\, x} + 1-F^n(x)-n(1-F(x))F^{n-1}(x) \, dx\\
    &= \pricep{F}{n}{r^*}+ \int_{r^*}^{\infty} 1+(n-1)F^n(x)-nF^{n-1}(x) \, dx\;.
\end{align*}
Also, due to \eqref{eq:helper_bound_reserve}, for all $x\geq r^*$:
\begin{align*}
1-F^n(x)-n(1-F(x))F^{n-1}(x)
  &=\left[\frac{1-F^n(x)}{1-F(x)}-nF^{n-1}(x) \right] (1-F(x))\\
  &\leq r^* \left[\frac{1-F^n(x)}{1-F(x)}-nF^{n-1}(x) \right] f(x)\;.
\end{align*}

By performing a change of variable to quantile space, that is setting $z=1-F(x)$ and
observing that $\frac{d\, z}{d\, x}=-f(x)$ and $1-F(r^*)=q^*$, we get that
\begin{align*}
\int_{r^*}^{\infty} 1-F^n(x)-n(1-F(x))F^{n-1}(x) \, dx
    &\leq r^*\int_0^{q^*}\frac{1-(1-z)^n}{z}-n(1-z)^{n-1}\, dz\\
    &= -r^*\left[1-(1-q^*)^n\right]+r^*\int_0^{q^*}\frac{1-(1-z)^n}{z}\, dz\\
    &= -\pricep{F}{n}{r^*}+r^*\int_0^{q^*}\frac{1-(1-z)^n}{z}\, dz\;.
\end{align*}
Thus,
$$
\myerson{F}{n} \leq r^*\int_0^{q^*}\frac{1-(1-z)^n}{z}\, dz\;.
$$\end{proof}

\subsection{MHR Distributions}
\label{sec:MHR_props}
In this section we state some properties of MHR distributions that
will play a critical role into deriving our main results in the rest of the paper.
\Cref{lemma:bound_tail_orderstats}, in particular, might be of independent
interest, since it is providing powerful tail-bounds with respect to the order
statistics of the distribution:

\begin{lemma}
\label{lemma:bound_tail_orderstats} For any continuous MHR random variable $X$,
integers $1\leq k \leq n$ and real $c\in[0,1]$,
$$
\prob{X < c\cdot\expectsmall{\orderstat{X}{k}{n}}}\leq 1- e^{-c(H_{n}-H_{n-k})}\;.
$$
\end{lemma}
\begin{proof}\
Let $E$ denote an exponential random variable and also let $F$ and $G$ denote the cumulative probability
functions of $X$ and $\orderstat{X}{k}{n}$, respectively. Then (see also
\cref{append:prob_basics})
\begin{equation}
\label{eq:pdf_ordstat_1}
\frac{dG(y)}{dy}=k\binom{n}{k}F^{k-1}(y)(1-F(y))^{n-k} \frac{dF(y)}{dy}\;,
\end{equation} for almost all $y\in [0,\infty)$. To simplify notation, also let $\nu =
\expectsmall{\orderstat{X}{k}{n}}$. Our goal then is to upper-bound
$F(c\nu)$, i.e.\ lower-bound $1-F(c\nu)$. Since $F$ is MHR, $\zeta(c)=\ln (1-F(c\nu))$ is a
concave function of $c$ with $\zeta(0)=0$; thus, assuming $c\in[0,1]$ and applying Jensen's inequality,
\begin{equation*}
\ln (1-F(c\nu)) \geq c\ln(1-F(\nu))\geq c\expect{\ln(1-F(\orderstat{X}{k}{n}))}=c\int_0^\infty \ln(1-F(y))\,d G(y)\;;
\end{equation*}
the integral can be further simplified using \eqref{eq:pdf_ordstat_1} and the changes of variables $u=F(y)$, $t=-\ln(1-u)$;
\begin{align*}
c\int_0^\infty \ln(1-F(y))\,d G(y)
    &=c k\binom{n}{k} \int_0^\infty \ln(1-F(y)) F^{k-1}(y)(1-F(y))^{n-k} \,d F(y)\\
    &=c k\binom{n}{k} \int_0^1 \ln(1-u) u^{k-1}(1-u)^{n-k} \,d u\\
    &=-c k\binom{n}{k} \int_0^\infty t (1-e^{-t})^{k-1}(e^{-t})^{n-k} \,d t\\
    &= -c \expect{\orderstat{E}{k}{n}}\\
    &= -c(H_{n}-H_{n-k})\;,
\end{align*}
the last equality following from
\cref{append:prob_basics}. So, applying the exponential function on both sides,
finally we get the desired
$$
1-F(c\nu) \geq e^{-c(H_{n}-H_{n-k})}\;.
$$
\end{proof}

The next lemma states some useful bounds on the monopoly reserve of an MHR distribution:
\begin{lemma}
\label{lem:bounds_reserve_price}
For any MHR distribution with expectation $\mu$, monopoly reserve $r^*$ and
corresponding quantile $q^*$:
\begin{enumerate}
\item $q^*\geq 1/e$;
\item $\ln(1/q^*)\cdot \mu \leq r^* \leq \frac{\ln(1/q^*)}{1-q^*}\cdot \mu$.
\end{enumerate}
\end{lemma}
\begin{proof}
The first property is by now almost folklore, see e.g.~\citep[Lemma~1]{aggarwal2009efficiency}
or \citep[Claim~B.2]{Babaioff2015}. Alternatively, it can be seen as the limiting case of \cref{lemma:regularproperties} as $\lambda\to 0$, since $\lim_{\lambda\to 0^+}(1-\lambda)^{1/\lambda}=1/e$.

For the second property, applying \citep[Corollary 3.10]{Barlow1964} for the
first-order moments ($r=1$), we get that for any quantile $q=1-F(x)$ of our MHR
distribution with $q\geq 1/e$, it must be that
$$
-\ln q \cdot \mu \leq x \leq \left[\int_0^1 q^y\,dy\right]^{-1}\cdot \mu =
\left(\frac{q-1}{\ln  q}\right)^{-1} \mu\;.
$$
By the first property of our lemma, it is valid to use the above inequality with
the monopoly reserve quantile $q^*=1-F(r^*)$ and so, by setting $q\gets q^*$ and
$x\gets r^*$ we have that
$$
-\ln(q^*)\mu \leq r^* \leq -\frac{\ln(q^*)}{1-q^*}\mu\;.
$$
\end{proof}

Finally, the following lemma shows that the high-order statistics of MHR
distributions are ``well-behaved'', in the sense that they cannot be away from the
expectation:
\begin{lemma}
\label{lem:bound_2ndordstat_mean_MHR} For any MHR random variable $X$ and integer
$n\geq 2$,
$$
\expectsmall{\orderstat{X}{n-1}{n}}\geq \left(1-\frac{H_n-1}{n-1}\right)\cdot
\expectsmall{X}\;.
$$
\end{lemma}
\begin{proof} For convenience denote $\mu=\expectsmall{X}$ and
$\nu=\expectsmall{\orderstat{X}{n-1}{n}}$. From
\citet[Lemma~5.3]{babaioff2017posting} we know that, since $X$ is MHR, its
highest-order statistic is upper bounded by
$$
\expectsmall{\orderstat{X}{n}{n}}\leq H_n\cdot \mu\;.
$$
Using this we get that:
$$
n\cdot\mu = \expect{\sum_{i=1}^n
\orderstat{X}{i}{n}}=\sum_{i=1}^{n-1}\expectsmall{\orderstat{X}{i}{n}}+\expectsmall{\orderstat{X}{n}{n}}\leq
(n-1)\nu + H_n\cdot \mu\;,
$$
and thus $(n-1)\nu \geq (n-H_n)\mu$, or equivalently, $\nu \geq
\frac{(n-H_n)}{n-1}\mu=\left(1-\frac{H_n-1}{n-1}\right)\mu$.
\end{proof}

\subsection{\texorpdfstring{$\lambda$}{lambda}-Regular Distributions}
\label{sec:lambda_reg-props}

The following lemmas are the counterparts of \cref{lemma:bound_tail_orderstats} and
\cref{lem:bounds_reserve_price} (Property~1), extending them to $\lambda$-regular
distributions for $\lambda>0$.

\begin{lemma}
\label{lemma:bound_tail_regular}
Let $X$ be a $\lambda$-regular distribution, for $\lambda\in(0,1]$. Then, for any
integer $1\leq k\leq n$ and real $c\in[0,1]$,
$$
\prob{X \leq c\cdot\expectsmall{\orderstat{X}{k}{n}}}\leq 1-
\left(1+c\left(\frac{n!\Gamma(n+1-k-\lambda)}{(n-k)!\Gamma(n+1-\lambda)}-1\right)\right)^{-1/\lambda}\;.
$$
\end{lemma}

\begin{proof}
Let $F$ and $G$ be the cumulative density functions of $X$ and $\orderstat{X}{k}{n}$
respectively. Let also $\nu=\expectsmall{\orderstat{X}{k}{n}}$. As $F$ is
$\lambda$-regular, the function $\zeta(c)=(1-F(c\nu))^{-\lambda}$ is a convex
function on $c$, with $\zeta(0)=1$; thus, assuming $c\in[0,1]$, and applying
Jensen's inequality,

\begin{equation}
\zeta(c)\leq 1+c(\zeta(1)-1)=1+c((1-F(\nu))^{-\lambda}-1)\leq 1+c(\expectsmall{(1-F(\orderstat{X}{k}{n}))^{-\lambda}}-1)\;.
\label{eq:zeta}\end{equation}

The rest of the proof follows exactly as in the proof of
\cref{lemma:bound_tail_orderstats}. We use a change of variable to compute the
expected value:

\begin{align*}
\expectsmall{(1-F(\orderstat{X}{k}{n}))^{-\lambda}}
&=\int_0^\infty (1-F(y))^{-\lambda}dG(y)\\
&=k\binom{n}{k}\int_0^\infty F(y)^{k-1}(1-F(y))^{n-k-\lambda}dF(y)\\
&=k\binom{n}{k}\int_0^1 u^{k-1}(1-u)^{n-k-\lambda}du\\
&= k\binom{n}{k} \mathrm{B}(k,n+1-k-\lambda)\\
&=\frac{n!\Gamma(n+1-k-\lambda)}{(n-k)!\Gamma(n+1-\lambda)}\;.
\end{align*}
Plugging
this into \eqref{eq:zeta} and rearranging gives us the desired result.
\end{proof}

\begin{lemma}[\citet{SchweizerSzech2019}]
\label{lemma:regularproperties}
For any $\lambda$-regular distribution with $\lambda\in(0,1]$ and monopoly quantile $q^\ast$,
\begin{equation*}
q^\ast\geq(1-\lambda)^{1/\lambda}\;.
\end{equation*}
\end{lemma}

\section{Bounds for MHR Distributions}
\label{sec:MHR}

To facilitate us with stating and proving our bounds for the approximation
ratio of pricing, we define the following auxiliary function $g_n:[0,\infty)\longrightarrow
[0,\infty)$, for any positive integer $n$,
\begin{equation}
\label{eq:gdef} g_n(c) \equiv c[1-(1-e^{-c(H_n-1)})^n]
\end{equation}
and its (unique) maximizer in $[0,1]$ by
\begin{equation}
\label{eq:cparsdef} c_n \equiv \argmax_{c\in[0,1]} g_n(c)\;.
\end{equation}
In~\cref{app:auxfunprops} we prove some properties of $g_n$ that will be used in the rest of this section.

\subsection{Upper Bounds}
\label{sec:upper} This section is dedicated to proving the main result of our paper.
First (\cref{th:main_upper}) we show that pricing is indeed asymptotically optimal
with respect to revenue and then (\cref{th:main_upper_small}) we also provide a more
refined upper-bound on the approximation ratio that is fine-tuned to work well for a
small number of bidders $n$. As we will see in the following \cref{sec:lower}, our
upper bound analysis of this section is essentially tight (see also
\cref{fig:approx_lower}).

\begin{figure}
  \centering
\begin{tikzpicture}
\input{plot_mhr_upper}
\end{tikzpicture}
\Description{The upper bounds on the approximation ratio of anonymous pricing for
$n$ i.i.d.\ bidders with MHR valuations, given by~\cref{th:main_upper} and
\cref{th:main_upper_small}. The best (smallest) of the two converges to the optimal
value of $1$ as the number of bidders grows large, at a rate of $1+O\left(\ln \ln
n/\ln n\right)$. A single, unified plot of this can be seen in
\cref{fig:approx_lower}, together with a matching lower bound. In the worst case
($n=3$), our upper bound is at most $1.354$.}
  \caption{The upper bounds on the approximation ratio $\apx{F}{n}$ of anonymous
  pricing for $n$ i.i.d.\ bidders with MHR valuations, given by~\cref{th:main_upper}
  (blue) and \cref{th:main_upper_small} (red). The best (smallest) of the two
  converges to the optimal value of $1$ as the number of bidders grows large, at a
  rate of $1+O\left(\ln \ln n/\ln n\right)$. A single, unified plot of this can be
  seen in \cref{fig:approx_lower} (black), together with a matching lower bound
  (red). In the worst case ($n=3$), our upper bound is at most $1.354$.}
\label{fig:approx_upper}
\end{figure}

\begin{theorem}
\label{th:main_upper}
Using the same take-it-or-leave-it price, to sell an item to $n$ buyers with i.i.d.\
valuations from a continuous MHR distribution $F$, is asymptotically optimal with
respect to revenue. In particular,
$$
\apx{F}{n}=1+O\left(\frac{\ln \ln n}{\ln
n}\right)\;.
$$
\end{theorem}
A plot of the exact values of this upper bound (given by~\eqref{eq:apx_bound_1} below) can be seen in~\cref{fig:approx_upper} (blue).
\begin{proof}
First notice that by using the monopoly reserve price $r^*$ of $F$ as a
take-it-or-leave it price to the $n$ bidders, we get an expected revenue of
\begin{equation}
\label{eq:price1_bound}
\pricep{F}{n}{r^*}
=r^*(1-F(r^*)^n)
=r^*[1-(1-q^*)^n]
= R(q^*)\frac{1-(1-q^*)^n}{q^*}\;,
\end{equation}
where $q^*=1-F(r^*)$ is the quantile of the monopoly reserve price, for which we know that $q^*\geq\frac{1}{e}$ (\cref{lem:bounds_reserve_price}), and $R$ denotes the revenue curve (see~\cref{sec:model}).

Next, for simplicity denote $\nu = \expect{\orderstat{X}{n-1}{n}}$.
For any real $c\in [0,1]$, if we offer a price of $c\cdot \nu$ we have
\begin{equation}
\label{eq:bound_price_second_order_c}
\pricep{F}{n}{c\nu}
=c\nu[1-F(c\nu)^n]
\geq c\nu\left[1-\left(1-e^{-c(H_n-1)}\right)^n\right]\;,
\end{equation}
the inequality holding due to \cref{lemma:bound_tail_orderstats} (for $k=n-1$). Optimizing with respect to $c$ we get that
\begin{equation}
\label{eq:bound_price_second_order_opt}
\price{F}{n} \geq \nu \max_{c\in[0,1]}g_n(c)\;.
\end{equation}

Using the two lower bounds \eqref{eq:price1_bound} and
\eqref{eq:bound_price_second_order_opt} on the pricing revenue, in conjunction with
the upper bound on the optimal revenue from \cref{lemma:opt_bound_Fu_et_al} we can
bound the approximation ratio of pricing by
\begin{align}
\apx{F}{n}&= \frac{\myerson{F}{n}}{\price{F}{n}} \notag\\
  &\leq \frac{\nu}{\nu \max_{c\in[0,1]}g_n(c)}+ \frac{R(q^*)(1-q^*)^{n-1}}{R(q^*)\frac{1-(1-q^*)^n}{q^*}}\notag\\
  &= \frac{1}{\max_{c\in[0,1]}g_n(c)} + \frac{q^*(1-q^*)^{n-1}}{1-(1-q^*)^n}\label{eq:apx_bound_3}\\
  & \leq \frac{1}{\max_{c\in[0,1]}g_n(c)} + \frac{(e-1)^{n-1}}{e^n-(e-1)^{n}} \label{eq:apx_bound_1}\\
  &= 1+O\left(\frac{\ln\ln n}{\ln n}\right)+O\left(\left(\frac{e}{e-1}\right)^{-n}\right)\;. \label{eq:apx_bound_2}
\end{align}
\Cref{eq:apx_bound_1} holds by observing that function
$x\mapsto\frac{x(1-x)^{n-1}}{1-(1-x)^n}$ is decreasing over $(0,1]$, for any $n\geq
2$, and taking into consideration that $q^*\geq 1/e$, while for
\eqref{eq:apx_bound_2} we make use of the asymptotics from  \cref{lem:3}. The upper
bound given by \eqref{eq:apx_bound_1} is plotted by the blue line
in~\cref{fig:approx_upper}.
\end{proof}

\begin{theorem}
\label{th:main_upper_small} The approximation ratio of the revenue obtained by using
the same take-it-or-leave-it price, to sell an item to $n$ buyers with i.i.d.\
valuations from a continuous MHR distribution $F$, is at most
$$
\apx{F}{n}\leq
\max_{q\in[1/e,1]}\min\sset{\frac{1}{1-(1-e^{-H_n+1})^n}+\frac{q(1-q)^{n-1}}{1-(1-q)^n},\frac{\int_0^q\frac{1-(1-z)^n}{z}\,dz}{1-(1-q)^n}}\;.
$$
In particular, the worst case (maximum) of this quantity is attained at $n=3$ and is
at most $\apx{F}{3}\leq 1.354$.
\end{theorem}
A plot of the exact values of this upper bound can
be seen in~\cref{fig:approx_upper} (red).
\begin{proof}
From \eqref{eq:apx_bound_3} in the proof of \cref{th:main_upper} we
can get the following upper bound on the approximation ratio, by using (possibly
suboptimally) $c\gets 1$ for the maximization operator:
$$
\apx{F}{n}\leq \frac{1}{g_n(1)} + \frac{q^*(1-q^*)^{n-1}}{1-(1-q^*)^n}
=\frac{1}{1-(1-e^{-H_n+1})^n}+\frac{q^*(1-q^*)^{n-1}}{1-(1-q^*)^n}\;.
$$
On the other hand, using the reserve price of $F$ as a price and combining the
guarantee of \eqref{eq:price1_bound} with the upper bound on the optimal revenue
from \cref{lem:opt_bound_2}, gives us
$$
\apx{F}{n} \leq \frac{r^*\int_{0}^{q^*}\frac{1-(1-z)^{n}}{z}\,
dz}{R(q^*)\frac{1-(1-q^*)^n}{q^*}}=
\frac{\int_0^{q^*}\frac{1-(1-z)^n}{z}\,dz}{1-(1-q^*)^n}\;,
$$
since $R(q^*)=r^*q^*$. Recalling that $q^*\in[1/e,1]$ and taking the best (i.e.,
minimum) of the two bounds above, finishes the proof.
\end{proof}

\subsection{Lower Bound}
\label{sec:lower} The lower bound instance of this section (\cref{th:lower_expo})
shows that our main positive result for the approximation ratio of pricing under MHR
distributions in \cref{th:main_upper} is essentially tight (see also
\cref{fig:approx_lower}). It is achieved by an exponential distribution instance.
Before proving it, we need the following auxiliary lemma about the maximizers of
functions $g_n$ that we introduced in \eqref{eq:gdef}. Its proof can be found in
\cref{app:auxfunprops}.

\begin{lemma}
\label{lem:propsg}
For any positive integer $n$, function $g_n$ (defined in
\eqref{eq:gdef}) has a unique maximizer. Furthermore, for all $n\geq 17$,
$$
\argmax_{c\geq 0} g_n(c) \leq 1\;.
$$
\end{lemma}

\begin{theorem}
\label{th:lower_expo}
For $n\geq 2$ bidders with exponentially i.i.d.\ valuations,
the approximation ratio of anonymous pricing is at least
$$ \apx{\mathcal{E}}{n}\geq\frac{1}{\max_{c\geq 0}g_n(c)}\;,$$
where function $g_n$ is defined in
\eqref{eq:gdef} and $\mathcal E$ is the exponential distribution. In particular, the upper
bound derived in the proof of \cref{th:main_upper} is tight (up to an exponentially
vanishing \emph{additive} factor).
\end{theorem}
A plot of the
lower bound given by the theorem above can be seen in \cref{fig:approx_lower} (red).
\begin{proof}
Let $X\sim \mathcal E$ be an exponential random variable.
Since the revenue of a second-price auction cannot be greater than the optimal one, we have
$$
\myerson{\mathcal{E}}{n}
\geq \expect{\orderstat{X}{n-1}{n}}
=H_n-1,
$$
where the equality is taken from~\cref{append:prob_basics}. Furthermore,
$$
\price{\mathcal E}{n}
= \sup_{x\geq 0}x\left(1-F_{\mathcal E}^n(x)\right)
= \sup_{x\geq 0}x\left[1-\left(1-e^{-x}\right)^n\right]
= (H_n-1)\max_{c\geq 0}g_n(c)\;.
$$
Putting the above together, we get the desired lower bound on the approximation
ratio.

For the tightness, we need to show that our lower bound is within an additive,
exponentially decreasing factor of the upper bound given in \eqref{eq:apx_bound_1}.
Since the second term in \eqref{eq:apx_bound_1} is at most
$O\left(\left(\frac{e}{e-1}\right)^{-n}\right)$, it is enough to show that, for a
sufficiently large number of bidders $n$,
$$
\max_{c\in[0,\infty)} g_n(c)= \max_{c\in[0,1]} g_n(c)\;.
$$
This is exactly what we proved in~\cref{lem:propsg}, for any $n\geq 17$.
\end{proof}

\subsection{Explicit Prices -- Knowledge of the Distribution}
\label{sec:prior_indi}
\begin{figure}
  \centering
\begin{tikzpicture}
\input{plot_mhr_lower}
\end{tikzpicture}
\Description{Bounds on the approximation ratio of anonymous pricing for
  $n=3$ up to $n=30$ i.i.d. bidders with MHR valuations: the upper bound on optimal
  pricing derived in \cref{sec:upper} (see also \cref{fig:approx_upper}),
  the lower bound given by \cref{th:lower_expo}, and the upper bound of
  pricing at the expected value of the second-highest order statistic, scaled down
  by parameter $c_n$, given in \cref{cor:upper_bound_prior_indi} of
  \cref{sec:prior_indi}. They are all (asymptotically) optimal, their (additive)
  difference decreasing exponentially fast. They all converge to the optimal value
  of $1$ at a rate of $1+O(\ln\ln n/\ln n)$.}
  \caption{Bounds on the approximation ratio of anonymous pricing for
  $n=3,\dots,30$ i.i.d.\ bidders with MHR valuations: the upper bound on optimal
  pricing (black) derived in \cref{sec:upper} (see also \cref{fig:approx_upper}),
  the lower bound (red) given by \cref{th:lower_expo}, and the upper bound of
  pricing at the expected value of the second-highest order statistic, scaled down
  by parameter $c_n$ (blue), given in \cref{cor:upper_bound_prior_indi} of
  \cref{sec:prior_indi}. They are all (asymptotically) optimal, their (additive)
  difference decreasing exponentially fast. They all converge to the optimal value
  of $1$ at a rate of $1+O(\ln\ln n/\ln n)$.}
\label{fig:approx_lower}
\end{figure}

Our main result from \cref{sec:upper} demonstrates that a seller, facing $n$ bidders
with i.i.d.\ valuations from an MHR distribution $F$, can achieve (asymptotically)
optimal revenue by using just an anonymous, take-it-or-leave-it price. Taking a
careful look within the proof of \cref{th:main_upper}, we see that this upper bound
is derived by comparing the optimal Myersonian revenue (via the bound provided by
\cref{lemma:opt_bound_Fu_et_al}) to that of two different anonymous pricings;
namely, first (see \eqref{eq:price1_bound}) we use the monopoly reserve $r^*$ of $F$,
and then (see \eqref{eq:bound_price_second_order_c} and \eqref{eq:bound_price_second_order_opt})
a multiple of the expectation $\nu=\expectsmall{\orderstat{X}{n-1}{n}}$ of the
second-highest order statistic of $F$, in particular $c_n\cdot \nu$ where $c_n=\argmax_{c\in[0,1]} g_n(c)$ was defined in~\eqref{eq:cparsdef}.
Although the latter price requires only the knowledge of
$\nu=\expectsmall{\orderstat{X}{n-1}{n}}$, that is not the case for the former;
determining the reserve price $r^*$ demands, in general, a detailed knowledge of the
distribution $F$: it is the maximizer of $r(1-F(r))$.

As a result, we would ideally like to provide a more robust solution, that would
still provide optimality but depend only on limited information about $F$. If we pay
even closer attention to the proof of \cref{th:main_upper}, and the derivation of
\eqref{eq:apx_bound_2} in particular, we will see that the summand of our upper
bound that corresponds to the pricing using $r^*$ is exponentially decreasing,
according to $\left(\frac{e}{e-1}\right)^{-n}$. Therefore, if we could show that the
expected revenue achieved by using an anonymous price of $c_n \nu$ is within a constant
factor from that of using an anonymous price of $r^*$, then we could deduce that using only price $c_n
\nu$ yields essentially the same approximation ratio (and in particular, asymptotically optimal revenue). We now proceed to formalize this line of reasoning.

\begin{lemma}
\label{lem:reserve_ordstat_comparison} For $n\geq 2$ bidders with i.i.d.\ valuations
from an MHR distribution $F$ with monopoly reserve $r^*$ and parameters
$c_n\in[0,1]$ given by \eqref{eq:cparsdef},
$$
\pricep{F}{n}{c_n\cdot \expectsmall{\orderstat{X}{n-1}{n}}}\geq
(1-o(1))\frac{e-1}{e} \cdot \pricep{F}{n}{r^*}\;,
$$
where $X\sim F$.
\end{lemma}
\begin{proof}
For convenience, denote $\mu=\expectsmall{X}$ and $\nu =
\expectsmall{\orderstat{X}{n-1}{n}}$. By the proof of \cref{th:main_upper} (see
\eqref{eq:bound_price_second_order_c} and \eqref{eq:bound_price_second_order_opt}) we know that
by offering an anonymous price of $c_n\cdot \nu$ gives us an expected revenue of at
least
\begin{equation*}
\pricep{F}{n}{c_n\cdot \nu} \geq \nu \max_{c\in[0,1]}g_n(c)
    \geq\max_{c\in[0,1]}g_n(c)\frac{n-H_n}{n-1}\cdot \mu\;,
\end{equation*}
the second inequality holding due to~\cref{lem:bound_2ndordstat_mean_MHR}.

On the other hand, from \eqref{eq:price1_bound} we know that using the reserve price
$r^*$ as an anonymous price to all bidders gives an expected revenue of at most
\begin{equation*}
\pricep{F}{n}{r^*} = r^*[1-(1-q^*)^n]
    \leq \frac{\ln(1/q^*)}{1-q^*}[1-(1-q^*)^n] \cdot \mu\;,
\end{equation*}
the inequality holding due to \cref{lem:bounds_reserve_price}.

Putting everything together, we finally get that
\begin{align}
\frac{\pricep{F}{n}{r^*}}{\pricep{F}{n}{c_n\nu}}
&\leq
\frac{\ln(1/q^*)}{1-q^*}[1-(1-q^*)^n]\frac{n-1}{n-H_n}\frac{1}{\max_{c\in[0,1]}g_n(c)}\label{eq:helper7}\\
&\leq \frac{e}{e-1}\frac{n-1}{n-H_n}\frac{1}{\max_{c\in[0,1]}g_n(c)}\notag\\
&\leq (1+o(1))\frac{e}{e-1}\;.\notag
\end{align}
The second inequality holds because $\frac{\ln(1/q^*)}{1-q^*}[1-(1-q^*)^n]\leq
\frac{\ln(1/q^*)}{1-q^*}\leq \frac{e}{e-1}$, since the function
$x\mapsto\frac{\ln(1/x)}{1-x}$ is decreasing for $x>0$ and $q^*\geq 1/e$ (from
Property~1 of \cref{lem:bounds_reserve_price}). The last inequality is a consequence
of \cref{lem:3} and the fact that $H_n\leq \ln(n)+1$.
\end{proof}

As discussed before, \cref{lem:reserve_ordstat_comparison} shows us that there
indeed exists an anonymous price that depends on the knowledge of only the
expectation of the second-highest order statistic of the valuation distribution and which,
furthermore, guarantees an (asymptotically) optimal revenue. We can even provide a
closed-form upper bound for it:
\begin{theorem}
\label{cor:upper_bound_prior_indi} Let $F$ be an MHR distribution and
$\orderstat{X}{n-1}{n}$ denote the second-highest out of $n$ i.i.d.\ draws from
$F$. Then, using an anonymous price of $c_n\cdot
\expectsmall{\orderstat{X}{n-1}{n}}$, where $c_n$ is given in \eqref{eq:cparsdef}, to
sell an item to $n\geq 2$ bidders with i.i.d.\ valuations from $F$, guarantees a
revenue with approximation ratio of at most
$$
\frac{\myerson{F}{n}}{\pricep{F}{n}{c_n\expectsmall{\orderstat{X}{n-1}{n}}}}
\leq
\frac{1}{\max_{c\in[0,1]}g_n(c)}\left[1+
\frac{1}{e}\frac{n-1}{n-H_n}\left(\frac{e-1}{e}\right)^{n-2}\right]\;.
$$
\end{theorem}
A plot of this upper bound can be seen in~\cref{fig:approx_lower} (blue).
\begin{proof} Simulating the proof of the approximation upper bound in
\cref{th:main_upper}, but now using \eqref{eq:helper7} to approximate
$\pricep{F}{n}{r^*}$ by $\pricep{F}{n}{c_n\expectsmall{\orderstat{X}{n-1}{n}}}$, the
derivation in \eqref{eq:apx_bound_3} gives us that
\begin{align*}
\frac{\myerson{F}{n}}{\pricep{F}{n}{c_n\expectsmall{\orderstat{X}{n-1}{n}}}}
&\leq \frac{1}{\max_{c\in[0,1]}g_n(c)}\\
&+ \frac{\ln(1/q^*)}{1-q^*}[1-(1-q^*)^n]\frac{n-1}{n-H_n}\frac{1}{\max_{c\in[0,1]}g_n(c)}\cdot \frac{q^*(1-q^*)^{n-1}}{1-(1-q^*)^n}\\
&=\frac{1}{\max_{c\in[0,1]}g_n(c)}\left[1+ \frac{n-1}{n-H_n}\ln(1/q^*)q^*(1-q^*)^{n-2}\right]\\
&\leq \frac{1}{\max_{c\in[0,1]}g_n(c)}\left[1+ \frac{1}{e}\frac{n-1}{n-H_n}\left(\frac{e-1}{e}\right)^{n-2}\right]\;,
\end{align*}
the last inequality coming from \cref{lem:helper_bound_1}, together with the fact
that $q^*\in[1/e,1]$ (see Property~1 of \cref{lem:bounds_reserve_price}).
\end{proof}

\section{Bounds for \texorpdfstring{$\lambda$}{lambda}-Regular Distributions}
\label{sec:lambdareg}
\begin{figure}
\centering
\scalebox{0.55}{
\begin{tikzpicture}
\input{plot_regular_5}
\end{tikzpicture}}
~
\scalebox{0.55}{
\begin{tikzpicture}
\input{plot_regular_20}
\end{tikzpicture}}
~
\scalebox{0.55}{
\begin{tikzpicture}
\input{plot_regular_100}
\end{tikzpicture}}
\Description{Upper and lower bounds on the approximation ratio of anonymous pricing for $n=5$ (left), $n=20$ (centre) and $n=100$ (right) bidders with i.i.d. $\lambda$-regular valuations, as a function of $\lambda$.}
\caption{Upper (\cref{thm:regularuppfix}) and lower (\cref{thm:regularlowfix}) bounds on the approximation ratio of anonymous pricing for $n=5$ (left), $n=20$ (centre) and $n=100$ (right) bidders with i.i.d.\ $\lambda$-regular valuations, as a function of $\lambda$.}
\label{fig:regupplowbounds}
\end{figure}

In this section we provide the generalized, $\lambda$-regular counterparts of our
main results for MHR distributions of the previous~\cref{sec:MHR}. In particular, we
provide upper (\cref{thm:regularuppfix}; cf.~\cref{th:main_upper}) and lower
(\cref{thm:regularlowfix}; cf.~\cref{th:lower_expo}) bounds on the approximation
ratio of anonymous pricing for $n$ bidders with i.i.d.\ $\lambda$-regular
valuations, and also derive an asymptotically tight expression for large $n$
(\cref{thm:regularinf}; cf.~\cref{th:main_upper}).

The following quantities will help us to state and prove our results in this section.
For an integer $n\geq 2$ and
$\lambda\in(0,1]$, we define the quantities $\beta_{n,\lambda}, a_{n,\lambda} > 0$
and the function $g_{n,\lambda}:[0,\infty)\rightarrow[0,\infty)$ as follows:
\begin{equation}
\label{eq:helperreg_ab}
    \beta_{n,\lambda} \equiv \frac{n!\Gamma(2-\lambda)}{\Gamma(n+1-\lambda)}=\prod_{k=2}^n\left(1-\frac{\lambda}{k}\right)^{-1},
    \qquad
    a_{n,\lambda} \equiv
      \begin{cases}
      \frac{(1-\lambda)^{1/\lambda}\left[1-(1-\lambda)^{1/\lambda}\right]^{n-1}}{1-\left[1-(1-\lambda)^{1/\lambda}\right]^n},
      &\text{if}\;\; \lambda\in (0,1)\;,\\
      \frac{1}{n}, &\text{if}\;\; \lambda=1\;,
      \end{cases}
\end{equation}
\begin{equation}
\label{eq:helperreg_g}
    g_{n,\lambda}(c) \equiv c\left[1-\left[1-\left[1+c\left(\beta_{n,\lambda}-1\right)\right]^{-1/\lambda}\right]^n\right]\;.
\end{equation}
The function $g_n$ introduced in \cref{eq:gdef} can be recovered from $g_{n,\lambda}$ in the limit $\lambda\rightarrow0$. Note also that $\beta_{n,\lambda}$ corresponds to the fraction in
\cref{lemma:bound_tail_regular} with $k=n-1$. Using Stirling's approximation (see,
e.g.,~\citet[Ch. 8]{rudin:76}) we can derive the asymptotics
\begin{equation}\label{eq:betaapprox}\beta_{n,\lambda}=\frac{n!\Gamma(2-\lambda)}{\Gamma(n+1-\lambda)}\sim\Gamma(2-\lambda)n^\lambda\;,\end{equation}
valid for fixed $\lambda$, and for large $n$.

\begin{theorem}
\label{thm:regularuppfix}
Let $F$ be a $\lambda$-regular distribution with $\lambda\in(0,1]$, and $n\geq 2$.
Using the same take-it-or-leave-it price, to sell an item to $n$ buyers with i.i.d.\
valuations from $F$, achieves an approximation ratio of at most
\[\apx{F}{n}\leq \frac{1}{\sup_{c\in[0,1]}g_{n,\lambda}(c)}+a_{n,\lambda}\]
with respect to the optimal revenue,
where $a_{n,\lambda}$ and $g_{n,\lambda}$ are defined as in \eqref{eq:helperreg_ab} and \eqref{eq:helperreg_g}.
\end{theorem}

\begin{proof}
We follow the same steps as for \cref{th:main_upper}, but use
\cref{lemma:bound_tail_regular} and the quantile bound from
\cref{lemma:regularproperties}. Specifically, instead of \eqref{eq:bound_price_second_order_c} we bound the revenue from pricing at $c\cdot \nu$, where $c\in[0,1]$ and $\nu=\expect{\orderstat{X}{n-1}{n}}$, as
\begin{equation}
\label{eq:bound_price_second_order_c_lambda}
\pricep{F}{n}{c\nu}
=c\nu[1-F(c\nu)^n]
\geq c\nu\left[1-\left[1-\left[1+c\left(\beta_{n,\lambda}-1\right)\right]^{-1/\lambda}\right]^n\right]\;.
\end{equation}
the inequality holding due to \cref{lemma:bound_tail_regular} (for $k=n-1$). Optimizing with respect to $c$ we get that
$$\price{F}{n} \geq \nu \sup_{c\in[0,1]}g_{n,\lambda}(c)\;.
$$
We can now plug this bound at the derivation in \cref{th:main_upper} to get
\begin{align*}
\apx{F}{n}&= \frac{\myerson{F}{n}}{\price{F}{n}} \\
  &\leq \frac{\nu}{\nu \sup_{c\in[0,1]}g_{n,\lambda}(c)}+ \frac{R(q^*)(1-q^*)^{n-1}}{R(q^*)\frac{1-(1-q^*)^n}{q^*}} \\
  &= \frac{1}{\sup_{c\in[0,1]}g_{n,\lambda}(c)} + \frac{q^*(1-q^*)^{n-1}}{1-(1-q^*)^n} \\
  & \leq \frac{1}{\sup_{c\in[0,1]}g_{n,\lambda}(c)} + a_{n,\lambda}\;.
\end{align*}
For the last step, we use the bound $q^\ast\geq (1-\lambda)^{1/\lambda}$ from \cref{lemma:regularproperties}, together with the definition of $a_{n,\lambda}$ as in \eqref{eq:helperreg_ab}.
\end{proof}

For the lower bounds, we introduce the following family of \emph{rescaled Pareto} distributions $F_{\lambda,r}$, with support $[1,\infty)$, for $\lambda\in(0,1]$ and $r\in(0,1]$:

\begin{equation}
\label{eq:pareto_instances}
F_{\lambda,r}(x)=1-\frac{1}{\left[1+\frac{1}{r}(x-1)\right]^{1/\lambda}}\;.
\end{equation}
These can be seen as lying at the edge of
$\lambda$-regularity; it is not difficult to see that $F_{\lambda, r}$ is $\lambda$-regular, but \emph{not} $\lambda'$-regular for $\lambda'<\lambda$ (see~\cref{sec:lambdareg-model}).
They are inspired by the lower-bound construction of~
\citet[Appendix~C.3]{Duetting2016}, but we generalized them to be $\lambda$-regular and also removed the point mass at the right endpoint of the
support in order to guarantee continuity.
On the other hand, for $r=1$, our distributions reduce to standard Pareto: $F_{\lambda,1}=1-\frac{1}{x^{1/\lambda}}$.

We first collect below some basic properties of rescaled Pareto distributions, concerning
their expected second-highest order statistic and pricing revenue;  their proof can be found
in \cref{app:auxfunprops}.
\begin{lemma}\label{lem:basicpareto}
For any $\lambda\in(0,1]$ and $r\in(0,1]$,
\begin{enumerate}
    \item $\expect[X\sim F_{\lambda,r}]{X_{n-1:n}}=1+r\left(\beta_{n,\lambda}-1\right)$;
    \item $\price{F_{\lambda,r}}{n}=\sup_{q\in[0,1]}\left(1+r\left(\frac{1}{q^\lambda}-1\right)\right)\left(1-(1-q)^n\right)$.
\end{enumerate}
\end{lemma}

For the sake of exposition we introduce the function $H_{n,\lambda}(r,q)$, for
$n\geq2$, $\lambda\in(0,1]$, $r\in(0,1]$, and $q=[0,1]$,
\begin{equation}\label{eq:hnlambda}
    H_{n,\lambda}(r,q)=\left(1+r\left(\frac{1}{q^\lambda}-1\right)\right)\left(1-(1-q)^n\right)\;.
\end{equation}
Note that $H_{n,\lambda}(r,q)$ is continuously defined at $q=0$ as the singularity
is removable.

\begin{theorem}\label{thm:regularlowfix} For $\lambda\in(0,1]$, $r\in(0,1]$, and
$n\geq 2$ bidders with i.i.d.\ valuations from the rescaled Pareto distribution
$F_{\lambda,r}$ (see~\eqref{eq:pareto_instances}), the approximation ratio of anonymous pricing is at least

\begin{equation}\label{eq:regularlowfix_1}\apx{F_{\lambda,r}}{n}\geq
\frac{1+r\left(\beta_{n,\lambda}-1\right)}{\sup_{q\in[0,1]}H_{n,\lambda}(r,q)}\;.\end{equation}
This implies the following lower bound on the approximation ratio of $\lambda$-regular
distributions:
\begin{equation}\label{eq:regularlowfix}\apx{n}{\lambda}\geq\adjustlimits\sup_{r\in[0,1]}\inf_{q\in[0,1]}\frac{1+r\left(\beta_{n,\lambda}-1\right)}{H_{n,\lambda}(r,q)}\;.\end{equation}
\end{theorem}

\begin{proof}
Using \cref{lem:basicpareto} (1), and the fact that the optimal revenue can be lower bounded by the second-highest order statistic, gives
\[\myerson{F_{\lambda,r}}{n}\geq\expect[X\sim F_{\lambda,r}]{X_{n-1:n}}=1+r\left(\beta_{n,\lambda}-1\right)\;.\]
Using \cref{lem:basicpareto} (2), and the definition of $H_{n,\lambda}$ from \eqref{eq:hnlambda}, gives
\[\price{F_{\lambda,r}}{n}=\sup_{q\in[0,1]}H_{n,\lambda}(r,q)\;.\]
Taking the ratio between these two quantities proves \eqref{eq:regularlowfix_1}. If we optimize this ratio for $r\in(0,1]$, we obtain
\begin{align*}
\apx{n}{\lambda}&\geq\sup_{r\in(0,1]}\apx{F_{\lambda,r}}{n}\\
&\geq\sup_{r\in(0,1]}\frac{1+r\left(\beta_{n,\lambda}-1\right)}{\sup_{q\in[0,1]}H_{n,\lambda}(r,q)}\\
&=\adjustlimits\sup_{r\in[0,1]}\inf_{q\in[0,1]}\frac{1+r\left(\beta_{n,\lambda}-1\right)}{H_{n,\lambda}(r,q)}\;;
\end{align*}
note that in the last step, we can allow $r=0$ without loss since the right-hand side is well-defined and gives a trivial lower bound of 1.
\end{proof}

A plot of the bounds given in
\cref{thm:regularuppfix,thm:regularlowfix} can be seen in
\cref{fig:regupplowbounds}, for different values of $n$ and $\lambda$.

\subsection{Asymptotic Analysis}
\label{sec:lambda_reg_asy}
\begin{figure}
\centering
\begin{tikzpicture}
\input{plot_regular_asymptotic}
\end{tikzpicture}
\Description{The asymptotically tight value of the approximation ratio of anonymous
pricing, given in \cref{thm:regularinf}, as a function of the regularity parameter
$\lambda$ (for $n\to\infty$ i.i.d. bidders).}
\caption{ The asymptotically tight value of the approximation ratio of anonymous
pricing, given in \cref{thm:regularinf}, as a function of the regularity parameter
$\lambda$ (for $n\to\infty$ i.i.d.\ bidders). }
\label{fig:regular_asymptotic}
\end{figure}

By observing the plots in \cref{fig:regupplowbounds}, it seems that the upper and
lower bounds are approaching some smooth function of $\lambda$ as $n$ grows large;
moreover, this function appears to increase from $1$ at $\lambda=0$ to
$\frac{e}{e-1}\approx 1.58$ at $\lambda=1$, which would recover the known bounds for
MHR (this paper, \cref{sec:MHR}) and regular (see,
e.g.,~\citep{Chawla2010a,Duetting2016}) distributions. In the remainder of this
paper we prove this is indeed the case, and characterize the limiting function. In
other words, we are interesting in taking the limit (as $n\rightarrow\infty$) of the
quantities defined in \cref{thm:regularuppfix,thm:regularlowfix}.

For each $\lambda\in(0,1]$, let us define the function $g_\lambda:[0,\infty)\rightarrow[0,\infty)$ as follows.

\begin{equation}\label{eq:glambda}
    g_{\lambda}(c)=c\left(1-e^{-(c\Gamma(2-\lambda))^{-1/\lambda}}\right)\;.
\end{equation}
The function $g_\lambda$ can be obtained from the function $g_{n,\lambda}$ introduced in \cref{eq:helperreg_g} as $n\rightarrow\infty$. We also define $\lambda^\ast\approx 0.4940$ as the unique positive root over $(0,1]$
of the equation (see~\cref{lem:lambdastar})
\begin{equation}\label{eq:lambdastar}1-\left(1+\frac{\Gamma(2-\lambda)^{-1/\lambda}}{\lambda}\right)e^{-\Gamma(2-\lambda)^{-1/\lambda}}=0\;.\end{equation}

For each $\lambda\in(0,1)$, let also $\eta(\lambda)$ denote the unique positive
solution of the equation $e^x=1+\frac{x}{\lambda}$, which is related to the function
$\eta(k)$ appearing in~\citet[Section 3.1.2]{Blumrosen2008a}. In fact, we must
mention here that one can derive a lower bound on the asymptotic approximation ratio
from~\citep{Blumrosen2008a}, which coincides with our \cref{thm:regularinf} in the
branch $0<\lambda\leq\lambda^\ast$. Although Blumrosen and Holenstein, in general,
study distributions satisfying the von Mises conditions, for their lower bounds they
make use of power law distributions of the form $F(x)=1-1/x^k$, for $k>1$. These
correspond to our rescaled Pareto distribution $F_{r,\lambda}$ from
\eqref{eq:pareto_instances} with $r=1$ and $\lambda=1/k$.

For the main result of this section we shall make use of the following technical lemma whose proof can be found in \cref{app:auxfunprops}.

\begin{lemma}\label{lem:supglam} For each $\lambda\in(0,1]$, let $g_\lambda$ be defined as in \eqref{eq:glambda} and $\eta(\lambda)$ be the unique positive solution of the equation $e^x=1+\frac{x}{\lambda}$. Let also $\lambda^\ast$ be the unique root of \eqref{eq:lambdastar}. The supremum of the function $g_\lambda$ over $[0,1]$ is as follows.
\begin{align*}
\text{If }0<\lambda\leq\lambda^\ast\text{, then}\quad&\sup_{c\in[0,1]}g_\lambda(c)=\sup_{c\geq 0}g_\lambda(c)=\frac{\eta(\lambda)^{1-\lambda}}{\Gamma(2-\lambda)(\lambda+\eta(\lambda))}\;.\\
\text{If }\lambda^\ast\leq\lambda\leq 1\text{, then}\quad&\sup_{c\in[0,1]}g_\lambda(c)=\phantom{\sup_{c\geq0}}g_\lambda(1)=1-e^{-\Gamma(2-\lambda)^{-1/\lambda}}\;.
\end{align*}
\end{lemma}

\begin{theorem}\label{thm:regularinf}
For $\lambda\in(0,1]$, the approximation ratio of anonymous pricing with arbitrarily
many bidders having i.i.d.\ valuations from a $\lambda$-regular distribution, is
asymptotically
\[\lim_{n\rightarrow\infty}\apx{n}{\lambda}=
\frac{1}{\sup_{0\leq c\leq1}g_\lambda(c)}=
\left\{\begin{array}{cc}\frac{\Gamma(2-\lambda)(\lambda+\eta(\lambda))}{\eta(\lambda)^{1-\lambda}},&0<\lambda\leq\lambda^\ast\;,\\
\\\frac{1}{1-e^{-\Gamma(2-\lambda)^{-1/\lambda}}},&\lambda^\ast\leq\lambda\leq
1\;,\end{array}\right.\] where $g_\lambda$ is defined in \eqref{eq:glambda},
$\lambda^\ast$ is the unique root of \eqref{eq:lambdastar}, $\Gamma$ is the gamma
function, and $\eta(\lambda)$ is the unique positive solution of the equation
$e^x=1+\frac{x}{\lambda}$.
\end{theorem}
A plot of this asymptotic approximation ratio can be seen
in~\cref{fig:regular_asymptotic}.
\begin{proof} The second equality, i.e.\ the characterization of $\sup_{c\in[0,1]}g_\lambda(c)$, comes from \cref{lem:supglam}.
The proof of the theorem can be split into three parts; we
start by providing an upper bound on the asymptotics; as for the lower bounds, our
proof considers the cases  $0<\lambda\leq\lambda^\ast$ and
$\lambda^\ast<\lambda\leq1$  separately.

To prove an upper bound, we start from the result obtained in
\cref{thm:regularuppfix},

\[\apx{n}{\lambda}\leq
\frac{1}{\sup_{c\in[0,1]}g_{n,\lambda}(c)}+a_{n,\lambda}\;.\]

For each $\lambda\in(0,1]$ and each $c\in[0,1]$, the Stirling approximation in
\eqref{eq:betaapprox} yields the pointwise convergence $g_{n,\lambda}(c)\rightarrow
g_\lambda(c)$. Thus, by elementary analysis\footnote{It is worth
mentioning that one could prove, with some technical effort, that the convergence
$g_{n,\lambda}(c)\rightarrow g_\lambda(c)$ is actually uniform on $c$, which would
allow us to interchange the limit with the supremum and write
$\lim_{n\to\infty}\sup_{c\in[0,1]}g_{n,\lambda}(c)=\sup_{c\in[0,1]}g_{\lambda}(c)$;
however, we will not need this result as the lower bound will be matching, so we
omit its proof.}, we have
$$\liminf_{n\rightarrow\infty}\sup_{0\leq c\leq
1}g_{n,\lambda}(c)\geq\sup_{0\leq c\leq 1}g_{\lambda}(c)\;.$$
As the additive term $a_{n,\lambda}$ vanishes as
$n\to\infty$, we get the desired upper bound,
\begin{equation}\label{eq:reguppasym}
\limsup_{n\rightarrow\infty}\apx{n}{\lambda}\leq\frac{1}{\sup_{c\in[0,1]}g_\lambda(c)}\;.
\end{equation}

To prove lower bounds, we study the asymptotic behaviour of the result obtained in
\cref{thm:regularlowfix},
\[\apx{n}{\lambda}\geq\adjustlimits\sup_{r\in[0,1]}\inf_{q\in[0,1]}\frac{1+r\left(\beta_{n,\lambda}-1\right)}{H_{n,\lambda}(r,q)}\;.\]

We begin by setting $r=1$, and applying the change of variables
$c=1/(\Gamma(2-\lambda)n^\lambda q^\lambda)$, yielding
\begin{align*}
\apx{n}{\lambda}&\geq\frac{\beta_{n,\lambda}}{\sup_{0\leq q\leq
1}\frac{1-(1-q)^n}{q^\lambda}}\\
&=\frac{\frac{\beta_{n,\lambda}}{\Gamma(2-\lambda)n^\lambda}}{\sup_{c\geq1/(\Gamma(2-\lambda)n^\lambda)}c\left[1-\left(1-\frac{(c\Gamma(2-\lambda))^{-1/\lambda}}{n}\right)^n\right]}\;.
\end{align*}
Note that the numerator of the above fraction goes to 1 as $n\rightarrow\infty$ due
to Stirling's approximation. As for the denominator, we need some technical work to
ensure that the limit and the supremum operators commute, and to show that it
converges to $\sup_{c\geq 0}g_\lambda(c)$. This is done in
\cref{lem:lowboundtechnical1} in \cref{app:auxfunprops}. Thus, we get
\begin{equation}
\label{eq:lower_asy}
\liminf_{n\rightarrow\infty}\apx{n}{\lambda}\geq\frac{1}{\sup_{c\geq
0}g_\lambda(c)}\;,
\end{equation}
which matches the desired quantity as long as $0<\lambda\leq\lambda^\ast$, due to \cref{lem:supglam}.

To get tight lower bounds for the case $\lambda^\ast<\lambda\leq 1$, we take an
approach very much inspired by that in \cite{Duetting2016}; our starting point is
again \cref{thm:regularlowfix}, but now the idea is to carefully choose a value of
$r$ which depends on $n$, for which a specific choice of optimal quantile $q^\ast$
gives the desired bound.

For each $n\geq2$ and $\lambda\in(0,1]$, recall the function
$H_{n,\lambda}:[0,1]\times[0,1]\rightarrow\mathbb{R}$ from
\eqref{eq:hnlambda}. As this function is continuous on a compact set, we can apply
Berge's Maximum Theorem (see, e.g,~\cite[Theorem~17.31]{Aliprantis2006a}) to
conclude that the correspondence $r\mapsto\argmax_{q\in[0,1]} H_{n,\lambda}(r,q)$ is
non-empty, compact valued and upper hemicontinuous.\footnote{One could, with
additional technical work, also prove that $H_{n,\lambda}(r,q)$ has a single peak
(in $q$) for each $r$, making this correspondence a continuous function; the rest of
the argument would be essentially an application of the intermediate value theorem.}
When $r=0$, we have $H_{n,\lambda}(0,q)=1-(1-q)^n$, which has a single peak at
$q=1$. Next we consider the case $r=1$, that is,
$H_{n,\lambda}(1,q)=\frac{1}{q^\lambda}(1-(1-q)^n)$. In
\cref{lem:lowboundtechnical2}, \cref{app:auxfunprops}, we prove that this function
has a single peak, and that for $\lambda^\ast<\lambda\leq 1$ and large enough $n$,
its peak lies to the left of $\beta_{n,\lambda}^{-1/\lambda}$. Thus, by
hemicontinuity, we can conclude that, for large enough $n$, there must exist some
value of $r\in[0,1]$, say $r_n$, such that $H_{n,\lambda}(r_n,q)$ is maximized at
precisely the quantile $q^\ast_n=\beta_{n,\lambda}^{-1/\lambda}$.\footnote{Note that
this statement is not merely existential: we can compute $r_n$ by solving the
equation $\frac{\partial}{\partial\, q} H_{n,\lambda}(r_n,q^\ast_n)=0$.} We can now
plug this into \cref{thm:regularlowfix}, obtaining
\begin{align*}
    \apx{n}{\lambda}&\geq\inf_{0\leq q\leq
    1}\frac{1+r_n\left(\beta_{n,\lambda}-1\right)}{H_{n,\lambda}(r_n,q)}\\
    &=\frac{1+r_n\left(\beta_{n,\lambda}-1\right)}{\left(1+r_n\left(\beta_{n,\lambda}-1\right)\right)\left(1-\left(1-\beta_{n,\lambda}^{-1/\lambda}\right)^n\right)}\\
    &=\frac{1}{1-\left(1-\beta_{n,\lambda}^{-1/\lambda}\right)^n}\;;
\end{align*}
by taking limits (and with the help of Stirling's approximation), we get
\[\liminf_{n\rightarrow\infty}\apx{n}{\lambda}\geq\frac{1}{1-e^{-\Gamma(2-\lambda)^{-1/\lambda}}}\;,\]
which matches the desired quantity as long as $\lambda^\ast<\lambda\leq 1$, due to \cref{lem:supglam}. This concludes the proof.
\end{proof}

\section{Conclusion and Future Directions}
\label{sec:conclusion}

In this paper, we studied the performance of anonymous selling mechanisms for a
Bayesian setting with a single item and $n$ bidders with i.i.d.~ valuations. We
completely characterized the asymptotic approximation ratio (with respect to the
optimal, Myersonian revenue) for $\lambda$-regular distributions with
$\lambda\in[0,1]$,
\[\adjustlimits\lim_{n\rightarrow\infty}\sup_{F\in\mathcal{D}_\lambda}\apx{F}{n}=\frac{1}{\sup_{0\leq
c\leq 1}g_\lambda(c)}\;.\]
This quantity increases smoothly (see~\cref{fig:regular_asymptotic}) from $1$ for
MHR distributions to $\frac{e}{e-1}\approx 1.58$ for regular distributions. For the
special case of MHR distributions, we also characterized the rate of convergence and
provided explicit, ``good'' pricing schemes that depend only on the knowledge of the
expected second-highest order statistic of the distribution.

A few interesting questions remain. Two quantities of independent interest are
\[\sup_{n\geq
2}\sup_{F\in\mathcal{D}_\lambda}\apx{F}{n}\qquad\text{and}\qquad\adjustlimits\sup_{F\in\mathcal{D}_\lambda}\limsup_{n\rightarrow\infty}\apx{F}{n}\;.\]

The first one corresponds to \emph{global} bounds on the approximation ratio, which
require a finer analysis, especially in the ``small'' $n$ range. Even for MHR
distributions, there is still a gap between the global upper bound of $1.35$ (numerically
achieved at $n=3$ in \cref{th:main_upper_small}) and the global lower
bound of $1.27$ (numerically achieved at $n=17$ in \cref{th:lower_expo}).

The second one intuitively captures settings where the seller's prior knowledge of a
large market is assumed to be size-independent. Studying this quantity amounts
to asking: do the lower bounds of \cref{thm:regularinf} \emph{require} constructing
a ``bad'' distribution $F_n$ for \emph{each} $n$ separately? In the range closer to
MHR, i.e. $0<\lambda\leq\lambda^\ast$, the answer is ``no'': our lower bounds were
obtained by setting $r=1$ globally, independent of $n$. But even for regular
distributions, there is still a gap between the size-independent lower bound of
$1.40$  (achieved by numerically maximizing \eqref{eq:lower_asy}) and the upper
bound of $1.58$ (see~\cref{fig:regular_asymptotic} at $\lambda=1$).

Another interesting direction would be to characterize analytically the rate of
convergence (with respect to the number of bidders $n$) of the approximation ratio
given by~\cref{thm:regularuppfix}. In other words, generalize \cref{th:main_upper}
for $\lambda$-regular distributions with $\lambda>0$.

\bibliographystyle{ACM-Reference-Format}

redpajama_set_name: RedPajamaArXiv


Football Festivus has us in a giving mood!
As we wrap up our first year here at Three Point Stance Magazine, we wanted to be the ones to give the gifts of season.
Saturday begins "The Most Wonderful Time of the Year" – FOOTBALL FESTIVUS! At least one game, every day, into 2016, and to celebrate we are giving our December issue, our bowl preview (and our largest EVER) for free!
Get the December Issue here!
If you like what you see and want to get more 3PSMag in your life, subscribe to a Season Ticket (also makes a great stocking stuffer)!


Here is an updated version of a popular dish that everyone is sure to enjoy. It is very quick and convenient as it uses a ready-made fresh cheese sauce. Just add your choice of sausage or salami from the Deli Counter.
Cut the cauliflower into large florets leaving most of the inner leaves on. Cook in a large pan of boiling water for 7-10 minutes, or until just tender. Drain well.
Meanwhile, peel and discard the skin from the sausage and roughly chop. Place in a frying pan and stir over a high heat until the fat begins to run and the sausage starts to turn crispy at the edges. Add the salad onions and stir over the heat for a further 1 minute. Remove from the heat and stir in the cauliflower to coat in the juices, then transfer into a shallow ovenproof dish.
Preheat the grill to high. Heat the cheese sauce according to the instructions on the pack, then stir in the mayonnaise and half the Parmigiano Reggiano. Spoon the sauce over the cauliflower.
Sprinkle the remaining Parmigiano Reggiano over the top and brown under the hot grill for 3-4 minutes before serving.
The whole dish can be made ahead, then covered and chilled in the fridge overnight. Reheat in a hot oven at 200°C, gas mark 6 for 25 minutes until piping hot and golden brown.


I CHALLENGE YOU — What is your PHILOSOPHY?
For the Traditional Catholic such as myself, we take Holy Week serious, as should all those who think of themselves as Christians, and everyone concerned about life beyond this one. Because of this being Holy Week I will not be posting very much, perhaps here and there depending on if and when inspirations come my way. Please continue to read this short post for a little story below.
Check this story out don't CLICK OFF or run away; it is not religious; however, it can be. Last week I was indulging in one of those old classic black and white movies found on Youtube. One of the characters is speaking, while discussing with another mentions his philosophy, and I adopted it for my secular philosophy as well. However, when you think about it long enough, it flows from this world our earthly life to the spiritual where we find everlasting happiness.
I like that philosophy; I wonder if anyone would take the challenge and think about what your philosophy is.
Share it if you will here on WordPress. Sort of a Share your World to borrow the fantastic words of others here on WordPress.
The theme is delicious so we think of food. I usually don't photograph food, however, June of 2017 I was tempted and did capture an image of my favorite fruit, cherries while washing water drops appeared upon the cluster. Later when I uploaded the image to my Corel Paint Shop Pro; wanting to experiment with an effect known as the Magnifying Lens this was the result. Hope you find it interesting.


The Sheriff is a Court Officer entitled to seize goods from the debtor which may then be sold to realise funds for the discharge of the debt. This can take quite some time, and in many cases the Judgement will be returned because the Sheriff is of the opinion that the debtor has no goods which can be seized. In the case of a Limited Company the Sheriff may be the only realistic option after registration. We also lodge Judgements with the Sheriff for low value accounts.
If you are sure that the debtor (and not somebody else) owns something valuable, for example a car, you can ask the Sheriff to seize it.
The Sheriff can also enter into an instalment arrangement with a debtor, which may be the best way of getting paid over a reasonable period of time.


Grounds For Sculpture offers opportunities for sponsorship. By sponsoring an exhibition or other event, your corporation can achieve on-site and off-site visibility, publicity, and advertising, as well as create memorable special events to engage clients, employees and guests. Both sponsorships and memberships can be tailored to the needs of your organization.
Join with a special group of business leaders in our community who care deeply about keeping the arts alive in New Jersey! The Grounds For Sculpture Business Partner Program (BPP) represents an exciting and significant partnership between area businesses and art in our community. The business community's membership and participation play an invaluable part in the GFS's growth and success by helping the GFS to present new exhibitions, financially sustain its permanent collection and enhance its programs for children and adults.
For more information on becoming a member of the GFS Business Partner Program, or to craft a Business Partner Program exclusively to meet your business needs, please contact Janis Martin-Hughes at (609) 249-0248 or jmhughes@groundsforsculpture.org.


The last time I directed a play was in 2005 (while I was pregnant with twin daughters—who were born seven weeks early on Christmas Eve). In over a decade of selecting shows for Lyric Arts' annual theater season, this is the first time I have felt this strongly about a script and my need to direct it. For anyone who knows me, however, it shouldn't be surprising that a show like Prancer is what drew me back to directing.
In many ways, this is the perfect Christmas show. In fact, it meets all off all of my Lyric Arts' holiday show requirements—joy, tears, family, nostalgia, and magic—and it encapsulates everything I love about the holiday season.
At the center of this story is the relationship between Jessica and her father. We long for their relationship to heal right along with Prancer's injury. Ultimately, Jessica's boundless love and optimism reopens her father's heart to the world around him, while also opening the hearts and changing the lives of many others in the process.
No matter your religion or personal beliefs, each one of us is called to be a light in the darkness for one another—especially at this time of the year. My greatest hope is that Prancer ignites that light for you, and that you leave Lyric Arts carrying it in your heart, ready to share it with those you love and those who need it most.
That, in my mind, is the true meaning and spirit of this extraordinary time of year.
I would like to thank my exceptional production team of designers and technicians, along with my incredible cast, for making my re-entry into directing such an easy, joyful, and collaborative process.
Happy Hanukkah, Happy Kwanzaa, Blessed Solstice, and Merry Christmas.
Watch our Director's Take video to find out what more Laura has to say about the show!
DIRECTOR'S TAKE: Laura Tahja Johnson Talks "Prancer" from Lyric Arts Staff on Vimeo.


The area around Lake Maggiore has always been very popular with cyclists, and over the decades Varese has produced many champions who have made their mark on the history of cycling. Since 1900 a succession of Varese natives have ridden their way to the top of the sport: riders of the calibre of Luigi Ganna, Alfredo Binda, Michele Mara, Wladimiro Panizza, Claudio Chiappucci, Ivan Basso and Stefano Garzelli.
The Varese area offers routes and rides for all levels of fitness and training with an awe-inspiring variety of experiences: you can enjoy gentle rides along the banks of the lake, explore the woods, follow the rivers through the neighbouring valleys, or challenge yourself on steep climbs with some gradients that even exceed 20%!
The Province of Varese and Lake Maggiore also offer a wealth of off-road experiences with extreme slopes and tricky terrain for mountain biker and cross-country trails with steep descents and rough tracks for downhill fans. For thrill-seeking mountain bikers we recommend the northern part of the province where you can explore woods and dirt tracks that hug the mountains and offer panoramic views of Lake Maggiore, the Alps and Monte Rosa.
Lake Varese lies at the foot of Mount Campo dei Fiori and is bordered by the city of Varese and another eight towns in the province.
More than 200 athletes from Switzerland and Lombardia will attend the XCO Valceresio Bike in Cuasso al Monte. Discover more on the official site.
The international race will take place in Solbiate Arno the 9th of June. You'll find all the details on the official site.


Today we are pleased to announce the third release of Pipeline - 0.3.0. Besides a battery of new features and fixes, the main focus of this release is to add support for the Google Kubernetes Engine GKE, and to simplify/strengthen security using OAuth2 and Vault.
A major change in 0.3.0 is that Pipeline now requires GitHub OAuth authentication similar to a CI/CD flow. Accordingly, it allows both Pipeline and the CI/CD flow to be authenticated by a single mechanism, as opposed to before, when Pipeline requiried only basic authentication. Also, this release adds support for three different serverless/function-as-service frameworks.
A control plane is available for all supported providers. And an end-to-end howto guide (including a full CI/CD flow) is available, here.
We have added native support for Google's Kubernetes engine, on which the Pipeline control plane is available as a Kubernetes deployment, and which can also provision and deploy clusters to GKE.
We strongly believe that managed Kubernetes services are the future, and most of our investment in cloud neutrality and provisioning is built on managed Kubernetes services, both in the cloud and on-premise.
In the 0.3.0 release, components of Pipeline have been re-worked to easily streamline the incorporation of new cloud providers, and to provide the same level of automation and easier enablement to new cloud providers.
This release, 0.3.0, adds support for Google's Managed Kubernetes GKE support, and moves away from username/password-based authentications and towards OAuth2 tokens. Both Pipeline and the CI/CD component use OAuth2 tokens issued by GitHub after successful GitHub OAuth2 authentication.
For further details, read the Pipeline how-to documentation.
Here, we have demonstrated the complexity and number of building blocks necessary in order to host your own PaaS and become your own microservice provider. We do this to better understand and illustrate the level of work, maintenance, as well as the HA deployments and Kubernetes expertise, that's required to run these components.


Idris Aziz has seen—and created—plenty of changes in his 22 years as a security officer in Los Angeles.
He's also gained a wealth of experience, which he uses to keep people safe on his hospital's graveyard shift.
His experience also includes working to make things better for everyone.
His union activism paid off when he and his fellow security officers decided to organize their own union in Los Angeles. Working as a union member is very different from the way he and his family used to get by.
"Most security contractors didn't pay for healthcare before," he says, pointing out the difference it makes to have formed a union with other security officers in L.A.
Having a fair process to resolve problems on the job.
What kind of changes does Idris see on the horizon?
He believes in the power of his union to help make it happen.


Five months ago I sent a resume to a company in Fort Myers that I'd never heard of. Four and a half months ago I came down to Punta Gorda for the first time. Four months ago I sent more resumes to more companies in the Sarasota/Fort Myers area. Three months ago I started interviewing. Two months ago I interviewed for the position I ended up taking. One month ago I accepted my new job and signed the lease on my new house. This week I moved into my new house and started the process of building a life here alone, away from my village, with new friends, in a new village.
And today another morning begins in paradise… a lovely dinner with friends last night, nearly settled into my house, but I'm still struggling with how fast everything has changed. How short five months really is. Honestly it's almost breathtaking when I step back and see how much everything has changed.
Five months ago I was on month 11 of unemployment, today I have a 2 min. commute to my new office. Five months ago I drank coffee every morning as I watched the sun rise over Lake Hollingsworth, today I can see Charlotte Harbor from my office steps. Five months ago I ate dinner on the pool deck, today my lanai faces a tropical jungle that is so very peaceful at night and I can't wait to eat dinner outside and listen to the nightlife serenade. Five months ago I was out with friends nearly all the time, today I occasionally go to dinner with friends but I'm still building my village and learning about the area and I feel like I'm looking for change in the things I do for fun.
Everything changes… into a different good.
Yes, I'll get used to this I know. One day I suspect that I'll look around and realize that five years have passed and this little town of Punta Gorda has become home. But not today. Today I'm between worlds. Today I'm still handling all of the change. Today change is my companion and my friend. Today change is all I know.
So here's my advice… change is going to happen whether you like it or not so control the chaos by doing it yourself. Blow up your life occasionally… and deal with the aftermath. Don't get so wrapped up in keeping everything the same that you become rigid and trapped. Happy is where you find it. So go look for it.