# Wardrop equilibrium and Braess’s paradox for varying demand

Jasper Verbree, Ashish Cherukuri J. Verbree and A. Cherukuri are with the
ENgineering and TEchnology institute Groningen (ENTEG), University of
Groningen, {j.verbree<EMAIL_ADDRESS>
###### Abstract

This work explores the relationship between the set of Wardrop equilibria (WE)
of a routing game, the total demand of that game, and the occurrence of
Braess’s paradox (BP). The BP formalizes the counter-intuitive fact that for
some networks, removing a path from the network decreases congestion at WE.
For a single origin-destination routing games with affine cost functions, the
first part of this work provides tools for analyzing the evolution of the WE
as the demand varies. It characterizes the piece-wise affine nature of this
dependence by showing that the set of directions in which the WE can vary in
each piece is the solution of a variational inequality problem. In the process
we establish various properties of changes in the set of used and minimal-cost
paths as demand varies. As a consequence of these characterizations, we derive
a procedure to obtain the WE for all demands above a certain threshold. The
second part of the paper deals with detecting the presence of BP in a network.
We supply a number of sufficient conditions that reveal the presence of BP and
that are computationally tractable. We also discuss a different perspective on
BP, where we establish that a path causing BP at a particular demand must be
strictly beneficial to the network at a lower demand. Several examples
throughout this work illustrate and elaborate our findings.

##  1 Introduction

With the ever increasing amount of traffic that finds its way to the road, the
challenges of designing efficient traffic networks becomes more and more
prevalent. Unfortunately, when drivers make routing choices in a selfish
manner, that is, when traffic routes according to Wardrop equilibrium (WE)
[1], road networks are susceptible to innefficiencies which are hard to
predict in advance, and hard to detect when they occur. For instance, in some
cases travel cost of all drivers could be decreased by removing some roads in
the network; a phenomenon known as Braess’s paradox (BP). Constructing a road
that subsequently increases travel cost of all drivers using a network is of
course the epitome of innefficiency. However, detecting whether or not a
traffic network is or will be susceptible to BP, even when using a simple
model in which travel costs on roads are affine functions of the traffic on
that road, is in general NP-hard [2].

In addition to being computationally expensive to detect, BP is also known to
be highly dependent on the amount of traffic, or demand, that traverses a
network. Though the removal of a road can decrease travel cost for one level
of demand, it can increase travel cost at other levels of demand. Removal of a
road responsible for BP therefore requires careful consideration of the effect
of that removal for the whole range of demands which the network can
experience.

Motivated by the above listed observations, we study the relation between
these two challenges. To be specific, we study non-atomic, single origin-
destination routing games with affine cost functions on the edges of the
network. For these type of games we analyze the effects that changes in the
demand have on the WE of these games, and then use the obtained observations
to gain insight in how the effects of BP change as the demand varies. On the
basis of these insights we can give various easy-to-check sufficient
conditions revealing the presence of BP.

### Literature review

Wardrop equilibria(WE), first introduced in [3], have long been an important
part of traffic modeling and control. The underlying idea of this concept is
that when the flow over a traffic network is a WE, no driver can achieve a
lower travel cost by switching its routing choices. In this way it captures
the behavior of drivers minimizing their individual travel cost in an
intuitive way. The concept has practical use since the set of WE is
equivalently given by the set of solutions of a Variational Inequality (VI),
which can be computed efficiently. We refer to [1] for a survey on the subject
of WE in general.

Research on routing games with changing demand, and the effects thereof on WE
and the associated costs, often analyzes a more general framework then we
consider here. In [4], WE are studied in a dynamic setting, where demand is
time-dependent. Work in [5] is focused on studying the relation between the
total cost under WE and the minimally attainable total cost, the difference
between which is known as the price of anarchy. A thorough investigation of
the continuity of WE of routing games and monotonicity of the associated costs
with respect to changes in the demand is done in [6]. When multiple Origin-
Destination (OD) pairs are considered, [7] shows how costs under WE can
decrease as demand increases. In [8, 9] the sensitivity of WE to changes in a
broader class of parameters than only the demand is investigated. Most closely
related to our work in this context is [8]. The conclusion obtained in the
first part of this work are similar to results obtained in [8], the difference
being that we consider a more limited set of cost functions (namely affine
cost functions), only consider a single OD-pair, and crucially, do not
constrain the WE to be unique. In addition, several intermediate results
obtained in our analysis turn out to be useful in the second part of this
paper, concerning the Braess’s paradox.

Similar to the subject of Wardrop equilibria, the related concept of Braess’s
paradox (BP), has been the subject of a lot of research since its introduction
in [10] (see [11] for an English translation). Various approaches to detecting
the presence of BP have been studied, of which we mention a few examples here.
In [12], a necessary and sufficient condition for the occurrence of BP are
given based on properties of the solutions of a minimization problem.
Similarly, in [13], a comparison between flows that minimize specific
objectives, such as WE, and the flow that minimizes the average cost are used
to identify links that potentially cause BP. In [14], a heuristic method is
employed first identifying single links which cause BP, and subsequently
finding the subset of all these links that when removed lead the lowest cost
under WE. Rather than focusing on a network with given demand and cost
functions, the work [15] investigates the relation between network topology
and BP, showing that any network that is not series-parallel is subject to BP
for some assignment of cost functions. However, despite these investigations,
tractable options for detecting BP remain limited, and the general problem of
detecting BP has in fact been shown to be NP-hard [2]. In light of this
computational intractability, the likelihood of a network being subject to
Braess’s paradox has been studied. In [16], it is shown that for randomly
generated Erdös-Renyi graphs, the likelihood of there existing a set of edges
which cause BP at some demand tends to one as the number of vertices tends to
infinity. In [17], necessary and sufficient conditions for the occurrence of
BP are given, and it is shown, under the limiting assumption that paths that
were used under WE before removal of an edge are still used under WE after
removal as well, that BP is as likely to occur as not. Closer to the subject
of our work, the relation between demand and BP has also been studied in
several papers. For the archetypical example of the Wheatstone network with
affine costs, BP has been shown to only appear within a finite range of
demands [18, 19]. It has also been shown that under somewhat restrictive
assumptions an edge responsible for BP will for higher levels of demand remain
unused [20].

### Statement of contributions

The aim of this paper is to study the relationship between changing demand,
Wardrop equilibrium (WE) and Braess’s paradox (BP), in the context of non-
atomic, single-origin destination routing games with affine, non-decreasing
cost functions on the edges. The paper can be broadly divided into two parts,
the first characterizes the change in WE as demand shifts and the second
considers Braess’s paradox, its identification and the effect of demand on it.

When the WE is unique for all demand values, the map from the demand to the WE
and the cost incurred by each path at WE (loosely termed as the WE cost-
vector) is piece-wise affine. These pieces are defined by a set of points that
we refer to as breakpoints. That is, the WE and the WE cost-vector vary
linearly with demand between any two consecutive breakpoints. These
breakpoints are finite in number. When the WE is not unique, the situation is
similar, the only change being that the map from the demand to WE is set-
valued. In the first part of our work, our contributions consist of the
following results concerning the evolution of the set of WE:

  1. 1.

In (Corollary 3.6 and Lemma 4.3), we analyze how the used sets and active sets
evolve between and at breakpoints. The used set is the set of paths that carry
non-zero flow for at least on WE. The active set is the set of paths that
incur minimum cost at WE among all paths.

  2. 2.

The main result of the first part (Proposition 4.10) is the characterization
of the directions in which the WE can vary as the demand increases. We call
these directions the directions of increase. We show that these can be
computed by solving a VI problem. Essentially this is a generalization of
results in [8], where a similar property was derived under the assumption that
WE are unique.

  3. 3.

In the process of establishing the main result, we also characterize the map
from demand to the WE-cost (cost incurred by the entire flow at WE) and from
demand to the WE cost-vector (cost of each path at a WE) between consecutive
breakpoints (Proposition 4.6 and Corollary 4.7).

  4. 4.

The final set of results in this section studies the behavior of WE in the
“final interval” (Section 4.2); that is, the interval that starts at the
largest finite breakpoint and extends till positive infinity. Specifically, we
give a method to compute the largest finite breakpoint (Corollary 4.19), the
direction in which WE cost and WE cost-vector evolve in the final interval
(Proposition 4.15 and Lemma 4.17), and the active set in the final interval
(Lemma 4.18).

Using the results of the first part, we study Braess’s paradox and give the
following main insights that form the second part of our contributions:

  1. 1.

We introduce the concept of a _necessary_ set of paths, which for a given
demand is a set of paths on which the total amount of flow is positive under
any WE. We show in Proposition 5.10 that when a set of paths is not necessary
at a demand, then this indicates that it is either unnecessary for all lower
levels of demand, or this set is responsible for BP on some lower level of
demand.

  2. 2.

Next we provide a set of affine functions which give a set of sufficient
conditions for the presence of BP (Lemma 5.12). Specifically, if at any
demand, the WE-cost of the game is more than the value that any of these
affine functions take at this demand, then the network is subject to BP. In
fact we show that the network is subject to BP if and only if its WE-cost is
less than one of these affine functions (Proposition 5.15). However, obtaining
all of these affine functions is computationally intractable. Therefore we
provide two more sufficient conditions, based on these affine fuctions, that
detect BP at a particular demand in a tractable manner. The first one
(Corollary 5.13) shows that if the slope of WE-cost increases at any
breakpoint, then the network is subject to BP. Additionally, if at a given
demand, the set of directions of increase does not overlap with a simplex,
then the routing game is subject to BP at that demand (Proposition 5.14)

  3. 3.

The next set of results views BP in a broader perspective and explores its
dependence on the demand. We show that any set of paths responsible for BP at
some demand must have been strictly beneficial for some lower level of demand
(Corollary 5.19). Here, beneficial means that removal of that set of paths
will strictly increase the WE-cost. Motivated by this observation, we
introduce two simple metrics that measure the value of a set of paths over a
range of demands. For the first metric, we show that over a range of demand,
removing a set of paths does not have a negative impact cost-wise (Proposition
5.20). When considering the second metric, we show that the over a range of
demand, removing a set of paths does not have a positive impact cost-wise
(Proposition 5.21). Thus, these two results give a guideline for the planner
to remove paths based on the metric that needs to be improved on.

Several results listed above are supported with illustrative examples that
clarify nuances and aid understanding.

### Notation

The set of natural numbers is denoted by $\mathbb{N}$. For any
$n\in\mathbb{N}$ we write ${[n]:=\\{1,2,\cdots,n\\}}$ and
${[n]_{0}:=\\{0,1,\cdots,n\\}}$. We use $\mymathbf{0}_{n}$ to denote the
$n$-dimensional vector of zeros. If the dimension is clear from the context,
we simply write $\mymathbf{0}$. The hyperplane in n containing set of points
whose elements add up to $D\in\real$ is written as
${\mathcal{H}_{D}:=\\{f\in{}^{n}\;|\;\sum_{i\in[n]}f_{i}=D\\}}$. For any
$f^{-},f^{+}\in{}^{n}$ and $\mu\in[0,1]$ we use
$\operatorname{coco}_{\mu}(f^{-},f^{+}):=\mu f^{-}+(1-\mu)f^{+}$ to denote the
convex combination of $f^{-}$ and $f^{+}$. For a set $\mathcal{P}\subseteq[n]$
we use ${\mathcal{P}^{c}=\\{p\in[n]\;|\;p\notin\mathcal{P}\\}}$ to denote the
complement of that set, and write $\left\lvert{\mathcal{P}}\right\rvert$ for
the number of elements in $\mathcal{P}$. For a matrix $A\in{}^{n\times n}$, we
let $A_{i}\in{}^{1\times n}$ denote the $i$-th row of that matrix. Given a map
${g:\real\rightarrow{}^{n}}$, we use $\frac{\partial^{+}}{\partial
x}g(x):=\lim_{h\rightarrow 0^{+}}\frac{g(x+h)-g(h)}{h}$ and
${\frac{\partial^{-}}{\partial x}g(x):=\lim_{h\rightarrow
0^{-}}\frac{g(x+h)-g(h)}{h}}$ to denote the right-hand and left-hand
derivative of $g$ at $x$, respectively, whenever these limits exists.

##  2 Model and problem statement

Consider a network defined by a directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=[N]$,
$N\in\mathbb{N}$, is the set of vertices and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges. Each
edge $e_{k}\in\mathcal{E}$ consists of an ordered pair of vertices
$(v^{\operatorname{in}}_{k},v^{\operatorname{out}}_{k})$, where
$v^{\operatorname{in}}_{k},v^{\operatorname{out}}_{k}\in\mathcal{V}$. A path
$p$ from $v_{o}$ to $v_{d}$ is then an ordered set of edges
$(e_{p_{1}},\cdots,e_{p_{l}})$ such that
$v^{\operatorname{in}}_{p_{1}}=v_{o}$, $v^{\operatorname{out}}_{p_{l}}=v_{d}$
and $v^{\operatorname{out}}_{pk}=v^{\operatorname{in}}_{pk+1}$ for all
$k\in[l-1]$. In addition, we define paths as being acyclic, meaning that
$v^{\operatorname{out}}_{pj}\neq v^{\operatorname{in}}_{p_{i}}$ for all $1\leq
i\leq j\leq l$. To this network, we associate an origin $v_{o}\in\mathcal{V}$
and a destination $v_{d}\in\mathcal{V}$. We denote the set of paths in the
graph starting at $v_{o}$ and ending at $v_{d}$ by $\mathcal{P}$. Consider an
amount of traffic, denoted $D\in{\mathbb{R}}_{\geq 0}$, and referred to as the
_demand_ , that needs to be routed from origin to destination using paths in
$\mathcal{P}$. The way the traffic is divided over the paths gives rise to a
flow $f\in{\mathbb{R}}_{\geq 0}^{n}$, where $n=|\mathcal{P}|$ is the number of
paths from origin to destination, and an element $f_{p}$ of $f$ denotes the
amount of flow that is routed over path $p$. The flow is assumed to be non-
atomic, meaning that $f$ is a continuous variable. The set of _feasible_ flows
is then given by

$\mathcal{F}_{D}:=\Bigl{\\{}f\in{\mathbb{R}}_{\geq
0}^{n}\;|\;\sum_{p\in\mathcal{P}}f_{p}=D\Bigr{\\}}.$ (1)

For a flow $f$, the amount of traffic on edge $e_{k}\in\mathcal{E}$ is given
by

$f_{e_{k}}:=\sum_{\\{p\in\mathcal{P}\;|\;e_{k}\in p\\}}f_{p}.$ (2)

We associate a real-valued cost function $f_{e_{k}}\mapsto
C_{e_{k}}(f_{e_{k}})$ to each edge $e_{k}$, which models the time it takes to
traverse an edge $e_{k}$ given the flow on that edge. We assume that these
functions are in the set $\mathcal{K}$ of continuous, non-negative, non-
decreasing, affine functions. We write

$C_{e_{k}}(f_{e_{k}}):=\alpha_{e_{k}}f_{e_{k}}+\beta_{e_{k}},$ (3)

where $\alpha_{e_{k}},\beta_{e_{k}}\in{\mathbb{R}}_{\geq 0}$. The cost of
traversing a path $p$ is given by the summation of the costs of all the edges
in the path, that is,

$C_{p}(f):=\sum_{e_{k}\in p}C_{e_{k}}(f_{e_{k}}).$

For notational convenience, we define the following:

$\displaystyle C_{e}(f)$
$\displaystyle:=\big{(}C_{e_{1}}(f_{e_{1}}),\cdots,C_{e_{q}}(f_{e_{q}})\big{)}^{\top},$
$\displaystyle C(f):=\big{(}C_{1}(f),$
$\displaystyle\cdots,C_{n}(f)\big{)}^{\top},\text{ and
}\,\mathcal{C}:=\\{C_{e_{k}}\\}_{e_{k}\in\mathcal{E}},$

where $q:=\left\lvert{\mathcal{E}}\right\rvert$. Here, $C_{e}$ collects the
costs of all edges in a vector and similarly, $C$ collects the costs of all
paths. Combining (2) and (3), we can express the _path-cost function_ as:

$C(f)=Af+\beta,$ (4)

where $\beta:=(\beta_{p})_{p\in\mathcal{P}}$ is the vector with entries
$\beta_{p}=\sum_{e_{k}\in p}\beta_{e_{k}}$ and $A\in{\mathbb{R}}_{\geq
0}^{n\times n}$ is a matrix with the $(p,r)$-th entry given by
${A_{pr}=\sum_{e_{k}\in(p\cap r)}\alpha_{e_{k}}}$. Therefore, $A$ is symmetric
and in fact positive semi-definite. This can be seen by noting that
${A=B^{\top}QB}$, where $B\in{}^{q\times n}$ is defined by $B_{k,i}=1$ if
$e_{k}\in p_{i}$ and $B_{k,i}=0$ otherwise, and $Q\in{}^{q\times q}$ is a
diagonal matrix with $Q_{k,k}=\alpha_{e_{k}}\geq 0$.

Taken together, the set of paths $\mathcal{P}$, the set of cost functions
$\mathcal{C}$ over the edges in the paths of $\mathcal{P}$, and the demand
$D\geq 0$ define a _routing game_ , which we denote with the tuple
$(\mathcal{P},\mathcal{C},D)$. We will also refer to
$(\mathcal{P},\mathcal{C})$ as a routing game when we want to consider it for
multiple levels of demand. We assume that participants of a routing game want
to minimize the cost that they incur as they traverse the network, and choose
a path accordingly. To include this in our model, we assume that the resulting
flow over paths is a Wardrop equilibrium (WE).

######  Definition 2.1.

(Wardrop Equilibrium): Given a routing game $(\mathcal{P},\mathcal{C},D)$, a
flow ${f^{D}\in{\mathbb{R}}_{\geq 0}^{n}}$ is called a Wardrop equilibrium if
$f^{D}\in\mathcal{F}_{D}$ and for every $p\in\mathcal{P}$ such that
$f^{D}_{p}>0$ we have

$C_{p}(f^{D})\leq C_{r}(f^{D})\quad\text{for all }r\in\mathcal{P}.$ (5)

We will denote the set of all Wardrop equilibria as $\mathcal{W}_{D}$.
$\bullet$

The intuition behind this definition is that when the flow is in WE, none of
the participants can decrease their travel-time by choosing another path. Note
that this implies that all paths receiving a positive amount of flow incur the
same cost.

A flow $f\in\mathcal{F}_{D}$ satisfying (5) exists [21, Section 3.1.2], and
thus we know that a WE exists. In general, there can be multiple solutions to
(5), showing that WE are not necessarily unique. However, when
$\alpha_{e_{k}}>0$ for all $e_{k}\in\mathcal{E}$, then for each edge, the flow
at different WE is same; that is, if
$f^{D},\widehat{f}^{D}\in\mathcal{W}_{D}$, then
$f^{D}_{e_{k}}=\widehat{f}^{D}_{e_{k}}$ [1]. When $\alpha_{e_{k}}=0$ for some
$e_{k}\in\mathcal{E}$, then the flow on edges are not necessarily the same for
all WE, but the edge costs are; that is , for
$f^{D},\widehat{f}^{D}\in\mathcal{W}_{D}$, we have
$C_{e_{k}}(f^{D})=C_{e_{k}}(\widehat{f}^{D})$ for all $e_{k}\in\mathcal{E}$.
In fact, $\widehat{f}^{D}\in\mathcal{F}_{D}$ is a WE if and only if
$C_{e_{k}}(f^{D})=C_{e_{k}}(\widehat{f}^{D})$. This property is sometimes
referred to as the _essential uniqueness_ of a WE [22]. Note that since the
functions in $\mathcal{C}$ are affine, this gives a way of representing
$\mathcal{W}_{D}$ as a set of points satisfying a number of affine equality
constraints. Hence, $\mathcal{W}_{D}$ is convex. Furthermore, since for each
edge the cost is equal for all WE in $\mathcal{W}_{D}$, it follows that the
same holds for the costs on all paths, that is, $C(f^{D})=C(\widehat{f}^{D})$.
As a consequence of this property, we can define the set of paths that are
_active_ at demand $D$ as

$\mathcal{R}^{\operatorname{act}}_{D}:=\\{p\in\mathcal{P}\;|\;C_{p}(f^{D})\leq
C_{r}(f^{D}),\,\,\forall f^{D}\in\mathcal{W}_{D},\,\,\forall
r\in\mathcal{P}\\}.$ (6)

This set collects all the paths that have minimum cost under any WE for the
demand $D$. Similarly, we define the set of paths that are _used_ at demand
$D$ as

$\mathcal{R}^{\operatorname{use}}_{D}:=\\{p\in\mathcal{P}\;|\;\exists
f^{D}\in\mathcal{W}_{D}\text{ such that }f^{D}_{p}>0\\}.$ (7)

Note that from (5), we have
$\mathcal{R}^{\operatorname{use}}_{D}\subseteq\mathcal{R}^{\operatorname{act}}_{D}$.
The set $\mathcal{R}^{\operatorname{act}}_{D}$ and
$\mathcal{R}^{\operatorname{use}}_{D}$ will play an essential role in the
upcoming exposition where we analyze the evolution of WE as demand varies. As
such, we define the following notation: for a set
${\mathcal{R}=\\{p_{1},p_{2},\cdots,p_{m}\\}\subseteq\mathcal{P}}$ and a flow
$f\in{}^{n}$ we write

$\displaystyle f_{\mathcal{R}}$
$\displaystyle:=(f_{p_{1}},f_{p_{2}},\cdots,f_{p_{m}})^{\top},$ $\displaystyle
C_{\mathcal{R}}(f)$
$\displaystyle:=\big{(}C_{p_{1}}(f),C_{p_{2}}(f),\cdots,C_{p_{m}}(f)\big{)}^{\top}.$

That is, $f_{\mathcal{R}}$ and $C_{\mathcal{R}}$ collect the flow and costs
for all paths in $\mathcal{R}$. We define a map
${\lambda^{\operatorname{WE}}:{\mathbb{R}}_{\geq
0}\rightarrow{\mathbb{R}}_{\geq 0}}$ that stands for the cost experienced by
participants under WE as

$\lambda^{\operatorname{WE}}(D):=\min_{p\in\mathcal{P}}C_{p}(f^{D})=C_{r}(f^{D}),\quad
r\in\mathcal{R}^{\operatorname{act}}_{D}.$ (8)

Similarly, we define the map $\lambda^{\operatorname{vec}}:{\mathbb{R}}_{\geq
0}\rightarrow{\mathbb{R}}_{\geq 0}^{n}$,
${D\mapsto\lambda^{\operatorname{vec}}(D):=C(f^{D})}$, where $f^{D}$ is any
flow that belongs to the set $\mathcal{W}_{D}$. We will refer to
$\lambda^{\operatorname{WE}}$ and $\lambda^{\operatorname{vec}}$ as the _WE-
cost_ and the _WE cost-vector_ , respectively. We will also denote the $p$-th
component of $\lambda^{\operatorname{vec}}(D)$ by
$\lambda^{\operatorname{vec}}_{p}(D)$.

The exposition of the following sections can be broadly categorized in two
themes. The first section (Section 4) gathers results related to behavior of
the WE as the demand increases. The second one (Section 5) introduces the
notion of Braess’s paradox and studies how to detect it and how it varies with
the demand. Wherever necessary we illustrate the intuition and implications of
our results using appropriate examples.

##  3 Preliminaries

Here we introduce some preliminary material on how the set of WE can be
obtained by solving either a variational inequality problem (VI) or
alternatively an optimization problem. We then gather some useful results on
the evolution of the set of WE and the active and used sets as the demand
varies.

######  Definition 3.1.

(Variational inequalities (VIs)): Given a map $G:{}^{n}\rightarrow{}^{n}$ and
a set $\mathcal{X}\subset{}^{n}$, the associated variational inequality
problem, denoted $\operatorname{VI}(\mathcal{X},G)$ is to find
$x^{*}\in\mathcal{X}$ such that the following holds:

$G(x^{*})^{\top}(x-x^{*})\geq 0,\enskip\forall x\in\mathcal{X}.$ (9)

The set of solutions $x^{*}\in\mathcal{X}$ satisfying the above property is
denoted as $\operatorname{SOL}(\mathcal{X},G)$. $\bullet$

######  Proposition 3.2.

(WE as the solution of a VI [23]): Let $(\mathcal{P},\mathcal{C},D)$ be given.
A flow $f^{D}$ is a Wardrop equilibrium if and only if
$f^{D}\in\operatorname{SOL}(\mathcal{F}_{D},C)$.

We note that when $C(f)=Af$ for some matrix $A\in{}^{n\times n}$, we use the
notation
$\operatorname{SOL}(\mathcal{F},A):=\operatorname{SOL}(\mathcal{F},C)$.

Alternatively, WE can be characterized as the solution of a convex
optimization problem. This characterization will give us the tools for
analyzing the evolution of the WE cost $\lambda^{\operatorname{WE}}$ as demand
changes.

######  Proposition 3.3.

(WE as the solution of an optimization problem [1]): Let
$(\mathcal{P},\mathcal{C},D)$ be given. A flow $f^{D}$ is a Wardrop
equilibrium if and only if it is an optimal solution of the following
minimization problem

$V(D):=\min_{f\in\mathcal{F}_{D}}\sum_{e_{k}\in\mathcal{E}}\int_{0}^{f_{e_{k}}}C_{e_{k}}(z)dz.$
(10)

The relationship between $V$ and $\lambda^{\operatorname{WE}}$ is given in the
following useful result from [5].

######  Proposition 3.4.

(Properties of WE cost $\lambda^{\operatorname{WE}}$ [5]): Let
$(\mathcal{P},\mathcal{C})$ be given. The functions
$\lambda^{\operatorname{WE}}$ and $\lambda^{\operatorname{vec}}$ are
continuous, piece-wise affine, and $\lambda^{\operatorname{WE}}$ is non-
decreasing on the interval $[0,\infty)$. Moreover, for any $D>0$ we have

$\frac{\partial}{\partial D}V(D)=\lambda^{\operatorname{WE}}(D).$

Consequently, $V$ is convex and differentiable on $(0,\infty)$.

The next result summarizes properties of the active set
$\mathcal{R}^{\operatorname{act}}_{D}$, and how it changes as the demand
varies. Recall that for any two vectors $f^{-},f^{+}\in{}^{p}$ and any scalar
${\mu\in[0,1]}$, we use the notation
${\operatorname{coco}_{\mu}(f^{-},f^{+})=\mu f^{-}+(1-\mu)f^{+}}$ to represent
convex combinations.

######  Lemma 3.5.

(Evolution of the active set [5]): Let $(\mathcal{P},\mathcal{C})$ be given.
For any ${0\leq D^{-}\leq D^{+}}$ that satisfy
${\mathcal{R}^{\operatorname{act}}_{D^{-}}=\mathcal{R}^{\operatorname{act}}_{D^{+}}}$,
the following hold

  1. 1.

For all $D\in[D^{-},D^{+}]$, we have
$\mathcal{R}^{\operatorname{act}}_{D}=\mathcal{R}^{\operatorname{act}}_{D^{-}}=\mathcal{R}^{\operatorname{act}}_{D^{+}}$.

  2. 2.

If $f^{D^{-}}\in\mathcal{W}_{D^{-}}$, $f^{D^{+}}\in\mathcal{W}_{D^{+}}$ and
${\mu\in[0,1]}$, then
$\operatorname{coco}_{\mu}(f^{D^{-}},f^{D^{+}})\in\mathcal{W}_{T}$, where
$T=\operatorname{coco}_{\mu}(D^{-},D^{+})$.

A consequence of the above result is that for any ${D\in{\mathbb{R}}_{\geq
0}}$ there exists an interval $[D^{-},D^{+}]$ containing $D$ such that
$\mathcal{R}^{\operatorname{act}}_{T}=\mathcal{R}^{\operatorname{act}}_{D}$
for all $T\in(D^{-},D^{+})$, while
$\mathcal{R}^{\operatorname{act}}_{T}\neq\mathcal{R}^{\operatorname{act}}_{D}$
for all $T\in[D^{-},D^{+}]^{c}$. This observation, together with the fact that
there are only a finite number of subsets of $\mathcal{P}$ leads to the
upcoming result. It states that there is a finite set of disjoint open
intervals covering the non-negative real line, excepting a finite number of
points, such that the active and used set remain constant in each of these
intervals. Furthermore, no two such active sets, associated to different open
intervals, are equal, and the same holds for the associated used sets.

######  Corollary 3.6.

(Piece-wise constant evolution of the active and used sets): Let
$(\mathcal{P},\mathcal{C})$ be given. There exists a finite set of points
${\mathcal{D}:=\\{D_{0},D_{1},\cdots,D_{M},D_{M+1}\\}\subset{\mathbb{R}}_{\geq
0}\cup\\{+\infty\\}}$ with $D_{0}=0$, $D_{M+1}=\infty$ and $D_{j}>D_{j-1}$ for
all ${j\in[M+1]}$, and corresponding sets of subsets of $\mathcal{P}$ denoted
$\\{\mathcal{J}^{\operatorname{act}}_{0},\mathcal{J}^{\operatorname{act}}_{1},\cdots,\mathcal{J}^{\operatorname{act}}_{M}\\}$
and
$\\{\mathcal{J}^{\operatorname{use}}_{0},\mathcal{J}^{\operatorname{use}}_{1},\cdots,\mathcal{J}^{\operatorname{use}}_{M}\\}$,
such that, for all $i\in[M]_{0}$ and $D\in(D_{i},D_{i+1})$, we have

$\mathcal{R}^{\operatorname{act}}_{D}=\mathcal{J}^{\operatorname{act}}_{i},\quad\mathcal{R}^{\operatorname{use}}_{D}=\mathcal{J}^{\operatorname{use}}_{i}.$

Furthermore,
$\mathcal{J}^{\operatorname{act}}_{i}\neq\mathcal{J}^{\operatorname{act}}_{j}$
and
$\mathcal{J}^{\operatorname{use}}_{i}\neq\mathcal{J}^{\operatorname{use}}_{j}$
for all $i\neq j$.

In the above result, the claim regarding the piece-wise constant evolution of
active sets was established in [5, Section 4]. This property in combination
with Lemma 3.5-2 and (4) yields the claim regarding piece-wise evolution of
the used sets. For the sake of completeness, a proof of this last part is
given in Appendix A.

We call the demands in the set $\mathcal{D}$ _breakpoints_ , as these are the
points where the active set changes. Note that the above result makes no
claims about the relationship between the active set at a breakpoint and the
adjacent open intervals. We will shed light on this aspect in Lemma 4.3 in the
subsequent section. Finally, we note that the points in the set $\mathcal{D}$
are also the points where the WE cost-vector $\lambda^{\operatorname{vec}}$ is
non-differentiable, further motivating our choice for the term _breakpoints_.
We formally establish this in Proposition 4.6 in the next section.

##  4 Evolution of WE: Directions of increase and its properties

In this section we analyze the evolution of the WE as the demand increases. We
demonstrate our results throughout this section using the two examples
explained below. They will provide the necessary intuition and context for the
technical exposition.

$v_{o}$$v_{d}$$e_{1}$$e_{3}\enskip$$e_{5}$$e_{2}$$\enskip e_{4}$ Figure 1: The
Wheatstone network.

Figure 2: The WE at different demands for the routing game defined by the
Wheatstone network (Figure 2) and costs (12).

######  Example 4.1.

(Evolution of WE): We discuss here two simple networks:

  1. (Case-a)

For the first example, consider the Wheatstone network depicted in Figure 2,
with edge-cost functions given by

$\displaystyle C_{e_{1}}(f_{e_{1}})=f_{e_{1}},$ $\displaystyle
C_{e_{2}}(f_{e_{2}})=1,$ (11) $\displaystyle C_{e_{3}}(f_{e_{3}})=1,$
$\displaystyle C_{e_{4}}(f_{e_{4}})=f_{e_{4}},\hskip 8.0pt$ $\displaystyle
C_{e_{5}}(f_{e_{5}})=0.$

There are three paths from the origin to the destination in this network,
namely, ${p_{1}=(e_{1},e_{2})}$, $p_{2}=(e_{3},e_{4})$ and
${p_{3}=(e_{1},e_{5},e_{4})}$, with path-cost functions given respectively by

$\begin{split}C_{1}(f)&=f_{1}+f_{3}+1,\\\ C_{2}(f)&=f_{2}+f_{3}+1,\\\
C_{3}(f)&=f_{1}+f_{2}+2f_{3},\end{split}$ (12)

where we recall that $f=(f_{1},f_{2},f_{3})$ is the vector of path flows.
Having defined the routing game $(\mathcal{P},\mathcal{C})$, the explicit
expression for the WE as a function of the demand $D$, which is illustrated in
Figure 2, is given by the following:

$f^{D}=\begin{cases}\left(\begin{array}[]{ccc}0,&0,&D\end{array}\right)^{\top}&\text{for
}D\in[0,1],\\\
\left(\begin{array}[]{ccc}D-1,&D-1,&2-D\end{array}\right)^{\top}&\text{for
}D\in[1,2],\\\
\left(\begin{array}[]{ccc}\frac{D}{2},&\frac{D}{2},&0\end{array}\right)^{\top}&\text{for
}D\in[2,\infty).\end{cases}$ (13)

It is important to note that $f^{D}$ changes continuously, and moreover, it
evolves in a piece-wise affine manner. The points at which the evolution
changes from one affine piece to the next will later turn out to be exactly
the breakpoints in $\mathcal{D}$ defined in Corollary 3.6. Notice that in this
example the WE is unique for any demand and the evolution of the WE as demand
increases is fully characterized by the right-hand derivative of the map
$D\mapsto f^{D}$:

$f^{\delta}(D):=\frac{\partial^{+}}{\partial
D}f^{D}=\begin{cases}\left(\begin{array}[]{ccc}0,&0,&1\end{array}\right)^{\top}&\text{for
}D\in[0,1),\\\
\left(\begin{array}[]{ccc}1,&1,&-1\end{array}\right)^{\top}&\text{for
}D\in[1,2),\\\
\left(\begin{array}[]{ccc}\frac{1}{2},&\frac{1}{2},&0\end{array}\right)^{\top}&\text{for
}D\in[2,\infty).\end{cases}$

$v_{o}$$v_{d}$$e_{1}$$e_{3}$$e_{2}$$e_{4}$ Figure 3: The Wheatstone network
after merging the top and bottom nodes.

Note that on the intervals where the map $D\mapsto f^{D}$ is affine, naturally
the direction in which the WE moves is constant.

  2. (Case-b)

When the WE are not unique, the situation can become more complicated. To
illustrate this, we slightly modify our example. Instead of connecting the top
and bottom node in the Wheatstone network (Figure 2) with the edge $e_{5}$, we
merge them into one node. The resulting network is depicted in Figure 3. The
edge-cost functions in $\mathcal{C}$ are still given by (11), except that edge
$e_{5}$ no longer exists. There are now four paths in $\mathcal{P}$, namely
$p_{1}=(e_{1},e_{2})$, $p_{2}=(e_{3},e_{4})$, $p_{3}=(e_{1},e_{4})$, and
$p_{4}=(e_{3},e_{2})$, and the path-cost function is given by

$C(f)=Af+b=\left(\begin{array}[]{cccc}1&0&1&0\\\ 0&1&1&0\\\ 1&1&2&0\\\
0&0&0&0\\\ \end{array}\right)f+\left(\begin{array}[]{c}1\\\ 1\\\ 0\\\ 2\\\
\end{array}\right).$ (14)

Note that $Af^{0}=\mymathbf{0}$ for $f^{0}=(-1,-1,1,1)^{\top}$ and so, for any
flow $f$ and any value $\epsilon>0$, we have $C(f+\epsilon f^{0})=C(f)$. In
other words, rerouting equal amounts of flow from $p_{1}$ to $p_{2}$ and from
$p_{3}$ to $p_{4}$, or vice versa, does not change the path-cost. As a
consequence, the WE of $(\mathcal{P},\mathcal{C})$ are not always unique, and
we instead find a set of WE given by

$\displaystyle\mathcal{W}_{D}:=\enskip\begin{cases}\left\\{\left(\begin{array}[]{cccc}0&0&D&0\end{array}\right)^{\top}\right\\}&\text{for
}D\in[0,1],\\\
\\{f\in\mathcal{F}_{D}\;|\;f_{1}+f_{3}=1,f_{2}+f_{3}=1\\}&\text{for }D\geq
1.\\\ \end{cases}$ (15)

Using this, we obtain the directions along which the WE can move as the demand
increases as:

$\displaystyle\Gamma_{D}:=\begin{cases}\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f^{\delta}_{1},f^{\delta}_{2},f^{\delta}_{4}=0,\hskip
2.0ptf^{\delta}_{3}=1\\},&\text{for }D\in[0,1),\\\
\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f^{\delta}_{1},f^{\delta}_{2},f^{\delta}_{4}\geq
0,\hskip 2.0ptf^{\delta}_{1}=f^{\delta}_{2}=-f^{\delta}_{3}\\},&\text{for
}D=1,\\\
\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f^{\delta}_{1}+f^{\delta}_{3}=0,\hskip
2.0ptf^{\delta}_{2}+f^{\delta}_{3}=0\\},&\text{for }D\geq 1.\end{cases}$ (16)

