# Maximizing revenue in the presence of intermediaries

Gagan Aggarwal  Kshipra Bhawalkar  Guru Guruganesh  Andres Perlroth

###### Abstract

We study the mechanism design problem of selling $k$ items to unit-demand
buyers with private valuations for the items. A buyer either participates
directly in the auction or is represented by an intermediary, who represents a
subset of buyers. Our goal is to design robust mechanisms that are independent
of the demand structure (i.e. how the buyers are partitioned across
intermediaries), and perform well under a wide variety of possible contracts
between intermediaries and buyers.

We first consider the case of $k$ identical items where each buyer draws its
private valuation for an item i.i.d. from a known $\lambda$-regular
distribution. We construct a robust mechanism that, independent of the demand
structure and under certain conditions on the contracts between intermediaries
and buyers, obtains a constant factor of the revenue that the mechanism
designer could obtain had she known the buyers’ valuations. In other words,
our mechanism’s expected revenue achieves a constant factor of the optimal
welfare, regardless of the demand structure. Our mechanism is a simple posted-
price mechanism that sets a take-it-or-leave-it per-item price that depends on
$k$ and the total number of buyers, but does not depend on the demand
structure or the downstream contracts.

Next we generalize our result to the case when the items are not identical. We
assume that the item valuations are separable, i.e. $v_{ij}=\eta_{j}v_{i}$ for
buyer $i$ and item $j$, with each private $v_{i}$ drawn i.i.d. from a known
$\lambda$-regular distribution. For this case, we design a mechanism that
obtains at least a constant fraction of the optimal welfare, by using a menu
of posted prices. This mechanism is also independent of the demand structure,
but makes a relatively stronger assumption on the contracts between
intermediaries and buyers, namely that each intermediary prefers outcomes with
a higher sum of utilities of the subset of buyers represented by it.

##  1 Introduction

The fact that the game is always bigger than you think is a major concern in
applied mechanism design. In many applications, auctioneers design their
auction assuming that the ultimate consumers are the ones bidding in the
auction. However, in many markets, buyers are not bidding in the auction but
are, instead, being represented by intermediaries. For example, intermediaries
are a common, though often ignored, element of advertisement auctions on the
Internet. In Sponsored search and Display ad auctions, advertisers are often
represented by ad agencies who optimize their online ad campaigns.111See Choi
et al. (2020) for a comprehensive review of intermediation in ad-auctions.
Another example is the AdExchange marketplace that sells advertisements on
webpages. In an AdExchange, the advertisers are represented by Ad Networks,
who do real-time bidding on their behalf into the AdExchange auction
(Muthukrishnan, 2009). Similarly, intermediation plays an important role in
over-the-counter markets. As described in Duffie et al. (2005), customers
interested in buying such assets usually execute their trades with dealers
(intermediaries), which are the ones interacting with the seller.

In this context, classic auction design may under-perform since intermediaries
may enable buyers to engage in collusive behavior, or because of the double
marginalization issue impacting the intermediaries’ preferences for outcomes.
The information about which buyers each intermediary represents and the
intermediaries’ incentives in the auction (which depend on the downstream
negotiation with buyers) is usually hard for the seller to know. With this in
mind, we design mechanisms that do not rely on this information. Specifically,
we design an intermediary-proof mechanism with two properties:

  1. 1.

It is independent of the market structure – which buyers are represented by
which intermediaries.

  2. 2.

The revenue obtained is a constant factor of the optimal welfare (the highest
revenue the auctioneer could possibly obtain).

Furthermore, our mechanism consists of a simple posted-pricing scheme that
depends only on the number of buyers, number of items and some order
statistics of the buyers’ valuation distribution.

###  1.1 Model and main results

Our model consists of one seller (the auctioneer) who owns $k$ items and $n$
unit-demand buyers. We start with the problem where the items are identical
and later tackle the case of non-identical but related items. For the
identical items case, each buyer has the same valuation for each item, which
is unknown to the seller. The valuations $(v_{i})_{i\in[n]}$ are assumed to be
drawn independently from the same distribution $F$. We further assume that the
distribution $F$ is $\lambda$-regular (see Definition 5 for details); note
that the class of $\lambda$-regular distributions allows us to smoothly
interpolate between monotone hazard rate (MHR) distributions ($\lambda=0$) and
the more general class of regular distributions $(\lambda=1)$. Each buyer
either participates directly in the auction or is represented by one of $m$
intermediaries. Taking an agnostic approach to how these decisions are made,
we consider a general partition of the buyers where all the buyers in one part
are represented by the same intermediary. Next, we abstract from the
downstream decisions and contracts between buyers and intermediaries and
consider a general class of utility functions for intermediaries. This class
is motivated by, and includes, two of the most natural and commonly-studied
intermediary utility functions: (a) surplus-maximizing intermediary which
maximizes the surplus of the buyers it represents and (b) the monopolist
intermediary that maximizes its profit from captive buyers. The class consists
of all utility functions that satisfy three natural properties: that each
intermediary can secure at least a payoff of zero (individual rationality);
that their payoff cannot be greater than the surplus created by the buyers
(i.e. intermediaries don’t create value); and that when the seller posts a
uniform price $r$ per item such that there are $q$ Buyers represented by
Intermediary $l$ with valuation at least $r$, then Intermediary $l$ will buy
at least $\tau_{l}q$ items in expectation (Buyer-Disconnectability).

The first result of the paper is the construction of a mechanism that for any
partition of the buyers and any aggregators’ utility functions that satisfy
the above conditions, guarantees at least
$\tau\frac{1}{2}(1-\lambda)^{\frac{1}{\lambda}}\left(1-\frac{1}{e}\right)$
fraction of the welfare where $\tau=\min\tau_{l}$ (see Theorem 1). This
translates to a $\tau\cdot 1/2e(1-1/e)$ approximation factor for MHR
distributions and a $0$ approximation factor for regular distributions222We
show that any mechanism that gets the same revenue from different market
structures (like ours) cannot get a constant factor of the revenue for regular
distributions – see Section 6 for details.. In other words, independent of
which buyers each intermediary represents and the exact details of the
downstream interaction between buyers and intermediaries, our mechanism gets a
constant-factor approximation of the revenue the seller could obtain if she
had complete information about the buyers’ valuations. We would like to note
that a priori, it is not at all obvious that such a robust mechanism exists.
As we show in Section 3, implementing the revenue-maximizing mechanism for a
particular partition of buyers can perform poorly when faced with a different
partition of buyers. The mechanism is a uniform posted-pricing scheme that
only depends on the number of items $k$, number of bidders $n$, and the
distribution $F$. More precisely, the seller posts a price per item
$p^{R}=\mathbb{E}[v^{(1,\lceil n/k\rceil)}]$, where $v^{(1,j)}$ is the largest
order statistic of $j$ samples drawn from $F$.333In case of excess demand,
items are randomly allocated among interested bidders.

Next in Section 5, we consider the problem when the items are not identical.
In particular, we consider the case of separable values, i.e. Buyer $i$’s
valuation of receiving item $j$ is given by $\eta_{j}v_{i}$. This is inspired
by sponsored search advertising, where different positions on the page may
have different click-through-rates and therefore different values (note that
this does not model sponsored search exactly as in our model, we can sell an
arbitrary subset of items, not necessarily a prefix). Compared to the
identical items case, the difficulty here is that to compete with welfare,
higher-weighted items must be allocated to high-valuation bidders. This
requires the mechanism to charge a higher cost for higher-weight items and
screen buyers according to their preference for high-value/high-cost items. To
do this, we make a more detailed assumption about the intermediaries’
preferences and consider the case where each intermediary is a surplus-
maximizing intermediary. With this, we construct a sequential posted-price
mechanism that, for every partition of buyers, obtains revenue equal to a
constant fraction of the welfare. Although the pricing scheme is more subtle
than for the homogeneous case, it nevertheless still possesses the nice
property of depending only on the number of items $k$, the weight values
$(\eta_{j})_{j\in[k]}$, the number of bidders $n$, and the valuation
distribution $F$.

###  1.2 Why is this interesting?

From an applied perspective, our intermediary-proof mechanisms have appealing
properties which, aside from the revenue guarantees, make them very suitable
for applications. First, their simplicity. Our mechanisms are a posted
pricing, requiring a simple menu to implement – this makes bidders less likely
to make strategic errors (Li, 2017). This contrasts with optimal auctions in
multidimensional environments (like ours) which are usually quite complex
(Daskalakis et al., 2017). Second, the mechanisms are detail-free – the seller
only requires knowledge of the number of buyers and good estimates about
buyers’ valuations 444In fact, our mechanism only requires us to estimate the
order statistics of the buyers distributions., and does not need to learn any
information about the market structure or the details of the intermediaries’
utility functions to implement the mechanism.

In fact, the price that we use, $\mathbb{E}[v^{(1,\lceil n/k\rceil)}]$, where
$v^{(1,j)}$ is the largest order statistic of $j$ samples drawn from $F$, is a
very natural function of the valuation distribution. Intuitively, this
captures the real competition for each item since there are $n/k$ buyers per
item. Although pricing based on the order statistics of the buyers’
distributions are commonly used in mechanism design, we believe this
particular function is new and its generalizations might prove useful in other
multi-item settings.

A consequence of our results (see Corollary 3), that might be of independent
interest, is that the optimal revenue for every demand structure and bidders’
utility functions (that satisfy the above conditions) is at least a constant
fraction of the optimal welfare (which is the same for all demand structures)
assuming that the distribution is $\lambda$-regular with $\lambda$ bounded
away from $1$ by a constant. In particular, this is true for the full
competition case, when all buyers participate directly in the auction and
their utility functions are simply quasi-linear. Consider any per-item uniform
posted-price mechanism (for the identical items case) that is constant-
competitive with optimal revenue under full competition. Since a uniform
posted-price mechanism achieves the same revenue under different demand
structures (upto a factor of $\tau$), this mechanism would also be constant-
competitive with respect to optimal welfare (and thus optimal revenue) under
all demand structures and bidders’ utility functions satisfying the above
conditions.

Another result that might be of independent interest is Lemma 1, which shows
that the largest order statistic of a $\lambda$-regular distribution is also
distributed according to a $\lambda$-regular distribution. The analogous
property for MHR distributions has proved quite useful in analyzing mechanisms
for those distributions, and we believe this property might be helpful in
extending some of those results to the $\lambda$-regular case.

###  1.3 Related Work

Our work differs from the literature about intermediation in auctions by
taking a robust approach to the market structure and the downstream contracts
between buyers and intermediaries. Prior work has tried to solve the optimal
mechanism for specific market structures while our mechanism provides a
constant approximation. Because finding the optimal mechanism has the
technical difficulty of first the need to characterize the subgame between
aggregators and buyers, most of this literature has centered their attention
in describing the downstream dynamics with a restrictive assumption on the
number of items, intermediaries, and buyers (Hummel et al., 2016;
Stavrogiannis et al., 2013; Balseiro et al., 2019; Balseiro and Candogan,
2017).555An important exception is Allouah and Besbes (2017) who shows in a
general framework that it is Pareto improving not to restrict the number of
bids each intermediary can submit. Closer to our work, Feldman et al. (2010)
shows that for the one-item case, the optimal mechanism when each intermediary
has one buyer captive consists of a second price auction (SPA) with a reserve
price that is decreasing with the number of bidders. Our mechanism instead
proposes a fixed pricing, which increases with the number of
bidders.666Feldman et al. (2010) also restricts attention to valuations
distribution satisfying the monotone hazard rate property, and hence, our
revenue guarantee apply to their setting. Finally, when buyers’ valuations are
fully correlated, Bergemann et al. (2017) shows that the optimal mechanism is
a posted-price mechanism.

####  1.3.1 Collusion in Auctions

The second stream of literature related to our work is the one studying
collusion in auctions (see Krishna (2009) for a textbook review of this
topic). This area studies auction design when bidders form bidding rings
(cartel) and collude with other bidders in the ring. In this context, a
bidding ring can be seen as an intermediary in our model. Che and Kim (2006)
provide a methodology to make a mechanism robust to any form of collusion. Che
and Kim (2009); Pavlov (2008) provide conditions where they can reshape the
optimal mechanism into a collusion-proof one. Although such results go along
the lines of our robustness approach regarding the market structure (here, how
the cartels are conformed), such mechanisms differ from ours in two crucial
layers. (i) They depend on the bidders’ specific payoff structures, while in
our mechanisms, such dependence is minimal. (ii) Their mechanisms are not ex-
post individually rational while our robust mechanisms satisfy this
property.777Che et al. (2018) shows that under some restriction on the
cartels, the optimal collusion-proof mechanism satisfies ex-post individually
rationality.

####  1.3.2 Multi-parameter Revenue-Optimal Auctions

Our work is also closely related to the work on multi-parameter mechanism
design. With intermediaries controlling multiple bids, they resemble buyers
buying multiple goods with set function valuation over the set of goods. In
particular, when the utility function of each intermediary is the aggregate
surplus of the buyers it represents, the intermediaries’ value for a set of
$i$ items is the sum of its $i$ highest values. This valuation function is
submodular as adding an item to a smaller set yields higher incremental value.
Note however that the intermediaries’ values for disjoint subsets of items are
not independent.

