Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Braess' Paradox and the Price of Anarchy (2019) (cadlag.org)
46 points by luu on Aug 22, 2020 | hide | past | favorite | 12 comments


This misses the seminal result of Roughgarden & Tardos – the price of anarchy in the example is 4/3, but that is also the maximum price in any network where travel time scales linearly with traffic.[1]

[1] https://theory.stanford.edu/~tim/papers/routing.pdf


Up and Atom has a video on Braess' Paradox, among others https://www.youtube.com/watch?v=cALezV_Fwi0


Contrary to the video Cheonggyecheon is not Braess Praradox.

For instance "To address the consequent traffic problem, the Cheonggyecheon Restoration Project Headquarters established traffic flow measures "

"The project contributed to a 15.1% increase in bus ridership and a 3.3% increase in subway ridership"

It was a billion restoration project.

It is a good example how any superficial improvement to traffic where a road is removed is called Braess' Paradox.

Or anytime a road is added or upgraded and it gets worse for anyone, everyone says Braess' Paradox.


Economically, this is a nice illustration of “externalities”. Each individual’s choice negatively effects the outcome of the others.

I wonder if the efficient outcome is restored again by allowing agents to pay each other to take a certain route. For example, agent 1 could get 0.009 from the other 99 agents for agreeing to take the detour. Thereby, the 99 agents save 0.01-0.009=0.001 each and the one agent gains 99*0.009-0.5=0.4 or so.


Isn’t this just because you assume that the agents are acting selfishly? Why not just introduce some local coordination to minimize overall costs?


Because in a traffic scenario people do act selfishly!


Just a scenario I’ve experienced— You’re at the super market in one of those help your self lines. Unless the store is not busy, there is always some traffic.

Sometimes you have one or a few items, and someone in front will let you pass. (Will wait)

Other times someone in front of you has a lot and they apologize for holding up the line. You might think, no problem at all. (Is patient)

And yet others are so harried and stressed they will take every advantage offered. (Always go)

Seems there is enough variation just on personal experience. Supermarket lines could be a good simulation.


Not necessarily, you can have cars communicate locally to compute better strategies, and to provide suggestions to drivers for this strategies.

Same for map apps


In practice, not really! Only when others around them also act selfishly, or there is urgency.


People may not act outwardly selfishly, but people may not realize that their individual action is selfish from a game theory perspective.

Everyone takes the highway because it is the fastest way to travel. However every additional car does slow it down. And this will continue until travel times on the highway either match non-highway travel times or the road literally can't handle more people. But no one thinks that driving the car to the grocery store across town to redeem a coupon is "selfish", because everyone thinks they're in traffic, not that they are traffic.


If you show people two routes, they will choose the faster one. Even if you tell them it would be very helpful to take the slower one.


Braess Praradox is fake news.

Price of Anarchy it a legitimate issue.

See beefmans link for how they tie together better.

I'd like to know if there's anything interesting outside of a lab to the result.




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

Search: