Grant: Discovery Grants Program - Individual
University of Waterloo
$48,000.00
Algorithm Design for Strategic and Uncertain Environments
FY 2024-25
Summary
As information and communication systems become increasingly complex, it is essential to develop efficient algorithmic tools for the design, maintenance and management of such systems, especially decentralized networks like the Internet and high-speed communication networks. This research program shall investigate the algorithmic questions that arise in such settings, focusing on two main themes.
(1) The design of protocols that need to function in the presence of self-interested agents (e.g., autonomous systems on the Internet). In such settings, the task of algorithm-design is complicated by the fact that the data relevant to the problem may be controlled by self-interested agents. Consequently, one needs to elicit this data by incentivizing the users so that self-interested behavior leads to desirable outcomes. We shall focus on the development of techniques for the design and analysis of such efficient "manipulation-resistant" mechanisms. A particular emphasis will be to identify ways for "exporting" algorithms into manipulation-resistant mechanisms. We shall approach this task both by examining well-entrenched notions of manipulation-resistance like truthfulness, as also by considering the algorithmic Nash implementation problem of designing mechanisms whose Nash equilibria possess desirable properties. Our research will draw upon ideas from Computer Science and Economics and contribute to the thriving field of algorithmic mechanism design, an area whose importance has been recognized by leading IT companies such as Google, Microsoft, Amazon, due to its applications in e-commerce.
(2) Decision-making under uncertainty. Uncertainty is a facet of many decision environments, and for effective decision making, one needs to consider models that explicitly incorporate the uncertainty. A broad objective of our research is to explore models that abstract such settings, and devise methods for solving the algorithmic problems arising in such models. We shall study key problems that capture the underlying difficulties in such settings, focusing on the rich class of stochastic vehicle routing problems, and devise techniques of broad applicability. We shall also investigate distributionally-robust stochastic problems, wherein the distribution modeling the uncertainty is itself imprecise, and we seek to hedge with respect to a class of distributions. The techniques we develop should find use in the design of various types of networks such as communication networks, which have to handle uncertain traffic, and supply-chain networks, where one faces demand uncertainty.
We will often encounter computationally-intractable problems, and our approach will be to devise an approximation algorithm, which is an efficient algorithm that always returns a provably near-optimal solution. Approximation algorithms are a common thread of this research, and our research will also further the development of general principles for the design and analysis of such algorithms.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2024-04532
Name nom
Swamy, Chaitanya
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
48000
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
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
Algorithm Design for Strategic and Uncertain Environments
Keywords
algorithms; approximation algorithms; algorithmic game theory; combinatorial optimization; stochastic combinatorial optimization
Application summary
As information and communication systems become increasingly complex, it is essential to develop efficient algorithmic tools for the design, maintenance and management of such systems, especially decentralized networks like the Internet and high-speed communication networks. This research program shall investigate the algorithmic questions that arise in such settings, focusing on two main themes.
(1) The design of protocols that need to function in the presence of self-interested agents (e.g., autonomous systems on the Internet). In such settings, the task of algorithm-design is complicated by the fact that the data relevant to the problem may be controlled by self-interested agents. Consequently, one needs to elicit this data by incentivizing the users so that self-interested behavior leads to desirable outcomes. We shall focus on the development of techniques for the design and analysis of such efficient "manipulation-resistant" mechanisms. A particular emphasis will be to identify ways for "exporting" algorithms into manipulation-resistant mechanisms. We shall approach this task both by examining well-entrenched notions of manipulation-resistance like truthfulness, as also by considering the algorithmic Nash implementation problem of designing mechanisms whose Nash equilibria possess desirable properties. Our research will draw upon ideas from Computer Science and Economics and contribute to the thriving field of algorithmic mechanism design, an area whose importance has been recognized by leading IT companies such as Google, Microsoft, Amazon, due to its applications in e-commerce.
(2) Decision-making under uncertainty. Uncertainty is a facet of many decision environments, and for effective decision making, one needs to consider models that explicitly incorporate the uncertainty. A broad objective of our research is to explore models that abstract such settings, and devise methods for solving the algorithmic problems arising in such models. We shall study key problems that capture the underlying difficulties in such settings, focusing on the rich class of stochastic vehicle routing problems, and devise techniques of broad applicability. We shall also investigate distributionally-robust stochastic problems, wherein the distribution modeling the uncertainty is itself imprecise, and we seek to hedge with respect to a class of distributions. The techniques we develop should find use in the design of various types of networks such as communication networks, which have to handle uncertain traffic, and supply-chain networks, where one faces demand uncertainty.
We will often encounter computationally-intractable problems, and our approach will be to devise an approximation algorithm, which is an efficient algorithm that always returns a provably near-optimal solution. Approximation algorithms are a common thread of this research, and our research will also further the development of general principles for the design and analysis of such algorithms.