# Buy-Many Mechanisms for Many Unit-Demand Buyers

Shuchi Chawla
UT-Austin
<EMAIL_ADDRESS>Rojin Rezvan
UT-Austin
<EMAIL_ADDRESS>Yifeng Teng
Google Research
<EMAIL_ADDRESS>Christos Tzamos
UW-Madison
<EMAIL_ADDRESS>
###### Abstract

A recent line of research has established a novel desideratum for designing
approximately-revenue-optimal multi-item mechanisms, namely the buy-many
constraint. Under this constraint, prices for different allocations made by
the mechanism must be subadditive implying that the price of a bundle cannot
exceed the sum of prices of individual items it contains. This natural
constraint has enabled several positive results in multi-item mechanism design
bypassing well-established impossibility results.

Our work addresses a main open question from this literature involving the
design of buy-many mechanisms for multiple buyers. Our main result is that a
simple sequential item pricing mechanism with buyer-specific prices can
achieve an $O(\log m)$ approximation to the revenue of any buy-many mechanism
when all buyers have unit-demand preferences over $m$ items. This is the best
possible as it directly matches the previous results for the single-buyer
setting where no simple mechanism can obtain a better approximation. Our
result applies in full generality: even though there are many alternative ways
buy-many mechanisms can be defined for multi-buyer settings, our result
captures all of them at the same time. We achieve this by directly competing
with a more permissive upper-bound on the buy-many revenue, obtained via an
ex-ante relaxation.

##  1 Introduction

Revenue maximization in multi-parameter settings is notoriously challenging.
It is known, for example, that in the absence of strong assumptions on the
buyer’s value distribution, the optimal revenue cannot be approximated within
any finite factor by any mechanism with finite description complexity even for
the simplest possible setting of two items and a single unit-demand buyer [19,
4].

Yet, as Chawla et al. [10] showed, this infinite gap between the revenue of
the optimal mechanism and any simple mechanism arises precisely when the
mechanism offers “super-additive” options that charge for some bundles of
items more than the sum of prices of their individual components. They
proposed an alternate model for revenue maximization to capture situations
where overcharging buyers for certain options is not desirable or feasible.
For example, if the buyer is allowed to participate in the mechanism multiple
times and the mechanism charges for a bundle of two items more than the sum of
the two item prices, the buyer can purchase each item separately to construct
the bundle at a cheaper price. The so-called ”buy-many” constraint indicates
that it shouldn’t be possible for a buyer to improve her utility by combining
together multiple options of the mechanism. Requiring such a constraint
enables positive results even without requiring any assumptions on the buyer’s
valuation function or the value distribution. Chawla et al. [10] showed that
for settings with a single buyer and $m$ items, the optimal revenue obtained
from a buy-many mechanism is no more than $O(\log m)$ times the revenue
obtained from an item pricing. This result holds for arbitrary distributions
over arbitrary valuation functions.

Our work addresses the primary direction left open by Chawla et al. [10] and
its followups, namely extending the buy-many constraint to settings with
multiple buyers. Obtaining such an extension however is challenging as there
is a large number of potential definitions for buy-many mechanisms depending
on the particular implementation of the mechanism and information available to
the buyers.

We start by describing one of the simplest settings in which buyers arrive one
after the other, and each buyer faces a single-buyer mechanism.

#### Sequential Buy-Many Mechanisms

Sequential mechanisms make offers to each buyer sequentially in a pre-
specified order. The $i$-th buyer in the order, is asked to choose which items
to purchase among the subset of items that remain after buyers $1$ through
$i-1$ have made their choices. A natural definition for the buy-many
constraint for this multi-buyer setting boils down to offering a buy-many
constrained mechanism to each buyer for any subset of items remaining, i.e.
the full-mechanism can be defined as a collection of single-buyer mechanisms
$\mathcal{M}_{i,S}\in\textsc{BuyMany}$ for any buyer $i$ and any subset $S$ of
remaining items.

Beyond this simple but somewhat restrictive setting, there are several other
more broad definitions for buy-many mechanisms.

#### Ex-Post Buy-Many Mechanisms

A more flexible design space for multi-buyer buy-many mechanisms is to
consider direct mechanisms in which buyers truthfully submit their valuations
and conditional on the valuations of other buyers each buyer is faced with a
single buyer buy-many mechanism. Buy-many mechanisms for this setting are
specified as a collection of single buyer buy-many mechanisms
$\mathcal{M}_{i,\vec{v}_{-i}}\in\textsc{BuyMany}$ for any buyer $i$ and any
combination of valuation functions $v_{-i}$ for the other buyers.

#### Bayesian Buy-Many Mechanisms

Another potential definition of multi-buyer buy-many mechanisms is to consider
Bayesian settings in which we require the options any single buyer faces to be
buy-many in expectation of the valuations of other buyers. If
$q_{i}(v_{i},\vec{v}_{-i})$ and $p_{i}(v_{i},\vec{v}_{-i})$ is the allocation
and price offered to buyer $i$ when her value is $v_{i}$ and the other buyers
have valuations $\vec{v}_{-i}$, we would require that the single buyer
mechanism with allocation probabilities
$q_{i}(v_{i})\triangleq\mathbb{E}_{\vec{v}_{-i}}q_{i}(v_{i},\vec{v}_{-i})$ and
price
$p_{i}(v_{i})\triangleq\mathbb{E}_{\vec{v}_{-i}}p_{i}(v_{i},\vec{v}_{-i})$ to
satisfy the buy-many constraint.

### An ex-ante relaxation of buy-many revenue

To obtain a comprehensive theory of multi-buyer buy-many mechanisms without
going into the intricacies of specific applications, we avoid choosing any
particular extension of the buy-many constraint, and instead define a
relaxation of the optimal buy-many revenue that simultaneously captures a
broad range of settings. In particular, it encompasses all the aforementioned
examples of sequential buy-many, ex-post buy-many and Bayesian buy-many
mechanisms.

We provide an upper bound on the maximum revenue achievable by buy-many
mechanisms that are agnostic to the specific details of the underlying
setting. In particular, we view multi-buyer settings as a collection of
single-buyer instances via an ex-ante relaxation that allows the mechanism to
allocate each item multiple times as long as the expected number of buyers
each item is allocated to is at most 1. To be specific, let
$\textsc{BuyManyRev}_{i}(x)$ denote the maximum revenue achievable by a
single-buyer mechanism for buyer $i$ that is buy-many (or a distribution over
buy-many mechanisms) and allocates each item $j$ with probability at most
$x_{j}$ over the randomness of buyer $i$’s valuation. Then the following
program gives an upper bound on the revenue of multi-buyer buy-mechanisms:

$\textsc{ExAnte-BuyManyRev}\,:=\,\max_{x_{1},...,x_{n}\geq
0}\sum_{i}\textsc{BuyManyRev}_{i}(x_{i})\text{ such that
}\sum_{i}x_{i}\preceq\mathbf{1}$

Our goal in this work is to design simple multi-buyer mechanisms that are
clearly buy-many but at the same time are competitive with this general upper-
bound given by the ex-ante relaxation.

#### Remark

We remark that in multi-buyer settings, in contrast to the single buyer
setting, the buy-many constraint may not necessarily stem from the buyer’s
ability to visit the mechanism multiple times or submit multiple bids in an
auction. It is unclear what would happen in such a case. Instead, we view the
buy-many constraint as a standalone desideratum for the design of mechanisms
that discourages such behavior and captures buying preferences beyond utility
maximization. Indeed, many buyers faced with super-additive options may be
deterred from choosing them worrying that they will overpay, even if
purchasing multiple options is not possible. Moreover, sellers consistently
offering such options may be considered exploitative as well as leaving
opportunities for side-markets and incentivize buyers to behave non-
truthfully.

