Robust Learning of Optimal Auctions
Authors: Wenshuo Guo
Michael Jordan
Emmanouil Zampetakis
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: optimal auction
robust learning
sample complexity

Abstract: We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. First, we prove tight upper bounds on the revenue we can obtain with a corrupted distribution under a population model, for both regular valuation distributions and distributions with monotone hazard rate (MHR). We then propose new algorithms that, given only an ``approximate distribution'' for the bidder's valuation, can learn a mechanism whose revenue is nearly optimal simultaneously for all ``true distributions'' that are $\alpha$-close to the original distribution in Kolmogorov-Smirnov distance. The proposed algorithms operate beyond the setting of bounded distributions that have been studied in prior works, and are guaranteed to obtain a fraction  $1-O(\alpha)$ of the optimal revenue under the true distribution when the distributions are MHR.  Moreover, they are guaranteed to yield at least a fraction $1-O(\sqrt{\alpha})$ of the optimal revenue when the distributions are regular. We prove that these upper bounds cannot be further improved, by providing matching lower bounds. Lastly, we derive sample complexity upper bounds for learning a near-optimal auction for both MHR and regular distributions.

Robust Learning of Optimal Auctions
Wenshuo Guo
Michael I. Jordan University California, Berkeley jordanêcs. werkeley. edu edu
University of California, Berkeley wer.:ece..bbreeey........ eddu
Manolis Zampetakis University of California, Berkeley mzampet.Bberkeeey edu
Abstract
We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. First, we prove tight upper bounds on the revenue we can obtain with corrupted distribution under a population model, for both regular valuation distributions and distributions with monotone hazard rate (MHR). We then propose new algorithms that, given only an "approximate distribution" for the bidder's valuation, can learn mechanism whose revenue nearly optimal simultaneously for all "true distributions" that are a-close to the original distribution in Kolmogorov-Smimat proposed algorithms operate beyond the setting of bounded distributions that have been studied in prior works, and are guaranteed to obtain a fraction O(a) of the optimal revenue under the true distribution when the distributions are MHR. Moreover, they are guaranteed to yield least fraction O(va) of the optimal revenue when the distributions are regular. We prove that these upper bounds cannot be further improved, by providing matching lower bounds. Lastly, we derive sample complexity upper bounds for learning a near-optimal auction for both MHR and regular distributions.
distance. The
Introduction
Optimal auctions play a crucial role in economic theory, with a wide range of applications across various industries, public sectors, and online platforms [Myerson, 1981, Bykowsky et al., 2000, Roth and Ockenfels, 2002, Klemperer, 2002, Milgrom and Milgrom, 2004, Lahaie al., 2007]. In such auctions, pricing mechanisms need to be determined by the auction designer so as to satisfy various desired goals, such as revenue maximization and incentive compatibility. Often this determination is made based on information about the buyers that is assumed to be available a priori. For example, in a standard valuation model, each bidder has valuation over the available items, and the sellers knows the distribution of these valuations, they could design an optimal auction which maximizes the revenue.
Arguably the fundamental difficulty in the design of optimal auctions is that real valuations are private and unknown to the auction designer. Consider specifically the problem of selling one item to multiple buyers. Suppose that we model the buyers' valuations as arising as independent draws from buyer-specific prior distributions. In this scenario, what the optimal mechanism terms of the expected revenue? This problem was solved by Myerson [1981] through a characterization of virtual value functions. In particular, we can define virtual value function of each buyer based on their
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

