ICES: Small: Heuristic Mechanism Design

计算机制设计（Computational Mechanism Design，CMD）试图理解如何在多智能体系统中促进期望的结果，尽管有私人信息，自我利益和有限的计算资源。CMD在许多设置中找到应用;例如，在无线频谱和机场着陆权的公共部门，在互联网广告，在供应链中的表达性采购，在计算系统中的资源分配。一个关键的概念是防策略性：该机制的结果应该是强大的，以防止通过参与者所持有的私人信息的误报而进行的操纵。在满足这些丰富领域对CMD的需求时，我们通常需要从经济机制设计的理论到可部署的计算机制的实践之间建立桥梁。这个项目的主要目标是利用可扩展的启发式优化算法，使它们适用于具有自我利益的设置。而不是寻求可证明的最佳，但可能不适用的机制（无论是没有复杂性的考虑，如在经济理论，或与最坏情况下的复杂性考虑，是在理论计算机科学中常见的），我们提出了一个新的计算议程。尽管如此，启发式搜索算法被广泛采用，并找到了很好的经验成功。我们寻找类似的东西，在输入被分配给参与者的设置中，每个人都是自私的，并且愿意误报输入，以改善对他们有利的结果。而不是寻找最佳的机制之间的类多项式时间算法，我们寻求采用搜索算法，尽管最坏情况下的指数运行时间（如果运行到完成）具有出色的经验性能。感兴趣的具体主题包括：（a）自动自我校正，应用在线敏感性分析自动校正算法的结果，使算法与支付相结合，并使其具有防策略性;（B）近似防策略性的度量，使设计无需求解均衡;以及（c）通过使用机器学习自动生成支付规则，通过在假设空间上施加适当的结构。成功的进展将提供新的和基本的方法论，用以开发激励一致的机制（例如，在一个实施例中，用于资源和任务分配），其享有优秀的经验性质并且能够扩展到现实世界的领域。机制设计理论已经产生了广泛的社会影响，使无线频谱和发电能力等公共资源的拍卖成为可能，并通过有效的广告为互联网企业带来收入。启发式机制设计的新框架将实现新一代机制，用于人、企业和组织之间的大规模协调和资源分配，并有望广泛应用于电子商务（包括移动的商务）、云计算和整个供应链。

Computational mechanism design (CMD) seeks to understand how to promote desirable outcomes in multi-agent systems, despite private information, self-interest and limited computational resources. CMD finds application in many settings; e.g., in the public sector for wireless spectrum and airport landing rights, in Internet advertising, in expressive sourcing in the supply chain, in allocating resources in computational systems. A key concept is strategyproofness: the mechanism's outcome should be robust against manipulations through misreports of private information held by participants.In meeting the demands for CMD in these rich domains, we often need to bridge from the theory of economic mechanism design to the practice of deployable, computational mechanisms. The broad goal of this project is to leverage scalable, heuristic optimization algorithms, making them applicable in settings with self-interest. Rather than seeking provably optimal but possibly inapplicable mechanisms (either without complexity considerations, as in economic theory, or with worst-case complexity considerations, as is commonplace in theoretical computer science), we propose a new computational agenda.Provable guarantees are often unavailable when search algorithms are applied to real-world optimization problems. Still, heuristic search algorithms are widely employed, and find good empirical success. We seek something analogous to this for settings in which inputs are distributed to participants, each self-interested and willing to misreport inputs in order to improve the outcome in their favor. Rather than looking for optimal mechanisms amongst the class of polynomial-time algorithms, we seek to employ search algorithms with excellent empirical performance despite worst-case exponential run-time (if run-to-completion.)Specific topics of interest include: (a) automatic self-correction, to apply online sensitivity analysis to automatically correct the outcome of an algorithm, allowing the algorithm to be coupled with payments and made strategyproof; (b) metrics for approximate strategyproofness, to enable design without solving for equilibrium; and (c) automatic generation of payment rules through the use of machine learning, by imposing appropriate structure on the hypothesis space.Successful progress will provide new and fundamental methodologies with which to develop incentive-aligned mechanisms (e.g., for resource and task allocation) that enjoy excellent empirical properties and are able to scale to real-world domains. The theory of mechanism design has already provided broad societal impact, in enabling the auctioning of public resources such as wireless spectrum and power generation capacity, and in driving revenue to internet businesses by enabling efficient advertising. A new framework for heuristic mechanism design will enable a new generation of mechanisms for large-scale coordination and resource allocation amongst people, firms and organizations, with the promise of broad applications to electronic commerce (including mobile commerce), cloud computing, and across the supply chain.