Portal de Periódicos da CAPES

On the Competitive Ratio of the Random Sampling Auction

2005; Springer Science+Business Media; Linguagem: Inglês

10.1007/11600930_89

1611-3349

Uriel Feige, Abraham D. Flaxman, Jason D. Hartline, Robert Kleinberg,

Mobile Crowdsensing and Crowdsourcing

We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of 7600 on its competitive ratio); our analysis improves the bound to 15. In support of the conjecture that random sampling auction is in fact 4-competitive, 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.