Mechanism design via correlation gap
Mechanism design via correlation gap
复制标题
通过相关间隙进行机制设计
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Qiqi Yan
中科院分区：
文献类型：
--
作者：
Qiqi Yan
对于单一贝叶斯环境中的收入和福利最大化，Chawla等人（Stoc10）最近表明，与本文中的最佳机制相比，顺序的张贴优点机制（SPMS）可以表现出色。我们基于与相关差距的概念的联系，对这一事实进行理论解释。
对于具有矩阵约束的拍卖环境，我们可以将机制的性能与随机集合的单调下调函数的期望相关联。对应于SPM的某些需求，这是独立的。忽略随机集中的相关性，因此我们在使用某些SPM而不是最佳机制方面的损失。通过一个良好的恒定因素。
利用这一联系，我们对Chawla等人的贪婪SPM进行了严格的分析。 （1--1/√2πk） - K-Unit拍卖的重要子案例的APPROXIMATION，并为具有p独立于设置系统约束的环境给出（P + 1） - approximation。
For revenue and welfare maximization in single-dimensional Bayesian settings, Chawla et al. (STOC10) recently showed that sequential posted-price mechanisms (SPMs), though simple in form, can perform surprisingly well compared to the optimal mechanisms. In this paper, we give a theoretical explanation of this fact, based on a connection to the notion of correlation gap.
Loosely speaking, for auction environments with matroid constraints, we can relate the performance of a mechanism to the expectation of a monotone submodular function over a random set. This random set corresponds to the winner set for the optimal mechanism, which is highly correlated, and corresponds to certain demand set for SPMs, which is independent. The notion of correlation gap of Agrawal et al. (SODA10) quantifies how much we "lose" in the expectation of the function by ignoring correlation in the random set, and hence bounds our loss in using certain SPM instead of the optimal mechanism. Furthermore, the correlation gap of a monotone and submodular function is known to be small, and it follows that certain SPM can approximate the optimal mechanism by a good constant factor.
Exploiting this connection, we give tight analysis of a greedy-based SPM of Chawla et al. for several environments. In particular, we show that it gives an e/(e − 1)-approximation for matroid environments, gives asymptotically a 1/(1--1/√2πk)-approximation for the important sub-case of k-unit auctions, and gives a (p + 1)-approximation for environments with p-independent set system constraints.