Assessing the Robustness of Cremer-McLean with Automated Mechanism Design
Assessing the Robustness of Cremer-McLean with Automated Mechanism Design
复制标题
通过自动化机构设计评估 Cremer-McLean 的鲁棒性
DOI：
10.1609/aaai.v29i1.9293
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Giuseppe Lopomo
中科院分区：
文献类型：
--
作者：
Michael Albert;Vincent Conitzer;Giuseppe Lopomo
在机制设计文献中的一个经典结果中，Cremerand McLean（1985）表明，如果买方的估值充分相关，则存在一种机制，允许卖方从有效配置中提取全部剩余作为收入。这个结果通常被视为“好得令人难以置信”（在实践中），使人们对其建模假设产生怀疑。在本文中，我们使用自动化机制设计方法来评估Cremer-McLean结果对放松其主要技术假设的敏感性。这一假设意味着，竞标者可能拥有的每一种估值都会导致外部信号的唯一条件分布。我们放宽了这一点，允许多个估值与外部信号上的相同分布一致。使用与Cremer-McLean类似的见解，我们提供了一种高效的算法来计算这种更一般的情况下的最优收益。使用该算法，我们观察到，随着与分布一致的估值数量的增加，最优收益迅速下降到储备价格机制的收益。因此，自动化机制设计使我们能够深入了解Cremer-McLean“好得令人难以置信”的精确含义。
In a classic result in the mechanism design literature, Cremerand McLean (1985) show that if buyers’ valuations are sufficiently correlated, a mechanism exists that allows the seller to extract the full surplus from efficient allocation as revenue. This result is commonly seen as “too good to be true” (in practice), casting doubt on its modeling assumptions. In this paper, we use an automated mechanism design approach to assess how sensitive the Cremer-McLean result is to relaxing its main technical assumption. That assumption implies that each valuation that a bidder can have results in a unique conditional distribution over the external signal(s). We relax this, allowing multiple valuations to be consistent with the same distribution over the external signal(s). Using similar insights to Cremer-McLean, we provide a highly efficient algorithm for computing the optimal revenue in this more general case. Using this algorithm, we observe that indeed, as the number of valuations consistent with a distribution grows, the optimal revenue quickly drops to that of a reserve-price mechanism. Thus, automated mechanism design allows us to gain insight into the precise sense in which Cremer-McLean is “too good to be true.”