Better with Byzantine: Manipulation-Optimal Mechanisms

摘要

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