Efficient Routing Under Selfish Behavior: Bandit Learning and Targeted Taxation in Atomic Congestion Games

Abstract

The increasing integration of technology with our infrastructure systems, such as transportation and communication networks, spotlights the importance of understanding how individual selfish behaviors impact collective social efficiency. This thesis investigates atomic selfish routing games, where discrete, heterogeneous agents compete for shared resources, such as in road traffic or internet routing cases. Classic results such as the Braess paradox show that individual rational behaviors can lead to socially poor outcomes. To address these inefficiencies, this research develops a bandit-based learning algorithm that enables agents to iteratively learn low-latency routes with minimal information while accounting for the computational complexity that comes with large strategy spaces. This algorithm can find near-Nash equilibrium for the selfish routing game even in cases with thousands of players and graphs over a thousand edges and vertices.

Empirical tests on real-world transportation network datasets show that carefully designed incentive mechanisms formed using a modest and targeted version of the marginal cost pricing tax can effectively mitigate social inefficiencies. Specifically, a small proportion of roads taxed combined with a small degree of taxation is enough to recover a significant majority of system-wide inefficiency. Inspired by Stackelberg games and the emergence of autonomous vehicle technology, this thesis also explores the impact of introducing altruistically coordinated agents, analogous to autonomous vehicles. Results show a clear linear relationship between the proportion of altruistic agents and efficiency gains, showing potential for congestion mitigation via introducing such agents.