Learning Within an Instance for Designing High-Revenue Combinatorial Auctions

1 Introduction

In a (limited-supply) combinatorial auction, a seller has m indivisible items to allocate among a set S of n bidders. Combinatorial auctions have various real-world applications. Two examples include auctions for allocating licenses for bands of the electromagnetic spectrum and sourcing auctions for supply chain management. The design of truthful, high-revenue combinatorial auctions is a central problem in mechanism design. A comprehensive account of combinatorial auctions may be found in Cramton et al. [2006].

A common strategy for designing truthful, high-revenue auctions when there is an unlimited supply of each good has been to use a random-sampling mechanism. A randomsampling mechanism splits the bidders into two groups, and applies the optimal auction for each group to the other group (thereby achieving truthfulness, since the auction run on any bidder's group is independent of her reported valuation). In unlimited-supply settings, random-sampling mechanisms satisfy strong guarantees [Goldberg et al., 2001; Balcan et al., 2005; Alaei et al., 2009].

However, until now, there has been no unified, generalpurpose method of adapting the random-sampling approach to analyze the limited-supply setting. Limited supply poses additional significant technical challenges, since allocations of items to bidders must be feasible. For example, randomsampling with any mechanism class that allows bidders to purchase according to their demand functions would violate supply constraints. Most adaptations of random-sampling to limited supply deal with feasibility issues in complicated ways, for example, by constructing intricate revenue benchmarks to limit the number of buyers who can make a purchase [Balcan et al., 2007], or by placing combinatorial constraints on the environment [Devanur and Hartline, 2009; Devanur et al., 2015].

In this paper we circumvent these issues by applying auction formats that generalize the classical Vickrey-ClarkeGroves (VCG) auction [Vickrey, 1961; Clarke, 1971; Groves, 1973] to sell all m items to a random group of participatory bidders. These auctions prescribe feasible allocations and payments (and are incentive compatible). Several parameterized generalizations of the VCG auction have been studied with the aim of increasing revenue by introducing weights to favor certain bidders or allocations. Examples include affine-maximizer auctions (AMAs) [Roberts, 1979], virtualvaluations combinatorial auctions (VVCAs) [Likhodedov and Sandholm, 2004; Likhodedov and Sandholm, 2005; Sandholm and Likhodedov, 2015], λ-auctions [Jehiel et al., 2007], mixed-bundling auctions with reserve prices [Tang and Sandholm, 2012], and mixed-bundling auctions [Jehiel et al., 2007]. However, little is known when it comes to formal approximation guarantees for these auction classes.

A direct adaptation of vanilla random sampling can do poorly when the auction class is rich. Suppose we randomly partition the set of bidders into two groups S1 and S2 , and apply the optimal mechanism for S1 to S2 . Consider learning a second-price auction with a reserve in the case of selling a single item. Suppose there is one bidder who values the item at 10 and the remaining buyers' values are in [0, 9]. The high bidder is in S1 with probability 1/2. So with probability 1/2, the optimal reserve price for S1 is 10, and the revenue obtained from S2 is 0. More generally, since we study large parameterized auction classes, the optimal auction for S1 potentially overfits to a small number of bidders. Another adaption along the lines of vanilla random sampling to prevent overfitting would be to partition the set S of bidders into N groups, use the first N - 1 groups to learn a high-revenue auction, and then apply that auction to the Nth group. The issue with this approach is that generalization guarantees would require N large. Thus the final mechanism only sells items to a tiny fraction of bidders, incurring a large revenue loss.

Our main learning-within-an-instance (LWI) mechanism alleviates these issues by randomly drawing a set of participatory bidders Spar, and then sampling several proportionallysized learning groups from Slrn := S \ Spar to learn an auction that is close-to-optimal in expectation for a random learning group. Our approach is a form of automated mechanism design [Conitzer and Sandholm, 2002; Sandholm, 2003].

1.1 Setup and the MainMechanism

In our model, the seller has m indivisible items to allocate among a set S of n bidders/buyers. Each buyer is described by her valuation function vi : 2{1,...,m} →R≥0 over bundles of the m items. (We implicitly assume that each buyer's value for getting the empty bundle is zero.) We do not assume that b ⊆ b′ implies v(b) ≤ v(b′ ) (a common assumption called free disposal). For an allocation α, vi(α) denotes the value buyer i assigns to the bundle she receives according to α (we assume that buyers valuations are independent of what other buyers' receive). For an allocation α, W(α) = ∑ni=1 vi(α) denotes the welfare of α, and W-i(α) = ∑j̸=i vj(α) denotes the welfare of α when bidder i is absent. For a set of bidders S, W(S) = maxαW(α) denotes the welfare of an efficient allocation, that is, an allocation that maximizes welfare. The VCG auction uses the efficient allocation α∗ , and bidder i pays maxαW-i(α) -W-i(α∗ ). The auctions we study in this paper are parameterized generalizations of the VCG auction that modify the welfare function by applying boosts to specific allocations with the aim of increasing revenue. For an auction M and a set of bidders S′ ⊆ S, we denote by RevM(S′ ) the sum of the payments made by bidders in S′ when the seller runs M among bidders in S′ . We write S′ ∼p S to denote a subset S′ being sampled from S by including each bidder in S′ independently with probability p. We now present the main mechanism of this paper.

Learning-within-an-instance mechanism (LWI) Parameters: p, q,N

1. Draw a group of participatory buyers Spar ∼p S.
2. Draw learning groups of buyers S1, . . . , SN ∼q S \ Spar.
3. Find the mechanism ̂ M ∈ M that maximizes empirical revenue 1N ∑Nt=1 RevM(St) over the learning groups.
4. Apply mechanism ̂ M to Spar.

When M is a class of incentive-compatible mechanisms, LWI is incentive-compatible since ̂ M does not depend on the valuations of the bidders in Spar.

1.2 Summary of the Contributions of this Paper

In section 2 we provide the main guarantees satisfied by our LWI framework. The guarantees are derived using learningtheoretic techniques. Informally, they provide (high probability) lower bounds on the performance of LWI of the form Rev̂ M (Spar) ≥ W(S)(LM - εM(N, δ)) - τM, where LM measures the revenue loss incurred by allocating items only to participatory bidders, εM is a standard learning-theoretic error term that depends on the intrinsic complexity of M, and τM is an additional error term we coin partition discrepancy. Partition discrepancy is also a measure of the intrinsic complexity of M, but is simultaneously a measure of the level of uniformity in the set S of bidders. We provide examples and a general bound to illustrate properties of partition discrepancy.

In section 3 we introduce a new class of auctions called bundling-boosted auctions. These auctions are parameterized in a way that does not depend on the number of bidders who participate in the auction (unlike most previous generalizations of the VCG auction). We prove bounds on the intrinsic complexity of bundling-boosted auctions (and a few other natural subclasses of auctions) that have no dependence on the number of bidders. We show that under certain conditions LWI on the class of bundling-boosted auctions yields an (O(p) - ε)-approximation with high probability.

In section 4 we show how our learning-within-an-instance mechanism can be implemented in a sample and computationally efficient manner for bundling-VCG auctions and sparse bundling-boosted auctions by leveraging practically efficient routines for solving winner determination.

In section 5 we show how to use structural revenue maximization to decide what auction class to use with LWI when there is a constraint on the number of learning groups.

1.3 Additional Related Research

There have been various alternate approaches to revenue maximization for limited supply. Balcan, Blum, and Mansour [2008] obtain a O(2√logmlog logm)-approximation for bidders with subadditive valuations, which was improved to a O(log2 m)-approximation by Chakraborty, Huang, and Khanna [2013]. Both these works studied item-pricing mechanisms. Sandholm and Likhodedov [2005; 2015] obtain a (2 + 2 log(h/l))-approximation when bidders have additive valuations, where l and h are lower and upper bounds on the valuation of any bidder for any item. Our results significantly improve upon these existing results in various situations. For example, for W(S) sufficiently large, we prove that our LWI mechanism run on the class of bundling-boosted auctions yields an (O(p) - ε)-approximation. In addition, previous approximations are on expected revenue, while we give the much stronger guarantee of high-probability revenue approximation. Furthermore, our results do not require restrictions on valuation functions, giving them very broad applicability.

A recent line of work studies learning revenue-maximizing auctions for limited supply across instances [Mohri and Medina, 2014; Morgenstern and Roughgarden, 2015; Balcan et al., 2018]. These works laid down the framework for understanding learning-theoretic quantities related to auctions in order to prove generalization guarantees. Our paper studies the significantly tougher and unsolved problem of learning from a single instance for limited supply. We extend the techniques of Balcan et al. [2005] (that can be viewed as learning within an instance for unlimited supply) and show that learning theory combined with the power of parameterized auctions provides a way to meaningfully learn within an instance in the more challenging setting of limited supply.

2 Main Guarantees of our Framework

In this section we present the main guarantees satisfied by LWI in terms of structural properties of the auction class and the set of bidders. Our guarantees are in terms of partition discrepancy, delineability, and the following quantity that controls the revenue loss incurred by selling only to bidders in Spar. For S′ ⊆ S, let OPTM(S′ ) = supM∈MRevM(S′ ) and let LM(S′ ) = OPTM(S′ )/W(S).

For a given participatory set of bidders Spar, partition discrepancy measures the worst-case deviation in an auction class between the revenue on Spar versus the expected revenue on a set of bidders sampled from S\Spar. For 0 < q < 1 and Spar ⊂ S, partition discrepancy is defined as

Partition discrepancy is a measure of both the intrinsic complexity of the classMand the amount of uniformity in the set S of bidders. We now present general guarantees for LWI in terms of partition discrepancy (the full derivations are in the appendix). The guarantees follow from uniform convergence results, and depend on the expected Rademacher complexity RM(N; S \ Spar) of M with respect to S \ Spar and the pseudodimension Pdim(M) of M. We provide definitions and some standard results from learning theory that we use in our proofs in the appendix. ̂ M denotes the empirical-revenuemaximizing mechanism used by LWI.

Theorem 1. Let Spar denote the participatory set of bidders chosen by a run of LWI. Then, with probability ≥ 1 - 2δ over the draw of S1, . . . , SN ∼q S \ Spar, (a) Rev̂ M (Spar) ≥ W(S)(LM(Spar) - 4RM(N; S \ Spar) - √2 ln(1/δ)/N ) - 2τM(q, Spar) and (b) Rev̂ M (Spar) ≥ W(S)(LM(Spar) - 240√Pdim(M)/N - √2 ln(1/δ)/N ) - 2τM(q, Spar ).

Proof sketch. Uniform convergence results relate the empirical revenue of ̂ M on the learning groups to the optimal expected revenue on a random learning group. Partition discrepancy ties both these quantities to revenue on Spar.

If M has finite pseudodimension (this is not necessarily the case if we only have a bound on Rademacher complexity), we can give an equivalent sample-complexity version of the guarantee. Let N(ε, δ, Pdim(M)) = 4802 Pdim(M) ln ( 1δ ) /ε2 .

Corollary 1. Let Spar denote the participatory set of bidders chosen by a run of LWI with parameters p, q,N, where N ≥ N(ε, δ, Pdim(M)). Then, with probability ≥ 1 - 2δ

To understand the pseudodimension of various mechanism classes, Balcan et al. [2018] introduced the notion of delineability. A class of mechanisms M is (d, h)-delineable if (1) every M ∈ M can be parameterized by a vector θ ∈ Rd , and (2) for every set S of bidder valuations, there are at most h hyperplanes partitioning Rd such that RevS(θ) := Revθ(S) is linear in θ over each connected component of Rd determined by the hyperplanes. The way we have stated delineability requires h to be independent of the number of bidders in S. We include an analysis of the case where h is allowed to be a function of n in the appendix. The following example illustrates delineability in a simple case. Balcan et al. [2018] provide more examples and a more detailed discussion.

Example 1 (Second-price auctions with a reserve price). The class of second-price auctions with reserve prices for selling a single item is (1, 2)-delineable. Indeed, if v1 and v2 are highest and second-highest values for the item, respectively, then for r < v2 the revenue of a second-price auction with reserve r is v2, for v2 ≤ r ≤ v1 it is r, and for r > v1 it is 0.

Rademacher complexity, pseudodimension, and delineability are connected through the following relations: RM(N; Slrn) ≤ 60W(S)√Pdim(M)/N [Dudley, 1987] and if M is (d, h)-delineable, Pdim(M) ≤ 9d ln(4dh) [Balcan et al., 2018].

We present our main guarantee in terms of delineability:

Theorem 2. Suppose M is (d, h)-delineable. Let Spar denote the participatory set of bidders chosen by a run of LWI with parameters p, q,N, where N ≥ N(ε, δ, 9d ln(4dh)). Then, with probability ≥ 1 - 2δ over the draw of S1, . . . , SN ∼q S \ Spar, Rev̂ M (Spar) ≥ W (S)(LM(Spar ) - ε) - 2τM(q, Spar ).

We provide analogous guarantees for mechanism classes that satisfy a version of delineability that is dependent on the number of bidders in the appendix.

2.1 Partition Discrepancy

In this section we develop a further understanding of partition discrepancy. We first provide two examples illustrating structural properties of partition discrepancy. We then provide a general-purpose high-probability bound on partition discrepancy based on pseudodimension of the mechanism class.

The first example relates the failure of vanilla random sampling to large partition discrepancy using the scenario given in the introduction. We show how LWI alleviates that issue.

Example 2 (LWI versus random sampling). Consider the example from the introduction where a single item is for sale and M is the class of second-price auctions with reserve. There is one bidder with value 10, and all remaining bidders' values are in [0, 9]. Suppose LWI is run with parameters p = 1/2, q = 1 (which corresponds to vanilla random sampling). Then, for any participatory set Spar, τM(1, Spar) = 10 = W(S), achieved by setting a reserve price of 10. If instead LWI was run with parameters p = q < 1, the high bidder is in S \ Spar with probability 1 - p, and in this case

τM(q, Spar) = 10q If, for example, p = q = 1/20, this is a small additive loss in the overall revenue guarantee.

The next example involves replica economies, where the set of bidders is composed of several copies of a ground set of bidders. Replica economies have been studied extensively in economics (and recently from an algorithmic viewpoint) in the context of convergence to equilibria [Debreu and Scarf, 1963; Aumann, 1964; Barman and Echenique, 2020].

Example 3 (Replica economies). Suppose S0 = {v1, v2, v3}, and S consists of n0 replicas of S0. Let M be a populationsize-independent auction class. We show in the appendix that if n0 is sufficiently large, τM(1, Spar) = 0 with high probability over the draw of Spar ∼1/2 S.

We now present a general bound on partition discrepancy in terms of the learning-theoretic complexity of Mwhen LWI is run with parameters p = 1/3 and q = 1/2. For each bidder i, let ˜ vi = max|S′ |≥n/3-5√n supM∈M |RevM(S′ ∪ {i}) - RevM(S′ )| and let ˜ v = (˜ v1, . . . , ˜ vn) ∈ Rn . These terms measure how sensitive the mechanism class is to the addition of a single bidder to an already large set of bidders. In the following results on partition discrepancy, we condition on the (probability ≥ 1-e-25 ) event that |Spar| ≥ n/3-5√n. Theorem 3. With probability ≥ 1 - δ over the draw of Spar ∼1/3 S, τM(1/2, Spar) ≤ ||˜ v||2√2nPdim(M) ln 4e2 Pdim(M)W(S) δ .

Proof sketch. We bound τM for a single mechanism M using concentration bounds. We then apply a union bound over a learning-theoretic cover of M. Classical learning-theory results bound the cover size in terms of Pdim(M).

Combined with Corollary 1, we have:

When W(S) is sufficiently large, we can condense the bound on partition discrepancy to contribute at most an ε loss. Corollary 2. Run LWI with parameters N, p = 1/3, q = 1/2, where N ≥ N(ε, δ, Pdim(M)). If W(S)2 - 8n||˜ v||22 Pdim(M) ε2 ln(W(S)) ≥ 8n||˜ v||22 Pdim(M) ε2 ln ( 4e2 Pdim(M) δ ), Rev̂ M (Spar) ≥ W(S)(LM(Spar) - 2ε) with probability ≥ 1 - 3δ.

Remark. We emphasize that small partition discrepancy (for example, stipulating that τM is a fixed constant) should be viewed as a uniformity condition on the set of bidders. Theorem 3 provides just one way of understanding partition discrepancy by relating it to learning-theoretic quantities.

3 Population-Size-Independent Auctions

In this section we instantiate our main guarantee for specific mechanism classes M to obtain more concrete revenue approximations. The following is a na¨ıve lower bound on LM(Spar) for auction classes that can run a second-price auction on the grand bundle {1, . . . , m} with a reserve price.

Proposition 1. Let v1 ≥ · · · ≥ vn denote the valuations of each bidder in S on the grand bundle. For any 0 < α ≤ 1 such that αn is an integer, any mechanism class M containing the second-price auction on the grand bundle with reserve price r for every r satisfies LM(Spar) ≥ vαn W(S) with probability ≥ 1 - e-αnp over the draw of Spar ∼p S.

However, any bidder's value for the grand bundle can be an arbitrarily bad approximation to W(S). In the remainder of the paper we introduce some new auction classes and prove more fine-tuned approximations for those classes.

We now study a handful of population-size-independent auction classes, that is, auction classes that can be parameterized in a way that does not depend on the number of bidders. Traditional variants to the VCG auction including λauctions and AMAs specify boosts based on particular allocations and are thus not independent of the population size (and in particular cannot be used with LWI in a natural way since S1, . . . , SN, Spar can all vary in size). In contrast to these, our auctions specify boosts based on bundles and bundlings.

A bundling is a partition of items {1, . . . ,m} into bundles. We say that an allocation respects a bundling if no two items in the same bundle are allocated to different buyers. For an allocation β, let blg(β) denote the finest bundling respected by β, that is, the bundling with the fewest number of bundles that β respects. For example, if β allocates items 1 and 3 to bidder 1, and the remaining items to bidder 2, blg(β) = {{1, 3}, {2, 4, . . . ,m}}. Let Φ denote the collection of all bundlings. |Φ| < (0.792m/ ln(m+ 1))m [Berend and Tassa, 2010]. We now introduce two new auction classes that can be viewed as population-size-independent analogues of λ-auctions and VVCAs, respectively.

The class of bundling-boosted auctions is the class auctions parameterized by real |Φ|-dimensional vectors ω ∈ R|Φ| that specify additive boosts ω(φ) for each bundling φ ∈ Φ. The overall allocation α∗ used by a bundling-boosted auction ω is chosen to maximize W(α) + ω(blg(α)), and bidder i pays maxα(W-i(α) + ω(blg(α))) - (W-i(α∗ ) - ω(blg(α∗ ))). Equivalently, ω is the λ-auction with λ(α) = ω(blg(α)).

The class of bundle-boosted auctions is the class of auctions parameterized by real 2m-dimensional vectors ω ∈ R2m that specify additive boosts ω(b) for each bundle b ⊆ {1, . . . ,m}. The overall allocation α∗ is chosen to maximize W(α)+ ∑b∈blg(α) ω(b), and bidder i pays maxα(W-i(α)+ ∑b∈blg(α) ω(b)) - (W-i(α∗ ) + ∑b∈blg(α∗ ) ω(b)). Equivalently, the class of bundle-boosted auctions is the subclass of VVCAs where the parameters are constant across bidders.

The class of bundling-VCG auctions [Kroer and Sandholm, 2015] consists of all φ-VCG auctions, where a φ-VCG auction runs VCG while treating each bundle in φ as an indivisible item. The class of bundling-VCG auctions is a subclass of the class of bundle-boosted auctions: the φ-VCG auction can be represented by the bundle-boosted auction with ω(b) = 0 if b can be represented as a union of bundles from φ, and ω(b) = -∞ otherwise. The class of bundle-boosted auctions is a subclass of the class of bundling-boosted auctions: a bundle-boosted auction is a bundling-boosted auction with the restriction that ω(φ) = ∑b∈φ ω(b).

Since bundling-boosted and bundle-boosted auctions are subclasses of λ-auctions, they are both delineable with h(n) = (n + 1)2m+1 due to Balcan et al. [2018] (see the appendix for a derivation of LWI guarantees when only weaker delineability parameters that depend on the number of bidders are known). The following is a much stronger delineability result that has no dependence on the number of bidders.

Theorem 5. The class of bundling-boosted auctions is (|Φ|, |Φ|2 + m|Φ|3 )-delineable and the class of bundleboosted auctions is (2m, |Φ|2 +m|Φ|3 )-delineable.

Proof sketch. We prove that there are at at most m|Φ| bidders whose absence affects the allocations used by any bundlingboosted auction. This allows us to count the relevant hyperplanes delineating R|Φ| in a way that is independent of n.

Sandholm and Likhodedov [2005; 2015] (implicitly) study properties of the class of auctions parameterized by vectors ω ∈ Rm that specify additive boosts depending on the size of the bundle. We call this class of auctions bundle-size-boosted auctions. Bundle-size-boosted auctions are a subclass of bundle-boosted auctions: the equivalent bundle-boosted auction satisfies ω(b) = ω(|b|). For the class of bundle-sizeboosted auctions, we can prove a stronger delineability result.

Theorem 6. The class of bundle-size-boosted auctions is (m, meO(√m) )-delineable.

Figure 1 summarizes the containment relations between the various auction classes.

3.1 Guarantees for Bundling-Boosted Auctions

The class of bundling-boosted auctions is a rich class of auctions. If the efficient allocation when bidder i is absent also maximizes welfare when all bidders are present among all allocations respecting the same finest bundling, there is a bundling-boosted auction that extracts revenue equal to the welfare of the efficient allocation. More generally:

Theorem 7. Given a set of S bidders, let β denote the efficient allocation and let β-i denote the efficient allocation when bidder i is absent. Let ∆i(S) = maxα:blg(α)=blg(β-i)W(α) - W(β-i). There exists a bundling-boosted auction with revenue W(S) - ∑i ∆i(S).

Proof sketch. Let φ = blg(β) and let φ-i = blg(β-i). The bundling-boosted auction with ω(φ) = 0, ω(φ-i) = W(β)- W(β-i), and ω(φ′ ) = -∞ for all other bundlings φ′ ∈ Φ \ {φ, φ-1, . . . , φ-n} extracts the claimed revenue.

We give a simple example of bidder valuations that satisfy ∆i(S′ ) = 0 for every i and every S′ ⊆ S in the appendix.

Concentration inequalities enable us to provide bounds on LM(Spar) for the class of bundling-boosted auctions. We have ESpar [OPTM(Spar)] ≥ ESpar [W(Spar) - ∑i ∆i(Spar)] ≥ pW(S) - ∑i ∆i(Spar). If we run LWI with parameters p, q,N, we have (assuming for readability that ∆i(Spar) = 0 for all i) LM(Spar) ≥ (1 - η)p with probability ≥ 1 - e-2η2 p2W(S)2 /||¯ v||22, where ¯ v = (maxb⊆{1,...,m} vi(b))i∈S ∈ Rn , by McDiarmid's inequality.

Combined with Theorem 2, we get our main guarantee for the class of bundling-boosted auctions. For readability, we state our guarantees assuming ∆i(Spar) = 0 for every i.

Theorem 8. Let M be the class of bundling-boosted auctions. Let N ≥ N(ε, δ, Pdim(M)) and run LWI with parameters N, p, q. As long as W(S)2 ≥ ||¯ v||22 ln(1/δ)/2η2 p2 , Rev̂ M (Spar) ≥ W(S)((1 - η)p - ε) - 2τM(q, Spar) with probability ≥ 1 - 3δ conditional on ∆i(Spar) = 0 for all i.

Removing the assumption on ∆i(Spar) would replace the (1 - η)p loss term with (1 - η)(p - ∑i ∆i(Spar)/W(S)).

4 Efficient LearningWithin an Instance

We now explore two mechanism classes for which LWI can be implemented efficiently by leveraging efficient routines for solving winner determination (a generalization of the problem of computing efficient allocations). Though computing ̂ M = argmaxM∈M 1N ∑Nt=1 RevM(St) is NP-hard since it involves solving winner determination (which is well known to be NP-hard) winner determination can be solved efficiently in practice [Sandholm et al., 2005].

For the class of bundling-VCG auctions, we show that the branch-and-bound technique of Kroer and Sandholm [2015] is compatible with LWI. We did not derive a revenueguarantee for this class of auctions, however. For the class of sparse bundling-boosted auctions, which are bundlingboosted auctions with a constant number of positive boosts, we show that a revenue guarantee similar to (but more sample efficient than) Theorem 8 holds. We then show how LWI can be efficiently implemented for this class.

4.1 Bundling-VCGAuctions

Kroer and Sandholm [2015] give a branch-and-bound algorithm to compute the revenue-maximizing bundling-VCG auction for a given set of bidders. While our setting is different than theirs, their integer-program techniques can be directly used by LWI. Let f denote a function used as an upper bound in branch-and-bound to compute the optimal bundling. For learning groups S1, . . . , SN and x a node in the search tree (corresponding to a partial bundling), let ˆ f(x) = 1N ∑t f(x; St). Recall that f is admissible if its value at any node is an upper bound for the maximum revenue obtainable in the subtree rooted at that node, and f is monotonic if it decreases down each path in the search tree. These properties ensure that branch-and-bound finds the revenueoptimal bundling.

Proposition 2. If f is admissible for computing the optimal bundling, ˆ f is admissible for computing the empirically optimal bundling. The same holds for monotonicity.

4.2 Sparse Bundling-Boosted Auctions

Let Φ0 ⊂ Φ with |Φ0| = B, and let m0 be the number of bundles in the finest bundling in Φ0. Consider the subclass of bundling-boosted auctions for which ω(φ) > 0 only if φ ∈ Φ0 (and ω(φ) = 0 otherwise), which we call Φ0bundling-boosted auctions. The same argument used to prove Theorem 5 shows that the class of Φ0-bundling-boosted auctions is (B, B2 +m0B3 )-delineable. Let W Φ0 (S) denote the welfare of the welfare-maximizing allocation to bidders in S, subject to the constraint that the finest bundling respected by the allocation is in Φ0. The same arguments used to obtain Theorem 7 yield a guarantee with respect to W Φ0 (S).

Theorem 9. Let Mbe the class of Φ0-bundling-boosted auctions. Let N ≥ N(ε, δ, Pdim(M)) and run LWI with parameters N, p, q. As long as W Φ0 (S)2 ≥ ||¯ v||22 ln(1/δ)/2η2 p2 , Rev̂ M (Spar ) ≥ W Φ0 (S)((1 - η)p - ε) - 2τM(q, Spar ) with probability ≥ 1 - 3δ conditional on ∆i(Spar) = 0 for all i.

For B a fixed constant, the number of learning groups N required by LWI is O(B ln(m0B)) (hiding the dependence on ε and δ). In contrast, optimizing over the entire class of bundling-boosted auctions as in Theorem 8 would require N to be exponential (in m). For this class of auctions, we describe an algorithm that implements LWI with run-time exponential in B but polynomial in all other parameters (including the run time of the winner determination routine used). A similar algorithmwas used in Balcan et al. [2020], though in a different setting than ours.

Theorem 10. Let B = |Φ0|, and let m0 be the number of bundles in the finest bundling in Φ0. Given learning groups S1, . . . , SN, the empirical-revenue maximizing Φ0-bundling-boosted auction can be computed in (Nm0B)O(B) + 2w(m0, n)Nm0B time, where w(m0, n) is the time required to solve winner determination for n buyers with valuations over m0 items.

Proof sketch. We first show that there is a set H of at most NB2 +Nm0B2 hyperplanes partitioning RB such that empirical revenue is linear in ω within each region. Writing these hyperplanes down requires at most NB +Nm0B calls to our winner determination routine. The maximum empirical revenue in each region can be found by solving a linear program with B variables and at most |H| constraints.

4.3 Structural Revenue Maximization

Suppose the mechanism designer can only sample a limited number N of learning groups (due to a run-time constrant, for example). We introduced several new auction classes, but which one should the mechanism designer use in conjunction with LWI? Structural revenue maximization (SRM) helps answer this question. SRM suggests maximizing empirical revenue minus a regularization term that penalizes more complex mechanisms to ensure that the chosen auction is indeed likely to generalize well, rather than overfitting to the learning groups. Our generalization guarantee in Theorem 1 provides the appropriate regularizer εM(N, δ) = 240√Pdim(M)/N + √2 ln(1/δ)/N. Say the mechanism designer is deciding between auctions inM1 and auctions in M2. Let ̂ M1, ̂ M2 be the empirical-revenue-maximizing auctions fromM1 andM2, respectively, for one run of LWI. The mechanism designer should use mechanism ̂ Mk, k ∈ {1, 2}, that maximizes 1N ∑t Rev̂ Mk (St) - εMk (N, δ) since empirical revenue minus εM(N, δ) is a more accurate lower bound on expected revenue than empirical revenue alone. An SRM approach combined with LWI is incentive compatible since the final mechanism only depends on the learning groups of bidders. Our use of SRM is similar to SRM across instances, which was discussed in Balcan et al. [2018]. SRM for auction design was first proposed by Balcan et al. [2005], also for learning within an instance (but for unlimited supply).

5 Conclusions and Future Research

We developed a new framework for designing truthful, highrevenue combinatorial auctions for limited supply. Our mechanism learns within an instance. It generalizes and improves over previously-studied random-sampling mechanisms.

We proved guarantees on the performance of LWI based on a market-shrinkage term and a new complexity measure we coined partition discrepancy, which simultaneously measured intrinsic complexity of the auction class and uniformity in the set of bidders. We explored examples and proved a general bound on partition discrepancy. We then introduced new population-size-independent auction classes, and proved strong generalization bounds for these classes. We showed how LWI can be implemented efficiently by leveraging practically-efficient routines for solving winner determination, and showed how structural revenue maximization helps choose the right auction class to prevent overfitting.

Many interesting new directions arise from this work. First, developing a fuller picture of partition discrepancy would be of independent interest both in mechanism design and learning theory more broadly. Next, population-sizeindependent auctions are more versatile than other auction formats since they may be designed and specified without knowledge of the number of bidders participating. A further study of such auctions could yield insights into other revenue-maximization settings (for example, when the distribution over bidders is known) when the number of bidders is unknown. Finally, LWI-like frameworks could be applicable to more general mechanism design settings that involve optimization subject to incentive-compatibility constraints.

Acknowledgements

This material is based on work supported by the NSF under grants IIS-1618714, IIS-1718457, IIS-1901403, and CCF1733556, CCF-1535967, CCF-1910321, and SES-1919453, the ARO under award W911NF2010081, DARPA under cooperative agreement HR00112020003, an AWS Machine Learning Research Award, an Amazon Research Award, a Bloomberg Research Grant, and a Microsoft Research Faculty Fellowship.