# Distributional Robustness: From Pricing to Auctions

Nir Bachrach Technion – Israel Institute of Technology. Email:
<EMAIL_ADDRESS>Inbal Talgam-Cohen Technion – Israel
Institute of Technology. Email<EMAIL_ADDRESS>
###### Abstract

Robust mechanism design is a rising alternative to Bayesian mechanism design,
which yields designs that do not rely on assumptions like full distributional
knowledge. We apply this approach to mechanisms for selling a single item,
assuming that only the mean of the value distribution and an upper bound on
the bidder values are known. We seek the mechanism that maximizes revenue over
the worst-case distribution compatible with the known parameters. Such a
mechanism arises as an equilibrium of a zero-sum game between the seller and
an adversary who chooses the distribution, and so can be referred to as the
max-min mechanism.

Carrasco et al. [2018] derive the max-min _pricing_ when the seller faces a
single bidder for the item. We go from max-min pricing to max-min _auctions_
by studying the canonical setting of two i.i.d. bidders, and show the max-min
mechanism is the second-price auction with a randomized reserve. We derive a
closed-form solution for the distribution over reserve prices, as well as the
worst-case value distribution, for which there is simple economic intuition.
In fact we derive a closed-form solution for the reserve price distribution
for any number of bidders.

Our technique for solving the zero-sum game is quite different than that of
Carrasco et al. – it involves analyzing a discretized version of the setting,
then refining the discretization grid and deriving a closed-form solution for
the non-discretized, original setting. Our results establish a difference
between the case of two bidders and that of $n\geq 3$ bidders.

##  1 Introduction

Bayesian mechanism design. Traditional mechanism design centers around the
Bayesian approach, in which unknown features of the environment (such as
agents’ preferences) are assumed to come from a commonly-known prior
distribution. The design goal is to maximize an objective like revenue in
expectation over this prior. A beautiful theory has developed for the Bayesian
model; in particular, consider one of the simplest standard mechanism design
problems: a seller with a single item for sale, and bidders with privately-
known values $v_{1},v_{2}$ drawn independently from a known distribution $F$.
The design goal is to maximize the expected revenue (over the random values
and any internal randomness of the mechanism). For the special case of a
single bidder, it is not hard to deduce the optimal pricing mechanism – set a
deterministic price $r$ that maximizes the expected revenue $r(1-F(r))$. The
celebrated theory of Myerson [1981] extends this result from optimal pricing
to optimal auctions, yielding the mechanism with optimal expected revenue for
the case of two or more bidders. One of the “all-time greatest hits” of
mechanism design is the Myerson optimal auction for i.i.d. values, which turns
out to be the ubiquitous second-price auction with a deterministic reserve
$r=r(F)$.

Robust mechanism design. One drawback of the Bayesian theory is its reliance
on a strong common-knowledge assumption with respect to the distribution. As
Nobel laureate Robert Wilson pointed out, for economic theory to be applicable
to practice we must strive to repeatedly weaken such assumptions Wilson
[1987]. The Wilson doctrine combined with classic robust optimization models
inspired a rich literature on _robust mechanism design_. In our single-item
auction context, a distributionally-robust mechanism does not have full
knowledge of the value distribution – although such a distribution exists “in
the background” [_cf_., Devanur et al., 2015] – and is required to perform
well for a worst-case such distribution. Robust mechanism design can be seen
as bridging the worst- and average-case approaches of CS and economics,
respectively,111Robust mechanism design can thus be viewed as part of the
_beyond worst-case analysis_ agenda Roughgarden [2020]. thus holding much
promise for generating new insight.

Distributional robustness. Rather than full Bayesian knowledge, the designer
is assumed to have access either to certain _parameters_ of the distribution
(e.g., mean value), or to samples from it, or to additional bidders with
values from the same distribution. The goal is to use these alternatives to
design “optimal” distributionally-robust auctions, for an appropriate
definition of optimality. Different notions of optimality have led to
different branches of research, notably _prior-independent_ versus _max-min_
optimal mechanism design. Our focus in this paper is on parametric knowledge
of the distribution and on max-min optimal auctions.

The canonical problem in this area is described by Carroll [2019], as follows:

> “It can be natural to ask what happens if the designer has only partial
> information about the distribution, and wishes to maximize a guarantee under
> this partial information […] For example, what happens if the seller instead
> does not know the distribution, but only knows the mean and an upper bound
> on $v$, and wishes to design a mechanism to _maximize expected profit in the
> worst case_ over all distributions consistent with this knowledge?”

This is the problem we wish to make progress on in this paper.

Zero-sum game perspective. Mathematically, the problem of designing the max-
min optimal mechanism given parametric knowledge of the distribution can be
modeled as a zero-sum game, where a seller-player is trying to maximize
expected revenue, and an adversary-player (also referred to as “nature”) is
trying to minimize the revenue by picking the worst-case distribution
compatible with the parametric knowledge. A _Nash equilibrium_ of the zero-sum
game yields a stable max-min strategy for the seller, i.e., a
distributionally-robust optimal auction. Many recent works on robust mechanism
design have taken the zero-sum game approach [e.g., Bei et al., 2019, Gravin
and Lu, 2018, Carroll, 2017, 2015, Dütting et al., 2019, Babaioff et al.,
2020].

The zero-sum game model highlights two core ideas of the max-min approach:
First, the seller should _randomize_ in order to hedge her uncertainty;
indeed, the seller-player’s equilibrium strategy is generally a _mixed_ one. A
second idea is to strike the right balance between relaxation of unrealistic
knowledge assumptions, and good performance of the mechanism. This is achieved
by carefully balancing the powers of the seller and adversary in the zero-sum
game. If the adversary has too much power (reflecting extreme lack of
knowledge on behalf of the seller), the robust auction arising from the
equilibrium might be trivial and uninformative. An intuitive indication of
striking the right balance is that the max-min strategy of the seller yields a
robustly-optimal auction format that turns out to be ubiquitous in practice (a
notable example is Carroll [2017]).

A gap in the literature and our main result. The problem in the above
description by Carroll [2017] has been addressed for several important cases.
First and foremost, Carrasco et al. [2018] solve it when there is a _single_
bidder for the item, establishing the robust parallel to the optimal Bayesian
_pricing_. This parallel turns out to be a random pricing scheme where the
price is distributed according to a log-uniform distribution – in line with
the above intuition of hedging against uncertainty through randomization.

Che [2022] tackles a generalization to more than one bidder, but allows the
bidder values to be _correlated_ in an unknown way (i.e., the adversary
chooses the worst-case correlation among the values). Suzdaltsev [2020a] also
tackles a generalization beyond a single bidder; in his model the bidders are
i.i.d., but the seller’s strategies in the zero-sum game are limited to
_deterministic_ auctions. To our knowledge, the case of max-min randomized
auction design for more than one bidder with i.i.d. values has not been
addressed. In other words, the literature is missing the robust parallel to
the optimal Bayesian _auction_ , which in this case is the “greatest hit”
second-price auction with deterministic reserve.

Our main result in this paper addresses this gap in the literature for the
two-bidder case. In our zero-sum game, the adversary is _not_ allowed to
correlate the bidder values, whereas the seller _is_ allowed to choose a
randomized mechanism; we view this as a natural balance of powers between the
players, and indeed the equilibrium of this game yields a standard and wide-
spread auction format as the max-min optimum. As our main result, we solve
this game and show that the robust parallel to the optimal auction for two
i.i.d. bidders is the second-price auction with _random_ reserve. We also give
a closed-form solution for the seller’s optimal distribution over reserve
prices.

Interestingly, we can partially extend our result to any number of i.i.d.
bidders: For $n\geq 3$ bidders, we find the robust-optimal distribution of the
reserve price assuming the seller applies a second-price auction with reserve.
However, such an auction is no longer the overall robust-optimal mechanism.

###  1.1 Our Contribution and Takeaways

Two bidders. Our main theorem is the following:

######  Theorem (Informal, see Theorem 3.2).

Consider a parametric auction setting with two bidders, whose values are drawn
i.i.d. from a distribution with known mean value $\mu$ and support contained
in $[0,\overline{v}]$. Consider the zero-sum game between the seller choosing
a mechanism, and the adversary choosing a value distribution with mean $\mu$
and support contained in $[0,\overline{v}]$, where the seller’s payoff is the
expected revenue. If $M^{*}$ is the second-price auction with randomized
reserve sampled from $Q^{*}$, then $(M^{*},F^{*})$ is an equilibrium of the
zero-sum game, where $Q^{*},F^{*}$ are CDFs defined (roughly) as follows:

  * •

$\underline{v}$ is the unique solution in $[0,\overline{v}]$ to
$\underline{v}\left(1+\log\nicefrac{{\overline{v}}}{{\underline{v}}}\right)=\mu$.

  * •

$F^{*}$ is the (generalized) equal-revenue distribution over the support
$[\underline{v},\overline{v}]$, that is,
$F^{*}(v)=1-\nicefrac{{\underline{v}}}{{v}}$.

  * •

$Q^{*}$ is a normalized ratio between the log-uniform distribution and the
equal-revenue distribution:

$Q^{*}(r)\propto\frac{\log\nicefrac{{r}}{{\underline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\cdot\frac{1}{1-\nicefrac{{\underline{v}}}{{r}}}\text{
where }r\in(\underline{v},\overline{v}].$

The theorem provides the optimal distributionally-robust auction for a seller
whose parametric knowledge is $(\mu,\overline{v})$, as well as the worst-case
distribution $F^{*}$ of the bidders’ values. The key takeaway is that while a
randomized reserve price is the optimal distributionally-robust pricing for a
single bidder Carrasco et al. [2018], the second-price auction with a
randomized reserve is the optimal distributionally-robust pricing for two
bidders.

Economic interpretation: Indifference. The worst-case (min-max) equilibrium
distribution $F^{*}$ over bidder values has a clear economic interpretation –
it always induces the same expected revenue for the seller, regardless of the
reserve price realization. Indeed, this ability to “induce indifference” is
the salient property of the equal-revenue distribution, and the reason why it
emerges in the analysis of so many mechanism design settings. The indifference
on the seller’s behalf means that the adversary is “robust” to the seller’s
randomization over prices, making equal-revenue a natural candidate for the
adversary’s min-max optimum. Intuitively, in the absence of knowledge (in this
case about the seller’s reserve price), the player (adversary) should opt for
a strategy whose payoff is agnostic to the unknown details; any dependence on
such details will be taken advantage of by the opponent (seller).

Similar explanations for robustly-optimal designs that induce indifference can
be found in [e.g., Carroll, 2015, Dütting et al., 2019, Carroll, 2017, Gravin
and Lu, 2018, Carrasco et al., 2018]. However, as noted by Babaioff et al.
[2020], this principle of agnosticism does not always hold. In our case, the
max-min distribution $Q^{*}$ of the seller does not induce indifference on the
adversary’s side. In other words, the seller fails to make the adversary
indifferent, thus enabling the adversary to take advantage of the seller’s
ignorance.

Mathematical explanation of the indifference. Our analysis gives an intuitive
mathematical explanation for why the principle of agnosticism holds for the
seller but not for the adversary, and a general way to predict for which zero-
sum games and which players we expect to get indifference. Consider a zero-sum
game which has an equilibrium composed of strategies in the interior of the
players’ strategy spaces.222If the equilibrium is not composed of such
strategies, the indifference can be only on a subspace where the strategies do
fall in the interior. Consider the game’s payoff function. If $R$ is the
random reserve price of the second-price auction played by the seller, and $F$
is the value distribution played by the adversary, the payoff (expected
revenue) can be shown to be
$R(1-F^{2}(R))+\int_{R}^{\overline{v}}\left(1-F(v)\right)^{2}dv$. A key
observation is that the payoff is _linear_ in the distribution of $R$ (the
seller’s strategy) and _quadratic_ in $F$ (the adversary’s strategy).

By this observation, we expect indifference for the seller but not the
adversary: Since the equilibrium is a saddle point of the payoff function
(which by assumption falls in the interior), the gradients of the payoff
function should be zero at the equilibrium point. Furthermore, by linearity in
the seller’s strategy, the gradient is a function of only the adversary’s
strategy. Putting these two together, the gradient is zero given the
equilibrium strategy of the adversary for any strategy of the seller. Hence
the seller’s strategy does not affect her payoff – i.e., the seller is
indifferent. For similar reasons, the non-linearity of the payoff in the
adversary’s strategy means we do not expect indifference for the adversary.

Beyond two bidders. Our main theorem beyond two bidders is the following:

######  Theorem (Informal, see Theorem 4.1).

Consider a parametric auction setting with $n\geq 3$ bidders, whose values are
drawn i.i.d. from a distribution with known mean value $\mu$ and support
contained in $[0,\overline{v}]$. Consider the zero-sum game between the seller
choosing a distribution for a randomized reserve price in a second price
auction, and the adversary choosing a value distribution with mean $\mu$ and
support contained in $[0,\overline{v}]$, where the seller’s payoff is the
expected revenue. Then $(Q^{*},F^{*})$ is an equilibrium of the zero-sum game,
where $Q^{*},F^{*}$ are CDFs defined (roughly) as follows:

  * •

$\underline{v}$ is the smaller among two solutions to
$\left(n-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}\right)\underline{v}=\left(n-1\right)^{2}\mu.$

  * •

Case 1: $\underline{v}\leq\overline{v}$.

    * –

$F^{*}(v)$ mixes a generalized equal-revenue distribution over the support
$[\underline{v},\overline{v}]$, that is $1-\frac{\underline{v}}{(n-1)^{2}v}$,
and a point mass distribution at $v_{0}=\frac{\underline{v}}{n-1}$.

    * –

$Q^{*}(r)$ is a normalized ratio between a truncated log-uniform distribution
and $\left(F^{*}\right)^{n-1}$:

$Q^{*}(r)\propto\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{r}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\cdot\left(F^{*}(r)\right)^{-(n-1)}\text{
where }r\in(\underline{v},\overline{v}].$

For $r\in[0,\underline{v})$ it is simply $Q^{*}(r)=Q^{*}(\underline{v})$.

  * •

Case 2: $\underline{v}\geq\overline{v}$.

    * –

$Q^{*}$ is simply a point mass distribution on zero, which is equivalent to a
simple second price auction with no reserve price.

    * –

$F^{*}$ is a binary distribution between two possible values
$\\{v_{0},\overline{v}\\}$, where
$v_{0}=\mu-\frac{\overline{v}-\mu}{\left(n-1\right)^{2}-1}$.

This theorem provides a solution to the seller’s optimal distribution for a
reserve price in a second price auction, but it does not guarantee that this
is the robust optimal mechanism overall, and indeed we can find mechanisms
that would achieve better results if the bidders’ valuations are drawn from
$F^{*}$ (Section 4.6). In this case, the indifference that nature induces on
the seller is only partial, as the indifference only happens outside of
$[v_{0},\min\\{\underline{v},\overline{v}\\}]$. While a second price auction
with randomized reserve cannot take advantage of this, other mechanisms can
abuse $F^{*}$ better, and get a higher expected revenue.

###  1.2 Our Techniques

The method of Carrasco et al. [2018] does not seem to easily extend beyond a
single bidder. Carrasco et al. [2018] characterize the transfer function of
the distributionally-robust optimal pricing as the non-negative monotonic hull
of a linear polynomial.333They also address a parametric setting where the
first $N$ moments of the distribution are known, in which case the polynomial
is of degree $N$. In the case of multiple bidders, the polynomial is no longer
single-dimensional, and so applying this method seems more complicated.
Instead, we suggest the following approach.

We first limit the seller from applying general mechanisms to using only
second-price auctions with a random reserve. We refer to the resulting game
(in which the adversary’s strategy space has not changed) as the _reduced_
zero-sum game. In order to solve this game, we consider a simpler case, where
the distributions that constitute the strategies of both the seller and the
adversary are discrete, and the possible reserves/values are constrained to a
known finite set.

For the discrete case, we only find recursive relations between adjacent
points in the constrained finite set. By increasing the size of the finite
set, and making the distance between the points smaller and smaller, we can
take the limit of the recursive relations, and get ODEs (ordinary differential
equations) that describe a solution to the non-discretized problem. This
enable us to guess a potential solution.

It remains to show that our guess based on the ODEs is an equilibrium of the
reduced zero-sum game. This is done by showing that no player can do better,
even with perfect prior knowledge on the other player’s chosen distribution.
In fact we show that in the two bidder case, it is an equilibrium even of the
non-reduced game, in which the seller can choose any mechanism (rather than
only second-price-based mechanisms). To achieve this we utilize the
indifference of the seller over the interval $[0,\overline{v}]$.

In Appendices A-C we provide an alternative analysis in which we are not
required to guess a solution, rather we deduce it mathematically. Appendix B
in particular provides a mathematical foundation for the technique of deducing
the general solution based on the discrete one. We also show that the idea of
discretization can help solve other variants, e.g. one in which no upper bound
on the values is known, by revisiting the single-bidder case solved by
Carrasco et al. [2018]. Our analysis of this case appears in Appendix F.

###  1.3 Additional Related Work

Robust mechanism design. There is a large and steadily-growing body of
literature on the design of robust economic mechanisms in various domains,
where the robustness is to different kinds of uncertainties (e.g., contract
design robust to uncertain technologies Carroll [2015], Bayesian persuasion
robust to uncertain utilities Babichenko et al. [2021], or auction design
robust to the bidders’ attitude toward ambiguity Koçyiğit et al. [2019]). The
literature is too large to cover here comprehensively – see Carroll [2019] for
a recent survey.

Distributional robustness. A very active research area studies distributional
robustness, with several routes being explored. First, one needs to choose the
benchmark against which the robust mechanism’s performance is measured. The
main benchmarks are (1) the optimal non-robust auction that knows the
distribution, and (2) our benchmark, namely the max-min robust auction that
maximizes the performance against the worst-case distribution. A third
benchmark – (3) the welfare – was recently considered in very interesting work
of Anunrojwong et al. [2022], which is concurrent and independent to our work.

For the first benchmark, the performance is usually measured by a
multiplicative approximation guarantee, and this branch of research is known
as _prior-independent_ mechanism design [e.g., Dhangwatnotai et al., 2015,
Talgam-Cohen, 2020]. An alternative measure is additive regret [e.g.,
Babichenko et al., 2021, Savage, 1951].444Regret in repeated settings has also
been studied but is beyond our scope. For the second benchmark, in this work
we aim to achieve it exactly rather than approximately, but approximations of
it have been considered in other contexts [e.g., Bei et al., 2019]). In some
cases connections have been established between the two benchmarks Azar and
Micali [2013], Giannakopoulos et al. [2020]. For the third benchmark,
Anunrojwong et al. [2022] show that the second price auction with randomized
reserve minimizes the worst-case regret in comparison to extracting full
welfare. In other words, it minimizes the regret due to not knowing the values
and instead only knowing their supports. Their work thus establishes another,
very different way in which the second price auction with randomized reserve
is robustly optimal, and their robust optimality result persists across
several distribution families.

Besides choosing the benchmark, another choice is whether to allow the
augmentation of resources to compensate for the uncertainty, e.g. the addition
of competing bidders Bulow and Klemperer [1996], Koçyiğit et al. [2019], or
alternatively whether to allow sample access to the unknown distribution
[e.g., Cole and Roughgarden, 2014, Allouah et al., 2021b, c, Babaioff et al.,
2018]. In this work we allow neither; closer to our approach are works that
allow access to some statistic [e.g., Allouah et al., 2021a].

Robustness to correlation. The basic setting of distributionally robust
mechanism design includes a single seller, bidder and item. A recent line of
work studies _more than one item_ , applying robustness to the challenging
domain of multi-parameter mechanism design. The robustness in this context is
usually to correlation among the item values Carroll [2017], Gravin and Lu
[2018], Babaioff et al. [2020], and sometimes (in addition to correlation) to
details of the marginal distributions Che and Zhong [2021], Brooks and Du
[2021], Giannakopoulos et al. [2020]. The basic setting has also been
generalized to the complementary case of _multiple bidders_ , where the
robustness is to correlation among them (and possibly to distributional
details as well) Suzdaltsev [2020b], Bei et al. [2019], Che [2022], Koçyiğit
et al. [2019], He and Li [2022]. Distributional robustness has also been
studied with asymptotically-many bidders [e.g. Segal, 2003].

Max-min mechanisms with parametric information. The closest work to ours is by
Carrasco et al. [2018]. They study the same problem as ours, but with a
_single_ bidder. The parametric information they consider is either the first
moment and an upper bound on the values, or the first two moments. They also
consider multiple moments, although in this case the max-min mechanism cannot
be given explicitly. Their work has generated many follow-ups for a single
bidder: Their max-min design is shown by Giannakopoulos et al. [2020] to also
be a good prior-independent design; Carrasco et al. [2019] study an extension
to a divisible item; and Chen et al. [2021] show an alternative proof through
via the minimax theorem and a novel geometric approach. Suzdaltsev [2020a]
studies almost the same problem as ours – in his model there is also more than
one i.i.d. bidder, but unlike us he only considers _deterministic_ mechanisms.
He therefore gets a completely different design with no reserve price, which
does not form an equilibrium of the zero-sum game.

To our knowledge, the first works on parametric information were by Azar and
Micali [2013] and Azar et al. [2013], in the context of prior-independent
mechanism design. En route to prior-independence, Azar and Micali [2013] find
a deterministic max-min solution in a setting with multiple bidders and
_infinitely many copies_ of the item – their setting is thus closer to a
single-bidder setting than to a multi-bidder one. Allouah and Besbes [2020]
also study prior-independence with parametric information.

Robustness for two bidders. Several recent works on robust mechanism design
focus on the canonical two-bidder case, but in different contexts than ours:
First, a central open question in prior-independent mechanism design is to
identify the prior-independent revenue-optimal mechanism for selling a single
item to two agents with i.i.d. values. There is a line of work on this
question, including Hartline et al. [2020], Fu et al. [2015], Dhangwatnotai et
al. [2015], Allouah and Besbes [2020]. Hartline and Johnsen [2021] develop a
method for lower-bounding prior-independent guarantees and apply it to a pair
of two-bidder problems. Bergemann et al. [2021] study max-min auction design
for two bidders, but where the seller’s uncertainty is about the correct model
of the bidders’ beliefs on the item’s quality, so the max-min optimum is very
different than ours.

##  2 Model

###  2.1 Parametric Auction Settings

We study a simple auction setting in which a seller offers a single item to
$n$ bidders. Each bidder $i$ has a privately-known value $v_{i}\geq 0$ for the
item, and the values are i.i.d. samples from a distribution $F$. Let
$\vec{v}=(v_{1},\dots,v_{n})$. The goal of the seller (a.k.a.  _designer_) is
to maximize her expected revenue from selling the item to the competing
bidders, where the expectation is taken over the random values as well as the
internal randomness of the mechanism. What distinguishes our setting from
standard mechanism design is that the seller has only _parametric knowledge_
of the distribution $F$. We denote the parameters of the distribution as
follows: let $\mu$ be its expectation, and let $\overline{v}$ be an upper
bound on its support, i.e.:

$\mathbb{E}_{v_{i}\sim F}[v_{i}]=\mu;~{}~{}~{}v_{i}\in[0,\overline{v}].$

A parametric auction setting is thus defined by a pair $(\mu,\overline{v})$.
Let $\mathcal{F}=\mathcal{F}(\mu,\overline{v})$ be the space of all
_compatible_ distributions, where $F$ is compatible if it has expectation
$\mu$ and support within $[0,\overline{v}]$.

The design space: Truthful auctions. The auctions we consider as the seller’s
design space are standard: The bidders submit bids $b_{1},\dots,b_{n}$ for the
item. The seller uses an allocation rule (possibly randomized) to map the bids
$\vec{b}=(b_{1},\dots,b_{n})$ to an allocation of the item. A payment rule $p$
determines how much to charge the bidders in expectation: $p_{i}(\vec{b})$ is
the expected payment of bidder $i$ given bid profile $\vec{b}$. The allocation
and payment rules may depend on the parametric knowledge of the distribution
from which the bids are independently drawn.

Bidders have quasi-linear utilities: bidder $i$’s expected utility is his
expected value for the (possibly randomized) allocation, less his expected
payment $p_{i}(\vec{b})$. We focus on _truthful_ – i.e., dominant-strategy
_incentive compatible (IC)_ and _individually rational (IR)_ – auctions, where
the bidders maximize their expected utilities by participating and reporting
their true values to the seller (regardless of how others report).555Since
distribution $F$ is unknown, the natural truthfulness notion in our model is
dominant-strategy rather than Bayesian, since it is hard to predict how
bidders would behave under uncertainty Bei et al. [2019]. Even if bidders did
know the distribution, one would like mechanisms that do not rely on the
bidders’ precise knowledge, especially since such mechanisms tend to be
unnatural (i.e., asking the bidders to report the distribution, and punishing
them all if the reports disagree). Thus we can assume $\vec{b}=\vec{v}$.
Requiring truthfulness is without loss of generality by the revelation
principle Myerson [1981]. Denote the design space of truthful auctions for a
parametric auction setting $(\mu,\overline{v})$ by
$\mathcal{M}=\mathcal{M}(\mu,\overline{v})$.

A reduced design space: Second-price auctions with a random reserve. A simple,
ubiquitous auction format that will play a central role in our results is the
_second price auction with reserve_. Let $r$ (or $R$) denote the reserve
price. This auction is (dominant-strategy) truthful, so we can assume that the
bidders truthfully report $v_{1},\dots,v_{n}$ as their bids. The item is
allocated to a highest bidder $i^{*}\in\operatorname*{argmax}_{i}\\{v_{i}\\}$
if the highest value $v_{i^{*}}$ strictly exceeds the reserve $r$ (tie-
breaking among the bidders can be arbitrary). The item is not allocated if
neither value clears the reserve. If the item is allocated, the winner’s
payment is the maximum between the reserve $r$ and the second-highest bid.
Note that the reserve price is allowed to be _randomized_ ; we denote the
distribution over reserve prices by $Q$. We are interested in studying the
reduced design space of second-price auctions with a random reserve. If the
seller is limited to the reduced design space, then $Q$ will be chosen
depending on the seller’s parametric knowledge. Denote the space of
distributions over the reserve price (which constitutes the reduced design
space) by $\mathcal{Q}=\mathcal{Q}(\mu,\overline{v}$).

###  2.2 Robust Revenue Performance and Zero-Sum Games

The seller’s goal is to use her parametric knowledge of the value distribution
to choose an auction $M$ with optimal _robust revenue performance_ – the
expected revenue of $M$ when the bidders’ values are drawn from the _worst-
case_ compatible distribution $F\in\mathcal{F}$. Following a long tradition in
robust mechanism design Wald [1950], we approach this problem by treating it
as a zero-sum game between two players: the seller, and a player we refer to
as the _adversary_ or _nature_.

The general zero-sum game. In the general zero-sum game, the seller can choose
any mechanism $M$ in the design space $\mathcal{M}$ as her action. The action
space of the adversary is $\mathcal{F}$, consisting of every compatible
distribution $F$. For a pair of actions $(M,F)$, the seller’s payoff is the
revenue of $M$ in expectation over its internal randomness as well as over the
random i.i.d. values $v_{1},\dots,v_{n}$ drawn from $F$. We denote this payoff
by $\operatorname*{Rev}_{F}(M)$ where

$\operatorname*{Rev}_{F}(M)=\mathbb{E}_{v_{1},v_{2}\sim_{\operatorname*{i.i.d.}}F}\left[\sum_{i}p_{i}(\vec{v})\right]$

(recall that $p$ is the payment rule of $M$; the adversary’s payoff is of
course $-\operatorname*{Rev}_{F}(M)$).

The reduced zero-sum game. We are also interested in a related zero-sum game
in which the action space of the adversary is unchanged, and the action space
of the seller is reduced to include only second-price auctions with random
reserves. This action space can be described as $\mathcal{Q}$, where every
$Q\in\mathcal{Q}$ is a distribution over reserve prices. Note that in a
setting where there is a known upper bound $\overline{v}$ on the values, there
is no point in setting a reserve price above $\overline{v}$. Therefore from
now on we assume without loss that $\mathcal{Q}$ contains only distributions
with supports contained in $[0,\overline{v}]$.

To define the payoff of the reduced zero-sum game, we introduce the following
(slightly overloaded) notation: let $\operatorname*{Rev}_{F}(r)$ denote the
expected revenue of the second-price auction with a fixed reserve price $r$
(the expectation is over the i.i.d. values from $F$). For a pair of actions
$(Q,F)$, the seller’s payoff is $\operatorname*{Rev}_{F}(r)$ in expectation
over the random reserve $r\sim Q$. We denote this payoff by

$\operatorname*{Rev}_{F}(Q)=\mathbb{E}_{r\sim
Q}\left[\operatorname*{Rev}_{F}(r)\right].$

Problem formulation. In each of the zero-sum games, the seller’s problem is to
find a max-min strategy. In fact, we seek an equilibrium for each of the zero-
sum games.666The advantage of an equilibrium is that it ensures the seller’s
strategy is stable, i.e., the seller would not gain from deviating. We denote
an equilibrium of the general zero-sum game by $(M^{*},F^{*})$, and refer to
the problem of finding it by Problem (P1). We denote an equilibrium of the
reduced zero-sum game by $(Q^{*},F^{*})$, and refer to the problem of finding
it by Problem (P2):

$\displaystyle M^{*}$
$\displaystyle\in\operatorname*{argmax}_{M\in\mathcal{M}}\min_{F\in\mathcal{F}}\operatorname*{Rev}_{F}(M),$
$\displaystyle F^{*}$
$\displaystyle\in\operatorname*{argmin}_{F\in\mathcal{F}}\max_{M\in\mathcal{M}}\operatorname*{Rev}_{F}(M);$
(P1) $\displaystyle Q^{*}$
$\displaystyle\in\operatorname*{argmax}_{Q\in\mathcal{Q}}\min_{F\in\mathcal{F}}\operatorname*{Rev}_{F}(Q),$
$\displaystyle F^{*}$
$\displaystyle\in\operatorname*{argmin}_{F\in\mathcal{F}}\max_{Q\in\mathcal{Q}}\operatorname*{Rev}_{F}(Q).$
(P2)

Observe that $M^{*}$ (respectively, $Q^{*}$) maximizes the robust revenue
performance over the seller’s design space (respectively, reduced design
space), since in both cases the worst-case $F\in\mathcal{F}$ is chosen. Thus,
solving Problem (P1) achieves our ultimate goal of finding the auction with
optimal robust revenue performance.

Note that it is not immediately clear that the general and the reduced zero-
sum games have equilibria; there is a large supply of minimax theorems that
can potentially be applied, but this is redundant as we shall explicitly
construct pure-strategy equilibria for both games.

A note on coinciding with the reserve price. Notice that in our formulation of
second-price auctions with a reserve price, the item is sold only when there
is at least one bidder with a _strictly_ higher bid than the reserve. The
strictness is not necessary for our results, but guarantees the existence of a
worst-case distribution $F$ for any distribution $Q$ over reserve prices: For
example, if the seller (who chooses $Q$) places a probability mass on reserve
price $r$, our formulation avoids a situation where the adversary (who chooses
$F$) wishes to place probability mass on values as close as possible to $r$
from below, but not on $r$ itself. In this situation, without strictness, $F$
could only approach the worst case distribution but could never quite reach
it.

Distributions of interest. The _equal-revenue_ distribution “arises in many
examples” in the mechanism design literature [Hartline, 2021, Chapter 4]. In
most appearances in the literature, the support of this distribution is
$[1,\infty)$ or $[1,\overline{v}]$ in truncated versions. We consider a
slightly generalized version in which the support is
$[\underline{v},\overline{v}]$: the CDF is
$F(v)=1-\nicefrac{{\underline{v}}}{{v}}$ for
$v\in[\underline{v},\overline{v})$, and $F(\overline{v})=1$. Another
distribution of interest for us is the _reciprocal_ or _log-uniform_
distribution: the CDF is
$F(v)=\frac{\log\nicefrac{{v}}{{\underline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}$
for $v\in[\underline{v},\overline{v}]$. Throughout, all logarithms are in the
natural base $e$ unless indicated otherwise.

##  3 The Case of Two Bidders

In this section we solve Problem (P1), when there are only two bidders. We
will achieve that by solving Problem (P2), and proving that no mechanism can
do better.

######  Theorem 3.1 (Solution of Problem (P2) for two bidders).

When there are two bidders, there exists an equilibrium
$\left(Q^{*},F^{*}\right)\in\mathcal{Q}\times\mathcal{F}$ that solves Problem
(P2). The equilibrium is described by:

$\displaystyle F^{*}(v)$
$\displaystyle=\begin{cases}0&v\in[0,\underline{v}],\\\
1-\nicefrac{{\underline{v}}}{{v}}&v\in[\underline{v},\overline{v}),\\\
1&v\geq\overline{v}\end{cases},$ $\displaystyle Q^{*}(r)$
$\displaystyle=\begin{cases}\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)\cdot\left(\frac{1}{\log\overline{v}-\log\underline{v}}\right)&r\in[0,\underline{v}],\\\
\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)\cdot\left(\frac{r}{r-\underline{v}}\right)\cdot\left(\frac{\log
r-\log\underline{v}}{\log\overline{v}-\log\underline{v}}\right)&r\in(\underline{v},\overline{v}],\end{cases}$

where $\underline{v}$ is the unique solution to
$\underline{v}\left(1+\log\overline{v}-\log\underline{v}\right)=\mu$.

Figure 1:  The solution to Problem (P2) with two bidders for the parametric
settings in which $\mu=0.3$ and $\overline{v}=1$. The pair $(F^{*},Q^{*})$ is
an equilibrium of the reduced zero-sum game, where $F^{*}$ is the adversarial
distribution of bidder values, and $Q^{*}$ is the seller’s distribution over
reserve prices for the second-price auction. $F^{*}$ is a generalized equal-
revenue distribution with support $[\underline{v},\overline{v}]$ for an
appropriate $\underline{v}$, and $Q^{*}$ is a ratio of a log-uniform
distribution and an equal-revenue one, with the same support. In fact, we show
that $(F^{*},Q^{*})$ also constitutes a solution to Problem (P1), yielding a
distributionally-robust optimal auction for two bidders.

Interestingly, the distribution chosen by the adversary is identical to the
case of a single bidder solved by Carrasco et al. [2018]. The distribution
chosen by the seller is different: it has a positive mass on zero, and the
rest of the mass is spread continuously on $[\underline{v},\overline{v}]$.
This is illustrated (for a particular parametric setting) in Fig 1. For a
single bidder, the seller chooses the log-uniform distribution
$\frac{\log\nicefrac{{r}}{{\underline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}$.
In the two bidder case, we observe that the sellers uses the log-uniform
distribution divided by the equal-revenue distribution, and normalized to be
in $[0,1]$.

An important and possibly surprising implication of Theorem 3.1 is that the
second-price auction with a randomized reserve sampled from $Q^{*}$ is an
_overall_ robustly optimal mechanism. This constitutes our main result for two
bidders and is proven in Section 3.4.

######  Theorem 3.2 (Main: Solution of Problem (P1) for two bidders).

Let $M^{*}$ be the second-price auction with randomized reserve sampled from
$Q^{*}$, where $Q^{*}$ is as described in Theorem 3.1. Let $F^{*}$ be as
described in Theorem 3.1 as well. Then, if there are exactly two bidders, then
$(M^{*},F^{*})$ is an equilibrium that solves Problem (P1).

Proof overview. Since the adversary is limited to choosing only distributions
with a known mean value, we can use the method of Lagrange multipliers, and
find a saddle point for the Lagrangian developed in Section 3.1. In Section
3.2 we consider a discrete case, where the seller’s possible reserve prices,
and the bidders’ possible valuations are limited to a finite set. We then find
certain conditions that a saddle point of the Lagrangian would satisfy in the
discrete case (Claims 3.4-3.5). Afterwards, by importing these conditions to
the general case, we find ODEs which we suspect that a saddle point for the
non-discrete Lagrangian would satisfy, and use them to find a candidate
solution $(Q^{*},F^{*})$ (Section 3.3). After finding the suspected solution
$(Q^{*},F^{*})$, we prove in Section 3.4 that it is a saddle point of the
Lagrangian, and simultaneously prove that no other mechanism could achieve a
better expected revenue if the adversary does choose distribution $F^{*}$.
This completes the proof.

A discrete-to-continuous technique of possible independent interest. Note that
our proof, in particular Section 3.3, uses a technique that allows us to go
from the discrete case to the general case, as follows. As described in the
proof overview, in Section 3.2 we find conditions which a saddle point of the
Lagrangian (i.e. an equilibrium of the discrete game) would satisfy assuming
it’s not on the boundary. Roughly, these conditions describe a recursive
relation that adjacent points in the discretization should satisfy to be an
equilibrium. For example, if we consider points $y_{1},\dots,y_{k}$ of the
discrete grid, a recursive relation is of the form $y_{i+1}=\psi(y_{i},\dots)$
(where the $\dots$ can be replaced by additional arguments).

In Section 3.3 we wish to go from the discrete to the general case. We do this
by making the discretization finer and finer, and more importantly,
translating the recursive relation into an ODE condition that holds in the
limit. Interestingly, we do not need to solve the discrete case, prove that
the limit exists, nor show that the condition on the limit necessarily holds.
This is because we use this technique only to derive a guess of what the
equilibrium is in the general case, and later prove that we guessed correctly.
For a complete picture however, in Appendices A-C we prove the correctness of
this technique, namely we solve the discrete case, and establish both
convergence and that the resulting ODE condition on the equilibrium indeed
holds. This proof of correctness strengthens our belief that the described
discrete-to-continuous technique may be of independent interest.

###  3.1 The Lagrangian for Maximizing Expected Revenue

We denote by $v^{(i)}$ the $i$-th highest valuation of the bidders. When the
seller uses a second price auction with a reserve price $r$, the expected
revenue is given by

$\displaystyle\operatorname*{Rev}_{F}(r)$ $\displaystyle=E\left[r\cdot
1_{v^{\left(2\right)}\leq
r<v^{\left(1\right)}}\right]+E\left[v^{\left(2\right)}\cdot
1_{r<v^{\left(2\right)}}\right]$
$\displaystyle=r\left(1-F^{2}\left(r\right)\right)+\int_{r}^{\overline{v}}\left(1-F\left(v\right)\right)^{2}dv.$

Therefore, when the seller randomizes a reserve price sampled from
distribution $Q$, the expected revenue is

$\displaystyle\operatorname*{Rev}_{F}(Q)$
$\displaystyle=\int_{-\infty}^{\infty}\left(r\left(1-F^{2}\left(r\right)\right)+\int_{r}^{\overline{v}}\left(1-F\left(v\right)\right)^{2}dv\right)dQ\left(r\right).$

We can assume that $Q$’s support is contained in $[0,\overline{v})$, since
negative reserve price is meaningless, and reserve price of $\overline{v}$ or
higher would yield now revenue. If we also assume that $Q$ is continuous over
$(0,\overline{v})$ and differentiable almost everywhere, we get

$\displaystyle\operatorname*{Rev}_{F}(Q)$
$\displaystyle=Q\left(0\right)\int_{0}^{\overline{v}}\left(1-F\left(v\right)\right)^{2}dv+\int_{0}^{\overline{v}}Q^{\prime}\left(r\right)\left(r\left(1-F^{2}\left(r\right)\right)+\int_{r}^{\overline{v}}\left(1-F\left(v\right)\right)^{2}dv\right)dr$
$\displaystyle=\int_{0}^{\overline{v}}\left(Q^{\prime}\left(v\right)v\left(1-F^{2}\left(v\right)\right)+Q\left(v\right)\left(1-F\left(v\right)\right)^{2}\right)dv.$

To get this we use

$\displaystyle\int_{0}^{\overline{v}}\int_{r}^{\overline{v}}Q^{\prime}\left(r\right)\left(1-F\left(v\right)\right)^{2}dvdr$
$\displaystyle=\int_{0}^{\overline{v}}\int_{0}^{v}Q^{\prime}\left(r\right)\left(1-F\left(v\right)\right)^{2}drdv$
$\displaystyle=\int_{0}^{\overline{v}}\left(1-F\left(v\right)\right)^{2}\left(Q\left(r\right)-Q\left(0\right)\right)dv.$

Since nature is limited to choose distributions with a mean value of $\mu$, we
have the constraint

$\int_{0}^{\overline{v}}\left(1-F\left(v\right)\right)dv=\mu.$

So we get the Lagrangian we get is

$\mathcal{L}(Q,F)=\int_{0}^{\overline{v}}\left(Q^{\prime}\left(v\right)v\left(1-F^{2}\left(v\right)\right)+Q\left(v\right)\left(1-F\left(v\right)\right)^{2}-\lambda\left(1-F\left(v\right)\right)\right)dv.$
(1)

######  Claim 3.3.

For every distribution $Q\in\mathcal{Q}$, and any $\lambda$, distribution $F$
minimizes $\operatorname*{Rev}_{F}(Q)$ over $\mathcal{F}$ if and only if $F$
minimizes $\mathcal{L}(Q,F)$ over $\mathcal{F}$.

###### Proof.

Since $\int_{0}^{\overline{v}}(1-F(v))dv=\mu$ for any $F\in\mathcal{F}$, then

$\mathcal{L}(Q,F)=\operatorname*{Rev}_{F}(Q)-\lambda\mu.$

The difference between the two functions does not depend on $F$, and that
completes the proof. ∎

###  3.2 The Discrete Case

For simpler analysis, we consider a discretization of the problem. Let $k>1$
be the discretization parameter. We effectively limit the support of the
seller’s distribution over reserve prices and the adversary’s distribution
over values to $k+1$ possible options
$\mathbf{r}_{k}=(r_{k,1},\dots,r_{k,k},r_{k,k+1})$, where
$r_{k,i}=\frac{i-1}{k}\cdot\overline{v}$ for every $1\leq i\leq k+1$.

In the discrete problem, the distribution functions are step functions with
jumps only on values of $\mathbf{r}_{k}$, so we can represent the
distributions using finite vectors $\mathbf{q},\mathbf{x}$ of size $k$, where
$q_{i}=Q(r_{k,i})$ and $x_{i}=F(r_{k,i})$. With this, we can represent the
revenue as a function of $\mathbf{q},\mathbf{x}$.

Similarly to how we got Formula (1), we get

$\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=\sum_{i=1}^{k}(q_{i}-q_{i-1})r_{k,i}(1-x_{i}^{2})+\frac{\overline{v}}{k}\cdot\sum_{i=1}^{k}q_{i}\left(1-x_{i}\right)^{2}-\lambda\frac{\overline{v}}{k}\sum_{i=1}^{k}\left(1-x_{i}\right),$
(2)

where $q_{0}=0$.

We note that we can also assume that $q_{k}=1$. That is because if $q_{k}<1$,
then there is a non zero probability for a reserve price of zero, which would
yield no revenue, because the seller will never sell the item.

We can use Formula (2) to find equations a saddle point should satisfy.

######  Claim 3.4.

For any $\mathbf{x}=(x_{1},\dots,x_{k})\in[0,\infty)^{k}$ and for every $1\leq
i\leq k-1$

$\frac{\partial}{\partial q_{i}}\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=0\iff
x_{i+1}=\sqrt{\frac{\overline{v}}{k}\cdot\frac{2}{r_{k,i}+\nicefrac{{\overline{v}}}{{k}}}(x_{i}-x_{i}^{2})+x_{i}^{2}}.$

Likewise, we do the same to describe $\mathbf{q}$.

######  Claim 3.5.

For any $\mathbf{x}\in(0,\overline{v})^{n}$,
$\mathbf{q}\in(0,\overline{v})^{n-1}$, and for every $2\leq i\leq k$

$\frac{\partial}{\partial x_{i}}\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=0\iff
q_{i-1}=q_{i}-\frac{\nicefrac{{\lambda}}{{2}}-q_{i}\left(1-x_{i}\right)}{r_{k,i}x_{i}}\cdot\nicefrac{{\overline{v}}}{{k}},$

and

$\frac{\partial}{\partial x_{1}}\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=0\iff
q_{1}=\frac{\lambda}{2(1-x_{1})}.$

Claims 3.4 and 3.5 provide a recurrence relation for a potential saddle point
of $\mathcal{L}_{k}$.

In order to continue with the proof of Theorem 3.1, we do not need to prove
anything more for the discrete case. However, it is also possible to prove the
existence of an equilibrium in the discrete case. We do it in Appendix A.

###  3.3 Candidate Equilibrium

Based on Claims 3.4 and 3.5, we are able to guess ODEs that an equilibrium for
the non-discrete problem would satisfy. We do not need to prove the steps to
achieve those ODEs, or that solving them is a saddle point of
$\mathcal{L}(Q,F)$. That is because the goal here is only to find candidates
for an equilibrium. Only after finding the candidates (see Equations (5) and
(7)), we prove in Section 3.4 that they do solve Problem (P1).

##### Guesses for ODEs based on the discrete case.

We assume that for any $k>1$, there exists
$\mathbf{q}_{k}^{*},\mathbf{x}_{k}^{*}$ that are a saddle point for
$\mathcal{L}_{k}(\mathbf{q},\mathbf{x})$. We denote the corresponding
distributions by $Q^{*}_{k},F^{*}_{k}$, which means that
$Q^{*}_{k}(r_{k,i})=q_{i}$, and $F^{*}_{k}(r_{k,i})=x_{i}$.

Next, we assume that there exist $Q^{*},F^{*}$ such that

$\displaystyle\lim_{k\to\infty}Q^{*}_{k}$ $\displaystyle=Q^{*},$
$\displaystyle\lim_{k\to\infty}F^{*}_{k}$ $\displaystyle=F^{*}.$

Based on Claim 3.4, we guess that for $F=F^{*}$

$\displaystyle\frac{dF(r)}{dr}$
$\displaystyle=\lim_{k\to\infty}\frac{F_{k}^{*}\left(r+\nicefrac{{\overline{v}}}{{k}}\right)-F_{k}^{*}(r)}{\nicefrac{{\overline{v}}}{{k}}}$
$\displaystyle=\lim_{\delta\to
0}\frac{\sqrt{\delta\cdot\frac{2}{r+\delta}(F(r)-F^{2}(r))+F^{2}(r)}-F(r)}{\delta}.$

This a partial derivative of the function

$\displaystyle\psi_{F}(\delta,r,y)=\sqrt{\delta\cdot\frac{2}{r+\delta}(y-y^{2})+y^{2}}.$

This is the function that describes the recursive relation in Claim 3.4, since
according to the claim,
$F_{k}^{*}(r_{k,i+1})=\psi_{F}\left(\nicefrac{{\overline{v}}}{{k}},r_{k,i},F_{k}^{*}(r_{k,i})\right)$.

This yields the ODE

$\displaystyle\frac{d}{dr}F^{*}(r)$
$\displaystyle=\frac{\partial\psi_{F}(\delta,r,y)}{\partial\delta}\left(0,r,F^{*}(r)\right)$
$\displaystyle=\frac{(1-F^{*}(r))F^{*}(r)}{rF^{*}(r)}$
$\displaystyle=\frac{1-F^{*}(r)}{r}.$ (3)

This only applies when $F^{*}(r)\neq 0$.777For the case where $F^{*}(r)=0$, we
can see that $\psi(\delta,r,0)=0$, and thus the derivative would be zero as
well.

We can use a similar idea for $Q^{*}$. We define

$\psi_{Q}(\delta,r,y,z)=y-\frac{\nicefrac{{\lambda}}{{2}}-y\left(1-z\right)}{rz}\cdot\delta.$

According to Claim 3.5

$Q^{*}_{k}\left(r_{k,i}-\nicefrac{{\overline{v}}}{{k}}\right)=\psi_{Q}\left(\nicefrac{{\overline{v}}}{{k}},r_{k,i},Q^{*}_{k}(r_{k,i}),F^{*}_{k}(r_{k,i})\right).$

And we guess that

$\displaystyle\frac{dQ^{*}(r)}{dr}$
$\displaystyle=\lim_{k\to\infty}\frac{Q_{k}^{*}\left(r-\nicefrac{{\overline{v}}}{{k}}\right)-F_{k}^{*}(r)}{-\nicefrac{{\overline{v}}}{{k}}}$
$\displaystyle=\lim_{\delta\to
0}\frac{\psi_{Q}\left(\delta,r,Q(r),F^{*}(r)\right)-\psi_{Q}\left(0,r,Q(r),F^{*}(r)\right)}{-\delta}.$
$\displaystyle=-\frac{\partial\psi_{Q}(\delta,r,y,z)}{\partial\delta}\left(0,r,Q^{*}(r),F^{*}(r)\right)$
$\displaystyle=\frac{\nicefrac{{\lambda}}{{2}}-Q^{*}(r)\left(1-F^{*}(r)\right)}{rF^{*}(r)}.$
(4)

##### Solution to the ODEs.

A solution for Eq (3) is of the form

$F^{*}(v)=1-\frac{c}{v},$

everywhere where $F^{*}(v)\neq 0$. With the assumptions of continuity over
$[0,\overline{v})$, and a mean value of $\mu$, we get

$F^{*}(v)=\begin{cases}0&v\in[0,\underline{v}),\\\
1-\nicefrac{{\underline{v}}}{{v}}&v\in[\underline{v},\overline{v}),\\\
1&v\geq\overline{v},\end{cases}$ (5)

where $\underline{v}\left(1+\log\overline{v}-\log\underline{v}\right)=\mu$.

Now, we can solve for the seller’s distribution. Since the ODE is not defined
where $F^{*}(r)=0$, it is only defined on $(\underline{v},\overline{v}]$. We
substitute $F^{*}(v)=1-\nicefrac{{\underline{v}}}{{v}}$ in Eq (4), and we get

$\frac{dQ(r)}{dr}=\frac{\nicefrac{{\lambda}}{{2}}-Q^{*}(r)\cdot\nicefrac{{\underline{v}}}{{r}}}{r-\underline{v}}.$

The solution to this ODE is

$Q^{*}(r)=\left(\frac{r}{r-\underline{v}}\right)\cdot\left(c+\nicefrac{{\lambda}}{{2}}\cdot\log
r\right),$

for an unknown $c$.

We know that the seller would never set a reserve price of $\overline{v}$, so
the continuity on $\overline{v}$ is known. Since $Q^{*}(\overline{v})=1$, we
can solve
$c=1-\nicefrac{{\underline{v}}}{{\overline{v}}}-\nicefrac{{\lambda}}{{2}}\log\overline{v}$,
and thus

$Q^{*}(r)=\left(\frac{r}{r-\underline{v}}\right)\cdot\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}-\nicefrac{{\lambda}}{{2}}\cdot\log\nicefrac{{\overline{v}}}{{r}}\right).$

We also know that as a distribution function, $Q^{*}(r)\in[0,1]$ for every
$r$. Since
$\lim_{r\to\underline{v}^{+}}\left(\frac{r}{r-\underline{v}}\right)=\infty$,
we know that

$\displaystyle 0$
$\displaystyle=\lim_{r\to\underline{v}^{+}}\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}-\nicefrac{{\lambda}}{{2}}\cdot\log\nicefrac{{\overline{v}}}{{r}}\right)$
$\displaystyle=1-\nicefrac{{\underline{v}}}{{\overline{v}}}-\nicefrac{{\lambda}}{{2}}\cdot\log\nicefrac{{\overline{v}}}{{\underline{v}}},$
$\displaystyle\implies\nicefrac{{\lambda}}{{2}}$
$\displaystyle=\frac{1-\nicefrac{{\underline{v}}}{{\overline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}.$
(6)

This suggests that for $r\in(\underline{v},\overline{v}]$

$Q^{*}(r)=\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)\cdot\left(\frac{r}{r-\underline{v}}\right)\cdot\left(\frac{\log
r-\log\underline{v}}{\log\overline{v}-\log\underline{v}}\right).$

Now we only need to solve for $r\in[0,\underline{v}]$. From Claim 3.5,
$Q^{*}_{k}(0)=\frac{\lambda}{2\left(1-F_{k}^{*}(0)\right)}$. Therefore

$\displaystyle Q^{*}(0)$
$\displaystyle=\frac{\lambda}{2\left(1-F^{*}(0)\right)}$
$\displaystyle=\frac{1-\nicefrac{{\underline{v}}}{{\overline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}.$

Likewise
$\lim_{r\to\underline{v}^{+}}Q^{*}(r)=\frac{1-\nicefrac{{\underline{v}}}{{\overline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}$,
and since $Q^{*}(r)$ is a distribution function, it is non-decreasing.
Therefore, our guess for $Q^{*}$ is

$Q^{*}(r)=\begin{cases}\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)\cdot\left(\frac{1}{\log\overline{v}-\log\underline{v}}\right)&r\in[0,\underline{v}],\\\
\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)\cdot\left(\frac{r}{r-\underline{v}}\right)\cdot\left(\frac{\log
r-\log\underline{v}}{\log\overline{v}-\log\underline{v}}\right)&r\in(\underline{v},\overline{v}].\end{cases}$
(7)

###  3.4 Proof of Theorem 3.2

We have guessed that $Q^{*},F^{*}$ (Equations (5)-(7)) are an equilibrium for
Problem (P2). We will prove this guess directly.

######  Claim 3.6.

If the seller uses a second price auction with a randomized reserve price
sampled from $Q^{*}$, then $F^{*}$ minimizes the expected revenue of the
seller among all distributions with a mean value of $\mu$, and support
contained in $[0,\overline{v}]$.

###### Proof.

We have previously found the Lagrangian for this problem in Eq (1). We will
minimize it point-wise, which means we need to minimize the integrand as a
function of $F(v)$, which we denote by $h_{v}(z)$. So

$\displaystyle
h_{v}\left(z\right)=Q^{\prime}\left(v\right)v\left(1-z^{2}\right)+Q\left(v\right)\left(1-z\right)^{2}-\lambda\left(1-z\right).$

We use
$\lambda=\frac{2\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}$
as in Eq (6). When $v\in(\underline{v},\overline{v}]$ we use
$Q\left(v\right)=\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)\cdot\left(\frac{v}{v-\underline{v}}\right)\cdot\left(\frac{\log
v-\log\underline{v}}{\log\overline{v}-\log\underline{v}}\right)$, which leads
to

$\displaystyle
h_{v}\left(z\right)=\left(\frac{1-\nicefrac{{\underline{v}}}{{\overline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)\left(\frac{v}{v-\underline{v}}\right)\left(\left(1-\frac{\underline{v}\log\nicefrac{{v}}{{\underline{v}}}}{v-\underline{v}}\right)\left(1-z^{2}\right)+\left(\log\nicefrac{{v}}{{\underline{v}}}\right)\left(1-z\right)^{2}-2\left(1-\nicefrac{{\underline{v}}}{{v}}\right)\left(1-z\right)\right).$

After deriving by $z$, and searching for a root of the derivative, we get

$\displaystyle\left(1-\frac{\underline{v}\log\nicefrac{{v}}{{\underline{v}}}}{v-\underline{v}}\right)z+\left(\log\nicefrac{{v}}{{\underline{v}}}\right)\left(1-z\right)$
$\displaystyle=1-\nicefrac{{\underline{v}}}{{v}},$ $\displaystyle\implies z$
$\displaystyle=1-\nicefrac{{\underline{v}}}{{v}}.$

We can also verify that the second derivative is positive, which proves that
$F(v)=1-\nicefrac{{\underline{v}}}{{v}}$ does minimizes the integrand point-
wise, for $v\in(\underline{v},\overline{v}]$.

When $v\in[0,\underline{v})$, we get that

$\displaystyle
h_{v}\left(z\right)=\left(\frac{1-\nicefrac{{\underline{v}}}{{\overline{v}}}}{\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)\left(z^{2}-1\right),$

which clearly has a minimum at $z=0$, proving that $F(v)=F^{*}(v)$ minimizes
the Lagrangian and thus the expected revenue among all distributions with
support contained in $[0,\overline{v}]$ and a mean value of $\mu$. ∎

######  Claim 3.7.

If the bidders’ valuation is sampled from $F^{*}$, using a second-price
auction with a randomized reserve price sampled from $Q^{*}$ maximizes the
expected revenue among all truthful mechanisms.

###### Proof.

$F^{*}$ coincides with the equal-revenue distribution on
$[\underline{v},\overline{v})$, which means the _virtual valuation_ there is
always zero. Therefore, since by Myerson [1981] the expected revenue of a
truthful mechanism is equal to the expected virtual welfare, it is fully
determined by the allocation rule in the case where the value is exactly
$\overline{v}$. The maximum revenue is achieved if the item is always
allocated to a seller with value $\overline{v}$ if one exists. Since this is
the case for a second price auction with randomized price sampled from
$Q^{*}$, then it maximizes the expected revenue among all truthful mechanisms.
∎

Claims 3.3, 3.6 and 3.7 simultaneously complete the proof for both Theorem 3.1
and Theorem 3.2.

##  4 Beyond Two Bidders

In this section we assume that are $n$ bidders, and find the optimal pricing
distribution the seller can use in a second price auction with a randomized
reserve price.

######  Theorem 4.1 (Solution of Problem (P2) for $n\geq 3$ bidders).

Consider $n\geq 3$ bidders. There exists an equilibrium
$\left(Q^{*},F^{*}\right)\in\mathcal{Q}\times\mathcal{F}$ that solves Problem
(P2). Let $\underline{v}$ be the smaller among the two solutions to

$\left(n-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}\right)\underline{v}=\left(n-1\right)^{2}\mu.$

If $\underline{v}\leq\overline{v}$ then the equilibrium is described by:

$\displaystyle F^{*}(v)$
$\displaystyle=\begin{cases}0&v\in\left[0,v_{0}\right),\\\
1-\frac{1}{\left(n-1\right)^{2}}&v\in\left[v_{0},\underline{v}\right),\\\
1-\frac{v_{0}}{v\left(n-1\right)}&v\in[\underline{v},\overline{v}),\\\
1&v\geq\overline{v},\end{cases}$ $\displaystyle Q^{*}(r)$
$\displaystyle=\begin{cases}\left(1-\frac{v_{0}}{\overline{v}\left(n-1\right)}\right)^{n-1}\left(\frac{\left(n-1\right)^{2}}{\left(n-1\right)^{2}-1}\right)^{n-1}\left(\frac{n-1-\frac{1}{n-1}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)&r\in[0,\underline{v}),\\\
\left(1-\frac{v_{0}}{\overline{v}\left(n-1\right)}\right)^{n-1}\left(\frac{\left(n-1\right)r}{\left(n-1\right)r-v_{0}}\right)^{n-1}\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{r}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)&r\in[\underline{v},\overline{v}],\end{cases}$

where $v_{0}=\frac{\underline{v}}{n-1}$.

If $\underline{v}\geq\overline{v}$, the equilibrium is described by

$\displaystyle F^{*}(v)$
$\displaystyle=\begin{cases}0&v\in\left[0,v_{0}\right),\\\
1-\frac{1}{(n-1)^{2}}&v\in[v_{0},\overline{v}),\\\
1&v\geq\overline{v},\end{cases}$ $\displaystyle Q^{*}(r)$
$\displaystyle=1\quad r\geq 0,$

where $v_{0}=\mu-\frac{\overline{v}-\mu}{\left(n-1\right)^{2}-1}$.

Note that for $\underline{v}=\overline{v}$ the two expressions for
$(F^{*},Q^{*})$ coincide.

This theorem is true for $n\geq 3$, since for $n=2$, $Q^{*}(r)$ as defined
here is not defined for $r\in[0,\underline{v}]$. However, the theorem does
agree with Theorem 3.1 over $(\underline{v},\overline{v}]$, which means that
the limit $\lim_{r\to\underline{v}^{+}}Q^{*}(r)$ is the same as in Theorem
3.1.

Figure 2:  The solution $(F,Q)$ to Problem (P2) for the parametric settings in
which $n=3,\mu=0.3$ and $\overline{v}=1$. $F$ represents that each of the
bidders has a probability of $\nicefrac{{3}}{{4}}$ to have a valuation of
$v_{0}=0.0965$, and otherwise sample a valuation from a generalized truncated
equal-revenue distribution between $\underline{v}=0.193$ to $1$. $Q$ is a
ratio of a truncated log-uniform distribution and an equal-revenue
distribution to the power of $n-1$, with the same support.

Figure 3:  The solution to Problem (P2) for the parametric settings in which
$n=3,\mu=\nicefrac{{2}}{{3}}$ and $\overline{v}=1$. In this case $\mu$ is
sufficiently large that the seller would always choose a reserve price of 0,
and each of the bidders randomizes between $v_{0}=\nicefrac{{5}}{{9}}$ with
probability $0.75$, and $\overline{v}=1$.

Unlike the case where there are two bidders that we have solved with Theorem
3.1, or the case with a single bidder solved by Carrasco et al. [2018], the
adversary’s optimal distribution is not a truncated equal revenue
distribution, as it has a point of discontinuity at
$v_{0}\in(0,\overline{v})$. As a result, this mechanism is not the optimal
among all truthful mechanisms; we expand upon this point in Section 4.6. The
theorem also shows that depending on $n$, if the known upper bound is small
enough (or equivalently, the mean value is large enough), then the optimal
pricing distribution is to always choose a reserve price of zero, which simply
results in a standard second price auction. When the upper bound is large
enough, the seller would do better by randomizing between a reserve price of
zero, and a reserve price sampled from a truncated log-uniform distribution
divided by $(F^{*})^{n-1}$. We illustrate the optimal distributions in Figures
3 and 3.

Proof overview. The proof starts in a similar way to the proof of Theorem 3.1
by developing the Lagrangian (Section 4.1). In Section 4.2 we define the
discrete case, and use it to find ODEs that an equilibrium would satisfy.
However, in this case, assuming continuity will result with a non monotone
CDF, which is impossible (see failed attempt described in Section 4.3). This
leads us to guess equilibrium distributions, which are not continuous, but
depend on some unknown parameters (also in Section 4.3). After guessing the
potential equilibrium, in (Section 4.4) we set the unknown parameters in such
a way that will allow us to prove that both the seller and nature are playing
a best response to the other player’s chosen distribution (the proof appears
in Section 4.5).

###  4.1 The Lagrangian for Maximizing Expected Revenue

We write the formula for the expected revenue, with $n$ bidders.

######  Claim 4.2.

For any $F\in\mathcal{F}$, and distribution $Q\in\mathcal{Q}$ that is
continuous over $(0,\overline{v}]$, the revenue is expressed by

$\operatorname*{Rev}_{F}(Q)=\int_{0}^{\overline{v}}\left(Q^{\prime}\left(v\right)v\left(1-F^{n}\left(v\right)\right)+Q\left(v\right)\left(1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)\right)\right)dv.$

Since nature is limited to a known expected value, we will minimize the
Lagrangian instead, where the Lagrangian is defined as

$\displaystyle\mathcal{L}(Q,F)=$
$\displaystyle\operatorname*{Rev}_{F}(Q)-\lambda\int_{0}^{\overline{v}}\left(1-F(v)\right)dv.$
(8)

Similarly to the two bidder case, it is enough to solve the problem on
$\mathcal{L}$ instead of $\operatorname*{Rev}$.

###  4.2 ODEs through the Discrete Case

Like in the two bidder case, we consider a discretization of the problem. Let
$k>1$ be the discretization parameter. We limit the support of the seller’s
distribution over reserve prices and the adversary’s distribution over values
to $k+1$ possible options $\mathbf{r}_{k}=(r_{k,1},\dots,r_{k,k},r_{k,k+1})$,
where $r_{k,i}=\frac{i-1}{k}\cdot\overline{v}$ for every $1\leq i\leq k+1$.

Like in the two bidder case, we can represent the distributions using finite
vectors $\mathbf{q},\mathbf{x}$ of size $k$, where $q_{i}=Q(r_{k,i})$ and
$x_{i}=F(r_{k,i})$. The Lagrangian we get is

$\displaystyle\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=\sum_{i=1}^{k}\left(\left(q_{i}-q_{i-1}\right)r_{k,i}\left(1-x_{i}^{n}\right)+\nicefrac{{\overline{v}}}{{k}}\cdot
q_{i}\left(1-nx_{i}^{n-1}+\left(n-1\right)x_{i}^{n}\right)-\nicefrac{{\overline{v}}}{{k}}\cdot\lambda\left(1-x_{i}\right)\right).$

Since we are looking for a saddle point, we find conditions for the derivative
to be zero.

######  Claim 4.3.

For any $\mathbf{x}=(x_{1},\dots,x_{k})\in[0,\infty)^{k}$ and for every $1\leq
i\leq k-1$, the Lagrangian for $n$ bidders satisfies

$\frac{\partial}{\partial q_{i}}\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=0\iff
x_{i+1}=\sqrt[n]{\frac{n}{r_{k,i}+\nicefrac{{\overline{v}}}{{k}}}\left(x_{i}^{n-1}-x_{i}^{n}\right)\cdot\frac{\overline{v}}{k}+x_{i}^{n}}.$

######  Claim 4.4.

For any $\mathbf{x}\in(0,\overline{v})^{n}$,
$\mathbf{q}\in(0,\overline{v})^{n-1}$, and for every $2\leq i\leq k$, the
Lagrangian for $n$ bidders satisfies

$\frac{\partial}{\partial x_{i}}\mathcal{L}_{k}(\mathbf{q},\mathbf{x})=0\iff
q_{i-1}=q_{i}-\frac{\nicefrac{{\lambda}}{{n}}-q_{i}\left(n-1\right)x_{i}^{n-2}\left(1-x_{i}\right)}{r_{k,i}x_{i}^{n-1}}\cdot\nicefrac{{\overline{v}}}{{k}}.$

We do not prove these claims, since the proofs are almost identical to the
proofs of Claims 3.4-3.5.

Like in the two bidder case, we find ODEs based on Claims 4.3-4.4. We define

$\psi_{F}(\delta,v,y)=\sqrt[n]{\frac{n}{v+\delta}\left(y^{n-1}-y^{n}\right)\delta+y^{n}},$

and we get the ODE

$\displaystyle\frac{d}{dr}F(r)$
$\displaystyle=\frac{\partial\psi_{F}(\delta,r,y)}{\partial\delta}\left(0,r,F(r)\right)$
$\displaystyle=\frac{1-F(r)}{r}.$ (9)

Likewise, we define

$\displaystyle\psi_{Q}(\delta,r,y,z)=y-\frac{\nicefrac{{\lambda}}{{n}}-y\left(n-1\right)z^{n-2}\left(1-z\right)}{rz^{n-1}}\cdot\delta,$

and we get the ODE

$\displaystyle\frac{d}{dr}Q(r)$
$\displaystyle=-\frac{\partial\psi_{Q}(\delta,r,y,z)}{\partial\delta}\left(0,r,Q(r),F(r)\right)$
$\displaystyle=\frac{\lambda}{nrF^{n-1}(r)}-\frac{\left(n-1\right)Q(r)\left(1-F(r)\right)}{rF(r)}.$
(10)

###  4.3 Failed Attempt and Intuition

Here we attempt the same approach as in the case of two bidders and show that
it fails. Through the failed attempt we gain intuition for the correct shape
of the equilibrium.

We assume first that there exist $Q^{*},F^{*}$ that are an equilibrium for
Problem (P2), and they solve the ODEs (9)-(10), everywhere where their
derivative is positive.888The reason we don’t assume the ODEs are correct when
the derivative is zero, is that a negative derivative may produce better
results, but it’s impossible for a distribution function, which mean that the
derivative in the discrete case may not be zero.

If $F^{*}(v)$ is continuous over $[0,\overline{v})$ and differentiable almost
everywhere on the same interval, then

$F^{*}(v)=\begin{cases}0&v\in[0,\underline{v}],\\\
1-\nicefrac{{\underline{v}}}{{v}}&v\in[\underline{v},\overline{v}),\\\
1&v\geq\overline{v},\end{cases}$

where $\underline{v}$ is defined such that the mean value would be $\mu$. If
that is the case, then we can solve for $Q^{*}$ similarly to how we solve it
in the two bidder case, and we get

$\displaystyle
Q^{*}(r)=\left(\frac{r}{r-\underline{v}}\right)^{n-1}\left(\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)^{n-1}+\frac{\lambda\log\nicefrac{{r}}{{\overline{v}}}}{n}\right),$

for any $r\in(\underline{v},\overline{v}]$. However, even if we use the
$\lambda$ that solves
$\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}+\frac{\lambda\log\nicefrac{{r}}{{\overline{v}}}}{n}=0$,
we still end up with

$\lim_{r\to\underline{v}^{+}}\left(\frac{r}{r-\underline{v}}\right)^{n-1}\left(\left(1-\nicefrac{{\underline{v}}}{{\overline{v}}}\right)^{n-1}+\frac{\lambda\log\nicefrac{{r}}{{\overline{v}}}}{n}\right)=\infty.$

This is impossible, which suggests that our assumptions are incorrect. The
most “suspicious” assumption is the continuity of $F^{*}$ over
$[0,\overline{v})$. To fix this, we guess that $F^{*}$ has mass on a point
$v_{0}$, which together with the ODE (9), results with

$\displaystyle F^{*}(v)$ $\displaystyle=\begin{cases}0&v\in[0,v_{0}),\\\
1-\nicefrac{{a}}{{\underline{v}}}&v\in[v_{0},\underline{v}),\\\
1-\nicefrac{{a}}{{v}}&v\in[\underline{v},\overline{v}),\\\
1&v\geq\overline{v},\end{cases}$ (11)

for some unknown $0\leq a,v_{0},\underline{v}$. When we use the ODE (10) over
$[\underline{v},\overline{v}]$, with $Q^{*}(\overline{v})=1$, and
$F^{*}(v)=1-\nicefrac{{a}}{{v}}$, we get

$Q^{*}(r)=\left(\frac{r}{r-a}\right)^{n-1}\left(\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}+\frac{\lambda}{n}\log\nicefrac{{r}}{{\overline{v}}}\right).$

We guess that similarly to the two bidder case, $Q^{*}$ has no mass in
$(0,\underline{v})$, which means that our guess is

$Q^{*}(r)=\begin{cases}\left(\frac{\underline{v}}{\underline{v}-a}\right)^{n-1}\left(\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}+\frac{\lambda}{n}\log\nicefrac{{\underline{v}}}{{\overline{v}}}\right)&r\in[0,\overline{v}),\\\
\left(\frac{r}{r-a}\right)^{n-1}\left(\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}+\frac{\lambda}{n}\log\nicefrac{{r}}{{\overline{v}}}\right)&r\in[\underline{v},\overline{v}],\end{cases}$
(12)

