The Analysis and Design of Network Congestion Games

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.