# Bundling in Oligopoly:
Revenue Maximization with Single-Item Competitors

Moshe Babaioff
Hebrew University of Jerusalem<EMAIL_ADDRESS>Moshe
Babaioff’s research is supported in part by a Golda Meir Fellowship. Linda Cai
Princeton University<EMAIL_ADDRESS>Brendan Lucier
Microsoft Research<EMAIL_ADDRESS>
###### Abstract

We consider a principal seller with $m$ heterogeneous products to sell to an
additive buyer over independent items. The principal can offer an arbitrary
menu of product bundles, but faces competition from smaller and more agile
single-item sellers. The single-item sellers choose their prices after the
principal commits to a menu, potentially under-cutting the principal’s
offerings. We explore to what extent the principal can leverage the ability to
bundle product together to extract revenue.

Any choice of menu by the principal induces an oligopoly pricing game between
the single-item sellers, which may have multiple equilibria. When there is
only a single item this model reduces to Bertrand competition, for which the
principal’s revenue is $0$ at any equilibrium, so we assume that no single
item’s value is too dominant. We establish an upper bound on the principal’s
optimal revenue at every equilibrium: the expected welfare after truncating
each item’s value to its revenue-maximizing price. Under a technical condition
on the value distributions — that the monopolist’s revenue is sufficiently
sensitive to price — we show that the principal seller can simply price the
grand-bundle and ensure (in any equilibrium) a constant approximation to this
bound (and hence to the optimal revenue). We also show that for some value
distributions violating our conditions, grand-bundle pricing does not yield a
constant approximation to the optimal revenue in any equilibrium.

##  1 Introduction

True monopolies are rare. Even a large, dominant seller in a given market will
almost certainly need to contend with small, agile competitors who attempt to
offer similar products. For example, suppose that a large firm has many
heterogeneous goods to sell to a buyer who values them additively and
independently. This setting has been studied extensively in the algorithmic
mechanism design literature when the seller is a monopolist, and it is known
that the seller can often extract more revenue (sometimes close to the full
social welfare) by bundling goods together and selling them as packages
instead of selling each item separately [HN12, HN17, LY13, BILW14]. But this
sort of aggressive bundling strategy carries risk: if a smaller competitor
were able to replicate one of the products, they could sell it as a stand-
alone offering and attract away customers who have an especially strong
preference for it relative to the others. On the other hand, selling items à
la carte leaves the firm vulnerable to being undercut on prices. Either way,
the threat of competition even from smaller sellers of individual products can
substantially impact the firm’s sales strategy and revenue.

Our goal in this paper is to understand the ability of a multi-product
principal seller to extract revenue in settings where he faces competition
from agile item sellers. In our model there is a single multi-good seller (the
principal) who has $m$ items to sell, plus a pool of item sellers who each has
only a single one of the $m$ item types to sell. For most of the paper we will
assume that there is exactly one competing item seller per item type.111Our
results extend naturally to having an arbitrary and possibly different number
of item sellers for each good (including none at all), as we discuss in our
model extensions below. The principal, acting as a market leader, first
selects and commits to an arbitrary menu of product bundles. Then,
simultaneously, each item seller picks her own deterministic menu for selling
her item (equivalently, picks a price for her item). The item sellers can
randomize over different prices. The buyer, aiming to maximize her utility,
then decides on a subset to buy from the principal seller, and on the set of
items she buys from the item sellers.

The presence of the item sellers impedes the ability of the principal to
extract revenue because of their ability to undercut the principal’s prices.
In the special case of only a single item, this is classic Bertrand
competition. Indeed, if the principal chooses any price $p>0$, a competing
item seller would simply undercut $p$ by some small amount and steal away all
of the principal’s sales. Thus, in the case of a single item type, it is
impossible for the principal to generate any revenue. However, if there are
two or more items, the principal has a power that the item sellers do not: the
power to bundle items together and sell them as a package. We ask: _What are
the limits on the revenue of the principal due to the competition? Under which
market conditions can the principal extract significant revenue even in the
presence of such competition?_

Any given choice of menu by the principal seller defines a downstream
oligopolistic pricing game played by the item sellers. Our solution concept in
that downstream game is mixed Nash equilibrium (NE): each item seller selects
a distribution over price choices that maximizes her expected revenue given
the menu of the principal and the distributions selected by the other item
sellers. With a discrete pricing space a mixed NE is guaranteed to exist, but
is not unique in general. We are able to prove an upper bound on the revenue
attainable by the principal that is robust to the choice of equilibrium: it
holds for any choice of menu and any equilibrium of play by the item sellers.
We show that the principal’s revenue cannot be greater than the expected sum
of truncated item values, where each item’s value is truncated to its
(maximal) revenue-maximizing price.

######  Theorem 1.1.

Suppose the buyer has independent item values $v_{i}\sim F_{i}$ and that
$r_{i}\in\arg\max_{r}\\{r(1-F_{i}(r))\\}$ is the maximal revenue-maximizing
price for item $i$. Then for any menu of the principal seller and any mixed
Nash equilibrium among the item sellers, the expected revenue of the principal
seller is at most the buyer’s expected truncated social welfare
$\mathop{{}\mathbb{E}}_{\vec{v}{\sim\times_{i}F_{i}}}[\sum_{i}\min\\{v_{i},r_{i}\\}]$.

We note that this upper bound may be substantially lower than the revenue
obtainable by a monopolist. For example, suppose the item value distributions
are i.i.d. draws from an equal revenue distribution supported on $[1,H]$ for
some large $H>m$,222This is the distribution $F$ over $[1,H]$ such that
$1-F(z)=1/z$ for all $1\leq z<H$. skewed slightly so that $1$ is the unique
revenue-maximizing price. In this instance it is known that a monopolist
seller can obtain revenue $\Omega(m\log m)$ by appropriately pricing the grand
bundle of all items. But the expected truncated welfare, our upper bound on
the principal’s revenue in our competitive setting, is much lower, just
$O(m)$.

What makes it harder for the principal to extract revenue than a monopolist?
We recall that for a monopolist, it is possible to achieve a constant fraction
of the optimal revenue with a simple menu that either prices the grand bundle
of all items, or sets a separate price on each individual item and allows the
buyer to purchase à la carte [BILW14]. In our competitive setting, however,
the latter is not an option: setting a separate price on each item reduces the
problem to $m$ independent instances of Bertrand competition, leading to each
item’s price being undercut by its item seller and no revenue being generated
for the principal. On the other hand, by bundling items together, the
principal might encourage item sellers to keep their prices high; however, as
we show, an item seller will never choose a price higher than their maximal
monopolist reserve price $r_{i}$. This ultimately prevents the principal from
extracting revenue from higher values, leading to our upper bound on the
principal’s optimal revenue.

We show that, under certain assumptions on the value distributions, it is
possible for the principal to guarantee a constant approximation to the
expected truncated social welfare (which, by Theorem 1.1, upper bounds the
optimal revenue). Moreover, this is achievable with a simple menu that offers
only the grand bundle of all products at a carefully-selected price.

######  Theorem 1.2 (Informal).

Suppose each item’s value distribution is $(\lambda,C)$-price-sensitive
(described below) and that the variance of the truncated social welfare is
sufficiently high (as a function of $\lambda$, $C$, and $\max_{i}r_{i}$). Then
there exists a price $p$ at which the principal can sell the grand bundle of
all items such that, at any mixed NE for the item sellers, the principal’s
revenue is at least $1/3$ of the expected truncated social welfare.

The assumptions we impose on the value distributions are of two types. First,
we require that the total variance of the sum of truncated values is high
relative to each individual item’s contribution. This implies that no
individual item contributes too much to the expected truncated welfare, or has
too high an influence on the likelihood of sale to the principal. This is an
expansion of the requirement that there be more than one item for sale (which,
recall, is necessary for the principal to obtain any revenue at all). For
example, if we have multiple items but a single item contributes almost all of
the value, then we are “essentially” in the single-item case and similar
issues persist. To give another example of what can go wrong if individual
item sellers have high influence, suppose each of the $m$ items has value 1
for sure. Then for any price $p$ that the principal sets on the grand bundle,
there is a Nash equilibrium in which every item seller sets price $p/m$,
precisely coordinating to undercut the grand bundle price and resulting in
revenue $0$ for the principal. In this case, even though no individual item
dominates the welfare, each individual item seller still has substantial
influence on the buyer’s aggregate purchasing decisions at equilibrium. Our
condition that the variance is sufficiently high excludes such a scenario,
since no individual item price will be significantly predictive of the buyer’s
utility-maximizing behavior.

Second, we require that each item’s value distribution is non-trivially “price
sensitive”, by which we mean that the revenue obtained decreases sufficiently
(parameterized by $\lambda$) at prices sufficiently below the revenue-
maximizing price (parameterized by $C$). This is a technical condition that
essentially rules out point-mass distributions and equal-revenue
distributions, requiring that the distributions are sufficiently far from
these edge case distributions (and the bound we require on the number of items
is parameterized by how far they are).

We leave a formal definition of the price sensitivity condition to later
sections (see Section 4). Instead, we now note some simpler sufficient
conditions that imply our approximation result:

  1. 1.

In the i.i.d. case where all item values are drawn from a distribution $G$, if
$G$ has a unique revenue-maximizing price $r^{*}$ that is greater than the
minimum positive value in the support of $G$, our conditions will be satisfied
for all sufficiently large $m$.

  2. 2.

For every $i$, there exists a $\delta$ such that if the value distribution of
item $i$ has revenue-optimizing price $r_{i}\geq r_{min}>0$, density at least
$\delta/r_{i}>0$ on $[0,r_{i}]$, and strictly concave revenue curves (in price
space) with second derivatives at most $-\delta/r_{i}<0$, our conditions will
be satisfied for all sufficiently large $m$.

It is worth noting that while in Theorem 1.2 and its corollaries we describe
our assumptions as though they must hold for all items, this is not strictly
necessary. Our results degrade gracefully in that sense that if some subset
$S$ of the items satisfy the necessary conditions, then the principal’s
revenue can approximate the expected truncated welfare of the items in $S$.
Indeed, the principal can always choose to ignore any items not in $S$,
leaving the corresponding item sellers to act as monopolists (so in every
equilibrium they price at their revenue-maximizing prices).

While the assumptions we impose are technical and we suspect they can be
relaxed, we show that some form of assumption on the value distributions is
necessary for the grand bundle to obtain a good revenue-approximation result.
We construct a family of problem instances for which, unlike in Bertrand
competition, the principal’s optimal menu generates substantial revenue. For
this family, the revenue of the best partition menu (in which the items are
partitioned into disjoint bundles and each is assigned a price) is higher than
the revenue of any grand-bundle pricing by an arbitrarily large factor
($\Theta(m)$). We leave open the question of how to construct an approximately
optimal menu (which must necessarily be more complex than pricing the grand
bundle) for general distributions. In particular, is there always an
approximately revenue-optimal menu for the principal that is a partition menu?
If so, is it possible to construct such an approximately-optimal menu in
polynomial time?

Proof Techniques. We now briefly describe the proof of Theorem 1.2 and how it
differs from corresponding results for a monopolist seller. For a monopolist,
if the buyer’s expected total value from all items is sufficiently
concentrated around its mean, the principal can collect a constant fraction of
this surplus by pricing the grand bundle at a price that is constant fraction
of the mean. The idea behind Theorem 1.2 is similar, but the principal must
additionally consider the impact of prices chosen by the item sellers in
equilibrium. If the buyer’s expected _truncated_ welfare is sufficiently
concentrated around its mean, the principal can attempt to extract a constant
fraction of this welfare as revenue with a price that is constant fraction of
the mean. This can potentially work if the competing item sellers set prices
close to their optimal monopolist reserves $r_{i}$, but (unlike for a
monopolist) this approach would certainly fail if the item sellers set prices
so low that the buyer rarely buys from the principal. To show that this
doesn’t happen under the assumptions of Theorem 1.2, we use the Berry-Esseen
theorem to argue that the expected truncated welfare is sufficiently _anti_
-concentrated (in addition to our earlier requirement of being concentrated
enough). This variability implies that either the principal seller sells the
grand bundle with constant probability (in which case we are already done,
since the price is a constant fraction of the benchmark), or each individual
item seller has limited influence on whether or not the buyer purchases from
the principal. In the latter case, item sellers behave like (approximate)
monopolists, so as long as their revenue is non-trivially sensitive to their
choice of price, they will choose prices close enough to their revenue-
maximizing prices at equilibrium (at least $C\cdot r_{i}$ for every $i$ where
$C>0$ is a constant that depends on the value distribution). But now, since
the item sellers are setting high prices, the principal effectively acts as a
monopolist with respect to the truncated value distributions and can capture a
constant fraction of the truncated welfare by its choice of price on the grand
bundle.

Model extensions. Our model focuses on the case that there is one item seller
for each item the principal seller has. Our results can easily be extended to
the case that there is any number of item sellers for each good (including
none at all). In any case that there are several item sellers which all supply
exactly the same item, the price of that item will drop to 0 in every
equilibrium (standard Bertrand competition between these item sellers), so
such items cannot contribute to the revenue of the principal at all.333The
principal can extract the exact same revenue with or without these items,
since it can be assumed the buyer would purchase those items from the item
sellers at price $0$ regardless, so would behave as though the items are not
offered by the principal. Let us now move to consider items that have no item
seller at all. The principal seller is a monopolist on these items. Let $X$ be
the set of items or which the principal is a monopolist, and $Y$ be the set of
items with exactly one item seller for each item. Similarly to the claim
proved by Hart and Nisan[HN12], we observe that the revenue of principal in
this model is bounded by the revenue obtainable from $X$ plus the welfare of
$Y$. By the result of [BILW14], either selling the items in $X$ separately, or
bundling all of them together, provides constant approximation to the optimal
revenue of the monopolist. Combining the appropriate menu for $X$ with our
offer of $Y$ as a bundle in the case that we are able to obtain a positive
result (constant approximation to the expected truncated social welfare), we
get constant approximation to the optimal menu over the set $X\cup Y$.

Organization. In Section 2 we formalize our model, including the market timing
and equilibrium concept. In Section 3 we establish our upper bound on the
principal’s optimal revenue, by first analyzing the structure of the buyer’s
purchasing decisions (Section 3.1) and the best-responses prices of the item
sellers (Section 3.2) then bounding the principal’s revenue at equilibrium
(Section 3.3). In Section 4 we prove our main result: a constant revenue
approximation for the principal under a general set of conditions, followed by
some market structures that satisfy these conditions. Finally, in Section 5 we
show that the best achievable revenue from pricing the grand bundle can be an
arbitrarily poor approximation to the principal’s optimal revenue.

### Additional Related Work

Auction Design for a Monopolist Seller. Revenue optimal auction design is
known to be a hard problem, even when the designer has monopoly over the
market. Specifically, when an auction involves multiple items, even when there
is only one additive buyer, the revenue optimal auction of a monopolist may
involve unrealistic features such as requiring randomization, lack of revenue
monotonicity, and being computationally intractable [Tha04, MV07, Pav11, HN13,
DDT14, HR15, DDT17]. On the other hand, simple auction formats have been shown
to provide a constant approximation to the monopolist optimal revenue for an
additive buyer [HN12, HN17, LY13, BILW14]. [CDW16] establishes a duality
framework which gives a tractable benchmark that bounds the optimal revenue
within constant factor. The benchmark has subsequently been heavily utilized
in the design and analysis of simple and approximately optimal auctions [LP18,
CZ17, EFF+17a, EFF+17b, BCWZ17, DW17, FLLT18, BW19, CS21]. Specifically, in
the setting of one additive buyer, the better between selling separately and
selling the grand bundle is a constant approximation to the optimal revenue.
Relative to that literature, we initiate a study of revenue benchmarks for a
non-monopolistic principal who acts as a market leader and can design a menu
(possibly with bundling) to which other sellers might respond.

Oligopoly.  Oligopoly has long been a topic studied in economics. Most
literature studies price competition between two or several large firms who
offer similar sets of products. See, for example, [Che97, AV10] for examples
of duopoly analysis. Particularly related to this paper is a line of work that
studies how much a firm who has obtained monopolist status in one product can
use bundling to deter single product competitors in another product, and its
legislative implications [Whi89, Nal04, Vic05, ADR13]. More recent work has
considered competition between multiple firms who can each bundle their
products, such as [KRK20] which considers the case of two firms each with two
products.

In contrast, our work studies the strategies of a large firm that offers
multiple products, given that small competitors already exist in the market
for each product. Such situations is common for tech markets (e.g. security
products, graphic products), where the fixed cost of maintaining a small
business is relatively lower compared to other. [Man13] studies this setting,
but under the restricted assumption that the principal seller sells two
products. [SYZ22] also studies the two product setting, but where the
principal seller is competing with several small businesses for each product.
Our paper initiates a systematic study of oligopoly with single item
competitors, where we allow any number of items to be offered by the principal
seller, and we focus on the principal seller’s problem of constructing an
approximately revenue-optimal menu.

##  2 Model and Preliminaries

We consider a market for a set ${\mathcal{M}}$ of $m$ item types. Items are
indivisible. There is a single buyer in the market, interested in buying at
most one item from each item type, and having a private additive non-negative
valuation over subsets of items. We denote the value of item
$i\in{\mathcal{M}}$ by $v_{i}\geq 0$, and thus the value of a subset of items
$B\subseteq{\mathcal{M}}$ is $\sum_{i\in B}v_{i}$.

We assume that the valuation of the buyer is drawn from a prior distribution
$F$, which is common knowledge among all participants, with the value of each
item $i$ drawn independently from the distribution $F_{i}$ with support in
$[0,\infty)$, so $F=\times_{i=1}^{m}F_{i}$. We assume (wlog) that $F_{i}$ is
non-trivial ($F_{i}[v_{i}=0]<1$). Let $\mathsf{Rev}_{F_{i}}(\cdot)$ be the
revenue function for $F_{i}$: the revenue by pricing at price $x$ is
$\mathsf{Rev}_{F_{i}}(x)=x\cdot(1-F_{i}(x))$. 444Where we write
$F_{i}(x)=\Pr_{v_{i}\sim F_{i}}[v_{i}<x]$. When clear from the context we use
$\mathsf{Rev}_{i}(\cdot)$ to denote $\mathsf{Rev}_{F_{i}}(\cdot)$. We assume
that $F_{i}$ has a maximal revenue-maximizing (Myerson) price. That is, there
exist a price $r_{i}$ such that
$\mathsf{Rev}_{F_{i}}(r_{i})\geq\mathsf{Rev}_{F_{i}}(x)$ for every price $x$,
and $\mathsf{Rev}_{F_{i}}(r_{i})>\mathsf{Rev}_{F_{i}}(y)$ for every price
$y>r_{i}$. The realized value profile of the buyer
$\vec{v}=(v_{1},\cdots,v_{m})$ is drawn from the prior product distribution
$F=\times_{i=1}^{m}F_{i}$. Only the buyer knows the realized values.

