Carnegie Mellon University
Browse
file.pdf (144.11 kB)

Applications of Automated Mechanism Design

Download (144.11 kB)
journal contribution
posted on 1998-06-01, 00:00 authored by Vincent Conitzer, Tuomas SandholmTuomas Sandholm


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.

History

Date

1998-06-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC