License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05011.5
URN: urn:nbn:de:0030-drops-2677
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/267/
Go to the corresponding Portal

Sandholm, Tuomas

Automated Mechanism Design

pdf-format:
05011.SandholmTuomas.Paper.267.pdf (0.04 MB)

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:DagSemProc.05011.5,
  author =	{Sandholm, Tuomas},
  title =	{{Automated Mechanism Design}},
  booktitle =	{Computing and Markets},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/267},
  URN =		{urn:nbn:de:0030-drops-2677},
  doi =		{10.4230/DagSemProc.05011.5},
  annote =	{Keywords: Automated mechanism design, mechanism design}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI