Computational criticisms of the revelation principle

Publisher Website
Google Scholar
Abstract
The revelation principleis 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 moti- vated to be truthful. We show that reasonable constraints on com- putation 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 truth- ful mechanisms—a dogma that has, to our knowledge, never been criticized before. First, we study settings where the optimal truth- ful mechanism isNP -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 theNP -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 in- sincere mechanism is equally good as the optimal truthful mecha- nism 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.

This publication has 3 references indexed in Scilit: