On Random Sampling Auctions for Digital Goods

In the context of auctions for digital goods, an interesting random sampling auction has been proposed by Goldberg et al. [2001]. This auction has been analyzed by Feige et al. [2005], who have shown that it obtains in expectation at least 1/15 fraction of the optimal revenue, which is substantially better than the previously proven constant bounds but still far from the conjectured lower bound of 1/4. In this article, we prove that the aforementioned random sampling auction obtains at least 1/4 fraction of the optimal revenue for a large class of instances where the number of bids above (or equal to) the optimal sale price is at least 6. We also show that this auction obtains at least 1/4.68 fraction of the optimal revenue for the small class of remaining instances, thus leaving a negligible gap between the lower and upper bound. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.