Applications of Automated Mechanism Design

Mechanism design is the art of designing the rules of the game so that desirable systemwide outcomes are obtained even though every agent in the system acts based on self-interest. Mechanism design has traditionally been a manual process. We recently (UAI-02) proposed automated mechanism design (AMD), and studied its worst-case complexity. This paper contains the first experimental work on AMD. We describe our implementation of AMD using a mixed integer/linear programming package (CPLEX 8.0), which we applied to a variety of scenarios that arise in different real-world settings. It created new optimal mechanisms for (divorce) dispute settlement, reinvented the Myerson optimal auction, invented optimal combinatorial auctions (a well-known important open research problem), and created new optimal mechanisms for public goods problems (both single-good and multi-good problems). We contrast the generated optimal mechanisms to the available mechanisms in the game theory literature. Finally, we present experimental scalability results of our implementation of AMD.