Routing game

A routing game models users choosing paths through a flow network, where each user's travel time depends on the traffic using the selected edges. A nonatomic model treats each user as infinitesimal; at equilibrium, every used path has minimum latency among the available paths. An atomic model instead lets individual players move a nonzero amount of traffic.

Consider one unit of nonatomic demand and two parallel edges with latencies ${\ell }_1(x)=x$ and ${\ell }_2(x)=1$. Sending all flow on the first edge is an equilibrium: its latency is one, and an infinitesimal user cannot obtain less on the second. If a planner sends fraction $x$ on the first edge, total travel cost isThis is minimized at $x=1/2$, with cost $3/4$, below the equilibrium cost one. The example exhibits a price of anarchy of $4/3$ and separates individual latency minimization from minimum total cost.