Instead of a single direction, we find a set of directions along which the set
of WE evolves. That is, for every $D$ and every $f^{\delta}\in\Gamma_{D}$,
there exist $f^{D}\in\mathcal{W}_{D}$ and $\epsilon^{*}>0$ such that for all
${\epsilon\in[0,\epsilon^{*})}$ the flow ${f^{D}+\epsilon f^{\delta}}$ is a WE
for demand $D+\epsilon$. Note that, as in the previous example, the non-
negative real line is divided into intervals such that the set of directions
$\Gamma_{D}$ is constant in each interval. This possibility of nonunique WE
introduces most of the technicalities that need to be addressed in the
upcoming results. $\bullet$

Our first objective is to prove that the WE changes continuously with respect
to the demand $D$.

######  Lemma 4.2.

(Continuity of the map $D\mapsto\mathcal{W}_{D}$): Let
$(\mathcal{P},\mathcal{C})$ be given. The (set-valued) map
$D\mapsto\mathcal{W}_{D}$ is continuous; that is, for every $D\geq 0$ and
$\epsilon>0$ the following hold:

  1. 1.

There exists a $\delta>0$ such that for all $f^{D}\in\mathcal{W}_{D}$ and
$T\geq 0$ satisfying $\left\lvert{T-D}\right\rvert<\delta$ there exists
$f^{T}\in\mathcal{W}_{T}$ such that $\|f^{D}-f^{T}\|<\epsilon$.

  2. 2.

There exists a $\delta>0$ such that for all $T\geq 0$ satisfying
$\left\lvert{T-D}\right\rvert<\delta$ and all $f^{T}\in\mathcal{W}_{T}$ there
exists $f^{D}\in\mathcal{W}_{D}$ such that $\|f^{D}-f^{T}\|<\epsilon$.

The first and second part of the above definition are known as lower- and
upper-semicontinuity, respectively [24], or alternatively as inner- and outer-
semicontinuity, respectively [25]. The result follows from [26, Theorem 4.2]
and noting that since $A$ is positive semi-definite and symmetric, it is
_cocoercive_ [26, Theorem 3.3]. With the above continuity property
established, we can start our investigation into the evolution of the set of
WE by looking at the evolution of the active and used sets. Our next result
shows how these sets evolve as the demand varies in the interval
$[D_{i},D_{i+1}]$, where ${D_{i},D_{i+1}\in\mathcal{D}}$. Recall that the set
$\mathcal{D}$ contains the points where the active and used sets change (see
Corollary 3.6).

