On the price of anarchy in unbounded delay networks

We investigate the worst case delay ratio between the Nash equilibrium and the social optimum in networks of N parallel links (routes) with unbounded delay functions. We compute this ratio, known as the "price of anarchy", for the case when the link delay functions correspond to M/M/ 1-FCFS or M/G/ 1-PS. For this problem, we find that the price of anarchy depends on the network topology in the sense that it is precisely equal to N. We then extend our results to M/G/ 1-FCFS and G/G/ 1-FCFS delay functions and compute the price of anarchy in a heavy load regime. Our results indicate that, even in very simple topological settings, the price of selfish behavior can potentially be very high.