A response to 'Mechanism Design with Partial Verification and Revelation Principle'

摘要

After the acceptance of our paper "Alternatives to Truthfulness are Hard to Recognize," Lan Yu pointed out a mistake in our characterization of the Revelation Principle with quasi-linear utility (Theorem 7 in our paper). We claimed that the Nested Range Condition (NRC) on a reduced version of the correspondence graph is sufficient and necessary for the Revelation Principle to hold. Lan provided us with a proof that a subtly different and slightly weaker condition, called Strong Decomposability, is actually the correct one. It is nice to know that when payments are allowed not even NRC guarantees that the Revelation Principle holds! We remark that the other contributions of our work remain correct as Theorem 7 is orthogonal to the rest of our results. In particular, the hardness result in Sect. 4.2 of our work only exploits the non-completeness of the correspondence graph to encode a 3-SAT formula.