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.