@inproceedings{fu2015randomization,
author = {Fu, Hu and Immorlica, Nicole and Lucier, Brendan and Strack, Philipp},
title = {Randomization Beats Second Price as a Prior-Independent Auction},
booktitle = {ACM Conference on Electronic Commerce 2015},
year = {2015},
month = {July},
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.},
url = {http://approjects.co.za/?big=en-us/research/publication/randomization-beats-second-price-prior-independent-auction/},
edition = {ACM Conference on Electronic Commerce 2015},
}