Price of anarchy in Boston road network

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.