### Approximating the buy-many revenue by item pricings

Although buy-many mechanisms can, in general, be quite complicated, we show
that when all buyers are unit-demand, the optimal buy-many revenue (as well as
the ex-ante upper-bound) can be approximated via a simple class of mechanisms,
namely sequential item pricings. We obtain an $O(\log m)$ approximation where
$m$ is the number of items, matching within constant factors the approximation
achieved by Chawla et al. [10] and Briest et al. [4] for single buyer
settings.

######  Theorem 1.1.

For $n$ independent buyers that are unit-demand over $m$ items with value
distribution $\boldsymbol{\mathcal{D}}$,

$\textsc{ExAnte-BuyManyRev}(\boldsymbol{\mathcal{D}})\leq O(\log
m)\textsc{SRev}(\boldsymbol{\mathcal{D}}).$

Here SRev denotes the optimal revenue achievable through sequential item
pricings. A sequential item pricing mechanism interacts with buyers
sequentially in a particular order. It offers to each buyer the set of
remaining items at predetermined item prices and allows the buyer to purchase
any item of her choice. Notably, our approximation result holds for a worst-
case order of arrival of the buyers. Furthermore, the item prices offered to
each buyer are non-adaptive in that prices are computed once at the beginning
of the mechanism before buyer values are instantiated, and do not change based
on instantiated values and purchasing decisions of buyers that arrive earlier
in the ordering. Interestingly, sequential item pricing was previously shown
in [8] to obtain a constant-factor approximation to the overall (non-buy-many)
optimal revenue for unit-demand buyers when buyers’ values are independent
across items.

### Our techniques

Our main approximation result consists of two parts, each of which is of
independent interest. First, we define an ex-ante supply-constrained
relaxation of (distributions over) item pricings, similar to the ex-ante
relaxation of general buy-many mechanisms discussed above. We show that the
ex-ante item pricing revenue provides a logarithmic approximation to the ex-
ante buy-many revenue for unit-demand buyers.

Focusing on ex-ante relaxations allows us to revert back to the single-agent
setting. We extend the logarithmic upper bound on the gap between buy-many and
item pricing revenues proved by [10] to the single buyer setting with a supply
constraint. However, extending [10]’s argument is not straightforward because
it does not provide any control on how the expected allocation of the item
pricing relates to that of the optimal buy-many mechanism. We instead consider
a Lagrangian version of the limited supply setting: in this setting, we are
given a production cost for each item and our goal is to maximize the
mechanism’s profit, namely its revenue minus the expected cost it has to pay
to produce the items it sells. Unfortunately, it turns out that for some cost
vectors, the expected profit of a buy-many mechanism can be an $\Omega(m)$
factor larger than the expected profit of any item pricing. We show instead
that the optimal item pricing profit approximates the profit of an optimal
buy-many mechanism that faces slightly higher (in multiplicative terms)
production costs. This allows us to obtain a logarithmic bound on the gap
between the two ex-ante relaxations.

######  Theorem 1.2.

For any joint value distribution $\boldsymbol{\mathcal{D}}$ over $n$ unit-
demand buyers and $m$ items,

$\textsc{ExAnte-BuyManyRev}(\boldsymbol{\mathcal{D}})\leq O(\log
m)\textsc{ExAnte-SRev}(\boldsymbol{\mathcal{D}}).$

The second part of our argument relates the ex-ante item pricing revenue to
the revenue of a non-adaptive sequential item pricing. This part employs an
argument reminiscent of prophet inequalities and contention resolutions
schemes (see, e.g., Feldman et al. [14]). The key component in our argument is
to show that item pricing revenue exhibits a sort of concavity as a function
of allocation probabilities: given any item pricing $p$ with allocation
probabilities $x$ and any $\alpha<1$, we can find another item pricing that
allocates items with probabilities at most $\alpha x$ and obtains at least an
$\alpha$ fraction of $\mathbf{p}$’s revenue. This allows us to mimic the
allocation probabilities as well as the revenue of the ex-ante item pricing
relaxation within a constant factor.

######  Theorem 1.3.

For any joint value distribution $\boldsymbol{\mathcal{D}}$ over $n$ unit-
demand buyers and $m$ items,

$\textsc{ExAnte-SRev}(\boldsymbol{\mathcal{D}})\leq
2\textsc{SRev}(\boldsymbol{\mathcal{D}}).$

Theorem 1.1 follows immediately from Theorems 1.2 and 1.3. We prove Theorem
1.2 in Section 3 and Theorem 1.3 in Section 4.

### Further related work

The buy-many constraint was first proposed as an alternative to unconstrained
revenue maximization by Briest, Chawla, Kleinberg, and Weinberg [4] in the
context of a single unit-demand buyer. Chawla, Teng, and Tzamos [10] extended
the notion to arbitrary single buyer settings. Chawla, Rezvan, Teng, and
Tzamos [12] present improved approximations for buy-many mechanisms in single
buyer settings where buyers’ values satisfy an additional ordering property
that includes, for example, the so-called FedEx setting. In a different
direction, Chawla, Teng, and Tzamos [11] study the menu size complexity and
revenue continuity of single buyer buy-many mechanisms. All of these works
focus on single buyer problems.

There is extensive literature on approximating the optimal non-buy-many
revenue under various constraints on the buyers’ value distributions in both
single-buyer and multi-buyer settings. Interestingly, many of these
approximation results are achieved through sequential item pricing (or, in
some cases, grand bundle pricing) mechanisms. For example, Chawla, Hartline,
Malec, and Sivan [8] show that for multiple settings of matroid feasibility
constraints, sequential item pricings give a constant approximation to the
optimal non-buy-many revenue. In particular, for multiple unit-demand buyers
with independent values over all items, sequential item pricing gives a
6.75-approximation to the optimal revenue, and this competitive ratio was
improved to 4 by Alaei [1] and generalized to a setting where each item has
multiple units. For buyers with more general distribution, either a sequential
pricing mechanism with personalized item prices or a sequential item pricing
with anonymous prices and entry fee gives a constant approximation to the
optimal revenue when there are multiple fractional subadditive buyers [5] and
an $O(\log\log m)$ approximation when buyers are subadditive [13, 5]. Also see
[7, 9, 20, 19, 21, 3, 24, 22] for some other previous work on using simple
mechanisms to approximate the optimal non-buy-many revenue. For sequential
item pricings to be able to approximate the revenue of the optimal non-buy-
many mechanisms, an important assumption is that each buyer should have
independent item values, which we do not assume in this work.

Finally, ex-ante relaxations, first introduced to multi-buyer mechanism design
by Alaei [1] and Yan [23], have emerged as a powerful tool for simplifying
multi-buyer mechanism design problems by breaking them up into their single-
agent counterparts. For example, Chawla and Miller [6] and Cai and Zhao [5]
employ this approach for designing sequential mechanisms that approximate the
optimal revenue for multiple agents with subadditive values. Such a technique
is also used for analyzing the setting where buyers have non-linear utilities
[2, 16, 17], and determining the revelation gap of the optimal mechanisms [15,
18].

##  2 Definitions

