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
In most mechanism design settings, optimal general-purpose mechanisms
are not known. Thus the automated design of mechanisms tailored to
specific instances of a decision scenario is an important
problem. Existing techniques for automated mechanism design (AMD) require
the revelation of full utility information from agents, which can be
very difficult in practice.
In this work, we study the automated design
of mechanisms that only require partial revelation of utilities. 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. We provide a set of optimization routines
that can be combined to address the trade-offs between the amount of
communication, approximation of incentive properties, and objective value
achieved by a mechanism. This allows for the automated design of
partial revelation mechanisms with worst-case guarantees on
incentive properties for any objective function (revenue, social
welfare, etc.).
To appear, AAAI-2007
Return to List of Papers