11 ms·
Braess’ paradox
- cousin_it 10y agoYeah. 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.
- wowSelfDriving 10y agoYeah, great more propaganda. More self driving car talking points. Wonderful.
- teej 10y agoOk, I'll bite. What's so bad about self-driving cars?
- jayajay 10y agoI'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.
- gizmo686 10y agoThe 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_hacked#t-334737 https://www.ted.com/talks/avi_rubin_all_your_devices_can_be_...
- pavel_lishin 10y ago> 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.)
- chansecodina 10y agoAny 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.
- deleted 10y ago[deleted]
- jayajay 10y agoYou are right, I only mentioned bikes so as to draw a more stark contrast between the two extremes.
- em3rgent0rdr 10y agothis wiki article seems to get posted every few months... https://hn.algolia.com/?query=%09Braess’%20paradox&type=story https://hn.algolia.com/?query=%09Braess’%20paradox&type=stor...
- tunesmith 10y agoAnother 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.
- peller 10y agoI 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.
- mikeash 10y agoThere 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.
- peller 10y agoAgreed. 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.
- xyzzy4 10y agoHN might as well pin this article to the top since it gets reposted so much.
- jayajay 10y agoI benefited from this repost.
- laszlokorte 10y agoThe 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.
- mulmen 10y agoI don't speak German, can you provide a link to the paragraph and/or a translation?
- diziet 10y agohttps://de.wikipedia.org/wiki/Braess-Paradoxon#Mechanisches_Analogon https://de.wikipedia.org/wiki/Braess-Paradoxon#Mechanisches_...
- schoen 10y agoThe 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.
- austinjp 10y agoYou may appreciate this video: https://www.youtube.com/watch?v=nMrYlspifuo https://www.youtube.com/watch?v=nMrYlspifuo
- zardeh 10y agoSomeone 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?
- argonaut 10y agoHaving studied both topics (just coursework), I don't think so.
- zardeh 10y agoThat'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.
- cr0sh 10y agoI 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.
- brianchu 10y agoI'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 https://arxiv.org/pdf/1506.02142v6.pdf, which proves it's equivalent to approximating gaussian processes (this is beyond me).
- WhitneyLand 10y ago>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?
- argonaut 10y agoThis applies even with perfect information, as long as drivers are completely selfish.
- lvh 10y agoHow'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.)
- saosebastiao 10y agoExactly. In other words, in order to globally optimize for throughput, you would have to deoptimize some people's routes.
- snrplfth 10y agoNormally you would do this through prices, but most roads don't work that way.
- trvlngsalesmn 10y agoHwy 635 in Dallas has a variable-toll expressway lower level.
- Pfhreak 10y agoIs 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.
- ufo 10y agoIT doesn't have to https://en.wikipedia.org/wiki/Braess%27_paradox#Example https://en.wikipedia.org/wiki/Braess%27_paradox#Example
- cs702 10y agoThe 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!
- whack 10y agoI 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.
- alimw 10y agoThis is the so-called Pigovian Tax. Also named for Arthur Pigou is a road traffic thought experiment much like Braess's ("Pigou's example").
- Chris2048 10y agoSo 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?
- whack 10y agoNo, 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.
- Chris2048 10y agoHow does one car impact another? Wouldn't the drivers gravitate to the least congested/long road, and hence distribute across capacity?
- trvlngsalesmn 10y agoI 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?
- obstinate 10y agoThey do this on some exits. Speak with your county commissioners, the police, etc. https://www.youtube.com/watch?v=9Ia4pzskae8&list=PLEEC4A6D0A6CD0C5B&index=9 https://www.youtube.com/watch?v=9Ia4pzskae8&list=PLEEC4A6D0A...
- beefman 10y agoSee also, the Price of Anarchy [1] and How Bad is Selfish Routing [2]. 1 https://en.wikipedia.org/wiki/Price_of_anarchy https://en.wikipedia.org/wiki/Price_of_anarchy 2 http://theory.stanford.edu/~tim/papers/routing.pdf http://theory.stanford.edu/~tim/papers/routing.pdf
- dksidana 10y agoIt will be interesting to see a case where all drivers use real-time traffic updates from services like Google Maps
- TempleOS 10y agoGod is perfectly just. A CIA dentist ruined a tooth. God said it counted as a sacrifice. God says... Tanner's oscillated vow's treachery's pearliest aroma's setter herbivore's squishy smudgy pressmen Patton cockpits ham smidgen's cesarian's unruliness's alphas terrace yet hovel visualization's vivacious ligatured Montpelier's tort's sociopath aspire spotlighting excisions Masada's nippy
- drewhk 10y agoHm, can't this be circumvented by pushing towards a correlated equilibrium (https://en.wikipedia.org/wiki/Correlated_equilibrium https://en.wikipedia.org/wiki/Correlated_equilibrium) instead of a Nash equilibrium?
- runeks 10y ago"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." - Antoine de Saint-Exupery
- dx034 10y agoThat'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.
- basicplus2 10y agoThis reminds me of the example of the placement of a barrier at an exit to reduce the number of interactions to improve pedestrian flow http://www.gkstill.com/CV/PhD/Chapter3.html http://www.gkstill.com/CV/PhD/Chapter3.html 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
- cr0sh 10y agoDang you hit it before me - I was wondering the same thing, and posted about it to another comment here...