Optimal mechanism design and money burning

Jason D Hartline, Tim Roughgarden

Research output: Chapter in Book/Report/Conference proceedingConference contribution

94 Scopus citations

Abstract

Mechanism design is now a standard tool in computer science for aligning the incentives of self-interested agents with the objectives of a system designer. There is, however, a fundamental disconnect between the traditional application domains of mechanism design (such as auctions) and those arising in computer science (such as networks): while monetary transfers (i.e., payments) are essential for most of the known positive results in mechanism design, they are undesirable or even technologically infeasible in many computer systems. Classical impossibility results imply that the reach of mechanisms without transfers is severely limited. Computer systems typically do have the ability to reduce service quality-routing systems can drop or delay traffic, scheduling protocols can delay the release of jobs, and computational payment schemes can require computational payments horn users (e.g., in spam-fighting systems). Service degradation is tantamount to requiring that users burn money, and such "payments" can be used to influence the preferences of the agents at a cost of degrading the social surplus. We develop a framework for the design and analysis of money-burning mechanisms to maximize the residual surplus-the total value of the chosen outcome minus the payments required. Our primary contributions are the following. We define a general template for prior-free optimal mechanism design that explicitly connects Bayesian optimal mechanism design, the dominant paradigm in economics, with worst-case analysis. In particular, we establish a general and principled way to identify appropriate performance benchmarks in prior-free mechanism design. For general single-parameter agent settings, we characterize the Bayesian optimal money-burning mechanism. For multi-unit auctions, we design a near-optimal prior-free money-burning mechanism: for every valuation profile, its expected residual surplus is within a constant factor of our benchmark, the residual surplus of the best Bayesian optimal mechanism for this profile. For multi-unit auctions, we quantify the benefit of general transfers over money-burning: optimal money-burning mechanisms always obtain a, logarithmic fraction of the full social surplus, and this bound is tight.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages75-84
Number of pages10
ISBN (Print)9781605580470
DOIs
StatePublished - 2008
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
Country/TerritoryCanada
CityVictoria, BC
Period5/17/085/20/08

Keywords

  • Algorithms
  • Economics
  • Theory

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Optimal mechanism design and money burning'. Together they form a unique fingerprint.

Cite this