On Braess’ paradox and non-increasing cost functions

Braess’ para­dox is a counter-intu­it­ive res­ult in trans­port­a­tion sci­ence, which in essence states that if you add addi­tion­al capa­city to a net­work, over­all net­work per­form­ance may in fact decrease, if agents are free to (greed­ily) choose a path that min­im­ises their own latency. In this post, I’ll explain Braess’ para­dox, and provide a new example that uses only non-increas­ing cost func­tions.

Let’s con­sider the fol­low­ing net­work setup:

Braess’ paradox - initial setup

We have four towns, s, v, w and t, and one unit of traffic that needs to get from s to t using this net­work. The cost func­tions c(x) on the links indic­ate how long it takes to use that route as a func­tion of the frac­tion of the traffic that will take that link (in some unit of time, say hours). For example, if the link’s cost func­tion is c(x) = x and half the traffic goes along that link, then it will take every­one half an hour to tra­verse that link. You can think of these roads as nar­row roads that are rather sus­cept­ible to con­ges­tion. The links with cost func­tions c(x) = 1 are not affected by the traffic flow at all; these are ana­log­ous to long, but very wide, high­ways.

In the above case, because the top route (s-v-t) is identic­al to the bot­tom route (s-w-t), traffic will spread itself out between the two routes: half will go up the top and the oth­er half will go down the bot­tom. The aver­age time taken is 1.5 hours. But what if the loc­al gov­ern­ment decided to improve the net­work by adding a new super-fast high­way from v to w that takes abso­lutely no time to tra­verse?

Braess’ paradox - augmented network

The people tak­ing the s-w link will think, “Hey, going via s-v-w is no worse than tak­ing s-w, and it can actu­ally be quick­er. I’ll take that instead!” The same logic goes for why every­one will end up tak­ing v-w-t instead of v-t, because v-w-t can­not be worse, but it can actu­ally be faster, if a small frac­tion of people don’t take it (note the cost func­tion on w-t). So every­one ends up on s-v-w-t, which means an aver­age time of 2 hours. Oops.

If you think back to the real world, that’s why build­ing a new high­way doesn’t solve all our traffic night­mares, and can, in some cases, make the prob­lem worse. People using sides roads or tak­ing the train to work con­verge on the new high­way, and you’re back to square one.

Braess’ para­dox doesn’t just occur for net­works where the cost of a link goes up as the num­ber of people use it. For net­works with non-increas­ing cost func­tions (e.g. the cost of a link goes down as the num­ber of people use it goes up), where con­ges­tion is a good thing, we can find an ana­log­ous situ­ation. Con­sider the fol­low­ing net­work, where 1 unit of traffic needs to be routed from s1 to t1, and anoth­er unit from s2 to t2:

Decreasing case - initial setup

You’ll find that the total cost is 6 (3 each for the s1-t1 and s2-t2 guys). Now, someone with deep pock­ets builds a new link to shave a little off the s1-t1 route:

Decreasing case - augmented network

The dir­ect s1-t1 route is more attract­ive than the 3 hour hike via u and v, so every­one who wants to go from s1 to t1 takes that route instead. Because the u-v link isn’t shared any­more, its cost goes up quite a bit, and the total cost now becomes 6.5. Shar­ing is caring.

Tags: , , , ,

1 comment

  1. Dan’s avatar

    So this is why new high­ways are always imme­di­ately con­ges­ted.

Comments are now closed.