We study the multidimensional mechanism design problem where the seller has
$m$ heterogeneous items to sell to $n$ buyers with independent value
distributions, and aims to maximize the revenue. The buyer $i$’s value vector
over items is specified by a distribution $\mathcal{D}_{i}$ over all value
functions $v_{i}:2^{[m]}\rightarrow\mathbb{R}^{\geq 0}$. Each of these such
functions $v_{i}$ assigns a non-negative value to any subset of items
$S\subseteq[m]$. Let
$\boldsymbol{\mathcal{D}}=\mathcal{D}_{1}\times\cdots\times\mathcal{D}_{n}$
denote the joint distribution over all values.

#### Unit-demand Buyers

In this paper, we focus on the setting where every buyer is unit-demand. We
say that a buyer is unit-demand over all items, if the buyer is only
interested in purchasing one item, and her value for any set of items is
solely determined by the item that is most valuable to her. In other words,
for any set of items $S\subseteq[m]$, $v_{i}(S)=\max\limits_{j\in
S}v_{i}(\\{j\\})$. When the buyer’s identity is clear from the context, we
drop the subscript $i$ and denote $v(\\{j\\})$ by $v_{j}$. We make no
assumptions on each buyer’s value distribution $\mathcal{D}_{i}$ – the buyer’s
values for different items can be arbitrarily correlated.

#### Single-buyer Mechanisms

By the taxation principle, any single-buyer mechanism is equivalent to a menu
of options, and the buyer can select an outcome that maximizes her utility.
Without loss of generality, we can assume that the menu assigns a price to
every randomized allocation, a.k.a. lottery, $\lambda\in\Delta_{m}$, and can
therefore simply represent the mechanism by a pricing function $p$.
$p(\lambda)$ denotes the price of the lottery $\lambda$. For a buyer of type
$v$, her (expected) value for a lottery $\lambda$ is defined by
$v(\lambda):=\sum_{i}v_{i}\lambda_{i}$, and her utility for the lottery is
defined to be $u_{v,p}(\lambda):=v(\lambda)-p(\lambda)$. When $p$ is clear
from the context, we drop the subscript and write the buyer’s utility as
$u_{v}(\lambda)$. Henceforth, we will refer interchangeably to mechanisms as
pricing functions.

Given a pricing function $p$, a buyer of type $v$ chooses the utility-
maximizing lottery, denoted
$\lambda_{v,p}:=\operatorname{arg\,max}_{\lambda}u_{v,p}(\lambda)$. The
buyer’s utility in the mechanism $p$ is given by
$u_{p}(v):=v(\lambda_{v,p})-p(\lambda_{v,p})$; the buyer’s payment is
$\textsc{Rev}_{p}(v):=p(\lambda_{v,p})$. We write the revenue of the mechanism
under buyer distribution $\mathcal{D}$ as
$\textsc{Rev}_{p}(\mathcal{D})=\mathbb{E}_{v\sim\mathcal{D}}\textsc{Rev}_{p}(v)$.
The mechanism is called a buy-one mechanism since the buyer only purchases one
option from the menu.

#### Single-buyer Buy-Many Mechanisms

In single buyer settings, if the buyer is allowed to purchase multiple options
from a mechanism’s menu, we call the mechanism buy-many. In particular, in a
buy-many mechanism the buyer can purchase a (random) sequence of lotteries,
where each lottery in the sequence can depend adaptively on the instantiations
of previous lotteries. At the end of the process, the buyer gets the union of
all allocated items in each step and pays the sum of the prices of all
purchased lotteries.

Any buy-many mechanism can be described by a buy-one pricing function that
satisfies a buy-many constraint. Intuitively, a buy-one pricing function
satisfies the buy-many constraint if the buyer always prefers to purchase a
single option from the menu, even if she has the option to adaptively interact
with the mechanism multiple times.222For formal definitions, see [10]. For
example, for a pricing function $p$, let $\hat{p}_{i}$ denote the minimum cost
of acquiring item $i$ by repeatedly purchasing some lottery until the item is
instantiated. Then, the buy-many constraint implies that for any $\lambda$,
$p(\lambda)\leq\hat{p}\cdot\lambda$. Pricing functions that satisfy the buy-
many constraint are called buy-many pricings, and we use BuyMany to denote the
set of such functions.

Let
$\textsc{BuyManyRev}(\mathcal{D}):=\max_{p\in\textsc{BuyMany}}\textsc{Rev}_{p}(\mathcal{D})$
denote the revenue of the optimal buy-many mechanism for a buyer with value
distribution $\mathcal{D}$.

#### Item Pricings and Sequential Item Pricings

In a single-buyer setting, a (deterministic) item pricing mechanism sets an
item price $p_{j}\in\mathbb{R}_{+}$ for every item $j$; a buyer with value
function $v$ purchases the item $j$ that maximizes $v_{j}-p_{j}$. We use the
price vector $p=(p_{1},\cdots,p_{m})$ to denote the item pricing. Denote by
$\textsc{SRev}(\mathcal{D})$ the optimal revenue obtained by any item pricing
for a buyer with distribution $\mathcal{D}$. We also define random item
pricing mechanisms as distributions over deterministic item pricings; we
continue to use $p$ to denote such pricings, although $p$ is now a random
variable.

A sequential item pricing for a multi-buyer setting specifies a serving order
$\sigma$ being a permutation over the $n$ buyers, and $n$ item pricings
$p_{1},\cdots,p_{n}$, such that at step $i$ the seller posts the pricing
$p_{\sigma(i)}$ to buyer $\sigma(i)$, and the buyer purchases her favorite
among the items that are still available. We use
$\textsc{SRev}(\boldsymbol{\mathcal{D}})$ to denote the optimal revenue
obtained by a sequential item pricing mechanism for buyers with values drawn
from the joint distribution $\boldsymbol{\mathcal{D}}$.

#### Profit Maximization under Production Costs

For a single-buyer setting, we study the profit-maximizing problem of the
seller where each item has a production cost. Let
$c=(c_{1},c_{2},\cdots,c_{m})\in\mathbb{R}_{+}^{m}$ denote the vector of
production costs. Then the profit of the single-buyer mechanism given by
pricing $p$ is defined to be the revenue minus the production costs of the
items:

$\textsc{Profit}_{p,c}(\mathcal{D})=\mathbb{E}_{v\sim\mathcal{D}}[p(\lambda_{v,p})-\lambda_{v,p}\cdot
c].$

We denote by $\textsc{SProfit}_{c}(\mathcal{D})=\max_{\textrm{item pricing
}p}\textsc{Profit}_{p,c}(\mathcal{D})$ the optimal profit achievable by item
pricings for the buyer with distribution $\mathcal{D}$ when there are
production costs $c$ for all items. Similarly define
$\textsc{BuyManyProfit}_{c}(\mathcal{D})=\max_{\textrm{buy-many
}p}\textsc{Profit}_{p,c}(\mathcal{D})$ to be the optimal profit achievable by
buy-many mechanisms for the buyer with distribution $\mathcal{D}$ for the
setting with production costs $c$.

### Ex-ante constrained revenue

Ex-ante relaxations are a powerful technique for reducing multi-buyer
mechanism design problems to their single-buyer counterparts. The key idea is
to relax the ex-post supply constraint on items to an ex-ante feasibility
constraint that requires each item to be sold at most once in expectation.

For the following discussion, we will use $x_{ij}$ to denote the probability
of allocating item $j$ to buyer $i$; $x_{i}=(x_{i1},\cdots,x_{im})$ to denote
the vector of allocations of all items to buyer $i$; and
$x=(x_{1},\cdots,x_{n})$ to denote the (two-dimensional) vector of all
allocations.

