Automated design of multistage mechanisms


Conference Paper

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-stagemechanism 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.

Duke Authors

Cited Authors

  • Sandholm, T; Conitzer, V; Boutilier, C

Published Date

  • December 1, 2007

Published In

Start / End Page

  • 1500 - 1506

International Standard Serial Number (ISSN)

  • 1045-0823

Citation Source

  • Scopus