Algorithmic Mechanism Design: Theory and Application

算法机制设计：理论与应用

• 批准号: RGPIN-2022-04191
• 负责人: Vetta, Adrian
• 金额: $ 4.01万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750394
• 关键词: Algorithmic; Mechanism; Design; Theory; Application

This proposal pertains to algorithmic mechanism design in multi-agent systems. Classical mechanism design attempts to address problems caused by the disparate objectives of the individual agents. In particular, it concerns the theoretical implementation of incentive-compatible systems that are resistant to strategic gaming. Algorithmic mechanism design extends its focuses beyond basic incentives and onto practical implementation. Specifically, the aim is to construct mechanisms that are fast and efficient but also have provably strong performance guarantees, both in theory and practice. From a computer science perspective, computational complexity plays a fundamental role here: practical mechanisms must be computationally implementable. Furthermore, we are interested in fair mechanism design. We desire systems that are simple, transparent and unbiased. Notably, there are two aspects that must be considered. One, mechanisms whose underlying algorithms are fair and two, mechanisms that produce fair outcomes. We emphasize that these two aspects are not necessarily synonymous and investigating and understanding this distinction is a key aim of this proposal. Multi-agent systems are ubiquitous so the potential range of application is vast, but our focus is upon the following important applications: combinatorial auction mechanisms such as spectrum auctions, cap-and-trade mechanisms to combat pollution, kidney-exchange mechanisms, voting mechanisms, and unbiased decision-making mechanisms. Evidently, the basic methodological tools we will use arise from game theory and from algorithms and complexity. In addition, to quantitatively analyze performance and performance trade-offs across multiple objectives, mathematical techniques from optimization and from probability theory will be invaluable. Finally, in many of these projects, networks play a fundamental role in modelling the underlying problem structure. Consequently, algorithmic methods from graph theory and combinatorics will then be at the heart of our quantitative analyses. The expected impact of this research program is two-fold. On the theory-side, our work will allow for the development of new tools and methodologies to aid in the design of mechanisms that are both fair and efficacious. On the applied-side, our work will provide expert guidance to decision makers worldwide and, most specifically, to Canadian decision makers with regards to kidney exchanges, spectrum auctions, and carbon pricing.

这个建议属于多智能体系统中的算法机制设计。经典的机制设计试图解决由个体代理的不同目标引起的问题。特别是，它涉及的理论实现的激励兼容的系统，抵抗战略游戏。激励机制的设计将其重点从基本激励扩展到实际执行。具体而言，目的是建立快速和有效的机制，但也有可证明的强大的性能保证，无论是在理论上还是实践中。从计算机科学的角度来看，计算复杂性在这里起着基础性的作用：实用的机制必须是计算可实现的。此外，我们对公平的机制设计感兴趣。我们希望系统简单、透明和公正。值得注意的是，必须考虑两个方面。第一种机制的基础算法是公平的，第二种机制产生公平的结果。我们强调，这两个方面不一定是同义词，调查和理解这一区别是本提案的一个关键目标。多智能体系统是无处不在的，所以潜在的应用范围是广阔的，但我们的重点是在以下重要的应用：组合拍卖机制，如频谱拍卖，总量管制和交易机制，以打击污染，肾脏交换机制，投票机制和公正的决策机制。显然，我们将使用的基本方法论工具来自博弈论、算法和复杂性。此外，为了定量分析多个目标的性能和性能权衡，来自优化和概率论的数学技术将是非常宝贵的。最后，在许多这样的项目中，网络在模拟潜在问题结构方面发挥着重要作用。因此，来自图论和组合学的算法方法将成为我们定量分析的核心。这项研究计划的预期影响是双重的。在理论方面，我们的工作将允许开发新的工具和方法，以帮助设计既公平又有效的机制。在应用方面，我们的工作将为全球决策者提供专家指导，特别是加拿大决策者关于肾脏交换，频谱拍卖和碳定价。