Welcome to ICS2011
Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 166-178, 978-7-302-24517-9
Tsinghua University Press
We consider a dynamic auction model, where bidders sequentially arrive to the market. The values of the bidders for the item for sale are independently drawn from a distribution, but this distribution is unknown to the seller. The seller offers a take-it-or-leave-it price for each arriving bidder (possibly different for different bidders), and aims to maximize revenue. We study how well can such sequential posted-price mechanisms approximate the optimal revenue that is achieved when the distribution is known to the seller. On the negative side, we show that sequential posted-price mechanisms cannot guarantee a constant fraction of this revenue when the class of candidate distributions is unrestricted. We show that this impossibility holds even if the set of possible distributions is very small, or when the seller has a prior distribution over the candidate distributions. On the positive side, we devise a posted-price mechanism that guarantees a constant fraction of the known-distribution revenue when all candidate distributions exhibit the monotone hazard rate property.