{'fraction_non_alphanumeric': 0.059086561750860155, 'fraction_numerical': 0.01397359301444559, 'mean_word_length': 3.7554636739515654, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 48, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A General Theory of Sample Complexity for Multi-Item Profit Maximization

The design of profit-maximizing multi-item mechanisms is a notoriously challenging problem with tremendous real-world impact. The mechanism designer's goal is to field a mechanism with high expected profit on the distribution over buyers' values. Unfortunately, if the set of mechanisms he optimizes over is complex, a mechanism may have high empirical profit over a small set of samples but low expected profit. This raises the question, how many samples are sufficient to ensure that the empirically optimal mechanism is nearly optimal in expectation? We uncover structure shared by a myriad of pricing, auction, and lottery mechanisms that allows us to prove strong sample complexity bounds: for any set of buyers' values, profit is a piecewise linear function of the mechanism's parameters. We prove new bounds for mechanism classes not yet studied in the sample-based mechanism design literature and match or improve over the best known guarantees for many classes. The profit functions we study are significantly different from well-understood functions in machine learning, so our analysis requires a sharp understanding of the interplay between mechanism parameters and buyer values. We strengthen our main results with data-dependent bounds when the distribution over buyers' values is"well-behaved."Finally, we investigate a fundamental tradeoff in sample-based mechanism design: complex mechanisms often have higher profit than simple mechanisms, but more samples are required to ensure that empirical and expected profit are close. We provide techniques for optimizing this tradeoff.


Introduction
One of the most tantalizing and long-standing open problems in mechanism design is profit maximization in multi-item, multi-buyer settings. Much of the literature surrounding this problem rests on the strong assumption that the mechanism designer knows the distribution over buyers' values. In reality, this information is rarely available. The support of the distribution alone is often doubly exponential, so obtaining and storing the distribution is impractical.
We relax this assumption and instead assume that the mechanism designer only has a set of samples from the distribution Sandholm, 2004, 2005;Sandholm and Likhodedov, 2015). In this work, we develop learning-theoretic foundations of sample-based mechanism design. In particular, we provide generalization guarantees which bound the difference between the empirical profit of a mechanism over a set of samples and its expected profit on the unknown distribution.
A substantial body of theory on sample-based mechanism design has developed recently, primarily in single-parameter settings (Alon et al., 2017;Elkind, 2007;Cole and Roughgarden, 2014;Huang et al., 2015;Medina and Mohri, 2014;Morgenstern and Roughgarden, 2015;Roughgarden and Schrijvers, 2016;Devanur et al., 2016;Gonczarowski and Nisan, 2017;Hartline and Taggart, 2016;Bubeck et al., 2017;Chawla et al., 2014). In this paper, we present a general theory for deriving worst-case generalization guarantees in multi-item settings, as well as data-dependent guarantees when the distribution over buyers' values is well-behaved. We analyze mechanism classes that have not yet been studied in the sample-based mechanism design literature and match or improve over the best-known guarantees for many of the special classes that have been studied.

Our contributions
Our contributions come in three interrelated parts.
A general theory of worst-case generalization guarantees for profit maximization. We uncover a key structural property shared by a variety of mechanisms which allows us to prove strong generalization guarantees: for any fixed set of bids, profit is a piecewise linear function of the mechanism's parameters. Our main theorem provides generalization guarantees for any class exhibiting this structure. To prove this theorem, we relate the complexity of the partition splitting the parameter space into linear portions to the intrinsic complexity of the mechanism class, which we quantify using pseudo-dimension. In turn, pseudo-dimension bounds imply generalization bounds. We prove that many mechanisms throughout economics, artificial intelligence, and theoretical computer science share this structure, and thus our main theorem yields strong learnability guarantees.
We prove that our main theorem applies to randomized mechanisms, making us the first to provide generalization bounds for these mechanisms. Our guarantees apply to lotteries, a general representation of randomized mechanisms, which are extremely important in the intersection of economics and computation (e.g., (Babaioff et al., 2017;Briest et al., 2010;Chawla et al., 2010)). Randomized mechanisms are known to generate higher expected revenue than deterministic mechanisms in many settings (e.g., Conitzer and Sandholm (2003); Dobzinski and Dughmi (2009)). Our results imply, for example, that if the mechanism designer plans to offer a menu of lotteries over m items to an additive or unit-demand buyer, thenÕ U 2 m/ 2 samples are sufficient to ensure that every menu's expected profit is -close to its empirical profit, where U is the maximum profit achievable over the support of the buyer's valuation distribution.
We also provide guarantees for pricing mechanisms using our main theorem. These include item-pricing mechanisms, also known as posted-price mechanisms, where each item has a price and buyers buy their utility-maximizing bundles. These mechanisms are prevalent throughout economics and computation (e.g., (Feldman et al., 2015;Babaioff et al., 2014;Cai et al., 2016)). Additionally, we study multi-part tariffs, where there is an upfront fee and a price per unit. We are the first to provide generalization bounds for these tariffs and other non-linear pricing mechanisms, which have been studied in economics for decades (e.g., (Oi, 1971;Feldstein, 1972;Wilson, 1993)). For instance, our main theorem guarantees that if there are κ units of a single good for sale, theñ O U 2 κ/ 2 samples are sufficient to learn a nearly optimal two-part tariff. See Figure 1 for an illustration of the partition of the two-part tariff parameter space into piecewise-linear portions.
Our main theorem implies generalization bounds for many auction classes, such as second price auctions, which are fundamentally important in economics and beyond (e.g., (Vickrey, 1961;Cesa-Bianchi et al., 2015;Daskalakis and Syrgkanis, 2016)). We also study generalized VCG auctions, such as affine maximizer auctions, virtual valuations combinatorial auctions, and mixed-bundling auctions, which have been studied in AI and economics (e.g., (Sandholm and Likhodedov, 2015;Roberts, 1979;Lavi et al., 2003;Dobzinski and Sundararajan, 2008;Jehiel et al., 2007)). Figure 1: This figure illustrates a partition of the two-part tariff parameter space into piecewiselinear portions. Under a two-part tariff there are multiple units of a single good for sale. The seller sets an entry fee p 0 and a price p 1 per unit. If the buyer wishes to buy t ≥ 1 units, she pays p 0 + p 1 · t and otherwise she pays nothing. See Example 2.1 for more details.
Next, we combine our analysis with tools from the structured prediction literature in theoretical machine learning. In doing so, we provide more refined upper bounds for several "simple" mechanism classes and answer an open question posed by Morgenstern and Roughgarden (2016).
A key challenge which differentiates our generalization guarantees from those typically found in machine learning is the sensitivity of these mechanisms to small changes in their parameters. For example, changing the price of a good can cause a steep drop in profit if the buyer no longer wants to buy it. Meanwhile, for many well-understood function classes in machine learning, there is a close connection between the distance in parameter space between two parameter vectors and the distance in function space between the two corresponding functions. Understanding this connection is often the key to quantifying the class's intrinsic complexity. Intrinsic complexity typically translates to pseudo-dimension or another metric which allows us to derive learnability guarantees. Since profit functions do not exhibit this predictable behavior, we must carefully analyze the structure of the mechanisms we study in order to derive strong generalization guarantees.
Data-dependent generalization guarantees for profit maximization. We provide several data-dependent tools that strengthen our main theorem when the distribution over buyers' values is "well-behaved." First, we prove generalization guarantees that, surprisingly, are independent of the number of items for item-pricing mechanisms, second price auctions with reserves, and a subset of lottery mechanisms. Under anonymous prices, our bounds do not depend on the number of bidders either. These guarantees hold when the bidders are additive with values drawn from item-independent distributions (bidder i 1 's value for item j is independent from her value for item j , but her value for item j may be arbitrarily correlated with bidder i 2 's value for item j).
Bidders with item-independent value distributions have been studied extensively in prior research (e.g., (Cai and Daskalakis, 2017;Yao, 2014;Cai et al., 2016;Goldner and Karlin, 2016;Babaioff et al., 2017;Chawla et al., 2007;Hart and Nisan, 2012)). Cai and Daskalakis (2017) provide learning algorithms for bidders with valuations drawn from product distributions, which are item-independent. Their algorithms return mechanisms whose expected revenue is a constant fraction of the optimal revenue obtainable by any randomized and Bayesian truthful mechanism. Relying on prior work (Morgenstern and Roughgarden, 2016;Goldner and Karlin, 2016), their sample complexity guarantee when the buyers are additive is O (U/ ) 2 (nm log(nm) + log(1/δ)) , where n is the number of buyers. We improve this to O (U/ ) 2 (n log n + log(1/δ)) , completely removing the dependence on the number of items.
We also provide data-dependent generalization guarantees that, at a high level, are robust to outliers. Worst-case generalization guarantees typically grow linearly with the maximum profit achievable over the support of the distribution. They are thus pessimistic when the highest valua-tions have a low probability mass. We show how to obtain stronger guarantees in this setting.
See Table 1 for a subset of our bounds and Table 2 in Appendix A for all bounds. For ease of comparison, we represent them using Rademacher complexity, a tool we use to prove our datadependent bounds. Classic results in learning theory guarantee that with high probability over a set of samples S, for any mechanism in a class M, the difference between its expected and empirical profit isÕ R S (M) + U 1/|S| , where R S (M) is the Rademacher complexity of M over S. Typically,Õ R S (M) + U 1/|S| goes to zero as |S| grows. Bounding this quantity by , we can solve for the number of samples sufficient to ensure that empirical and expected profit are -close.
Structural profit maximization. Many of the mechanism classes we study exhibit a hierarchical structure. For example, when designing a pricing mechanism, the designer can segment the population into k groups and charge each group a different price. This is prevalent throughout daily life: movie theaters and amusement parks have different admission prices per market segment, with groups such as Child, Student, Adult, and Senior Citizen. In the simplest case, k = 1 and the prices are anonymous. If k equals the number of buyers, the prices are non-anonymous, thus forming a hierarchy of mechanisms. In general, the designer should not choose the simplest class to optimize over simply to guarantee good generalization because more complex classes are more likely to contain nearly optimal mechanisms. We show how the mechanism designer can determine the precise level in the hierarchy assuring him the optimal tradeoff between profit maximization and generalization.

