A paradox of congestion in a queuing network

Joel E. Cohen
Frank P. Kelly

Journal of Applied Probability 27 (1990) 730-734.

Abstract

In an uncongested transportation network, adding routes and capacity to an existing network must decrease, or at worst not change, the average time individuals require to travel through the network from a source to a destination. Braess (1968) discovered that the same is not true in congested networks. Here we give an example of a queuing network in which added capacity leads to an increase in the mean transit time for everyone. Self-seeking individuals are unable to refrain from using the additional capacity, even though using it leads to deterioration in the mean transit time. This example appears to be the first queuing network to demonstrate the general principle that in non-cooperative games with smooth payout functions, user-determined equilibria generically deviate from system-optimal equilibria.

Keywords: Braess's paradox; Nash equilibria; non-cooperative game
JSTOR copy of paper, or here.
Citations.
Frank Kelly's papers