In this market there are multiple sellers that supply the desired items, all
with $0$ cost of production. There is one seller that we call the _principal
seller_ who can supply any subset of the $m$ items. In addition to the
principal seller, there are $m$ _item sellers_ , where item seller $i$ can
supply a copy of item $i\in{\mathcal{M}}$ only (that is, an item that is
completely identical to the $i$’th item supplied by the principal seller). The
sellers have no value for their items, only value for money received from the
buyer. All agents are assumed to be risk neutral, with quasi-linear utility
functions. Each seller aims to maximize their revenue obtained. The buyer aims
to maximize their expected utility, defined as the difference between their
valuation for the acquired items and the total price paid.

##### Market Timing

Informally, our market operates as follows. First, the principal seller
chooses a deterministic menu of offers, and commits to it. Then, each item
seller simultaneously picks her own deterministic menu for selling her item
(equivalently, picks a price for her item). Finally, the buyer selects a
subset of items to buy from the principal seller and a subset of items to buy
from the item sellers, either of which might be empty. More formally, the
timing of our market is as follows:

  1. 1.

The principal seller first chooses and commits to a deterministic menu of
prices, one for each subset of items $T\subseteq{\mathcal{M}}$. We will write
$p\colon 2^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ to denote the price menu
selected by the principal seller, so that $p(T)$ is the price assigned to
subset $T\subseteq{\mathcal{M}}$.555As is standard, it will sometime be
convenient to think about a partial menu that does not explicitly list all
subsets as menu entries (e.g., only prices the grand bundle). In this case, we
assume free disposal so that the price of a set $T$ is the cheapest price of
all $S$ such that $T\subseteq S$ in the menu, and infinite if there is no such
set $S$.  The principal has to offer the option of buying nothing and paying
zero ($p(\emptyset)=0$). We denote by $\mathcal{P}$ the space of all such
deterministic price menus.

  2. 2.

Next, knowing the menu $p$ picked by the principal seller, the item sellers
simultaneously select prices for their corresponding items. Each item seller
$i$ chooses a single non-negative price $q_{i}\geq 0$ at which to offer item
$i$.

  3. 3.

Finally, the buyer value profile $(v_{1},\ldots,v_{M})\sim\times_{i}F_{i}$ is
realized, and the buyer purchases items from the principal and/or some item
sellers. This involves choosing a single subset $T\subseteq{\mathcal{M}}$ of
items from the menu offered by the principal and paying $p(T)$ to the
principal, as well as choosing a subset $U\subseteq{\mathcal{M}}$ of items
from individual item sellers, paying $q_{i}$ to each item seller $i\in U$. The
buyer acts as a price-taker and will always make purchase decisions to
maximize their own utility. In case of indifference, we assume that the buyer
breaks ties in favor of minimizing the revenue of the principal seller,666As
item sellers price their items after the principal seller, they can always
slightly reduce their price to win any tie. and then in favor of maximizing
the number of items purchased from the item sellers.

Thus, for menu $p$ and item sellers prices $\vec{q}$, the buyer’s utility when
her values for the items are $\vec{v}$ is $\sum_{i\in T\cup
U}v_{i}-p(T)-\sum_{i\in U}q_{i}$. The principal seller obtains revenue $p(T)$,
and each item seller $i$ obtains either revenue $q_{i}$ if $i\in U$, and $0$
otherwise.

##### The Game and Equilibrium Concepts

Given a value distribution $F$ for the buyer, a menu $p\in\mathcal{P}$ picked
by the principal seller together with the buyer behaviour as specified above,
induce a simultaneous-move game $G_{p,F}$ among the item sellers. A mixed
strategy $s_{i}$ of item seller $i$ is a distribution over prices $q_{i}$. We
will assume for technical convenience that item prices are constrained to be
multiples of some arbitrarily and sufficiently small increment $\epsilon>0$
(and that $q_{i}\leq 1$ for each $i$, which is without loss of generality
since $v_{i}\leq 1$). Note that item sellers pick strategies in the game
$G_{p,F}$, thus the strategy may depend on $p$. The space of mixed strategies
of item seller $i$ is denoted by $S_{i}$. Given $p$ and a profile of mixed
strategies $\vec{s}=(s_{1},s_{2},\ldots,s_{m})$, we denote the (expected)
utility of item seller ${i}$ in the game $G_{p,F}$ by $u_{i,F}({p},\vec{s})$
(where the expectation is over the distribution of values $\vec{v}\sim F$ and
distribution of item seller prices, $q_{i}\sim s_{i}$ for every $i$). When $F$
is clear from the context we sometimes use $u_{i}({p},\vec{s})$ to the utility
$u_{i,F}({p},\vec{s})$.

We are now ready to define equilibria of the game $G_{p,F}$.

######  Definition 2.1.

Consider a market with value distribution $F=\times_{i}F_{i}$. For any
principal menu $p\in{\mathcal{P}}$, a (mixed) Nash Equilibrium of the induced
game $G_{p,F}$ is a profile of strategies
$(s_{1}^{*},s_{2}^{*},\dots,s_{m}^{*})\in\times_{i=1}^{m}S_{i}$ among item
sellers such that for every item seller $i$ and for all $s_{i}\in S_{i}$ we
have:

$u_{i,F}({p},(s_{i}^{*},s_{{-i}}^{*}))\geq u_{i,F}({p},(s_{i},s_{{-i}}^{*})),$

where $s_{{-i}}^{*}$ represents the strategy profile of all item sellers other
than item seller $i$.

We first briefly comment on the existence of Nash equilibria in $G_{p,F}$. For
any $F$ and $p$, consider a game $G^{\prime}_{p,F}$, which is identical to
$G_{p,F}$, except that the pricing space for each item seller $i$ is
restricted to $[0,r_{i}]$. Since we assume prices are multiples of some
arbitrarily small increment, the game $G^{\prime}_{p,F}$ is finite and thus at
least one mixed Nash equilibrium is guaranteed to exist. We will soon see in
Section 3 (in particular Lemma 3.1) that for any item seller $i$, pricing
above $r_{i}$ is a weakly dominated strategy, so any deviation to a price
above $r_{i}$ is not beneficial. As a result, a mixed Nash equilibrium in
$G^{\prime}_{p,F}$ is also a mixed Nash equilibrium in $G_{p,F}$.

Given $F=\times_{i}F_{i}$, a menu $p$ and a profile of mixed strategies
$\vec{s}=(s_{1},s_{2},\ldots,s_{m})$, the _revenue (utility) of the principal
seller from $(p,\vec{s})$_ in the game $G_{p,F}$ is defined to be the expected
payment to the principal with menu $p$ when $\vec{v}\sim F$, and $q_{i}\sim
s_{i}$ for every item seller $i$ (given the buyer behaviour). The _revenue of
the principal seller from menu $p$_ is defined to be the lowest revenue, over
all Nash equilibrium profiles $\vec{s}$, of the principal seller from
$(p,\vec{s})$ in the game $G_{p,F}$. The principal seeks to find $p$ with high
revenue from menu $p$.

##  3 An Upper Bound on the Principal’s Revenue

In this section we analyze the behavior of the agents in our model. We will
discuss both the buyer utility and the item sellers’ utilities, and
consequently, structures in their decision making processes. Using these
observations, we will present a benchmark that upper bounds the revenue the
principal obtains by any menu she picks, in any mixed Nash equilibrium of the
induced game between the item sellers. Missing proofs in this section can be
found in Appendix B.

###  3.1 Understanding the Buyer’s Optimal Decision

We begin by considering the purchase decision of a buyer with value profile
$\vec{v}$ for the items, given the pricing decisions $(p,\vec{q})$ of all
sellers. In our analysis, we will represent the buyer’s utility with different
purchase options using the following notation:

Utility from the Principal: We use $\mathsf{ub}_{P,\vec{v}}(T,p)$ to denote
the maximum utility the buyer can attain by purchasing any subset $S\subseteq
T$ of items from the principal seller, when the buyer’s realized values are
$\vec{v}$ and the principal’s price menu $p$. That is:

$\mathsf{ub}_{P,\vec{v}}(T,p)=\max_{S\subseteq T}\left(\sum_{i\in
S}v_{i}-p(S)\right).$

Utility from Item Sellers: We use $\mathsf{ub}_{I,\vec{v}}(T,\vec{q})$ to
denote the maximum utility the buyer can attain by purchasing any subset
$S\subseteq T$ of items from the item sellers, when the buyer’s realized
values are $\vec{v}$ and the item sellers price vector is $\vec{q}$. That is:

$\mathsf{ub}_{I,\vec{v}}(T,\vec{q})=\max_{S\subseteq T}\sum_{i\in
S}(v_{i}-q_{i}).$

Clearly, items that are priced higher than their value will not be acquired.

Utility of Best Response Considering Seller Strategies: Fix some realized
values $\vec{v}$ of the buyer, a price menu $p$ of the principal seller, and a
vector of (possibly randomized) strategies $(s_{1},\cdots,s_{n})$ of the item
sellers. The buyer’s expected utility from their utility-maximizing purchasing
decision will be denoted by $\mathsf{ub}_{\vec{v}}(p,s_{1},\cdots,s_{n})$ and
is computed as follows:

$\displaystyle\mathsf{ub}_{\vec{v}}(p,s_{1},\cdots,s_{n})=\mathop{{}\mathbb{E}}_{\vec{q}\sim\vec{s}}\left[\max_{T\subseteq{\mathcal{M}}}\left\\{\mathsf{ub}_{P,\vec{v}}(T,p)+\mathsf{ub}_{I,\vec{v}}({\mathcal{M}}\backslash
T,\vec{q})\right\\}\right].$ (1)

It will also be useful to introduce notation for the difference in utility
from choosing between the principal and the item sellers for the same set of
items. Namely, we define

$\displaystyle\mathsf{diff}_{\vec{v}}(T,p,\vec{q})=\mathsf{ub}_{P,\vec{v}}(T,p)-\mathsf{ub}_{I,\vec{v}}(T,\vec{q}).$
(2)

An immediate implication of (1) is that given $\vec{v}$, $p$, and $\vec{q}$,
the set $T$ of items that the buyer purchases from the principal is a
maximizer of $\mathsf{diff}_{\vec{v}}(T,p,\vec{q})$. The following lemma uses
this observation to characterize how a change in the valuation profile
$\vec{v}$ can influence the set of items purchased from the principal; this
will be useful later when analyzing the principal’s optimal revenue.
claimclaimValueChange Fix any $p$ and any $\vec{q}$. Suppose that $\vec{v}$
and $\vec{v}^{\prime}$ differ only on a subset $S\subseteq M$ of items, and
let $T$ and $T^{\prime}$ denote the items purchased from the principal under
valuations $\vec{v}$ and $\vec{v}^{\prime}$ respectively. Then if $T\cap
S=T^{\prime}\cap S$ then $T=T^{\prime}$.

###  3.2 Item Seller Best-Responses

We next turn to the pricing problem faced by an item seller in the game
defined by the principal’s chosen menu $p$. We first consider the best
response of an item seller $i$ given a deterministic profile of prices
$q_{-i}$ selected by the other item sellers. We will show (in Lemma 3.1) that
the best response problem for $i$ can be viewed as a monopolist’s pricing
problem, but with revenue reduced by a factor that depends on the selected
price, with higher prices leading to steeper reductions.

We begin by characterizing the ways in which a change in one item seller’s
price can influence the set of items purchased from the principal seller.
claimclaimSameMaxMenu Fix some principal menu $p$, item seller $i$, the prices
of the other item sellers $q_{-i}$, and the realized buyer valuation
$\vec{v}$. Then there exist sets $T_{i}\ni i$ and $T_{\neg i}\not\ni i$ and a
threshold $\theta_{i}\geq 0$ such that, if $q_{i}$ is the price chosen by
agent $i$, then the set that the buyer purchases from the principal is $T_{i}$
if $q_{i}\leq\theta_{i}$, and is $T_{\neg i}$ if $q_{i}>\theta_{i}$.

An immediate corollary of Claim 3.2 is that the probability of sale for an
item seller is weakly decreasing in the choice of price $q_{i}$. This is true
even if we fix the buyer’s realized values $\vec{v}$, and in particular even
if we condition on the buyer’s value for item $i$ being higher than the chosen
price $q_{i}$. This is because a higher price from item seller $i$ will
increase the attractiveness of purchasing a set that includes item $i$ from
the principal. To state this formally, we will write
$\mathbbm{1}_{i,\vec{v}}(p,\vec{q})$ for the indicator variable of sale for
item seller $i$, given valuations $\vec{v}$, principal menu $p$, and item
seller prices $\vec{q}$.

propositionclaimProbMonotone Fix any item seller $i$ and prices
$q^{\prime}_{i}>q_{i}$ for seller $i$. Then for any principal menu $p$, other
item sellers’ prices $q_{-i}$, and buyer values $\vec{v}$, it holds that
$\mathbbm{1}_{i,\vec{v}}(p,(q_{i},q_{-i}))\geq\mathbbm{1}_{i,\vec{v}}(p,(q^{\prime}_{i},q_{-i}))$.

Our goal now is to analyze the revenue maximization problem for item seller
$i$. For an item seller $i$, their expected revenue from choosing a price
$q_{i}$ is simply $q_{i}$ times the probability of sale. We will use
$\mathsf{us}_{i,F}(p,\vec{s})$ to denote the utility of item seller $i$, given
the price menu $p$ of the principal, the value distribution
$F=\times_{i}F_{i}$ for the buyer, and the (possibly mixed) strategies
$\vec{s}$ of all item sellers. When $F$ is clear from the context we sometimes
use $\mathsf{us}_{i}(p,\vec{s})$ to denote $\mathsf{us}_{i,F}(p,\vec{s})$.
Then, recalling that $\mathbbm{1}_{i,\vec{v}}(p,\vec{q})$ is the indicator
variable for sale by item seller $i$, the following lemma relates the item
seller’s utility to the revenue of a monopolist seller.

######  Lemma 3.1.

For any menu $p$ and any profile of mixed strategies $\vec{s}$ it holds that:

$\displaystyle\mathsf{us}_{i}(p,\vec{s})={\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}\left[\mathsf{Rev}_{F_{i}}(q_{i})\cdot\mathop{{}\mathbb{E}}_{v_{-i}\sim
F_{-i},q_{-i}\sim
s_{-i}}\left[\mathbbm{1}_{i,(\infty,v_{-i})}(p,\vec{q})\right]\right]}$ (3)

###### Proof.

From the definition of $\mathbbm{1}_{i,\vec{v}}(p,\vec{q})$, we have

$\displaystyle\mathsf{us}_{i}(p,\vec{s})$
$\displaystyle=\mathop{{}\mathbb{E}}_{\vec{q}\sim\vec{s},\vec{v}\sim
F}\left[q_{i}\cdot\mathbbm{1}_{i,\vec{v}}(p,\vec{q})\right]$
$\displaystyle=\mathop{{}\mathbb{E}}_{\vec{q}\sim\vec{s},v_{-i}\sim
F_{-i}}\left[q_{i}\cdot\mathbb{P}_{v_{i}\sim F_{i}}[v_{i}\geq
q_{i}]\cdot\mathop{{}\mathbb{E}}_{v_{i}\sim F_{i}|{v_{i}}\geq
q_{i}}[\mathbbm{1}_{i,\vec{v}}(p,\vec{q})]\right]$ (4)

We next notice that, taking $T_{i}$ and $T_{\neg i}$ as in the statement of
Claim 3.2, for any $v_{i}\geq q_{i}$ we have that
$\mathbbm{1}_{i,\vec{v}}(p,\vec{q})=1$ if and only if the buyer does not
choose option $T_{i}$ at price $q_{i}$, which recall occurs if and only if
$\mathsf{diff}_{\vec{v}}(T_{i},p,\vec{q})\geq\mathsf{diff}_{\vec{v}}(T_{\neg
i},p,\vec{q})$ (from equation (2) and the discussion immediately following.)
But we notice that, as we change $v_{i}$, the value of
$\mathsf{diff}_{(v_{i},v_{-i})}(T_{i},p,\vec{q})$ remains the same for any
$v_{i}\geq q_{i}$. This is because

$\displaystyle\mathsf{diff}_{(v_{i},v_{-i})}(T_{i},p,\vec{q})$
$\displaystyle=\mathsf{ub}_{P,\vec{v}}(T_{i},p)-\mathsf{ub}_{I,\vec{v}}(T_{i},\vec{q})$
$\displaystyle=\left(\sum_{j\in T_{i}}v_{j}-p(T_{i})\right)-\left(\sum_{j\in
T_{i}}v_{j}-\sum_{j\in T_{i}}\min(v_{j},q_{j})\right)$
$\displaystyle=\sum_{j\in T_{i}}\min(v_{j},q_{j})-p(T_{i}).$

We therefore conclude that $\mathbbm{1}_{i,\vec{v}}(p,\vec{q})$ is a constant
for all $v_{i}\geq q_{i}$. In particular, $\mathop{{}\mathbb{E}}_{v_{i}\sim
F_{i}|{\color[rgb]{.75,0,.25}{v_{i}}}\geq
q_{i}}[\mathbbm{1}_{i,\vec{v}}(p,\vec{q})]=\mathbbm{1}_{i,(\infty,v_{-i})}(p,\vec{q})$.
Plugging this into (4), we conclude that

$\displaystyle\mathsf{us}_{i}(p,\vec{s})$
$\displaystyle=\mathop{{}\mathbb{E}}_{\vec{q}\sim\vec{s},v_{-i}\sim
F_{-i}}\left[q_{i}\cdot\mathbb{P}_{v_{i}\sim F_{i}}[v_{i}\geq
q_{i}]\cdot\mathbbm{1}_{i,(\infty,v_{-i})}(p,\vec{q})\right]$
$\displaystyle=\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}\left[\mathsf{Rev}_{F_{i}}(q_{i})\cdot\mathop{{}\mathbb{E}}_{v_{-i}\sim
F_{-i},q_{-i}\sim
s_{-i}}\left[\mathbbm{1}_{i,(\infty,v_{-i})}(p,\vec{q})\right]\right]$

