2020/09/27 by Francisco Benita, Vittorio Bilò, Benita, Francisco +7
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #FOS: Economics and business #Game Theory and Applications #Game Theory and Voting Systems #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2009.12871
openalex publication_date 2020/09/27 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We investigate traffic routing both from the perspective of theory as well as\nreal world data. First, we introduce a new type of games: \θ-free flow\ngames. Here, commuters only consider, in their strategy sets, paths whose\nfree-flow costs (informally their lengths) are within a small multiplicative\n(1+\θ) constant of the optimal free-flow cost path connecting their\nsource and destination, where \θ\≥0. We provide an exhaustive analysis\nof tight bounds on PoA(\θ) for arbitrary classes of cost functions, both\nin the case of general congestion/routing games as well as in the special case\nof path-disjoint networks. Second, by using a large mobility dataset in\nSingapore, we inspect minute-by-minute decision-making of thousands of\ncommuters, and find that \θ=1 is a good estimate of agents' route\n(pre)selection mechanism. In contrast, in Pigou networks, the ratio of the\nfree-flow costs of the routes, and thus \θ, is \infinite; so,\nalthough such worst case networks are mathematically simple, they correspond to\nartificial routing scenarios with little resemblance to real world conditions,\nopening the possibility of proving much stronger Price of Anarchy guarantees by\nexplicitly studying their dependency on \θ. For example, in the case of\nthe standard Bureau of Public Roads (BPR) cost model, wherece(x)= ae\nx4+be, and for quartic cost functions in general, the standard PoA bound for\n\θ=\∞ is 2.1505, and this is tight both for general networks as\nwell as path-disjoint and even parallel-edge networks. In comparison, for\n\θ=1, the PoA in the case of general networks is only 1.6994, whereas\nfor path-disjoint/parallel-edge networks is even smaller (1.3652), showing\nthat both the route geometries as captured by the parameter \θ as well as\nthe network topology have significant effects on PoA.\n