On the Complexity of Simple and Optimal Deterministic
Mechanisms for an Additive Buyer

arXiv:1702.07032v2 [cs.GT] 14 Jul 2017

Xi Chen∗

George Matikas†

Dimitris Paparas‡

Mihalis Yannakakis§

Abstract
We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive
buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly,
even when the optimal solution is guaranteed to be of a very simple kind: the seller picks a price for each
individual item and a price for the grand bundle of all the items; the buyer can purchase either the grand
bundle at its given price or any subset of items at their total individual prices. The following problems
are also #P-hard, as immediate corollaries of the proof:
1. determining if individual item pricing is optimal for a given instance,
2. determining if grand bundle pricing is optimal, and
3. computing the optimal (deterministic) revenue.
On the positive side, we show that when the distributions are i.i.d. with support size 2, the optimal
revenue obtainable by any mechanism, even a randomized one, can be achieved by a simple solution of
the above kind (individual item pricing with a discounted price for the grand bundle) and furthermore,
it can be computed in polynomial time. The problem can be solved in polynomial time too when the
number of items is constant.

∗

Columbia University. Email: xichen@cs.columbia.edu. Research supported by NSF CCF-1149257 and CCF-1423100.
Columbia University. Email: matikas@cs.columbia.edu. Research supported by NSF CCF-1423100.
‡
University of Wisconsin-Madison. Email: paparas@cs.wisc.edu. Research supported by NSF CCF-1320654 and CCF1617505.
§
Columbia University. Email: mihalis@cs.columbia.edu. Research supported by NSF CCF-1320654 and CCF1423100.
†

1

1 Introduction
Consider the following natural scenario: A customer walks in a grocery store with the intention of buying
some items. The store owner has statistical information from past customers that reveals how much a typical
customer values each item. Her goal is to assign prices for the items and offer discounts for bundles of them
to encourage the customer to spend more money in a way that maximizes her expected revenue.
In this paper we formally study practices like the above, which we refer to as the optimal bundle-pricing
problem, under the setting where a single additive buyer is interested in n heterogeneous items offered by a
seller. While the buyer’s values for the items are unknown, the seller is given as input a product distribution
F = F1 × · · · × Fn from which the valuations v = (v1 , . . . , vn ) of the buyer for the n items are drawn,
where each Fi is a discrete distribution given explicitly (by listing its support and probabilities). The seller
offers a finite menu M of bundles to the buyer (or a bundle-pricing), with each entry of the menu consisting
of a subset (bundle) T ⊆ [n] of items and the price πT at which it is sold. Given a menu M , the buyer draws
P
her valuations v from F and then either buys a bundle T from M that maximizes her utility i∈T vi − πT
or nothing if the utility of every bundle in M is negative1 ; the price πT of the bundle bought by the buyer
is the revenue of the seller. The goal of the seller is to find a menu that maximizes her expected revenue
(i.e., the expected price πT that the buyer pays), which is known to be equivalent to the problem of Revenue
Optimal Deterministic Mechanism Design. If we extend bundle-pricings to allow the seller to offer a finite
menu of lotteries (or a lottery-pricing), where a lottery is a pair ((x1 , . . . , xn ), π) with π being its price
and xi ∈ [0, 1] being the probability of the buyer getting item i ∈ [n] if this lottery is purchased, we
obtain the optimal lottery-pricing problem, also known in the literature as the problem of Revenue Optimal
Randomized Mechanism Design. We define the two problems formally in Section 2.2
It is worth pointing out that bundle-pricing schemes commonly used in practice do not necessarily list
explicitly the bundles offered in the menu, but may specify them implicitly in a succinct manner. For
example, in the case of offering a simple item-pricing without any discounts for bundles, the seller needs
only to specify a price for each item (n numbers in total); the induced menu consists of all 2n subsets of
items, each priced at the sum of prices of items in the subset, and has the desired property that the buyer’s
problem, i.e., finding an optimal bundle in the menu given v, is easy to solve. Because of this, it would
not be appropriate to require the output of the bundle-pricing problem to be an explicit list of bundles in an
optimal menu, but rather it can be represented in a reasonably succinct way. The exact representation of the
output, however, will not affect our main results, as we explain when we describe them later in this Section.
Both optimal deterministic and randomized mechanism design problems have been studied intensively
during the past decade [Tha04, GHK+ 05, Bri08, CHK07, CHMS10, CD11, CMS10, BCKW10, Pav10,
WT14, BILW14, DDT14, DDT12, DDT13, DDT15, HN12, MV06, Rub16, LY13, Yao15]. For some instances, randomized mechanisms can achieve strictly higher revenue than deterministic mechanisms. However, deterministic mechanisms (bundle-pricings) are much more widely used in practice (especially “simple” pricing schemes); we will focus on deterministic mechanisms in this paper. Recently, much effort has
been devoted to understanding the power and limitations of simple pricing schemes, that is, menus that can
be described succinctly in a natural way and at the same time induce an easy-to-solve buyer’s problem.
Some of the examples include (i) selling all items separately (item-pricing), (ii) selling only the grand bundle that consists of all items (grand-bundle pricing), and (iii) partition mechanisms, where one partitions
1

Ties in utility are broken in favor of a bundle with higher price (and value).
We choose to follow the language of bundle-pricings and lottery-pricings in this paper, instead of deterministic and randomized
mechanisms, mainly because they are conceptually closer to common practices seen in the real world and are easier to understand
for readers that are not familiar with mechanism design (e.g., there is no need to introduce the notion of truthfulness).
2

2