Related research
Sample-based mechanism design was introduced in the context of automated mechanism design (AMD). In AMD, the goal is to design algorithms that take as input information about a set of buyers and return a mechanism that maximizes an objective such as revenue (Conitzer and Sandholm, 2002;Sandholm, 2003;Conitzer and Sandholm, 2004). The input information about the buyers in early AMD was an explicit description of the distribution over their valuations. The support of the distribution's prior is often doubly exponential, for example in combinatorial auctions, so obtaining and storing the distribution is impractical. In response, sample-based mechanism design was introduced where the input is a set of samples from this distribution Sandholm, 2004, 2005;Sandholm and Likhodedov, 2015). Those papers also introduced the idea of searching for a high-revenue mechanism in a parameterized space where any parameter vector yields a mechanism that satisfies the individual rationality and incentive-compatibility constraints. This was in contrast to the traditional, less scalable approach of representing mechanism design as an unrestricted optimization problem where those constraints need to be explicitly modeled. The parameterized work studied algorithms for designing combinatorial auctions with high empirical revenue. We follow the parameterized approach, but we study generalization guarantees, which they did not address.
Prior work on the sample complexity of profit maximization has primarily concentrated on the single-item setting, with the exception of work by Morgenstern and Roughgarden (2016); Balcan et al. (2016); Syrgkanis (2017); Medina and Vassilvitskii (2017), and Cai and Daskalakis (2017). We provide a detailed comparison of our results to these papers on multi-item mechanisms in Section 6. Earlier work of Balcan et al. (2008) addressed sample complexity for revenue maximization in unrestricted supply settings. From an algorithmic perspective, Devanur et al. (2016); Hartline and Taggart (2016), and Gonczarowski and Nisan (2017) Table 1: A subset of our Rademacher complexity bounds. We denote the maximum profit achievable by any mechanism in the class over the support of the bidders' valuation distribution by U . There are m items and n buyers. The cost function is general unless otherwise noted.
for learning nearly-optimal single-item auctions in various settings.
Several papers proved sample complexity guarantees using tools from the structured prediction literature (e.g., (Collins, 2000)), which we discuss in Section 5. Balcan et al. (2014) and Hsu et al. (2016) used these tools in a different setting than us: Balcan et al. (2014) provided algorithms that make use of past data describing the purchases of a utility-maximizing agent to produce a hypothesis function that can accurately forecast the future behavior of the agent. Hsu et al. (2016) used structured prediction to bound the pseudo-dimension of welfare maximization for item-pricing mechanisms as well as the concentration of demand for any particular good. Morgenstern and Roughgarden (2016) relied on structured prediction to provide sample complexity guarantees for several so called "simple" mechanism classes. In several cases, they proved loose guarantees using structured prediction; in the appendix, they used a first-principles approach to prove stronger guarantees. They did not explicitly consider the partition of the parameter space into regions over which profit is linear, but we can map their approach into our framework. In essence, their proofs break the parameter space into axis-aligned rectangles over which profit is linear. By analyzing more general partitions than axis-aligned rectangles, we match their tighter guarantees and provide bounds for mechanism classes they did not study.

