Approximately-Strategyproof and Tractable Multi-Unit Auctions
| Title: | Approximately-Strategyproof and Tractable Multi-Unit Auctions |
| Author: |
Kothari, Anshul; Parkes, David C.; Suri, Subhash
Note: Order does not necessarily reflect citation order of authors. |
| Citation: | Kothari, Anshul, David C. Parkes, and Subhash Suri. 2005. Approximately-strategyproof and tractable multi-unit auctions. Decision Support Systems 39(1): 105-121. Previously published in Proceedings of the 4th ACM Conference on Electronic Commerce: San Diego, California, USA, June 9-12, 2003. New York, N.Y.: ACM Press, 166-175. |
| Full Text & Related Files: |
Kothari_Approximately.pdf (224.8Kb; PDF) 
|
| Abstract: | We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multiunit allocation problem. The bidding language allows marginal-decreasing piecewise-constant curves and quantity-based side constraints. We develop a fully polynomial-time approximation scheme for the multiunit allocation problem, which computes a (1+ε) approximation in worst-case time T=O(n3/ε), given n bids each with a constant number of pieces. We integrate this approximation scheme within a Vickrey–Clarke–Groves (VCG) mechanism and compute payments for an asymptotic cost of O(T log n). The maximal possible gain from manipulation to a bidder in the combined scheme is bounded by εV/(1+ε), where V is the total surplus in the efficient outcome. |
| Published Version: | doi:10.1016/j.dss.2004.08.009 |
| Other Sources: | http://www.eecs.harvard.edu/econcs/pubs/kothari_long.pdf |
| Terms of Use: | This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:4031557 |
| Downloads of this work: |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [13843]
Contact administrator regarding this item (to report mistakes or request changes)