where $a,\underline{v}$ are the same as in $F^{*}$, and $\lambda$ is unknown.

Our next goal is to find values of $a,v_{0},\underline{v}$ and $\lambda$ such
that those formulas will indeed describe an equilibrium. We will also find
when such values don’t exist, and prove that it only happens when a
deterministic reserve price of zero is the optimal pricing distribution for
the second price auction.

###  4.4 Candidate Equilibrium

We will now find $a,v_{0},\underline{v},\lambda$ such that $(Q^{*},F^{*})$ can
be an equilibrium. We will find equations that an equilibrium must satisfy.
Afterwards, we will be able to prove that $(Q^{*},F^{*})$ is indeed an
equilibrium.

Assume that there exist $a,v_{0},\underline{v}$, and $\lambda$ such that
$(Q^{*},F^{*})$ described by formulas (11) and (12) is an equilibrium. The
next three claims (Claims 4.5, 4.6, 4.7) provide four equations which the
variables must satisfy, allowing us to find their values.

######  Claim 4.5.

$a,v_{0}$ and $\underline{v}$ satisfy

$a\left(1-\frac{v_{0}}{\underline{v}}-\log\nicefrac{{\underline{v}}}{{\overline{v}}}\right)=\mu-
v_{0}.$

###### Proof.

