Learning Multi-item Auctions with (or without) Samples

arXiv:1709.00228v1 [cs.GT] 1 Sep 2017

Yang Cai
McGill University, Canada
cai@cs.mcgill.ca

Constantinos Daskalakis
EECS and CSAIL, MIT, USA
costis@csail.mit.edu

September 4, 2017

Abstract
We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item
multi-bidder settings, for a wide range of bidder valuations including unit-demand, additive, constrained
additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly
studied setting where sample access to the bidders’ distributions over valuations is given, for both regular
distributions and arbitrary distributions with bounded support. Here, our algorithms require polynomially
many samples in the number of items and bidders. The second is a more general max-min learning setting
that we introduce, where we are given “approximate distributions,” and we seek to compute a mechanism
whose revenue is approximately optimal simultaneously for all “true distributions” that are close to the ones
we were given. These results are more general in that they imply the sample-based results, and are also
applicable in settings where we have no sample access to the underlying distributions but have estimated
them indirectly via market research or by observation of bidder behavior in previously run, potentially
non-truthful auctions.
All our results hold for valuation distributions satisfying the standard (and necessary) independenceacross-items property. They also generalize and improve upon recent works of Goldner and Karlin [28]
and Morgenstern and Roughgarden [35], which have provided algorithms that learn approximately optimal
multi-item mechanisms in more restricted settings with additive, subadditive and unit-demand valuations
using sample access to distributions. We generalize these results to the complete unit-demand, additive,
and XOS setting, to i.i.d. subadditive bidders, and to the max-min setting.
Our results are enabled by new uniform convergence bounds for hypotheses classes under product
measures. Our bounds result in exponential savings in sample complexity compared to bounds derived by
bounding the VC dimension, and are of independent interest.

1 Introduction
The design of revenue-optimal auctions is a central problem in Economics and Computer Science, which has
found myriad applications in online and offline settings, ranging from sponsored search and online advertising
to selling artwork by auction houses, and public goods such as drilling rights and radio spectrum by governments. The problem involves a seller who wants to sell one or several items to one or multiple strategic bidders
with private valuation functions, mapping each bundle of items they may receive to how much value they
derive from the bundle. As no meaningful revenue guarantee can possibly be achieved without any information about the valuations of the bidders, the problem has been classically studied under Bayesian assumptions,
where a joint distribution from which all bidders’ valuations are drawn is common knowledge, and the goal is
to maximize revenue in expectation with respect to this distribution.
In the single-item setting, Bayesian assumptions have enabled beautiful and influential developments in
auction theory. Already 36 years ago, a breakthrough result by Myerson identified the optimal single-item
auction when bidder values are independent [36], and the ensuing decades saw a great deal of further understanding and practical applications of single-item auctions, importantly in online settings.
However, the quest for optimal multi-item auctions has been quite more challenging. It has been recognized
that revenue-optimal multi-item auctions can be really complex, may exhibit counter-intuitive properties, and
be fragile to changes in the underlying distributions; for a discussion and examples see survey [18]. As such,
it is doubtful that there is a crisp characterization of the structure of optimal multi-item auctions, at least not
beyond single-bidder settings [19]. On the other hand, there has been significant recent progress in efficient
computation of revenue-optimal auctions [14, 15, 1, 7, 3, 8, 9, 12, 10, 2, 6, 20]. Importantly, this progress has
enabled identifying simple auctions (mostly variations of sequential posted pricing mechanisms) that achieve
constant factor approximations to the revenue of the optimum [5, 42, 11, 16, 13], under the item-independence
assumption of Definition 1 and Example 1. These auctions are way simpler than the optimum, and have strong
incentive properties: they are dominant strategy truthful, while still competing against the optimal Bayesian
truthful mechanism. The current state-of-the-art is given as Theorem 8, which applies to bidders with valuation
functions from the broad class of fractionally subbaditive (a.k.a. XOS) valuations, which contains submodular.
As our discussion illustrates, studying auctions assuming Bayesian priors has been quite fruitful, enabling
us to identify guiding principles for how to structure auctions to achieve optimal (in single-item settings)
or approximately optimal (in multi-item settings) revenue. To apply this theory to practice, however, one
needs knowledge of the underlying distributions. Typically, one would estimate these distributions via market
research or by observations of bidder behavior in prior auctions, then use the estimated distributions to design
a good auction. However, estimation involves approximation, and the performance of mechanisms can be
quite fragile to errors in the distributions. This motivates studying whether optimal or approximately optimal
auctions can be identified when one has imperfect knowledge of the true distributions.
With this motivation, recent work in Computer Science has studied whether approximately optimal mechanisms can be “learned” given sample access to the underlying distributions. This work has lead to an almost
complete picture for the single-item (and the more general single-parameter) setting where Myerson’s theory
applies, showing how near-optimal mechanisms can be learned from polynomially many (in the approximation
and the number of bidders) samples [26, 17, 33, 31, 34, 22, 38, 29].
On the multi-item front, however, where the analogue of Myerson’s theory is elusive, and unlikely, our
understanding is much sparser. Recent work of Morgenstern and Roughgarden [35] has taken a computational
learning theory approach to identify the sample complexity required to optimize over classes of simple auctions. Combined with the afore-described results on the revenue guarantees of simple auctions, their work
leads to algorithms that learn approximately optimal auctions in multi-item settings with multiple unit-demand
bidders, or a single subadditive bidder, from polynomially many samples in the number of items and bidders. These results apply to distributions satisfying the item-independence assumption of Definition 1 and
1

Example 1, under which the approximate optimality of simple auctions has been established.
While well-suited for identifying the sample complexity required to optimize over a class of simple mechanisms, which is a perfectly reasonable goal to have but not the one in this paper, the approach taken in [35] is
arguably imperfect towards proving polynomial sample bounds for learning approximately optimal auctions in
the settings where simple mechanisms are known to perform well in the first place. This is due to the following
discordance: (i) On the one hand, simple and approximately optimal mechanisms in multi-item settings are
mostly only known under item-independence. (ii) On the other hand, the computational learning techniques
employed in [35], and in particular bounding the pseudo-dimension of a class of auctions, are not fine enough
to discern the difference in sample complexity required to optimize under item-independence and without itemindependence. As such, this technique can only obtain polynomial sample bounds for approximate revenue
optimization if it so happens that a class of mechanisms is both learnable from polynomially-many samples
under arbitrary distributions, and it guarantees approximately optimal revenue under item-independence, or
for some other interesting class of distributions.1
In particular, bounding the pseudo-dimension of classes of auctions as a means to prove polynomialsample bounds for approximate revenue optimization hits a barrier even for multiple additive bidders with
independent values for items. In this setting, the approximately optimal auctions that are known are the best of
selling the items separately or running a VCG mechanism with entry fees [42, 11], as described in Section 5.2.
Unfortunately, the latter can easily be seen to have pseudo-dimension that is exponential in the number of
bidders, thus only implying a sufficient exponentially large sample size to optimize over these mechanisms.
Is this exponential sample size really necessary or an artifact of the approach? Recent work of Goldner and
Karlin [28] gives us hope that it is the latter. They show how to learn approximately optimal auctions in the
multi-item multi-bidder setting with additive bidders using only one sample from each bidder’s distribution,
assuming that it is regular and independent across items.
Our results. We show that simple and approximately optimal mechanisms are learnable from polynomiallymany samples for multi-item multi-bidder settings, whenever:
• the bidder valuations are fractionally subadditive (XOS), i.e. we can accommodate additive, unitdemand, constrained additive, and submodular valuations;
• the distributions over valuations satisfy the standard item-independence assumption of Definition 1 and
Example 1, and their single-item marginals are arbitrary and bounded, or (have arbitrary supports but
are) regular.2
In particular, our results constitute vast extensions of known results on the polynomial learnability of approximately optimal auctions in multi-item settings [35, 28]. Additionally we show that:
• whenever the valuations are additive and unit-demand, or whenever the bidders are symmetric and have
XOS valuations, our approximately optimal mechanisms can be identified from polynomially many
samples and in polynomial time;
• whenever the bidders are symmetric (i.e. their valuations are independent and identically distributed) and
have subadditive valuations, we can computefrom polynomially
many samples and in polynomial-time

n
a simple mechanism whose revenue is a Ω max{m,n} -fraction of the optimum, where m and n are
respectively the number of items and bidders. In particular, if the number of bidders is at least a constant
fraction of the number of items, the mechanism is a constant factor approximation; and
1

It is known that some restriction needs to be made on the distribution to gain polynomial sample complexity, as otherwise exponential lower bounds are known for learning approximately optimal auctions even for a single unit-demand bidder [24].
2
We note again that without the standard item-independence (or some other) restriction on the distributions, we cannot hope to
learn approximately optimal auctions from sub-exponentially many samples, even for a single unit-demand bidder [24].

2

• in the setting of the previous bullet, if the item marginals are regular, our mechanism is prior-independent,
i.e. there is a single mechanism, identifiable without any samples from the distributions, providing the
afore-described revenue guarantee.
Finally, the mechanisms learned by our algorithms for XOS bidders are either rationed sequential posted price
mechanisms (RSPMs) or anonymous sequential posted price mechanisms with entry fees (ASPEs) as defined
in Section 6. The mechanisms learned for symmetric subadditive bidders are RSPMs. RSPMs maintain a price
pij for every bidder and item pair and, in some order over bidders i = 1, . . . , n, they give one opportunity to
bidder i to purchase one item j that has not been purchased yet at price pij . ASPEs maintain one price pj for
every item and, in some order over bidders i = 1, . . . , n, they give one opportunity to bidder i to purchase any
subset S ′ of the items S that have not been purchased yet as long as he also pays an “entry fee” that depends
on S and the identity of the bidder. See Algorithm 3.
Learning without Samples. Thus far, our algorithms used samples from the valuation distributions to identify an approximately optimal and simple mechanism under item-independence. However, having sample access to the distributions may be impractical. Often we can observe the actions used by bidders in non-truthful
auctions that were previously run, and use these observations to estimate the distributions over valuations using
econometric methods [30, 37, 4]. In fact, it may likely be the case we have never sold all the items together in
the past, and only have observations of bidder behavior in non-truthful auctions selling each item separately.
Econometric methods would achieve better approximations in this case, but only for the item marginals. Finally, we may want to combine multiple sources of information about the distributions, combining past bidder
behavior in several different auctions and with market research data.
With this motivation in mind, we would like to extend our learnability results beyond the setting where
sample access to the valuation distributions is provided. We propose “learning” approximately optimal multiitem auctions given distributions that are close to the true distributions under some distribution distance d(·, ·).
In particular, given approximate distributions D̂1 , . . . , D̂n over bidder valuations, we are looking to identify a
mechanism M satisfying the following max-min style objective:
∀D1 , . . . , Dn s.t. d(Di , D̂i ) ≤ ǫ, ∀i : RevM (D1 , . . . , Dn ) ≥ Ω(OPT(D1 , . . . , Dn )) − poly(ǫ, m, n). (1)
That is, we want to find a mechanism M whose revenue is within a constant multiplicative and a poly(ǫ, m, n)
additive error from optimum, simultaneously in all possible worlds D1 , . . . , Dn , where d(Di , D̂i ) ≤ ǫ, ∀i. It
is not a priori clear that such a “one-fits-all” mechanism actually exists.
There are several notions of distance d(·, ·) between distributions that we could study in the formulation
of Goal (1), but we opt for an easy one to satisfy. We only require that we know every bidder’s marginal
distributions over single-item values to within ǫ in Kolmogorov distance;3 see Definition 2. All that this
requires is that the cumulative density functions of the approximating distributions over single-item values
is within ǫ in infinity norm from the corresponding cumulative density functions of the corresponding true
distributions. As such, it is an easy property to satisfy. For example, given sample access to any single-item
marginal, the DKW inequality [25] implies that O(log(1/δ)/ǫ2 ) samples suffice to learn it to within ǫ in
Kolmogorov distance, with probability at least 1 − δ. So achieving Goal (1) directly also implies polynomial
sample learnability of approximately optimal auctions. But a Kolmogorov approximation can also be arrived
at by combining different sources of information about the single-item marginals such as the ones described
above. Regardless of how the approximations were obtained, the max-min goal outlined above guarantees
3
Indeed, Goal (1) is achievable only for bounded distributions even in the single-item single-bidder setting. Given any bounded
distribution D̂, create D by moving ǫ probability mass in D̂ to +∞. It is not hard to see that D and D̂ are within ǫ in Kolmogorov
distance, but no single mechanism can satisfy the approximation guarantee for both D and D̂ simultaneously. Using a similar argument,
we can argue that the additive error has to depend on H which is the upper bound on any bidder’s value for a single item. See Section 2
for our formal model.

3

robustness of the revenue of the identified mechanism M with respect to all sources of error that came into the
estimation of the single-item marginal distributions.
While Goal (1) is not a priori feasible, we show how to achieve it in multi-item multi-bidder settings with
constrained additive bidders, or symmetric bidders with subadditive valuations, under the standard assumption
of item-independence. Our results are polynomial-time in the same cases as our sample-based results discussed
above.
Roadmap and Technical Ideas. In Section 4, we present a new approach for obtaining uniform convergence
bounds for hypotheses classes under product distributions; see Theorem 2 and Corollary 1. We show that our
approach can significantly improve the sample complexity bound obtained via traditional methods such as
VC theory. In particular, Table 3 compares the sample complexity bounds obtained via our approach to those
obtained by VC theory for different classes of hypotheses.
Our results for mechanisms make use of recent work on the revenue guarantees of simple mechanisms,
which are mainly variants of sequential posted pricing mechanisms [11, 13]. Using our results from Section 4, in Section 5, we derive uniform convergence bounds for the revenue of a class of mechanisms shown to
achieve a constant fraction of optimal revenue when all bidders have valuations that are constrained additive
over independent items. These mechanisms are called Sequential Posted Price with Entry Fee Mechanisms,
a.k.a. SPEMs,4 . As a corollary of the uniform convergence of SPEMs, we obtain our sample based results
for constrained additive bidders. In fact, we obtain a slightly stronger statement than uniform convergence of
the revenue of SPEMs, which also implies our max-min results for constrained-additive bidders; see Theorems 3 and 4. In particular, Theorem 4 and the DKW inequality imply the polynomial-sample learnability of
approximately revenue-optimal auctions for constrained additive bidders.
Technically speaking, our sample based and max-min approximation results for constrained additive bidders provide a crisp illustration of how we leverage item-independence and our new uniform convergence
bounds for product measures to sidestep the exponential pseudo-dimension of the class of mechanisms that
we are optimizing over. Let us discuss our max-min results which are stronger. Suppose Di = ×j Dij is the
true distribution over bidder i’s valuation and D̂i = ×j D̂ij is the approximating distribution, where Dij and
D̂ij are respectively the item j marginals. To argue that the revenue of some anonymous sequential posted
price with entry fees (ASPE) mechanism is similar under D = ×i Di and D̂ = ×i D̂i , we need to couple in
total variation distance the decisions of what sets all bidders buy in the execution of the mechanism under
D and D̂. The issue that we encounter is that there are exponentially many subsets each bidder may buy,
hence the naive use of the Kolmogorov bound ||Dij − D̂ij ||K ≤ ǫ, on each single-item marginal results in
an exponential blow-up in the total variation distance of what subset of items bidder i buys, invalidating our
desired coupling. To circumvent this challenge, we argue in Lemma 4 that the events corresponding to which
subset of items each buyer will buy are single-intersecting, according to Definition 4, when seen as events on
the buyer’s single-item values. Single-intersecting events may be non-convex and have infinite VC dimension.
Nevertheless, because single-item values are independent, our new uniform convergence bounds for product
measures (Lemma 3) imply that the difference in probabilities of any such event under D and D̂ is only a
factor of m, the number of items, larger than the bound ǫ on the Kolmogorov distance between single-item
marginals.
We specialize our results to unit-demand bidders in Section 5.1 to obtain computationally efficient solutions for both max-min and sample-based models. Similarly, Section 5.2 contains our results for additive
bidders. We also generalize our sample-based results for constrained additive bidders to XOS bidders in Section 6. Finally, we provide computationally efficient solutions for symmetric XOS and even symmetric subadditive bidders in Section 7. These results are based on showing that (i) the right parameters of SPEMs can
be efficiently and approximately identified with sample or max-min access to the distributions; and (ii) that
the revenue guarantees of simple mechanisms can be robustified to accommodate error in the setting of the
4

Note that any RSPM or ASPE is an SPEM.

4

parameters. In particular, our sample-based result for unit-demand bidders robustifies the ex-ante relaxation
of the revenue maximization problem from [1] and its conversion to a sequential posted pricing mechanism
from [15], and makes use of the extreme-value theorem for regular distributions from [7]. Our sample-based
result for additive bidders shows how to use samples to design mechanisms that approximate the revenue of
Yao’s VCG with entry fees mechanism [42]. Our sample-based results for XOS bidders show how to use
samples to approximate the parameters of the RSPM and ASPE mechanisms of [13], and argue, by re-doing
their duality proofs, that their revenue guarantees are robust to errors in the approximation. Finally, our sample based result for symmetric subadditive bidders is based on a new, duality based, approximation, showing
how to eliminate the use of ASPEs from the result of [13]. This even allows us to obtain prior-independent
mechanisms when the item marginals are regular.

2 Preliminaries
We focus on revenue maximization in the combinatorial auction with n independent bidders and m heterogenous items. Each bidder has a valuation that is subadditive over independent items (see Definition 1). We
denote bidder i’s type ti as htij im
j=1 , where tij is bidder i’s private information about item j. For each i, j,
we assume tij is drawn independently from the distribution Dij . Let Di = ×m
j=1 Dij be the distribution of
bidder i’s type and D = ×ni=1 Di be the distribution of the type profile. We use Tij (or Ti , T ) and fij (or fi , f )
to denote the support and density function of Dij (or Di , D). For notational convenience, we let t−i to be
the types of all bidders except i. Similarly, we define D−i , T−i and f−i for the corresponding distributions,
support sets and density functions. When bidder i’s type is ti , her valuation for a set of items S is denoted by
vi (ti , S). Throughout the paper we use OPT to denote the optimal revenue obtainable by any randomized and
Bayesian truthful mechanism.
Definition 1. [40] For every bidder i, whose type ti is drawn from a product distribution Fi = ×j Fij , her
distribution, Vi , over valuation functions vi (ti , ·) is subadditive over independent items if:
- vi (·, ·) has no externalities, i.e., for each ti ∈ Ti and S ⊆ [m], vi (ti , S) only depends on htij ij∈S , formally,
for any t′i ∈ Ti such that t′ij = tij for all j ∈ S, vi (t′i , S) = vi (ti , S).
- vi (·, ·) is monotone, i.e., for all ti ∈ Ti and U ⊆ V ⊆ [m], vi (ti , U ) ≤ vi (ti , V ).
- vi (·, ·) is subadditive, i.e., for all ti ∈ Ti and U , V ⊆ [m], vi (ti , U ∪ V ) ≤ vi (ti , U ) + vi (ti , V ).
We use Vi (tij ) to denote vi (ti , {j}), as it only depends on tij . When vi (ti , ·) is XOS (or constrained
additive) for all i and ti ∈ Ti , we say Vi is XOS (or constrained additive) over independent items.
Example 1. [40] We may instantiate Definition 1 to define restricted families of subadditive valuations as
follows. In all cases, suppose t = {tj }j∈[m] is drawn from ×j Dj . To define a valuation function that is:
- unit-demand, we can take tj to be the value of item j, and set v(t, S) = maxj∈S tj .
P
- additive, we can take tj to be the value of item j, and set v(t, S) = j∈S tj .

