Learning Multi-item Auctions with (or without) Samples

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 , 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 . 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 . On the other hand, there has been significant recent progress in efficient computation of revenue-optimal auctions . 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 , 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 .

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 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 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 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 , 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 item-independence. 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.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 .

In particular, bounding the pseudo-dimension of classes of auctions as a means to prove polynomial-sample 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 , 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 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.

We show that simple and approximately optimal mechanisms are learnable from polynomially-many samples for multi-item multi-bidder settings, whenever:

the bidder valuations are fractionally subadditive (XOS), i.e. we can accommodate additive, unit-demand, 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.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 .

In particular, our results constitute vast extensions of known results on the polynomial learnability of approximately optimal auctions in multi-item settings . 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 compute from polynomially many samples and in polynomial-time a simple mechanism whose revenue is a $\Omega\left({n\over\max\{m,n\}}\right)$-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

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 $p_{ij}$ for every bidder and item pair and, in some order over bidders $i=1,\ldots,n$, they give one opportunity to bidder $i$ to purchase one item $j$ that has not been purchased yet at price $p_{ij}$. ASPEs maintain one price $p_{j}$ for every item and, in some order over bidders $i=1,\ldots,n$, they give one opportunity to bidder $i$ to purchase any subset $S^{\prime}$ 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.

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 . 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 multi-item auctions given distributions that are close to the true distributions under some distribution distance $d(\cdot,\cdot)$. In particular, given approximate distributions $\hat{D}_{1},\ldots,\hat{D}_{n}$ over bidder valuations, we are looking to identify a mechanism $\cal M$ satisfying the following max-min style objective:

That is, we want to find a mechanism $\cal M$ whose revenue is within a constant multiplicative and a ${\rm poly}({\epsilon},m,n)$ additive error from optimum, simultaneously in all possible worlds $D_{1},\ldots,D_{n}$, where $d(D_{i},\hat{D}_{i})\leq\epsilon,\forall i$. It is not a priori clear that such a “one-fits-all” mechanism actually exists.