There is a long line of research studying multi-parameter mechanism design.
Cai et al. (2012a); Briest et al. (2010); Alaei et al. (2012) show how to
construct revenue-optimal mechanisms under fairly general conditions. However,
these mechanisms are necessarily complex Thanassoulis (2004); Manelli and
Vincent (2006); Hart and Reny (2015), leading to many papers studying simple
mechanisms for optimizing revenue in different settings. For example, there is
a stream of work providing simple mechanisms for set function valuations (such
as additive, unit-demand, submodular) Hart and Nisan (2017); Li and Yao
(2013); Babaioff et al. (2020); Yao (2015); Rubinstein and Weinberg (2015);
Cai et al. (2016); Chawla and Miller (2016); Cai and Zhao (2017). We refer the
readers to Cai and Zhao (2017) for the state of the art on this. These results
do not apply to our setting as they need the buyers’ valuations for disjoint
subsets of items to be independent which is not true in our setting. Also,
these mechanisms take the form of VCG with entry fee. VCG-like mechanisms can
perform poorly in the presence of intermediaries, need to be tailored to the
demand structure and make the intermediaries’ problem of bidding on behalf of
their buyer’s harder. For the correlated values setting, Hart and Nisan (2013)
show that finite menu-size mechanisms don’t perform well under arbitrary
correlations even with two items and one bidder.888 However, when the seller
is a max-min agent a pricing mechanism per item turns out to be optimal
Carroll (2017). In contrast, we show that with a specific type of correlation,
simple mechanisms with a small menu size perform well.

Another related sequence of papers Chawla et al. (2007, 2010a, 2010b); Alaei
et al. (2012); Cai et al. (2012b); Kleinberg and Weinberg (2012) provide
sequential posted-price mechanisms with a good approximation to the revenue.
As noted in the introduction, using Corollary 3, these mechanisms can be used
to obtain constant competitive mechanisms for our setting (see Proposition 5).
In fact, a special case of our results (namely, the homogeneous item case with
valuations drawn from an MHR distribution) can be obtained by combining the
results of Chawla et al. (2007, 2010a, 2010b) and a modification of the result
of Kleinberg and Yuan (2013), which considers the ratio of the optimal revenue
to optimal welfare and bounds this for the case of $c$-bounded regular
distributions. We note that it is not clear how to extend this approach to the
case of $\lambda$-regular distributions or the case of heterogeneous items.
For the case of heterogeneous items, existing posted price mechanisms do not
translate well to the intermediary setting and the result of Kleinberg and
Yuan (2013) does not apply to $\lambda$-regular distributions.

##  2 Model

The baseline model consists of a seller with $k$ items to sell. We first
consider the case where the items are homogeneous and later extend our results
to the case of non-homogeneous items with separable valuations (see Section
5). There are $n$ unit-demand buyers. For each $i\in[n]$, buyer $i$ has a
valuation $v_{i}$ for obtaining an item. We assume that the valuations $v_{i}$
are drawn independently and identically distributed (i.i.d.) according to a
distribution $F$ with support on $\mathbb{R}_{+}$.

A buyer may choose to bid directly in the auction or through an intermediary.
Our model is agnostic to how these decisions (and negotiations) are made and,
hence, we allow for an arbitrary partition of buyers across intermediaries
ultimately bidding in the auction.999A buyer bidding directly in the platform
corresponds to an intermediary exclusively representing him.

######  Definition 1 (Demand Structure).

The demand structure $(m,\pi)$ of a market with $n$ buyers is composed of
$m\leq n$ intermediaries and a partition $\pi(\cdot)$ of the set of buyers
$[n]$. For an intermediary $l\in[m]$ $\pi(l)$ denotes the set of buyers that
$l$ represents.

In particular, notice that our model includes the competition case, when all
buyers are bidding directly in the auction ($m^{C}=n$, $\pi^{C}(l)=\\{l\\}$),
and the monopsony case, when all buyers are represented by the same
intermediary ($m^{M}=1$, $\pi^{M}(1)=[n]$).

Although we consider the demand structure as exogenously given, our results
can be easily extended to a setting where buyers strategically decide whether
to participate directly in the auction or to be represented by a particular
intermediaries (see Remark 1 below for details).

Intermediaries’ utility functions

Motivated by two of the most natural and commonly-studied intermediary utility
functions – (a) surplus-maximizing intermediary which maximizes the surplus of
the buyers it represents and (b) the monopolist intermediary that maximizes
its profit from captive buyers – we consider a general class of intermediary
utility functions. Let ${\bm{v}}_{l}=(v_{i})_{i\in\pi(l)}$ be the valuations
of the buyers represented by Intermediary $l$. Given $x_{l}\in[k]$ items
allocated to Intermediary $l$ for a price $p_{l}\in\mathbb{R}_{+}$, we denote
by $U_{l}(x_{l},p_{l};{\bm{v}}_{l})$ Intermediary $l$’s utility function. We
apply the following natural restrictions:

  1. 1.

(Individual Rationality) The Intermediary $l$ does not obtain any item, it
gets a payoff of zero (i.e. $l$ always opt out from the auction).

  2. 2.

(Does not create value) For every vector of valuations ${\bm{v}}_{l}$,
allocation $x_{l}$, and price $p_{l}$ we have that

$\displaystyle U_{l}(x_{l},p_{l};{\bm{v}}_{l})\leq
V(x_{l},p_{l};{\bm{v}}_{l}):=$
$\displaystyle\max_{z_{l}\in[0,1]^{\pi(l)}}\left\\{\sum_{i\in\pi(l)}v_{i}z_{il}-p_{l}\;\bigg{|}\;\sum_{i\in\pi(l)}z_{il}\leq
x_{l}\right\\}$

  3. 3.

(Buyer-Disconnectability) When Intermediary $l$ can obtain the items for a
uniform price of $r$ per item, Intermediary $l$ wants to purchase at least
$\tau_{l}\cdot|\\{i:v_{i}\geq r\;\mbox{ for }i\in\pi(l)\\}|$ items in
expectation, for $\tau_{l}\in(0,1]$. In particular, for a surplus-maximizing
intermediary $\tau_{l}=1$ while for a monopolist intermediary
$\tau_{l}\geq\frac{1}{e}$ whenever $F$ is MHR (see Lemma 2 for details).

Condition 1 implies that intermediaries cannot obtain a negative payoff.
Condition 2 captures that intermediaries do not generate value, hence, their
payoff is bounded by $V(x_{l},p_{l};{\bm{v}}_{l})$, the highest surplus
Intermediary $l$ can generate among buyers in $\pi(l)$. Condition 3 is a
Buyer-Disconnectability condition: when items are not bundled and have a
uniform per-item price $r$, if $s$ buyers in $\pi(l)$ would like to buy an
item at the price $r$, then, independent of the valuations
${\bm{v}}_{\pi(l)\setminus s}$, Intermediary $l$ wants to buy at least
$\tau_{l}\cdot s$ items at that price. The probability $\tau_{l}$ captures the
level of double-marginalization that may arise due to the downstream
interaction between Intermediary $l$ and Buyers $i\in\pi(l)$. For example,
when Intermediary $l$ is a monopolist (with respect to the buyers in
$\pi(l)$), trying to maximize its own revenue, we have that
$\tau_{l}\geq\frac{1}{e}$ if the distribution $F$ is MHR (see Lemma 3 for a
precise statement).

The restrictions on the intermediaries’ utility functions include models
previously studied. Consider the following examples:

  * •

A negotiation between buyers and intermediaries (with no asymmetric
information) can lead to a utility function of the form

$U_{l}(x_{l},p_{l};{\bm{v}}_{l})=\alpha_{l}(v_{l},x_{l},p_{l})V(x_{l},p_{l};{\bm{v}}_{l}),$
(1)

where $\alpha_{l}({\bm{v}}_{l},x_{l},p_{l})$ may represent either Intermediary
$l$’s bargaining power or an auditing fee. In particular, when
$\alpha_{l}\equiv 1$, Intermediary $l$ has full bargaining power. A simple
exercise shows that for this class of utilities functions, the Buyer-
Disconnectability condition holds with $\tau_{l}=1$.

  * •

Intermediaries are profit-maximizers and lack knowledge of buyers’ valuations.
The intermediary can run a revenue maximizing truthful auction to maximize its
profit. Lemma 3 shows that these utilities functions satisfy our requirements
with $\tau_{l}=c(\lambda)$.

The seller’s problem. The seller wants to implement a mechanism that maximizes
her revenue. From the revelation principle (Myerson, 1981), we can restrict
our attention to direct bayesian incentive compatible mechanisms (BIC). That
is, $(x_{l},p_{l})_{l\in[m]}$, where
$x_{l}:[\underline{v},\overline{v}]^{n}\to\Delta([k])$,101010For a set $X$, we
denote by $\Delta(X)$ the set of probability measures on $X$.
$p_{l}:[\underline{v},\overline{v}]^{n}\to\mathbb{R}_{+}$, satisfying

$\displaystyle\mathbb{E}[U_{l}(x_{l}({\bm{v}}_{l},{\bm{v}}_{-l}),p_{l}({\bm{v}}_{l},{\bm{v}}_{-l});{\bm{v}}_{l})\;|{\bm{v}}_{l}]$
$\displaystyle\geq\mathbb{E}[U_{l}(x_{l}({\bm{v}}^{\prime}_{l},{\bm{v}}_{-l}),p_{l}({\bm{v}}^{\prime}_{l},{\bm{v}}_{-l});{\bm{v}}_{l})\;|{\bm{v}}_{l}]$
(IC)
$\displaystyle\mathbb{E}[U_{l}(x_{l}({\bm{v}}_{l},{\bm{v}}_{-l}),p_{l}({\bm{v}}_{l},{\bm{v}}_{-l});{\bm{v}}_{l})\;|{\bm{v}}_{l}]$
$\displaystyle\geq 0$ (IR) $\displaystyle\sum_{l\in[m]}x_{l}({\bm{v}})$
$\displaystyle\leq k\qquad\mbox{ (a.s.)}.$

We denote by
$\mbox{Rev}(F,m,\pi;({\bm{x}},{\bm{p}}))=\mathbb{E}\bigg{[}\sum_{l\in[m]}p_{l}({\bm{v}})\bigg{]}$
the revenue the seller receives by implementing mechanism
$({\bm{x}},{\bm{p}})$.

We define $\mbox{Rev}(F,m,\pi)$ to be the optimal expected revenue.

######  Definition 2 (Optimal Expected Revenue, $\mbox{Rev}(F,m,\pi)$).

$\mbox{Rev}(F,m,\pi)=\max_{({\bm{x}},{\bm{p}})\in\mbox{(BIC)}}\mbox{Rev}(F,m,\pi;({\bm{x}},{\bm{p}})).$

######  Definition 3 ($v^{(j,t)}$).

Define $v^{(j,t)}$ to be the $j^{th}$-order statistic of
${\bm{v}}=(v_{i})_{i\in[t]}$, where each $v_{i}$ is drawn i.i.d. according to
the distribution $F$.

######  Definition 4 (Expected Optimal Welfare, $\mbox{Wel}(F)$).

$\mbox{Wel}(F)=\mathbb{E}\bigg{[}\max_{{\bm{x}}\in\mathbb{R}^{n}}\sum_{i\in[n]}v_{i}x_{i}\bigg{]}=\mathbb{E}\bigg{[}\sum_{j=1}^{k}v^{(j,n)}\bigg{]},$

where $v^{(j,n)}$ is the $j^{th}$-order statistics of the random variable
${\bm{v}}=(v_{i})_{i\in[n]}$.

######  Remark 1.

For the purpose of a clearer exposition, our model restricts attention to
cases where the demand structure is independent of the mechanism selected by
the seller. However, our results can be easily generalized for the cases when
$(m,\pi)$ is a function of $({\bm{x}},{\bm{p}})$.

Revenue benchmark: We will use Expected Optimal Welfare, $\mbox{Wel}(F)$
defined above as our revenue benchmark. Our use of this benchmark is motivated
by two factors: (a) The maximum revenue a seller can extract can never exceed
this benchmark (as noted in the lemma below), and (b) the optimal revenue
mechanism (and the optimal revenue) is typically difficult to characterize in
multi-parameter settings.

######  Lemma 1.

For every distribution $F$ and demand structure $(m,\pi)$,
$\mbox{Rev}(F,m,\pi)\leq\mbox{Wel}(F)$.

This result is standard in the auction literature and it naturally extends to
our setting since intermediaries don’t create value (Condition 2 on $U_{l}$).

#### Distributional Assumptions

We use $\phi(v):=v-\frac{1-F(v)}{f(v)}$ to denote the virtual valuation for a
value $v$, drawn from a distribution with CDF $F$ and PDF $f$. Throughout the
paper we make the following assumption.

######  Definition 5 ($\lambda$-regularity).

Given $\lambda\in[0,1]$, a distribution $F$ is $\lambda$-regular if $\lambda
v+\frac{1-F(v)}{f(v)}$ is non-decreasing on
$v\in[\underline{v},\overline{v}]$.

######  Assumption 1 ($F$ is $\lambda$-regular).

The distribution $F$ has a density $f>0$ on the support
$[\underline{v},\overline{v}]$ ($\underline{v}<\overline{v}\leq\infty$), and
is $\lambda$-regular for $\lambda<1$.

Observe that for $\lambda=0$, the condition is equivalent to the monotone
hazard rate condition commonly used in economics literature, while for
$\lambda=1$, the condition is equivalent to the Myerson regularity condition.
A distribution satisfying the $\lambda$-regularity has three important
properties which are key to the robustness of our mechanism.

######  Fact 1.

Let $F^{(1)}$ the distribution of the first order statistic of $n$ i.i.d.
random variables drawn according to $\lambda$-regular distribution $F$. Then,
$F^{(1)}$ is $\lambda$-regular.

To the best of our knowledge, 1 is not known prior to our work and we provide
a full proof in the appendix. We use a nontrivial characterization of
$\lambda$-regular distributions given by Schweizer and Szech (2019)] to prove
this fact and it might be of independent interest.

We define the following notation which will be used throughout the paper:

######  Definition 6.

($c(\lambda)$) We define the quantity
$c(\lambda)=(1-\lambda)^{\frac{1}{\lambda}}$ for all $\lambda\in(0,1]$ and
define $c(0)=\lim_{\lambda\to 0}c(\lambda)=\frac{1}{e}$.

######  Fact 2.

[Schweizer and Szech (2019)] For a random variable $v$ drawn from a
$\lambda$\- regular distribution $F$, we have that
$\mathbb{P}[v\geq\mathbb{E}[v]]\geq c(\lambda)$.

