# Learning Simple Auctions

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2016.

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

- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [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)
- [Learning to Maximize Gains From Trade in Small Markets](https://mlsanity.com/paper/2401.11596/) (2024)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (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)
- [Max-affine regression via first-order methods](https://mlsanity.com/paper/2308.08070/) (2023)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [An Interpretable Automated Mechanism Design Framework with Large Language Models](https://mlsanity.com/paper/2502.12203/) (2025)
- [Aligned Textual Scoring Rules](https://mlsanity.com/paper/2507.06221/) (2025)
- [Online Stackelberg Optimization via Nonlinear Control](https://mlsanity.com/paper/2406.18805/) (2024)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (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)
- [Artificial Intelligence for Multi-Unit Auction design](https://mlsanity.com/paper/2404.15633/) (2024)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)
- [Learning to Price with Persuasion](https://mlsanity.com/paper/2608.16699/) (2026)

## Abstract (arXiv)

We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of "simple" auctions. Our framework captures all of the most prominent examples of "simple" auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The technique we propose is to break the analysis of auctions into two natural pieces. First, one shows that the set of allocation rules have large amounts of structure; second, fixing an allocation on a sample, one shows that the set of auctions agreeing with this allocation on that sample have revenue functions with low dimensionality. Our results effectively imply that whenever it's possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior (given a polynomial number of samples).