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 language||English (US)|
|Title of host publication||Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011|
|Publisher||Association for Computing Machinery|
|Number of pages||14|
|State||Published - 2011|
|Name||Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms|
ASJC Scopus subject areas