Notation
We consider the problem of selling m heterogeneous goods to n buyers. We denote a bundle of goods as a quantity vector q ∈ Z m ≥0 and we denote the i th component of q as q[i]. Accordingly, the bundle consisting of only one copy of the i th item is denoted by the standard basis vector e i , where e i [i] = 1 and e i [j] = 0 for all j = i. Each buyer j ∈ [n] has a valuation function v j over bundles of goods. If one bundle q 0 is contained within another bundle q 1 (i.e., q 0 and v j (0) = 0. We denote an allocation as Q = (q 1 , . . . , q n ) where q j is the bundle of goods that buyer j receives under allocation Q. The cost to produce the bundle q is denoted as c (q) and the cost to produce the allocation Q is c (Q). Suppose there are κ i units available of item i. Let K = m i=1 κ i . We use v j = (v j (q 1 ) , . . . , v j (q K )) to denote buyer j's values for all of the K bundles and we use v = (v 1 , . . . , v n ) to denote a vector of buyer values. We also study additive buyers (v j (q) = m i=1 q[i]v j (e i )) and unit-demand buyers v j (q) = max i:q[i]≥1 v j (e i ) . Every auction in the classes we study is incentive compatible, so we assume that the bids equal the bidders' valuations.
We say that profit M (v) is the profit of a mechanism M on the valuation vector v. For a distribution D over buyers' values, we denote the expected profit of M over D as profit D (M ) and for a set of samples S, we denote the average profit of M over S as profit S (M ).
We study real-valued functions parameterized by vectors p in R d , denoted as f p : X → R. For a fixed v ∈ X , we often consider f p (v) as a function of its parameters, which we denote as f v (p).

A general theory for worst-case generalization guarantees
We now present a general theory for deriving generalization bounds. We assume there is an unknown distribution D over buyers' values, with support X . For a given mechanism class M, we aim to define a function M (N, δ) such that the following generalization guarantee holds: With probability 1−δ over the draw S ∼ D N , for any M ∈ M, |profit S (M ) − profit D (M )| ≤ M (N, δ).
Our main theorem uses structure shared by a myriad of mechanism classes to characterize the function M (N, δ), which is called a uniform convergence bound. Our results apply broadly to parameterized sets M of mechanisms. This means that every mechanism in M is defined by a vector p ∈ R d , where the value of d depends on the mechanism class. For example, p ∈ R m might be a vector of prices. Our guarantees apply to mechanism classes where for every valuation vector v ∈ X , profit as a function of the parameters p, denoted profit v (p), is piecewise linear. We begin by illustrating this property via several simple examples.
Example 2.1 (Two-part tariffs). In a two-part tariff, there are multiple units of a single good for sale. The seller sets an upfront fee p 0 and a price per unit p 1 . If a buyer wishes to buy t ≥ 1 units, she pays the upfront fee p 0 plus p 1 · t, and if she does not want to buy anything, she does not pay anything. Two-part tariffs have been studied extensively by economists (Oi, 1971;Feldstein, 1972;Wilson, 1993) and are prevalent throughout daily life. For example, gym and golf membership programs often require an upfront membership fee plus a fee per month. In many cities, purchasing a public transportation card requires a small upfront fee and an additional cost per ride. Many coffee machines, such as those made by Keurig and Nespresso, require specialty coffee pods. Purchasing these pods amounts to paying a fee per unit on top of the upfront fee, which is the cost of the coffee machine.
The buyer will buy nothing if v 1 (1) − (p 0 + p 1 ) < 0. She will buy exactly t ∈ [κ − 1] units so long as v 1 (t) − (p 0 + p 1 · t) ≥ 0 and v 1 (t + 1) − (p 0 + p 1 · (t + 1)) < 0. Finally, she will buy κ units so long as v 1 (κ) − (p 0 + p 1 · κ) ≥ 0. Therefore, there are κ hyperplanes splitting R 2 into convex regions such that within any one region, the number of units bought does not vary. So long as the number of units bought is invariant, profit is a linear function of p 0 and p 1 . See Figure 1 for an illustration.
Example 2.2 (Lotteries). A lottery is defined by a price p ∈ R and a vector φ = is the probability that the bidder receives item i. In this example, we consider the simple case where there is one additive buyer, no supplier cost, and a single lottery for sale. The buyer's expected utility for a lottery (φ, p) is E q∼φ [v (q)] − p. We know that the buyer will choose to buy the lottery so long as E q∼φ [v (q)] = v · (φ[1], . . . , φ[m]) ≥ p. If the buyer buys the lottery, she will pay a price of p, and otherwise she will pay nothing. Therefore, there is a single hyperplane breaking the parameter space into regions where profit is linear.
We provide generalization guarantees that are closely dependent on the "complexity" of the partition splitting R d into regions such that profit v (p) is linear. Inspired by structure exhibited by many mechanism classes, such as Examples 2.1 and 2.2, we require that this partition be defined by a finite number of hyperplanes. We give the following name to this type of mechanism class: Definition 2.3 ((d, t)-delineable). We say a mechanism class M is (d, t)-delineable if: 1. The class M consists of mechanisms parameterized by vectors p from a set P ⊆ R d ; and 2. For any v ∈ X , there is a set H of t hyperplanes such that for any connected component P of P \ H, the function profit v (p) is linear over P .
We relate delineability to the mechanism class's intrinsic complexity using pseudo-dimension.
Definition 2.4 (Pseudo-dimension (Pollard, 1984)). Let S = v (1) , . . . , v (N ) be a subset of X and let z (1) , . . . , z (N ) ∈ R be a set of targets. We say that z (1) , . . . , z (N ) witness the shattering of S by M if for all T ⊆ S, there exists some mechanism M T ∈ M such that for all v (i) ∈ T , profit M T v (i) ≤ z (i) and for all v (i) ∈ T , profit M T v (i) > z (i) . If there exists some z ∈ R N that witnesses the shattering of S by M, then we say that S is shatterable by M. Finally, the pseudo-dimension of M, denoted Pdim (M), is the size of the largest set that is shatterable by M.  Theorem 2.5 provides generalization bounds in terms of pseudo-dimension.
Theorem 2.5 (Pollard (1984)). For any M, let U be the maximum profit achievable by mechanisms in M.
In Theorem 2.6, we relate pseudo-dimension to delineability. The full proof is in Appendix A.
Proof sketch. Suppose the pseudo-dimension of M is N . By definition, there exists a set S = v (1) , . . . , v (N ) that is shattered by M. Let z (1) , . . . , z (N ) ∈ R be the points that witness this shattering. Again, by definition, we know that for any T ⊆ [N ], there exists a parameter vector To this end, for v (i) ∈ S, let H (i) be the set of t hyperplanes such profit v (i) (p) is linear over each connected component of P \ H (i) . We now consider the overlay of all N partitions P \ H (1) , . . . , P \ H (N ) . This overlay is made up of the sets P 1 , . . . , P τ , which are the connected components of P \ N i=1 H (i) . For each set P j and each i ∈ [N ], P j is completely contained in a single connected component of P \ H (i) , which means that profit v (i) (p) is linear over P j . (See Figures 2a, 2b, and 2c.) Since profit is linear within each set P j for j ∈ [τ ], we use the hyperplanes defined by those linear functions to further subdivide each set P j into regions P where for all i ∈ [N ] and all p ∈ P , either profit v (i) (p) < z (i) or vice versa (but not both). (See Figure 2d.) Thus, at most one vector p ∈ P * can come from P . Counting the number of subdivisions proves the theorem.

Delineable mechanism classes
We now show that a diverse array of mechanism classes are delineable, so we can apply Theorem 2.6. We warm up with Examples 2.1 and 2.2. The full proofs of all theorems are in Appendix A.
Theorem 2.7. Let M be the class of two-part tariffs over a single bidder and κ units of a single good. Then M is (2, κ)-delineable.
Proof. The parameter space defining M is R 2 . As we saw in Example 2.1, for any valuation vector v, there are κ hyperplanes splitting R 2 into regions over which profit v (p) is linear.
Theorem 2.8. Let M be the class of lottery mechanisms over m items and one additive bidder. Suppose that the cost to produce each item is zero. Then M is (m + 1, 1)-delineable.
Proof. This class's parameter space is R m+1 , since there is one price p for the lottery and one probability φ[i] per item i. As we saw in Example 2.2, for any valuation vector v, there is a single hyperplane splitting R m+1 into regions such that within any one region, profit v (p) is linear.

Lotteries
We now apply Theorem 2.6 to lottery menus, a generalization of Example 2.2. A length-lottery menu is a set M = φ (0) , p (0) , φ (1) , p (1) , . . . , φ ( ) , p ( ) ⊆ R m × R, where φ (0) = 0 and p (0) = 0. As is typical in the lottery literature, we assume there is a single buyer; our results easily generalize to multiple buyers. Given a buyer with values defined by v, let (φ v , p v ) ∈ M be the lottery that maximizes the buyer's expected utility. We assume the buyer is additive or unitdemand, so their expected utility for ]. Let M be the class of all length-lottery menus.
The key challenge in bounding Pdim (M) is that E q∼φv [c (q)] is not a piecewise linear function of the parameters φ (0) , . . . , φ ( ) . To overcome this challenge, rather than bounding Pdim (M), we bound the pseudo-dimension of a related class M . We then show that optimizing over M amounts to optimizing over The important insight is that M is delineable because for a fixed pair (v, z), both the lottery the buyer chooses and the bundle j:z[j]<φv[j] e j are defined by a set of hyperplanes.
Proof sketch. The buyer will prefer lottery j ∈ {0, . . . , } so long as . So long as the buyer's preferred lottery φ (j) , p (j) and the cost c i:z[i]<φ (j) [i] e i are fixed, profit is a linear function of the price.
The following theorem guarantees that optimizing over M amounts to optimizing over M itself. It follows from the fact that for all v and M , profit

Non-linear pricing mechanisms
Non-linear pricing mechanisms are specifically used to sell multiple units of each good. We assume that the cost function caps the total number of units of each item that the producer will supply. In other words, there is some cap κ i per item i such that it costs more to produce κ i units of item i than the buyers will pay. Formally, this means that there exists (κ 1 , . . . , κ m ) ∈ R m such that for all v ∈ X and all allocations Q = (q 1 , . . . , q n ), if there exists an item i such that n j=1 q j Menus of two-part tariffs. Menus of two-part tariffs are a generalization of Example 2.1. The seller offers the buyers different two-part tariffs and each buyer chooses the tariff and number of units that maximizes his utility. If the prices are non-anonymous, then each buyer is presented with a different menu of two-part tariffs.
Theorem 2.11. Let M and M be the classes of anonymous and non-anonymous length-menus of two-part tariffs. Then M is 2 , O n (κ ) 2 -delineable and M is 2n , O n (κ ) 2 -delineable.
Proof sketch. This proof is similar to that of Theorem 2.7, except the parameter space is R κ and there are now at most O n (κ ) 2 relevant hyperplanes: for each buyer j, she must decide which tariff to buy and how many units to buy. For non-anonymous prices, the argument is similar.
General non-linear pricing mechanisms. We study non-linear pricing under Wilson's bundling interpretation (Wilson, 1993): If the prices are anonymous, there is a price per quantity vector q denoted p (q). Buyer j will purchase the bundle that maximizes v j (q) − p (q). If the prices are non-anonymous, there is a price per quantity vector q and buyer j ∈ [n] denoted p j (q).
Theorem 2.12. Let M and M be the classes of anonymous and non-anonymous non-linear pricing mechanisms.
Proof sketch. For anonymous prices, each mechanism is defined by K parameters because there are K bundles and a price per bundle. Next, for each bidder j ∈ [n], there are K 2 hyperplanes of the form v j (q) − p (q) = v j (q ) − p (q ) determining whether the buyer prefers the bundle q or q . The analysis for non-anonymous prices follows similarly.
We prove polynomial bounds when prices are additive over items (Theorem A.4 in Appendix A).

Item-pricing mechanisms
We now describe the application of Theorem 2.6 to anonymous and non-anonymous item-pricing mechanisms. Under anonymous prices, the seller sets a price per item. Under non-anonymous prices, there is a buyer-specific price per item. We assume that there is some fixed but arbitrary ordering on the buyers such that the first buyer in the ordering arrives first and buys the bundle of goods that maximizes his utility, then the next buyer in the ordering arrives and buys the bundle of remaining goods that maximizes his utility, and so on.
Theorem 2.13. Let M and M be the classes of item-pricing mechanisms with anonymous prices and non-anonymous prices, respectively. If the buyers are additive, then M is (m, m)-delineable and M is (nm, nm)-delineable.
Proof sketch. For a given valuation vector v, let j i be the buyer with the highest value for item i. Under anonymous prices, we know item i will be bought so long as v j i (e i ) is at least the price of item i. Once the items bought are fixed, profit is linear. Therefore, there are m hyperplanes splitting R m into regions where profit is linear. The analysis for non-anonymous prices is similar.

Auctions
We now present applications of Theorem 2.6 to auctions.
Second price item auctions with item reserves. These auctions are only strategy proof for additive bidders, so we restrict our attention to this setting. In the case of non-anonymous reserves, there is a price p j (e i ) for each item i and each bidder j. The bidders submit bids on the items. For each item i, the highest bidder j wins the item if her bid is above p j (e i ). She pays the maximum of the second highest bid and p j (e i ). If the bidder with the highest bid bids below her reserve, the item goes unsold. In the case of anonymous reserves, p 1 (e i ) = p 2 (e i ) = · · · = p n (e i ) for each item i.
Theorem 2.14. Let M and M be the classes of anonymous and non-anonymous second price item auctions. Then M is (m, m)-delineable and M is (nm, m)-delineable.
Proof sketch. Given a vector v ∈ X , let j i be the highest bidder for item i and let j i be the second highest bidder. Under anonymous prices, there are 2m hyperplanes splitting R m into regions where profit is linear; they correspond to whether or not v j i (e i ) ≥ p (e i ), and whether or not v j i (e i ) ≥ p (e i ). The analysis for non-anonymous prices follows similarly.
Mixed bundling auctions with reserve prices (MBARPs). MBARPs (Jehiel et al., 2007;Tang and Sandholm, 2012) are a variation on the VCG mechanism with item reserve prices, with an additional fixed boost to the social welfare of any allocation where some bidder receives the grand bundle. The allocation is the boosted social welfare maximizer and the payments are the VCG payments on the boosted social welfare values.
Formally, MBARPs are defined by a parameter γ ≥ 0 and m reserve prices p (e 1 ) , . . . , p (e m ). Let λ be a function such that λ (Q) = γ if some bidder receives the grand bundle under allocation Q and 0 otherwise. For an allocation Q, let q Q be the items not allocated. Given a valuation vector v, the MBARP allocation is Using the notation Theorem 2.15. Let M be the set of MBARPs. Then M is m + 1, (n + 1) 2 2m -delineable.
Proof sketch. Each MBARP is defined by m + 1 parameters: the m reserves and the fixed boost for the grand bundle allocations. To compute the boosted VCG payments, it is necessary to compute n + 1 allocations: the allocation maximizing boosted social welfare with all bidders participating and the allocation without each bidder in turn. We show that there are (n + 1) 2 2m hyperplanes delineating regions of R m+1 where these allocations are fixed, in which case profit is linear.
Affine maximizer auctions (AMAs). AMAs are an expressive mechanism class: Roberts (1979) proved that AMAs are the only ex post truthful mechanisms over unrestricted value domains. Later, Lavi et al. (2003) proved that under natural assumptions, every truthful multi-item auction is an "almost" AMA, that is, an AMA for sufficiently high values. An AMA is defined by a weight per bidder w j ∈ R >0 and a boost per allocation λ (Q) ∈ R ≥0 . By increasing any w j or λ (Q), the seller can increase bidder j's bids or increase the likelihood that Q is the auction's allocation. The AMA allocation Q * is the one which maximizes the weighted social welfare, i.e., The payments have the same form as the VCG payments, with the parameters factored in to ensure truthfulness. Formally, using the notation Virtual valuation combinational auctions (VVCAs) (Likhodedov and Sandholm, 2004) are a special case of AMAs where each λ (Q) is split into n terms such that λ (Q) = n j=1 λ j (Q) where λ j (Q) = c j,q for all allocations Q that give bidder j exactly bundle q. Finally, λ-auctions (Jehiel et al., 2007) are a special case of AMAs where the bidder weights equal 1.
Theorem 2.16. Let M, M , and M be the classes of AMAs, VVCAs, and λ-auctions, respectively.
Proof sketch. The AMA profit function is not piecewise linear in its parameters since it involves dividing by the bidder weights. Therefore, we map the parameters into an O (n (n + 1) m )-dimensional space over which profit is piecewise linear. We show that this higher-dimensional space can be partitioned by (n + 1) 2m+1 hyperplanes so that within any one region, the allocation with all bidders participating and the allocations without each bidder in turn are fixed, which means that the VCG-style payments are linear in this higher dimensional space.
Theorem 2.16 implies exponentially-many samples are sufficient to ensure that empirical and expected profit are close. Balcan et al. (2016) prove an exponential number of samples is also necessary.
We now study two hierarchies of AMAs. In Section 4, we show how to learn which level of the hierarchy optimizes the tradeoff between generalization and profit for the setting at hand. Q-boosted AMAs and λ-auctions. Let Q be a set of allocations. The set of Q-boosted AMAs (resp., λ-auctions) consists of all AMAs (resp., λ-auctions) where only allocations in Q are boosted. In other words, if λ (Q) > 0, then Q ∈ Q.
Proof sketch. This proof is similar to that of Theorem 2.16, but we need not map into as highdimensional a space as in that proof since there are fewer parameters defining each auction.

Data-dependent generalization guarantees
In this section, we provide two data-dependent means of strengthening the results in Section 2 when the underlying distribution is "well-behaved." The first applies to bidders whose values are drawn from item-independent distributions and mechanisms whose profit functions decompose additively. For example, under item-pricing mechanisms, the profit function decomposes into the profit obtained from selling item 1, plus the profit obtained by selling item 2, and so on. We obtain surprisingly strong guarantees in this setting: our bounds do not depend on the number of items and under anonymous prices, they do not depend on the number of bidders either.
Second, we provide tools for deriving generalization guarantees that are robust to outliers. Our worst-case bounds from Section 2 grow linearly with the maximum profit achievable over the support of the distribution. These bounds are thus pessimistic when the highest valuations in the support have low probability mass. We show how to obtain stronger guarantees in this setting.
To obtain our data-dependent guarantees, we move from pseudo-dimension to Rademacher complexity (Bartlett and Mendelson, 2002;Koltchinskii, 2001), which allows us to prove distributiondependent generalization guarantees. This is the key advantage of Rademacher complexity over pseudo-dimension; pseudo-dimension implies generalization guarantees that are worst-case over the distribution whereas Rademacher complexity implies distribution-dependent guarantees. We prove that this shift to Rademacher complexity from pseudo-dimension is in fact necessary in order to obtain guarantees that are independent of the number of items (Theorem 3.6).
We now define Rademacher complexity. Given a set S = v (1) , . . . , v (N ) , the empirical Rademacher complexity of M with respect to S is defined as (2014)). Rademacher complexity and pseudo-dimension are closely connected:

