Better with Byzantine: Manipulation-Optimal Mechanisms

<p>A mechanism is manipulable if it is in some agents’ best interest to misrepresent their private information. The revelation principle<br>establishes that, roughly, anything that can be accomplished by a manipulable mechanism can also be accomplished with a truthful mechanism.<br>Yet agents often fail to play their optimal manipulations due to computational limitations or various flavors of incompetence and cognitive biases.<br>Thus, manipulable mechanisms in particular should anticipate byzantine<br>play. We study manipulation-optimal mechanisms: mechanisms that are<br>undominated by truthful mechanisms when agents act fully rationally,<br>and do better than any truthful mechanism if any agent fails to act rationally in any way. This enables the mechanism designer to do better<br>than the revelation principle would suggest, and obviates the need to<br>predict byzantine agents’ irrational behavior. We prove a host of possibility and impossibility results for the concept which have the impression<br>of broadly limiting possibility. These results are largely in line with the<br>revelation principle, although the considerations are more subtle and the<br>impossibility not universal.</p>