# robust_learning_of_optimal_auctions__eca2f757.pdf

Robust Learning of Optimal Auctions

Wenshuo Guo University of California, Berkeley wguo@cs.berkeley.edu

Michael I. Jordan University of California, Berkeley jordan@cs.berkeley.edu

Manolis Zampetakis University of California, Berkeley mzampet@berkeley.edu

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 α-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(α) 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( α) 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.

1 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 et 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 a valuation over the available items, and if 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 is the optimal mechanism in terms of the expected revenue? This problem was solved by Myerson [1981] through a characterization of virtual value functions. In particular, we can define a virtual value function of each buyer based on their

35th Conference on Neural Information Processing Systems (Neur IPS 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.1

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 et al., 2016, Morgenstern and Roughgarden, 2015, 2016, Syrgkanis, 2017, Dudík et al., 2017, Gonczarowski and Nisan, 2017, Huang et 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, a 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. It is a challenging problem; indeed, as we show in Counterexample 1 in Section 4, auction designs that are optimal in the absence of corruptions can become arbitrarily bad even if a small portion of the samples are corrupted. Building on earlier work by Cai and Daskalakis [2017] and Brustle et al. [2020], we tackle a 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?

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-Smirnov (KS) distance α 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 ρ(α)) OPT for the smallest possible error ρ(α) and with the use of a 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 a corrupted distribution under a population model. For distributions with monotone hazard rate (MHR), and with total corruption α, we obtain an approximation ratio of 1 O(α) compared to the optimal revenue under the true distribution (see Theorem 3.6). For regular valuation distributions, where for total corruption α, we get an approximation ratio of 1 O( α) (see Theorem 3.8).

2. To achieve these upper bounds, we propose a new theoretical algorithm for the population model (see Algorithm 1) 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 α-close to the given distribution in Kolmogorov-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 a 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

1More 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 a 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 approximately 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 a 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 an auction which maximizes the expected revenue on the underlying, unknown distribution over bidder valuations. 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 is closely related to 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 a given approximate distribution, and the goal is to compute an auction whose revenue is approximately optimal simultaneously for all true distributions" that are close to the given one. They provide an algorithm that achieves a poly-α 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, a 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 3 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 4 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 5.

2 Preliminaries

We begin by formally defining the setting we 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 v R+ for this item. We assume that v is a 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) = v 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 v and D are unknown to the seller.

However, the seller can access i.i.d. samples that are drawn from a distribution D, which is α-close to D with regard to the Kolmogorov distance: Definition 2.1. (Kolmogorov-Smirnov distance) For probability measures µ and ν on R, define

dk(µ, ν) = sup x R |µ(( , x)) ν(( , x))|.

It is well known that dk(µ, ν) d T V (µ, ν), where d T V denotes the total variation (TV) distance between µ and ν. The closeness of D to D is thus formalized as follows:

dk(D , D) α,

for some α > 0.

Multi-bidder setting. Consider one item for sale to n bidders. Each bidder has a private valuation, vi R+, where vi is independently drawn from the corresponding prior distribution D i . Thus, the valuations v = (v1, v2, , vn) follow a product distribution D = D 1 D n. Each bidder submits a bid bi 0. Denote all the bids as b = (b1, , bn). A mechanism in this setting consists of two rules: the allocation rule x(b) that takes the bids b and outputs the probability xi(b) 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 ui(b) = vi xi(b) pi(b). The goal of the seller is to find a mechanism that maximizes the expected revenue E[P

i [n] pi(b)], where the expectation is over v D , under the following Dominant Strategy Incentive Compatibility (DSIC) and the Individual Rationality (IR) constraints:

ui(vi, b i) ui(bi, b i) for all vi, bi R+ and all b i Rn 1 + (DSIC)

ui(vi, b i) 0 for all vi R+ and all b i Rn 1 + . (IR)

We consider the setting in which the valuations and the prior distributions are unknown to the seller. Instead, the seller has access to a finite number of i.i.d. samples drawn from the product distribution D = D1 Dn, where each Di satisfies

dk(D i , Di) αi,

for some αi > 0, i [n].

Revenue objective. Letting D, D be product or single bidder distributions as described above, we define MD to be the mechanism that achieves the optimal revenue for the value distributions D 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 a valuation vi Di, define the virtual value function for this bidder as φi(v) def = v 1 Fi(v)

fi(v) , where Fi and fi are the CDF and PDF of Di. The hazard rate of the

distribution Di is defined as the function fi(v) 1 Fi(v). Then, the distribution Di is said to be regular if the virtual value φi(v) is monotonically non-decreasing in v. Further, distribution Di has monotone hazard rate (MHR) if fi(v) 1 Fi(v) is monotone non-decreasing.

3 The Population Model