- constrained additive, we can take tj to be the value of item j, and set v(t, S) = maxR⊆S,R∈I
some downward closed set system I ⊆ 2[m] .
(k)

P

j∈R tj ,

for

- XOS (a.k.a. fractionally subadditive), we can take tj = {tj }k∈[K] to encode all possible values associated
P
(k)
with item j, and take v(t, S) = maxk∈[K] j∈S tj .

Note that constrained additive valuations contain additive and unit-demand valuations as special cases,
and are contained in XOS valuations.
Distribution Access Models
We consider the following three different models to access the distributions.
5

• Sample access to bounded distributions. We assume that for any buyer i and any type ti ∈ Ti , her
value Vi (tij ) for any single item j lies in [0, H].
• Sample access to regular distributions. We assume that for any buyer i and any type ti ∈ Ti , the
distribution of her value Vi (tij ) for any item j is regular.
• Direct access to approximate distributions. We assume that we have direct access to a distribution
D̂ = ×i∈[n],j∈[m]D̂ij , for example we can query the pdf, cdf of D̂ and take samples from D̂. Moreover,
for any buyer i and any type ti ∈ Ti , the distributions of the random variable Vi (tij ) when tij is sampled
from D̂ij or Dij are within ǫ in Kolmogorov distance, and both distributions are supported on [0, H].
Definition 2. The Kolmogorov distance between two distributions P and Q over R, denoted ||P − Q||K , is
defined as supx∈R | PrX∼P [X ≤ x] − PrX∼Q [X ≤ x]|. The total variation distance between two probability
measures P and Q on a sigma-algebra F of subsets of some sample space Ω, denoted ||P − Q||T V , is defined
as supE∈F |P (E) − Q(E)|.

3 Summary of Our Results
We summarize our results in the following two tables. Table 1 contains all sample-based results and Table 2
contains all results under the max-min learning model.
Valuations

# bidders

Distributions

Approximation

Sample Complexity

additive [28]
additive

n
n

regular
arbitrary [0, H]

Ω(OPT)
Ω(OPT) − ǫ · H

1
poly(n, m, 1/ǫ)

unit-demand [35]
unit-demand

n
n

arbitrary [0, H]
regular

Ω(OPT) − ǫ · H
Ω(OPT)

poly(n, m, 1/ǫ)
poly(n, m)

constrained additive
constrained additive

n
n

arbitrary [0, H]
regular

Ω(OPT) − ǫ · H
Ω(OPT)

poly(n, m, 1/ǫ)
poly(n, m)

XOS
XOS

n
n

arbitrary [0, H]
regular

Ω(OPT) − ǫ · H
Ω(OPT)

poly(n, m, 1/ǫ)
poly(n, m)

subadditive [35]

1

arbitrary [0, H]

poly(m, 1/ǫ)

subadditive

n i.i.d.

arbitrary [0, H]

subadditive

n i.i.d.

regular

Ω(OPT)
−ǫ·H
n
Ω max{n,m} · OPT − ǫ · H


n
· OPT
Ω max{n,m}


poly(n, m, 1/ǫ)
prior-independent

Table 1: Summary of Our Sample-based Results.

4 Uniform Convergence under Product Measures
In this section, we develop machinery for obtaining uniform convergence bounds for hypotheses over product
measures. Our goal is to save on the sample complexity implied by VC dimension bounds, as summarized
in Table 3. Indeed, we obtain low sample complexity bounds for indicators over single-intersecting sets (see
6

Valuations

# bidders

Distributions

Approximation

additive

n

arbitrary [0, H]

Ω(OPT) − O(ǫ · n · m · H)

unit-demand

n

arbitrary [0, H]

Ω(OPT) − O(ǫ · n · m · H)

constrained additive

n

arbitrary [0, H]

Ω(OPT) − O(ǫ · n · m2 · H)

subadditive

n i.i.d.

arbitrary [0, H]

Ω



n
max{n,m}



· OPT − O(ǫ · n · m · H)

Table 2: Summary of Our Max-min Learning Results.
Definition 4), which play a key role in proving our results for learning approximately revenue-optimal auctions.
Our main results of this section are Theorem 2 for general functions, and Corollary 1 for sets.
We first define what type of uniform convergence bounds we seek to prove.
Definition 3 ((ǫ, δ)-uniform convergence with respect to proxy measure). A hypothesis class H of functions
mapping domain set X to R has (ǫ, δ)-uniform convergence with sample complexity s(ǫ, δ) iff, for all ǫ, δ > 0,
there exists a processing P : X s(ǫ,δ) → ∆(X ) such that for any distribution D ∈ ∆(X ) when k = s(ǫ, δ):
"
#
Pr

z1 ,··· ,zk ∼D

sup Ez∼P(z1 ,··· ,zk ) [g(z)] − Ez∼D [g(z)] ≤ ǫ ≥ 1 − δ.

g∈H

When X is the Cartesian product of a collection of sets X1 , . . . , Xk , i.e. X = ×i Xi , we say that a hypothesis
class H as above has (ǫ, δ)-p.m. uniform convergence with sample complexity s(ǫ, δ) if the above holds for
all D that are product measures over X .
Next we provide a simple lemma, which leads to a simple version of our main result stated as Theorem 1.
Our main result, stated as Theorem 2, follows.
Lemma 1. Let X1 , . . . , Xd be d domain sets and H be a hypothesis class with functions mapping from the
product space ×di=1 Xi to R. For all i ∈ [d], let Hi be the projected hypothesis class of H on Xi , that is,
Hi = {g | ∃f ∈ H ∃ a−i ∈ ×j6=i Xj ∀ xi ∈ Xi , g(xi ) = f (xi , a−i )}. For every i ∈ [d], let Di and D̂i be two
distributions supported on Xi . Suppose for all i ∈ [d],
sup Ex∼Di [g(x)] − Ex∼D̂i [g(x)] ≤ ǫ,

g∈Hi

then
sup Ex∼×d

f ∈H

i=1 Di

[f (x)] − Ex∼×d

i=1 D̂i

[f (x)] ≤ d · ǫ.

Proof. Let Fi and F̂i be the probability measure function for Di and D̂i respectively. We will prove the
statement using a hybrid argument. We create a sequence of product distributions {D (j) }j≤d , where D (j) =
D̂1 × · · · × D̂j × Dj+1 × · · · × Dd , and D (0) = D, D (d) = D̂. To prove our claim, it suffices to show that for
any integer j ∈ [d],
|Ex∼D(j−1) [f (x)] − Ex∼D(j) [f (x)]| ≤ ǫ.

7

Next, we show how to derive this inequality.
|Ex∼D(j−1) [f (x)] − Ex∼D(j) [f (x)]|
!
Z
Z
f (xj , x−j )dFj (xj ) dF̂1 (x1 ) · · · dF̂j−1 (xj−1 )dFj+1 (xj+1 ) · · · dFd (xd )
=
Xj

×i6=j Xi

−
=

Z

≤ǫ ·

×i6=j Xi

Z

Z

Z

Xj

×i6=j Xi

!

f (xj , x−j )dF̂j (xj ) dF̂1 (x1 ) · · · dF̂j−1 (xj−1 )dFj+1 (xj+1 ) · · · dFd (xd )



Exj ∼Dj [f (xj , x−j )] − Exj ∼D̂j [f (xj , x−j )] dF̂1 (x1 ) · · · dF̂j−1 (xj−1 )dFj+1 (xj+1 ) · · · dFd (xd )
dF̂1 (x1 ) · · · dF̂j−1 (xj−1 )dFj+1 (xj+1 ) · · · dFd (xd )

×i6=j Xi

=ǫ

Theorem 1. Let X1 , . . . , Xd be d domain sets and H a hypothesis class of functions mapping from the product
space ×di=1 Xi to R. For all i ∈ [d], let Hi be the projected hypothesis class of H on Xi , that is Hi =
{g | ∃f ∈ H ∃ a−i ∈ ×j6=i Xj ∀ xi ∈ Xi , g(xi ) = f (xi , a−i )}.
Suppose that, for all i ∈ [d], Hi has (ǫ, δ)-uniform convergence with sample complexity si (ǫ, δ). Then H
has (ǫ, δ)-p.m. uniform convergence with sample complexity s(ǫ, δ) = maxi∈[d] si (ǫ/d, δ/d).
In particular, let z (1) , . . . , z (ℓ) be a sample of size ℓ = s(ǫ, δ) from a product measure ×i∈[d] Di . Define
(1)

(ℓ)

(j)

D̂i = Pi (zi , . . . , zi ), for all i ∈ [d], where zi
corresponding to Hi ’s uniform convergence. Then
"
Pr

z (1) ,...,z (ℓ)

is the i-th entry of sample z (j) and Pi is the processing
#

sup Ez∼×i∈[d] D̂i [f (z)] − Ez∼×i∈[d]Di [f (z)] ≤ ǫ ≥ 1 − δ.

f ∈H

i
h
Proof of Theorem 1: Since ℓ ≥ si (ǫ/d, δ/d), Pr supg∈Hi Ez∼D̂i [g(z)] − Ez∼Di [g(z)] ≤ ǫ/d ≥ 1−δ/d for

all i ∈ [d]. By the union bound, with probability at least 1 − δ, supg∈Hi Ez∼D̂i [g(z)] − Ez∼Di [g(z)] ≤ ǫ/d
for all i ∈ [d]. According to Lemma 1, supf ∈H Ez∼× D̂i [f (z)] − Ez∼×i∈[d] Di [f (z)] ≤ ǫ with probability
i∈[d]
at least 1 − δ. ✷
Theorem 2. Let X1 , . . . , Xd be d domain sets and H a hypothesis class of functions mapping from the product
d
space ×
i=1 Xi to R. For all T ⊆ [d], let HT be the projected hypothesis class of H on XT ≡ ×i∈T Xi , that is,
HT = g | ∃f ∈ H ∃ a−T ∈ ×j ∈/ T Xj ∀ xT ∈ XT , g(xT ) = f (xT , a−T ) . Suppose that, for all T ⊆ [d], HT
has (ǫ, δ)-p.m. uniform convergence with sample complexity sT (ǫ, δ), and define
s(ǫ, δ) =

min
max sTi (ǫ/k, δ/k).
i=1,...,k
k, partitions
T1 ⊔T2 ⊔. . .⊔Tk = [d]

(2)

Then H has (ǫ, δ)-p.m. uniform convergence with sample complexity s(ǫ, δ).
In particular, let z (1) , . . . , z (ℓ) be a sample of size ℓ = s(ǫ, δ) from a product measure ×i∈[d] Di . Suppose that the optimum of (2) is attained at k = k̃ for partition T̃1 ⊔ T̃2 ⊔ . . . ⊔ T̃k̃ = [d]. Define D̂T̃i =
8

(1)

(j)

(ℓ)

PT̃i (z T̃ , . . . , z T̃ ), for all i ∈ [d], where z T̃ contains the entries of sample z (j) in coordinates T̃i and PT̃i is
i
i
i
the processing corresponding to HT̃i ’s uniform convergence. Then
Pr

z (1) ,...,z (ℓ)

"

sup Ez∼×

f ∈H

i∈[k̃] D̂T̃i

#

[f (z)] − Ez∼×i∈[d] Di [f (z)] ≤ ǫ ≥ 1 − δ.

Proof of Theorem 2: For every possible partition use Theorem 1. ✷
Nest, we specialize Theorem 2 to indicator functions over sets.
Corollary 1. We use the same notation as in Theorem 2. Suppose that all functions in H map ×di=1 Xi to
{0, 1}, i.e. they are indicators over sets. Suppose also that the VC dimension of HT (viewed as a collection of
sets) is VT . Define


Vmax =
min
k2 · max VTi .
(3)
i=1,...,k
k, partitions
T1 ⊔T2 ⊔. . .⊔Tk = [d]
Assume that the 
optimum of (3) is attained
 at k = k̃ for partition T̃1 ⊔ T̃2 ⊔ . . . ⊔ T̃k̃ = [d].
· ln k̃ǫ +
Then ℓ = O Vmax
ǫ2
gence for H. Formally,
"
Pr

z (1) ,...,z (ℓ)

k̃ 2
ǫ2

· ln k̃δ samples from ×i∈[d] Di suffice to obtain (ǫ, δ)-p.m. uniform conver-

sup Ez∼×

f ∈H

i∈[k̃] D̂T̃i

#

[f (z)] − Ez∼×i∈[d] Di [f (z)] ≤ ǫ ≥ 1 − δ,

where for a given sample z (1) , . . . , z (ℓ) from a product distribution ×i∈[d] Di the distributions D̂T̃i are defined
(1)

(ℓ)

(j)

i

i

i

to be uniform over z T̃ , . . . , z T̃ , where z T̃ contains the entries of sample z (j) in coordinates T̃i .
Table 3 compares the sample complexity for uniform convergence implied by Theorem 2 and Corollary 1
to that implied by VC theory, when the underlying measures are product. Suppose H contains the indicator
functions of all convex sets in Rd . VC theory does not provide any finite sample bound for uniform convergence, as the VC dimension of H is ∞. Do our results provide a finite bound? Notice that, for all i, H
i
2
simply contains all intervals in R. Hence, Vi = 2 and Corollary 1 implies that ℓ = O( dǫ2 · log dδ + log dǫ )
samples suffice to obtain (ǫ, δ)-p.m.
uniform


 convergence for H . In fact, our sample complexity bound can
2

log

1

be improved to O dǫ2 · log dδ , as O ǫ2 δ samples suffice to guarantee (ǫ, δ)-uniform convergence for all
intervals in R due to the DKW inequality [25].
In the next a few sections, we apply our uniform convergence results to learn a mechanism with approximately optimal revenue. A type of events called single-intersecting (see Definition 4) plays a key role in our
analysis. These events are defined based on the geometric shape of the corresponding sets. For example, balls,
rectangles and all convex sets are single-intersecting, but this definition includes some non-convex sets as well,
for example, “cross-shaped” sets. It turns out that being able to handle these non-convex sets is crucial for our
results, as many events we care about are not convex but nonetheless are single-intersecting.

Definition 4 (Single-intersecting Events). For any event E in Rℓ , E is single-intersecting if the intersection of E and any line
an interval. More formally, for any i ∈ [ℓ]
 thatℓ is parallel to one of the axes is
ℓ−1 , the intersection of L and E is of the form
,
where
a
∈
R
and
any
line
L
=
x
∈
R
|
x
=
a
−i
i
i
−i
−i

x ∈ Rℓ | x−i = a−i , xi ∈ [a, ā] where a ≤ ā. In particular, we allow a to be −∞ and ā to be +∞.
¯
¯
¯
9

We establish a uniform convergence bound for single-intersecting events by combing the DKW inequality and
Theorem 1.
Lemma 2. For any integer ℓ, let H be the hypothesis class that contains all indicator functions
single for

ℓ2
ℓ
intersecting events in R . Then H has (ǫ, δ)-p.m. uniform convergence with sample complexity O ǫ2 · log δℓ .

Proof. As the projected hypothesis class for the i-th coordinate simply contains all intervals in R, the sample
complexity for (ǫ, δ)-uniform convergence is O( ǫ12 · log 1δ ) due to the DKW inequality. The claim follows from
Theorem 1.

Next, we show a slightly stronger statement, which is a type of uniform convergence bound when access
to approximate distributions is given. More specifically, we argue that for any single-intersecting event, the
difference in the probability of this event under two product distributions D = ×i∈[ℓ] Di and D̂ = ×i∈[ℓ] D̂i is
at most 2ξ · ℓ, if ||Di − D̂i ||K ≤ ξ for all i. It is not hard to see that Lemma 3 and the DKW inequality imply
Lemma 2.
Lemma 3. For any integer ℓ, let D = ×ℓi=1 Di and D̂ = ×ℓi=1 D̂i , where Di and D̂i are both supported on R
for any i ∈ [ℓ]. If ||Di − D̂i ||K ≤ ξ, PrD [E] − PrD̂ [E] ≤ 2ξ · ℓ for any single-intersecting event E.
Proof. Let H = {1x∈E : E is single-intersecting}. By the definition of single-intersecting events, Hi is the set
of the indicator functions of all intervals in R for any i ∈ [ℓ]. Since ||Di − D̂i ||K ≤ ξ,
sup Ex∼Di [g(x)] − Ex∼D̂i [g(x)] ≤ 2ξ.

g∈Hi

By Lemma 1,
sup Ex∼D [f (x)] − Ex∼D̂ [f (x)] ≤ 2ξ · ℓ.

f ∈H

The following table (Table 3) summarizes some uniform convergence bounds implied by our results in this
section.
Hypotheses Class

VC Bound

Bounds from Theorem 2 and Corollary 1

axis-aligned rectangles in Rd
polytopes with k facets in Rd
arbitrary convex sets in Rd
single-intersecting sets in Rd

Õ(d/ǫ2 )
Õ(dk/ǫ2 )
∞
∞

Õ(d/ǫ2 )
Õ(d · min{d, k}/ǫ2 )
Õ(d2 /ǫ2 )
Õ(d2 /ǫ2 )

Table 3: Number of samples required for (ǫ, Θ(1))-p.m. uniform convergence for different H’s.

5 Constrained Additive Bidders: Uniform Convergence of the Revenue of Sequential Posted Price with Entry Fee Mechanisms
We consider a specific class of mechanisms, namely Sequential Posted Price with Entry fee Mechanisms, a.k.a.
SPEMs; see Algorithm 1 for details. Cai and Zhao [13] recently showed that if the bidders’ valuations are XOS

