Bayesian Incentive Compatibility via Fractional Assignments

Xiaohui Bei, Zhiyi Huang

2011 · 76 citations · 18 references

Concepts

Abstract

Very recently, Hartline and Lucier [HL10] studied single-parameter mechanism design prob-lems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian incentive compatible (BIC) mechanisms and preserved the expected social welfare. It remains a 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 -BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an -BIC mechanism that achieves constant approximation.

References

18