# Randomization beats Second Price as a Prior-Independent Auction

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2015.

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

- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Algorithmic Robust Forecast Aggregation](https://mlsanity.com/paper/2401.17743/) (2024)
- [On the limitations of data-based price discrimination](https://mlsanity.com/paper/2204.12723/) (2022)
- [Regret Minimization with Noisy Observations](https://mlsanity.com/paper/2207.09435/) (2022)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)

## Abstract (arXiv)

Designing revenue optimal auctions for selling an item to n symmetric bidders is a fundamental problem in mechanism design. Myerson (1981) shows that the second price auction with an appropriate reserve price is optimal when bidders' values are drawn i.i.d. from a known regular distribution. A cornerstone in the prior-independent revenue maximization literature is a result by Bulow and Klemperer (1996) showing that the second price auction without a reserve achieves (n-1)/n of the optimal revenue in the worst case. We construct a randomized mechanism that strictly outperforms the second price auction in this setting. Our mechanism inflates the second highest bid with a probability that varies with n. For two bidders we improve the performance guarantee from 0.5 to 0.512 of the optimal revenue. We also resolve a question in the design of revenue optimal mechanisms that have access to a single sample from an unknown distribution. We show that a randomized mechanism strictly outperforms all deterministic mechanisms in terms of worst case guarantee.