We say that a single-buyer pricing function $p_{i}$ satisfies the ex-ante
constraint $x_{i}$ with respect to the value distribution $\mathcal{D}_{i}$ if
for all $j\in[m]$, the expected allocation of item $j$ to the buyer is no more
than $x_{ij}$: $\mathbb{E}_{v\sim\mathcal{D}_{i}}[\lambda_{v,p_{i}}]\leq
x_{i}$. Note that this definition extends to random pricing functions $p$ in
the straightforward manner: we want the expected allocation to be bounded by
$x_{i}$ where the expectation is taken over both the buyer’s value and the
randomness in the mechanism. That is,
$\mathbb{E}_{v\sim\mathcal{D}_{i},p}[\lambda_{v,p_{i}}]\leq x_{i}$.

For a single buyer $i$ and an ex-ante constraint $x_{i}$, we can now define
the optimal revenue that can be obtained from the buyer subject to an ex-ante
constraint for various classes of mechanisms. In particular, let $\Delta_{IP}$
denote the space of all distributions over item pricings, and $\Delta_{BM}$
denote the space of all distributions over buy-many pricings. Then we define:

$\displaystyle\textsc{SRev}(\mathcal{D}_{i},x_{i})$
$\displaystyle=\max_{p\in\Delta_{IP}:\,p\text{ satisfies $x_{i}$ w.r.t.
$\mathcal{D}_{i}$}}\textsc{Rev}_{p}(\mathcal{D}_{i}),$ and,
$\displaystyle\textsc{BuyManyRev}(\mathcal{D}_{i},x_{i})$
$\displaystyle=\max_{p\in\Delta_{BM}:\,p\text{ satisfies $x_{i}$ w.r.t.
$\mathcal{D}_{i}$}}\textsc{Rev}_{p}(\mathcal{D}_{i}).$

Given a combined vector $x$ of ex-ante constraints for every buyer $i\in[m]$,
we can write the collective revenue of the optimal single-buyer mechanisms
that satisfy these constraints as:

$\displaystyle\textsc{EA-SRev}(\boldsymbol{\mathcal{D}},x)$
$\displaystyle=\sum_{i}\textsc{SRev}(\mathcal{D}_{i},x_{i}),$ and,
$\displaystyle\textsc{EA-BuyManyRev}(\boldsymbol{\mathcal{D}},x)$
$\displaystyle=\sum_{i}\textsc{BuyManyRev}(\mathcal{D}_{i},x_{i}),$

Finally, we can define the ex-ante relaxation for each class of mechanisms.

$\displaystyle\textsc{EA-SRev}(\boldsymbol{\mathcal{D}})$
$\displaystyle=\max_{x:\,\sum_{i}x_{ij}\leq 1\forall j\in[m]}\textsc{EA-
SRev}(\boldsymbol{\mathcal{D}},x),$ and, $\displaystyle\textsc{EA-
BuyManyRev}(\boldsymbol{\mathcal{D}})$
$\displaystyle=\max_{x:\,\sum_{i}x_{ij}\leq 1\forall j\in[m]}\textsc{EA-
BuyManyRev}(\boldsymbol{\mathcal{D}},x),$

##  3 Relating the Ex-ante Relaxations

In this section we bound the gap between the ex-ante optimal buy many revenue
and the ex-ante optimal item pricing revenue when the seller faces many unit-
demand buyers. We prove the following theorem.

######  Theorem 3.1.

For any single unit-demand buyer with value distribution $\mathcal{D}$ over
$m$ items and any ex-ante constraint $x\in\Delta_{m}$,

$\textsc{EA-BuyManyRev}(\mathcal{D},x)\leq O(\log m)\textsc{EA-
SRev}(\mathcal{D},x).$

Applying this theorem to each of $n$ buyers, we obtain the following
corollary.

######  Theorem 1.2.

For any joint value distribution $\boldsymbol{\mathcal{D}}$ over $n$ unit-
demand buyers and $m$ items,

$\textsc{EA-BuyManyRev}(\boldsymbol{\mathcal{D}})\leq O(\log m)\textsc{EA-
SRev}(\boldsymbol{\mathcal{D}}).$

Before we present a formal proof of Theorem 3.1, let us describe the main
ideas. Theorem 3.1 is a generalization of Theorem 1.1 from Chawla et al. [10]
for unit-demand buyers, which shows that the ratio of BuyManyRev and SRev is
bounded by $O(\log n)$ in the absence of an ex-ante supply constraint. Our
proof borrows heavily from that previous work. As discussed previously, the
proof technique of Chawla et al. does not lend itself to the ex-ante setting
because it does not provide much control over the allocation probability of
the random item pricing it produces. Indeed, the (random) item pricing it
returns is independent of the buyer’s value distribution, whereas the
allocation probabilities (that are expectations over values drawn from the
distribution) necessarily depend on the value distribution. Instead of
applying the approach of Chawla et al. directly, we first consider a
Lagrangian version of the supply constrained problem.

To simplify the following discussion, we consider a single buyer $i$ and write
the ex-ante buy many and item pricing revenues of this buyer simply as
$\textsc{BuyManyRev}(x)$ and $\textsc{SRev}(x)$ respectively. Viewing
$\textsc{SRev}(x)$ and $\textsc{BuyManyRev}(x)$ as two multi-variate functions
over $x\in\Delta_{m}$, we first observe that for any fixed ex-ante constraint
$x^{o}$, there exists a cost vector $c^{o}$ such that $x^{o}$ is the solution
to the optimization problem $\max_{x}(\textsc{SRev}(x)-c^{o}\cdot x)$. Indeed,
because $\textsc{SRev}(x)$ is concave, $c^{o}=\nabla\textsc{SRev}(x^{o})$ is
such a function. Furthermore, $c^{o}$ is a non-negative vector, and so the gap
between $\textsc{SRev}(x^{o})$ and $\textsc{BuyManyRev}(x^{o})$ is bounded by
the gap between $\textsc{SRev}(x^{o})-c\cdot x^{o}$ and
$\textsc{BuyManyRev}(x^{o})-c\cdot x^{o}$. This motivates studying the
Lagrangian problem of maximizing the profit of a mechanism subject to
production costs $c^{o}$. In particular, for any value distribution
$\mathcal{D}$, we have:

$\max_{x}\frac{\textsc{EA-BuyManyRev}(\mathcal{D},x)}{\textsc{EA-
SRev}(\mathcal{D},x)}\leq\max_{c}\frac{\textsc{BuyManyProfit}_{c}(\mathcal{D})}{\textsc{SProfit}_{c}(\mathcal{D})}$

Unfortunately, the gap on the right hand side can be very large:

######  Theorem 3.2.

There exists a unit-demand value distribution $\mathcal{D}$ over $m$ items and
a cost vector $c\in\mathbb{R}^{m}$, such that
$\textsc{BuyManyProfit}_{c}=\Omega(m)\textsc{SProfit}_{c}(\mathcal{D})$.

We instead provide a bi-criteria approximation for the Lagrangian problem. In
particular, we compare the profit of the optimal item pricing for cost vector
$c$ with the profit of the optimal buy many mechanism with production costs
$2c$. This suffices to imply Theorem 3.1 with a slight worsening in the
approximation factor.

######  Theorem 3.3.

For any single unit-demand buyer with value distribution $\mathcal{D}$ over
$m$-items and production costs vector $c$,

$\textsc{BuyManyProfit}_{2c}(\mathcal{D})\leq 2\ln
4m\,\textsc{SProfit}_{c}(\mathcal{D}).$

The rest of the section is organized as follows. We first show a complete
proof of Theorem 3.1 based on Theorem 3.3. We then describe and verify the gap
example in Theorem 3.2. The proof of Theorem 3.3 is deferred to the appendix.
Each of these components is self-contained.

