Computational Criticisms of the Revelation Principle
The revelation principle is a cornerstone tool in mechanism design. It states that one can restrict attention, without loss in the designer’s objective, to mechanisms in which A) the agents report their types completely in a single step up front, and B) the agents are motivated to be truthful. We show that reasonable constraints on computation and communication can invalidate the revelation principle. Regarding A, we show that by moving to multi-step mechanisms, one can reduce exponential communication and computation to
linear—thereby answering a recognized important open question in mechanism design. Regarding B, we criticize the focus on truthful mechanisms—a dogma that has, to our knowledge, never been criticized before. First, we study settings where the optimal truthful mechanism is N P -complete to execute for the center. In that setting we show that by moving to insincere mechanisms, one can shift the burden of having to solve the N P -complete problem from
the center to one of the agents. Second, we study a new oracle model that captures the setting where utility values can be hard to compute even when all the pertinent information is available—a situation that occurs in many practical applications. In this model we show that by moving to insincere mechanisms, one can shift the burden of having to ask the oracle an exponential number of costly queries from the center to one of the agents. In both cases the insincere mechanism is equally good as the optimal truthful mechanism in the presence of unlimited computation. More interestingly, whereas being unable to carry out either difficult task would have hurt the center in achieving his objective in the truthful setting, if the agent is unable to carry out either difficult task, the value of the center’s objective strictly improves.