Automated Mechanism Design

Abstract

Mechanisms design has traditionally been a manual endeavor.  In 2002, Conitzer and Sandholm introduced the automated mechanism design (AMD) approach, where the mechanism is computationally created for the specific problem instance at hand. This has several advantages: 1) it can yield better mechanisms than the ones known to date, 2) it applies beyond the problem classes studied manually to date, 3) it can circumvent seminal economic impossibility results that hold for classes of problems but not all instances, and 4) it shifts the burden of design from man to machine.  In this talk I will overview our results on AMD to date.  I will cover problem representations and the computational complexity of different variants of the design problem.  Initial applications include revenue-maximizing combinatorial auctions and (combinatorial) public goods problems.  Algorithms for AMD will be discussed.  To reduce the computational complexity of designing optimal combinatorial auctions, I introduce an incentive compatible, individually rational subfamily called Virtual Valuations Combinatorial Auctions.  The auction mechanism's revenue can be boosted (started, for example, from the VCG) by hill-climbing in this subspace.  I will also present computational complexity and communication complexity results that motivate multi-stage and non-truth-promoting mechanisms.  Finally, I present our first steps toward automatically designing multi-stage mechanisms.