Revenue maximization via machine learning with noisy data
Year: 2022

Abstract:
Increasingly, copious amounts of consumer data are used to learn high-revenue mechanisms via machine learning. Existing research on mechanism design via machine learning assumes that there is a distribution over the buyers’ values for the items for sale and that the learning algorithm’s input is a training set sampled from this distribution. This setup makes the strong assumption that no noise is introduced during data collection. In order to help place mechanism design via machine learning on firm foundations, we investigate the extent to which this learning process is robust to noise. Optimizing revenue using noisy data is challenging because revenue functions are extremely volatile: an infinitesimal change in the buyers’ values can cause a steep drop in revenue. Nonetheless, we provide guarantees when arbitrarily correlated noise is added to the training set; we only require that the noise has bounded magnitude or is sub-Gaussian. We conclude with an application of our guarantees to multi-task mechanism design, where there are multiple distributions over buyers’ values and the goal is to learn a high-revenue mechanism per distribution. To our knowledge, we are the first to study mechanism design via machine learning with noisy data as well as multi-task mechanism design.

heading: 1 Introduction
text: Revenue maximization in multi-item settings is one of the most important, long-standing open problems in mechanism design. In Bayesian Mechanism Design, there is a set of items for sale and an underlying distribution defining a set of agents’ values for the items. A mechanism determines which buyers receive which items and what they pay. For decades, research in economics has assumed that the mechanism designer must know the exact distribution over buyers’ values. An explosion of research [e.g., 1, 4, 19, 20, 25, 26, 28, 30, 31, 33, 37, 40, 44–48, 51] has relaxed this strong assumption: instead, the distribution is unknown and the mechanism designer only has a training set of i.i.d. samples. Using the training set, the goal is to learn a mechanism with high expected revenue. Learning-based mechanism design is on the verge of taking over as the main tool for designing high-revenue mechanisms for selling items—a cornerstone of many modern enterprises.
Motivated by recent literature on the brittleness of deep learning models in the face of imperceptible noise [32, 41, 52], an important question is whether adversarial noise has the same effect in learningbased mechanism design. Learning methods deployed in real-world settings to design mechanisms
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
must be robust to minute noise in the data. We provide guarantees for learning mechanisms with high expected revenue in the face of an adversary that can add arbitrarily correlated noise to the training set; we only require that the noise has bounded magnitude or is sub-Gaussian. In contrast, classic learning-theoretic results typically rely on the stronger assumption that the training samples are independent.

heading: 1.1 Summary of main contributions and overview of techniques
text: We set out to determine whether imperceptible adversarial noise in the training set can cause a catastrophic loss in the learned mechanism’s expected revenue. Our main contribution is a sensitivity analysis of revenue with respect to the noise’s magnitude, which answers this question in the negative. Our results apply to empirical revenue maximization, the canonical approach to learning-based mechanism design. To our knowledge, we are the first to study learning-based mechanism design under adversarial noise. We provide guarantees for optimizing revenue over several classic mechanism classes: second-price auctions with non-anonymous reserves under additive buyers, single-priced lottery mechanisms under unit-demand buyers, and item-pricing mechanisms under unit-demand buyers. These classes have been studied extensively [e.g., 6, 18, 24, 46, 51] and can be viewed as hypothesis classes, just as DNNs correspond to a particular (brittle) type of hypothesis class. In some settings, mechanisms from these classes have been shown to provide approximately optimal revenue [22, 23, 35, 39].
The key challenge we face is that revenue functions are extremely sensitive to small perturbations of the buyers’ values. In a second-price auction, for example, slightly shifting the highest bid from below to above the reserve price can cause an arbitrarily large drop in revenue, as illustrated in Figure 1. The set of bidders whose bids are above their reserve prices can completely change when even an infinitesimal amount of noise is added, radically altering the analytical form of the revenue function. This is unlike most functions that we understand well from a learning-theoretic perspective, which generally are smooth, continuous, or—more broadly—exhibit a straightforward connection between parameters and output value. Despite the volatility of these revenue functions, we nonetheless are able to prove bounds on the revenue loss incurred by optimizing over a noisy training set.
Our second main contribution is an application of our guarantees to multi-task mechanism design. To our knowledge, we are the first to study this problem. The existing literature on mechanism design via machine learning assumes that there is a single distribution defining the buyers’ values. Often, however, the mechanism designer may be interested in designing high-revenue mechanisms for multiple related distributions. Each distribution thus defines a distinct learning task. The goal is to leverage the similarity between the distributions to learn a high-revenue mechanism per distribution. Multi-task learning has proven useful in fields such as Computer Vision and Natural Language Processing [53], and we demonstrate its value in mechanism design as well. Our main technical insight is that we can transform training instances from one task into slightly noisy training instances for another task and make use of our near-optimality guarantees under noised samples.

heading: 1.2 Related research
text: Adversarial Machine Learning: A prominent line of research on machine learning in the presence of noise studies the case where some fraction of the training data may be noisy (data poisoning). Research in this vein includes settings where every instance can be corrupted with probability η < 1 [e.g., 3] and where an η-fraction of the training data can be corrupted [e.g., 16, 27]. Meanwhile, in our setting, every sample may be adversarially perturbed with probability 1, not just an η-fraction, though we require that the perturbation be bounded. Another line of research, especially prominent in Computer Vision, studies the case where the test data can be adversarially perturbed within, for example, an `p-ball [32, 41, 52]. We, on the other hand, are concerned with noisy training data and face the unique challenges imposed by mechanism design.
Mechanism Design with Noised Distributions: While the robustness of mechanism design in the face of model uncertainty has been well studied (see for instance work by Bergemann and Morris [14] and Bergemann and Schlag [15]), to our knowledge, there has been relatively less work done on mechanism design via machine learning in the particular setting where samples are not necessarily drawn i.i.d. from the true distribution. The paper most closely related to ours is that by Cai and Daskalakis [20], who show that given access to a noisy distribution, it is possible to learn a mechanism with high expected revenue over the true distribution if the Kolmogorov distance between the noisy and true distributions are small. One might hope that the uniform distribution over the noisy training data could constitute the noisy distribution, but the Kolmogorov distance between this empirical distribution and the true distribution could be as large as 1, so these results do not apply to our setting. Moreover, we note that Cai and Daskalakis [20] makes the stronger assumption that the buyers’ values follow a product distribution, whereas our assumed noise model allows for arbitrarily correlated distributions.
Multi- vs Single-item Mechanism Design: Further afield, Huang et al. [38] and Guo et al. [33] have also studied mechanism design under noisy settings, albeit under single-item settings. By contrast, we study a wider and different set of multi-item mechanism classes including multi-item lotteries and multi-item item-pricing mechanisms.
The past few decades of research on revenue-maximizing multi-item mechanism design has demonstrated that results and intuition from the single-item setting do not always carry over to the multi-item setting. And we see that this is the case in our paper as well. For example, an item-pricing mechanism for a single item would have a straight-forward stability analysis (similar to the analysis of a single-item anonymous second-price auction that we include for intuition in Appendix B.1). With multiple items and unit-demand buyers, however, stability does not even hold. Therefore, intuition from the single-item case does not carry over to the multi-item case, and we must use completely different analysis techniques.
Dispersion: The technique needed is that of dispersion (section 3.4). Our bounds improve based on how “nice” the distribution over buyers’ values is, quantified by dispersion [5]. Dispersion has primarily been used to provide regret bounds [5, 8]. Balcan et al. [7] also use dispersion in mechanism design, though for a very different problem: estimating how much utility an agent can gain by misreporting their value in a manipulable mechanism.
The appendix summarizes additional related work on mechanism design with side information, multi-task learning, transfer learning, and approximate incentive compatibility.

heading: 2 Notation
text: There are n buyers and m items for sale. Each buyer i ∈ [n] has a value for each item j ∈ [m], denoted as vij ≥ 0. We analyze unit-demand and additive buyers. If buyer i is unit-demand, he is only interested in obtaining one item, so his value for a bundle b ⊆ [m] of goods is equal to the maximum value he has for any item in b, maxj∈b vij . If buyer i is additive, his value for a bundle b ⊆ [m] is ∑ j∈b vij . We use the notation vi = (vi1, . . . , vim) to denote buyer i’s values for all m items and v = (v1, . . . ,vn) ∈ Rnm to denote all n buyers’ values. When there is only one item, we use the notation v = (v1, . . . , vn) ∈ Rn, where vi ∈ R is buyer i’s value for the item.
We study mechanism classes parameterized by vectors r ∈ Rd for some d (for example, the class of second-price auctions parameterized by non-anonymous reserves r). The mechanisms we analyze
are dominant-strategy incentive compatible, so we assume the bids equal the buyers’ true values. We denote the revenue of the mechanism defined by r when the buyers’ values equal v by revr(v). For simplicity of notation, we assume revr(v) is in [0, 1] though our results can be extended to the case where revr(v) ∈ [0, H] for some H (all bounds must simply be multiplied by H).

heading: 3 Learning under adversarial noise
text: In this section, we study mechanism design via machine learning when the data is corrupted. Let S = { v(1), . . . ,v(L) } ⊂ Rnm≥0 be a set of valuation vectors drawn from an unknown distribution D.
Our learning algorithm receives a poisoned training set S ′ = { w(1), . . . ,w(L) } ⊂ Rnm≥0 .
Bounded Noise Model: To model the imperceptible noise that corrupts the bids, we assume the bounded noise model that is commonly assumed in adversarial defense literature. That is, for some known > 0, all samples ` ∈ [L], all bidders i ∈ [n], and all items j ∈ [m], w(`)ij ∈ [ v (`) ij − , v (`) ij ] ,
or more succinctly, v(`) − ≤ w(`) ≤ v(`). (If we only know that ∥∥v(`) −w(`)∥∥∞ ≤ , we can shift all bids in each vector w(`) down by , in which case v(`) − 2 ≤ w(`) ≤ v(`).). Our goal is to use the noisy set S ′ to learn a mechanism with high expected revenue over D. We provide some more motivating factors for our choice of the noise model in the context of mechanism design. Besides its prevalence in adversarial learning literature, (1) Such noise may arise when one is using estimated bids to learn auction parameters. We give a concrete example in Section 4 where we study multi-task mechanism design. (2) The noise may result from bounded rationality on the part of the bidders, leading to small, seemingly-innocuous differences between the buyers’ true values and reported values. (3) Lastly, we note that our results can immediately be extended to cover unbounded standard noise models such as sub-Gaussian noise. In this case, suppose that each element of each vector v(i) ∈ S is perturbed by subG(σ2) to obtain the noisy vector w(i). Then with probability 1 − δ, for all i ∈ [L], ||w(i) − v(i)||∞ ≤ σ √ 2 log 2Lnmδ . The noise need not be independent. Therefore, all of our results hold with (high) probability 1− 2δ over the draw of the true values S and the noise for = 2σ √ 2 log 2Lnmδ .
Our Approach: We begin by fixing a mechanism class parameterized by vectors r ∈ Rd for some d (for example, the class of second-price auctions parameterized by non-anonymous reserves r). Given the training set S ′, the most widely used learning algorithm is empirical revenue maximization (ERM), which returns the parameter setting r̂′ that maximizes average empirical revenue over S ′. This algorithm will be the subject of our study. Throughout this section, we analyze the following key question: what is the difference between the expected revenue of the mechanism defined by r̂′, Ev∼D [revr̂′(v)], and that of the optimal mechanism in the class, maxr∈Rd E [revr(v)]? Another key aspect of learning besides optimality is sample complexity. In machine learning beyond the context of mechanism design, prior research [e.g., 49] has shown that a large increase in sample complexity is needed to handle noise with bounded `∞-norm. By contrast, under the same noise assumption, we show that empirical revenue maximization can achieve near-optimal revenue without significantly higher sample complexity. This exposes a notable contrast between the two learning tasks. We provide lower bounds showing that ERM’s loss has an optimal dependence on the noise .

heading: 3.1 Robustness
text: We begin by providing guarantees for any mechanism class that satisfies a notion of robustness, which helps us isolate exactly the properties we need to prove that robust revenue optimization is possible. A class is robust if it satisfies two properties. The first is a stability property. Let r̂ be the empirically optimal parameter setting over the set S of true samples, which means that of all r ∈ Rd, average revenue over S is maximized when r = r̂. Let r̂′ be the empirically optimal parameter vector over the noisy set S ′. Stability is satisfied when the average revenues of r̂ and r̂′ over S are close. Our second property relies on a classic learning-theoretic notion of convergence. It is satisfied when, for every parameter vector r, average revenue over the set S is close to expected revenue. Although convergence bounds have been derived in prior research for the mechanism classes we analyze [6, 46], a convergence bound alone does not imply any guarantees whatsoever for optimization with noisy
data. This is why we introduce the separate notion of stability, which has not been previously studied in the automated mechanism design literature. The challenge then lies in proving that a variety of mechanism classes satisfy stability. To begin, we define the two properties formally as follows:
Definition 3.1. Given two functions p : [0, 1] × Z2 → R and q : [0, 1] × Z3 → R, we say that a mechanism class is p-stable and q-convergent if the following conditions hold:
1. p-stable. For any L ≥ 1, let S = { v(1), . . . ,v(L) } ⊂ Rnm≥0 and S ′ = { w(1), . . . ,w(L) } ⊂ Rnm≥0
be two arbitrary sets of vectors such that v(`) − ≤ w(`) ≤ v(`) for all ` ∈ [L]. Let r̂ and r̂′ be the empirically optimal parameter vectors over S and S ′: r̂ = argmaxr∈Rd ∑L `=1 revr ( v(`) ) and
r̂′ = argmaxr∈Rd ∑L `=1 revr ( w(`) ) . We require that on average over S , the revenues of r̂ and r̂′
are close: 1L ∑L `=1 revr̂ ( v(`) ) − revr̂′ ( v(`) ) ≤ p( , n,m).
2. q-convergent. For any L ≥ 1 and δ ∈ (0, 1), with probability 1− δ over the draw S ∼ DL, for every vector r ∈ Rd, the difference between the average revenue over S and the expected revenue is at most q(δ, L, n,m). In other words, ∣∣ 1 L ∑ v∈S revr(v)− E [revr(v)] ∣∣ ≤ q(δ, L, n,m). If a mechanism class is p-stable and q-convergent, then the expected revenue of the empirically optimal mechanism over the noisy samples S ′ is close to the expected revenue of the optimal mechanism in the class. For completeness, the proof is in Appendix B.
Fact 3.2. Fix a p-stable and q-convergent mechanism class. Let S = { v(1), . . . ,v(L) } and S ′ ={
w(1), . . . ,w(L) }
be two sets of valuation vectors such that for all ` ∈ [L], v(`) − ≤ w(`) ≤ v(`). Let r̂′ be empirically optimal over S ′: r̂′ = argmaxr∈Rd ∑L `=1 revr ( w(`) ) . With probability 1− δ over S ∼ DL, maxr∈Rd Ev∼D [revr(v)]− Ev∼D [revr̂′(v)] ≤ p( , n,m) + 2q(δ, L, n,m).
We now prove that several mechanism classes are stable: second-price auctions with non-anonymous reserves and lotteries. (For intuition, we also analyze the simpler class of second-price auctions with anonymous reserves in Appendix B.1.) Table 1 summarizes our results.

heading: 3.2 Non-anonymous second-price auctions
text: We prove that second-price auctions with non-anonymous reserves and additive bidders are robust. In the single-item setting, this auction is defined by a vector r ∈ Rn, where ri is bidder i’s reserve price. Each bidder submits a bid and the mechanism discards all bidders whose bids are smaller than their reserves. If there are bidders remaining, the highest bidder, say bidder i, wins and pays the maximum of the second-highest remaining bid and ri (or ri if there are no other remaining bids). In the multi-item case, there is only one copy of each item and there is a separate auction per item. The mechanism is defined by r = (r1, . . . , rm) ∈ Rnm, where rj ∈ Rn is the reserve vector for item j.
We begin by analyzing single-item auctions, which then implies guarantees for multiple items. The key challenge is that the set of bidders whose bids are above their reserves can completely change when even infinitesimal noise is added, radically altering the analytical form of the revenue function.
Theorem 3.3. Single-item non-anonymous second-price auctions are p-stable with p( , n,m) = 2 . Proof. For any L ≥ 1, let S = { v(1), . . . ,v(L) } ⊂ Rn≥0 and S ′ = { w(1), . . . ,w(L) } ⊂ Rn≥0 be two sets of valuation vectors such that v(`) − ≤ w(`) ≤ v(`) for all ` ∈ [L]. Let r̂′ be the empirically optimal reserve vector over S ′ and let r̂ be empirically optimal over S . This proof relies on two key lemmas. The first states that if we shift the reserve vector r̂—which is empirically optimal over S—down by an additive factor of = ( , . . . , ) ∈ Rn and apply it to the valuations in S ′, little revenue is lost. We use the standard notation 〈x〉 = max{x, 0}. The full proof is in Appendix B.2.
Lemma 3.4. Let r = (〈r̂1 − 〉 , . . . , 〈r̂n − 〉) . If revr̂ ( v(`) ) > 0, then revr ( w(`) ) ≥
revr̂ ( v(`) ) − 2 . Proof sketch of Lemma 3.4. Suppose that revr̂ ( v(`) ) > 0. Let i be the winner under the values v(`) and reserve r̂. Since v(`)i ≥ r̂i, we know that w (`) i ≥ 〈v (`) i − 〉 ≥ 〈r̂i − 〉, so under the values w(`) and reserve r , there is at least one bidder whose bid is at least his reserve. Let i′ be the winner under the valuation vector w(`) and reserve r . We split this proof into four cases that depend on:
1. Whether or not i = i′, and 2. Whether—under v(`) and r̂—there is another bidder besides i whose bid is at least his
reserve (in other words, whether or not {t : v(`)t ≥ r̂t, t 6= i} = ∅). In the first case, i = i′ and {t : v(`)t ≥ r̂t, t 6= i} 6= ∅. Let k be the index of the second-highest bidder in v(`) whose bid is above his reserve in r̂: k = argmaxt 6=i{v (`) t : v (`) t ≥ r̂t}. This means that revr̂(v(`)) = max{r̂i, v(`)k }. Since v (`) k ≥ r̂k, we have that w (`) k ≥ 〈v (`) k − 〉 ≥ 〈r̂k − 〉. Since k 6= i and i = i′, it must be that k 6= i′, so {t : w(`)t ≥ 〈r̂t − 〉, t 6= i′} 6= ∅ (in particular, the set contains k). Let k′ be the index of the second-highest bidder inw(`) whose bid is above his reserve in r : k′ = argmaxt 6=i′{w (`) t : w (`) t ≥ 〈r̂t − 〉}, which means that revr (w(`)) = max{r̂i′ − , w (`) k′ }. Since k ∈ {t : w(`)t ≥ 〈r̂t − 〉, t 6= i′}, we know that w (`) k′ ≥ w (`) k ≥ v (`) k − . Putting this all together, we prove that revr (w (`)) ≥ max{r̂i − , w(`)k′ } ≥ max{r̂i, v (`) k } − 2 = revr̂(v(`))− 2 . We prove the other three cases in the appendix.
We use Lemma 3.4 to continue Theorem 3.3’s proof. Let I be the set of indices ` such that revr̂ ( v(`) ) > 0. By Lemma 3.4, ∑L `=1 revr̂ ( v(`) ) = ∑ `∈I revr̂ ( v(`) ) ≤ ∑ `∈I revr ( w(`) ) +
2L ≤ ∑L `=1 revr ( w(`) ) + 2L ≤ ∑L `=1 revr̂′ ( w(`) ) + 2L .
Next, we prove that for any reserve vector r, revenue under the samples v(`) will only be higher than revenue under the samples w(`), which intuitively makes sense since w(`) ≤ v(`). The proof, which has a similar structure as the proof of Lemma 3.4, is in Appendix B.2.
Lemma 3.5. For all samples ` ∈ [L] and reserve vectors r ∈ Rn, revr ( w(`) ) ≤ revr ( v(`) ) . Since ∑L `=1 revr̂ ( v(`) ) ≤ ∑ revr̂′ ( w(`) ) + 2L , Lemma 3.5 implies that the theorem holds.
We next use Theorem 3.3 to prove stability guarantees in the case where there are multiple items and n additive buyers. It follows from the fact that the mechanism’s revenue decomposes additively over the items. The proof is in Appendix B.2.
Theorem 3.6. The set of multi-item non-anonymous second-price auctions under n additive buyers is p-stable with p( , n,m) = 2m .
Theorem 3.6 and the fact that the class is q-convergent with q(δ, L, n,m) = O (√
1 L ( nm log(nm) + log 1δ )) [46] implies that optimization under noise is possible:
Corollary 3.7. Let S = { v(1), . . . ,v(L) } ⊂ Rnm≥0 and S ′ = { w(1), . . . ,w(L) } ⊂ Rnm≥0 be two sets
such that for all ` ∈ [L], v(`) − ≤ w(`) ≤ v(`). Let r̂′ = argmaxr∈Rnm ∑L `=1 revr ( w(`) ) . With
high probability over S ∼ DL, maxr∈Rnm Ev∼D [revr(v)]−Ev∼D [revr̂′(v)] = Õ ( m + √ nm L ) .
This dependence on m is tight: no algorithm has better error than m . Therefore, empirical revenue maximization provides an optimal dependence on the error term . The proof is in Appendix B.2.
Proposition 3.8. Fix an arbitrary error term . For any deterministic algorithm A that takes as input a training set S ⊆ Rnm and returns a vector of non-anonymous reserves A(S) ∈ Rnm, there exists a distribution D such that with probability 1 over the draw S = { v(1), . . . ,v(L) } ∼
DL, maxr∈Rnm E [revr(v)] − E [ revA(S′)(v) ] = Ω(m ) for some noisy training set S ′ ={
w(1), . . . ,w(L) } such that ∥∥v(`) −w(`)∥∥∞ ≤ for all ` ∈ [L].

heading: 3.3 Lotteries
text: We next prove that single-priced lottery mechanisms satisfy our stability and convergence conditions. We analyze a setting where there are n unit-demand buyers with values for m items. Unlike the previous section, we assume there are at least n units of each good available. A single-priced lottery is defined by n(m+1) parameters: for each buyer i, there is a price ri0 ∈ R≥0 and a set of probabilities ri1, . . . , rim ∈ [0, 1] with ∑m j=1 rij = 1. If the buyer chooses to pay ri0, she will receive one item
J ∈ [m], and Pr[J = j] = rij . Therefore, her expected utility is ∑m j=1 vijrij − ri0. She will choose to participate in the lottery so long as her expected utility is at least 0. We prove that this mechanism class satisfies our stability and convergence conditions. The full proof is in Appendix B.3.
Theorem 3.9. The set of lotteries with n unit-demand buyers is p-stable with p( , n,m) = n .
Proof sketch. We sketch the proof that p( , n,m) = in the single-buyer setting (n = 1) and for the sake of generality, we prove the guarantee for n buyers in the appendix. For any L ≥ 1, let S = { v(1), . . . ,v(L) } ⊂ Rm≥0 and S ′ = { w(1), . . . ,w(L) } ⊂ Rm≥0 be two arbitrary sets of valuation vectors such that v(`) − ≤ w(`) ≤ v(`) for all ` ∈ [L]. Let r̂ = (r̂0, r̂1, . . . , r̂m) be the empirically optimal parameter vector over the set S and let r̂′ = (r̂′0, r̂′1, . . . , r̂′m) be the empirically optimal parameter vector over the set S ′. We prove that 1L ∑L `=1 revr̂ ( v(`) ) − revr̂′ ( v(`) ) ≤ .
We first prove that if we shift the price r̂0 down by and evaluate the resulting lottery over S ′, little revenue is lost. Specifically, letting r = (max {r̂0 − , 0} , r̂1, . . . , r̂n) we prove that if revr̂ ( v(`) ) > 0,
then revr ( w(`) ) ≥ revr̂ ( v(`) ) − . This implies that ∑L `=1 revr̂ ( v(`) ) ≤ ∑L `=1 revr ( w(`) ) +L .
Since r̂′ is empirically optimal under S ′, ∑L `=1 revr̂ ( v(`) ) ≤ ∑L `=1 revr̂′ ( w(`) ) + L .
Next, we prove that for any parameter vector r, revenue under the samples v(`) will only be higher than revenue under the samples w(`). Specifically, for every ` ∈ [L] and any parameter vector r ∈ Rm+1, revr ( w(`) ) ≤ revr ( v(`) ) . This implies that ∑L `=1 revr̂ ( v(`) ) ≤ L + ∑L `=1 revr̂′ ( v(`) ) . By a natural generalization of prior research [6], q(δ, L, n,m) = O (√
1 L ( nm log(nm) + log 1δ )) .
Fact 3.2 and Theorem 3.9 imply our main result for this section—that the class of lotteries is robust: Corollary 3.10. Let S = { v(1), . . . ,v(L) } ⊂ Rnm≥0 and S ′ = { w(1), . . . ,w(L) } ⊂ Rnm≥0 be two sets
such that for all ` ∈ [L], v(`)− ≤ w(`) ≤ v(`). Let r̂′ = argmaxr∈Rn(m+1) ∑L `=1 revr ( w(`) ) .With
high probability over S ∼ DL, maxr∈Rn(m+1) Ev∼D [revr(v)]− E [revr̂′(v)] = Õ ( n + √ nm L ) .
This dependence on n is tight: no algorithm has better error than n . The proof is in Appendix B.3.
Proposition 3.11. Fix an arbitrary error term . For any deterministic algorithm A that takes as input a training set S ⊆ Rnm and returns a vector of lottery parameters A(S) ∈ Rn(m+1), there exists a distribution D such that with probability 1 over the draw S = { v(1), . . . ,v(L) } ∼
DL, maxr∈Rn(m+1) E [revr(v)] − E [ revA(S′)(v) ] = Ω(n ) for some noisy training set S ′ ={
w(1), . . . ,w(L) } such that ∥∥v(`) −w(`)∥∥∞ ≤ for all ` ∈ [L].

heading: 3.4 Guarantees via dispersion
text: We now provide guarantees for the class of item-pricing mechanisms under unit-demand buyers, under which revenue is a particularly volatile function. In fact, the p-stability property does not hold for any non-trivial stability function p. We show that we can use another tool—called dispersion [5]— to obtain guarantees for learning with a noisy dataset. Therefore, we illustrate that p-stability is a sufficient but not necessary condition for obtaining robustness guarantees for a wide range of mechanism classes. We showcase this for item-pricing mechanisms.
Item-pricing mechanisms: Let there be n buyers and m items and as in Section 3.2, we assume there is only one unit of each item for sale. There is a non-anonymous price rij ∈ R for each buyer i ∈ [n] and each item j ∈ [m]. First, buyer 1 arrives and buys the item j ∈ [m] that maximizes his utility v1j − r1j (or chooses not to buy if v1j < r1j for all items j ∈ [m]). Next, buyer 2 arrives and selects the item among the remaining that maximizes his utility v2j − r2j (or chooses not to buy). This process continues for each buyer i ∈ [n]. As in the previous section, we use the notation revr(v) to denote the revenue of the mechanism with prices r ∈ Rnm when the buyers have values v ∈ Rnm. Under item-pricing mechanisms, we face an immediate obstacle which is that p-stability does not necessarily hold for any non-trivial choice of the function p: the empirically optimal prices over the noisy set S ′ might have terrible revenue on average over the true set S (Lemma B.11 in Appendix B.4). The primary challenge in proving a stability guarantee is that an agent may have very different values for two items but very similar utilities given a set of prices r. If we add a little noise to the buyer’s values, their preference ordering over the items may flip. In turn, this may cause the buyer to select a low-cost item instead of a high-cost item, thus triggering a sharp drop in revenue. As a result, average revenue over a noisy training set may be completely different from average revenue over the uncorrupted training set. If, however, given any price vector r, the buyers’ utilities across items are not too similar (they are “dispersed”), their preferences will not change if a bit of noise is added to their values. Below, we formally capture this notion of dispersion.
Definition 3.12 (( , k)-dispersion). Let S = { v(1), . . . ,v(L) } ⊂ Rnm≥0 be a set of valuation vectors. We say that S is ( , k)-dispersed if for any price vector r ∈ Rm, there are at most k valuation vectors in S such that for some buyer i ∈ [n], either: 1. For some item pair j, j′ ∈ [m], buyer i’s utility for item j is within of her utility for item j′, or 2. Buyer i’s utility for some item j is between 0 and .
The parameter k allows for some slack: for some—but not all—of the valuation vectors in S, the buyers’ utilities can concentrate. Later in this section, we demonstrate that dispersion holds under mild assumptions. First, we provide a guarantee based on dispersion for optimizing prices using a noisy training set. The full proof is in Appendix B.4.
Theorem 3.13. Let S = { v(1), . . . ,v(L) } ∼ DL be a set of (2 , k)-dispersed vectors. Let S ′ ={
w(1), . . . ,w(L) } ⊂ Rnm≥0 be another set such that for all ` ∈ [L], ∥∥v(`) −w(`)∥∥∞ ≤ . Let r̂′ be empirically optimal over S ′: r̂′ = argmaxr∈Rnm ∑L `=1 revr ( w(`) ) . With probability 1− δ over the
draw of S, maxr∈Rnm Ev∼D [revr(v)]− E [revr̂′(v)] = O ( k L + √ 1 L ( nm log(nm) + log 1δ )) .
Proof sketch. We first prove that for any price vector r, average revenue over S is within kL of average revenue over S ′, for the following reason. Due to dispersion, for most of the valuation vectors v(`) ∈ S, the buyers will choose to buy the same set of goods regardless of whether their values are defined by v(`) or w(`), so the revenue remains constant. For at most k valuation vectors in S, the allocation may change arbitrarily, but revenue is always bounded in the interval [0, 1], which is why the bound contains the term kL . Finally, to relate average and expected revenue, we use a generalization bound from prior research [46] which equals the second summand of our bound.
This result raises an important question: when will a set of valuations be dispersed? One example, also observed in prior research [5], is when the distribution over buyers’ values is relatively “smooth” (a la smoothed analysis [50]), formalized as follows.
Definition 3.14. For any distribution over an abstract set X with probability density function f : X → R≥0, the density function is κ-bounded if maxx∈X f(x) ≤ κ.
The proof of the following lemma is in Appendix B.4. Lemma 3.15. Suppose that for every buyer i ∈ [n] and every pair of items j, j′ ∈ [m], buyer i’s values for items j and j′ have a κ-bounded joint density function. Then for any > 0, with probability 1 − δ over the draw S = { v(1), . . . ,v(L) } ∼ DL, the set S is (2 , k)-dispersed with
k = 4Lnm2κ +O ( nm2 √ L log nmδ ) .
Theorem 3.13 and Lemma 3.15 imply learning guarantees for optimizing with noisy data when dispersion holds, even for these extremely volatile revenue functions.

heading: 4 Multi-task learning
text: We now show how our results from the previous section apply to multi-task mechanism design.
Setup: In this setting, there are T tasks, and each task t ∈ [T ] is defined by a distribution D(t) over buyers’ values. Each distribution could represent, for example, buyers from different regions or market segments. The learning algorithm receives a training set sampled from each task’s distribution. Given a mechanism class parameterized by vectors r ∈ Rd (which equal, for example, reserve prices) and the T training sets, our goal is to learn a parameter setting r(t) for each task t with high expected revenue over D(t). In particular, maxr∈Rd Ev∼D(t) [revr(v)]−Ev∼D(t) [revr(t)(v)] should be small. Task relatedness: If the distributions are completely unrelated, there is no hope that sharing information across tasks could improve learning. Thus, we require some notion of “task-relatedness”. Under our model of task-relatedness, buyers’ values across tasks are similar up to additive shifts which represent, for example, differences in their income brackets. More formally, for each buyer i ∈ [n] and item j ∈ [m], there is an underlying distribution Dij over R≥0. Let D = ×i,jDij denote the cross product of these nm distributions. Each task t ∈ [T ] is defined by an unknown vector of common-base values b(t) ∈ Rn. Intuitively, when b(t)i is large, buyer i tends to be willing to pay more for items, and when b(t)i is small, buyer i tends to be frugal. This model is inspired by the well-studied common-base-value model [9, 24]. For each task t ∈ [T ], our learning algorithm receives L samples v(1,t), . . . ,v(L,t) ∈ Rnm. Each sample v(`,t) is generated by sampling z(`,t) ∼ D and defining buyer i’s value for item j to be v(`,t)ij = b (t) i + z (`,t) ij . This defines a distribution D (t) ij over buyer i’s value for item j. We use the notation D(t) = ×i,jD(t)ij to denote the cross product of these nm distributions for task t. The learning algorithm does not know the vectors b(t) or z(`,t); it only observes the valuation vectors v(`,t). Throughout this section, we use the (slight abuse of) notation b(t) + z(`,t) to denote v(`,t). In Appendix D, we supply empirical evidence that demonstrates that this is a reasonable model of task-relatedness on real-world auction data.
Sample bootstrapping: Our multi-task approach follows from the observation that for each task t ∈ [T ], St = { b(t) + z(`,τ) : τ ∈ [T ], ` ∈ [L] } is a training set of LT samples from the tth task’s distribution D(t) since each vector z(`,τ) is sampled from D. However, we cannot compile this training set since we do not know the base values b(t). Nonetheless, in Appendix C, we show that it is straightforward to compute a set of vectors S ′t = { w(`,t,τ) : ` ∈ [L], τ ∈ [T ] } that closely approximate* the vectors in St: with high probability, for all pairs of tasks t, τ ∈ [T ] and indices ` ∈ [L],
∥∥b(t) + z(`,τ) −w(`,t,τ)∥∥∞ = Õ (√ 1Lm). From our results in Section 3, we know that it is possible to learn a mechanism with high expected revenue over the distribution D(t) using the noisy training set S ′t. We summarize the resulting guarantees below. All proofs are in Appendix C.
Multi-item non-anonymous second-price auctions. Our results from Section 3.2 imply the following guarantee for learning a high-revenue multi-item second-price auction with non-anonymous reserves under additive bidders. Theorem 4.1. For each task t ∈ [T ], let r̂′t be the empirically optimal reserve vector over the set S ′t: r̂′t = argmaxr∈Rnm ∑L `=1 ∑T τ=1 revr ( w(`,t,τ) ) . With probability 1− δ, for every task t ∈ [T ],
maxr∈Rnm Ev∼D(t) [ revr(v)− revr̂′t(v) ] = Õ (√ 1 LT ( nm+ log Tδ ) + mL log nT δ ) .
*In some cases, we show that it is also possible to exactly recover the vectors in St (Appendix C.2).
This theorem implies that for any γ ∈ (0, 1), when L = Ω̃ ( m/γ2 ) and T = Ω̃(n), the revenue of the auction defined by the reserves r̂′t is within γ of optimal: maxEv∼D(t) [revr(v)] − Ev∼D(t) [ revr̂′t(v) ] ≤ γ. In contrast, the best-known single-task sample complexity guarantee re-
quires L = Ω̃ ( nm/γ2 ) [46]†. Our per-task sample complexity is smaller by a multiplicative factor equalling the number of buyers.
Lotteries. Our results from Section 3.3 imply that under unit-demand buyers, optimizing lottery parameters using the noisy training sets S ′t results in nearly optimal revenue. Theorem 4.2. For each task t, let r̂′t be the empirically optimal lottery parameter vector over the set S ′t: r̂′t = argmaxr∈Rn(m+1) ∑L `=1 ∑T τ=1 revr ( w(`,t,τ) ) . With probability 1 − δ, for every t ∈ [T ],
maxr∈Rn(m+1) Ev∼D(t) [ revr(v)− revr̂′t(v) ] = Õ (√ 1 LT ( nm+ log Tδ ) + n 2 Lm log nT δ ) . Theorem 4.2 implies that for any γ ∈ (0, 1), when L = Ω̃ ( n/γ2 ) , T = Ω̃(m), and there are more items than buyers (m > n), the revenue of the lottery defined by r̂′t is within γ of optimal: maxEv∼D(t) [revr(v)]− Ev∼D(t) [ revr̂′t(v) ] ≤ γ. Meanwhile, the best-known single-task sample
complexity bound requires L = Ω̃ ( nm/γ2 ) [6]. Our approach’s per-task sample complexity is better by a multiplicative factor of m.

heading: 5 Conclusions
text: We provided guarantees for learning high-revenue mechanisms with noisy data. Learning in the presence of noise is particularly challenging in mechanism design because revenue functions are volatile, exhibiting many jump discontinuities. We were nonetheless able to provide revenue guarantees only under the assumption that the magnitude of the noise is bounded or sub-Gaussian. Our guarantees apply to the dominant approach to learning-based mechanism design: empirical revenue maximization (ERM). We demonstrated the application of our guarantees to multi-task mechanism design. We thus initiated the study of both learning with noisy data and multi-task learning in mechanism design.
Future directions: (1) We focused on learning with bounded noise rather than noise of arbitrary magnitude (the full adversarial game). This is an exciting future direction if any guarantees are indeed possible when bids may be arbitrarily altered, and may require the development of new learning algorithms beyond ERM. (2) A major bottleneck for empirical evaluations in learningbased mechanism design is the lack of public datasets—we are only aware of one, from eBay [44]. We focused on theoretical guarantees, but applied research on robust and multi-task learning in mechanism design is a great future direction. (3) Building on our results for multi-task learning, what other notions of task-relatedness permit strong multi-task sample complexity bounds?
Negative societal impacts: This paper falls into the broader line of research on using machine learning for mechanism design. In this direction, collecting individuals’ data and using it to fine-tune prices could have negative privacy implications. The development of privacy-preserving approaches to mechanism design via machine learning is a great direction for future research.

heading: 6 Checklist
text: 1. For all authors... (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s
contributions and scope? [Yes] (b) Did you describe the limitations of your work? [Yes] We discussed the limitations of
our work in the “Future directions” paragraph of Section 5. (c) Did you discuss any potential negative societal impacts of your work? [Yes] We
discussed any potential negative societal impacts in Section 5.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [Yes] (b) Did you include complete proofs of all theoretical results? [Yes] We provide full,
detailed proofs of all results. Due to space constraints, the main body includes proof sketches of some of the results, and the full proofs of these results are in the appendix.
3. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either in the supplemental material or as a URL)? [N/A] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they
were chosen)? [N/A] (c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [N/A] (d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [N/A] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] (b) Did you mention the license of the assets? [N/A] (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects... (a) Did you include the full text of instructions given to participants and screenshots, if
applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount
spent on participant compensation? [N/A]

Review summaries:
The paper studies the problem of learning revenue-maximizing auction mechanisms from samples when the observed samples may be adversarially corrupted. It shows that just applying ERM will still work well in terms of performance and sample complexity. It also shows that a particular multi-task version of the auction learning problem can be reduced to the problem of learning under adversarial noise, and so ERM will also work for this problem. 

The authors study revenue maximization for auctions from samples corrupted by bounded (adversarial) noise. They propose a condition called stability which, together with convergence bounds, guarantees that empirical risk minimization on the sample achieves near-optimal performance on the true distribution. They demonstrate that simple auction formats such as the second-price auctions with reserves satisfy stability.   Finally, they use stability to help design auctions for multi-task settings where the distribution over values in each task is a translation of the base distribution over values (and the translation is unknown). The main insight is that the samples from other tasks can be appropriately transferred to improve the revenue approximation guaranteed for each task.    

This paper provides robustness analysis for several existing types of auctions when the empirical bids can be perturbed within an L1 ball. The authors proposed two conditions: p-stable and q-convergent, under which the expected revenue of the empirically optimal mechanism over the noisy samples is close to the expected revenue of the optimal mechanism in the class. The authors further show that several existing mechanisms satisfy these conditions to various degree.