Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$25,000.00

Algorithmic game theory and approximate network design

EF 2010-11

Résumé
The last decade has seen renewed interest in classical game theory -- a field that studies the behavior of rational self-interested agents in competitive environments. The current focus is on algorithmic aspects of games: Can we find Nash equilibria efficiently in certain games? What is the loss in social welfare (the price of anarchy) if players are allowed to act independently and greedily? Are there incentive mechanisms that force players to behave in a truthful and fair manner? For many of these questions, ideas from combinatorial optimization and theoretical computer science provide key new insights. Conversely, Gupta et al. [STOC '03, FOCS '03] showed that game-theoretic cost-sharing ideas can be fruitfully applied to the design and analysis of approximation algorithms for network design problems. The long-term goal of my research is to further explore the relationship between game theory, theoretical computer science and combinatorial optimization. I have contributed to this area in joint work with S. Leonardi and G. Schaefer. We studied a game-theoretic variant of the Steiner forest problem, where each player j, out of a set of k players, strives to connect the vertices of her terminal pair (s_j, t_j) in a given undirected, edge-weighted graph G. We show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein and Ravi [Siam J. of Computing, 1995] and Goemans and Williamson [Siam J. of Computing, 1995] yields a 2-budget balanced and group-strategyproof mechanism for this game. We also showed that the mechanism-design ideas used in our work give rise to a new linear programming relaxation for the Steiner forest problem which is strictly stronger than the well-known undirected cut relaxation for this problem. As short-term goals, I plan to address the following questions: can we use the new Steiner forest LP relaxation to obtain better Steiner forest approximation algorithms? Can the mechanism design techniques used for the Steiner forest problem be applied to a larger class of network design problems? Can we obtain tighter LP relaxations for these problems?
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
288340-2007
Name nom
Konemann, Jochen
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
2010
Competition year année de concours
2007
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
802
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 systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
4
Nb partie
5
Application title
Algorithmic game theory and approximate network design
Keyword
NSERC
Application summary
The last decade has seen renewed interest in classical game theory -- a field that studies the behavior of rational self-interested agents in competitive environments. The current focus is on algorithmic aspects of games: Can we find Nash equilibria efficiently in certain games? What is the loss in social welfare (the price of anarchy) if players are allowed to act independently and greedily? Are there incentive mechanisms that force players to behave in a truthful and fair manner? For many of these questions, ideas from combinatorial optimization and theoretical computer science provide key new insights. Conversely, Gupta et al. [STOC '03, FOCS '03] showed that game-theoretic cost-sharing ideas can be fruitfully applied to the design and analysis of approximation algorithms for network design problems. The long-term goal of my research is to further explore the relationship between game theory, theoretical computer science and combinatorial optimization. I have contributed to this area in joint work with S. Leonardi and G. Schaefer. We studied a game-theoretic variant of the Steiner forest problem, where each player j, out of a set of k players, strives to connect the vertices of her terminal pair (s_j, t_j) in a given undirected, edge-weighted graph G. We show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein and Ravi [Siam J. of Computing, 1995] and Goemans and Williamson [Siam J. of Computing, 1995] yields a 2-budget balanced and group-strategyproof mechanism for this game. We also showed that the mechanism-design ideas used in our work give rise to a new linear programming relaxation for the Steiner forest problem which is strictly stronger than the well-known undirected cut relaxation for this problem. As short-term goals, I plan to address the following questions: can we use the new Steiner forest LP relaxation to obtain better Steiner forest approximation algorithms? Can the mechanism design techniques used for the Steiner forest problem be applied to a larger class of network design problems? Can we obtain tighter LP relaxations for these problems?