Nathanael Hyafil
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: nhyafil@cs.toronto.edu
Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
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.
To appear, IJCAI-07