Bayesian incentive compatibility via fractional assignments

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