as required. ∎

An interpretation of Lemma 3.1 is that the item seller’s revenue when pricing
using strategy $s_{i}$ is equal to the expectation (over $q_{i}\sim s_{i}$) of
the product of the item seller’s monopolist Myerson revenue when pricing at
$q_{i}$, reduced by the expectation of
$\mathbbm{1}_{i,(\infty,v_{-i})}(p,\vec{q})$ (over $v_{-i}$ and $q_{-i}$)
which depends on $q_{i}$ but not on $v_{i}$, and is monotone non-increasing in
$q_{i}$.

###  3.3 An Upper Bound on the Principal’s Revenue

In this section we present an upper bound on the principal revenue for any
menu and in any Nash equilibrium. The upper bound is the expected welfare when
each item value distribution is truncated at the highest Myerson price for
that distribution.

######  Definition 3.2 (Expected Truncated Social Welfare).

For any $i\in{\mathcal{M}}$, let $F_{i}$ be a value distribution for item $i$
and let $r_{i}$ be the maximal Myerson price for $F_{i}$. The buyer’s
_expected truncated social welfare_ when her item value vector
$(v_{1},\ldots,v_{n})$ is sampled from $\times_{i}F_{i}$ is defined to be
$\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim F_{i}}[\min(r_{i},v_{i})]$.

We prove that the expected truncated welfare upper bounds the revenue of the
principal seller:

######  Theorem 3.3.

Consider a market with value distribution $F=\times_{i}F_{i}$. For any menu
$p$ of the principal seller, and for any mixed Nash equilibrium $\vec{s}$ in
the game $G_{p,F}$, the expected revenue of principal seller under
$(p,\vec{s})$ is at most the buyer’s expected truncated social welfare
$\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim F_{i}}[\min(r_{i},v_{i})]$.

To prove Theorem 3.3, we first argue that the claimed bound holds under the
assumption that each $s_{i}$ is supported on $[0,r_{i}]$. We actually prove
something stronger: if each $s_{i}$ is supported on some arbitrary range
$[0,\bar{s}_{i}]$, then the principal’s revenue is at most the welfare when
the value of item $i$ is truncated at $\bar{s}_{i}$. This is true even if the
strategies $s_{i}$ are not in equilibrium, and even if the principal can
choose menu $p$ after the item sellers commit to their strategies.

######  Proposition 3.4.

Consider a market with value distribution $F=\times_{i}F_{i}$. Fix any menu
$p$ of the principal seller and any strategies $\vec{s}$ (which may not be a
NE) in the game $G_{p,F}$. Denote the supremum of the support of $s_{i}$ by
$\bar{s}_{i}$. Then the expected revenue of principal seller under
$(p,\vec{s})$ is at most $\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim
F_{i}}[\min(\bar{s}_{i},v_{i})]$.

###### Proof.

Fix any $\vec{q}$ and $p$. Recall that for all $i$ and all $\vec{v}$ in the
support of $F$, $\mathbbm{1}_{i,\vec{v}}(p,\vec{q})$ is constant for all
$v_{i}>q_{i}$. By Claim 3.1, this means that the set of items purchased from
the principal is constant for all $v_{i}>q_{i}$ as well. Let $F^{\prime}_{i}$
denote the distribution over $\min\\{v_{i},q_{i}\\}$ where $v_{i}\sim F_{i}$.
Then we conclude that the distribution over the set of items purchased from
the principal is not affected if we replace $F_{i}$ with $F^{\prime}_{i}$.
Applying this argument to each $i$ in sequence, we conclude that the
distribution over the set of items purchased from the principal is identical
under $\times_{i}F_{i}$ and $\times_{i}F^{\prime}_{i}$. This implies that the
principal’s expected revenue is likewise the same under $\times_{i}F_{i}$ and
$\times_{i}F^{\prime}_{i}$.

Since, for any $p$ and $\vec{q}$, the expected revenue achieved by the
principal is at most the expected welfare, we conclude that the principal’s
revenue is at most the expected welfare under $\times_{i}F^{\prime}_{i}$,
which is $\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim
F^{\prime}_{i}}[\min(q_{i},v_{i})]=\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim
F_{i}}[\min(q_{i},v_{i})]$.

Taking an expectation over $\vec{q}\sim\vec{s}$ and noting that
$q_{i}\leq\bar{s}_{i}$ for all such realizations, the principal’s expected
revenue is at most $\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim
F_{i}}[\min(\bar{s}_{i},v_{i})]$, as claimed. ∎

Our next step is to consider items $i$ for which the item seller’s strategy
$s_{i}$ is not supported on $[0,r_{i}]$. We observe that any such seller must
be generating revenue $0$ at equilibrium.

######  Lemma 3.5.

Consider a market with value distribution $F=\times_{i}F_{i}$. Fix any menu
$p$ of the principal seller, and any strategy profile $\vec{s}$ in the game
$G_{p,F}$, such that $s_{i}$ is a best response of item seller $i$ to
$s_{-i}$. If the probability that $s_{i}$ assigns to prices strictly greater
than $r_{i}$ is positive, then the expected revenue of item seller $i$ under
$(p,\vec{s})$ in $G_{p,F}$ is $0$.

###### Proof.

For any $z_{i}>{r_{i}}$ we have $r_{i}\times\mathbb{P}[v_{i}\geq
r_{i}]>z_{i}\times\mathbb{P}[v_{i}\geq z_{i}]$ (from the definition of
$r_{i}$). Since we also have $\mathop{{}\mathbb{E}}_{q_{-i}\sim
s_{-}i,v_{-i}\sim
F_{-i}}\left[\mathbbm{1}_{i,(\infty,v_{-i})}(p,(z_{i},q_{-i}))\right]\leq\mathop{{}\mathbb{E}}_{q_{-i}\sim
s_{-}i,v_{-i}\sim
F_{-i}}\left[\mathbbm{1}_{i,(\infty,v_{-i})}(p,(r_{i},q_{-i}))\right]$ by
Proposition 3.2, Equation (3) implies that
$\mathsf{us}_{i}(p,(z_{i},s_{-i}))<\mathsf{us}_{i}(p,(r_{i},s_{-i}))$ unless
$\mathsf{us}_{i}(p,(z_{i},s_{-i}))=\mathsf{us}_{i}(p,(r_{i},s_{-i}))=0$.
Therefore, if any $z_{i}>r_{i}$ is in the support of $s_{i}$, we must have
$\mathsf{us}_{i}(p,(z_{i},s_{-i}))=0$ and hence
$\mathsf{us}_{i}(p,(s_{i},s_{-i}))=0$. ∎

We are now ready to complete the proof of Theorem 3.3. Roughly speaking, we
will show that the principal cannot extract high revenue from any item $i$ for
which the item seller’s strategy $s_{i}$ is not supported on $[0,r_{i}]$. This
follows because, since any such item seller must be obtaining $0$ revenue at
equilibrium, the principal must be selling item $i$ whenever $v_{i}>0$.

###### Proof of Theorem 3.3.

Observe that, for each $i$, we have ${r}_{i}>0$, ${r}_{i}$ is in the support
of $F_{i}$, and that $E_{v_{i}\sim F_{i}}[\min(v_{i},{r}_{i})]>0$. Let $Z$ be
the set of indexes of item sellers that price strictly above ${r_{i}}$ with
positive probability according to $s_{i}$. By Lemma 3.5, each $i\in Z$ has
expected revenue $0$ at equilibrium. So for any $i\in Z$ and any $q_{i}>0$,
the probability that item seller $i$ sells item $i$ at price $q_{i}$ must be
$0$ (as otherwise there is a beneficial deviation for item seller $i$). By
Claim 3.2, the threshold $\theta_{i}$ for $i$ must be $0$, and thus there is a
set $T_{\neg i}$ that is bought for any $\vec{v}$ (in the support of $F$) with
$v_{i}>0$. In particular, for every $\vec{v}$ with $v_{i}>0$ the probability
(over $\vec{q}\sim\vec{s}$) of the principal selling item $i$ must be $1$
(since otherwise item seller $i$ could obtain positive revenue by pricing at
some $\varepsilon_{i}>0$).

Let us now introduce some notation. Fixing $p$ and $\vec{q}$, let $T(\vec{v})$
be the set of items purchased from the principal when the valuation profile is
$\vec{v}$. And for any $\vec{v}$, let $\psi(\vec{v})$ be the vector with $i$th
coordinate $\min\\{v_{i},r_{i}\\}$ for all $i\in Z$. That is, $\psi(\vec{v})$
is the vector $\vec{v}$ with each coordinate $i\in Z$ capped at $r_{i}$.

We now claim that for any realization of $\vec{q}\sim\vec{s}$ and any
$\vec{v}$ in the support of $F$, $T(\vec{v})=T(\psi(\vec{v}))$. This is
because $\vec{v}$ and $\psi(\vec{v})$ differ only on items $i\in Z$ for which
$v_{i}>0$, and we have argued that $T(\vec{v})$ and $T(\psi(\vec{v}))$ must
both contain all such items. Claim 3.1 therefore implies that
$T(\vec{v})=T(\psi(\vec{v}))$.

Write $F^{\prime}=\times_{i}F^{\prime}_{i}$ for the distribution over
$\psi(\vec{v})$ for $\vec{v}\sim F$. Since $T(\vec{v})=T(\psi(\vec{v}))$ for
all $\vec{q}\sim\vec{s}$ and $\vec{v}\sim F$, the principal generates the same
expected revenue under value distribution $F$ and value distribution
$F^{\prime}$. It therefore suffices to show that the principal’s expected
revenue under $(p,\vec{s})$ with value distribution $F^{\prime}$ is at most
the buyer’s expected truncated social welfare.

Define $Y=M\backslash Z$ for notational convenience, so that $Z$ and $Y$ form
a partition of $M$. Write $Rev(Y)$ for the expected revenue of the principal’s
revenue-optimal menu that sells only items in $Y$, over $\vec{v}\sim
F^{\prime}$ and $\vec{q}\sim\vec{s}$. Write $Wel(Z)$ for the expected welfare
of items in $Z$, again over $\vec{v}\sim F^{\prime}$. We then claim that the
principal’s expected revenue under $(p,\vec{s})$ is at most $Rev(Y)+Wel(Z)$.
claimlemSubsetBound Consider a market with value distribution
$F^{\prime}=\times_{i}F^{\prime}_{i}$ and a partition of the items to sets
$Y,Z\subset{\mathcal{M}}$ ($Y\mathbin{\dot{\cup}}Z={\mathcal{M}}$). For any
menu $p$ of the principal seller, and for any mixed Nash equilibrium $\vec{s}$
in the game $G_{p,F}$, the expected revenue of principal seller under
$(p,\vec{s})$ is at most $Rev(Y)+Wel(Z)$. We note that such a bound on the
seller’s revenue is already known for the case of a monopolist (see [HN17]),
and the proof for the principal seller is very similar; we include the proof
of Section 3.3 in Appendix B for completeness. Now, by Proposition 3.4, the
definition of $Y$, and the fact that $F^{\prime}_{i}=F_{i}$ for all $i\in Y$,
we have $Rev(Y)\leq\sum_{i\in Y}\mathop{{}\mathbb{E}}_{v_{i}\sim
F_{i}}[\min(r_{i},v_{i})]$. From the definition of $F^{\prime}_{i}$ for $i\in
Z$, $Wel(Z)=\sum_{i\in Z}\mathop{{}\mathbb{E}}_{v_{i}\sim
F_{i}}[\min(r_{i},v_{i})]$. Our claim then implies that the principal’s
expected revenue under $(p,\vec{s})$ is at most
$\sum_{i}\mathop{{}\mathbb{E}}_{v_{i}\sim F_{i}}[\min(r_{i},v_{i})]$, as
required. ∎

We note that there are markets in which the principal cannot obtain revenue
that is any constant approximation to the upper bound: a trivial example
illustrating this is a market with only one item, in which the principal
cannot obtain positive revenue, yet the expected truncated social welfare is
positive. Yet, when the principal is able to find a menu with revenue that is
constant approximation to the upper bound, it is clearly a constant
approximation to the optimal revenue of the principal. In the next section we
move to present sufficient conditions for such revenue extraction.

##  4 Approximating Optimal Revenue via Bundle Pricing

In this section we show that under certain conditions on the value
distributions, the principal seller can guarantee expected revenue that is a
constant approximation to the expected truncated social welfare. Moreover,
this can be achieved by a menu that prices only the grand bundle of all items.
As the expected truncated social welfare is an upper bound on the principal’s
revenue (by Theorem 3.3), that simple menu is a constant approximation to the
revenue-maximizing menu for the principal.

We begin by building up some intuition for the conditions we will impose on
the value distributions. Intuitively, selling the items as a single grand
bundle can potentially be a good strategy for the principal when the buyer’s
value for the grand bundle is concentrated (e.g., close to a Gaussian
distribution), and no single item affects the buyer’s value for the bundle to
a significant degree. Such a concentration plays an important role even in the
simpler setting of Monopolist pricing [BILW14], and is guaranteed to occur
when the variance of the buyer’s value for the grand bundle is much larger
than the buyer’s value for any individual item.

However, in our setting, the principal seller faces extra complexity due to
the competing item sellers. Our goal is a revenue guarantee that holds over
all equilibria (similar to the price of anarchy), so we must bound the
principal’s revenue over all outcomes that can occur in item seller
equilibria. Ideally (from the principal’s perspective), each item seller would
set a price that is not too much lower than their highest Myerson price. To
this end, we further analyze item seller best-response strategies by examining
the revenue curve faced by an item seller. Recall from Lemma 3.1 that, given
the principal’s pricing menu $p$, item seller $i$’s revenue under strategy
profile $(s_{1},\cdots,s_{n})$ is equal to

$\displaystyle\mathsf{us}_{i}(p,\vec{s})$
$\displaystyle={\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}\left[\mathsf{Rev}_{F_{i}}(q_{i})\cdot\mathop{{}\mathbb{E}}_{v_{-i}\sim
F_{-i},q_{-i}\sim
s_{-i}}\left[\mathbbm{1}_{i,(\infty,v_{-i})}(p,\vec{q})\right]\right]}$
$\displaystyle=\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}\left[\mathsf{Rev}_{F_{i}}(q_{i})\cdot\mathbb{P}_{v_{-i}\sim
F_{-i},q_{-i}\sim s_{-i}}\left[\max_{T\ni i}\left\\{p(T)-\sum_{j\in T,j\neq
i}\min(v_{j},q_{j})\right\\}\geq q_{i}\right]\right],$

where we recall that $\mathsf{Rev}_{F_{i}}(\cdot)$ is the monopolist revenue
function for item $i$ with value distribution $F_{i}$. If we restrict our
attention to a principal who is using a grand bundling strategy, where
$p(T)=p({\mathcal{M}})$ for all non-empty sets $T$, the above formula can be
simplified to

$\displaystyle\mathsf{us}_{i}(p,\vec{s})=\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}\left[\mathsf{Rev}_{F_{i}}(q_{i})\cdot\mathbb{P}_{v_{-i}\sim
F_{-i},q_{-i}\sim
s_{-i}}\left[p({\mathcal{M}})-q_{i}\geq\sum_{j\in{\mathcal{M}},j\neq
i}\min(v_{j},q_{j})\right]\right].$ (5)

Observe that the first term inside the expectation is just the monopolist
revenue of item seller $i$ when pricing at $q_{i}$, and the second term can be
interpreted as the probability that the buyer does not purchase the grand
bundle from the principal, conditioned on the buyer having value for item $i$
that is at least $q_{i}$. As long as the aggregate variance in the truncated
social welfare is high, the second term will be relatively insensitive to
changes in $q_{i}$. If we additionally assume that item seller $i$’s
monopolist revenue is non-trivially sensitive to large price reductions (i.e.,
well below the highest Myerson price), item seller $i$’s best response price
must be close to their highest Myerson price, which is what we want. This
motivates the following property of value distributions, which we call “price
sensitivity.”

######  Definition 4.1 ((Monopolist) Price Sensitivity).

Let $F_{i}$ be the value distribution of item $i$ and $r_{i}$ be the highest
Myerson price for item $i$. $F_{i}$ is _$(\lambda,C)$ -price sensitive_ for
parameters $C\in(0,1)$ and $\lambda>0$ if for all $\alpha\in[0,C]$ it holds
that $\frac{\mathsf{Rev}_{F_{i}}(r_{i})-\mathsf{Rev}_{F_{i}}(\alpha\cdot
r_{i})}{(1-\alpha)\cdot r_{i}}\geq\lambda$.

Intuitively, the price sensitivity property requires that the revenue curve
$\mathsf{Rev}_{F_{i}}(\cdot)$ decays steeply enough for prices substantially
lower than the highest Myerson price $r_{i}$. A geometric interpretation of
$(\lambda,C)$-price sensitivity is that, over the range $q\in[0,C\cdot
r_{i}]$, the revenue curve $\mathsf{Rev}_{F_{i}}(\cdot)$ lies below a line of
slope $\lambda$ passing through the point
$(r_{i},\mathsf{Rev}_{F_{i}}(r_{i}))$. See Figure 1.

In our main theorem (Definition 4.1) we formally show that large variance and
price sensitivity are sufficient conditions for selling the grand bundle to be
constant revenue-approximating for the principal seller. In this section we
will provide intuitions and discuss the proof outline for Definition 4.1. All
missing proofs in this section can be found in Appendix C.

We define some notations. For $v_{i}\sim F_{i}$ we use $V_{i}(r_{i})$ to
denote the random variable $\min(v_{i},r_{i})$: the value of item $i$
truncated at $r_{i}$. Note that the truncated social welfare is the random
variable $V(\vec{r})=\sum_{i}V_{i}(r_{i})=\sum_{i}\min(v_{i},r_{i})$ where
$v_{i}\sim F_{i}$ for every $i$ and $\vec{r}=(r_{1},...,r_{m})$. The expected
truncated social welfare is simply the mean of $V(\vec{r})$, and we write
$\sigma(V(\vec{r}))$ to denote the standard deviation of $V(\vec{r})$. We use
$\mu_{i}(r_{i})=\mu(V_{i}(r_{i}))$ to denote the mean of $V_{i}(r_{i})$, and
$\sigma_{i}(r_{i})=\sigma(V_{i}(r_{i}))$ to denote the standard deviation of
$V_{i}(r_{i})$. For distributions $F_{1},\ldots,F_{m}$ we define
$K(F_{1},\ldots,F_{m})=\frac{\max_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}{\min_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}$
to be the ratio between the largest and smallest value of
$\left\\{r_{i}-\mu_{i}(r_{i})\right\\}$. Also, for notational convenience, we
will sometimes use $p$ to denote the principal’s price of the grand bundle,
instead of $p({\mathcal{M}})$. We are now ready to state our main result.

