Hard-to-Manipulate Combinatorial Auctions

DSpace/Manakin Repository

Hard-to-Manipulate Combinatorial Auctions

Citable link to this page


Title: Hard-to-Manipulate Combinatorial Auctions
Author: Sanghvi, Saurabh; Parkes, David C.

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

Citation: Sanghvi, Saurabh, and David C. Parkes. 2004. Hard-to-manipulate combinatorial auctions. Harvard University Technical Report.
Full Text & Related Files:
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.
Published Version: http://www.eecs.harvard.edu/econcs/pubs/hard_to_manipulate.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:4064048
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search