dc.contributor.author | Kothari, Anshul | |
dc.contributor.author | Parkes, David C. | |
dc.contributor.author | Suri, Subhash | |
dc.date.accessioned | 2010-04-30T14:15:04Z | |
dc.date.issued | 2005 | |
dc.identifier.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. | en_US |
dc.identifier.issn | 0167-9236 | en_US |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:4031557 | |
dc.description.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. | en_US |
dc.description.sponsorship | Engineering and Applied Sciences | en_US |
dc.language.iso | en_US | en_US |
dc.publisher | Elsevier | en_US |
dc.relation.isversionof | doi:10.1016/j.dss.2004.08.009 | en_US |
dc.relation.hasversion | http://www.eecs.harvard.edu/econcs/pubs/kothari_long.pdf | en_US |
dash.license | LAA | |
dc.subject | approximation algorithm | en_US |
dc.subject | multiunit auctions | en_US |
dc.subject | strategyproof | en_US |
dc.subject | approximately-strategyproof | en_US |
dc.subject | bidding language | en_US |
dc.title | Approximately-Strategyproof and Tractable Multi-Unit Auctions | en_US |
dc.type | Journal Article | en_US |
dc.description.version | Author's Original | en_US |
dc.relation.journal | Decision Support Systems | en_US |
dash.depositing.author | Parkes, David C. | |
dc.date.available | 2010-04-30T14:15:04Z | |
dc.identifier.doi | 10.1016/j.dss.2004.08.009 | * |
dash.contributor.affiliated | Parkes, David | |