Adaptive Limited-Supply Online Auctions
Hajiaghayi, Mohammad T.
MetadataShow full item record
CitationHajiaghayi, Mohammad T., Robert Kleinberg, and David C. Parkes. 2004. Adaptive limited-supply online auctions. In EC'04: Proceedings of the 5th ACM Conference on Electronic Commerce: May 17-20, 2004, New York, New York, 71-80. New York, N.Y.: ACM Press.
AbstractWe study a limited-supply online auction problem, in which an auctioneer has k goods to sell and bidders arrive and depart dynamically. We suppose that agent valuations are drawn independently from some unknown distribution and construct an adaptive auction that is nevertheless value- andtime-strategy proof. For the k=1 problem we have a strategyproof variant on the classic secretary problem. We present a 4-competitive (e-competitive) strategyproof online algorithm with respect to offline Vickrey for revenue (efficiency). We also show (in a model that slightly generalizes the assumption of independent valuations) that no mechanism can be better than 3/2-competitive (2-competitive) for revenue (efficiency). Our general approach considers a learning phase followed by an accepting phase, and is careful to handle incentive issues for agents that span the two phases. We extend to the k›1 case, by deriving strategyproof mechanisms which are constant-competitive for revenue and efficiency. Finally, we present some strategyproof competitive algorithms for the case in which adversary uses a distribution known to the mechanism.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4045847
- FAS Scholarly Articles