This is equivalent to the constraint

$\int_{0}^{\overline{v}}(1-F^{*}(v))dv=\mu$

(using the definition of $F^{*}(v)$ according to (11)). ∎

If $(Q^{*},F^{*})$ is an equilibrium, that means that the seller cannot find a
better distribution than $Q^{*}$ if we fix $F^{*}$. Since
$\operatorname*{Rev}_{F^{*}}(Q^{*})=E_{r\sim
Q^{*}}\left[\operatorname*{Rev}_{F^{*}}(r)\right]$, and we know that
$\operatorname*{Rev}_{F^{*}}(Q^{*})\geq\operatorname*{Rev}_{F^{*}}(r)$ for
every $r$, than we can conclude that for every $r_{1},r_{2}$ in the support of
$Q^{*}$

$\operatorname*{Rev}_{F^{*}}(r_{1})=\operatorname*{Rev}_{F^{*}}(r_{2}).$

This requirement yields another equation according to the following claim.

######  Claim 4.6.

The following statements are equivalent

  * •

$\operatorname*{Rev}_{F^{*}}(r_{1})=\operatorname*{Rev}_{F^{*}}(r_{2})$ for
every $r_{1},r_{2}$ in the support of $Q^{*}$.

  * •

$a,v_{0}$ and $\underline{v}$ satisfy

