Tata Institute of Fundamental Research
The Analysis and Design of Network Congestion Games
Seminar
Speaker:
Umang Bhaskar (California Institute of Technology
1200 E. California Blvd.
Pasadena, CA 91125
United States of America)
Organiser:
Kavitha Telikepalli
Date:
Thursday, 5 Jun 2014, 12:00 to 13:00
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: In many applications, users strategically choose paths in a network to minimize the congestion they face. Examples of such applications are road traffic, data networks, and machine scheduling. Network congestion games model this strategic behaviour of the users, and are used to understand and predict the impact of this behaviour on congestion in the network.
In this talk, I first introduce network congestion games and present results for fundamental properties of these games. I then consider a natural design problem: to increment capacity in the network under a fixed budget, so that the average congestion for the strategic users is minimized. This problem is widely studied in transportation research. Despite this, there are very few guarantees for polynomial-time algorithms. I will present both algorithms and hardness results for this network improvement problem in different network topologies, and describe a number of related problems as directions for future research.
| Speaker: | Umang Bhaskar (California Institute of Technology 1200 E. California Blvd. Pasadena, CA 91125 United States of America) |
| Organiser: | Kavitha Telikepalli |
| Date: | Thursday, 5 Jun 2014, 12:00 to 13:00 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: In many applications, users strategically choose paths in a network to minimize the congestion they face. Examples of such applications are road traffic, data networks, and machine scheduling. Network congestion games model this strategic behaviour of the users, and are used to understand and predict the impact of this behaviour on congestion in the network.
In this talk, I first introduce network congestion games and present results for fundamental properties of these games. I then consider a natural design problem: to increment capacity in the network under a fixed budget, so that the average congestion for the strategic users is minimized. This problem is widely studied in transportation research. Despite this, there are very few guarantees for polynomial-time algorithms. I will present both algorithms and hardness results for this network improvement problem in different network topologies, and describe a number of related problems as directions for future research.
In this talk, I first introduce network congestion games and present results for fundamental properties of these games. I then consider a natural design problem: to increment capacity in the network under a fixed budget, so that the average congestion for the strategic users is minimized. This problem is widely studied in transportation research. Despite this, there are very few guarantees for polynomial-time algorithms. I will present both algorithms and hardness results for this network improvement problem in different network topologies, and describe a number of related problems as directions for future research.