Show simple item record

dc.contributor.authorKothari, Anshul
dc.contributor.authorParkes, David C.
dc.contributor.authorSuri, Subhash
dc.date.accessioned2010-04-30T14:15:04Z
dc.date.issued2005
dc.identifier.citationKothari, 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.issn0167-9236en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4031557
dc.description.abstractWe 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.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherElsevieren_US
dc.relation.isversionofdoi:10.1016/j.dss.2004.08.009en_US
dc.relation.hasversionhttp://www.eecs.harvard.edu/econcs/pubs/kothari_long.pdfen_US
dash.licenseLAA
dc.subjectapproximation algorithmen_US
dc.subjectmultiunit auctionsen_US
dc.subjectstrategyproofen_US
dc.subjectapproximately-strategyproofen_US
dc.subjectbidding languageen_US
dc.titleApproximately-Strategyproof and Tractable Multi-Unit Auctionsen_US
dc.typeJournal Articleen_US
dc.description.versionAuthor's Originalen_US
dc.relation.journalDecision Support Systemsen_US
dash.depositing.authorParkes, David C.
dc.date.available2010-04-30T14:15:04Z
dc.identifier.doi10.1016/j.dss.2004.08.009*
dash.contributor.affiliatedParkes, David


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record