###  3.1 Proof of Theorem 3.1

###### Proof of Theorem 3.1.

We first note that $\textsc{SRev}(x)$ is a concave function over $x$ because
it optimizes for revenue over random pricings. Fix an ex-ante constraint
$x^{o}$ and consider the function
$g(x):=\textsc{SRev}(x)-x\cdot\nabla\textsc{SRev}(x^{o})$. This function is
maximized at $x=x^{o}$. Furthermore, since $\textsc{SRev}(x)$ is monotone non-
decreasing, $\nabla\textsc{SRev}(x^{o})\geq\mathbf{0}$, and so
$c:=\nabla\textsc{SRev}(x^{o})$ can be thought of as a vector of production
costs. Since $g(x)$ is exactly the profit of an item pricing for buyer
distribution $\mathcal{D}$ with allocation $x$ and production cost vector $c$
for all items, we know that the random item pricing $p$ that achieves
$\textsc{SRev}(x^{o})$ is also the optimal item pricing for a unit-demand
buyer with value distribution $\mathcal{D}$ and item production costs $c$,
without any allocation constraint.333It is possible that $p$ has allocation
$y\leq x^{o}$, with $\textsc{SRev}(y)=\textsc{SRev}(x^{o})$. However, for any
item $i$ such that $y_{i}<x^{o}_{i}$, since
$\textsc{SRev}(y)=\textsc{SRev}(x^{o})$, the gradient
$\nabla\textsc{SRev}(x^{o})$ has value $c_{i}=0$ on the $i$th component. Thus
the profit of item pricing $p$ for the buyer with production costs $c$ is
still $\textsc{SRev}(x^{o})-c\cdot x^{o}$, although the actual allocation is
less than $x^{o}$.

Now consider the buy-many profit optimization problem with production costs
$2c$. The optimal profit is given by $\textsc{BuyManyProfit}_{2c}$.
Restricting attention to buy many mechanisms that satisfy the the ex-ante
constraint $x^{o}$, we let $\textsc{BuyManyProfit}_{2c}(x^{o})$ denote the
optimal profit obtained over that set of mechanisms. Then, we can apply
Theorem 3.3 to obtain:

$\displaystyle\textsc{SRev}(x^{o})$ $\displaystyle=$
$\displaystyle\textsc{SProfit}_{c}(x^{o})+c\cdot x^{o}$ $\displaystyle=$
$\displaystyle\textsc{SProfit}_{c}(\mathcal{D})+c\cdot x^{o}$
$\displaystyle\geq$ $\displaystyle\frac{1}{2\ln
4m}\textsc{BuyManyProfit}_{2c}(\mathcal{D})+c\cdot x^{o}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2\ln 4m}\textsc{BuyManyProfit}_{2c}(x^{o})+c\cdot
x^{o}$ $\displaystyle=$ $\displaystyle\frac{1}{2\ln
4m}(\textsc{BuyManyProfit}_{2c}(x^{o})+2c\cdot x^{o})+c\cdot
x^{o}(1-\frac{1}{\ln 4m})$ $\displaystyle\geq$ $\displaystyle\frac{1}{2\ln
4m}\textsc{BuyManyRev}(x^{o}),$

Here the first line is true by extracting the terms of item costs; the second
line is true since $x=x^{o}$ is optimal for profit under item costs $c$; the
third line is true by Theorem 3.3; the fourth line is true since adding an
allocation restriction cannot increase profit; the last line is true since
$\textsc{BuyManyProfit}_{2c}(x^{o})+2c\cdot
x^{o}\geq\textsc{BuyManyRev}(x^{o})$. This finishes the proof of the theorem.
∎

###  3.2 Proof of Theorem 3.2

###### Proof of Theorem 3.2.

Let $c=(0,m,m,\cdots,m)$. For every $i$ such that $2\leq i\leq m$, let
$v^{(i)}$ be the following unit-demand value function: $v^{(i)}_{1}=2^{i}$;
$v^{(i)}_{i}=m$; $v^{(i)}_{j}=0$ for $j\not\in\\{1,i\\}$. In other words, the
buyer with value $v^{(i)}$ is only interested in two items $1$ and $i$, with
the value for the first item being $2^{i}$, and that for item $i$ being $m$.
Consider the following value distribution $\mathcal{D}$: for every $i$ such
that $2\leq i\leq m$, with probability $2^{-i}$, $v=v^{(i)}$; for the
remaining probability, $v=\mathbf{0}$. Now we analyze $\textsc{SProfit}_{c}$
and $\textsc{BuyManyProfit}_{c}$.

For any item pricing $p$, consider its profit contribution from the first item
and the rest of the items. Since the buyer’s value for the first item forms a
geometric distribution, the profit contribution from the first item is upper
bounded by the revenue of selling only the first item, which is $O(1)$. For
the rest of the items, since when the buyer purchases some item $j>1$, the
item must have a price at most $m=c_{j}$, which means that the profit
contribution of item $j$ is at most 0. Thus $\textsc{SProfit}_{c}=O(1)$.

Consider the following buy-many mechanism: for every $i\geq 2$, there is a
menu entry with allocation $\lambda^{(i)}$ and price
$p^{(i)}=2^{i-1}+\frac{m}{2}$, where
$\lambda^{(i)}_{1}=\lambda^{(i)}_{i}=0.5$. For any $\lambda\in\Delta_{m}$ that
is not some $\lambda^{(i)}$, its price is determined by the cheapest way to
adaptively purchase it with $\lambda^{(2)},\cdots,\lambda^{(m)}$. For every
buyer of type $v^{(i)}$, she buys lottery $(\lambda^{(i)},p^{(i)})$ in the
mechanism with utility 0.444We can reduce the price of $\lambda^{(i)}$ by some
small $\epsilon>0$ to make each buyer type’s utility be strictly positive.
Since item $i$ is only of interest to buyer $v^{(i)}$, the buyer would not
purchase any other set of lotteries in the mechanism. Since profit from buyer
$v^{(i)}$ is $2^{i-1}$, and she gets realized in $\mathcal{D}$ with
probability $2^{-i}$, the expected profit of the buy-many mechanism is
$\Omega(m)$. ∎

##  4 Approximation Via Sequential Item Pricing

We will now focus on item pricings and prove Theorem 1.3. In particular, we
show that non-adaptive sequential item pricings can obtain half of the ex-ante
optimal item pricing revenue, regardless of the order in which buyers are
served.

######  Theorem 1.3.

(Restatement) For any joint distribution
$\boldsymbol{\mathcal{D}}=(\mathcal{D}_{1},\mathcal{D}_{2},\cdots,\mathcal{D}_{n})$
over $n$ buyers and any order $\sigma$ on arrival of buyers, there exists a
deterministic sequential item pricing $q$ with buyers arriving in order
$\sigma$, such that

$\textsc{Rev}_{\mathcal{D}}(q)\geq\frac{1}{2}\textsc{EA-
SRev}(\boldsymbol{\mathcal{D}}).$

Our argument is based loosely around online contention resolution schemes
(OCRS) [14] and prophet inequality arguments. The idea is to start with the
optimal solution to the ex ante item pricing revenue:
$x^{*}:=\operatorname{arg\,max}_{x:\sum_{i}x_{ij}\leq 1\forall
j\in[m]}\sum_{i}\textsc{SRev}(\mathcal{D}_{i},x_{i})$. Then, given some
ordering $\sigma$ over the buyers, we try to mimic this allocation by choosing
pricings for each buyer that ensure that the buyer receives allocation
comparable to $x^{*}_{i}$. As in OCRS, we tradeoff assigning enough allocation
to a buyer with maintaining a good probability that items remain available for
future buyers.

