An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
复制标题
次加法组合拍卖的 O(log log m) 预言不等式
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Brendan Lucier
中科院分区：
文献类型：
--
作者：
Paul Dütting;Thomas Kesselheim;Brendan Lucier
先知不平等比较了在线算法对于随机优化问题的预期性能与事后预期的最佳解决方案的预期性能。它们是经典最差竞争分析的主要替代方法，在简单（张贴）激励机制的设计和分析中尤其重要，并具有可证明的近似保证。该领域的一个主要开放问题涉及亚辅助组合拍卖。在这里，具有亚估值功能的N代理争夺M项目的分配。目的是找到最大化分配总值的项目的分配。问题是是否存在此问题的先知不平等，该问题显着超过了O（log M）的最著名近似因素。我们通过提供O（日志M）先知不平等来取得重大进展。我们的证明是通过一种新颖的原始偶尔方法。它也是建设性的，导致在线政策采用静态和匿名物品价格的形式，可以在多项式时间内计算出对估值的适当查询访问权限。作为我们方法的应用，我们基于发布的价格构建了一种简单而激励的兼容机制，该机制可实现O（log M）近似值，以在项目独立假设下对亚基估值的最佳收入达到最佳收入。
Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here n agents with subadditive valuation functions compete for the assignment of m items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of O(log m). We make major progress on this question by providing an O(log log m) prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an O(log log m) approximation to the optimal revenue for subadditive valuations under an item-independence assumption.