読者です 読者をやめる 読者になる 読者になる

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 をクロールして地図ネットワークを作成……!?