Bayesian incentive compatibility via matchings

Jason D Hartline*, Robert Kleinberg, Azarakhsh Malekian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Optimally allocating cellphone spectrum, advertisements on the Internet, and landing slots at airports is computationally intractable. When the participants may strategize, not only must the optimizer deal with complex feasibility constraints but also with complex incentive constraints. We give a very simple method for constructing a Bayesian incentive compatible mechanism from any, potentially non-optimal, algorithm that maps agents' reports to an allocation. The expected welfare of the mechanism is, approximately, at least that of the algorithm on the agents' true preferences.The construction is based on a maximum weight matching in the type space of each agent that be calculated quickly when the type spaces are reasonably sized. Furthermore, the computation can be performed independently for each agent and, therefore, scales well with the number of agents. A similar construction was previously given by Hartline and Lucier (2010) for agents with single-dimensional types; ours allows multi-dimensional types.

Original languageEnglish (US)
Pages (from-to)401-429
Number of pages29
JournalGames and Economic Behavior
StatePublished - Jul 1 2015


  • Algorithmic mechanism design
  • Bayesian mechanism design
  • Incentive compatibility
  • Multi-dimensional preferences

ASJC Scopus subject areas

  • Finance
  • Economics and Econometrics

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

Cite this