Stronger guarantees for additively-decomposable classes
In the following corollary of Theorem 2.6, we show that if the profit functions of a class M decompose additively into a number of simpler functions, then we can easily bound R S (M) using the Rademacher complexity of those simpler functions. We then demonstrate the power of this corollary by proving stronger guarantees for many well-studied mechanism classes when the bidders are additive and their valuations are drawn from item-independent distributions. This includes bidders with values drawn from product distributions as a special case, which have been extensively studied in the mechanism design literature (e.g., (Cai and Daskalakis, 2017;Yao, 2014;Cai et al., 2016;Goldner and Karlin, 2016;Babaioff et al., 2017;Hart and Nisan, 2012)).
We say that a mechanism class M parameterized by vectors p ∈ R d decomposes additively if for all p ∈ R d , there exist T functions f 1,p , . . . , f T,p such that the function profit p can be written as profit p (·) = f 1,p (·) + · · · + f T,p (·).
Corollary 3.2. Suppose that M is a set of additively decomposable mechanisms parameterized by vectors p ∈ P. Moreover, suppose that for all p ∈ P, the range of f i,p over the support of D is [0, U i ] and that the class {f i,p : p ∈ P} is (d i , t i )-delineable. Then for any set of samples S ∼ D N , Proof. The corollary follows from Theorems 2.6 and 3.1, and the fact that for any sets G and G of functions mapping X to R and any set S ⊆ X , R S ({g + g : g ∈ G, g ∈ G }) ≤ R S (G)+ R S (G ).
We now instantiate Corollary 3.2 for several mechanism classes. The full proofs are in Appendix B. Proof sketch. We decompose profit p into m profit functions profit 1,p , . . . , profit m,p , where profit i,p is the profit obtained from selling item i. We then prove that each class profit i,p : p ∈ R m ≥0 is (1, 1)-delineable and that U = U 1 + · · · + U m since D is item-independent.
The following theorem follows from the same logic as Theorem 3.3.
Theorem 3.4. Let M and M be the sets of anonymous and non-anonymous item-pricing mechanisms, respectively. Suppose the bidders are additive, D is item-independent, and the cost function is additive. For any set of samples Theorem 3.5. Let M be the set of length-item lottery menus. If the bidder is additive, D is item-independent, and the cost function is additive, then for any set S ∼ D N , Proof sketch. The theorem follows from proving that the class of all single-item lotteries M i is 2 , 2 -delineable. We prove this by showing that the lottery the buyer chooses depends on +1 2 hyperplanes, one per pair of lotteries. Once the lottery is fixed, profit M i (v) is a linear function.
Finally, we prove lower bounds showing that one could not hope to prove the generalization guarantees implied by Theorems 3.3 and 3.4 using pseudo-dimension alone. We sketch the proof for one case. The full proof is in Appendix B.
Proof sketch. Let M be the class of anonymous item-pricing mechanisms over one additive bidder.
Let v (i) be a vector where v , let M T be the mechanism defined such that the price of item i is 2 if i ∈ T and otherwise, its price is 0. If i ∈ T , then profit M T v (i) = 2 and otherwise, profit M T v (i) = 0. Therefore, the targets z (1) = · · · = z (m) = 1 witness the shattering of S by M.

Stronger guarantees in the presence of outliers
We now show that even if there are occasionally outliers with unusually high valuations, the empirical Rademacher complexity need not be blown out of proportion based on those outliers.
Proof sketch. First, we split the sample into two groups L and B. The set L consists of all v ∈ S such that M P M (v) ≤ a and B = S \ L. We then split the Rademacher complexity formula up between the sets L and B, proving that N R S (M) ≤ |L| R L (M) + |B| R B (M). We use a Chernoff bound to show that with high probability, |B| is small, and thus the summand |B| R B (M) contributes little to the Rademacher complexity bound. Therefore, the importance of U in the bound is diminished.
In the following remark, we note that it is possible to learn an estimate for a given any confidence parameter b using a small number of samples because the VC dimension of thresholds is 1.
There are many ways to bound M P M (v) and thus apply Remark 3.8 and Theorem 3.7. For example, if M is the class of two-part tariffs over κ units and a single buyer, then M P M (v) = max q∈ [κ] {v (q) − c (q)} or if M is the class of lottery menus with an additive cost function, We include examples of other bounds on M P M (v) in Appendix B.

