Price of anarchy in Boston road network

Hye Jin Youn*, Hawoong Jeong, Fabian Roth, Matthew Silver, Marie Helen Clutier, Peter Ittzes

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)S217-S221
JournalJournal of the Korean Physical Society
Volume48
Issue numberSUPPL. 2
StatePublished - Feb 1 2006

Keywords

  • Complex network
  • Decentralized system
  • Game theory

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Fingerprint Dive into the research topics of 'Price of anarchy in Boston road network'. Together they form a unique fingerprint.

Cite this