In this section, we 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 4 where we show how to learn optimal auctions when we only have sample access to D.

We begin in Section 3.1 with the description 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 of 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 a proof sketch for the single-bidder 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 = D1 Dn, such that the dk(D i , Di) αi and its goal is to find a mechanism that achieves approximately optimal revenue for D , where D = Πi D i . Without further assumptions, this is an impossible task, as we explain in Section 4 via an example. Thus we assume that the algorithm possesses some additional knowledge regarding D i , either that it is MHR or regular, and the mechanism needs to exploit this additional property.

To utilize the additional property of the distributions D i , our mechanism uses the important concept of the link function for MHR and regular distributions. Definition 3.1 (Link Function). The link function h M(x; F) for MHR distributions is defined as h M(x; F) = ln(1 F(x)) and the link function hr(x; F) for regular distributions is defined as hr(x; F) = 1/(1 F(x)). We also define the corresponding inverse link functions h 1 M (x; h) = 1 exp( h(x)) and h 1 r (x; h) = 1 1/h(x). Observe that h 1 M (x; h M(x; F)) = F(x) and h 1 r (x; hr(x; F)) = F(x). We may write h M(x) or hr(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 a regular distribution is convex and non-decreasing. Second, the link function is monotone with regard to F. These two properties are important when we define the notion of a minimal MHR/regular distribution in a Kolmogorov ball, momentarily, which will be used as a 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 is MHR or regular. To see this, first consider a single bidder with a valuation distribution F. Denote the optimal reserve price for selling one item to her as x , and the optimal expected revenue as OPT(F). Then, when F is MHR, we show that x is also the unique minimizer of (h M(x) log(x)). On the other hand, when F is regular, v is the point where hr(x) intersects with its tangent line kx, with k = 1/OPT(F ) (proof details in Appendix). Figure 1 illustrates such a useful property for h M and hr explicitly, for a single-item, single-bidder auction.

log(x) log(OPT(F))

Figure 1: Optimal reserve price x with regard to 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 D1 and D2 with CDFs as F1 and F2. Then, we say D1 (first-order) stochastically dominates D2 if for every x X,

F1(x) F2(x),

denoted as D1 D2. We say a product distribution D = Πi Di (component-wise) stochastically dominates another product distribution D = Πi D i if for every i, we have Di D i. Lemma 3.3 (Strong revenue monotonicity [Guo et al., 2019]). Let D, D be two product distributions such that D D, then, for M that is the optimal mechanism for D, we have:

Rev(M, D) Rev(M, D ).

Algorithm 1 Robust Myerson Auction in the Population Model

1: Input: α1 . . . αn > 0, link function h( ), possibly corrupted valuation distribution F = Πn i=1 Fi. 2: for i = 1...n do 3: Compute a minimal regular / MHR distribution in Bdk,αi( Fi) according to Eq (1), denote as b Fi. 4: end for 5: Set b F = Πn i=1 b Fi. 6: Output Myerson s optimal auction M b F w.r.t. the distribution b F.

Figure 2: A minimal regular distribution in Bdk,α, in the space transformed by applying the link function.

The following lemma illustrates the importance of the link functions as well as their connection with first-order stochastic dominance. The proof of this lemma is given in Appendix A. Lemma 3.4. A distribution with CDF F is MHR if and only if h M(x; F) is a convex function of x. Similarly, F is regular if and only if hr(x; F) is a convex function of x. Moreover, for two MHR (resp. regular) distributions F1 and F2, such that F1 F2, we have that h M(x; F1) h M(x; F2) (resp. hr(x; F1) hr(x; F2)) for all x.

A 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 F, denote the set of all the distributions that are α-close to F in Kolmogorov distance as Bdk,α(F):

Bdk,α(F) def = {F : dk(F , F) α}.

Further, define a minimal MHR/regular distribution within Bdk,α(F) as:

b F(x) = h 1(x;bh), where bh(x) def = max F Bdk,α(F ) F is MHR / regular

h F(x) x R+. (1)

Figure 2 gives an illustration of a minimal regular distribution within Bdk,α(F), in the space transformed by the link function of regular distributions.

3.2 Analysis for MHR distributions

In this section we state the results for the performance of Algorithm 1 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 = D 1 D n be a product distribution where every D i is MHR. Let also D = D1 Dn be any product distribution such that for all i [n] it holds that dk(D i , Di) αi. If M is the mechanism that Algorithm 1 outputs with input D then it holds that

Rev( M, D )

In particular for n = 1, if α = α1, then we have that Rev( M, D ) (1 O (α)) OPT(D ).

Proof sketch for n = 1. The first key step in our proof is the observation that, by construction, Algorithm 1 runs the Myerson optimal auction on an MHR distribution b F, such that b F is stochastically dominated by any other MHR distribution that is within Bdk,α( F ). On the other hand we have dk(F (x), F(x)) α. Applying the triangle inequality, we have dk(F (x), b F(x)) 2α. It is then sufficient for us to bound the ratio of the optimal revenue for any two MHR distributions F1 and F2, with dk(F1, F2) 2α, and where F1 is stochastically dominated by F2.

The key part of our proof then considers such F1, F2, and due to the fact that the ratio of the revenues, OPTF1/OPTF2, is scale invariant, we assume without loss of generality that OPTF1 = 1. We then prove that this leads to h(P F1) 1. The result then follows from two further key lemmas.

First, for any reserve price x < P F1, |h1(x) h2(x)| = log 1 F2(x) 1 F1(x) . Further applying the fact that by assumption |F1(x) F2(x)| α we show that |h1(x) h2(x)| = O(α) for any reserve price x < P F1. Second, using the fact that F1 is stochastically dominated by F2, we derive that P F2 P F1. The conclusion then follows from bounding the ratio of s1(x) = h1(x) log(x), and s2(x) = h2(x) log(x), based on the definition of P F1 and P F2.

Next we show that the information-theoretic Algorithm 1 is optimal up to constants for MHR distributions. We provide the proof of the following theorem in Appendix C.

Theorem 3.7. Let M be any DSIC and IR mechanism that takes as input a product distribution D = D1 Dn. Then there exists a product distribution D = D 1 D n such that dk(D i , Di) α, D i is MHR for every i, and

Rev(M, D ) (1 Ω(n α)) OPT(D ).

3.3 Analysis for regular distributions

In this section we state the results for the performance of Algorithm 1 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 = D 1 D n be a product distribution where every D i is regular. Let also D = D1 Dn be any product distribution such that for all i [n] it holds that dk(D i , Di) αi. If M is the mechanism that Algorithm 1 outputs with input D then it holds that

Rev( M, D )

Proof sketch for n = 1. We first prove a general result that for two regular distributions F and F, such that dk(F, F) α, where F(x) is stochastically dominated by F(x) for x R+. The optimal revenue of these two distributions is close, formally OPT(F )

OPT( F ) 1 O( α). The first key step replies on using the link function hr(x) = 1 1 F (x) for regular distributions. Since hr(x) preserves the same monotonicity property as F(x), we first derive a lower bound on hr(x, F) that is hr(x, F) hr(x, F) αh2 r(x, F), using the fact that dk(F, F) α. This bound gives us useful constraints to discuss in different cases in the following part of the proof. Denote the corresponding optimal reserve prices for F and F as P and P. We discuss separately two cases for h( P), where, for case 1 we have h( P) 1 α, and for case 2, we have h( P) > 1 α. Using the connection from the link

function to the revenue (see Figure 1), case 1 directly leads to the conclusion that OPT(F )

OPT( F ) 1 α. Case 2 is more subtle and requires a more careful argument. Lastly, by construction, Algorithm 1 runs the Myerson optimal auction on a regular distribution b F, such that b F b F (x) for all x R+, for any other regular distribution F (x) such that dk(F (x), F(x)) α. Applying the triangle inequality and combining with the conclusions obtained from the two cases concludes the proof.

Finally, we show that the information-theoretic Algorithm 1 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 as input a product distribution D = D1 Dn. Then there exists a product distribution D = D 1 D n such that dk(D i , Di) α, D i is regular for every i, and

Rev(M, D ) (1 Ω( n α)) OPT(D ).

4 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 is a small gap between our upper and lower bounds.

An important notion to explain our algorithm for the finite-sample case is the following notion of the convex envelope. Definition 4.1 (Convex Envelope). The convex envelope Conv(f) of a function f is a function with the following property

Conv(f)(x) = sup{g(x) | g is convex and g f over R+}.

In words, Conv(f) is the maximum convex function that is below f.

For our algorithm one important property of the convex envelope is expressed in the following lemma whose proof is presented in Appendix A. Lemma 4.2. Let f be a non-decreasing piecewise constant function with k pieces, then Conv(f) can be computed in time poly(k) and is a 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 = Πn i=1Di, link function h( ). 2: Let E = Πn i=1Ei be the empirical distribution, i.e., the uniform distribution over the samples.

3: for i = 1 . . . n do

4: Construct c Ei as following: let q Ei(v) be the quantile of Ei; the quantile of c Ei is as follows:

q b Ei(v) =

max 0, q Ei(v) q

2q Ei(v)(1 q Ei(v)) ln(2mnδ 1)

m 4 ln(2mnδ 1)

5: Construct Ei such that h Ei( ) is the convex envelope of h b E( ) , i.e.

Ei( ) = h 1 Conv h( b Ei( ))

7: Set E = Πn i=1 Ei 8: Output Myerson s optimal auction M E 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 is necessary if we wish to obtain any non-trivial result in the robust auction learning setting that we 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 . Now consider D to be the corrupted distribution where probability mass α is removed from the mass closer to 0 and it is placed as a point mass at the point c/α for some number c. In this case, running Algorithm 2 without step 5 will result is implementing an auction with reserve price that is very close to c/α. The probability though that the true agent with distribution D will buy this item goes to zero with a rate exp( c/α) as c . Hence, the total revenue will be at most (c/α) exp( c/α) and therefore we can make the total revenue to go to zero as we increase c . 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 2 for MHR and regular distributions. The proof of the following result can be found in Appendix D.

Theorem 4.3 (Finite samples, Regular distribution). Let D = D 1 D n be a product distribution where every D i is regular. Let also D = D1 Dn be any product distribution such that for all i [n] it holds that dk(D i , Di) αi. If M is the mechanism that Algorithm 2 outputs with input m samples from D and assume that m = Ω maxi [n] log( 1

δ )/α2 i then it holds that

Rev( M, D )

Additionally, in the single-bidder case with n = 1 and α = α1 the sample requirement becomes m = Ω log( 1

The corresponding theorem for MHR distributions is the following, whose proof can be found in Appendix D. Theorem 4.4 (Finite samples, MHR distribution). Let D = D 1 D n be a product distribution where every D i is MHR. Let also D = D1 Dn be any product distribution such that for all i [n] it holds that dk(D i , Di) αi. If M is the mechanism that Algorithm 2 outputs with input m samples from D and assume that m = Ω maxi [n] log 1

δ /α2 i then it holds that

Rev( M, D )

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 a simple way on the sum of all the fractions of corruptions for each bidder; i.e., Pn i=1 αi, indicating the important effect of the total amount of corruption. Second, for regular distributions, in Theorem 4.3 we obtain a tight sample complexity bound for the single-bidder case, with m = Ω log( 1

δ )/α3/2 . For multi-bidder settings, our upper bound contains a small gap, with m = Ω maxi [n] log( 1

δ )/α2 i . Whether such a 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 multi-bidder settings the sample complexity bounds are of the same order, but we 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 1 O p Pn i=1 αi fraction of the optimal revenue, while the guarantee for MHR distributions

is a (1 O (Pn i=1 αi)) fraction of the optimal revenue.

We next provide an information-theoretic 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 a single-item single-buyer setting that takes as input m samples from a distribution D. If

Rev(M, D ) (1 O( α)) OPT(D ),

for all distributions D such that dk(D , D) α, where D is regular, then m Ω log( 2

δ )/α3/2 . Additionally, if Rev(M, D ) (1 O(α)) OPT(D ),

for all distributions D such that dk(D , D) α, where D is MHR, we have m Ω log( 2

Theorem 4.5 provides a general sample complexity lower bound on learning a near-optimal auction with at least a (1 O( n α)) 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 a 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, in a setting in which the samples can be corrupted adversarially. We first consider the information-theoretic limit in a

population model, assuming exact knowledge of the adversarially perturbed valuation distribution. We develop a theoretical algorithm which obtains a tight upper bound on the revenue for the MHR and regular distributions, obtaining the information-theoretic limit of the robustness guarantee. We then relax the population model and derive sample complexity bounds for learning optimal auctions from samples. We propose a 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-1-2941. WG also acknowledges support from a Google Ph D fellowship. MZ was supported by NSF DMS-2023505 (FODSI).

Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. ar Xiv preprint ar Xiv:1606.04145, 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 itemindependence: Learnability via robustness. In Proceedings of the 21st ACM Conference on 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. IEEE, 2011.

Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In 2017 IEEE 58th Annual Symposium on 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 Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, pages 528 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 singleparameter auction environments. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 856 868, 2017.

Yannai A Gonczarowski and S Matthew Weinberg. The sample complexity of up-to-ε multidimensional revenue maximization. Journal of the ACM, 68(3):1 28, 2021.

Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-parameter revenue maximization. In Proceedings of the 51st 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 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-Kiefer-Wolfowitz 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. ar Xiv preprint ar Xiv:1506.03684, 2015.

Jamie 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 E 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 on 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. ar Xiv preprint ar Xiv:1704.02598, 2017.

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 a small factor in a specific multi-bidder case and leave that as 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 to 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 proofs 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 experimental results (either in the supplemental material or as a URL)? [N/A] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] (c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A] (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...

(a) If your work uses existing assets, did you cite the creators? [N/A] (b) Did you mention the license of the assets? [N/A]

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]

(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A] (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] 5. If you used crowdsourcing or conducted research with human subjects...

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]