Structural profit maximization
In this section, we use our results from Section 2 to provide tools for optimizing the profitgeneralization tradeoff. We begin by demonstrating this tradeoff pictorially. For the sake of illustration, suppose that M is a mechanism class that decomposes into a nested sequence of subclasses M 1 ⊆ · · · ⊆ M t = M. For example, if M is the class of AMAs, then M k could be the class of all Q-boosted AMAs with |Q| = k. Prior work (Balcan et al., 2016) gave uniform convergence bounds for AMAs without taking advantage of the class's hierarchical structure. We illustrate uniform convergence bounds in the left panel of Figure 3 with t = 4. On the x-axis, we chart the growth in mechanism complexity, using a measure such as Rademacher complexity. On the y-axis, for i = 1, 2, 3, 4, we plot the empirical profit over a set of samples S of the mechanism M i (S) ∈ M i that maximizes empirical profit. We also plot the lower bound on the expected profit of M i (S) which is equal to profit S (M i (S)) − M (N, δ). This lower bound is always increasing, so the mechanism designer may erroneously think that M 4 (S) is the best mechanism to field.
Our general theorem allows us to be more careful since we can easily derive bounds M i (N, δ) for each class M i . Then, we can spread the confidence parameter δ across all subsets M 1 , . . . , M t using a weight function w : N → [0, 1] such that w (i) ≤ 1. More formally, by a union bound, we are guaranteed that with probability at least 1 − δ, for all mechanisms M ∈ M, the difference between profit S (M ) and profit D (M ) is at most min i:M ∈M i M i (N, δ · w (i)). This is illustrated in the right panel of Figure 3, where for i = 1, 2, 3, 4, the lower bound on the expected profit of M i (S) is its empirical profit minus M i (N, δ · w (i)). By maximizing this complexity-dependent lower bound on expected profit, the designer can correctly determine that M 2 (S) is a better mechanism to field than M 4 (S). Structural profit maximization (SPM) is the process of maximizing this complexity-dependent lower bound.
Both the decomposition of M into subsets and the choice of a weight function allow the designer to encode his prior knowledge about the market. For example, if mechanisms in M i are likely more profitable than others, he can increase w (i). The larger the weight w (i) assigned to M i is, the larger δ · w (i) is, and a larger δ · w (i) implies a smaller M i (N, δ · w (i)), thereby implying stronger guarantees.
We now present an application of SPM to item pricing. Group pricing is prevalent throughout daily life: movie theaters, amusement parks, and tourist attractions have different admission prices per market segment, with groups such as Child, Student, Adult, and Senior Citizen. Formally, the designer can segment the buyers into k groups and charge each group a different price. If k = 1, the prices are anonymous and if k = n, they are non-anonymous, thus forming a mechanism hierarchy. For k ∈ [n], let M k be the class of non-anonymous pricing mechanisms where there are k price groups. In other words, for all mechanisms in M k , there is a partition of the buyers B 1 , . . . , B k such that for all t ∈ [k], all pairs of buyers j, j ∈ B t , and all items i ∈ [m], p j (e i ) = p j (e i ). We derive the following guarantee for this hierarchy.
Theorem 4.1. Let M be the class of non-anonymous item-pricing mechanisms over additive bidders and let w : [n] → R be a weight function such that n i=1 w (i) ≤ 1. Then for any δ ∈ (0, 1), with probability at least 1 − δ over the draw S ∼ D N , for any k ∈ [n] and any mechanism M ∈ M k , Proof sketch. First, we prove that M k is (km, nm)-delineable. The theorem then follows from Theorems 2.5 and 2.6, and by multiplying δ with w (k).
We also prove the following theorem for the hierarchy of AMAs defined by the classes of Qboosted AMAs. For an AMA M , let Q M be the set of all allocations Q such that λ (Q) > 0.
Theorem 4.2. Let M be the class of AMAs and let w be a weight function that maps sets of allocations Q to [0, 1] such that w (Q) ≤ 1. With probability 1 − δ over the draw S ∼ D N , for any M ∈ M, Theorem 4.2 follows from Theorems 2.5, 2.6, and 2.17: we only need to multiply the weight term with δ as it appears in the resulting bound. Theorems 2.11, 2.17, and 2.9 similarly imply results for two-part tariffs, Q-boosted λ-auctions, and lottery menus (see Theorems C.1, C.2, and C.3 in Appendix C).

Connection to structured prediction
In this section, we connect the hyperplane structure we investigate in this paper to the structured prediction literature in machine learning (e.g., (Collins, 2000)), thus proving even stronger generalization bounds for item-pricing mechanisms under buyers with unit-demand and general valuations and answering an open question by Morgenstern and Roughgarden (2016). Morgenstern and Roughgarden (2016) used structured prediction to provide sample complexity guarantees for several "simple" mechanism classes. They observed that these classes have profit functions which are the composition of two simpler functions: A generalized allocation function f (1) p : X → Y and a simplified profit function f . For example, Y might be the set of allocations. In this case, we say that M is F (1) , F (2) -decomposable, where F (1) = f (1) p : p ∈ P and F (2) = f (2) p : p ∈ P . See Example D.1 in Appendix D for an example of this decomposition. Morgenstern and Roughgarden (2016) bound Pdim (M) using the "complexity" of F (1) , which they quantified using tools from structured prediction, namely, linear separability.
Definition 5.1 (a-dimensionally linearly separable). A set of functions F = {f p : X → Y | p ∈ P} is a-dimensionally linearly separable if there exists a function ψ : X ×Y → R a and a vector w p ∈ R a for each p ∈ P such that f p (v) ∈ argmax α∈Y w p , ψ (v, α) and |argmax α∈Y w p , ψ (v, α) | = 1.
If M is F (1) , F (2) -decomposable and F (1) is a-dimensionally linearly separable over Y, we say that M is a-dimensionally linearly separable over Y.
The bounds Morgenstern and Roughgarden (2016) provided using linear separability are loose in several settings: for anonymous and non-anonymous item-pricing mechanisms under additive bidders, their structured prediction approach gives a pseudo-dimension bound of O m 2 and O nm 2 log m , respectively. They left as an open question whether linear separability can be used to prove tighter guarantees. Using the hyperplane structures we study in this paper, we prove that the answer is "yes." We require the following refined notion of (d, t)-delineable classes.
Definition 5.2 ((d, t 1 , t 2 )-divisible). Suppose M consists of mechanisms parameterized by vectors p ⊆ R d and that M is F (1) , F (2) -decomposable. We say that M is (d, t 1 , t 2 )-divisible if: 1. For any v ∈ X , there is a set H of t 1 hyperplanes such that for any connected component P of R d \ H, the function f 2. For any v ∈ X and any α ∈ Y, there is a set H 2 of t 2 hyperplanes such that for any connected component P of R d \ H 2 , the function f v,α (p) is linear over all p ∈ P .
Proof sketch. Suppose that N is the pseudo-dimension of M. Let S = v (1) , . . . , v (N ) be a shatterable set of size N and let z (1) , . . . , z (N ) be the corresponding witnesses. Morgenstern and Roughgarden (2016) showed that N must be bounded by the product of the following quantities: 1. The number of subsets of S of size a, times the number of ways to label those subsets using functions from F (1) .
2. Roughly speaking, the size of the following vector set, maximized over all α (1) , . . . , α (N ) ∈ Y: First, we prove the first quantity is bounded by ω = N a ·min |Y| a , d (at 1 ) d . An obvious upper bound on this quantity is N a · |Y| a ≤ N a |Y| a . When |Y| is large, we prove a more refined bound of d (at 1 ) d by using the fact that for any subset S ⊆ S of size a, there are at 1 hyperplanes splitting is constant for all v ∈ S , and there are d (at 1 ) d such regions (Buck, 1943). We use a similar argument to bound the second quantity.

Divisible mechanism classes
We instantiate Theorem 5.3 with full proofs in Appendix D.  Proof sketch. The proof is similar to Theorem 5.4's, except there are 2 m 2 hyperplanes per bidder defining their preference ordering on the bundles: one for each pair of bundles. This amounts to at most t 1 = n2 2m hyperplanes splitting R m into regions where the items allocated are fixed.
When there are anonymous prices, the number of hyperplanes in the partition is large, so considering the hyperplane partition does not help us. As a result, Theorem 5.5 implies the same bound Morgenstern and Roughgarden (2016) gave. In the case of non-anonymous prices, analyzing the hyperplane partition gives a better bound than their bound of O nm 2 log n .
In Theorem D.4 in Appendix D, we use Theorem 5.3 to prove pseudo-dimension bounds of O (m log m) and O (nm log nm) for the classes of second price auctions for additive bidders with anonymous and non-anonymous reserves, respectively. In Theorem D.5, we prove the same for item-pricing mechanisms. We thus answer the open question by Morgenstern and Roughgarden (2016). These bounds match those implied by Theorems 2.13 and 2.14.
6 Comparison of our results to prior research Morgenstern and Roughgarden (2016) studied "simple" multi-item mechanisms: item-pricing mechanisms and second-price item auctions. See Section 5.1, Table 1, and Table 2 for a comparison of our guarantees. Balcan et al. (2016) provided generalization guarantees for AMAs, λ-auctions, VVCAs, and MBARPs. See Table 1c in Section 1 for a comparison of our guarantees.
Syrgkanis (2017) provided generalization guarantees specifically for the mechanism that maximizes empirical revenue. This is in contrast to our bounds, which apply uniformly to every mechanism in a given class. This is crucial when it may not be computationally feasible to determine an empirically optimal mechanism, but only an approximation. Syrgkanis (2017)  Cai and Daskalakis (2017) provided learning algorithms that return mechanisms whose expected revenue is a constant fraction of the optimal revenue obtainable by any randomized and Bayesian truthful mechanism. As we describe in Section 1, under additive buyers, we completely remove the dependence on the number of items from their algorithm's sample complexity guarantee. When the bidders are unit-demand, their algorithm returns a non-anonymous item-pricing mechanism. Based on work by Morgenstern and Roughgarden (2016), their algorithm has a sample complexity guarantee of O (U/ ) 2 nm 2 log n + log (1/δ) . Via Theorem 3.4, we improve this to O (U/ ) 2 (nm log (nm) + log (1/δ)) . They also provided algorithms for bidders with other types of valuations, such as subadditive and XOS. In these cases, their algorithms return item-pricing mechanisms with entry fees. Our main theorem would provide pessimistic guarantees for these mechanisms due to the exponentially large number of parameters. To circumvent this, their proofs use specific structural properties exhibited by bidders with product distributions, whereas the primary focus of this paper is to provide a general theory applicable to many different mechanisms and buyer types. Medina and Vassilvitskii (2017) studied single-bidder, multi-item pricing in a different model from ours, where there is no bound on the number of items but each item is defined by a feature vector. Their pricing algorithm has access to a bid predictor mapping from feature vectors to bids. They related their algorithm's performance to the bid predictor's accuracy, among other factors. Devanur et al. (2016) studied several single-item auction classes, including the class M of second price item auctions with non-anonymous reserves and no cost function. They proved that N = O (U/ ) 2 (n log (U/ ) + log (1/δ)) samples are sufficient to ensure that with probability 1−δ over the draw S ∼ D N , for all M ∈ M, |profit S (M ) − profit D (M )| ≤ . Our Theorem 2.14 for the multi-item case, specialized to the single-item setting, implies that O (U/ ) 2 (n log n + log (1/δ)) samples are sufficient, which is incomparable to Devanur et al.'s bound due to the log factors.

