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 will 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. We illustrate all of these techniques on an
optimal auction example. 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.
First International Workshop on Incentive Based Computing, at the IEEE/WIC/ACM International Conference on Web Intelligence (WI), Compiegne, France.
Return to List of Papers