the items into disjoint groups, each with its own price, and sells the groups separately. While it is known
that none of these solutions is optimal in general among bundle-pricings, there has been substantial work
studying basic questions for each of these simple solutions, including the following: How does the revenue
achievable by these solutions compare with optimal revenues achievable by bundle or lottery pricings? What
are conditions under which these solutions are optimal? Can we compute an optimal solution of each type?
In case (i) of selling the items separately, we know how to compute efficiently an optimal item-pricing:
each item is assigned separately its optimal price following Myerson’s theory [Mye81]. In both cases (ii) and
(iii) of the grand bundle and partition mechanisms, the problem of finding an optimal solution is intractable
(#P-hard [DDT12] and NP-hard [Rub16], respectively). However, the fact that it is hard to find an optimal
solution of a certain type (grand bundle or partition mechanisms) does not mean that one cannot easily find
a solution that is not of this type and has higher revenue (for example, by selling also individual items), or
possibly even find a solution that is optimal among all bundle-pricings. Thus, two central questions remain
concerning the bundle-pricing (or optimal deterministic mechanism design) problem:
1. Is there an efficient algorithm that finds an optimal bundle-pricing?
2. If the problem above is hard in general, is there such an algorithm when the instance is promised
to have a “simple” optimal bundle-pricing?
Our results resolve both questions in the negative by showing that the problem is #P-hard, even when the
distributions have support size 2 for each item and, more importantly, even when the instance is promised to
have a unique optimal bundle-pricing that is of a very simple kind, which we call a discounted item-pricing:
the seller picks a price for each individual item and a price for the grand bundle of all the items; the buyer
can purchase either the grand bundle at its given price or any subset of items at their total individual prices.
Such a solution can be described using n + 1 numbers and the buyer’s problem is also easy to solve. This is
the reason why the exact output format of the problem does not affect our hardness result.
This result tells us that the bundle-pricing (deterministic mechanism design) problem is inherently computationally hard, and furthermore the difficulty is not (only) due to the fact that the optimal solution can
be very complex, of the kind that one would not use in practice anyway; the problem is hard even when the
optimal solution is extremely simple: standard item pricing with a discount for the grand bundle.
As a by-product of the proof, we also resolve in the negative the question of whether there is a ‘nice’
characterization (i.e., an easy-to-check necessary and sufficient condition) of when item-pricings are optimal, i.e., whether an item-pricing can achieve the optimal revenue achievable by bundle pricings or whether
bundling helps. The same applies to grand-bundle pricings (and partition mechanisms), i.e., there is no easyto-check characterization for the optimality of grand-bundle pricings under standard complexity-theoretic assumptions.
On the positive side, we show that when F1 , . . . , Fn are i.i.d. with support size 2, the optimal revenue
achievable by any pricing scheme, even a lottery one, can be achieved by a discounted item-pricing which,
furthermore, can be computed in polynomial time. We discuss our results in detail below in Section 1.1.

1.1 Our Results
Given an input distribution F, we use BR EV (F), SR EV (F), DR EV (F) and R EV (F) to denote the optimal
expected revenues achievable by a grand-bundle pricing (i.e., selling the grand bundle only), an item-pricing
(i.e., selling all items separately), a bundle-pricing, and a lottery-pricing, respectively.
First we state our positive result for i.i.d. distributions with support size 2:

3

Theorem 1.1. When F1 , . . . , Fn are i.i.d. with support size 2 ({a, b} and a < b), R EV (F) can always be
achieved by a discounted item-pricing where the grand bundle is priced at kb+(n−k)a for some k ∈ [0 : n]
and each item is priced at b. Moreover, the parameter k can be found in polynomial time.
Our main result addresses the two questions from the introduction in the negative: we show that it is
#P-hard to find an optimal bundle-pricing for a single additive buyer, even when F is a product distribution
and each Fi has support size 2. Although in general an optimal solution can be highly complex and consist
of exponentially many bundles without a succinct description, our hardness result is established on instances
that are guaranteed to have a unique and very simple optimal solution, namely, the discounted item-pricing
that we defined earlier. Such a pricing scheme corresponds to the ubiquitous practice of offering an individual price πi for each item i and also the grand bundle of all items at a discounted price π, for example a
combo of a toothpaste, a toothbrush, dental floss, and mouth wash offered at a 15% discount as compared
to the cost of buying them separately. The buyer can choose to buy the grand bundle at π or any subset T
P
of items at i∈T πi , whichever brings the highest (nonnegative) utility (note that in the latter case the buyer
will obviously buy the set T of all items whose price is less than or equal to the buyer’s value). While a discounted item-pricing offers exponentially many bundles, it has a succinct representation by n + 1 numbers
and is easy to implement in practice. We state our main hardness result in Theorem 1.2:
Theorem 1.2. The optimal bundle-pricing problem is #P-hard even when (1) all distributions have support
size 2 and (2) the instance is promised to have a unique optimal solution that is a discounted item-pricing.
Indeed, the hard instances constructed in the proof of Theorem 1.2 have the property that either
(i) the grand-bundle pricing3 that offers the grand bundle at the sum of low values of all items; or
(ii) the discounted item-pricing that offers each individual item at its high value and the grand bundle
at a specific value that can be computed from the instance in polynomial time,
is guaranteed to be optimal among all bundle-pricings, but it is #P-hard to determine which one is better.
Note that (i) can be equivalently described as an item-pricing, with each item priced at its low value, and the
revenue can be computed in polynomial time. These observations together lead to a number of corollaries.
Corollary 1.3. The following problems are #P-hard:
1. Given a product distribution F, decide whether DR EV (F) = SR EV (F), i.e., whether an
item-pricing is optimal among all bundle-pricings.
2. Given a product distribution F, decide whether DR EV (F) = BR EV (F), i.e., whether a
grand-bundle pricing is optimal among all bundle-pricings.
Corollary 1.4. The following problems are #P-hard:
1. Given a product distribution F, compute DR EV (F).
2. Given a product distribution F and a valuation v, compute the bundle bought at v in any
optimal bundle-pricing.
We remark finally that all the hardness results hold if the number of items is unbounded. For a constant
number of items, we obtain a polynomial-time algorithm (though the dependency of its running time on the
number of items is exponential).
Theorem 1.5. When the number of items is constant, an optimal bundle-pricing can be computed in polynomial time.
3

Note that a grand-bundle pricing is a special case of discounted item-pricings.

4

1.2 Related Work
The seminal work of Myerson [Mye81] completely settles the case of selling a single item, by giving a computationally efficient and deterministic mechanism (i.e., a pricing of the item) that maximizes the expected
revenue among all possible, randomized or deterministic, mechanisms. The more general multi-dimensional
setting, however, turns out to be inherently more difficult. Unlike Myerson’s setting, randomization in general improves the revenue when there are many items for sale, even if there is a single unit-demand buyer
[Tha04] (i.e. the buyer wants to buy only one item) or an additive buyer [MV06]. It is also known that the optimal menu of lotteries may have exponential size [CDO+ 15, HN13]. Moreover, under standard complexitytheoretic assumptions, recent results rule out the existence of computationally efficient algorithms that find
a revenue-optimal deterministic or randomized mechanism for a unit-demand buyer [CDP+ 14, CDO+ 15,
GHK+ 05, Bri08], or a randomized mechanism for an additive buyer [DDT14]. However, hardness results for
the optimal deterministic mechanism design problem with an additive buyer are limited. Rubinstein [Rub16]
proved that finding an optimal partition mechanism is strongly NP-hard; Daskalakis et al. [DDT12] proved
that finding an optimal price for selling the grand bundle is #P-hard. These results are for restrictions of the
problem that impose a specific menu structure, and the original problem remained open before this work.
Among these hardness results, the one that is most relevant to ours is that of Daskalakis, Deckelbaum,
and Tzamos [DDT14]. They construct instances F with support size 2 for each Fi and show that the problem of finding an optimal lottery-pricing (or randomized mechanism) is #P-hard. This, however, does not
have any consequences for the bundle-pricing problem for two reasons. First, the deterministic mechanism
design problem is not necessarily harder than the randomized one. In fact, in the setting of a unit-demand
buyer, the deterministic problem is provably “easier”: the randomized problem is #P-hard [CDO+ 15] while
the deterministic one is in NP [CDP+ 14]. Second, for the construction of [DDT14] to work for bundlepricings, it would need to be the case that optimal menus of lotteries of their instances are deterministic and
consist of bundles only. However, this is not the case: the solution in [DDT14] makes essential use of the
randomization feature and the optimal menu for F contains a large number of lotteries (with probabilities
in (0, 1)) for valuations in a certain “critical” region. Compared to techniques used in [DDT14], ours are
different in the following two aspects: (1) Since DR EV (F) is captured by an integer program (instead of a
linear program for R EV (F); see Section 2), we cannot use LP duality but have to rely on more discrete and
combinatorial arguments to identify its optimal integer solutions; (2) An important step in both proofs is to
relax the integer (or linear) program that captures DR EV (F) (or R EV (F)). Our relaxation is significantly
different from the LP relaxation of [DDT14]. We need to keep a large set of global constraints from the
original IP while local constraints suffice for the purpose of [DDT14].
Most of the work on the deterministic mechanism design problem for an additive buyer so far focuses
on approximation. Hart and Nisan [HN12] studied two simple deterministic mechanisms for product distributions: selling items separately or selling the grand bundle only. They showed that selling items separately
and grand bundling are respectively Ω(1/ log2 n) and Ω(1/ log n) approximations of the optimal revenue
achievable by any (possibly randomized) mechanism (later improved by Li and Yao [LY13] to Ω(1/ log n)
for both schemes, which is known to be tight [HN12]). While neither of these two schemes can achieve by
itself a constant factor approximation, Babaioff et al. [BILW14] showed that the better of the two gives a
(1/6)-approximation. Recently, Daskalakis et al. [DDT13, DDT15] studied conditions for grand-bundling
mechanisms to be optimal (for continuous distributions), and showed that this happens if and only if two
stochastic dominance conditions hold. Rubinstein [Rub16] worked on partition mechanisms and obtained a
polynomial-time approximation scheme (PTAS) for a revenue maximizing partition mechanism. A number
of other results [DW12, CH13] obtained approximation schemes for i.i.d. distributions with the MHR prop-

5

erty. Giannakopoulos and Koutsoupias [GK14] obtained optimal mechanisms for i.i.d. uniform distributions
with up to six items. Finally Yao [Yao15] introduced a new approach for reducing the k-item n-bidder problem to the k-item 1-bidder setting and gave a deterministic mechanism that yields at least a constant fraction
of the optimal revenue for the more general k-item n-bidder setting.
We also note that there is extensive work studying unit-demand buyers (e.g. [CDP+ 14, CDO+ 15,
GHK+ 05, Bri08, CHK07, CHMS10, CD11, CMS10, BCKW10, Pav10, WT14]). Besides the papers cited
earlier that address the complexity of an optimal mechanism in that context, the rest of the work, which
mostly concerns special cases or approximation, is not directly related to the topic of the present paper.

2 Preliminaries
Let Di be the support of Fi , and D = D1 × · · · × Dn be the set of valuation vectors. For each v ∈ D, let
Pr[v] = Pr[v1 ] × · · · × Pr[vn ]
F1

Fn

denote the probability of v drawn from F.
We first define DR EV (F), the optimal expected revenue obtainable by a bundle-pricing, by formulating
it using an integer program with n + 1 variables associated with each valuation v ∈ D: xv,1 , . . . , xv,n and
πv , where xv,i ∈ {0, 1} indicates whether item i is included in the bundle the buyer chooses from the menu
(with xv,i = 1 if item i is included) when her valuation is v and πv denotes the price of the bundle. We also
write xv = (xv,1 , . . . , xv,n ) ∈ {0, 1}n to denote the allocation vector for valuation v. The integer program
P
then maximizes the expected revenue: v∈D πv · Pr[v] subject to the following constraints:
1. xv,i ∈ {0, 1} for all v ∈ D;

2. For each v ∈ D, the utility is nonnegative:

P

i∈[n] vi

· xv,i − πv ≥ 0;

3. For all w, v ∈ D, w does not envy the bundle of v:
X

wi · xw,i − πw ≥

i∈[n]

X

wi · xv,i − πv .

i∈[n]

We refer to this integer program as the standard IP for DR EV (F) and the goal of the optimal bundle-pricing
problem is to find an optimal solution to the standard IP. As discussed earlier, the exact way of defining
the output of the problem does not affect our main results. (For example, one can adopt the model used in
[DDT14, CDO+ 15], where a polynomial-time algorithm A for the optimal bundle-pricing problem takes as
input a distribution F and a valuation v ∈ D and outputs a bundle A(F, v) such that {A(F, v) : v ∈ D} is
an optimal solution to the standard IP for DR EV (F). Under this formulation Theorem 1.2 implies that there
cannot be any such polynomial-time algorithm unless #P can be solved in polynomial time.)
The equivalence between the optimal bundle-pricing problem and deterministic mechanism design follows from the observation that any feasible solution {xv , πv : v ∈ D} to the standard IP for DR EV (F) can
be equivalently viewed as a deterministic mechanism that is both individually rational and truthful, and vice
versa: the mechanism, upon v reported by the buyer, assigns items xv to the buyer and charges her πv .
Sometimes (e.g., in Section 4), it is more convenient to replace πv by a nonnegative utility variable uv .

6

The standard IP maximizes the same expected revenue:


X X

vi · xv,i − uv  · Pr[v]
v∈D

i∈[n]

subject to the following (slightly simpler) constraints:
1. xv,i ∈ {0, 1} and uv ≥ 0 for all v ∈ D;

2. For all w, v ∈ D, w does not envy the bundle of v:


X
X
X
vi · xv,i − uv  = uv +
uw ≥
wi · xv,i − 
(wi − vi ) · xv,i .
i∈[n]

i∈[n]

i∈[n]

We refer to this IP as the standard IP (utility version) for DR EV (F).
On the other hand, the optimal revenue R EV (F) obtainable by a lottery-pricing is captured by the same
objective function and linear constraints, except that xv,i takes values in [0, 1] instead of {0, 1}. We refer to
this linear program as the standard LP for R EV (F).

3 IID with Support Size 2
We establish Theorem 1.1 in this section. Let F1 , . . . , Fn be i.i.d. distributions with support size 2. Without
loss of generality we can assume that the support is {1, b} with b > 1. (If the support is {0, b} the problem
is trivial: the optimal revenue can be achieved by offering every item at price b; if the support is {a, b} with
0 < a < b, then we can equivalently rescale it to {1, b/a}.) Let p ∈ (0, 1) be the probability that an item
takes value b, and 1 − p that it takes 1. We let Pi denote the probability of v ∼ F having i items at value b
and n − i at 1, for each i ∈ [0 : n]. That is,
 
n
Pi =
· pi · (1 − p)n−i .
i
The following lemma for Pi ’s is crucial. We delay its proof to the end of this section.
Lemma 3.1. There exists an integer k ∈ [0 : n] such that
(n − i)Pi − (b − 1)(Pi+1 + · · · + Pn )

(1)

is negative for all i : 0 ≤ i < k and is nonnegative for all i : k ≤ i ≤ n.
Let k ∈ [0 : n] be an integer that satisfies Lemma 3.1, which is unique and can be computed in
polynomial time. We use S ∗ to denote the following discounted item-pricing:
The grand bundle [n] is offered at kb + n − k and each item is offered individually at b (the
latter means that the buyer can buy any bundle T ⊆ [n] at price |T |b).
Given S ∗ , the behavior of the buyer is as follows. If a valuation vector has k or more items at b then the
buyer buys the grand bundle at kb + n − k; otherwise it buys all the items that have value b. The expected

7

revenue R∗ of the discounted item-pricing S ∗ is then
R∗ =

X

bi · Pi + (kb + n − k)

1≤i<k

X

Pi .

k≤i≤n

It is clear that given k, R∗ can be computed in polynomial time.
To finish the proof of Theorem 1.1, we show that S ∗ achieves the optimal revenue Rev(F).
Lemma 3.2. R∗ = Rev(F) when F1 , . . . , Fn are i.i.d. with support size 2 and k satisfies Lemma 3.1.
We start with some preparation for the proof of Lemma 3.2. First recall that when distributions are i.i.d.,
Daskalakis and Weinberg [DW12] showed that there always exists an optimal solution to the standard LP
for R EV (F) (we use the price version in this section) that is “symmetric”: For any permutation σ over [n]
with σ(v) = w (i.e. vσ(i) = wi for all i ∈ [n]), we always have σ(xv ) = xw and πv = πw , i.e., the lotteries
bought at v and w are the same under the permutation σ. Based on that, one can significantly reduce the
number of variables for the i.i.d. support-size 2 case, and we refer to the new LP described below as the
symmetric LP for R EV (F).
The symmetric LP has 3n + 1 variables: xi , for i = 1, . . . , n, is the probability of getting an item with
value b in v when the valuation v has i items at b (and n − i items at 1); yi , for i = 0, 1, . . . , n − 1, is the
probability of getting an item with value 1 when the valuation has i items at b; finally, πi for i = 0, 1, . . . , n
is the price of the lottery for a valuation with i items at b. The symmetric LP maximizes the expected
P
revenue: ni=0 πi · Pi subject to the same constraints of the standard LP after replacing πv by πℓ when v
has ℓ items at b and xv,i by xℓ if vi = b and by yℓ if vi = 1. It is not hard to see that the number of distinct
constraints left after the replacement is polynomial in n and thus, the symmetric LP can be solved exactly
in polynomial time. By [DW12], the optimal value of the symmetric LP is R EV (F).
We are now ready to prove Lemma 3.2.
Proof of Lemma 3.2. Since R∗ is the expected revenue of S ∗ , it suffices to show Rev(F) ≤ R∗ .
For this purpose we will relax the symmetric LP for R EV (F) and show that its optimal value is at most
∗
R . In the relaxed LP we only keep the following constraints of the symmetric LP:
1. 0 ≤ xi ≤ 1 for each i ∈ [n] and 0 ≤ yi ≤ 1 for each i ∈ [0 : n − 1].
2. π0 ≤ ny0 (i.e., the utility at the all-1 vector is nonnegative);
3. For each i ∈ [n], the constraint that the valuation w with wj = b for j ∈ [i] and wj = 1 for
j > i does not envy the lottery of v with vj = b for j ∈ [i − 1] and vj = 1 for j > i − 1:
bixi + (n − i)yi − πi ≥ b(i − 1)xi−1 + (n − i + b)yi−1 − πi−1 .

(2)

Note that when i = 1, x0 appears on the RHS with coefficient 0; when i = n, yn appears on the LHS
with coefficient 0. For convenience we introduce x0 = yn = 0 as dummy variables that never appear
in the relaxed LP but help simplify the presentation of these constraints.
Since all of them are part of the symmetric LP, the optimal value of the relaxed LP is at least R EV (F). In
the rest of the proof we show that the optimal value of the relaxed LP is at most R∗ .
To this end we use the constraints above to upperbound each πi using x and y variables. For i = 0 we
use π0 ≤ ny0 . For each j ∈ [n] we have from constraints (2) in the relaxed LP that:
πj ≤ πj−1 + bjxj + (n − j)yj − b(j − 1)xj−1 − (n − j + b)yj−1 .
8

Summing these inequalities for all j = 1, . . . , i, we get after some cancellations:
πi ≤ π0 + bixi + (n − i)yi − (b − 1)(yi−1 + yi−2 + · · · + y1 ) − (n + b − 1)y0 .
Plugging in π0 ≤ ny0 , we have for each i ∈ [n]:
πi ≤ bixi + (n − i)yi − (b − 1)(yi−1 + yi−2 + · · · + y1 + y0 ).
P
Replacing in the objective function i Pi · πi each πi by its upper bound, we get a linear form in the
xi ’s, i ∈ [n], and yi ’s, i ∈ [0 : n − 1], which upperbounds the value of the relaxed LP (note that x0 and yn
are dummy variables that do not really appear in any constraint). For each i ∈ [n], the coefficient of xi in the
linear form is bi · Pi , thus this term is maximized if we set xi = 1 for each i ∈ [n]. The coefficient of y0 is
nP0 −(b−1)(P1 +· · ·+Pn ) and the coefficient of yi for each i ∈ [n−1] is (n−i)Pi −(b−1)(Pi+1 +· · ·+Pn ).
From the choice of k ∈ [0 : n] and Lemma 3.1, we have for all i ∈ [0 : n − 1]: The coefficient of yi is
negative if i < k, and is nonnegative if i ≥ k. Therefore, the linear form is maximized when we set yi = 0
for all i < k and yi = 1 for all i ≥ k. Applying these substitutions in the linear form, the upper bound on
the value of the LP becomes (note that (n − i)Pi − (b − 1)(Pi+1 + · · · + Pn ) is 0 when i = n):
X

bi · Pi +

1≤i≤n

=

k≤i≤n−1

X

bi · Pi +

X

bi · Pi +

X

bi · Pi +

1≤i≤n

=



X

k≤i≤n

1≤i<k


(n − i)Pi − (b − 1)(Pi+1 + · · · + Pn )

X 

k≤i≤n

1≤i≤n

=

X

X


(n − i)Pi − (b − 1)(Pi+1 + · · · + Pn )



Pi · (n − i) − (b − 1)(i − k)

Pi · [n + (b − 1)k] = R∗ .

k≤i≤n

This finishes the proof of the lemma.
It remains to prove Lemma 3.1. We start with the following lemma.


P
Lemma 3.3. For all i = 1, . . . , n − 1, Pi (n − i) + j≥i+1 Pj n − pi > 0.

Proof. We use induction on n − i.
Basis: n − i = 1, i.e. i = n − 1. The left-hand side is




n−1
n−1
n−1
n
Pn−1 + Pn n −
=n·p
· (1 − p) + p · n −
= pn−1 > 0.
p
p

Induction Step: We have Pi (n − i) = Pi+1 · (i + 1) ·

1−p
p .

Therefore, the left-hand side is equal to





X
1−p
i
i
+ Pi+1 · n −
+
Pj n −
p
p
p
j≥i+2


X
i
1
Pj n −
= Pi+1 (n − (i + 1)) + Pi+1 · +
p
p
j≥i+2


X
i+1
> Pi+1 (n − (i + 1)) +
Pj n −
> 0,
p

LHS = Pi+1 · (i + 1) ·

j≥i+2

9

where the last inequality holds by the induction hypothesis.
Now we are ready to prove Lemma 3.1:
Proof of Lemma 3.1. We let k be the smallest i ∈ [0 : n] such that (1) is nonnegative (k is well defined as
(1) is 0 when i = n). To prove that (1) is nonnegative for all i ≥ k, it suffices to show that
(n − i)Pi
P
j≥i+1 Pj

is monotonically increasing for i from 0 to n − 1. Fix an i ∈ [n − 1]. Our goal is to show that

or equivalently, (n − i)Pi

P

(n − i)Pi
(n − (i − 1))Pi−1
P
P
−
> 0,
j≥i+1 Pj
j≥i Pj

j≥i Pj

− (n − (i − 1))Pi−1

P

j≥i+1 Pj

(n − (i − 1))Pi−1 = iPi ·

> 0. Since

1−p
,
p

we can rewrite the left-hand side as




X
X
X
1−p
Pi (n − i)
Pj − i
Pj  = Pi (n − i)Pi +
Pj (n − (i/p)) ,
p
j≥i

j≥i+1

j≥i+1

which is positive by Lemma 3.3. Therefore, the desired inequality holds.

4 Hardness of Revenue-Optimal Deterministic Mechanism Design
We prove Theorem 1.2 in this section. The plan is to reduce from the following #P-hard decision problem
called COMP introduced in [CDO+ 15]. The input consists of three parts: 1) a set B of n nonnegative
integers B = {b1 , . . . , bn } between 0 and 2n (we assume without loss of generality that b1 ≤ · · · ≤ bn );
2) a subset W ⊂ [n] of size |W | = n/2 (assume without loss of generality that n is even) and we use w
P
to denote i∈W bi ; and 3) an integer t. The question is to decide whether the number of S ⊂ [n] such
P
that |S| = n/2 and i∈S bi ≥ w is at least t or at most t − 1. While COMP was shown to be #P-hard in
[CDO+ 15], we need here the same problem with the following two extra conditions on the two input sets B
and W , which we will refer to as COMP∗ :
P
1. Every (n/2)-subset S ⊂ [n] with bn ∈ S has i∈S bi ≥ w, i.e. b1 + · · · + bn/2−1 + bn ≥ w.
2. Every (n/2)-subset S ⊂ [n] that does not contain bn but contains either b1 or b2 must have
P
i∈S bi < w, i.e. b2 + bn/2+1 + · · · + bn−1 < w.

