Worst-Case Mechanism Design via Bayesian Analysis

摘要: Budget feasible mechanism design is the study of procurement combinatorial auctions in which sellers have private costs to produce items, and buyer (auctioneer) aims maximize her valuation function on a subset purchased items under budget constraint total payment. One most important questions field “which domains admit truthful mechanisms with `small' approximations social optimum?” Singer [Proceedings 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] showed that submodular functions constant approximation mechanism. Dobzinski, Papadimitriou, 12th ACM Conference Electronic Commerce, ACM, New York, 2011, 273--282] gave an $O(\log^2n)$ for subadditive remarked “A fundamental question whether, regardless computational constraints, constant-factor exists functions.” In this paper, we ...