Tuesday, November 16, 2010

[FREE-FOOD] RAIN algorithm lunch, Y2E2 Room 105, 12:30-1:30pm, Wed Nov 17th

Lunch will be served

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 free-food-alert@lists.stanford.edu
Also check out http://free-food-alert.blogspot.com

No comments: