Price of Anarchy in Boston Road Network

다국어 초록 (Multilingual Abstract)

We present an optimization problem of network flow in decentralized systems like data transportation,
traffic, population, work flow, etc., where their latency cost functions are congestion-dependent.
The flow pattern can be intentionally regulated by a global rule or may emerge by individual selfish
strategies, depending on the type of system. The latter is known for settling at Nash equilibrium
in a game-theory context, which mostly results in worse than a global optimum in optimization
problems. This gap has been coined as “The price of anarchy”, representing the worst inefficiency
of selfishness. Nevertheless, this price can be lowered, according to Braess’s paradox, by removal
of edges in a given system that intend to reduce a global optimum, regardless of Nash equilibrium.
Accordingly, this paper investigates tendencies of the price of anarchy in a real system, a simplified
Boston road network, and our work suggests a potential application of new methods to optimize
flow in a decentralized system, which is closer to reality in diverse systems.

참고문헌 (Reference)

1 T. Roughgarden, "Selfish Routing and the Price of Anarchy" 2005

2 "Boston area from http://www.MapQuest.com" 2005

3 C. Papadimitriou, "Algorithms, games, and the Internet" (749) : 2001