######  Fact 3.

$\mathbb{P}[v^{(1,s-1)}\geq\mathbb{E}[v^{(1,s)}]]\geq\frac{s-1}{s}c(\lambda)$.

###### Proof.

Draw $X_{1},X_{2},\ldots,X_{s}$ i.i.d. from F. Let $v^{(1,s)}$ be the maximum
of $X_{1},X_{2},\ldots,X_{s}$, and let $v^{(1,s-1)}$ be the maximum of
$X_{1},X_{2},\ldots,X_{s-1}$. From 1 and 2, we know that
$\mathbb{P}[v^{(1,s)}\geq\mathbb{E}[v^{(1,s)}]]\geq c(\lambda)$. Since each of
the $s$ draws is equally likely to be $v^{(1,s)}$, the probability that
$v^{(1,s)}$ lies in the first $s-1$ draws is $\frac{s-1}{s}$, giving

$\displaystyle\mathbb{P}[v^{(1,s-1)}\geq\mathbb{E}[v^{(1,s)}]]$
$\displaystyle\geq\mathbb{P}[v^{(1,s)}\in\\{X_{1},X_{2},\ldots,X_{s-1}\\}]\cdot\mathbb{P}[v^{(1,s)}\geq\mathbb{E}[v^{(1,s)}]]\geq\frac{s-1}{s}c(\lambda)$

∎

##  3 The importance of being robust

In this section, we argue the importance of implementing a mechanism that is
robust to the details of the intermediaries’ utility functions and to the
different demand structures that may arise.

First, consider the dependence on intermediaries’ utility functions. An
intermediary’s utility function arises from the downstream
negotiations/contracts/mechanisms involving the individual buyers it
represents. These downstream interactions may take many different forms and
can vary by intermediary and change over time. It is hard for a seller to know
about the details of these downstream interactions between each intermediary-
buyer pair. And even in cases where the seller knows these details, the seller
could be faced with a difficult mechanism design problem involving bidders
with complex and heterogeneous multi-dimensional utility functions (see the
literature review section in the introduction for a flavor of the difficulty
of the problem). A mechanism that does not depend on the details of the
intermediaries’ payoff structures lets the seller sidestep these issues,
additionally guaranteeing that it will continue to perform well even when the
downstream contracts change.

Next, we argue the importance of implementing a mechanism that is robust to
different demand structures. To this effect, we will show that natural
revenue-maximizing mechanisms tailored for a particular demand structure can
have perform quite poorly when faced with a different demand structure. If a
seller implements a mechanism that depends on the demand structure, the seller
should either know the demand structure beforehand with some certainty or
construct a mechanism in which the seller learns the demand structure as part
of the mechanism. We note that it is possible to construct a mechanism that
learns the demand structure without incurring any cost (in one of its
equilibria)111111The first stage of the mechanism consists of asking each
intermediary how many buyers it is representing, and if the total sum is not
$n$, then the seller does not move to the second stage of the mechanism.
Clearly, an equilibrium exists where intermediaries truthfully report the
number of buyers they represent. Even though such a mechanism may perform well
in theory, the first stage of the mechanism is quite unstable – there exist
equilibria such that the mechanism never reaches the second step, resulting in
zero revenue for the seller.

In the rest of the section, we show that natural revenue-maximizing mechanisms
designed for a particular demand structure $(m,\pi)$ can perform poorly when
presented with a different demand structure $(m^{\prime},\pi^{\prime})$. More
precisely, we compare two extreme demand structures: competition
$(m^{C}=[n],\pi^{C}(l)=\\{l\\})$ and monopsony $(m^{M}=1,\pi^{M}(1)=[n])$. For
this exposition, we assume that intermediaries have complete information and
full bargaining power, i.e., their utilities functions are
$U_{l}(x_{l},p_{l};{\bm{v}}_{l})=V(x_{l},p_{l};{\bm{v}}_{l})=\sum_{j=1}^{x_{l}}v^{(j,\pi(l))}-p_{l}$.

Along with showing that robustness is critical in situations where the demand
structure is unknown, we observe a surprising result that is of independent
interest. We show that there are instances where a seller prefers facing a
monopsony demand structure rather than full competition. Even though
competition is helpful in raising prices in an auction, facing one bidder that
demands multiple items allows the seller to construct bundle mechanisms which
are known to be more effective compared to simply selling the items separately
(McAfee et al., 1989). In particular, we observe that the competition effect
is particularly helpful in situations when there is scarcity of items (small
$k$) while the bundling effect is helpful in the presence of many items (high
$k$).

###  3.1 Optimal mechanism for the competition case

We first characterize the optimal auction for the competition case and show
that in some instances, it performs poorly for the monopsony case.

######  Proposition 1.

In the competition case, the revenue-maximizing mechanism can be implemented
with $(k+1)^{th}$-price auction with a reserve price $r=\phi^{-1}_{F}(0)$.

Although this statement is a well-known result in the literature, for the sake
of completeness we provide a complete proof in the appendix.

To simplify notation, we define
$\mbox{Rev}^{C}({\bm{x}},{\bm{p}})=\mbox{Rev}^{C}(F,m^{C},\pi^{C};({\bm{x}},{\bm{p}}))$
and $\mbox{Rev}^{C}=\mbox{ Rev}^{C}(F,m^{C},\pi^{C})$. Likewise, we define
Rev${}^{M}({\bm{x}},{\bm{p}})$ and RevM for the monopsony case.

The next proposition shows that there exists an instance where the revenue
obtained by the optimal mechanism for the competition case is not constant-
competitive when the demand structure is monopsony (we defer the proof to the
appendix).

######  Proposition 2.

Let $({\bm{x}}^{C},{\bm{p}}^{C})$ be the optimal mechanism for the competition
case. Then for every $\gamma>0$, there exist $n,F,k$ such that
Rev${}^{M}({\bm{x}}^{C},{\bm{p}}^{C})<\gamma$RevM.

###  3.2 Optimal mechanism for the monopsony case

The previous result shows that implementing the optimal mechanism for the
competition case can have a low performance when the demand structure is a
monopsony. To show the converse, that the optimal mechanism for the monopsony
case has a low performance on the competition setting, is technically
challenging since we need to solve a multi-item mechanism design problem. Even
for $k=n$, when the intermediary’s valuations for the items are i.i.d, we have
that there are instances where the optimal mechanism consists of a complex set
of menus (Daskalakis et al., 2017). For the case $k<n$, when valuations are
correlated, finding the optimal mechanism is believed to be hard, and to the
best of our knowledge, it remains an open problem. That being said, the next
result shows that the simple mechanism of selling all items as a bundle gets a
constant factor of the optimal revenue, and when $k=n$, it is asymptotically
optimal. This result suggests that for $k=n$ a seller facing a monopsony
should implement a (near-optimal for large $n$) pure bundling strategy. Once
again, due to space constraints, we will defer the proofs to the appendix.

######  Proposition 3.

Suppose that $F$ is MHR, then for the monopsony case consider the mechanism
selling all $k$ items in a bundle for a price $p_{B}=\phi_{G}^{-1}(0)$ where
$G$ is the distribution of $\sum_{i=1}^{k}v^{(i,n)}$. Then, the above
mechanism provides at least $\frac{1}{e}$ of the optimal mechanism. Moreover
for any distribution $F$ with finite moments we have that when $k=n$, the
revenue of selling the bundle at a price
$p^{\epsilon}_{B}=n(\mathbb{E}[v]-\epsilon)$ is asymptotically optimal as
$n\to\infty$ and $\epsilon\to 0$.121212Csorgo (1989); Broniatowski and Weber
(1998) show an asymptotic result for the case $k<n$ when the hazard rate
$h_{F}$ has a linear growth and $k(n)$ does not increase too fast with $n$.

Using the previous result we obtain the surprising result that a monopsony may
be preferable for the seller over competition.

######  Corollary 1.

There are some instances where R${}^{M}>$RC.

Next we show that the bundle pricing mechanisms can make very little revenue
when faced with Competition demand structure, compared to the optimal
mechanism for Competition.

######  Proposition 4.

Consider the case $k=n$ and suppose that the seller implements the
asymptotically optimal bundle pricing mechanism
$({\bm{x}}^{B},p_{B}^{\epsilon})$. Then for every $\gamma>0$, there exists an
instance $F$ such that Rev${}^{C}({\bm{x}}^{B},p_{B}^{\epsilon})<\gamma$RevC.

##  4 The Intermediary-Proof Mechanism

This section constructs the Intermediary-Proof Mechanism (IPM) and shows that
for any demand structure $(m,\pi)$ and any intermediaries’ utility functions
$(U_{l})_{l\in[m]}$ satisfying conditions (1)-(3), the IPM obtains a constant
factor of the welfare and, therefore, of the optimal expected revenue
$\mbox{Rev}(F,m,\pi)$. As a corollary, we obtain that the revenue-maximizing
mechanism for each particular market structure is always a constant factor of
the welfare.

We begin by identifying a key property of order statistics of i.i.d. samples
from a distribution $F$. We show that expectation of the highest value among
$\lceil n/k\rceil$ i.i.d. samples is at least a constant fraction of the
average of the expectations of the top $k$ samples among $n$ i.i.d.
samples.131313Because intermediaries’ don’t create value (Condition 2) and
buyers are unit-demand, without loss of generality we can assume that $k\leq
n$. We note that the above fact is true for all distributions. The lemma below
will serve as the basis for the Intermediary-Proof Mechanism .

######  Lemma 2.

Recall that $v^{(j,t)}$ is the $j^{th}$-order statistics of $t$ i.i.d. random
variables drawn according to $F$. If $n\geq k$,

$k\cdot\mathbb{E}[v^{(1,\lceil
n/k\rceil)}]\geq\left(1-\frac{1}{e}\right)\left(\sum_{j=1}^{k}\mathbb{E}[v^{(j,n)}]\right),$

###### Proof.

Let $X=\\{v_{1},\dots v_{n}\\}$ be a set of $n$ i.i.d. random variables drawn
from $F$. We denote the $k$ largest random variables to be
$v^{(1,n)},v^{(2,n)},\dots,v^{(k,n)}$ and we shall refer to them as “large”
elements. Let $s=\lceil n/k\rceil$. One way to choose $s$ random variables
uniformly at random is to choose a subset of size $s$ uniformly at random from
$X$. Let $Y=\\{Y_{1},\dots Y_{s}\\}$ be a uniformly random subset of X of size
$s$. If the set $Y$ contains a large element, then the $\max_{i}{Y_{i}}$ must
be a large element. In expectation, the value of a large element is
$\sum_{j=1}^{k}\mathbb{E}[v^{(j,n)}]/k$. We will now show that the probability
that $Y$ contains no large elements is at most $\frac{1}{e}$.

To see this, observe that

$\displaystyle\mathbb{P}[Y\text{ contains no large elements}]$
$\displaystyle=\frac{\binom{n-k}{s}}{\binom{n}{s}}$
$\displaystyle=\frac{(n-k)!}{n!}\cdot\frac{(n-s)!}{(n-k-s)!}$
$\displaystyle=\prod_{j=1}^{k}\left(1-\frac{s}{n-k+j}\right)$
$\displaystyle\leq\prod_{j=1}^{k}\left(1-\frac{s}{sk-k+j}\right)\leq(1-1/k)^{k}\leq
1/e$

Thus we get that
$\mathbb{E}[v^{(1,s)}]\geq(1-\frac{1}{e})\cdot\frac{1}{k}\mathbb{E}[\sum_{j=1}^{k}v^{(j,n)}]$.
∎

We are now in position to present the Intermediary-Proof Mechanism .

######  Definition 7 (Intermediary-Proof Mechanism).

Let $s=\lceil n/k\rceil$. The Intermediary-Proof Mechanism
$({\bm{x}}^{R},{\bm{p}}^{R})$ consists of a simple uniform single-item pricing
scheme where each item is sold separately at a price
$p^{R}=\mathbb{E}[v^{(1,s)}]$. In the case of excess demand, items are
randomly allocated among the interested bidders.

Remarkably, the IPM is a simple single-item posted-price that depends only on
the number of items $k$, number of buyers $n$ and the distribution $F$. Thus,
the seller does not have to learn the demand structure nor the intermediaries’
payoff. In other words, the IPM is completely robust to the intermediaries’
involvement in the auction. Besides the simplicity of its implementation,
posted prices have appealing properties for the bidders’ behavior (Goldberg
and Hartline, 2005).

We next prove that the Intermediary-Proof Mechanism obtains a constant factor
of the optimal revenue. The proof proceeds by dividing the $n$ bidders into
$k$ groups of roughly $\lceil n/k\rceil$ bidders and estimating the revenue
from selling a single item to each group.

######  Theorem 1.

Let $\tau=\min_{l\in[m]}\tau_{l}$, then for every distribution $F$ and demand
structure $(m,\pi)$ we have that

$\mbox{Rev}(F,m,\pi;({\bm{x}}^{R},{\bm{p}}^{R}))\geq\tau\cdot\frac{c(\lambda)}{2}\cdot\left(1-\frac{1}{e}\right)\mbox{Wel}(F)\geq\tau\cdot\frac{c(\lambda)}{2}\cdot\left(1-\frac{1}{e}\right)\mbox{Rev}(F,m,\pi).$

Recall $c(\lambda)=(1-\lambda)^{\frac{1}{\lambda}}$ for $\lambda\in(0,1]$ and
$c(0)=\lim_{\lambda\to 0}c(\lambda)=\frac{1}{e}$. Also recall that $\lambda=0$
for MHR distributions.

###### Proof.

We start by dividing the $n$ valuations $v_{i}$, $i\in[n]$, randomly into $k$
sets of size $s^{\prime}$, where $s^{\prime}=1$ if $s=1$, and $s^{\prime}=s-1$
otherwise (there might be some leftover valuations after we make the sets). We
note that the maximum valuation in each of these sets is distributed according
to $v^{(1,s^{\prime})}$.

