7 ms·

Braess' paradox: adding a new road to a city can slow down traffic

98 points by Thorondor 11y ago

matthj 11y ago
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.
- stuaxo 11y ago
  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.
- gizmo686 11y ago
  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.
  - matthj 11y ago
    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.
    - benbou09 11y ago
      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.
      - eru 11y ago
        Especially if there's a way to redistribute the social gains.
  - deleted 11y ago
    [deleted]
- pash 11y ago
  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 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.
  - sandworm101 11y ago
    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.
- reddytowns 11y ago
  If you believe that, then you don't understand Braess' paradox.
- oceanpumpkins 11y ago
  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?
- abhgh 11y ago
  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.
  - micwawa 11y ago
    "Nobody uses pure strategies anymore. They're too popular" - Yogi Berra
biggestbob 11y ago
Why is paradox? Seem obvious to me. If person can explain, thank you.
- eru 11y ago
  Check out https://www.youtube.com/watch?v=nMrYlspifuo https://www.youtube.com/watch?v=nMrYlspifuo Does it still seem obvious in the physical context?
Asbostos 11y ago
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.
- TeMPOraL 11y ago
  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.
  - eru 11y ago
    Or at least it gives you easy special cases you can sanity check your general solutions against.
- Certhas 11y ago
  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/083036/pdf http://iopscience.iop.org/article/10.1088/1367-2630/14/8/083...
  - adekok 11y ago
    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.
    - mikexstudios 11y ago
      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-infinite-grid-of-resistors-whats-the-equivalent-resistance http://physics.stackexchange.com/questions/2072/on-this-infi...
jasonjei 11y ago
I remember reading a piece by WIRED that discussed this phenomenon in Southern California: http://www.wired.com/2014/06/wuwt-traffic-induced-demand/ http://www.wired.com/2014/06/wuwt-traffic-induced-demand/ ("Building Bigger Roads Actually Makes Traffic Worse")
- WildUtah 11y ago
  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.
personjerry 11y ago
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.
- mjevans 11y ago
  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.
rumcajz 11y ago
Are there any examples of this happening when a new internet link is added?
- shitloadofbooks 11y ago
  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.
abhgh 11y ago
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.
Tinyyy 11y ago
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.
Leszek 11y ago
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.
- Leszek 11y ago
  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 https://www.youtube.com/watch?v=xiOEYNGV5P8
  - eru 11y ago
    I found https://www.youtube.com/watch?v=nMrYlspifuo https://www.youtube.com/watch?v=nMrYlspifuo linked from your video. It has much more explanation.
- ricksplat 11y ago
  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 :-)
  - jamessb 11y ago
    I think the original mechanical analogy is due to Cohen and Horowitz: http://www.nature.com/nature/journal/v352/n6337/abs/352699a0.html 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 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.
Theodores 11y ago
Why does everything have to have a new 'paradox' when perfectly good physics exists already: https://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws 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.
- teraflop 11y ago
  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?
  - madez 11y ago
    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.
    - teraflop 11y ago
      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.)
      - madez 11y ago
        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".
ocfnash 11y ago
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/201561716294611219-2015-07CompSciHayesRev.pdf http://www.americanscientist.org/libraries/documents/2015617... 2. http://bit-player.org/2015/traffic-jams-in-javascript http://bit-player.org/2015/traffic-jams-in-javascript
milkers 11y ago
That reminds me another notion from The Mythical Man-Month; Brooks's law: Adding manpower to a late software project makes it later.
Agustus 11y ago
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.
micwawa 11y ago
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/blanchetcarlierfinal.pdf https://www.ceremade.dauphine.fr/~carlier/blanchetcarlierfin...
- alimw 11y ago
  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...
  - micwawa 11y ago
    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.
    - alimw 11y ago
      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 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."
      - 11y ago
cbr 11y ago
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.
somebodyother 11y ago
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-anarchy https://mitpress.mit.edu/books/selfish-routing-and-price-ana...

98 points by Thorondor 11y ago

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.

stuaxo 11y ago
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.
gizmo686 11y ago
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.
- matthj 11y ago
  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.
  - benbou09 11y ago
    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.
    - eru 11y ago
      Especially if there's a way to redistribute the social gains.
- deleted 11y ago
  [deleted]
pash 11y ago
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 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.
- sandworm101 11y ago
  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.
reddytowns 11y ago
If you believe that, then you don't understand Braess' paradox.
oceanpumpkins 11y ago
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?
abhgh 11y ago
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.
- micwawa 11y ago
  "Nobody uses pure strategies anymore. They're too popular" - Yogi Berra

biggestbob 11y ago

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

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

Asbostos 11y ago

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.

TeMPOraL 11y ago
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.
- eru 11y ago
  Or at least it gives you easy special cases you can sanity check your general solutions against.
Certhas 11y ago
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/083036/pdf http://iopscience.iop.org/article/10.1088/1367-2630/14/8/083...
- adekok 11y ago
  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.
  - mikexstudios 11y ago
    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-infinite-grid-of-resistors-whats-the-equivalent-resistance http://physics.stackexchange.com/questions/2072/on-this-infi...

jasonjei 11y ago

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

WildUtah 11y ago
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.

personjerry 11y ago

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.

mjevans 11y ago
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.

rumcajz 11y ago

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

shitloadofbooks 11y ago
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.

abhgh 11y ago

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.

Tinyyy 11y ago

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.

Leszek 11y ago

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.

Leszek 11y ago
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 https://www.youtube.com/watch?v=xiOEYNGV5P8
- eru 11y ago
  I found https://www.youtube.com/watch?v=nMrYlspifuo https://www.youtube.com/watch?v=nMrYlspifuo linked from your video. It has much more explanation.
ricksplat 11y ago
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 :-)
- jamessb 11y ago
  I think the original mechanical analogy is due to Cohen and Horowitz: http://www.nature.com/nature/journal/v352/n6337/abs/352699a0.html 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 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.

Theodores 11y ago

Why does everything have to have a new 'paradox' when perfectly good physics exists already: https://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws 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.

teraflop 11y ago
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?
- madez 11y ago
  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.
  - teraflop 11y ago
    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.)
    - madez 11y ago
      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".

ocfnash 11y ago

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/201561716294611219-2015-07CompSciHayesRev.pdf http://www.americanscientist.org/libraries/documents/2015617... 2. http://bit-player.org/2015/traffic-jams-in-javascript http://bit-player.org/2015/traffic-jams-in-javascript

milkers 11y ago

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

Agustus 11y ago

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.

micwawa 11y ago

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/blanchetcarlierfinal.pdf https://www.ceremade.dauphine.fr/~carlier/blanchetcarlierfin...

alimw 11y ago
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...
- micwawa 11y ago
  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.
  - alimw 11y ago
    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 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."
    - 11y ago

cbr 11y ago

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.

somebodyother 11y ago

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-anarchy https://mitpress.mit.edu/books/selfish-routing-and-price-ana...