prior distributions. An optimal auction then lets the buyer with the largest non-negative virtual value win the item, and charges the winner a price that equals the threshold value above which she wins.'
Unfortunately. there is a further fundamental challenge in deploying these theoretical results in practice, which is that in real-world settings the auction designer may not even know the prior distributions on valuations. Instead, what the designer might hope for is that there is a stream of previous transactions, or some other relevant auxiliary data, that is helpful in inferring the buyers' private distributions. This perspective has motivated an active recent literature learning optimal auctions from samples [Cole and Roughgarden, 2014, Devanur al., 2016, Morgenstern and Roughgarden, 2015, 2016, Syrgkanis, 2017, Dudik et al., 2017, Gonczarowski and Nisan, 2017, Huang al., 2018, Roughgarden and Schrijvers, 2016, Balcan et al., 2018, Guo et al., 2019, Roughgarden and Wang, 2019, Gonczarowski and Weinberg, 2021]. In this line of work, the central question is: suppose we are only able to access the prior distributions in the form of independent samples, how many samples are sufficient and necessary for finding an approximately optimal auction?
While this merging of mechanism design and learning theory is appealing, further concern arises. Given the potentially adversarial setting of auction design, do we really believe that the data that we observe are drawn in accord with our assumptions? More concretely, is the learning of optimal auctions robust to adversarial corruptions of the samples? This problem is arguably at the core of what it means to learn an optimal auction. Counterexample 1 in Section 4, auction designs that are optimal in the absence of corruptions can become arbitrarily bad even if small portion of the samples are corrupted. Building on earlier work by Cai and Daskalakis [2017] and Brustle et al. [2020], we tackle key open problem-what is the best approximation to the optimal revenue for arbitrary levels of corruption for distributions with unbounded support? And what is the mechanism that achieves it?
a challenging problem; indeed, as we show in
In summary, in this work we explore the problem of the robust learning of optimal auctions, where the samples of bidders' valuations are subject to corruption and their support is unbounded. In particular, we consider having access to samples that are drawn from some distribution D which is within a Kolmogorov-S -mirnnvv (KS) distance a of the true distribution D', Denote OPT as the maximum revenue we can achieve under the true valuation distributions. Our goal is to design mechanisms that are guaranteed to achieve a revenue of at least (1 11-ple p(aa)) OPT for the smallest possible error p(a) and with the use of minimal number of samples.
1.1 Our results
We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We summarize our main results as follows:
1. We derive tight upper bounds on the revenue we can obtain with corrupted distribution under a population model. For distributions with monotone hazard rate (MHR), and with total corruption a, we obtain an approximation ratio of 1 O(a) compared to the optimal revenue under the true distribution (see Theorem 3.6). For regular valuation distributions, where for total corruption o, we get an approximation ratio of 1 - O(var) (see Theorem 3.8).
2. To achieve these upper bounds, we propose new theoretical algorithm for the population model (see Algorithm 1) that, given only an "approximate distribution" for the bidder's s valuation, can learn mechanism whose revenue is nearly optimal simultaneously for all "true distributions" that are a-close to the given distribution in Kolmogorov-Smie Smirnov distance. The proposed algorithm operates beyond the setting of bounded distributions that have been studied in prior works; indeed, they apply to general unbounded MHR and regular distributions.
3. We further show that these upper bounds under the population model cannot be further improved (up to constant log factors), by providing matching lower bounds for both the MHR and regular distributions (see Theorem 3.7 and Theorem 3.9).
4. Lastly, we derive sample complexity upper bounds for learning near-optimal auction for both MHR and regular distributions with multiple bidders (Theorem 4.3 and Theorem 4.4), and propose a practical algorithm (see Algorithm 2) which takes samples as input. We also
Moore generally, the optimal auction picks the winner based on the virtual value after an "ironing" procedure.

---

provide accompanying sample complexity lower bounds (Theorem 4.5), and demonstrate small gap relative to the corresponding upper bounds.
1.2 Related work
Designing revenue optimal auctions is a classic problem in economic theory that has attracted much research attention. We survey the most closely related work in two main areas.
Learning optimal auctions from samples. Recent work has explored settings of learning approx- imately optimal auction from samples, both for single-item auctions [Cole and Roughgarden, 2014], and multi-item auctions [Balcan et al., 2018, 2016, Morgenstern and Roughgarden, 2015, Syrgkanis, 2017]. Most recently, Guo et al. [2019] provide complete set of sample complexity bounds for single-item auctions, by deriving matching upper and lower bounds up to a poly-logarithmic factor. While these approaches have obtained fruitful results on the sample complexity of learning optimal auctions, a key assumption that is commonly made in this work is that the samples are independently and identically drawn from the bidders' valuation distributions, with the goal of learning auction which maximizes the expected revenue on the underlying, unknown distribution over bidder valua- tions. A major difference in our work is that we consider that the samples can suffer from potential corruptions, which is a significantly more challenging setting.
Robustness of learning optimal auctions. Our paradigm on the robust learning of optimal auctions closely related recent work that considers the learning of auctions from mismatched distributions or corrupted samples. Cai and Daskalakis [2017] consider a multi-item auction setting, where there is given "approximate distribution," and the goal is to compute auction whose revenue is approximately optimal simultancously for all "true distributions" that are close to the given one. They provide an algorithm that achieves poly-a additive loss compared to the true optimal revenue. More recently, Brustle et al. [2020] consider learning multi-item auctions where bidders' valuations are drawn from correlated distributions that can be captured by Markov random fields. However, they make a key simplifying assumption that the bidders' valuation for the items lie in some bounded interval. Our results, by contrast, apply to the general setting of unbounded valuation distributions, setting that requires new theoretical machinery. To the best of our knowledge, our work constitutes the first analysis of the learnability of single-item optimal auctions from corrupted samples for unbounded distributions.
Organization. In Section 2, we provide background on auction models and formally state our problem. Section contains our main theoretical statements for the population model. We propose an algorithm that achieves optimal theoretical upper bounds, by providing matching lower bounds. Section contains our main results on learning with finite samples. We provide a practical algorithm that takes samples from the corrupted distribution, and provides sample complexity upper and lower bounds for both the regular and MHR distributions cases. We conclude in Section
2 Preliminaries
We begin by formally defining the setting study for robust learning of optimal auctions, which includes the revenue objective and the general classes of valuation distributions that we consider.
2.1 Auction models
Single-bidder setting. Consider one item for sale to one bidder. The bidder has a private valuation E R. for this item. We assume that v is random variable distributed according to the distribution D*, with support R,,, cumulative distribution function F, and probability density function f.
It is well known that the optimal auction in this setting is a reserve price auction, such that the task for the seller is to compute a reserve price p that optimizes revenue [Myerson, 1981]. We assume that the bidder has a quasi-linear utility that is equal to u(p) = p if she decides to buy the item and u(p) = 0 otherwise. The seller aims to set p such that her expected revenue-i.e. the received payment- is maximized. We consider the setting where both and D) are unknown to the seller.
3