These extra conditions will come in handy in the reduction below.

4.1 #P-Hardness of COMP∗
We show that COMP∗ is #P-hard via a polynomial-time reduction from COMP. Let (B, W, t) be an input to
the original COMP problem, where B = {b1 , . . . , bn } with b1 , . . . , bn ∈ [0 : 2n ], W ⊂ [n] with |W | = n/2,
P
and w = i∈W bi . We first construct from B a new set B ′ of 4n integers between 0 and 24n :
10

1. B ′ contains n integers 22n + bi , i ∈ [n];
2. B ′ contains 24n (as the largest integer in B ′ ) and 3n/2 copies of 23n ;
3. The rest of 3n/2 − 1 integers of B ′ are all 0 (so the smallest two integers in B ′ are 0).
The new set W ′ contains 2n integers from B ′ : the 3n/2 copies of 23n and each of 22n + bi , i ∈ W . Let


X
4n − 1
w′ =
b = (3n/2) · 23n + (n/2) · 22n + w and t′ =
+ t.
2n − 1
′
b∈W

P
We show that B ′ and W ′ satisfy the two extra conditions. For the first part note that b∈S b > w′ for
any subset S that contains the largest integer 24n . On the other hand, if S is a 2n-subset of W ′ that does not
contain 24n but contains at least one 0, then we have (using bi ≤ 2n for all i ∈ [n])
X

