selfish routing

Braess’ para­dox is a counter-​​intuitive res­ult in trans­port­a­tion sci­ence, which in essence states that if you add addi­tional 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-​​increasing cost functions.

Let’s con­sider the fol­low­ing net­work 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, highways.

In the above case, because the top route (s-​​v-​​t) is identical 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 other half will go down the bot­tom. The aver­age time taken is 1.5 hours. But what if the local 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 traverse?

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 quicker. 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-​​increasing 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 another unit from s2 to t2:

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:

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.