Solving N player dynamic routing games with congestion: a mean field approach (extended abstract)

The recent emergence of navigational applications has changed traffic patterns and enables new types of congestion-aware routing control like dynamic road pricing. Using fundamental diagram of traffic flows -- applied in macroscopic and mesoscopic traffic modeling -- we introduce a new N-player dynamic routing game with explicit congestion dynamics. The model is well-posed and can reproduce heterogeneous departure time and congestion spill back phenomenon. However, as Nash equilibrium computation is PPAD-complete, solving the game becomes untractable for large but realistic numbers of drivers N, as illustrated numerically. Therefore, the corresponding mean field game is introduced. Its equilibrium policy provides an approximate Nash equilibrium of the original game, with vanishing average deviation incentives when N goes to infinity. Experiments are performed on several classical benchmark networks of the traffic community: the Pigou, Braess, and Sioux Falls networks with heterogeneous origin, destination and departure time tuples. The Pigou and the Braess examples reveal the accuracy of the mean field approximation whenever the number of vehicles exceeds N=30. On the Sioux Falls network (76 links, 100 time steps), this approach enables learning traffic dynamics with more than 14,000 vehicles.

• Machine Intelligence

• Networking