Bayesian Incentive Compatibility via Fractional Assignments

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 work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 71 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.