The Buyer-Disconnectability condition on $U_{l}$ (Condition 3) implies that
Intermediary $l$ will try to buy at least $\tau\cdot|\\{i:v_{i}\geq
p^{R},i\in\pi(l)\\}|$ items in expectation. Using this, we lower bound the
revenue as follows.

$\displaystyle\mbox{Rev}(F,m,\pi;({\bm{x}}^{R},{\bm{p}}^{R}))$
$\displaystyle\geq\tau\sum_{i=1}^{n}\mathbb{P}[\text{Buyer }i\mbox{ has value
at least }p^{R}]\cdot p^{R}$ $\displaystyle\geq\tau\cdot
k\cdot\mathbb{P}[v^{(1,s^{\prime})}\geq p^{R}]\cdot p^{R}$
$\displaystyle\geq\tau\cdot k\cdot\frac{s^{\prime}}{s}\cdot
c(\lambda)\cdot\mathbb{E}[v^{(1,s)}]$
$\displaystyle\geq\tau\cdot\frac{s^{\prime}}{s}\cdot
c(\lambda)\cdot\left(1-\frac{1}{e}\right)\cdot\underbrace{\left(\sum_{j=1}^{k}\mathbb{E}[v^{(j,n)}]\right)}_{\mbox{Wel}(F)}$
$\displaystyle\geq\tau\cdot\frac{c(\lambda)}{2}\cdot\left(1-\frac{1}{e}\right)\mbox{Wel}(F)$
$\displaystyle\geq\tau\cdot\frac{c(\lambda)}{2}\cdot\left(1-\frac{1}{e}\right)\mbox{Rev}(F,m,\pi).$

The third inequality holds because of 3 and the definition of $p^{R}$. The
fourth inequality comes from Lemma 2. The last inequality is due to Lemma 1. ∎

In the proof of the theorem we observe that $1/2$ factor is not necessary when
$s^{\prime}=s$, i.e., when $n/k$ is an integer number. The following corollary
remarks this observation.

######  Corollary 2.

Suppose that $n/k$ is an integer number. Then,

$\mbox{Rev}(F,m,\pi;({\bm{x}}^{R},{\bm{p}}^{R}))\geq\tau
c(\lambda)\left(1-\frac{1}{e}\right)\mbox{Wel}(F)\geq\tau
c(\lambda)\left(1-\frac{1}{e}\right)\mbox{Rev}(F,m,\pi).$

A second consequence of Theorem 1, which is of independent interest, shows
that for every demand structure and bidders’ utility functions satisfying
Conditions (1) - (3), the optimal revenue is a constant factor of the optimal
welfare.

######  Corollary 3.

For every distribution $F$ and demand structure $(m,\pi)$, we have that

$\mbox{Rev}(F,m,\pi)\geq\tau\frac{c(\lambda)}{2}\left(1-\frac{1}{e}\right)\mbox{Wel}(F).$

The above corollary enables us to show that per-item posted-price mechanisms
that perform well in the full competition setting (when all buyers participate
directly in the auction) perform well in the context of intermediation as well
when conditions (1)-(3) are satisfied. This is because per-item posted-price
mechanisms provide, up to a constant factor $\tau$, the same revenue for the
seller under all demand structures. Combined with Corollary 3, this implies
that if a per-item posted-price mechanism is a constant approximation of the
optimal revenue for a particular demand structure (e.g. full competition),
then it is a constant approximation of the welfare, and hence the optimal
revenue for any demand structure.141414Chawla et al. (2007) construct a
uniform per-item posted-pricing mechanism that is at least a 14% approximation
of the optimal mechanism when buyers are directly bidding in the auction
(competition case). Corollary 3 guarantees that this mechanism provides a
$\tau\;\frac{0.14}{2e}\left(1-\frac{1}{e}\right)$ approximation of the welfare
and also the revenue for any demand structure. We now extend this to a more
general class of mechanisms.

######  Definition 8 ($\beta$-Robust Mechanism).

A mechanism $({\bm{x}},{\bm{p}})$ is a $\beta$-Robust Mechanism if for every
distribution $F$ and demand structures $(m,\pi)$, $(m^{\prime},\pi^{\prime})$
we have that
$\mbox{Rev}(F,m^{\prime},\pi^{\prime};({\bm{x}},{\bm{p}}))\geq\beta\;\mbox{Rev}(F,m,\pi;({\bm{x}},{\bm{p}}))$.151515Note
that from the Buyer-Disconnectability condition on the intermediaries’ utility
function, every per-item posted-pricing mechanism is a $\tau$-Robust
Mechanism.

######  Proposition 5.

Consider a $\beta$-Robust Mechanism $({\bm{x}},{\bm{p}})$ such that the
revenue for the demand structure $(\overline{m},\overline{\pi})$ is a $\gamma$
approximation of $\mbox{Rev}(F,\overline{m},\overline{\pi})$. Then for every
distribution $F$ and demand structure $(m,\pi)$ we have that

$\displaystyle\mbox{Rev}(F,m,\pi;({\bm{x}},{\bm{p}}))\geq\beta\gamma\tau\frac{c(\lambda)}{2}\left(1-\frac{1}{e}\right)\mbox{Wel}(F)\geq\beta\gamma\tau\frac{c(\lambda)}{2}\left(1-\frac{1}{e}\right)\mbox{Rev}(F,m,\pi).$

###### Proof.

We do the proof in two steps. First, because $({\bm{x}},{\bm{p}})$ is a
$\beta$-Robust Mechanism we have that
$\mbox{Rev}(F,m,\pi;({\bm{x}},{\bm{p}}))\geq\beta\;\mbox{Rev}(F,\overline{m},\overline{\pi};({\bm{x}},{\bm{p}}))$.
Second, Corollary 3 implies that
$\mbox{Rev}(F,\overline{m},\overline{\pi};({\bm{x}},{\bm{p}}))\geq\gamma\tau\frac{c(\lambda)}{2}\left(1-\frac{1}{e}\right)\mbox{Wel}(F)$.
We conclude using that $\mbox{Wel}(F)\geq\mbox{Rev}(F,m,\pi)$. (Lemma 1). ∎

To finish this section we present two important applications of Theorem 1. The
first one is when the intermediaries are aware of the buyers’ valuations, and
their payoff is a fraction of the overall surplus (see Equation (1)). In that
case, $\tau_{l}=1$ for every $j$.

######  Corollary 4.

When intermediaries utilities’ functions are of the form described in Equation
(1) the robust mechanism gets at least a
$\frac{c(\lambda)}{2}\left(1-\frac{1}{e}\right)$ fraction of the Optimal
welfare (and revenue).

The second application is the case of double marginalization when each
intermediary does not know the buyer’s valuation and decides to implement the
profit-maximizing mechanism. The following lemma shows that for that case
$\tau_{l}\geq\frac{1}{e}$.

For the sake of exposition, we state and prove the following lemma first for
the case when the distribution is MHR(i.e. $\lambda=0$). We present the
general lemma below and defer the proof to the appendix.

######  Lemma 3.

Suppose that Intermediary $l$ is a monopolist and only knows the prior of the
buyer’s valuations. If the seller posts a price $p$ per item and Buyer
$i\in\pi(l)$ has valuation $v_{i}\geq p$ then the probability that
Intermediary $l$ would like to buy one item is at least $\frac{1}{e}$.

###### Proof.

Because the price per item is $p$, the mechanism design problem for
Intermediary $l$ is the same one solved in the Proof of Proposition 1 when the
cost of production is $p$. Thus, Intermediary $l$ would like to allocate the
item to Buyer $i$ if $\phi_{F}(v_{i})\geq p$. Thus, we need to show that
$\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq p]\geq\frac{1}{e}$.

From Bayes’ rule we derive that

$\displaystyle\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq p]$
$\displaystyle=\frac{\mathbb{P}[\phi_{F}(v_{i})\geq p,v_{i}\geq
p]}{\mathbb{P}[v_{i}\geq p]}=\frac{\mathbb{P}[\phi_{F}(v_{i})\geq
p]}{\mathbb{P}[v_{i}\geq p]}$
$\displaystyle=\frac{1-F(\phi^{-1}_{F}(p))}{1-F(p)}.$

The second equality follows from the fact that
$\phi_{F}(v_{i})=v_{i}-(1-F(v_{i}))/f(v_{i})\leq v_{i}$. Also, note that
$1-F(v)=e^{-H(v)}$ where $H(v)=\int_{0}^{v}h_{F}(z)dz$. Then, we have that

$\displaystyle\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq p]$
$\displaystyle=e^{-(H(\phi^{-1}_{F}(p))-H(p))}$ $\displaystyle\geq
e^{-\max_{p\geq 0}(H(\phi^{-1}_{F}(p))-H(p))}$
$\displaystyle=e^{-\max_{p\geq\phi^{-1}(0)}(H(p)-H(\phi_{F}(p)))},$

where the last equality holds because $\phi_{F}$ is increasing.

To conclude the proof, we assert that $H(p)-H(\phi_{F}(p))\leq 1$. Indeed,
because $F$ is MHR we have that $H$ is convex with $H^{\prime}(v)=h_{F}(v)$.
The convexity and differentiability of $H$ implies that

$H(\phi_{F}(p))\geq H(p)+h_{F}(p)(\phi_{F}(p)-p).$ (2)

From the definition of the virtual valuation we have that
$\phi_{F}(p)=p-\frac{1}{h_{F}(p)}$. Replacing in the previous inequality we
conclude that $H(p)-H(\phi_{F}(p))\leq 1$. ∎

######  Lemma 4.

Suppose that Intermediary $l$ is a monopolist and only knows the prior of the
buyer’s valuations. If the seller posts a price $p$ per item and Buyer
$i\in\pi(l)$ has valuation $v_{i}\geq p$ then the probability that
Intermediary $l$ would like to buy one item is at least $c(\lambda)$. Recall
$c(\lambda)=(1-\lambda)^{\frac{1}{\lambda}}$ for $\lambda\in(0,1]$ and
$c(0)=\lim_{\lambda\to 0}c(\lambda)=\frac{1}{e}$.

We defer the proof to the appendix.

######  Corollary 5.

Suppose that each intermediary is behaving as monopolist and implementing the
profit-maximizer mechanism. Then, the robust mechanism has a
$\frac{c(\lambda)^{2}}{2}\left(1-\frac{1}{e}\right)$ revenue guarantee.

##  5 Selling non-homogeneous items

In this section, we consider the problem when the items are not necessarily
homogeneous. We consider $k$ items with weights
$\eta_{1}\geq\eta_{2}\geq\ldots\geq\eta_{k}\geq 0$ so that the value for buyer
$i$ of getting item $j$ is $\eta_{j}v_{i}$. Given that the items are non-
identical, we will adapt the mechanisms the seller can implement to
incorporate per-item allocation. In this setting, a BIC mechanism consists of
$(x_{jl},p_{l})_{j\in[k],l\in[m]}$, where $x_{jl}$ is the probability that
Intermediary $l$ get item $j\in[k]$ and $p_{l}$ corresponds to the price
Intermediary $l$ has to pay.

In this generalized model, the expected welfare is given by
$\mbox{Wel}(F)=\sum_{j=1}^{k}\eta_{j}\mathbb{E}[v^{(j,n)}]$.

Observe that the mechanism for the identical items case will not perform well
in the general setting. Intermediary-Proof Mechanism does not distinguish
between the case of uniform item weights and the case of one item with a high
weight and the rest with near-zero weights. In the latter case, we need to
charge close to $E[v^{(1,n)}]$ in order to compete with welfare, and this
could be much higher than $E[v^{(1,\lceil n/k\rceil)}]$, e.g. for $k=n$.

Condition on utility functions of Intermediaries: We observe that in order to
guarantee good welfare, higher-weight items need to cost more on a per-unit-
weight basis. Otherwise there will be no way to screen for higher value buyers
to assign them the higher-weight items. In addition, we need to ensure that
the utility functions are such that the intermediary will choose higher-value,
higher-cost items over lower-value, lower cost items in some cases. With this
in mind, we will impose the following, relatively strong, condition on the
utility functions of the Intermediaries for the purpose of this section. We
will assume that the utility function of Intermediary $l$ is such that it
tries to maximize the surplus among its buyers, i.e.,
$U_{l}(x_{l},p_{l};{\bm{v}}_{l})=V(x_{l},p_{l};{\bm{v}}_{l}):=\max_{z_{l}\in[k]^{\pi(l)}}\left\\{\sum_{i\in\pi(l),j\in[k]}v_{i}\eta_{l}z_{ijl}\bigg{|}\;\forall
l\;\sum_{i\in\pi(l)}z_{ijl}\leq x_{l,j}\right\\}-p_{l}.$ Here $x_{l,j}$ is the
fraction of item $j$ assigned to the intermediary and $z_{ijl}$ is the
fraction of item $j$ that the aggregator assigns to $i$. Let
$z^{*}_{l}(x_{l})$ be the $z_{l}$ that maximizes the above expression. Then
intermediary $l$ gets a utility of
$U_{l}(x_{l},p_{l};{\bm{v}}_{l})=\sum_{j=1}^{x_{l}}\sum_{j=1}^{k}v_{i}\eta_{j}z^{*}_{ijl}-p_{l}$.

As we argued in the previous paragraph, it is important to ensure that items
with higher weights are charged a higher price to ensure that we can screen
for buyers with a high value. However, we need to make sure that the balance
of prices is such that the high-value items are still bought with a reasonable
probability.

###  5.1 A robust mechanism for heterogeneous items

In this section, we give a sequential posted-price mechanism with non-uniform
per-item prices, and show that it gets a revenue that is a constant fraction
of the optimal welfare.

######  Definition 9 (Intermediary-Proof Mechanism for Heterogeneous Items).