theoremthmGeneralPrincipalBundleRev Consider a market with value distribution
$F=\times_{i}F_{i}$. Assume that there exists constant $\lambda>0$ and
$C=1-\frac{\min_{i\in{\mathcal{M}}}F_{i}(r_{i})^{4}}{8K+1}$ where
$K=K(F_{1},\ldots,F_{m})$ such that the value distribution of every item
$i\in{\mathcal{M}}$ is $(\lambda,C)$-price sensitive. In addition, assume
$\sigma(V(\vec{r}))\geq\frac{12}{(\lambda(1-C))^{3/2}}\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}$.
When the principal offers the grand bundle at price
$p=\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},C\cdot
r_{i})]+\frac{\sigma(V(\vec{r}))}{4}$, the revenue of the principal in every
Nash equilibrium of the game $G_{p,F}$ is at least $\frac{1}{3}$ of the
expected truncated social welfare
$\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},r_{i})]$.

We note that as $K=K(F_{1},\ldots,F_{m})$ grows large, $C$ approaches $1$ and
the requirement on the variance $\sigma(V(\vec{r}))$ becomes more demanding.
Thus, conditions that imply that $K$ is not too large are desirable. For
example, when items are i.i.d. we get $K=1$, the best we can hope for. For
non-i.i.d., it will sometimes be beneficial for the principal not to bundle
items that significantly increase $K$, when their removal does not decrease
the expected truncated welfare too much (such pre-processing is simple, and we
do not discuss it further).

###  4.1 Implications

Since the statement of Definition 4.1 is a bit technical, we here discuss two
corollaries of Definition 4.1 that provide simpler sufficient conditions for
our approximation result. In both cases we show that selling the grand bundle
gives a constant approximation to the principal’s optimal revenue when the
number of items is sufficiently large. In the first case, items values are
sampled i.i.d. from a distribution for which the Myerson price is not the
minimal value in the support. In the second case, each (not necessarily
identical) distribution is $\delta$-smooth and $\delta$-revenue-concave
(formally defined in Definition 4.2 and Definition 4.3).

####  4.1.1 I.I.D. Valuations

We start with the i.i.d. case, first looking at a single distribution. [One
Item Distribution, price sensitivity]lemmalemPriceSense Consider some value
distribution $G$, and assume it has a highest Myerson price $r_{G}$. Then $G$
is $(\lambda,C)$-price sensitive for $C=1-\frac{G(r_{G})^{4}}{9}$ and
$\displaystyle\lambda=\lambda(G)=\min_{C^{\prime}\leq
C}\frac{\mathsf{Rev}_{G}(r_{G})-\mathsf{Rev}_{G}(C^{\prime}\cdot
r_{G})}{(1-C^{\prime})\cdot r_{G}}$.

Let $\sigma_{G}(r_{G})$ denote the standard deviation of $\min(v,r_{G})$,
where $v\sim G$. We next show that for a distribution $G$ that is
$(\lambda,C)$-price sensitive and has a highest Myerson price $r_{G}$, the sum
of $m$ i.i.d. samples from distribution $G$ will reach a target minimal
variance threshold $\frac{12}{(\lambda(1-C))^{3/2}}\cdot r_{G}$ if we take $m$
that is large enough. [Independent and Identical Items,
variance]lemmalemIIDVar Consider markets with $m$ i.i.d items, each with value
distribution $F_{i}=G$ that is $(\lambda,C)$-price sensitive and has a highest
Myerson price $r_{G}$. If
$m\geq\frac{144}{\lambda^{3}(1-C)^{3}}\cdot\left\lparen\frac{r_{G}}{\sigma_{G}(r_{G})}\right\rparen^{2}$
then $\sigma(V(\vec{r}))\geq\frac{12}{(\lambda(1-C))^{3/2}}\cdot r_{G}$.

Combining Section 4.1.1, Section 4.1.1 and Definition 4.1 we derive the
following corollary.

[Independent and Identical Items, revenue]corollarycorIIDRev Let $G$ be a
distribution that has a unique Myerson price $r_{G}>inf(G)$. Then for all
sufficiently large $m$ (polynomial in parameters of $G$) and valuation
distribution $F=\times_{i=1}^{m}G=G^{m}$, the principal can find a price for
the grand bundle such that she obtains revenue at least a $\frac{1}{3}$
fraction of the expected truncated social welfare
$\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},r_{i})]$ in every equilibrium of
$G_{p,F}$.

####  4.1.2 Non-I.I.D. Smooth and Revenue-Concave Valuations

For non-i.i.d. distributions, a similar result can be obtained when all item
distributions satisfy the following extra conditions. The following notion
captures a function with negative second derivative bounded away from $0$.

######  Definition 4.2 ($\delta$-revenue-concave).

For $\delta>0$, we say that a distribution $G$ is _$\delta$ -revenue-concave_
if $G$ is twice differentiable, and for revenue function
$h(x):=\mathsf{Rev}_{G}(x)=x\cdot(1-G(x))$, it holds that
$h^{\prime\prime}(x)\leq-\delta/r_{G}$ for all $x\in(0,r_{G})$, where $r_{G}$
is the highest Myerson price of $G$.777Note that $\delta$-revenue-concavity
implies that the Myerson price is unique.

The following notion captures a smooth distribution, where the probability
density function is bounded away from $0$ from below.

######  Definition 4.3 ($\delta$-smooth).

For $\delta>0$, we say that a distribution $G$ is _$\delta$ -smooth_ if $G$ is
differentiable and $G^{\prime}(x)\geq\delta/r_{G}$ for every $x\in(0,r_{G})$,
where $r_{G}$ is the highest Myerson price of $G$.

We now show that when a distribution is $\delta$-revenue-concave and
$\delta$-smooth, we can lower bound the price sensitivity of the distribution
and the variance of truncated welfare, using $\delta$ as a parameter.

[Revenue Concave Distributions, price sensitivity]lemmalemSmoothPriceSense
Consider some value distribution $G$ that for some $\delta>0$ is
$\delta$-revenue-concave. Let $r_{G}$ be the unique Myerson price of $G$. Then
$G$ is $(\lambda,C)$-price sensitive for
$\lambda\leq\frac{\delta}{2}\cdot(1-C)$.

[Smooth Distributions, variance]lemmalemSmoothVariance Consider some value
distribution $G$ supported on $[0,1]$ that is $\delta$-smooth with a highest
Myerson price $r_{G}$. Then the variance of $\min(v,r_{G})$, where $v\sim G$,
is $\Omega(\delta)\cdot(r_{G})^{2}$. Moreover,
$r_{G}-\mathop{{}\mathbb{E}}_{v\sim G}[\min(v,r_{G})]=\Omega(\delta)\cdot
r_{G}$. Definition 4.3 shows that the standard deviation of individual items
whose distribution is $\delta$-smooth is bounded by $\Omega(\delta)$.
Meanwhile, a more detailed reasoning about Definition 4.3 (see a full
discussion in Section C.1) shows that in order to apply Definition 4.1, it is
sufficient for the standard deviation for the buyer’s value of all items to be
$\Theta\left(\mathsf{poly}\left(\frac{1}{\delta},\frac{r_{max}}{r_{min}}\right)\right)$,
where $0<r_{min}\leq r_{max}$ are values such that the interval
$[r_{min},r_{max}]$ contains each item’s highest Myerson price. Taking the
number of items $m$ to be sufficiently large
($m=\mathsf{poly}\left(\frac{1}{\delta},\frac{r_{max}}{r_{min}}\right)$)
ensures the standard deviation constraint in Definition 4.1 is satisfied, and
yields the following corollary. [Revenue Concave Smooth Distributions,
revenue]corollarycorSmoothRev Fix any $r_{max}$, $r_{min}>{0}$. Consider a
market with $m$ items, where each item $i$ has a value distribution $F_{i}$
that is $\delta$-smooth and $\delta$-revenue-concave, with highest Myerson
price $r_{i}\in[r_{min},r_{max}]$. When
$m=\Omega(\mathsf{poly}(\frac{1}{\delta},\frac{r_{max}}{r_{min}}))$, the
principal can sell the grand bundle and obtain revenue at least a
$\frac{1}{3}$ fraction of the expected truncated social welfare
$\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},r_{i})]$ in every equilibrium of
$G_{p,F}$.

###  4.2 Outline of the Proof of Theorem 4.1

##### Additional Notations.

Expanding on the notation of $V_{i}(r_{i})$ that we defined earlier in the
section, we will use $V_{i}(s_{i})$ to denote the random variable
$\min(v_{i},q_{i})$, where $v_{i}\sim F_{i}$ and $q_{i}$ is a random pricing
strategy that is drawn from the item seller $i$’s mixed strategy $s_{i}$. We
will denote $\mu_{i}(s_{i})=\mu(V_{i}(s_{i}))$ and
$\sigma_{i}(s_{i})=\sigma(V_{i}(s_{i}))$ as the mean and standard deviation of
$V_{i}(s_{i})$, respectively. Similarly, we will use $\mu(\vec{s})$ and
$\sigma(\vec{s})$. to represent the mean and standard deviation of
$\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})$, respectively. We also use
$\mu_{-i}(s_{-i})$ and $\sigma_{-i}(s_{-i})$ to represent the mean and
standard deviation of $\sum_{j\neq i}V_{j}(s_{j})$, respectively. For the sake
of simplicity in notation, when item seller $i$’s strategy $s_{i}$ is pure and
pricing at $q_{i}$, we would just use $q_{i}$ to represent $s_{i}$. For
example, $V_{i}(C\cdot r_{i})$ denote the random variable of
$\min(v_{i},C\cdot r_{i})$ when $v_{i}\sim F_{i}$.

##### Preliminary: The Berry-Esseen Theorem

In our proof of the main theorem, we will need to obtain a tight bound on the
following probability term in Equation 5, which can be viewed as the c.d.f of
the sum of $m-1$ independent random variables $V_{j}(s_{j})$.

$\displaystyle\mathbb{P}_{v_{-i}\sim F_{-i},q_{-i}\sim
s_{-i}}\left[p({\mathcal{M}})-q_{i}\geq\sum_{j\in{\mathcal{M}},j\neq
i}\min(v_{j},q_{j})\right]=\mathbb{P}_{v_{-i}\sim
F_{-i}}\left[p({\mathcal{M}})-q_{i}\geq\sum_{j\in{\mathcal{M}},j\neq
i}V_{j}(s_{j})\right].$ (6)

To bound the difference between the distribution of
$\sum_{j\in{\mathcal{M}},j\neq i}V_{j}(s_{j})$ and that of a Gaussian, we will
make extensive use of the Berry-Esseen Theorem, which is stated below.

######  Theorem 4.4 (Berry-Esseen Theorem [Ber41, Ess42]).

Given independent random variables $Y_{1},\cdots,Y_{m}$ with mean $0$, for any
index $j\in[m]$, let $\sigma_{i}$ be the standard deviation of $Y_{i}$, and
let $\rho_{i}=\mathop{{}\mathbb{E}}[|Y_{i}|^{3}]$. Let $\sigma$ be the
standard deviation of $\sum_{i=1}^{m}Y_{i}$
($\sigma^{2}=\sum_{i=1}^{m}\sigma_{i}^{2}$). Then the Kolmogorov–Smirnov
distance between $\frac{\sum_{i}Y_{i}}{\sigma}$ and the standard normal
distribution $\mathcal{N}(0,1)$ is at most
$0.5606\cdot\frac{1}{\sigma}\cdot\max_{i=1}^{m}\frac{\rho_{i}}{\sigma^{2}_{i}}$.

Note that since the Berry-Esseen Theorem requires the random variables of mean
$0$, the theorem will be applied on random variables
$Y_{j}=V_{j}(s_{j})-\mu_{j}(s_{j})$. The probability term in Equation 6 remain
unchanged when $\sum_{j\neq i}\mu_{j}(s_{j})$ is subtracted from both sides of
the inequality “$p({\mathcal{M}})-q_{i}\geq\sum_{j\in{\mathcal{M}},j\neq
i}V_{j}(s_{j})$”.

##### Preserving Variance Between $\min(v_{i},r_{i})$ and $V_{i}(s_{i})$.

When proving our main theorem, we will assume that the buyer’s value for the
bundle has a much higher variance than the highest Myerson price for any item
seller $i$. However, this does not immediately translate into an understanding
of the variance of $\sum_{j\in{\mathcal{M}},j\neq i}V_{j}(s_{j})$, which is
the quantity that we actually need to study. Here we present sufficient
conditions for the mean and variance of $\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})$
to be within a constant factor of the mean and variance of the random variable
$\sum_{j\in{\mathcal{M}}}\min(v_{j},r_{j})$. This will enable us to lower
bound the mean and variance of $\sum_{j\in{\mathcal{M}},j\neq i}V_{j}(s_{j})$
(which is sufficiently close to that of
$\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})$). As a result we obtain tight bounds on
probability distribution of the random variable $\sum_{j\in{\mathcal{M}},j\neq
i}V_{j}(s_{j})$ using the Berry-Esseen Theorem.

Firstly, when $s_{j}$ is lower bounded by $C\cdot r_{i}$ for sufficiently
large $C$ (as specified below), Lemma 4.2 implies that the variance of
$V_{j}(s_{j})$ will be a constant fraction of the variance of
$\min(v_{j},r_{j})$.

lemmacoroConstVarianceBound For any $K\geq 1$ and $C$ such that $C\geq
1-\frac{F_{i}(r_{i})^{4}}{2K+1}$, it holds that $\sigma_{i}^{2}(C\cdot
r_{i})\geq\left\lparen 1-\frac{1}{K}\right\rparen\cdot\sigma_{i}^{2}(r_{i})$.
Even if Section 4.2 is not satisfied for some items, as long as the mean of
$\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})$ is high enough, the variance of
$\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})$ will also constant approximate the
variance of the buyer’s truncated welfare.

lemmalemHighMeanVar For any $C\geq
1-\frac{\min_{i\in{\mathcal{M}}}F_{i}(r_{i})^{4}}{8K+1}$, where
$K=K(F_{1},\ldots,F_{m})$ and any item seller strategy profile such that
$\mu(\vec{s})=\sum_{i}\mu_{i}(s_{i})\geq\sum_{i}\mu_{i}(C\cdot r_{i})$, it
holds that
$\sigma^{2}(\vec{s})=\sum_{i}\sigma_{i}^{2}(s_{i})\geq\frac{1}{2}\sum_{i}\sigma^{2}_{i}(r_{i})=\sigma^{2}(\vec{r})$.

Now, we are ready to discuss the proof outline of our main theorem.

##### Proof Outline of Definition 4.1.

When the principal prices the grand bundle at price
$p=\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},C\cdot
r_{i})]+\frac{\sigma(V(\vec{r}))}{4}$, consider any mixed Nash equilibrium
$(s_{1},\cdots,s_{n})$ between the item sellers in $G_{p,F}$. Note that the
principal’s revenue is just equal to $p$ times the probability that the buyer
purchases the grand bundle from the principal. Fix any vector of values
$\vec{v}$. The buyer purchases the grand bundle from the principal if and only
if 1) their value for the bundle $\sum_{i}v_{i}$ is at least $p$ and 2) the
buyer gains more utility from purchasing all items from the principal seller
rather than buying any subset of items from the item sellers. Letting
$q_{i}\sim s_{i}$ be the realized price set by each item seller $i$, we show
that 2) is satisfied when $p<\sum_{i}\min(v_{i},q_{i})$. (Essentially, this
inequality implies that the buyer gains higher utility from purchasing the
principal’s grand bundle than purchasing any subset of items from the item
sellers.) This automatically implies that condition 1) is satisfied as well.
Hence the principal’s revenue is just equal to $p\cdot\mathbb{P}_{\vec{v}\sim
F,\vec{q}\sim\vec{s}}\left[p<\sum_{i}\min(v_{i},q_{i})\right]$.

To show that this revenue is high, note that since $K\geq 1$ (by definition),
it holds that $C=1-\frac{\min_{i\in{\mathcal{M}}}F_{i}(r_{i})^{4}}{8K+1}\geq
1-\frac{1}{8+1}=\frac{8}{9}$. Hence $p\geq
C\cdot\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},r_{i})]\geq\frac{8}{9}\cdot\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},r_{i})]$.
So if it were the case that $\mathbb{P}_{\vec{v}\sim
F,\vec{q}\sim\vec{s}}[p<\sum_{i}\min(v_{i},q_{i})]\geq 1/2$, then the
principal seller achieves a revenue of
$\frac{1}{2}\cdot\frac{8}{9}\cdot\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},r_{i})]$,
which is at least $\frac{4}{9}$ of our revenue benchmark, as required. It
remains to consider the case $\mathbb{P}[p<\sum_{i}\min(v_{i},q_{i})]<1/2$.
Our goal is to show we can still achieve a high approximation ratio to our
revenue benchmark in this case. We show this by proving the following lemma,
which shows that each item seller $i$ would never want to price below $C\cdot
r_{i}$. lemmalemContainedResponse Consider a market with value distribution
$F=\times_{i}F_{i}$. Assume that there exists constant $\lambda>0$ such that
for $C=1-\frac{\min_{i\in{\mathcal{M}}}F_{i}(r_{i})^{4}}{8K+1}$ where
$K=K(F_{1},\ldots,F_{m})$, all items $i\in{\mathcal{M}}$ have value
distributions that are $(\lambda,C)$-price sensitive. In addition, assume the
variance of the buyer’s value for the bundle
$\sigma(V(\vec{r}))\geq\frac{12}{(\lambda(1-C))^{3/2}}\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}$.
Given principal grand bundle price
$p=\sum_{i}\mathop{{}\mathbb{E}}[\min(v_{i},C\cdot
r_{i})]+\frac{\sigma(V(\vec{r}))}{4}$ and item seller equilibrium
$(s_{1},\cdots,s_{n})$ in $G_{p,F}$, if the buyer not purchases the grand
bundle with probability $\geq 1/2$, then the support of each $s_{i}$ is
contained in $[C\cdot r_{i},r_{i}]$.

