Abstract

Mechanism Design with Partial Revelation

Mechanism Design with Partial Revelation

Nathanaël Hyafil, Craig Boutilier

Classic direct mechanisms require full utility revelation from agents, which can be very difficult in practical multi-attribute settings. In this work, we study partial revelation within the framework of one-shot mechanisms. Each agent's type space is partitioned into a finite set of partial types and agents (should) report the partial type within which their full type lies. A classic result implies that implementation in dominant strategies is impossible in this model. We first show that a relaxation to Bayes-Nash implementation does not circumvent the problem. We then propose a class of partial revelation mechanisms that achieve approximate dominant strategy implementation, and describe a computationally tractable algorithm for myopically optimizing the partitioning of each agent's type space to reduce manipulability and social welfare loss. This allows for the automated design of one-shot partial revelation mechanisms with worst-case guarantees on both manipulability and efficiency.

URL: www.cs.toronto.edu/~nhyafil/Papers/HyafilBoutilierIJCAI07