Algorithmic Mechanism Design: Theory and 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.