Let $u_{j}=E[v^{(1,\lceil n/j\rceil)}]$. Define
${r}_{j}={r}_{j+1}+u_{j}\cdot(\eta_{j}-\eta_{j+1})$. Intermediary-Proof
Mechanism for Heterogeneous Items is a sequential posted-price mechanism that
offers the same menu of prices to each Intermediary, ordering the
Intermediaries in an arbitrary order. The menu consists of individual prices
for each item, with the price of item $j$ being $r_{j}$, and each Intermediary
allowed to buy any items it likes as long as the item is still available.

Note that $u_{j}$ and $r_{j}$ are decreasing in $j$. Thus the intermediary
pays more for positions with higher $\eta_{j}$.

We will show that due to the choice of $r_{j}$s, an intermediary representing
a buyer with value $v_{i}$ will purchase item $j$ if $v_{i}\in[u_{j},u_{j-1})$
(or another item with the same $\eta$ as $j$), since this item will generate
the most value through buyer $i$. Below we make this more formal for
intermediaries representing multiple buyers.

######  Definition 10 (Demand-set, $D(j)$).

For any buyer $i$, let $B(i)$ be the lowest-indexed item $j$ s.t. $v_{i}\geq
u_{j}$. Let demand-set of item $j$ be $D(j)=\\{i\in[n]|B(i)=j\\}$. Note that
$D$ is a partition of the set of buyers.

######  Lemma 5.

When an intermediary $l$ is offered the above menu of prices, one optimal
choice for the intermediary is to buy at least those available items $j$ for
which the demand-set $D(j)$ includes a buyer from $\pi(l)$.

###### Proof.

Recall that the intermediary is trying to select a subset of available items
that maximizes
$U_{l}(x_{l},p_{l};{\bm{v}}_{l})=\sum_{j=1}^{x_{l}}\sum_{j=1}^{k}v_{i}z^{*}_{ijl}-p_{l}$.
Contrary to the above claim, let the intermediary not buy an item $j$ even
though it has a buyer $i\in D(j)$. Let $z^{*}_{ijl}$ denote its allocation. If
$\sum_{j=1}^{k}z^{*}_{ijl}<1$, then the Intermediary can clearly increase its
utility by buying $j$ fractionally and assigning it to $i$. If
$\sum_{j=1}^{k}z^{*}_{ijl}=1$, then we will show that the Intermediary can buy
item $j$ instead of the one currently assigned to $i$, without any loss in
utility. Consider the case where buyer $i$ is assigned an item $j^{\prime}<j$.
Note that $v_{i}<u_{j^{\prime\prime}}$ for all $j^{\prime\prime}<j$. By the
construction of $r_{j}$’s,

$r_{j^{\prime}}-r_{j}=\sum_{k=j^{\prime}}^{j-1}u_{k}(\eta_{k}-\eta_{k+1})\geq
v_{i}(\eta_{j^{\prime}}-\eta_{j}).$

This inequality is strict when $\eta_{j}^{\prime}>\eta_{j}$. Rearranging we
get, $v_{i}\eta_{j}-r_{j}\geq v_{i}\eta_{j^{\prime}}-r_{j^{\prime}}$. The
intermediary may not necessarily allocate the new item to $i$. However in
allocating the item to somebody else the intermediary will further increase
its utility. Therefore, the Intermediary can swap item $j^{\prime}$ for $j$
without any loss in utility. This process can be continued for multiple items
until a whole unit $j$ is purchased.

Suppose instead that buyer $i$ is assigned an item $j^{\prime}>j$. For all
$j^{\prime\prime}\geq j$, $v_{i}>u_{j^{\prime\prime}}$. By the construction of
$r_{j}$s,

$r_{j}-r_{j^{\prime}}=\sum_{k=j}^{j^{\prime}-1}u_{k}(\eta_{k}-\eta_{k+1})\leq
v_{i}(\eta_{j}-\eta_{j^{\prime}}),$

and we conclude that the intermediary would prefer to swap $j$ instead of
$j^{\prime}$ ∎

Note that the Intermediary might buy more items than the ones specified in the
above lemma.

######  Theorem 2.

The Intermediary-Proof Mechanism for Heterogeneous Items obtains a revenue of
at least

$\left(1-e^{-c(\lambda)/2}\right)\cdot(1-\frac{1}{e})\mbox{Wel}(F).$

###### Proof.

Let $v$ be a random draw from $F$, we denote by $p_{j}=\mathbb{P}[u_{j-1}\geq
v\geq u_{j}]$.

From Lemma 5, which holds independently of the shape of the distribution $F$,
we know that if the valuation of at least one buyer lies in the range
$[u_{j-1},u_{j}]$, then item $j$ will be bought. Thus the probability that
item $j$ is sold is

