Hacker News new | past | comments | ask | show | jobs | submit login
Braess' paradox: adding a new road to a city can slow down traffic (wikipedia.org)
98 points by Thorondor on Oct 16, 2015 | hide | past | favorite | 61 comments



Taken to the extreme, if you made such a dense network of roads that it was effectively just one giant paved surface, then I think it's obvious that it'd be inefficient since everyone is barging through trying to go in their own straight line and getting in each other's way. In that case, adding barriers and one-way lanes would intuitively speed up people's journeys. So perhaps Braess's paradox is only unintuitive for simple cases that are very close to our existing road networks.


But that's not all there is to it. It really is a network phenomenon. Otherwise you wouldn't expect it to also appear in power networks: http://iopscience.iop.org/article/10.1088/1367-2630/14/8/083...


A standard physics question is to calculate the electrical flow between two points on an infinite square grid of resistors.

Not surprisingly, the flow isn't large. The electricity takes many path through the circuit.

Here, too, having fewer paths would result in large flow.


But the equivalent resistance always decreases as the grid of resistors increase. I don't see how having "fewer paths would result in a large flow".

See: http://physics.stackexchange.com/questions/2072/on-this-infi...


Wow, it seems like you can do it with a simple DC circuit too! That paper's a bit complicated but if you just make the road network with constant voltage drop diodes and resistors instead of constant travel time roads and time-proportional-to-traffic roads respectively, it looks like adding a link actually increases the voltage drop across the overall circuit for a constant current!!


It's a generally helpful technique to try and push a problem to both limits alongside some variable; it often reveals new solutions or insights.


Or at least it gives you easy special cases you can sanity check your general solutions against.


I once saw a particularly interesting physical manifestation of this paradox (performed I believe by Chris Bishop), where a weight was suspended from two partially elastic ropes, both attached to the ceiling. These two suspending ropes were connected in the middle by another rope. The weight was analogous to the destination, and the ropes were the roads, with the total duration of the route being analogous to the distance of the weight from the ceiling. When we removed the central road (by cutting the connecting rope), the weight paradoxically went up instead of down.

I wish I had a video of this demonstration, it really hammered in the point (for me) that this is a real phenomenon and not just mathematical trickery or electrical weirdness.


This is close enough, it's not quite as clear as the demonstration I saw but it shows the same effect: https://www.youtube.com/watch?v=xiOEYNGV5P8


I found https://www.youtube.com/watch?v=nMrYlspifuo linked from your video. It has much more explanation.


That's really interesting. I presumed that Braess' paradox was as a result of the overhead of competition but this demonstration doesn't seem to model that.

I presume in the demonstration you're describing the central rope was not partially elasticated as the other two? (as demonstrated in the two videos)

Does Braess' paradox apply if the central rope is elasticated? Does it apply for a parallel route also or just for a route that joins to existing series routes?

I think if it's just a joining link then the effect could be modelled in signal theory as the result of partial feedback. Still no idea how the experiment works though :-)


I think the original mechanical analogy is due to Cohen and Horowitz: http://www.nature.com/nature/journal/v352/n6337/abs/352699a0...

In this setup, cutting the link essentially converts the two springs from being in series to parallel: http://ibin.co/2JEsCKEYRisb

If the central string was elastic, this would cause the weight to initially hang lower, but have no effect on the position reached after it is cut (assuming that it does not stretch so much that the other strings stop being slack). The effect would thus appear larger.


The paradox does not take into account the rigidity of a roadway user's route. If your current route to work takes x minutes amount of time to drive and a new roadway is about to be opened that will reduce the drive time by ten minutes (x-10). News announces the new route, ribbons are cut, and signage is put in place announcing the new roadway.

* The user is aware of the new roadway and utilizes the roadway.

* The user knows that the old route was 10 minutes more and was the current ideal.

* Other users utilize the route under the same 10 minute saving condition, driving up the amount of traffic over time, even when the new route ends up adding travel time to the original time.

* Users do not consider going back to the old route, even though it may be better now as the system builders had declared this route to be the best. There is also an internal feeling that if the new route was like this, what will the old route look like.

* When talking to people who drive, once a known route has been established, it takes a lot to get them to change. That is why accepting Waze provides such a great opportunity for balancing traffic and utilizing roadway capacity.


