On the Competitive Ration of Online Sampling Auctions
Georgios Pierrakos from the University of California, Berkeley.
We study online profit-maximizing auctions for digital goods with
adversarial bid selection and uniformly random arrivals. Our goal is to
design auctions that are constant competitive with F^(2); in this sense
our model lies at the intersection of prior-free mechanism design and
secretary problems. We first give a generic reduction that transforms
any offline auction to an online one, with only a loss of a factor of 2
in the competitive ratio; we then present some natural auctions, both
randomized and deterministic, and study their competitive ratio; our
analysis reveals some interesting connections of one of these auctions
with RSOP, which we further investigate in our final section.
free-food-alert mailing list email@example.com
Also check out http://free-food-alert.blogspot.com