A key difference in our setting relative to work on OCRS is that the latter
mostly focuses on utilitarian objectives, e.g. social welfare, so that the
tradeoff is easily quantified: choosing an alternative with half the
probability of the ex ante optimum, for example, provides half its
contribution to the objective. Chawla et al. [7] show how to apply this
approach to revenue for unit demand buyers with values independent across
items by transforming values to Myersonian virtual values. Unfortunately this
approach does not extend to values correlated across items because in
correlated settings it is not possible to assign virtual values to each
individual value independent of other values.

We develop an alternate argument. For any single unit-demand buyer, we
consider how the item pricing revenue changes as the allocation of the buyer
is decreased from some intended allocation $x^{*}$ to a new allocation $y$
that is component-wise smaller. We show that if $x^{*}$ is realized by item
pricing $p$, then we can realize allocation $y$ while obtaining revenue at
least $y\cdot p$. In particular, uniformly scaling down allocations by some
factor scales down revenue by no more than the same factor. This allows us to
carry out the OCRS-style argument. We formalize the above claim as a lemma
before providing a proof of Theorem 1.3.

In the following discussion, for any unit-demand buyer with value distribution
$\mathcal{D}$, let $\mathbf{x}_{p,S}(\mathcal{D})$ be the allocation vector of
item pricing $p$ over the set of available items $S\subseteq[m]$. We remove
the distribution $\mathcal{D}$ whenever it is clear from the context. When
$S=[m]$, we use $\mathbf{x}_{p}$ instead of $\mathbf{x}_{p,[m]}$.

######  Lemma 4.1.

For any unit-demand buyer, any deterministic item pricing $p$, and any
distribution over set $S$ of available items, let
$x^{*}=\mathbb{E}_{S}[\mathbf{x}_{p,S}]$ be the expected allocations of $p$
conditioned on the available set of items being $S$. Then for any allocation
vector $y\in\Delta_{m}$ such that $y\preceq x^{*}$, there exists a random item
pricing $q$ such that

$\mathbb{E}_{q,S}[\mathbf{x}_{q}(S)]=y,\textrm{ and }\textsc{Rev}_{q,S}=y\cdot
p.$

###### Proof.

We first prove the theorem when both $S$ and $p$ are deterministic. Then, we
extend the proof to the case where the available set $S$ can be possibly
randomized.

For $p=(p_{1},\ldots,p_{m})\in\mathbb{R}_{+}^{m}$ being a deterministic item
pricing, assume that the set of available items is fixed to be some
deterministic set $S$. For any set $T\subseteq S$, define item pricing $p_{T}$
to be the pricing $p$ restricted to items in $T$. In other words,
$p_{T,j}=p_{j}$ for all $j\in T$, and $p_{T,j}=\infty$ otherwise. For ease of
notation, let $x_{T}=\mathbf{x}_{p,T}$ be the allocation under available set
$T$. Observe that for any $j\not\in T$, $x^{*}_{j}=0$ and for any $j\in T$,
$x_{T}(j)\geq x^{*}_{j}$: the latter is true since under the same pricing,
when fewer items are available, buyer types that purchase an item not in $T$
may switch to purchase some item in $T$, while the other buyer types’
incentives remain unchanged. Thus for $y\preceq x^{*}$, $y$ is in the convex
hull of the set of $2^{|S|}$ points $X=\\{x_{T}|T\subseteq S\\}$. Write
$y=\sum_{T\subseteq S}\alpha_{T}x_{T}$ as a convex combination of vectors in
$X$, here $\alpha_{T}\in[0,1]$ for every $T$, and $\sum_{T}\alpha_{T}=1$.
Consider the following randomized item pricing $q$: with probability
$\alpha_{T}$, $q=p_{T}$, $\forall T\subseteq S$. Then the expected allocation
of $q$ is exactly $y$. On the other hand, the expected revenue is
$\textsc{Rev}_{q,S}=p\cdot y$ because whenever item $j$ is sold in $q$, it is
sold at a price of $p_{j}$.

Now let $S$ be a random variable over sets of available items. By defining
$x_{T}=\mathbb{E}_{S}\mathbf{x}_{p,T\cap S}$ to be the expected allocation of
item pricing $p$ under available item set $T\cap S$, the above proof still
goes through. This finishes the proof of the lemma. ∎

With the help of the lemma above, we are now ready to prove Theorem 1.3.

###### Proof of Theorem 1.3.

For every buyer $i$, let $p_{i}$ be the (randomized) item pricing defining
$\textsc{EA-SRev}(\mathcal{D})$, and $x_{i}$ be the corresponding allocation
vector. We may assume $\sigma_{i}=i$ without loss of generality. We build the
desired deterministic sequential item pricing $q$ incrementally for every
buyer. At arrival of buyer $i$, we use the allocation vector $x_{i}$, the
distribution over currently available items (where the randomness comes from
previous buyers and item pricings) and Lemma 4.1 to produce a (randomized)
item pricing vector $q_{i}$ with the property that for $S_{i}$ being the
random set of available items to buyer $i$,

$\mathbb{E}_{q_{i},S_{i}}[x_{q_{i},S_{i}}(\mathcal{D}_{i})]=\frac{x_{i}}{2},\,\text{and,
}\,\mathbb{E}_{q_{i},S_{i}}[\textsc{Rev}_{q_{i}}(\mathcal{D}_{i},S_{i})]=\frac{x_{i}}{2}\cdot
p_{i}=\frac{1}{2}\textsc{EA-SRev}(\mathcal{D}_{i}).$ (1)

Here $\textsc{Rev}_{q_{i}}(\mathcal{D}_{i},S_{i})$ denotes the revenue of item
pricing $q_{i}$ for buyer $i$ conditioned on the available item set being
$S_{i}$ when $i$ arrives. If such $q_{i}$ exists for every $i$, then the
random sequential item pricing $q$ satisfies
$\textsc{Rev}_{\boldsymbol{\mathcal{D}}}(q)\geq\frac{1}{2}\textsc{EA-
SRev}(\boldsymbol{\mathcal{D}})$. Thus there must exist a realization of $q$
being a deterministic sequential item pricing satisfying the requirement of
the theorem.

Now it suffices to show that item pricing $q_{i}$ exists for (1), and the rest
of the proof is dedicated to proving this. An important observation is that if
by induction the item prices $q_{i^{\prime}}$ satisfying (1) exist for every
$i^{\prime}<i$, then every item belongs to $S_{i}$ with probability at least
$\frac{1}{2}$. Such a observation is true by noticing that by union bound, the
allocation of item $j$ in the first $i-1$ steps is at most
$\sum_{i^{\prime}<i}\frac{x_{i^{\prime}j}}{2}\leq\sum_{i^{\prime}\leq
m}\frac{x_{i^{\prime}j}}{2}\leq\frac{1}{2}$ since item $j$ has a total ex-ante
allocation at most 1.

When $p_{i}$ is deterministic, since every element in $[m]$ exists with
probability at least $\frac{1}{2}$ in $S_{i}$, we know that for any realized
buyer type, her favorite item still remains with probability at least
$\frac{1}{2}$ and she would not deviate to purchase something else. Thus
$\mathbb{E}_{p_{i},S_{i}}[\mathbf{x}_{p_{i},S_{i}}]\succeq\frac{1}{2}x_{i}$.
By Lemma 4.1, there exists a random item pricing $q$, such that
$\mathbb{E}_{q,S_{i}}[\mathbf{x}_{q,S_{i}}]=\frac{1}{2}x_{i}$, and
$\mathbb{E}_{q,S_{i}}[\textsc{Rev}_{q,S_{i}}]=\frac{1}{2}x_{i}\cdot
p_{i}=\frac{1}{2}\textsc{EA-SRev}(\mathcal{D}_{i})$. Thus (1) is satisfied.

