Automated Mechanism Design: A New Application Area for Search Algorithms

Mechanism design is the art of designing the rules of thegame (aka. mechanism) so that a desirable outcome (according to a given objective) is reached despite the fact that each agent acts in his own self-nterest. Examples include the design of auctions, voting protocols, and divorce settlement procedures. Mechanisms have traditionally been designed manually for classes of problems. In 2002, Conitzer and Sandholm introduced the automated mechanism design approach, where the mechanism is computationally created for the specific problem instance at hand. This approach 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 economicimpossibility results, and 4) it shifts the burden of design from man to machine. In this write-up I overview the approach, focusing on problem representations, computational complexity, and initial applications. I also lay out an agenda for future research in this area.