Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.

main_review: Robust learning optimal auctions is a very important problem. In general the paper is well-written. 

The 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). 

I have some comments about the results for the sample access case. 
1) The bounds are not tight and make the results less complete. 
2) 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.
3) 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). 
4) 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.

limitations_and_societal_impact: Limitations are discussed above.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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. 

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

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

The paper also provides nearly matching upper and lower bounds on sample complexity in the sample model. 

Overall, this is a pretty neat contribution to mechanism design literature, and is a good fit for NeurIPS. 

Specific comments:

1) Page 4, line 2: it should be \mu and \nu. Currently it is written as \mu and \mu.
2) Definition 3.5: give --> given
3) 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. 
4) Definition 3.5 is written in terms of cdfs. This is understood, but good to explicitly mention this.
5) 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. 
6) 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. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths

The 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).


Weaknesses

While 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?).


Detailed comments

Def 3.5: "d_k(F', F) \le F": F => \alpha

First paragraph in sec 3.2, "... can be found in Appendix G" (and several other places): do you mean Appendix B?

Thm 3.7: what happend to the 1/ln(n) factor in the proof in Appendx C.1?

Proof sketch of thm 3.8, first sentence, "F(x) is stochastically dominated by F(x) for all x": this can't be right...

Thm 4.3 (and 4.4): is this just because the empirical CDF uniformly converges to the population CDF at rate m^{-1/2}?

Line 313, "sample complexity upper bounds depend on sum of \alpha_i": doesn't it depend on max_i \alpha_i^2?  Also "depends" => "depend"

Line 315, discussion about lower bounds: it's a bit confusing to see this before seeing the lower bounds (thm 4.5)
limitations_and_societal_impact: I don't have concerns.
review_title: null

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)