MA1

Automated Mechanism Design: Methods and Applications
Yevgeniy Vorobeychik and Vincent Conitzer

The field of mechanism design considers how to design systems with multiple self-interested agents, when those agents' preferences are unknown to the designer. It has had considerable impact, particularly in enlightening auction and election design. One limitation is that while the theoretical literature has much to say about mechanisms that maximize the sum of agents' valuations, far less is known about other objectives. Automated mechanism design (AMD) is an attempt to address this shortcoming computationally by searching through the space of possible mechanisms.

In this tutorial, we give an introduction to mechanism design (no previous background required) and then describe the AMD problem in two settings. First, we assume that the outcome set and the type set (the set of possible preferences) are finite. In that case, optimal randomized mechanisms can be designed in polynomial time, whereas designing optimal deterministic mechanisms is generally NP-hard. Second, we assume that the designer has control over a finite set of continuous parameters, and the sets of outcomes and player types are infinite. In this setting, AMD can be formulated as a stochastic black-box optimization problem and solved using stochastic search techniques. We also review several variants and applications.

Yevgeniy Vorobeychik is a Post Doctorial Researcher at the University of Pennsylvania. His interests lie on the intersection of Computer Science and Game Theory. Specifically, Yevgeniy is interested in mechanism design and game theoretic analysis of complex multi-agent systems using simulation-based models. Example applications include supply chains and keyword auctions.

Vincent Conitzer is an Assistant Professor of Computer Science and Economics at Duke University. His research deals with computational aspects of microeconomics — in particular game theory, mechanism design, voting/social choice, and auctions — with a focus on their use in artificial intelligence and multiagent systems.

(back)