School of Technology and Computer Science Seminars
The Analysis and Design of Network Congestion Games
by Dr. Umang Bhaskar (California Institute of Technology, USA)
Thursday, June 5, 2014
from
to
(Asia/Kolkata)
at Colaba Campus ( AG-80 )
at Colaba Campus ( AG-80 )
Description |
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. |