10

over independent items, the best SPEM achieves a constant fraction of the optimal revenue. 5 This section
has two goals. The first is to show that, when bidders have constrained additive valuations over independent
items, polynomially many samples suffice to guarantee uniform convergence for the revenue of all SPEMs,
and hence our ability to select a near-optimal SPEM from polynomially many samples. This can be proven by
applying our uniform convergence result for single-intersecting events (Lemma 2). The second (and stronger
goal) is to show that we can learn a near-optimal SPEM under the max-min learning model (Theorem 4). We
show that the revenue of any SPEM changes no more than O(ǫ · m2 · n · H) under the true and approximate
valuation distributions (Theorem 3), where ǫ is an upper bound of the Kolmogorov distance between the true
and approximate distributions for every item marginal of every bidder. It is, of course, not hard to see that
Theorem 3 and the DKW inequality imply uniform convergence of the revenue of all SPEMS. To establish
Theorem 3, we need to apply Lemma 3 instead of Lemma 2.
Algorithm 1 Sequential Posted Price with Entry Fee Mechanism (SPEM)
Require: A collection of prices {pij }i∈[n],j∈[m] and a collection of entry fee functions {δi (·)}i∈[n] where
δi : 2[m] 7→ R is bidder i’s entry fee function.
1: S ← [m]
2: for i ∈ [n] do
3:
Show bidder i the set of available items S and set the entry fee for bidder i to be δi (S).
4:
if Bidder i pays the entry fee δi (S) then
P
5:
i receives her favorite bundle Si∗ and pays j∈S ∗ pij .
i
6:
S ← S\Si∗ .
7:
else
8:
i gets nothing and pays 0.
9:
end if
10: end for
We first establish a technical lemma, which states that, for any set of items S, any set of prices {pj }j∈[m]
and entry fee δ, the distribution over the set of items purchased by a constrained additive bidder whose valuation
is drawn from D = ×j∈[m] Dj and D̂ = ×j∈[m] D̂j has total variation distance at most 2mξ, if ||Dj − D̂j ||K ≤ ξ
for every item j ∈ [m]. This is quite surprising. Given that, for each set of items S ′ ⊆ S, the difference in
the probability that the buyer will purchase this particular set S ′ under D and D̂ could already be as large as
Θ(mξ), and the distribution has an exponentially large support size, a trivial argument would give a bound of
2m · Θ(mξ). To overcome this analytical difficulty, we argue instead that for any collection of sets of items,
the event that the buyer’s favorite set lies in this collection is single-intersecting. Then our result follows from
Lemma 3. Notice that it is crucial that Lemma 3 holds for all events that are single-intersecting, as the event
we consider here is clearly non-convex in general.
Lemma 4. For any set S ⊆ [m], any prices {pj }j∈[m] and entry fee δ(S), let L and L̂ be the distributions
over the set of items purchased from S by a constrained additive bidder under prices {pj }j∈[m] and entry fee
δ when her type is drawn from D = ×j∈[m] Dj and D̂ = ×j∈[m] D̂j respectively. If ||Dj − D̂j ||K ≤ ξ for all
item j, ||L − L̂||T V ≤ 2mξ.
Proof. For any set R ⊆ S, let ER be the event that the bidder purchases set R. Proving that the total vari|S|
ation distance
between
h
i L andh L̂ isS no morei than 2m · ξ is the same as proving that for any K ≤ 2 ,
SK
≤ 2m · ξ where R1 , · · · RK are arbitrary distinct subsets of
PrD t ∈ ℓ=1 ERℓ − PrD̂ t ∈ K
ℓ=1 ERℓ
5

Cai and Zhao [13] showed that the best ASPE or RSPM achieves a constant fraction of the optimal revenue. Clearly, any ASPE is
also a SPEM, and any RSPM is simply a SPEM if we force the bidders to be unit-demand by only allowing each of them to purchase
at most one item.

11

S
S. Since the dimension of the bidder’s type space is m, if we can prove that K
ℓ=1 ERℓ is always singleintersecting, our claim follows from Lemma 3.
For any j ∈ [m] and a−j ∈ Rm−1
≥0 , let Lj (a−j ) = {(tj , a−j ) |tj ∈ R≥0 }. We claim that Lj (a−j ) intersects
with at most two different EU and EV where U and V are subsets of S. WLOG, we assume that (0, a−j ) ∈ EU .
• If U = ∅, that means the utility of the favorite set for type (0, a−j ) is smaller than the entry fee δ(S). If
we increase the value of tj , two cases could happen: (1) the utility of the favorite set is still lower than
the entry fee; (2) the utility of the favorite set is higher than the entry fee. In case (1), (tj , a−j ) ∈ E∅ .
In case (2), the bidder pays the entry fee and purchases her favorite set V . Then item j must be in
V , because otherwise the utility for set V does not change from type (0, a−j ) to type (tj , a−j ). If we
keep increasing tj , bidder i’s favorite set remains to be V and she keeps accepting the entry fee and
purchasing V . Hence, Lj (a−j ) can intersect with at most one event ER where R is non-empty.
• If U 6= ∅, that means U is the favorite set of type (0, a−j ) and the utility for winning set U is higher than
the entry fee. If we increase the value of tj , two cases could happen: (1) U remains the favorite set; (2)
a different set V becomes the new favorite set. In case (1), (tj , a−j ) ∈ EU . In case (2), item j must lie in
V but not in U , otherwise how could U be better than V for type (0, a−j ) but worse for type (tj , a−j ).
If we keep increasing tj , the bidder’s favorite set remains to be V and she keeps accepting the entry fee
and purchasing V . Hence, Lj (a−j ) can intersect at most two different events.
It is not hard to see that any event ER is an intersection of halfspaces, so the intersection of Lj (a−j ) with
any event ER is an interval. Also, notice that any type t ∈ Rm
≥0 must lie in an event ER for some set R ⊆ S.
If Lj (a−j ) intersects with two different events EU and EV , the two intersected intervals must lie back to back
on Lj (a−j ). Otherwise, Lj (a−j ) intersects with at least three different events. Contradiction. Since Lj (a−j )
intersects with at most two different events, no matter which of these events are in {ERℓ }ℓ∈[K] , the intersection
SK
S
of Lj (a−j ) and K
ℓ=1 ERℓ is single-intersecting. Now our
ℓ=1 ERℓ is either empty or an interval meaning
claim simply follows from Lemma 3.
Theorem 3. Suppose all bidders’ valuations are constrained additive over independent items. For any SPEM,
let R EV and Rd
EV be its expected revenue under D and D̂ respectively. If Dij and D̂ij are both supported on
[0, H], and ||Dij − D̂ij ||K ≤ ξ for all i ∈ [n] and j ∈ [m],
R EV − Rd
EV ≤ 2nmξ · (mH + OPT) .

Proof. We use a hybrid argument. Consider a sequence of distributions {D (i) }i≤n , where D (i) = D̂1 × · · · ×
D̂i × Di+1 × · · · × Dn , and D (0) = D, D (n) = D̂. We use R EV (i) to denote the expected revenue of the SPEM
under D (i) . To prove our claim, it suffices to argue that R EV (i−1) − R EV (i) ≤ 2ξm · (m · H + OPT) . We
denote by Sk and Sk′ the random set of items that remain available after visiting the first k bidders under D (i−1)
and D (i) . Clearly, for k ≤ i − 1, ||Sk − Sk′ ||T V = 0, so the expected revenue collected from the first i − 1
bidders under D (i−1) and D (i) is the same. According to Lemma 4, ||Si − Si′ ||T V ≤ 2m · ξ. The total amount
of money bidder i spends can never be higher than her value for receiving all the items which is at most m · H.
So the difference in the expected revenue collected from bidder i under D (i−1) and D (i) is at most 2ξ · m2 H.
Suppose R is the set of remaining items after visiting the first i bidders, then the expected revenue collected
from the last n − i bidders is the same under D (i−1) and D (i) , as these bidders have the same distributions.
Moreover, this expected revenue is no more than OPT, since the optimal mechanism can simply just sell R
to the last n − i bidders using the same prices and entry fee as in the SPEM we consider. Of course, for any
fixed R, the probabilities that Si = R and Si′ = R are different, but since for any R the expected revenue from
the last n − i bidders is at most OPT, the difference in the expected revenue from the last n − i bidders under
12

D (i−1) and D (i) is at most ||Si − Si′ ||T V · OPT ≤ 2ξ · mOPT. Hence, the total difference between R EV (i−1)
and R EV (i) is at most 2ξm · (mH + OPT).
Theorem 4. (Max-min Learning for Constrained Additive Bidders) When all bidders’ valuations are constrained additive over independent items and for any bidder i and any item j, Dij and D̂ij are supported on
1
), then with only access to D̂ = ×i,j D̂ij , our algorithm can
[0, H] and ||Dij − D̂ij ||K ≤ ǫ for some ǫ = O( nm
2
learn an RSPM or ASPE whose revenue is at least OPT
c − ǫ · O(m nH), where OPT is the optimal revenue by
any BIC mechanism under D = ×i,j Dij . c > 1 is an absolute constant.
Clearly, Theorem 4 also implies a polynomial sample complexity bound for learning an approximately
revenue-optimal mechanism. A better sample complexity bound can be obtained directly, i.e. without invoking
the uniform convergence of the revenue of SPEMs, and is stated as Theorem 9 for the broader class of XOS
valuations. Similarly, when bidders have simpler valuations, i.e., additive or unit-demand valuations, we can
sharpen our results and achieve polynomial-time learnability of the approximately optimal mechanism using
more specialized techniques. See Sections 5.1 and 5.2 for details.

5.1 Unit-demand Valuations: Polynomial-Time Learning
In this section, we consider bidders with unit-demand valuations, sharpening our results to show how to learn
approximately revenue-optimal mechanisms in polynomial time. It is shown in a sequence of works [15, 32,
11] that there exists a sequential posted price mechanism (SPM see Algorithm 2 for details) that achieves at
1
of the optimal revenue when bidders are unit-demand. We show that under all three distribution access
least 24
models of Section 2 there exists a polynomial-time algorithm that learns a sequential posted price mechanism
whose revenue approximates the optimal revenue. We only sketch the proof here and postpone the details to
Appendix B.
Theorem 5. When all bidders have unit-demand valuations and
• Dij is supported on [0, H] for all bidder i and item j, there exists a polynomial
algorithm that learns
 time


1 2
OPT
m2 n log nǫ + log 1δ
an SPM whose revenue is at least 144 − ǫH with probability 1 − δ given O ǫ
samples from D; or
• Dij is a regular distribution for all bidder i and item j, there exists a polynomial time algorithm that
2 2 2
learns a randomized SPM whose revenue is at least OPT
33 with probability 1−δ given O(max{m, n} m n ·
nm
log δ ) samples from D; or
• we are only given access to D̂ij where ||D̂ij −Dij ||K ≤ ǫ for all bidder i and item j, there is a polynomial

time algorithm that constructs a randomized SPM whose revenue under D is at least 14 − (n + m) · ǫ ·
OPT
6
8 − 2ǫ · mnH .

Sample Access to Bounded Distributions: the result is due to Morgenstern and Roughgarden [35].

Direct Access to Approximate Distributions: we first consider a convex program based on D (see Figure 1)
which is usually referred to as the ex-ante relaxation of the revenue maximization problem [1], and use its
optimum as a proxy for OPT. Next, we consider a similar convex program based on D̂ (see Figure 2) and
show that the optima of the two convex programs are close to each other. Finally, we use techniques developed
by Chawla et al. [15] to convert the optimal solution of the second convex program into a randomized SPM.
We can show that the constructed randomized SPM achieves a revenue that approximates the optimum of the
second convex program under D, which implies that the mechanism’s revenue also approximates the OPT. As
6

1
), this is the max-min guarantee we want to achieve.
If we set ǫ to be O( m+n

13

we are given D̂, we can solve the second convex program and convert its optimal solution into a randomized
SPM in polynomial time. See Theorem 10 in Appendix B.1 for further details.
Sample Access to Regular Distributions: we use a similar convex program relaxation based approach as
in the previous case. The main difference is that regular distributions could be unbounded and thus ruin the
approximation guarantee. We show how to use the Extreme Value theorem in [7] to truncate the distributions
without hurting the revenue by much. See Theorem 12 in Appendix B.3 for further details.

5.2 Additive Valuations: Polynomial-Time Learning
In this section, we consider bidders with additive valuations, again sharpening our results to show polynomialtime learnability. It is known that the better of the following two mechanisms achieves at least 81 of the optimal
revenue when all bidders have additive valuations [42, 11]:
Selling Separately: the mechanism sells each item separately using Myerson’s optimal auction.
VCG with Entry Fee: the mechanism solicits bids b = (b1 , · · · , bn ) from the bidders, then offers each
bidder i the option to participate for an entry fee ei (b−i , Di ), which is the median of the random variable
P
7
+
j∈[m] (tij − maxk6=i bkj ) , where ti ∼ Di . This random variable is exactly bidder i’s utility when her type
is ti and the other bidders’ are b−i . If bidder i chooses to participate, she pays the entry fee and can take any
item j at price maxk6=i bkj . Notice that the mechanism never over allocate any item, as only the highest bidder
for an item can afford it.
Indeed, only counting the revenue from the entry fee in the second mechanism and the optimal revenue
from selling the items separately already suffices to provide an 8-approximation [42, 11].
Theorem 6 ([11]). Let SR EV be the optimal revenue for selling the items separately and BR EV be the expected
entry fee collected from the VCG with entry fee mechanism. Then OPT ≤ 6 · SR EV + 2 · BR EV .
Goldner and Karlin [28] showed that one sample suffices to learn a mechanism that achieves a constant
fraction of the optimal revenue when Dij is regular for all i ∈ [n] and j ∈ [m]. We show how to learn an
approximately optimal mechanism in the other two models.
Theorem 7. When the bidders have additive valuations and
• Dij is supported on [0, H] for all bidder i and item j, we can learn in polynomial
time a mechanism 
 

m 2
OPT
· n log n log 1ǫ + log 1δ
whose expected revenue is at least 32 −ǫ·H with probability 1−δ given O
ǫ
samples from D; or
• we are only given access to distributions D̂ij where ||D̂ij − Dij ||K ≤ ǫ for all bidder i and item j, there
is a polynomial time algorithm that constructs a mechanism whose expected revenue under D is at least
1
OPT
266 − 96ǫ · mnH when ǫ ≤ 16 max{m,n} .
Sample Access to Bounded Distributions: Goldner and Karlin’s proof [28] can be directly applied to the
bounded distributions to show a single sample suffices to learn a mechanism whose expected revenue approximates the BR EV . Then as SR EV is the revenue of m separate single-item auctions, we can use the result
in [35] to approximate it. See Theorem 13 in Appendix C.1 for further details.
Direct Access to Approximate Distributions: for each single item, we apply Theorem 5 to learn an individual
auction, then run these learned auctions in parallel. Clearly, the combined auction’s revenue approximates
7

The entry fee function defined in [42, 11] is slightly different. They showed that there exists an entry fee Xi , such that bidder
i accepts the entry fee with probability at least 1/2. Then they argued that extracting Xi /2 as the revenue in the VCG with entry
fee mechanism is enough to obtain a factor 8 approximation. It is not hard to observe that our entry fee is accepted with probability
exactly 1/2, thus our entry fee is at least as large as Xi . So our mechanism also suffices to provide a factor 8 approximation.

14

SR EV . For BR EV , we show that for every bidder i and every bid profile b−i of the other bidders, the event that
corresponds to bidder i accepting any entry fee is single-intersecting (see Definition 4). This implies that the
probability forP
a bidder to accept an entry fee under D̂ and D is close (Lemma 3). So we can essentially use
the median of j∈[m] (tij − maxk6=i bkj )+ with ti ∼ D̂i as the entry fee. See Theorem 14 in Appendix C.2 for
further details.

6 XOS Valuations
In this section we go beyond constained additive valuations to show learnability of approximately revenueoptimal auctions from polynomially many samples. The better of the following two mechanisms is known to
achieve a constant fraction of the optimal revenue, when bidders have valuations that are XOS over independent
items [13].
Rationed Sequential Posted Price Mechanism (RSPM): the mechanism is almost the same as SPM in Algorithm 2, except there is an extra constraint that every bidder can purchase at most one item.
Anonymous Sequential Posted Price with Entry Fee Mechanism (ASPE): every buyer faces the same
collection of item prices {pj }j∈[m] . The seller visits the bidders sequentially. For every bidder, the seller
shows her all the available items (i.e. items that have not yet been purchased) and the associated price for
each item, then asks her to pay a personalized entry fee which depends on her type distribution and the set of
available items. If the bidder accepts the entry fee, she can proceed to purchase any available item at the given
price; if she rejects the entry fee, she neither receives nor pays anything. See Algorithm 3 for details.
Theorem 8. [13] There exists a collection of prices {p∗j }j∈[m] , such that if we set the entry fee function
δi∗ (S) to be the median of bidder i’s utility for set S, either the ASPE(p∗ , δ∗ ) or the best RSPM achieves at
least a constant fraction of the optimal revenue when bidders’
valuations are XOS over independent items.
P
More formally, let u∗i (ti , S) = maxS ∗ ⊆S vi (ti , S ∗ ) − j∈S ∗ p∗j be bidder i’s utility for the set of items S
when her type is ti . We define δi∗ (S) to be the median of the random variable u∗i (ti , S) (with ti ∼ Di ) for
any set S ⊆ [m]. Moreover, the price p∗j for any item j is no larger than 2G, where G = maxi,j Gij and
o
n
1
.
Gij := supx Prtij ∼Dij [Vi (tij ) ≥ x] ≥ 5 max{m,n}

Our goal next is to bound the sample complexity for learning a near-optimal RSPM and the ASPE described
in Theorem 8 under XOS valuations.
We consider first the task of learning a near-optimal RSPM. In a RSPM, all bidders are restricted to be
unit-demand, so the revenue of the best RSPM is upper bounded by the optimal revenue in the corresponding
unit-demand setting. In Section 5.1, we have shown how to learn an approximately optimal mechanism for
unit-demand bidders, and those algorithms can be used to approximate the best RSPM.
So, for the rest of this section, it suffices to focus on learning an ASPE whose revenue approximates the
revenue of the ASPE described in Theorem 8. We will do this in Section 6.1. Before that, we need a robust
version of Theorem 8. In the next Lemma, we argue that if we use a collection of prices {p′j }j∈[m] sufficiently
close to {p∗j }j∈[m] and entry fee δi′ (S) sufficiently close to the median of the utility for every bidder i and
subset S, the better of the corresponding ASPE and the best RSPM still approximates the optimal revenue. We
postpone the proof to Appendix D.
Lemma 5. For any ǫ > 0 and µ ∈ [0, 14 ], let {p′j }j∈[m] be a collection of prices such that |p′j − p∗j | ≤ ǫ
for all j ∈ [m], where {p∗j }j∈[m] is the collection of prices in Theorem 8. Let δi′ (S) be bidder i’s entry fee
′
′
function such that Prti ∼D
+ µ] for any set S ⊆ [m], where u′i (ti , S) =
P i [ui (t′i , S) ≥ δi (S)] ∈ [1/2 − µ, 1/2
′
′
∗
maxS∗⊆S vi (ti , S ) − j∈S ∗ pj . Then, either the ASPE(p , δ ) or the best RSPM achieves revenue at least
OPT
C1 (µ) − C2 (µ) · (m + n) · ǫ when bidders’ valuations are XOS over independent items. Both C1 (·) and C2 (·)
are monotonically increasing functions that only depend on µ.
15

Definition 5. We say a collection of prices {pj }j∈[m] is in the B-bounded ǫ-net if pj is a multiple of ǫ and
no larger than B for any item j. For any collection of prices {pj }j∈[m] , we say the entry fee functions are µbalanced if for every bidder i and every set S ⊆ [m], her entryP
fee δi (S) satisfies Prti ∼Di [ui (ti , S) ≥ δi (S)] ∈
[1/2 − µ, 1/2 + µ], where ui (ti , S) = maxS∗⊆S vi (ti , S ∗ ) − j∈S ∗ pj .
Corollary 2. For bidders with valuations that are XOS over independent items and any ǫ > 0, there exists
a collection of prices {pj }j∈[m] in the 2G-bounded ǫ-net such that for any µ-balanced entry fee functions
− C2 (µ) ·
{δi (·)}i∈[n] with µ ∈ [0, 14 ], either the ASPE(p, δ) or the best RSPM achieves revenue at least COPT
1 (µ)
(m + n) · ǫ.

6.1 XOS Valuations: sample access to bounded and regular distributions
In this section, we consider how to learn an ASPE with high revenue given sample access to D. Our learning
algorithm is a two-step procedure. In the first step, we take a few samples from D and use these samples to
set the entry fee for every collection of prices {pj }j∈[m] in the ǫ-net. More specifically, to decide δi (S) we
compute the utility of bidder i for set S under {pj }j∈[m] over all the samples and take the empirical median
among all these utilities to be δi (S). With a polynomial number of samples, we can guarantee that for any
{pj }j∈[m] in the ǫ-net the computed entry fee functions {δi (·)}i∈[n] are µ-balanced. Now, we have created
an ASPE for every {pj }j∈[m] in the ǫ-net. In the second step, we take some fresh samples from D and use
them to estimate the revenue for each of the ASPEs we created in the first step, then pick the one that has the
highest empirical revenue. It is not hard to argue that with a polynomial number of samples the mechanism
we pick has high revenue with probability almost 1. Combining our algorithm with Theorem 5, we obtain the
following theorem.
Theorem 9. When all bidders’ valuations are XOS over independent items and
• the random variable Vi (tij ) is supported on [0, H] for each bidder i and item j, we can learn an RSPM
and an ASPE such that with probability at least 1 − δ the better
at
 of the two mechanisms has revenue

mn 2
m+n
1
OPT
least c1 − ξ · H for some absolute constant c1 > 1 given O ( ξ ) · (m · log ξ + log δ ) samples
from D;
• the random variable Vi (tij ) is regular for each bidder i and item j, we can learn an RSPM and an ASPE
such that with probability at least 1 − δ the better of the two mechanisms has revenue at least OPT
c2 for

1
2
2
2
some absolute constant c2 > 1 given O max{m, n} m n m log(m + n) + log δ samples from D.

The bounded case is proved as Theorem 15 in Appendix D.1. The regular case is proved as Theorem 16 in
Appendix D.1.

7 Symmetric Bidders
In this section, we consider symmetric bidders (Di = Di′ for all i and i′ ∈ [n]) with XOS and subadditive
valuations. For XOS valuations, our goal is to improve our algorithms from Section 6 to be computationally efficient under bidder symmetry. For subadditive valuations, our goal is to establish the learnability of
approximately optimal mechanisms whose revenue improves as the number of bidders becomes comparable
to the number of items. We only describe the results here and postpone the formal statements and proofs to
Appendix E.
• XOS valuations: we can learn in polynomial time an approximately optimal mechanism with a polynomial number of samples when the valuations are XOS over independent items. Our algorithm essentially
16

estimates all the parameters needed to run the RSPM and ASPE used in [13]. In general, it is not clear
how to estimate these parameters efficiently. But when the bidders are symmetric, one only needs to
consider “symmetric parameters” which greatly simplifies the search space and allows us to estimate all
the parameters in polynomial time. See Appendix E.2 for details.
• subadditive valuations:
when

 the valuations are subadditive over independent items, the optimal revn
enue is at most O max{m,n} times larger than the highest revenue obtainable by an RSPM. In other
words, if the number of items is within a constant times the number of bidders, an RSPM suffices to
extract a constant fraction of the optimal revenue. Applying our results for unit-demand bidders in Section 5.1, we can learn a nearly-optimal RSPM, which is also a good approximation to OPT. In fact, when
the distribution for random variable Vi (tij ) is regular for every bidder i and item j, we can design a priorindependent mechanism that achieves a constant fraction of the optimal revenue. See Appendix E.3 for
details.

Appendix
A

Our Mechanisms

Here are the detailed description of the two major mechanisms we use: Sequential Posted Price Mechanism
(SPM) and Anonymous Sequential Posted Price with Entry Fee Mechanism (ASPE). We also use the Rationed
Sequential Posted Price Mechanism (RSPM) when bidders are not unit-demand. RSPM is almost identical to
SPM except that there is an extra constraint saying that no bidder can purchase more than one item.
Algorithm 2 Sequential Posted Price Mechanism (SPM)
Require: Pij is the price for bidder i to purchase item j.
1: S ← [m]
2: for i ∈ [n] do
3:
Show bidder i the set of available items S.
P
P
4:
i purchases her favorite bundle Si∗ ∈ maxS ′ ⊆S vi (ti , S ′ ) − j∈S ′ Pij and pays j∈S ∗ Pij .
i
5:
S ← S\Si∗ .
6: end for
Algorithm 3 Anonymous Sequential Posted Price with Entry Fee Mechanism (ASPE)
Require: A collection of prices {pj }j∈[m] and a collection of entry fee functions {δi (·)}i∈[n] where δi :
2[m] 7→ R is bidder i’s entry fee function.
1: S ← [m]
2: for i ∈ [n] do
3:
Show bidder i the set of available items S and set the entry fee for bidder i to be δi (S).
4:
if Bidder i pays the entry fee δi (S) then
P
5:
i receives her favorite bundle Si∗ and pays j∈S ∗ pj .
i
6:
S ← S\Si∗ .
7:
else
8:
i gets nothing and pays 0.
9:
end if
10: end for
17

B Missing Details from Section 5.1
B.1

Unit-demand Valuations: direct access to approximate distributions

We first consider the model where we only have access to an approximate distribution D̂. The following
definition is crucial for proving our result.
Definition 6. For any single dimensional distribution D with cdf F , we define its revenue curve RD : [0, 1] 7→
R≥0 as
RD (q) = max x · q · F −1 (1 − q) + (1 − x) · q̄ · F −1 (1 − q̄)
¯
¯
s.t. x · q + (1 − x) · q̄ = q
¯
x, q, q̄ ∈ [0, 1]
¯
where F −1 (1 − p) = sup{x ∈ R : Prv∼D [v ≥ x] ≥ p}.
Lemma 6 (Folklore). Let ϕij (·) and ϕ̂ij (·) be the ironed virtual value function for distribution Dij and D̂ij
RH
RH
respectively, then for any q ∈ [0, 1], RDij (q) = F −1 (1−q) ϕ(x)dF (x) and RD̂ij (q) = F̂ −1 (1−q) ϕ̂(x)dF (x).
ij

ij

Since the ironed virtual value function is monotonically non-decreasing, RDij (·) and RD̂ij (·) are concave
functions.

We provide an upper bound of the optimal revenue using RDij in the next Lemma. To do that, we first
need the definition of the Single-Dimensional Copies Setting.
Single-Dimensional Copies Setting: In the analysis for unit-demand bidders in [15, 11], the optimal revenue
is upper bounded by the optimal revenue in the single-dimensional copies setting defined in [15]. We use the
same technique. We construct nm agents, where agent (i, j) has value Vi (tij ) of being served with tij ∼ Dij ,
and we are only allow to use matchings, that is, for each i at most one agent (i, k) is served and for each j
at most one agent (k, j) is served8 . Notice that this is a single-dimensional setting, as each agent’s type is
specified by a single number. Let OPT C OPIES -UD be the optimal BIC revenue in this copies setting.
Lemma
there exists a collection of non-negative numbers {qij }i∈[n],j∈[m] satisP 7. For unit-demand bidders,P
fying i qij ≤ 1 for all j ∈ [m] and j qij ≤ 1 for all i ∈ [n], such that the optimal revenue
OPT ≤ 4 ·

X

RDij (qij ).

i,j

Proof. As shown in [11], OPT ≤ 4OPT C OPIES -UD. Let qij be the ex-ante probability that agent (i, j) is
served in the optimal mechanism for the copies setting. Chawla et al. [15] showed that OPT C OPIES -UD ≤
P
i,j RDij (qij ). Our statement follows from the two inequalities above.
Next, we consider a convex program (Figure 1) and argue that the value of the optimal solution of this
program is at least 18 of the optimal revenue.
Lemma 8. The optimal solution of convex program in Figure 1 is at least
8

OPT
8 .

This is exactly the copies setting used in [15], if every bidder i is unit-demand and has value Vi (tij ) with type ti . Notice that this
unit-demand multi-dimensional setting is equivalent as adding an extra constraint, each buyer can purchase at most one item, to the
original setting with subadditive bidders.

18

max

X

RDij (qij )

i,j

s.t.

X

qij ≤

1
2

for all j ∈ [m]

qij ≤

1
2

for all i ∈ [n]

i

X
j

qij ≥ 0

for all i ∈ [n] and j ∈ [m]

Figure 1: A Convex Program for Unit-demand Bidders with Exact Distributions.
n q′ o
ij
′ } be the collection of nonnegative numbers in Lemma 7. Clearly,
is a set of feasible
Proof. Let {qij
2
 q′ 
′ )
′ )
R
RDij (qij
R
(q
Dij (0)
Dij ij
solution for the convex program. Since RDij (·) is concave, RDij 2ij ≥
+
=
.
2
2
2
Therefore,
 ′ 
X
qij
OPT
1 X
′
RDij
RDij (qij
)≥
.
≥ ·
2
2
8
i,j

i,j

If we know all Fij exactly, we can solve the convex program (Figure 1) and use the optimal solution to
construct an SPM via an approach provided in [15, 11]. The constructed sequential posted mechanism has
revenue at least 41 of the optimal value of the convex program, which is at least OPT
32 . Next, we show that
with only access to F̂ij , we can essentially carry out the same approach. Consider a different convex program
(Figure 2).

max

X

RD̂ij (qij )

i,j

s.t.

X

qij ≤

1
+n·ǫ
2

for all j ∈ [m]

qij ≤

1
+m·ǫ
2

for all i ∈ [n]

i

X
j

qij ≥ 0

for all i ∈ [n] and j ∈ [m]

Figure 2: A Convex Program for Unit-demand Bidders with Approximate Distributions.
Not that if the support size for all D̂ij is upper bounded by some finite number s, the convex program
above can be rewritten as a linear program with size poly(n, m, s). In the following Lemma, we prove that the
optimal values of the two convex programs above are close.
∗}
Lemma 9. Let {qij
i∈[n],j∈[m] and {q̂ij }i∈[n],j∈[m] be the optimal solution of the convex program in Figure 1
and 2 respectively.
X
X
∗
RD̂ij (q̂ij ) ≥
RDij (qij
) − ǫ · mnH.
i,j

i,j

∗ , q̄ ∗ and x ∈ [0, 1] be the numbers
Proof. We first fix some notations. For any bidder i and item j, let qij
ij
ij
¯
−1
−1
∗
∗
∗
∗
∗
∗ +(1−x )· q̄ ∗ = q ∗ .
satisfy that xij · qij ·Fij (1− qij )+(1−xij )· q̄ij ·Fij (1− q̄ij ) = RDij (qij ) and xij · qij
ij
ij
ij
¯
¯
¯
19





∗ ), p̄ = F −1 (1 − q̄ ∗ ), and q ′ = x · 1 − F̂ (p ) + (1 − x ) · 1 − F̂ (p̄ ) .
Let pij = Fij −1 (1 − qij
ij
ij
ij
ij ij
ij
ij ij
ij
ij
¯
¯
¯
By the definition of RD̂ij (·),




′
RD̂ij (qij
) ≥ xij · 1 − F̂ij (pij ) · pij + (1 − xij ) · 1 − F̂ij (p̄ij ) · p̄ij
¯
¯

(4)

∗ − ǫ, 1 − q ∗ + ǫ] and F̂ (p̄ ) ∈ [1 − q̄ ∗ − ǫ, 1 − q̄ ∗ + ǫ]. Hence,
Since ||D̂ij − Dij ||K ≤ ǫ, F̂ij (pij ) ∈ [1 − qij
ij ij
ij
ij
ij
∗ ) − ǫ¯· H. Therefore, R
′ )≥R
∗ ) − ǫ · H.
¯
¯
(q
(q
the RHS of inequality (4) is greater than RDij (qij
Dij ij
D̂ij ij
′ }
Next, we argue that {qij
is
a
feasible
solution
for
the
convex
program
in Figure 2. Since 1 −
i∈[n],j∈[m]
P ′
P ∗
∗
∗
′
∗
F̂ij (pij ) ≤ qij + ǫ and 1 − F̂ij (p̄ij ) ≤ q̄ij + ǫ, qij ≤ qij + ǫ. Thus, i qij ≤ i qij + n · ǫ ≤ 21 + n · ǫ for all
P ′
¯
¯
≤ 21 + m P
j ∈ [m]. Similarly, we can proveP j qij
· ǫ for all i ∈ [n]. As
is the optimal solution
P {q̂ij }i∈[n],j∈[m]
′ )≥
∗ ) − ǫ · mnH.
for the second convex program, i,j RD̂ij (q̂ij ) ≥ i,j RD̂ij (qij
R
(q
i,j Dij ij

Finally, we show how to use the optimal solution of the convex program in Figure 2 to construct an
SPM that approximates the optimal revenue well. We first provide a general transformation that turns any
approximately feasible solution of convex program in Figure 1 to an SPM mechanism.
Lemma 10. For any distribution D = ×i∈[n],j∈[m]Dij , given a collection of independent random variables
{pij }i∈[n],j∈[m] such that
X

i∈[n]

and

X

Pr

[tij ≥ pij ] ≤ 1 − η1 ,

Pr

[tij ≥ pij ] ≤ 1 − η2 , for all i ∈ [n],

pij ,tij ∼Dij

j∈[m]

pij ,tij ∼Dij

for all j ∈ [m]

we can construct in polynomial time a randomized SPM such that the revenue under D is at least


X
η1 η2 ·
Epij pij · Pr [tij ≥ pij ] .
i,j

tij ∼Dij

Proof. Consider a randomized SPM that sells item j to bidder i at price pij . Notice that bidder i purchases
exactly item j if all of the following three conditions hold: (i) for all bidders ℓ 6= i, tℓj is smaller than the
corresponding price pℓj , (ii) for all items k 6= j, tik is smaller than the corresponding price pik , and (iii) tij
is greater than the corresponding price pij . These
P three conditions are independent from each other. The first
condition holds with probability
at
least
1
−
ℓ6=i Prpℓj ,tℓj ∼Dℓj [tℓj ≥ pℓj ] ≥ η1 . The second condition holds
P
with probability at least 1 − k6=j Prpik ,tik ∼Dik [tik ≥ pik ] ≥ η2 . When the first two conditions hold, bidder i


purchases item j whenever she can afford it. Her expected payment is E
 pij pij · Prtij ∼Dij [tij ≥pij ] . Hence,
the expected revenue for selling item
 i is at least η1 η2 · Epij pij · Prtij ∼Dij [tij ≥ pij ] and the total
P j to bidder
expected revenue is at least η1 η2 · i,j Epij pij · Prtij ∼Dij [tij ≥ pij ] .
Lemma 11. Given any feasible solution {qij }i∈[n],j∈[m] of the convex program in Figure 2, we can con
1
−
(n
+
m)
·
ǫ
·
struct
a
(randomized)
SPM
in
polynomial
time
such
that
its
revenue
under
D
is
at
least
4

P
i,j RD̂ij (qij ) − ǫ · nmH .

Proof. We first fix some notations. For any bidder i and item j, let qij , q̄ij and xij ∈ [0, 1] be the numbers
¯
satisfying xij · qij · F̂ij−1 (1 − qij ) + (1 − xij ) · q̄ij · F̂ij−1 (1 − q̄ij ) = RD̂ij (qij ) and xij · qij + (1 − xij ) · q̄ij = qij .
¯
¯
¯
20

We use pij to denote a random variable that is pij = F̂ij−1 (1 − qij ) with probability xij and p̄ij = F̂ij−1 (1 − q̄ij )
¯
¯
with probability 1 − xij .
Next, we construct a randomized SPM based on {pij }i∈[n],j∈[m] according to Lemma 10. Note that
X

i∈[n]

Pr

pij ,tij ∼Dij

[tij ≥ pij ] ≤

X

i∈[n]

Pr
pij ,tij ∼D̂ij

!

=

!

=

[tij ≥ pij ] + ǫ

X

qij + nǫ ≤

X

qij + mǫ ≤

i∈[n]

1
+ 2nǫ
2

for all item j, and
X

j∈[m]

Pr

pij ,tij ∼Dij

[tij ≥ pij ] ≤

X

j∈[m]

Pr
pij ,tij ∼D̂ij

[tij ≥ pij ] + ǫ

i∈[m]

1
+ 2mǫ
2

for all bidder i. Hence, we can construct in polynomial time a randomized SPM with revenue at least

 X



1
1
− 2nǫ
− 2mǫ ·
Epij pij · Pr [tij ≥ pij ]
tij ∼Dij
2
2
i,j
!#
"
X

1
Pr [tij ≥ pij ] − ǫ
Epij pij ·
− (n + m)ǫ
≥
4
t
∼D̂ij
ij
i,j

X

1
≥
RD̂ij (qij ) − ǫ · nmH
− (n + m)ǫ
4
i,j

≤ ǫ, and the second inequality is because pij is upper bounded
The first inequality is because Dij − D̂ij
h
i K
by H and Epij pij · Prtij ∼D̂ij [tij ≥ pij ] = RD̂ij (qij ) by the definition of pij .
Theorem 10. For unit-demand bidders, given distributions D̂ij where D̂ij − Dij

K

≤ ǫ for all i ∈ [n] and

j ∈ [m], there is a polynomial
 OPT time algorithm
 that constructs a randomized SPM whose revenue under D is at
1
least 4 − (n + m) · ǫ · 8 − 2ǫ · mnH .

Proof. Our algorithm first computes the optimal solution {q̂ij }i∈[n],j∈[m] for the convex program in Figure 2,
then constructs a randomized SPM based on {q̂ij }i∈[n],j∈[m] using Lemma 11. It is not hard to see that our
algorithm runs in polynomial time. By chaining the inequalities
 OPT in Lemma 8, 9 and 11, we can argue that the
1
revenue of our mechanism is at least 4 − (n + m) · ǫ · 8 − 2ǫ · mnH .

B.2

Unit-demand Valuations: sample access to bounded distributions

When the distributions Dij are all bounded, the following theorem provides the sample complexity.
Theorem 11. [35] When Dij is supported on [0, H] for all bidder i and item j, the sample complexity for(ǫ, δ)2

uniformly learning the revenue of SPMs for unit-demand bidders is O 1ǫ
m2 n log n log 1ǫ + log 1δ . That
is, with probability 1 − δ, the empirical revenue based on the samples for any SPM is within ǫ · H of its true
expected revenue. Moreover, with the same number of samples, there is a polynomial time algorithm that
learns an SPM whose revenue is at least OPT
144 − ǫH with probability 1 − δ.

21

B.3

Unit-demand Valuations: sample access to regular distributions

In this section, we show there exists a polynomial time algorithm that learns an SPM whose revenue is at least a
constant fraction of the optimal revenue with polynomial in n and m samples. Note that unlike in the previous
two models, the error of our learning algorithm is only multiplicative when the distributions are regular. First,
we present a Lemma regarding the revenue curve function for regular distributions.
Lemma 12. [7] For any regular distribution F , let RF (·) be the corresponding revenue curve. For any
0 < q ′ ≤ q ≤ p < 1,
(1 − p) · RF (q ′ ) ≤ RF (q).
Throughout this section, we use Z to denote max{m, n} and C to be a constant that will be specified later.
1
does not affect the objective
Using Lemma 12, we show in the next Lemma that restricting qij to be at least CZ
value of the convex program in Figure 1 by too much.
′
∗}
Lemma 13. Suppose {qij
i∈[n],j∈[m] is the optimal solution of the convex program in Figure 1. Let qij =
 P
 OPT
P
1
1
1
∗
′
∗
max{ CZ , qij }, then i,j RDij (qij ) ≥ 1 − CZ · i,j RDij (qij ) ≥ 1 − CZ · 8 .
P
∗ ) ≥ OPT . So to prove the statement, it suffices to argue that
Proof. According to Lemma 8, i,j RDij (qij
8

′ ) ≥ 1− 1
∗ ). If q ∗ = q ′ , this inequality clearly holds. If q ∗ 6= q ′ ,
for any i and j, RDij (qij
·
R
(q
Dij ij
ij
ij
ij
ij
CZ
′ )≥
∗ ≤ q ′ = 1 . Since F is regular, we can apply Lemma 12 to q ′ and q ∗ and obtain inequality R
(q
qij
ij
D
ij
ij
ij
ij
ij  CZ
1
∗ ).
· RDij (qij
1 − CZ
′
Dij

Using Lemma 13, we argue how to compute in polynomial time an approximately optimal SPM. Suppose
is the distribution that we obtain after truncating Dij at a threshold Hij 9 , and we have direct access to a

′ such that D̂ ′ − D ′
discrete distribution D̂ij
ij
ij

K

≤ ǫ for all i and j. We show in the following Lemma that

′ }
the optimal solution of a convex program similar to the one in Figure 2 but for {D̂ij
i∈[n],j∈[m] can guide us to
design an approximately optimal SPM under D in polynomial time. As we have sample access to D, we will
′ }
argue later that a polynomial number of samples suffices to generate {D̂ij
i∈[n],j∈[m] .
1
1
, 1 − 3C·Z
]
Lemma 14. Let {Hij }i∈[n],j∈[m] be a collection of positive numbers satisfying Fij (Hij ) ∈ [1 − C·Z
′
for all i ∈ [n] and j ∈ [m]. Let Dij be the distribution of the random variable min{tij , Hij } where tij ∼ Dij ,
′ − D′
D̂ij
ij

′ be a discrete distribution such that
and D̂ij

K

≤ ǫ for all i ∈ [n] and j ∈ [m]. Suppose

′ , then given direct access to D̂ ′ , we can
s is an upper bound of the support size for any distribution D̂ij
ij

1
1
compute in time polynomial in n, m and s a randomized
SPM
that
achieves
revenue
at
least
−
2
C − 2nǫ ·

1
1
1
1 − CZ
· OPT
2 − C − 2mǫ ·
8 − 2ǫ · nmH under D, where H = maxi,j Hij .

Proof. Consider the following convex program:
max

X

RD̂′ (qij )

i,j

s.t.

X

qij ≤

1
1
+ +n·ǫ
2 C

for all j ∈ [m]

qij ≤

1
1
+ +m·ǫ
2 C

for all i ∈ [n]

i

X
j

qij ≥ 0
9

ij

for all i ∈ [n] and j ∈ [m]

′
Let tij ∼ Dij , then min{tij , Hij } is the corresponding truncated random variable drawn from Dij
.

22

∗}
′ = max{ 1 , q ∗ }.
Let {qij
Figure 1 and qij
i∈[n],j∈[m] be the optimal solution of the convex hprogram in
C·Z ij
i
−1
′
′
′
For every i and j, let pij = Fij (1 − qij ) and q̃ij = Prtij ∼D̂′ tij ≥ pij . By the definition of Hij , p′ij ≤ Hij ,
ij
so
!


′
′
Pr ′ tij ≥ p′ij − ǫ ≥ p′ij qij
p′ij q̃ij ≥ p′ij
− ǫ · Hij = RDij (qij
(5)
) − ǫ · Hij .
tij ∼Dij

′ equals to R
′
p′ij qij
Dij (qij ) because Dij is a regular distribution.
Next, we argue that {q̃ij }i∈[n],j∈[m] is a feasible solution of the convex program above. Observe that

X
X
X
1
1
1
′
∗
q̃ij ≤
qij
+ nǫ ≤
qij
+
+ nǫ ≤ + + nǫ
CZ
2 C
i

i

i

for all item j ∈ [m] and
X

q̃ij ≤

j

X

′
qij
+ nǫ ≤

j

X

∗
qij
+

j

1
CZ



1
1
+ + mǫ
2 C

+ mǫ ≤

for all bidder i ∈ [n].
d be the optimal solution of the convex program above. As {q̃ij }i∈[n],j∈[m] is a feasible solution,
Let OPT


X
X
X
1
OPT
′
′
d
pij q̃ij ≥
RDij (qij ) − ǫ · nmH ≥ 1 −
OPT ≥
RD̂′ (q̃ij ) ≥
− ǫ · nmH.
·
ij
CZ
8
i,j

i,j

i,j

The second last inequality is due to inequality (5) and the last inequality is due to Lemma 13.
So far, we have argued that the optimal solution of our convex program has value close to the OPT. We will
show in the second part of the proof that using the optimal solution of our convex program, we can construct
d Let q̂ij be the optimal solution of the convex program
an SPM whose revenue under D is close to OPT.
above and p̂ij be the corresponding random price, that is, Prp̂ij ,tij ∼D̂′ [tij ≥ p̂ij ] = q̂ij and RD̂′ (q̂ij ) =
ij
ij
i
h
Ep̂ij p̂ij · Prtij ∼D̂′ [tij ≥ p̂ij ] . As p̂ij ≤ Hij ,
ij

Pr

p̂ij ,tij ∼Dij

[tij ≥ p̂ij ] =

Pr

′
p̂ij ,tij ∼Dij

[tij ≥ p̂ij ] ∈ [q̂ij − ǫ, q̂ij + ǫ].

Therefore, for all item j
X
i

Pr

p̂ij ,tij ∼Dij

and for all bidder i
X
Pr
j

p̂ij ,tij ∼Dij

[tij ≥ p̂ij ] ≤

[tij ≥ p̂ij ] ≤

X
i

X
j

Pr

′
p̂ij ,tij ∼D̂ij

Pr

′
p̂ij ,tij ∼D̂ij

[tij ≥ p̂ij ] + nǫ =

X

q̂ij + nǫ ≤

1
1
+ + 2nǫ
2 C

q̂ij + mǫ ≤

1
1
+ + 2mǫ.
2 C

i

[tij ≥ p̂ij ] + mǫ =

X
j

According to Lemma 10, we can construct a randomized SPM with {p̂ij }i∈[n],j∈[m] whose revenue is at least


 1
 P
1
1
1
i,j Ep̂ij p̂ij · Prtij ∼Dij [tij ≥ p̂ij ] under D. Clearly,
2 − C − 2nǫ · 2 − C − 2mǫ ·


Ep̂ij p̂ij ·

"

Pr [tij ≥ p̂ij ] ≥ Ep̂ij p̂ij ·

tij ∼Dij

Pr [tij ≥ p̂ij ] − ǫ

′
tij ∼D̂ij

23

!#

≥ RD̂′ (q̂ij ) − ǫ · Hij .
ij

Therefore, the revenue of the constructed randomized SPM under D is at least
 
 


1
1
1
1
d − ǫ · nmH
− − 2nǫ ·
− − 2mǫ · OPT
2 C
2 C

 
 


1
1
1
1
1
OPT
≥
− − 2nǫ ·
− − 2mǫ ·
1−
− 2ǫ · nmH .
·
2 C
2 C
CZ
8
It is not hard to see that both {q̂ij }i∈[n],j∈[m] and {p̂ij }i∈[n],j∈[m] can be computed in time polynomial in n, m
and s.
When ǫ is small enough, the additive error in Lemma 14 can be converted into a multiplicative error. Next,
′ }
we argue that with a polynomial number of samples, we can learn {Hij }i∈[n],j∈[m] and {D̂ij
i∈[n],j∈[m] with
enough accuracy.
Theorem 12. If for all bidder i and item j, Dij is a regular distribution, we can learn in polynomial
 time
nm
OPT
2
2
2
with probability 1 − δ a randomized SPM whose revenue is at least 33 with O Z m n · log δ (Z =
max{m, n}) samples.

samples from each Dij , we can find an Hij such that Fij (Hij )
Proof. First, if we take O C 2 · Z 2 · log nm
δ
1
1
δ
lies in[1 − CZ
, 1 − 3CZ
] with probability 1 − 2nm
. By the union bound, the probability that all Hij satisfy
1
1
δ
, 1 − 3C·Z
] for all i and j.
the requirement is at least 1 − 2 . From now on, we assume Fij (Hij ) ∈ [1 − C·Z
1
Observe that OPT ≥ maxi,j Hij · 3C·Z , as the expected revenue for selling item j to bidder i at price Hij
Hij
1
. Therefore, there exists sufficiently large constant d and C, if ǫ = d·Znm
the randomized
is at least 3C·Z
OPT
SPM learned in Lemma 14 has revenue at least 33
 . According to′ the Dvoretzky-Kiefer-Wolfowitz (DKW)
samples from Dij (we can take samples from Dij then cap
inequality [25], if we take O d2 Z 2 n2 m2 · log nm
δ
′ be the uniform distribution over the samples, D ′ − D̂ ′
the samples at Hij ) and let D̂ij
ij
ij
δ
′ − D̂ ′
. By the union bound, Dij
probability 1− 2nm
ij

≤

K

≤

1
d·Znm

with

1
d·Znm

for all i ∈ [n] and j ∈ [m] with probability

′ we learned from O Z 2 n2 m2 · log nm
at least 1 − δ/2. Finally, by another union bound, the Hij and D̂ij
δ
samples satisfy Fij (Hij ) ∈ [1 −

1
C·Z , 1

−

1
3C·Z ]

K

′ − D̂ ′
and Dij
ij

K

≤

1
d·Znm

for all i and j with probability

at least 1 − δ. In other words, we can learn a randomized SPM whose revenue is at least OPT
33 with probability

′ is at most
at least 1 − δ using O Z 2 n2 m2 · log nm
samples.
Furthermore,
the
support
size
of
any D̂ij
δ

samples, so our learning algorithm runs in time polynomial in n and m.
O Z 2 n2 m2 · log nm
δ

C

Missing Details from Section 5.2

C.1 Additive Valuations: sample access to bounded distributions
As shown by Goldner and Karlin [28], one sample suffices to design a mechanism that approximates BR EV .
The idea is toP
use the VCG with entry fee mechanism but replace the entry fee ei (b−i , Di ) for bidder i with
ei (b−i , si ) = j∈[m] (sij − maxk6=i bkj )+ , where si is a sample drawn from Di . It is easy to argue that for any
b−i , over the randomness of the sample si and bidder i’s real type ti , the event that eP
i (b−i , si ) ≥ ei (b−i , Di )
and bidder i accepts the entry fee ei (b−i , si ) happens with probability at least 81 . As 12 · i∈[n] Et [ei (t−i , Di )] =
BR EV , the
P expected revenue (over the randomness of the types and the samples) from their mechanism is at
least 81 · i∈[n] Et [ei (t−i , Di )] = BR4EV . Next, we show how to learn a mechanism that approximates SR EV .
24

Lemma 15. When Dij is supported on [0, H] for all bidder i and item j, the sample complexity for
(ǫ, δ)

1 2
1
1
2
uniformly learning the revenue of SPMs for additive bidders is O ǫ
m n log n log ǫ + log δ . More-

over, we can learn in polynomial time an SPM whose revenue is at least
given the same number of samples.

SR EV
4

−

3ǫ
2

· H with probability 1 − δ

Proof. The first half of the Lemma was proved by Morgenstern and Roughgarden [35]. We show how to
prove the second half of the claim. Let OPTj be the optimal revenue for selling item j. By the prophet
inequality [41], there exists an SPM for selling item j with a collection of prices {pij }i∈[n] that achieves
revenue at least OPTj /2. As the bidders are additive, if we run the SPMs for selling each item simultaneously,
the expected revenue is exactly the sum of the revenue of the SPM mechanisms for auctioning a single item.
Note that the simultaneous SPM is indeed a SPM for selling all items. Hence, there exists an SPM that
achieves revenue
 sample complexity for (ǫ, δ)-uniformly learning the revenue of
  at least OPT/2. Since the
1
1
m 2
n log n log ǫ + log δ , the empirical revenue induced by the samples is within ǫ · H of
SPMs is O
ǫ
the true expected revenue with probability 1 − δ for any SPM.
We use ERopt to denote the optimal empirical revenue obtained by any SPM. If we apply the prophet
inequality to the empirical distribution, we can construct an SPM whose empirical revenue ER is at least
ERopt /2. Notice that ERopt is at most ǫ · H less than the optimal true expected revenue obtained by any
SPM, which is at least OPT/2. Combining the two inequalities above, we have ER ≥ OPT/4 − ǫ/2 · H with
probability 1 − δ. Also, the true expected revenue of our SPM is at least ER − ǫ · H, so our SPM achieves
3ǫ
expected revenue at least OPT
4 − 2 · H with probability 1 − δ.
Now we are ready to prove our Theorem for additive bidders when their valuations are bounded.
Theorem 13. When the bidders have additive valuations and Dij is supported on [0, H] for all bidder i and
item j, we can learn in polynomial time a mechanism whose expected revenue is at least OPT
32 − ǫ · H with
probability 1 − δ given

  
1
1
m 2
· n log n log + log
O
ǫ
ǫ
δ
samples from D.

SR EV
ǫ
Proof. According to Lemma
we can learn a mechanism
 whose revenue is at least 4 − 24 · H with
 15,


2
probability 1 − δ given O mǫ · n log n log 1ǫ + log 1δ samples. As we explained in the beginning of this
section, with one sample from the distribution we can construct a randomized mechanism whose expected
revenue is at least BR4EV . Therefore, the better of our two mechanisms has expected revenue at least OPT
32 − ǫ · H
with probability 1 − δ.

C.2 Additive Valuations: direct access to approximate distributions
In this section, we discuss how to learn an approximately optimal mechanism for additive bidders when we are
given direct access to approximate value distributions. Again, we first show how to learn a mechanism whose
revenue approximates SR EV then we provide another mechanism whose revenue approximates BR EV .
Lemma 16. For additive bidders, given distributions D̂ij where

D̂ij − Dij

K

≤ ǫ for all i ∈ [n] and

j ∈ [m], there is a polynomial time algorithm
that constructs a randomized SPM whose revenue under D is at

1
SR EV
least 4 − ǫ · n ·
8 − 2ǫ · mnH .

Proof. Let OPTj be the optimal revenue for selling item j. As the bidders are additive, if we can construct

a randomized SPM Mj for every item j such that its expected revenue under D is at least 14 − ǫ · n ·
25



OPTj
8


− 2ǫ · nH , running these m randomized SPMs in parallel generates expected revenue at least
 
 
 

X 1
OPTj
1
SR EV
−ǫ·n ·
− 2ǫ · nH =
−ǫ·n ·
− 2ǫ · mnH
4
8
4
8
j∈[m]

under D. Due to Theorem 10, we can construct in polynomial time such a randomized SPM Mj for each item
j based on ×i∈[n] D̂ij .
Next, we show how to choose the entry fee based on D̂ = ×i,j D̂ij , so that the VCG with entry fee
mechanism has revenue that approximates BR EV under the true distribution D. More specifically, we use
the median of i’s utility under D̂i = ×j∈[m] D̂ij as bidder i’s entry fee. We prove the result in two steps.
We first show that if we can use an entry fee function such that every bidder i accepts her entry fee with
probability between [1/2 − η, 1/2] for any possible bid profiles b−i of the other bidders, the expected revenue
is at least (1/2 − η) · BR EV . Second, we show how to compute in polynomial time such entry fee functions
with η = O(mǫ) based on D̂.
Lemma 17. Suppose for every bidder i, di (·) : T−i 7→ R is a randomized entry fee function such that for any
bid profile b−i ∈ T−i of the other bidders




+
X 
1
1


− η,
≥ di (b−i ) ∈
tij − max bkj
Pr
k6=i
ti ∼Di
2
2
j∈[m]

with probability at least 1 − δ. Then if we use di (·) as the entry fee function in the VCG with entry fee
mechanism, the expected revenue is at least (1 − δ − 2η) · BR EV .
hP
i 

+
Proof. When Prti ∼Di
(t
−
max
b
)
≥
d
(b
)
∈ 21 − η, 21 , di (b−i ) is no less than the origij
i
−i
k6
=
i
kj
j∈[m]
inal entry fee ei (b−i , Di ) for any bid profile
−i of the other bidders. The expected revenue under the new entry
 bP
fee functions is at least ((1 − δ) · 12 − η · i∈[n] Eb−i ∼D−i [ei (b−i , Di )] ≥ (1 − δ − 2η) · BR EV .
Lemma 18. For any bidder i and any bid profile b−i from the other bidders, let Fi,b−i and F̂i,b−i be the distriP
butions for the random variable j∈[m] (tij − maxk6=i bkj )+ when ti is drawn from Di and D̂i respectively.

If Dij − D̂ij

K

≤ ǫ for all bidder i and item j, Fi,b−i − F̂i,b−i

K

≤ 2mǫ for all i and b−i . Moreover,

when mǫ ≤ 1/16, we can compute a randomized mechanism whose expected revenue is at least BR5EV .
o
n
P
+
(t
−
max
b
)
≥
x
. It is easy
Proof. For any real number x, consider event Ei,b−i ,x = ti
k6=i kj
j∈[m] ij
to see that Ei,b−i ,x is single-intersecting for any any i, b−i and x. According to Lemma 3,
Pr

ti ∼Di






Ei,b−i ,x − Pr Ei,b−i ,x ≤ 2mǫ
ti ∼D̂i

for any i, b−i and x. Hence, Fi,b−i − F̂i,b−i

K

≤ 2mǫ.

Next, we argue how to construct a randomized entry fee di (b−i ) in polynomial time with only sample access of F̂i,b−i . Suppose we take k samples from F̂i,b−i and sort them in descending order s1 ≥ s2 ≥ · · · ≥ sk .
Let the entry fee di (b−i ) to be s⌈ 5k ⌉ . By the Chernoff bound, with probability at least 1 − exp(−k/128) (over
16
hP
i


+
(t
−
max
b
)
≥
d
(b
)
= Prti ∼D̂i Ei,b−i ,di (b−i )
the randomness of the samples) Prti ∼D̂i
i −i
k6=i kj
j∈[m] ij






lies in 14 , 38 . Since Prti ∼Di Ei,b−i ,di (b−i ) = Prti ∼D̂i Ei,b−i ,di (b−i ) ± 2mǫ,
Pr

ti ∼Di




1 1
Ei,b−i ,di (b−i ) ∈ [ , ],
8 2
26

if mǫ ≤ 1/16. According
to Lemma 17, the expected revenue under our entry fee di (b−i ) is at least

1
BR EV
if we choose k to be larger than some absolute constant. Clearly,
4 − exp(−k/128) · BR EV ≥
5
the procedure above can be completed in polynomial time with access to D̂.
Combining Lemma 16 and 18, we are ready to prove our main result of this section.
Theorem 14. If all bidders have additive valuations, given distributions D̂ij where D̂ij − Dij

K

≤ ǫ for

all i ∈ [n] and j ∈ [m], there is a polynomial time algorithm that constructs a mechanism whose expected
1
revenue under D is at least OPT
266 − 96ǫ · mnH when ǫ ≤ 16 max{m,n} .
Proof. Since ǫ ≤
3
16

SR EV
8

1
,
16 max{m,n}


we can learn in polynomial time a randomized SPM whose revenue is at

least
·
− 2ǫ · mnH and a VCG with entry fee mechanism whose revenue is at least BR EV /5. As
OPT ≤ 6 · SR EV + 2BR EV (Theorem 6), the better of the two mechanisms we can learn in polynomial time
has revenue at least OPT
266 − 96ǫ · mnH.

D

Missing Details from Section 6

Proof of Lemma 5: We only sketch the proof here. Let P OST R EV denote the highest revenue obtainable
by any RSPM. In [13], Cai and Zhao constructed an upper bound of the optimal revenue using duality and
separated the upper bound into three components: S INGLE , TAIL and C ORE. Both S INGLE and TAIL are
within constant times the P OST R EV , and the ASPE(p∗ , δ∗ ) is used to bound the C ORE. It turns out one
can use essentially the same proof as in [13] to prove that the mechanism ASPE(p′, δ′ ) has revenue at least
a1 (µ) · C ORE − a2 (µ) · P OST R EV − a3 (µ) · (n + m) · ǫ where a1 (µ), a2 (µ) and a3 (µ) are functions that
map µ to positive numbers. In other words, we can replace ASPE(p∗ , δ∗ ) with ASPE(p′, δ′ ) and still obtain a
constant factor approximation. ✷

D.1 Missing Proofs from Section 6.1
We formalize the first step of our algorithm in the following lemma.
Lemma 19. For any B > 0, ǫ > 0, η ∈ [0, 1] and µ ∈ [0,

1
4 ],

suppose we take K = O



log

1
+log n+m log B
η
ǫ
µ2



samples t(1) , · · · , t(K) from D. For any collection of prices {pj }j∈[m] in the B-bounded ǫ-net, define the
(p)

(1)

(K)

entry fee δi (S) of bidder i for setPS under {pj }j∈[m] to be the median of ui (ti , S), · · · , ui (ti , S), where
ui (ti , S) = maxS∗⊆S vi (ti , S ∗ )− j∈S ∗ pj . Then with probability 1−η, for any collection of prices {pj }j∈[m]
n
o
(p)
in the B-bounded ǫ-net, δi (·)
is a collection of µ-balanced entry fee functions.
i∈[n]

Proof. For any fixed {pj }j∈[m] , fixed bidder i and fixed set S, it is easy to argue that the probability for
(p)

Prti ∼Di [ui (ti , S) ≥ δi (S)] to be larger than 21 + µ or smaller than 12 − µ is at most 2exp(−2Kµ2 ) due to
the Chernoff bound. Next, we take a union bound over all {pj }j∈[m] in the ǫ-net, all bidders and all possible
(p)

subsets of [m], so the probability that for any collection of prices {pj }j∈[m] in the ǫ-net {δi (·)}i∈[n] is a
m m
collection of µ-balanced entry fee functions is at least 1 − 2 exp(−2Kµ2 ) · Bǫ
· 2 · n. If we take K to be

at least

log η1 +log n+m log
µ2

B
ǫ

, the success probability is at least 1 − η.

Next, we formalize the second step of our learning algorithm.

27

Lemma 20. For any B ≥ 2G, ǫ, ǫ′ > 0, η ∈ [0, 1] and µ ∈ [0, 14 ], suppose for every collection of
(p)

prices {pj }j∈[m] in the B-bounded ǫ-net, {δi (·)}i∈[n] is a collection of µ-balanced entry fee functions.
We use S to denote the set that contains ASPE(p, δ(p) ) for every p in the B-bounded ǫ-net. If we take

K = O

log

1
+m log B
η
ǫ
ǫ′2

′

samples t(1) , · · · , t(K) from D and let ASPE(p′ , δ(p ) ) be the mechanism that has
′

the highest revenue in S. Then with probability at least 1 − η, the better of ASPE(p′ , δ(p ) ) and the best RSPM
achieves revenue at least COPT
− C2 (µ) · (m + n) · ǫ − 2mnB · ǫ′ .
1 (µ)
Proof. For any {pj }j∈[m] in the ǫ-net, define R EV (p) to be the expected revenue of ASPE(p, δ(p) ) and Rd
EV (p)
(p)
d
be the average revenue of ASPE(p, δ ) among the K samples. First, we argue that R EV (p) is a random
variable that lies between [0, mnB]. The revenue from selling the items can be at most mB as there are only
m items and pj ≤ B for all j ∈ [m]. How about the entry fee? For any bidder i,
X
1
m
≤ .
Pr [vi (ti , [m]) ≥ mG] ≤
Pr [Vi (tij ) ≥ G] ≤
ti ∼Di
tij ∼Dij
5 max{m, n}
5
j∈[m]

The first inequality is because vi (ti , ·) is a subadditive function for every type ti ∈ Ti , so for vi (ti , [m]) to
be greater than mG, there must exist a item j such that Vi (tij ) ≥ G. The second inequality follows from the
definition of G in Theorem 8.
(p)
If there exists a set S ⊆ [m] such that δi (S) > mG, we have
h
i 1
1
(p)
Pr [vi (ti , [m]) ≥ mG] ≥ Pr vi (ti , [m]) ≥ δi (S) ≥ − µ ≥ .
ti ∼Di
ti ∼Di
2
4
(p)

Contradiction. Note that the second inequality is because δi (·) is µ-balanced. Hence, the entry fee is always
upper bounded by mG and Rd
EV (p) is at most mnG + mB ≤ mnB. Also, notice that the expectation of
Rd
EV (p) is exactly R EV (p). By the Chernoff bound,
i
h
′2
′
Pr R EV (p) − Rd
EV (p) ≤ mnB · ǫ ≥ 1 − 2 exp(−2K · ǫ )
for any fixed {pj }j∈[m] . By the union bound, the probability that for all {pj }j∈[m] in the ǫ-net
′
R EV (p) − Rd
EV (p) ≤ mnB · ǫ

m
is at least 1 − 2 exp(−2K · ǫ′2 ) · Bǫ , which is lower bounded by 1 − η due to our choice of K. When this
′
happens, the expected revenue of ASPE(p′, δ(p ) ) is at most 2mnB · ǫ′ less than the highest expected revenue
achievable by any of these mechanisms, because
′
′
′
′
d
R EV (p′ ) ≥ Rd
EV (p ) − mnB · ǫ ≥ R
EV (p) − mnB · ǫ ≥ R EV (p) − 2mnB · ǫ

for any p in the ǫ-net. Combining this inequality with Corollary 2 completes our proof.

Note that Lemma 19 and 20 hold for all distributions D. The reason we require D to be bounded or regular
is because without these restrictions, we do not know how to approximate the best RSPM. In the following
Theorem, we combine Lemma 19, 20 and Theorem 11 to obtain the sample complexity of our learning
algorithm for bounded distributions.
Theorem 15. When all bidders’ valuations are XOS over independent
and the random variable
Vi (tij )
 items

2 
mn
1
is supported on [0, H] for any bidder i and any item j, with O
· m · log m+n
samples
ξ
ξ + log δ

from D, we can learn an RSPM and an ASPE such that with probability at least 1 − δ the better of the two
mechanisms has revenue at least OPT
c − ξ · H for some absolute constant c > 1.
28

Proof. With O

  

2
1
2 n log n log 1 + log 1
m
samples, we can obtain an RSPM whose revenue is at
ξ
ξ
δ

1
least 24
of the revenue of the best RSPM minus 2ξ · H with probability 1 − δ/2 according to Theorem 11.
ξ
ξ·H
and ǫ′ = 12mn
Let µ be some fixed constant in [0, 41 ], B = 2H, ǫ = 6C2 (µ)(m+n)
. According to Lemma 19,


samples, we can construct an entry fee function for each price vector
given O log 1δ + log n + m log m+n
ξ
in the B-bounded ǫ-net, such that all these entry fee functions
with probabilityat least 1 − δ/4.
 are µ-balanced

2 
mn
1
According to Lemma 20, we can learn an ASPE with O
· m · log m+n
fresh samples
ξ
ξ + log δ

− 2ξ · H
from D, such that the better of the ASPE we learned and the best RSPM has revenue of at least COPT
1 (µ)
with probability 1 − δ/4. Combining the statements
we can learn with probability
1 − δ a mechanism
 above,

2 
mn
1
whose revenue is at least OPT
· m · log m+n
samples.
c − ξ · H with O
ξ
ξ + log δ

In the next Theorem, we combine Lemma 19, 20 and Theorem 12 to obtain the sample complexity of our
learning algorithm for regular distributions.
Theorem 16. When all bidders’ valuations are XOS over independent items and the random variable
Vi (tij )
is regular for each item j ∈ [m] and bidder i ∈ [n], with O Z 2 m2 n2 · m · log(m + n) + log 1δ (Z =
max{m, n}) samples from D, we can learn an RSPM and an ASPE such that with probability at least 1 − δ
the better of the two mechanisms has revenue at least OPT
c for some absolute constant c > 1.
Proof. According to Theorem 12, we can learn with probability
 1 − δ/2 a randomized RSPM whose revenue
nm
1
2
2
2
with O Z m n · log δ samples. Next, we learn an ASPE with high
is at least 33 of the optimal RSPM

revenue. With O Z 2 · log nm
samples
from each Dij , we can estimate Wij such that
δ


1 1
,
Pr [Vi (tij ) ≥ Wij ] ∈
tij ∼Dij
6Z 5Z
δ
. By the union bound, the probability that all Wij satisfy the requirement is at least
with probability 1 − 4nm
δ
1 − 4 . So with probability at least 1 − 4δ , Wij ≥ Gij for all i ∈ [n] and j ∈ [m].
ξ·B
ξ
Let B = 2·maxi,j Wij , µ be some fixed constant in [0, 41 ], ǫ = C2 (µ)Z(m+n)
for some small
and ǫ′ = 2mnZ

1
constant ξ, which will be specified later. We know that given O log δ + log n + m log(m + n) samples, we
can construct µ-balanced entry fee functions for all price vectors in the B-bounded ǫ-net with probability
1 − δ/8 due to Lemma 19. According to Lemma 20, we can learn an ASPE with



1
2 2 2
O Z m n · m · log(m + n) + log
δ

fresh samples from D, such that the better of the ASPE we learned and the best RSPM has revenue of at least
2ξ·B
OPT
C1 (µ) − Z with probability 1 − δ/8. Note that there exists a bidder i and an item j such that Wij = B/2,
so OPT ≥

B
2

·

1
6Z

and for sufficiently small ξ,

OPT
C1 (µ)

−

2ξ·B
Z

≥

OPT
2C1 (µ) .

can learn with probability 1 − δ a mechanism
whose revenue is at least

1
2
2
2
O Z m n · m · log(m + n) + log δ samples.

29

Combining the statements above, we
OPT
c

for some absolute constant c with

E Learning Algorithms for Symmetric Bidders
E.1

An Upper Bound of the Optimal Revenue for Symmetric Bidders

In this section, we introduce an upper bound to OPT based on duality [13], which is crucial for us to prove
the approximation ratios of our learning algorithms. We first fix some notation. Let P OST R EV be the highest
revenue obtainable by any RSPM. As the bidders are symmetric, we drop the subscript i when there is no
confusion. In particular, we use V (tij ) to denote bidder i’s value for winning item j if her private information
for item j is tij , and v(ti , S) to denote bidder i’s value for set S when her type is ti . We use Dj to denote the
distribution of the private information about item j. Let σiS (t) be the interim probability for bidder i to receive
exactly set S ⊆ [m] when her type is t.
In [13], an upper bound of the optimal revenue is derived using duality theory. Their upper bound applies
to asymmetric bidders with valuations that are subadditive over independent items. When the bidders are
symmetric, we can simplify their upper bound. First, we need the definition of b-balanced thresholds.
Definition 7 (b-balanced Thresholds). For any constant b ∈ (0, 1), a collection of positive real numbers
b
].
{βj }j∈[m] is b-balanced if for all i ∈ [n] and j ∈ [m], Prtij ∼Dj [V (tij ) ≥ βj ] ∈ [ nb , n−1
Note that when bidders are asymmetric, b-balanced thresholds are not guaranteed to exist, as there may not
b
exist any βj that satisfies Prtij ∼Dj [V (tij ) ≥ βj ] ∈ [ nb , n−1
] for all bidder i simultaneously. Next, we define
the C OREη (β) which will be crucial for upper bounding the optimal revenue.10
Definition 8 (C ORE). Given any collection of thresholds {βj }j∈[n] and a nonnegative constant η ≤ 41 ,
P
• if j∈[m] Prtj ∼Dj [V (tj ) ≥ βj ] ≤ 12 − η, let cη (β) be 0;


P
• otherwise, let cη (β) be a nonnegative number such that j∈[m] Prtj ∼Dj [V (tj ) ≥ βj + cη (β)] ∈ 21 − η, 12 .
For every type t, let Cη (t) = {j | V (tj ) < βj + cη (β)}. Then,
X X
X
C OREη (β) = max
f (ti ) ·
σiS (ti ) · v (ti , S ∩ Cη (ti )) ,
σ∈P (D)

i∈[n] ti ∈Ti

S⊆[m]

where P (D) is the set of all feasible interim allocation rules. That is, C OREη (β) is the maximum welfare a
mechanism can extract out of the allocation of items whose individual value for the bidder they are allocated
to is lower than the adjusted thresholds.
It was shown in [13] that every collection of thresholds induces an upper bound to the optimal revenue. In
particular, for any choice of thresholds {βj }j∈[m] and η 11 , the revenue R EV (M ) of any BIC mechanism M is
upper bounded by
2 · S INGLE (M, β) + 4 · TAIL η (M, β) + 4 · C OREη (M, β) (Adapted from Theorem 2 in [13]).
These terms depend on the choice of {βj }j∈[m] , η as well as the mechanism M . We refer interested readers
to [13] for the definitions of these terms. To obtain a benchmark/upper bound of the optimal revenue, one can
simply replace the above expression with
2 · max S INGLE (M, β) + 4 · max TAIL η (M, β) + 4 · max C OREη (M, β).
M

M

M

10

For readers that are familiar with the definition of the C ORE in [13], C OREη (β) is essentially the same term but adapted for
symmetric bidders.
11
In [13], the thresholds are allowed to depend on the identity of the bidder. More specifically, for any i ∈ [n] and j ∈ [m], there
is an associated threshold βij . Their upper bound applies to asymmetric thresholds as well. Indeed, when the bidders are asymmetric,
their upper bound is induced by a set of asymmetric thresholds. As we only discuss symmetric bidders in this section, we focus on
symmetric thresholds for simplicity. Regarding η, Cai and Zhao only considered the case when η = 0, but their analysis can be easily
modified to accommodate any η ≤ 1/4. See Theorem 17 for the modified upper bound.

30

It is not hard to see that this benchmark may be impossible to approximate for certain choices of the thresholds.
Just imagine the case when the thresholds are extremely high, then maxM C OREη (M, β) becomes the optimal
social welfare which can be arbitrarily large comparing to the optimal revenue. What Cai and Zhao [13]
showed was that when the thresholds are b-balanced, this upper bound can indeed be approximated by the
revenue of an RSPM and an ASPE. From now on, we only consider b-balanced thresholds.
Using results in [13], we can further simplify the benchmark. In particular, maxM S INGLE (M, β) is less
2
· P OST R EV for any
than 6 · P OST R EV for all choices of {βj }j∈[n] and maxM TAIL η (M, β) is less than 1−b
choice of η and b-balanced thresholds {βj }j∈[n] . Moreover, maxM C OREη (M, β) ≤ C OREη (β). Combining
the inequalities above, we obtain the following Theorem.
Theorem 17 (Adapted from [13]). When the bidders are symmetric and have valuations that are subadditive
over independent items, for any constant b ∈ (0, 1), η ≤ 14 and a collection of b-balanced thresholds {βj }j∈[m] ,
OPT ≤

E.2



12 +

8
1−b



· P OST R EV + 4 · C OREη (β).

Symmetric Bidders with XOS Valuations

In this section, we show how to learn in polynomial time an approximately optimal mechanism for symmetric
bidders with XOS valuations given sample access to the distributions. According to Theorem 17, we only need
to learn a mechanism that approximates P OST R EV and C OREη (β). From Section 5.1, we know how to approximated P OST R EV in polynomial time, so we focus on learning a mechanism whose revenue approximates
C OREη (β).
First, we need a crucial property about XOS valuations.
Lemma 21 (Supporting Pricesn[23]). oIf v(t, ·) is an XOS function, for any subset S ⊆ [m] there exists a
collection of supporting prices θjS (t)
for v(t, S) such that
j∈S

P

1. v(t, S ′ ) ≥ j∈S ′ θjS (t) for all S ′ ⊆ S and
P
S
2.
j∈S θj (t) = v(t, S).

Let v ′ (ti , S) = v (ti , S ∩ Cη (ti )) and Fi be the distribution of the valuation v ′ (ti , S). As the bidders are
symmetric, Fi = Fi′ for any i and i′ . The C OREη (β) is exactly the maximum expected social welfare if
every bidder i’s valuation is drawn independently from Fi . Cai and Zhao [13] showed how to use an ASPE to
approximate this term. In the next Lemma, we construct the prices used in their ASPE and show its relation to
C OREη (β).
Lemma 22. (Adapted from [13]) Let every bidder i’s valuation be v ′ (ti , S) = v (ti , S ∩ Cη (ti )) when her type
is ti and σ ∗ be a symmetric allocation that achieves α-fraction of the optimal social welfare with respect to
v ′ (·, ·). For every item j ∈ [m], let
Qη,j =

X
1 X X
S∩C (t )
∗
·
f (ti ) ·
σiS
(ti ) · θj η i (ti ),
2
i∈[n] ti ∈Ti

n
o
S∩C (t )
where θj η i (ti )

j∈S∩Cη (ti )

S:j∈S

is the supporting prices for v (ti , S ∩ Cη (ti )). Let
u∗ (t, S) = max
v(t, S ∗ ) −
∗
S ⊆S

X

j∈S ∗

31

Qη,j

be a bidder’s utility for the set of items S when her type is t. We define δ∗ (S) to be the median of the
 random
∗
∗
variable u (t, S) (with t ∼ ×j∈[m]Dj ) for any set S ⊆ [m]. The revenue of ASPE {Qη,j }j∈[m] , δ is at least
α · C OREη (β)
− C(b, η) · P OST R EV ,
2

where C(b, η) is a function that only depends on b and η.
Proof. We can essentially use the same proof in [13] to prove that the expected revenue of the ASPE is at least
X
Qη,j − C(b, η) · P OST R EV .
j∈[m]

For readers that are familiar with that proof, the only thing we need to make sure is that our choice of σ ∗ and
{βj }j∈[m] satisfy Lemma 5 in [13]. Since σ ∗ is symmetric and {βj }j∈[m] is b-balanced, for all bidder i and
item j
X
b
· (n − 1) = b,
Pr [V (tkj ) ≥ βj ] ≤
tkj ∼Dj
n−1
k6=i

and
Pr [V (tij ) ≥ βj ] /b ≥ 1/n ≥ ·

tij ∼Dj

Next, we argue

P

ti ∈Ti

j∈[m] Qη,j

X

j∈[m]

Qη,j =

X

≥

α·C OREη (β)
.
2

fi (ti ) ·

X

∗
σiS
(ti ).

S:j∈S

Observe that

X
1 X X
∗
·
f (ti ) ·
σiS
(ti ) · v ′ (ti , S) ≥ α · C OREη (β).
2
i∈[n] ti ∈Ti

S

The last inequality is because C OREη (β) is the maximum social welfare under v ′ (·, ·) and σ ∗ achieves α
fraction of that.
Lemma 23. For any ǫ > 0 and µ ∈ [0, 41 ], let {Qj }j∈[m] be a collection of prices such that |Qj − Qη,j | ≤ ǫ
for all j ∈ [m]. Let δ(S) be the entry fee function such that Pr
Pt∼×j∈[m] Dj [u(t, S) ≥ δ(S)] ∈ [1/2−µ, 1/2+µ]
∗
for any set S ⊆ [m], where u(t, S) = maxS∗⊆S v(t, S ) − j∈S ∗ Qj . Then, the ASPE(Q, δ) achieves at least
α·C OREη (β)
B1 (µ)

− B2 (b, η, µ) · P OST R EV − B3 (µ) · (m + n) · ǫ revenue when bidders’ valuations are XOS over
independent item. Both B1 (µ) and B3 (µ) are functions that only depend on µ and B2 (b, η, µ) is a function that
only depends on µ, b and η.

Proof. It turns out the proof in [13] is robust enough to accommodate the error ǫ and µ. We can prove the
claim by following essentially the same analysis as in [13]. We do not include the details here.
E.2.1 Leaning the ASPE in Polynomial Time
We first show how to learn a collection of b-balanced thresholds and the corresponding cη (β).
a
Lemma 24. For any positive constant b < 1 and η ≤ 14 , there is a polynomial time algorithm that computes

collection of b-balanced thresholds {βj }j∈[m] and cη (β) with probability 1−δ using O m2 n4 log m
samples
δ
from distribution ×j∈[m] Dj .

32


(1)
(K)
Proof. Given K = O m2 n4 log m + log 1δ samples tj , . . . , tj from distribution Dj , we construct Fj as


 
(K)
(1)
. According to the DKW Theorem [25], with probability
the uniform distribution over V tj , . . . , V tj
at least 1 − δ/m,
1
for all x
(6)
Pr [V (tj ) ≥ x] − Pr [vj ≥ x] ≤
tj ∼Dj
vj ∼Fj
c · mn2
where c is a constant that will be specified later. From now on, we assume that Inequality (6) holds for every
j, which happens with probability 1 − δ.
h
 i
(ℓ)
(ℓ)
b
As 1/K ≤ 3nb 2 ≤ n−1
− 3nb 2 − nb − 3nb 2 , there must exist a sample tj such that Prvj ∼Fj vj ≥ V tj
∈
i
 
h
(ℓ)
b
b
b
b
. Note that
n + 3n2 , n−1 − 3n2 . Let βj = V tj



1
1
Pr [V (tj ) ≥ βj ] ∈ Pr [vj ≥ βj ] −
, Pr [vj ≥ βj ] +
.
tj ∼Dj
vj ∼Fj
c · mn2 vj ∼Fj
c · mn2
i
h
b
. Thus, βj is b-balanced for all item j.
If c is less than 3b , Prtj ∼Dj [V (tj ) ≥ βj ] ∈ nb , n−1
P
Next, we argue how to learn cη (β). If j∈[m] Prvj ∼Fj [vj ≥ βj ] ≤ 21 − η2 , let cη (β) = 0. This is a
P
valid choice, as j Prtj ∼Dj [V (tj ) ≥ βj ] is at most 12 − η2 + cn1 2 ≤ 21 according to inequality (6). SupP
pose j∈[m] Prvj ∼Fj [vj ≥ βj ] > 21 − η2 , as m/K < η4 , there must exist some item k ∈ [m] and a sami
h
 
 


P
(ℓ)
(ℓ)
≥ βk such that j∈[m] Prvj ∼Fj vj ≥ βj + V tk − βk ∈ 21 − η4 , 21 − η2 . Let cη (β) =
ple V tk
 
(ℓ)
V tk − βk . According to inequality (6),
X

j∈[m]


1 1 η
1
1 η
− −
, − +
.
Pr [V (tj ) ≥ βj + cη (β)] ∈
tj ∼Dj
2 4 cn2 2 2 cn2




P
For sufficiently large c, j Prtj ∼Dj [V (tj ) ≥ βj + cη (β)] ∈ 12 − η, 12 .
Finding each βj takes O(K log K) time and finding the cη (β) takes O(mK) time. So we can learn
in polynomial time
 a collection of b-balanced thresholds {βj }j∈[m] and cη (β) with probability 1 − δ using
m
2
4
O m n log δ samples.

Next, we show how to learn the prices of the ASPE. As showed by Feige [27], there exists a polynomial
time algorithm that achieves 1− 1e fraction of the optimal social welfare when bidders have XOS valuations. We
let σ ∗ be the interim allocation rule induced by Feige’s algorithm and estimate the prices by running Feige’s
algorithm on sampled valuation profiles. To run Feige’s algorithm, we need a demand oracle for bidder’s
valuations. In the following Lemma, we argue that v ′ (t, ·) is an XOS function for any type t, and given a value
(or demand, XOS) oracle for v(t, ·), we can construct in polynomial time the corresponding oracle for v ′ (t, ·).
First, we define these oracles formally.
Definition 9. We consider the following three oracles for a bidder’s valuation function v(t, ·):
• Value oracle: takes a set S ⊆ [m] as the input and returns v(t, S).
• Demand oracle: takes a collection of prices {pj }P
j∈[m] as an input and returns the favorite set under
these prices, that is, S ∗ ∈ argmaxS∈[m] v(t, S) − j∈S pj .
• XOS oracle (only when v(t, ·) is XOS): takes a set S ⊆ [m] as the input and returns the supporting
prices {θjS (t)}j∈S for v(t, S).
33

Lemma 25. Given a collection of thresholds {βj }j∈[m] and cη (β). For any set S ⊆ [m], let v ′ (t, S) =
v(t, S ∩ Cη (t)). If v(t, ·) is an XOS function, v ′ (t, ·) is also an XOS function. Given a value (or demand, XOS)
oracle for v(t, ·), we can construct in polynomial time a value (or demand, XOS) oracle for v ′ (t, ·).
Proof. If v(t, ·) is an XOS function, v(t, ·) can be represented as the max of a collection of additive functions.
Observe that if we change the values for items in Cη (t) to 0 in each of these additive functions, v ′ (t, ·) equals
to the max of this new collection of additive functions. Hence, v ′ (t, ·) is also an XOS function.
If we are given a value oracle for v(t, ·), it is straightforward to construct a value oracle for v ′ (t, ·). If
we are given a demand oracle for v(t, ·), here is how to construct a demand oracle for v ′ (t, ·). For every
queried price vector {pj }j∈[m] , we change the price for each item outside Cη (t) to 2v(t, [m]) and keep the
prices for the items in Cη (t). Let this new price vector be p′ . We query the demand oracle of v(t, ·) on p′ .
The output set should also be the demand set for v ′ (t, ·) under prices p, as the bidder can only afford items
in Cnη (t) and v ′ (t,
o S) = v(t, S) for any set S ⊆ Cη (t). Finally, we consider the XOS oracle. For any set S,
S∩Cη (t)

let θj

(t)

S∩Cη (t)

j∈S∩Cη (t)

be the supporting prices for v(t, S ∩ Cη (t)). Let γjS (t) = θj

for all item j in

Cη (t) ∩ S and γjS (t) = 0 for all item j in S − Cη (t). According to the definition of v ′ (t, ·), {γjS (t)}j∈S is the
supporting price for v ′ (t, S). So given an XOS oracle for v(t, ·), we can compute the supporting price of any
set S for v ′ (t, ·) in polynomial time.

Lemma 25 shows that v ′ (t, ·) is also an XOS function for any type t and with access to a demand oracle
for v(t, ·) we can construct a demand oracle for v ′ (t, ·) in polynomial time. So we can indeed run Feige’s
algorithm on v ′ . In the next Lemma, we show how to learn a collection of prices {Qj }j∈[m] and entry fee
function δ(·, ·) such that the corresponding ASPE has high revenue.
Lemma 26. Given a collection of b-balanced thresholds {βj }j∈[m] and cη (β), and access to value, demand
and XOS oracles for valuation v(t, ·) for every type t, there is a polynomial time algorithm that learns an
C OREη (β)
ASPE({Qj }j∈[m] , δ) whose revenue is at least
− g(b, η) · P OST R EV − K2 · ξ · OPT with probability
K1


samples from ×j∈[m] Dj , where K1 and K2 are positive absolute
at least 1 − ζ using O n3 (m + n)2 log m
ζ
constants, and g(b, η) is a function that only depends on b and η.
Proof. According to Lemma 25, we can construct value, demand and XOS oracles for valuation v ′ (t, ·) given
access to the corresponding oracles for v(t, ·). We use {γjS (t)}j∈S to denote the output of the XOS oracle for
S∩Cη (t)

v ′ (t, ·) on set S. In particular, γjS (t) = 0 for all j ∈ S − Cη (t) and γjS (t) = θj

(t) for all j ∈ S ∩ Cη (t),

S∩C (t)
{θj η (t)}j∈S∩Cη (t)

where
is the supporting prices for v(t, S ∩ Cη (t)). Let A(t) be the allocation computed
by Feige’s algorithm on the valuation profile (v ′ (t1 , ·), . . . , v ′ (tn , ·)), where Ai (t) denotes the set of items that
bidder i receives. Let σ ∗ be the interim allocation rule induced by A(·) when bidders types are all drawn from
∗ (t ) = Pr
×j∈[m] Dj independently. That is, σiS
i
t−i [Ai (t) = S]. We use the same definition for Qη,j as in
Lemma 22. In other words, Qη,j is the contribution of item j to the social welfare under allocation rule σ ∗ , so
we can rewrite it as


X
1
A (t)
· Et 
1 [j ∈ Ai (t)] · γj i (ti ) .
2
i∈[n]


 A (t(ℓ) ) (ℓ)
P
(ti ). We
Let t(1), . . . , t(K) be K sampled type profiles, and q (ℓ) = 21 i∈[n] 1 j ∈ Ai (t(ℓ) ) · γj i
1 P
(ℓ)
S
set Qj to be K · ℓ∈[K] q . Since γj (t) ≤ βj + cη (β) for any j, S and t, Qj ≤ βj + cη (β). By the Chernoff
bound,
Pr [|Qj − Qη,j | ≤ ǫ · (βj + cη (β))] ≥ 1 − 2 exp(−2K · ǫ2 ).
34

As {βj }j∈[m] is a collection of b-balanced thresholds, we can obtain revenue βj · nb by only selling
item j to one bidder at price βj . Hence, βj ≤ n·OPT
b . Now, consider a posted price mechanism that
sells
item
j
at
price
β
+
c
(β).
A
single
bidder
will
purchase at least one item with probability at least
j
η
P
1
j Prtj ∼Dj [V (tj ) ≥ βj + cη (β)] which is no less than 2 − η if cη (β) > 0. Hence, the revenue of this mech
ξ
anism is at least cη (β) · 12 − η . As η ≤ 14 , cη (β) ≤ 4OPT. If we let ǫ = (m+n)·(n/b+4)
for some small
i
h
log 4m
ζ
ξ
constant ξ which will be specified later and K = 2ǫ2ζ , we have Pr |Qj − Qη,j | ≤ m+n
· OPT ≥ 1 − 2m
.


In other words, with O n3 (m + n)2 log m
samples from ×j∈[m] Dj (as each tℓ costs n samples), we can
ζ

ξ
· OPT for all item j
learn in polynomial time a collection of prices {Qj }j∈[m] such that |Qj − Qη,j | ≤ m+n
with probability 1 − ζ/2.
Next, we consider the entry fee function. We use essentially the same argument as in Lemma 19. Suppose
we take L samples t(1) , · · · , t(L) from ×j∈[m]Dj . Define the entry fee δ(S) for set S under {Qj }j∈[m] to be
P
the median of u(t(1) , S), · · · , u(t(L) , S), where u(t, S) = maxS∗⊆S v(t, S ∗ ) − j∈S ∗ pj . Given any constant
µ ∈ [0, 1/4], for any fixed set S, it is easy to argue that the probability for Prt∼×j∈[m] Dj [u(t, S) ≥ δ(S)] to
be larger than 21 + µ or less than 21 − µ is at most 2 exp(−2Lµ2 ) due to the Chernoff bound. If we let L to be
1/ζ
a · m+log
for a sufficiently large constant a, the probability that δ(·) is a µ-balanced entry fee function is at
µ2
least 1 − ζ/2 by the union bound.

samples from ×j∈[m] Dj , we can compute in polynomial time a colHence, with O n3 (m + n)2 log m
ζ

lection of prices {Qj }j∈[m] and a entry fee function δ(·) such that the revenue of the ASPE {Qj }j∈[m] , δ(·)
(1−1/e)·C ORE (β)

η
− B2 (b, η, µ) · P OST R EV − ξ · B3 (µ) · OPT with probability 1 − ζ due to Lemma 23.
is at least
B1 (µ)
Our claim follows by fixing the value of µ to be some constant.

Theorem 18. For symmetric bidders with valuations that are XOS over independent items,
1. when V (tj ) is upper bounded by H for any j ∈ [m] and any tj , with
O

n 5 + m2 n


4

m
+
· log
δ

 2 
!
1
1
1
m2 n log n log + log
ǫ
ǫ
δ

samples from ×j∈[m] Dj , we can learn in polynomial time with probability 1 − δ a mechanism whose
revenue is at least c1 · OPT − ǫ · H for some absolute constant c1 ;
2. when the distribution of random variable V (tj ) with tj ∼ Dj is regular for all item j ∈ [m], with

m
nm 
O n5 · log
+ max{m, n}2 m2 n2 · log
δ
δ

samples from ×j∈[m] Dj , we can learn in polynomial time with probability 1 − δ a mechanism whose
revenue is at least c2 · OPT for some absolute constant c2 .

Proof of Theorem 18: Combining Lemma 24, Lemma 26 and Theorem 17, we know how to compute in
polynomial time an ASPE whose revenue is at least a1 · OPT −a2 · P OST
 R EV with probability 1 − δ/2 for
some absolute constant a1 , a2 , and we only need O n5 + m2 n4 · log m
δ samples from ×j∈[m] Dj . When the
P OST R EV
distributions are bounded, we canlearn in polynomial time an RSPM
 whose revenue is at least 144 − ξH
 2

1
with probability 1 − δ/2 using O
m2 n log n log 1ǫ + log 1δ
samples (Theorem 11). By choosing the
ξ
ratio between ξ and ǫ to be the right constant, we can show the first part of our claim. When V (tj ) is a regular
R EV
random variable for every item j, we can learn in polynomial time an RSPM whose revenue is at least P OST
33
35


samples (Theorem 12). Therefore, we can
with probability 1 − δ/2 using O max{m, n}2 m2 n2 · log nm
δ
learn a mechanism in polynomial time such that with probability 1 − δ whose revenue is at least a constant
fraction of the OPT. This proves the second part of our claim.✷

E.3

Symmetric Bidders with Subadditive Valuations

In this section, we argue that if the bidders are symmetric and m = O(n), there exists a collection of bbalanced thresholds {βj }j∈[m] for a fixed constant b, such that P OST R EV is within a constant fraction of the
benchmark. Note that this argument only applies to symmetric bidders, as b-balanced thresholds may not even
exist for asymmetric bidders.
We set η = 0 for this section and drop the subscript η when there is no confusion. We show how to
upper bound C ORE(β) with P OST R EV by choosing a particular collection of b-balanced thresholds. Let Z =
n
n
. It is not hard to see that 3Z
-balanced thresholds exist, as we can choose βj such that
max{m, n} and b = 3Z
1
Prtj ∼Dj [V (tj ) ≥ βj ] = 3Z .
P
n
-balanced thresholds, then C ORE(β) ≤ j∈[m] βj .
Lemma 27. Let {βj }j∈[m] be a collection of 3Z
Proof. As {βj }j∈[m] are

n
3Z -balanced,

Prtij ∼Dj [V (tij ) ≥ βj ] ≤
X

j∈[m]

σ∈P (D)

≤ max

σ∈P (D)

= max

σ∈P (D)

= max

σ∈P (D)

≤

X

βj

P

X X

1
2Z .

Therefore,

j∈[m] βj .

X

f (ti ) ·

i∈[n] ti ∈Ti

X X

i∈[n] ti ∈Ti

X X

X

σiS (ti ) · v(ti , S ∩ C(ti ))

S⊆[m]



f (ti ) · 

i∈[n] j∈[m]

j

≤

1
Pr [V (tj ) ≥ βj ] ≤ ,
tj ∼Dj
2

so c(β) = 0. Next, we upper bound C ORE(β) by
C ORE(β) = max

n
(n−1)·3Z



βj · 



βj · 

X

X

σiS (ti ) ·

j∈S

S⊆[m]

X

f (ti ) ·

ti ∈Ti

X X

i∈[n] ti ∈Ti

X

S:j∈S

fi (ti ) ·

X

S:j∈S



βj 



σiS (ti )


σiS (ti )

j

The first inequality is because v(ti , ·) is a subadditive function, so
X
X
v(ti , S ∩ Ci (ti )) ≤
V (tij ) ≤
j∈S∩Ci (ti )

j∈S∩Ci (ti )

βj ≤

X

βj .

j∈S

P
P
P
The last inequality is because i∈[n] ti ∈Ti fi (ti ) · S:j∈S σiS (ti ) ≤ 1 is the ex-ante probability for bidder
i to receive item j, and for any feasible interim allocation σ, the sum of all bidders’ ex-ante probabilities for
receiving item j should not exceed 1.
P
In the following Lemma, we demonstrate that j∈[m] βj is upper bounded by 9Z
n · P OST R EV .
36

Lemma 28. Let {βj }j∈[m] be a collection of

n
3Z -balanced

thresholds, P OST R EV ≥

n
9Z

·

P

j∈[m] βj .

Proof. Let us consider an RSPM where the price for selling item j to bidder i is βj . Bidder i purchases item
n
j if that is the only item she can afford and no one else can afford item j. As {βj }j∈[m] are 3Z
-balanced, the
probability that no one else can afford item j is at least


X
2
n
1 −
)≥ .
Pr [V (tkj ) ≥ βj ] ≥ (1 −
tkj ∼Dj
3Z
3
k6=i

Also, the probability that i cannot afford any item other than j is at least


X
n(m − 1)
1
1 −
Pr [V (tiℓ ) ≥ βℓ ] ≥ 1 −
≥ .
tiℓ ∼Dℓ
3Z(n − 1)
2
ℓ6=j

1
Therefore, bidder i purchases item j with probability at least 13 Prtij ∼Dj [V (tij ≥ βj )] ≥ 9Z
. Whenever this
P P βj
n P
event happens, it contributes βj to the revenue. So the total revenue is at least j i 9Z = 9Z · j βj .

Combining Theorem 17, Lemma 27 and 28, we obtain the following Theorem.

Theorem 19. For symmetric bidders with valuations that are subadditive over independent items,


36 max{n, m}
· P OST R EV .
OPT ≤ 24 +
n
n
9 max{n,m} · C ORE (β) if {βj }j∈[m] is a collection
9 max{n,m}
n
·
n
3 max{n,m} and replacing C ORE (β) with

Proof. Combining Lemma 27 and 28, we have P OST R EV ≥
n
of 3 max{n,m}
-balanced thresholds. By setting b to be
P OST R EV in Theorem 17, we have

OPT ≤
As

n
3 max{n,m}

12 +

8
1−

≤ 1/3,
OPT ≤



n
3 max{n,m}

36 max{n, m}
+
n

36 max{n, m}
24 +
n



!

· P OST R EV .

· P OST R EV .

E.3.1 Learning an Approximately Optimal Mechanism for Symmetric Subadditive Bidders
With Theorem 19, we only need to learn a mechanism that approximates the optimal revenue obtainable by
any RSPM. The next Lemma connects RSPMs with SPMs in an induced unit-demand setting.
Lemma 29. Consider n symmetric bidders whose types are drawn independently from ×m
j=1 Dj . Let Fj be
the distribution for random variable V (tj ) where tj ∼ Dj . We define an induced unit-demand setting with n
symmetric unit-demand bidders whose values for item j are drawn independently from Fj . For any collection
of prices {pij }i∈[n],j∈[m], the revenue of the RSPM with these prices in the original setting is exactly the same
as the revenue of the SPM with these prices in the induced unit-demand setting.
Proof. As in an RSPM bidders can purchase at most one item, bidders behave exactly the same as in the
induced unit-demand setting. Since the prices in the SPM and RSPM are the same, bidders purchase exactly
the same items. Hence, the revenue is the same.
37

Corollary 3. For symmetric bidders with valuations that are subadditive over independent items,
n
· OPT,
OPTU D ≥ Ω
Z

where Z = max{m, n} and OPTU D is the optimal revenue for the induced unit-demand setting.
Proof. Combine Theorem 19 and Lemma 29.

Lemma 29 implies that learning an approximately optimal RSPM is equivalent as learning an approximately optimal SPM in the induced unit-demand setting. Next, we apply our results in Section 5.1 to the
induced unit-demand setting to learn an RSMP that approximates the optimal revenue in the original setting.
In the next Theorem, we show that even though the bidders’ valuations could be complex set functions, e.g.,
submodular, XOS and subadditive, as long as m = O(n), the approximate distributions for the bidders’ values
for winning any single item provides sufficient information to learn an approximately optimal mechanism.
Theorem 20. For symmetric bidders with valuations that are subadditive over independent items, let Fj be
the distribution of V (tj ) where tj ∼ Dj . If Fj is supported on [0, H] for all j ∈ [m], given distributions F̂j
≤ ǫ for all j ∈ [m], there is a polynomial time algorithm that constructs a randomized
where F̂j − Fj
K
RSPM whose revenue under the true distribution D is at least

  


1
n
− (n + m) · ǫ · Ω
· OPT − 2ǫ · mnH .
4
max{m, n}

Proof. Let Z = max{m, n}. According to Corollary 3, OPTU D = Ω Zn · OPT. Since ||F̂j − Fj ||K ≤ ǫ
for all j ∈ [m], we can learn a randomized SPM in the induced unit-demand
setting whose revenue under the

 OPTU D
1
true distribution is at least 4 − (n + m) · ǫ ·
− 2ǫ · mnH based on Theorem 10. By Lemma 29,
8
we can construct an RSPM with the same collection of (randomized) prices and achieve revenue
   


n
1
· OPT − 2ǫ · mnH
− (n + m) · ǫ · Ω
4
Z
in the original setting.

If we are given sample access to bounded distributions, we show in the following Theorem that a polynomial number of samples suffices to learn an approximately optimal mechanism, when m = O(n).
Theorem 21. For symmetric bidders with valuations that are subadditive over independent items, let Fj be
the distribution of V (tj ) where tj ∼ Dj . If Fj is supported
on [0,H] for all j ∈ [m], there is a polynomial

n
max{m,n}

· OPT − ǫH with probability 1 − δ using
!
 2 
1
1
1
· m2 n log n log + log
O
ǫ
ǫ
δ

time algorithm that learns an RSPM whose revenue is Ω

samples.
Proof. According to Corollary 3, OPTU D = Ω



n
max{m,n}



· OPT. Due to Theorem 11,
 2 
!
1
1
1
O
· m2 n log n log + log
ǫ
ǫ
δ

samples suffices to learn in polynomial time with probability 1 − δ an SPM with revenue at least Ω(OPTU D ) −
ǫ · H for the induced unit-demand
 Lemma 29, we can construct an RSPM with the same collection
 setting. By
n
of prices and achieve revenue Ω max{m,n} · OPT − ǫH in the original setting.
38

Finally, if the distribution of the random variable V (tj ) with tj ∼ Dj is regular for all item j ∈ [m], we
prove in the next theorem that there exists a prior-independent mechanism that achieves a constant fraction
of the optimal revenue if m = O(n). Note that approximately optimal prior-independent mechanisms for
symmetric unit-demand bidders are known due to the work by Devanur et al. [21] and Roughgarden et al. [39].
Our result is obtained by combining Theorem 19 and the afore-mentioned prior independent mechanisms.
Theorem 22. For symmetric bidders with valuations that are subadditive over independent items, let Fj be the
distribution of V (tj ) where
j . If Fj is regular for all j ∈ [m], there is a prior-independent mechanism
 tj ∼ D
with revenue at least Ω

n
max{m,n}

· OPT. Moreover, the mechanism can be implemented efficiently.

Proof. The mechanism in [21] or [39] provides an approximately optimal prior-independent mechanism in
the induced unit-demand setting. Let us use M to denote this mechanism. Suppose we restrict every bidder
to purchase at most one item in the original setting and then run mechanism M . The expected revenue is
UD
the same as M
 revenue in the induced setting. Since M ’s expected
 revenue
 is Ω(OPT ) and
 ’s expected
n
n
·OPT, the mechanism we constructed has revenue Ω max{m,n}
·OPT. Since M can
OPTU D = Ω max{m,n}
be implemented efficiently for unit-demand bidders, our mechanism can also be implemented efficiently.

39

References
[1] Saeed Alaei. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers.
In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011. 1, 1, 5.1
[2] Saeed Alaei, Hu Fu, Nima Haghpanah, and Jason Hartline. The Simple Economics of Approximately
Optimal Auctions. In the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2013. 1
[3] Saeed Alaei, Hu Fu, Nima Haghpanah, Jason Hartline, and Azarakhsh Malekian. Bayesian Optimal
Auctions via Multi- to Single-agent Reduction. In the 13th ACM Conference on Electronic Commerce
(EC), 2012. 1
[4] Susan Athey and Philip Haile. Nonparametric approaches to auctions. Handbook of econometrics, 6(Part
A):3847–3965, 2007. 1
[5] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. A Simple and Approximately Optimal Mechanism for an Additive Buyer. In the 55th Annual IEEE Symposium on Foundations
of Computer Science (FOCS), 2014. 1
[6] Anand Bhalgat, Sreenivas Gollapudi, and Kamesh Munagala. Optimal auctions via the multiplicative
weight method. In ACM Conference on Electronic Commerce, EC ’13, Philadelphia, PA, USA, June
16-20, 2013, pages 73–90, 2013. 1
[7] Yang Cai and Constantinos Daskalakis. Extreme-Value Theorems for Optimal Multidimensional Pricing.
In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011. 1, 1, 5.1, 12
[8] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. An Algorithmic Characterization of
Multi-Dimensional Mechanisms. In the 44th Annual ACM Symposium on Theory of Computing (STOC),
2012. 1
[9] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. Optimal Multi-Dimensional Mechanism
Design: Reducing Revenue to Welfare Maximization. In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012. 1
[10] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. Understanding Incentives: Mechanism
Design becomes Algorithm Design. In the 54th Annual IEEE Symposium on Foundations of Computer
Science (FOCS), 2013. 1
[11] Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg. A duality based unified approach to bayesian
mechanism design. In the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016. 1, 1,
5.1, 5.2, 6, 7, B.1, B.1, B.1
[12] Yang Cai and Zhiyi Huang. Simple and Nearly Optimal Multi-Item Auctions. In the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2013. 1
[13] Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In the 49th Annual
ACM Symposium on Theory of Computing (STOC), 2017. 1, 1, 5, 5, 6, 8, 7, D, E.1, E.1, 10, 11, 17, E.2,
22, E.2, E.2
[14] Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. Algorithmic Pricing via Virtual Valuations.
In the 8th ACM Conference on Electronic Commerce (EC), 2007. 1
40

[15] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-Parameter Mechanism Design and Sequential Posted Pricing. In the 42nd ACM Symposium on Theory of Computing
(STOC), 2010. 1, 1, 5.1, 5.1, B.1, B.1, 8, B.1
[16] 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, EC ’16, Maastricht,
The Netherlands, July 24-28, 2016, pages 579–596, 2016. 1
[17] Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings
of the 46th Annual ACM Symposium on Theory of Computing, 2014. 1
[18] Constantinos Daskalakis. Multi-item auctions defying intuition? ACM SIGecom Exchanges, 14(1):41–
75, 2015. 1
[19] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Strong duality for a multiple-good
monopolist. Econometrica, 2017. 1
[20] Constantinos Daskalakis, Nikhil R. Devanur, and S. Matthew Weinberg. Revenue maximization and
ex-post budget constraints. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015, pages 433–447, 2015. 1
[21] Nikhil R. Devanur, Jason D. Hartline, Anna R. Karlin, and C. Thach Nguyen. Prior-independent multiparameter mechanism design. In Internet and Network Economics - 7th International Workshop, WINE
2011, Singapore, December 11-14, 2011. Proceedings, pages 122–133, 2011. E.3.1, E.3.1
[22] NR Devanur, Z Huang, and CA Psomas. The sample complexity of auctions with side information. In
48th Annual ACM SIGACT Symposium on Theory of Computing, 2016. 1
[23] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial
auctions with complement-free bidders. In STOC, pages 610–618, 2005. 21
[24] Shaddin Dughmi, Li Han, and Noam Nisan. Sampling and representation complexity of revenue maximization. In International Conference on Web and Internet Economics (WINE), 2014. 1, 2
[25] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages
642–669, 1956. 1, 4, B.3, E.2.1
[26] Edith Elkind. Designing and learning optimal finite support auctions. In Proceedings of the eighteenth
annual ACM-SIAM symposium on Discrete algorithms, pages 736–745. Society for Industrial and Applied Mathematics, 2007. 1
[27] Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing,
39(1):122–142, 2009. E.2.1
[28] Kira Goldner and Anna R. Karlin. A prior-independent revenue-maximizing auction for multiple additive
bidders. In Web and Internet Economics - 12th International Conference, WINE 2016, Montreal, Canada,
December 11-14, 2016, Proceedings, pages 160–173, 2016. (document), 1, 1, 3, 5.2, 5.2, C.1
[29] Yannai A. Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single-parameter
auction environments. CoRR, abs/1610.09976, 2016. 1
[30] Emmanuel Guerre, Isabelle Perrigne, and Quang Vuong. Optimal nonparametric estimation of first-price
auctions. Econometrica, 68(3):525–574, 2000. 1
41

[31] Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. In Proceedings
of the Sixteenth ACM Conference on Economics and Computation, 2015. 1
[32] Robert Kleinberg and S. Matthew Weinberg. Matroid Prophet Inequalities. In the 44th Annual ACM
Symposium on Theory of Computing (STOC), 2012. 5.1
[33] Mehryar Mohri and Andres Munoz Medina. Learning theory and algorithms for revenue optimization in
second price auctions with reserve. In ICML, pages 262–270, 2014. 1
[34] Jamie Morgenstern and Tim Roughgarden. The pseudo-dimension of near-optimal auctions. arXiv
preprint arXiv:1506.03684, 2015. 1
[35] Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 1298–1318, 2016.
(document), 1, 1, 3, 5.1, 5.2, 11, C.1
[36] Roger B. Myerson. Optimal Auction Design. Mathematics of Operations Research, 6(1):58–73, 1981. 1
[37] Harry J Paarsch and Han Hong. An introduction to the structural econometrics of auction data. MIT
Press Books, 1, 2006. 1
[38] Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the 2016 ACM Conference
on Economics and Computation, pages 1–18. ACM, 2016. 1
[39] Tim Roughgarden, Inbal Talgam-Cohen, and Qiqi Yan. Supply-limiting mechanisms. In 13th ACM
Conference on Electronic Commerce (EC), 2012. E.3.1, E.3.1
[40] Aviad Rubinstein and S. Matthew Weinberg. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In Proceedings of the Sixteenth ACM Conference on Economics and
Computation, EC ’15, Portland, OR, USA, June 15-19, 2015, pages 377–394, 2015. 1, 1
[41] Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative
random variables. Ann. Probab., 12(4):1213–1216, 11 1984. C.1
[42] Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In SODA,
2015. 1, 1, 5.2, 7

42

