Bayesian Incentive Compatibility via Fractional Assignments

Details Bayesian Incentive Compatibility via Fractional Assignments Bayesian Incentive Compatibility via Fractional Assignments

2010-05-24

arxiv.org/abs/1005.4244v4

Computer Science

Computer Science and Game Theory

22 pages, 1 figure

Scientific paper

Very recently, Hartline and Lucier studied single-parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive-Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an eps-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an eps-BIC mechanism that achieves constant approximation.

Affiliated with

Also associated with

No associations

Rating

Bayesian Incentive Compatibility via Fractional Assignments 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 Incentive Compatibility via Fractional Assignments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bayesian Incentive Compatibility via Fractional Assignments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-118716