$a\left(n-\left(n-1\right)\nicefrac{{v_{0}}}{{\underline{v}}}\right)=v_{0}.$

###### Proof.

If we fix $F=F^{*}$ as described in (11) by $a,v_{0}$ and $\underline{v}$, the
seller’s best pricing distribution would be any distribution over
$\operatorname*{argmax}_{r}\operatorname*{Rev}_{F}(r)$.

On $[\underline{v},\overline{v})$, we know that $F(v)=1-\frac{a}{v}$, and thus

$\frac{d}{dr}r(1-F^{n}(r))=1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right).$

Therefore, for every $r\in[\underline{v},\overline{v})$

$\displaystyle\operatorname*{Rev}_{F}(r)$
$\displaystyle=r\left(1-F^{n}\left(r\right)\right)+\int_{r}^{\overline{v}}\left(1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)\right)dv$
$\displaystyle=r\left(1-F^{n}\left(r\right)\right)+\left(\overline{v}\left(1-\lim_{v\to\overline{v}}F^{n}\left(v\right)\right)-r\left(1-F^{n}\left(r\right)\right)\right)$
$\displaystyle=\overline{v}\left(1-\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n}\right).$

This means that
$\operatorname*{Rev}_{F}(r_{1})=\operatorname*{Rev}_{F}(r_{2})$ for any
$r_{1},r_{2}\in[\underline{v},\overline{v})$.

Now, we only need to solve for
$\operatorname*{Rev}_{F}(0)=\operatorname*{Rev}_{F}(\underline{v})$. This is
equivalent to

$\int_{0}^{\underline{v}}\left(1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)\right)=\underline{v}\left(1-\left(1-\frac{a}{\underline{v}}\right)^{n}\right),$

which is

$v_{0}+\left(\underline{v}-v_{0}\right)\left(1-n\left(1-\frac{a}{\underline{v}}\right)^{n-1}+\left(n-1\right)\left(1-\frac{a}{\underline{v}}\right)^{n}\right)=\underline{v}\left(1-\left(1-\frac{a}{\underline{v}}\right)^{n}\right).$

This is equivalent to

$a\left(n-\left(n-1\right)\nicefrac{{v_{0}}}{{\underline{v}}}\right)=v_{0},$

which completes the proof. ∎

To make sure that $F^{*}$ is nature’s best response to $Q^{*}$, we will prove
that it minimizes the integrand

$Q^{\prime}\left(v\right)v\left(1-F^{n}\left(v\right)\right)+Q\left(v\right)\left(1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)\right)-\lambda(1-F(v))$

of the Lagrangian in (8) point-wise, where $Q=Q^{*}$. The next claim yields
two additional equations that make sure $F^{*}$ minimizes the integrand for
every $v\in[0,\underline{v})$.

######  Claim 4.7.

If $a,v_{0},\underline{v},$ and $\lambda$ satisfy

  * •

$\frac{\lambda}{Q^{*}(0)}=\frac{n}{n-1}\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n-2}$,

  * •

$a\left(n-1\right)^{2}=\underline{v}$,

then $F=F^{*}$ minimizes

$1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)-\frac{\lambda}{Q^{*}(0)}\left(1-F\left(v\right)\right),$

for every $v\in[0,\underline{v}]$.

###### Proof.

According to Lemma 3 in Suzdaltsev [2020a], if
$\frac{\lambda}{Q(0)}=\frac{n}{n-1}\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n-2}$,
then both $F(v)=0$, and $F(v)=1-\frac{1}{(n-1)^{2}}$ minimize the integrand
pointwise over $F(v)\in[0,1]$. So, when
$\frac{\lambda}{Q(0)}=\frac{n}{n-1}\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n-2}$,
we only need to make sure that
$F(v)\in\left\\{0,1-\frac{1}{(n-1)^{2}}\right\\}$ for every
$v\in[0,\underline{v}]$.

Since $F(v)=0$ for every $v\in[0,v_{0})$, we only demand that
$F(v)=1-\frac{1}{(n-1)^{2}}$ for every $v\in[v_{0},\underline{v}]$, which
yields $a\left(n-1\right)^{2}=\underline{v}$. ∎

Combining Claims 4.5, 4.6, 4.7 we get four equations that
$a,v_{0},\underline{v},\lambda$ must satisfy. This allows us to solve for
those variables. We get that $\underline{v}$ must solve

$\left(n-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}\right)\underline{v}=\left(n-1\right)^{2}\mu.$
(13)

This has a unique solution in $(0,\overline{v}]$ only if
$\left(n-\frac{1}{n-1}\right)\overline{v}>\left(n-1\right)^{2}\mu$, otherwise,
it has no solutions in $(0,\overline{v}]$. When it does have a solution, the
rest of the variables are described by

$\displaystyle v_{0}$ $\displaystyle=\frac{\underline{v}}{n-1},$ (14)
$\displaystyle a$ $\displaystyle=\frac{\underline{v}}{(n-1)^{2}},$ (15)
$\displaystyle\lambda$
$\displaystyle=\frac{n\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}.$
(16)

Now, when Eq (13) does have a solution in $(0,\underline{v}]$ we have a
candidate for an equilibrium.

###  4.5 Proof of Theorem 4.1

When we use Equations (13)-(16) and Formulas (12)-(11), we get the same
distributions as in Theorem 4.1, assuming $\underline{v}\leq\overline{v}$. We
now prove Claims 4.8 and 4.9 that establish these are valid distributions that
form an equilibrium. The complementary case $\underline{v}\geq\overline{v}$ is
addressed in Claim 4.10. Combining these claims proves the theorem.

######  Claim 4.8.

If $\underline{v}\in[0,\overline{v}]$ solves Eq (13), and $a,v_{0},\lambda$
are defined by Equations (14)-(16), then $F^{*},Q^{*}$ defined as in Formulas
(12), (11), are non decreasing and their image is contained in $[0,1]$.

###### Proof.

Since $0<a<\underline{v}$, then $F^{*}$ is non decreasing and its image is
contained in $[0,1]$. When using these values for $Q^{*}$, we get (when
$r\in[\underline{v},\overline{v}]$)

$Q^{*}(r)=\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{r}{r-a}\right)^{n-1}\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{r}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right).$
(17)

The derivative over $[\underline{v},\overline{v}]$ is

$\frac{Q^{*}(r)}{dr}=-\left(n-1\right)\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{r}{r-a}\right)^{n}\frac{\frac{\underline{v}}{n-1}\log\nicefrac{{r}}{{\underline{v}}}+\underline{v}-r}{r^{2}\left(\left(n-2\right)n+\left(n-1\right)\log\nicefrac{{\overline{v}}}{{\underline{v}}}\right)}.$

To show that this is non negative, we only need to prove that

$\frac{\underline{v}}{n-1}\log\nicefrac{{r}}{{\underline{v}}}+\underline{v}-r\leq
0.$

This is equivalent to

$\frac{\log\nicefrac{{r}}{{\underline{v}}}}{n-1}+1-\nicefrac{{r}}{{\underline{v}}}\leq
0,$

which is true for $r\in[\underline{v},\overline{v}]$, for any $n\geq 3$. ∎

The former claim proves that $Q^{*}$ and $F^{*}$ are distribution functions.
Now we will prove that they also solve Problem (P2).

######  Claim 4.9.

If $\underline{v}\in[0,\overline{v}]$ solves Eq (13), and $a,v_{0},\lambda$
are defined by Equations (14)-(16), and $F^{*},Q^{*}$ are defined as in
Formulas (12), (11), then $F=F^{*}$ minimizes the expression

$\frac{Q^{*}\left(v\right)}{dv}v\left(1-F^{n}\left(v\right)\right)+Q^{*}\left(v\right)\left(1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)\right)-\lambda\left(1-F\left(v\right)\right),$

for any $v\in[\underline{v},\overline{v})$ and $F$ that its image is contained
in $[0,1]$.

###### Proof.

For any $v\in[\underline{v},\overline{v})$ we define

$h_{v}(z)=\frac{dQ^{*}\left(v\right)}{dv}v\left(1-z^{n}\right)+Q^{*}\left(v\right)\left(1-nz^{n-1}+\left(n-1\right)z^{n}\right)-\lambda\left(1-z\right).$

We get

$\frac{dh_{v}(z)}{dz}=-n\frac{dQ^{*}\left(v\right)}{dv}vz^{n-1}-n\left(n-1\right)Q^{*}\left(v\right)\left(1-z\right)z^{n-2}+\lambda.$

After substituting for
$Q^{*}(v)=\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{v}{v-a}\right)^{n-1}\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{v}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)$,
and $z=1-\frac{a}{v}$, we get

$\displaystyle\frac{dh_{v}(z)}{dz}=$ $\displaystyle
n\left(n-1\right)\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{v}{v-a}\right)\frac{\left(n-1\right)a\log\nicefrac{{v}}{{\underline{v}}}+\underline{v}-v}{v\left(\left(n-2\right)n-\left(n-1\right)\log\nicefrac{{\underline{v}}}{{\overline{v}}}\right)}$
$\displaystyle-n\left(n-1\right)\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{v}{v-a}\right)\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{v}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)\cdot\frac{a}{v}+\lambda$

We dived by
$n\left(n-1\right)\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}$, and
write
$\lambda_{2}=\frac{\lambda}{n\left(n-1\right)\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}}$,
and we get

$\displaystyle\left(\frac{1}{v-a}\right)\frac{a\log\nicefrac{{v}}{{\underline{v}}}+\frac{\underline{v}}{n-1}-\frac{v}{n-1}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}-\left(\frac{1}{v-a}\right)\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{v}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)\cdot
a+\lambda_{2}$ $\displaystyle=$
$\displaystyle-\frac{1}{n-1}\cdot\frac{1}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}+\lambda_{2}.$

Therefore, when
$\lambda=\frac{n\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}$,
$Q(v)=\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{v}{v-a}\right)^{n-1}\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{v}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)$,
and $z=1-\frac{a}{v}$ we get

$\frac{dh_{v}(z)}{dz}=0.$

To prove that it is a local minimum, we look at the second derivative

$\displaystyle\frac{d^{2}h_{v}(z)}{dz^{2}}=n\left(n-1\right)\left(\left(\left(n-1\right)Q^{*}\left(v\right)-v\frac{dQ^{*}\left(v\right)}{dv}\right)z-\left(n-2\right)Q^{*}\left(v\right)\right)z^{n-3}.$

Since we only care about the sign, we only need to analyze

$\left(\left(n-1\right)Q^{*}\left(v\right)-v\frac{dQ^{*}\left(v\right)}{dv}\right)z-\left(n-2\right)Q^{*}\left(v\right).$
(18)

Substituting
$Q^{*}(v)=\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}\left(\frac{v}{v-a}\right)^{n-1}\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{v}}{{\underline{v}}}}{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}\right)$,
and $z=1-\nicefrac{{a}}{{v}}$, we get a positive value for every
$v>\underline{v}$ (See Appendix E.1 for details).

This proves that we found a local minimum. Since
$\frac{d^{2}h_{v}(z)}{dz^{2}}$ has only a single root in $(0,\infty)$, this is
the single local minimum in this interval. When $z=0$, we get that (18) is
negative, since $Q^{*}(v)>0$. That proves that the second derivative’s single
positive root is in $\left(0,1-\nicefrac{{a}}{{v}}\right)$. Therefore, $h_{v}$
is rising on $\left(1-\nicefrac{{a}}{{v}},1\right)$, which means that
$h_{v}\left(1-\nicefrac{{a}}{{v}}\right)<h_{v}(1)$.

We now only need to prove that $h_{v}\left(1-\nicefrac{{a}}{{v}}\right)\leq
h_{v}(0)$. To shorten the analysis ,we define

$\displaystyle\tilde{h}_{v}\left(z\right)=$
$\displaystyle\left(\frac{n-1-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}}{\left(1-\nicefrac{{a}}{{\overline{v}}}\right)^{n-1}}\right)\cdot
h_{v}\left(z\right)$ $\displaystyle=$
$\displaystyle\left(\frac{v}{v-a}\right)^{n-1}\left(n-1-\frac{1}{n-1}+\log\nicefrac{{v}}{{\underline{v}}}\right)\left(1-nz^{n-1}+\left(n-1\right)z^{n}\right)$
$\displaystyle-\left(\frac{v}{v-a}\right)^{n-1}\left(\frac{\left(n-1\right)a\log\nicefrac{{v}}{{\underline{v}}}+\underline{v}-v}{v-a}\right)\left(1-z^{n}\right)-n\left(1-z\right).$

It is enough to show that
$\tilde{h}_{v}(0)-\tilde{h}_{v}\left(1-\nicefrac{{a}}{{v}}\right)\geq 0$, and
indeed (see Appendix E.1)

$\displaystyle\tilde{h}_{v}(0)-\tilde{h}_{v}\left(1-\nicefrac{{a}}{{v}}\right)=\log\nicefrac{{v}}{{\underline{v}}}-\frac{1-\nicefrac{{\underline{v}}}{{v}}}{n-1}\geq
0.$

∎

The next claim handles the case when there is no solution $\underline{v}$ to
(13) in $[0,\overline{v}]$.

######  Claim 4.10.

If there is no solution for (13) in $[0,\overline{v}]$, then $(Q^{*},F^{*})$
solve Problem (P2), where

$\displaystyle F^{*}(v)$
$\displaystyle=\begin{cases}0&v\in\left[0,v_{0}\right),\\\
1-\frac{1}{(n-1)^{2}}&v\in[v_{0},\overline{v}),\\\
1&v\geq\overline{v},\end{cases}$ $\displaystyle Q^{*}(r)$
$\displaystyle=1\quad r\geq 0,$

where $v_{0}=\mu-\frac{\overline{v}-\mu}{\left(n-1\right)^{2}-1}$.
Furthermore, $F^{*}$ is nature’s unique best response to the seller’s $Q^{*}$.

###### Proof.

Since there is no solution for (13) in $[0,\overline{v}]$, we know that

$\left(n-\frac{1}{n-1}\right)\overline{v}>\left(n-1\right)^{2}\mu,$

