ICES: Small: Heuristic Mechanism Design

ICES：小：启发式机制设计

• 批准号: 1101570
• 负责人: David Parkes
• 金额: $ 35.99万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-05-01 至 2015-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1101570&HistoricalAwards=false
• 关键词: ICES; Small; Heuristic; Mechanism; Design

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.

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