---

However, the seller can access i.idd. samples that are drawn from distribution D, which is a-close to D with regard the Kolmogorov distance:
Definition 2.1. (Kolmogorov-Smirmo) distance) For probability measures j and v on I, define
dk v) sup pu(0-0,, v((-00,z))
It is well known that (z, & dry (H, where drv denotes the total variation (TV) distance between j and v. The closeness of 'D to DD* is thus formalized as follows:
du (D", D) a
for some 0.
Multi-bidder setting. Consider one item for sale bidders. Each bidder has a private valuation, E IR.,, where 02 is independently drawn from the corresponding prior distribution D. Thus, the valuations = (11, 022 ... Un) follow a product distribution D* = =D
D; Each bidder submits a bid b; > 0. Denote all the bids as b (b1, bb,). A mechanism in this setting consists of two rules: the allocation rule x(b) that takes the bids and outputs the probability z, that each bidder i will receive the item, and the payment rule p(b) that takes the bids b and outputs the payment of bidder i. Bidder i's utility is then (b) = V; (b)bb Pi(b). The goal of the seller is to find mechanism that maximizes the expected revenue EE (en Ps (b)), where the expectation is
D', under the following Dominant Strategy Incentive Compatibility (DSIC) and the Individual Rationality (IR) constraints:
(e; b-i) 3) > (bbb; b-;)
for all Us b, E R2 and all b E E
(DSIC)
(1; b- >
for all Us R4 and all b-, R
(IR)
consider the setting in which the valuations and the prior distributions are unknown to the seller. Instead, the seller has access to finite number of i.i.d. samples drawn from the product distribution
D Dj x ... Dn, where each D, satisfies
du (D; D.) & oz.
for some a; > O, Vi E [n].
Revenue objective. Letting D. D' be product single bidder distributions as described above, define MD be mechanism that achieves the optimal revenue for the value distributions and OPT(D) its expected revenue. Let also Rev(MD, D') be the expected revenue of the mechanism MD when applied to a setting where the values are drawn with respect to D'.
2.2 Monotone hazard rate (MHR) and regular distributions
For any bidder i with valuation U/ ~ D;, define the virtual value function for this bidder as 1-F,(u) where F; and fa are the CDF and PDF D;. The hazard rate of the distribution D; is defined as the function file) I-F Then, the distribution D; is said to be regular if the virtual value (v) is monotonically non-decreasing in Further, distribution Dj has monotone hazard rate (MHR) I-F((e)
(v) def v fe(m)
fa(w) is monotone non-decreasing.
The Population Model
In this section, study the problem of learning optimal auction assuming that we have the exact knowledge of the adversarially perturbed distributions D. We relax this assumption in Section where we show how to learn optimal auctions when only have sample access to D.
We begin in Section 3.1 with the deseription of our mechanism in the population model. Then, in Section 3.2, we present our analysis for the population mechanism for Monotone Hazard Rate distributions and we also present the sketch our proof for the single-bidder case. Similarly, in Section 3.3 we state our analysis for the population mechanism for regular distributions and we present proof sketch for the single-bidde case. Finally, we show that our proposed mechanism achieves optimal (up to constants) guarantees among any mechanism in the population model.

---

3.1 Robust Myerson auction in the population model
Our algorithm assumes as an input the exact knowledge of a product distribution, = D, x.... Dr.. such that the d2 D.) & ag and its goal is to find a mechanism that achieves approximately optimal revenue for D where D 11, Without further assumptions, this is an impossible task, we explain in Section 4 via an example. Thus we assume that the algorithm possesses some additional knowledge regarding D, either that it is MHR regular, and the mechanism needs exploit this additional property.
To utilize the additional property of the distributions D;, our mechanism uses the important concept of the link function for MHR and regular distributions.
Definition 3.1 (Link Function). The link function (a; for MHR distributions is defined as (ar F) = - =In11 F(x)) and the link function (a; F) for regular distributions is defined as (1; F) 1/(1 - F(x)). We also define the corresponding inverse link functions AM (a:; h) 1 exp(-h(x)) and (x;; h)
1/h(z). Observe that MM (a; har (a; F)) F(xr) and h,- ( (x; F)) = Fz)). We may write hM (x) or (x) when F is clear from the context.
We provide some intuition on the link function. First, by construction, the link function of either an MHR distribution or regular distribution is convex and non-decreasing. Second, the link function monotone with regard to F. These two properties are important when we define the notion of minimal MHRR/rgular distribution in Kolmogorov ball, momentarily, which will be used as necessary step in our algorithm.
Importantly, the link function provides a convenient characterization of the optimal reserve price and optimal revenue for a distribution F that MHR or regular. To see this, first consider single bidder with a valuation distribution F. Denote the optimal reserve price for selling one item to her as z", and the optimal expected revenue as (P)( Then, when MHR, we show that x also the unique minimizer of (har (z) (og(z)). On the other hand, when F is regular, v" is the point where (c)) intersects with its tangent line kr, with k = 1/OPT(F) (proof details Appendix). Figure illustrates such useful property for hMs and h, explicitly, for single-item, single-bidder auction.
(x)(F)
h,(F)
OPT(F)
log(x) log(OPT(F) (0.1)
X
X
Figure 1:
Optimal reserve price x" with regard the link function, for a single-item single-bidder auction with a valuation distribution F. (left) F' is MHR; (right) F is regular.
Next, we formally define stochastic dominance between two distributions, and state the property of strong revenue monotonicity.
Definition 3.2 (Stochastic dominance). Given two distributions D2 and D2 with CDFs as F1 and Fz- Then, we say Dj (first-order) stochastically dominates D. if for every x e X.
(x( < F2)x)
denoted as D1 2 D2. We say a product distribution = II,D; (component-wise) stochastically dominates another product distribution D' II, if for every i, we have D, ž D/..
Lemma 3.3 (Strong revenue monotonicity [Guo et al., 2019]). Ler D, D' be two product distributions
such that D' 2 D. then, for M that is the optimal mechanism for D. we have:
Rev(M,D) D) < Rev(M, (ev(M, D').
5

---

h
Algorithm Robust Myerson Auction in the Population Model
Input: 01 .1...an > 0, link function f(+), possibly cor- [I Fs.
rupted valuation distribution
JFF. F) sa
2: for iori= I...n do
3: Compute a minimal regular / MHR distribution in
(0.1)
ox (F:) according to Eq (1), denote as F..
4: end for
Figure 2: A minimal regular distri- bution in Bd in the space trans- formed by applying the link func- tion.
5: Set F = II;
6: Output Myerson's optimal auction Mp w.r.t. the distri-
bution F.
The following lemma illustrates the importance of the link functions well as their connection with first-order stochastic dominance. The proof this lemma is given Appendix A.
Lemma 3.4. A distribution with CDF F is MHR if and only if h has F) a convex function of Similarly, F is regular if and only if fe (2; F)) is a convex function of x. Moreover, for two MHR (resp. regular) distributions F1 and F2, such that Fi č F2, we have that has (z; Fi) has (z; F2) (resp. (r; F1) & (2; F2)) for all x.
key idea used in our algorithm is the minimal MHR/regular distribution within a Kolmogorov distance divergence ball. Formally,
Definition 3.5. For a given distribution with its cumulative distribution function as denote the set of all the distributions that are a-close to F in Kolmogorov distance as Ba o (F):
Bd (F) def (F' dx F)
Further, define minimal MHR/regular distribution within Ba (F) as:
F(x) (x; where
T(x)) def
h (F(zz) Ve R+.
(1)
FEBa F MHR regular
Figure gives an illustration of minimal regular distribution within Be),a(F) in the space trans- formed by the link function of regular distributions.
3.2 Analysis for MHR distributions
In this section state the results for the performance of Algorithm for MHR distributions and we provide a proof sketch for the single-bidder case. The full proof of the following theorem can be found in Appendix B.
Theorem 3.6. Let D' = Di x... X D be product distribution where every D is MHR. Let also D D= D, x ... D, be any product distribution such that for all i [m] it holds that dy (Di, D.) & os. If M is the mechanism that Algorithm I outputs with input D then it holds that
(1)0(a0)
1 1 Σ 03s 2x)) OPT(D").
Rev Rev(M, M,D")>
In particular for 1, if an then we have that Rev(M, Dr) > (1 - ( -PT(D*)
Proof sketch for 1. The first key step in our proof is the observation that, by construction, Algorithm runs the Myerson optimal auction on an MHR distribution F, such that F stochastically dominated by any other MHR distribution that within Big (F*). On the other hand we have d..FF*() F(x)) & Applying the triangle inequality, we have da F (x), F(x)) < 2a. is then sufficient for us bound the ratio of the optimal revenue for any two MHR distributions Fi and F2, with du (F1, F2) < 20, and where F is stochastically dominated by Fg.

---

The key part of our proof then considers such F1. F2, and due to the fact that the ratio of the revenues, OPT /OPT F2. is scale invariant, we assume without loss generality that OPT r. 1. We then prove that this leads to h(PF,) & 1. The result then follows from two further key lemmas.
First, for any reserve price Ph. [An (ar) h=(x))] = log 1-Fx(x) (()) Further applying the fact
that by assumption [F [2(x)) < a we show that |/, (2: - (a:) = ((a) for any reserve
price I < PE.- Second, using the fact that Fi is stochastically dominated by F2, we derive that
PF < PF. The conclusion then follows from bounding the ratio of 8 (1 = h (ar) log(z)) and
22) ) (x) log(z), based on the definition of Pt. and PF.
Next we show that the information-theorest Algorithm is optimal up to constants for MHR distributions. We provide the proof of the following theorem Appendix C.
Theorem 3.7. Let M be any DSIC and mechanism that takes as input a product distribution
D D2 .... Du-- Then there exists a product distribution D = =D; x X Di such that dDD); D:) < o, DJ is MHR for every i, and
Rev(M, < (1- a)) OPT(D")
3.3 Analysis for regular distributions
In this section we state the results for the performance of Algorithm for regular distributions and we provide a proof sketch for the single-bidder case. The full proof of the following theorem can be found in Appendix B.
Theorem 3.8. Let D* = x x xD,
nt be a product distribution where every Dj is regular. Let also D D= Dj x... D, be any product distribution such that for all i [m] it holds that dy (D, D:) & og. If M the mechanism that Algorithm 1 outputs with input D then holds that
Lev(M.D')
1-5
Σ ai
-OPTDD").
Proof sketch for = 1. We first prove general result that for two regular distributions F and F, such that dy (F, & a, where Fx)) is stochastically dominated by F(x) for x E R,. The optimal revenue of these two distributions is close, formally OPT(F)
OPT(F) > 1 The first key step replies using the link function h, (2:) I-F(z) for regular distributions. Since h, (2) preserves the same monotonicity property as F(x). we first derive a lower bound on h (z, F) that is (x, FF > (2, F') ah; (z, F), using the fact that da dx (F, F)= & This bound gives useful constraints to discuss in different cases in the following part of the proof. Denote the corresponding optimal reserve prices for F and F P and P. We discuss separately two cases for h(P). where, for case we have h( ((P)= < 1 and for case 2, we have h (P) > V Using the connection from the link
v
function to the revenue (see Figure I), case directly leads to the conclusion that OPT(F) OPT(F) > 1- Va. Case 2 more subtle and requires a more careful argument. Lastly, by construction, Algorithm runs the Myerson optimal auction on a regular distribution F, such that F > F'(x)) for all E R4,, for any other regular distribution (x) such that dy dx (z), Fx)) & a. Applying the triangle inequality and combining with the conclusions obtained from the two cases concludes the proof.
Finally, we show that the information- copmmattion-thooettie Algorithm is optimal up to constants for regular distributions. We provide the proof of the following theorem in Appendix C.
Theorem 3.9. Let M be any DSIC and IR mechanism that takes input a product distribution
D D2 ... D..- Then there exists a product distribution D D X ... X D such that
dD; D.) o. Dj is regular for every and
Rev(M,D') & (1 ((Vn.a)) OPT((D))
7

---

Finite Samples
We provide a practical algorithm that takes samples from the corrupted distribution D as an input. We show that this algorithm achieves almost optimal sample complexity for the MHR distribution case and the single-bidder regular distribution case, whereas for the multi-bidder regular distributions there small gap between our upper and lower bounds.
An important notion to explain our algorithm for the finite-sample case the following notion of the convex envelope.
Definition 4.1 (Convex Envelope). The convex envelope CJnw(() of function f is a function with the following property
(z) (x)(g(x)) g convex and over IR++).
In words, (fmv(f) is the maximum convex function that is below f.
For algorithm important property of the convex envelope is expressed in the following lemma whose proof is presented Appendix A.
Lemma 4.2. Let f be a non decceascgg piecewise constant function with pieces, then Conv(f) can be computed in time poly(k) (k) and is piecewise linear function with O(k) pieces.
Algorithm 2 Robust Empirical Myerson Auction
1: Input: m i.i.d samples from (possibly corrupted) value distribution D 11==, D,, link function h(-)).
2: Let E I E, be the empirical distribution, i.e., the uniform distribution the samples.
3: for = 1... n do
4: Construct F, as following: let (v)) be the quantile of Eg the quantile of E; is as follows:
g (v) max (c) (v) V (10 In(2mn5-1)
if o >> 0
5: Construct E; such that h (B:()) is the convex envelope of h (B()) i.e.
E,(-) h (Cono (Λ(É(O)))
6: end for
7: Set É 1 E,
8: Output Myerson's optimal auction Mg. w.r.t. E.
The above algorithm resembles the main algorithm of Guo et al. [2019] with the addition of step 5. We first show that step 5 necessary we wish to obtain any non-trivial result the robust auction learning setting that explore in this paper.
Counterexample 1. Imagine we have just one agent, i.e., n = 1, with true distribution D* equal to an exponential distribution with parameter À 1. Also, to strengthen our counterexample imagine that we have available an infinite number of samples, i.e., m - do. Now consider D to be the corrupted distribution where probability mass a is removed from the mass closer to 0 and it is placed as point mass at the point c/a for some number e. this case, running Algorithm 2 without step will result is implementing an auction with reserve price that is very close to c/a. The probability though that the true agent with distribution D* will buy this item goes to zero with a rate exp(-c/ as + co. Hence, the total revenue will be at most (c/a) exp(-c/o) and therefore we can make the total revenue to go to zero as we increase - oo. Observe that this counterexample works even though we assumed that the initial distribution D* is MHR.
We next provide the analysis of the performance of Algorithm for MHR and regular distributions. The proof of the following result can be found in Appendix D.

---

Theorem 4.3 (Finite samples, Regular distribution). Ler D Di x... D be product nt distribution where every D is regular. Let also D = DI x..,,, D, be any product distribution such that for all i [n) it holds that dy Dz) at. If M is the mechanism that Algorithm 2 outputs with input samples from D and assume that 52 (max4e[m) {log( (2s)))))))) then it holds that
Pr Rev (Me
11-
(1
Σ ai
n
OPT(D") > 21-8. 8.
Additionally, in the single- bidder case with 1 and ai the sample requirement becomes 52 (log())/a²/7))
The corresponding theorem for MHR distributions is the following, whose proof can be found in Appendix D.
Theorem 4.4 (Finite samples, MHR distribution). Ler D = xi x D be product distribution where every D is MHR. Let also D = "D x ... Dr be any product distribution such that for all i [n]] it holds that du (Di, D.) & a4. If M is the mechanism that Algorithm 2 outputs with input m samples from D and assume that 52 (max44((1) {log (t) /a.}) then it holds that
Σ 2a:))
at)) .)PTD)))))) 21
Pr Rev(MM,
1 1
We make a few remarks about the sample complexity upper bounds in the sequel.
First, in both Theorem 4.3 and Theorem 4.4, the sample complexity upper bounds depend in simple way on sum all the fractions of corruptions for each bidder; i.e., Σ,= ag indicating important effect of the total amount of corruption. Second, for regular distributions, in Theorem 4.3 obtain a tight sample complexity bound for the single-bidder case, with
52 (log( ( ///aa/3))))))) For
multi-bidder settings, our upper bound contains a small gap, with m = Å [max4e[ni { (log(t)/a()) Whether such gap can be matched is an interesting open question for future work. Lastly, comparing Theorem 4.3 and Theorem 4.4, it appears that for the bounds are of the same order, but emphasize the key difference that for regular distributions this sample size is needed to provide a much weaker guarantee on the revenue objective, which is a
settings the sample complexity
(I (1- (1-O ( fraction of the optimal revenue, while the guarantee for MHR distributions a (1 0 (E.)a))))) a:)) fraction of the optimal revenue.
We next provide an cntemattion-thhoreee lower bound that establishes the tightness of our upper bounds for the single-bidder single-item case with regular and MHR distributions.
Theorem 4.5 (Sample complexity lower bounds). Let M be any DSIC and IR mechanism for
single-item single-buyer setting that takes as input m. samples from distribution D. If
Rev M, D (1 11-00 ((((a)) OPT(D"),
for all distributions D such that (D", D) < a, where D* is regular, then m > E (log(2)/(3//3)
Additionally, if
Rev(M, D*) > (1 O(a)) OPT(D") for all distributions D' such that (D",
"0",7 (D < where D* is MHR, we have m > Ω (log()) /233)
Theorem 4.5 provides a general sample complexity lower bound on learning a near-optimal auction with at least (1 O n a)) fraction of the optimal revenue under the true valuation distribution. In comparison to our upper bounds (see Theorem 4.3 and Theorem 4.4), there is small gap and we leave the nature of this gap as an open question for future work.
5 Conclusions
We have studied the learning of revenue-optimal auctions for multiple bidders, setting in which the samples can be corrupted adversarially. We first consider the informationn-thcortiee limit in

---

population model, assuming exact knowledge of the adversarially perturbed valuation distribution. We develop a theoretical algorithm which obtains tight upper bound on the revenue for the MHR and regular distributions, obtaining the information- theeorrtc limit of the robustness guarantee. We then relax the population model and derive sample complexity bounds for learning optimal auctions from samples. We propose practical algorithm which takes the corrupted samples as input, and provide the sample complexity upper bounds for the MHR distribution case and the single-bidder regular distribution case. We also provide accompanying sample complexity lower bounds, and demonstrate a small gap relative to the corresponding upper bounds.
Acknowledgments and funding transparency statement.
We wish to acknowledge support from the Vannevar Bush Faculty Fellowship program under grant number N00014-21- 11001--21-1---- 11---2941. WG also acknowledges support from a Google PhD fellowship. MZ was supported by NSF DMS-2023505 (FODSI).
References
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. arXiv preprint 1eXiv:1606.044 2016.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 173-174, 2018.
Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without item- independence: Learnability via robustness. In Proceedings of the 21st ACM Conference Economics and Computation, pages 715-761, 2020.
Mark M Bykowsky, Robert J Cull, and John O Ledyard. Mutually destructive bidding: The FCC auction design problem. Journal of Regulatory Economics, 17(3):205-228, 2000.
Yang Cai and Constantinos Daskalakis. Extreme-value theorems for optimal multidimensional pricing. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 522 531. IEBE, 2011.
Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pages 516-527. IEEE, 2017.
Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pages 243-252, 2014.
Nikhil R Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pages 426-439. 2016.
Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jen- nifer Wortman Vaughan. Oracle-effiiennt online learning and auction design. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, pages 528-55282 539. IEEE, 2017.
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
Yannai A Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single- parameter auction environments. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 856-868, 2017.
Yannai A Gonezarowski and S Matthew Weinberg. The sample complexity of up-to-e multi- dimensional revenue maximization. Journal of the ACM, 68(3):1228, 2021.
10

---

Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang, Settling the sample complexity of single-paramen parameter revenue maximization. In Proceedings of the S1st Annual ACM SIGACT Symposium on Theory of Computing, pages 662-673, 2019.
Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. SIAM Journal on Computing, 47(3):651--0 674,, 2018.
Paul Klemperer. What really matters in auction design. Journal of Economic Perspectives, 16(1): 169-189, 2002.
Sébastien Lahaie, David M Pennock, Amin Saberi, and Rakesh V Vohra. Sponsored search auctions. Algorithmic Game Theory, 1:699-716, 2007.
Pascal Massart. The tight constant in the Dvoretzky-Kiene BeentikkKKKier----re wiffeo inequality. The Annals of Probability, pages 1269-1283, 1990.
Paul Milgrom and Paul Robert Milgrom. Putting Auction Theory to Work. Cambridge University Press, 2004.
Jamie Morgenstern and Tim Roughgarden. The pseudo-dimension of near-optimal auctions, arXiv preprint orXiv:/506.03660 2015.
Jamic Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory, pages 1298-1318. PMLR, 2016.
Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
Alvin Roth and Axel Ockenfels. Last-minute bidding and the rules for ending second-price auctions: Evidence from ebay and amazon auctions on the internet. American Economic Review, 92(4): 1093-1103, 2002.
Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the 2016 ACM Conference Economics and Computation, pages 1-18, 2016.
Tim Roughgarden and Joshua R Wang. Minimizing regret with multiple reserves, ACM Transactions on Economics and Computation, 7(3):1-18, 2019.
Vasilis Syrgkanis. A sample complexity measure with applications to learning optimal auctions. arXiv preprint arXiv: 025980 2017.

---

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 aim to provide a holistic picture by investigating both the upper and lower learning bounds in the settings of interest. We provided discussions when they do not match by small factor in specific multi-bidder case and leave that an open question for future work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We study the theoretical limit on the learnability of robust optimal auctions and provide information theoretical limit with sample complexity bounds under certain model assumptions.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] see all Theorem/Proposition statements.
(b) Did you include complete proof' of all theoretical results? [Yes] see Appendix for all missing proofs.
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 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 (c.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/releusing new assets...
(a) 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]
(c) Did you discuss whether the data you 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 participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "fQlZe4uUIO-", "reviewer": "Reviewer_WsiF", "summary": "This paper studies the problem of learning revenue-optimal single-item auction using bidder valuation samples with adversarial corruptions. \n\nThe paper first studies the case when there’s a given distribution. When the true distribution is alpha-close to the given distribution in Kolmogorov-Smirnov distance, the paper shows an algorithm to to get at least 1-O(alpha) of the optimal revenue for regular distributions and at least 1-O(sqrt(alpha)) of the optimal revenue for MHR distributions. The paper also provides negative results to show the algorithms are tight.\n\nThe paper also gives an algorithm of approximating optimal auction when only samples from the given distribution are provided.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Robust learning optimal auctions is a very important problem. In general the paper is well-written. \n\nThe paper’s results for a given distribution are pretty complete. The only comment is that it would be better if the lower bounds (Thm 3.7, 3.9) provided can be improved to prove for any vector of (alpha_1,...,alpha_n). And it might be better to make it clear that to what extent these lower bounds show the algorithm is optimal (the algorithm would look more optimal if a more instance-dependent lower bound can be shown). \n\nI have some comments about the results for the sample access case. \n1) The bounds are not tight and make the results less complete. \n2) The paper chooses to study the case when the distribution is adversarially corrupted. I am wondering how much it can say about the case when some samples are adversarially corrupted.\n3) In the sample access setting, for a given corrupted distribution, an algorithm should tradeoff between the revenue guarantee and the number of samples. The paper’s theorem only gives one point on this tradeoff curve. I am wondering what will be the complete picture of the tradeoff (for example, by relaxing distance guarantee, you can get more tradeoff points). \n4) It might be good to compare the performance of the paper’s algorithm in the case with 0 corruptions to prior work to get a sense of how tight the result is.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "OnffCa_gS5I", "reviewer": "Reviewer_fxPB", "summary": "This paper studies the problem of revenue maximization in a single-item setting, with one or many bidders, when the value distribution of the bidders presented to the mechanism designer may be corrupted. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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 studies the problem of revenue maximization in a single-item setting, with one or many bidders, when the value distribution of the bidders presented to the mechanism designer may be corrupted. The mechanism designer either has exact knowledge of the adversarially corrputed distribution, or only sample access to it. In both these models, the paper develops mechanisms that obtain good revenue when compared to the original distribution. In particular, when we fix an original product distribution D*, and consider any corrupted product distribution \\tilde{D}, s.t., for each i, \\tilde{D_i} is within an \\alpha_i Kolmogorov-Smirnov distance of D*, the algorithm can take any such \\tilde{D} as input and output a mechanism that gets good revenue w.r.t. D*. The \"goodness\" is measured through an approximation factor, which is multiplicative, and is equal to (1-O(\\sum_i \\alpha_i)) for MHR distributions and is equal to (1-O(\\sum_i \\sqrt{\\alpha_i})) for regular distributions. \n\nThe distributions are unbounded, and this consitutes the primary difference of this work from earlier works that assume bounded distributions and obtain additive approximations that are dependent on the upper bound H of the support. No result can be obtained for all distributions. So the previous results restrict through boundedness, and this result restricts through MHR and regularity. But the important part is that MHR/regularity restriction leads to development of new techniques in this work. \n\nIn particular, the paper develops the notion of link and inverse-link functions. For MHR, the link function is -ln(1-F(x)), and for regular it is 1/(1-F(x)). These link functions, apart from having nice properties like convex and non-decreasing, also provide an alternate characterization for the monopoly price and optimal revenue.  The optimal algorithm simply outputs the Myerson optimal auction for the minimal distribution in the Kolmogorov ball around the input distribution \\tilde{D}, where the notion of minimality crucially uses the link function definition. \n\nThe paper also provides nearly matching upper and lower bounds on sample complexity in the sample model. \n\nOverall, this is a pretty neat contribution to mechanism design literature, and is a good fit for NeurIPS. \n\nSpecific comments:\n\n1) Page 4, line 2: it should be \\mu and \\nu. Currently it is written as \\mu and \\mu.\n2) Definition 3.5: give --> given\n3) Definition 3.5: The quantity after \\leq should not be F I think; it should be \\alpha? Also, the ball is currently defined for one bidder distributions. Extension to product distribution is clear, but would be nice to explicitly spell it out. \n4) Definition 3.5 is written in terms of cdfs. This is understood, but good to explicitly mention this.\n5) In the definition of \\hat{h} in equation 1: under the max it says F is MHR/regular. What is F? Do you mean F-bar? Also, in general it is good to avoid the F-bar notation as it is sometimes used to refer to 1-F. \n6) In the \\hat{F} that is finally computed in Equation (1): how do we ensure that it is MHR/regular? If the F-bars that get used are MHR/regular, then the \\hat{F} that comes out is also MHR/regular I guess? Please expand a bit on it. ", "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": "4.5"}, "extra_text": {}}, {"review_id": "ETjJeXr2b8N", "reviewer": "Reviewer_gj2u", "summary": "The paper studies the problem of designing approximately revenue-optimal auctions using corrupted / inaccurate priors, where inaccuracy is measured by the Kolmogorov-Smirnov distance, i.e., the maximum difference in the two CDFs.  The authors consider the multi-bidder single-item setting, and focus on the cases of regular and MHR prior distributions.  Notably, they do not assume bounded support.  The main results are almost matching (multiplicative) upper and lower bounds on the maximum revenue achievable given inaccurate priors with bounded KS distances to the real ones.  The authors further apply their results to sample-based settings, and derive similar upper bounds with polynomial number of samples from the inaccurate priors.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths\n\nThe paper is overall well written.  The problem of auction design using corrupted / inaccurate priors is important, and has numerous potential applications (including auction design from samples as discussed in the paper).  The authors provide almost matching upper and lower bounds for this problem for both regular and MHR value distributions, which demonstrate a curious distinction between the two classes of distributions.  The technical contributions regarding inaccurate priors appear nontrivial (e.g., the use of link functions appears insightful, unbounded support and multiplicative approximations are subtle but quite often technically challenging).\n\n\nWeaknesses\n\nWhile I'm overall positive about the paper, my main concern is whether the paper makes sufficient *conceptual* contribution to the problem (I think the technical contribution is well justified).  Quite some prior work explicitly or implicitly (primarily dealing with problems such as dynamic auctions, auction design from samples, etc.) studies auction design with inaccurate priors, and I think (and I could be wrong) that some previous results also rely on assumptions about the Kolmogorov-Smirnov distance, which emerge naturally in auction design from samples.  From the discussion in the paper, the impression I got is that the main conceptual difference between this paper and prior work is in unbounded distributions.  While this is certainly an issue worth addressing, I'd be more excited if the authors could provide further justifications regarding the importance of this particular issue, or point out other conceptual contributions of the paper (e.g., are these the first almost tight bounds?).\n\n\nDetailed comments\n\nDef 3.5: \"d_k(F', F) \\le F\": F => \\alpha\n\nFirst paragraph in sec 3.2, \"... can be found in Appendix G\" (and several other places): do you mean Appendix B?\n\nThm 3.7: what happend to the 1/ln(n) factor in the proof in Appendx C.1?\n\nProof sketch of thm 3.8, first sentence, \"F(x) is stochastically dominated by F(x) for all x\": this can't be right...\n\nThm 4.3 (and 4.4): is this just because the empirical CDF uniformly converges to the population CDF at rate m^{-1/2}?\n\nLine 313, \"sample complexity upper bounds depend on sum of \\alpha_i\": doesn't it depend on max_i \\alpha_i^2?  Also \"depends\" => \"depend\"\n\nLine 315, discussion about lower bounds: it's a bit confusing to see this before seeing the lower bounds (thm 4.5)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't have concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the revenue-optimal mechanism design when the bidder value distribution can be adversarially corrupted, and gives tight bounds on the achievable approximation and the sample complexity. This is a nice contribution and a good fit to NeurIPS.
Decision: Accept (Spotlight)