For a traffic network, we have routes and links as before, only here we specify the delay on a link as a function of the flow along that link , where as before. Then a natural notion of an equilibrium is a distribution of flows such that no customer stands to gain by changing route. Formally, take S the set of source-destination pairs, the incidence matrix of pairs s and routes r, and S(r) the routes between the same source-destination pair as r.
Then define a Wardrop equilibrium to be a flow vector such that for any ,
that is, the delay on this route is less than or equal to the delay on any route between that pair of vertices.
A natural assumption would be that is increasing in for each j, and if we further assume that each is continuously differentiable, then we can prove that a Wardrop Equilibrium exists.
Why? Consider the optimisation problem
where f is the flow requirement. The feasible region is convex and the objective function is convex differentiable so the optimum exists. The Lagrangian is
and at the minimum
So the delay on j, and then
So can interpret as the minimum delay for this route, and so a solution to this problem is a Wardrop Equilibrium. If s are strictly increasing, then have uniqueness in , from the optimisation problem, but not in . For example, you could have two essentially identical routes from A to B, and from B to C, and it then doesn’t matter how you concatenate them to form a flow from A to C.
Note the counterintuitive Braess’s Paradox, where adding a route increasing the size of the delay at the Wardrop Equilibrium. The canonical example can be seen here, where the addition of the road across causes the delay to increase from 83 to 92. And indeed such effects have been observed in ‘real life’ as well.
Note that one explanation for why this seems counter-intuitive is that the objective function isn’t necessarily the most natural one. For a Wardrop equilibrium, the agents are acting entirely selfishly given present information. From the point of view of society, it might make more sense to minimise the average delay . In this case the Lagrangian gives
So if add a congestion charge of to the delay function, the Wardrop Equilibrium becomes equal to the societal optimal. Note that this is NOT the societal optimal for (delay + charge). However, we have seen that a toll will enable selfish behaviour to produce a societal optimum. This is an example of mechanism design, which can be considered a branch of game theory, where the aim is to design systems so that agents work in a societally optimal manner.
- Why Blocking Roads Can Speed Up Traffic (measureofdoubt.com)
- So You Want to Reduce Your Costs? Don’t Focus on Cost Reductions (empwaynek.wordpress.com)