b ≤ (3n/2) · 23n + (n/2 − 1) · (22n + 2n ) < w′ .

b∈S

P
Let S be a 2n-subset that satisfies b∈S b ≥ w′ . Then either i) S contains 24n , or ii) S contains
all the 3n/2 copies of 23n and a subset of n/2 integers 22n + bi , with the sum of the latter being at least
(n/2)·22n +w. This then implies that (B, W, t) is a yes-instance if and only if (B ′ , W ′ , t′ ) is a yes-instance.
It follows that COMP∗ is also #P-hard.

4.2 The Reduction
We now present the reduction from COMP∗ to the optimal bundle-pricing problem.
Given an input instance (B, W, t) of COMP∗ (with B and W satisfying the extra conditions) we define
an instance F of optimal bundle-pricing with n + 1 items and support size 2. We shall refer to the first n
items as item i for i ∈ [n] and refer to the last item as the special item. Let
h = 22n ,

p=

1
,
2(h + 1)

δ=

1
,
23n

a i = bi δ

and

hi = h + ai ,

for each i ∈ [n]

(hence ai ∈ [0, 2n δ] and is an integer multiple of δ). Then item i is supported on {1, hi + 1}. The probability
of hi + 1 is p and the probability of 1 is 1 − p. Let
c = wδ,

α = (n/2)h + c,

σ=

1
pn

and

τ=

σ
σ+α

(hence c ∈ [0, (n/2)2n δ] and is an integer multiple of δ). The special item is supported on {σ, σ + α}. The
probability of σ + α is τ − ǫ and the probability of σ is 1 − τ + ǫ = (α/(σ + α)) + ǫ for some ǫ (which is
not necessarily positive) to be specified at the end of the proof; for now we only require that |ǫ| = o(1/σ).
Note that since σ ≫ α, the probability τ − ǫ of σ + α is very close to 1, and the probability 1 − τ + ǫ of
σ is positive but very close to 0. This finishes the description of the bundle pricing instance F (except the
choice of the parameter ǫ which we will set at the end).

4.3 Plan of the Proof
Our plan for the proof is the following. In Section 4.4, we introduce some notation and define two simple
bundle-pricings (Solution 1 and 2), as feasible solutions to the standard IP for DR EV (F), both of which are
11

discounted item-pricings. Most of the work lies in Section 4.5, where we show that whenever |ǫ| = o(1/σ),
one of these two solutions is the unique optimal solution to the standard IP and achieves DR EV (F). This is
done by relaxing the standard IP and showing that one of these two solutions is the unique optimal solution
to the relaxed IP. As they are both feasible to the standard IP, we conclude that one of them is uniquely
optimal for the standard IP.
Finally, we set ǫ carefully (with |ǫ| = o(1/σ) as promised) in Section 4.6 to show that Solution 2
is strictly better if the (B, W, t) used in the construction of F is a yes-instance of problem COMP∗ , and
Solution 2 is strictly better if it is a no-instance. This finishes the proof of Theorem 1.2.

4.4 Notation and two simple solutions
For convenience, we will use a subset S ⊆ [n] to denote a valuation vector over the first n items, where
i ∈ S (or i ∈
/ S) means that item i takes the high value hi + 1 (or low value 1). We will also use (S, σ + α)
(or (S, σ)) to denote a full valuation vector over all the n + 1 items in which the special item has the high
value σ + α (or low value σ).
Given S ⊆ [n], we write Pr[S] to denote p|S|(1 − p)n−|S| ; given an integer i ∈ [0 : n], we write
 
n
Pr[i] =
· pi (1 − p)n−i ,
i
P
P
use Pr[i ≥ k] to denote ni=k Pr[i], and Pr[i > k] to denote ni=k+1 Pr[i]. We also use Pr[S, σ] and
Pr[S, σ + α] to denote the probabilities of valuations (S, σ) and (S, σ + α):
Pr[S, σ] = Pr[S] · (1 − τ + ǫ)

and

Pr[S, σ + α] = Pr[S] · (τ − ǫ).

We use the standard IP for DR EV (F) (the utility version) but rename the variables as follows. For
each S ⊆ [n] we use xS,i ∈ {0, 1} to denote the variable for item i in valuation (S, σ) for each i ∈ [n],
zS ∈ {0, 1} to denote the variable for the special item, and uS ≥ 0 to denote the utility. For each S ⊆ [n],
we use x′S,i ∈ {0, 1} to denote the variable for item i in valuation (S, σ + α), zS′ ∈ {0, 1} to denote the
variable for the special item, and u′S ≥ 0 to denote the utility.
The two simple bundle-pricings we are interested in are the following:
Solution 1: Offer the grand bundle at σ + n, or (equivalently) offer each item at its low value.
Solution 2: The discounted item-pricing where the grand bundle is offered at σ + α + n and each
individual item is offered at its high value. As discussed in the introduction, this means that the buyer
can buy either the grand bundle at σ + α + n or any bundle of items at the sum of their high values.
When this menu is offered, the buyer buys the grand bundle if its utility is positive (since her utility
from buying items priced at their high values can never be positive) and buys the bundle of items at
their high values (if any) if the utility from the grand bundle is negative. For the case when the utility
from the grand bundle is 0, the buyer still gets the grand bundle since it always gives a higher
revenue.
These two bundle-pricings induce two feasible solutions to the standard IP:
1. In Solution 1, every valuation (S, σ) and (S, σ + α) buys the grand bundle. So we have for each
S ⊆ [n] and i ∈ [n], xS,i = zS = x′S,i = zS′ = 1. Regarding the utilities we have
uS =

P

i∈S

hi

and
12

u′S = α +

P

i∈S

hi .

P
2. In Solution 2 we have 1) for each S ⊆ [n] and i ∈ [n], x′S,i = zS′ = 1 and u′S = i∈S hi ; 2) for each
P
P
S ⊆ [n] with i∈S hi ≥ α, we have xS,i = zS = 1 for all i ∈ [n], uS = i∈S hi − α; 3) for each
P
S ⊆ [n] with i∈S hi < α, we have xS,i = 1 for each i ∈ S, xS,i = 0 for each i ∈
/ S, zS = 0, and
uS = 0. Given our choice of parameters (i.e. h ≫ ai , c), every S with |S| > n/2 satisfies case 2)
and every S with |S| < n/2 satisfies case 3). A set S with |S| = n/2 satisfies case 2) if we have
P
P
i∈S ai ≥ c (equivalently,
i∈S bi ≥ w) and satisfies case 3) otherwise. This is the connection with
∗
COMP that we will explore in the reduction.
As discussed in the plan, we introduce a relaxation of the standard IP that only contains a subset of its
constraints and refer to it as the relaxed IP. It contains the following constraints:
1. xS,i , zS , x′S,i , zS′ ∈ {0, 1} and uS , u′S ≥ 0, for all S ⊆ [n] and i ∈ [n];
2. For each S 6= ∅, (S, σ + α) does not envy (∅, σ + α):
u′S ≥ u′∅ +

P

i∈S

hi · x′∅,i .

3. For each S ⊆ [n], (∅, σ + α) does not envy (S, σ):
u′∅ ≥ uS −

