Incollection,

The Price of Anarchy in Transportation Networks

, , and .
Abstract Book of the XXIII IUPAP International Conference on Statistical Physics, Genova, Italy, (9-13 July 2007)

Abstract

The price for traveling in a network paid by a single traveler often depends on decisions made by other passengers. In particular, the time spent on each link in the journey (e.g. a road or an airport) is known to increase steeply with the total number of users in real transportation networks. Different policies to assign passengers to routes through the network can affect the distribution of traffic and, hence, the delays experienced by individuals. It is known from game theory that users can cause unnecessarily long travel times to others and sometimes even themselves if allowed to individually seek the quickest paths. However, it remains unknown how inefficient such decisions based on everybody's self-interest are in real networks. Here we show that travel times in Boston's road network can be expected to be up to 30% longer than the ``Social Optimum''. To gain a better understanding under what circumstances users have to pay such a substantial ``price of anarchy'', we analyze different models for traffic networks suggested in the recent literature. A famous result in traffic optimization (known as Braess' paradox) states that removing links can sometimes reduce effective travel times. We find that this phenomenon exists in the Boston network, but improvements are too small to make link deletions a promising way for controling selfish behavior.

Tags

Users

  • @statphys23

Comments and Reviews