The revelation principle for mechanism design with reporting costs


Conference Paper

The revelation principle is a key tool in mechanism design. It allows the designer to restrict attention to the class of truthful mechanisms, greatly facilitating analysis. This is also borne out in an algorithmic sense, allowing certain computational problems in mechanism design to be solved in polynomial time. Unfortunately, when not every type can misreport every other type (the partial verification model), or-more generally-misreporting can be costly, the revelation principle can fail to hold. This also leads to NP-hardness results. The primary contribution of this paper consists of characterizations of conditions under which the revelation principle still holds when misreporting can be costly. (These are generalizations of conditions given earlier for the partial verification case [Green and Laffont 1986; Yu 2011].) We also study associated computational problems.

Full Text

Duke Authors

Cited Authors

  • Kephart, A; Conitzer, V

Published Date

  • July 21, 2016

Published In

  • Ec 2016 Proceedings of the 2016 Acm Conference on Economics and Computation

Start / End Page

  • 85 - 102

International Standard Book Number 13 (ISBN-13)

  • 9781450339360

Digital Object Identifier (DOI)

  • 10.1145/2940716.2940795

Citation Source

  • Scopus