######  Lemma 4.3.

(Relationship between active and used sets over an interval): For a given
$(\mathcal{P},\mathcal{C})$, let $D_{i},D_{i+1}\in\mathcal{D}$ and let
$\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{P}$ and
$\mathcal{J}^{\operatorname{use}}_{i}\subseteq\mathcal{P}$ be the associated
active and used sets on $(D_{i},D_{i+1})$, respectively. Then, we have

$\displaystyle\mathcal{R}^{\operatorname{use}}_{D_{i}}$
$\displaystyle\subseteq\mathcal{J}^{\operatorname{use}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{R}^{\operatorname{act}}_{D_{i}},$
(17a) $\displaystyle\mathcal{R}^{\operatorname{use}}_{D_{i+1}}$
$\displaystyle\subseteq\mathcal{J}^{\operatorname{use}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{R}^{\operatorname{act}}_{D_{i+1}}.$
(17b)

###### Proof.

We will first establish (17a). Let
$p\in\mathcal{R}^{\operatorname{act}}_{D_{i}}$ and
$r\in(\mathcal{R}^{\operatorname{act}}_{D_{i}})^{c}$. It follows that
$\lambda^{\operatorname{vec}}_{p}(D_{i})<\lambda^{\operatorname{vec}}_{r}(D_{i})$.
Continuity of the map $D\mapsto\mathcal{W}_{D}$, as proven in Lemma 4.2,
implies continuity of the map $\lambda^{\operatorname{vec}}(\cdot)$.
Therefore, it follows that for small enough $\epsilon>0$ we have
$\lambda^{\operatorname{vec}}_{p}(T)<\lambda^{\operatorname{vec}}_{r}(T)$ for
all $T\in[D_{i},D_{i}+\epsilon)$. It follows that
$r\in(\mathcal{R}^{\operatorname{act}}_{T})^{c}$ for all
$T\in[D_{i},D_{i}+\epsilon)$, which shows that
$r\in(\mathcal{J}^{\operatorname{act}}_{i})^{c}$. Thus we have
$\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{R}^{\operatorname{act}}_{D_{i}}$.
Similarly, it follows from Lemma 4.2 that for small enough $\epsilon>0$ there
exists $f^{T}\in\mathcal{W}_{T}$ such that $f^{T}_{p}>0$ for all
$p\in\mathcal{R}^{\operatorname{use}}_{D_{i}}$ and
$T\in[D_{i},D_{i}+\epsilon)$. This shows that
$\mathcal{R}^{\operatorname{use}}_{D_{i}}\subseteq\mathcal{R}^{\operatorname{use}}_{T}$
for all $T\in[D_{i},D_{i}+\epsilon)$. Thus we have
$\mathcal{R}^{\operatorname{use}}_{D_{i}}\subseteq\mathcal{J}^{\operatorname{use}}_{i}$.
By definition of the active and used sets, we also have
$\mathcal{J}^{\operatorname{use}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i}$,
proving (17a). The result (17b) concerning
$\mathcal{R}^{\operatorname{use}}_{D_{i+1}}$ and
$\mathcal{R}^{\operatorname{act}}_{D_{i+1}}$ follows by the same arguments
considering the interval $(D_{i+1}-\epsilon,D_{i+1}]$. ∎

The implication of the above is that when the demand $D$ moves from the point
$D_{i}$ into the interval $(D_{i},D_{i+1})$, the used set
$\mathcal{R}^{\operatorname{use}}_{D}$ can only gain elements, while the
active set $\mathcal{R}^{\operatorname{act}}_{D}$ can only lose elements. When
the demand $D$ then moves from the interval $(D_{i},D_{i+1})$ to the point
$D_{i+1}$ the situation is reversed. That is,
$\mathcal{R}^{\operatorname{use}}_{D}$ can only lose elements, while
$\mathcal{R}^{\operatorname{act}}_{D}$ can only gain elements. Also note that
since
$\mathcal{J}^{\operatorname{use}}_{i}\neq\mathcal{J}^{\operatorname{use}}_{j}$
and
$\mathcal{J}^{\operatorname{act}}_{i}\neq\mathcal{J}^{\operatorname{act}}_{j}$
for all $i\neq j$, both the active and the used set must change as $D$ moves
from $(D_{i-1},D_{i})$ to $(D_{i},D_{i+1})$. Turning our attention back to
Example 4.1a, using (12) and (13), we derive
$\mathcal{R}^{\operatorname{act}}_{D}$ and
$\mathcal{R}^{\operatorname{use}}_{D}$ as:

$\displaystyle(\mathcal{R}^{\operatorname{act}}_{D},\mathcal{R}^{\operatorname{use}}_{D})=\begin{cases}(\\{p_{3}\\},\emptyset)&\text{for
}D=0,\\\ (\\{p_{3}\\},\\{p_{3}\\})&\text{for }D\in(0,1),\\\
(\\{p_{1},p_{2},p_{3}\\},\\{p_{3}\\})&\text{for }D=1,\\\
(\\{p_{1},p_{2},p_{3}\\},\\{p_{1},p_{2},p_{3}\\})&\text{for }D\in(1,2),\\\
(\\{p_{1},p_{2},p_{3}\\},\\{p_{1},p_{2}\\})&\text{for }D=2,\\\
(\\{p_{1},p_{2}\\},\\{p_{1},p_{2}\\})&\text{for }D\in(2,\infty).\\\
\end{cases}$

This illustrates the behavior stated in Lemma 4.3. This lemma also allows us
to establish the following minor extension of Lemma 3.5:

######  Corollary 4.4.

(Convex combinations of WE in $[D_{i},D_{i+1}]$): For a given
$(\mathcal{P},\mathcal{C})$ and $D_{i},D_{i+1}\in\mathcal{D}$, let
$D,T\in[D_{i},D_{i+1}]$. Then, for any ${f^{D}\in\mathcal{W}_{D}}$,
$f^{T}\in\mathcal{W}_{T}$, and ${\mu\in[0,1]}$, we have
$\operatorname{coco}_{\mu}(f^{D},f^{T})\in\mathcal{W}_{\operatorname{coco}_{\mu}(D,T)}$.

###### Proof.

The result for the case $D,T\in(D_{i},D_{i+1})$ is already stated in Lemma
3.5. Now consider the case ${D=D_{i}}$ and ${T=D_{i+1}}$. For given
$\mu\in[0,1]$, $f^{D}\in\mathcal{W}_{D}$, and $f^{T}\in\mathcal{W}_{T}$,
denote ${f^{\mu}:=\operatorname{coco}_{\mu}(f^{D},f^{T})}$. Since
$f^{D},f^{T}\geq 0$, we have $f^{\mu}\geq 0$, and it follows in a
straigthforward manner that $f^{\mu}\in\mathcal{F}_{T_{\mu}}$, where
$T_{\mu}:=\operatorname{coco}_{\mu}(D,T)$.

Now let $p\in\mathcal{P}$ be a path such that $f^{\mu}_{p}>0$. It follows that
either $f^{D}_{p}>0$ or $f^{T}_{p}>0$. Since $D=D_{i}$ and $T=D_{i+1}$, we
obtain either $p\in\mathcal{R}^{\operatorname{use}}_{D_{i}}$ or
$p\in\mathcal{R}^{\operatorname{use}}_{D_{i+1}}$. In both cases, Lemma 4.3
implies that $p\in\mathcal{J}^{\operatorname{use}}_{i}$, and subsequently the
same result implies that
$p\in\mathcal{R}^{\operatorname{act}}_{D_{i}}\cap\mathcal{R}^{\operatorname{act}}_{D_{i+1}}$.
Thus, we have

$\displaystyle C_{p}(f^{D})$ $\displaystyle\leq C_{r}(f^{D}),\quad\forall
r\in\mathcal{P},$ $\displaystyle C_{p}(f^{T})$ $\displaystyle\leq
C_{r}(f^{T}),\quad\forall r\in\mathcal{P}.$

Since the function $C$ is affine and $f^{\mu}$ is a convex combination of
$f^{D}$ and $f^{T}$, we get $C_{p}(f^{\mu})\leq C_{r}(f^{\mu})$ for all
$r\in\mathcal{P}$. This establishes the WE condition (5) and thus we have
shown that $f^{\mu}\in\mathcal{W}_{T_{\mu}}$. The cases $D=D_{i}$,
$T\in(D_{i},D_{i+1})$ and $D\in(D_{i},D_{i+1})$, $T=D_{i+1}$ follow using
similar arguments. ∎

The main goal of this section is to characterize the evolution of the set of
WE. In Example 4.1, we noted the existence of a (set of) _direction(s)_
$f^{\delta}$ along which the WE moved when the demand increases in the
interval between points of $\mathcal{D}$. We call such a direction a
_direction of increase_. The collection of all such vectors, denoted
$\Gamma_{D}$, is referred to as the set of directions of increase. Our goal is
thus to characterize this set $\Gamma_{D}$, which is formally defined as
follows:

######  Definition 4.5.

(Set of directions of increase): Let $(\mathcal{P},\mathcal{C},D)$ be given.
The set of _directions of increase_ $\Gamma_{D}$ is the set of all directions
$f^{\delta}\in\mathcal{H}_{1}$ in which the flow can be increased, starting
from some WE in $\mathcal{W}_{D}$, such that the new flow is a WE as long as
the increase is small enough. That is,

$\displaystyle\Gamma_{D}:=\\{f^{\delta}$
$\displaystyle\in\mathcal{H}_{1}\;|\;\exists f^{D}\in\mathcal{W}_{D},\hskip
2.0pt\bar{\epsilon}>0\text{ such that }f^{D}+\epsilon
f^{\delta}\in\mathcal{W}_{D+\epsilon}\hskip
2.0pt\forall\epsilon\in[0,\bar{\epsilon}]\\}.\hbox{$\bullet$}$

This definition of $\Gamma_{D}$ puts emphasis on the local properties of this
set. However, we note that for any $D\in[D_{i},D_{i+1})$ every WE
$f^{T}\in\mathcal{W}_{T}$, where $T\in(D,D_{i+1}]$, is of the form
$f^{D}+(T-D)f^{\delta}$, where $f^{D}\in\mathcal{W}_{D}$ and
$f^{\delta}\in\Gamma_{D}$. In other words, all WE in the range $[D,D_{i+1}]$
are characterized by $\mathcal{W}_{D}$ and $\Gamma_{D}$. This fact can be
derived from Corollary 4.4.

###  4.1 Characterizing $\Gamma_{D}$

Before we address the evolution of the WE by deriving an expression for
$\Gamma_{D}$, we first shift our attention to the evolution of the WE-cost
$\lambda^{\operatorname{WE}}$ and the WE cost-vector
$\lambda^{\operatorname{vec}}$. We characterize the evolution of the WE cost-
vector $\lambda^{\operatorname{vec}}$ and relate it to the set $\Gamma_{D}$.

######  Proposition 4.6.

(The evolution of $\lambda^{\operatorname{vec}}$): Let
$(\mathcal{P},\mathcal{C})$ be given. For any ${i\in[M]_{0}}$, there exists a
vector $\delta C^{i}$ such that the following hold:

  1. 1.

for all $D\in[D_{i},D_{i+1})$ and $f^{\delta}\in\Gamma_{D}$

$Af^{\delta}=\delta C^{i},$ (18)

  2. 2.

for all $T\in[D_{i},D_{i+1}]$

$\lambda^{\operatorname{vec}}(T)=\lambda^{\operatorname{vec}}(D_{i})+(T-D_{i})\delta
C^{i},$ (19)

  3. 3.

$\delta C^{i}\neq\delta C^{i+1}$.

###### Proof.

We start with the second claim, which is a consequence of the affine form of
$C$, given in (4), and the convexity result in Corollary 4.4. Let
$f^{D_{i}}\in\mathcal{W}_{D_{i}}$ and $f^{D_{i+1}}\in\mathcal{W}_{D_{i+1}}$
and define

$f^{\delta_{0}}:=(D_{i+1}-D_{i})^{-1}(f^{D_{i+1}}-f^{D}).$

By Corollary 4.4 any convex combination of $f^{D_{i}}$ and $f^{D_{i+1}}$ is a
WE. To be specific, pick some $\mu\in[0,1]$ and let
$f^{\mu}:=\operatorname{coco}_{\mu}(f^{D_{i}},f^{D_{i+1}})$. Then,
$f^{\mu}\in\mathcal{W}_{T_{\mu}}$, where
${T_{\mu}=\operatorname{coco}_{\mu}(D_{i},{D_{i+1}})}$. Furthermore, we have

$\displaystyle f^{\mu}$
$\displaystyle=f^{D_{i}}+(1-\mu)(f^{D_{i+1}}-f^{D_{i}})$
$\displaystyle=f^{D_{i}}+(T_{\mu}-D_{i})\frac{f^{D_{i+1}}-f^{D_{i}}}{{D_{i+1}}-D_{i}}$
$\displaystyle=f^{D_{i}}+(T_{\mu}-D_{i})f^{\delta_{0}}.$

Using the affine nature of $C$, given in (4), and the definition of
$\lambda^{\operatorname{vec}}$ we derive

$\displaystyle\lambda^{\operatorname{vec}}(T_{\mu})$
$\displaystyle=C(f^{\mu})$ (20)
$\displaystyle=C\big{(}f^{D_{i}}+(T_{\mu}-D_{i})f^{\delta_{0}}\big{)}$
$\displaystyle=C(f^{D_{i}})+(T_{\mu}-D_{i})Af^{\delta_{0}}$
$\displaystyle=\lambda^{\operatorname{vec}}(D_{i})+(T_{\mu}-D_{i})Af^{\delta_{0}}.$

Since the above holds for all $\mu\in[0,1]$ it follows that, for all
$T\in[D_{i},D_{i+1}]$, we have
${\lambda^{\operatorname{vec}}(T)=\lambda^{\operatorname{WE}}(D_{i})+(T_{\mu}-D_{i})Af^{\delta_{0}}}$.
Setting $\delta C^{i}:=Af^{\delta_{0}}$ the second statement is proven.

To show the first statement, let $D^{-}\in[D_{i},D_{i+1})$ and let
$f^{\delta}\in\Gamma_{D^{-}}$. It follows that there exists
$D^{+}\in(D^{-},D_{i+1}]$ and $f^{D^{+}}\in\mathcal{W}_{D^{+}}$ such that

$f^{D^{+}}=f^{D^{-}}+(D^{+}-D^{-})f^{\delta}.$

Using the same derivation as in (20) we find

$\displaystyle\lambda^{\operatorname{vec}}(D^{+})=\lambda^{\operatorname{vec}}(D^{-})+(D^{+}-D^{-})Af^{\delta}.$
(21)

However, from (19) we have

$\displaystyle\lambda^{\operatorname{vec}}(D^{+})$
$\displaystyle=\lambda^{\operatorname{vec}}(D_{i})+(D^{-}-D_{i})\delta
C^{i}+(D^{+}-D^{-})\delta C^{i}$
$\displaystyle=\lambda^{\operatorname{vec}}(D^{-})+(D^{+}-D^{-})\delta C^{i},$
(22)

where we have again used
$\lambda^{\operatorname{vec}}(D^{-})=\lambda^{\operatorname{vec}}(D_{i})+(D^{-}-D_{i})\delta
C^{i}$. Comparing expressions (21) and (22), we get $Af^{\delta}=\delta
C^{i}$, proving the first statement.

We show the third statement using contradiction. To this end, assume that
${\delta C^{i}=\delta C^{i+1}}$ for some $i\in[M]_{0}$ and let
${p,r\in\mathcal{J}^{\operatorname{act}}_{i}}$. By definition of the active
set it follows that
$\lambda^{\operatorname{vec}}_{p}(D)=\lambda^{\operatorname{vec}}_{r}(D)$ for
all $D\in(D_{i},D_{i+1})$. Combined with (19) this implies $\delta
C^{i}_{p}=\delta C^{i}_{r}$. Under the assumption that $\delta C^{i}=\delta
C^{i+1}$ we then have, by (19), that
$\lambda^{\operatorname{vec}}_{p}(D)=\lambda^{\operatorname{vec}}_{r}(D)$ for
all $D\in(D_{i},D_{i+2})$ and $p,r\in\mathcal{J}^{\operatorname{act}}_{i}$. As
a consequence either all of the paths in
$\mathcal{J}^{\operatorname{act}}_{i}$ are in the active set on the interval
$(D_{i+1},D_{i+2})$ or none of them are. That is, one of the following holds:
$\mathcal{J}^{\operatorname{act}}_{i}\cap\mathcal{J}^{\operatorname{act}}_{i+1}=\emptyset$
or
$\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i+1}$.
However, note that from Lemma 4.3 we obtain
$\mathcal{R}^{\operatorname{use}}_{D_{i+1}}\subseteq\mathcal{J}^{\operatorname{use}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i}$
and
$\mathcal{R}^{\operatorname{use}}_{D_{i+1}}\subseteq\mathcal{J}^{\operatorname{use}}_{i+1}\subseteq\mathcal{J}^{\operatorname{act}}_{i+1}$.
Since $D_{i+1}>0$, we have
$\mathcal{R}^{\operatorname{use}}_{D_{i+1}}\neq\emptyset$ and it follows that
$\mathcal{J}^{\operatorname{act}}_{i}\cap\mathcal{J}^{\operatorname{act}}_{i+1}\neq\emptyset$.
Thus, we must have
$\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i+1}$.

Now since
$\mathcal{J}^{\operatorname{act}}_{i}\neq\mathcal{J}^{\operatorname{act}}_{i+1}$,
there must exist some path
$r^{\prime}\in(\mathcal{J}^{\operatorname{act}}_{i})^{c}\cap\mathcal{J}^{\operatorname{act}}_{i+1}$.
Since $r^{\prime}$ is not in the active set
$\mathcal{J}^{\operatorname{act}}_{i}$, one can find a path
$p^{\prime}\in\mathcal{J}^{\operatorname{act}}_{i}$ and a demand
$D\in(D_{i},D_{i+1})$ such that
$\lambda^{\operatorname{vec}}_{p^{\prime}}(D)<\lambda^{\operatorname{vec}}_{r^{\prime}}(D)$.
On the other hand, by Lemma 4.3,
$r^{\prime}\in\mathcal{J}^{\operatorname{act}}_{i+1}$ implies
${r^{\prime}\in\mathcal{R}^{\operatorname{act}}_{D_{i+1}}}$ and so,
$\lambda^{\operatorname{vec}}_{r^{\prime}}(D_{i+1})\leq\lambda^{\operatorname{vec}}_{p^{\prime}}(D_{i+1})$.
Combining the above two facts with the affine form (19), we deduce that
$\delta C^{i}_{p^{\prime}}>\delta C^{i}_{r^{\prime}}$. Since $\delta
C^{i+1}=\delta C^{i}$ it follows from (19) that
$\lambda^{\operatorname{vec}}_{p^{\prime}}(D)>\lambda^{\operatorname{vec}}_{r^{\prime}}(D)$
for all $D\in(D_{i+1},D_{i+2})$. However, this contradicts the fact that
$p^{\prime}\in\mathcal{J}^{\operatorname{act}}_{i}\subseteq\mathcal{J}^{\operatorname{act}}_{i+1}$.

We see that we arrive at a contradiction, and therefore the premise must be
false. We conclude that ${\delta C^{i+1}\not=\delta C^{i}}$. ∎

Proposition 4.6 shows that directions of increase at any demand $D$ belong to
a subspace and the map defining this subspace relates to the map
$\lambda^{\operatorname{vec}}$. The above result also shows that
$\lambda^{\operatorname{vec}}$ is affine on the intervals between the
breakpoints in $\mathcal{D}$ and non-differentiable at the points in
$\mathcal{D}$. The latter fact is due to the last conclusion in the result.
Below we prove a similar result for the evolution of
$\lambda^{\operatorname{WE}}$.

