Bayesian algorithmic mechanism design

Jason D Hartline, Brendan Lucier

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

58 Scopus citations

Abstract

The principal problem in algorithmic mechanism design is in merging the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. This field is motivated by the observation that the preeminent approach for designing incentive compatible mechanisms, namely that of Vickrey, Clarke, and Groves; and the central approach for circumventing computational obstacles, that of approximation algorithms, are fundamentally incompatible: natural applications of the VCG approach to an approximation algorithm fails to yield an incentive compatible mechanism. We consider relaxing the desideratum of (ex post) incentive compatibility (IC) to Bayesian incentive compatibility (BIC), where truthtelling is a Bayes-Nash equilibrium (the standard notion of incentive compatibility in economics). For welfare maximization in single-parameter agent settings, we give a general black-box reduction that turns any approximation algorithm into a Bayesian incentive compatible mechanism with essentially the same approximation factor.

Original languageEnglish (US)
Title of host publicationSTOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
Pages301-310
Number of pages10
DOIs
StatePublished - Jul 23 2010
Event42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States
Duration: Jun 5 2010Jun 8 2010

Publication series

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

Other

Other42nd ACM Symposium on Theory of Computing, STOC 2010
CountryUnited States
CityCambridge, MA
Period6/5/106/8/10

Keywords

  • Bayesian incentive compatibility
  • algorithms
  • mechanism design
  • social welfare.

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Bayesian algorithmic mechanism design'. Together they form a unique fingerprint.

Cite this