Incremental Mechanism Design
Incremental Mechanism Design
复制标题
增量机构设计
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
Vincent Conitzer;T. Sandholm
传统上，机制设计几乎完全集中在真实机制的设计上。这有几个缺点：1.在某些设置（例如投票设置）中，不存在期望的策略证明机制; 2.真实机制不能利用计算上受限的代理可能不能找到最佳操纵的事实，以及3.当自动设计机构时，这种方法导致约束优化问题，对于这些问题，当前的技术不能扩展到非常大的实例。在本文中，我们提出了一种完全不同的方法：我们从一个简单的（可操作的）机制开始，并在一系列迭代中逐步使其更具策略性。
我们给出了我们的方法生成的机制（变体）的示例，包括一般支付环境中的VCG机制，以及带有决选的多元化投票规则。我们还提供了几个基本的算法，自动执行我们的方法在一般设置。最后，我们讨论如何计算困难的代理找到任何剩余的有益的操纵。
Mechanism design has traditionally focused almost exclusively on the design of truthful mechanisms. There are several drawbacks to this: 1. in certain settings (e.g. voting settings), no desirable strategy proof mechanisms exist; 2. truthful mechanisms are unable to take advantage of the fact that computationally bounded agents may not be able to find the best manipulation, and 3. when designing mechanisms automatically, this approach leads to constrained optimization problems for which current techniques do not scale to very large instances. In this paper, we suggest an entirely different approach: we start with a naive (manipulable) mechanism, and incrementally make it more strategy proof over a sequence of iterations.
We give examples of mechanisms that (variants of) our approach generate, including the VCG mechanism in general settings with payments, and the plurality-with-runoff voting rule. We also provide several basic algorithms for automatically executing our approach in general settings. Finally, we discuss how computationally hard it is for agents to find any remaining beneficial manipulation.