######  Corollary 4.7.

(Evolution of $\lambda^{\operatorname{WE}}$): Let $(\mathcal{P},\mathcal{C})$
be given. For any ${i\in[M]_{0}}$, there exists a value $\delta\lambda^{i}\geq
0$ such that for all $T\in[D_{i},D_{i+1}]$

$\lambda^{\operatorname{WE}}(T)=\lambda^{\operatorname{WE}}(D_{i})+(T-D_{i})\delta\lambda^{i}.$

Furthermore,
$\delta\lambda^{i}=\min_{r\in\mathcal{J}^{\operatorname{act}}_{i}}\delta
C^{i}_{r}$.

###### Proof.

The result follows from (19) and noting that for any $i\in[M]_{0}$ and
${D\in(D_{i},D_{i+1})}$ we have
$\lambda^{\operatorname{WE}}(D)=\lambda^{\operatorname{vec}}_{p}(D)$ for any
$p\in\mathcal{J}^{\operatorname{act}}_{i}$. ∎

We illustrate Proposition 4.6 and Corollary 4.7, as well as some of the
nuances of the evolution of the cost with an example:

######  Example 4.8.

($\lambda^{\operatorname{WE}}$ can be differentiable at points in
$\mathcal{D}$):

  1. (a)

First we show that, even though we know $\delta C^{i}\neq\delta C^{i+1}$, we
can have $\delta C^{i}=\delta C^{j}$ whenever $j\notin\\{i-1,i,i+1\\}$. That
is, the direction in which $\lambda^{\operatorname{vec}}$ varies as demand
changes is different in consecutive intervals between breakpoints but it can
be same for non-consecutive intervals. Note that this differs from how active
and used sets vary, (see Corollary 3.6),since these sets are not same for any
pair of intervals. Consider the network depicted in Figure 4, which is the
Wheatstone network with the additional edge $e_{6}$.

$v_{o}$$v_{d}$$e_{1}$$e_{3}\enskip$$e_{5}$$e_{2}$$\enskip e_{4}$$e_{6}$ Figure
4: The Wheatstone network with an added parallel path.

For $e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$, and $e_{5}$ we use the cost functions
given in (11), and for the new edge $e_{6}$ we use

$C_{e_{6}}(f_{e_{6}}):=2.1.$

There are four paths through this network, given by ${p_{1}:=(e_{1},e_{2})}$,
$p_{2}:=(e_{3},e_{4})$, $p_{3}:=(e_{1},e_{5},e_{4})$ and ${p_{4}:=(e_{6})}$.
The resulting path-cost function is given by

$C(f)=Af+b=\left(\begin{array}[]{ccccc}1&0&1&0\\\ 0&1&1&0\\\ 1&1&2&0\\\
0&0&0&0\\\ \end{array}\right)f+\left(\begin{array}[]{c}1\\\ 1\\\ 0\\\ 2.1\\\
\end{array}\right)$

As long as the WE-cost of this game is lower than the constant cost of path
$p_{4}$, the WE will be the same as that of the game in Example 4.1a, with in
addition $f_{p_{4}}=0$. Furthermore, as demand increases and the WE-cost
reaches the constant cost of path $p_{4}$, all subsequent flow will be routed
on path $p_{4}$. That is, we have

$f^{D}=\begin{cases}\left(\begin{array}[]{cccc}0,&0,&D,&0\end{array}\right)^{\top}&\text{for
}D\in[0,1],\\\
\left(\begin{array}[]{cccc}D-1,&D-1,&2-D,&0\end{array}\right)^{\top}&\text{for
}D\in[1,2],\\\
\left(\begin{array}[]{cccc}\frac{D}{2},&\frac{D}{2},&0,&0\end{array}\right)^{\top}&\text{for
}D\in[2,2.2],\\\
\left(\begin{array}[]{cccc}1.1,&1.1,&0,&D-2.2\end{array}\right)^{\top}&\text{for
}D\in[2.2,\infty).\end{cases}$

Consequently, we obtain

$\displaystyle\lambda^{\operatorname{vec}}(D)=\begin{cases}\left(\begin{array}[]{cccc}1+D,&1+D,&2D,&2.1\end{array}\right)^{\top}&\text{for
}D\in[0,1],\\\
\left(\begin{array}[]{cccc}2,&2,&2,&2.1\end{array}\right)^{\top}&\text{for
}D\in[1,2],\\\
\left(\begin{array}[]{cccc}1+\frac{D}{2},&1+\frac{D}{2},&D,&2.1\end{array}\right)^{\top}&\text{for
}D\in[2,2.2],\\\
\left(\begin{array}[]{cccc}2.1,&2.1,&2.2,&2.1\end{array}\right)^{\top}&\text{for
}D\in[2.2,\infty).\end{cases}$

Figure 5: The evolution of $\lambda^{\operatorname{vec}}(D)$ for the routing
game discussed in Example 4.8a.

In Figure 5, we plot these maps, and it is immediately apparent that on the
intervals $D\in(1,2)$ and $D\in(2.2,\infty)$ the cost of all paths remain
constant. In other words, we have $\delta C^{1}=\delta C^{3}=\mymathbf{0}$.

  2. (b)

Note that even though $\lambda^{\operatorname{vec}}$ is necessarily not
differentiable at the points in $\mathcal{D}$, the same does not hold for
$\lambda^{\operatorname{WE}}$. To see this, again consider the network in
Figure 4, where as before the cost functions of the edges $e_{1}$, $e_{2}$,
$e_{3}$ and $e_{4}$ are given by (11), but for the edges $e_{5}$ and $e_{6}$
we set

$C_{e_{5}}(f_{e_{5}}):=f_{e_{5}},\quad C_{e_{6}}(f_{e_{6}}):=2+f_{e_{6}}.$

The resulting path-cost function is given by

$C(f)=Af+b=\left(\begin{array}[]{ccccc}1&0&1&0\\\ 0&1&1&0\\\ 1&1&3&0\\\
0&0&0&1\\\ \end{array}\right)f+\left(\begin{array}[]{c}1\\\ 1\\\ 0\\\ 2\\\
\end{array}\right)$

and we get the following expression for the WE:

$f^{D}=\begin{cases}\left(\begin{matrix}0,&0,&D,&0\end{matrix}\right)^{\top}&\text{for
}D\in[0,\frac{1}{2}],\\\
\frac{1}{3}\left(\begin{matrix}2D-1,&2D-1,&2-D,&0\end{matrix}\right)^{\top}&\text{for
}D\in[\frac{1}{2},2],\\\
\frac{1}{3}\left(\begin{matrix}D+1,&D+1,&0,&D-2\end{matrix}\right)^{\top}&\text{for
}D\in[2,\infty).\end{cases}$

Note that for $D\in(\frac{1}{2},2)$ and $D\in(2,\infty)$ we have
${\mathcal{R}^{\operatorname{act}}_{D}=\\{p_{1},p_{2},p_{3}\\}}$ and
${\mathcal{R}^{\operatorname{act}}_{D}=\\{p_{1},p_{2},p_{4}\\}}$,
respectively. Therefore, $\lambda^{\operatorname{vec}}$ should not be
differentiable at $D=2$, which is verified by noting that

$\lambda^{\operatorname{vec}}_{p_{4}}(D)=\begin{cases}2&\text{for
}D\in[0,2],\\\ \frac{1}{3}D+\frac{4}{3}&\text{for }D\in[2,\infty).\end{cases}$

However, $\lambda^{\operatorname{WE}}$ is given by

$\lambda^{\operatorname{WE}}(D)=\begin{cases}3D\quad&\text{for
}D\in[0,\frac{1}{2}],\\\ \frac{1}{3}D+\frac{4}{3}\quad&\text{for
}D\in[\frac{1}{2},\infty).\end{cases}$

The full evolution of $\lambda^{\operatorname{vec}}$ and
$\lambda^{\operatorname{WE}}$ is depicted in Figure 6.

Figure 6: The evolution of $\lambda^{\operatorname{WE}}$ and
$\lambda^{\operatorname{vec}}_{p_{4}}$ for the routing game discussed in
Example 4.8b.

We see that $\lambda^{\operatorname{WE}}$ is differentiable on
$(\frac{1}{2},\infty)$, despite the fact that
$\lambda^{\operatorname{vec}}_{p_{3}}$ and
$\lambda^{\operatorname{vec}}_{p_{4}}$ clearly show a breakpoint at $D=2$.
$\bullet$

With the evolution of $\lambda^{\operatorname{vec}}$ and
$\lambda^{\operatorname{WE}}$ established, our next goal is to characterize
$\Gamma_{D}$ in a comprehensive way. For ease of exposition we first define
the set of _directions of feasibility_.

######  Definition 4.9.

(Direction of feasibility): Let $(\mathcal{P},\mathcal{C},D)$ be given. The
set of _directions of feasibility_ $\mathcal{M}_{D}$ is the set of all
directions $f^{\delta}\in\mathcal{H}_{1}$ in which the flow can be increased
such that the no flow is assigned to or taken from paths that are inactive
under WE, and a non-negative flow is assigned to paths that are unused under
WE. That is,

$\mathcal{M}_{D}:=\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f_{\mathcal{R}^{\operatorname{act}}_{D}\setminus\mathcal{R}^{\operatorname{use}}_{D}}^{\delta}\geq
0,\enskip f_{(\mathcal{R}^{\operatorname{act}}_{D})^{c}}^{\delta}=0\\},$ (23)

where
$(\mathcal{R}^{\operatorname{act}}_{D})^{c}=\mathcal{P}\setminus\mathcal{R}^{\operatorname{act}}_{D}$.
$\bullet$

Intuitively, for any direction $f^{\delta}$ in $\mathcal{M}_{D}$ there exists
a WE $f^{D}\in\mathcal{W}_{D}$ and a value $\bar{\epsilon}>0$ such that for
all $\epsilon\in[0,\bar{\epsilon}]$ we have $f^{D}+\epsilon
f^{\delta}\in\mathcal{F}_{D+\epsilon}$, and no flow is routed onto inactive
paths. That is, there exists a WE in $\mathcal{W}_{D}$ such that moving from
that WE in the direction $f^{\delta}$ for a small enough amount will keep the
resulting flow feasible, and contained within the set of paths that was
active. The main result of this section is that $\Gamma_{D}$ can be obtained
as the set of solutions of a VI problem, where the feasible set is given by
$\mathcal{M}_{D}$. Recall that $A\in{}^{n\times n}$ is the matrix related to
the flow dependent part of the path-cost function $C$; i.e. $C(f)=Af+\beta$.
We will show that the following holds:

######  Proposition 4.10.

(Directions of increase as solutions to a VI): Let
$(\mathcal{P},\mathcal{C},D)$ be given. Then,

$\Gamma_{D}=\operatorname{SOL}(\mathcal{M}_{D},A).$

Working towards a proof of the above, we first show two intermediate
statements. The first states that the set of directions of increase is
contained in the set of directions of feasibility.

######  Lemma 4.11.

($\Gamma_{D}$ is a subset of $\mathcal{M}_{D}$): Let
$(\mathcal{P},\mathcal{C},D)$ be given. Then,
$\Gamma_{D}\subseteq\mathcal{M}_{D}$.

###### Proof.

Let $f^{\delta}\in\Gamma_{D}$, and let $D_{i},D_{i+1}\in\mathcal{D}$ satisfy
${D\in[D_{i},D_{i+1})}$. Then there exist $f^{D}\in\mathcal{W}_{D}$,
${T\in(D,D_{i+1}]}$, and $f^{T}\in\mathcal{W}_{T}$ such that
${f^{T}=f^{D}+(T-D)f^{\delta}}$. Thus we have
${f^{\delta}=(T-D)^{-1}(f^{T}-f^{D})}$. Note that since
${D\in[D_{i},D_{i+1})}$ and $T\in(D,D_{i+1}]$ it follows from Lemma 4.3 that
$\mathcal{R}^{\operatorname{use}}_{T}\subseteq\mathcal{R}^{\operatorname{act}}_{D}$.
Therefore
$(\mathcal{R}^{\operatorname{act}}_{D})^{c}\subseteq(\mathcal{R}^{\operatorname{use}}_{T})^{c}$.
Consequently, by definition of the used set (7), we have
$f_{(\mathcal{R}^{\operatorname{use}}_{T})^{c}}^{T}=0$ and so,
$f_{(\mathcal{R}^{\operatorname{act}}_{D})^{c}}^{T}=0$. By definition of the
active set (6) and the WE condition (5) we have
$f_{(\mathcal{R}^{\operatorname{act}}_{D})^{c}}^{D}=0$. This shows that
$f_{(\mathcal{R}^{\operatorname{act}}_{D})^{c}}^{\delta}=0$.

Once again, by definition of the used set we have
$f_{\mathcal{R}^{\operatorname{act}}_{D}\setminus\mathcal{R}^{\operatorname{use}}_{D}}^{D}=0$
and by feasiblity of WE we have $f^{T}\geq 0$. Therefore
$f_{\mathcal{R}^{\operatorname{act}}_{D}\setminus\mathcal{R}^{\operatorname{use}}_{D}}^{\delta}\geq
0$, which completes the proof. ∎

In the next statement we establish some properties of sets of the form
$\operatorname{SOL}(\mathcal{M},A)$ where $\mathcal{M}$ is of the form (23),
which we require for proving Proposition 4.10.

######  Proposition 4.12.

(Properties of $\operatorname{SOL}(\mathcal{M},A)$): Let $\mathcal{P}$,
$\mathcal{C}$, $T\in\real$, and $\mathcal{R},\mathcal{Q}\subseteq\mathcal{P}$
satisfying $\mathcal{R}\subseteq\mathcal{Q}$ be given. In addition, let

$\mathcal{M}:=\\{f^{\delta}\in\mathcal{H}_{T}\;|\;f^{\delta}_{\mathcal{Q}\setminus\mathcal{R}}\geq
0,\quad f^{\delta}_{\mathcal{Q}^{c}}=0\\}.$

We then have the following properties:

  1. 1.

$\operatorname{SOL}(\mathcal{M},A)$ is non-empty.

  2. 2.

There exists a vector $\delta C\in{}^{n}$ such that
$f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$ if and only if
$f^{\delta}\in\mathcal{M}$ and $Af^{\delta}=\delta C$.

  3. 3.

If $f^{\delta}_{p}>0$ for some
$f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$ and $p\in\mathcal{P}$, then
$A_{p}f^{\delta}=\min_{r\in\mathcal{Q}}A_{r}f^{\delta}$.

  4. 4.

If $p\in\mathcal{R}$ and $f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$,
then ${A_{p}f^{\delta}=\min_{r\in\mathcal{Q}}A_{r}f^{\delta}}$.

###### Proof.

_Part 1:_ The first claim follows by noting that
${f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)}$ if and only if it solves
[27, Section 1.3.1]

minimize $\displaystyle\quad\frac{1}{2}f^{\top}Af$ (24) subject to
$\displaystyle\quad f\in\mathcal{M}.$

Since $A$ is positive semi-definite and $\mathcal{M}$ is closed and convex,
this minimization problem has a non-empty solution set, showing that
$\operatorname{SOL}(\mathcal{M},A)$ is non-empty.

_Part 2:_ To prove the “only if” side, let
${f^{\delta_{1}},f^{\delta_{2}}\in\operatorname{SOL}(\mathcal{M},A)}$. By
Definition 3.1, we have

$\displaystyle(Af^{\delta_{1}})^{\top}(f^{\delta_{2}}-f^{\delta_{1}})$
$\displaystyle\geq 0,$ (25)
$\displaystyle(Af^{\delta_{2}})^{\top}(f^{\delta_{1}}-f^{\delta_{2}})$
$\displaystyle\geq 0.$

Since $A$ is symmetric and positive semidefinite we have

$\displaystyle 0$
$\displaystyle\leq(f^{\delta_{1}}-f^{\delta_{2}})^{\top}A(f^{\delta_{1}}-f^{\delta_{2}})$
$\displaystyle=(Af^{\delta_{1}})^{\top}(f^{\delta_{1}}-f^{\delta_{2}})-(Af^{\delta_{2}})^{\top}(f^{\delta_{1}}-f^{\delta_{2}})\leq
0,$

where the last inequality follows from (25). Thus, we have
$A(f^{\delta_{1}}-f^{\delta_{2}})=0$. This shows that there exists a $\delta
C\in{}^{n}$ such that $Af^{\delta}=\delta C$ for all
$f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$. Now we show the “if” part of
the claim. Let $f^{\delta_{0}}\in\mathcal{M}$ be a flow satisfying
$Af^{\delta_{0}}=\delta C$. We wish to show that
$f^{\delta_{0}}\in\operatorname{SOL}(\mathcal{M},A)$. Since this set is
nonempty, consider some $f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$. From
what we have shown above, we obtain $Af^{\delta_{0}}=Af^{\delta}$. Therefore,
using this equality, the following derivation holds for any $f\in\mathcal{M}$:

$\displaystyle(Af^{\delta_{0}})^{\top}(f-f^{\delta_{0}})$
$\displaystyle=(Af^{\delta})^{\top}(f-f^{\delta_{0}})$
$\displaystyle=(Af^{\delta})^{\top}(f-f^{\delta}+f^{\delta}-f^{\delta}_{0})$
$\displaystyle=(Af^{\delta})^{\top}(f-f^{\delta})+(Af^{\delta})^{\top}(f^{\delta}-f^{\delta_{0}})$
$\displaystyle=(Af^{\delta})^{\top}(f-f^{\delta})\geq 0.$

Here the final inequality holds since $f\in\mathcal{M}$ and
${f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)}$. We see that
$(Af^{\delta_{0}})^{\top}(f-f^{\delta_{0}})\geq 0$ for all $f\in\mathcal{M}$
and therefore $f^{\delta_{0}}\in\operatorname{SOL}(\mathcal{M},A)$. This shows
that the second claim holds.

_Part 3:_ Let $f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$ and assume for
the sake of contradiction that there exist $p\in\mathcal{P}$ and
$r\in\mathcal{Q}$ such that $f^{\delta}_{p}>0$ and
$A_{p}f^{\delta}>A_{r}f^{\delta}$. Since $f^{\delta}_{p}>0$ and
$r\in\mathcal{Q}$ it follows by definition of $\mathcal{M}$, that
$f:=f^{\delta}-\epsilon(e_{p}-e_{r})\in\mathcal{M}$ for small enough
$\epsilon>0$. Here $e_{i}$ is the vector defined by $(e_{i})_{i}=1$ and
$(e_{i})_{j}=0$ for all $j\neq i$. We then have

$\displaystyle(Af^{\delta})^{\top}(f-f^{\delta})$
$\displaystyle=\epsilon(f^{\delta})^{\top}A(e_{p}-e_{r})$
$\displaystyle=\epsilon(A_{p}f^{\delta}-A_{r}f^{\delta})<0.$

This contradicts $f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$. We conclude
that if $f^{\delta}_{p}\neq 0$ then
${A_{p}f^{\delta}=\min_{r\in\mathcal{Q}}A_{r}f^{\delta}}$, proving the third
claim. The same arguments can be used to prove the last claim. ∎

