Bayesian Incentive Compatibility via Matchings

Jason D. Hartline, Robert Kleinberg, Azarakhsh Malekian

Abstract

We give a simple reduction from Bayesian incentive compatible mechanism design to algorithm design in settings where the agents’ private types are multidimensional. 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.
BibTeX
@inproceedings{hartline2011bayesian,
  author = {Jason D. Hartline and Robert Kleinberg and Azarakhsh Malekian},
  title = {{Bayesian Incentive Compatibility via Matchings}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.58},
}

Loading related content...

Figure