$\displaystyle\mathbb{P}[\text{item }j\;\text{is sold}]$ $\displaystyle\geq
1-\mathbb{P}[\text{all values lie outside}[u_{j-1},u_{j}]$
$\displaystyle=1-(1-p_{j})^{n}$ $\displaystyle\geq 1-e^{-p_{j}\cdot n}$

Therefore the revenue obtained will be at least

$\displaystyle\min_{p_{j}}\sum_{j=1}^{k}r_{j}$
$\displaystyle\cdot(1-e^{-p_{j}\cdot n})$

Next, we note what we know about the $p_{j}$s. First, $0\leq p_{j}\leq 1$.
Further, Lemma 9, stated and proved in the appendix, shows that for $j\geq 1$
we have that

$n\cdot\sum_{t\leq j}p_{t}\geq\frac{j}{2}(1-\lambda)^{\frac{1}{\lambda}}.$

The above system can be written as a convex program

$\displaystyle\max\sum_{j=1}^{k}r_{j}$ $\displaystyle\cdot e^{-p_{j}\cdot n}$
(Primal) $\displaystyle n\cdot\left(\sum_{j=1}^{s}p_{j}\right)$
$\displaystyle\geq\frac{s}{2}(1-\lambda)^{\frac{1}{\lambda}}\qquad\text{ for
all }1\leq s\leq k$ $\displaystyle 0\leq p_{j}$ $\displaystyle\leq
1\qquad\qquad\qquad\text{ for all }1\leq j\leq k$

From Lemma 10, stated and proved in the appendix, we get that the minimum
value of the above program is achieved when
$p_{1}=\dots=p_{k}=\frac{1}{2n}(1-\lambda)^{\frac{1}{\lambda}}$. Plugging this
into the objective, the revenue obtained is at least

$\displaystyle(1-e^{-1/2(1-\lambda)^{\frac{1}{\lambda}}})\cdot\sum_{i=1}^{k}r_{i}$
$\displaystyle=(1-e^{-1/2(1-\lambda)^{\frac{1}{\lambda}}})\cdot\sum_{i=1}^{k}i\cdot(\eta_{i}-\eta_{i+1})\cdot
u_{i}$
$\displaystyle\geq(1-e^{-1/2(1-\lambda)^{\frac{1}{\lambda}}})\left(1-\frac{1}{e}\right)\cdot\sum_{i=1}^{k}(\eta_{i}-\eta_{i+1})\cdot\mathbb{E}[\sum_{j=1}^{i}v^{(j,n)}]$
collapsing the sum and noting that $\eta_{k+1}=0$,
$\displaystyle=(1-e^{-1/2(1-\lambda)^{\frac{1}{\lambda}}})\left(1-\frac{1}{e}\right)\cdot\sum_{i=1}^{k}\eta_{i}\cdot
v^{(i,n)}$

The latter quantity is the welfare and this concludes the proof. ∎

##  6 Open problems

In this section, we describe some open problems in designing mechanisms that
are robust to intermediaries.

Regular distributions: Does an intermediary-proof mechanism exist for the case
when the buyers’ valuations are regular? Recall regular distributions are
$\lambda$-regular with $\lambda=1$. This problem requires a different approach
than the one used in our work: with regular distributions, using welfare as
the revenue benchmark will not allow us to show a good approximation
ratio.161616For example, the welfare for the equal revenue distribution
$F(v)=1-\frac{1}{v}$ for $v\in[1,\infty)$, which is a regular distribution, is
unbounded.. Hence, the difficulty lies in finding an alternate
characterization of the optimal revenue that, ideally, does not go through
understanding the optimal mechanism for each demand structure, which is known
to be a hard problem (Daskalakis et al., 2014). Furthermore, the following
lemma shows that a simple mechanism that posts a price per item cannot achieve
a constant approximation ratio.

######  Lemma 6.

There exists a regular distribution $\mathcal{F}$ such that with $n$ items to
sell and $n$ buyers represented by an intermediary with values drawn i.i.d.
from distribution $\mathcal{F}$, the optimal revenue from item pricing is
$\Omega(\ln n)$ worse than the optimal revenue.

The proof of Lemma 6 considers a distribution closely related to the equal
revenue distribution. On the one hand, we show that the optimal item pricing
yields at most $O(n)$ in revenue irrespective of the demand structure. While,
on the other hand, using concentration arguments we show that a bundle price
of $\Theta(n\log n)$ will be accepted by a monopsony intermediary with a
constant probability. We defer the formal proof to the appendix.171717If we
restrict the demand structures to be either a monopsony (a single intermediary
representing all buyers) or the competition case (each buyer represents
themselves), we can obtain a $2$-approximation mechanism by uniformly randomly
choosing between item prices and a single bundle price.

Non-identical buyer valuations, more general heterogeneous valuations: Another
natural problem is to design an intermediary-proof mechanism when buyers can
have non-identical and/or general (non-separable) item-specific valuations for
the items. We expect that the intermediary-proof mechanism for the non-
identical buyers setting would require personalized pricing for each buyer
and, when there are complementarities between the goods, pricing for bundles
would also be needed.

Characterization of the optimal mechanism for the monopsony case: Another
interesting problem comes from the connection between an intermediary
representing multiple buyers and a single buyer with valuations for multiple
items. More precisely, a surplus-maximizing intermediary can be interpreted as
a single buyer whose valuations for the $k$ items correspond to the
$k$-highest valuations of the buyers the intermediary represents. Thus, our
intermediary framework microfounds a natural type of correlation between the
buyer’s valuations for the multi-item setting. It would be interesting to
characterize the optimal mechanism for this natural multi-item setting: single
buyer whose valuations for the $k$ objects are drawn from the $k$-highest
order statistics of $n$ i.i.d. draws. This question has been partially
answered for two extreme cases: for $k=1$ the optimal mechanism is a simple
posted price (Myerson, 1981), while the case of $k=n$ is known to be a hard
problem (Daskalakis et al., 2014). It would be interesting to study how the
complexity of the optimal mechanism changes as a function of $k$.

## References

  * Alaei et al. [2012] Saeed Alaei, Hu Fu, Nima Haghpanah, Jason Hartline, and Azarakhsh Malekian.  Bayesian optimal auctions via multi- to single-agent reduction.  In _Proceedings of the 13th ACM Conference on Electronic Commerce_ , EC ’12, page 17, New York, NY, USA, 2012. Association for Computing Machinery.  ISBN 9781450314152.  doi: 10.1145/2229012.2229017.
  * Allouah and Besbes [2017] Amine Allouah and Omar Besbes.  Auctions in the online display advertising chain: A case for independent campaign management.  Technical Report 17-60, Columbia Business School Research Paper, 2017\.  URL https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2919665.
  * Babaioff et al. [2020] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg.  A simple and approximately optimal mechanism for an additive buyer.  _J. ACM_ , 67(4), jun 2020.  ISSN 0004-5411.  doi: 10.1145/3398745.  URL https://doi.org/10.1145/3398745.
  * Balseiro and Candogan [2017] Santiago R Balseiro and Ozan Candogan.  Optimal contracts for intermediaries in online advertising.  _Operations Research_ , 65(4):878–896, 2017.  doi: 10.1287/opre.2017.1618.
  * Balseiro et al. [2019] Santiago R. Balseiro, Ozan Candogan, and Huseyin Gurkan.  _Intermediation in Online Advertising_ , pages 505–528.  Springer International Publishing, Cham, 2019.  ISBN 978-3-030-01863-4.  doi: 10.1007/978-3-030-01863-4˙21.
  * Barlow et al. [1963] Richard E. Barlow, Albert W. Marshall, and Frank Proschan.  Properties of probability distributions with monotone hazard rate.  _The Annals of Mathematical Statistics_ , 34(2):375–389, 1963.  ISSN 00034851.  URL http://www.jstor.org/stable/2238381.
  * Bergemann et al. [2017] Dirk Bergemann, Benjamin Brooks, and Stephen Morris.  Selling to intermediaries: Optimal auction design in a common value model.  Technical report, Cowles Foundation for Research in Economics, Yale University, 2017.  URL https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3018883.
  * Briest et al. [2010] Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg.  Pricing randomized allocations.  In Moses Charikar, editor, _Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010_ , pages 585–597. SIAM, 2010.  doi: 10.1137/1.9781611973075.49.  URL https://doi.org/10.1137/1.9781611973075.49.
  * Broniatowski and Weber [1998] Michel Broniatowski and Michel Weber.  Strong laws for sums of extreme values.  _Theory of Probability & Its Applications_, 42(3):395–404, 1998.  doi: 10.1137/S0040585X97976283.
  * Cai and Zhao [2017] Yang Cai and Mingfei Zhao.  Simple mechanisms for subadditive buyers via duality.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017_ , pages 170–183. ACM, 2017.  doi: 10.1145/3055399.3055465.  URL https://doi.org/10.1145/3055399.3055465.
  * Cai et al. [2012a] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg.  An algorithmic characterization of multi-dimensional mechanisms.  In Howard J. Karloff and Toniann Pitassi, editors, _Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012_ , pages 459–478. ACM, 2012a.  doi: 10.1145/2213977.2214021.  URL https://doi.org/10.1145/2213977.2214021.
  * Cai et al. [2012b] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg.  Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization.  In _53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012_ , pages 130–139. IEEE Computer Society, 2012b.  doi: 10.1109/FOCS.2012.88.  URL https://doi.org/10.1109/FOCS.2012.88.
  * Cai et al. [2016] Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg.  A duality based unified approach to bayesian mechanism design.  In Daniel Wichs and Yishay Mansour, editors, _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , pages 926–939. ACM, 2016.  doi: 10.1145/2897518.2897645.  URL https://doi.org/10.1145/2897518.2897645.
  * Carroll [2017] Gabriel Carroll.  Robustness and separation in multidimensional screening.  _Econometrica_ , 85(2):453–488, 2017.  doi: 10.3982/ECTA14165.
  * Chawla and Miller [2016] Shuchi Chawla and J. Benjamin Miller.  Mechanism design for subadditive agents via an ex ante relaxation.  In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, _Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016_ , pages 579–596. ACM, 2016.  doi: 10.1145/2940716.2940756.  URL https://doi.org/10.1145/2940716.2940756.
  * Chawla et al. [2007] Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg.  Algorithmic pricing via virtual valuations.  In Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick, editors, _Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007_ , pages 243–251. ACM, 2007.  doi: 10.1145/1250910.1250946.  URL https://doi.org/10.1145/1250910.1250946.
  * Chawla et al. [2010a] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan.  Multi-parameter mechanism design and sequential posted pricing.  In Leonard J. Schulman, editor, _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ , pages 311–320. ACM, 2010a.  doi: 10.1145/1806689.1806733.  URL https://doi.org/10.1145/1806689.1806733.
  * Chawla et al. [2010b] Shuchi Chawla, David L. Malec, and Balasubramanian Sivan.  The power of randomness in bayesian optimal mechanism design.  In David C. Parkes, Chrysanthos Dellarocas, and Moshe Tennenholtz, editors, _Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010_ , pages 149–158. ACM, 2010b.  doi: 10.1145/1807342.1807366.  URL https://doi.org/10.1145/1807342.1807366.
  * Che and Kim [2006] Yeon-Koo Che and Jinwoo Kim.  Robustly collusion-proof implementation.  _Econometrica_ , 74(4):1063–1107, 2006.  doi: 10.1111/j.1468-0262.2006.00694.x.
  * Che and Kim [2009] Yeon-Koo Che and Jinwoo Kim.  Optimal collusion-proof auctions.  _Journal of Economic Theory_ , 144(2):565–603, 2009.  ISSN 0022-0531.  doi: 10.1016/j.jet.2008.07.004.
  * Che et al. [2018] Yeon-Koo Che, Daniele Condorelli, and Jinwoo Kim.  Weak cartels and collusion-proof auctions.  _Journal of Economic Theory_ , 178:398–435, 2018.  ISSN 0022-0531.  doi: 10.1016/j.jet.2018.09.005.
  * Choi et al. [2020] Hana Choi, Carl F. Mela, Santiago R. Balseiro, and Adam Leary.  Online Display Advertising Markets: A Literature Review and Future Directions.  _Information Systems Research_ , 31(2):556–575, June 2020.  doi: 10.1287/isre.2019.0902.  URL https://ideas.repec.org/a/inm/orisre/v31y2020i2p556-575.html.
  * Csorgo [1989] Sandor Csorgo.  Limit theorems for sums of order statistics.  Technical report, North Carolina State University. Dept. of Statistics, 1989.  URL https://repository.lib.ncsu.edu/bitstream/handle/1840.4/3676/ISMS_1989_1795.pdf?sequence=1.
  * Daskalakis et al. [2014] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos.  The complexity of optimal mechanism design.  In Chandra Chekuri, editor, _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014_ , pages 1302–1318. SIAM, 2014.  doi: 10.1137/1.9781611973402.96.  URL https://doi.org/10.1137/1.9781611973402.96.
  * Daskalakis et al. [2017] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos.  Strong duality for a multiple-good monopolist.  _Econometrica_ , 85(3):735–767, 2017.  doi: 10.3982/ECTA12618.
  * Duffie et al. [2005] Darrell Duffie, Nicolae Gârleanu, and Lasse Heje Pedersen.  Over-the-counter markets.  _Econometrica_ , 73(6):1815–1847, 2005.  doi: 10.1111/j.1468-0262.2005.00639.x.
  * Feldman et al. [2010] Jon Feldman, Vahab Mirrokni, S Muthukrishnan, and Mallesh M Pai.  Auctions with intermediaries.  In _Proceedings of the 11th ACM conference on Electronic commerce_ , pages 23–32, 2010.  doi: 10.1145/1807342.1807346.
  * Goldberg and Hartline [2005] Andrew V. Goldberg and Jason D. Hartline.  Collusion-resistant mechanisms for single-parameter agents.  In _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’05, page 620–629, USA, 2005. Society for Industrial and Applied Mathematics.  ISBN 0898715857.
  * Hart and Nisan [2013] Sergiu Hart and Noam Nisan.  The menu-size complexity of auctions.  In Michael J. Kearns, R. Preston McAfee, and Éva Tardos, editors, _Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013_ , pages 565–566. ACM, 2013.  doi: 10.1145/2492002.2482544.  URL https://doi.org/10.1145/2492002.2482544.
  * Hart and Nisan [2017] Sergiu Hart and Noam Nisan.  Approximate revenue maximization with multiple items.  _Journal of Economic Theory_ , 172:313–347, 2017.  doi: 10.1016/j.jet.2017.09.001.
  * Hart and Reny [2015] Sergiu Hart and Philip J. Reny.  Maximal revenue with multiple goods: Nonmonotonicity and other observations.  _Theoretical Economics_ , 10(3):893–922, 2015\.  doi: 10.3982/TE1517.
  * Hummel et al. [2016] Patrick Hummel, R Preston McAfee, and Sergei Vassilvitskii.  Incentivizing advertiser networks to submit multiple bids.  _International Journal of Game Theory_ , 45(4):1031–1052, 2016.
  * Kleinberg and Weinberg [2012] Robert Kleinberg and S. Matthew Weinberg.  Matroid prophet inequalities.  In Howard J. Karloff and Toniann Pitassi, editors, _Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012_ , pages 123–136. ACM, 2012.  doi: 10.1145/2213977.2213991.  URL https://doi.org/10.1145/2213977.2213991.
  * Kleinberg and Yuan [2013] Robert Kleinberg and Yang Yuan.  On the ratio of revenue to welfare in single-parameter mechanism design.  In _Proceedings of the Fourteenth ACM Conference on Electronic Commerce_ , EC ’13, page 589–602, New York, NY, USA, 2013. Association for Computing Machinery.  ISBN 9781450319621.  doi: 10.1145/2492002.2482584.
  * Krishna [2009] Vijay Krishna.  _Auction Theory_.  Number 9780123745071 in Elsevier Monographs. Elsevier, December 2009.  ISBN ARRAY(0x5667d1a0).  URL https://ideas.repec.org/b/eee/monogr/9780123745071.html.
  * Li [2017] Shengwu Li.  Obviously strategy-proof mechanisms.  _American Economic Review_ , 107(11):3257–87, November 2017.  doi: 10.1257/aer.20160425.
  * Li and Yao [2013] Xinye Li and Andrew Chi-Chih Yao.  On revenue maximization for selling multiple independently distributed items.  _Proc. Natl. Acad. Sci. USA_ , 110(28):11232–11237, 2013.  doi: 10.1073/pnas.1309533110.  URL https://doi.org/10.1073/pnas.1309533110.
  * Manelli and Vincent [2006] Alejandro M. Manelli and Daniel R. Vincent.  Bundling as an optimal selling mechanism for a multiple-good monopolist.  _J. Econ. Theory_ , 127(1):1–35, 2006.  doi: 10.1016/j.jet.2005.08.007.  URL https://doi.org/10.1016/j.jet.2005.08.007.
  * McAfee et al. [1989] R. Preston McAfee, John McMillan, and Michael D. Whinston.  Multiproduct Monopoly, Commodity Bundling, and Correlation of Values*.  _The Quarterly Journal of Economics_ , 104(2):371–383, 05 1989.  ISSN 0033-5533.  doi: 10.2307/2937852.
  * Milgrom and Segal [2002] Paul Milgrom and Ilya Segal.  Envelope theorems for arbitrary choice sets.  _Econometrica_ , 70(2):583–601, 2002.
  * Muthukrishnan [2009] S. Muthukrishnan.  Ad exchanges: Research issues.  In Stefano Leonardi, editor, _Internet and Network Economics_ , pages 1–12, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.  ISBN 978-3-642-10841-9.  doi: 10.1007/978-3-642-10841-9˙1.
  * Myerson [1981] Roger B Myerson.  Optimal auction design.  _Mathematics of operations research_ , 6(1):58–73, 1981.  doi: 10.1287/moor.6.1.58.
  * Pavlov [2008] Gregory Pavlov.  Auction design in the presence of collusion.  _Theoretical Economics_ , 3(3):383–429, 2008\.  doi: 1555-7561/20080383.
  * Rényi [1953] A. Rényi.  On the theory of order statistics.  _Acta Mathematica Academiae Scientiarum Hungaricae_ , 4:191–231, 1953.  doi: 10.1007/BF02127580.
  * Rubinstein and Weinberg [2015] Aviad Rubinstein and S. Matthew Weinberg.  Simple mechanisms for a subadditive buyer and applications to revenue monotonicity.  In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, _Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015_ , pages 377–394. ACM, 2015.  doi: 10.1145/2764468.2764510.  URL https://doi.org/10.1145/2764468.2764510.
  * Russell and Seo [1989] William R Russell and Tae Kun Seo.  Representative sets for stochastic dominance rules.  In _Studies in the Economics of Uncertainty_ , pages 59–76. Springer, 1989.
  * Schweizer and Szech [2019] Nikolaus Schweizer and Nora Szech.  Performance bounds for optimal sales mechanisms beyond the monotone hazard rate condition.  _Journal of Mathematical Economics_ , 82:202–213, 2019\.  ISSN 0304-4068.  doi: 10.1016/j.jmateco.2019.02.007.
  * Stavrogiannis et al. [2013] Lampros C. Stavrogiannis, Enrico H. Gerding, and Maria Polukarov.  Competing intermediary auctions.  In _Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems_ , AAMAS ’13, page 667–674, New York, NY, USA, 2013. Association for Computing Machinery.  ISBN 9781450319935.
  * Thanassoulis [2004] John Thanassoulis.  Haggling over substitutes.  _Journal of Economic Theory_ , 117(2):217–245, 2004.  ISSN 0022-0531.  doi: https://doi.org/10.1016/j.jet.2003.09.002.
  * Yao [2015] Andrew Chi-Chih Yao.  An _n_ -to-1 bidder reduction for multi-item auctions and its applications.  In Piotr Indyk, editor, _Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015_ , pages 92–109. SIAM, 2015.  doi: 10.1137/1.9781611973730.8.  URL https://doi.org/10.1137/1.9781611973730.8.

##  Appendix A Proof of 1

For the remaining proofs, we will use the following key property of
$\lambda$-regular distributions.

######  Proposition 6 (Proposition 1, Schweizer and Szech [2019]).

A distribution $F$ is $\lambda$-regular if and only if an increasing convex
function $H_{\lambda}$ exists such that
$1-F(v)=\Gamma_{\lambda}(H_{\lambda}(v))$ where
$\Gamma_{\lambda}(v)=(1+\lambda v)^{-\frac{1}{\lambda}}$. Moreover,
$H_{\lambda}(v)=\int_{0}^{v}r_{\lambda}(z)dz$ where
$r_{\lambda}(v)=\frac{1}{(1-F(v))^{\lambda}}h_{F}(v)$.

See 1

###### Proof of 1.

Given $n$ i.i.d random variables drawn according to $F$, the distribution of
the first order statistic is given by $F^{n}(x)$. Thus, we want to show that
if $F$ is $\lambda$\- regular then $F^{n}$ is $\lambda$-regular. From
Schweizer and Szech [2019] Proposition 1, this is equivalent to showing that
$g_{\lambda}\circ F^{n}(x)$ is a convex function where
$g_{\lambda}(x)=\frac{1}{\lambda}\left(\frac{1}{(1-x)^{\lambda}}-1\right)$.

Assume first that $F$ is twice-differentiable (at the end of the proof, we
show how to remove this assumption). Under the differentiablity assumption,
the previous condition turns to $(g_{\lambda}\circ F^{n})^{\prime\prime}\geq
0$.

Because,

$\displaystyle\frac{1}{n}(g_{\lambda}\circ F^{n})^{\prime\prime}$
$\displaystyle=f(x)^{2}\left(g_{\lambda}^{\prime\prime}(F^{n}(x))nF^{n-1}(x)^{2}+g_{\lambda}^{\prime}(F^{n}(x))(n-1)F^{n-2}(x)\right)$
$\displaystyle\quad+g_{\lambda}^{\prime}(F^{n}(x))F^{n-1}(x)f^{\prime}(x),$
$\displaystyle g_{\lambda}^{\prime}(x)$
$\displaystyle=\frac{1}{(1-x)^{1+\lambda}},$ $\displaystyle
g_{\lambda}^{\prime\prime}(x)$ $\displaystyle=\frac{1+\lambda}{1-x}\cdot
g_{\lambda}^{\prime}(x),$

we have that $g_{\lambda}\circ F^{n}$ is convex if and only if

$g_{\lambda}^{\prime}(F^{n}(x))\cdot
F^{n-2}(x)\cdot\left[f(x)^{2}\left(\frac{1+\lambda}{1-F^{n}(x)}nF^{n}(x)+(n-1)\right)+F(x)f^{\prime}(x)\right]\geq
0.$

Using Lemma 7, whose proof is below, we obtain that

$\displaystyle\frac{1}{n}(g_{\lambda}\circ F^{n})^{\prime\prime}$
$\displaystyle\geq g_{\lambda}^{\prime}(F^{n}(x))\cdot
F^{n-2}(x)\cdot\left[\frac{1+\lambda}{1-F(x)}F(x)f^{2}(x)+F(x)f^{\prime}(x)\right]$
$\displaystyle=F^{n-1}(x)\cdot
g_{\lambda}^{\prime}(F^{n}(x))\cdot\left[\frac{1+\lambda}{1-F(x)}f^{2}(x)+f^{\prime}(x)\right]$
$\displaystyle=F^{n-1}(x)\cdot
g_{\lambda}^{\prime}(F^{n}(x))\cdot\left[\frac{1+\lambda}{1-F(x)}f^{2}(x)+f^{\prime}(x)\right].$

Observe that in the last expression, the first term is trivially positive; the
second term is positive since $g_{\lambda}^{\prime}>0$; the third term is
positive because $F$ is $\lambda$-regular.181818A distribution twice-
differentiable $F$ is $\lambda$-regular if and only if $(1-F(x))^{-\lambda}$
is convex, which is equivalent to
$\frac{1+\lambda}{1-F(x)}f^{2}(x)+f^{\prime}(x)\geq 0$ for every $x$.
Therefore, $g_{\lambda}\circ F^{n}$ is convex which implies that $F^{n}$ is a
$\lambda$-regular distribution.

To finish the proof we need to tackle the case where $F$ is not necessarily
twice-differentiable. Lemma 8, which is proven below, guarantees a sequence of
distributions $(F_{t})_{t\geq 0}$ that are $\lambda$-regular and twice-
differentiable satisfying that $F_{t}\to F$ uniformly on compact sets. Because
$F_{t}$ are twice-differentiable, we have that $g_{\lambda}\circ F_{t}^{n}$ is
convex. Hence, taking the limit as $t\to\infty$, we conclude that
$g_{\lambda}\circ F^{n}$ is convex. Therefore, $F^{n}$ is a $\lambda$-regular
distribution. ∎

######  Lemma 7.

Given a real $F\in[0,1]$ and $\lambda\in[0,1]$, the following inequality holds

$\frac{1+\lambda}{1-F^{n}}nF^{n}+(n-1)\geq\frac{1+\lambda}{1-F}F$ (3)

for every $n\in\mathbb{N}$.

###### Proof.

First, we assert that it is sufficient to show Inequality (3) for the case
$\lambda=1$. To see this, observe that Inequality (3) is equivalent to

$\frac{nF^{n}}{1-F^{n}}+\frac{n-1}{1+\lambda}\geq\frac{F}{1-F}.$

We conclude by observing that the lowest value of the left-hand-side happens
when $\lambda=1$ while the right-hand-side is independent of $\lambda$.

Next, consider the function $h(F)=\frac{nF^{n}}{{1-F^{n}}}-\frac{F}{1-F}$.
From the previous paragraph, we need to show that $h(F)\geq-\frac{n-1}{2}$. To
this extent, we show that $h$ is decreasing and that $\lim_{F\to
1}h(F)=-\frac{n-1}{2}$.

To tackle that $h$ is decreasing, observe that

$\displaystyle h^{\prime}(F)$
$\displaystyle=\frac{n^{2}F^{n-1}}{1-F^{n}}+\frac{n^{2}F^{2n-1}}{(1-F^{n})^{2}}-\frac{1}{(1-F)}-\frac{F}{(1-F)^{2}}$
$\displaystyle=\frac{n^{2}F^{n-1}}{(1-F^{n})^{2}}-\frac{1}{(1-F)^{2}}.$

Thus,

$(1-F)^{2}h^{\prime}(F)=\frac{n^{2}F^{n-1}}{(\sum_{i=0}^{n-1}F^{i})^{2}}-1.$

Because $F^{i}\geq F^{n-1}$ for $i\leq n-1$, we conclude that
$(1-F)^{2}h^{\prime}(F)\leq 0$. Therefore, $h$ is decreasing on $[0,1]$.

For the last step of the proof, observe that

$\displaystyle\lim_{F\to 1}h(F)$ $\displaystyle=\lim_{F\to
1}\frac{nF^{n}}{1-F^{n}}-\frac{F}{1-F}$ $\displaystyle=\lim_{F\to
1}\frac{nF^{n}(1-F)-(1-F^{n})\cdot F}{(1-F^{n})(1-F)}$ Applying L’Hopital’s
rule twice, we get $\displaystyle\lim_{F\to 1}h(F)$
$\displaystyle=\frac{n^{2}(n-1)-(n^{2}-1)\cdot n}{n(n+1)-n+1}$
$\displaystyle=-\frac{n-1}{2}.$

∎

######  Lemma 8.

Given a $\lambda$-regular distribution $F$, a sequence of distributions
$(F_{t})_{t\geq 0}$ exists that are $\lambda$-regular and twice-differentiable
such that $F_{t}\to F$ uniformly on compact sets.

###### Proof.

Proposition 6 tells us that
$1-F(v)=\Gamma_{\lambda}(H_{\lambda}(r_{\lambda}(v)))$ with $H_{v}$ convex and
increasing. Russell and Seo [1989] shows that a sequence of infinite
differentiable convex increasing functions $(H_{t}(v))_{t\geq 0}$ exists such
that $H_{t}\to H_{\lambda}$ uniformly on compact sets. Furthermore, we can
construct $H_{t}$ so that $H_{t}(0)=H_{\lambda}(0)=0$ and
$\lim_{v\to\infty}H_{t}(v)=\infty$. Hence, the distribution
$F_{t}(v)=1-\Gamma_{\lambda}(H_{t}(v))$ is well-defined, twice-differentiable,
satisfies that $F_{t}\to F$ uniformly on compact sets ($\Gamma_{\lambda}$ is a
continuous function), and from Proposition 6 is $\lambda$-regular. ∎

##  Appendix B Missing proofs from Section 2

See 1

###### Proof of Lemma 1.

Given a BIC $({\bm{x}},{\bm{p}})$, the IR constraint and the Condition 2 on
the utility function $U_{l}$ imply that
$\mathbb{E}[p_{l}({\bm{v}}_{l},{\bm{v}}_{-l})|{\bm{v}}_{l}]\leq\mathbb{E}[\sum_{i\in\pi(l)}x_{i}({\bm{v}}_{i},{\bm{v}}_{-i})v_{i}]$.
Therefore,

$\mbox{Rev}(F,m,\pi;({\bm{x}},{\bm{p}}))=\sum_{l\in[m]}\mathbb{E}[p_{l}({\bm{v}})]\leq\sum_{l\in[m]}\mathbb{E}\left[\sum_{i=1}^{x_{l}}v^{(i,l)}\right]\leq\mbox{Wel}(F).$

We conclude that $\mbox{Rev}(F,m,\pi)\leq\mbox{Wel}(F)$. ∎

##  Appendix C Missing proofs from Section 3

See 1

###### Proof of Proposition 1.

We show a more general result which has Proposition 1 as a specific case. We
claim that the profit-maximizing mechanism for selling $k$ objects, each
having a production cost $c$, to $n$ bidders consists on setting a
$(k+1)$-price auction with reserve price $\phi^{-1}_{F}(c)$.

The proof consists of adapting the technique used in Myerson [1981] for this
particular setting. First, let $U_{j}(x_{j},p_{j}|v_{j})=v_{j}x_{j}-p_{j}$ the
bidder’s utility. Given $({\bm{x}},{\bm{p}})$ a direct mechanism and we denote
by
$W_{j}(v_{j})=\mathbb{E}[U_{j}(x_{j}(v_{j},{\bm{v}}_{-j}),p_{j}(v_{j},{\bm{v}}_{-j}))|v_{j}]$.
The quasi-linearity of $U_{j}$ implies that the incentive compatibility of
$({\bm{x}},{\bm{p}})$ is equivalent to (i) that
$\chi^{x_{j}}_{j}(v_{j})=\mathbb{E}_{{\bm{v}}_{-j}}[x_{j}(v_{j},{\bm{v}}_{-j})]$
is non-decreasing, and
$W_{j}(v_{j})=W_{j}(\underline{v})+\int_{\underline{v}}^{v_{j}}\chi_{j}(z)dz$
[Milgrom and Segal, 2002]. The (IR) constraint implies that
$W_{j}(\underline{v})=0$. Furthermore, the equivalence result pins-down the
price $p_{j}$ as function of the allocation rule $x_{j}$ by :
$\mathbb{E}_{{\bm{v}}_{-j}}[p_{j}(v_{j},{\bm{v}}_{-j})]=v_{j}\chi_{j}(v_{j})-W_{j}(v_{j})$.

Using the previous characterization, the seller’s problem turns to

$\displaystyle\max_{{\bm{x}}:[\underline{v},\overline{v}]^{n}\to[0,1]^{n}}$
$\displaystyle\quad\sum_{j\in[n]}\mathbb{E}_{v_{j}}\left[v_{j}\chi^{x_{j}}_{j}(v_{j})-V_{j}(v_{j})-c\chi^{x_{j}}_{j}(v_{j})\right]=\mathbb{E}_{{\bm{v}}}\bigg{[}\sum_{j\in[n]}(\phi_{F}(v_{j})-c)x_{j}({\bm{v}})\bigg{]}$
subject to $\displaystyle\quad\chi^{x_{j}}_{j}\mbox{is non-decreasing for
every }j\in[n]$ $\displaystyle\quad\sum_{j\in[n]}x_{j}({\bm{v}})\leq k,$

where the equality in the optimization problem comes from integration by
parts.

Solving the relaxed problem without taking into account the monotonicity
constraint, we obtain that the solution is

$x_{j}^{*}({\bm{v}})=\begin{cases}1&\mbox{ if }v_{j}\geq v^{(k)}\mbox{ and
}\phi_{F}(v_{j})\geq c\\\ 0&\mbox{ otherwise}\end{cases}.$

Accordingly,
$p^{*}_{j}({\bm{v}})=x_{j}^{*}({\bm{v}})\max\\{v^{(k+1)},\phi^{-1}_{F}(c)\\}$
is an optimal pricing scheme.

Finally, using that $F$ has the MHR property we conclude that
$\chi_{j}^{x^{*}_{j}}$ is non-decreasing. Therefore,
$({\bm{x}}^{*},{\bm{p}}^{*})$ is the revenue-maximizing mechanism. ∎

See 2

###### Proof.

Let $k=1$. First note that, the revenue of the optimal mechanism with
monopsony ($\mbox{Rev}^{M}$) is at least as much as the mechanism that sells
the item with a posted price $p=\mathbb{E}[v^{(1,n)}]$. Hence, we obtain that

$\mbox{Rev}^{M}\geq\mathbb{E}[v^{(1,n)}]\;\mathbb{P}[v^{(1,n)}\geq\mathbb{E}[v^{(1,n)}]]\geq\frac{1}{e}\mathbb{E}[v^{(1,n)}],$

where the second inequality is due to Lemma 2. On the other hand, as noted in
Proposition 1 the optimal competition mechanism is a second-price auction with
a reserve price. In the monopsony case, we have that in every Bayes Nash
Equilibrium the intermediary will only buy the item, for a price $r$, when
$v^{(1,n)}\geq r$. Thus the revenue of the optimal competition mechanism in a
market with a monopsony demand structure is
$\mbox{Rev}^{M}({\bm{x}}^{C},{\bm{p}}^{C})=r\mathbb{P}[v^{(1,n)}\geq r]\leq
r$.

Next, let $F$ be standard exponential distribution with $f(x)=exp(-x)$ and
$F(x)=1-exp(-x)$. The hazard rate $h_{F}(z)=1$ which implies that the reserve
price is $r=1$ (independent of $n$). For exponential distributions,
$\mathbb{E}[v^{(1,n)}]=\sum_{j=1}^{n}{\frac{1}{n-j+1}}=\mathcal{H}(n)$ Rényi
[1953]. Thus $\lim_{n\to\infty}\mathbb{E}[v^{(1,n)}]=\infty$, and we conclude
that
$\lim_{n\to\infty}\frac{\mbox{Rev}^{M}({\bm{x}}^{C},{\bm{p}}^{C})}{\mbox{Rev}^{M}}=0$.
∎

See 3

###### Proof.

The revenue of setting the optimal pricing $p_{B}$ is greater or equal than
the revenue of selling the bundle at price
$\mathbb{E}[\sum_{j=1}^{k}v^{(j,n)}]$. Because $G$ satisfies the MHR property
(combine 1 with the fact MHR distributions are closed under summation Barlow
et al. [1963]), Lemma 2 implies that

$\mathbb{E}\left[\sum_{j=1}^{k}v^{(j,n)}\right]\cdot\mathbb{P}\left[\sum_{j=1}^{k}v^{(j,n)}\geq\mathbb{E}\left[\sum_{j=1}^{k}v^{(j,n)}\right]\right]\geq\frac{1}{e}\;\mathbb{E}\left[\sum_{j=1}^{k}v^{(j,n)}\right]=\frac{1}{e}\;\mbox{Wel}(F).$

Using Lemma 1, we conclude that pricing the bundle at $p_{B}$ obtains a
revenue of at least $\frac{1}{e}$ of RevM.

For $k=n$, the Law of Large Numbers 191919Since the distribution F is MHR, the
moments are bounded and law of large numbers can be applied [Barlow et al.,
1963]. implies that $\lim_{n\to\infty}\mathbb{P}[\sum_{j=1}^{n}v^{(j,n)}\geq
p_{B}^{\epsilon}]=1$ for every $\epsilon>0$. Hence,
$\lim_{n\to\infty}\frac{p_{B}^{\epsilon}\mathbb{P}[\sum_{j=1}^{n}v^{(j,n)}\geq
p_{B}^{\epsilon}]}{\mbox{Wel}(F)}=1-\frac{\epsilon}{\mathbb{E}[v]}.$ We
conclude by taking $\epsilon\to 0$. ∎

See 1

###### Proof.

Consider the case $k=n$. From Proposition 3 we have that the bundle price
$p_{B}^{\epsilon}$ is asymptotically optimal. Hence, the revenue of the bundle
is approximately $n\mathbb{E}[v]$, while the revenue of Competition is
$nr\mathbb{P}[v\geq r]$. From Markov Inequality, we know that
$\mathbb{E}[v]=\mathbb{E}[v|v\geq r]\mathbb{P}[v\geq
r]+\mathbb{E}[v|v<r]+\mathbb{P}[v<r]\geq r\mathbb{P}[v\geq r]$. Further the
last inequality is strict as long as $\mathbb{P}[v>r]>0$ or
$\mathbb{E}[v|v<r]>0$ and $\mathbb{P}(v<r)>0$, which is true for distribution
with at least two non-zero points in its support. Thus, the revenue of the
bundle is more than the revenue from Competition. ∎

See 4

###### Proof.

For the competition case the probability of selling the bundle is equivalent
to the probability that the highest valuation bidder would like to get the
bundle. Hence,
$Rev^{C}({\bm{x}}^{B},{\bm{p}}^{B})=p^{\epsilon}_{B}\mathbb{P}[v^{(1,n)}\geq
p^{\epsilon}_{B}]\leq n\mathbb{E}[v]\mathbb{P}[v^{(1,n)}\geq
n(\mathbb{E}[v]-\epsilon)]$. On the other hand, Rev${}^{C}=nr\mathbb{P}[v\geq
r]$. Therefore, we have that

$\frac{\mbox{Rev}^{C}({\bm{x}}^{B},{\bm{p}}^{B})}{\mbox{Rev}^{C}}\leq\frac{\mathbb{E}[v]\cdot\mathbb{P}[v^{(1,n)}\geq
n(\mathbb{E}[v]-\epsilon)]}{r\mathbb{P}[v\geq r]}\leq\frac{\mathbb{E}[v]\cdot
E[v^{(1,n)}]}{n(\mathbb{E}[v]-\epsilon)\cdot rP[v\geq r]},$

where the second inequality comes from Markov Inequality. We conclude that for
a bounded distribution $F$,
$\lim_{n\to\infty}\frac{\mbox{Rev}^{C}({\bm{x}}^{B},{\bm{p}}^{B})}{\mbox{Rev}^{C}}=0$.
∎

##  Appendix D Missing proofs from Section 4

See 4

###### Proof of Lemma 4.

The optimal behavior of the monopolist, discussed in Lemma 3, implies that
what we just need to show that $\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq
p]\geq(1-\lambda)^{\frac{1}{\lambda}}$.

