Automated Design of Robust Mechanisms
Automated Design of Robust Mechanisms
复制标题
稳健机构的自动化设计
DOI：
10.1609/aaai.v31i1.10574
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Stone
中科院分区：
文献类型：
--
作者：
Michael Albert;Vincent Conitzer;P. Stone
我们引入了一类新的机制，稳健机制，它是事后机制和贝叶斯机制之间的中介。这类新的机制使机制设计者能够纳入对投标人估值分布的不精确估计，从而提供强有力的保证，确保该机制的表现至少与事后机制一样好，同时在许多情况下表现得更好。我们进一步将这一类扩展到具有高概率激励相容和个体理性、ε-稳健机制的机制。利用自动机制设计和稳健优化技术，我们给出了一个关于投标人类型数目的算法多项式来设计健壮性和ε健壮性机制。我们的实验表明，当机制设计者对分布进行估计并且投标人的估值与外部可验证的信号相关时，这种新的机制可以显著地优于传统的机制设计技术。
We introduce a new class of mechanisms, robust mechanisms, that is an intermediary between ex-post mechanisms and Bayesian mechanisms. This new class of mechanisms allows the mechanism designer to incorporate imprecise estimates of the distribution over bidder valuations in a way that provides strong guarantees that the mechanism will perform at least as well as ex-post mechanisms, while in many cases performing better. We further extend this class to mechanisms that are with high probability incentive compatible and individually rational, ε-robust mechanisms. Using techniques from automated mechanism design and robust optimization, we provide an algorithm polynomial in the number of bidder types to design robust and ε-robust mechanisms. We show experimentally that this new class of mechanisms can significantly outperform traditional mechanism design techniques when the mechanism designer has an estimate of the distribution and the bidder’s valuation is correlated with an externally verifiable signal.