On Braess' paradox and non-increasing cost functions

Braess' paradox is a counter-intuitive result in transportation science, which in essence states that if you add additional capacity to a network, overall network performance may in fact decrease, if agents are free to (greedily) choose a path that minimises their own latency. In this post, I'll explain Braess' paradox, and provide a new example that uses only non-increasing cost functions.

Let's consider the following network 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 network. The cost functions c(x) on the links indicate how long it takes to use that route as a function of the fraction of the traffic that will take that link (in some unit of time, say hours). For example, if the link's cost function is c(x) = x and half the traffic goes along that link, then it will take everyone half an hour to traverse that link. You can think of these roads as narrow roads that are rather susceptible to congestion. The links with cost functions c(x) = 1 are not affected by the traffic flow at all; these are analogous to long, but very wide, highways.

In the above case, because the top route (s-v-t) is identical to the bottom 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 bottom. The average time taken is 1.5 hours. But what if the local government decided to improve the network by adding a new super-fast highway from v to w that takes absolutely no time to traverse?

Braess’ paradox - augmented network

The people taking the s-w link will think, "Hey, going via s-v-w is no worse than taking s-w, and it can actually be quicker. I'll take that instead!" The same logic goes for why everyone will end up taking v-w-t instead of v-t, because v-w-t cannot be worse, but it can actually be faster, if a small fraction of people don't take it (note the cost function on w-t). So everyone ends up on s-v-w-t, which means an average time of 2 hours. Oops.

If you think back to the real world, that's why building a new highway doesn't solve all our traffic nightmares, and can, in some cases, make the problem worse. People using sides roads or taking the train to work converge on the new highway, and you're back to square one.

Braess' paradox doesn't just occur for networks where the cost of a link goes up as the number of people use it. For networks with non-increasing cost functions (e.g. the cost of a link goes down as the number of people use it goes up), where congestion is a good thing, we can find an analogous situation. Consider the following network, where 1 unit of traffic needs to be routed from s1 to t1, and another 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 pockets builds a new link to shave a little off the s1-t1 route:

Decreasing case - augmented network

The direct s1-t1 route is more attractive than the 3 hour hike via u and v, so everyone who wants to go from s1 to t1 takes that route instead. Because the u-v link isn't shared anymore, its cost goes up quite a bit, and the total cost now becomes 6.5. Sharing is caring.

Tags: , , , ,

  1. Dan’s avatar

    So this is why new highways are always immediately congested.

    Reply

Reply

Your email address will not be published. Required fields are marked *