ICES: Small: Heuristic 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.