Section 4.2 is quite technical, so here we summarize the flow of the argument.
First, we show that when the probability of the buyer not purchasing the grand
bundle from the principal is at least $1/2$, then this probability would still
remain relatively large even if one of the sellers (say seller $i$) changes
their pricing strategy arbitrarily. Moreover, we show that unless the
probability of the buyer not purchasing the grand bundle is close to $1$, the
mean of $\sum_{j\neq i}V_{j}(s_{j})$ is high enough to apply Section 4.2, and
hence the variance of $\sum_{j\neq i}V_{j}(s_{j})$ is large enough for the
error term to be sufficiently small when applying the Berry-Esseen Theorem.
Given this limited competitive pressure from the principal and sufficiently
large variance, we apply Berry-Esseen to show that it is strictly suboptimal
for an item seller $i$ to price below $C\cdot r_{i}$. Hence, in the
equilibrium $(s_{1},\cdots,s_{n})$, the support of each item seller $i$’s
strategy $s_{i}$ is contained in $[C\cdot r_{i},r_{i}]$.

Finally, we apply Section 4.2 to argue that $\sum_{j\neq i}V_{j}(s_{j})$ has
high variance, then use the Berry-Esseen Theorem again (plus the fact that
item sellers’ equilibrium prices lie in $[C\cdot r_{i},r_{i}]$ from Lemma 4.2)
to prove that the value of $\mathbb{P}[p<\sum_{i}\min(v_{i},q_{i})]$ must be
at least 0.38. Since $C\geq 8/9$, we conclude that the principal’s revenue is
at least $(0.38)C\geq 1/3$ of the expected truncated welfare.

##  5 Bundling is Not Always Revenue Constant Competitive.

Theorem 4.1 provides conditions under which selling the grand bundle
approximates not only the optimal principal’s revenue, but our relaxed
benchmark of the expected truncated social welfare. Are such these conditions
necessary? Of course, we cannot hope to approximate the expected truncated
social welfare in all settings: for example, if there is only a single good,
the logic of Bertrand competition shows that the principal cannot generate
positive revenue with any menu. But even in this case, selling only the grand
bundle trivially achieves the principal’s optimal revenue (which is $0$). This
leads us to ask: does selling the grand bundle always yield a constant
approximation to the principal’s optimal revenue? We show in this section that
the answer is _no_ : there are markets in which the principal seller cannot
extract high revenue by pricing the grand bundle, yet some other deterministic
menu is able to extract much higher revenue. Thus, it is not always the case
that by simply pricing the grand bundle the principal can approximate the
optimal revenue. Specifically, the market constructed does not have high
enough variance to match the condition on the variance of Theorem 4.1, and
indeed we show that pricing the grand bundle does no provide high revenue in
any NE. On the other hand, the fact that in that market there is no single
item that dominates all other items is shown to be enough for some other menu
to obtain much higher revenue in every equilibrium (by bundling similar items
and pricing those bundles).

######  Theorem 5.1.

There exist $m$-item markets with the following properties: For value
distribution $F=\times_{j=1}^{m}F_{j}$ of that market, there is a principal
menu $p$ such that in any equilibrium strategies $\vec{s}$ for the item
sellers in $G_{p,F}$, the principal revenue is $\Theta(m)$, while for any
grand pricing menu $p^{\prime}$ and any equilibrium strategies for the item
sellers in $G_{p^{\prime},F}$, the revenue of the principal seller is $O(1)$.

To provide some intuition behind Theorem 5.1, recall that in the monopolist
setting the revenue-optimal menu can always be constant-approximated by either
selling the grand bundle only or selling all items separately [BILW14]. In
that result, the ability to sell all items separately is important to capture
revenue in cases where a single item has unexpectedly high realized value. In
contrast, the principal in our setting cannot capture this revenue in the same
way: selling items separately generates no revenue, since this results in
Bertrand competition for each item. This doesn’t immediately imply Theorem
5.1, however, because our upper bound on revenue truncates very high values,
so the scenario with just a single high value is not problematic for
approximating the optimal revenue (i.e., because it is anyway hopeless for the
principal to extract substantial revenue from any one item). However, as it
turns out, there can still be situations where the optimal revenue is driven
by a few high-valued items (more than one, but at most a constant) that
dominate the total welfare. These cases are necessarily rare, and would be
handled by selling items separately in the monopolist setting. But in our
setting, these rare events might be the most important to revenue. By
designing the high-item-value events to occur at different orders of magnitude
for different items, one can construct scenarios where the principal cannot
obtain high revenue by bundling all items together, but could generate high
revenue by bundling together items whose values are at similar scales,
essentially simulating the sell-items-separately solution that would be
employed by a monopolist.

We now describe our construction for Theorem 5.1 that implements the intuition
above. Fix any constant $K>2$; we will prove the claim for $m\gg K^{2}$ that
is even. Let $n=m/2$. In the market we construct there are $n$ pairs of items:
$T_{1},\cdots,T_{n}$. For each $i\in[n]$, set $T_{i}$ contains two items,
sampled i.i.d from the following binary distribution $F_{i}$. The value is
$H_{i}=K^{2\cdot 3^{(i-1)}}$ with probability $x_{i}=K^{-3^{(i-1)}}$, and zero
otherwise. There are $m=2n$ items: for $i\in[n]$, both item ${2i-1}$ and item
${2i}$ are distributed according to $F_{i}$ (so
$F=\times_{i=1}^{m}(F_{i}\times F_{i})$). Observe that for clarity of
exposition the construction uses integer values instead of values in $[0,1]$
(the construction can of course be rescaled to $[0,1]$).

In Section 5.1 we will construct a menu for the principal with revenue
$\Omega(m)$; this will be a partition menu that sets a price on each pair of
items $T_{i}$. Then in Section 5.2 we will show that every grand bundle menu
for the principal generates revenue $O(1)$, competing the proof of Theorem
5.1.

###  5.1 Principal Revenue from Partition Bundles.

Consider a principal pricing strategy that bundle items in each set $T_{i}$
together at price $H_{i}+\varepsilon=K^{2\cdot 3^{(i-1)}}+\varepsilon$. We
will prove that in any item seller equilibrium, the revenue of the principal
is $\Theta(m)$. Intuitively, for each set $T_{i}$, the principal seller is
selling the bundle with probability at most $x_{i}^{2}$. Hence the item
sellers cannot improve their probability of sale by too much by reducing their
price from $H_{i}$ (which is the unique Myerson price for item $i$).
Consequently, each item seller’s price in equilibrium will price at exactly
$H_{i}$. This ensures that when the principal is pricing at
$H_{i}+\varepsilon$, the buyer would purchase the bundle $T_{i}$ from the
principal if they have a high value for both items in $T_{i}$. By our
construction of the example, the principal gets revenue at least $H_{i}\cdot
x_{i}^{2}=1$ for each set $T_{i}$. Adding the revenue over all $n$ sets, the
principal gets revenue at least $n=m/2$. We formalize this in the next claims.
claimpropPerPartitionRev Fix $x<\frac{1}{2}$. Let $D$ be the following binary
distribution supported on $\\{0,H=\frac{1}{x^{2}}\\}$: the value is $H$ with
probability $x$, and $0$ otherwise. Consider a market with buyer value sampled
from $F=D\times D$. Then when the principal sells the bundle of the two items
at $p=H+\varepsilon$ for some sufficiently small $\varepsilon$, there is a
unique NE (in which each item seller prices at $H$), and the revenue of the
principal in this NE is at least $1$.

claimpropPartitionEquilibrium Consider a market with buyer value distribution
$F=\times_{i=1}^{m}(F_{i}\times F_{i})$. Assume the principal seller is using
a partition bundle pricing $p$ over item set ${\mathcal{M}}$, where the
partitioned disjoint sets are $T_{1}$, $\cdots$, $T_{n}$. Then
$(s_{1},\cdots,s_{m})$ is an equilibrium in $G_{p,F}$ if and only if for each
$i\in[n]$, $\\{s_{j}\\}_{j\in T_{i}}$ is an equilibrium for the sub-game
$G_{p(T_{i}),F_{i}\times F_{i}}$ over item set $T_{i}$, where the principal is
posting a bundle price $p(T_{i})$.

We note that the claim above holds more generally: every partition menu
essentially breaks the game between the items sellers to sub-games, one for
each part of the partition, with correspondence between NE in the large game
and in the sub-games. Combining the two claims we conclude:

lemmalemPrevBound There exists a principal pricing strategy $p$ that sells
partitioned bundles $T_{1}$, $\cdots$, $T_{n}$, such that when each pair
$T_{j}$ is priced at $H_{j}+\varepsilon$ there is a unique NE in the game
$G_{p,F}$ and the principal’s revenue of this NE is $\Theta(m)$.

###  5.2 Principal Revenue from Selling the Grand Bundle.

We saw that the principal can obtain revenue of $\Theta(m)$ by a partition
menu. We next show that the revenue by selling the grand bundle is much lower.
Specifically, for any menu of the principal in which the only set offered is
the grand bundle at price $p$, it holds that the revenue of the principal is
$O(1)$ in every equilibrium of $G_{p,F}$. We separate the price range of the
principal seller into three categories: when $p<3\cdot H_{1}$, when $p\geq
3\cdot H_{n}$, and when there exists some $i\in[n-1]$, where $3\cdot H_{i}\leq
p<3\cdot H_{i+1}.$ We will show that in the first case, the principal is
selling at a constant price, resulting in $O(1)$ revenue. In the second case,
the principal’s price is too high and will never sell. The third case (where
the grand bundle price $p$ falls between the high support of set $T_{i}$ and
$T_{i+1}$ for index $i$) is the most interesting. Observe that simple arguing
that the revenue is bounded by $p$ times the probability that the value is at
least $p$ is not enough (e.g., for $p=H_{j}$ that product is at least
$H_{j}\cdot V_{j}=K^{2\cdot 3^{(j-1)}}\cdot K^{-3^{(j-1)}}=K^{3^{(j-1)}}$,
which might be much larger than $m$ for large $j$). We will show that in this
case, the higher value item sellers are incentivized to reduce their price to
a point where the buyer purchases the grand bundle only if they have positive
value for at least two items in $\bigcup_{j=i+1}^{n}T_{j}$. Thus the principal
is in a similar situation as if they are merely selling the set $T_{i+1}$, and
obtains only $O(1)$ revenue.

We will start by considering the expected revenue of a particular item seller
$j\in\bigcup_{k=i+1}^{n}T_{k}$.

proposition claimCopySellerProbabilitySale Assume that $3\cdot H_{i}\leq
p<3\cdot H_{i+1}$ for some $i\in[n-1]$. For any item $j$ in
$\bigcup_{k=i+1}^{n}T_{k}$ and any $q_{j}$ in the support of $s_{j}$, it holds
that $\mathbb{P}[p-q_{j}\geq\sum_{k\neq i}V_{k}(s_{k})]>\left\lparen
1-3\left\lparen x_{i+1}+\frac{1}{p\cdot x_{i}^{2}}\right\rparen\right\rparen$.

The above claim can be viewed as saying conditioned on $s_{j}=q_{j}$ and
$v_{j}\geq q_{j}$, the probability of the buyer not purchasing from the
principal must be at least $1-3(x_{i+1}+\frac{3x_{i}^{2}}{p})$. Notice that
given $p\geq 3\cdot H_{i}$, in order for the buyer to be interested in the
bundle, their value for some item in $\bigcup_{k=i+1}^{n}T_{k}$ must be high.
We can now apply a union bound to bound the probability of the buyer
purchasing the grand bundle, and as a result, the principal seller’s revenue.

lemmalemPrincipalRevPricingAtSI For any grand-bundle menu $p$ such that
$3\cdot H_{n}>p\geq 3\cdot K^{2}$, the revenue of the principal in any NE of
the game $G_{p,F}$ is at most $36$.

Using the above two claims we bound the revenue of any grand-bundle pricing in
any equilibrium by a constant. lemmalemBrevBound For any grand-bundle menu
$p$, the revenue of the principal in any Nash equilibrium of the game
$G_{p,F}$ is $O(1)$.

##  6 Conclusion and Future Work

Our work explores revenue guarantee of the principal seller in a oligopoly
setting, particularly when facing agile item competitors who set the prices of
their items in response to the principal seller’s pricing strategy. We study
the ability of the principal to extract revenue by using her unique power to
price bundles of items.

Our work is by no means comprehensive in this space and we hope we can inspire
future work on auction pricing with competitors. First, on a technical level,
we expect there is ample room to generalize or extend our approximation
result. This could involve establishing other approximation results under
different sufficient conditions on the value distributions, developing
additional upper bounds on the principal seller’s revenue, and/or exploring
the power of more complex bundling strategies.

Another direction for follow-up work is to expand the set of allowable buyer
and/or seller preferences. For example, one could investigate the impact of
non-additive buyer valuations, such as submodular or subadditive valuations.
One could also introduce production costs for the sellers, which might impact
pricing and/or entry decisions by the potential competitors.

Yet another direction is to relax our assumptions on the nature of the
competition faced by the principal seller. For example, in our model the item
sellers set prices independently at equilibrium. However, it is also natural
to consider item sellers who collude with each other in the way they set
prices, either explicitly or via algorithmic collusion due to using similar
off-the-shelf pricing algorithms. One could consider separately the cases
where colluding sellers can transfer utility between each other or not. Taking
this one step further, one could also consider competitors who own multiple
items and can offer bundles for the items available to them; this can be
thought of as a form of advanced collusion with both transfers and the ability
to bundle goods.

Finally, our work focuses on revenue maximization from the principal seller’s
perspective. Another related angle of inspection is the buyer’s surplus:
namely, how much does the buyer’s surplus improve, relative to the monopolist
case, if the principal seller has item competitors for some or all items? This
could have implications for policy considerations such as antitrust concerns,
where one might seek to understand the extent to which item sellers serve as
effective competition for a dominant principal seller.

## References

  * [ADR13] Alessandro Avenali, Anna D’Annunzio, and Pierfrancesco Reverberi.  Bundling, competition and quality investment: a welfare analysis.  Review of Industrial Organization, 43:221–241, 2013.
  * [AV10] Mark Armstrong and John Vickers.  Competitive non-linear pricing and bundling.  The Review of Economic Studies, 77(1):30–60, 2010.
  * [BCWZ17] Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao.  Approximating gains from trade in two-sided markets via simple mechanisms.  In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, pages 589–590, 2017\.
  * [Ber41] Andrew C Berry.  The accuracy of the gaussian approximation to the sum of independent variates.  Transactions of the american mathematical society, 49(1):122–136, 1941.
  * [BILW14] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg.  A simple and approximately optimal mechanism for an additive buyer.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 21–30, 2014.
  * [BW19] Hedyeh Beyhaghi and S. Matthew Weinberg.  Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items.  In Proceedings of the 51st ACM Symposium on Theory of Computing Conference (STOC), 2019.
  * [CDW16] Yang Cai, Nikhil Devanur, and S. Matthew Weinberg.  A duality based unified approach to bayesian mechanism design.  In Proceedings of the 48th ACM Conference on Theory of Computation(STOC), 2016.
  * [Che97] Yongmin Chen.  Equilibrium product bundling.  Journal of business, pages 85–103, 1997.
  * [CS21] Linda Cai and Raghuvansh R. Saxena.  99% revenue with constant enhanced competition.  In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 224–241. ACM, 2021\.
  * [CZ17] Yang Cai and Mingfei Zhao.  Simple mechanisms for subadditive buyers via duality.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 170–183, 2017.
  * [DDT14] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos.  The Complexity of Optimal Mechanism Design.  In the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014\.
  * [DDT17] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos.  Strong duality for a multiple-good monopolist.  Econometrica, 85(3):735–767, 2017.
  * [DW17] Nikhil R. Devanur and S. Matthew Weinberg.  The optimal mechanism for selling to a budget constrained buyer: The general case.  In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, pages 39–40, 2017\.
  * [EFF+17a] Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg.  The competition complexity of auctions: A bulow-klemperer result for multi-dimensional bidders.  In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, page 343, 2017.
  * [EFF+17b] Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg.  A simple and approximately optimal mechanism for a buyer with complements: Abstract.  In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, page 323, 2017.
  * [Ess42] Carl-Gustav Esseen.  On the liapunov limit error in the theory of probability.  Ark. Mat. Astr. Fys., 28:1–19, 1942.
  * [FLLT18] Hu Fu, Christopher Liaw, Pinyan Lu, and Zhihao Gavin Tang.  The value of information concealment.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2533–2544, 2018.
  * [HN12] Sergiu Hart and Noam Nisan.  Approximate Revenue Maximization with Multiple Items.  In the 13th ACM Conference on Electronic Commerce (EC), 2012.
  * [HN13] Sergiu Hart and Noam Nisan.  The menu-size complexity of auctions.  In the 14th ACM Conference on Electronic Commerce (EC), 2013.
  * [HN17] Sergiu Hart and Noam Nisan.  Approximate revenue maximization with multiple items.  J. Economic Theory, 172:313–347, 2017.
  * [HR15] Sergiu Hart and Philip J. Reny.  Maximizing Revenue with Multiple Goods: Nonmonotonicity and Other Observations.  Theoretical Economics, 10(3):893–922, 2015.
  * [KRK20] Araz Khodabakhshian, Guillaume Roels, and Uday S Karmarkar.  Competitive bundling in a bertrand duopoly.  Working Paper, 2020.
  * [LP18] Siqi Liu and Christos-Alexandros Psomas.  On the competition complexity of dynamic mechanism design.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2008–2025, 2018.
  * [LY13] Xinye Li and Andrew Chi-Chih Yao.  On revenue maximization for selling multiple independently distributed items.  Proceedings of the National Academy of Sciences, 110(28):11232–11237, 2013.
  * [Man13] Andrea Mantovani.  The strategic effect of bundling: A new perspective.  Review of Industrial Organization, 42:25–43, 2013.
  * [MV07] A. M. Manelli and D. R. Vincent.  Multidimensional Mechanism Design: Revenue Maximization and the Multiple-Good Monopoly.  Journal of Economic Theory, 137(1):153–185, 2007.
  * [Nal04] Barry Nalebuff.  Bundling as an entry barrier.  The Quarterly Journal of Economics, 119(1):159–187, 2004.
  * [Pav11] Gregory Pavlov.  Optimal mechanism for selling two goods.  The B.E. Journal of Theoretical Economics, 11(3), 2011.
  * [SYZ22] Jie Shuai, Huanxing Yang, and Lan Zhang.  Dominant firm and competitive bundling in oligopoly markets.  Games and Economic Behavior, 132:421–447, 2022.
  * [Tha04] John Thanassoulis.  Haggling over substitutes.  Journal of Economic Theory, 117:217–245, 2004.
  * [Vic05] John Vickers.  Abuse of market power.  The Economic Journal, 115(504):F244–F261, 2005.
  * [Whi89] Michael D Whinston.  Tying, foreclosure, and exclusion, 1989.