From Bayes’ rule we have that

$\displaystyle\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq p]$
$\displaystyle=\frac{\mathbb{P}[\phi_{F}(v_{i})\geq p,v_{i}\geq
p]}{\mathbb{P}[v_{i}\geq p]}=\frac{\mathbb{P}[\phi_{F}(v_{i})\geq
p]}{\mathbb{P}[v_{i}\geq p]}$
$\displaystyle=\frac{1-F(\phi^{-1}_{F}(p))}{1-F(p)},$

where the second equality follows from the fact that
$\phi_{F}(v_{i})=v_{i}-(1-F(v_{i}))/f(v_{i})\leq v_{i}$.

Because $F$ is $\lambda$-regular, Proposition 6 implies that that
$1-F(v)=\Gamma_{\lambda}(H_{\lambda}(v))$ where
$\Gamma_{\lambda}(v)=(1+\lambda v)^{-\frac{1}{\lambda}}$ and that
$H_{\lambda}(v)=\int_{0}^{v}r_{\lambda}(z)dz$ where
$r_{\lambda}(v)=\frac{1}{(1-F(v))^{\lambda}}h_{F}(v)$. Therefore,

$\displaystyle\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq p]$
$\displaystyle=\frac{\Gamma_{\lambda}(H_{\lambda}(\phi^{-1}_{F}(p)))}{\Gamma_{\lambda}(H_{\lambda}(p))}.$
(4)

