Robust Learning of Optimal Auctions

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

text: √ α) 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.

heading: 1 Introduction
text: 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 (NeurIPS 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.

heading: 1.1 Our results
text: 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.

heading: 1.2 Related work
text: 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.

heading: 2 Preliminaries
text: 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.

heading: 2.1 Auction models
text: 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(µ, ν) 6 dTV (µ, ν), where dTV denotes the total variation (TV) distance between µ and ν. The closeness of D̃ to D∗ is thus formalized as follows:
dk(D∗, D̃) 6 α, 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[ ∑ 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̃ = D̃1 × · · · × D̃n, where each D̃i satisfies
dk(D∗i , D̃i) 6 α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′.

heading: 2.2 Monotone hazard rate (MHR) and regular distributions
text: 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.

heading: 3 The Population Model
text: 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.

heading: 3.1 Robust Myerson auction in the population model
text: Our algorithm assumes as an input the exact knowledge of a product distribution, D̃ = D̃1×· · ·×D̃n, such that the dk(D∗i , D̃i) 6 αi and its goal is to find a mechanism that achieves approximately optimal revenue for D∗, where D∗ = ΠiD∗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 hM (x;F ) for MHR distributions is defined as hM (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−1M (x;h) = 1 − exp(−h(x)) and h−1r (x;h) = 1 − 1/h(x). Observe that h−1M (x;hM (x;F )) = F (x) and h−1r (x;hr(x;F )) = F (x). We may write hM (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 (hM (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 hM and hr explicitly, for a single-item, single-bidder auction.
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) 6 F2(x),
denoted as D1 D2. We say a product distribution D = ΠiDi (component-wise) stochastically dominates another product distribution D′ = ΠiD′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) 6 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̃ = Πni=1F̃i. 2: for i = 1. . . n do 3: Compute a minimal regular / MHR distribution in
Bdk,αi(F̃i) according to Eq (1), denote as F̂i. 4: end for 5: Set F̂ = Πni=1F̂i. 6: Output Myerson’s optimal auction MF̂ w.r.t. the distri-
bution F̂ .
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 hM (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 hM (x;F1) 6 hM (x;F2) (resp. hr(x;F1) 6 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 ) 6 α}.
Further, define a minimal MHR/regular distribution within Bdk,α(F ) as:
F̂ (x) = h−1(x; ĥ), where ĥ(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.

heading: 3.2 Analysis for MHR distributions
text: 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̃ = D̃1 × · · · D̃n be any product distribution such that for all i ∈ [n] it holds that dk(D∗i , D̃i) 6 αi. If M̃ is the mechanism that Algorithm 1 outputs with input D̃ then it holds that
Rev(M̃,D∗) > ( 1− Õ ( n∑ i=1 αi )) ·OPT(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 F̂ , such that 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)) 6 α. Applying the triangle inequality, we have dk(F ∗(x), F̂ (x)) 6 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) 6 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) 6 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)| 6 α 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 6 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̃ = D̃1 × · · · × D̃n. Then there exists a product distribution D∗ = D∗1 × · · · × D∗n such that dk(D∗i , D̃i) 6 α, D∗i is MHR for every i, and
Rev(M,D∗) 6 (1− Ω̃(n · α)) ·OPT(D∗).

heading: 3.3 Analysis for regular distributions
text: 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 everyD∗i is regular. Let also D̃ = D̃1 × · · · D̃n be any product distribution such that for all i ∈ [n] it holds that dk(D∗i , D̃i) 6 αi. If M̃ is the mechanism that Algorithm 1 outputs with input D̃ then it holds that
Rev(M̃,D∗) > 1− 5 · √√√√ n∑
i=1
αi  ·OPT(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̄ ) 6 α, 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) = 11−F (x) for regular distributions. Since hr(x) preserves the same monotonicity property as F (x), we first derive a lower bound on h̄r(x, F̄ ) that is h̄r(x, F̄ ) > hr(x, F )− αh2r(x, F ), using the fact that dk(F, F̄ ) 6 α. 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̄ ) 6 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 F̂ , such that F̂ > F̂ ′(x) for all x ∈ R+, for any other regular distribution F ′(x) such that dk(F ′(x), F̃ (x)) 6 α. 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̃ = D̃1 × · · · × D̃n. Then there exists a product distribution D∗ = D∗1 × · · · × D∗n such that dk(D∗i , D̃i) 6 α, D∗i is regular for every i, and
Rev(M,D∗) 6 (1− Ω( √ n · α)) ·OPT(D∗).

heading: 4 Finite Samples
text: 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 6 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 = Πni=1Di, link function h(·).
2: Let E = Πni=1Ei be the empirical distribution, i.e., the uniform distribution over the samples. 3: for i = 1 . . . n do
4: Construct Êi as following: let qEi(v) be the quantile of Ei; the quantile of Êi is as follows:
qÊi(v) = max { 0, qEi(v)− √ 2qEi (v)(1−qEi (v)) ln(2mnδ−1) m − 4 ln(2mnδ−1) m − αi } if v > 0
1 if v = 0 5: Construct Ẽi such that h ( Ẽi(·) ) is the convex envelope of h ( Ê(·) ) , i.e.
Ẽi(·) = h−1 ( Conv ( h(Êi(·)) )) 6: end for 7: Set Ẽ = Πni=1Ẽi 8: Output Myerson’s optimal auction MẼ 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̃ = D̃1 × · · · D̃n be any product distribution such that for all i ∈ [n] it holds that dk(D∗i , D̃i) 6 α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
Pr Rev(M̃,D∗) > 1−O √√√√ n∑ i=1 αi  ·OPT(D∗)  > 1− δ.
Additionally, in the single-bidder case with n = 1 and α = α1 the sample requirement becomes m = Ω̃ ( log( 1δ )/α 3/2 ) .
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̃ = D̃1 × · · · D̃n be any product distribution such that for all i ∈ [n] it holds that dk(D∗i , D̃i) 6 αi. If M̃ is the mechanism that Algorithm 2 outputs with input m samples from D̃ and assume that m = Ω̃ ( maxi∈[n] { log ( 1 δ ) /α2i }) then it holds that
Pr ( Rev(M̃,D∗) > ( 1− Õ ( n∑ i=1 αi )) ·OPT(D∗) ) > 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 a simple way on the sum of all the fractions of corruptions for each bidder; i.e., ∑n 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 (√∑n
i=1 αi
)) fraction of the optimal revenue, while the guarantee for MHR distributions
is a (1−O ( ∑n 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̃) 6 α, where D∗ is regular, then m > Ω̃ ( log( 2δ )/α 3/2 ) . Additionally, if Rev(M,D∗) > (1−O(α)) ·OPT(D∗),
for all distributionsD∗ such that dk(D∗, D̃) 6 α, whereD∗ is MHR, we havem > Ω̃ ( log( 2δ )/α 3/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.

heading: 5 Conclusions
text: 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 PhD fellowship. MZ was supported by NSF DMS-2023505 (FODSI).

Review summaries:
This paper studies the problem of learning revenue-optimal single-item auction using bidder valuation samples with adversarial corruptions.   The 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.  The paper also gives an algorithm of approximating optimal auction when only samples from the given distribution are provided. 

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.