When $p_{i}$ is random, consider any instantiation of $p_{i}$. The same as the
reasoning in the previous paragraph,
$\mathbb{E}_{p_{i},S_{i}}[\mathbf{x}_{p_{i},S_{i}}]\succeq\frac{1}{2}\mathbf{x}_{p_{i}}$
still holds, and there exists a random item pricing $q_{p_{i}}$ such that
$\mathbb{E}_{q_{p_{i}},S_{i}}[\mathbf{x}_{q_{p_{i}},S_{i}}]=\frac{1}{2}\mathbf{x}_{p_{i}}$,
and
$\mathbb{E}_{q_{p_{i}},S_{i}}[\textsc{Rev}_{q_{p_{i}},S_{i}}]=\frac{1}{2}\mathbf{x}_{p_{i}}\cdot{p_{i}}$.
Consider the following random item pricing $q_{i}$: firstly generate a
realization of random item pricing $p_{i}$, then generate a realization of
random item pricing $q_{p_{i}}$ defined above. The expected allocation of
$q_{i}$ is

$\mathbb{E}_{p_{i}}\mathbb{E}_{q_{p_{i}},S}[\mathbf{x}_{q_{p_{i}},S}]=\frac{1}{2}x_{i},$

while the expected revenue is

$\mathbb{E}_{p_{i}}\mathbb{E}_{q_{p_{i}},S}[\textsc{Rev}_{q_{p_{i}},S}]=\mathbb{E}_{p_{i}}\left[\frac{1}{2}\mathbf{x}_{p_{i}}\cdot
p_{i}\right]=\frac{1}{2}\textsc{EA-SRev}(\mathcal{D}_{i}).$

Thus $q_{i}$ satisfies (1), which finishes the proof of the theorem.

∎

## References

  * Alaei [2014] Saeed Alaei.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  _SIAM Journal on Computing_ , 43(2):930–972, 2014\.
  * Alaei et al. [2013] Saeed Alaei, Hu Fu, Nima Haghpanah, and Jason Hartline.  The simple economics of approximately optimal auctions.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pages 628–637. IEEE, 2013.
  * Babaioff et al. [2014] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg.  A simple and approximately optimal mechanism for an additive buyer.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pages 21–30. IEEE, 2014.
  * Briest et al. [2015] Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg.  Pricing lotteries.  _Journal of Economic Theory_ , 156:144–174, 2015.
  * Cai and Zhao [2017] 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_ , pages 170–183, 2017.
  * Chawla and Miller [2016] Shuchi Chawla and J Benjamin Miller.  Mechanism design for subadditive agents via an ex ante relaxation.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , pages 579–596, 2016.
  * Chawla et al. [2007] Shuchi Chawla, Jason D Hartline, and Robert Kleinberg.  Algorithmic pricing via virtual valuations.  In _Proceedings of the 8th ACM Conference on Electronic Commerce_ , pages 243–251, 2007.
  * Chawla et al. [2010] Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan.  Multi-parameter mechanism design and sequential posted pricing.  In _Proceedings of the forty-second ACM symposium on Theory of computing_ , pages 311–320, 2010.
  * Chawla et al. [2015] Shuchi Chawla, David Malec, and Balasubramanian Sivan.  The power of randomness in bayesian optimal mechanism design.  _Games and Economic Behavior_ , 91:297–317, 2015.
  * Chawla et al. [2019] Shuchi Chawla, Yifeng Teng, and Christos Tzamos.  Buy-many mechanisms are not much better than item pricing.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 237–238, 2019.
  * Chawla et al. [2020] Shuchi Chawla, Yifeng Teng, and Christos Tzamos.  Menu-size complexity and revenue continuity of buy-many mechanisms.  In _Proceedings of the 21st ACM Conference on Economics and Computation_ , pages 475–476, 2020.
  * Chawla et al. [2021] Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos.  Pricing ordered items.  _arXiv preprint arXiv:2106.04704_ , 2021.
  * Dütting et al. [2020] Paul Dütting, Thomas Kesselheim, and Brendan Lucier.  An o(log log m) prophet inequality for subadditive combinatorial auctions.  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 306–317, 2020.  doi: 10.1109/FOCS46700.2020.00037.
  * Feldman et al. [2016] Moran Feldman, Ola Svensson, and Rico Zenklusen.  Online contention resolution schemes.  In _Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms_ , pages 1014–1033. SIAM, 2016.
  * Feng and Hartline [2018] Yiding Feng and Jason D Hartline.  An end-to-end argument in mechanism design (prior-independent auctions for budgeted agents).  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 404–415. IEEE, 2018.
  * Feng et al. [2019] Yiding Feng, Jason D Hartline, and Yingkai Li.  Optimal auctions vs. anonymous pricing: Beyond linear utility.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 885–886, 2019.
  * Feng et al. [2020] Yiding Feng, Jason Hartline, and Yingkai Li.  Simple mechanisms for non-linear agents.  _arXiv preprint arXiv:2003.00545_ , 2020.
  * Feng et al. [2021] Yiding Feng, Jason D Hartline, and Yingkai Li.  Revelation gap for pricing from samples.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1438–1451, 2021.
  * Hart et al. [2013] Sergiu Hart, Noam Nisan, et al.  _The menu-size complexity of auctions_.  Center for the Study of Rationality, 2013.
  * Kleinberg and Weinberg [2012] Robert Kleinberg and Seth Matthew Weinberg.  Matroid prophet inequalities.  In _Proceedings of the forty-fourth annual ACM symposium on Theory of computing_ , pages 123–136, 2012.
  * Li and Yao [2013] 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.
  * Rubinstein and Weinberg [2018] Aviad Rubinstein and S Matthew Weinberg.  Simple mechanisms for a subadditive buyer and applications to revenue monotonicity.  _ACM Transactions on Economics and Computation (TEAC)_ , 6(3-4):1–25, 2018.
  * Yan [2011] Qiqi Yan.  Mechanism design via correlation gap.  In _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , pages 710–719. SIAM, 2011.
  * Yao [2014] Andrew Chi-Chih Yao.  An n-to-1 bidder reduction for multi-item auctions and its applications.  In _Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 92–109. SIAM, 2014.

##  Appendix A Proof of Theorem 3.3

######  Theorem 3.3.

For any single unit-demand buyer with value distribution $\mathcal{D}$ over
$m$-items and production costs vector $c$,

$\textsc{BuyManyProfit}_{2c}(\mathcal{D})\leq 2\ln
4m\,\textsc{SProfit}_{c}(\mathcal{D}).$

###### Proof of Theorem 3.3.

The proof is similar to the proof of Theorem 1.3 in [10] without production
costs. When constructing the item pricing, we need to take the item costs into
consideration.

Let $p$ be the optimal buy-many mechanism under production cost $2c$. Observe
that for any lottery $\lambda\in\Delta_{m}$, without loss of generality we can
assume that $p(\lambda)\geq 2c\cdot\lambda$: otherwise, we can just remove all
menu options with price smaller than production cost, and replace them with
the cheapest way to generate the lottery with the remaining options. This way,
each lottery $\lambda\in\Delta_{m}$ has price at least $2c\cdot\lambda$.
Furthermore, each buyer type that previously purchase some lottery with
production cost larger than the price would deviate to purchase some menu
option with price being at least the production cost, while other buyer types’
incentives remain unchanged, which means the total profit (i.e. payment minus
item costs) does not decrease.

