Online Auctions with Re-usable Goods

DSpace/Manakin Repository

Online Auctions with Re-usable Goods

Citable link to this page


Title: Online Auctions with Re-usable Goods
Author: Hajiaghayi, Mohammad; Kleinberg, Robert; Mahdian, Mohammad; Parkes, David C.

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

Citation: Hajiaghayi, Mohammad, Robert Kleinberg, Mohammad Mahdian, and David Parkes. 2005. Online auctions with re-usable goods. In EC'05: Proceedings of the 6th ACM Conference on Electronic Commerce: June 5-8, 2005, Vancouver, Canada, ed. ACM Conference on Electronic Commerce, Association for Computing Machinery, Special Interest Group on Electronic Commerce, 165-174. New York, N.Y.: ACM Press.
Full Text & Related Files:
Abstract: This paper concerns the design of mechanisms for online scheduling in which agents bid for access to a re-usable resource such as processor time or wireless network access. Each agent is assumed to arrive and depart dynamically, and in the basic model require the resource for one unit of time. We seek mechanisms that are truthful in the sense that truthful revelation of arrival, departure and value information is a dominant strategy, and that are online in the sense that they make allocation decisions without knowledge of the future. First, we provide two characterizations for the class of truthful online allocation rules. The characterizations extend beyond the typical single-parameter settings, and formalize the role of restricted misreporting in reversing existing price-based characterizations. Second, we present an online auction for unit-length jobs that achieves total value that is 2-competitive with the maximum offline value. We prove that no truthful deterministic online mechanism can achieve a better competitive ratio. Third, we consider revenue competitiveness and prove that no deterministic truthful online auction has revenue that is constant-competitive with that of the offline Vickrey-Clarke-Groves (VCG) mechanism We provide a randomized online auction that achieves a competitive ratio of O(log h), where h is the ratio of maximum value to minimum value among the agents; this mechanism does not require prior knowledge of h. Finally, we generalize our model to settings with multiple re-usable goods and to agents with different job lengths.
Published Version: doi:10.1145/1064009.1064027
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