##  Appendix A Illustration for Price Sensitivity.

Figure 1: $(\lambda,C)$-Price Sensitive Revenue Curve. For distribution
$F_{i}$, the revenue function
$\mathsf{Rev}(q_{i})=q_{i}\cdot(1-F_{i}(q_{i}))$, must be below the line with
slope $\lambda$ that passes through $(r_{i},\mathsf{Rev}(r_{i}))$ for every
price below $C\cdot r_{i}$, where $r_{i}$ is the maximal Myerson price for
$F_{i}$.

##  Appendix B Omitted Proofs in Section 3

*

###### Proof.

The set $T$ maximizes $\mathsf{diff}_{\vec{v}}(T,p,\vec{q})$ and the set
$T^{\prime}$ maximizes
$\mathsf{diff}_{\vec{v}^{\prime}}(T^{\prime},p,\vec{q})$. If $T\neq
T^{\prime}$ then we must have
$\mathsf{diff}_{\vec{v}}(T,p,\vec{q})\geq\mathsf{diff}_{\vec{v}}(T^{\prime},p,\vec{q})$
and
$\mathsf{diff}_{\vec{v}^{\prime}}(T^{\prime},p,\vec{q})\geq\mathsf{diff}_{\vec{v}^{\prime}}(T,p,\vec{q})$,
with at least one of them strict (since we break ties consistently). So in
particular we must have

$\displaystyle\mathsf{diff}_{\vec{v}}(T,p,\vec{q})+\mathsf{diff}_{\vec{v}^{\prime}}(T^{\prime},p,\vec{q})>\mathsf{diff}_{\vec{v}}(T^{\prime},p,\vec{q})+\mathsf{diff}_{\vec{v}^{\prime}}(T,p,\vec{q}).$
(7)

On the other hand, for any $T$ and $T^{\prime}$ with $T\cap S=T^{\prime}\cap
S$, we must have
$\mathsf{diff}_{\vec{v}}(T,p,\vec{q})-\mathsf{diff}_{\vec{v}^{\prime}}(T,p,\vec{q})=\sum_{i\in
T\cap S}(v_{i}-v^{\prime}_{i})=\sum_{i\in T^{\prime}\cap
S}(v_{i}-v^{\prime}_{i})=\mathsf{diff}_{\vec{v}}(T^{\prime},p,\vec{q})-\mathsf{diff}_{\vec{v}^{\prime}}(T^{\prime},p,\vec{q})$.
As this is inconsistent with (7), we conclude that $T=T^{\prime}$ as required.
∎

*

###### Proof.

Fix $q_{-i}$, given $q_{i}<q^{\prime}_{i}$, then for any $T_{i}$ such that
$i\in T_{i}$, the utility difference for the buyer for purchasing from the
item seller side items in $T_{i}$ is just the difference of utility for the
particular item. That is,888Here and elsewhere, we will use $(x)_{+}$ to mean
$\max\\{x,0\\}$.

$\mathsf{ub}_{I,\vec{v}}(T_{i},(q_{i},q_{-i}))-\mathsf{ub}_{I,\vec{v}}(T_{i},(q^{\prime}_{i},q_{-i}))=(v_{i}-q_{i})_{+}-(v_{i}-q^{\prime}_{i})_{+}=(\min(v_{i},q^{\prime}_{i})-q_{i})_{+}.$

On the other hand, for any $T_{\neg i}$ such that $i\not\in{{T_{\neg i}}}$,
there is no utility difference, namely

$\mathsf{ub}_{I,\vec{v}}({{T_{\neg
i}}},(q_{i},q_{-i}))-\mathsf{ub}_{I,\vec{v}}({{T_{\neg
i}}},(q^{\prime}_{i},q_{-i}))=0.$

As
$\mathsf{diff}_{\vec{v}}(T,p,\vec{q})=\mathsf{ub}_{P,\vec{v}}(T,p)-\mathsf{ub}_{I,\vec{v}}(T,\vec{q})$
and
$\mathsf{diff}_{\vec{v}}(T,p,(q^{\prime}_{i},q_{-i}))=\mathsf{ub}_{P,\vec{v}}(T,p)-\mathsf{ub}_{I,\vec{v}}(T,(q^{\prime}_{i},q_{-i}))$,
we conclude that

$\displaystyle\mathsf{diff}_{\vec{v}}(T,p,(q^{\prime}_{i},q_{-i}))=\mathsf{diff}_{\vec{v}}(T,p,(q_{i},q_{-i}))+(\min(v_{i},q^{\prime}_{i})-q_{i})_{+}\quad\text{
for any }T\ni i$ (8)

and

$\displaystyle\mathsf{diff}_{\vec{v}}({{T_{\neg
i}}},p,(q_{i},q_{-i}))=\mathsf{diff}_{\vec{v}}({{T_{\neg
i}}},p,(q^{\prime}_{i},q_{-i}))\quad\text{ for any }{{T_{\neg i}}}\not\ni i.$
(9)

Write $T(q_{i})$ for the set that the buyer purchases from the principal given
$q_{i}$. Note that
$T(q_{i})\in\operatorname*{arg\,max}_{T}\\{\mathsf{diff}_{\vec{v}}(T,p,(q_{i},q_{-i}))\\}$,
with ties broken as per our tie-breaking rule for the buyer. Note also that,
due to our tie-breaking in favor of purchasing more items from item sellers,
we must have $i\in T(0)$ (since if $q_{i}=0$ it is never utility-decreasing
for the buyer to acquire item $i$ from item seller $i$, regardless of what was
purchased from the principal). Define $T_{i}=T(0)$, so that
$\mathsf{diff}_{\vec{v}}(S,p,(0,q_{-i}))\leq\mathsf{diff}_{\vec{v}}(T_{i},p,(0,q_{-i}))$
for all sets $S$. Then for any $S\ni i$ and any $q_{i}$, equation (8) implies

$\displaystyle\mathsf{diff}_{\vec{v}}(S,p,(q_{i},q_{-i}))$
$\displaystyle=\mathsf{diff}_{\vec{v}}(S,p,(0,q_{-i}))+v_{i}-q_{i}$
$\displaystyle\leq\mathsf{diff}_{\vec{v}}(T_{i},p,(0,q_{-i}))+v_{i}-q_{i}$
$\displaystyle=\mathsf{diff}_{\vec{v}}(T_{i},p,(q_{i},q_{-i}))$

and hence (by consistent tie-breaking) if $S=T(q_{i})$ then we must have
$S=T_{i}$. By the same argument, if there exists some $q_{i}>q^{\prime}_{i}>0$
and sets $S,T\not\ni i$ such that $T=T(q_{i})$ and $S=T(q^{\prime}_{i})$, then
we must have $S=T$. We can therefore write $T_{\neg i}$ for the unique set
$T_{\neg i}\not\ni i$ purchased at any choice of $q_{i}$. Finally, since
$\mathsf{diff}_{\vec{v}}(T_{\neg i},p,(q_{i},q_{-i}))$ is independent of
$q_{i}$ whereas $\mathsf{diff}_{\vec{v}}(T_{i},p,(q_{i},q_{-i}))$ is
decreasing, there exists a threshold $\theta_{i}$ such that $T_{i}$ is chosen
for $q_{i}\leq\theta_{i}$ and $T_{\neg i}$ is chosen for $q_{i}>\theta_{i}$. ∎

*

###### Proof.

By Section 3.2 there exist sets $T_{i}\ni i$ and $T_{\neg i}\not\ni i$ and a
threshold $\theta_{i}\geq 0$ such that the set that the buyer purchases from
the principal is $T_{i}$ if $q_{i}\leq\theta_{i}$, and is $T_{\neg i}$ if
$q_{i}>\theta_{i}$. For any $q_{i}>0$, it is utility-maximizing for the buyer
to purchase item $i$ from item seller $i$ precisely if (a) item $i$ is not
purchased from the principal and (b) $v_{i}\geq q_{i}$. We conclude that
$\mathbbm{1}_{i,\vec{v}}(p,\vec{q})=0$ for all
$q_{i}>\max\\{v_{i},\theta_{i}\\}$, and $\mathbbm{1}_{i,\vec{v}}(p,\vec{q})=1$
for all $0<q_{i}<\max\\{v_{i},\theta_{i}\\}$. For the remaining case that
$q_{i}=0$, we note that the buyer will always purchase from the item seller
regardless of what was purchased from the principal. We conclude that
$\mathbbm{1}_{i,\vec{v}}(p,(q_{i},q_{-i}))$ is monotone non-decreasing in
$q_{i}$, as claimed. ∎

*

###### Proof.

Write $Rev(p)$ for the expected revenue under $(p,\vec{s})$. What we will show
is that $Rev(Y)\geq Rev(p)-Wel(Z)$. Indeed, consider the following (direct
revelation) mechanism for the principal to sell the items in $Y$ only. The
principal solicits reported values $v_{i}\sim F_{i}$ for $i\in Y$, then draws
$\tilde{v}_{i}\sim F^{\prime}_{i}$ for $i\in Z$, then executes the mechanism
for $M$ described by price menu $p$. If any item $i\in Z$ is to be allocated
under this mechanism, we instead transfer the simulated value $\tilde{v}_{i}$
to the buyer. This randomized mechanism has expected revenue at least
$Rev(p)-Wel(Z)$, as $Wel(Z)$ is the maximum expected transfer to the buyer.
Furthermore, as the only randomization is in the simulation of
$\tilde{v}_{i}$, we can derandomize by choosing the revenue-maximizing choice
of $\tilde{v}$ (since the mechanism is dominant strategy incentive compatible,
as there is only a single buyer). The resulting deterministic mechanism can be
described as a deterministic menu, so its expected revenue must be at most
$Rev(Y)$. We conclude that $Rev(Y)\geq Rev(p)-Wel(Z)$, as claimed. ∎

##  Appendix C Omitted Proofs in Section 4

###  C.1 Omitted Proofs in Section 4.1

*

###### Proof.

By the definition of $(\lambda,C)$-price sensitivity, $G$ is
$(\lambda,C)$-price sensitive if and only if for $C$ it holds that $\forall
C^{\prime}\in[0,C]$,
$\lambda\leq\frac{\mathsf{Rev}_{G}(r_{G})-\mathsf{Rev}_{G}(C^{\prime}\cdot
r_{G})}{(1-C^{\prime})\cdot r_{G}}$. Clearly $\lambda=\min_{C^{\prime}\leq
C}\frac{\mathsf{Rev}_{G}(r_{G})-\mathsf{Rev}_{G}(C^{\prime}\cdot
r_{G})}{(1-C^{\prime})\cdot r_{G}}$ satisfies this condition. ∎

*

###### Proof.

Since the items are i.i.d, we know that the standard deviation of the buyer’s
truncated value for $m$ items is $\sqrt{m}$ times the standard deviation of
the buyer’s truncated value for one item. Hence
$\sigma(V(\vec{r}))=\sqrt{m}\cdot\sigma_{G}(r_{G})$. When
$m\geq\frac{144}{\lambda^{3}(1-C)^{3}}\cdot\left\lparen\frac{r_{G}}{\sigma_{G}(r_{G})}\right\rparen^{2}$,
$\sqrt{m}\geq\frac{12}{(\lambda(1-C))^{3/2}}\cdot\frac{r_{G}}{\sigma_{G}(r_{G})}$,
and hence
$\sigma(V(\vec{r}))=\sqrt{m}\cdot\sigma_{G}(r_{G})\geq\frac{12}{(\lambda(1-C))^{3/2}}\cdot
r_{G}$. ∎

*

###### Proof.

Since $r_{G}$ is a unique Myerson price, by Section 4.1.1, $G$ is
$(\lambda,C)$-price sensitive for $C=1-\frac{G(r_{G})^{4}}{9}$ and some
$\lambda(G)>0$ (otherwise by the definition of $\lambda(G)$, there must exists
a point on the revenue curve which has the same value as
$\mathsf{Rev}_{G}(r_{G})$, violating the uniqueness assumption). Since
$r_{G}>\inf(G)$, then $1-C=\frac{G(r_{G})^{4}}{9}>0$. Additionally,
$r_{G}>\inf(G)$ ensures that $\sigma_{G}(r_{G})>0$, since there is some
variation in the values. By Section 4.1.1, for $m$ that is polynomial in
$1/G(r_{G})$, $1/\lambda(G)$ and $\sigma_{G}(r_{G})$, the standard deviation
requirement in Definition 4.1 is satisfied, and hence the theorem result
applies. ∎

*

###### Proof.

Since $G$ is $\delta$-revenue-concave, we know that for the revenue function
$h(x)=x\cdot(1-G(x))$, $h^{\prime\prime}(x)\leq-\delta/r_{G}$ by definition.
By the definition of $r_{G}$, $h^{\prime}(r_{G})=0$. Hence for any $q<r_{G}$,

$\displaystyle h^{\prime}(q)\geq
h^{\prime}(q)-h^{\prime}(r_{G})=-\int_{q}^{r_{G}}h^{\prime\prime}(x)\,dx\geq(r_{G}-q)\cdot\frac{\delta}{r_{G}},$

and thus

$\displaystyle h(r_{G})-h(C\cdot r_{G})$ $\displaystyle=\int_{C\cdot
r_{G}}^{r_{G}}h^{\prime}(x)\geq\int_{C\cdot
r_{G}}^{r_{G}}(r_{G}-x)\cdot\frac{\delta}{r_{G}}\,dx=\frac{\delta}{r_{G}}\cdot\left(r_{G}\cdot
x-\frac{1}{2}x^{2}\right)\biggr{|}^{r_{G}}_{C\cdot
r_{G}}=\frac{1}{2}\delta(1-C)^{2}r_{G}.$

Now, by Section 4.1.1$,\lambda=\min_{C^{\prime}\leq
C}\frac{\mathsf{Rev}_{G}(r_{G})-\mathsf{Rev}_{G}(C^{\prime}\cdot
r_{G})}{(1-C^{\prime})\cdot r_{G}}$. Since $G$ is $\delta$-revenue-concave,
$\frac{\mathsf{Rev}_{G}(r_{G})-\mathsf{Rev}_{G}(C^{\prime}\cdot
r_{G})}{(1-C^{\prime})\cdot r_{G}}$ is minimized when $C^{\prime}=C$. Hence

$\displaystyle\lambda=\frac{\mathsf{Rev}_{G}(r_{G})-\mathsf{Rev}_{G}(C\cdot
r_{G})}{(1-C)\cdot r_{G}}=\frac{\frac{1}{2}\delta(1-C)^{2}r_{G}}{(1-C)\cdot
r_{G}}=\frac{\delta}{2}\cdot(1-C).$

∎

*

###### Proof.

Since $G$ is $\delta$-smooth, for any $x\in(0,1)$,
$G^{\prime}(x)\geq\frac{\delta}{r_{G}}$. Hence for any $x\in(0,1)$,
$G(x)=\int_{0}^{x}G^{\prime}(x)\,dx\geq x\cdot\frac{\delta}{r_{G}}$, hence

$\displaystyle r_{G}-\mathop{{}\mathbb{E}}_{v\in
G}[\min(v,r_{G})]=r_{G}-\mu_{G}(r_{G})=\int_{0}^{r_{G}}G(x)\,dx\geq\int_{0}^{r_{G}}x\cdot\frac{\delta}{r_{G}}\,dx\geq\frac{\delta\cdot
r_{G}}{2}.$

Now, we will bound the variance of $V_{G}(r_{G})=\min(v,r_{G})$.

$\displaystyle var(V_{G}(r_{G}))$
$\displaystyle=\mathop{{}\mathbb{E}}[(V_{G}(r_{G})-\mu_{G}(r_{G}))^{2}]\geq\int_{0}^{r_{G}}G^{\prime}(x)\cdot(x-\mu_{G}(r_{G}))^{2}\,dx$
$\displaystyle\geq\int_{0}^{r_{G}}\frac{\delta}{r_{G}}\cdot(x-\mu_{G}(r_{G}))^{2}\,dx=\frac{\delta}{r_{G}}\cdot\frac{1}{3}\left(x-\mu_{G}(r_{G})\right)^{3}\biggr{|}_{0}^{r_{G}}$
$\displaystyle=\frac{\delta}{3r_{G}}\left(\cdot(r_{G}-\mu_{G}(r_{G}))^{3}+\mu_{G}(r_{G})^{3}\right)$
$\displaystyle\geq\frac{\delta}{3r_{G}}\cdot\frac{(r_{G})^{3}}{4}=\frac{\delta\cdot(r_{G})^{2}}{12}.$

The first to second line is by the bound on $G^{\prime}(x)$, the second to
third line is just by evaluating the integral, and the third to forth line is
by minimizing the convex function $(r_{G}-x)^{3}+x^{3}$. ∎

*

###### Proof.

Observe that $r_{G}-\mathop{{}\mathbb{E}}_{v\sim
G}[\min(v,r_{G})]=\Omega(\delta)\cdot r_{G}$ and that $r_{max}\geq r_{G}\geq
r_{min}$. This imply that for any $\delta$-smooth distributions
$F_{1},F_{2},\ldots,F_{m}$, for all $i$, it holds that
$K=K(F_{1},F_{2},\ldots,F_{m})\leq\frac{r_{max}}{\Omega(\delta)\cdot
r_{min}}$. Note that by $\delta$-smoothness, $F_{i}(r_{i})\geq\delta$. Thus
for the choice of $C$ in Definition 4.1,
$1-C=\min_{i\in{\mathcal{M}}}\frac{F_{i}^{4}(r_{i})}{8K+1}=\Omega(\delta^{5}\cdot\frac{r_{min}}{r_{max}})$.
Hence by Definition 4.3, every distribution $F_{i}$ is $(\lambda,C)$-price
sensitive for
$\lambda=\frac{\delta}{2}(1-C)=\Omega(\delta^{6}\cdot\frac{r_{min}}{r_{max}})$.

By Definition 4.3, the variance of each distribution $F_{i}$ is
$\Omega(\delta\cdot r_{min}^{2})$. In order to satisfy the standard deviation
requirement in Definition 4.1, the variance for $m$ items must be at least

