Public Projects, Boolean Functions, and the Borders of Border's Theorem
Public Projects, Boolean Functions, and the Borders of Border's Theorem
复制标题
公共项目、布尔函数和边界定理的边界
DOI：
10.1145/2764468.2764538
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
Parikshit Gopalan;N. Nisan;Tim Roughgarden
边境定理给出了贝叶斯单项环境可行的临时分配规则的直观线性表征，并且在经济和算法机制设计中具有多种应用。 Border定理的所有已知概括都限制了关注相对简单的设置，或者诉诸近似。本文确定了复杂性理论障碍，该障碍物表明，假设标准的复杂性分离，则边界定理不能显着扩展到最新的范围之外。当应用于公共项目设置时，我们还确定了迈尔森的最佳拍卖理论与布尔功能分析的一些基本结果之间的惊人紧密联系。
Border's theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in economic and algorithmic mechanism design. All known generalizations of Border's theorem either restrict attention to relatively simple settings, or resort to approximation. This paper identifies a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. We also identify a surprisingly tight connection between Myerson's optimal auction theory, when applied to public project settings, and some fundamental results in the analysis of Boolean functions.