Hacker News new | past | comments | ask | show | jobs | submit login
Braess’ paradox (wikipedia.org)
136 points by dedalus on Jan 8, 2017 | hide | past | favorite | 91 comments

Another example of the Nash equilibrium being worse than the group optimum is some examples of Tragedy of the Commons, things like overfishing. It's possible to create a model that shows that a more regulated environment leads to more fish per individual than the Nash equilibrium.

I don't think it's appreciated enough that some forms of regulation actually do make things better for everyone, and that acting only in one's own self-interest can lead to results that are provably worse for your own self-interest.

"I don't think it's appreciated enough that some forms of regulation actually do make things better for everyone, and that acting only in one's own self-interest can lead to results that are provably worse for your own self-interest."

As someone who is libertarian-ish, I find that a funny thing to say which doesn't jive with reality. Western countries usually have huge governments with huge amounts of regulation, and the default assumption of almost everyone around me seems to be that regulation is the way to deal with almost anything we don't like.

So saying that it's not appreciated that some regulation makes things better for everyone sounds to me like saying "it's not appreciated enough that clothes make us warm".

(Unless, of course, you're referring only to specific circles, e.g. libertarian economists).

This contributor to the talk page will appreciate no such thing:

this whole article is poorly veiled propaganda by the current communist administration to justify government ownership of roads. After all, who but the government could remove a link to benefit "everyone"? By generating this absurd fake propaganda, it hopes to ply public sympathy toward state involvement and ownership. Naturally the actual proposed "facts" are totally rubbish: it is obvious that you could never decrease traffic congestion in an area by removing already congested roads. The article is an obvious hoax from the first sentence: "Braess's paradox, credited to the mathematician Dietrich Braess" redlinks. I've added a deletion tag. (talk) 01:27, 31 March 2010 (UTC)

I am always amazed that people with such thought processes are not locked in padded cells, or at least taken to some provincial farmhouse to rest for a while before returning to society.

The Wikipedia talk pages are a more effective prison than any mere set of walls.

> the default assumption of almost everyone around me seems to be that regulation is the way to deal with almost anything we don't like.

Well, in my experience, people are very polarized about this: either they want to go to the gulch, or they want a very protective state that deals with everything. Both population seems comparable, number-wise; YMMV.

I think this is an illusion. The way upvoting/clickbait works primarily rewards extreme opinions, so the moderates are quitting the discussion.

True, but I was including real life discussions, with friends, colleagues etc.

Then you have a very skewed sample set. Empirically, libertarians rate in the single-digit percentages of the population. People who conform to the libertarian stereotypes probably even less so; I'm "libertarian" because I would tend to think we're overregulated right now rather than underregulated, but it doesn't mean that I want to indiscriminately slice everything away, nor that I am permanently predisposed to slicing everything away no matter how much we might somehow slice. I'd get off that ride sooner than a lot of other "libertarians".

Personally I can't help but reading anyone trying to blame underregulation on libertarians as effectively an admission that they have run out of excuses. There just aren't enough libertarians to have that much of an effect on anything. Even "deregulation" is not generally the libertarians running wild, it's non-libertarians trying to implement a "free market", for some definition of said, but they're generally not libertarians and the same people will happily vote for crony capitalism or a ton of other sorts of regulations.

You're refering to true libertarians, but many people like the idea of being one, or at least tell others that they are, even though you're correct that they're often just after some "free market" which is not free at all in practice, or just tax cuts.

When was the last time you heard someone go "you know, those regulations on the plimping of stuffthings really make the world better", versus the last time you heard "damn the government for their ridiculous regulations, costing us money for no good".

Being a public servant is a thankless job.

Net neutrality seems almost universally praised. The FDA is quite popular too.

some forms of regulation actually do make things better for everyone

Best example is that property rights are such a form of regulation. When it comes to fisheries, wildlife, open public lands, air pollution, and intellectual 'property,' the optimal regulation gets much more complicated.

It is one kind of regulation, but it is usually not enough regulation and sometimes also the wrong regulation (think about public roads, the right to cross the high seas freely, ...)

Tragedy of the commons is fundamentally different.

This paradox would be like if adding more fish to a pond, caused there to be less fish in the pond.

I can translate this paradox into fish for you, if you want :).

Suppose you have two ponds, one with a large population of low value fish, and one with a limited number of high value fish. The value of fish caught from the big pond is 1/2, and the value of the small pond is 40/n, where n is the number of fisherman using the pond.