P

i∈S

hi · xS,i + α · zS .

4. For each S ⊆ [n], (S, σ) does not envy (∅, σ + α):
uS ≥ u′∅ +

P

i∈S

hi · x′∅,i − α · z∅′ .

5. For each pair of T, S with T ⊂ S ⊆ [n], (S, σ) does not envy (T, σ):
uS ≥ uT +

P

i∈S\T

hi · xT,i .

The objective function of the relaxed IP is the same expected revenue:
!
X
X X
(hi + 1) · xS,i +
xS,i + σ · zS − uS · Pr[S, σ]
S⊆[n]

i∈S

+

X

S⊆[n]

i∈S
/

X
X
(hi + 1) · x′S,i +
x′S,i + (σ + α) · zS′ − u′S
i∈S

i∈S
/

!

· Pr[S, σ + α].

4.5 One of the two simple solutions is optimal
Our goal is the following lemma about optimal solutions to the relaxed IP:
Lemma 4.1. In an optimal solution to the relaxed IP, if z∅ = 1, then it must be Solution 1; if z∅ = 0, then it
must be Solution 2.
As both solutions are feasible for the standard IP, we have the following corollary:
Corollary 4.2. Either Solution 1 or 2 is the unique optimal solution to the standard IP.
We start the proof of Lemma 4.1 with a few simple observations.
13

Lemma 4.3. In any optimal solution to the relaxed IP, we have xS,i = 1 for all S ⊆ [n] and i ∈ S, x′S,i = 1
for all S 6= ∅ and i ∈ [n], and zS′ = 1 for all S ⊆ [n].
Proof. The part of x′S,i = 1 for all S 6= ∅ and i ∈ [n] and zS′ = 1 for all S 6= ∅ is trivial as they do not
appear in the constraints of the relaxed IP but appear with a positive coefficient in the objective function.
For z∅′ , note that it only appears on the right hand side with a negative coefficient. Thus, if z∅′ = 0 in a
feasible solution, we can switch it to 1 and the new solution remains feasible but the expected revenue goes
up strictly. The same argument works for xS,i for all S ⊆ [n] and i ∈ S.
Next we show that x′∅,i = 1 for all i ∈ [n] in any optimal solution to the relaxed IP.
Lemma 4.4. In an optimal solution to the relaxed IP, x′∅,i = 1 for all i ∈ [n] and u′S = u′∅ +
all nonempty S ⊆ [n].

P

i∈S

hi for

Proof. Assume for contradiction that x′∅,i = 0 for i ∈ I and I is nonempty. Then we make the following
changes to obtain a new solution:
i) We change x′∅,i from 0 to 1 for each i ∈ I;
P
ii) For each S 6= ∅, we increase u′S by i∈S∩I hi ;

P
iii) For each S ⊆ [n], we replace uS by the maximum of the original uS and u′∅ + i∈S hi − α
P
(by doing this the new uS can go up by at most i∈S∩I hi because of constraints (4)).

We first verify that the new solution remains feasible and then show that its expected revenue is strictly
better than that of the original solution. For its feasibility, constraints in (2) and (4) are trivial. (3) for S
P
holds trivially if uS remains the same. Otherwise uS = u′∅ + i∈S hi − α and thus,
uS −

P

i∈S

hi · xS,i + α · zS = uS −

P

i∈S

hi + α · zS ≤ uS −

P

i∈S

hi + α = u′∅ .

For 5), the constraint for T ⊂ S holds trivially if uT remains the same. If uT goes up, we have
uS ≥ u′∅ +

P

i∈S

hi − α

and

uT = u′∅ +

P

i∈T

hi − α

P
P
and thus, uS − uT ≥ i∈S\T hi ≥ i∈S\T hi · xT,i . This shows that the new solution is also feasible.
Finally, comparing the two solutions, the net gain of expected revenue in the new one is at least
!
X
X
 X
phi > 0
hi = |I| · (τ − ǫ) · (1 − p)n −
Pr[S, σ + α] + Pr[S, σ]
|I| · Pr[∅, σ + α] −
i∈S∩I

S⊆[n]

i∈I

as by our choice of parameters the first term is close to |I| and the second term is close to |I|/2.
The second part of the lemma follows trivially since u′S appears only in the LHS of constraints (2) when
S 6= ∅ and appears in the objective function with a negative coefficient.
So far we have shown in an optimal solution to the relaxed IP that every entry in x′ and z′ is 1 and the
P
only unsettled variable in u′ is u′∅ , with u′S = u′∅ + i∈S hi for all S 6= ∅. (For a sanity check, note that
these conditions hold in Solution 1 and 2.) Next we prove the first case of Lemma 4.1.
Lemma 4.5. In an optimal solution to the relaxed IP, if z∅ = 1, then it must be Solution 1.

14

Proof. Assuming z∅ = 1, we have u′∅ ≥ u∅ + α from constraints (3). Next we show that x∅,i = 1 for all
i ∈ [n]. Assume for contradiction that x∅,i = 0 for i ∈ I and I is nonempty. Then we make the following
changes to obtain a new solution: i) We change x∅,i from 0 to 1 for every i ∈ I; and ii) For each S 6= ∅, we
P
change uS to be the maximum of the original uS and u∅ + i∈S hi (by doing this uS can go up by at most
P
i∈S∩I hi due to constraints (5) for T = ∅).
We first verify that the new solution is also feasible and then show that its expected revenue is strictly
higher than that of the old solution. For its feasibility, constraints in (2) and (4) are trivial. For (3), the
P
constraint for S ⊆ [n] is trivial if uS stays the same. Otherwise, uS = u∅ + i∈S hi and
RHS of (3) = uS −

P

i∈S

hi + α · zS = u∅ + α · zS ≤ u∅ + α ≤ u′∅ .

P
The constraint (5) for T ⊂ S is trivial if uT remains the same. Otherwise, we have uT = u∅ + i∈T hi and
P
P
uS ≥ u∅ + i∈S hi . Thus, uS − uT ≥ i∈S\T hi · xT,i . This finishes the proof of feasibility.
Next the net gain of expected revenue in the new solution is at least
!
X
X
X
n
|I| · Pr[∅, σ] −
Pr[S, σ] ·
hi = (1 − τ + ǫ) · |I| · (1 − p) −
phi > 0,
S⊆[n]

i∈S∩I

i∈I

following the same argument used in the previous lemma. We conclude that x∅,i = 1 for all i ∈ [n].
P
Finally, given that x∅,i = 1 for all i ∈ [n] and u∅ ≥ 0, we have uS ≥ i∈S hi , u′∅ ≥ α and
u′S = u′∅ +

X

hi ≥ α +

i∈S

X

hi .

i∈S

Comparing it with Solution 1, a) the utility of every valuation of this solution is at least as large as that of
Solution 1; and b) every allocation variable xS,i , x′S,i , zS and zS′ in Solution 1 is 1 (the maximum possible).
Thus, its revenue is no more than that of Solution 1 and in order to be optimal, it must be exactly the same
as Solution 1. This finishes the proof of the lemma.
In the rest of this subsection, we consider the more challenging case when z∅ = 0, and prove the second
part of Lemma 4.1 using a sequence of lemmas. First we show that u′∅ = 0 when z∅ = 0.
Lemma 4.6. In any optimal solution to the relaxed IP, if z∅ = 0 then we have u′∅ = 0.
Proof. Assume for contradiction that u′∅ > 0. We show first that u′∅ > 0 implies that u′∅ ≥ δ.
For this purpose we fix all the allocation variables to their {0, 1} values in the optimal solution and
P
replacing each u′S , S 6= ∅, using u′S = u′∅ + i∈S hi (by Lemma 4.5) to obtain a linear program over the
rest of utility variables uS , S ⊆ [n], and u′∅ . The linear program maximizes the objective function (hence
these utility variables must have the minimum possible values), subject to the constraints (1), (3), (4), (5) of
the relaxed IP (note that constraints (2) are already satisfied). All the constraints (3), (4), (5) of the relaxed
IP have the form v ≥ v ′ + b where v, v ′ are two variables from the set V = {uS : S ⊆ [n]} ∪ {u′∅ } and b
has the form c1 h + c2 δ, where c1 , c2 are integers and |c2 | ≤ O(n2n ) (note that all hi have this form with
c2 ∈ [0, 2n ], α also has this form with c2 ∈ [0, (n/2)2n ], and the allocation variables have value 0 or 1).
Recall that h = 22n and δ = 1/23n . The problem of finding the optimal utilities becomes a shortest-path
problem over 2n + 2 vertices: the set V plus an extra vertex 0 as the source vertex. The distance from 0
to each vertex in V is set to 0 and the distance from v ′ to v is set to −b if v ≥ v ′ + b is a constraint in the
relaxed IP. The optimal value of u′∅ is then the length of the shortest path from vertex 0 to vertex u′∅ with
15

the sign changed. Hence u′∅ is a sum of at most 2n + 1 edge weights (−b), with each of them being an
integer multiple c1 of h plus an integer multiple c2 of δ (with |c2 | ≤ O(n2n )). As a result, u′∅ is of the form
d1 h + d2 δ where d1 and d2 are both integers and |d2 | = O(n22n ). For u′∅ to be positive, we have either
d1 > 0, in which case u′∅ = Ω(h) (as δ = 1/23n ), or d1 = 0 and d2 > 0, in which case u′∅ ≥ δ.
Now we modify the given solution to obtain a new solution. We then show that the new solution is
also feasible and its expected revenue is strictly higher. Let D denote the set of all subsets S ⊂ [n] with
P
P
i∈S hi < α, and U denote the set of all S ⊆ [n] with
i∈S hi ≥ α. We modify the solution as follows:
i) We set xS,i = 0 and zS = 0 for all S ∈ D and i ∈
/ S;
P
ii) We change u′∅ to 0 and u′S to i∈S hi ;