Consider the following item pricing $q$ from $p$: For each item $i$, let

$q_{i}=\min_{\lambda\in\Delta_{m}}\frac{p(\lambda)-c\cdot\lambda}{\lambda_{i}}+c_{i}.$
(2)

In other words, item pricing $q$ is defined by setting the price of each item
$i$ to be the cheapest way to purchase the item, while taking into
consideration the production cost. We further define item pricing $q_{\alpha}$
parameterized by $\alpha\in\mathbb{R}$ to model the degree of influence of the
production costs better:

$q_{\alpha,i}=\alpha c_{i}+(1-\alpha)q_{i}.$

Under such item pricing $q_{\alpha}$, for any buyer with value function $v$,
her utility $u(v,\alpha)$ is

$u(v,\alpha)=\max_{\lambda\in\Delta_{m}}\left(v(\lambda)-\alpha
c\cdot\lambda-(1-\alpha)p(\lambda)\right).$

Let $\lambda_{\alpha}$ be the lottery purchased by buyer $v$ under pricing
$q_{\alpha}$. By the envelope theorem, we have

$\frac{d}{d\alpha}u(v,\alpha)=(p-c)\cdot\lambda_{\alpha}.$

Thus the profit $\textsc{Profit}_{q_{\alpha},c}(v)$ of buyer $v$ under pricing
$q_{\alpha}$ and production cost $c$ is

$\textsc{Profit}_{q_{\alpha},c}(v)=q_{\alpha}(\lambda_{\alpha})-c\cdot\lambda_{\alpha}=(1-\alpha)(p-c)\cdot\lambda_{\alpha}=(1-\alpha)\frac{d}{d\alpha}u(v,\alpha).$
(3)

Next, we consider two special cases: $\alpha=-1$ and $\alpha=1-\frac{1}{2m}$,
and we bound the corresponding utility of buyer $v$ under pricing
$q_{\alpha}$.

When $\alpha=-1$, we have

$\displaystyle q_{\alpha,i}$ $\displaystyle=$ $\displaystyle-c_{i}+2q_{i}$
$\displaystyle=$ $\displaystyle
c_{i}+2\cdot\min_{\lambda\in\Delta_{m}}\frac{p(\lambda)-c\cdot\lambda}{\lambda_{i}}$
$\displaystyle\geq$ $\displaystyle
c_{i}+2\cdot\min_{\lambda\in\Delta_{m}}\frac{p(\lambda)}{2\lambda_{i}}$
$\displaystyle\geq$
$\displaystyle\min_{\lambda\in\Delta_{m}}\frac{p(\lambda)}{\lambda_{i}}.$

Here the second line is by the definition (2) of $q_{i}$; the third line is by
the earlier observation that $p(\lambda)\geq 2c\cdot\lambda$ for any lottery
$\lambda\in\Delta_{m}$. Notice that under buy-many pricing $p$, for any
lottery $\lambda^{o}$, the following strategy gives allocation
$\lambda^{o}\in\Delta_{m}$ with price
$\sum_{i}\lambda^{o}_{i}\min_{\lambda\in\Delta_{m}}\frac{p(\lambda)}{\lambda_{i}}$:
with probability $\lambda_{i}^{o}$, repeatedly purchase
$\operatorname{arg\,min}_{\lambda\in\Delta_{m}}\frac{p(\lambda)}{\lambda_{i}}$
until getting item $i$. Since $p$ satisfies the buy-many constraint, we have
for any $\lambda^{o}\in\Delta_{m}$,

$p(\lambda^{o})\leq\sum_{i}\lambda^{o}_{i}\min_{\lambda\in\Delta_{m}}\frac{p(\lambda)}{\lambda_{i}}\leq\lambda^{o}\cdot
q_{\alpha}$

In other words, $q_{\alpha}$ is more expensive than $p$ on any lottery, thus
the utility of any buyer $v$ is smaller under $q_{\alpha}$:

$u_{v}(p)\geq u(v,-1).$ (4)

When $\alpha=1-\frac{1}{2m}$, notice that by (2),
$(q_{i}-c_{i})\lambda_{i}\leq p(\lambda)-c\cdot\lambda$ for any
$\lambda\in\Delta_{m}$. Summing over all $i\in[m]$ we have

$(q-c)\cdot\lambda=\sum_{i=1}^{m}(q_{i}-c_{i})\lambda_{i}\leq
m(p-c)\cdot\lambda.$ (5)

Let $\lambda^{*}\in\Delta_{m}$ be the lottery purchased by buyer $v$ under the
optimal buy-many mechanism $p$ with cost $2c$. Then

${}\begin{split}u(v,1-\frac{1}{2m})&=\max_{\lambda\in\Delta_{m}}\left(v(\lambda)-q\cdot\lambda\cdot\frac{1}{2m}-(1-\frac{1}{2m})c\cdot\lambda\right)\\\
&\geq\max_{\lambda\in\Delta_{m}}\left(v(\lambda)-c\cdot\lambda-\frac{p(\lambda)-c\cdot\lambda}{2}\right)\\\
&=\max_{\lambda}\left(v(\lambda)-p(\lambda)+\frac{p(\lambda)}{2}-\frac{c\cdot\lambda}{2}\right)\\\
&\geq
v(\lambda^{*})-p(\lambda^{*})+\frac{p(\lambda^{*})}{2}-\frac{c\cdot\lambda^{*}}{2}\\\
&\geq u_{v}(p)+\frac{1}{2}\textsc{Profit}_{p,2c}(v),\\\ \end{split}$ (6)

Here the second line is by (5), and the last line is by the definition of the
utility $u_{v}(p)$ of the buyer $v$ under mechanism $p$, and the definition of
the profit $\textsc{Profit}_{p,2c}(v)$ of buyer $v$ in the setting with
production costs. By adding (4) and (6), we have

$\displaystyle
u(v,1-\frac{1}{2m})-u(v,0)\geq\frac{1}{2}\textsc{Rev}_{p,2c}(v).$ (7)

Consider $\alpha$ to be randomly drawn from distribution over
$[-1,1-\frac{1}{2m}]$ with density $\frac{1}{(1-\alpha)\ln 4m}$. The expected
profit of buyer $v$ under pricing $q_{\alpha}$ and item costs $c$ is

$\displaystyle\mathbb{E}_{\alpha}\textsc{Profit}_{q_{\alpha},c}(v)$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\alpha}(1-\alpha)\frac{d}{d\alpha}u(v,\alpha)$
$\displaystyle=$
$\displaystyle\int_{-1}^{1-\frac{1}{2m}}\frac{1}{(1-\alpha)\ln
4m}\cdot(1-\alpha)\frac{d}{d\alpha}u(v,\alpha)d\alpha$ $\displaystyle=$
$\displaystyle\frac{1}{\ln 4m}\left(u(v,1-\frac{1}{2m})-u(v,-1)\right)$
$\displaystyle\geq$ $\displaystyle\frac{1}{2\ln 4m}\textsc{Profit}_{p,2c}(v),$

here the first line is from (3); the last line is from (7). Taking the
expectation over all $v\sim\mathcal{D}$, we know that there exists a pricing
$q_{\alpha}$ such that
$\textsc{Profit}_{q_{\alpha},c}(\mathcal{D})\geq\frac{1}{2\ln
4m}\textsc{Profit}_{p,2c}(\mathcal{D})$. This finishes the proof of the
theorem. ∎