Conclusion
In this work, we prove generalization guarantees by taking advantage of structure shared by a diverse array of mechanisms: for a fixed set of buyer values, profit is a piecewise linear function of the mechanism's parameters. We relate the intrinsic complexity of a given mechanism class to the complexity of the partition breaking the parameter space into linear portions. We thus derive strong guarantees for many widely-studied mechanism classes, including lotteries, pricing mechanisms, and auctions. We both prove new bounds for mechanism classes not yet studied in the sample-based mechanism design literature, and match or improve over the best known guarantees for many mechanism classes. We provide data-dependent generalization guarantees which strengthen our main theorem when the underlying distribution over buyers' values is "well-behaved." Finally, we analyze hierarchical structures breaking up the mechanism classes we study and show how to pinpoint the level in the hierarchy that optimizes the tradeoff between empirical profit and generalization.
Submultiplicative Glivenko-Cantelli and uniform convergence of revenues. Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS).
Proof. Suppose Pdim(M) = N . By definition, there exists a set S = v (1) , . . . , v (N ) that is shattered by M. Let z (1) , . . . , z (N ) ∈ R be the points that witness this shattering. Again, by definition, we know that for any T ⊆ [N ], there exists a parameter vector p T ∈ P such that if To show that the pseudo-dimension N of M is O(d log(dt)), we will show that |P * | = 2 N < dN d dt d , which means that N = O(d log(dt)).
To this end, for v (i) ∈ S, let H (i) be the set of t hyperplanes such that for any connected component P of P \ H (i) , profit v (i) (p) is linear over P . We now consider the overlay of all N partitions P \ H (1) , . . . , P \ H (N ) . Formally, this overlay is made up of the sets P 1 , . . . , P τ , which are the connected components of P \ N i=1 H (i) . For each set P j and each i ∈ [N ], P j is completely contained in a single connected component of P \ H (i) , which means that profit v (i) (p) is linear over P j . (See Figures 2a, 2b, and 2c for illustrations.) As we know from work by Buck (1943), since where on one side of the hyperplane, profit v (i) (p) ≤ z (i) and on the other side, profit v (i) (p) > z (i) . Let H P j be all N hyperplanes for all N samples, i.e., H P j = a (i) Notice that in any connected component P of P j \H P j , for all i ∈ [N ], profit v (i) (p) is either greater than z (i) or less than z (i) (but not both) for all p ∈ P . (See Figure 2d for an illustration.) Thus, at most one vector p ∈ P * can come from P . In total, the number of connected components of P j \ H P j is smaller than dN d . The same holds for every partition P j . Thus, the total number of regions where for all i ∈ [N ], profit v (i) (p) is either greater than z (i) or less than z (i) (but not both) is smaller than dN d · d(N t) d . We may bound |P * | = 2 N < dN d · d(N t) d , which means that N < 2d log N + 2 log d + d log t. By Lemma A.1, with a = 2d, b = 2 log d + d log t, and x = N , we have that N < 8d log(4d) + d log t + 2 log d ≤ 9d log(4dt) = O(d log(dt)).
Proof. By definition of profit m ,

