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.