Abie Flaxman (CMU)
“Random Sampling Auctions”
September 29, 15:00-16:00, PPB 300
ABSTRACT:
Random sampling is the most prevalent technique for designing incentive-compatible auctions to maximize the auctioneer’s profit when the bidders’ valuations are a priori unknown. The first and simplest application of random sampling to auctions is in the context of auctioning a digital good. For this problem, the random sampling optimal price auction works by selecting a bipartition of the bidders uniformly at random and offering the optimal sale price for each part to the other part.
We give a simple analysis of the competitive ratio of the random sampling auction. The random sampling auction was previously known to be worst-case competitive with a bound of 7600; our analysis improves the bound to 15. It is believed that the auction is in fact 4-competitive, and we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.
This is joint work with Uri Feige, Jason Hartline, and Bobby Kleinberg.
