Grant: Discovery Grants Program - Individual
McGill University
$55,000.00
Algorithmic Mechanism Design: Theory and Application
EF 2024-25
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2022-04191
Name nom
Vetta, Adrian
Department département
School of Computer Science, Department of Mathematics and Statistics
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
2024
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
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Algorithmic Mechanism Design: Theory and Application
Keywords
algorithms and complexity; mechanism design and game theory; algorithmic economics; graph theory and combinatorics; network optimization; learning dynamics; approximation algorithms; spectrum auctions; cap-and-trade systems; kidney exchange
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.