Randomization beats Second Price as a Prior-Independent Auction

Abstract

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.

References in corpus (2)

• Optimal Auctions for Correlated Buyers with Sampling
• Making the Most of Your Samples

Cited by in corpus (7)

• How to manipulate truthful prior-dependent mechanisms?
• Thresholding at the monopoly price: an agnostic way to improve bidding strategies in revenue-maximizing auctions
• The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue
• An End-to-end Argument in Mechanism Design (Prior-independent Auctions for Budgeted Agents)
• Benchmark Design and Prior-independent Optimization
• Revelation Gap for Pricing from Samples
• Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization