Wardrop Equilibrium

I remember having those unpleasant lines in our high school canteen, flooded by the starving students queeing for their lunch, I would always pick a window with fewer people waiting, compromising myself with awful food. Another similar thought that always stricked me was the odds that tourists always pick the same time to travel, there’s almost always traffic congestion everywhere during holiday seasons. Yeah, lives have been always so hard.
On the first level of thinking, when there’s a lack of resource you attempt to find alternatives, e.g., picking another time for traveling, another food window, etc.. The level two thinking is maybe ‘‘since other people are avoiding holidays, what if I insist on going out on holidays’’? Or maybe there’s a twisted level three thinking, ‘‘what if everybody thinks like the level two thinker, ….’’ It’s somewhat intimidating to follow this infinite hierachy, but definitely rewarding, as there are certainly moments when people are regretting their travel decisions, thinking to themselves ‘‘I probably should not have gone the high way.’’

The aforementioned phenomenons significantly resembled the first idea proposed by Wardrop¹ in 1952. Wardrop conducted some “before-and-after” analysis over some traffic data, and came into the two alternative criteria to determine the flow distribution on the routes,

1. The journey times on all the routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route;
2. The average journey time is a minimum.

It was not until Beckmann², 1956 that the two simple yet powerful ideas were mathematically formulated, and was considered an example of Rosenthal games³. The first principle basically states that nobody should be happy to deviate from their own routes, which is essentially the behavior of Nash equilibrium.

To elaborate, we consider a transporation network represented by a directed, finite, and connected graph $ \mathcal{G} = (\mathcal{V}, \mathcal{E})$, where \(\mathcal{V}\) represent road junctions, the edges \(\mathcal{E}\) represent road segments. The set of Origin-Destination (OD) pairs is \(\mathcal{W} \subseteq \mathcal{V} \times \mathcal{V}\), indexed by \(w\), \(|\mathcal{W}| = :W\). Let \(\mathcal{P}: = \bigcup_{w\in\mathcal{W}}\mathcal{P}_w\) be the set of directed paths between OD pairs, each path set \(\mathcal{P}_w\) is indexed by \(w\).

The individual vehicles traveling through \(\mathcal{G}\) are infinitesimal players over \(\mathcal{G}\), denoted by a measurable space \((\mathcal{X}, \mathcal{M}, m)\). The players are non-atomic, i.e., \( m(x) = 0 \ \ \forall x \in \mathcal{X}\); they are split into distinct populations indexed by the OD pairs, i.e., \(\mathcal{X} = \bigcup_{w\in\mathcal{W}} \mathcal{X}_w\) and \(\mathcal{X}_w \bigcap\) \(\mathcal{X}_w’ = \emptyset,\ \forall w, w^{’} \in \mathcal{W}\). For each OD pair \(w \in \mathcal{W}\), let \(m_w = m(\mathcal{X}_w) \) represent the traffic demand. For each player \(x \in \mathcal{X}_w\), we assume that their travel path \(a \in \mathcal{P}_w\) is fixed right after the path selection.

The action profile of all the players \(\mathcal{X}\) induces an edge flow vector \(q \in \mathbb{R}^{|\mathcal{E}|}_+\), where \(q_e := \int_{\mathcal{X}} \mathbb{I}_{{e \in a}} m(dx), e \in \mathcal{E}\), and a path flow vector \(\mu \in \Delta :=\{(\mu_p)_{p\in \cup_{w\in \mathcal{W}}\mathcal{P}_w} | \mu_p := {\int_{\mathcal{X}_w} \mathbb{I}_{{a = p}} m(dx)}\}\). The edge-path incident matrix is \(\Lambda = [\Lambda^1 \vert , \ldots, \vert \Lambda^{|\mathcal{W}|}] \in \mathbb{R}^{|\mathcal{E}| \times |\mathcal{P}|}\), \(\Lambda^w_{e, p} = \mathbb{I}_{{e\in p}}, \forall e\in \mathcal{E}, w \in \mathcal{W}, p \in \mathcal{P}_w\). Easy to verify the compact form of edge-path flow relation is \(q = \Lambda \mu\).

Let \((\Omega, \mathcal{F}, \mathbb{P})\) be the probability space, \(l_e: \mathbb{R}_+ \times \Omega \to \mathbb{R}_+\) be the cost/latency functions, measuring the travel delay of the edge \(e \in \mathcal{E}\) determined by its edge flow \(q_e\) and a state variable \(\omega \in \Omega\) that is universal for the entire traffic network, e.g., \(\omega\) can represent the weather condition, road incidents or anything that affects the congestion level. Let \(l : \mathbb{R}^{|\mathcal{E}|}_{\geq 0} \times \Omega \mapsto \mathbb{R}^{|\mathcal{E}|}_+\) denote the vector-valued latency function.For an instance \(\omega \in \Omega\), the latency of path \(p\) is defined as \(\ell_p : = \sum_{e \in p} l_e (q_e, \omega ) = \Lambda^{\top}_p l (\Lambda \mu, \omega )\), which can be seen as a function of \(\mu\) and \(\omega\), written as \(\ell_p = \ell_p(\mu, \omega)\). We write the vector-valued path latency function as \(\ell : \Delta \times \Omega \mapsto \mathbb{R}^{|\mathcal{P}|}_+\). Each instance \(\omega\) determines a congestion game, captured by the tuple \(\mathcal{G}_c^{\omega} = ( \mathcal{G}, \mathcal{W}, \mathcal{X} , \mathcal{P}, \mathcal{\ell}(\cdot, \omega) )\). Each path flow profile \(\mu \in \Delta\) induces a probability measure associated with the positive random vector \(\ell(\mu, \cdot): \Omega \mapsto \mathbb{R}^{|\mathcal{P}|}_+\). The following assumption gives some realistic properties for the latency.

