wardrop equilibrium | Eventually Almost Everywhere

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 $D_j(y_j)$ , where $y_j=\sum_r A_{jr}x_r$ 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, $H_{sr}$ 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 $(x_r,r\in R)$ such that for any $x_r>0$ ,

$\sum_j D_j(y_j)A_{jr}=\min_{r'\in S(r)}\sum_j D_j(y_j)A_{jr}$

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 $D_j(y_j)$ is increasing in $y_j$ for each j, and if we further assume that each $D_j$ is continuously differentiable, then we can prove that a Wardrop Equilibrium exists.

Why? Consider the optimisation problem

$\min\quad\sum_j \int_0^{y_j}D_j(u)du,\quad x\geq 0,Hx=f,Ax=y$

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

$L(x,y,\lambda,\mu)=\sum_j \int_0^{y_j}D_j(u)du+\lambda\cdot (f-Hx)-\mu\cdot(y-Ax)$

and at the minimum

$0=D_j(y_j)-\mu_j,\quad 0=-\lambda_{S(r)}+\sum_j \mu_jA_{jr}$

So $\mu_j$ the delay on j, and then

$\lambda_{S(r)}\left\{\begin{array}{l l}=\sum_j\mu_jA_{jr}& \quad x_r>0\\ \leq \sum_j\mu_jA_{jr} & \quad x_r=0\\ \end{array} \right.$

So can interpret $\lambda_{S(r)}$ as the minimum delay for this route, and so a solution to this problem is a Wardrop Equilibrium. If $D_j$ s are strictly increasing, then have uniqueness in $(y_j)$ , from the optimisation problem, but not in $(x_r)$ . 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 $\min \sum_jy_jD_j(y_j)$ . In this case the Lagrangian gives

$0=D_j(y_j)+y_jD_j'(y_j)-\mu_j,\quad 0=-\lambda_{S(r)}+\sum_j\mu_jA_{jr}$

So if add a congestion charge of $y_jD_j'(y_j)$ 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)

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Tag Archives: wardrop equilibrium

Braess’s Paradox and Traffic Networks

Related articles