TY - GEN

T1 - Bayesian algorithmic mechanism design

AU - Hartline, Jason D

AU - Lucier, Brendan

PY - 2010/7/23

Y1 - 2010/7/23

N2 - 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.

AB - 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.

KW - Bayesian incentive compatibility

KW - algorithms

KW - mechanism design

KW - social welfare.

UR - http://www.scopus.com/inward/record.url?scp=77954691037&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954691037&partnerID=8YFLogxK

U2 - 10.1145/1806689.1806732

DO - 10.1145/1806689.1806732

M3 - Conference contribution

AN - SCOPUS:77954691037

SN - 9781605588179

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 301

EP - 310

BT - STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing

T2 - 42nd ACM Symposium on Theory of Computing, STOC 2010

Y2 - 5 June 2010 through 8 June 2010

ER -