Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$25,000.00

Algorithms for planning under uncertainty and in the presence of selfish users

EF 2007-08

Résumé
Technological advances over the past few years have led to the development of systems of rapidly increasing size and complexity. The design, maintenance and management of such systems, especially high-speed telecommunication networks and decentralized networks like the Internet, which are the important computing and communication platforms of the future, present several challenges. In this proposal, we shall focus on two important issues that arise in the design of such systems: (a) Uncertainty in the data or specifications. Uncertainty is a facet of many practical decision environments, and to function effectively one needs to anticipate uncertainty and take measures to be robust in the presence of uncertainty. We will investigate the key underlying algorithmic problems in models that  abstract these settings, and develop techniques and efficient algorithms for effectively tackling these problems. (b) The presence of uncoordinated components in the system with ``selfish'' interests. In an environment with self-interested users, like the Internet with its autonomous sub-networks, one can no longer assume that the users will act as stipulated by the system designer to optimize performance. We shall study, when, and to what extent, does selfish behavior affect performance, ways to mitigate the resulting inefficiencies, and ways to devise algorithms in such selfish environments that resist manipulation. In many cases, the algorithmic problems encountered are computationally intractable (e.g., NP-hard) optimization problems, so it is unlikely that exact solutions can be computed in polynomial time, 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 constitute a unifying theme of this research, and our research will also have impact on this rich and exciting field by furthering the development of general principles 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
327620-2006
Name nom
Swamy, Chaitany
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
2007
Competition year année de concours
2006
Award amount
25000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
Partie
2
Nb partie
3
Application title
Algorithms for planning under uncertainty and in the presence of selfish users
Keyword
NA
Application summary
Technological advances over the past few years have led to the development of systems of rapidly increasing size and complexity. The design, maintenance and management of such systems, especially high-speed telecommunication networks and decentralized networks like the Internet, which are the important computing and communication platforms of the future, present several challenges. In this proposal, we shall focus on two important issues that arise in the design of such systems: (a) Uncertainty in the data or specifications. Uncertainty is a facet of many practical decision environments, and to function effectively one needs to anticipate uncertainty and take measures to be robust in the presence of uncertainty. We will investigate the key underlying algorithmic problems in models that  abstract these settings, and develop techniques and efficient algorithms for effectively tackling these problems. (b) The presence of uncoordinated components in the system with ``selfish'' interests. In an environment with self-interested users, like the Internet with its autonomous sub-networks, one can no longer assume that the users will act as stipulated by the system designer to optimize performance. We shall study, when, and to what extent, does selfish behavior affect performance, ways to mitigate the resulting inefficiencies, and ways to devise algorithms in such selfish environments that resist manipulation. In many cases, the algorithmic problems encountered are computationally intractable (e.g., NP-hard) optimization problems, so it is unlikely that exact solutions can be computed in polynomial time, 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 constitute a unifying theme of this research, and our research will also have impact on this rich and exciting field by furthering the development of general principles for the design and analysis of these algorithms.