article · 2011

Bayesian Incentive Compatibility via Fractional Assignments

Cited by 67Abstract and details only

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.

Cite this paper

APA 7

Bei, X., & Huang, Z. (2011). Bayesian Incentive Compatibility via Fractional Assignments.

MLA 9

Bei, Xiaohui, and Zhiyi Huang. “Bayesian Incentive Compatibility via Fractional Assignments.” 2011.

Chicago

Bei, Xiaohui, and Zhiyi Huang. 2011. “Bayesian Incentive Compatibility via Fractional Assignments.”

Harvard

Bei, X. and Huang, Z. (2011) ‘Bayesian Incentive Compatibility via Fractional Assignments’.

BibTeX

@article{bei2011bayesian,
  title = {{Bayesian Incentive Compatibility via Fractional Assignments}},
  author = {Bei, Xiaohui and Huang, Zhiyi},
  year = {2011}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.