Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$54,000.00

Algorithm Design in Strategic and Uncertain Environments

EF 2022-23

Résumé
As information and communication systems become increasingly complex, there is a growing need for the development of efficient algorithmic tools for the design, maintenance and management of such systems, especially decentralized networks like the Internet and high-speed telecommunication networks. This research program will investigate the algorithmic questions that arise in such settings, focusing on two main problems. (a) 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 is often controlled by self-interested agents. Consequently, one needs to elicit this data by cleverly 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 such as truthfulness, and 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, Yahoo, Microsoft. (b) 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 that arise 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 that will find use in a variety of settings. We shall also investigate ambiguous stochastic problems, wherein the distribution modeling the uncertainty is itself imprecise. The techniques we develop should be useful in the design of communication networks, which often have to handle uncertain traffic. In many cases, the algorithmic problems encountered are computationally intractable, and our approach will be to devise an approximation algorithm for the problem, that is, a polynomial-time algorithm that always delivers a provably near-optimal feasible solution. Approximation algorithms are a common thread in our research, and our research will also further the development of techniques for the design and analysis of these algorithms.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-03885
Name nom
Swamy, Chaitanya
Department département
Combinatorics and Optimization - 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
2022
Competition year année de concours
2016
Award amount
54000
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
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:7
Partie
1
Nb partie
7
Application title
Algorithm Design in Strategic and Uncertain Environments
Application summary
As information and communication systems become increasingly complex, there is a growing need for the development of efficient algorithmic tools for the design, maintenance and management of such systems, especially decentralized networks like the Internet and high-speed telecommunication networks. This research program will investigate the algorithmic questions that arise in such settings, focusing on two main problems. (a) 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 is often controlled by self-interested agents. Consequently, one needs to elicit this data by cleverly 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 such as truthfulness, and 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, Yahoo, Microsoft. (b) 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 that arise 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 that will find use in a variety of settings. We shall also investigate ambiguous stochastic problems, wherein the distribution modeling the uncertainty is itself imprecise. The techniques we develop should be useful in the design of communication networks, which often have to handle uncertain traffic. In many cases, the algorithmic problems encountered are computationally intractable, and our approach will be to devise an approximation algorithm for the problem, that is, a polynomial-time algorithm that always delivers a provably near-optimal feasible solution. Approximation algorithms are a common thread in our research, and our research will also further the development of techniques for the design and analysis of these algorithms.