Hard-to-Manipulate Combinatorial Auctions

DSpace/Manakin Repository

Hard-to-Manipulate Combinatorial Auctions

Show simple item record

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

Files in this item

Files Size Format View
Sanghvi_Hard.pdf 172.0Kb PDF View/Open

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7456]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University

Show simple item record

 
 

Search DASH


Advanced Search
 
 

Submitters