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.