Hard-to-Manipulate Combinatorial Auctions

Hard-to-Manipulate Combinatorial Auctions

DSpace/Manakin Repository

Hard-to-Manipulate Combinatorial Auctions

dc.contributor.author	Sanghvi, Saurabh
dc.contributor.author	Parkes, David C.
dc.date.accessioned	2010-05-11T18:00:24Z
dc.date.issued	2004
dc.identifier.citation	Sanghvi, Saurabh, and David C. Parkes. 2004. Hard-to-manipulate combinatorial auctions. Harvard University Technical Report.	en_US
dc.identifier.uri	http://nrs.harvard.edu/urn-3:HUL.InstRepos:4064048
dc.description.abstract	Mechanism design provides a framework to solve distributed optimization problems in systems of self-interested agents. The combinatorial auction is one such problem, in which there is a set of discrete items to allocate to agents. Unfortunately, recent results suggest that it is impossible to implement reasonable approximations without losing robustness to manipulation. Furthermore, the Vickrey-Clarke-Groves (VCG) mechanism is known to be vulnerable to manipulation when agents can bid under multiple false names. In this paper we relax incentive constraints and require only that useful manipulation be NP-hard. We prove that any tractable approximation algorithm can be made to produce a hard-to-manipulate (VCG-based) mechanism, providing a useful counterpoint to these negative results. We also show that falsename bid manipulation in the VCG is NP-hard.	en_US
dc.description.sponsorship	Engineering and Applied Sciences	en_US
dc.language.iso	en_US	en_US
dc.publisher	Division of Applied Science, Harvard University	en_US
dc.relation.isversionof	http://www.eecs.harvard.edu/econcs/pubs/hard_to_manipulate.pdf	en_US
dash.license	LAA
dc.title	Hard-to-Manipulate Combinatorial Auctions	en_US
dc.type	Research Paper or Report	en_US
dc.description.version	Accepted Manuscript	en_US
dc.relation.journal	Harvard University Technical Report	en_US
dash.depositing.author	Parkes, David C.
dc.date.available	2010-05-11T18:00:24Z