License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-2677
URL: http://drops.dagstuhl.de/opus/volltexte/2005/267/

Sandholm, Tuomas

Automated Mechanism Design

pdf-format:
Dokument 1.pdf (42 KB)


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.

BibTeX - Entry

@InProceedings{sandholm:DSP:2005:267,
  author =	{Tuomas Sandholm},
  title =	{Automated Mechanism Design},
  booktitle =	{Computing and Markets},
  year =	{2005},
  editor =	{Daniel Lehmann and Rudolf M{\"u}ller and Tuomas Sandholm},
  number =	{05011},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/267},
  annote =	{Keywords: Automated mechanism design, mechanism design}
}

Keywords: Automated mechanism design, mechanism design
Seminar: 05011 - Computing and Markets
Issue date: 2005
Date of publication: 31.08.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI