# Robust Learning of Optimal Auctions

arXiv: https://arxiv.org/abs/2107.06259 · HTML: https://mlsanity.com/paper/2107.06259/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 13 Jul 2021.

## Builds on (most cited first, 14 of 14)

- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Making the Most of Your Samples](https://mlsanity.com/paper/1407.2479/) (2014)
- [Ironing in the Dark](https://mlsanity.com/paper/1511.06918/) (2015)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [A Sample Complexity Measure with Applications to Learning Optimal Auctions](https://mlsanity.com/paper/1704.02598/) (2017)
- [The Pseudo-Dimension of Near-Optimal Auctions](https://mlsanity.com/paper/1506.03684/) (2015)

## Built on by (most cited first, 3 of 3)

- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)
- [Advancing Ad Auction Realism: Practical Insights & Modeling Implications](https://mlsanity.com/paper/2307.11732/) (2023)

## Abstract (arXiv)

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.