Rating: 4.5
Bookmark
Save as PDF
Print
Email
Blog It
Stumble It!
Digg It
Counterintuitive physics may help everyone drive home quicker
Network of the main roads in Boston-Cambridge. Road colors indicate the amount of delay caused in the Nash flow if the road is removed (red indicating the greatest delay, blue indicating no delay). Black dotted roads are those whose removal reduces the travel time, a counterintuitive effect known as Braess’s paradox. Image credit: Hyejin Youn, et al.
A recent study has investigated just how much time is lost due to individuals opting for strategies that maximize their own personal utility rather than the social optimum, which often aren’t the same. Physicists Hyejin Youn and Hawoong Jeong from the Korea Advanced Institute of Science and Technology in Daejeon, Korea, and computer scientist Michael Gastner from the Santa Fe Institute and the University of New Mexico in the US, call this lost time “the price of anarchy” (POA) that society must pay for the lack of individual coordination.
Defined as the ratio of the total travel time of an individual’s optimal route to the total travel time of society’s optimal routes, a high POA means that individuals pursuing the best route for themselves are slowing down the overall traffic flow. When analyzing the traffic in three major cities – Boston, London, and New York City – the researchers found that individuals waste up to 30%, 24%, and 28% of their travel time, respectively, due to choosing a personally optimal route instead of a socially optimal one. The team also calculated the POA for four simulated traffic networks, and found similar results.
“People usually believe that inefficiency can be lessened by providing more information,” the scientists told PhysOrg.com. “On the contrary, our model assumes the full information of traffic and shortest paths in a given traffic condition for every player; that is, all the traffic conditions are known to every player. As GPS and computer-modeling-based devices are developed more and more, we believe the drivers follow [an individually optimal] flow more and more.”
At the core of the price of anarchy are two related concepts: Waldrop’s principle and the Nash equilibrium. Waldrop’s principle, which is fairly obvious, says that humans approach the problem of finding routes in a network from the self-interested perspective of finding the quickest route for themselves.
The second concept, the Nash equilibrium, occurs when an individual cannot choose a better strategy for himself if other individuals keep their strategies unchanged (i.e. an individual can not improve his situation by changing unilaterally). In the traffic situation, say you know which routes the other drivers take, maybe because you’ve tried different routes to find out which is the fastest way to get home from work. After trying different routes, you choose the route that is fastest for yourself. Then you cannot find a faster route as long as the other drivers stick to their same routes (which they do, because they cannot find faster routes, either).
But if many drivers could change their routes simultaneously, then the effect might be a decrease in everyone’s travel time, and society would come closer to the social optimum rather than languishing in the Nash equilibrium. The scientists found that modifying the network structure can sometimes lead to faster overall travel times, since network changes affect everyone. Surprisingly, they found that closing certain roads can sometimes increase efficiency and allow drivers to travel faster.
This counterintuitive result, that adding extra capacity to a network can sometimes reduce its overall efficiency, is called Braess’s paradox. The paradox exists because the Nash equilibrium and the social optimum react in different ways to changes in the network. Specifically, closing a road cannot improve the socially optimal travel time, but it could potentially improve the Nash travel time. This is because individuals seeking their own fastest times may get further away from the social optimum by taking the individually-optimal roads, and closing those roads forces them to take the socially optimal path. In the same way, adding new roads in an attempt to decrease congestion might even create more delay in the Nash equilibrium, but not necessarily decrease congestion in the social optimum strategy.
“Braess’s paradox is interesting and counterintuitive,” the authors explained. “It is still controversial to say that closing a road is the best way to deal with a complex traffic network. Instead, we would rather emphasize that opening a new road without careful consideration can worsen the system contrary to the original intention.”
The scientists noted that studying traffic flow could not only help planners design better road networks, but could also have applications in other areas of science, such as electronics and economics. For example, physicists know that removing wires in an electric circuit can sometimes counterintuitively increase the conductance, similar to how removing roads can sometimes increase traffic flow. Understanding the agents’ behaviors in a network can also be useful for designing networks such as the Internet and peer-to-peer file sharing, as well as optimizing (or minimizing) flow in many different kinds of networks.
“It was surprising and delighting at first: similar principles also emerge in physics without having a direct connection to game theory,” the authors said.
More information: Youn, Hyejin; Gastner, Michael T.; and Jeong, Hawoong. “Price of Anarchy in Transportation Networks: Efficiency and Optimality Control.” Physical Review Letters 101, 128701 (2008).
Copyright 2008 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.
“People usually believe that inefficiency can be lessened by providing more information,” the scientists told PhysOrg.com. “On the contrary, our model assumes the full information of traffic and shortest paths in a given traffic condition for every player; that is, all the traffic conditions are known to every player. As GPS and computer-modeling-based devices are developed more and more, we believe the drivers follow [an individually optimal] flow more and more.”
At the core of the price of anarchy are two related concepts: Waldrop’s principle and the Nash equilibrium. Waldrop’s principle, which is fairly obvious, says that humans approach the problem of finding routes in a network from the self-interested perspective of finding the quickest route for themselves.
The second concept, the Nash equilibrium, occurs when an individual cannot choose a better strategy for himself if other individuals keep their strategies unchanged (i.e. an individual can not improve his situation by changing unilaterally). In the traffic situation, say you know which routes the other drivers take, maybe because you’ve tried different routes to find out which is the fastest way to get home from work. After trying different routes, you choose the route that is fastest for yourself. Then you cannot find a faster route as long as the other drivers stick to their same routes (which they do, because they cannot find faster routes, either).
But if many drivers could change their routes simultaneously, then the effect might be a decrease in everyone’s travel time, and society would come closer to the social optimum rather than languishing in the Nash equilibrium. The scientists found that modifying the network structure can sometimes lead to faster overall travel times, since network changes affect everyone. Surprisingly, they found that closing certain roads can sometimes increase efficiency and allow drivers to travel faster.
This counterintuitive result, that adding extra capacity to a network can sometimes reduce its overall efficiency, is called Braess’s paradox. The paradox exists because the Nash equilibrium and the social optimum react in different ways to changes in the network. Specifically, closing a road cannot improve the socially optimal travel time, but it could potentially improve the Nash travel time. This is because individuals seeking their own fastest times may get further away from the social optimum by taking the individually-optimal roads, and closing those roads forces them to take the socially optimal path. In the same way, adding new roads in an attempt to decrease congestion might even create more delay in the Nash equilibrium, but not necessarily decrease congestion in the social optimum strategy.
The scientists noted that studying traffic flow could not only help planners design better road networks, but could also have applications in other areas of science, such as electronics and economics. For example, physicists know that removing wires in an electric circuit can sometimes counterintuitively increase the conductance, similar to how removing roads can sometimes increase traffic flow. Understanding the agents’ behaviors in a network can also be useful for designing networks such as the Internet and peer-to-peer file sharing, as well as optimizing (or minimizing) flow in many different kinds of networks.
“It was surprising and delighting at first: similar principles also emerge in physics without having a direct connection to game theory,” the authors said.
More information: Youn, Hyejin; Gastner, Michael T.; and Jeong, Hawoong. “Price of Anarchy in Transportation Networks: Efficiency and Optimality Control.” Physical Review Letters 101, 128701 (2008).
Copyright 2008 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.
» Next Article in Physics - Physics: Flexi display technology is now
Video
Editorials
Free Magazines
Free White Papers
Newsletter
Advanced Search
Goto Archive
Suggest a story idea
Send feedback
