Monday November 7th at 4.30pm

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.