P
iii) For each S ∈ D we change uS to 0; For each S ∈ U we change uS to i∈S hi − α (which
is nonnegative by the definition of U and can only go down compared to the old solution
by constraints (4) using x′∅,i = 1 from Lemma 4.4 and z∅′ = 1 from Lemma 4.3).
Every other entry remains the same as in the original solution.
We first show that the new solution is feasible. Constraints in (2) are trivial. For (3), if S ∈ D, we have
P
P
uS = 0 and zS = 0 and thus, the RHS is − i∈S hi ≤ 0 = u′∅ ; if S ∈ U , we have uS = i∈S hi − α and
thus, the RHS is −α + α · zS ≤ 0 = u′∅ . For constraints in (4), if S ∈ D, we have uS = 0 and the RHS is
P
P
i∈S hi − α = uS . Finally for (5),
i∈S hi − α < 0 = uS (by the definition of D); if S ∈ U the RHS is
the constraint is trivial if both S of T are in U , or both of them are in D. The only case left is that S ∈ U
and T ∈ D (the other case of S ∈ D and T ∈ U cannot happen as T ⊂ S), in which case the constraint is
trivial since uT = 0 and xT,i = 0 for all i ∈
/ T . This finishes the feasibility proof.
Next we bound the net gain of expected revenue in the new solution. For this purpose we discuss two
cases: a) There exists an S with |S| < n/2 (and thus, S ∈ D) such that zS = 1 in the original solution; and
b) Every S with |S| < n/2 has zS = 0 in the original solution.
We start with the first case. The existence of such an S implies that u′∅ ≥ Ω(h) in the original solution
by constraint (3). Note that the utility uS for every S does not increase and the utility u′S for every S goes
down by at least Ω(h). Therefore the expected revenue goes up by at least
Ω(h) · (τ − ǫ) − Pr[∅, σ] · n −

X

(n + σ) · Pr[S, σ]

∅6=S∈D

≥ Ω(h) − (1 − τ + ǫ) · n − O(σ) · (1 − τ + ǫ) · (1 − (1 − p)n ) > 0.
For the last term, we plug in 1 − τ + ǫ = O(α/(σ + α)) = O(α/σ) and (1 − p)n ≥ 1 − pn to have
 α

O(σ) · (1 − τ + ǫ) · (1 − (1 − p)n ) = O σ · · pn = O(n2 ) = o(h).
σ

For the second case, we use u′∅ ≥ δ. Let D ′ denote the set of S with |S| < n/2. Since zS = 0 for all
S ∈ D ′ in the original solution, the expected revenue goes up by at least
δ · (τ − ǫ) −

X

S∈D ′

n · Pr[S, σ] −

X

(n + σ) · Pr[S, σ]

S∈D\D ′

≥ Ω(δ) − (1 − τ + ǫ) · n − O(σ) · (1 − τ + ǫ) · Pr[n/2].
For the last term, we have O(σ) · (1 − τ + ǫ) = O(α) = O(n22n ) and Pr[n/2] < 2n · pn/2 . As a result,
their product is much smaller than δ = 1/23n as p = O(1/22n ). This finishes the proof.
16

Let D and U be the sets defined in the proof above. We have the following simple corollary:
Corollary 4.7. In any optimal solution to the relaxed IP, if z∅ = 0 then zS = 0 for all S ∈ D.
P
P
Proof. By constraints (3), for S ∈ D: 0 ≥ uS − i∈S hi + α · zS . Thus, α · zS ≤ i∈S hi < α.
Next we show that if z∅ = 0 in an optimal solution, then xS,i = 0 for all S ∈ D and i ∈
/ S.

Lemma 4.8. In an optimal solution, if z∅ = 0 then xS,i = 0 for all S ∈ D and i ∈
/ S.
Proof. Assume for contradiction that we do not have xT,i = 0 for all sets T ∈ D and i ∈
/ T . (For reasons
that will become clear later we need special treatments for not only those T at level n/2 but those at level
(n/2) − 1 as well.) We use G to denote the set of pairs (T, k) such that |T | < (n/2) − 1, k ∈
/ T and
∗
xT,k = 1; we use G to denote the set of pairs (T, k) such that |T | = (n/2) − 1, k ∈
/ T , T ∪ {k} ∈ U and
xT,k = 1; we use G1† to denote the set of pairs (T, k) such that |T | = (n/2) − 1, k ∈
/ T , T ∪ {k} ∈ D
(so it follows from the first condition that B and W satisfy that n ∈
/ T ∪ {k}) and xT,k = 1; we use G2† to
denote the set of pairs (T, k) such that |T | = n/2, T ∈ D, k ∈
/ T and xT,k = 1. Then G ∪ G ∗ ∪ G1† ∪ G2†
†
†
is nonempty. We next use G, G ∗ , G1 and G2 to define two sets E and E † , where E consists of subsets of size
n/2 and E † consists of subsets of size n/2 + 1 so they are disjoint.
1. S ⊂ [n] is in E if |S| = n/2, S ∈ U and T ∪ {k} ⊆ S for some pair (T, k) ∈ G ∪ G ∗ .
2. S ⊂ [n] is in E † if |S| = (n/2) + 1 and satisfies either S = T ∪ {k} for some pair (T, k) ∈ G2† or
S = T ∪ {k, r} for some pair (T, k) ∈ G1† with r being the smallest index not in T ∪ {k}.
We need the following simple claim about zS , S ∈ E ∪ E † , in the original solution.
Claim 4.9. We have zS = 0 for every S ∈ E ∪ E † in the original solution.
Proof. For each S ∈ E (with T ∪ {k} ⊆ S for some (T, k) ∈ G ∪ G ∗ ) we have from constraint (5):
uS ≥ uT +

X

hi · xT,i ≥ hk

i∈S\T

and thus, by constraint (3):
0 = u′∅ ≥ uS −

X

hi + α · zS ≥ −((n/2) − 1)h −

i∈S

X

ai + α · zS ,

i∈S\{k}

which implies that zS = 0 since α ≥ (n/2)h and h ≫ ai .
For each S ∈ E † , if S = T ∪ {k} for some (T, k) ∈ G2† , we have uS ≥ hk and by constraint (3):
0 = u′∅ ≥ uS −

X

hi + α · zS ≥ −

i∈S

X

hi + α · zS ,

i∈T

P

which implies that zS = 0 since T ∈ D implies that i∈T hi < α.
Finally if S ∈ E † satisfies S = T ∪ {k, r} for some (T, k) ∈ G1† , we have uS ≥ hk and thus,
0 = u′∅ ≥ uS −

X

hi + α · zS ≥ −

i∈S

X

i∈T ∪{r}

17

hi + α · zS .

Note that n ∈
/ T (by the first condition of B and W and the fact that T ∪ {k} ∈ D), r 6= n, and T ∪ {r}
contains either 1 or 2 (by our choice of r, as the smallest index not in T ∪ {k}). Using the second condition
P
about B and W , we have i∈T ∪{r} hi < α and thus, zS = 1. This finishes the proof.
Claim 4.9 inspires us to derive a new solution by making the following changes in the old one:

i) For all (T, k) ∈ G ∪ G ∗ ∪ G1† ∪ G2† , change xT,k from 1 to 0 (so that xT,k = 0 in the new solution for
all T ∈ D and k ∈
/ T );
ii) For all S ∈ E ∪ E † , change zS from 0 to 1;
P
iii) For all S ∈ D, change uS to 0; For all S ∈ U , change uS to i∈S hi − α (note that the new uS is
nonnegative as S ∈ U and can only go down from the original by constraint (4)).
All other entries remain the same in the new solution.
We first verify that the new solution is feasible and then show that it is strictly better than the old solution.
For the feasibility, constraints (2) are trivial. For (3), the constraint is trivial if S ∈ D (since uS = zS = 0);
P
if S ∈ U , we have uS = i∈S hi − α and thus, the RHS is at most 0. For (4), the constraint is trivial if
S ∈ D (since the RHS is negative); if S ∈ U , the LHS and RHS are the same. For (5), the constraint is
trivial if T ∈ D (since the RHS is 0); otherwise we have both S and T are in U and the constraint follows
P
P
from uS = i∈S hi − α and uT = i∈T hi − α in the new solution. This finishes the proof of feasibility
of the new solution.
Note that each utility variable in the new solution can only go down from that in the old solution. As a
result, the net gain of expected revenue in the new solution is at least
X

X

σ · Pr[S, σ] −

S∈E∪E †

Pr[T, σ].

(T,k)∈G∪G ∗ ∪G1† ∪G2†

Ignoring the common factor of 1 − τ + ǫ and rearranging the terms, we obtain

 
X
X
X
 X
σ
Pr[S] −
Pr[T ] + σ
Pr[S] −
S∈E

(T,k)∈G∪G ∗

S∈E †

(T,k)∈G1† ∪G2†




Pr[T ] .

Below we show that the first term is positive if G ∪ G ∗ is nonempty and the second term is positive if G1† ∪ G2†
is nonempty. This shows that the expected revenue goes up strictly in the new solution.
We start with the second term which is easier. By the definition of E † from G1† and G2† , we have
|G2† | ≤ ((n/2) + 1) · |E † | and

|G1† | ≤ ((n/2) + 1) · (n/2) · |E † |.

Thus, the second term is at least
σ · |E † | · p(n/2)+1 (1 − p)(n/2)−1 − n · |E † | · pn/2 (1 − p)n/2 − n2 · |E † | · p(n/2)−1 (1 − p)(n/2)+1 > 0
when E † 6= ∅ since p2 σ ≫ pn + n2 . This finishes the proof, as E † 6= ∅ whenever G1† ∪ G2† 6= ∅.
For the first term, note that |G ∗ | ≤ (n/2) · |E| and thus,
X

