Hard-to-Manipulate Combinatorial Auctions
| 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: |
Sanghvi_Hard.pdf (176.2Kb; PDF) 
|
| 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 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5128]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
