On the Competitive Ratio of Online Sampling Auctions
On the Competitive Ratio of Online Sampling Auctions
E. Koutsoupias,G. Pierrakos
2010 · DOI: 10.1145/2465769.2465775
21 Citations
TLDR
A generic reduction is given that transforms any offline auction to an online one with only a loss of a factor of 2 in the competitive ratio, and some interesting connections are revealed of one of these auctions with RSOP.