since the term
$\left(n-\frac{1}{n-1}+\log\nicefrac{{\overline{v}}}{{\underline{v}}}\right)\underline{v}$
is increasing in $[0,\overline{v}]$.

When the seller uses no reserve price, then $F^{*}$ is nature’s best response
according to Proposition 1 in Suzdaltsev [2020a].

$F^{*}$ is unique since $z=0,1-\frac{1}{(n-1)^{2}}$ are the only minimum
points of the integrand $h_{v}(z)$ of Lagrangian, and therefore $F^{*}$ is the
only CDF in $\mathcal{F}$ that minimizes it point-wise. For clarity

$h_{v}(z)=1-nF^{n-1}\left(v\right)+\left(n-1\right)F^{n}\left(v\right)-\lambda(1-F(v)),$

where $\lambda$ is given by equations (13)-(16)

Now we need to show that if we fix $F^{*}$, then any reserve price higher than
zero is no better than no reserve price. To simplify our analyses, we consider
the case where the highest bidder does buy the item when the reserve price is
equal to her valuation.

Since the lowest valuation any bidder can have is $v_{0}$, then any reserve
price equal or lower than $v_{0}$ will have no effect, so we only need to
check reserve prices higher than $v_{0}$. Since the nature is binary, any
reserve price between $v_{0}$ and $\overline{v}$ will not change the
allocation of the item, so we can only benefit from increasing the reserve
price. We only need to show that a reserve price of $\overline{v}$ is no
better than no reserve price. The expected revenue for no reserve price is

$\displaystyle\operatorname*{Rev}_{F^{*}}(0,F^{*})$
$\displaystyle=v_{0}+\left(\overline{v}-v_{0}\right)\left(1-n\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n-1}+\left(n-1\right)\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n}\right)$
$\displaystyle=\overline{v}\left(1-\left(1-\nicefrac{{v_{0}}}{{\overline{v}}}\right)\left(1+\frac{1}{n-1}\right)\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n-1}\right).$

The expected revenue of reserve price $\overline{v}$ is

$\displaystyle\operatorname*{Rev}_{F^{*}}(\overline{v})=\overline{v}\left(1-\left(1-\frac{1}{\left(n-1\right)^{2}}\right)^{n}\right).$

Therefore

$\displaystyle\operatorname*{Rev}_{F^{*}}(0)\geq\operatorname*{Rev}_{F^{*}}(\overline{v})$
$\displaystyle\iff$
$\displaystyle\left(1-\nicefrac{{v_{0}}}{{\overline{v}}}\right)\left(1+\frac{1}{n-1}\right)\leq
1-\frac{1}{\left(n-1\right)^{2}}$ $\displaystyle\iff$
$\displaystyle\left(n-1\right)^{2}\mu\geq\overline{v}\left(n-\frac{1}{n-1}\right).$

This is true from the assumption that Eq (13) has no solutions in
$[0,\overline{v}]$. ∎

###### Proof of Theorem 4.1.

If there is a solution $\underline{v}$ to Eq (13) in $[0,\overline{v}]$, then
from Claim 4.6 we know that
$\operatorname*{Rev}_{F^{*}}(r_{1})=\operatorname*{Rev}_{F^{*}}(r_{2})$, for
any $r_{1},r_{2}$ in the support of $Q^{*}$, which includes $\underline{v}$.
Since $F^{*}$ has no mass on $(v_{0},\underline{v})$, then any
$r\in[v_{0},\underline{v})$ cannot yield higher revenue than a reserve price
of $\underline{v}$. Likewise, since there is no mass over $[0,v_{0})$, any
reserve price lower than $v_{0}$ would have the same revenue as a reserve
price of zero. Therefore, we can conclude that $Q^{*}$ maximizes the expected
revenue if nature uses $F^{*}$. From Claims 4.7-4.9, we get that distribution
$F^{*}$ is nature’s best response to the seller’s $Q^{*}$, which completes the
proof for the case that $\underline{v}\in[0,\overline{v}]$ is a solution to Eq
(13).

The case where there is no solution $\underline{v}$ to Eq (13) in
$[0,\overline{v}]$ is handled by Claim 4.10. This completes the proof. ∎

###  4.6 Not an Optimal Mechanism

Assuming an equilibrium exists, the second price auction with randomized
reserve price is not the optimal mechanism when $n\geq 3$, this is the case
because nature does not use an equal-revenue distribution. We now provide an
example.

######  Example 4.11.

For $n=3,\overline{v}=1,\mu=\nicefrac{{2}}{{3}}$, Theorem 4.1 says that when
restricted to second price auctions with randomized reserve, it is optimal for
the seller to always choose a reserve price of zero, and the adversary’s
optimal distribution is

$\displaystyle F^{*}(v)$
$\displaystyle=\begin{cases}0&v\in\left[0,\nicefrac{{5}}{{9}}\right),\\\
\nicefrac{{3}}{{4}}&v\in\left[\nicefrac{{5}}{{9}},\overline{v}\right),\\\
1&v\geq\overline{v}.\end{cases}$

The expected revenue in this case is $0.625$, see Fig 3.

However, the seller can do better. Using _ironing_ Myerson [1981] (see also
Hartline [2021]), we can find an optimal mechanism for the seller assuming the
nature uses $F^{*}$. This mechanism randomly picks a winner, uniformly among
all the highest bidders, and allocates the item to the winner. The payment for
the item is as follows

  * •

If all bidders reported a value of $\nicefrac{{5}}{{9}}$ then the payment is
$\nicefrac{{5}}{{9}}$.

  * •

If at least two bidders reported a value of $1$, then the payment is $1$.

  * •

If only one bidder reported a value of $1$, then the payment is
$\frac{23}{27}$.

Note: the mechanism handles false reports by ignoring bidders with bidding of
less than $\nicefrac{{5}}{{9}}$, and treat any bidding in
$\left[\nicefrac{{5}}{{9}},1\right)$ the same as $\nicefrac{{5}}{{9}}$.
Bidding a value higher than 1 is treated the same as as bidding a value of 1.

In this mechanism, being truthful is a dominant strategy. The only case where
it is different then second price, is when one bidder (assume bidder 1) has a
valuation of $1$, and the other two have valuations of $\nicefrac{{5}}{{9}}$.
The utility for bidder 1 of truthful bidding in this case is
$1-\frac{23}{27}=\frac{4}{27}$. By reporting less than 1, the bidder would win
with probability of $\nicefrac{{1}}{{3}}$, and would pay
$\nicefrac{{5}}{{9}}$. This results in an expected utility of
$\nicefrac{{1}}{{3}}\cdot\left(1-\nicefrac{{5}}{{9}}\right)=\frac{4}{27}$ as
well. Therefore, the bidders cannot gain anything by reporting falsely, and
the mechanism is truthful.

The expected revenue in this case is
$\frac{5}{9}\cdot\left(\frac{3}{4}\right)^{3}+\frac{23}{27}\cdot
3\cdot\frac{1}{4}\cdot\left(\frac{3}{4}\right)^{2}+1\cdot\left(\frac{1}{4^{3}}+3\cdot\frac{1}{4^{2}}\cdot\frac{3}{4}\right)=\frac{3}{4}$.
Which is higher than the revenue we get from the second price auction.

The mechanism presented in Example 4.11 is optimal for $F^{*}$, but not the
other way around, and it would be the case for any other mechanism that is
equal to it for $F^{*}$. That is easy to see since nature can choose the
trivial point mass distribution only on $\mu=\nicefrac{{2}}{{3}}$, which would
guarantee a revenue no higher than $\nicefrac{{2}}{{3}}$.

According to Claim 4.10, $F^{*}$ is nature’s unique best response to $Q^{*}$,
in the same setting of the example. That means that every other equilibrium of
Problem (P2) is of the form $(Q,F^{*})$ for some $Q\in\mathcal{Q}$, and it
achieve the same expected revenue. Therefore, the example here prove that no
second price auction with randomized reserve can be an equilibrium for the
general Problem (P1).

##  5 Discussion

In this work we identify the second price auction with random reserve as the
robustly revenue-optimal mechanism for two i.i.d. bidders, in settings where
only the mean and support of the value distribution are known. We develop an
expression for the robustly optimal distribution of the random reserve, and
generalize this finding to $n\geq 3$ bidders. This distribution constitutes
part of an equilibrium of a zero-sum game between the seller, who controls the
random reserve price, and an adversary who controls the value distribution.
Our main technique is to start from a discretization of the setting, uncover
recursive relations between the discretized probabilities, and use these
relations to derive a guess of the equilibrium distributions. We also give an
explanation of when to expect the equilibrium to induce indifference among one
or both of the zero-sum game players. These technical contributions can
possibly be of more general applicability in robustly optimal mechanism
design.

Our work raises several open questions for future research.

##### Beyond two bidders.

First, while for $n\geq 3$ bidders we establish the max-min optimal
distribution of the reserve price when the seller is confined to second price
auctions, the following is still open:

######  Open Question 1.

What is the max-min optimal auction given parametric distributional knowledge
for $n\geq 3$ bidders?

In Section 4 we show that the answer to Open Question 1 is generally _not_ a
second price auction with randomized reserve. This raises the next question:

######  Open Question 2.

Are there natural conditions under which the second price auction with random
reserve is max-min optimal for $n\geq 3$ bidders, such as _regularity_ of the
value distribution [Myerson, 1981]?

The regularity assumption may require new techniques for the analysis, but it
seems like an intuitively logical condition to try given that even for known
distributions, the optimality of the second price auction with (deterministic)
reserve holds only for a regular value distribution (in fact, Example 4.11
demonstrates its sub-optimality for irregular distributions). An interesting,
high-level research direction is to understand whether there is a formal
connection between the optimal and robustly optimal auctions. E.g., is it just
a “coincidence” that for two bidders, the optimal and robustly optimal auction
formats are quite similar (up to randomization of the reserve price)?

##### Beyond i.i.d. bidders.

Our focus in this work is on the case of i.i.d. bidders. Indeed, in revenue
maximization with known value distributions, the case of bidders with values
that are independent and even i.i.d. is very central: independence enables the
fundamental theory of Myerson, and precludes “unrealistic” results like the
Crémer-McLean auction Crémer and McLean [1988]. Furthermore, i.i.d. leads to
the celebrated result that the second price auction with deterministic reserve
is optimal. This makes the i.i.d. case interesting for robust revenue
maximization as well, but a natural next step is to go beyond this assumption.

######  Open Question 3.

What is the max-min optimal auction given parametric distributional knowledge
for independent bidders with value distributions that are not necessarily
identical?

As for the case of correlated bidders, this case has been studied in the
robust revenue maximization literature. In particular, Che [2022] studies a
similar setting to ours while dropping the i.i.d. assumption. His results are
as follows: If the seller chooses a second price auction with randomized
reserve, then nature will strongly correlate the bidders in the sense that
just one (randomly chosen) bidder will be a true contender for the item, and
all other bidders will have the same value $\alpha$. In effect, nature is
using the power to correlate in order to abuse the second price auction
format, by eliminating the revenue-inducing competition among the bidders and
leaving a single bidder “in the game”. When nature has this power (due to
dropping the i.i.d. restriction, or even just the independence restriction),
Che demonstrates that second price is not robustly optimal in general even for
two bidders. (He goes on to show that under additional uncertainty about the
bidders’ information, second price is robustly optimal among a subclass of
mechanisms he terms “competitive”.)

An interesting direction for future work is to limit the correlation that
nature can introduce among bidders, and study the optimal mechanism robust
against limited correlation (rather than against extreme coordination of the
bidders as above, which is arguably less realistic).

## References

  * [1]
  * Allouah et al. [2021a] Amine Allouah, Achraf Bahamou, and Omar Besbes. 2021a.  Optimal Pricing with a Single Point. In _Proceedings of the 22nd ACM Conference on Economics and Computation (EC)_. ACM, 50.
  * Allouah et al. [2021b] Amine Allouah, Achraf Bahamou, and Omar Besbes. 2021b.  Pricing with Samples. (2021).  Forthcoming in Operations Research.
  * Allouah et al. [2021c] Amine Allouah, Achraf Bahamou, and Omar Besbes. 2021c.  Revenue Maximization from Finite Samples. In _Proceedings of the 22nd ACM Conference on Economics and Computation (EC)_. ACM, 51.
  * Allouah and Besbes [2020] Amine Allouah and Omar Besbes. 2020.  Prior-Independent Optimal Auctions.  _Manag. Sci._ 66, 10 (2020), 4417–4432.
  * Anunrojwong et al. [2022] Jerry Anunrojwong, Santiago Balseiro, and Omar Besbes. 2022\.  On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design. (2022).  Forthcoming in EC’22.
  * Azar et al. [2013] Pablo Azar, Silvio Micali, Constantinos Daskalakis, and S. Matthew Weinberg. 2013.  Optimal and Efficient Parametric Auctions. In _Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. 596–604.
  * Azar and Micali [2013] Pablo Daniel Azar and Silvio Micali. 2013.  Parametric Digital Auctions. In _Proceedings of the 4th ACM Conference on Innovations in Theoretical Computer Science (ITCS)_. 231–232.
  * Babaioff et al. [2020] Moshe Babaioff, Michal Feldman, Yannai A. Gonczarowski, Brendan Lucier, and Inbal Talgam-Cohen. 2020\.  Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer. In _Proceedings of the 21st ACM Conference on Economics and Computation (EC)_. ACM, 191.
  * Babaioff et al. [2018] Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, and Shay Moran. 2018.  Are Two (Samples) Really Better Than One?. In _Proceedings of the 19th ACM Conference on Economics and Computation (EC)_. ACM, 175.
  * Babichenko et al. [2021] Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. 2021.  Regret-Minimizing Bayesian Persuasion. In _Proceedings of the 22nd ACM Conference on Economics and Computation (EC)_. ACM, 128.
  * Bei et al. [2019] Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang. 2019\.  Correlation-Robust Analysis of Single Item Auction. In _Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, 193–208.
  * Bergemann et al. [2021] Dirk Bergemann, Benjamin Brooks, and Stephen Morris. 2021\.  Maxmin Auction Design with Known Expected Values. (2021).  Working paper available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2886456.
  * Brooks and Du [2021] Benjamin Brooks and Songzi Du. 2021.  Maxmin Auction Design with Known Expected Values. (2021).  Working paper.
  * Bulow and Klemperer [1996] Jeremy Bulow and Paul Klemperer. 1996.  Auctions versus Negotiations.  _American Economic Review (AER)_ 86, 1 (1996), 180–94.
  * Carrasco et al. [2018] Vinicius Carrasco, Vitor Farinha Luz, Nenad Kos, Matthias Messner, Paulo Monteiro, and Humberto Moreira. 2018.  Optimal selling mechanisms under moment conditions.  _Journal of Economic Theory (JET)_ 177 (2018), 245–279.
  * Carrasco et al. [2019] Vinicius Carrasco, Vitor Farinha Luz, Paulo Monteiro, and Humberto Moreira. 2019.  Robust mechanisms: The curvature case.  _Econ. Theory_ 68, 1 (2019), 203–222.
  * Carroll [2015] Gabriel Carroll. 2015\.  Robustness and Linear Contracts.  _American Economic Review_ 105, 2 (2015), 536–563.
  * Carroll [2017] Gabriel Carroll. 2017\.  Robustness and Separation in Multidimensional Screening.  _Econometrica_ 85, 2 (2017), 453–488.
  * Carroll [2019] Gabriel Carroll. 2019\.  Robustness in Mechanism Design and Contracting.  _Annual Review of Economics_ 11 (2019), 139–166.
  * Che [2022] Ethan Che. 2022\.  Robustly Optimal Auction Design under Mean Constraints. (2022).  Available at https://arxiv.org/abs/1911.07103, forthcoming in EC’22.
  * Che and Zhong [2021] Yeon-Koo Che and Weijie Zhong. 2021.  Robustly-Optimal Mechanism for Selling Multiple Goods. In _Proceedings of the 22nd ACM Conference on Economics and Computation (EC)_. ACM, 314–315.
  * Chen et al. [2021] Zhi Chen, Zhenyu Hu, and Ruiqin Wang. 2021.  Screening with Limited Information: A Dual Perspective and A Geometric Approach. In _Proceedings of the 17th Conference on Web and Internet Economics (WINE)_. Springer.
  * Cole and Roughgarden [2014] Richard Cole and Tim Roughgarden. 2014.  The sample complexity of revenue maximization. In _Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC)_. ACM, 243–252.
  * Crémer and McLean [1988] Jacques Crémer and Richard P. McLean. 1988.  Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions.  _Econometrica_ 56, 6 (1988), 1247–1257.
  * Devanur et al. [2015] Nikhil R. Devanur, Jason D. Hartline, and Qiqi Yan. 2015\.  Envy freedom and prior-free mechanism design.  _J. Econ. Theory_ 156 (2015), 103–143.
  * Dhangwatnotai et al. [2015] Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. 2015\.  Revenue maximization with a single sample.  _Games and Economic Behavior (GEB)_ 91 (2015), 318–333.
  * Dütting et al. [2019] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. 2019\.  Simple versus Optimal Contracts. In _Proceedings of the 20th ACM Conference on Economics and Computation (EC)_. ACM, 369–387.
  * Fu et al. [2015] Hu Fu, Nicole Immorlica, Brendan Lucier, and Philipp Strack. 2015\.  Randomization Beats Second Price as a Prior-Independent Auction. In _Proceedings of the 16th ACM Conference on Economics and Computation (EC)_. ACM, 323.
  * Giannakopoulos et al. [2020] Yiannis Giannakopoulos, Diogo Poças, and Alexandros Tsigonias-Dimitriadis. 2020.  Robust Revenue Maximization Under Minimal Statistical Information. In _Proceedings of the 16th Conference on Web and Internet Economics (WINE)_. Springer, 177–190.
  * Gravin and Lu [2018] Nick Gravin and Pinyan Lu. 2018.  Separation in Correlation-Robust Monopolist Problem with Budget. In _Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, 2069–2080.
  * Hartline [2021] Jason D. Hartline. 2021\.  Mechanism Design and Approximation. (2021).  Textbook under preparation available at http://jasonhartline.com/MDnA/.
  * Hartline and Johnsen [2021] Jason D. Hartline and Aleck C. Johnsen. 2021.  Lower Bounds for Prior Independent Algorithms. (2021).  Working paper available at https://arxiv.org/abs/2107.04754.
  * Hartline et al. [2020] Jason D. Hartline, Aleck C. Johnsen, and Yingkai Li. 2020\.  Benchmark Design and Prior-independent Optimization. In _Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS)_. IEEE, 294–305.
  * He and Li [2022] Wei He and Jiangtao Li. 2022.  Correlation-robust auction design.  _Journal of Economic Theory_ 200 (2022).  Article 105403.
  * Koçyiğit et al. [2019] C. Koçyiğit, Garud Iyengar, Daniel Kuhn, and Wolfram Wiesemann. 2019.  Distributionally Robust Mechanism Design.  _Manag. Sci._ 66, 1 (2019), 159–189.
  * Myerson [1981] Roger B. Myerson. 1981\.  Optimal auction design.  _Mathematics of Operations Research (MOR)_ 6, 1 (1981), 58–73.
  * Roughgarden [2020] Tim Roughgarden (Ed.). 2020\.  _Beyond the Worst-Case Analysis of Algorithms_.  Cambridge University Press.
  * Savage [1951] Leonard Jimmie Savage. 1951\.  The theory of statistical decision.  _J. Amer. Statist. Assoc._ 46, 253 (1951), 55–67.
  * Segal [2003] Ilya Segal. 2003\.  Optimal pricing mechanisms with unknown demand.  _American Economic Review (AER)_ 93, 3 (2003), 509–529.
  * Suzdaltsev [2020a] Alex Suzdaltsev. 2020a.  Distributionally Robust Pricing in Independent Private Value Auctions. (2020).  Working paper available at https://arxiv.org/abs/2008.01618.
  * Suzdaltsev [2020b] Alex Suzdaltsev. 2020b.  An Optimal Distributionally Robust Auction. (2020).  Working paper available at https://arxiv.org/abs/2006.05192.
  * Talgam-Cohen [2020] Inbal Talgam-Cohen. 2020\.  Prior-Independent Auctions.  In _Beyond the Worst-Case Analysis of Algorithms_ , Tim Roughgarden (Ed.). Cambridge University Press, 586–605.
  * Wald [1950] Abraham Wald. 1950\.  _Statistical Decision Functions_.  John Wiley.
  * Wikipedia [2021] Wikipedia. 2021\.  Arzelà–Ascoli theorem — Wikipedia, The Free Encyclopedia.  https://en.wikipedia.org/w/index.php?title=Arzel%C3%A0%E2%80%93Ascoli_theorem&oldid=1049740502.  [Online; accessed 9-February-2022].
  * Wilson [1987] Robert B. Wilson. 1987\.  Game-theoretic approaches to trading processes.  In _Advances in Economic Theory: Fifth World Congress_ , Truman F. Bewley (Ed.). Cambridge University Press, 33–77.