We note that when the set $\mathcal{R}$ is empty, the first three statements
of the above proposition are equivalent to well-known results on the
existence, essential uniqueness, and properties of the cost of WE, which can
be proven in much the same way. To be specific, when $\mathcal{R}$ is empty,
the set $\mathcal{M}$ is simply the feasible set for the routing game with
$\mathcal{P}=\mathcal{Q}$, and $C(f)=A_{\mathcal{Q}}f+b_{\mathcal{Q}}$, where
$A_{\mathcal{Q}}$ is the matrix $A$ with the rows and columns associated to
paths in $\mathcal{Q}^{c}$ removed, and $b_{\mathcal{Q}}$ is the vector with
the elements associated to $\mathcal{Q}^{c}$ removed. The first two claims
then state the existence and essential uniqueness of WE and the third claim
states that any used path has minimal cost among all paths, which is the WE
condition. When $\mathcal{Q}=\mathcal{R}^{\operatorname{act}}_{D}$ and
$\mathcal{R}=\mathcal{R}^{\operatorname{use}}_{D}$, we have
$\mathcal{M}=\mathcal{M}_{D}$, and the third and fourth claim gain a useful
intuitive interpretation. Namely, the third claim shows that for any
$f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D},A)$, any path in the active
set that gains flow when moving in the direction of $f^{\delta}$ must have the
smallest increase in cost among all active paths. The same holds for any used
path, regardless of how the flow on that path changes.

Finally we are ready to prove Proposition 4.10.

###### Proof of Proposition 4.10.

First we show that $\operatorname{SOL}(\mathcal{M}_{D},A)\subseteq\Gamma_{D}$.
To do this we rely heavily on the conclusions of Proposition 4.12. Note the
parallelism between the set $\mathcal{M}$ given there and the set
$\mathcal{M}_{D}$ used here; that is $\mathcal{M}=\mathcal{M}_{D}$ when we set
$\mathcal{Q}:=\mathcal{R}^{\operatorname{act}}_{D}$ and
$\mathcal{R}:=\mathcal{R}^{\operatorname{use}}_{D}$. Let
$f^{D}\in\mathcal{W}_{D}$ be a WE satisfying
$f^{D}_{\mathcal{R}^{\operatorname{use}}_{D}}>0$. Such a WE exists since the
set $\mathcal{W}_{D}$ is convex. To see this, let
$r\in\mathcal{R}^{\operatorname{use}}_{D}$. By definition of the used set
there exists a WE $f^{r}\in\mathcal{W}_{D}$ satisfying $f^{r}_{r}>0$. Setting
$f^{D}=\sum_{r\in\mathcal{R}^{\operatorname{use}}_{D}}\mu_{r}f^{r}$, where
$\mu_{r}\in(0,1)$ for all $r\in\mathcal{R}^{\operatorname{use}}_{D}$ and
$\sum_{r\in\mathcal{R}^{\operatorname{use}}_{D}}\mu_{r}=1$ it follows that
$f^{D}\in\mathcal{W}_{D}$ and
$f^{D}_{\mathcal{R}^{\operatorname{use}}_{D}}>0$. Now, for a given
$f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D},A)$ and $\epsilon>0$ we write

$f^{D+\epsilon}:=f^{D}+\epsilon f^{\delta}.$

Note that since $f^{D}_{\mathcal{R}^{\operatorname{use}}_{D}}>0$ and
$f^{\delta}\in\mathcal{M}_{D}$ we have $f^{D+\epsilon}\geq 0$ as long as
$\epsilon>0$ is small enough. We will show that for such small enough
$\epsilon$ we have $f^{D+\epsilon}\in\mathcal{W}_{D+\epsilon}$ which then
implies ${f^{\delta}\in\Gamma_{D}}$. Let $p\in\mathcal{P}$ be a path such that
$f^{D+\epsilon}_{p}>0$. This implies that either (a) $f^{D}_{p}>0$ or (b)
$f^{\delta}_{p}>0$. If $f^{D}_{p}>0$ it follows that
${p\in\mathcal{R}^{\operatorname{use}}_{D}}$. In addition, Proposition 4.12-4
tells us that
${A_{p}f^{\delta}=\min_{r\in\mathcal{R}^{\operatorname{act}}_{D}}A_{r}f^{\delta}}$.
Similarly, when $f^{\delta}_{p}>0$, the definition of $\mathcal{M}_{D}$ shows
that $p\in\mathcal{R}^{\operatorname{act}}_{D}$ and so from Proposition
4.12-3, we have
${A_{p}f^{\delta}=\min_{r\in\mathcal{R}^{\operatorname{act}}_{D}}A_{r}f^{\delta}}$.
Also for both cases (a) and (b), we have
$p\in\mathcal{R}^{\operatorname{act}}_{D}$ and so
${C_{p}(f^{D})=\min_{r\in\mathcal{P}}C_{r}(f^{D})}$. Using these properties
and Proposition 4.6, it follows that

$\displaystyle C_{p}(f^{D+\epsilon})$ $\displaystyle=C_{p}(f^{D})+\epsilon
A_{p}f^{\delta}$
$\displaystyle\leq\min_{r\in\mathcal{P}}\bigl{(}C_{r}(f^{D})+\epsilon
A_{r}f^{\delta}\bigr{)}$
$\displaystyle=\min_{r\in\mathcal{P}}C_{r}(f^{D+\epsilon}).$

Thus $f^{D+\epsilon}_{p}>0$ implies
${C_{p}(f^{D+\epsilon})=\min_{r\in\mathcal{P}}C_{r}(f^{D+\epsilon})}$ which
means the the WE condition (5) is satisfied, and it follows that
$f^{D+\epsilon}\in\mathcal{W}_{D+\epsilon}$. Therefore,
${\operatorname{SOL}(\mathcal{M}_{D},A)\subseteq\Gamma_{D}}$.

To show $\Gamma_{D}\subseteq\operatorname{SOL}(\mathcal{M}_{D},A)$, let
$f^{\delta}\in\Gamma_{D}$. Since
$\operatorname{SOL}(\mathcal{M}_{D},A)\subseteq\Gamma_{D}$, we then know that
there exists an
${f^{\delta_{0}}\in\Gamma_{D}\cap\operatorname{SOL}(\mathcal{M}_{D},A)}$. By
Lemma 4.11 we have $f^{\delta}\in\mathcal{M}_{D}$, and by Proposition 4.6 we
have ${Af^{\delta}=Af^{\delta_{0}}}$. Therefore, it follows from Proposition
4.12 that ${f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D},A)}$. In
conclusion, we obtain ${\Gamma_{D}=\operatorname{SOL}(\mathcal{M}_{D},A)}$. ∎

We next illustrate the equivalence established in Proposition 4.10 for the
routing game associated to Figure 3, as discussed in Example 4.1b. Consider
the demand $D=1$. Using (14) and (15) we obtain
${\mathcal{R}^{\operatorname{act}}_{D}=\\{p_{1},p_{2},p_{3},p_{4}\\}}$ and
${\mathcal{R}^{\operatorname{use}}_{D}=\\{p_{3}\\}}$. Thus, by definition
$\mathcal{M}_{D}=\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f^{\delta}_{1},f^{\delta}_{2},f^{\delta}_{4}\geq
0\\}$. We also have ${\ker(A)=\\{f\in\real\;|\;f_{1}=f_{2}=-f_{3}\\}}$. Note
that ${\ker(A)\cap\mathcal{M}_{D}}$ is nonempty and in fact, from (16), we
have $\Gamma_{D}=\ker(A)\cap\mathcal{M}_{D}$. Therefore, we will show next
that $\operatorname{SOL}(\mathcal{M}_{D},A)=\ker(A)\cap\mathcal{M}_{D}$, which
corroborates the claim of Proposition 4.10. Select some
$f\in\ker(A)\cap\mathcal{M}_{D}$. Since $A$ is positive semi-definite we
obtain

$(Af^{\delta})^{\top}(f-f^{\delta})\leq 0$

for any $f^{\delta}\in\mathcal{M}_{D}$. Using (9) in the definition of
$\operatorname{SOL}(\mathcal{M}_{D},A)$ it follows that in order for
${f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D},A)}$ to hold, we need
$f^{\delta}\in\ker(A)\cap\mathcal{M}_{D}$. Furthermore, when
${f^{\delta}\in\ker(A)\cap\mathcal{M}_{D}}$, we have
$(Af^{\delta})^{\top}(f-f^{\delta})=0$ for any $f\in\mathcal{M}_{D}$. In other
words, $\operatorname{SOL}(\mathcal{M}_{D},A)=\ker(A)\cap\mathcal{M}_{D}$.
From (16), we then have $\Gamma_{D}=\operatorname{SOL}(\mathcal{M}_{D},A)$, as
claimed.

The established results have interesting consequences regarding the evolution
of the WE in the final interval $(D_{M},\infty)$. However, before we present
these, we finish our analysis of the evolution of the set of WE by
establishing some basic properties of the set $\Gamma_{D}$, which are now
straightforward consequences of Proposition 4.10. First, note that
$\Gamma_{D}$ is closed, which follows from the fact that $\mathcal{M}_{D}$ is
closed [27, Section 1.1]. In addition, $\Gamma_{D}$ is convex [27, Theorem
2.3.5].

######  Corollary 4.13.

Let $(\mathcal{P},\mathcal{C},D)$ be given. Then $\Gamma_{D}$ is nonempty,
closed, and convex.

In Example 4.1 we noted that the non-negative real line was divided into
intervals in which the set of directions of increase $\Gamma_{D}$ remains
constant. Using Propostion 4.10, we can show that this is not an artifact of
the considered example and that it holds for any routing game.

######  Lemma 4.14.

($\Gamma_{D}$ is constant between breakpoints in $\mathcal{D}$): Let
$(\mathcal{P},\mathcal{C})$ and ${D_{i},D_{i+1}\in\mathcal{D}}$ be given.
There exists a set $\Gamma^{i}\subset\mathcal{H}_{1}$ such that for all
${D\in(D_{i},D_{i+1})}$ we have $\Gamma_{D}=\Gamma^{i}$. Furthermore,
$\Gamma_{D_{i}}\subseteq\Gamma^{i}$ and
$\Gamma^{i+1}\cap\Gamma^{i}=\emptyset$.

###### Proof.

The existence of $\Gamma^{i}$ such that $\Gamma_{D}=\Gamma^{i}$ for all
${D\in(D_{i},D_{i+1})}$ follows directly from Proposition 4.10 and observing
that the set $\mathcal{M}_{D}$ is same for all $D\in(D_{i},D_{i+1})$, which
follows from Corollary 3.6. Let $f^{\delta}\in\Gamma_{D_{i}}$ and pick
$T\in(D_{i},D_{i+1}]$, $f^{D_{i}}\in\mathcal{W}_{D_{i}}$ and
$f^{T}\in\mathcal{W}_{T}$ such that

$f^{T}=f^{D_{i}}+(T-D_{i})f^{\delta}.$

Pick $\mu\in(0,1)$ and let $T_{\mu}=\operatorname{coco}_{\mu}(D_{i},T)$ and
$f^{\mu}=\operatorname{coco}_{\mu}(f^{D_{i}},f^{T})$. Note that
${T_{\mu}\in(D_{i},D_{i+1})}$, ${T\in(T_{\mu},D_{i+1})}$, and from Corollary
4.4, $f^{\mu}\in\mathcal{W}_{T_{\mu}}$. Moreover,
$f^{T}=f^{\mu}+(T-T_{\mu})f^{\delta}$. Therefore
$f^{\delta}\in\Gamma_{T_{\mu}}=\Gamma^{i}$, showing that
$\Gamma_{D_{i}}\subseteq\Gamma^{i}$. For the last statement, note that if
there exists $f^{\delta}\in\Gamma^{i}\cap\Gamma^{i+1}$ then the first
conclusion of Proposition 4.6 implies $\delta C^{i+1}=\delta C^{i}$,
contradicting the third conclusion of Proposition 4.6. Therefore
$\Gamma^{i+1}\cap\Gamma^{i}=\emptyset$. ∎

###  4.2 Obtaining $D_{M}$

In this section, we derive several properties pertaining to the interval
$(D_{M},\infty)$, where we recall that $D_{M}$ is the final finite-valued
breakpoint in $\mathcal{D}$. In particular, we give a rigorous way in which
the value $D_{M}$ can be computed. In the process and to its own merit we find
the directions in which $\lambda^{\operatorname{vec}}$ varies over
$(D_{M},\infty)$, as well as associated directions of increase in
$\Gamma^{M}$. This then allows us to obtain an expression for
$\lambda^{\operatorname{WE}}(D)$ for any $D\geq D_{M}$. Using this we can
compute the final active set $\mathcal{J}^{\operatorname{act}}_{M}$, after
which the value of $D_{M}$ can be obtained.

We start with the result that $\Gamma^{M}$ overlaps with
$\operatorname{SOL}(\mathcal{F}_{1},A)$. This gives us a direct method for
identifying $\delta C^{M}$, which is the direction in which the WE cost-vector
$\lambda^{\operatorname{vec}}$ evolves in the interval $(D_{M},\infty)$. This
will also prove remarkably useful later on, when investigating Braess’s
paradox.

######  Proposition 4.15.

(Finding $\delta C_{M}$ by solving $\operatorname{SOL}(\mathcal{F}_{1},A)$):
Let $(\mathcal{P},\mathcal{C})$ and ${D\geq
D_{M}=\max\big{(}\mathcal{D}\setminus\\{\infty\\}\big{)}}$ be given. Then, we
have:

  1. 1.

$\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ is non-empty,

  2. 2.

$Af^{\delta}=\delta C^{M}$ for all
$f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)$,

  3. 3.

$\delta\lambda^{M}=\min_{r\in\mathcal{P}}\delta C^{M}_{p}$.

###### Proof.

We note that the second statement follows from the first. To see this, let
${f^{\delta}\in\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)}$. From
Proposition 4.6 we have $Af^{\delta}=\delta C^{M}$, and Proposition 4.12 then
gives us $A\widetilde{f}^{\delta}=\delta C^{M}$ for all
$f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)$. Thus, to prove the first
two claims, it is enough to show that
$\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ is non-empty, which we
now do.

First we show that $\Gamma_{D}\cap\mathcal{F}_{1}$ is non-empty. For any
${f^{\delta}\in\Gamma_{D}}$ we already have ${f^{\delta}\in\mathcal{H}_{1}}$.
Therefore to establish that $\Gamma_{D}\cap\mathcal{F}_{1}$ is non-empty it is
enough to prove the existence of $f^{\delta}\in\Gamma_{D}$ such that
$f^{\delta}\geq 0$. This we will do by constucting a sequence
$\\{f^{\delta,i}\\}_{i\in\mathbb{N}}\subset\Gamma_{D}$ that converges to an
$f^{\delta}$ satisfying $f^{\delta}\geq 0$. Then, using the fact that
$\Gamma_{D}$ is closed (as stated in Corollary 4.13), we conclude that
$f^{\delta}\in\mathcal{F}_{1}\cap\Gamma_{D}$.

Let $f^{D}\in\mathcal{W}_{D}$, and let $\\{f^{T_{i}}\\}_{i\in\mathbb{N}}$ be a
sequence of WE satisfying $f^{T_{i}}\in\mathcal{W}_{T_{i}}$, where $D_{M}\leq
D<T_{1}$, $T_{i}<T_{i+1}$ for all $i$, and
$\lim_{i\rightarrow\infty}T_{i}=\infty$. We then define the sequence
$\\{f^{\delta,i}\\}_{i\in\mathbb{N}}$ by setting

$f^{\delta,i}:=(T_{i}-D)^{-1}(f^{T_{i}}-f^{D}).$

Since $D\geq D_{M}$ and $T_{i}>D$ for all $i\in\mathbb{N}$, it follows from
Corollary 4.4 that any convex combination of $f^{D}$ and $f^{T_{i}}$ is a WE;
that is, for any $\epsilon\in[0,T_{i}-D)$ we find that $f^{D}+\epsilon
f^{\delta,i}$ is a WE. By Definition 4.5, we deduce that
$f^{\delta,i}\in\Gamma_{D}$ for all $i\in\mathbb{N}$. In addition, the
sequence $\\{f^{\delta,i}\\}_{i\in\mathbb{N}}$ is bounded. To show this, let
$t:=\max_{r\in\mathcal{P}}f^{D}_{r}$. Since $f^{T_{i}}\geq 0$ for all
$i\in\mathbb{N}$ we obtain $(f^{T_{i}}_{r}-f^{D}_{r})\geq-t$ for all
$r\in\mathcal{P}$ and all $i\in\mathbb{N}$. Therefore,
$f^{\delta,i}_{r}\geq-t(T_{i}-D)^{-1}$ for all $r\in\mathcal{P}$ and
$i\in\mathbb{N}$. Letting
$\mathcal{R}_{i}:=\\{r\in\mathcal{P}\;|\;f^{\delta,i}_{r}<0\\}$ it follows
that

$\sum_{r\in\mathcal{R}_{i}}f^{\delta}_{r}\geq-nt(T_{i}-D)^{-1}.$

Since $f^{\delta,i}\in\mathcal{H}_{1}$ the above implies that
$f^{\delta,i}_{r}\leq nt(T_{i}-D)^{-1}+1$ for all $r\in\mathcal{P}$. Since
$T_{1}\leq T_{i}$ for all $i\in\mathbb{N}$ we get ${-t(T_{1}-D)^{-1}\leq
f^{\delta,i}_{r}\leq-nt(T_{1}-D)^{-1}+1}$ for all $r\in\mathcal{P}$ and
$i\in\mathbb{N}$. In other words, $\\{f^{\delta,i}\\}_{i\in\mathbb{N}}$ is
bounded. Therefore, the sequence contains a subsequence, denoted
$\\{f^{\delta,i_{k}}\\}_{k\in\mathbb{N}}$, that converges. For this
subsequence, since $\lim_{k\rightarrow\infty}T_{i_{k}}=\infty$ it follows that
$\lim_{k\to\infty}f^{\delta,i_{k}}_{r}\geq 0$ for all $r\in\mathcal{P}$. We
see that

$f^{\delta}:=\lim_{k\to\infty}f^{\delta,i_{k}}\geq 0.$

Since $\Gamma_{D}$ is closed, it follows that $f^{\delta}\in\Gamma_{D}$. Thus,
there exists $f^{\delta}\in\Gamma_{D}\cap\mathcal{F}_{1}$.

The final step is to show that $f^{\delta}\in\Gamma_{D}\cap\mathcal{F}_{1}$
implies ${f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)}$. This we do by
showing that $f^{\delta}$ is a WE of the routing game with the path cost
function $\widetilde{C}(f)=Af$ and the feasible set $\mathcal{F}_{1}$.

Given an $f^{\delta}\in\Gamma_{D}\cap\mathcal{F}_{1}$, let $p\in\mathcal{P}$
satisfy $f^{\delta}_{p}>0$. By definition of the set $\Gamma_{D}$ we then know
that for some $T>D$ there exist WE $f^{T}\in\mathcal{W}_{T}$ satisfying
$f^{T}_{p}>0$. Since $D\geq D_{M}$ this implies that the path $p$ is used, and
therefore active, in the interval $(D_{M},\infty)$. In other words,
$p\in\mathcal{J}^{\operatorname{act}}_{M}$.

For the sake of contradiction assume that $r\in\mathcal{P}$ satsifies
$A_{r}f^{\delta}<A_{p}f^{\delta}$. Since $f^{\delta}\in\Gamma_{D}$ we have
$Af^{\delta}=\delta C^{M}$, which implies
$\lambda^{\operatorname{vec}}(T)=\lambda^{\operatorname{vec}}(D)+(T-D)Af^{\delta}$
for any $T\in(D,\infty)$. It follows that for large enough $T$ we have
$\lambda^{\operatorname{vec}}_{r}(T)<\lambda^{\operatorname{vec}}_{p}(T)$,
which implies that $p\notin\mathcal{R}^{\operatorname{act}}_{T}$. Since
${T>D}$, and $D\geq D_{M}$ this implies that for some ${T\in(D_{M},\infty)}$,
the path $p$ is not active. In other words
$p\notin\mathcal{J}^{\operatorname{act}}_{M}$. We have arrived at a
contradiction, and therefore we conclude that
$A_{p}f^{\delta}=\min_{r\in\mathcal{P}}A_{r}f^{\delta}$. In other words,
$f^{\delta}$ is a WE of the routing game with the path cost function
$\widetilde{C}(f)=Af$ and the feasible set $\mathcal{F}_{1}$. By Proposition
3.2 this implies $f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)$.

