SCIENCE@home

Computational criticisms of the revelation principle

Vincent Conitzer,T. Sandholm

Published 2004 in ACM Conference on Economics and Computation

ABSTRACT

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 NP -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 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-60 of 60 references · Page 1 of 1

CITED BY

Showing 1-88 of 88 citing papers · Page 1 of 1