Grant: Discovery Grants Program - Individual
McGill University
$55,000.00
Algorithmic Mechanism Design: Theory and Application
FY 2022-23
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2022-04191
Name nom
Vetta, Adrian
Department département
Computer Science, School of - Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2022
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:1
Partie
1
Nb partie
5
Application title
Algorithmic Mechanism Design: Theory and Application
Application summary
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.