For the third statement, note that when $\delta C^{M}_{r}<\delta\lambda^{M}$
for some $r\in\mathcal{P}$, this implies that in the interval
$(D_{M},\infty)$, the cost of path $r$ under WE increases at a slower rate
than the WE-cost. Since the cost of all paths in this interval increases at a
constant rate, this implies that at some demand $T>D_{M}$,
$\lambda^{\operatorname{vec}}_{r}(T)<\lambda^{\operatorname{WE}}(T)$. However,
the WE-cost is the minimal cost of all paths under WE, and therefore this is
not possible. Thus we have $\delta\lambda^{M}=\min_{r\in\mathcal{P}}\delta
C^{M}$. This concludes the proof. ∎

The intuition behind the above result is as follows. Consider a demand $D$ in
the final interval $[D_{M},\infty)$, for which we have
$\Gamma_{D}\subseteq\Gamma^{M}$ by Lemma 4.14, and consider the set of
directions in which the WE moves as demand increases from $D$; that is,
consider the set $\Gamma_{D}$. Since the interval $[D_{M},\infty)$ stretches
to infinity without encountering any other breakpoint, there must be some
direction in $\Gamma_{D}$ along which we can move indefinitely. For any
direction $f^{\delta}$ which takes flow from some path, that is the vector has
some negative component, one can only move a finite amount in that direction
as sooner or later the flow on that path then becomes zero, and we can no
longer move in that direction. Thus, there must be some
$f^{\delta}\in\Gamma_{D}\cap\mathcal{F}_{1}$. In addition, when moving in such
a “nonnegative” direction of increase the cost of all paths receiving flow
must remain minimal to satisfy the WE conditions. Therefore, the cost of paths
receiving flow must show the minimal increase among all paths. This implies
that in fact $f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)$, which in
turn shows the above result. Note that these observations do not imply
$\operatorname{SOL}(\mathcal{M}_{D},A)=\operatorname{SOL}(\mathcal{F}_{1},A)$,
as for instance demonstrated in Example 4.1b. There we see that for any $D\geq
D_{M}=1$ there exist $f^{\delta}\in\Gamma_{D}$ and $p\in\mathcal{P}$ such that
$f^{\delta}_{p}<0$.

Having obtained $\delta C^{M}$ by solving
$\operatorname{SOL}(\mathcal{F}_{1},A)$, we now give a full characterization
of $\Gamma^{M}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ in the below result.
Note that the result considers $\Gamma_{D}$ for some $D\geq D_{M}$ instead of
$\Gamma^{M}$, but whenever $D>D_{M}$ we have $\Gamma_{D}=\Gamma^{M}$.

######  Proposition 4.16.

(Obtaining $\Gamma^{M}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ ): Let
$(\mathcal{P},\mathcal{C})$ and $D\geq D_{M}$ be given. The set
$\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ is equal to the set of
solutions of the following minimization problem:

minimize $\displaystyle\beta^{\top}f^{\delta}$ (26) subject to $\displaystyle
Af^{\delta}=\delta C^{M},$ $\displaystyle f^{\delta}\in\mathcal{F}_{1}.$

###### Proof.

We start with the observation that taken together Propositions 4.12 and 4.15
imply ${f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)}$ if and only if
$f^{\delta}\in\mathcal{F}_{1}$ and $Af^{\delta}=\delta C^{M}$. In other words,
the feasibility set of the problem (26) is equal to
$\operatorname{SOL}(\mathcal{F}_{1},A)$. Thus, our goal is to show that
$f^{\delta}$ is an optimal solution of (26) if and only if it is feasible and
$f^{\delta}\in\Gamma_{D}$.

We proceed with the “if” part, that is, if $f^{\delta}\in\Gamma_{D}$ and is a
feasible point of (26), then it is an optimal solution of (26). To do so, let
$f^{D_{M}}\in\mathcal{W}_{D_{M}}$ and consider the minimization problem

minimize $\displaystyle(f^{\delta})^{\top}(Af^{D_{M}}+\beta)$ (27) subject to
$\displaystyle Af^{\delta}=\delta C^{M},$ $\displaystyle
f^{\delta}\in\mathcal{F}_{1}.$

This minimization problem is actually equivalent to (26), meaning that
$f^{\delta}$ is an optimal solution of (26) if an only if it is so for (27).
To see this, note that since $f^{D_{M}}\in\mathcal{W}_{D_{M}}$, we have
$Af^{D_{M}}+\beta=\lambda^{\operatorname{vec}}(D_{M})$. Therefore, if
$p\in\mathcal{P}$ satisfies $f^{D_{M}}_{p}>0$, then it follows that
$p\in\mathcal{R}^{\operatorname{use}}_{D_{M}}$, and by Lemma 4.3 we then have
$p\in\mathcal{J}^{\operatorname{use}}_{M}$. We see that $p$ is in the used set
on the interval $[D_{M},\infty)$, and therefore it must maintain minimal cost
under WE among all paths as the demand increase from $D$ to infinity.
Consequently ${\delta C^{M}_{p}=\min_{r\in\mathcal{P}}\delta
C^{M}_{r}=\delta\lambda^{M}}$. Since $D\geq D_{M}$ we also have, by
Proposition 4.6, that $\delta C^{M}=Af^{\delta}$ for any
$f^{\delta}\in\Gamma_{D}$. Therefore $A_{p}f^{\delta}=\delta\lambda^{M}$
whenever $f^{D_{M}}_{p}>0$. Since $f^{D_{M}}\in\mathcal{F}_{D_{M}}$ this
implies

$(f^{\delta})^{\top}Af^{D_{M}}=D_{M}\delta\lambda^{M}\quad\text{ for all
}f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A).$ (28)

We see that the term $(f^{\delta})^{\top}Af^{D_{M}}$ is constant over the
feasible set of (27). Therefore $f^{\delta}$ solves (27) if and only if it
minimizes the term $\beta^{\top}f^{\delta}$ over the feasible set. This is
exactly the objective function of (26), and since the feasible sets of (26)
and (27) are the same, this shows that (26) and (27) have the same set of
optimal solutions.

Next we obtain a lower bound on the objective function of (27). We have
${\lambda^{\operatorname{vec}}(D_{M})=Af^{D_{M}}+\beta}$, and in addition
$\lambda^{\operatorname{WE}}(D_{M})=\min_{r\in\mathcal{P}}\lambda^{\operatorname{vec}}_{r}(D_{M})$.
In other words,
$\lambda^{\operatorname{vec}}(D_{M})\geq\lambda^{\operatorname{WE}}(D_{M})\mymathbf{1}$,
where $\mymathbf{1}$ is the vector of ones. For any
$f^{\delta}\in\mathcal{F}_{1}$ all elements of $f^{\delta}$ are nonnegative,
and sum to one, and therefore it follows that for all
$f^{\delta}\in\operatorname{SOL}(\mathcal{F}_{1},A)$ we have

$\displaystyle(f^{\delta})^{\top}(Af^{D_{M}}+\beta)$
$\displaystyle=(f^{\delta})^{\top}\lambda^{\operatorname{vec}}(D_{M})$
$\displaystyle\geq\lambda^{\operatorname{WE}}(D_{M}).$

Next we show that any
$f^{\delta}\in\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ achieves
this lower bound. We know from Proposition 4.15 that
$\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ is non-empty, so we can
pick
${\widetilde{f}^{\delta}\in\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)}$.
By Proposition 4.10 we then have
$\widetilde{f}^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D},A)$. Now let
$p\in\mathcal{P}$ satisfy $\widetilde{f}^{\delta}_{p}>0$. From the definition
of $\Gamma_{D}$ it follows that
$p\in\mathcal{R}^{\operatorname{use}}_{T}=\mathcal{J}^{\operatorname{use}}_{M}$
for some $T>D$, and by Lemma 4.3 this implies
$p\in\mathcal{R}^{\operatorname{act}}_{D_{M}}$. Therefore
$\lambda^{\operatorname{vec}}_{p}(D_{M})=\lambda^{\operatorname{WE}}(D_{M})$.
Since $\widetilde{f}^{\delta}\in\mathcal{F}_{1}$ it follows that

$(\widetilde{f}^{\delta})^{\top}\lambda^{\operatorname{vec}}(D_{M})=\lambda^{\operatorname{WE}}(D_{M}),$
(29)

showing that $\widetilde{f}^{\delta}$ achieves the lower bound we established
for (27). In other words, $\widetilde{f}^{\delta}$ is a solution of (27), and
is therefore also a solution to (26). This shows that
$\Gamma_{D}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$ is contained within the
set of solutions of (26).

We now proceed with the “only if” part. Let $f^{\delta}$ be a solution of
(26), and therefore also a solution of (27). We know from the derivation of
(29) that this implies
$(f^{\delta})^{\top}\lambda^{\operatorname{vec}}(D_{M})=\lambda^{\operatorname{WE}}(D_{M})$.
Since
${\lambda^{\operatorname{vec}}(D_{M})\geq\lambda^{\operatorname{WE}}(D_{M})\mymathbf{1}}$
and $f^{\delta}\in\mathcal{F}_{1}$ this gives us

$\lambda^{\operatorname{vec}}_{p}(D_{M})=\lambda^{\operatorname{WE}}(D_{M})\quad\text{
for all }p\in\mathcal{P}\text{ satisfying }f^{\delta}_{p}>0.$

In other words, $f^{\delta}_{p}>0$ implies
$p\in\mathcal{R}^{\operatorname{act}}_{D_{M}}$. Together with
${f^{\delta}\in\mathcal{F}_{1}}$ this shows that
$f^{\delta}\in\mathcal{M}_{D_{M}}$. Thus we have
$f^{\delta}\in\mathcal{M}_{D_{M}}$ and $Af^{\delta}=\delta C^{M}$. From
Proposition 4.10 we have
$\Gamma_{D_{M}}=\operatorname{SOL}(\mathcal{M}_{D_{M}},A)$, from Proposition
4.6 we have $A\widehat{f}^{\delta}=\delta C^{M}$ for all
$\widehat{f}^{\delta}\in\Gamma_{D_{M}}$ and from Proposition 4.12 it then
follows that $\widehat{f}^{\delta}\in\Gamma_{D_{M}}$ if and only if
$\widehat{f}^{\delta}\in\mathcal{M}_{D_{M}}$ and $A\widehat{f}^{\delta}=\delta
C^{M}$. Thus we see that $f^{\delta}\in\Gamma_{D_{M}}$. From Corollary 4.14 we
have $\Gamma_{D_{M}}\subseteq\Gamma^{M}$, and thus we conclude that
$f^{\delta}\in\Gamma_{D}$ for any $D\geq D_{M}$. This completes the proof. ∎

Next, we use the obtained results to express $\lambda^{\operatorname{WE}}(D)$
for any $D\geq D_{M}$.

######  Lemma 4.17.

(Obtaining $\lambda^{\operatorname{WE}}(D)$ for $D\geq D_{M}$): Let
$(\mathcal{P},\mathcal{C})$ and $D\geq D_{M}$ be given. In addition, let
$\bar{\beta}=\beta^{\top}f^{\delta}$, where $f^{\delta}$ is a solution of
(26). Then, we have

$\lambda^{\operatorname{WE}}(D)=\delta\lambda^{M}D+\bar{\beta}.$

###### Proof.

First pick $D>D_{M}$ and let $f^{\delta}$ be a solution of (26). From
Proposition 4.16, we have
$f^{\delta}\in\Gamma^{M}\cap\operatorname{SOL}(\mathcal{F}_{1},A)$.
Additionally,
$\lambda^{\operatorname{WE}}(D)=\lambda^{\operatorname{WE}}(D_{M})+(D-D_{M})\delta\lambda^{M}$
holds. Now consider the expression

$(f^{\delta})^{\top}\Big{(}A\big{(}f^{D_{M}}+(D-D_{M})f^{\delta}\big{)}+\beta\Big{)},$

where $f^{D_{M}}\in\mathcal{W}_{D_{M}}$. Since $f^{D_{M}}\geq 0$ and
$f^{\delta}\geq 0$ it follows that $f^{D_{M}}+(D-D_{M})f^{\delta}\geq 0$. In
combination with ${f^{\delta}\in\Gamma^{M}}$, this shows that
$f^{D_{M}}+(D-D_{M})f^{\delta}\in\mathcal{W}_{D}$. Thus, we have
$A\big{(}f^{D_{M}}+(D-D_{M})f^{\delta}\big{)}+\beta=\lambda^{\operatorname{vec}}(D)$.
By the same arguments used to derive (29), we obtain
${(f^{\delta})^{\top}\lambda^{\operatorname{vec}}(D)=\lambda^{\operatorname{WE}}(D)}$.
Thus we have

$\displaystyle(f^{\delta})^{\top}\Big{(}A\big{(}f^{D_{M}}+(D-D_{M})f^{\delta}\big{)}+\beta\Big{)}$
$\displaystyle=(f^{\delta})^{\top}\lambda^{\operatorname{vec}}(D)$ (30)
$\displaystyle=\lambda^{\operatorname{WE}}(D)$

We also have the following:

$\displaystyle(f^{\delta})^{\top}\Big{(}A\big{(}f^{D_{M}}+(D-D_{M})f^{\delta}\big{)}+\beta\Big{)}$
(31)
$\displaystyle=(f^{\delta})^{\top}Af^{D_{M}}+(D-D_{M})(f^{\delta})^{\top}Af^{\delta}+\beta^{\top}f^{\delta}.$

From (28) we have $(f^{\delta})^{\top}Af^{D_{M}}=D_{M}\delta\lambda^{M}$. From
arguments similar to those for (29) we also find
${(D-D_{M})(f^{\delta})^{\top}Af^{\delta}=(D-D_{M})\delta\lambda^{M}}$. These
facts combined with expressions (30) and (31) yield

$\displaystyle\lambda^{\operatorname{WE}}(D)$
$\displaystyle=(f^{\delta})^{\top}\Big{(}A\big{(}f^{D_{M}}+(D-D_{M})f^{\delta}\big{)}+\beta\Big{)}$
$\displaystyle=D\delta\lambda^{M}+\beta^{\top}f^{\delta}.$

Since $f^{\delta}$ is a solution of (26) we therefore have

$\lambda^{\operatorname{WE}}(D)=D\delta\lambda^{M}+\bar{\beta}.$

The above holds for any $D>D_{M}$, and from Corollary 4.7 it follows that the
equality also holds for $D=D_{M}$, which concludes the proof. ∎

Thus far we have characterized how $\lambda^{\operatorname{vec}}$ and
$\lambda^{\operatorname{WE}}$ vary over the final interval. Using the latter,
our next result shows how we can use this information to obtain
$\mathcal{J}^{\operatorname{act}}_{M}$.

######  Lemma 4.18.

(Obtaining $\mathcal{J}^{\operatorname{act}}_{M}$): For a given
$(\mathcal{P},\mathcal{C},D)$, let $f^{\delta}$ be an optimal solution of
(26). Consider the following index sets:

$\displaystyle\mathcal{I}_{1}$
$\displaystyle=\\{r\in\mathcal{P}\;|\;f^{\delta}_{r}>0\\},$
$\displaystyle\mathcal{I}_{2}$
$\displaystyle=\\{r\in\mathcal{P}\;|\;f^{\delta}_{r}=0,\hskip 2.0pt\delta
C^{M}_{r}>\delta\lambda^{M}\\},$ $\displaystyle\mathcal{I}_{3}$
$\displaystyle=\\{r\in\mathcal{P}\;|\;f^{\delta}_{r}=0,\hskip 2.0pt\delta
C^{M}_{r}=\delta\lambda^{M}\\}.$

Let $f^{*}$ be a solution of the following convex minimization problem:

minimize $\displaystyle\quad f^{\top}Af+f^{\top}\beta$ (32a) subject to
$\displaystyle\quad f_{r}=0$ $\displaystyle\forall r\in\mathcal{I}_{2},$ (32b)
$\displaystyle\quad f_{r}\geq 0$ $\displaystyle\forall r\in\mathcal{I}_{3},$
(32c) $\displaystyle\quad C_{r}(f)\geq\delta\lambda^{M}D+\bar{\beta}$
$\displaystyle\forall r\in\mathcal{I}_{3},$ (32d) $\displaystyle\quad
C_{r}(f)=\delta\lambda^{M}D+\bar{\beta}$ $\displaystyle\forall
r\in\mathcal{I}_{1},$ (32e) $\displaystyle\quad\mymathbf{1}^{\top}f=D.$ (32f)

We then have that $p\in\mathcal{J}^{\operatorname{act}}_{M}$ if and only if
$\delta C_{p}^{M}=\delta\lambda^{M}$ and
$C_{p}(f^{*})=\delta\lambda^{M}D+\bar{\beta}$.

The following is a long proof, and for this reason we first provide some
intuition to clarify the underlying ideas. The optimization problem (32) is
designed with the aim of identifying the set
$\mathcal{J}^{\operatorname{act}}_{M}$. Note that due to the previous results
we can already obtain $\delta C^{M}$ and $\delta\lambda^{M}$ as well as an
element $f^{\delta}$ of $\Gamma^{M}$, which provide quite some information
about $\mathcal{J}^{\operatorname{act}}_{M}$. For instance, on the interval
$(D_{M},\infty)$, the cost under WE of any path $r\in\mathcal{I}_{2}$
increases faster than $\delta\lambda^{M}$, where the latter is the minimum
over all paths of the increase in cost under WE. Thus, the cost of these paths
can not remain minimal on this interval, which immediately shows that
$\mathcal{J}^{\operatorname{act}}_{M}\cap\mathcal{I}_{2}=\emptyset$.
Similarly, since $f^{\delta}\in\Gamma^{M}$ we know that any path in
$\mathcal{I}_{1}$ is used under WE in the interval $(D_{M},\infty)$, which
shows that $\mathcal{I}_{1}\subseteq\mathcal{J}^{\operatorname{act}}_{M}$.
What remains is to find which paths in $\mathcal{I}_{3}$ are in
$\mathcal{J}^{\operatorname{act}}_{M}$, which can be done by solving (32). The
reason that this works is that (32) is designed in such a way that for any
solution $f^{*}$ the flow $f^{*}+\epsilon f^{\delta}$ is a WE as long as
$\epsilon>0$ is large enough. Appropriately picking $\epsilon$ will then
ensure that the constructed flow is a WE with demand in $(D_{M},\infty)$.
Consequently the active set $\mathcal{J}^{\operatorname{act}}_{M}$ is given by
the paths that have minimal cost given the flow $f^{*}+\epsilon f^{\delta}$.
Using the conditions imposed by the constraints we can show that these are
exactly the paths for which $\delta C_{p}^{M}=\delta\lambda^{M}$ and
$C_{p}(f^{*})=\delta\lambda^{M}D+\bar{\beta}$, completing the argument. Before
we start the proof, we explicitely note that the result holds for _any_
$D\in\real$. Therefore it can be used without prior knowledge of $D_{M}$.

###### Proof of Lemma 4.18.

We start by noting that from (26) we have $f^{\delta}\geq 0$ and from
Proposition 4.15 we have $\delta\lambda^{M}=\min_{r\in\mathcal{P}}\delta
C^{M}$. This implies that
$\mathcal{P}=\mathcal{I}_{1}\cup\mathcal{I}_{2}\cup\mathcal{I}_{3}$.

The first part of the proof is now to show that

$\displaystyle(f^{*})^{\top}Af^{*}+(f^{*})^{\top}\beta=D(\delta\lambda^{M}D+\bar{\beta})$

holds for any optimizer $f^{*}$ of (32). To prove that this is true, we
construct a specific optimal solution $f^{\prime}$ of (32) in the following
way. Let $f^{T}\in\mathcal{W}_{T}$ for some $T>D_{M}$, and let

${f^{\prime}:=f^{T}+(D-T)f^{\delta}}.$

