How Bad is Selfish Routing? 1: A Nash Flow Costs No More Than Any Flow Feasible for Twice the Rates, for Continuous Nondecreasing LatenciesResearch Paper
In a road or communication network, traffic is routed by many independent users, each choosing a route that is fastest for itself given the congestion caused by everyone else. The resulting Nash flow (also called a Wardrop equilibrium, after Wardrop 1952) need not minimize the total delay experienced by all users: Braess's paradox shows that adding a road…