Price of Anarchy on Complex Networks

We present an optimization problem of decentralized transportation networks, where latency depends linearly on congestion of a link. The system shows that a collection of individual optimization of the flow does not always meet the most optimized outcome that is conventionally assumed. We suggest that the Price of Anarchy, the ratio of two optimums, can quantify such discrepancy and accordingly regarded as an index of inefficiency of the system. We also measure the Price of Anarchy of model networks with various underlying structures, and a simplified Boston road network. Our numerical result confirms the existence of the Price of Anarchy in the networks. Finally, we find Braess's paradox is not just a pedagogical example, but inefficiency that can counterintuitively take place in real.