$\displaystyle\frac{144\cdot r^{2}_{max}}{\lambda^{3}(1-C)^{3}}=\frac{144\cdot
r^{2}_{max}}{\Omega(\delta^{6}\cdot\frac{r_{min}}{r_{max}})^{3}\cdot\Omega(\delta^{5}\cdot\frac{r_{min}}{r_{max}})}=O\left(\left(\frac{1}{\delta}\right)^{23}\cdot\left(\frac{r_{max}}{r_{min}}\right)^{4}\cdot
r^{2}_{max}\right).$

Hence for some
$m=\Omega\left(\left(\frac{1}{\delta}\right)^{24}\cdot\left(\frac{r_{max}}{r_{min}}\right)^{6}\right)=\mathsf{poly}\left(\frac{1}{\delta},\frac{r_{max}}{r_{min}}\right)$,
the variance of $m$ items satisfy the requirements in Definition 4.1. We can
now apply Definition 4.1 to get the bound on principal revenue. ∎

###  C.2 Omitted Proofs in Section 4.2

For the reader’s convenience, we reiterate the notations used in this section.

For $v_{i}\sim F_{i}$ we use $V_{i}(r_{i})$ to denote the random variable
$\min(v_{i},r_{i})$: the value of item $i$ truncated at $r_{i}$. Note that the
truncated social welfare is the random variable
$V(\vec{r})=\sum_{i}V_{i}(r_{i})=\sum_{i}\min(v_{i},r_{i})$ where $v_{i}\sim
F_{i}$ for every $i$ and $\vec{r}=(r_{1},...,r_{m})$. The expected truncated
social welfare is simple the mean on $V(\vec{r})$, and we write
$\sigma(V(\vec{r}))$ to denote the standard deviation of the truncated social
welfare $V(\vec{r})$. We use $\mu_{i}(r_{i})=\mu(V_{i}(r_{i}))$ to denote the
mean of $V_{i}(r_{i})$, and $\sigma_{i}(r_{i})=\sigma(V_{i}(r_{i}))$ to denote
the standard deviation of $V_{i}(r_{i})$.

Expanding on the notation of $V_{i}(r_{i})$ that we defined earlier in the
section, we will use $V_{i}(s_{i})$ to denote the random variable
$\min(v_{i},q_{i})$, where $q_{i}$ is a random pricing strategy that is drawn
from the item seller $i$’s mixed strategy $s_{i}$. We will denote
$\mu_{i}(s_{i})=\mu(V_{i}(s_{i}))$ and
$\sigma_{i}(s_{i})=\sigma(V_{i}(s_{i}))$ as the mean and standard deviation of
$V_{i}(s_{i})$, respectively. Similarly, we will use $\mu(\vec{s})$ and
$\sigma(\vec{s})$. to represent the mean and standard deviation of
$\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})$, respectively. We also use
$\mu_{-i}(s_{-i})$ and $\sigma_{-i}(s_{-i})$ to represent the mean and
standard deviation of $\sum_{j\neq i}V_{j}(s_{j})$, respectively. For the sake
of simplicity in notation, when item seller $i$’s strategy $s_{i}$ is pure and
pricing at $q_{i}$, we would just use $q_{i}$ to represent $s_{i}$. For
example, $V_{i}(C\cdot r_{i})$ denote the random variable of
$\min(v_{i},C\cdot r_{i})$ when $v_{i}\sim F_{i}$.

For distributions $F_{1},\ldots,F_{m}$ we define
$K(F_{1},\ldots,F_{m})=\frac{\max_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}{\min_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}$
to be the ratio between the largest and smallest value of
$\left\\{r_{i}-\mu_{i}(r_{i})\right\\}$. Also, for notational convenience, we
will sometimes use $p$ to denote the principal’s price of the grand bundle,
instead of $p({\mathcal{M}})$.

######  Claim C.1.

For any $1\geq C>0$ and item seller $i$’s strategy $s_{i}$ such that
$\inf(s_{i})\geq C\cdot r_{i}$, it holds that
$\sigma_{i}^{2}(s_{i})\geq\left\lparen 1-\frac{2(1-C)}{C\cdot
F_{i}(r_{i})^{4}}\right\rparen\cdot\sigma_{i}^{2}(r_{i})$.

###### Proof.

By the definition of variance,
$\sigma_{i}(r_{i})^{2}=\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]-\mu_{i}(r_{i})^{2}$
and
$\sigma_{i}(s_{i})^{2}=\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]-\mu_{i}(s_{i})^{2}$.
We can assume WLOG that $s_{i}$ is supported on $[0,r_{i}]$, because if it is
support on values that are larger than $r_{i}$, then truncating these values
at $r_{i}$ will only make the variance the $V_{i}(s_{i})$ smaller.

Since all support of $s_{i}$ is at most $r_{i}$,
$\mathop{{}\mathbb{E}}[V_{i}(s_{i})]\leq\mathop{{}\mathbb{E}}[V_{i}(r_{i})]$
and thus
$\mathop{{}\mathbb{E}}[V_{i}(s_{i})]^{2}\leq\mathop{{}\mathbb{E}}[V_{i}(r_{i})]^{2}$.
Therefore

$\displaystyle\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(s_{i})$
$\displaystyle=(\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]-\mathop{{}\mathbb{E}}[V_{i}(r_{i})]^{2})-(\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]-\mathop{{}\mathbb{E}}[V_{i}(s_{i})]^{2})$
$\displaystyle\leq\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]-\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]\leq(\mathbb{P}[q_{i}\leq
v_{i}<r_{i}]+\mathbb{P}[r_{i}\leq v_{i}])\cdot(r_{i}^{2}-q_{i}^{2}).$

The rest of our proof will bound
$\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]-\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]$
from above, as well as $\sigma_{i}^{2}(r_{i})$ from below. This will help us
establish a relationship between $\sigma_{i}^{2}(s_{i})$ and
$\sigma_{i}^{2}(r_{i})$.

Let $q_{i}=\inf(s_{i})$. We can write out
$\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]$ as the weighted sum over conditional
probabilities using the law of total probability over events $0\leq
V_{i}(r_{i})\leq q_{i}$, $q_{i}\leq V_{i}(r_{i})\leq r_{i}$ and $r_{i}\leq
V_{i}(r_{i})$. Note that when $V_{i}(r_{i})<r_{i}$,
$V_{i}(r_{i})=\min(v_{i},r_{i})$ is really just equal to $v_{i}$. Meanwhile,
when $V_{i}(r_{i})\geq r_{i}$, $V_{i}(r_{i})=r_{i}$. Hence we have

$\displaystyle\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]$
$\displaystyle=\mathbb{P}[0\leq
v_{i}<q_{i}]\cdot\mathop{{}\mathbb{E}}[v_{i}^{2}|v_{i}\leq
q_{i}]+\mathbb{P}[q_{i}\leq
v_{i}<r_{i}]\cdot\mathop{{}\mathbb{E}}[v_{i}^{2}|q_{i}\leq v_{i}\leq
r_{i}]+\mathbb{P}[r_{i}\leq v_{i}]\cdot r_{i}^{2}$
$\displaystyle\leq\mathbb{P}[0\leq
v_{i}<q_{i}]\cdot\mathop{{}\mathbb{E}}[v_{i}^{2}|v_{i}\leq
q_{i}]+\mathbb{P}[q_{i}\leq v_{i}]\cdot r_{i}^{2}$ (10)

Since $q_{i}=\inf(s_{i})$, we know that
$\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]\geq\mathop{{}\mathbb{E}}[V_{i}(q_{i})^{2}]$.
Using the law of total probability again, we get

$\displaystyle\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]\geq\mathop{{}\mathbb{E}}[V_{i}(q_{i})^{2}]$
$\displaystyle=\mathbb{P}[0\leq
v_{i}<q_{i}]\cdot\mathop{{}\mathbb{E}}[v_{i}^{2}|v_{i}\leq
q_{i}]+\mathbb{P}[q_{i}\leq v_{i}]\cdot q_{i}^{2}$ (11)

By subtracting Equation 11 from Equation 10, we get:

$\displaystyle\Rightarrow\mathop{{}\mathbb{E}}[V_{i}(r_{i})^{2}]$
$\displaystyle-\mathop{{}\mathbb{E}}[V_{i}(s_{i})^{2}]\leq\mathbb{P}[q_{i}\leq
v_{i}]\cdot(r_{i}^{2}-q_{i}^{2}).$

Since $r_{i}$ is a Myerson price, it maximizes the function
$x\cdot\mathbb{P}[x\leq v_{i}]$. Hence for any $w$, $\mathbb{P}[v_{i}\geq
w]\leq\frac{r_{i}\cdot\mathbb{P}[r_{i}\leq v_{i}]}{w}$. Since $q_{i}\geq
C\cdot r_{i}$, it must be the case that

$\displaystyle\mathbb{P}[q_{i}\leq
v_{i}]\leq\frac{r_{i}\cdot\mathbb{P}[r_{i}\leq v_{i}]}{C\cdot
r_{i}}=\frac{1}{C}\cdot\mathbb{P}[r_{i}\leq v_{i}].$

Therefore

$\displaystyle\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(s_{i})$
$\displaystyle\leq\frac{1}{C}\cdot\mathbb{P}[r_{i}\leq
v_{i}]\cdot(r_{i}^{2}-q_{i}^{2})\leq\frac{1}{C}\cdot\mathbb{P}[r_{i}\leq
v_{i}]\cdot(r_{i}^{2}-(C\cdot r_{i})^{2})$
$\displaystyle=\frac{1}{C}\cdot\mathbb{P}[r_{i}\leq
v_{i}]\cdot(1-C)\cdot(1+C)\cdot
r_{i}^{2}\leq\frac{1}{C}\cdot\mathbb{P}[r_{i}\leq v_{i}]\cdot 2(1-C)\cdot
r_{i}^{2}.$

The last line is by $C\leq 1$.

Finally, we also bound $\sigma_{i}^{2}(r_{i})$. The variance
$\sigma_{i}^{2}(r_{i})$ can be written as the expectation of
$(V_{i}(r_{i})-\mu_{i}(r_{i}))^{2}$. By the law of total expectation,

$\displaystyle\sigma_{i}^{2}(r_{i})\geq\mathbb{P}[r_{i}\leq
v_{i}]\cdot(r_{i}-\mu_{i}(r_{i}))^{2},$

where

$\displaystyle\mu_{i}(r_{i})$
$\displaystyle=\int_{0}^{r_{i}}\mathbb{P}[v_{i}\geq v]\,dv$
$\displaystyle\leq\int_{0}^{r_{i}}\min\left(\frac{\mathbb{P}[r_{i}\leq
v_{i}]\cdot r_{i}}{v},1\right)\,dv$
$\displaystyle\leq\int_{0}^{\mathbb{P}[r_{i}\leq v_{i}]\cdot
r_{i}}1\cdot\,dv+\int_{\mathbb{P}[r_{i}\leq v_{i}]\cdot
r_{i}}^{r_{i}}\frac{\mathbb{P}[r_{i}\leq v_{i}]\cdot r_{i}}{v}\,dv$
$\displaystyle\leq\mathbb{P}[r_{i}\leq v_{i}]\cdot
r_{i}\cdot\left(1+\log\left(\frac{1}{\mathbb{P}[r_{i}\leq
v_{i}]}\right)\right).$

For the above equation, the first to second line is by the fact that $r_{i}$
is the myerson price, a monopolist pricing at $v$ will get $\mathbb{P}[v\leq
v_{i}]\cdot v\leq\mathbb{P}[r_{i}\leq v_{i}]\cdot r_{i}$, the second to fourth
line are by expanding the terms and calculating the integral. Thus

$\displaystyle r_{i}-\mu_{i}(r_{i})\geq r_{i}-\mathbb{P}[r_{i}\leq v_{i}]\cdot
r_{i}\cdot\left\lparen 1+\log\left(\frac{1}{\mathbb{P}[r_{i}\leq
v_{i}]}\right)\right\rparen\geq\left(1-\mathbb{P}[r_{i}\leq
v_{i}]\cdot\left\lparen 1+\log\left(\frac{1}{\mathbb{P}[r_{i}\leq
v_{i}]}\right)\right\rparen\right)\cdot r_{i}.$

By examining the Taylor expansion of $1-\mathbb{P}[r_{i}\leq
v_{i}]\cdot\left\lparen 1+\log\left(\frac{1}{\mathbb{P}[r_{i}\leq
v_{i}]}\right)\right\rparen$ at $\mathbb{P}[r_{i}\leq v_{i}]=1$, we get that
for any $\mathbb{P}[r_{i}\leq v_{i}]\in(0,1]$,

$\displaystyle 1-\mathbb{P}[r_{i}\leq v_{i}]\cdot\left\lparen
1+\log\left(\frac{1}{\mathbb{P}[r_{i}\leq
v_{i}]}\right)\right\rparen\geq(1-\mathbb{P}[r_{i}\leq v_{i}])^{2}/2.$ (12)

Thus

$\displaystyle\sigma_{i}^{2}(r_{i})\geq\mathbb{P}[r_{i}\leq
v_{i}]\cdot(r_{i}-\mu_{i}(r_{i}))^{2}\geq\mathbb{P}[r_{i}\leq v_{i}]\cdot
r_{i}^{2}\cdot(1-\mathbb{P}[r_{i}\leq v_{i}])^{4}/4=\mathbb{P}[r_{i}\leq
v_{i}]\cdot r_{i}^{2}\cdot F_{i}(r_{i})^{4}/4.$

From both bounds on $\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(s_{i})$ and
$\sigma_{i}^{2}$ itself, we conclude that

$\displaystyle\frac{\sigma_{i}(r_{i})^{2}-\sigma_{i}^{2}(s_{i})}{\sigma_{i}(r_{i})^{2}}\leq\frac{\mathbb{P}[r_{i}\leq
v_{i}]\cdot r_{i}^{2}\cdot\frac{2(1-C)}{C}}{\mathbb{P}[r_{i}\leq v_{i}]\cdot
r_{i}^{2}\cdot F_{i}(r_{i})^{4}}=\frac{2(1-C)}{C\cdot F_{i}(r_{i})^{4}},$

and thus $\sigma_{i}^{2}(s_{i})\geq\left\lparen 1-\frac{2(1-C)}{C\cdot
F_{i}(r_{i})^{4}}\right\rparen\cdot\sigma_{i}^{2}(r_{i})$. ∎

*

###### Proof.

Since $C\geq 1-\frac{F_{i}(r_{i})^{4}}{2K+1}$, then $2(1-C)\leq
2\cdot\frac{F_{i}(r_{i})^{4}}{2K+1}$. Meanwhile, $C\geq
1-\frac{F_{i}(r_{i})^{4}}{2K+1}\geq 1-\frac{1}{2K+1}=\frac{2K}{2K+1}$. Hence

$\displaystyle\frac{2(1-C)}{C\cdot(1-\mathbb{P}[r_{i}\leq
v_{i}])^{4}}\leq\frac{2\cdot\frac{F_{i}(r_{i})^{4}}{2K+1}}{\frac{2K}{2K+1}\cdot
F_{i}(r_{i})^{4}}=\frac{1}{K},$

and thus $1-\frac{2(1-C)}{C\cdot F_{i}(r_{i})^{4}}\geq 1-\frac{1}{K}$.
Plugging above inequality into C.1 yields our corollary. ∎

######  Lemma C.2.

Let $\inf(s_{i})$ be the infinum of the support of $s_{i}$, then

$\displaystyle\frac{\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(q_{i})]}{2(\inf(s_{i})-\mu_{i}(\inf(s_{i}))}\geq\mu_{i}(r_{i})-\mu_{i}(s_{i})\geq\frac{\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(s_{i})}{2(r_{i}-\mu_{i}(r_{i}))}$

###### Proof.

Firstly, consider the case where $s_{i}$ is a pure strategy at $q_{i}$. Then,

$\displaystyle\mu_{i}(q_{i})=\mathop{{}\mathbb{E}}[V_{i}(q_{i})]=\int_{0}^{q_{i}}1-F_{i}(x)\,dx$

and

$\displaystyle\sigma_{i}^{2}(q_{i})=\mathop{{}\mathbb{E}}[V_{i}^{2}(q_{i})]-\mu_{i}^{2}(q_{i})$
$\displaystyle=\int_{0}^{q_{i}^{2}}1-F_{i}(\sqrt{x})dx-\mu_{i}^{2}(q_{i})$
$\displaystyle=\int_{0}^{q_{i}}(1-F_{i}(x))\cdot 2x\,dx-\mu_{i}^{2}(q_{i}).$

Note that although the action space of the item sellers are confined to
multiples of $\varepsilon$, for the purpose of this lemma we will consider the
derivative of $\mu_{i}(q_{i})$ and $\sigma^{2}(q_{i})$ over the domain
$[0,1]$. Our derivative computation is purely a technical tool for our proof.

Now, we can compute the derivatives of both $\mu_{i}(q_{i})$ and
$\sigma^{2}(q_{i})$ to see the rate of change of these quantities when a price
reduction at $q_{i}$ occurs.

$\displaystyle\derivative{\mu_{i}(q_{i})}{q_{i}}=1-F_{i}(q_{i})$

and

$\displaystyle\derivative{\sigma_{i}^{2}(q_{i})}{q_{i}}$
$\displaystyle=(1-F_{i}(q_{i}))\cdot
2q_{i}-2\mu_{i}(q_{i})\cdot(1-F_{i}(q_{i}))$
$\displaystyle=(1-F_{i}(q_{i}))\cdot(2q_{i}-2\mu_{i}(q_{i})).$

Let $\mathsf{rem}(q_{i})=q_{i}-u_{i}(q_{i})$, then

$\displaystyle\mathsf{rem}(q_{i})=\int_{0}^{q_{i}}1\,dx-\int_{0}^{q_{i}}1-F_{i}(x)\,dx=\int_{0}^{q_{i}}F_{i}(x)\,dx.$

Clearly, $\mathsf{rem}(q_{i})$ is monotonically non-decreasing in $q_{i}$.
Moreover, from our computation,
$\derivative{\sigma_{i}^{2}(q_{i})}{q_{i}}=\mathsf{rem}(q_{i})\cdot\derivative{\mu_{i}(q_{i})}{q_{i}}$.
Now we can use this formula to rewrite the difference between variance of
$V_{i}(q_{i})$ and $V_{i}(r_{i})$, and bound this difference using the
difference in mean.

$\displaystyle\sigma^{2}(r_{i})-\sigma^{2}(q_{i})=\int_{q_{i}}^{r_{i}}\derivative{\sigma_{i}^{2}(x)}{q_{i}}\,dx=\int_{q_{i}}^{r_{i}}2\cdot\mathsf{rem}(x)\cdot\derivative{\mu_{i}(x)}{x}\,dx.$

By the fact that $\mathsf{rem}(x)$ is monotonically non-decreasing,
$\mathsf{rem}(x)$ is at most $\mathsf{rem}(r_{i})$ and at least
$\mathsf{rem}(q_{i})$. Hence

$\displaystyle\int_{q_{i}}^{r_{i}}2\cdot\mathsf{rem}(x)\cdot\derivative{\mu_{i}(x)}{x}\,dx\geq
2\mathsf{rem}(r_{i})\int_{q_{i}}^{r_{i}}\derivative{\mu_{i}(x)}{x}\,dx=2\mathsf{rem}(r_{i})\cdot(\mu(r_{i})-\mu(q_{i})).$

Similarly,

$\displaystyle\int_{q_{i}}^{r_{i}}2\cdot\mathsf{rem}(x)\cdot\derivative{\mu_{i}(x)}{x}\,dx\leq\mathsf{rem}(q_{i})\cdot(\mu(r_{i})-\mu(q_{i}))$

Hence for a pure strategy $q_{i}$, our theorem statement holds

$\displaystyle\frac{\sigma^{2}(r_{i})-\sigma^{2}(q_{i})}{\mathsf{rem}(q_{i})}\geq\mu(r_{i})-\mu(q_{i})\geq\frac{\sigma^{2}(r_{i})-\sigma^{2}(q_{i})}{\mathsf{rem}(r_{i})}.$

For randomized strategy $s_{i}$, the left part of the equation holds by taking
expectation over $q_{i}\sim s_{i}$:

$\displaystyle\mu_{i}(r_{i})-\mu_{i}(s_{i})=\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\mu_{i}(r_{i})-\mu_{i}(s_{i})]\leq\frac{\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(q_{i})]}{2(\inf(s_{i})-\mu_{i}(\inf(s_{i}))}.$

For the right part of the equation, we simply use the fact that

$\displaystyle\sigma_{i}^{2}(s_{i})=\mathop{{}\mathbb{E}}[V_{i}^{2}(s_{i})]-\mu_{i}^{2}(s_{i})$
$\displaystyle=\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\mathop{{}\mathbb{E}}[V_{i}^{2}(q_{i})]]-(\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\mu_{i}(q_{i})])^{2}$
$\displaystyle\geq\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\mathop{{}\mathbb{E}}[V_{i}^{2}(q_{i})]]-\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}\left[\mu_{i}(q_{i})^{2}\right]=\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\sigma_{i}^{2}(q_{i})].$

