= 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 is
$$
C(x)=x^2+(1-x).
$$
This 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.
Back to article page
