Price of anarchy in real transportation networks: efficiency, regret and inequality

Thu, 03/21/2019 - 12:00 / 14:00

203, Viale Romania, 32

Speaker: Barnabé Monnot , Singapore University of Technology and Design

Price of anarchy (PoA), introduced in the seminal paper by Koutsoupias and Papadimitriou (1999), measures the efficiency gap between a system of self-interested agents at equilibrium and the same system optimised by a central planner. Early results providing robust PoA bounds for general networks in routing games kickstarted a long line of inquiry on its properties in different settings. Its ubiquity in the last two decades was further reinforced by the wide range of games it found applications to: transportation networks, online routing, queues, auctions.

For all these theoretical investigations, it is surprising that few works have attempted to actually measure it in practice. From an experiment conducted in Singapore for which tens of thousands of students carried a custom-built sensor recording location data with several environmental factors, we draw a precise picture of the efficiency of the city state's transportation network. We show how the data can be mined to understand equilibrium properties of the system and give an empirical upper bound to the PoA, much lower than its theoretical counterpart. In turn, the data reveals something about the inequality among commuting subjects across modes of transportation and wealth levels. We analyse a new model linking inequality to mode pricing and congestion, giving general results for inequality in routing games