2011 · 76 citations · 18 references
BusinessEconomicsMathematicsAuction TheoryGame TheoryMicroeconomicsBayesian Decision TheoryBayesian GamesBayesian InferenceBayesian StatisticsCombinatorial AuctionsIncentive CompatibilityApproximation In Mechanism DesignBayesian Incentive CompatibilityBayesian Mechanism DesignBayesian OptimizationPrior Distribution SpecificationSocial Welfare Theorems
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.
18
COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERS
William Vickrey · The Journal of Finance · 1961 · 7.3K citations
Roger B. Myerson · Mathematics of Operations Research · 1981 · 6.1K citations
Theodore Groves · Econometrica · 1973 · 3.3K citations
Management, Organization Studies, Organizational Behavior +17
Multipart pricing of public goods
Edward H. Clarke · Public Choice · 1971 · 3.3K citations
Walrasian Equilibrium with Gross Substitutes
Faruk Gül, Ennio Stacchetti · Journal of Economic Theory · 1999 · 648 citations