Tuomas Sandholm
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA, 15213
email: sandholm@cs.cmu.edu
Vincent Conitzer
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA, 15213
email: conitzer@cs.cmu.edu
Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
Mechanism design is the study of preference aggregation
protocols that work well in the face
of self-interested agents. We present the first
general-purpose techniques for automatically designing
multistage mechanisms. These can reduce
elicitation burden by only querying agents for information
that is relevant given their answers to
previous queries. We first show how to turn a given
(e.g., automatically designed using constrained optimization
techniques) single-stage mechanism into
the most efficient corresponding multistage mechanism
given a specified elicitation tree. We then
present greedy and dynamic programming (DP) algorithms
that determine the elicitation tree (optimal
in the DP case). Next, we show how the query
savings inherent in the multistage model can be
used to design the underlying single-stage mechanism
to maximally take advantage of this approach.
Finally, we present negative results on the design
of multistage mechanisms that do not correspond
to dominant-strategy single-stage mechanisms: an
optimal multistage mechanism in general has to
randomize over queries to hide information from
the agents.
To appear, IJCAI-07
Return to List of Papers