Adaptive Limited-Supply Online Auctions

DSpace/Manakin Repository

Adaptive Limited-Supply Online Auctions

Citable link to this page


Title: Adaptive Limited-Supply Online Auctions
Author: Hajiaghayi, Mohammad T.; Kleinberg, Robert; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

Citation: Hajiaghayi, 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.
Full Text & Related Files:
Abstract: We 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.
Published Version: doi:10.1145/988772.988784
Other Sources:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search