Improved Prior-Free Auctions with Ordered Bidders

A central problem in Microeconomics is to design auctions with good revenue properties. Consider the following setting. Multiple bidders are participating in an auction. The bidders' valuations for the items are private knowledge, but they are drawn from publicly known prior distributions. The goal is to implement a truthful auction (no bidder can gain in utility by misreporting her valuation) that maximizes the expected revenue. Here, the expectation is over the prior distributions of the bidders' valuations, and the random choices made by the auctioneer.

Naturally, to execute the auction with optimal expected revenue, the auctioneer first needs to know the prior distributions. An intriguing question is to design a truthful auction that is oblivious to these priors, and yet manages to get a constant factor of the optimal revenue. Such auctions are called {\em prior-free}. This question was posed in a seminal paper by Goldberg et al. [SODA 2001].

Goldberg et al. presented a constant approximate prior-free auction when there are identical copies of an item available in unlimited supply, bidders are unit-demand, and their valuations are drawn from  i.i.d. distributions. Very recently, Leonardi et al. [STOC 2012] generalized this setting to non i.i.d. bidders when the auctioneer knows the ordering of their reserve prices. Leonardi et al. presented a prior-free auction that achieves a O(log∗n) approximation. We improve upon this result and give a simple prior-free auction with constant approximation guarantee (joint work with Janardhan Kulkarni, Kamesh Munagala and Xiaoming Xu).