Item-pricing
Theorem 2.10. With probability 1 − δ over the draw of a sample v (1) , Proof. We know that with probability at least 1 − δ over the draw of a sample We also know from Lemma A.2 that Therefore, the theorem statement holds.
Proof. The buyer will prefer lottery j ∈ {0, . . . , } so long as v · φ (j) > v · φ (k) for any k = j, which amount to +1 2 hyperplanes in R (m+1) defining the lottery the buyer chooses. Next, for each lottery φ Theorem 2.11. Let M and M be the classes of anonymous and non-anonymous length-menus of two-part tariffs. Then M is 2 , O n (κ ) 2 -delineable and M is 2n , O n (κ ) 2 -delineable.
Proof. In the case of anonymous prices, every length-menu of two-part tariffs is defined by d = 2 parameters: the fixed fee and unit price for each of the menu entries. Buyer j will choose the quantity q and menu entry (p 1 q). Therefore, the quantity q and menu entry that she chooses is determined by (κ ) 2 hyperplanes in R d of the form v j (q) − (p 1 q ). In total, there are n( κ) 2 hyperplanes that determine the menu entry and quantity demanded by all n buyers, over which profit is linear in the fixed fees and unit prices.
In the case of non-anonymous reserve prices, the same argument holds, except that every lengthmenu of two-part tariffs is defined by 2n parameters: for each buyer, we must set the fixed fee and unit price for each of the menu entries.
Theorem 2.12. Let M and M be the classes of anonymous and non-anonymous non-linear pricing mechanisms. Let K = m i=1 (κ i + 1). Then M is K, nK 2 -delineable and M is nK, nK 2delineable.
Proof. We begin by analyzing the case where there are anonymous prices. Every non-linear pricing mechanism is defined by d = m i=1 (κ i + 1) parameters because that is the number of different bundles and there is a price per bundle. Buyer j will prefer the bundle corresponding to the quantity vector q over the bundle corresponding to the quantity vector q if v j (q) − p(q) ≥ v j (q ) − p(q ). Therefore, there are at most m i=1 (κ i + 1) 2 hyperplanes in R d determining each buyer's preferred bundle -one hyperplane per pair of bundles. This means that there are a total of n m i=1 (κ i + 1) 2 hyperplanes in R d such that in any one region induced by these hyperplanes, the bundles demanded by all n buyers are fixed and profit is linear in the prices of these n bundles.
In the case of non-anonymous prices, the same argument holds, except that every non-linear pricing mechanism is defined by n m i=1 (κ i + 1) parameters -one parameter per bundle-buyer pair.
In the case of anonymous prices, any additively decomposable non-linear pricing mechanism is defined by d = m i=1 (κ i + 1) parameters. As in the proof of Theorem 2.12, there are a total of n m i=1 (κ i + 1) 2 hyperplanes in R d such that in any one region induced by these hyperplanes, the bundles demanded by all n buyers are fixed and profit is linear in the prices of these n bundles.
In the case of non-anonymous prices, the same argument holds, except that every non-linear pricing mechanism is defined by n m i=1 (κ i + 1) parameters -one parameter per item, quantity, and buyer tuple.
Theorem 2.13. Let M and M be the classes of item-pricing mechanisms with anonymous prices and non-anonymous prices, respectively. If the buyers are additive, then M is (m, m)-delineable and M is (nm, nm)-delineable.
Proof. In the case of anonymous prices, every item-pricing mechanisms is defined by m prices p ∈ R m , so the parameter space is R m . Let j i be the buyer with the highest value for item i. We know that item i will be bought so long as v j i (e i ) ≥ p(e i ). Once the items bought are fixed, profit is linear. Therefore, there are m hyperplanes splitting R m into regions where profit is linear.
In the case of non-anonymous prices, the parameter space is R nm since there is a price per buyer and per item. The items each buyer j is willing to buy is defined by m hyperplanes: v j (e i ) ≥ p j (e i ). So long as these preferences are fixed, profit is a linear function of the prices. Therefore, there are nm hyperplanes splitting R nm into regions where profit is linear.
Theorem 2.14. Let M and M be the classes of anonymous and non-anonymous second price item auctions. Then M is (m, m)-delineable and M is (nm, m)-delineable.
Proof. For a given valuation vector v, let j i be the highest bidder for item i and let j i be the second highest bidder. Under anonymous prices, item i will be bought so long as v j i (e i ) ≥ p(e i ). If buyer j i buys item i, his payment depends on whether or not v j i (e i ) ≥ p(e i ). Therefore, there are t = 2m hyperplanes splitting R m into regions where profit is linear. In the case of non-anonymous prices, the only difference is that the parameter space is R nm .
Proof. Fix v (t) ∈ S. First, for each bundle q ∈ {0, 1} m , let Q q be the set of allocations where exactly the elements of q are allocated, and let Notice that regardless of the reserve prices, if q is comprised of the items allocated in the allocation of an MBARP, then Q q will be the allocation. After all, if (r 1 , . . . , r m ) are the reserve prices of an arbitrary MBARP, then it will always be the case that r j for any allocation Q = (q 1 , . . . , q n ) ∈ Q q by definition of Q q . Let R v (t) q be the subset of R m+1 such that if an MBARP is parameterized by (γ, r 1 , . . . , r m ) ∈ In other words, (γ, r 1 , . . . , r m ) ∈ R v (t) q if and only if it falls in the intersection of 2 m − 1 halfspaces.
Similarly, if q = 1, it is not hard to see that we can write R v (t) 1 as the intersection of 2 m − 1 halfspaces. The same holds for the MBARP without any one bidder's participation, leading to a total of (n + 1)2 m (2 m − 1) relevant hyperplanes. Whenever these n + 1 allocations are fixed, the profit is a fixed linear function of the m reserve prices and γ.
Proof. Let K = (n + 1) m be the total number of allocations and let p be a parameter vector where the first n components correspond to the bidder weights w j for j ∈ [n], the next n components correspond to 1/w j for j ∈ [n], the next 2 n 2 components correspond to w i /w j for all i = j, the next K components correspond to λ(Q) for every allocation Q, and the final nK components correspond to λ(Q)/w j for all allocations Q and all bidders j ∈ [n]. In total, the dimension of this parameter space is at most 2n + 2n 2 + K + nK = O(nK). Let v be a valuation vector. We claim that this parameter space can be partitioned using t = (n + 1)K 2 hyperplanes into regions where in any one region P , there exists a vector k such that profit v (p) = k · p for all p ∈ P .
To this end, an allocation Q = (q 1 , . . . , q n ) will be the allocation of the AMA so long as for all allocations Q = (q 1 , . . . , q n ) = Q. Since the number of different allocations is at most K, the allocation of the auction on v is defined by at most K 2 hyperplanes in R d . Similarly, the allocations Q −1 , . . . , Q −n are also determined by at most K 2 hyperplanes in R d . Once these allocations are fixed, profit is a linear function of this parameter space.
The proof for VVCAs follows the same argument except that we redefine the parameter space to consist of vectors where the first n components correspond to the bidder weights w j for j ∈ [n], the next n components correspond to 1/w j for j ∈ [n], the next 2 n 2 components correspond to w i /w j for all i = j, the next K = n2 m components correspond to the bidder-specific bundle boosts c j,q for every quantity vector q and bidder j ∈ [n], and the final nK components correspond to c k,q /w j for every quantity vector q and every pair of bidders j, k ∈ [n]. The dimension of this parameter space is at most 2n + 2n 2 + K + nK ≤ 2K + nK + K + nK = O(nK ).
Finally, the proof for λ-auctions follows the same argument as the proof for AMAs except there are zero bidder weights. Therefore, the parameter space consists of vectors with K components corresponding to λ(Q) for every allocation Q.
Proof. Let K = (n + 1) m be the total number of allocations and let p be a parameter vector where the first n components correspond to the bidder weights w j for j ∈ [n], the next n components correspond to 1/w j for j ∈ [n], the next 2 n 2 components correspond to w i /w j for all i = j, the next |Q| components correspond to λ(Q) for every allocation Q ∈ |Q|, and the final n|Q| components correspond to λ(Q)/w j for all allocations Q ∈ Q and all bidders j ∈ [n]. In total, the dimension of this parameter space is at most 2n + 2n 2 + |Q| + n|Q| < (n + 2)(n + |Q|) ≤ 3n(n + |Q|). We set d = 3n(n + |Q|). Fix some valuation vector v. We claim that the allocation of any Q-boosted AMA is determined by at most (n + 1)K 2 hyperplanes in R d . To see why this is, the allocation will be Q j = q j 1 , . . . , q j n where . . , q k n . This decision governing which of the K possible allocations will be the AMA allocation is defined by the K 2 hyperplanes, one per pair of distinct allocations Q j and Q k .
By a similar argument, it is straightforward to see that K 2 hyperplanes determine the allocation of any AMA in this restricted space without any one bidder's participation. This leads us to a total of (n + 1)K 2 hyperplanes which partition the space of Q-boosted AMA parameters in a way such that for any two parameter vectors in the same region, the auction allocations are the same, as are the allocations without any one bidder's participation. Once these allocations are fixed, profit is a linear function in this parameter space.
The proof for λ-auctions is very similar to that for AMAs. However, we claim that the allocation of any Q-boosted λ-auction is determined by at most (n + 1)(|Q| + 1) 2 hyperplanes in R |Q| . This is because without the bidder weights, the allocation of the Q-boosted λ-auction will either be a boosted allocation or the VCG allocation if it is not boosted. Therefore, there are only (|Q| + 1) 2 hyperplanes determining the allocation of the λ-auction, and the same number of hyperplanes determine the allocation of the λ-auction in this restricted space without any one bidder's participation. Once these allocations are fixed, profit is linear function of the λ-terms.

B Proofs from Section 3
Lemma B.1. Let X = X 1 × · · · × X d . Let F = {f p : p ∈ P} be a set of functions mapping X to R, parameterized by a set P = P 1 ×· · ·×P d . Suppose for i ∈ [d], there exists a class F i = f (i) p : p ∈ P i of functions mapping X i to R such that for any p = (p[1], . . . , p[d]) ∈ P, f p decomposes additively as Proof. Recall that for any set A ⊆ R, s = sup A if and only if: 1. For all > 0, there exists a ∈ A such that a > s − , and 2. For all a ∈ A, a ≤ s.
We will show that t = sup v∈X ,p∈P f p (v). First, we will show that condition (1) holds. In particular, we want to show that for all > 0, there exists v ∈ X and p ∈ P such that f . . , v d ) ∈ X and (p 1 , . . . , p d ) ∈ P, we may conclude that condition (1) holds.
Next, we will show that condition (2) holds. In particular, we want to show that for all v ∈ X and p ∈ P, f p (v) ≤ t. We know that f Therefore, condition (2) holds. Proof. We begin with anonymous second-price auctions, which are parameterized by a set P ⊂ R m . Without loss of generality, we may write P = P 1 × · · · × P m , where P i ⊂ R. Given a valuation vector v and an item i, let v(i) ∈ R n be all n buyers' values for item i. Let profit p (v(i)) be the profit obtained by selling item i with a reserve price of p. Notice that for any p ∈ P, . Let X i be the support of the distribution over v(i) and let U i = sup p∈P i ,v(i)∈X i profit p (v(i)). Next, let X be the support of D. By definition, since U is the maximum profit achievable via second price auctions over valuation vectors from X , we may write U = sup v∈X ,p∈P profit p (v). Since D is item-independent, we know that X = X 1 × · · · × X m . Therefore, we may apply Lemma B.1, which tells us that U = m i=1 U i . Finally, each class of functions profit p : p ∈ P i is (1, 2)-delineable, since for v(i) ∈ X i , profit v(i) (p) is linear so long as p is larger than the largest component of v(i), between the second largest and largest component of v(i), or smaller than the second largest component of v(i). By Corollary 3.2, we may conclude that for any set of samples S ∼ D N , R S (M) ≤ O U 1/N . The bound on R S (M ) follows by almost the exact same logic, except for a few adjustments. First of all, the class is defined by nm parameters coming from some set P ⊆ R nm , since there are n non-anonymous prices per item. Without loss of generality, we assume P = P 1 × · · · × P m , where P i ⊆ R n is the set of non-anonymous prices for item i. Given a set of non-anonymous prices p ∈ R n for item i, let profit p (v(i)) be the profit of selling the item the bidders defined by v(i) given the reserve prices p. Notice that profit v(i) (p) is linear so long as for each bidder j, p[j] is either larger than their value for item i or smaller than their value. Thus, the set profit p : p ∈ P i is (n, n)-delineable. Defining each U i in the same way as before, Lemma B.1 guarantees that U = m i=1 U i . Therefore, by Corollary 3.2, we may conclude that for any set of samples S ∼ D N , R S (M ) ≤ O U n log n/N . Proof. We begin with anonymous item-pricing mechanisms, which are parameterized by a set P ⊂ R m . Without loss of generality, we may write P = P 1 × · · · × P m , where P i ⊂ R. Given a valuation vector v and an item i, let v(i) ∈ R n be all n buyers' values for item i. Let profit p (v(i)) be the profit obtained by selling item i at a price of p, i.e., profit p (v(i)) = 1 {||v(i)||∞≥p} (p − c(e i )). Notice that for any p ∈ P, profit p (v) = m i=1 profit p[i] (v(i)). Let X i be the support of the distribution over v(i) and let U i = sup p∈P i ,v(i)∈X i profit p (v(i)). Next, let X be the support of D. By definition, since U is the maximum profit achievable via item-pricing mechanisms over valuation vectors from X , we may write U = sup v∈X ,p∈P profit p (v). Since D is item-independent, we know that X = X 1 × · · · × X m . Therefore, we may apply Lemma B.1, which tells us that U = m i=1 U i . Finally, each class of functions profit p : p ∈ P i is (1, 1)-delineable, since for v(i) ∈ X i , profit v(i) (p) is linear so long as ||v(i)|| ∞ ≤ p or ||v(i)|| ∞ > p. By Corollary 3.2, we may conclude that for any set of samples The bound on R S (M ) follows by almost the exact same logic, except for a few adjustments. First of all, the class is defined by nm parameters coming from some set P ⊆ R nm , since there are n non-anonymous prices per item. Without loss of generality, we assume P = P 1 × · · · × P m , where P i ⊆ R n is the set of non-anonymous prices for item i. Given a set of non-anonymous prices p ∈ R n for item i, let profit p (v(i)) be the profit of selling the item the bidders defined by v(i) given the prices p. Notice that profit v(i) (p) is linear so long as for each bidder j, p(e j ) is either larger than their value for item i or smaller than their value. Thus, the set profit p : p ∈ P i is (n, n)delineable. Defining each U i in the same way as before, Lemma B.1 in Appendix B guarantees that U = m i=1 U i . Therefore, by Corollary 3.2, we may conclude that for any set of samples S ∼ D N , R S (M ) ≤ O U n log n/N . Theorem 3.5. Let M be the set of length-item lottery menus. If the bidder is additive, D is item-independent, and the cost function is additive, then for any set S ∼ D N , Proof. For a given menu M = (M 1 , . . . , M m ) of item lotteries, let profit M i (v) be the profit achieved from menu M i . Since the cost function is additive, . Let X i be the support of the distribution D i over v(e i ) and let . By definition, since U is the maximum profit achievable via item menus over valuation vectors from X , we may write U = sup v∈X ,M ∈M profit M (v). Since D is a product distribution, we know that X = X 1 × · · · × X m . Therefore, we may apply Lemma B.1, which tells us that U = m i=1 U i . Finally, for each i ∈ [n], the class of all single-item lotteries M i is (2 , 2 )-delineable, since for v(e i ) ∈ X i , the lottery the buyer chooses depends on the +1 for j, j ∈ {0, . . . , }, and once the lottery is fixed, profit M i (v) is a linear function. , let M T be the mechanism defined such that the price of item i is 2 if i ∈ T and otherwise, its price is 0. If i ∈ T , then profit M T (v (i) ) = 2 and otherwise, profit M T (v (i) ) = 0. Therefore, the targets z (1) = · · · = z (m) = 1 witness the shattering of S by M. This example also proves that the pseudo-dimension of the class of second-price auctions with anonymous reserve prices is also at least m, since in the single-bidder case, this class is identical to M.
Next, let M be the class of item-pricing mechanisms with non-anonymous prices. We construct a set S of nm n-bidder, m-item valuation vectors that can be shattered by M . For i ∈ [m] and j ∈ [n], let v (i,j) be valuation vector where v (i,j) j (e i ) = 3 and v , let M T be the mechanism defined such that the price of item i for bidder j is 2 if (i, j) ∈ T and otherwise, it is 0. If (i, j) ∈ T , then profit M T (v (i,j) ) = 2 and otherwise, profit M T (v (i,j) ) = 0. Therefore, the targets z (i,j) = 1 for all i ∈ [m], j ∈ [n] witness the shattering of S by M. This example with the prices as reserve prices also proves that the pseudo-dimension of the class of second-price auctions with non-anonymous reserve prices is at least nm.
By a Chernoff bound, we know that Assume that it is indeed the case that We define the sets B = i : M P M v (i) > a and L = i : M P M v (i) ≤ a . We may write Therefore, Theorem B.2. Let M be the class of length-lottery menus under an additive or unit-demand bidder. Suppose the cost function is additive.
Since we are only maximizing profit over a single buyer's valuation vector v, we only need to bound the maximum revenue achievable via a single lottery. If the buyer chooses to buy a lottery (p, φ), the profit will be p − m i=1 c(e i ) · φ[i]. So long as p ≤ v · φ, the buyer will buy the lottery, so we can maximize profit by setting {v j (e i )}1 max j∈[n] {v j (e i )} ≥ c(e i ) .
Proof. Suppose the buyers are additive. Under a second-price item auction or an item-pricing mechanism, we can always obtain revenue that equals m i=1 max j∈ [n] {v j (e i )} by charging a price of max j∈[n] {v j (e i )} for each item i. However, if the cost to produce item i is greater than max j∈[n] {v j (e i )}, the seller should not sell it. The bound thus follows.