To show that $f^{\prime}$ is an optimal solution of (32) our first step is to
show that it satisfies all the constraints. Then we obtain the objective
function value $(f^{\prime})^{\top}Af^{\prime}+(f^{\prime})^{\top}\beta$ and
finally we show that this value is optimal, proving that $f^{\prime}$ is a
solution of (32).

_Step 1: $f^{\prime}$ is feasible:_ We start by considering the constraints on
the paths in $\mathcal{I}_{1}$ given in (32e). Note that since $f^{\delta}$ is
a solution of (26), Proposition 4.16 gives $f^{\delta}\in\Gamma_{T}$, and
Proposition 4.10 then implies
$f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{T},A)$. Also note that we have

$\displaystyle C(f^{\prime})$ $\displaystyle=Af^{\prime}+\beta,$ (33)
$\displaystyle=A\big{(}f^{T}+(D-T)f^{\delta}\big{)}+\beta,$
$\displaystyle=Af^{T}+\beta+(D-T)Af^{\delta},$
$\displaystyle=C(f^{T})+(D-T)Af^{\delta}.$

Now let $p\in\mathcal{I}_{1}$, which gives $f^{\delta}_{p}>0$, and since
$f^{\delta}\in\Gamma_{T}$ is a direction of increase, this implies that
$p\in\mathcal{R}^{\operatorname{use}}_{T^{+}}$ for some $T^{+}>T$. However,
since $T\in(D_{M},\infty)$, we obtain
${p\in\mathcal{J}^{\operatorname{use}}_{M}\subseteq\mathcal{J}^{\operatorname{act}}_{M}}$.
Therefore, we have $p\in\mathcal{R}^{\operatorname{act}}_{T}$ and so,
$C_{p}(f^{T})=\lambda^{\operatorname{WE}}(T)$. Consequently, Lemma 4.17 then
tells us that $C_{p}(f^{T})=\delta\lambda^{M}T+\bar{\beta}$. Furthermore, the
fact that $p\in\mathcal{J}^{\operatorname{use}}_{M}$, in combination with
Proposition 4.12, implies
$A_{p}f^{\delta}=\min_{r\in\mathcal{J}^{\operatorname{act}}_{M}}A_{r}f^{\delta}$.
It then follows from Corollary 4.7 that $A_{p}f^{\delta}=\delta\lambda^{M}$.
Collecting these deduced facts that
$C_{p}(f^{T})=\delta\lambda^{M}T+\bar{\beta}$ and
$A_{p}f^{\delta}=\delta\lambda^{M}$ and employing them in (33) then gives us

$\displaystyle C_{p}(f^{\prime})$
$\displaystyle=\delta\lambda^{M}T+\bar{\beta}+(D-T)\delta\lambda^{M},$
$\displaystyle=\delta\lambda^{M}D+\bar{\beta}.$

Thus, $f^{\prime}$ satisfies the constraint (32e). Similar arguments can be
used to show that any path $p\in\mathcal{I}_{3}$ satisfies
$C_{p}(f^{T})\geq\delta\lambda^{M}T+\bar{\beta}$ and
$A_{p}f^{\delta}=\delta\lambda^{M}$, leading to the conclusion that
${C_{p}(f^{\prime})\geq\delta\lambda^{M}D+\bar{\beta}}$. That is, $f^{\prime}$
satisfies (32c).

To show that the constraint on paths in $\mathcal{I}_{2}$ holds, let
$p\in\mathcal{I}_{2}$, which by definition means $\delta
C^{M}_{p}>\delta\lambda^{M}$. Since $f^{\delta}\in\Gamma_{T}$, from
Proposition 4.12, we have $\delta C^{M}=Af^{\delta}$. In combination with
${\delta\lambda^{M}=\min_{r\in\mathcal{J}^{\operatorname{act}}_{M}}A_{r}f^{\delta}}$
we see that $\delta C^{M}_{p}>\min_{r\in\mathcal{P}}\delta C^{M}_{r}$. In
other words, the cost under WE of path $p$ can not remain minimal on the
entire interval $(D_{M},\infty)$ and therefore
$p\notin\mathcal{J}^{\operatorname{act}}_{M}$. Since $T\in(D_{M},\infty)$,
this implies $p\notin\mathcal{R}^{\operatorname{act}}_{T}$, which gives
$p\notin\mathcal{R}^{\operatorname{use}}_{T}$. Therefore, $f^{T}_{p}=0$.
Furthermore, since $p\notin\mathcal{R}^{\operatorname{act}}_{T}$ and
$f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{T},A)$ it follows from the
definition of $\mathcal{M}_{T}$ that $f^{\delta}_{p}=0$. Consequently,
$f^{\prime}_{p}=0$, and so, $f^{\prime}$ satisfies the constraint (32b).

For the constraint (32c) on the paths in $\mathcal{I}_{3}$, note that since
$f^{T}\in\mathcal{F}_{T}$, we have $f^{T}\geq 0$. For any $p$ with
$f^{\delta}_{p}=0$ it then follows that $f^{\prime}_{p}\geq 0$, as required.
That the final constraint (32f) holds follows from the definition of
$f^{\prime}$. Thus, in summary, $f^{\prime}$ satisfies all constraints in
(32), and is therefore feasible.

_Step 2: Obtaining an expression for
$(f^{\prime})^{\top}Af^{\prime}+(f^{\prime})^{\top}$:_ The next step required
for showing $f^{\prime}$ is an optimal solution of (32) is to obtain an
expression of ${(f^{\prime})^{\top}Af^{\prime}+(f^{\prime})^{\top}\beta}$,
which will later be shown to be the lower bound of the objective function of
(32) over the feasible set. To get this expression, we show that if
$f^{\prime}_{p}\neq 0$ for some $p$, then
${C_{p}(f^{\prime})=\delta\lambda^{M}D+\bar{\beta}}$. This fact is
consequently used to show that
${(f^{\prime})^{\top}Af^{\prime}+(f^{\prime})^{\top}\beta=(f^{\prime})^{\top}C(f^{\prime})=D(\delta\lambda^{M}D+\bar{\beta})}$.

Let $p$ be a path such that $f^{\prime}_{p}\neq 0$. It follows that either
$f^{\delta}_{p}>0$ or ${f^{\delta}_{T}>0}$ (note that both vectors are
nonnegative, so values less than zero are not possible). For the first case,
$f^{\delta}_{p}>0$, we have $p\in\mathcal{I}_{1}$ which we have already shown
implies ${C_{p}(f^{\prime})=\delta\lambda^{M}D+\bar{\beta}}$. For the second
case, $f^{T}_{p}>0$, we have
$p\in\mathcal{R}^{\operatorname{use}}_{T}\subseteq\mathcal{R}^{\operatorname{act}}_{T}$,
and therefore we have
${C_{p}(f^{T})=\lambda^{\operatorname{WE}}(T)=\delta\lambda^{M}T+\bar{\beta}}$.

Setting $\mathcal{M}_{T}=\mathcal{M}$ in Proposition 4.12 yields
$A_{p}f^{\delta}=\min_{r\in\mathcal{R}^{\operatorname{act}}_{T}}A_{r}f^{\delta}$,
and Corollary 4.7 then implies $A_{p}f^{\delta}=\delta\lambda^{M}$. Using
these conclusions in (33), we obtain
$C_{p}(f^{\prime})=\delta\lambda^{M}D+\bar{\beta}$. In summary,
$f^{\prime}_{p}\neq 0$ implies
$C_{p}(f^{\prime})=\delta\lambda^{M}D+\bar{\beta}$ and we then have

$\displaystyle(f^{\prime})^{\top}Af^{\prime}+(f^{\prime})^{\top}\beta$
$\displaystyle=(f^{\prime})^{\top}C(f),$ (34)
$\displaystyle=D(\delta\lambda^{M}D+\bar{\beta}).$

_Step 3: $f^{\prime}$ is optimal:_ To finish proving that $f^{\prime}$ is an
optimal solution of (32), we show that $D(\delta\lambda^{M}D+\bar{\beta})$ is
in fact a lower bound on $f^{\top}Af+f^{\top}\beta$ for any $f$ satisfying the
constraints of (32). Therefore, let $f$ be an element of the feasible set of
(32). Consider $p$ such that $f_{p}\neq 0$. Since
$\mathcal{P}=\mathcal{I}_{1}\cup\mathcal{I}_{2}\cup\mathcal{I}_{3}$, the
constraints in (32) then imply $p\in\mathcal{I}_{1}\cup\mathcal{I}_{3}$. From
constraint (32e), if $p\in\mathcal{I}_{1}$, then we have
$C_{p}(f)=\delta\lambda^{M}D+\bar{\beta}$. On the other hand, if
$p\in\mathcal{I}_{3}$, then we obtain
$C_{p}(f)\geq\delta\lambda^{M}D+\bar{\beta}$ from (32d).

Since $\mymathbf{1}^{\top}f=D$, the same derivation as in (34) then gives

$f^{\top}Af+f^{\top}\beta\geq D(\delta\lambda^{M}D+\bar{\beta}D).$ (35)

We see that $D(\delta\lambda^{M}D+\bar{\beta})$ is a lower bound on the
objective function value of (32), and $f^{\prime}$ achieves this lower bound.
Since $f^{\prime}$ is also feasible for this minimization problem, it follows
that it is an optimal solution of (32).

From the above we draw the conclusion that any optimizer $f^{*}$ of (32)
satisfies
$(f^{*})^{\top}Af^{*}+(f^{*})^{\top}\beta=D(\delta\lambda^{M}D+\bar{\beta})$.
As shown in the derivation of (35), any feasible $f$ and path $p$ satisfying
$f_{p}\neq 0$ satisfy $C_{p}(f)\geq\delta\lambda^{M}D+\bar{\beta}$.
Consequently we have the following for any optimizer $f^{*}$ of (32):

$C_{p}(f^{*})=\delta\lambda^{M}D+\bar{\beta}\quad\text{for all }p\text{ such
that }f^{*}_{p}\neq 0.$ (36)

The next part of the proof is to establish that for any optimizer $f^{*}$ of
(32), there exists $D^{+}>0$ such that the following holds:

$f^{D^{+}}:=f^{*}+(D^{+}-D)f^{\delta}\in\mathcal{W}_{D^{+}}.$

_Step 4: $f^{D^{+}}$ is a WE:_ We start by noting that if $f^{*}_{p}<0$, then
the constraint (32e) along with the definition of the set $\mathcal{I}_{1}$
imply $f^{\delta}_{p}>0$. Thus, there exists large enough $D^{+}$ such that
$f^{D^{+}}\geq 0$, and therefore, $f^{D^{+}}\in\mathcal{F}_{D^{+}}$. Next, a
similar derivation as in (33) gives us

$C(f^{D^{+}})=C(f^{*})+(D^{+}-D)Af^{\delta}.$ (37)

Now choose $p$ such that $f^{D^{+}}_{p}>0$. This implies that either
$f^{\delta}_{p}>0$ or $f^{*}_{p}>0$. For the first case, $f^{\delta}_{p}>0$,
we have $p\in\mathcal{I}_{1}$ and the constraint (32e) gives us
$C_{p}(f^{*})=\delta\lambda^{M}D+\bar{\beta}$, and we have already shown in
Step 1 that in this case $A_{p}f^{\delta}=\delta\lambda^{M}$. Thus, we get

$C_{p}(f^{D^{+}})=\delta\lambda^{M}D^{+}+\bar{\beta}.$ (38)

Now consider the second case $f^{*}_{p}>0$. Using (36), we deduce
$C_{p}(f^{*})=\delta\lambda^{M}D+\bar{\beta}$. Furthermore, constraint (32b)
implies that $p\in\mathcal{I}_{1}\cup\mathcal{I}_{3}$. From Step 1, we get
that for $p\in\mathcal{I}_{1}\cup\mathcal{I}_{3}$, the expression $\delta
C^{M}_{p}=\delta\lambda^{M}$ holds. In combination with (37) this shows that
(38) holds.

To establish that $f^{D^{+}}$ is a WE, all that remains to be shown is that
${C_{p}(f^{D^{+}})\geq\delta\lambda^{M}D^{+}+\bar{\beta}}$ whenever
$f^{D^{+}}_{p}=0$. Therefore, let $p$ be a path such that $f^{D^{+}}_{p}=0$.
This can occur when $f^{*}_{p}<0$ and $f^{\delta}_{p}>0$, however, in this
case the previous arguments already show that (38) holds. The only other way
in which $f^{D^{+}}_{p}=0$ is when $f^{*}_{p}=0$ and $f^{\delta}_{p}=0$. We
split this scenario in two cases. First we consider $\delta
C_{p}^{M}>\delta\lambda^{M}$. In this case it follows from $\delta
C^{M}=Af^{\delta}$ in combination with (37) that for large enough $D^{+}$ we
get

$C_{p}(f^{D^{+}})\geq\delta\lambda^{M}D^{+}+\bar{\beta}.$ (39)

The second case is ${\delta C_{p}^{M}=\delta\lambda^{M}}$ (In Step 3 we
already argued that $\delta C_{p}^{M}=\delta\lambda^{M}$ for all
$p\in\mathcal{I}_{1}$ and from the defintion of $\mathcal{I}_{2}$ and
$\mathcal{I}_{3}$ it follows that $\delta C_{p}^{M}<\delta\lambda^{M}$ is not
possible.) For this case (32d) gives
$C_{p}(f^{*})\geq\delta\lambda^{M}D+\bar{\beta}$. Once again, using $\delta
C^{M}=Af^{\delta}$ in combination with (37) we find that (39) holds. In
conclusion, for large enough $D^{+}$ we have $f^{D^{+}}\geq 0$ and
$f^{D^{+}}_{p}=0$ implies (39), and $f^{D^{+}}_{p}>0$ implies (38). In other
words, as long as $D^{+}$ is large enough, $f^{D^{+}}$ is a WE. It follows
that we can pick $D^{+}$ such that $D^{+}\in(D_{M},\infty)$ and
$f^{D^{+}}\in\mathcal{W}_{D^{+}}$.

To finish the proof we now have
$\mathcal{J}^{\operatorname{act}}_{M}=\mathcal{R}^{\operatorname{act}}_{D^{+}}$.
Since the cost under WE is unique, it follows that
$p\in\mathcal{J}^{\operatorname{act}}_{M}$ if and only if it has minimal cost
among all paths for the flow $f^{D^{+}}$. In Step 4, we have shown that the
paths with minimal cost are exactly those for which $\delta
C^{M}_{p}=\delta\lambda^{M}$ and $C_{p}(f^{*})=\delta\lambda^{M}D+\bar{\beta}$
hold and therefore, this concludes the proof. ∎

Now that we can derive $\mathcal{J}^{\operatorname{act}}_{M}$ using the above
result, we finish this section by showing that we can also find $D_{M}$, as
well as an associated WE $f^{D_{M}}$.

######  Corollary 4.19.

(Obtaining $D_{M}$): Let $(\mathcal{P},\mathcal{C})$ be given, and consider
the following minimization problem:

minimize $\displaystyle\mymathbf{1}^{\top}f$ subject to $\displaystyle
C_{p}(f)\leq C_{r}(f)\quad$ $\displaystyle\text{ for all
}p\in\mathcal{J}^{\operatorname{act}}_{M}\text{ and }r\in\mathcal{P},$
$\displaystyle f_{r}=0\quad$ $\displaystyle\text{ for all
}r\in(\mathcal{J}^{\operatorname{act}}_{M})^{c},$ $\displaystyle f\geq 0.$

For any solution $f^{*}$ of the above we have $\mymathbf{1}^{\top}f^{*}=D_{M}$
and $f^{*}\in\mathcal{W}_{D_{M}}$.

###### Proof.

Since any WE for a demand in $(D_{M},\infty)$ satisfies the constraints, we
see that the feasible set is non-empty. Also note that due to the affine and
non-strict nature of the constraints, this implies that any WE in
$\mathcal{W}_{D_{M}}$ is also feasible. It is then easy to prove that any
solution $f^{*}$ to the given minimization problem must be a WE, and also that
any flow of the form $f^{*}+\epsilon f^{\delta}$, where
$f^{\delta}\in\Gamma_{D_{M}}\cap\mathcal{F}_{1}$ and $\epsilon>0$, is a WE as
well. This shows that $f^{*}$ is a WE in the interval $[D_{M},\infty)$, and it
follows that $\mymathbf{1}^{\top}f^{*}=D_{M}$, which implies $f^{*}\in
f^{D_{M}}$. ∎

##  5 Braess’s paradox for changing demand

Figure 7: An illustration of BP for a routing game over the Wheatstone
network, Figure 2, with and without edge $e_{5}$ present and with costs
defined by (12).

A well-known phenomenon in the context of traffic networks is Braess’s paradox
(BP). A routing game is said to be subject to this paradox when removal of a
path from the network leads to lower cost for all participants. The classical
example is the one discussed in Example 4.1a, considering the Wheatstone
network depicted in Figure 2, where the cost functions are given by (11).
Consequently, path-cost functions are given by (12), and we have an explicit
expression for the WE in (13). Using these expressions, we find that
$\lambda^{\operatorname{WE}}(1)=2$. Alternatively, we can look at the same
network, but with edge $e_{5}$ removed. The cost functions remain the same,
but the path $p_{3}$ is no longer accessible. In this case the WE is given by
$\widetilde{f}^{D}=(\frac{1}{2},\enskip\frac{1}{2})^{\top}$, and we have
$\widetilde{\lambda}^{\operatorname{WE}}(1)=1.5$. Notice that for this level
of demand, $D=1$, removing $e_{5}$ has improved the situation for all
participants.

A natural question now is “What happens for other levels of demand?”. For the
Wheatstone network, the answer to this question is known to some extent. It
has been shown that for this network, using affine cost functions, the
associated routing game is subject to Braess’s paradox on at most a bounded
set of demands; i.e., there is an upper bound on the demand above which the
routing game is no longer subject to the paradox [18, 19]. Still, it is useful
to study the given example in a bit more detail to see what happens for
different levels of demand. We will therefore analyze this example further. We
give explicit expressions for $\lambda^{\operatorname{WE}}(D)$ and
$\widetilde{\lambda}^{\operatorname{WE}}(D)$, and show that there exists
demand where the presence of path $p_{3}$ is strictly beneficial.

######  Example 5.1.

(Evolution of BP):

  1. (a)

For the Wheatstone network (Example 4.1a and Figure 2)with the edge $e_{5}$
present we have

$\lambda^{\operatorname{WE}}(D)=\begin{cases}2D\quad&\text{if }0\leq D\leq
1,\\\ 2\quad&\text{if }1\leq D\leq 2,\\\ \frac{D}{2}+1\quad&\text{if }2\leq
D.\end{cases}$

For the network without $e_{5}$ present, the WE for any $D\geq 0$ is given by

$\widetilde{f}^{D}=\left(\begin{array}[]{cc}\frac{D}{2},&\frac{D}{2}\end{array}\right)^{\top},$

which gives us

$\widetilde{\lambda}^{\operatorname{WE}}(D)=\frac{D}{2}+1.$

The situation is illustrated in Figure 7. We see that the presence of path
$p_{3}$ is beneficial when ${0\leq D<\frac{2}{3}}$, detrimental when
$\frac{2}{3}<D<2$, and neutral when $D\in\\{\frac{2}{3}\\}\cup[2,\infty)$.
Clearly, the game being subject to Braess’s paradox at one level of demand
does not necessarily imply that adding the responsible path is detrimental
overall, and the situation warrants further investigation. The aim of this
section is therefore to study how the influence of a set of paths causing BP
changes as the demand varies.

Figure 8: An illustration of BP for a routing game over the network in Figure
3, with and without the path $(e_{1},e_{4})$ present, and with costs defined
by (14).

  2. (b)