Pr[T ] ≤ (n/2) · |E| · p(n/2)−1 (1 − p)(n/2)+1 .

(T,k)∈G ∗

18

To understand the sum over (T, k) ∈ G, we decompose G into G0 , . . . , G(n/2)−2 where Gℓ contains all the
pairs (T, k) ∈ G with |T | = ℓ. Fixing an ℓ, we examine the following bipartite graph between Gℓ and E:
(T, k) ∈ Gℓ and S ∈ E (and thus, S ∈ U ) are connected if T ∪ {k} ⊆ S. We claim that every (T, k) ∈ Gℓ
has at least one edge (it has a lot more but one is enough for our purpose).
To see this, we consider two cases: n ∈ T ∪ {k} or n ∈
/ T ∪ {k}. For the first case, from the first
condition on B and W , every set S of size n/2 that contains T ∪ {k} is in E and is connected with (T, k).
For the second case, every set S of size n/2 that contains T ∪ {k, n} is in E and is connected with (T, k).
(Here we used the fact that ℓ ≤ n/2 − 2 so T ∪ {k, n} has size no more than n/2, which is why we treated
sets of size n/2 − 1 differently throughout the proof.)
As a result, the number of edges between Gℓ and E is at least |Gℓ | but is at most


n/2
|E| ·
· (n/2 − ℓ).
ℓ
Therefore, we have
|E| ≥

|Gℓ |
n/2
ℓ

This implies that

· (n/2 − ℓ)

> |Gℓ | ·

1
.
n2n

P
Pr[S]
pn/2
1
pn/2
|E| · pn/2 · (1 − p)n/2
P S∈E
>
·
=
.
=
|Gℓ | · pℓ · (1 − p)n−ℓ
2pℓ n2n
2n2n pℓ
(T,k)∈Gℓ Pr[T ]

Therefore, we have

n/2−2

X

Pr[T ] =

X

X

Pr[T ] <

ℓ=0 (T,k)∈Gℓ

(T,k)∈G

! n/2−2
X
2n2n X
4n2n X
ℓ
·
Pr[S]
·
·
Pr[S].
p
<
n/2
pn/2 S∈E
p
S∈E
ℓ=0

Plugging in our choice of σ = 1/pn , we have
σ

X

S∈E

Pr[S] −

X

(T,k)∈G∪G ∗

Pr[T ] ≥



 X
4n2n
Pr[S] > 0
σ − n/2 − O(n/p) ·
p
S∈E

when E =
6 ∅. Our argument above also shows that E =
6 ∅ whenever G ∪ G ∗ 6= ∅.
Finally we prove the second part of Lemma 4.1. Lemma 4.1 follows from Lemma 4.5 and 4.10.
Lemma 4.10. In an optimal solution to the relaxed IP, if z∅ = 0, then it must be Solution 2.
Proof. We show that, when z∅ = 0, every utility variable in the optimal solution is at least as large as that
in Solution 2, and every allocation variable is at most as large as that in Solution 2. So for it to be optimal,
it must be exactly the same as Solution 2.
For utilities we first note that u′S is the same in both solutions for all S ⊆ [n] since in both we have
P
u′∅ = 0 and u′S = i∈S hi . Next for each S ∈ D, we have uS = 0 in Solution 2. Finally, for each S ∈ U
P
P
we have from constraint (4) that uS ≥ u′∅ + i∈S hi − α = i∈S hi − α in the optimal solution, which is at
least as large as uS in Solution 2. For allocation variables, we first have x′S,i = zS′ = 1 in both solutions for
all S ⊆ [n] and i ∈ [n]. Next we have xS,i = 1 in both solutions for all S ⊆ [n] and i ∈ S. For each S ∈ D,
we have xS,i = zS = 0 in both solutions for all i ∈
/ S. Finally for each S ∈ U , we have xS,i = zS = 1 in
Solution 2 for all i ∈
/ S. This finishes the proof of the lemma.
19