##  Appendix A Equilibrium in the Two Bidder Discrete Case

In this section we focus exclusively on the reduced zero-sum game, solving
Problem (P2) in a discretized model. In Section 3.2 we present two Claims
(3.4, 3.5) about a potential solution in this setting. We will prove its
existence and correctness here.

The discretized model. Let $k>1$ be the discretization parameter. We
effectively limit the support of both the seller’s distribution over reserve
prices and the adversary’s distribution over values to $k+1$ possible options
$\mathbf{r}_{k}=(r_{k,1},\dots,r_{k,k},r_{k,k+1})$, where
$r_{k,i}=\frac{i-1}{k}\cdot\overline{v}$ for every $1\leq i\leq k+1$. We
denote by $\mathcal{F}_{k}$ the set of all distribution functions over
$\mathbf{r}_{k}$ with a mean value of $\mu$, and by $\mathcal{Q}_{k}$ the set
of all distribution functions over $\mathbf{r}_{k}$. To be precise, the
functions in $\mathcal{F}_{k}$ and $\mathcal{Q}_{k}$ are step functions that
only have jumps in points of $\mathbf{r}_{k}$.

Our main result for the discretized model. The following theorem guarantees
the existence of a solution to Problem (P2) in the discrete case, and provides
properties that the solution satisfies. Together with the mean value
constraint, these properties uniquely describe the solution, and will allow us
to solve the general case in subsequent sections.

######  Theorem A.1.

For every $k>1$, there exists an equilibrium
$\left(Q^{*}_{k},F^{*}_{k}\right)\in\mathcal{Q}_{k}\times\mathcal{F}_{k}$ of
the reduced zero-sum game in the discretized model, where the seller and the
adversary are limited to $\mathbf{r}_{k}$. The equilibrium satisfies the
following:

  * •

$F^{*}_{k}(r_{k,i+1})=\sqrt{\frac{\overline{v}}{k}\cdot\frac{2}{r_{k,i}+\nicefrac{{\overline{v}}}{{k}}}(F^{*}_{k}(r_{k,i})-F^{*}_{k}(r_{k,i})^{2})+F^{*}_{k}(r_{k,i})^{2}}$
for every $1\leq i\leq k-1$;

  * •

$Q^{*}_{k}(r_{k,i-1})=Q^{*}_{k}(r_{k,i})-\frac{Q^{*}_{k}(0)(1-F^{*}_{k}(0))-Q^{*}_{k}(r_{k,i})(1-F^{*}_{k}(r_{k,i}))}{r_{k,i}F^{*}_{k}(r_{k,i})}\cdot\nicefrac{{\overline{v}}}{{k}}$
for every $2\leq i\leq k$;

  * •

$Q^{*}_{k}(r_{k,k})=1$.

###  A.1 Existence

We will prove that there exist non decreasing vectors
$\mathbf{q}^{*},\mathbf{x}^{*}\in[0,1]^{k}$ solving Claims 3.4-3.5.

######  Claim A.2.

There exists a unique vector $\mathbf{x}^{*}=(x_{1}^{*},\dots,x_{k}^{*})$ that
satisfies the following:

  * •

$\frac{\partial}{\partial q_{i}}\mathcal{L}(\mathbf{x}^{*},\mathbf{q})=0$ for
every $1\leq i\leq k-1$ and every $\mathbf{q}\in\mathbb{R}^{k-1}$.

  * •

$\nicefrac{{\overline{v}}}{{k}}\cdot\sum_{i=1}^{k}(1-x^{*}_{i})=\mu$.

  * •

$0<x_{1}^{*}<x_{2}^{*}\dots<x_{k}^{*}<1$.

###### Proof.

We define a new function $\chi_{i}:[0,1]\to[0,1]$ by

$\displaystyle\chi_{1}(x)$ $\displaystyle=x;$ $\displaystyle\chi_{i+1}(x)$
$\displaystyle=\sqrt{\frac{\overline{v}}{k}\cdot\frac{2}{r_{k,i}+\nicefrac{{\overline{v}}}{{k}}}(\chi_{i}(x)-\chi_{i}^{2}(x))+\chi_{i}^{2}(x)}\quad
1\leq i\leq k-1.$

It is not hard to see that for every $1\leq i\leq k-1$ and $x\in[0,1]$

$x\leq\sqrt{\frac{\overline{v}}{k}\cdot\frac{2}{r_{k,i}+\nicefrac{{\overline{v}}}{{k}}}(x-x^{2})+x^{2}}\leq
1,$

and if $x_{i}\in(0,1)$ then the inequalities are strict. From that we can see
that $0\leq\chi_{1}(x)\leq\dots\leq\chi_{k}(x)\leq 1$ for every $x\in[0,1]$,
and equality can only happen at $x=0,1$. It is also not hard to see that
$\chi_{i}(x)$ is continuous and increasing for every $1\leq i\leq k$.

We now define

$\bar{x}_{k}(x)=1-\frac{k\cdot\mu}{\overline{v}}+\sum_{i=1}^{k-1}(1-\chi_{i}(x)).$

Since $\chi_{1}(x),\dots,\chi_{k-1}(x)$ are all continuous and increasing,
then $\bar{x}_{k}(x)$ is continuous and decreasing. We can also get the values
of $\chi_{k}(x)$ and $\bar{x}_{k}(x)$ at $x=0,1$ with ease:

$\displaystyle\chi_{k}(0)$ $\displaystyle=0,$ $\displaystyle\chi_{k}(1)$
$\displaystyle=1;$ $\displaystyle\bar{x}_{k}(0)$
$\displaystyle=k\left(1-\nicefrac{{\mu}}{{\overline{v}}}\right)>0,$
$\displaystyle\bar{x}_{k}(1)$
$\displaystyle=1-k\cdot\nicefrac{{\mu}}{{\overline{v}}}<1.$

We now get that there is a unique value $x^{*}\in(0,1)$ such that
$\chi_{k}(x^{*})=\bar{x}_{k}(x^{*})$. We denote $x_{i}^{*}=\chi_{i}(x^{*})$
for every $1\leq i\leq k$, and $\mathbf{x}^{*}=(x_{1}^{*},\dots,x_{k}^{*})$.
From Claim 3.4 we get that for every $1\leq i\leq k-1$

$\frac{\partial}{\partial q_{i}}\mathcal{L}(\mathbf{x}^{*},\mathbf{q})=0.$

Since $x^{*}_{k}=\bar{x}_{k}(x^{*}_{1})$, we also know that
$\nicefrac{{\overline{v}}}{{k}}\cdot\sum_{i=1}^{k}(1-x^{*}_{i})=\mu$, which
concludes the proof. ∎

######  Claim A.3.

There exists a unique vector $\mathbf{q}^{*}=(q_{1}^{*},\dots,q_{k}^{*})$ that
satisfies the following:

  * •

$\frac{\partial}{\partial x_{i}}\mathcal{L}(\mathbf{x}^{*},\mathbf{q}^{*})=0$
for every $1\leq i\leq k-1$;

  * •

$0<q_{1}^{*}\dots<q_{k-1}^{*}<1$.

###### Proof.

Using Claim 3.5, and the knowledge that $q_{k}=1$ would be optimal, we can
calculate the rest of $q^{*}$ as a function of $\lambda$, where

$\displaystyle q^{*}_{i-1}(\lambda)$
$\displaystyle=q_{i}(\lambda)-\frac{\nicefrac{{\lambda}}{{2}}-q^{*}_{i}(\lambda)\left(1-x^{*}_{i}\right)}{r_{k,i}x^{*}_{i}}\cdot\nicefrac{{\overline{v}}}{{k}},$
$\displaystyle q^{*}_{k}(\lambda)$ $\displaystyle=1.$

It is clear that $q^{*}_{i}(\lambda)$ is decreasing for every $1\leq i\leq k$.
It is also easy to see that for every $2\leq i\leq k$

$q^{*}_{i-1}(\lambda)<q^{*}_{i}(\lambda)\iff
q^{*}_{i}(\lambda)<\frac{\nicefrac{{\lambda}}{{2}}}{1-x^{*}_{i}}.$

We can see that for $\lambda=2$

$\displaystyle
q^{*}_{k-1}(2)=1-\frac{x^{*}_{k}}{r_{k,k}x^{*}_{k}}\cdot\nicefrac{{\overline{v}}}{{k}}=1-\frac{\nicefrac{{\overline{v}}}{{k}}}{1-\nicefrac{{\overline{v}}}{{k}}}<1<\frac{\nicefrac{{\lambda}}{{2}}}{1-x^{*}_{k-1}}.$

With recursion we can easily see that $q_{1}^{*}(2)<1$ as well. For
$\lambda=0$ we see that

$\displaystyle
q^{*}_{k-1}(0)=1+\frac{1-x^{*}_{i}}{r_{k,i}x^{*}_{i}}\cdot\nicefrac{{\overline{v}}}{{k}}>1>\frac{\nicefrac{{\lambda}}{{2}}}{1-x^{*}_{k-1}},$

and similarly we get that $q_{1}^{*}(0)>1$.

From Claim 3.5, we also know that

$q_{1}^{*}=\frac{\nicefrac{{\lambda}}{{2}}}{1-x^{*}_{1}}.$

Since this expression is increasing in $\lambda$, and lower than 1 for
$\lambda=0$, and higher than 1 for $\lambda=2$, we get that there is a unique
solution $\lambda\in(0,2)$ such that

$q_{1}^{*}(\lambda)=\frac{\nicefrac{{\lambda}}{{2}}}{1-x^{*}_{1}}$

.

In order to prove that $q_{1}^{*}\dots<q_{k-1}^{*}$, we assume that there
exists $i$ such that $q_{i-1}^{*}>q_{i}^{*}$. Since $x_{i}^{*}>x_{i-1}^{*}$ we
get

$q_{i-1}^{*}>q_{i}^{*}>\frac{\nicefrac{{\lambda}}{{2}}}{1-x_{i}^{*}}>\frac{\nicefrac{{\lambda}}{{2}}}{1-x_{i-1}^{*}}\implies
q_{i-2}^{*}>q_{i-1}^{*}\implies
q_{1}^{*}>\dots>\frac{\nicefrac{{\lambda}}{{2}}}{1-x_{i}^{*}}>\frac{\nicefrac{{\lambda}}{{2}}}{1-x_{1}^{*}},$

which is a contradiction, since
$\frac{\nicefrac{{\lambda}}{{2}}}{1-x_{1}^{*}}=q_{1}^{*}$. ∎

###  A.2 Proof that the Saddle Point is an Equilibrium

Claims A.2 and A.3 only prove that the gradient is zero at
$(\mathbf{x}^{*},q^{*})$, but they do not guarantee that it is an equilibrium.
The next claim will prove that $\mathbf{x}^{*}$ is the adversary’s best
response to $\mathbf{q}^{*}$.

######  Claim A.4.

$\mathbf{x}=\mathbf{x}^{*}$ from Claim A.2 minimizes the Lagrangian
$\mathcal{L}(\mathbf{x},\mathbf{q}^{*})$, where $\mathbf{q}^{*}$ is given by
Claim A.3.

###### Proof.

In order to show that $\mathbf{x}^{*}$ is a minimum, we look on the second
derivative, and prove that it is always positive at $q^{*}$, which implies
that $x^{*}$ is the minimum.

$\displaystyle\frac{\partial^{2}}{\partial
x_{i}^{2}}\mathcal{L}_{k}(\mathbf{q}^{*},\mathbf{x})=-2(q^{*}_{i}-q^{*}_{i-1})r_{k,i}+2q^{*}_{i}\cdot\nicefrac{{\overline{v}}}{{k}}$

It is enough to show that

$\displaystyle(q^{*}_{i}-q^{*}_{i-1})r_{k,i}\leq
q^{*}_{i}\cdot\nicefrac{{\overline{v}}}{{k}}.$

For $i=1$ this is true since $r_{k,1}=0$ (and $q^{*}_{0}=0$). For $2\leq i\leq
k$ this is equivalent to

$\displaystyle\frac{q^{*}_{i}-q^{*}_{i-1}}{\nicefrac{{\overline{v}}}{{k}}}\cdot
r_{k,i}\leq q^{*}_{i}.$

From Claim 3.5 we get

$\displaystyle\frac{q^{*}_{i}-q^{*}_{i-1}}{\nicefrac{{\overline{v}}}{{k}}}\cdot
r_{k,i}$
$\displaystyle=\frac{\nicefrac{{\lambda}}{{2}}-q^{*}_{i}(1-x_{i})}{x_{i}}$
$\displaystyle=q^{*}_{i}-\frac{\nicefrac{{q^{*}_{i}-\lambda}}{{2}}}{x_{i}}$
$\displaystyle=q^{*}_{i}-\frac{q^{*}_{i}-q^{*}_{1}(1-x^{*}_{1})}{x_{i}}$
$\displaystyle\leq q^{*}_{i}.$

This completes the proof. ∎

Now we are ready to complete the proof of Theorem A.1.

###### Proof of Theorem A.1.

From Claims 3.4, 3.5, A.2, A.3 we get the unique vectors $\mathbf{x}^{*}$ and
$\mathbf{q}^{*}$ such that their corresponding distributions
$F^{*}_{k}\in\mathcal{F}_{k}$ and $Q^{*}_{k}\in\mathcal{Q}_{k}$, respectively,
satisfy the same formulas as in the theorem statement.

From Claim A.4 we get that $F^{*}_{k}$ is the adversary’s best response to
$Q^{*}_{k}$. The only thing left is to prove that $Q^{*}$ is the seller’s best
response to $F^{*}_{k}$.

From Claim A.2 we get that the derivative of the expected revenue in regard to
any of the seller’s variables is always zero at $F^{*}_{k}$, which means that
the revenue is constant, as long as there is no mass on $\overline{v}$. Since
any mass on $\overline{v}$ will only lower the expected revenue, we get that
$Q^{*}_{k}$ is a best response to $F^{*}_{k}$. ∎

##  Appendix B A Discrete-to-General Formalism