We note that classically, Braess’s paradox refers to the situation where
removal of an _edge_ (or a set of edges) leads to a lesser cost for all
participants, but here we will look at a slightly more generalized form of the
paradox, where removal of a _path_ , or set of paths, from the network leads
to a lesser cost for all participants. The previous example shows an instant
where these two cases are the same. However, it is possible that a a routing
game is subject to an instance of BP that only emerges as the result of
removing a (set of) path(s), but not as the result of removing a (set of)
edge(s). To show this, we revisit Example 4.1b. That is, we consider a routing
game over the network in Figure 3, with path-cost given by (14). Figure 8
shows the comparison between the cost of this game and the modified game where
path $p_{4}$ has been removed. Note that the case is essentially identical to
that of Example 4.1a. Observe now that the game is subject to BP on the
interval $D\in(\frac{2}{3},1)$, but in this case there is no edge which is
responsible for the inefficiency. Instead it is the presence of the path
$(e_{3},e_{2})$ that causes BP. $\bullet$

###  5.1 Preliminaries for analyzing BP

To ease the exposition of the upcoming analysis, we introduce definitions and
useful facts related to the concepts of _necessary sets_ , _modified games_
and _directions of decrease_.

####  5.1.1 Necessary sets

The set of all subsets of $\mathcal{P}$ that can not be removed from the game
without changing the WE at the demand $D$ is called the _necessary set_ at
$D$. Formally, we have the following definition.

######  Definition 5.2.

(Necessary sets): For a given $(\mathcal{P},\mathcal{C})$ we say that a set
$\mathcal{S}^{\texttt{nec}}\subseteq\mathcal{P}$ is _necessary_ at demand $D$
if

$f^{D}_{\mathcal{S}^{\texttt{nec}}}\neq 0\text{ for all
}f^{D}\in\mathcal{W}_{D}.$

That is, for every WE $f^{D}$, there exists at least one path in the set
$\mathcal{S}^{\texttt{nec}}$ that takes nonzero flow. We use $\mathcal{N}_{D}$
to denote the set of all necessary sets at $D$; that is,

$\mathcal{N}_{D}:=\\{\mathcal{S}^{\texttt{nec}}\subseteq\mathcal{P}\;|\;f^{D}_{\mathcal{S}^{\texttt{nec}}}\neq
0\text{ for all }f^{D}\in\mathcal{W}_{D}\\}.$

When $\mathcal{S}\notin\mathcal{N}_{D}$ we say that $\mathcal{S}$ is
_unnecessary_ at demand $D$. $\bullet$

Although at first glance the necessary set may seem closely related to the
used set $\mathcal{R}^{\operatorname{use}}_{D}$, we note that unlike
$\mathcal{R}^{\operatorname{use}}_{D}$ and
$\mathcal{R}^{\operatorname{act}}_{D}$, the necessary set is not guaranteed to
stay constant in between the breakpoints in $\mathcal{D}$. For instance, in
Example 4.1b we have $\mathcal{D}=\\{0,1,\infty\\}$. However, we can deduce
from the expression given for $\mathcal{W}_{D}$ in (15) that the singleton set
$\\{p_{3}\\}$ is necessary at all demands in $(0,2)$ while $\\{p_{3}\\}$ is
unnecessary for $D\geq 2$.

####  5.1.2 Modified games

To better accomodate our path-based notion of BP, we will introduce the
concept of a _modified game_. Given a routing game
$(\mathcal{P},\mathcal{C})$, a modified game is constructed by removing a set
of paths $\mathcal{S}^{\texttt{rem}}\subset\mathcal{P}$ from the game, which
is achieved by forcing the flow on paths in $\mathcal{S}^{\texttt{rem}}$ to be
zero, while keeping all cost functions the same. We use
$(\widetilde{\mathcal{P}},\mathcal{C})$ to denote such a modified game, where
$\widetilde{\mathcal{P}}=\mathcal{P}\setminus\mathcal{S}^{\texttt{rem}}$. We
also use the following notation:

$\displaystyle\widetilde{\mathcal{P}}$
$\displaystyle:=\mathcal{P}\setminus\mathcal{S}^{\texttt{rem}},$
$\displaystyle\widetilde{\mathcal{F}}_{D}$
$\displaystyle:=\\{\widetilde{f}\in{\mathbb{R}}_{\geq
0}^{n}\;|\;\sum_{p\in\widetilde{\mathcal{P}}}\widetilde{f}_{p}=D,\enskip\widetilde{f}_{\mathcal{S}^{\texttt{rem}}}=0\\},$
$\displaystyle\widetilde{\mathcal{H}}_{D}$
$\displaystyle:=\\{\widetilde{f}\in{}^{n}\;|\;\sum_{p\in\widetilde{\mathcal{P}}}\widetilde{f}_{p}=D,\enskip\widetilde{f}_{\mathcal{S}^{\texttt{rem}}}=0\\}.$

For notational convenience, the dimension of the flows
$\widetilde{f}\in\widetilde{\mathcal{F}}_{D}$ of the modified game is kept
equal to $n=\left\lvert{\mathcal{P}}\right\rvert$. For a modified game, we say
that $\widetilde{f}^{D}$ is a WE when
$\widetilde{f}^{D}\in\widetilde{\mathcal{F}}_{D}$ and for all
$p\in\widetilde{\mathcal{P}}$ such that $\widetilde{f}_{p}>0$ we have

$C_{p}(\widetilde{f}^{D})\leq C_{r}(\widetilde{f}^{D})\quad\text{for all
}r\in\widetilde{\mathcal{P}}.$

Analogously, we use the notation $\widetilde{(\cdot)}$ for other items related
to the modified game. We write

$\displaystyle\widetilde{\mathcal{W}}_{D}$
$\displaystyle:=\operatorname{SOL}(\widetilde{\mathcal{F}}_{D},C),$ (40)
$\displaystyle\widetilde{\lambda}^{\operatorname{vec}}(D)$
$\displaystyle:=C(\widetilde{f}^{D})\text{ for any
}\widetilde{f}^{D}\in\widetilde{\mathcal{W}}_{D},$
$\displaystyle\widetilde{\mathcal{R}}^{\operatorname{act}}_{D}$
$\displaystyle:=\\{p\in\widetilde{\mathcal{P}}\;|\;\widetilde{\lambda}^{\operatorname{vec}}_{p}(D)\leq\widetilde{\lambda}^{\operatorname{vec}}_{r}(D)\text{
for all }r\in\widetilde{\mathcal{P}}\\},$
$\displaystyle\widetilde{\mathcal{R}}^{\operatorname{use}}_{D}$
$\displaystyle:=\\{p\in\widetilde{\mathcal{P}}\;|\;\exists\widetilde{f}^{D}\in\widetilde{\mathcal{W}}_{D}\text{
such that }\widetilde{f}^{D}_{p}>0\\},$
$\displaystyle\widetilde{\lambda}^{\operatorname{WE}}(D)$
$\displaystyle:=\widetilde{\lambda}^{\operatorname{vec}}_{p}(D)\text{ for any
}p\in\widetilde{\mathcal{R}}^{\operatorname{act}}_{D},$
$\displaystyle\widetilde{\mathcal{M}}_{D}$
$\displaystyle:=\\{\widetilde{f}^{\delta}\in\widetilde{\mathcal{H}}_{1}\;|\;\widetilde{f}_{\widetilde{\mathcal{R}}^{\operatorname{act}}_{D}\setminus\widetilde{\mathcal{R}}^{\operatorname{use}}_{D}}^{\delta}\geq
0,\enskip\widetilde{f}_{(\widetilde{\mathcal{R}}^{\operatorname{act}}_{D})^{c}}^{\delta}=0\\},$
$\displaystyle\widetilde{\Gamma}_{D}$
$\displaystyle:=\operatorname{SOL}(\widetilde{\mathcal{M}}_{D},A).$

Similarly, we use $\widetilde{\mathcal{D}}$ to denote the set of breakpoints
of a modified game and use $\widetilde{D}_{i}$ to denote the $i$-th breakpoint
of $\widetilde{\mathcal{D}}$. We write $\widetilde{M}$ for the index of the
greatest finite valued breakpoint $\widetilde{D}_{\widetilde{M}}$ in
$\widetilde{\mathcal{D}}$ and use $\delta\widetilde{\lambda}^{i}$ and
$\delta\widetilde{C}^{i}$ to denote the directions in which respectively
$\widetilde{\lambda}^{\operatorname{WE}}$ and
$\widetilde{\lambda}^{\operatorname{vec}}$ evolve on the interval between
$\widetilde{D}_{i}$ and $\widetilde{D}_{i+1}$.

When we need to discuss multiple modified games simultanuously, as is
sometimes the case in a proof, we use a similar notation for concepts related
to these modified games, replacing $\widetilde{(\cdot)}$ with
$\widecheck{(\cdot)}$ or with $(\cdot)^{\prime}$, $(\cdot)^{\prime\prime}$, or
$(\cdot)^{\prime\prime\prime}$. (e.g. we use $\widecheck{\mathcal{P}}$, and
$\mathcal{P}^{\prime}$, $\mathcal{P}^{\prime\prime}$, and
$\mathcal{P}^{\prime\prime\prime}$ to denote the related sets of paths, and
similarly for the feasible set, WE-cost, etc.)

We note that a modified game is technically not a routing game as presented in
Section 2. The reason for this is that the feasible set has additional
restrictions and the definition of WE for a modified game only takes into
account a subset of the paths in $\mathcal{P}$. Of course, instead of setting
$\widetilde{f}_{\mathcal{S}^{\texttt{rem}}}=0$, we could simply drop this set
of paths from consideration, and let $\widetilde{f}\in{\mathbb{R}}_{\geq
0}^{\left\lvert{\widetilde{\mathcal{P}}}\right\rvert}$. In this case we could
define $\widetilde{\mathcal{F}}_{D}$ without imposing additional restrictions.
However, removing a set of paths from a routing game can result in a situation
which can no longer be represented by a graph. That is, in that case there
does not exists a graph, an associated origin-destination pair and a set of
cost functions such that the resulting routing game over all paths from the
origin to the destination has the same cost function as that of the modified
game. However, the results and proofs in this text are in no way dependent on
the existence of such a graph representation for the given set of paths and
associated cost functions. Therefore all results that we established for
routing games also hold for modified games. We specifically highlight that
$\widetilde{\mathcal{W}}_{D}$ and $\widetilde{\Gamma}_{D}$, as defined in
(40), are therefore indeed the set of WE of the modified game and the set of
directions of increase of the modified game respectively, as the notation
suggests.

####  5.1.3 Directions of decrease

The results in Section 4 consider the directions of _increase_ in which the WE
moves as the demand increases, but for some of the upcoming statements it is
useful to instead consider the set of _directions of decrease_ :

######  Definition 5.3.

(Set of directions of decrease): Let $(\mathcal{P},\mathcal{C},D)$ be given.
The set of _directions of decrease_ $\Gamma^{-}_{D}$ is the set of all
directions $f^{\delta}\in\mathcal{H}_{-1}$ in which the flow can be decreased,
starting from some flow in $\mathcal{W}_{D}$, such that the new flow is a WE
as long as the decrease is small enough. That is,

$\displaystyle\Gamma^{-}_{D}:=\\{f^{\delta}\in\mathcal{H}_{-1}\;|\;\exists
f^{D}\in\mathcal{W}_{D},\enskip\bar{\epsilon}>0\text{ such that
}f^{D}+\epsilon
f^{\delta}\in\mathcal{W}_{D-\epsilon}\enskip\forall\epsilon\in[0,\bar{\epsilon}]\\}.$

Similar to before, we define the set $\mathcal{M}_{D}^{-}$ of feasible descent
directions as

$\mathcal{M}_{D}^{-}:=\\{f^{\delta}\in\mathcal{H}_{-1}\;|\;f_{\mathcal{R}^{\operatorname{act}}_{D}\setminus\mathcal{R}^{\operatorname{use}}_{D}}^{\delta}\geq
0,\enskip f_{(\mathcal{R}^{\operatorname{act}}_{D})^{c}}^{\delta}=0\\}.$

The arguments made in Section 4 can then be repeated to obtain the following
modified version of Proposition 4.10:

######  Lemma 5.4.

(Directions of decrease as solutions to a VI): Let
$(\mathcal{P},\mathcal{C},D)$ be given. Then,

${\Gamma_{D}^{-}=\operatorname{SOL}(\mathcal{M}_{D}^{-},A)}.$

####  5.1.4 Properties of $V$

We recall from Section 3 the function $V$, and similarly define the function
$\widetilde{V}$ for a modified game as

$\displaystyle V(D)=$
$\displaystyle\min_{f\in\mathcal{F}_{D}}\sum_{e_{k}\in\mathcal{E}}\int_{0}^{f_{e_{k}}}C_{e_{k}}(z)dz,$
(41) $\displaystyle\widetilde{V}(D):=$
$\displaystyle\min_{\widetilde{f}\in\widetilde{\mathcal{F}}_{D}}\sum_{e_{k}\in\mathcal{E}}\int_{0}^{\widetilde{f}_{e_{k}}}C_{e_{k}}(z)dz.$

Using the inclusion $\widetilde{\mathcal{F}}_{D}\subseteq\mathcal{F}_{D}$ in
combination with Proposition 3.3 then yields us the following observations on
modified games and necessary sets:

######  Lemma 5.5.

(Relations between the original and the modified game): Let
$(\mathcal{P},\mathcal{C},D)$ and
$\mathcal{S}^{\texttt{rem}}\subset\mathcal{P}$ be given, and let $V$ and
$\widetilde{V}$ be given by (41). The following then hold:

  * •

$V(D)\leq\widetilde{V}(D)$,

  * •

$V(D)=\widetilde{V}(D)$ if and only if
$\mathcal{S}^{\texttt{rem}}\notin\mathcal{N}_{D}$,

  * •

if $\mathcal{S}^{\texttt{rem}}\notin\mathcal{N}_{D}$, then
$\widetilde{f}^{D}\in\widetilde{\mathcal{W}}_{D}$ if and only if
${\widetilde{f}^{D}_{\mathcal{S}^{\texttt{rem}}}=0}$ and
${\widetilde{f}^{D}\in\mathcal{W}_{D}}$. As a consequence, we then have
${\lambda^{\operatorname{WE}}(D)=\widetilde{\lambda}^{\operatorname{WE}}(D)}$.

Figure 9: A comparison between $V$ and $\widetilde{V}$ for the Wheatstone
network in Figure 2, with and without the path $p_{3}=(e_{1},e_{5},e_{4})$
present and with costs defined by (12).

The above statements are illustrated in Figure 9, which shows the functions
$V$ and $\widetilde{V}$ for the routing games considered in Example 5.1a.
Here, the path removed from $\mathcal{P}$ to form the modified game is
$\mathcal{S}^{\texttt{rem}}=\\{p_{3}\\}$. Notice that for demand in the
interval $(0,2)$, the singleton set $\mathcal{S}^{\texttt{rem}}=\\{p_{3}\\}$
is a necessary set and as expected, we have $V(D)<\widetilde{V}(D)$ for all
$D\in(0,2)$. Moreover, exactly at the point $D=2$, the set
$\mathcal{S}^{\texttt{rem}}$ is no longer necessary and we have
$V(2)=\widetilde{V}(2)$.

###  5.2 Evolution of WE-costs

Our upcoming discussion on BP depends for a large part on analysis of the WE-
cost $\lambda^{\operatorname{WE}}$. We show how knowledge on the evolution of
this cost can be leveraged to detect when a game is subject to BP. In
particular, we look at how the slope of $\lambda^{\operatorname{WE}}$ changes
at the breakpoints in $\mathcal{D}$. Since $\lambda^{\operatorname{WE}}$ is
potentially non-differentiable at these points, it is useful to consider both
the left-hand and right-hand side derivatives:

$\delta\lambda^{+}(T):=\frac{\partial^{+}}{\partial
D}\lambda^{\operatorname{WE}}(D)\Big{|}_{D=T},\quad\delta\lambda^{-}(T):=\frac{\partial^{-}}{\partial
D}\lambda^{\operatorname{WE}}(D)\Big{|}_{D=T}.$

Note that whenever $T\notin\mathcal{D}$, we have
$\delta\lambda^{+}(T)=\delta\lambda^{-}(\bar{D})$. Using Proposition 4.12 with
$\mathcal{M}=\mathcal{M}_{D}$ and $\mathcal{M}=\mathcal{M}^{-}_{D}$, we then
have the following observation:

######  Corollary 5.6.

(Relation between $\operatorname{SOL}(\mathcal{M}_{D},A)$ and slope of
$\lambda^{\operatorname{WE}}$): Let $(\mathcal{P},\mathcal{C},D)$ be given. We
have

$\displaystyle\delta\lambda^{+}(D)$
$\displaystyle=\min_{r\in\mathcal{R}^{\operatorname{act}}_{D}}A_{r}f^{\delta}\quad\hskip
10.0pt\text{for all }f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D},A),$
$\displaystyle\delta\lambda^{-}(D)$
$\displaystyle=-\min_{r\in\mathcal{R}^{\operatorname{act}}_{D}}A_{r}f^{\delta}\quad\text{for
all }f^{\delta}\in\operatorname{SOL}(\mathcal{M}_{D}^{-},A).$

We see that sets of the form $\operatorname{SOL}(\mathcal{M}_{D},A)$ are
important when studying $\delta\lambda^{+}(D)$ and $\delta\lambda^{-}(D)$. Our
next result therefore concerns sets of this form and derives properties that
will used in studying the evolution of cost.

######  Lemma 5.7.

(Properties of $\operatorname{SOL}(\mathcal{M},A)$): Let $\mathcal{P}$,
$\mathcal{C}\subset\mathcal{K}$, and sets
$\mathcal{Q},\mathcal{R},\widetilde{\mathcal{Q}},\widetilde{\mathcal{R}}\subseteq\mathcal{P}$
satisfying $\mathcal{R}\subseteq\mathcal{Q}$ and
$\widetilde{\mathcal{R}}\subseteq\widetilde{\mathcal{Q}}$ be given. In
addition, let

$\displaystyle\mathcal{M}$
$\displaystyle:=\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f^{\delta}_{\mathcal{Q}\setminus\mathcal{R}}\geq
0,\quad f^{\delta}_{\mathcal{Q}^{c}}=0\\},$
$\displaystyle\widetilde{\mathcal{M}}$
$\displaystyle:=\\{f^{\delta}\in\mathcal{H}_{1}\;|\;f^{\delta}_{\widetilde{\mathcal{Q}}\setminus\widetilde{\mathcal{R}}}\geq
0,\quad f^{\delta}_{\widetilde{\mathcal{Q}}^{c}}=0\\},$
$\displaystyle\mathcal{M}^{-}$
$\displaystyle:=\\{f^{\delta}\in\mathcal{H}_{-1}\;|\;f^{\delta}_{\mathcal{Q}\setminus\mathcal{R}}\geq
0,\quad f^{\delta}_{\mathcal{Q}^{c}}=0\\},$
$\displaystyle\widetilde{\mathcal{M}}^{-}$
$\displaystyle:=\\{f^{\delta}\in\mathcal{H}_{-1}\;|\;f^{\delta}_{\widetilde{\mathcal{Q}}\setminus\widetilde{\mathcal{R}}}\geq
0,\quad f^{\delta}_{\widetilde{\mathcal{Q}}^{c}}=0\\}.$

For given $f^{\delta}\in\operatorname{SOL}(\mathcal{M},A)$,
$\widetilde{f}^{\delta}\in\operatorname{SOL}(\widetilde{\mathcal{M}},A)$,
${f^{\delta-}\in\operatorname{SOL}(\mathcal{M}^{-},A)}$ and
${\widetilde{f}^{\delta-}\in\operatorname{SOL}(\widetilde{\mathcal{M}}^{-},A)}$,
if $\widetilde{\mathcal{M}}\subseteq\mathcal{M}$ (respectively,
$\widetilde{\mathcal{M}}^{-}\subseteq\mathcal{M}^{-})$ then we have