We investigate traffic routing both from the perspective of real world data as well as theory. First, we reveal through data analytics a natural but previously uncaptured regularity of real world routing behavior. Agents only consider, in their strategy sets, paths whose free-flow costs (informally their lengths) are within a small multiplicative (1 + θ) constant of the optimal free-flow cost path connecting their source and destination where θ≥ 0. In the case of Singapore, θ= 1 is a good estimate of agents’ route (pre)selection mechanism. In contrast, in Pigou networks the ratio of the free-flow costs of the routes and thus θ is infinite, so although such worst case networks are mathematically simple they correspond to artificial routing scenarios with little resemblance to real world conditions, opening the possibility of proving much stronger Price of Anarchy guarantees by explicitly studying their dependency on θ. We provide an exhaustive analysis of this question by providing provably tight bounds on PoA(θ) for arbitrary classes of cost functions both in the case of general congestion/routing games as well as in the special case of path-disjoint networks. For example, in the case of the standard Bureau of Public Roads (BPR) cost model, ce(x) = aex4+ be and more generally quartic cost functions, the standard PoA bound for θ= ∞ is 2.1505 [21] and it is tight both for general networks as well as path-disjoint and even parallel-edge networks. In comparison, in the case of θ= 1, the PoA in the case of general networks is only 1.6994, whereas for path-disjoint/parallel-edge networks is even smaller (1.3652), showing that both the route geometries as captured by the parameter θ as well as the network topology have significant effects on PoA (Fig. 1).

Data-Driven Models of Selfish Routing: Why Price of Anarchy Does Depend on Network Topology

Vinci C.
2020-01-01

Abstract

We investigate traffic routing both from the perspective of real world data as well as theory. First, we reveal through data analytics a natural but previously uncaptured regularity of real world routing behavior. Agents only consider, in their strategy sets, paths whose free-flow costs (informally their lengths) are within a small multiplicative (1 + θ) constant of the optimal free-flow cost path connecting their source and destination where θ≥ 0. In the case of Singapore, θ= 1 is a good estimate of agents’ route (pre)selection mechanism. In contrast, in Pigou networks the ratio of the free-flow costs of the routes and thus θ is infinite, so although such worst case networks are mathematically simple they correspond to artificial routing scenarios with little resemblance to real world conditions, opening the possibility of proving much stronger Price of Anarchy guarantees by explicitly studying their dependency on θ. We provide an exhaustive analysis of this question by providing provably tight bounds on PoA(θ) for arbitrary classes of cost functions both in the case of general congestion/routing games as well as in the special case of path-disjoint networks. For example, in the case of the standard Bureau of Public Roads (BPR) cost model, ce(x) = aex4+ be and more generally quartic cost functions, the standard PoA bound for θ= ∞ is 2.1505 [21] and it is tight both for general networks as well as path-disjoint and even parallel-edge networks. In comparison, in the case of θ= 1, the PoA in the case of general networks is only 1.6994, whereas for path-disjoint/parallel-edge networks is even smaller (1.3652), showing that both the route geometries as captured by the parameter θ as well as the network topology have significant effects on PoA (Fig. 1).
2020
978-3-030-64945-6
978-3-030-64946-3
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4785752
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? ND
social impact