Price of Anarchy in Transportation Networks: Efficiency and Optimality Control (PRL'08)

Price of Anarchy (POA)

• 輸送の効率の指標
• POA = C_UE / C_SO = 1.25
  • C_UE: 全員が自己中に動くときのコスト (nash均衡)
  • C_SO: 協調して中央値を最小化したときのコスト

Braess's paradox

• 不思議現象
  • 辺を削除したほうが効率が上がる
  • 辺を追加したほうが効率が下がる
• 実際のネットワークで（シミュレーションによる）観測に成功
  • Google Maps をクロールして地図ネットワークを作成……！？