From my (mathematician's) perspective, when the solution to the optimal transportation problem corresponds to a Nash equilibrium, this is called a Cournot-Nash equilibrium. This does not happen generically.

In other words, it is very unlikely to simultaneously minimize both the expected commute cost for the group and for each individual.

However, in the continuous case, you can fix this using taxes, tolls or incentives (in theory - in practice I don't know. )

Blanchet and Carlier have some nice mathematical articles including

https://www.ceremade.dauphine.fr/~carlier/blanchetcarlierfin...


Are you saying that an equilibrium is Cournot-Nash if it does manage to "simultaneously minimize both the expected commute cost for the group and for each individual"? Not sure that's right...


In the literature I've encountered a Cournot-Nash Equilibrium is a solution to an optimal transportation problem. There could be some discrepancies in definitions as to the parameters one is allowed to vary. This is also assumed to be a global minimum - not just local.


In the paper you reference, an 'optimal transport' problem does indeed arise in connection with Cournot-Nash equilibrium. However the naming is a coincidence, it is unrelated to the problem of finding the most efficient routing of traffic. Think rather 'earth-moving'. https://en.wikipedia.org/wiki/Earth_mover%27s_distance

The paper does however note the traffic problem in passing: "the variational approach we develop presents some similarities with the variational approach to Wardrop equilibria on congested networks and in both cases equilibria are socially inefficient."


The 'optimal transportation' is misleading in this case : People are not interchangeable, so you are actually trying to find a map between the space of { people who have to go places } and {routes they might take } . Once everybody has chosen a route, there is a measure on the space of routes. The cost of each route to each person depends on the measure on the route space. Once you have this pairing of measures, you can ask if it's optimal or not.


I think we agree :) Thanks for the reference btw, I'm supposed to be writing my thesis on such things.


Networked traffic routing apps like Waze ought to nullify the Braess' paradox; if everyone used Waze, new roads would always have a positive marginal impact.


The situation is complicated by induced demand [0], the phenomenon in which providing more roadway capacity tends to raise demand for it by reducing the cost of travel.

What typically happens when a new roadway opens or a congested route is widened is that travel times first fall, as expected; but soon the reduced travel times attract drivers who previously had used other routes, or who had commuted at off-peak times, or who had used public transit. Thus the improved roadway ends up with significantly more traffic than the old roadway, and the price (in travel time) of the increased capacity is bid back up near its previous level.

Added roadway capacity can lead to a welfare improvements, but it mostly comes in the form of fewer people shifting their schedules to beat rush-hour traffic or deigning to take public transit, and not through reductions in travel times. In actual fact, as we've seen throughout the era of American suburbanization, vast new roadways have probably substantially increased average travel times [1] by markedly changing patterns of land use (i.e., by giving rise to the modern low-density, car-dependent suburb), albeit while also engendering some welfare gains (e.g., increased suburban living space).

If you want to prevent induced demand from gobbling up expected improvements in travel times when you build new roads, you pretty much either have to (a) decrease demand by deliberately increasing the financial cost of travel (e.g., through tolls or congestion charges), or (b) over-build roadway capacity in the extreme, to the extent that just about everyone in the region can fit on the roads at once, alone in his or her own car (as is the situation in cities like mine).

0. https://en.m.wikipedia.org/wiki/Induced_demand

1. I mean in comparison to a counterfactual alternative history in which the urban-suburban commuter freeway systems typical of American cities went unbuilt. Commute times in European metropolises, which mostly lack the extensive commuter roadways and concomitant suburban sprawl of their American counterparts, are broadly lower than in American metros of similar sizes, for example.


That is true if the new road does is indeed the source of the new traffic. But it all falls apart if that future increase in traffic will be coming regardless of whether the road is built. that's where the paradox really breaks down.

You cannot solve the problem of an external source of new traffic, be it a new stadium at the edge of town or new machine added to the edge of a network, by not building in any new capacity. Well, you could if you simply chose not to serve that new node. Not running any new roads to a new airport is a great way to get that airport to close, just as not serving that new customer on your network is a great way to make that customer go elsewhere.

The other flipside to the pardox is that it really is applicable to any network. Sometimes the best way to improve the efficiency of mass transit is to cull bus/train routes. But try selling that in a modern city.


To put the original paradox another way, though: if you run a road out of town far enough, somebody will build an airport at the end. The airport is indeed an "external source of new traffic", but it was built because the traffic system had enough unused capacity to absorb the projected load.


I;m not convinced that the people building stadiums and airports go around looking for cities with extra traffic capacity. They are responding to forces well outside local traffic issues. The fact that they will generate increased traffic is a factor during planning and construction, but it is certainly not in any way a driving force behind the decision to build.


You kind of imply that building a new road is useless if travel time stays the same. But increased traffic bandwidth IS improvement, even if individual drivers don't feel it.

Also same thing applies to this paradox. Even if individual travel time is reduced for some, I doubt that overall traffic throughput is reduced. At worst case scenario it should stay the same.


That only appears to be the best option if you specify all trips to be made via private automobile. Road bandwidth is more efficient on bike or bus, but people will default to a car if the road is well suited and there is parking at the destination. It's not that the road is useless, it's that it perpetuates demand for driving and so can't solve congestion except by brute force saturation.

It's one of the big shifts in planning thought to get away from a simple engineering problem of moving more cars faster and try to integrate different modes and give land use a more careful impact assessment.


> Road bandwidth is more efficient on bike or bus

Not necessarily for the people on the bus. Efficiency in terms of capacity represents one of several possible optimization criteria; the distribution of transit times to various destinations represents another.


That assumes that people will change from a car to other options. At least where I live, that will not happen. They tried to do exactly what you said - instead of increasing size of roads, they broadened roads but made the new lanes only for public transport. The expected happened - everyone who used cars before, were using them after, and only thing that improved is people who ride bus reach destination a little faster. Same would be with bikes and other things - nothing will have impact, car throughput is basically only thing that matters in traffic congestion reduction.


If you expand capacity in one mode but hold the other ones steady, you're still running into Braess' paradox. It doesn't matter that there is more bus capacity if people were tolerating the existing car congestion before. People will not switch until the roads are jam-packed.

The paradox still applies when we consider the Tokyo rail network. There's lots of rail in Tokyo - it transports most of the commuters. Major lines are quite literally packed during rush hour. [0] Adding more rail will make the system even more popular, so the problem won't get better.

OTOH consider congestion charges. When interviewed[1], individuals do not believe they were significantly affected by the introduction of a charge, even though overall traffic levels go down substantially, by one fifth in the example used of Stockholm.

What we are changing when we change capacities is not speed or comfort, but a preference for what kind of congestion we get and how cheaply it will be filled. If our only goal is congestion reduction we should not be looking at the roads at all.

The San Francisco area has plenty of car traffic, but more recently, within the past decade or so, the public transit has become extremely popular. This is not because the transit has gotten substantially better by quality or speed metrics. It is because the population is making more trips and longer ones, and the public transit systems were the last resort for capacity. Demand for new trips is in turn caused by available housing being located distantly from workplaces. If newcomers were able to live where they worked, congestion would drop significantly.

[0] https://www.youtube.com/watch?v=pRBLnth4oSg [1] https://www.youtube.com/watch?v=wC33HAq--x8


My point was that in most places none of these things you mentioned actually helps reduce congestion except brute force capacity increase by building more or wider roads somewhere.

Sure, there always are some cases where fiddling with lanes, transport types and other relatively cheap means of changes makes traffic better, but in the end simply more roads are needed.


Your confusing a local optima with a global one. If you added enough rail capacity eventually you run out of people in the country to use up more capacity. Roads are something of a special case in that they scale terribly, but you really could build a rail network in a city that could handle 7 billion people per hour if cost was not an issue.


In the setup described here, all the roads have infinite throughput. There's no level of traffic at which they stop working altogether; you can push as many cars per unit time through either network, and that many cars per unit time will come out the other side. But, as with many kinds of system, you may pay a heavy price in latency if you insist on getting lots of bandwidth.

But there's something right in what you say. When you add the extra road you make travel time worse at low usage and better at high usage.

Suppose your network has an upper path with cost for x cars 1 on the left and x on the right, and a lower path with cost x on the left and 1 on the right, and the optional vertical road is free at any capacity. Then, if I've done the calculations right, average travel time with t cars is 1+t/2 without the extra road, and min(2,2t) with. So at t=1, which is the case usually used to demonstrate the paradox, the extra road increases the travel time from 1.5 to 2, but beyond that point increased traffic is free for the enlarged network but not for the original one. So, e.g., if t=10 then the extra road makes things 3x faster. The crossover point is at t=2, where both networks have average travel time 2.

So the extra road is a win if you expect t >= 2, and a loss if you expect t <= 2.

(If we measure throughput as "max traffic with such-and-such a limit to average travel time", then if the limit is <= 2 then both have finite throughput and the one with the extra road is worse, but if the limit is >= 2 then the network with the extra road has infinite bandwidth.)


The entire problem is that people look at the effect (Full roadways) and fail to see the related causes (the rent is too ed high (because we aren't building enough valid working and living (not just homes) spaces in the city)).


That only works if the app is willing to give individuals sub-optimal paths in order to optimize total performance. If that is the case, then an individual has incentive to not listen to the app.


Unfortunately, Waze has at least two incentives not to provide socially optimal paths. First, individuals would have an incentive to find individually-optimal paths by using a different app that provides them. Second, it seems likely that more people turn Waze on when traffic is bad, so social suboptimality might actually be good for Waze.

On the other hand, with socially optimal traffic patterns there would be induced demand and more drivers would come on the roads and potentially use Waze.

It's actually difficult to know what would make Waze better off, providing socially optimal routes or individually optimal routes.

Waze might also behave like many companies and ask for subsidies from local governments for turning on the social optimization, and the local governments are ill-equiped to know how much to pay.


If driverless cars always for go for the most favorable route for them, they might increase traffic a lot. Fortunately, it is also probably easier to force computers than people to follow socially optimal routes.


Especially if there's a way to redistribute the social gains.


Does Waze optimize for the socially optimal distribution over the whole network, or does it optimize for each individual traveller?

If it optimizes for each individual traveller, then Braess' paradox still applies even with Waze because all the travelers in Braess' paradox make the individually optimal choice.

If it optimizes for the socially optimal distribution, then it does solve the problem. But this sounds like an optimization problem that would be really hard to formulate and solve in practice, so I'd be surprised if Waze (or any other networked traffic app) did it right now. Maybe eventually?


I wonder how a route suggesting app, that accounts for traffic, avoids the El Farol Bar (lets call it EFB) problem. EFB essentially is people in the town of El Farol want to have a good time, and they the option of staying at home or going to the one bar the town has. If a lot of them end up at the bar, people would have had a better time staying at home. And if a lot of them stay at home, the bars are not crowded and they'd have had a better time in the bar.

The catch is no one knows in advance who is going to go the bar. It can be shown that no pure strategy can work for EFB.


"Nobody uses pure strategies anymore. They're too popular" - Yogi Berra


If you believe that, then you don't understand Braess' paradox.


In London they are proposing to build new tunnels under the Thames which will could massively increase traffic in east London.

Whether traffic moves faster or slower pollution is bound to increase.


That reminds me another notion from The Mythical Man-Month; Brooks's law: Adding manpower to a late software project makes it later.


My understanding of this is that you have a highway and a road (with a low speed limit). The highway gets congested if many people use it so they’ll all move slower. If everyone takes the highway, it’ll still be faster than the road, so everyone chooses to take the highway. On the other hand, if everyone spends half their time on the highway and the other half on the road, all of them will be able to travel faster (But there is no incentive to do so).

At Nash equilibrium, the highway is over-utilised while the road is under-utilised. So stripped to the core, this is an example of tragedy of the commons where if every single individual works for their sole interest, they will all lose out and yet nobody has an incentive to make a change.


Brian Hayes wrote a nice article about this a few months ago in American Scientist [1] and also wrote a little JS demo to tinker with linked from here [2].

1. http://www.americanscientist.org/libraries/documents/2015617...

2. http://bit-player.org/2015/traffic-jams-in-javascript


Anyone who wants to try this might consider playing or watching a video of the Cities: Skylines game. It's said to be a pretty good "traffic planner" simulation.


That game has really taught me how poorly most drivers algorithms probably are. A lot of that is probably a lack of visibility about the actual conditions ahead of the drivers.

I wonder how that would change if the actual cost (in time to that driver) of each potential route were known; even if that is in current time costs? (IE how would they operate if they had real time traffic enabled GPS?)

Also, their refusal to bypass turning sims is inane.


Ah, I love this stuff. Tim Roughgarten's work on selfish routing was my bible through an undergrad research project, it's succinct and packed with excellent proofs. https://mitpress.mit.edu/books/selfish-routing-and-price-ana...


I remember reading a piece by WIRED that discussed this phenomenon in Southern California: http://www.wired.com/2014/06/wuwt-traffic-induced-demand/ ("Building Bigger Roads Actually Makes Traffic Worse")


When the 880 connector between 980 and the Bay Bridge was rebuilt in 1998, traffic engineers were predicting that it would increase traffic congestion and lengthen almost all trips that used it or passed near it. And it did indeed slightly worsen the traffic conditions in the area compared to the interregnum after it fell down in the Loma Prieta quake in 1989. Traffic is still worse that it would be if CDOT just closed it and turned it into an urban garden or walking path with views or something.

That's not why it took so long to rebuild. The nine year process was the result of the usual corruption, insider jockeying, incompetence, bureaucracy, and lack of urgency from Bay Area government. The objections of CDOT and local residents that ardently opposed the freeway in their neighborhood were ignored and steamrollered as usual. Of course, the local officials, contractors, and CDOT shared and enjoyed the lucre from the $1,200,000,000 we all paid for the three mile connector.

Meanwhile the 1994 earthquake in LA triggered a special exception to the usual legal process where Gov Wilson could take personal responsibility for selecting a design, a contractor, a price, a schedule, and contract terms for rebuilding several segments of LA highway. They were all delivered on time and well under expected budget. Some were rebuilt in a couple months. No one had time to figure out if those could be beneficially abandoned.

And today Oakland and CDOT still cannot make the simple decision to admit error and close the 880 connector.


What fraction of the time does adding a new road slow down traffic? Or, equivalently, what fraction of the time does removing a road speed up traffic? If this fraction is high we should be experimenting with closing roads: that's a very cheap way to improve infrastructure.


I learnt this as a part of a course I was doing on social networks. This was under the game theory module. Pretty interesting stuff.


Why does everything have to have a new 'paradox' when perfectly good physics exists already:

https://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws

It is not as if cars are equipped with some superior intelligence when compared to electrons in a circuit, the behaviour is identical and the normal laws of physics apply.


I think you might have misunderstood. This example is notable precisely because cars don't behave like electrons in a circuit.

Or do you have an example of a situation in which Kirchhoff's laws predict that adding a wire to a circuit decreases the total current?


The weaker question "do you have an example of a situation in which adding a wire to a circuit decreases the total current?" is easy to answer positively. Adding a wire sometimes decreases total current.


Like I said, an example would be helpful, because I don't see how that's possible. (Unless we're talking about nonlinear devices like transistors, which doesn't seem like what the parent poster was talking about.)


I was thinking about electric circuits in general, so very much including transistors. I mean, we were also talking about street networks in general, or were we excluding intersections?

The simple example I was thinking about is a "digital potentiometer". Think about the audio output of your motherboard, which's amplification you can control digitally.

Kirkhoff's circuit laws are extremely simplifying.

An interesting exercise would be to prove the statement we were talking about in the fictional world of "Kirkhoff circuits".


Are there any examples of this happening when a new internet link is added?


I don't think it really applies to a packet switched network: > adding extra capacity to a network when the moving entities selfishly choose their route can in some cases reduce overall performance.

Network frames don't "selfishly choose their route" and are entirely at the whims of the Routers they pass through.

Because of complex routing and suboptimal peering/routing, a "shortcut" could be added that makes it quicker to get from A to X1 but makes it take much longer to get from A to X2 Additional routes (as in "directing packets the right way", not physical routes) would fix this and get the best of both worlds.


Why is paradox? Seem obvious to me. If person can explain, thank you.


Check out https://www.youtube.com/watch?v=nMrYlspifuo Does it still seem obvious in the physical context?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: