Revenue maximization via machine learning with noisy data
Authors: Ellen Vitercik
Tom Yan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Mechanism design
auction design
revenue maximization
machine learning theory
sample complexity
generalization guarantees
adversarial noise

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.

Revenue maximization via machine learning with noisy data
Ellen Vitercik
Department of Electrical Engineering and Computer Sciences University of California, Berkeley vitercik@berkeleyy .dd
Tom Yan
Department of Machine Learning Carnegie Mellon University tyyan@cmu.c edu
Abstract
Increasingly, copious amounts consumer data are used to learn high-revenue mechanisms via machine learning. Existing research on mechanism design via machine learning assumes that there distribution over the buyers' values for the items for sale and that the learning algorithm's '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 the buyers' values cause steep drop in revenue. Nonetheless, we provide guarantees when arbitrarily correlated noise added the training set; only require that the noise has bounded magnitude is sub-Gaussian We conclude with an application of our guarantees to multi-task mechanism design, where there multiple distributions over buyers' values and the goal is to lear high-revenue mechanism per distribution. To our knowledge, we are the first to study mechanism design via machine learning with noisy data well as multi-task mechanism design.
Introduction
Revenue maximization multi-item settings is one of the most important, long-standing open problems in mechanism design. In Bayesian Mechanism Design, there is 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 48 51 has relaxed this strong assumption: instead, the distribution is unknown and the mechanism designer only has a training set i..d. samples. Using the training set, the goal learn 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 comeestone of many modern enterprises.
of research [e.g.. g...1 I 19 20 25 26 28 30
33
37 40
Motivated by recent literature on the brittleness of deep learning models the face of imperceptible noise 33 41 (2), an important question is whether adversarial noise has the same effect in learning- based mechanism design. Learning methods deployed real-world settings to design mechanisms
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Revenue on true sample (P(1) m(2))
Revenue
Revenue noisy sample (W(r) w(2))
Reserve
((2) W(2)
((1)
((())
Figure 1: We illustrate revenue function volatility using the single-item second-price auction with reserve r. Let 0(1) be the highest bid and ((2) be the second-highest bid. Revenue as function of the reserve r equals U(2) if r S 1(2). r if ((2) < r S U(1), and 0 if > u(1)) as illustrated by the blue solid line. Suppose we receive noisy sample with highest bid w(1) ((1) and second-hip hiighet bid (((2) = L(2). Revenue is illustrated by the dotted grey line. Setting the reserve equal to w(1)
maximizes revenue on the noisy sample, but leads to zero revenue on the true values (t(1)) R(2))-
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 is sub-Gaussian. contrast, classic bearning-theoredd results typically rely on the stronger assumption that the training samples are independent.
1.1 Summary main contributions and overview of techniques
We set out to determine whether imperceptible adversarial noise in the training set can cause catastrophic loss in the learned mechanism's 's expected revenue. Our main contribution sensitivity analysis of revenue with respect to the noise's 's magnitude, which answers this question in the negative, Our results apply to empirical revenue maximization, the canonical approach learning- 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-priat lottery mechanisms under unit-demand buyers, and item-pricing mechanisms under unit-demand buyers. These classes have been studied extensively [e.g., [ 18 24 46, [1] 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
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 [ 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 learning theoretic perspective, which generally are smooth, continuous, or-more broadly-exhibi 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 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 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 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.

---

1.2 Related research
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 n < [e.g.. and where an 1--rraction of the training data can be corrupted [e.g.. 27]. Meanwhile, in our setting, every sample may be adversarially perturbed with probability 1, not just an r7-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 We, on the other hand, are concerned with noisy training data and face the unique challenges imposed by mechanism design.
example, an fy-ball [32 41 [52]
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 [T]). 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 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 product distribution, whereas our assumed noise model allows for arbitrarily correlated distributions.
Multi- vs Single-item Mechanism Design: Further afield, Huang et al. 68 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 him-ppiccing mechanisms.
The past few decades of research on revenue-maximizing multi-item mechanism design has demon- strated that results and intuition from the single-item setting do not always carry over the multi-item setting. And we see that this is the case in our paper as well. For example, an item- item-pricing mecha- nism for a single item would have ttraightfforwadd stability analysis (similar to the analysis of a single-item anonymous second-price auction that we include for intuition in Appendix B.I]. 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.
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 (.. Balcan et al. 77 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 manipulable mechanism.
Dispersion:
The appendix summarizes additional related work mechanism design with side information, multi-task learning, transfer learning, and approximate incentive compatibility.
2
Notation
There are n buyers and m items for sale. Each buyer i E [n] has value for each item j E [m]. denoted as Vyy 2 O. We analyze unma-demand and additive buyers. If buyer is unit-demand, he is only interested in obtaining one item, so his value for bundle b C [ma] of goods is equal to the maximum value he has for any item in b, maxjes Uzj- If buyer is additive, his value for a bundle b C [m]] is Σjeb Uij- We use the notation w; (U:1,-..; vim) denote buyer i's values for all m items and (UI,..., U2) Ra to denote all n buyers' values. When there only one item, we use the notation e = (V1..... vx) E IR,, where E R is buyer i's value for the item.
We study mechanism classes parameterized by vectors r E Rdd for some (for example, the class of second-price auctions parameterized by non non- anonymoo reserves r). The mechanisms we analyze
3

---

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 by (v), For simplicity of notation, we assume rev is in [0, 1J though our results can be extended to the case where rev,(v) E [0, H] for some H (all bounds must simply be multiplied by H).
Learning under adversarial noise
In this section, we study mechanism design via machine learning when the data is corrupted. Let S {o("), ..... v(4) C Rgg be set of valuation vectors drawn from unknown distribution D. Our learning algorithm receives a poisoned training set = = (o."),...,.(..) C CR200-
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 c 0, all samples & [E], all bidders i [n), and all items j E [mm] w 1 G, 1
(0)
or more succinetly, v(() - c < w(() (+) S v(.). (If we only know that | - w
S c, we can
shift all bids in each vector (h() down by c, in which case ()() - 2c S w(() S 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 concrete example in Section where we study multi-task mechanism design. (2) The noise may result from bounded rationality the part of the bidders, leading to small, seemingly- -innouuuuu 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 mub-Gaussian noise. In this case, suppose that each element of each vector y+)) E S is perturbed by subG(o²2 to obtain the noisy
vector (t), Then with probability 1 - 8, for all E [4], (/w(()) o| S oo 2 log 2mmm 8. The
noise need not be independent. Therefore, all of our results hold with (high) probability 1 - 20 over
the draw of the true values and the noise for = 20 2oog 8
Our Approach: We begin by fixing a mechanism class parameterized by vectors Rd for some (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 f' that maximizes average empirical revenue over S'. This algorithm will be the subject of our study. Throughout this section, analyze the following key question: what is the difference between the expected revenue of the mechanism defined by f', En-D frev (v)], and that of the optimal mechanism in the class, max frev, (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 foe -norm. By contrast, under the same noise assumption, 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 's loss has an optimal dependence on the noise e.
3.1 Robustness
We begin by providing guarantees for any mechanism class that satisfies a notion of robustness, which helps isolate exactly the properties need to prove that robust revenue optimization is possible. class is robust if satisfies two properties. The first is a stability property. Let e be the empirically optimal parameter setting over the set S of true samples, which means that of all r E RRd average revenue over S is maximized when r = f. Let j' be the empirically optimal parameter vector over the noisy set S'. Stability is satisfied when the average revenues of & and &' over S are close.
Our second property relies on a classic learning-theoree
notion convergence. It is satisfied when, for every parameter vector 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]. convergence bound alone does not imply any guarantees whatsoever for optimization with noisy

---

Mechanism class
Buyers' values
p-stable
Error bound
Single-item anonymous second-price auction
Additive
p(c, n,m m)
2c
Ōle + v I/L)
(Theorem B.2
(Corollary [.6)
Multi-item non mo-onnoy second-price auction
Additive
p(c, n. m) = 2me
Õ(me +
/mm/L L)
(Theorem 3.3
(Corollary 3.7
Multi-item con-anonymous lotteries
Unit-
p(c, n, m)
Ó(ne + v /nm/I1 L)
demand
(Theorem 3.9
(Corollary 3.10)
Item-pri nem-pricing mechanisms
Unit-
Does not satisfy
Ö(nm² (Rc +
//
demand
(Lemma B.11
(Theorem 3.13 Lemma 3.15
The distribution over buyers' values is K- x-bounded (Definition 3.14
Table Our p-stability guarantees together with the resulting error bounds. Item-pricing mechanisms do not satisfy p-stability, so we use alternative techniques to provide an error bound (Section 3.4)
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] 2² + R and [0, 1] x Z² - R, we say that mechanism class is p-stable and q-convergent if the following conditions hold:
p-stable. For any 1, let S (v()) be two arbitrary sets of vectors such that ( - < w < v() for all l [L]. Let F and F be the empirically optimal parameter vectors over and S':
v(1) C So and 8' {w ,..., w w()1) c Rg0
argmax,eR* El rev, (v(O) and r' = argmax, FER Ets revr (wl(). We require that on average over S, the revenues of and r' are close: 1 El reve (v(()) reve (v(9) S p(c, n, m).
g-convergent. For any every vector RR. the difference between the average revenue over S and the expected revenue at most (5, L, n, m). In other words, Eves (v), - E [rev,())] S q L,, n, m).
and 8 (o, 1), with probability 1 over the draw S ~ D'. for
a mechanism class is p-stable and g-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(l1) and S' (w.)),...,oo Let Fl be empirically optimal over S!: G' argmax Els rev, (w)( With probability 1 over S D'. maX,gra EewD (rev, Eu-D freve (v)) S p(c, m) + 2q L, n, m).
be two sets of valuation vectors such that for all E [L]. (()) - - w(() S v
We now prove that several mechanism classes stable: second-price auctions with non-anonymous reserves and lotteries. (For intuition, we also analyze the simpler class of second-pric -ooond auctions with anonymous reserves in Appendix B.I] Table summarizzs our results.
3.2 Non-anonymous second-prics price auctions
We prove that second-pric auctions with non-anonymous reserves and additive bidders are robust. In the single-item setting, this auction defined by a vector r E R", where r; is bidder i's reserve price. Each bidder submits a bid and the mechanism discards all bidders whose bids are smaller than their reserves. there are bidders remaining, the highest bidder, say bidder i, wins and pays the maximum of the second-highest remaining bid and r; (or if there are no other remaining bids). In the multi-item case, there only one copy of each item and there a separate auction per item. The mechanism is defined by r (ri...., Fm) E gam where T3 IR" is the reserve vector for item j.
5

---

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 non-anonymous recond-prics auctions are p-stable with p(e, n, m) = 2c.
....,,,.())) wll) C R w(() I v(t) for all [L]. Let F' be the empirically optimal reserve vector over S' and let f be empirically optimal over S. This proof relies on two key lemmas. The first states that if we shift the reserve vector f-which is empirically optimal over down by an additive factor of c= (c.....c) E R and apply it to the valuations in S little revenue lost. We use the standard notation (z) maxf2, (2. 0}. The full proof is in Appendix B.2
Proof. For any L 2 1, Set S = { v(L)] C P and S = f .....
be two sets of valuation vectors such that ((t)
Lemma 3.4. Let re rev, (vl0)= 2r.
(1f1 c) c) ,.... (fn -)) If reve (vl1) > 0, then rev,, (w(() 2
Proof sketch of Lemma 3.4 Suppose that rev, (v(0) > 0. Let be the winner under the values w(()
and reserve i. Since us 2 ft. we know that w 2 (v, e) (f-- 1 e), so under the values ((() and reserve there is at least one bidder whose bid is at least his reserve. Let i' be the winner under the valuation vector (() and reserve r.. We split this proof into four cases that depend on:
1. Whether or not i i= =', i'. and
2. Whether-under y(t) and there is another bidder besides whose bid is least his reserve (in other words, whether or not {t Uz 2 fr, f + i} = 0).
In the first case, = and {t vg 2 fe,t + i} * 0. Let & be the index of the second- -highet bidder in (9) whose bid is above his reserve in r: k argmax, (et ot A.). This means that rev,: (v()) max(f (x) (0), Since u/ 2 fR.. we have that wi 2 (06 =) 2 (fx t). Since (()
(2) (2)
(2)
k + and i = i', it must be that k + 1', so {1 wi 2 (fr e), # }'} A 0 (in particular, the set contains k)). Let be the index of the second-highest bidder in ( whose bid is above his reserve in w }.
Te: K' = argmax (w! wi (e)
(2)
2 (fr- - +)}. which means that rev,, (w(+) max(f,
Since & E {t w! 2 c), + J. we know that wa
(t) 2 wi
(E) 2 ukk
(e)
Putting this all
(0) together, we prove that rev,, (w) 2 max(f; - c, w 2 max(f;, o (0) 2e = rev+(v(0)) 2c.
We prove the other three cases the appendix.
We use Lemma 3.4 to continue Theorem rev, (v())) > 0. By Lemma 3.4 Σ
3.3 proof. Let I be the set of indices & such that rev (v(() = EeEr rev, (v(9) < EtEr revr, (w(+)-
2Le S Σt= rev,, (0) + 2Le
El rev, (w) + 2Le.
Next, we prove that for any reserve vector r, revenue under the samples (8)) will only be higher than
revenue under the samples wf!) which intuitively makes sense since ( S (2) The proof, which
has similar structure as the proof of Lemma 3.4 is in Appendix B.2
Lemma 3.5. For all samples l E [L] and reserve vectors r E R", rev, (w) & rev, (v())).
Since Ele rev, (v(0) < Σ rev (w!O) + 2Le, Lemma 3.5 implies that the theorem holds.
We next 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 's revenue decomposes additively over the items. The proof is in Appendix B.2
Theorem 3.6. The of multi-iten item non-anonymous second-price auctions under n additive buyers is p-stable with ple, n. m) 2me.
Theorem 3.6 and the fact that the class is g-convergent with q(5, L, n, m)
O
(V I Z (nm log(ma)))) + log 1)) [46] implies that optimization under noise is possible:

---

Corollary 3.7. Let S = {v("), ,..., c R2 and S' = (w())) w(1} C 20 be two sets
such that for all & E [L], w(0) = w()) I vlf) Let &' = argmax, rERmm >
high probability over S ~ D maX EewD [rev EEEDD rrev (v)] 8=1 rev, (w(1). With
Ô (me
This dependence on me is tight: no algorithm has better error than m.. Therefore, empirical revenue maximization provides an optimal dependence on the error term c. The proof in Appendix
Proposition 3.8. Fix an arbitrary envor term c. For any deterministic algorithm that takes as input training set S C IR and returns vector of non-anonymous reserves A(S) E RRum there exists a distribution 'D such that with probability 1 over the draw S = {v(2)..... ,bLL) 92(mc) for some noisy training set S' = (w)(1, ,..,, (ul(),...,..(()) such that ||0(()) wol0ll S fo all l e [T..
DL, max E [re) E [rev))s))
3.3 Lotteries
We next prove that single-priced lottery mechanisms satisfy our stability and convergence conditions. We analyze setting where there are unit-demand buyers with values for 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 r.o E Rzo and set of probabilities fi,,...,Pim rim E [0, 1] with Σ}= May = 1. If the buyer chooses to pay Tio, she will receive one item J E [m]] and Pr(J = j] = rij. Therefore, her expected utility is ΣØ= MayTay T20- She will choose to participate in the lottery so long as her expected utility is at least O. We prove that this mechanism class satisfies our stability and convergence conditions. The full proof is in Appendix [B.3
m
Theorem 3.9. The set of lotteries with n unit-demand buyers is p-stable with p(c, n, m) = nc.
Proof sketch. We sketch the proof that p(e, n, m) in the single-buyer setting (n = 1) and for the sake of generality, we prove the guarantee for buyers in the appendix. For any T, > 1, let S = ..... v(4) C Rno and S = =(w(), (..........) w(L)
C 1890 be two arbitrary sets of valuation vectors such that (1) E S (( S ((t) for all é e [L]. Let i = (fo, (fo.f1..... foo.f....,ff.. fm)) be the empirically optimal parameter vector over the set S and let f' = (f M 1...... ...... Frn) be the empirically optimal parameter vector over the set S'. We prove that E/= rev, (v) rev, (v(*)) S c.
We first prove that if we shift the price Åg down by e and evaluate the resulting lottery over S', little rev- enue is lost. Specifically, letting r. = (max {ru 0, fI....,frI .n)) we prove that if rev, (v((0) > 0, then revr, (w())= 2 rev; (v(()) -c. This implies that Σt= rev+ (1(() S EL revr, (u)(t) Te. Since F' is empirically optimal under S', Σ/= rev, (v) s E/ revp' (w(t)) + Le.
Next, we prove that for any parameter vector revenue under the samples v()) will only be higher than revenue under the samples (²) Specifically, for every E E [L] and any parameter vector r E Rm++1 rev, (f) < rev, (v())). This implies that Σt= rev, (vl()) I Le + El_ rev (v(()).
By a natural generalization of prior research (6, g(5, T,,, m) = O (v (na log(nm) + log } 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 = {1(1) ...... o(4) C Roam and = (1)
wll)} C Taam be two sets ELe rev, (w((). With high probability over S ~ DL, max,eRe(mt1) EewD (r)) - E [revær (v) Ô (nc + Vnm)..
such that for all E [Z], v000- -6 S wl0 S vl1), Let r'
This dependence on nc is tight: no algorithm has better error than nc. The proof is in Appendix B.3
Proposition 3.11. Fix arbitrary error term For any deterministic algorithm A that takes as input a training set C Rumm and returns a vector of lottery parameters A(S) E [R((m+1), there exists a distribution 'D such that with probability over the draw S = {b(1), (o(1),...,,t) (.()) DL, maxpgRetm+1) E [rev,(v)] - E [rev ((s)) (v)] = S((c)) for some noisy training set S' =
(1) (.)) such that (|0(0) w010 S eor all e [L].
7

---

3.4 Guarantees via dispersion
We now provide guarantees for the class of item- nem-pricing mechanisms under unit-demand buyers. under which revenue is 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 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- item-pricing mechanisms.
wem-pricing mechanisms: Let there be buyers and m items and in Section 3.2 we assume there is only one unit of each item for sale. There is non-anonymous price Faj. E R for each buyer i [m] and each item j E [m]. First, buyer arrives and buys the item j E [m]] that maximizes his utility Uij - "1 (or chooses not to buy if U1 < T1y for all items j E (m]) Next, buyer 2 arrives and selects the item among the remaining that maximizes his utility Vay Maj (or chooses not to buy).
This process continues for each buyer E [n]. As in the previous section, we use the notation (v) to denote the revenue of the mechanism with prices r E TR when the buyers have values e E R.m..
Under fiem-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. in Appendix B.4)).
The primary challenge in proving stability guarantee is that 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 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 noisy training set may he 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 bit of noise is added to their values. Below, we formally capture this notion of dispersion.
C R220 be a set of valuation vectors. We say that S is (c, k) -dispersed if for any price vector R", there are most l valuation vectors in S such that for some buyer i E [m]. either:
Definition 3.12 ((e, k)-dispersion). Let S {o()),.. ..... v(())
}
1. For some item pair j.J E [m]. buyer i's utility for item j is within c of her utility for item j', or
2. Buyer i's utility for some item j is between 0 and e.
The parameter i allows for some slack: for some but not afl-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 noisy training set. The full proof Appendix [..4
Theorem 3.13. Let S = (o(").......) ~ DL be a set of (2e, -)-dipeeredd vectors. Let S = {w ((()) Rum be another set such that for all E E [L]. ||0(0 - -w(()) w(1' S e. Let r' be empirically optimal over S' F' = urgmaxpeRum Ele rev, (w) With probabiiity 1 - ô over the draw of S, maXreRum EDeD [r)v E (v)] (+ v t log(mm)) + log t))
Proof sketch. We first prove that for any price vector r, average revenue over S is within & of average revenue over S', for the following reason. Due to dispersion, for most of the valuation vectors ((()) E S, the buyers will choose to buy the same set of goods regardless of whether their values are defined by u or w!(), so the revenue remains constant. For at most valuation vectors in S, the allocation may change arbitrarily, but revenue is always bounded in the interval jo, 1], which is why the bound contains the term &. Finally, to relate average and expected revenue, we use generalization bound from prior research [46] which equals the second summand of our bound. O
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 + R2o, the density function is k-bounded if max f(x) S
8

---

The proof of the following lemma is in Appendix B.4
Lemma 3.15. Suppose that for every buyer i E [n] and every pair of items j.3' E [m]] buyer i's values for items j and j' have a k-bounded joint density function. Then for any O, with probability - over the draw S = ( ...., v.l.) ~ D the set S is (2e, dispersed with
k 4Lnm kc + O (nm² VL
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.
4 Multi-task learning
We now show how our results from the previous section apply to multi-task mechanism design.
In this setting, there are T tasks, and each task ł E [7'] is defined by distribution D over buyers' values. Each distribution could represent, for example, buyers from different regions or market segments. The learning algorithm receives training set sampled from each task's 's distribution. Given mechanism class parameterized by vectors r E Id (which equal, for example, reserve prices) and the training sets, our goal is to learn a parameter setting (()) for each task t with high expected revenue over D(t), In particular, max Eu-Dio [rev,())] Eo-poo (rev,..) should be small.
Setup:
Task relatedness: If the distributions are completely unrelated. there is no hope that sharing infor- mation across tasks could improve learning. Thus, 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 e [n]] and item j E [m]. there is an underlying distribution Dij over Rzo. Let D = X X Diy denote the cross product of these nm distributions. Each task E [2] is defined by an unknown vector of
common-base values ((t) E RR. Intuitively, when 6, is large, buyer i tends to be willing to pay more for items, and when ((²) is small, buyer i tends to be frugal. This model inspired by the well-studied memmon--base-aiiee model [4]. For each task t E [T], our learning algorithm receives L samples (1.1)) (L,1) R Each sample (ff.)) is generated by sampling (f,tt) ~ 'D and defining buyer i's value for item to be vij
(E.4) 6 + Fij
(E.t). This defines a distribution D over buyer i's value for
item j. We use the notation (1)) X Dij to denote the cross product of these nmm distributions for task f. The learning algorithm does not know the vectors (()) or (f.(); it only observes the valuation vectors (ff.)) Throughout this section, we use the (slight abuse of) notation (() + ((+.t) to denote
v(f.)) 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 I [T). S. { (b(0) + ((.r)
[T), e E [4]} is training set of LT samples from the 1hh task's distribution (+t) since each vector (f,,)) is sampled from D. However, we cannot compile this
training set since we do not know the base values ((t) Nonetheless, in Appendix
C we show
that it is straightforward to compute a set of vectors S { (ff... f e [4], r E
[T]
that closely
approximate" the vectors in Sy: with high probability, for all pairs of tasks f, r
[T] and indices
é E [4]. (]600) (t.r) (((..) I~-- ò
(V Lm
From our results in Section
we know that
is possible to learn a mechanism with high expected revenue over the distribution DDt) using the noisy training set St. 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 fol-
lowing guarantee for learning a high-revenue multi-item second-prics auction with aon-anonymous reserves under additive bidders.
Theorem 4.1. For each task E [T]. let it be the empirically optimal reserve vector over the set S/ P. = argmax,eR'0 Et ΣT=1 rev, (w((..))) With probability 8, for every task E [T]. ma Ep-D(t) (r) revp:(1)) = δ
(nnn + log 7) + log 2T 8 LT
"In some cases, show that is also possible exactly recover the vectors in S. (Appendix C.2

---

This theorem implies that for any E (0, 1). when L = 2t (m/?²) and T (2(n), the rev- enue of the auction defined by the reserves fy is within y of optimal: max EE--D [rev, Ee-DIe [rev;; (v) I 7. In contrast, the best-known single-task sample complexity guarantee re-
quires L 52 (nm//?) 46 Our per-task sample complexity is smaller by multiplicatiie 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 St results in nearly optimal revenue.
Theorem 4.2. For each task t, let Pi be the empirically optimal lottery parameter vector over the set S/: F/ aEgmax Et=1 Er= rev, (wrlet.r)). -With probability 1 - 6, for every E [T],
= (V LT (nm + log %)) + L. log n2 8
maxpeR=(m+1) DieD (e) reve:
n²
Theorem 4.2 implies that for any y E (0, 1), when L = (m/>?), T = (mm). and there are more items than buyers (m > n), the revenue of the lottery defined by F is within of optimal: max maxEpxD((t) [re) - Ee-D(t frevæ (v)] S y. Meanwhile, the best-known single-task sample
complexity bound requires L = 52 (nm/?²) [6. Our approach's per-task sample complexity is better by a multiplicative factor of m.
Conclusions
We provided guarantees for learning high-revenue mechanisms with noisy data. Learning in the presence of noise particularly challenging in mechanism design because revenue functions volatile, exhibiting many jump discontinuities. We were nonetheless able to provide revenue guar- antees 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 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 exciting future direction if any guarantees 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 learning- based mechanism design is the lack of public datasets- we are only aware of one, from eBay [44). We focused theoretical guarantees, but applied research robust and multi-task learning in mechanism design is great future direction. (3) Building on our results for multi tasti-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-tuni prices could have negative privacy implications. The development of privacy pereey--reeeiinggg approaches to mechanism design via machine learning is great direction for future research.
References
[1] Noga Alon, Moshe Babaioff, Yannai Gonczarowski, Yishay Mansour, Shay Moran, and Amir Yehudayoff. Submultiplicaiiee Srivenko-Cantedd and uniform convergence of revenues. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
[2] Rie Kubota Ando and Tong Zhang. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research, 6(Nov):1817-18)) 2005.
of the mechanism class is at least nm [6] which suggests that the dependence may be necessary in the single-task setting.
'The
10

---

[3] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Proceedings of the Conference on Learning Theory (COLT), pages 167-190, 2015.
[4] Maria-Florina Balcan, Avrim Blum, Jason Hartline, and Yishay Mansour. Reducing mechanism design to algorithm design via machine learning. Journal of Computer and System Sciences, 74: 78 89, December 2008.
[5] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In Proceedings of the IEEE Symposium Foundations of Computer Science (FOCS), 2018.
[6] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the ACM Conference on Economics and Computation (EC), 2018.
[7] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Estimating approximate incentive compatibility. In Proceedings of the ACM Conference on Economics and Computation (EC), 2019.
[8] Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed setting. In Proceedings of the Conference on Uncertuinty in Artificial Intelligence (UAI), 2020.
[9] Hosseen Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi, and Saeed Seddighin. Revenue maximization for selling multiple correlated items. In Proceedings of the European Symposium on Algorithms (ESA), pages 95-105. Springer, 2015.
[10] Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-199 198, 2000.
[11] Xiaohui Bei and Zhiyi Huang. Bayesian incentive compatibility via fractional assignments. In Proceedings of the twenty-second annual ACM-SIAN symposium on Discrete Algorithms, pages 720-733. SIAM, 2011.
[12] Shai Ben-David and Reba Schuller Borbely. notion of task relatedness yielding provable multiple-task learning guarantees. Machine learning, 73(3):273-287, 2008
[13] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory learning from different domains. Machine learning, 79 (1-2):151-175, 2010.
[14] Dirk Bergemann and Stephen Morris. Robust mechanism design. Econometrica, pages 1771 1813, 2005.
[15] Dirk Bergemann and Karl Schlag. Robust monopoly pricing. Journal of Economic Theory, 146 (6):2527-2543, 2011.
[16] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 721-729, 2015.
[17] Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 2392-2401, 2017.
[18] Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg. Pricing randomized allocations. In Proceedingy of the ACM-SIAM Symposium Discrete Algorithms (SODA), pages 585-597. SIAM, 2010.
[19] Sébastien Bubeck, Nikhil R Devanur, Zhiyi Huang, and Rad Niazadeh. Online auctions and multi-scale online learning. In Proceedings of the ACM Conference on Economics and Computation (EC), 2017.
11

---

[20] Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2017.
[21] Yang Cai, Argyris Oikonomou, Grigoris Velegkas, and Mingfei Zhao. An efficient epsilon-brl to bic transformation and its application to black-box reduction in revenue maximization. arXiv preprint 19Xiv:1911.1111 2019.
[22] Shuchi Chawla, Jason D Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the ACM Conference on Economics and Computation (EC), 2007.
[23] Shuchi Chawla, Jason D Hartline, David L. Malec, and Balasubramanian Sivan. Multi paramerr mechanism design and sequential posted pricing. In Proceedings of the Anmual Symposium Theory of Computing (STOC), 2010.
[24] Shuchi Chawla, David Malec, and Balasubramanian Sivan. The power of randomness in Bayesian optimal mechanism design. Games and Economic Behavior, 91:297-317, 2015.
[25] Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2014.
[26] Nikhil R Devanur, Zhiyi Huang, and Christos-Alestt Alexandros Psomas. The sample complexity of auctions with side information. In Proceedings of the Anmual Symposium on Theory of Computing (STOC), 2016.
[27] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high- sigh-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742 864, 2019.
[28] Edith Elkind. Designing and learning optimal finite support auctions. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
[29] Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning. Information and Inference: A Journal of the IMA, 5(2):159-25) 20999999999900 2016.
[30] Yannai A Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single- parameter auction environments. In Proceedings of the Anmual Symposium on Theory of Computing (STOC), pages 856-868, 2017.
[31] Yannai A Gonczarowski and S Matthew Weinberg. The sample complexity of up-to-E multi- dimensional revenue maximization. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2018.
[32] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In Proceedings of the International Conference on Learning Representations (ICLR), 2014.
[33] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Setting the sample complexity of single- parameter revenue maximization. In Proceedings of the Annual Symposium Theory of Computing (STOC), 2019.
[34] Rishi Gupta and Tim Roughgarden. A PAC approach to application-specific algorithm selection. SIAM Journal on Computing, 46(3):992-1017, 2017.
[35] Sergiu Hart and Noam Nisan. Approximate revenue maximization with multiple items. In Proceedings of the ACM Conference on Economics and Computation (EC), 2012.
[36] Jason D Hartline and Brendan Lucier. Bayesian algorithmic mechanism design. In Proceedings of the Annual Symposium on Theory of Computing (STOC), pages 301-310, 2010.
[37] Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples, In Proceedings of the ACM Conference on Economics and Computation (EC), 2015.
[38] Zhiyi Huang, Jinyan Liu, and Xiangning Wang. Learning optimal reserve price against non- myopic bidders. arXiv preprint 1XXiv:804.111660 2018.
12

---

[39] Xinye Li and Andrew Chi-Chih Yao. On revenue maximization for selling multiple inde- pendently distributed items. Proceedings of the National Academy of Sciences, 110(28): 11232-11237, 2013.
[40] Anton Likhodedov and Tuomas Sandholm. Methods for boosting revenue in combinatorial auctions. In Proceedings of the AAAI Conference on Artificial Intelligence, 2004.
[41] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
[42] Yishay Mansour, Mchryar Mohri, and Afshin Rostamizadch. Domain adaptation: Learning bounds and algorithms. In Proceedings of the Conference on Learning Theory (COLT), 2009.
[43] Daniel McNamara and Maria-Florina Balcan. Risk bounds for transferring representations with and without fine-tuning. In Proceedings of the International Conference on Machine Learning (ICMI.), pages 2373-2381, 2017.
[44] Mehryar Mohri and Andrés Muñoz Medina. Learning theory and algorithms for revenue opti- mization in second price auctions with reserve. In Proceedings of the International Conference on Machine Learning (ICML), 2014.
[45] Jamie Morgenstern and Tim Roughgarden. On the pseudo-dimensien of nearly optimal auctions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2015.
[46] Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Proceedings of the Conference on Learning Theory (COLT), 2016.
[47] Andrés Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
[48] Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the ACM Conference on Economics and Computation (EC), 2016.
[49] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. arXiv preprint 100. 11285, 2018.
[50] Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385 463, 2004.
[51] Vasilis Syrgkanis. A sample complexity measure with applications to learning optimal auctions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
[52] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2014.
[53] Yu Zhang and Qiang Yang. A survey on mask learning, arXiv preprint 11Xiv:1707.08/) 2017.
6 Checklist
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
13

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you 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 proof's of these results are the appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as 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 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 obtained from people whose data you'le 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing 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 participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "tCo-XyjbQnQ", "reviewer": "Reviewer_6knT", "summary": "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. \n\nFinally, 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.\n  \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper builds on a line of recent work on revenue maximization from iid samples. The problem of revenue maximization from samples corrupted by adversarial noise is a natural extension. I found the setup for the multi-task setting and the insight that stability is helpful in this setting to be particularly interesting, and I would encourage the authors to add more detail about these results to the main body of the paper. The paper was well-written and seemed technically sound.\n\nWhile the proofs that the auction formats were stable were clearly written and seemed technically sound, I did not find the fact that these auctions were stable to be surprising considering the robustness properties proven in previous work (e.g. [29] and (*) below). \n\nIt is not clear that stability holds for revenue-optimal auction formats (i.e. the Myerson auction in the single item setup). Since the goal is ultimately revenue maximization, it seems important to design auctions from corrupted samples that achieve near-optimal revenue across all possible auction formats. \n\nAnother weakness is the assumption that the adversarial noise is bounded, which seems necessary for the proposed stability property to guarantee a high revenue. However, this assumption seems very strong, and it would be interesting to design variants of stability that are suitable for more realistic noise models. \n\nMinor comments:\n-\tParenthesis on last line of Def. 3.1 would help with clarity.\n\n(*) Huang, Liu, and Wang. Learning Optimal Reserve Price against Non-myopic Bidders, 2018. \n\n——-\nUpdate: Thanks to the authors for their detailed responses. Although investigating the stability of a richer class of mechanisms would provide a more comprehensive picture, the author response has convinced me that their results on multi-item auctions are sufficiently important for acceptance. I have thus decided to raised my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discussed the societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "tC7URSED7Ap", "reviewer": "Reviewer_7Ngd", "summary": "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\noptimal 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I find the paper well-written and the structure is relatively clear. I agree with the authors that robust auction design under noisy empirical data is an important problem with direct practical applications, and the authors did a good job in motivating the importance of auction design with noisy data. \n1. One main concern I have is about the bounded noise assumption, and I would like to see more justification for it in the auction setting. Based on my understanding, this assumption describes the scenario where each bid might be perturbed by a small epsilon distance w.r.t. the original true bids. However, as the authors also mentioned (in Cai and Daskalakis [18]), a seemingly more natural noisy data setting is to consider distributional changes. For example, a small fraction of the bids might be arbitrarily perturbed. The bounded noise assumption seems to be a bit restrictive in the sense that each bid can only be off by a small value.\n2. From the results (e.g. theorem 3.6 and 3.9), the revenue loss scales linearly in n / m and epsilon, even for the two classes of mechanisms that are shown to be p-stable and q-convergent. This seems to be a bit unsatisfying especially when n / m and epsilon is large. I would be curious to see if this is the optimal guarantee. \n3. Based on my understanding, some other commonly studied auctions, e.g. second price auction with anonymous price, do not satisfy the p-stable and q-convergent condition. I wonder if the \"sensitivity analysis\" that the authors presented can provide insights on adapting auctions to be p-stable and q-convergent.\n4, As the authors focused on ERM, I would be interested in seeing how the robustness guaranteed by p-stable and q-convergent is reflected in experiments, e.g. with simulated data.\n\n--------------------------\nConsidering the authors' response, I decide to change my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "XW6hTPft-VX", "reviewer": "Reviewer_dk54", "summary": "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.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Longer summary:\n\nThe paper considers the problem of learning an auction from samples when the samples may be corrupted by decreasing valuations by epsilon. (Not quite the same thing as $\\ell_\\infty$ adversarial corruption, but close). The core claim of the paper is that ordinary ERM still works well for many classes of auctions.\n\nThe general quantity of concern is difference between mean revenue of the auction learned on true data, and mean revenue of the auction learned on noisy data. Various techniques are presented for bounding this quantity with high probability. In particular, the authors show that if a class of mechanisms is p-stable (on average over true samples, the mechanisms learned on corrupted and true data have revenue bounded by p) and q-convergent (simply a normal error bound on empirical vs. mean revenue). The classes of mechanism studied in the paper are already known to be q-convergent for various q, so by showing this result and then providing a bound of p-stability for each mechanism, it's shown that ERM works well.\n\nIn one additional case (item-price mechanisms with unit-demand buyers), p-stability does not hold. However, if it is assumed that the bidder's valuation vectors are well-dispersed (which holds with high probability if the joint valuation distribution is smooth in the sense of never having a peak density larger than $\\kappa$), ERM again works well.\n\nFinally, a limited but plausible multi-task version of the auction learning problem is defined, inspired by the common-base value model of auctions. Given multiple datasets with different, unknown base values, one can compile a larger training set which has only small errors with high probability. Learning on this new dataset is equivalent to learning under noise, so the results above showing that ERM works well also work.\n\nOriginality:\n\nThe paper leans heavily on existing theoretical results and techniques for learning auctions from samples (e.g. $\\kappa$-boundedness of valuation distributions, dispersion). However, it is definitely still original.\n\nQuality:\n\nThe paper is high quality and well argued. \n\nClarity:\n\nThe NeurIPS page limit has produced some unavoidable fragmentation but there's nothing to be done about this.\n\nSignificance:\n\nThe problem is an important one. It's rare to have a large supply of truthful valuations to learn an auction, and even if they are available those valuations might shift over time. So understanding how to learn auctions robust to corrupted data is an important part of the overall project of learning auctions. The results don't present any new techniques to use, but rather show that naively training on the corrupted dataset should still work well, which is surprising and interesting.\n\nOther comments:\n\nThere is a large body of research on learning auctions in the face of distributional adversaries. Two arbitrary examples:\n\nKoçyiğit et al., Distributionally Robust Mechanism Design\n\nBergemann et al., Robust Monopoly Pricing\n\nThis is a different problem than what is addressed in this paper (which is particularly concerned with learning from samples, and does not present new learning algorithms, but rather shows that the naive approach is already fairly robust). But it is related, and I was surprised not to see any of this work even cited in the appendix. \n\nGiven the discussion of ICML 21 reviews, it's possible this material was cut to prevent confusion, but I think it might be worth mentioning some of it.\n\nThere is also some adversarial robustness literature briefly cited, but only work focusing on test-time evasion attacks. I don't think it's essential to the message of the paper at all, but it couldn't hurt to cite some of the work on poisoning, where the training dataset is corrupted, as this is closer to the setting studied in this paper.\n\nFinal update: I enjoyed reading this paper and my opinion remained positive after the discussion period.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theory-heavy paper that is unlikely to have much direct social impact, and the authors are very clear about the scope of their results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "N8qnho_igBK", "reviewer": "Reviewer_e5fx", "summary": "The authors provide guarantees for optimizing revenue using a learning-based framework over several common mechanism classes when an imperceptible adversarial noise is added to the training set. They then use the guarantees for multi-task mechanism design.  \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The authors make two original contributions - First, they study learning-based mechanism design under adversarial noise. Despite the volatility of the revenue functions, they conclude through a sensitivity analysis that there isn't a catastrophic loss in revenue when imperceptible adversarial noise is added. They also study the problem of multi-task mechanism design (which unlike existing literature doesn't assume that there is one single distribution defining the buyer's values).\n- The paper is well written and easy to read.\n- The problem that the authors' study and the results presented in the paper are of interest to both the fields of robust ML and mechanism design.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the revenue-optimal mechanism design when the bidder value distribution can be corrupted by bounded adversarial noise. This is a nice contribution and a good fit to NeurIPS.
Decision: Accept (Poster)