# Learning Multi-item Auctions with (or without) Samples

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Sep 2017.

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

- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Robust Learning of Optimal Auctions](https://mlsanity.com/paper/2107.06259/) (2021)
- [Multi-Platform Budget Management in Ad Markets with Non-IC Auctions](https://mlsanity.com/paper/2306.07352/) (2023)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [Uniform Laws of Large Numbers in Product Spaces](https://mlsanity.com/paper/2603.24493/) (2026)
- [Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce](https://mlsanity.com/paper/2405.07038/) (2024)
- [Learn then Decide: A Learning Approach for Designing Data Marketplaces](https://mlsanity.com/paper/2503.10773/) (2025)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Sample Complexity of Forecast Aggregation](https://mlsanity.com/paper/2207.13126/) (2022)
- [A Robust Multi-Item Auction Design with Statistical Learning](https://mlsanity.com/paper/2302.00941/) (2023)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)

## Abstract (arXiv)

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of valuations including unit-demand, additive, constrained additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly studied setting where sample access to the bidders' distributions over valuations is given, for both regular distributions and arbitrary distributions with bounded support. Our algorithms require polynomially many samples in the number of items and bidders. The second is a more general max-min learning setting that we introduce, where we are given "approximate distributions," and we seek to compute an auction whose revenue is approximately optimal simultaneously for all "true distributions" that are close to the given ones. These results are more general in that they imply the sample-based results, and are also applicable in settings where we have no sample access to the underlying distributions but have estimated them indirectly via market research or by observation of previously run, potentially non-truthful auctions. Our results hold for valuation distributions satisfying the standard (and necessary) independence-across-items property. They also generalize and improve upon recent works, which have provided algorithms that learn approximately optimal auctions in more restricted settings with additive, subadditive and unit-demand valuations using sample access to distributions. We generalize these results to the complete unit-demand, additive, and XOS setting, to i.i.d. subadditive bidders, and to the max-min setting. Our results are enabled by new uniform convergence bounds for hypotheses classes under product measures. Our bounds result in exponential savings in sample complexity compared to bounds derived by bounding the VC dimension, and are of independent interest.