Generalization of the MV Mechanism
Author(s)
Chen, Jing![Thumbnail](/bitstream/handle/1721.1/41515/MIT-CSAIL-TR-2008-023.pdf.jpg?sequence=5&isAllowed=y)
DownloadMIT-CSAIL-TR-2008-023.pdf (245.8Kb)
Additional downloads
Other Contributors
Theory of Computation
Advisor
Silvio Micali
Metadata
Show full item recordAbstract
Micali and Valiant proposed a mechanism for combinatorial auctions that is dominant-strategy truthful, guarantees reasonably high revenue, and is very resilient against collusions. Their mechanism, however, uses as a subroutine the VCG mechanism, that is not polynomial time.We propose a modification of their mechanism that is efficient, while retaining their collusion resilience and a good fraction of their revenue, if given as a subroutine an efficient approximation of the VCG mechanism.
Date issued
2008-05-01Other identifiers
MIT-CSAIL-TR-2008-023