Consider 50 fisherman living by both ponds, with a bridge connecting the two. The only equilibrium is 80 fisherman fishing the small pond and 20 fishing the big pond (otherwise at least 1 fisherman's catch rises by moving).

Suppose the government burns down the bridge. Now 50 fisherman fish at each pond, and total catch rises from 50 to 65.

In general, when you have 2 choices, one with higher quality and more sensitivity to increased use, then you get dynamics similar to this paradox. Whether government has the ability and incentive to intervene effectively is a separate question.

> a bridge connecting

You mean a road from one pond to the other one?


Yeah sure. Wrote the comment on the bus very quickly. Possible to alter the geography to make it clearer. A road allowing fast travel would be better than a bridge!

Braess' paradox is a little more indirect than that, so an analogy might be: Adding more fish to a pond causes you to catch fewer fish.

And another one (that captures the dynamics of Braess) is "undercharging for fish makes fish harder to obtain" (because it causes existing suppliers and sources to run out sooner).

That's analogous because, in a Braess situation, the new route appears more attractive to drivers individually (just as underpriced fish does), but their usage of said route will disproportionately exhaust the network's capacity.

And in both cases, there's a kind of "tragedy of the commons" dynamic.

One individual catching one more fish from a pond since there is fish in the pond would lead there to be less fish in the pond for the individual over time.

One individual choosing to simply not catch the one more fish (choosing to not drive the additional road) would make no difference because other people would take the fish/road.

Regulating overfishing (removing the road) leads to more fish for every individual over time (leads to better traffic times for everyone).

Your example misses some variable. Here is a better example: regulate fishing in an area where fishing is expensive. Prices go up. More fish flock to areas where fishing is done at an industrial cost-effective scale, more fish is extracted at a lower cost and re-imported, resulting in a permanent increase in extraction.

It's obviously more complicated in the real world as it misses some economic and biospheric mechanics, but it gives a starting thinking exercise.

I don't like the fishing to driving analogy. It's easy to see that regulation can lead to more total fish extracted from the ocean, but I'm having a hard time imagining an instance of this paradox for driving that isn't a consequence of fewer overall divers (or weird effects at intersections).

Exactly, this paradox is basically nonsense. There isn't any situations where this would happen, beyond some made-up math extreme edge cases.

I can see it happening quite easily in the real world if you do something like close a little shortcut that gets back on the main road via a light that only ever changes when it detects a car on the shortcut, but that's an intersection effect, which I don't think the paradox is focusing on.

Apart from the cited situations mentioned in the article, you mean, like:

> In Seoul, South Korea, a speeding up in traffic around the city was seen when a motorway was removed as part of the Cheonggyecheon restoration project.

It also mentions Stuttgart, New York City, Boston, and London.

A few of those examples admit that a large number of vehicles "disappeared", which brings the others into doubt. I'd be much more interested in examples where the total traffic volume was confirmed to remain the same, but traffic conditions still improved.

Wouldn't cars "dissapearing" be a sign that people have decided the quickest route to take involves not taking a car? How does that cast doubt on the data?

Or lift-sharing?

I fully agree with your point, but especially for the specific example you've raised, I think there are some very difficult complications that arise from the (lack of an effective) current global governance model.

For instance, regulations are mostly only effective if they're enforceable. With fishing taking place largely in international waters, and as I understand it, enforcement falling upon the coast-guard-equivalent of whichever country's flag the boat is flying, enforcement would be very difficult.

As far as implementing better regulations, any single nation implementing the good regulations would effectively be putting their own industry at an economic disadvantage (and by extension, their citizens who must pay for the more limited supply) compared to the more lax nations.

We see this with the global climate change debate too; basically every single nation needs to agree at the same time for global progress to be made.

Edit: clarified the first sentence.

There isn't much of a global governance model currently. The United Nations does a bit, but for the most part it's just anarchy between nations. Thus, it's really hard to get them to cooperate when the incentives push them to defect.

Agreed. The other route which seems popular are the "free trade" agreements, but so long as it's corporations writing them, as far as I can tell such deals are moving in the opposite direction of what would be best for the environment and the vast majority of citizens of the world.

> acting only in one's own self-interest can lead to results that are provably worse for your own self-interest.

To be precise: everyone acting in their own self interest can be worse for everyone's self-interest, than everyone not doing that. For an individual, acting in your own self-interest is still good for your self-interest, tautologically.

Fundamentally, the problem is that people can take resources for themselves, in a way that damages the total resource pool. Each fish you take is one that can't make more fish. Every car on a road slows down all the other cars.

>To be precise: everyone acting in their own self interest can be worse for everyone's self-interest, than everyone not doing that. For an individual, acting in your own self-interest is still good for your self-interest, tautologically.

No, the tautology would be "acting in your own self-interest is still acting for your self-interest".

No guarantee that the outcome would be the best for you -- unless you have unlimited information of future possibilities to pick what's best (then it would a tautology again).

For a trivial counter example let's imagine that after your and others actions, a benevolent benefactor gives $10 million dollars to the ones who self-sacrificed the most.

Nature can be such a factor -- only much less benevolent.

Okay, fair enough, but nothing like that is happening here. That situation requires a surprise, it needs something to happen that the actors didn't expect. Maybe because they didn't have perfect information, or because they didn't think hard enough about what they knew, or because the dice came up snake eyes, or whatever.

The Braess paradox and overfishing are problems even when everyone has perfect information.

Yes - there are actions that only make sense collectively, or at least "collectively enough". Which explains why someone may be in favor of tax increases even while taking advantage of deductions, or in favor of campaign finance reform while also taking corporate contributions - "you can't unilaterally disarm".

My point was more to make a distinction against the argument that regulation against a self-interested sort by definition means a worse outcome for that person. Sometimes a regulation leads to a better personal outcome than you'd get through Nash.

I had a hard time understanding how this could be true, until I read the simple math example presented. The problem seems to be one of externalities. Each individual driver is selfishly optimizing for his own travel time, but by choosing to drive in a short-congested route, instead of a longer-sparse route, he's negatively impacting the travel times of everyone else around him.

It's been well proven in economics that externalities, if unregulated, will produce sub-optimal outcomes. That the way to restore optimal outcomes is to impose a tax that's proportional to the negative externality imposed on others. In an ideal high-tech world, this can be achieved by having differential prices that each driver has to pay, to use each road/highway. In a low tech world, narrowing/closing a road is akin to imposing a tax on certain routes, which explains why it can counter-intuitively help us get to a more optimal outcome.

This is the so-called Pigovian Tax. Also named for Arthur Pigou is a road traffic thought experiment much like Braess's ("Pigou's example").

So if I understand it, adding road signs before the new route adding estimated travel times (that take congestion into account) will fix things? The paradox arises from considering only route length, and not congestion?

No, the problem comes from considering only your travel time, and not how your choices impact other drivers. The example given in the wiki demonstrates that even road signs with estimated travel times, will still not fix the above problem.

I wonder if any this applies to that experiment about adding obstacles in front of an exit speeding up exit times by slowing down individuals (especially in the case of an emergency - where sometimes the exits become blocked by the masses all trying to exit the same way - and perhaps even ignoring another route that would lead to a quicker exit)?

However the example have a road that takes 45 minutes regardless of how many drivers go through it, that is not very realistic is it. nowdays we have apps that can tell us in real time how long each path will take according to current traffic, and the time is never constant.

It's actually pretty realistic for very lightly congested roads. At those levels of congestion, the primary bottleneck is the distance and speed-limit. Marginally increased traffic will have minimal impact on travel time.

In contrast, for heavily congested roads, the primary bottleneck is the congestion itself. Hence, marginally increased traffic will have a proportional impact on travel time.

How does one car impact another? Wouldn't the drivers gravitate to the least congested/long road, and hence distribute across capacity?

Presumbly, adding a temporary speed-limit to a road would have a similar effect.

An overloaded shortcut is a trap.

The german wiki article has an paragraph about an analogue effect in mechanics in which adding an additional spring to support a hanging weight can causes the weight to hang lower than before. Which I found quite interesting.

I don't speak German, can you provide a link to the paragraph and/or a translation?

The article describes a weight initially hanging from two strong springs (blue) and two weak springs (yellow). The subsequent addition of the strong red spring in the indicated position will, according to the article's calculations, make the weight hang lower overall. I also find that pretty counterintuitive!

Edit: the explanation given is that the red spring redistributes forces so that more force is applied to the weak springs and less force to the strong springs, causing an overall greater total extension.

You may appreciate this video:


>if each driver is making the optimal self-interested decision as to which route is quickest, a shortcut could be chosen too often for drivers to have the shortest travel times

Does this just mean people are making bad decisions based on incomplete information?

For example, would this still be a problem if everyone was using Google Maps routing which changes routes based on congestion patterns?

This applies even with perfect information, as long as drivers are completely selfish.

How's that work? Is the idea that an individual driver would have to take a penalty in order for everyone else to have better road use?

(Also, is this specified somewhere? It seems like the paradox relies on people making their minds up ahead of time (hence imperfect information) and then not changing their minds halfway.)

The prisoner's dilemma linked to in the article is usually the go-to demo since it only has 4 outcomes.

The nash equilibrium would be for both prisoners to deflect but this is worse than if they both stayed silent.

Both staying silent is not an equilibrium because if one of them decides to be selfish and cheat, he can do better for himself.

Basically the information you need is agreement/cooperation ahead of time to know that neither side will cheat just to do slightly better for himself at the cost of others.

Having every driver take the shortest path for them is not the same thing as minimizing total transit time for all drivers. Similarly with some of the other tragedy-of-the-commons situations, having each fisher maximize the number of fish they catch is not the same thing as maximizing the total number of fish caught by all fishers.

Exactly. In other words, in order to globally optimize for throughput, you would have to deoptimize some people's routes.

In the toy example given in the linked page, with the A->B link in place the global optimum (in terms of total minutes spent travelling) is for 1750 cars to travel Start->A->End for 67.5 minutes of travel, 500 cars to travel Start->A->B->End for 45 minutes of travel and 1750 cars to travel Start->B->End for 67.5 minutes of travel. This gives a total of 258750 minutes spent travelling.

If you imagine that one of the Start->A->End travellers switches to Start->A->B->End, we now have 1749 cars travelling Start->A->End for 67.5 minutes, 501 cars travelling Start->A->B->End for 45.01 minutes and 1750 cars travelling Start->B->End for 67.51 minutes. The car that switched improved its own travel time from 67.5 minutes to 45.01 minutes, but the total time spent travelling increased to 258750.01 minutes (one driver saved themselves 22.49 minutes, but cost 2250 other drivers 0.01 minutes each).

So yes, if you found yourself in that second state, to improve the global optimum you would have to move to the first state by de-optimising the route of one of those 501 Start->A->B->End drivers.

Normally you would do this through prices, but most roads don't work that way.

Hwy 635 in Dallas has a variable-toll expressway lower level.

There are definitely many variable-tolled roads. The trouble is that frequently they are embedded in a system of non-tolled (or, really, not-allowed-to-be-tolled) roads, and that the tolling is not well-focused on congestion. Basically, the Braess "paradox" emerges if you try to make a road network that's optimal for travel patterns over an entire day, without using pricing to ration scarce space.

I learned about this in a course titled Dynamics of Complex Networks and Systems taught by Mark Spong, a robotics control theorist active in dynamical systems research. Ever since learning about Braess' Paradox in that course, I have noticed examples of it in the highways of DFW. The simplest case to spot is where an off-ramp feeds directly to the next on-ramp, creating a "shortcut" for drivers who exit and re-enter the highway.

I've tried to make the case that by closing "key" exits on the highway, we could reduce congestion. But who would be responsible for making that likely unpopular decision?

They do this on some exits. Speak with your county commissioners, the police, etc. https://www.youtube.com/watch?v=9Ia4pzskae8&list=PLEEC4A6D0A...

Yeah. Good road planning in the future should avoid situations where a driver can save 5 minutes by delaying 10 others for 1 minute. Adding new roads can certainly create such situations where they weren't before. You need serious effort to figure it out though, because adding a new road can have lots of other effects as well.


Ok, I'll bite.

What's so bad about self-driving cars?

I'm not OP, and I am not against self-driving cars, but self-driving cars are more unstable to perturbations like malicious software, hacking, and rogue or untested updates.

Edit: E.g. you can't tell a bunch of bicycles to crash into each other, but this is a possible directive if you equip those bicycles with the ability to take instructions and carry out arbitrary motion.

The comparison you should be drawing is to human driven cars; not bikes. In this case, I do not think that self-driving cars actually increase the threat of malicious hacking. As it is, most new cars are already drive-by-wire meaning that a hack of the car gives the attacker full control already. Modern cars are also already heavily computerized, which makes hacks possible (and which has been successfully demonstrated by researchers [0]).

Granted, being self driving will give a hacker options beyond, say, maxing the throttle and disabling brakes and steering.

[0] https://www.ted.com/talks/avi_rubin_all_your_devices_can_be_...

> As it is, most new cars are already drive-by-wire meaning that a hack of the car gives the attacker full control already.

I don't think that's fully the case; you can't tell most modern cars to swerve sharply to the left. You can also still turn off the majority of cars by turning the key. (And of course, for manual cars you can put the transmission into neutral.)

Any cars that have "automatic lane holding" could definitely be told to swerve left. Granted, steer-by-wire systems like that aren't quite pervasive yet. I believe electronically controlled throttle or brakes are more common. Locking individual brakes especially could quickly lead to a very bad situation. Also, putting the car in neutral or removing the key is likely not something that is going to occur to most people in the 1st half second or so that all this is happening.

You are right, I only mentioned bikes so as to draw a more stark contrast between the two extremes.

This reminds me of the example of the placement of a barrier at an exit to reduce the number of interactions to improve pedestrian flow


Scroll down to 3.5.3 Flow through a door.

I can't find the original article I read years ago but it showed a large round barrier to be the most effective, and more than one barrier for larger numbers of people

Dang you hit it before me - I was wondering the same thing, and posted about it to another comment here...

That's where variable toll expressways are a great idea. If you add a faster way and equip it with variable tolls, the paradox shouldn't appear. The new way will not be congested (if the toll has no upper limit) and drivers taking the traditional way will experience less congestion.

The Braess paradox applies to all networks, including the Internet, the financial system, FaceBook, etc.

It seems crazy, but interconnecting more nodes to improve efficiency (as measured by travel time, costs, etc.) can paradoxically make the whole network less efficient!

this wiki article seems to get posted every few months... https://hn.algolia.com/?query=%09Braess’%20paradox&type=stor...

See also, the Price of Anarchy [1] and How Bad is Selfish Routing [2].

1 https://en.wikipedia.org/wiki/Price_of_anarchy

2 http://theory.stanford.edu/~tim/papers/routing.pdf

Hm, can't this be circumvented by pushing towards a correlated equilibrium (https://en.wikipedia.org/wiki/Correlated_equilibrium) instead of a Nash equilibrium?

Is this a function of turbulence? When I think about 'perfect' traffic, I think about a pipe with water flowing through it without eddies. Branch and merge a pipe along its length and you'd introduce all sorts of ripples and turbulence.

Someone who is perhaps better versed in machine learning:

Is there some sort of intuition here that would connect this paradox to the effectiveness of dropout in deep neural networks, or am I drawing connections where there aren't any?

Having studied both topics (just coursework), I don't think so.

That's what I assumed, it feels like there should be an intuitive connection (both are kind of situations where a local optima is avoided by removing the greedily optimal path on a graph structure), but I may be wrong, i dunno.

I'm not sure dropout has anything to do with local optima or removing greedily optimal paths, since it is random.

The original dropout paper's handwavy justification for dropout is that it prevents co-adaptation. It prevents individual units (nodes/neurons) in the network from relying on specific units in the previous layer firing as well. This is a bad thing because it's fragile (if one unit is off). I say handwavy because this is just intuition; there is not really any proof that this is actually what is happening.

Another commonly cited motivation is that dropout is like learning an ensemble of multiple networks.

The only paper I've seen that theoretically analyzes dropout is: https://arxiv.org/pdf/1506.02142v6.pdf, which proves it's equivalent to approximating gaussian processes (this is beyond me).

I think that you could consider the co-adaption as a form of greedy local optima (I think this is a very handwavy explanation, though, and I'm having trouble forming it better, so take with that what you will). Dropout prevents that by not allowing the 'greedily optimal paths' to form, since sometimes they don't exist, so you can't rely on them too much.

Sure, but dropout actually increases training error (makes you less likely to find the globally optimal training error), with (sometimes) a decrease in generalization error (test error). So any connection is very thin.

Oh actually that's a really good point and I think makes the difference clear (there isn't such a train/test divide in the driving example).

Thank you :)

I think you may be on to something, because I was wondering how this might apply to deep learning as well; that is, such networks tend to have many layers and connections to generalize better, but at the expense of being slower (?). I'm not an expert either - but I think there may be something of interest there for study.

It will be interesting to see a case where all drivers use real-time traffic updates from services like Google Maps

HN might as well pin this article to the top since it gets reposted so much.

I benefited from this repost.

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away."

- Antoine de Saint-Exupery

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