# Sample Complexity of Automated Mechanism Design

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2016.

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

- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)
- [A Scalable Neural Network for DSIC Affine Maximizer Auction Design](https://mlsanity.com/paper/2305.12162/) (2023)
- [Differentiable Economics for Randomized Affine Maximizer Auctions](https://mlsanity.com/paper/2202.02872/) (2022)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [A Context-Integrated Transformer-Based Neural Network for Auction Design](https://mlsanity.com/paper/2201.12489/) (2022)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022)
- [Accelerating ERM for data-driven algorithm design using output-sensitive techniques](https://mlsanity.com/paper/2204.03569/) (2022)
- [Benefits of Permutation-Equivariance in Auction Mechanisms](https://mlsanity.com/paper/2210.05579/) (2022)
- [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)
- [The Pseudo-Dimension of Contracts](https://mlsanity.com/paper/2501.14474/) (2025)
- [Learning Competitive Equilibria in Exchange Economies with Bandit Feedback](https://mlsanity.com/paper/2106.06616/) (2021)
- [Automated Deterministic Auction Design with Objective Decomposition](https://mlsanity.com/paper/2402.11904/) (2024)
- [Aligned Textual Scoring Rules](https://mlsanity.com/paper/2507.06221/) (2025)
- [Optimal Automated Market Makers: Differentiable Economics and Strong Duality](https://mlsanity.com/paper/2402.09129/) (2024)
- [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)
- [Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning](https://mlsanity.com/paper/2407.04898/) (2024)
- [Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits](https://mlsanity.com/paper/2412.00345/) (2024)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)
- [Enhancing Affine Maximizer Auctions with Correlation-Aware Payment](https://mlsanity.com/paper/2602.09455/) (2026)
- [Learning to Price with Persuasion](https://mlsanity.com/paper/2608.16699/) (2026)

## Abstract (arXiv)

The design of revenue-maximizing combinatorial auctions, i.e. multi-item auctions over bundles of goods, is one of the most fundamental problems in computational economics, unsolved even for two bidders and two items for sale. In the traditional economic models, it is assumed that the bidders' valuations are drawn from an underlying distribution and that the auction designer has perfect knowledge of this distribution. Despite this strong and oftentimes unrealistic assumption, it is remarkable that the revenue-maximizing combinatorial auction remains unknown. In recent years, automated mechanism design has emerged as one of the most practical and promising approaches to designing high-revenue combinatorial auctions. The most scalable automated mechanism design algorithms take as input samples from the bidders' valuation distribution and then search for a high-revenue auction in a rich auction class. In this work, we provide the first sample complexity analysis for the standard hierarchy of deterministic combinatorial auction classes used in automated mechanism design. In particular, we provide tight sample complexity bounds on the number of samples needed to guarantee that the empirical revenue of the designed mechanism on the samples is close to its expected revenue on the underlying, unknown distribution over bidder valuations, for each of the auction classes in the hierarchy. In addition to helping set automated mechanism design on firm foundations, our results also push the boundaries of learning theory. In particular, the hypothesis functions used in our contexts are defined through multi-stage combinatorial optimization procedures, rather than simple decision boundaries, as are common in machine learning.