In the proofs of Theorems 3.1,4.1 we have first presented recursive relations
for a saddle point in the discrete case (For example Claim 3.4). To get ODEs
that the non-discrete distributions satisfy, we have defined a function that
represent the recursive relations, and derived it at zero, to get the ODEs.
Since we used it to guess an equilibrium, we did not need to provide a formal
proof, but this technique is proven formally here (Lemmas B.2, B.3). There
Lemmas are able to provide close form expression when going from a discrete
solution to a general one, without needing a close form solution to the
discrete case, which we believe may be of independent interest.

In Section B.1 we define formally what we mean by a sequence of recursive
solutions to the discretized settings indexed by $k$. Section B.2 establishes
conditions under which such a sequence is guaranteed to have a converging
subsequence with a continuous limit. Section B.3 provides a further guarantee
on the limit (under slightly stronger conditions), namely that it must satisfy
a certain ordinary differential equation _(ODE)_ appearing in Lemmas B.3-B.4.

###  B.1 Definitions

######  Definition B.1 (Recursive discrete+).

Let $\mathcal{I}\subseteq[0,\overline{v}]$ be an interval and let
$\mathcal{C},\mathcal{Z}$ be compact intervals. Consider a sequence
$\\{f_{k}\\}_{k\in\mathbb{N}}$ of functions from a domain
$\mathcal{X}\subseteq[0,\overline{v}]$ to a range $\mathcal{Y}$, where $f_{k}$
is a step function with jumps at $\mathbf{r}_{k}\cap\mathcal{X}$ for every
$k$. Let $I^{+}_{k}=\left\\{i\mid 1\leq i\leq k\text{ and
}r_{k,i},r_{k,i+1}\in\mathcal{X}\right\\}$ be the set of all indices such that
$f_{k}(\cdot)$ is defined on both $r_{k,i}$ and $r_{k,i+1}$. The sequence of
functions $\\{f_{k}\\}$ is called “recursive discrete+” if for every $k$ and
$i\in I_{k}^{+}$ we can express $f_{k}\left(r_{k,i+1}\right)$ as follows:

$f_{k}\left(r_{k,i+1}\right)=\psi\left(\frac{\overline{v}}{k},r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right),$
(19)

where $\\{a_{k}\\}\subset\mathcal{C}$ is some sequence, $\\{g_{k}\\}$ is a
sequence of functions from $\mathcal{X}$ to $\mathcal{Z}$ that uniformly
converge to a continuous function, and
$\psi(\delta,x,y,z,a):\mathcal{I}\times\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}\times\mathcal{C}\to\mathcal{Y}$
is a continuous function such that for every $x,y,z,a$,

$\psi(0,x,y,z,a)=y.$ (20)

Similarly to the definition of “recursive discrete+” we say that a sequence
$\\{f_{k}\\}_{k\in\mathbb{N}}$ is “recursive discrete-”, if it satisfies the
same conditions, but instead of condition (19) it satisfies

$f_{k}\left(r_{k,i-1}\right)=\psi\left(\frac{\overline{v}}{k},r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right).$
(21)

for every $k$ and $i\in I_{k}^{-}$, where $I^{-}_{k}=\left\\{i\mid 1\leq i\leq
k\text{ and }r_{k,i},r_{k,i-1}\in\mathcal{X}\right\\}$ the set of all indices
where $f_{k}$ is defined on both $r_{k,i}$ and $r_{k,i-1}$. If a sequence
$\\{f_{k}\\}_{k\in\mathbb{N}}$ is either recursive discrete+ or recursive
discrete- we simply say it is ”recursive discrete”.

The last two arguments of $\psi$ are optional, and $\psi$ can use only the
first three arguments; This is the case for $\\{F^{*}_{k}\\}$, where the value
of $F^{*}_{k}(r_{k,i+1})$ is only dependent on
$\delta=\frac{\overline{v}}{k},x=r_{k,i},y=F^{*}_{k}(r_{k,i})$. Those
arguments are used for $\\{Q^{*}_{k}\\}$, where the value at $r_{k,i-1}$ is
dependent on $\frac{\overline{v}}{k},r_{k,i},Q^{*}_{k}(r_{k,i})$ and on
$F^{*}_{k}(r_{k,i})$ and $Q^{*}_{k}(0)(1-F^{*}_{k}(0))$ as well.

###  B.2 Existence of a Uniformly-Convergent Subsequence with a Continuous
Limit

In this section we prove that a recursive discrete sequence, as defined above,
is guaranteed to contain uniformly converges subsequences, that converge into
a continuous function, when the corresponding function $\psi$ is Lipschitz.

######  Lemma B.2.

Let $\mathcal{I},\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{C}$ be intervals
where $0\in\mathcal{I}$, $\mathcal{I},\mathcal{X}\subseteq[0,\overline{v}]$,
and $\mathcal{Y},\mathcal{Z},\mathcal{C}$ are compact. Let
$\left\\{f_{k}\right\\}$ be a recursive discrete sequence for a suitable
function $\psi:\mathcal{I}\times\dots\times\mathcal{C}\to\mathcal{Y}$, and
corresponding sequences $\\{g_{k}\\}$ and $\\{a_{k}\\}$, where $\\{g_{k}\\}$
converges uniformly to a continuous function $g:\mathcal{X}\to\mathcal{Z}$.
Denote by $S$ the space of functions from $\mathcal{X}$ to $\mathcal{Y}$
endowed by the uniform metric
$d_{S}(h_{1},h_{2})=\sup_{x\in\mathcal{X}}\left\lvert
h_{1}(x)-h_{2}(x)\right\rvert$. If $\psi\left(\delta,x,y,z,a\right)$ is
Lipschitz in $\delta$, then the sequence $\left\\{f_{k}\right\\}$ is
relatively compact in $S$, and any limit is continuous.

###### Proof.

We assume that $\\{f_{k}\\}$ is recursive discrete+, and the proof for
recursive discrete- is similar. We define $I_{k}\coloneqq I_{k}^{+}$ where
$I_{k}^{+}$ is defined the same way as in Definition B.1. $\psi$ is
$c$-Lipschitz in $\delta$, which means that for every $k>1$ such that
$\frac{\overline{v}}{k}\in\mathcal{I}$ every and $i\in I_{k}$

$\displaystyle\left\lvert
f_{k}\left(r_{k,i+1}\right)-f_{k}\left(r_{k,i}\right)\right\rvert$
$\displaystyle=$
$\displaystyle\left\lvert\psi\left(\frac{\overline{v}}{k},r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right)-\psi\left(0,r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right)\right\rvert$
$\displaystyle\leq$ $\displaystyle\frac{\overline{v}}{k}\cdot c.$

This is an upper bound for the height of the jumps in $f_{k}$. Since in every
interval $[x_{1},x_{2}]$ there is no more than
$\left\lceil\frac{k}{\overline{v}}\cdot\left\lvert
x_{1}-x_{2}\right\rvert\right\rceil\leq\frac{k}{\overline{v}}\cdot\left\lvert
x_{1}-x_{2}\right\rvert+1$ jumps, we get that for every
$x_{1},x_{2}\in[0,\overline{v}]$

$\left\lvert f_{k}\left(x_{1}\right)-f_{k}\left(x_{2}\right)\right\rvert\leq
c\left\lvert x_{1}-x_{2}\right\rvert+\frac{\overline{v}}{k}\cdot c.$

If $\mathcal{X}$ is closed, and therefore compact, we use a generalization for
non-continuous functions of the Arzelà–Ascoli theorem [see, e.g., Wikipedia,
2021]. We conclude that $\\{f_{k}\\}$ is relatively compact in $S$, and any
limit is continuous.

If $\mathcal{X}$ is not compact, extend the definition of $f_{k}$ for each $k$
to $\overline{\mathcal{X}}$, the closure of $\mathcal{X}$. It is compact since
$\overline{\mathcal{X}}\subseteq[0,\overline{v}]$. We define
$\overline{f}_{k}$ to be identical to $f_{k}$ on $\mathcal{X}$. If a point
$x^{\prime}\in\overline{\mathcal{X}}\setminus\mathcal{X}$, we simply define
$\overline{f}_{k}(x^{\prime})=\lim_{x\to x^{\prime}}f_{k}(x)$, which exists
since $f_{k}$ is a step function and hence has no more than $k+1$ points of
discontinuity. The inequality

$\left\lvert\overline{f}_{k}\left(x_{1}\right)-\overline{f}_{k}\left(x_{2}\right)\right\rvert\leq
c\left\lvert x_{1}-x_{2}\right\rvert+\frac{\overline{v}}{k}\cdot c$

is still true for every $x_{1},x_{2}\in[0,\overline{v}]$, which allows us to
use the same generalization for non-continuous functions for Arzelà–Ascoli
theorem. Since the sequence $\\{\overline{f}_{k}\\}$ is relatively compact in
$S$, so is the sequence $\\{f_{k}\\}$. ∎

###  B.3 The Limit Must Satisfy an ODE

In the previous section, Lemma B.2 gives the existence of a uniformly
convergent subsequence with a continuous limit. Under slightly stronger
assumptions, we now prove a property that any limit must satisfy. One way to
use the resulting stronger lemma (Lemma B.3) is to combine the property it
establishes with other known properties that any limit must satisfy, such that
together this combination of properties is only satisfied by one function;
this will prove convergence of the sequence. We also show an almost equivalent
version (Lemma B.4) with less limitations.

######  Lemma B.3.

Let $\mathcal{I},\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{C}$ be compact
intervals where $0\in\mathcal{I}$, and
$\mathcal{I},\mathcal{X}\subseteq[0,\overline{v}]$. Let
$\left\\{f_{k}\right\\}$ be a recursive discrete sequence for a suitable
function $\psi:\mathcal{I}\times\dots\times\mathcal{C}\to\mathcal{Y}$, and
corresponding sequences $\\{g_{k}\\}$ and $\\{a_{k}\\}$ where $\\{g_{k}\\}$
converges uniformly to a continuous function $g:\mathcal{X}\to\mathcal{Z}$.
Denote by $S$ the space of functions from $\mathcal{X}$ to $\mathcal{Y}$
endowed by the uniform metric
$d_{S}(h_{1},h_{2})=\sup_{x\in\mathcal{X}}\left\lvert
h_{1}(x)-h_{2}(x)\right\rvert$.

If $\psi\left(\delta,x,y,z,a\right)$ is differentiable in $\delta$ and
$\frac{\partial}{\partial\delta}\psi\left(\delta,x,y,z,a\right)$ is
continuous, then the sequence $\left\\{f_{k}\right\\}$ is relatively compact
in $S$, and every limit $f$ is differentiable and satisfies

$f^{\prime}(r)=\begin{cases}\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(0,r,f(r),g(r),a\right)&\\{f_{k}\\}\text{
is recursive discrete+}\\\
-\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(0,r,f(r),g(r),a\right)&\\{f_{k}\\}\text{
is recursive discrete-}\end{cases},$

where $a$ is some limit of the subsequence $\\{a_{k_{j}}\\}$ and $f_{k_{j}}$
is the subsequence the converges into $f$.

###### Proof.

We prove this for the case of recursive discrete+. The case of recursive
discrete- is very similar. Since the derivative of $\psi$ in $\delta$ is
continuous on a compact space, $\psi$ is Lipschitz in $\delta$, and from Lemma
B.2 we get that $\\{f_{k}\\}$ is relatively compact in $S$, and any limit is
continuous. For every $k$ we define the function
$\tilde{f}:\mathcal{X}\to\mathcal{Y}$ to be equal to $f_{k}$ on
$\mathbf{r}_{k}$, but $\tilde{f}_{k}$ is continuous, and linear on
$[r_{k,i},r_{k,i+1}]$ for every $i\in I_{k}$. It is easy to see that for every
subsequence $\left\\{f_{k_{j}}\right\\}$ that converges uniformly to a
continuous function $f$, the subsequence $\left\\{\tilde{f}_{k_{j}}\right\\}$
also converges uniformly to $f$. For every $k$ such that
$\frac{\overline{v}}{k}\in\mathcal{I}$, and every $i\in I_{k}$, and every
$r\in[r_{k,i},r_{k,i+1})$

$\displaystyle\tilde{f}_{k}^{\prime}(r)$
$\displaystyle=\frac{f_{k}\left(r_{k,i+1}\right)-f_{k}\left(r_{k,i}\right)}{\frac{\overline{v}}{k}}$
$\displaystyle=\frac{\psi\left(\frac{\overline{v}}{k},r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right)-\psi\left(0,r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right)}{\frac{\overline{v}}{k}}$
$\displaystyle=\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(\delta^{\prime},r_{k,i},f_{k}\left(r_{k,i}\right),g_{k}\left(r_{k,i}\right),a_{k}\right),$

where $\delta^{\prime}\in\left[0,\frac{\overline{v}}{k}\right]$ and
$\tilde{f}_{k}^{\prime}(r)$ is defined to be the right derivative if
$r=r_{k,i,k}$. The derivative
$\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}$ is continuous
on a compact space, and thus uniformly continuous. Let $\\{k_{j}\\}$ be a
sequence such that $\\{f_{k_{j}}\\}$ converges uniformly to a continuous
function $f$ and $\\{a_{k_{j}}\\}$ converges to some $a\in\mathcal{C}$. We get
that for every $\varepsilon>0$, for any large enough $j$, and
$r\in\mathcal{X}$.

$\left\lvert\tilde{f}_{k_{j}}^{\prime}(r)-\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(0,r,f\left(r\right),g\left(r\right),a\right)\right\rvert<\varepsilon.$

Therefore, the sequence $\left\\{\tilde{f}_{k_{j}}^{\prime}\right\\}$ is
uniformly convergent, and it converges to $f^{\prime}$.999This is known when
the functions of the sequence are differentiable on the entire domain. While
this is not the case here, the functions are continuous and piecewise linear,
which suffices. This is true since for every continuous and piecewise linear
function $g$, the equality $g(x)=g(x_{0})+\int_{x_{0}}^{x}g^{\prime}(t)dt$
holds, and since
$\lim_{k\to\infty}\int_{\mathcal{X}^{\prime}}\tilde{f}_{k}^{\prime}(t)dt=\int_{\mathcal{X}^{\prime}}\lim_{k\to\infty}\tilde{f}_{k}^{\prime}(t)dt$
for every interval $\mathcal{X}^{\prime}\subseteq\mathcal{X}$, we conclude
that $\lim_{k\to\infty}\tilde{f}_{k}^{\prime}(x)=f^{\prime}(x)$. We conclude
that for every $r\in\mathcal{X}$

$f^{\prime}(r)=\lim_{j\to\infty}\tilde{f}_{k_{j}}^{\prime}(r)=\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(0,r,f\left(r\right),g\left(r\right),a\right).$

∎

Lemma B.2 requires $\psi$ to be Lipschitz over all the domain, and Lemma B.3
only works when we limit the domain of the sequence $\\{f_{k}\\}$ to a compact
interval. By representing a general interval as a countable infinite union of
compact intervals, and applying the lemmas to each of those intervals, we can
get a similar result with less limitations, as follows:

######  Lemma B.4.

Let $\mathcal{I},\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{C}$ be any
intervals where $0\in\mathcal{I}$,
$\mathcal{I},\mathcal{X}\subseteq[0,\overline{v}]$, and $\mathcal{C}$ is
compact. Let $\left\\{f_{k}\right\\}$ be a recursive discrete sequence for a
suitable function
$\psi:\mathcal{I}\times\dots\times\mathcal{C}\to\mathcal{Y}$, and
corresponding sequences $\\{g_{k}\\}$ and $\\{a_{k}\\}$ where $\\{g_{k}\\}$
converges uniformly to a continuous function $g:\mathcal{X}\to\mathcal{Z}$.

If for every compact interval $\tilde{\mathcal{X}}\subseteq\mathcal{X}$, there
are compact intervals $\tilde{\mathcal{Y}}\subseteq\mathcal{Y}$ and
$\tilde{\mathcal{Z}}\subseteq\mathcal{Z}$ such that for every large enough $k$
$f_{k}\left(\tilde{\mathcal{X}}\right)\subseteq\tilde{\mathcal{Y}}$ and
$g_{k}\left(\tilde{\mathcal{X}}\right)\subseteq\tilde{\mathcal{Z}}$, then the
following is true:

  1. 1.

If $\psi\left(\delta,x,y,z,a\right)$ is locally Lipschitz in $\delta$, then
any subsequence of $\left\\{f_{k}\right\\}$ has a locally uniform convergent
subsequence, and any limit is continuous.

  2. 2.

If $\psi\left(\delta,x,y,z,a\right)$ is differentiable in $\delta$ and
$\frac{\partial}{\partial\delta}\psi\left(\delta,x,y,z,a\right)$ is
continuous, then then any subsequence of $\left\\{f_{k}\right\\}$ has a a
locally uniform convergent subsequence, and every limit $f$ is differentiable
and satisfies

$f^{\prime}(r)=\begin{cases}\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(0,r,f(r),g(r),a\right)&\\{f_{k}\\}\text{
is recursive discrete+}\\\
-\frac{\partial\psi\left(\delta,x,y,z,a\right)}{\partial\delta}\left(0,r,f(r),g(r),a\right)&\\{f_{k}\\}\text{
is recursive discrete-}\end{cases},$

where $a$ is some limit of the subsequence $\\{a_{k_{j}}\\}$ and $f_{k_{j}}$
is the subsequence the converges into $f$.

###### Proof.

Any interval can be represented as an increasing union of compact intervals,
so there exist $J_{1}\subseteq J_{2}\subseteq\dots$ such that they are all
compact and $\bigcup_{i=1}^{\infty}\mathcal{X}$. By applying Lemma B.2 to all
of those, with suitable $\tilde{\mathcal{Y}},\tilde{\mathcal{Z}}$ intervals,