Standing Assumption

For all \(e \in \mathcal{E}\), the latency functions \(l_e\) are \(\omega\)-measurable, for all \(\omega \in \Omega\), \(l_e\) are \(L_0\)-Lipschitz continuous and differentiable in \(q_e\) with \(\cfrac{ \partial l_e (q_e, \omega)}{\partial q_e} > 0 \) for all \(q_e \geq 0\).

Now let’s define and find the equilibria satisfying of a deterministic game, i.e., when \(|\Omega|\) is a singleton. The first, as it turns out, coincides with the Nash Equilibrium.

Definition (Wardrop Equilibrium)

A path flow \(\mu \in \Delta\) is said to be a Wardrop Equilibrium (WE) if \(\forall w \in \mathcal{W}\), \( \mu_p > 0\) indicates \( \ell_p \leq \ell_{p^{\prime}}\) for all \(p^{\prime} \in \mathcal{P}_w\).

The second, while not satisfying the incentive conditions, somehow concides with the Nash equilibrium in a “regularized” version of the game, where the utility for each individual player is a sum of the latency and a “toll price”.

Definition (System Equilibrium)

A path flow \(\mu \in \Delta\) is said to be a system optimum if the aggregated latency \(S(\mu) := \sum_{e \in \mathcal{E}} q_e l_e \) is minimized.

Wardrop equilibrium can be characterized by the minimization of an objective function called Beckmann potential, we end this post by proving it.

Theorem

A path flow \(\mu^* \in \Delta\) is a WE if and only if it minimizes the Beckmann potential: $$ \min_{\mu \in \Delta} \Phi (\mu) := \sum_{e\in \mathcal{E}}\int_{0}^{(\Lambda \mu)_e} l_e (z) dz. $$

Proof

We first write down the constraint \(\Delta\) as a set of inequalities and equalities, $$ \begin{align*} -\mu & \preceq 0 \\ M \mu - \bf{m} & = 0 \end{align*} $$ where \(M \in \mathbb{R}^{W \times |\mathcal{P}|}\), \(M_{w,p} = 1\) if \(p \in \mathcal{P}_w\) otherwise \(0\), \(\boldsymbol{m} = (m_1, \ldots, m_W)\) is the measure vector.

Writing down the Lagrangian, by defining multipliers \(\lambda \in \mathbb{R}^{|\mathcal{P}|}, \nu \in \mathbb{R}^{W}\), let \(t_e = (0, \ldots, \underbrace{1}_{e^{th} edge}, \ldots, 0)\) be the basis vecotrs, $$ \mathcal{L} (\mu , \lambda, \nu ) = \sum_{e\in \mathcal{E}} \int_{0}^{(t_e \Lambda) \mu} l_e (z) dz - \lambda^{\top} \mu - \nu^{\top} (M\mu - \boldsymbol{m}). $$

The KKT condition says, $$ \begin{align*} \nabla_{\mu} \mathcal{L} & = \sum_{e \in \mathcal{E}} \Lambda^{\top} t_e^{\top} l_e(q_e ) - \lambda - M^{\top}\nu \\ & = \ell - \lambda - M^{\top}\nu = 0 \\ \lambda^{\top} \mu & = 0 \\ \lambda & \succeq 0 \end{align*} $$ we get that \(\ell \succeq M^{\top} \nu\), \(\ell^{\top }\mu = \nu^{\top} M \mu\), what this essentially means is that whenever \(\mu_p > 0\), \(\ell_p\) are identical in that path set \(\mathcal{P}_w\). To see this, note that \(\ell_p \geq (M^{\top} \nu)_p = \sum_{w \in \mathcal{W}} \nu_w \mathbb{I}_{ p \in \mathcal{P}_w }\), which is a constant lower bound for \(p \in \mathcal{P}_w\), fixing a \(w\); and \(\sum_{w \in \mathcal{W}}\sum_{p \in \mathcal{P}_w}\ell_p \mu_p = \sum_{w \in \mathcal{W}}\sum_{p \in \mathcal{P}_w} (M^{\top} \nu)_p \mu_p \), this implies that for any \(w \in \mathcal{W}\), if \(\mu_p > 0\) for some of the \(p \in \mathcal{P}_w\), the only possibility is that \(\ell_p = (M^{\top}\nu)_p\). The uniqueness of the edge flow solution \(q = \Lambda \mu\) can be established through calculating the Hessian of \(\Phi\), however, \(\mu\) is generally non-unique, as it should be in the solution set to a linear equation.