C Proofs from Section 4
Theorem 4.1. Let M be the class of non-anonymous item-pricing mechanisms over additive bidders and let w : [n] → R be a weight function such that n i=1 w (i) ≤ 1. Then for any δ ∈ (0, 1), with probability at least 1 − δ over the draw S ∼ D N , for any k ∈ [n] and any mechanism M ∈ M k , Proof. This theorem follows from the fact that M k is (km, nm)-delineable. Every mechanism in M k is defined by km parameters, one price per item per price group, and for every buyer j, the goods they are willing to buy are defined by the m hyperplanes v j (e i ) = p j (e i ) for every item i. Therefore, the theorem follows from Theorems 2.5 and 2.6, and by multiplying δ with w(k).
Two-part tariffs. Let M be the class of anonymous two-part tariff menus, by which we mean the union of all length-menus of two-part tariffs with anonymous prices. Similarly, let M be the class of non-anonymous two-part tariff menus. For a given menu M of two-part tariffs, let M be the length of its menu.
Theorem C.1. Let w : N → [0, 1] be a weight function such that w(i) ≤ 1. Then for any δ ∈ (0, 1), with probability at least 1 − δ over the draw of a set of samples of size N from D, for any mechanism M ∈ M, the difference between the average profit of M over the set of samples and the expected profit of M over D is .
Also, with probability at least 1 − δ over the draw of a set of samples of size N from D, for any mechanism M ∈ M , the difference between the average profit of M over the set of samples and the expected profit of M over D is at most .
Q-boosted λ-auctions. For the next theorem, given a λ-auction M , let Q M be the set of all allocations Q such that λ(Q) > 0.
Theorem C.2. Let M be the class of λ-auctions and let w be a weight function which maps sets of allocations Q to [0, 1] such that w(Q) ≤ 1. Then for any δ ∈ (0, 1), with probability at least 1 − δ over the draw of a set of samples of size N from D, for any mechanism M ∈ M, the difference between the average profit of M over the set of samples and the expected profit of M over D is at most .
Menu lotteries. Let M be the class of lottery menus, by which we mean the union of all lengthlottery menus. For a given lottery menu M , let M be the length of its menu.
Theorem C.3. Let w : N → [0, 1] be a weight function such that w(i) ≤ 1. Then for any δ ∈ (0, 1), with probability at least 1 − δ over the draw of a set of samples of size N from D, for any mechanism M ∈ M, the difference between the average profit of M over the set of samples and the expected profit of M over D is

D Proofs from Section 5
Example D.1 (Item-pricing mechanisms (Morgenstern and Roughgarden, 2016)). Let M be the class of anonymous item-pricing mechanisms over a single additive bidder and let p = (p 1 , . . . , p m ) be a vector of prices. In this case, we can define f  (1, p). Then the α that maximizes w p , ψ(v, α) is the α that maximizes the buyer's utility, i.e., f (1) p (v), as desired. Finally, we define f (2) p (v, α) = α, p , and we have that profit p (v) = f p (v) , as desired.
Proof. To prove this theorem, we will use the following standard notation. For a class F of realvalued functions mapping X to R, let S = v (1) , . . . , v (N ) be a subset of X . We define The pseudo-dimension of F is the size of the largest set S such that Π F (S) = 2 |S| . We also use the notation f (S) to denote the vector f (v (1) ), . . . , f (v (N ) ) . Morgenstern and Roughgarden (2016) proved the following lemma. (2016)). Suppose M is F (1) , F (2) -decomposable and a-dimensionally linearly separable. Let S = v (1) , . . . , v (N ) be a subset of X . Then To prove this theorem, we will show that max α (1) ,...,α (N ) ∈Y

Lemma D.2 (Morgenstern and Roughgarden
which means that 2 N < N 2d+a d 2 t d 2 ω, and thus N = O ((d + a) log(d + a) + d log t 2 + log ω). To this end, let α (1) , . . . , α (N ) be N arbitrary elements of Y and let z (1) , . . . , z (N ) be N arbitrary elements of R. Since M is (d, t 1 , t 2 )-divisible, we know that for each i ∈ [N ], there is a set H v (i) ,α (i) (p) is linear over P j . Since H (i) 2 ≤ t 2 for all i ∈ [N ], τ < d(N t 2 ) d (Buck, 1943). Now, consider a single connected component P j of P \ N i=1 H (i) 2 . For any sample v (i) ∈ S, we know that f (2) v (i) ,α (i) (p) is linear over P j . Let a (i) j ∈ R d and b (i) j ∈ R be the weight vector and offset such that f (2) v (i) ,α (i) (p) = a (i) j ·p+b (i) j for all p ∈ P j . We know that there is a hyperplane a v (i) ,α (i) (p) ≤ z (i) and on the other side, f (2) v (i) ,α (i) (p) > z (i) . Let H P j be all N hyperplanes for all N samples, i.e., H P j = a (i) . Notice that in any connected component P of P j \ H P j , for all i ∈ [N ], f v (i) ,α (i) (p) is either greater than z (i) or less than z (i) (but not both) for all p ∈ P .
In total, the number of connected components of P j \ H P j is smaller than dN d . The same holds for every partition P j . Thus, the total number of regions where for all i ∈ [N ], f v (i) ,α (i) (p) is either greater than z (i) or less than z (i) (but not both) is smaller than dN d · d(N t 2 ) d . In other words, . . .