# Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments

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

## Key facts

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

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

- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [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)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization](https://mlsanity.com/paper/2302.08108/) (2023)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (2022)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)

## Abstract (arXiv)

We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.