Bayesian incentive compatibility via matchings

Jason D Hartline, Robert Kleinberg, Azarakhsh Malekian

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

43 Scopus citations


We give a simple reduction from Bayesian incentive compatible mechanism design to algorithm design in settings where the agents' private types are multi-dimensional. The reduction preserves performance up to an additive loss that can be made arbitrarily small in polynomial time in the number of agents and the size of the agents' type spaces.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
PublisherAssociation for Computing Machinery
Number of pages14
ISBN (Print)9780898719932
StatePublished - 2011

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Bayesian incentive compatibility via matchings'. Together they form a unique fingerprint.

Cite this