There are several notions of distance $d(\cdot,\cdot)$ 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 $\epsilon$ in Kolmogorov distance;Indeed, Goal (1) is achievable only for bounded distributions even in the single-item single-bidder setting. Given any bounded distribution $\hat{D}$, create $D$ by moving $\epsilon$ probability mass in $\hat{D}$ to $+\infty$. It is not hard to see that $D$ and $\hat{D}$ are within $\epsilon$ in Kolmogorov distance, but no single mechanism can satisfy the approximation guarantee for both $D$ and $\hat{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. see Definition 2. All that this requires is that the cumulative density functions of the approximating distributions over single-item values is within $\epsilon$ 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 implies that $O(\log(1/\delta)/\epsilon^{2})$ samples suffice to learn it to within $\epsilon$ in Kolmogorov distance, with probability at least $1-\delta$. 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 robustness of the revenue of the identified mechanism $\cal 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.

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 . 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,Note that any RSPM or ASPE is an SPEM.. 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 $D_{i}=\times_{j}D_{ij}$ is the true distribution over bidder $i$’s valuation and $\hat{D}_{i}=\times_{j}\hat{D}_{ij}$ is the approximating distribution, where $D_{ij}$ and $\hat{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=\times_{i}D_{i}$ and $\hat{D}=\times_{i}\hat{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 $\hat{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 $||D_{ij}-\hat{D}_{ij}||_{K}\leq\epsilon$, 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 $\hat{D}$ is only a factor of $m$, the number of items, larger than the bound $\epsilon$ 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 parameters. In particular, our sample-based result for unit-demand bidders robustifies the ex-ante relaxation of the revenue maximization problem from and its conversion to a sequential posted pricing mechanism from , and makes use of the extreme-value theorem for regular distributions from . 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 . Our sample-based results for XOS bidders show how to use samples to approximate the parameters of the RSPM and ASPE mechanisms of , 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 . This even allows us to obtain prior-independent mechanisms when the item marginals are regular.

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 $t_{i}$ as $\langle t_{ij}\rangle_{j=1}^{m}$, where $t_{ij}$ is bidder $i$’s private information about item $j$. For each $i$, $j$, we assume $t_{ij}$ is drawn independently from the distribution $D_{ij}$. Let $D_{i}=\times_{j=1}^{m}D_{ij}$ be the distribution of bidder $i$’s type and $D=\times_{i=1}^{n}D_{i}$ be the distribution of the type profile. We use $T_{ij}$ (or $T_{i},T$) and $f_{ij}$ (or $f_{i},f$) to denote the support and density function of $D_{ij}$ (or $D_{i},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 $t_{i}$, her valuation for a set of items $S$ is denoted by $v_{i}(t_{i},S)$. Throughout the paper we use OPT to denote the optimal revenue obtainable by any randomized and Bayesian truthful mechanism.

For every bidder $i$, whose type $t_{i}$ is drawn from a product distribution $F_{i}=\times_{j}F_{ij}$, her distribution, $\mathcal{V}_{i}$, over valuation functions $v_{i}(t_{i},\cdot)$ is subadditive over independent items if:

- $v_{i}(\cdot,\cdot)$ has no externalities, i.e., for each $t_{i}\in T_{i}$ and $S\subseteq[m]$, $v_{i}(t_{i},S)$ only depends on $\langle t_{ij}\rangle_{j\in S}$, formally, for any $t_{i}^{\prime}\in T_{i}$ such that $t_{ij}^{\prime}=t_{ij}$ for all $j\in S$, $v_{i}(t_{i}^{\prime},S)=v_{i}(t_{i},S)$.

- $v_{i}(\cdot,\cdot)$ is monotone, i.e., for all $t_{i}\in T_{i}$ and $U\subseteq V\subseteq[m]$, $v_{i}(t_{i},U)\leq v_{i}(t_{i},V)$.

- $v_{i}(\cdot,\cdot)$ is subadditive, i.e., for all $t_{i}\in T_{i}$ and $U$, $V\subseteq[m]$, $v_{i}(t_{i},U\cup V)\leq v_{i}(t_{i},U)+v_{i}(t_{i},V)$.

We use $V_{i}(t_{ij})$ to denote $v_{i}(t_{i},\{j\})$, as it only depends on $t_{ij}$. When $v_{i}(t_{i},\cdot)$ is XOS (or constrained additive) for all $i$ and $t_{i}\in T_{i}$, we say $\mathcal{V}_{i}$ is XOS (or constrained additive) over independent items.

We may instantiate Definition 1 to define restricted families of subadditive valuations as follows. In all cases, suppose $t=\{t_{j}\}_{j\in[m]}$ is drawn from $\times_{j}D_{j}$. To define a valuation function that is:

- unit-demand, we can take $t_{j}$ to be the value of item $j$, and set $v(t,S)=\max_{j\in S}t_{j}$.

- additive, we can take $t_{j}$ to be the value of item $j$, and set $v(t,S)=\sum_{j\in S}t_{j}$.

- constrained additive, we can take $t_{j}$ to be the value of item $j$, and set $v(t,S)=\max_{R\subseteq S,R\in\mathcal{I}}\sum_{j\in R}t_{j}$, for some downward closed set system ${\cal I}\subseteq 2^{[m]}$.

- XOS (a.k.a. fractionally subadditive), we can take $t_{j}=\{t_{j}^{(k)}\}_{k\in[K]}$ to encode all possible values associated with item $j$, and take $v(t,S)=\max_{k\in[K]}\sum_{j\in S}t_{j}^{(k)}$.

Note that constrained additive valuations contain additive and unit-demand valuations as special cases, and are contained in XOS valuations.

We consider the following three different models to access the distributions.

Sample access to bounded distributions. We assume that for any buyer $i$ and any type $t_{i}\in T_{i}$, her value $V_{i}(t_{ij})$ for any single item $j$ lies in $[0,H]$.

Sample access to regular distributions. We assume that for any buyer $i$ and any type $t_{i}\in T_{i}$, the distribution of her value $V_{i}(t_{ij})$ for any item $j$ is regular.

Direct access to approximate distributions. We assume that we have direct access to a distribution $\hat{D}=\times_{i\in[n],j\in[m]}\hat{D}_{ij}$, for example we can query the pdf, cdf of $\hat{D}$ and take samples from $\hat{D}$. Moreover, for any buyer $i$ and any type $t_{i}\in T_{i}$, the distributions of the random variable $V_{i}(t_{ij})$ when $t_{ij}$ is sampled from $\hat{D}_{ij}$ or $D_{ij}$ are within $\epsilon$ in Kolmogorov distance, and both distributions are supported on $[0,H]$.

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.

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 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.

When ${\cal X}$ is the Cartesian product of a collection of sets ${\cal X}_{1},\ldots,{\cal X}_{k}$, i.e. ${\cal X}=\times_{i}{\cal X}_{i}$, we say that a hypothesis class ${\mathcal{H}}$ as above has $(\epsilon,\delta)$-p.m. uniform convergence with sample complexity $s(\epsilon,\delta)$ if the above holds for all ${\cal D}$ that are product measures over ${\cal 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.

Let ${\mathcal{F}}_{i}$ and $\hat{{\mathcal{F}}}_{i}$ be the probability measure function for ${\mathcal{D}}_{i}$ and $\hat{{\mathcal{D}}}_{i}$ respectively. We will prove the statement using a hybrid argument. We create a sequence of product distributions $\{{\mathcal{D}}^{(j)}\}_{j\leq d}$, where ${\mathcal{D}}^{(j)}=\hat{{\mathcal{D}}}_{1}\times\cdots\times\hat{{\mathcal{D}}}_{j}\times{\mathcal{D}}_{j+1}\times\cdots\times{\mathcal{D}}_{d},$ and ${\mathcal{D}}^{(0)}={\mathcal{D}}$, ${\mathcal{D}}^{(d)}=\hat{{\mathcal{D}}}$. To prove our claim, it suffices to show that for any integer $j\in[d]$,

Next, we show how to derive this inequality.

Suppose that, for all $i\in[d]$, ${\mathcal{H}}_{i}$ has $(\epsilon,\delta)$-uniform convergence with sample complexity $s_{i}(\epsilon,\delta)$. Then ${\mathcal{H}}$ has $(\epsilon,\delta)$-p.m. uniform convergence with sample complexity $s(\epsilon,\delta)=\max_{i\in[d]}s_{i}(\epsilon/d,\delta/d)$.

Then ${\mathcal{H}}$ has $(\epsilon,\delta)$-p.m. uniform convergence with sample complexity $s(\epsilon,\delta)$.

Proof of Theorem 2: For every possible partition use Theorem 1. $\Box$

Nest, we specialize Theorem 2 to indicator functions over sets.

We use the same notation as in Theorem 2. Suppose that all functions in ${\mathcal{H}}$ map $\times_{i=1}^{d}{\mathcal{X}}_{i}$ to $\{0,1\}$, i.e. they are indicators over sets. Suppose also that the VC dimension of ${\mathcal{H}}_{T}$ (viewed as a collection of sets) is $V_{T}$. Define

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.

We establish a uniform convergence bound for single-intersecting events by combing the DKW inequality and Theorem 1.

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

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 recently showed that if the bidders’ valuations are XOS over independent items, the best SPEM achieves a constant fraction of the optimal revenue. Cai and Zhao 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. 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(\epsilon\cdot m^{2}\cdot n\cdot H)$ under the true and approximate valuation distributions (Theorem 3), where $\epsilon$ 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.

We first establish a technical lemma, which states that, for any set of items $S$, any set of prices $\{p_{j}\}_{j\in[m]}$ and entry fee $\delta$, the distribution over the set of items purchased by a constrained additive bidder whose valuation is drawn from ${\mathcal{D}}=\times_{j\in[m]}{\mathcal{D}}_{j}$ and $\hat{{\mathcal{D}}}=\times_{j\in[m]}\hat{{\mathcal{D}}}_{j}$ has total variation distance at most $2m\xi$, if $||{\mathcal{D}}_{j}-\hat{{\mathcal{D}}}_{j}||_{K}\leq\xi$ for every item $j\in[m]$. This is quite surprising. Given that, for each set of items $S^{\prime}\subseteq S$, the difference in the probability that the buyer will purchase this particular set $S^{\prime}$ under ${\mathcal{D}}$ and $\hat{{\mathcal{D}}}$ could already be as large as $\Theta(m\xi)$, and the distribution has an exponentially large support size, a trivial argument would give a bound of $2^{m}\cdot\Theta(m\xi)$. 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.

For any set $S\subseteq[m]$, any prices $\{p_{j}\}_{j\in[m]}$ and entry fee $\delta(S)$, let ${\mathcal{L}}$ and $\hat{{\mathcal{L}}}$ be the distributions over the set of items purchased from $S$ by a constrained additive bidder under prices $\{p_{j}\}_{j\in[m]}$ and entry fee $\delta$ when her type is drawn from ${\mathcal{D}}=\times_{j\in[m]}{\mathcal{D}}_{j}$ and $\hat{{\mathcal{D}}}=\times_{j\in[m]}\hat{{\mathcal{D}}}_{j}$ respectively. If $||{\mathcal{D}}_{j}-\hat{{\mathcal{D}}}_{j}||_{K}\leq\xi$ for all item $j$, $||{\mathcal{L}}-\hat{{\mathcal{L}}}||_{TV}\leq 2m\xi.$

If $U=\emptyset$, that means the utility of the favorite set for type $(0,a_{-j})$ is smaller than the entry fee $\delta(S)$. If we increase the value of $t_{j}$, 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), $(t_{j},a_{-j})\in{\mathcal{E}}_{\emptyset}$. 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 $(t_{j},a_{-j})$. If we keep increasing $t_{j}$, bidder $i$’s favorite set remains to be $V$ and she keeps accepting the entry fee and purchasing $V$. Hence, $L_{j}(a_{-j})$ can intersect with at most one event ${\mathcal{E}}_{R}$ where $R$ is non-empty.

If $U\neq\emptyset$, 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 $t_{j}$, two cases could happen: (1) $U$ remains the favorite set; (2) a different set $V$ becomes the new favorite set. In case (1), $(t_{j},a_{-j})\in{\mathcal{E}}_{U}$. 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 $(t_{j},a_{-j})$. If we keep increasing $t_{j}$, the bidder’s favorite set remains to be $V$ and she keeps accepting the entry fee and purchasing $V$. Hence, $L_{j}(a_{-j})$ can intersect at most two different events.

Suppose all bidders’ valuations are constrained additive over independent items. For any SPEM, let Rev and $\widehat{\textsc{Rev}}$ be its expected revenue under $D$ and $\hat{D}$ respectively. If $D_{ij}$ and $\hat{D}_{ij}$ are both supported on $[0,H]$, and $||D_{ij}-\hat{D}_{ij}||_{K}\leq\xi$ for all $i\in[n]$ and $j\in[m]$,

We use a hybrid argument. Consider a sequence of distributions $\{D^{(i)}\}_{i\leq n}$, where $D^{(i)}=\hat{D}_{1}\times\cdots\times\hat{D}_{i}\times D_{i+1}\times\cdots\times D_{n},$ and $D^{(0)}=D$, $D^{(n)}=\hat{D}$. We use $\textsc{Rev}^{(i)}$ to denote the expected revenue of the SPEM under $D^{(i)}$. To prove our claim, it suffices to argue that $\left|\textsc{Rev}^{(i-1)}-\textsc{Rev}^{(i)}\right|\leq 2\xi m\cdot\left(m\cdot H+\text{OPT}\right).$ We denote by $\SS_{k}$ and $\SS^{\prime}_{k}$ the random set of items that remain available after visiting the first $k$ bidders under $D^{(i-1)}$ and $D^{(i)}$. Clearly, for $k\leq i-1$, $||\SS_{k}-\SS^{\prime}_{k}||_{TV}=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, $||\SS_{i}-\SS^{\prime}_{i}||_{TV}\leq 2m\cdot\xi$. 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\cdot H$. So the difference in the expected revenue collected from bidder $i$ under $D^{(i-1)}$ and $D^{(i)}$ is at most $2\xi\cdot m^{2}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 $\SS_{i}=R$ and $\SS^{\prime}_{i}=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 $D^{(i-1)}$ and $D^{(i)}$ is at most $||\SS_{i}-\SS^{\prime}_{i}||_{TV}\cdot\text{OPT}\leq 2\xi\cdot m\text{OPT}$. Hence, the total difference between $\textsc{Rev}^{(i-1)}$ and $\textsc{Rev}^{(i)}$ is at most $2\xi m\cdot\left(mH+\text{OPT}\right)$. ∎

(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$, $D_{ij}$ and $\hat{D}_{ij}$ are supported on $[0,H]$ and $||D_{ij}-\hat{D}_{ij}||_{K}\leq\epsilon$ for some $\epsilon=O(\frac{1}{nm})$, then with only access to $\hat{D}=\times_{i,j}\hat{D}_{ij}$, our algorithm can learn an RSPM or ASPE whose revenue is at least $\frac{\text{OPT}}{c}-{\epsilon\cdot O(m^{2}nH)}$, where OPT is the optimal revenue by any BIC mechanism under $D=\times_{i,j}D_{ij}$. $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.

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 that there exists a sequential posted price mechanism (SPM see Algorithm 2 for details) that achieves at least $\frac{1}{24}$ of the optimal revenue when bidders are unit-demand. We show that under all three distribution access 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.

When all bidders have unit-demand valuations and

$D_{ij}$ is supported on $[0,H]$ for all bidder $i$ and item $j$, there exists a polynomial time algorithm that learns an SPM whose revenue is at least $\frac{\text{OPT}}{144}-\epsilon H$ with probability $1-\delta$ given $O\left(\left(\frac{1}{\epsilon}\right)^{2}\left(m^{2}n\log\frac{n}{\epsilon}+\log\frac{1}{\delta}\right)\right)$ samples from $D$; or

$D_{ij}$ is a regular distribution for all bidder $i$ and item $j$, there exists a polynomial time algorithm that learns a randomized SPM whose revenue is at least $\frac{\text{OPT}}{33}$ with probability $1-\delta$ given $O(\max\{m,n\}^{2}m^{2}n^{2}\cdot\log\frac{nm}{\delta})$ samples from $D$; or

we are only given access to $\hat{D}_{ij}$ where $||\hat{D}_{ij}-D_{ij}||_{K}\leq\epsilon$ 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 $\left(\frac{1}{4}-(n+m)\cdot\epsilon\right)\cdot\left(\frac{\text{OPT}}{8}-2\epsilon\cdot mnH\right)$If we set $\epsilon$ to be $O(\frac{1}{m+n})$, this is the max-min guarantee we want to achieve..

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

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 , and use its optimum as a proxy for OPT. Next, we consider a similar convex program based on $\hat{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. 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 we are given $\hat{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 to truncate the distributions without hurting the revenue by much. See Theorem 12 in Appendix B.3 for further details.

2 Additive Valuations: Polynomial-Time Learning

In this section, we consider bidders with additive valuations, again sharpening our results to show polynomial-time learnability. It is known that the better of the following two mechanisms achieves at least $\frac{1}{8}$ of the optimal revenue when all bidders have additive valuations :

Selling Separately: the mechanism sells each item separately using Myerson’s optimal auction.

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 .

Let SRev be the optimal revenue for selling the items separately and BRev be the expected entry fee collected from the VCG with entry fee mechanism. Then $\text{OPT}\leq 6\cdot\textsc{SRev}+2\cdot\textsc{BRev}.$

Goldner and Karlin showed that one sample suffices to learn a mechanism that achieves a constant fraction of the optimal revenue when $D_{ij}$ is regular for all $i\in[n]$ and $j\in[m]$. We show how to learn an approximately optimal mechanism in the other two models.

When the bidders have additive valuations and

$D_{ij}$ 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 $\frac{\text{OPT}}{32}-{\epsilon}\cdot H$ with probability $1-\delta$ given $O\left(\left(\frac{m}{\epsilon}\right)^{2}\cdot\left(n\log n\log\frac{1}{\epsilon}+\log\frac{1}{\delta}\right)\right)$ samples from $D$; or

we are only given access to distributions $\hat{D}_{ij}$ where $||\hat{D}_{ij}-D_{ij}||_{K}\leq\epsilon$ 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 $\frac{\text{OPT}}{266}-96\epsilon\cdot mnH$ when $\epsilon\leq\frac{1}{16\max\{m,n\}}$.

Sample Access to Bounded Distributions: Goldner and Karlin’s proof can be directly applied to the bounded distributions to show a single sample suffices to learn a mechanism whose expected revenue approximates the BRev. Then as SRev is the revenue of $m$ separate single-item auctions, we can use the result in 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 SRev. For BRev, 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 for a bidder to accept an entry fee under $\hat{D}$ and $D$ is close (Lemma 3). So we can essentially use the median of $\sum_{j\in[m]}(t_{ij}-\max_{k\neq i}b_{kj})^{+}$ with $t_{i}\sim\hat{D}_{i}$ as the entry fee. See Theorem 14 in Appendix C.2 for further details.

XOS Valuations

In this section we go beyond constained additive valuations to show learnability of approximately revenue-optimal 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 .

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 $\{p_{j}\}_{j\in[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.

There exists a collection of prices $\{p^{*}_{j}\}_{j\in[m]}$, such that if we set the entry fee function $\delta^{*}_{i}(S)$ to be the median of bidder $i$’s utility for set $S$, either the ASPE$(p^{*},\delta^{*})$ or the best RSPM achieves at least a constant fraction of the optimal revenue when bidders’ valuations are XOS over independent items. More formally, let $u^{*}_{i}(t_{i},S)=\max_{S^{*}\subseteq S}v_{i}(t_{i},S^{*})-\sum_{j\in S^{*}}p^{*}_{j}$ be bidder $i$’s utility for the set of items $S$ when her type is $t_{i}$. We define $\delta^{*}_{i}(S)$ to be the median of the random variable $u^{*}_{i}(t_{i},S)$ (with $t_{i}\sim D_{i}$) for any set $S\subseteq[m]$. Moreover, the price $p^{*}_{j}$ for any item $j$ is no larger than $2G$, where $G=\max_{i,j}G_{ij}$ and $G_{ij}:=\sup_{x}\left\{\Pr_{t_{ij}\sim D_{ij}}\left[V_{i}(t_{ij})\geq x\right]\geq\frac{1}{5\max\{m,n\}}\right\}$.

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^{\prime}_{j}\}_{j\in[m]}$ sufficiently close to $\{p^{*}_{j}\}_{j\in[m]}$ and entry fee $\delta^{\prime}_{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.

For any $\epsilon>0$ and $\mu\in[0,\frac{1}{4}]$, let $\{p^{\prime}_{j}\}_{j\in[m]}$ be a collection of prices such that $|p^{\prime}_{j}-p^{*}_{j}|\leq\epsilon$ for all $j\in[m]$, where $\{p^{*}_{j}\}_{j\in[m]}$ is the collection of prices in Theorem 8. Let $\delta^{\prime}_{i}(S)$ be bidder $i$’s entry fee function such that $\Pr_{t_{i}\sim D_{i}}\left[u^{\prime}_{i}(t_{i},S)\geq\delta^{\prime}_{i}(S)\right]\in[1/2-\mu,1/2+\mu]$ for any set $S\subseteq[m]$, where $u^{\prime}_{i}(t_{i},S)=\max_{S*\subseteq S}v_{i}(t_{i},S^{*})-\sum_{j\in S^{*}}p^{\prime}_{j}$. Then, either the ASPE$(p^{\prime},\delta^{\prime})$ or the best RSPM achieves revenue at least $\frac{\text{OPT}}{{\mathcal{C}}_{1}(\mu)}-{\mathcal{C}}_{2}(\mu)\cdot(m+n)\cdot\epsilon$ when bidders’ valuations are XOS over independent items. Both ${\mathcal{C}}_{1}(\cdot)$ and ${\mathcal{C}}_{2}(\cdot)$ are monotonically increasing functions that only depend on $\mu$.

We say a collection of prices $\{p_{j}\}_{j\in[m]}$ is in the $B$-bounded $\epsilon$-net if $p_{j}$ is a multiple of $\epsilon$ and no larger than $B$ for any item $j$. For any collection of prices $\{p_{j}\}_{j\in[m]}$, we say the entry fee functions are $\mu$-balanced if for every bidder $i$ and every set $S\subseteq[m]$, her entry fee $\delta_{i}(S)$ satisfies $\Pr_{t_{i}\sim D_{i}}[u_{i}(t_{i},S)\geq\delta_{i}(S)]\in[1/2-\mu,1/2+\mu]$, where $u_{i}(t_{i},S)=\max_{S*\subseteq S}v_{i}(t_{i},S^{*})-\sum_{j\in S^{*}}p_{j}$.

For bidders with valuations that are XOS over independent items and any $\epsilon>0$, there exists a collection of prices $\{p_{j}\}_{j\in[m]}$ in the $2G$-bounded $\epsilon$-net such that for any $\mu$-balanced entry fee functions $\{\delta_{i}(\cdot)\}_{i\in[n]}$ with $\mu\in[0,\frac{1}{4}]$, either the ASPE$(p,\delta)$ or the best RSPM achieves revenue at least $\frac{\text{OPT}}{{\mathcal{C}}_{1}(\mu)}-{\mathcal{C}}_{2}(\mu)\cdot(m+n)\cdot\epsilon$.

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 $\{p_{j}\}_{j\in[m]}$ in the $\epsilon$-net. More specifically, to decide $\delta_{i}(S)$ we compute the utility of bidder $i$ for set $S$ under $\{p_{j}\}_{j\in[m]}$ over all the samples and take the empirical median among all these utilities to be $\delta_{i}(S)$. With a polynomial number of samples, we can guarantee that for any $\{p_{j}\}_{j\in[m]}$ in the $\epsilon$-net the computed entry fee functions $\{\delta_{i}(\cdot)\}_{i\in[n]}$ are $\mu$-balanced. Now, we have created an ASPE for every $\{p_{j}\}_{j\in[m]}$ in the $\epsilon$-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.

When all bidders’ valuations are XOS over independent items and

the random variable $V_{i}(t_{ij})$ 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-\delta$ the better of the two mechanisms has revenue at least $\frac{\text{OPT}}{c_{1}}-\xi\cdot H$ for some absolute constant $c_{1}>1$ given $O\left((\frac{mn}{\xi})^{2}\cdot(m\cdot\log\frac{m+n}{\xi}+\log\frac{1}{\delta})\right)$ samples from $D$;

the random variable $V_{i}(t_{ij})$ is regular for each bidder $i$ and item $j$, we can learn an RSPM and an ASPE such that with probability at least $1-\delta$ the better of the two mechanisms has revenue at least $\frac{\text{OPT}}{c_{2}}$ for some absolute constant $c_{2}>1$ given $O\left(\max\{m,n\}^{2}m^{2}n^{2}\left(m\log({m+n})+\log\frac{1}{\delta}\right)\right)$ 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.

Symmetric Bidders

In this section, we consider symmetric bidders ($D_{i}=D_{i^{\prime}}$ for all $i$ and $i^{\prime}\in[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 estimates all the parameters needed to run the RSPM and ASPE used in . 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 revenue is at most $O\left(\frac{n}{\max\{m,n\}}\right)$ 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 $V_{i}(t_{ij})$ is regular for every bidder $i$ and item $j$, we can design a prior-independent mechanism that achieves a constant fraction of the optimal revenue. See Appendix E.3 for details.

Appendix

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.

Appendix B Missing Details from Section 5.1

We first consider the model where we only have access to an approximate distribution $\hat{D}$. The following definition is crucial for proving our result.

where $F^{-1}(1-p)=\sup\{x\in R:\Pr_{v\sim{\mathcal{D}}}[v\geq x]\geq p\}$.

Let ${\varphi}_{ij}(\cdot)$ and $\hat{\varphi}_{ij}(\cdot)$ be the ironed virtual value function for distribution $D_{ij}$ and $\hat{D}_{ij}$ respectively, then for any $q\in$, ${R}_{D_{ij}}(q)=\int_{{F}^{-1}_{ij}(1-q)}^{H}{\varphi}(x)dF(x)$ and $R_{\hat{D}_{ij}}(q)=\int_{\hat{F}^{-1}_{ij}(1-q)}^{H}\hat{\varphi}(x)dF(x)$. Since the ironed virtual value function is monotonically non-decreasing, ${R}_{D_{ij}}(\cdot)$ and $R_{\hat{D}_{ij}}(\cdot)$ are concave functions.

We provide an upper bound of the optimal revenue using $R_{D_{ij}}$ 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 , the optimal revenue is upper bounded by the optimal revenue in the single-dimensional copies setting defined in . We use the same technique. We construct $nm$ agents, where agent $(i,j)$ has value $V_{i}(t_{ij})$ of being served with $t_{ij}\sim D_{ij}$, 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 servedThis is exactly the copies setting used in , if every bidder $i$ is unit-demand and has value $V_{i}(t_{ij})$ with type $t_{i}$. 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.. Notice that this is a single-dimensional setting, as each agent’s type is specified by a single number. Let $\textsc{OPT}^{\textsc{Copies-UD}}$ be the optimal BIC revenue in this copies setting.

For unit-demand bidders, there exists a collection of non-negative numbers $\{q_{ij}\}_{i\in[n],j\in[m]}$ satisfying $\sum_{i}q_{ij}\leq 1$ for all $j\in[m]$ and $\sum_{j}q_{ij}\leq 1$ for all $i\in[n]$, such that the optimal revenue

As shown in , $\text{OPT}\leq 4\textsc{OPT}^{\textsc{Copies-UD}}$. Let $q_{ij}$ be the ex-ante probability that agent $(i,j)$ is served in the optimal mechanism for the copies setting. Chawla et al. showed that $\textsc{OPT}^{\textsc{Copies-UD}}\leq\sum_{i,j}R_{D_{ij}}(q_{ij})$. 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 $\frac{1}{8}$ of the optimal revenue.

The optimal solution of convex program in Figure 1 is at least $\frac{\text{OPT}}{8}$.

Let $\{q^{\prime}_{ij}\}$ be the collection of nonnegative numbers in Lemma 7. Clearly, $\left\{\frac{q_{ij}^{\prime}}{2}\right\}$ is a set of feasible solution for the convex program. Since $R_{D_{ij}}(\cdot)$ is concave, $R_{D_{ij}}\left(\frac{q_{ij}^{\prime}}{2}\right)\geq\frac{R_{D_{ij}}(q^{\prime}_{ij})}{2}+\frac{R_{D_{ij}}(0)}{2}=\frac{R_{D_{ij}}(q^{\prime}_{ij})}{2}$. Therefore,

If we know all $F_{ij}$ exactly, we can solve the convex program (Figure 1) and use the optimal solution to construct an SPM via an approach provided in . The constructed sequential posted mechanism has revenue at least $\frac{1}{4}$ of the optimal value of the convex program, which is at least $\frac{\text{OPT}}{32}$. Next, we show that with only access to $\hat{F}_{ij}$, we can essentially carry out the same approach. Consider a different convex program (Figure 2).

Not that if the support size for all $\hat{D}_{ij}$ is upper bounded by some finite number $s$, the convex program above can be rewritten as a linear program with size ${\rm poly}(n,m,s)$. In the following Lemma, we prove that the optimal values of the two convex programs above are close.

Let $\{{q}^{*}_{ij}\}_{i\in[n],j\in[m]}$ and $\{\hat{q}_{ij}\}_{i\in[n],j\in[m]}$ be the optimal solution of the convex program in Figure 1 and 2 respectively.

We first fix some notations. For any bidder $i$ and item $j$, let \underaccent{\bar}{q}^{*}_{ij},\bar{q}^{*}_{ij} and $x_{ij}$ $\in$ be the numbers satisfy that x_{ij}\cdot\underaccent{\bar}{q}^{*}_{ij}\cdot{F_{ij}}^{-1}(1-\underaccent{\bar}{q}^{*}_{ij})+(1-x_{ij})\cdot\bar{q}^{*}_{ij}\cdot{F_{ij}}^{-1}(1-\bar{q}^{*}_{ij})=R_{D_{ij}}(q^{*}_{ij}) and x_{ij}\cdot\underaccent{\bar}{q}^{*}_{ij}+(1-x_{ij})\cdot\bar{q}^{*}_{ij}=q^{*}_{ij}. Let \underaccent{\bar}{p}_{ij}={F_{ij}}^{-1}(1-\underaccent{\bar}{q}^{*}_{ij}), $\bar{p}_{ij}={F_{ij}}^{-1}(1-\bar{q}^{*}_{ij})$, and q^{\prime}_{ij}=x_{ij}\cdot\left(1-\hat{F}_{ij}(\underaccent{\bar}{p}_{ij})\right)+(1-x_{ij})\cdot\left(1-\hat{F}_{ij}(\bar{p}_{ij})\right). By the definition of $R_{\hat{D}_{ij}}(\cdot)$,

Since $||\hat{D}_{ij}-D_{ij}||_{K}\leq\epsilon$, \hat{F}_{ij}(\underaccent{\bar}{p}_{ij})\in[1-\underaccent{\bar}{q}^{*}_{ij}-\epsilon,1-\underaccent{\bar}{q}^{*}_{ij}+\epsilon] and $\hat{F}_{ij}(\bar{p}_{ij})\in[1-\bar{q}^{*}_{ij}-\epsilon,1-\bar{q}^{*}_{ij}+\epsilon]$. Hence, the RHS of inequality (4) is greater than $R_{D_{ij}}(q_{ij}^{*})-\epsilon\cdot H$. Therefore, $R_{\hat{D}_{ij}}(q_{ij}^{\prime})\geq R_{D_{ij}}(q_{ij}^{*})-\epsilon\cdot H$.

Next, we argue that $\{q^{\prime}_{ij}\}_{i\in[n],j\in[m]}$ is a feasible solution for the convex program in Figure 2. Since 1-\hat{F}_{ij}(\underaccent{\bar}{p}_{ij})\leq\underaccent{\bar}{q}^{*}_{ij}+\epsilon and $1-\hat{F}_{ij}(\bar{p}_{ij})\leq\bar{q}^{*}_{ij}+\epsilon$, $q^{\prime}_{ij}\leq q^{*}_{ij}+\epsilon$. Thus, $\sum_{i}q^{\prime}_{ij}\leq\sum_{i}q^{*}_{ij}+n\cdot\epsilon\leq\frac{1}{2}+n\cdot\epsilon$ for all $j\in[m]$. Similarly, we can prove $\sum_{j}q^{\prime}_{ij}\leq\frac{1}{2}+m\cdot\epsilon$ for all $i\in[n]$. As $\{\hat{q}_{ij}\}_{i\in[n],j\in[m]}$ is the optimal solution for the second convex program, $\sum_{i,j}R_{\hat{D}_{ij}}(\hat{q}_{ij})\geq\sum_{i,j}R_{\hat{D}_{ij}}({q}^{\prime}_{ij})\geq\sum_{i,j}{R}_{D_{ij}}({q}^{*}_{ij})-\epsilon\cdot mnH$. ∎

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.

For any distribution ${\mathcal{D}}=\times_{i\in[n],j\in[m]}{\mathcal{D}}_{ij}$, given a collection of independent random variables $\{p_{ij}\}_{i\in[n],j\in[m]}$ such that

we can construct in polynomial time a randomized SPM such that the revenue under ${\mathcal{D}}$ is at least

Given any feasible solution $\{{q}_{ij}\}_{i\in[n],j\in[m]}$ of the convex program in Figure 2, we can construct a (randomized) SPM in polynomial time such that its revenue under $D$ is at least $\left(\frac{1}{4}-(n+m)\cdot\epsilon\right)\cdot\left(\sum_{i,j}R_{\hat{D}_{ij}}(q_{ij})-\epsilon\cdot nmH\right)$.

We first fix some notations. For any bidder $i$ and item $j$, let \underaccent{\bar}{q}_{ij},\bar{q}_{ij} and $x_{ij}$ $\in$ be the numbers satisfying x_{ij}\cdot\underaccent{\bar}{q}_{ij}\cdot\hat{F}_{ij}^{-1}(1-\underaccent{\bar}{q}_{ij})+(1-x_{ij})\cdot\bar{q}_{ij}\cdot\hat{F}_{ij}^{-1}(1-\bar{q}_{ij})=R_{\hat{D}_{ij}}(q_{ij}) and x_{ij}\cdot\underaccent{\bar}{q}_{ij}+(1-x_{ij})\cdot\bar{q}_{ij}=q_{ij}. We use $p_{ij}$ to denote a random variable that is \underaccent{\bar}{p}_{ij}=\hat{F}_{ij}^{-1}(1-\underaccent{\bar}{q}_{ij}) with probability $x_{ij}$ and $\bar{p}_{ij}=\hat{F}_{ij}^{-1}(1-\bar{q}_{ij})$ with probability $1-x_{ij}$.

Next, we construct a randomized SPM based on $\{p_{ij}\}_{i\in[n],j\in[m]}$ according to Lemma 10. Note that

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

For unit-demand bidders, given distributions $\hat{D}_{ij}$ where $\left|\left|\hat{D}_{ij}-D_{ij}\right|\right|_{K}\leq\epsilon$ for all $i\in[n]$ and $j\in[m]$, there is a polynomial time algorithm that constructs a randomized SPM whose revenue under $D$ is at least $\left(\frac{1}{4}-(n+m)\cdot\epsilon\right)\cdot\left(\frac{\text{OPT}}{8}-2\epsilon\cdot mnH\right)$.