How Bad is Selfish Routing? 4: With Polynomial Latencies of Degree p and Nonnegative Coefficients the Cost of a Nash Flow Is at Most p + 1 Times the Optimal CostResearch Paper
In a road or communication network carrying a large population of users, each user picks a route that is fastest for itself given the congestion caused by everyone else. The resulting traffic pattern, a Wardrop or Nash equilibrium, need not minimize the total travel time: Braess's paradox shows that adding a road can make every user slower. Transportation…