@conference {17636,
	title = {On random sampling auctions for digital goods},
	booktitle = {Proceedings of the 10th ACM conference on Electronic commerce},
	series = {EC {\textquoteright}09},
	year = {2009},
	month = {2009///},
	pages = {187 - 196},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {In the context of auctions for digital goods, an interesting Random Sampling Optimal Price auction (RSOP) has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. Since random sampling is a popular approach for auctions that aims to maximize the seller{\textquoteright}s revenue, this method has been analyzed further by Feige, Flaxman, Hartline and Kleinberg, who have shown that it is 15-competitive in the worst case -- which is substantially better than the previously proved bounds but still far from the conjectured competitive ratio of 4. In this paper, we prove that RSOP is indeed 4-competitive for a large class of instances in which the number λ of bidders receiving the item at the optimal uniform price, is at least 6. We also show that it is 4.68 competitive for the small class of remaining instances thus leaving a negligible gap between the lower and upper bound. Furthermore, we develop a robust version of RSOP -- one in which the seller{\textquoteright}s revenue is, with high probability, not much below its mean -- when the above parameter λ grows large. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.},
	keywords = {auction, mechanism design, random sampling},
	isbn = {978-1-60558-458-4},
	doi = {10.1145/1566374.1566402},
	url = {http://doi.acm.org/10.1145/1566374.1566402},
	author = {Alaei,Saeed and Malekian,Azarakhsh and Srinivasan, Aravind}
}
