Bayesian Algorithmic Mechanism Design

Details Bayesian Algorithmic Mechanism Design Bayesian Algorithmic Mechanism Design

2009-09-25

arxiv.org/abs/0909.4756v2

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Bayesian Algorithmic Mechanism Design does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bayesian Algorithmic Mechanism Design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bayesian Algorithmic Mechanism Design will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-326429