Hence

$\displaystyle\mu_{i}(r_{i})-\mu_{i}(s_{i})\geq\frac{\mathop{{}\mathbb{E}}_{q_{i}\sim
s_{i}}[\sigma^{2}(r_{i})-\sigma^{2}(q_{i})]}{\mathsf{rem}(r_{i})}\geq\frac{\sigma^{2}(r_{i})-\sigma_{i}^{2}(s_{i})}{r_{i}-\mu_{i}(r_{i})}.$

∎

######  Claim C.3.

For any $C\geq 1-\frac{F_{i}(r_{i})^{4}}{8K+1}$ where $K\geq 1$, it holds that
$C\cdot r_{i}-\mu_{i}(C\cdot
r_{i})\geq\frac{4}{5}\cdot(r_{i}-\mu_{i}(r_{i}))$.

###### Proof.

Again, let $\mathsf{rem}(C\cdot r_{i})=C\cdot r_{i}-\mu_{i}(C\cdot r_{i})$ and
$\mathsf{rem}(r_{i})=r_{i}-\mu_{i}(r_{i})$. Let
$\mathsf{Rev}_{i}(r_{i})=r_{i}\cdot(1-F_{i}(r_{i}))$. Since $r_{i}$ is the
Myerson price, for any $x\in[0,1]$,
$x(1-F_{i}(x))\leq\mathsf{Rev}_{i}(r_{i})$, hence $F_{i}(x)\geq
1-\frac{\mathsf{Rev}_{i}(r_{i})}{x}$. As we have discussed in Lemma C.2

$\displaystyle\mathsf{rem}(C\cdot r_{i})=\int_{0}^{C\cdot r_{i}}F_{i}(x)\,dx$
$\displaystyle\geq\int_{0}^{C\cdot
r_{i}}\max\left(0,1-\frac{\mathsf{Rev}_{i}(r_{i})}{x}\right)\,dx$
$\displaystyle\geq\int_{\mathsf{Rev}_{i}(r_{i})}^{C\cdot
r_{i}}1-\frac{\mathsf{Rev}_{i}(r_{i})}{x}\,dx$

When $x\geq r_{i}\cdot(1-F_{i}(r_{i})^{4})$,

$\displaystyle 1-\frac{\mathsf{Rev}_{i}(r_{i})}{x}\geq
1-\frac{r_{i}\cdot(1-F_{i}(r_{i}))}{r_{i}\cdot(1-F_{i}(r_{i})^{4})}\geq
1-\frac{1}{1+F_{i}(r_{i})}\geq\frac{F_{i}(r_{i})}{2}.$

Given that $C\geq 1-\frac{F_{i}(r_{i})^{4}}{2K+1}$,

$\displaystyle\int_{\mathsf{Rev}_{i}(r_{i})}^{C\cdot
r_{i}}1-\frac{\mathsf{Rev}_{i}(r_{i})}{x}\geq\int_{r_{i}\cdot(1-F_{i}(r_{i})^{4})}^{C\cdot
r_{i}}\frac{F_{i}(r_{i})}{2}$ $\displaystyle\geq\left\lparen
r_{i}\cdot\left\lparen 1-\frac{F_{i}(r_{i})^{4}}{2K+1}\right\rparen-
r_{i}\cdot\left\lparen
1-F_{i}(r_{i})^{4}\right\rparen\right\rparen\cdot\frac{F_{i}(r_{i})}{2}$
$\displaystyle=r_{i}\cdot\left\lparen
1-\frac{1}{2K+1}\right\rparen\cdot\frac{F_{i}(r_{i})^{5}}{2}.$

Meanwhile, $\mathsf{rem}(r_{i})-\mathsf{rem}(C\cdot r_{i})=\int_{C\cdot
r_{i}}^{r_{i}}F_{i}(x)\,dx$. Since it’s always true that $F_{i}(x)\leq
F_{i}(r_{i})$,

$\displaystyle\mathsf{rem}(r_{i})-\mathsf{rem}(C\cdot
r_{i})\leq(1-C)r_{i}\cdot F_{i}(r_{i})\leq\frac{F_{i}(r_{i})^{5}}{2K+1}.$

Since $K\geq 4$, we conclude that

$\displaystyle\frac{\mathsf{rem}(r_{i})}{\mathsf{rem}(C\cdot
r_{i})}=1+\frac{\mathsf{rem}(r_{i})-\mathsf{rem}(C\cdot
r_{i})}{\mathsf{rem}(C\cdot r_{i})}$ $\displaystyle\leq
1+\frac{\frac{F_{i}(r_{i})^{5}}{2K+1}}{\left\lparen
1-\frac{1}{2K+1}\right\rparen\cdot\frac{F_{i}(r_{i})^{5}}{2}}$
$\displaystyle\leq 1+\frac{1/9}{(1-1/9)\cdot 1/2}=1+1/4=5/4.$

This yields our claim. ∎

*

###### Proof.

By Lemma C.2, we know that

$\displaystyle\sigma^{2}(\vec{r})-\sigma^{2}(\vec{s})=\sum_{i\in{\mathcal{M}}}\left\lparen\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(s_{i})\right\rparen$
$\displaystyle\leq\sum_{i\in{\mathcal{M}}}2(r_{i}-\mu_{i}(r_{i}))\cdot(\mu_{i}(r_{i})-\mu_{i}(s_{i}))$
$\displaystyle\leq
2\max_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}\cdot\left\lparen\sum_{i\in{\mathcal{M}}}\mu_{i}(r_{i})-\sum_{i\in{\mathcal{M}}}\mu_{i}(s_{i})\right\rparen.$

By our assumption in the lemma,
$\sum_{i\in{\mathcal{M}}}\mu_{i}(s_{i})\geq\sum_{i}\mu_{i}(C\cdot r_{i})$.
Hence

$\displaystyle\sum_{i\in{\mathcal{M}}}\mu_{i}(r_{i})-\sum_{i\in{\mathcal{M}}}\mu_{i}(s_{i})\leq\sum_{i\in{\mathcal{M}}}\mu_{i}(r_{i})-\sum_{i\in{\mathcal{M}}}\mu_{i}(C\cdot
r_{i})=\sum_{i\in{\mathcal{M}}}(\mu_{i}(r_{i})-\mu_{i}(C\cdot r_{i})).$

Now, again by Lemma C.2,

$\displaystyle\sum_{i\in{\mathcal{M}}}(\mu_{i}(r_{i})-\mu_{i}(C\cdot r_{i}))$
$\displaystyle\leq\sum_{i\in{\mathcal{M}}}\frac{\sigma_{i}^{2}(r_{i})-\sigma_{i}^{2}(C\cdot
r_{i})}{2(C\cdot r_{i}-\mu_{i}(C\cdot r_{i}))}$
$\displaystyle\leq\frac{1}{2(\min_{i\in{\mathcal{M}}}\left\\{C\cdot
r_{i}-\mu_{i}(C\cdot
r_{i})\right\\})}\cdot\left\lparen\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})-\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(C\cdot
r_{i})\right\rparen.$

Note that our choice of $C$ satisfies the conditions in C.3, hence for all
$i\in{\mathcal{M}}$, $C\cdot r_{i}-\mu_{i}(C\cdot
r_{i})\geq\frac{4}{5}\cdot(r_{i}-\mu_{i}(r_{i}))$, and hence

$\displaystyle\sum_{i\in{\mathcal{M}}}(\mu_{i}(r_{i})-\mu_{i}(C\cdot
r_{i}))\leq\frac{5}{8(\min_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\})}\cdot\left\lparen\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})-\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(C\cdot
r_{i})\right\rparen.$

Plugging our choice of $C$ into Section 4.2, we get

$\displaystyle\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(C\cdot
r_{i})\geq\left(1-\frac{1}{K}\right)\cdot\sigma_{i}^{2}(r_{i}),$

hence

$\displaystyle\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})-\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(C\cdot
r_{i})\leq\frac{1}{K}\cdot\sigma_{i}^{2}(r_{i}).$ (13)

We conclude that

$\displaystyle\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})-\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(s_{i})$
$\displaystyle\leq\frac{2\max_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}{8/5\cdot\min_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}\cdot\frac{1}{K}\cdot\sigma_{i}^{2}(r_{i})$
$\displaystyle\leq\frac{2\max_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}{8/5\cdot\min_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}\cdot\frac{1}{4\cdot\frac{\max_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}{\min_{i\in{\mathcal{M}}}\left\\{r_{i}-\mu_{i}(r_{i})\right\\}}}\cdot\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})\leq\frac{1}{2}\cdot\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i}),$

and hence

$\displaystyle\sigma^{2}(\vec{s})=\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(s_{i})\geq\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})-\frac{1}{2}\cdot\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})=\frac{1}{2}\cdot\sum_{i\in{\mathcal{M}}}\sigma_{i}^{2}(r_{i})=\sigma^{2}(\vec{r}).$

∎

*

###### Proof.

Recall from our discussion in Section 3 (in particular, Equation 4), given the
principal is selling the grand bundle at price $p$ and other item sellers $j$
are using strategies $s_{j}$, item seller $j$ gets the following expected
revenue for pricing at $q_{i}$:

$\displaystyle\mathsf{us}_{i}(p,(q_{i},s_{-i}))=q_{i}\cdot\mathbb{P}[V_{i}(r_{i})\geq
q_{i}]\cdot\mathbb{P}[p-q_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})]=\mathsf{Rev}_{i}(q_{i})\cdot\mathbb{P}[p-q_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})].$

Assume the buyer chooses to buy the grand bundle with probability $<1/2$ when
item seller $i$ uses strategy $s_{i}$. Then

$\displaystyle\mathbb{P}[p\geq\sum_{j\neq
i}V_{j}(s_{j})]\geq\mathbb{P}[p\geq\sum_{j}V_{j}(s_{j})]\geq 1/2.$

We will show that in this case, pricing below $C\cdot r_{i}$ is a strictly
dominated strategy for item seller $i$. In particular, we will prove that for
any $\alpha\in[0,C)$,

$\displaystyle\mathsf{us}_{i}(p,(\alpha\cdot
r_{i},s_{-i}))<\mathsf{us}_{i}(p,(r_{i},s_{-i})).$ (14)

Pluggin in the formula for $\mathsf{us}_{i}(\cdot)$, Equation 14 is equivalent
to

$\displaystyle\frac{\mathbb{P}[p-r_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})]}{\mathbb{P}[p-\alpha\cdot r_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})]}\geq\frac{\mathsf{Rev}_{i}(\alpha\cdot
r_{i})}{\mathsf{Rev}_{i}(r_{i})}$

We know by all value distribution being $(\lambda,C)$-price sensitive that for
any $\alpha<C$, $\mathsf{Rev}_{i}(r_{i})-\mathsf{Rev}_{i}(\alpha\cdot
r_{i})\geq\lambda(1-\alpha)\cdot r_{i}$, and hence
$\frac{\mathsf{Rev}_{i}(\alpha\cdot r_{i})}{\mathsf{Rev}_{i}(r_{i})}\leq
1-\lambda(1-\alpha)$. Thus for our lemma, it is sufficient to prove that

$\displaystyle\frac{\mathbb{P}[p-r_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})]}{\mathbb{P}[p-\alpha\cdot r_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})]}\geq 1-\lambda(1-\alpha).$ (15)

When $\mathbb{P}[p-r_{i}\geq\sum_{j\neq i}V_{j}(s_{j})]\geq
1-\lambda(1-\alpha)$, above equation is automatically satisfied. Now we will
mainly focus on the case where $\mathbb{P}[p-r_{i}\geq\sum_{j\neq
i}V_{j}(s_{j})]<1-\lambda(1-\alpha)$. In this case, we will prove that the
standard deviation of the random variables $\sum_{j\neq i}V_{j}(s_{j})$s are
large, specifically, $\sigma_{-i}(s_{-i})=\sqrt{\sum_{j\neq
i}\sigma_{j}^{2}(s_{j})}\geq
2\cdot(\frac{1}{\lambda(1-c)}+2)\cdot\max_{i}r_{i}$. We will soon see that
this large standard deviation enables us to argue that item seller $i$’s
ability to affect the probability that the buyer purchases the grand bundle
from the principal is limited.

Let $A=2\cdot(\frac{1}{\lambda(1-c)}+2)$. Assume for contradiction that
$\sigma_{-i}(s_{-i})<A\cdot\max_{i}r_{i}$. We are considering the case that
$\mathbb{P}[p-r_{i}\geq\sum_{j\neq i}V_{j}(s_{j})]<1-\lambda(1-\alpha)$, hence
$\mathbb{P}[p-r_{i}<\sum_{j\neq i}V_{j}(s_{j})]\geq\lambda(1-\alpha)$. Let
$\Delta_{i}=p-r_{i}-\mathop{{}\mathbb{E}}[\sum_{j\neq i}V_{j}(s_{j})]$. By
chebyshev’s inequality, when $\Delta_{i}\geq 0$,

$\displaystyle\lambda(1-\alpha)$ $\displaystyle\leq\mathbb{P}\left[\sum_{j\neq
i}V_{j}(s_{j})>p-r_{i}\right]$ $\displaystyle=\mathbb{P}\left[\sum_{j\neq
i}V_{j}(s_{j})\geq\mathop{{}\mathbb{E}}[\sum_{j\neq
i}V_{j}(s_{j})]+\frac{(p-r_{i}-\mathop{{}\mathbb{E}}[\sum_{j\neq
i}V_{j}(s_{j})])}{\sigma_{-i}(s_{-i})}\cdot\sigma_{-i}(s_{-i})\right]$
$\displaystyle\leq\frac{\sigma_{-i}^{2}(s_{-i})}{\Delta_{i}^{2}}.$

Hence

$\displaystyle\Delta_{i}\leq\frac{\sigma_{-i}(s_{i})}{\sqrt{\lambda(1-\alpha)}}<\frac{A\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}}{\sqrt{\lambda(1-\alpha)}}.$

This means that the difference between the mean of $\sum_{j\neq
i}V_{j}(s_{j})$ and $p-r_{i}$ is small. Specifically,

$\displaystyle\mathop{{}\mathbb{E}}\left[\sum_{j\neq i}V_{j}(s_{j})\right]$
$\displaystyle\geq
p-r_{i}-\frac{A\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}}{\sqrt{\lambda(1-\alpha)}}\geq
p-\left\lparen
1+\frac{A}{\sqrt{\lambda(1-\alpha)}}\right\rparen\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}$
$\displaystyle\geq\sum_{i\in{\mathcal{M}}}\mathop{{}\mathbb{E}}[\min(v_{i},C\cdot
r_{i})]+\frac{\frac{12}{(\lambda(1-C))^{3/2}}\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}}{4}-\left\lparen
1+\frac{A}{\sqrt{\lambda(1-\alpha)}}\right\rparen\cdot\max_{j\in{\mathcal{M}}}\\{r_{j}\\}$
$\displaystyle\geq\sum_{i\in{\mathcal{M}}}\mathop{{}\mathbb{E}}[\min(v_{i},C\cdot
r_{i})].$

Now, this means that
$\mathop{{}\mathbb{E}}\left[\sum_{j\in{\mathcal{M}}}V_{j}(s_{j})\right]=\mathop{{}\mathbb{E}}[\sum_{j\neq
i}V_{j}(s_{j})]+V_{i}(s_{i})\geq\sum_{i\in{\mathcal{M}}}\mathop{{}\mathbb{E}}[\min(v_{i},C\cdot
r_{i})]$. By Section 4.2, we can bound the variance of random variable
$\sum_{j\neq i}V_{j}(s_{j})$:

$\displaystyle\sigma_{-i}^{2}(s_{-i})=\sum_{j\neq
i}\sigma^{2}_{j}(s_{j})=\sum_{j\in{\mathcal{M}}}\sigma^{2}_{j}(s_{j})-\sigma^{2}_{i}(s_{i})$
$\displaystyle\geq\frac{1}{2}\sum_{j\in{\mathcal{M}}}\sigma^{2}_{j}(r_{j})-r_{i}^{2}$