To tackle the right-hand-side of the above expression, we derive the following
inequalities.

First, because $F$ is $\lambda$-regular, we have that $H_{\lambda}$ is convex
with $H_{\lambda}^{\prime}(v)=r_{\lambda}(v)$ (Proposition 6). The convexity
and differentiability of $H_{\lambda}$ implies that

$\displaystyle H_{\lambda}(\phi_{F}(p))$ $\displaystyle\geq
H_{\lambda}(p)+r_{\lambda}(p)(\phi_{F}(p)-p)$
$\displaystyle=H_{\lambda}(p)+\frac{1}{(1-F(p))^{\lambda}}h_{F}(p)(\phi_{F}(p)-p).$

Second, from the definition of the virtual valuation we have that
$\phi_{F}(p)=p-\frac{1}{h_{F}(p)}$. Replacing in the previous inequality we
conclude that $H_{\lambda}(\phi_{F}(p))\geq
H_{\lambda}(p)-(1-F(p))^{-\lambda}$. Moreover, noticing that
$(1-F(p))^{-\lambda}=\Gamma_{\lambda}(H_{\lambda}(p))^{-\lambda}=1+\lambda
H_{\lambda}(v)$, we obtain that

$H_{\lambda}(\phi_{F}(p))\geq H_{\lambda}(p)(1-\lambda)-1.$

Third, because $\Gamma_{\lambda}$ is decreasing and that $\phi_{F}$ is
monotone, we derive from the previous inequality that

$\Gamma_{\lambda}(H_{\lambda}(p))\leq\Gamma_{\lambda}\big{(}\;H_{\lambda}(\phi^{-1}_{F}(p))(1-\lambda)-1\;\big{)}.$

To conclude the proof, we replace the above expression in Equation (4) and
obtain that

$\displaystyle\mathbb{P}[\phi_{F}(v_{i})\geq p|v_{i}\geq p]$
$\displaystyle\geq\frac{\Gamma_{\lambda}(H_{\lambda}(\phi^{-1}_{F}(p)))}{\Gamma_{\lambda}\big{(}H_{\lambda}(\phi^{-1}_{F}(p))(1-\lambda)-1\big{)}}$
$\displaystyle=\left(\frac{1+\lambda
H_{\lambda}(\phi^{-1}_{F}(p))}{1+\lambda\left(H_{\lambda}(\phi^{-1}_{F}(p))(1-\lambda)-1\right)}\right)^{-\frac{1}{\lambda}}$
$\displaystyle=\left({1-\lambda}\right)^{\frac{1}{\lambda}}.$

∎

##  Appendix E Missing proofs from Section 5

######  Lemma 9.

For $j\geq 1$,

$n\cdot\sum_{t\leq j}p_{t}\geq\frac{j}{2}(1-\lambda)^{\frac{1}{\lambda}}.$

###### Proof.

Observe that when $j=1$,

$np_{j}=n\mathbb{P}[x\geq\mathbb{E}[v^{(1,n)}]]\geq\mathbb{P}[v^{(1,n)}\geq\mathbb{E}[v^{(1,n)}]]\geq(1-\lambda)^{\frac{1}{\lambda}}.$

Here the first inequality follows from union bound and the second inequality
follows from 2. For $j>1$, $n\sum_{t\leq j}p_{j}=n\mathbb{P}[x\geq u_{j}]$.
Recall that $u_{j}=E[v^{(1,\lceil n/j\rceil)}]$. We can partition the set of
$n$ draws into $j$ sets each containing $s=\lceil\frac{n}{j}\rceil-1$ values.
From 1, we know that the maximum element in each partition will lie in the
bucket with probability at least $\frac{1}{2}(1-\lambda)^{\frac{1}{\lambda}}$
(as $l\geq 2$). Therefore,

$n\mathbb{P}[x\geq u_{j}]\geq j\cdot(s)\mathbb{P}[x\geq u_{j}]\geq
j\cdot\mathbb{P}[v^{(1,s)}\geq\mathbb{E}[v^{(1,s+1)}]]\geq
j/2(1-\lambda)^{\frac{1}{\lambda}}.$

∎

######  Lemma 10.

Consider $r_{1}\geq r_{2}\geq\cdots\geq r_{k}\geq 0$, then an optimal solution
to the convex program

$\displaystyle\max\sum_{j=1}^{k}r_{j}$ $\displaystyle\cdot e^{-p_{j}\cdot n}$
(Primal) $\displaystyle n\cdot\left(\sum_{j=1}^{s}p_{j}\right)$
$\displaystyle\geq\frac{s}{2}(1-\lambda)^{\frac{1}{\lambda}}\qquad\text{ for
all }1\leq s\leq k$ $\displaystyle 0\leq p_{j}$ $\displaystyle\leq
1\qquad\qquad\qquad\text{ for all }1\leq j\leq k$

is $p_{1}=p_{2}=\dots=p_{k}=\frac{1}{2n}(1-\lambda)^{\frac{1}{\lambda}}$.

###### Proof.

Our proof-technique uses the complementary slackness result for convex
duality.

Given the Primal problem, we denote by $\lambda_{s}$ the dual variable
corresponding to the first constraint and define
$S_{j}=\sum_{s=j}^{k}\lambda_{s}$. Naturally $S_{j}\geq S_{j+1}$. If we
lagrangify the first constraint and find the optimal value of $p_{j}$, we get
that $p_{j}=-\log(\frac{nS_{j}}{r_{j}})/n$. Substituting this value gives us
the objective. The constraint $0\leq p_{j}\leq 1$ gives us the second
constraint on $S_{j}$. Thus we obtain the following dual problem.

$\displaystyle\min\sum_{j=1}^{k}S_{j}\left(n-\frac{1}{2}(1-\lambda)^{\frac{1}{\lambda}}\right)$
$\displaystyle-S_{j}\cdot\log\left(\frac{nS_{j}}{r_{j}}\right)$ (Dual)
$\displaystyle S_{j}$ $\displaystyle\geq S_{j+1}\qquad\quad\text{ for all
}1\leq j\leq k-1$ $\displaystyle\frac{r_{j}}{ne^{n}}\leq S_{j}$
$\displaystyle\leq\frac{r_{j}}{n}\qquad\qquad\text{ for all }1\leq j\leq k.$

Consider the primal solution
$p_{j}=\frac{1}{2n}(1-\lambda)^{\frac{1}{\lambda}}$ and observe that this is a
feasible solution and achieves an objective value of
$\sum_{j=1}^{k}r_{j}e^{-1/2(1-\lambda)^{\frac{1}{\lambda}}}$. Consider setting
the dual to be $S_{j}=r_{j}\cdot e^{-1/2(1-\lambda)^{\frac{1}{\lambda}}}/n$.
Since $r_{1}\geq\dots r_{k}\geq 0$, we know that this dual is feasible and has
the same objective value. Since both the primal and dual are feasible and
bounded, we know that the primal solution $p_{j}$ is optimal. ∎

##  Appendix F Missing proofs from Section 6

See 6

###### Proof.

Let $n>e^{4}$ be an integer. Consider a distribution with support $[1,n)$ with
density $f(x)=\frac{n}{n-1}\times\frac{1}{x^{2}}$. Note that for this
distribution the C.D.F $F(x)=\frac{n}{n-1}\times(1-1/x)$. The optimal revenue
for selling single item with values drawn from distribution $f$ is
$\arg\max_{x}x(1-F(x))=\arg\max
x(1/x-1/n)\frac{n}{n-1}=(1-1/n)\frac{n}{n-1}=1$. Thus the optimal revenue for
selling $n$ items to $n$ I.I.D. bidders with values drawn from $f$ is $n$. In
the following lemma, we show that when the demand structure is monopsony, it
is possible to use bundle pricing to get $\Omega(n\ln{n})$ revenue.

We will show that the expected revenue from setting a bundle price of
$n\ln{n}/2$ is $\Omega(n\ln{n})$. For a bundle price $p$, the intermediary
will purchase the bundle if the sum of the $n$ values of its buyers is at
least $p$. Let $X_{1},X_{2},\ldots X_{n}$ denote the random variable
indicating the buyers draws and let $X=X_{1}+X_{2}+\cdots+X_{n}$, denote the
random variable for the sum of these $n$ random draws. For each $X_{i}$,
$\mathbb{E}[X_{i}]=\frac{n}{n-1}\ln{n}$, $\mathbb{E}[X_{i}^{2}]=n$, and hence
$Var[X_{i}]=n-(\frac{n\ln{n}}{n-1})^{2}$. Further
$\mathbb{E}[X]=\frac{n^{2}\ln{n}}{n-1}$ and
$Var[X]=n^{2}-\frac{n^{3}\ln{n}^{2}}{(n-1)^{2}}<n^{2}$.

We will use the following one-sided Chebychev’s inequality to prove this
result. For any random variable with mean $\mu$ and standard deviation
$\sigma$,

$\mathbb{P}[|x-\mu|\geq k\sigma]\leq
1/k^{2}\implies\mathbb{P}[\mu-k\bar{\sigma}\geq x]\leq 1/k^{2},$

for any $\bar{\sigma}\geq\sigma$. Setting $\mu=\frac{n^{2}\ln{n}}{n-1}$,
$\bar{\sigma}=n$, and $k=\frac{\mu}{2\bar{\sigma}}$,

$\mathbb{P}[X\leq\mu-k\bar{\sigma}=\mu/2]\leq
1/k^{2}=\frac{4\bar{\sigma}^{2}}{\mu^{2}}=\frac{4n^{2}(n-1)^{2}}{n^{4}\ln{n}^{2}}\leq
1/4.$

In the last step we use that $n>e^{4}$.

Thus $\mathbb{P}[X\geq\mathbb{E}[X]/2]\geq 3/4$ and setting a bundle price of
$\mathbb{E}[X]/2$, will yield a revenue of $\Omega(n\ln{n})$.

On the other hand, with item pricing, the most revenue that can be obtained is
$O(n)$. Thus item-pricing obtain at most $\Omega(\ln n)$ factor to the optimal
revenue. ∎