Worst-Case Mechanism Design via Bayesian Analysis
Worst-Case Mechanism Design via Bayesian Analysis
复制标题
通过贝叶斯分析进行最坏情况机制设计
DOI：
10.1137/16m1067275
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Lu
中科院分区：
文献类型：
--
作者：
Xiaohui Bei;Ning Chen;N. Gravin;P. Lu
预算可行机制设计是对采购组合拍卖的研究，其中卖方有生产物品的私人成本，而买方（拍卖师）的目标是在总付款的预算约束下最大化其对购买物品子集的估价函数。该领域最重要的问题之一是“哪些评估领域承认真实的预算可行机制，与社会最优值‘小’近似？” Singer [Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] 表明子模函数具有恒定逼近机制。 Dobzinski、Papadimitriou 和 Singer [第 12 届 ACM 电子商务会议论文集，ACM，纽约，2011 年，第 273--282 页] 给出了次加法函数的 $O(\log^2n)$ 近似机制，并指出“一个基本问题是，无论计算限制如何，是否存在针对次加法函数的常数因子预算可行机制” 功能”。在本文中，我们...
Budget feasible mechanism design is the study of procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize her valuation function on a subset of purchased items under the budget constraint on the total payment. One of the most important questions in the field is “which valuation domains admit truthful budget feasible mechanisms with `small' approximations to the social optimum?” Singer [Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] showed that submodular functions have a constant approximation mechanism. Dobzinski, Papadimitriou, and Singer [Proceedings of the 12th ACM Conference on Electronic Commerce, ACM, New York, 2011, pp. 273--282] gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that “A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions.” In this paper, we ...