Corelab Seminar

Thanasis Lianeas (NTUA)
Network Design for Bottleneck Routing Games

In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal.

In this talk, we will focus on the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We shall see that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox,but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as (n^0,121) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^0,121-), for any constant >0.