Braess Paradox(rjlipton.wpcomstaging.com)
rjlipton.wpcomstaging.com
Braess Paradox
https://rjlipton.wpcomstaging.com/2022/04/22/a-paradox/
7 comments
It seems to me the problem with adding a new road is that each driver tries to pick the optimal route for themselves but this causes more congestion overall. A bit like Prisoners Dilemma I guess. Every villain to himself. But what if drivers could be routed by a central algorithm by Google assistant for instance?
There's an analogous concept to Nash equilibria in transport engineering known as Wardrop's First Principle. In essence, at equilibrium no user has an incentive to change their behaviour by choosing an alternative route. A 'central routing algorithm' that optimises over the system is in essence Wardrop's Second Principle. https://en.wikipedia.org/wiki/John_Glen_Wardrop
Is there any progress in computing real world applications of this paradox to improve traffic? E.g. are there more streets that can be closed to improve New York traffic?
Even though the results seem unintuitive to most, I assume it should be easy for Google Maps to compute this.
Even though the results seem unintuitive to most, I assume it should be easy for Google Maps to compute this.
Braess Paradox is one of the nicest results in network science and traffic engineering. It's possible to find examples of its application in any situation that can be modelled as a network, from graph neural network architecture (removing connections and inducing sparsity can lead to better generalisation and efficiency under conditions); economics (introducing new trade connections can reduce wellbeing and efficiency under conditions); organisational theory (introducing firewalls between teams can reduce the prevalence of groupthink); and many more.
I’m not sure I understand the spring example shown. It’s definitely underdetermined as one solution is to have the middle string at tension 0 in which case there is no difference between what’s shown and what we get when this string is cut. So there seems to be maybe some extra criteria that need to be asserted for when we get the unexpected behavior… but I wonder if when that’s added in explicitly it wouldn’t seem so unintuitive.
for a great discussion on this, check out a book by tim roughgarden called "the price of anarchy"
Now this friday I had to travel on the south shore to see family. My sister, living further north, also had to come.
Normally, crossing the tunnel on a friday around 5 PM is a perfect recipe for disaster. With the tunnel partially closed, everyone thought it would take hours to cross it. My sister chose to take the long detour further east to take a ferry near Sorel.
I didn't have this option, but I recently heard about the Braess paradox, and although I'm not understanding it very well, I decided to take my chances and take the tunnel.
Well, it took exactly 10 minutes to cross it.