Discrete Mathematics and Optimization Seminar


Abraham Flaxman
Carnegie Melon University
Monday November 7th at 4.30pm
Burnside 1205



Title. Random Sampling Auctions

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.