Routing Games in the Wild: Efficiency, Equilibration, Regret, and a Price of Anarchy Bound via Long Division

Barnabé Monnot, Francisco Benita, Georgios PiliourasACM Trans. Economics and Comput 2022 · DOI · OpenReview

Abstract

Routing games are amongst the most well studied domains of game theory. How relevant are these pen-and-paper calculations to understanding the reality of everyday traffic routing? We focus on a semantically rich dataset that captures detailed information about the daily behavior of thousands of Singaporean commuters and examine the following basic questions: - Does the traffic stabilize? - Is the system behavior consistent with latency-minimizing agents? - Is the resulting system efficient? In order to capture the efficiency of the traffic network in a way that agrees with our everyday intuition we introduce a new metric, the Free-flow Index (FFI), which reflects the inefficiency resulting from system congestion. Along the way, we provide the first model-free computation of an upper bound to the price of anarchy utilizing only real world measurements of traffic data.
BibTeX
@article{monnot2022routing,
  author = {Barnabé Monnot and Francisco Benita and Georgios Piliouras},
  title = {{Routing Games in the Wild: Efficiency, Equilibration, Regret, and a Price of Anarchy Bound via Long Division}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2022},
  doi = {10.1145/3512747},
}

Loading related content...

Figure