4.6 Finishing the reduction from COMP∗
Finally, we show that with an appropriate choice of ǫ (with |ǫ| = o(1/σ) as promised) that can be computed
in polynomial time, we have 1) Solution 2 is strictly better than Solution 1 if (B, W, t) is a yes-instance of
COMP∗ ; and 2) Solution 1 is strictly better than Solution 2 if it is a no-instance.
The expected revenue of Solution 1 is Rev1 = n + σ. Let t∗ be the number of (n/2)-sets S ⊂ [n] with
P
is a yes-instance if t∗ ≥ t and is a no-instance if t∗ ≤ t − 1) and let R
i∈S hi ≥ α (recall that (B, W, t)
P
be the set of all sets S ⊂ [n] with i∈S hi < α. Then Rev2 of Solution 2 is



Rev2 = (n + σ + α) (τ − ǫ) + (1 − τ + ǫ) Pr[i > n/2] + t∗ · pn/2 · (1 − p)n/2
X
X
+ (1 − τ + ǫ)
Pr[S]
(hi + 1).
S∈R

i∈S

Below we use a = b ± c to denote |a − b| ≤ c. The sum
X

(hi + 1)p −

X

Pr[S]

S ∈R
/

i∈[n]

P

S∈R Pr[S] ·

P

i∈S (hi

+ 1) is equal to

X
X
(hi + 1) =
(hi + 1)p ± O(2n pn/2 nh).
i∈S

i∈[n]

Then Rev2 is equal to B − Aǫ, where
 X

X
Pr[S]
(hi + 1)
A = (n + σ + α) 1 − Pr[i > n/2] − t∗ · pn/2 · (1 − p)n/2 −
S∈R
i∈S


X

= (n + σ + α) 1 − Pr[i > n/2] −
(hi + 1)p ± O(σ2n pn/2 )
i∈[n]

= A′ ± O(σ2n pn/2 ),

where A′ = Θ(σ) is a number that we can compute efficiently. On the other hand, we note for B that
Pr[i > n/2] ≤ 2n pn/2+1 and (n + σ + α) · (1 − τ ) = O(α). As a result, we have


X
(hi + 1)p ± O(α2n pn/2+1 ).
B = (n + σ + α) τ + (1 − τ ) · t∗ · pn/2 · (1 − p)n/2 + (1 − τ )
i∈[n]

For convenience we write B as B = B ′ + C ′ · t∗ ± O(α2n pn/2+1 ), where
B ′ = (n + σ + α)τ + (1 − τ )

X

(hi + 1)p

and

C ′ = (n + σ + α) · (1 − τ ) · pn/2 · (1 − p)n/2

i∈[n]

can also be computed efficiently. Plugging in τ = σ/(σ + α) and hi = h + ai , we have
B ′ = (n + σ + α)τ + (1 − τ )n(h + 1)p + (1 − τ )p

X

ai

i∈[n]

=σ+

X
α
1
nσ
+
· n(h + 1) ·
+ (1 − τ )p
ai
σ+α σ+α
2(h + 1)
i∈[n]

= σ+n−

αn
+ (1 − τ )p
2(σ + α)

20

X

i∈[n]

ai .

Finally we choose ǫ to be (recall t is between 1 and 2n ; otherwise the problem is trivial)


X

αn
1  ′
+ (1 − τ )p
ai  ,
ǫ = ′ · C t − (1/2) −
A
2(σ + α)
i∈[n]

which can be computed efficiently and satisfies (using |A′ | = Θ(σ))


|ǫ| ≤ (1/A′ ) · O(αpn/2 2n ) + O(αn/σ) = O(αpn/2 2n /σ) = o(1/σ).

Plugging in our choice of ǫ, we have Rev2 − Rev1 = C ′ (t∗ − t + 1/2) ± O(α2n pn/2+1 ). Note that
C ′ = Ω(αpn/2 ) ≫ O(α2n pn/2+1 ). If t∗ ≥ t, Solution 2 is strictly better than Solution 1; if t∗ ≤ t − 1,
Solution 1 is strictly better. This finishes the proof of Theorem 1.2.

5 Constant Number of Items
In this section we prove Theorem 1.5. Let F = F1 × · · · × Fk be an instance of bundle-pricing for some
constant number of items k and assume without loss of generality that |SUPPORT (Fi )| = m for all i ∈ [k].
In this case, there are mk possible valuation vectors (a polynomial number), and d = 2k possible distinct
bundles (a constant number). The standard IP in this case has a polynomial number of variables and constraints. However, Integer Programming is NP-hard, so we will use a different method to solve the problem
in polynomial time. For the rest of this section, we assume two arbitrary orderings, one for the valuation
vectors and one for the bundles, and we will use vi to denote the ith valuation vector, and B(j) to denote
the jth bundle and pj to denote its price.
We will argue that we can generate in polynomial time a set of price vectors p that includes an optimal
one; we can then compute the expected revenue for each of these vectors and pick the best one. To this end,
we consider a partitioning of the d-dimensional space of possible price vectors p into cells, such that for all
p in the same cell, the buyer has the same behavior for every vi , i.e., buys the same bundle, if any. Consider
the following set H of hyperplanes over p.
P
1. For each valuation vi and bundle B(j), the set H includes ℓ∈B(j) vi,ℓ − pj = 0. (If the price vector
p is below the hyperplane, the buyer will not consider bundle B(j) for valuation vi .)
2. For each valuation vi and each pair of bundles B(j) and B(j ′ ), the set H includes the hyperplane
P
P
′
ℓ∈B(j) vi,ℓ − pj =
ℓ∈B(j ′ ) vi,ℓ − pj ′ . Note that for vi , the buyer prefers B(j) to B(j ) if p is on
one side of the hyperplane, she prefers B(j ′ ) to B(j) if p is on the other side, and if p lies on the
hyperplane itself then it depends on the order between the prices pj , pj ′ .
3. For each pair of bundles B(j) and B(j ′ ), the set H includes the hyperplane pj = pj ′ .
These hyperplanes partition the space of prices into cells, where a cell consists of all price vectors
that have the same relation to each of these hyperplanes, i.e., lie in the same open half-space or on the
hyperplane. We can assume that for a valuation vi and price vector p, if there is a tie both in utility and in
the price between some bundles, then the buyer selects a bundle according to some fixed tie-breaking rule,
for example she chooses among the tied bundles the one with the smallest index (the rule does not matter
for the revenue). It follows from the definition of the set H of hyperplanes, that for every cell C and every
valuation vi there is ki ∈ [d] such that the buyer selects the same bundle B(ki ) for every price vector p in
C, or buys no bundle (if they all have negative utility). Let VC (j) be the set of valuations for which the
21

P
buyer selects bundle B(j) if the price vector p ∈ C, and let QC (j) = Pr[VC (j)] = {Pr[vi ]|vi ∈ VC (j)}
be the probability that the buyer selects bundle B(j). The supremum revenue that the seller can extract for
P
a price vector p in the cell C, can be computed by solving the LP of maximizing j QC (j) · pj , subject
to p belonging to the closure of the cell C, i.e., p satisfying all the weak inequalities corresponding to the
bounding hyperplanes of C. By LP theory, the maximum value of the LP is achieved at some vertex; even if
the vertex does not belong to C but is in the closure, the corresponding price vector achieves this expected
revenue (by the maximum price tie breaking rule). The maximum over all cells C gives the supremum
revenue that can be achieved by any price vector. Thus, the supremum revenue is achieved at some vertex,
i.e., at the intersection of some d hyperplanes of the set H.
Therefore, we can compute an optimal solution by generating all vertices and picking the best one. For
every subset of d = 2k hyperplanes of H, solve the corresponding linear system of equations to check if
the hyperplanes intersect at a unique point p, and if p is nonnegative (if a price is negative then p cannot
be optimal). If so, compute the expected revenue of p by examining each valuation vi and determining
the bundle selected for vi , if any. Choose among these price vectors p the one that yields the maximum
revenue. The set H has a polynomial number of hyperplanes, and the dimension d = 2k is constant, so we
will consider a polynomial number of subsets to generate the set of price vectors p. Since the number of
valuations is polynomial, it takes polynomial time to compute the revenue of each vector p. Hence the total
time is polynomial. This finishes the proof of Theorem 1.5.

6 Conclusions
In this work, we studied the optimal bundle-pricing problem (or equivalently, the Revenue-Optimal Deterministic Mechanism Design problem). We showed that the problem is intractable (#P-hard) even when the
(independent) item distributions have support size 2 and the optimal solution has a very simple form of discounted item-pricing: the seller prices the individual items and offers also the grand bundle at a (possibly)
discounted price. Another consequence of the results is that there is no ‘nice’ (easy-to-check) characterization of when separate item pricing, or grand bundling extracts the maximum revenue DR EV (F) achievable
by any bundle-pricing. On the positive side, we showed that for i.i.d. distributions with support size 2, the
maximum revenue R EV (F) achievable by any lottery pricing can always be achieved by a discounted itempricing, and we can compute it in polynomial time. The problem can be also solved in polynomial time for
a constant number of items.
A number of interesting problems present themselves. First, we know from Babaioff et al. [BILW14]
that discounted item-pricing always achieves a constant fraction (at least 1/6th) of the maximum revenue;
what is the constant that can always be guaranteed with respect to the deterministic and randomized maximum revenue? Second, we know that we can compute efficiently an optimal item pricing, and it can be
shown that we can also compute an (1 − ǫ)-approximately optimal grand bundle price; can we compute
efficiently an (1 − ǫ)-approximately optimal discounted item pricing? (We believe this is the case.) Third,
besides extending simple item-pricing with the grand bundle, it is more generally natural to offer discounts
on disjoint groups of items, as in partition mechanisms. How powerful are such partitioned discounted itempricings, and can we compute efficiently an (1 − ǫ)-approximately optimal solution of this type? Finally,
regarding i.i.d. distributions, we know that randomization can increase the revenue for support size 3 in some
cases (an example is given by Hart and Nisan [HN12]). Are simple schemes able to extract (approximately)
the maximum revenue DR EV (F) achievable by any bundle pricing for general i.i.d. distributions?

22

References
[BCKW10] P. Briest, S. Chawla, R. Kleinberg, and S.M. Weinberg, Pricing randomized allocations, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 585–
597.
[BILW14]

M. Babaioff, N. Immorlica, B. Lucier, and S.M. Weinberg, A simple and approximately optimal
mechanism for an additive buyer, 55th IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, 2014, pp. 21–30.

[Bri08]

P. Briest, Uniform budgets and the envy-free pricing problem, Proceedings of the 35th International Colloquium on Automata, Languages and Programming, 2008, pp. 808–819.

[CD11]

Y. Cai and C. Daskalakis, Extreme-value theorems for optimal multidimensional pricing, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 2011,
pp. 522–531.

[CDO+ 15] X. Chen, I. Diakonikolas, A. Orfanou, D. Paparas, X. Sun, and M. Yannakakis, On the complexity of optimal lottery pricing and randomized mechanisms, Proceedings of the 56th Annual
IEEE Symposium on Foundations of Computer Sciences, 2015.
[CDP+ 14] X. Chen, I. Diakonikolas, D. Paparas, X. Sun, and M. Yannakakis, The complexity of optimal multidimensional pricing, Proceedings of the 25th ACM-SIAM Symposium on Discrete
Algorithms, 2014.
[CH13]

Y. Cai and Z. Huang, Simple and nearly optimal multi-item auctions, Proceedings of the 24th
ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 564–577.

[CHK07]

S. Chawla, J.D. Hartline, and R.D. Kleinberg, Algorithmic pricing via virtual valuations, Proceedings of the 8th ACM Conference on Electronic Commerce, 2007, pp. 243–251.

[CHMS10] S. Chawla, J.D. Hartline, D.L. Malec, and B. Sivan, Multi-parameter mechanism design and
sequential posted pricing, Proceedings of the 42nd Annual ACM Symposium on Theory of
Computing, 2010, pp. 311–320.
[CMS10]

S. Chawla, D.L. Malec, and B. Sivan, The power of randomness in bayesian optimal mechanism
design, Proceedings of the 11th ACM Conference on Electronic Commerce, 2010, pp. 149–
158.

[DDT12]

C. Daskalakis, A. Deckelbaum, and C. Tzamos, Optimal pricing is hard, Proceedings of the
8th Workshop on Internet and Network Economics, 2012, pp. 298–308.

[DDT13]

, Mechanism design via optimal transport, Proceedings of the 14th ACM conference
on Electronic commerce, 2013, pp. 269–286.

[DDT14]

, The complexity of optimal mechanism design, Proceedings of the 25th ACM-SIAM
Symposium on Discrete Algorithms, 2014, pp. 1302–1318.

[DDT15]

C. Daskalakis, A. Deckelbaum, and C. Tzamos, Strong duality for a multiple-good monopolist,
Proceedings of the Sixteenth ACM Conference on Economics and Computation (New York,
NY, USA), EC ’15, 2015.
23

[DW12]

C. Daskalakis and S.M. Weinberg, Symmetries and optimal multi-dimensional mechanism design, Proceedings of the 13th ACM Conference on Electronic Commerce, 2012, pp. 370–387.

[GHK+ 05] V. Guruswami, J.D. Hartline, A.R. Karlin, D. Kempe, C. Kenyon, and F. McSherry, On profitmaximizing envy-free pricing, Proceedings of the 16th Annual ACM-SIAM Symposium on
Discrete Algorithms, 2005, pp. 1164–1173.
[GK14]

Y. Giannakopoulos and E. Koutsoupias, Duality and optimality of auctions for uniform distributions, Proceedings of the 14th ACM Conference on Electronic Commerce, 2014, pp. 259–276.

[HN12]

S. Hart and N. Nisan, Approximate revenue maximization with multiple items, Proceedings of
the 13th ACM Conference on Electronic Commerce, 2012, pp. 656–656.

[HN13]

S. Hart and N. Nisan, The menu-size complexity of auctions, Proceedings of the 14th ACM
Conference on Electronic Commerce, 2013, pp. 565–566.

[LY13]

X. Li and A.C.-C. Yao, On revenue maximization for selling multiple independently distributed
items, Proceedings of the National Academy of Sciences of the United States of America, vol.
110, 2013, pp. 11232–11237.

[MV06]

A.M. Manelli and D.R. Vincent, Bundling as an optimal selling mechanism for a multiple-good
monopolist, Journal of Economic Theory 127 (2006), no. 1, 1–35.

[Mye81]

R.B. Myerson, Optimal auction design, Mathematics of Operations Research 6 (1981), no. 1,
58–73.

[Pav10]

G. Pavlov, Optimal Mechanism for Selling Two Goods, UWO Department of Economics Working Papers 20103, University of Western Ontario, Department of Economics, 2010.

[Rub16]

A. Rubinstein, On the computational complexity of optimal simple mechanisms, Proceedings of
the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA,
USA, January 14-16, 2016, 2016, pp. 21–28.

[Tha04]

J. Thanassoulis, Haggling over substitutes, Journal of Economic Theory 117 (2004), no. 2,
217–245.

[WT14]

Z. Wang and P. Tang, Optimal mechanisms with simple menus, Proceedings of the 15th ACM
Conference on Economics and Computation, 2014, pp. 227–240.

[Yao15]

A.C.-C. Yao, An n-to-1 bidder reduction for multi-item auctions and its applications, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 92–109.

24

