Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McMaster University

$17,000.00

Algorithmic and game-theoretic analysis of network design

EF 2013-14

Résumé
Is it possible for a network operator to lure network users into a certain behavior by lying to them for a very long time, especially when they are automated? Can we extend the lifetime of a solar-renewable battery used to keep traveling cars connected to the Internet? What is the best way to lay highways so that we can use the roads already built to connect cities as soon as possible on average? These are some of the problems arising during the modelling, construction, operation, and use of networks. They are addressed in this proposal by using tools from algorithmic game theory and by designing efficient approximation algorithms when those problems are proven to be computationally hard. The use of game-theoretical concepts to model environments with competitive entities has been the field of economists for many years. Algorithmic game theory is particularly suited for studying networks of selfish users and/or operators. The proposed work aspires to a paradigm shift in the use of algorithmic game theory from one-shot games to repeated games that now include a history of previous plays. We propose to do that by exploiting the constraints imposed on the players due to their automated (algorithmic) nature. Hence, the proposed work should reveal new connections between computer science and economics through the big volume of work already done by economists on repeated games and reputation effects. On a more practical level, the proposal introduces a new set of problems in approximation algorithms that are related to energy conservation and infrastructure construction in networks. Although more limited in scope than the objectives above, they nevertheless present us with the opportunity of immediate impact on the environment (by, for example, the clever scheduling of energy dispensation used for data transmission) or the cost of network infrastructure (by, for example, the time-efficient scheduling of building new roads). Such problems are usually hard to solve exactly, and, therefore, we propose the development of algorithms that produce provably good approximate solutions.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
262124-2012
Name nom
Karakostas, George
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2012
Award amount
17000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
800
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information and communication services
Area of application fr
Services d'information et de télé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
5
Application title
Algorithmic and game-theoretic analysis of network design
Keyword
NSERC
Application summary
Is it possible for a network operator to lure network users into a certain behavior by lying to them for a very long time, especially when they are automated? Can we extend the lifetime of a solar-renewable battery used to keep traveling cars connected to the Internet? What is the best way to lay highways so that we can use the roads already built to connect cities as soon as possible on average? These are some of the problems arising during the modelling, construction, operation, and use of networks. They are addressed in this proposal by using tools from algorithmic game theory and by designing efficient approximation algorithms when those problems are proven to be computationally hard. The use of game-theoretical concepts to model environments with competitive entities has been the field of economists for many years. Algorithmic game theory is particularly suited for studying networks of selfish users and/or operators. The proposed work aspires to a paradigm shift in the use of algorithmic game theory from one-shot games to repeated games that now include a history of previous plays. We propose to do that by exploiting the constraints imposed on the players due to their automated (algorithmic) nature. Hence, the proposed work should reveal new connections between computer science and economics through the big volume of work already done by economists on repeated games and reputation effects. On a more practical level, the proposal introduces a new set of problems in approximation algorithms that are related to energy conservation and infrastructure construction in networks. Although more limited in scope than the objectives above, they nevertheless present us with the opportunity of immediate impact on the environment (by, for example, the clever scheduling of energy dispensation used for data transmission) or the cost of network infrastructure (by, for example, the time-efficient scheduling of building new roads). Such problems are usually hard to solve exactly, and, therefore, we propose the development of algorithms that produce provably good approximate solutions.