# Monotonicity of Equilibria in Nonatomic Congestion Games

Roberto Cominetti‡ ‡ Facultad de Ingeniería y Ciencias, Universidad Adolfo
Ibáñez, Santiago, Chile<EMAIL_ADDRESS>,  Valerio Dose§ §
Dipartimento di Ingengeria Informatica, Automatica e Gestionale, “Sapienza”
Università di Roma, Italy<EMAIL_ADDRESS>and  Marco Scarsini¶ ¶
Dipartimento di Economia e Finanza, Luiss University, Viale Romania 32, 00197
Roma, Italy<EMAIL_ADDRESS>
###### Abstract.

This paper studies the monotonicity of equilibrium costs and equilibrium loads
in nonatomic congestion games, in response to variations of the demands. The
main goal is to identify conditions under which a paradoxical non-monotone
behavior can be excluded. In contrast with routing games with a single
commodity, where the network topology is the sole determinant factor for
monotonicity, for general congestion games with multiple commodities the
structure of the strategy sets plays a crucial role.

We frame our study in the general setting of congestion games, with a special
attention on multi-commodity singleton congestion games, for which we
establish the monotonicity of equilibrium loads with respect to every demand.
We then provide conditions for comonotonicity of the equilibrium loads, i.e.,
we investigate when they jointly increase or decrease after variations of the
demands. We finally extend our study from singleton congestion games to the
larger class of product-union congestion games, whose structure is reminiscent
of the concept of a series-parallel network.

Keywords: game theory, comonotonicity, singleton congestion games, Wardrop
equilibrium.

##  1\. Introduction

Common sense suggests that a rise in traffic demands entails longer travel
times. This implication is not always true. Traffic networks with a large
number of vehicles are often modeled as nonatomic games, with _Wardrop
equilibrium_ as the standard solution concept: for each origin-destination
(OD) pair, all the used paths have the same cost or travel time, whereas
unused paths have higher costs. While Hall, (1978) proved that in a single OD
network the equilibrium cost is an increasing function of the traffic demand,
Fisk, (1979) constructed an example with three OD pairs in which the
equilibrium cost of an OD pair decreases when the demand of a different OD
increases. Namely, in the network depicted in Fig. 1 with three OD pairs
$(a,b)$, $(b,c)$, $(a,c)$, a rise in the demand $d_{(a,b)}$ increases the cost
of the link $ab$ and pushes the $(a,c)$ pair to favor the use of the direct
link $ac$. This reduces the load on the link $bc$, which ultimately benefits
the pair $(b,c)$ by reducing its cost. Perhaps more surprising is the fact
that this phenomenon may even occur when all the demands increase by the same
factor: with demands $d_{(a,b)}=60$, $d_{(a,c)}=30$, $d_{(b,c)}=6$ the
equilibrium cost for the third OD is $C_{(b,c)}=24$, and when all the demands
are doubled it decreases to $C_{(b,c)}=18$.

$a$$b$$c$$x$$x+90$$x$ Figure 1. Fisk’s network.

On the other hand, even if the equilibrium cost on single OD networks
increases with the demand, the load on some edges may decrease after a surge
in the demand. This can be observed in the classical Wheatstone network
illustrated in Fig. 2 (see Braess,, 1968, Braess et al.,, 2005, for the famous
paradox that uses this network).

$\mathsf{O}$$v_{1}$$v_{2}$$\mathsf{D}$$x$$1$$0$$1$$x$ (a) Wheatstone network

$\mathsf{O}\,v_{1}\,v_{2}\mathsf{D}$ $\mathsf{O}\,v_{1}\mathsf{D}$
$\mathsf{O}\,v_{2}\mathsf{D}$ $\mu\in[0,1]$ $\mu$ $0$ $0$ $\mu\in[1,2]$
$2-\mu$ $\mu-1$ $\mu-1$ $\mu\in[2,+\infty)$ $0$ $\mu/2$ $\mu/2$

(b) Equilibrium loads

Figure 2. In the Wheatstone network with three paths and a single OD pair, the
equilibrium load on the vertical edge $(v_{1},v_{2})$ is decreasing for
$\mu\in[1,2]$.

Networks in which the equilibrium loads of all the edges increase with the
travel demand of every OD pair are more predictable and easier to handle for a
social planner, because an edge is never used below a certain level of demand
and is always used above that level. The goal of this paper is precisely to
understand when the equilibrium travel times and edge loads are monotone in
the demand, so that the paradoxical phenomena observed in the two examples
above cannot happen. We state our results in the general setting of congestion
games, rather than routing games, with a special focus on multi-commodity
singleton congestion games.

###  1.1. Our Results

For multi-commodity singleton congestion games, we show in Theorem 3 that,
even when there exist multiple equilibrium flows, one can always select an
equilibrium whose corresponding resource loads are monotone increasing with
respect to each demand. We then focus on the notion of comonotonicity, which
encodes the idea that different resource loads jointly increase or decrease
upon variations of the demands. We take a close look at how comonotonicity
depends on the structure of equilibria, in terms of how the commodities are
ranked by cost under different demand profiles, and how the resources become
active or inactive as the demands vary (Theorem 5). We also provide structural
results for the regions of the space of demands on which a fixed set of
resources is used at equilibrium (Theorem 6).

We next extend the monotonicity results from singleton congestion games to the
larger class of product-union congestion games (Theorem 10). Finally, we
derive an embedding that maps congestion games into routing games (Proposition
8) and characterize the classes of congestion games with good monotonicity
properties by embedding them into routing games (Theorem 11). This last result
sheds light on the features that produce the non-monotonicity paradoxes, and
highlights the difference between the single and multiple OD networks. When
the network has a single OD pair, its topology is the sole relevant factor to
guarantee the monotonicity of equilibrium loads, while for multiple ODs the
structure of the set of feasible routes also plays a crucial role.

###  1.2. Related Work

Several authors studied the sensitivity of Wardrop equilibria in routing games
with respect to changes in the demand. Hall, (1978) observed that, when the
costs are strictly increasing, the equilibrium loads depend continuously on
the demands. Patriksson, (2004) and Josefsson and Patriksson, (2007) studied
the directional differentiability (or lack thereof) of equilibrium costs and
loads, whereas Cominetti et al., (2023) studied differentiability along a
curve in the space of demands. Specific cases of differentiability, were also
considered in Pradeau, (2014).

As mentioned previously, Hall, (1978) proved that the equilibrium cost of an
OD pair increases when the demand of that OD grows. On the other hand Fisk,
(1979) noted that it may decrease as a consequence of a rise in the demand of
a different OD. Some positive results concerning the monotonicity of
equilibrium loads in series-parallel (SP) single-commodity networks can be
found in Klimm and Warode, (2022) for piece-wise linear costs and in Cominetti
et al., (2021) for general nondecreasing costs.

Traffic equilibria in routing games exhibit a multitude of paradoxes. The most
famous, due to Braess, (1968), Braess et al., (2005), shows that removing an
edge from a network could actually improve the equilibrium cost for all
players (see Fig. 2). Also surprising is the fact observed by Fisk, (1979)
that an OD can reduce its cost and benefit from an increase in the demand of a
different OD, even after doubling all the demands, as mentioned before. Fisk
and Pallottino, (1981) showed that such paradoxical phenomena could be
observed in real life in the City of Winnipeg, Manitoba, Canada. Dafermos and
Nagurney, (1984) studied how equilibrium costs are affected by changes in the
travel demand or addition of new routes under a more general non-separable
cost structure. A related paradoxical phenomenon was studied by Mehr and
Horowitz, (2020) in a model with both regular and autonomous vehicles: despite
the fact that autonomous vehicles are more efficient by allowing shorter
headways and distances, replacing regular with autonomous vehicles may
increase the total network delay.

A particularly simple class of congestion games is the one of singleton
congestion games where each strategy comprises a single resource. Different
variants of these type of games have been considered in the literature,
including atomic weighted and unweighted players, with splittable or
unsplittable loads, as well as nonatomic players.

For _atomic splittable_ singleton games, Harks and Timmermans, (2017)
developed a polynomial time algorithm to compute a Nash equilibrium with
player-specific affine costs. In a different direction, Bilò and Vinci, (2017)
investigated how the structure of the players’ strategy sets affects the
efficiency in singleton load balancing games. Atomic splittable singleton
games have also been used to model the charging strategies of a population of
electric vehicles (Ma et al.,, 2013, Deori et al.,, 2017, Nimalsiri et al.,,
2020). In a related but different direction, Castiglioni et al., (2019)
studied the computational complexity of finding Stackelberg equilibria in
games where one player acts as leader and the others as followers.

For _atomic unsplittable_ singleton games, Gairing and Schoppmann, (2007)
provided upper and lower bounds on the price of anarchy, distinguishing
between restricted and unrestricted strategy sets, weighted and unweighted
players, and linear vs. polynomial costs. Fotakis et al., (2009) studied the
combinatorial structure and computational complexity of Nash equilibria,
including the problems of deciding the existence of pure equilibria, computing
pure/mixed equilibria, and computing the social cost of a given mixed
equilibrium. Harks and Klimm, (2012) characterized the classes of cost
functions that guarantee the existence of pure equilibria for weighted routing
games and singleton congestion games.

Finally, in the _nonatomic_ setting, which is the focus of our paper,
Gonczarowski and Tennenholtz, (2016) used a clever hydraulic system
representation to study asymmetric singleton congestion games, presenting
applications in the home internet and cellular markets, as well as in cloud
computing. Another recent application of nonatomic singleton congestion games
to hospital choice in healthcare systems is discussed in van de Klundert et
al., (2023). In the special case of routing games, singleton games correspond
to parallel networks. Despite its simple topology they are nevertheless of
interest in the literature (see, e.g., Acemoglu and Ozdaglar,, 2007, Wan,,
2016, Harks et al.,, 2019)).

###  1.3. Organization of the paper

The paper is organized as follows. Section 2 recalls the standard model of
non-atomic congestion games and reviews the basic properties of equilibria.
This section includes the definition and the study of monotonic equilibrium
selection (MES) and comonotonicity. Section 3 and Section 4 both deal with
singleton congestion games. Section 3 contains the central monotonicity
result, whereas Section 4 discusses comonotonicity and the structure of the
domains associated to different sets of resources. Section 5 studies the
monotonicity properties of more complex congestion games beyond the case of
singleton strategies. Section 6 summarizes the results of our paper and
proposes some open problems. Appendix A includes some supplementary proofs.
Appendix B contains a list of the symbols used throughout the paper.

##  2\. Congestion Games and Equilibria

We begin by recalling the basic concepts and facts about nonatomic congestion
games, and by fixing the notations used throughout the whole paper. The basic
structural elements are:

  * •

a finite set $\mathcal{R}$ of _resources_ and, for each $r\in\mathcal{R}$, a
continuous nondecreasing _cost function_
$c_{r}\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$, where $c_{r}(x_{r})$ represents
the cost of resource $r$ under a workload $x_{r}$; and

  * •

a finite set $\mathcal{H}$ of _commodities_ and, for each $h\in\mathcal{H}$, a
family $\mathcal{S}^{h}\subset 2^{\mathcal{R}}$ of _feasible strategies_ ,
where every $s\in\mathcal{S}^{h}$ is a subset of resources
$s\subset\mathcal{R}$ with which a given task in $h$ can be performed.

These elements define a _congestion game structure_
$\mathcal{G}=\left(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}}\right)$
with $\boldsymbol{c}\coloneqq\left(c_{r}\right)_{r\in\mathcal{R}}$ the vector
of cost functions and
$\boldsymbol{\mathcal{S}}\coloneqq\times_{h\in\mathcal{H}}{\mathcal{S}^{h}}$
the set of strategy profiles. Every vector
$\boldsymbol{\mu}\coloneqq\left(\mu^{h}\right)_{h\in\mathcal{H}}$ of _demands_
$\mu^{h}\geq 0$, determines a _nonatomic congestion game_
$(\mathcal{G},\boldsymbol{\mu})$ as follows. Each $\mu^{h}$ splits into
_feasible flows_
$\boldsymbol{f}^{h}\coloneqq\left(f_{s}^{h}\right)_{s\in\mathcal{S}^{h}}$ such
that

$\mu^{h}=\sum_{s\in\mathcal{S}^{h}}f_{s}^{h},\quad f_{s}^{h}\geq 0,\text{ for
all }s\in\mathcal{S}^{h}.$ (2.1)

These flows combined induce aggregate _loads_ over the resources, given by

$(\forall r\in\mathcal{R})\qquad
x_{r}\coloneqq\sum_{h\in\mathcal{H}}\sum_{s\in\mathcal{S}^{h}}f_{s}^{h}\mathds{1}_{\\{r\in
s\\}},$ (2.2)

as well as _strategy costs_ , defined as

$(\forall s\subset\mathcal{R})\qquad c_{s}(\boldsymbol{f})\coloneqq\sum_{r\in
s}c_{r}(x_{r}).$ (2.3)

We let $\mathcal{F}_{\boldsymbol{\mu}}$ denote the set of _feasible flows_
$\boldsymbol{f}\coloneqq\big{(}\boldsymbol{f}^{h}\big{)}_{h\in\mathcal{H}}$
where each $\boldsymbol{f}^{h}$ satisfies Eq. 2.1, and
$\mathcal{X}_{\boldsymbol{\mu}}$ the set of _load profiles_
$\boldsymbol{x}=(x_{r})_{r\in\mathcal{R}}$ induced by all feasible flows
$\boldsymbol{f}\in\mathcal{F}_{\boldsymbol{\mu}}$. Assuming further that for
each commodity only the strategies with the smallest possible cost are
selected, leads to the concept of _Wardrop equilibrium_ : a feasible flow
$\boldsymbol{f}\in\mathcal{F}_{\mu}$ for which there exists a nonnegative
vector
$\boldsymbol{\lambda}\coloneqq\left(\lambda^{h}\right)_{h\in\mathcal{H}}$,
such that

$(\forall
h\in\mathcal{H})\qquad\begin{cases}c_{s}(\boldsymbol{f})=\lambda^{h}&\text{for
all }s\in\mathcal{S}^{h}\text{ with }f_{s}^{h}>0,\\\
c_{s}(f)\geq\lambda^{h}&\text{for all }s\in\mathcal{S}^{h}\text{ with
}f_{s}^{h}=0.\end{cases}$ (2.4)

The quantity $\lambda^{h}$ is called the _equilibrium cost_ of commodity
$h\in\mathcal{H}$. A strategy $s\in\mathcal{S}^{h}$ is said to be _active_ if
$c_{s}(\boldsymbol{f})=\lambda^{h}$. Similarly, a resource $r\in\mathcal{R}$
is _active_ for commodity $h\in\mathcal{H}$ if it belongs to some active
strategy.

As shown by Beckmann et al., (1956), the set of load profiles induced by
equilibrium flows coincides with the set of optimal solutions of the
minimization problem

$\min_{x\in\mathcal{X}_{\mu}}\sum_{r\in\mathcal{R}}C_{r}(x_{r}),$ (2.5)

where $C_{r}(x_{r})\coloneqq\int_{0}^{x_{r}}c_{r}(z)\ \textup{d}z$. Since the
cost functions $c_{r}$ are continuous and nondecreasing, the above objective
function is convex and differentiable. Thus, since
$\mathcal{X}_{\boldsymbol{\mu}}$ is a bounded polytope, for every
$\boldsymbol{\mu}$ there exists at least one optimal solution.

For an equilibrium load profile $\widehat{\boldsymbol{x}}$, we define the
equilibrium resource costs $\tau_{r}\coloneqq c_{r}(\widehat{x}_{r})$. By
using Fenchel’s duality theory (see e.g., Remark 11 in Appendix A, or
Fukushima, (1984) for the special case of nonatomic routing games), we can
prove that the equilibrium resource costs are optimal solutions of the
strictly convex dual program

$\min_{\tau}\sum_{r\in\mathcal{R}}C_{r}^{*}(\tau_{r})-\sum_{h\in\mathcal{H}}\left(\mu^{h}\,\min_{s\in\mathcal{S}^{h}}\sum_{r\in
s}\tau_{r}\right),$ (2.6)

where $C_{r}^{*}(\,\cdot\,)$ is the Fenchel conjugate of $C_{r}(\,\cdot\,)$,
which is strictly convex.

Thus, for each $\boldsymbol{\mu}$ the equilibrium resource costs $\tau_{r}$
are uniquely defined and are the same for all equilibrium loads. This implies
that the strategy costs $c_{s}=\sum_{r\in s}\tau_{r}$ and equilibrium costs
$\lambda^{h}=\min_{s\in\mathcal{S}^{h}}\sum_{r\in s}\tau_{r}$ depend only on
$\boldsymbol{\mu}$ and not on the particular equilibrium flow under
consideration, and hence also the active strategies and active resources only
depend on $\boldsymbol{\mu}$.

The _active regime_ at demand $\boldsymbol{\mu}$ is defined as
$\widehat{\boldsymbol{\mathcal{R}}}(\boldsymbol{\mu})\coloneqq(\widehat{\mathcal{R}}^{h}(\boldsymbol{\mu}))_{h\in\mathcal{H}}$
with $\widehat{\mathcal{R}}^{h}(\boldsymbol{\mu})$ the set of active resources
for commodity $h\in\mathcal{H}$. We also let
$\boldsymbol{\mu}\mapsto\lambda(\boldsymbol{\mu})$ denote the _equilibrium
cost_ map, whose basic properties are summarized in the next proposition.

######  Proposition 1.

Let $\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$ be a
congestion game structure. Then the equilibrium cost map
$\boldsymbol{\mu}\mapsto\lambda(\boldsymbol{\mu})$ is continuous and monotone
in the sense that
$\langle\lambda(\boldsymbol{\mu}_{1})-\lambda(\boldsymbol{\mu}_{2}),\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\rangle\geq
0$ for every
$\boldsymbol{\mu}_{1},\boldsymbol{\mu}_{2}\in\mathbb{R}_{+}^{\mathcal{H}}$. In
particular, each component $\lambda^{h}(\boldsymbol{\mu})$ is nondecreasing
with respect to its own demand $\mu^{h}$. Moreover, the equilibrium resource
costs $\tau_{r}(\boldsymbol{\mu})$ are uniquely defined and continuous.

Proposition 1 is a simple extension of Cominetti et al., (2021, Proposition
3.1) to the multi-commodity setting. See also Hall, (1978) for the case of
strictly increasing costs. For the sake of completeness, we include a proof of
Proposition 1 in Appendix A.

######  Remark 1.

When the cost functions are strictly increasing, thus invertible, Proposition
1 implies that the equilibrium load vector $\boldsymbol{x}(\boldsymbol{\mu})$
is unique for every $\boldsymbol{\mu}\in\mathbb{R}_{+}^{\mathcal{H}}$, and the
map $\boldsymbol{\mu}\mapsto x(\boldsymbol{\mu})$ is continuous. If the costs
are just nondecreasing, the equilibrium loads may be non-unique; there exists
some literature about the characterization of games having the so-called
uniqueness property (see, e.g., Milchtaich,, 2000, Konishi,, 2004,
Milchtaich,, 2005, Meunier and Pradeau,, 2014). Another natural question for
the case of multiple equilibria is whether there exists a continuous selection
$\boldsymbol{\mu}\mapsto x(\boldsymbol{\mu})$.

Although every equilibrium cost $\lambda^{h}$ is nondecreasing in the variable
$\mu^{h}$, it can actually decrease strictly when the demand in some other
commodity increases. It is also possible that the social cost
${\operatorname{\mathsf{SC}}}(\boldsymbol{\mu})=\sum_{h\in\mathcal{H}}\mu^{h}\lambda^{h}(\boldsymbol{\mu})$
decreases along a direction where the total demand
$\sum_{h\in\mathcal{H}}\mu^{h}$ increases (see Fisk,, 1979). In what follows,
we want to determine if a congestion game has an equilibrium selection such
that the resource loads are monotone with respect to an increase in any
demand. This is made precise in the following definition.

######  Definition 2.

A congestion game structure
$\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$ is said to
have a monotonic equilibrium selection (MES) if for each demand vector
$\boldsymbol{\mu}\in\mathbb{R}_{+}^{\mathcal{H}}$ there exists an equilibrium
load vector $\boldsymbol{x}(\boldsymbol{\mu})$ such that for every resource
$r\in\mathcal{R}$ the map
$\boldsymbol{\mu}\mapsto\boldsymbol{x}_{r}(\boldsymbol{\mu})$ is nondecreasing
with respect to each component $\mu^{h}$ of the demand.

In mixed scenarios where some demands increase and other decrease, one
naturally expects that the same will occur for the induced equilibrium loads.
However, it is still of interest to identify groups of resources whose
equilibrium loads vary in the same direction, regardless whether
$\boldsymbol{\mu}$ and $\boldsymbol{\mu}^{\prime}$ are comparable or not. In
such a case, observing an increase/decrease in the load of a specific resource
one can infer that all the remaining loads in the group move in the same
direction. This property is captured by the notion of comonotonicity: a family
of functions $\\{\psi_{i}:\Omega\to\mathbb{R}\\}_{i\in A}$ is _comonotonic_ if
for all $i,j\in A$ we have

$(\forall\omega_{1},\omega_{2}\in\Omega)\quad(\psi_{i}(\omega_{1})-\psi_{i}(\omega_{2}))(\psi_{j}(\omega_{1})-\psi_{j}(\omega_{2}))\geq
0.$ (2.7)

For singleton congestion games, we will identify subsets of resources whose
equilibrium loads exhibit such comonotonic behavior in specific regions of the
space of demands $\mathbb{R}_{+}^{\mathcal{H}}$. Informally, we will show that
a group of commodities that share the same equilibrium cost behave as a single
commodity, and the loads on the resources used by this group are comonotonic.

##  3\. Monotonicity in singleton congestion games

In a _singleton congestion game_ each strategy corresponds to a single
resource. Thus, for every commodity $h\in\mathcal{H}$ the set of feasible
strategies $\mathcal{S}^{h}$ can be viewed as a subset
$\mathcal{R}^{h}\subset\mathcal{R}$ of the set of resources. The following
result shows that the MES property holds in this case.

######  Theorem 3.

Every singleton congestion game
$\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$ has a MES.

###### Proof.

We will first prove the result for strictly increasing cost functions, and
then derive the result for nondecreasing costs by a regularization argument.

Suppose first that the costs $c_{r}(\,\cdot\,)$ are strictly increasing. We
will prove the existence of a MES locally by showing that for every demand
vector $\boldsymbol{\mu}_{0}\in\mathbb{R}_{+}^{\mathcal{H}}$ and every
commodity $h\in\mathcal{H}$, there exists $\varepsilon>0$ such that
$x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})\geq
x_{r}(\boldsymbol{\mu}_{0})$ for all $t\in[0,\varepsilon]$, where
$\boldsymbol{e}^{h}$ is the $h$-th vector of the canonical basis of
$\mathbb{R}^{\mathcal{H}}$. The global MES property throughout the space of
demands then follows from the continuity of the map
$\boldsymbol{\mu}\mapsto\boldsymbol{x}(\boldsymbol{\mu})$ (see Remark 1).

Let $\mathcal{R}_{0}$ be the set of resources such that
$c_{r}(x_{r}(\boldsymbol{\mu}_{0}))=\lambda^{h}(\boldsymbol{\mu}_{0})$. This
set contains the active resources for commodity $h$ but may also include
resources used by other commodities and that are not feasible for $h$. By
continuity of the equilibrium costs (Proposition 1), there exists
$\varepsilon>0$ such that an increase in the demand for commodity $h$ by an
amount $t$ smaller than $\varepsilon$ can only affect the equilibrium loads of
resources in $\mathcal{R}_{0}$, and therefore for $r\notin\mathcal{R}_{0}$ and
$t\in[0,\varepsilon]$ we have
$x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})=x_{r}(\boldsymbol{\mu}_{0})$.
Let us then focus on the resources $r\in\mathcal{R}_{0}$. Fix an arbitrary
$t\in[0,\varepsilon]$ and partition $\mathcal{R}_{0}$ into the three subsets

$\displaystyle\mathcal{R}_{0}^{+}$
$\displaystyle\coloneqq\\{r\in\mathcal{R}_{0}\colon
x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})>x_{r}(\boldsymbol{\mu}_{0})\\},$
(3.1) $\displaystyle\mathcal{R}_{0}^{-}$
$\displaystyle\coloneqq\\{r\in\mathcal{R}_{0}\colon
x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})<x_{r}(\boldsymbol{\mu}_{0})\\},$
(3.2) $\displaystyle\mathcal{R}_{0}^{=}$
$\displaystyle\coloneqq\\{r\in\mathcal{R}_{0}\colon
x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})=x_{r}(\boldsymbol{\mu}_{0})\\}.$
(3.3)

Suppose by contradiction that $\mathcal{R}_{0}^{-}$ is not empty. Since the
total demand at $\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h}$ is larger than the
total demand at $\boldsymbol{\mu}_{0}$, any flow removed from
$\mathcal{R}_{0}^{-}\cup\mathcal{R}_{0}^{=}$ must be transferred to
$\mathcal{R}_{0}^{+}$. This implies that there exists some commodity
$h^{\prime}$ which has feasible resources both in
$\mathcal{R}_{0}^{-}\cup\mathcal{R}_{0}^{=}$ and $\mathcal{R}_{0}^{+}$. This
contradicts the equilibrium condition for that commodity at demand
$\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h}$ because the cost of all resources
in $\mathcal{R}_{0}^{+}$ is strictly higher than the cost of the resources in
$\mathcal{R}_{0}^{-}\cup\mathcal{R}_{0}^{=}$. This establishes the existence
of a MES for the case of strictly increasing costs.

For nondecreasing costs $c_{r}(x_{r})$ we perturb them as
$c^{\varepsilon}_{r}(x_{r})\coloneqq c_{r}(x_{r})+2\varepsilon x_{r}$ with
$\varepsilon>0$, to make them strictly increasing, and then consider the limit
as $\varepsilon$ approaches zero. As recalled in Section 2, the equilibrium
flow $\boldsymbol{x}(\boldsymbol{\mu},\varepsilon)$ for the congestion game
structure
$\mathcal{G}^{\varepsilon}\coloneqq(\mathcal{R},\boldsymbol{c}^{\varepsilon},\boldsymbol{\mathcal{S}})$
is the unique solution of the Beckmann problem (2.5), which in this case has
the form

$\min_{x\in\mathcal{X}_{\mu}}\sum_{r\in\mathcal{R}}C_{r}(x_{r})+\varepsilon\lVert\boldsymbol{x}\rVert^{2},$
(3.4)

with $C_{r}(x_{r})\coloneqq\int_{0}^{x_{r}}c_{r}(z)\ \textup{d}z$. Tikhonov
regularization (see, e.g., Attouch,, 1996, section 1.1) tells us that
$\boldsymbol{x}(\boldsymbol{\mu},\varepsilon)$ converges, as $\varepsilon$
approaches zero, to the minimal norm equilibrium
$\boldsymbol{x}_{0}(\boldsymbol{\mu})$ of the original unperturbed game
$\mathcal{G}$. From the previous case of strictly increasing costs, for each
$\varepsilon>0$ the map
$\boldsymbol{\mu}\mapsto\boldsymbol{x}(\boldsymbol{\mu},\varepsilon)$ is
nondecreasing with respect to each demand $\mu^{h}$, and this property is
inherited by $\boldsymbol{\mu}\mapsto\boldsymbol{x}_{0}(\boldsymbol{\mu})$ in
the limit as $\varepsilon\downarrow 0$, providing a MES as claimed. ∎

######  Remark 2.

The quadratic regularizer $\varepsilon\|\boldsymbol{x}\|^{2}$ was introduced
by Tikhonov in the study of ill-posed inverse problems (Tikhonov,, 1943, 1963,
Tikhonov and Arsenin,, 1977). It is also the basis of _ridge regression_ in
statistics (Hoerl,, 1959, 1962, Hoerl and Kennard,, 1970). In our setting this
is just one choice among others, and can be replaced by a separable
regularizer $\varepsilon\sum_{i=1}^{n}g_{i}(x_{i})$ with
$g_{i}^{\prime}(\,\cdot\,)$ strictly increasing. Every such regularizer
selects a specific optimal solution in the limit when $\varepsilon\downarrow
0$ (see Attouch, (1996, theorem 2.1) and Auslender et al., (1997, proposition
2.5). Moreover, one can verify that the previous proof is still valid and
yields a monotone selection of the set of Wardrop equilibria. In particular,
$\varepsilon\sum_{i=1}^{n}x_{i}\log(x_{i})$ selects the Wardrop equilibrium of
maximal entropy. A similar entropic regularization was used in Rossi et al.,
(1989) to select one among multiple flow decompositions of a Wardrop
equilibrium (see Borchers et al.,, 2015, for a survey of related work). In our
case we deal with multiple equilibria and the regularization is used to obtain
a selection with monotonicity properties. As alternatives one may consider
general penalty schemes of the form
$\varepsilon\sum_{i=1}^{n}\theta(x_{i}/\varepsilon)$, including the classical
log-barrier $\theta(x)=-\log(x)$, the inverse-barrier $\theta(x)=1/x$, the
exponential penalty $\theta(x)=\exp(-x)$, and more (see Cominetti,, 1999). Let
us also mention the multi-scale regularizer
$\sum_{i=1}^{n}\varepsilon^{i}x_{i}^{2}$, which yields a hierarchical
selection principle: select the Wardrop equilibria that have the smallest
first coordinate $x_{1}^{2}$, among these the ones with smallest $x_{2}^{2}$,
and inductively with $x_{3}^{2},\ldots,x_{n}^{2}$.

##  4\. Comonotonicity and Active Regimes in Singleton Congestion Games

Theorem 3 shows that the equilibrium loads in singleton congestion games
respond monotonically when all the demands increase or stay the same. In mixed
cases where some demands increase and others decrease, one can still identify
groups of resources that behave comonotonically in specific regions of the
space of demands. A trivial example is when all commodities can use every
resource $\mathcal{R}^{h}\equiv\mathcal{R}$, so they can be treated as a
single commodity and the equilibrium loads are just nondecreasing functions of
the total demand $\mu_{\mathcal{H}}=\sum_{h\in\mathcal{H}}\mu^{h}$. More
generally, we will show that a subset $\mathcal{C}\subset\mathcal{H}$ of
commodities that have the same equilibrium cost, behave as if they were a
single-commodity on a smaller congestion game restricted to a subset
$\mathcal{R}_{\mathcal{C}}$ of resources, and the equilibrium loads of these
resources are nondecreasing functions of the aggregate demand
$\mu_{\mathcal{C}}$ of the group, so that they are comonotonic.

To state our result precisely, given a single commodity game structure
$\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$, we
partition the space of demands $\mathbb{R}_{+}^{\mathcal{H}}$ into different
regions characterized by the order in which the commodities are ranked by
equilibrium cost. That is, for any fixed weak order $\precsim$ on
$\mathcal{H}$ we consider the set of demands that rank the commodities exactly
in this order, that is (see Example 1 and Fig. 3)

$\Gamma^{\precsim}=\left\\{\boldsymbol{\mu}\in\mathbb{R}_{+}^{\mathcal{H}}\colon\lambda^{h}(\boldsymbol{\mu})\leq\lambda^{h^{\prime}}(\boldsymbol{\mu})\Leftrightarrow
h\precsim h^{\prime}\text{ for all }h,h^{\prime}\in\mathcal{H}\right\\}.$
(4.1)

We recall that the equivalence relation and strict order associated with
$\precsim$ are defined by

$\displaystyle(h^{\prime}\sim h)$ $\displaystyle\text{ if and only if
}(h\precsim h^{\prime})\text{ and }(h^{\prime}\precsim h),$
$\displaystyle(h^{\prime}\succ h)$ $\displaystyle\text{ if and only if
}(h\precsim h^{\prime})\text{ and }\neg(h^{\prime}\precsim h).$

The relation $\sim$ partitions $\mathcal{H}$ into equivalence classes, called
_cost classes_ : two commodities are in the same cost class if and only if
$h\sim h^{\prime}$, that is to say, if and only if
$\lambda^{h}(\boldsymbol{\mu})=\lambda^{h^{\prime}}(\boldsymbol{\mu})$ for all
$\boldsymbol{\mu}\in\Gamma^{\precsim}$. To each cost class $\mathcal{C}$ we
associate the subset $\mathcal{R}_{\mathcal{C}}$ of all the resources
$r\in\mathcal{R}$ that are feasible for some commodity $h\in\mathcal{C}$,
excluding those which are also feasible for higher ranked commodities
$h^{\prime}\succ h$, that is

$\mathcal{R}_{\mathcal{C}}=\left(\cup_{h\in\mathcal{C}}\mathcal{R}^{h}\right)\setminus\left(\cup_{h^{\prime}\succ\mathcal{C}}\mathcal{R}^{h^{\prime}}\right).$
(4.2)

######  Definition 4.

Let $\mathcal{C}$ be a cost class for a weak order $\precsim$ on
$\mathcal{H}$. We let
$\mathcal{G}_{\mathcal{C}}\coloneqq(\mathcal{R}_{\mathcal{C}},\boldsymbol{c},\mathcal{S}_{\mathcal{C}})$
denote the singleton congestion game with a _single commodity_ whose strategy
set $\mathcal{S}_{\mathcal{C}}$ comprises all the singletons in
$\mathcal{R}_{\mathcal{C}}$.

######  Example 1.

$\mathsf{O}$$\mathsf{D}$$x+1$$x$$x+2$

Figure 3. Representation of the regions $\Gamma^{\precsim}$ associated to the
possible orders of the equilibrium costs in Example 1. The first commodity
uses the two top links, and the second commodity uses the bottom two. The
three colors represent the regions $\Gamma^{\precsim}$ for the possible orders
$\precsim$ of the equilibrium costs.

Consider a singleton congestion game with three resources
$\mathcal{R}=\\{r_{1},r_{2},r_{3}\\}$ with affine costs $c_{1}(x)=x+1$,
$c_{2}(x)=x$, $c_{3}(x)=x+2$, and two commodities $\alpha$ and $\beta$ with
$\mathcal{R}^{\alpha}=\left\\{r_{1},r_{2}\right\\}$ and
$\mathcal{R}^{\beta}=\left\\{r_{2},r_{3}\right\\}$. For visualization, Fig. 3
(a) represents this as a routing game on a parallel network, where both
commodities have to move traffic between the two vertices, but each of them is
allowed to use only certain edges. In Fig. 3 (b) the horizontal axis
represents the demand of commodity $\alpha$ and the vertical axis the demand
of $\beta$. The three colors represent the regions $\Gamma^{\precsim}$
corresponding to the possible orders of $\lambda^{\alpha}$ and
$\lambda^{\beta}$. In the top-left region in green
$\lambda^{\alpha}<\lambda^{\beta}$, in the bottom-right region in orange
$\lambda^{\alpha}>\lambda^{\beta}$, whereas in the middle region in purple
$\lambda^{\alpha}=\lambda^{\beta}$. Hence, in the top-left and bottom-right
regions we have two cost classes $\mathcal{C}_{1}=\\{\alpha\\}$ and
$\mathcal{C}_{2}=\\{\beta\\}$, each containing one commodity. However, in the
top-left region the corresponding resource sets are
$\mathcal{R}_{\mathcal{C}_{1}}=\\{r_{1}\\}$ and
$\mathcal{R}_{\mathcal{C}_{2}}=\\{r_{2},r_{3}\\}$, whereas in the bottom-right
region $\mathcal{R}_{\mathcal{C}_{1}}=\\{r_{1},r_{2}\\}$ and
$\mathcal{R}_{\mathcal{C}_{2}}=\\{r_{3}\\}$. The region in purple has a single
cost class $\mathcal{C}=\\{\alpha,\beta\\}$ with
$\mathcal{R}_{\mathcal{C}}=\\{r_{1},r_{2},r_{3}\\}$. The sub-regions delimited
by horizontal and diagonal lines within a colored region, correspond to
different sets of active resources as described later.

######  Remark 3.

The regions $\Gamma^{\precsim}$ can be empty for some orders $\precsim$ (e.g.,
if $h,h^{\prime}\in\mathcal{H}$ are such that
$\mathcal{R}^{h}\subseteq\mathcal{R}^{h^{\prime}}$ we cannot have
$\lambda^{h}(\boldsymbol{\mu})<\lambda^{(h^{\prime})}(\boldsymbol{\mu})$). We
stress that each commodity $h\in\mathcal{H}$ belongs to a unique cost class
$\mathcal{C}$, whereas each resource $r$ belongs to the cost class of the
highest ranked commodity among those for which $r$ is feasible.

Our next result describes the equilibrium within a cost class $\mathcal{C}$:
we show that the loads on the resources in $\mathcal{R}_{\mathcal{C}}$
coincide with those of the single-commodity game $\mathcal{G}_{\mathcal{C}}$.
In other words, in terms of equilibrium loads the commodities in $\mathcal{C}$
behave as if they were a single commodity. This allows in turn to analyze the
comonotonicity of the equilibrium loads on $\mathcal{R}_{\mathcal{C}}$.

######  Theorem 5.

Let $\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$ be a
singleton congestion game structure, and $\Gamma^{\precsim}$ the region
associated with a weak order $\precsim$ on $\mathcal{H}$. Then, for each cost
class $\mathcal{C}$ for $\precsim$ we have:

  1. (a)

For all $\boldsymbol{\mu}\in\Gamma^{\precsim}$ and every equilibrium load
$\boldsymbol{x}$ of $(\mathcal{G},\boldsymbol{\mu})$, the vector
$\bar{\boldsymbol{x}}=(x_{r})_{r\in\mathcal{R}_{\mathcal{C}}}$ is an
equilibrium in the single-commodity game
$(\mathcal{G}_{\mathcal{C}},\mu_{\mathcal{C}})$ with aggregate demand
$\mu_{\mathcal{C}}\coloneqq\sum_{h\in{\mathcal{C}}}\mu^{h}$.

  2. (b)

If $\mathcal{G}_{\mathcal{C}}$ has a unique equilibrium for each demand in
$\mathbb{R}_{+}$, then for $\boldsymbol{\mu}\in\Gamma^{\precsim}$ the
equilibrium loads $x_{r}(\boldsymbol{\mu})$ with
$r\in\mathcal{R}_{\mathcal{C}}$ can be expressed as nondecreasing functions of
the aggregate demand $\mu_{\mathcal{C}}$, which is equivalent to the fact that
the equilibrium loads of the resources in $\mathcal{R}_{\mathcal{C}}$ are
comonotonic in the region $\Gamma^{\precsim}$.

###### Proof.

(a) Let $\boldsymbol{x}$ be an equilibrium load vector of demand
$\boldsymbol{\mu}\in\Gamma^{\precsim}$. We note that every commodity
$h\in\mathcal{C}$ allocates traffic only through resources in
$\mathcal{R}_{\mathcal{C}}$. Indeed, if a commodity $h\in\mathcal{C}$ has a
feasible resource also in $\mathcal{R}_{\mathcal{C}^{\prime}}$ with
$\mathcal{C}^{\prime}\neq\mathcal{C}$, then $h^{\prime}\succ h$ for every
$h^{\prime}\in\mathcal{C}^{\prime}$, which is equivalent to
$\lambda^{h^{\prime}}(\boldsymbol{\mu})>\lambda^{h}(\boldsymbol{\mu})$,
because $\boldsymbol{\mu}\in\Gamma^{\precsim}$. Because
$\boldsymbol{\mu}\in\Gamma^{\precsim}$, all the commodities $h\in\mathcal{C}$
have the same equilibrium cost
$\lambda^{h}(\boldsymbol{\mu})=:\lambda_{\mathcal{C}}(\boldsymbol{\mu})$,
which implies that for every $r,r^{\prime}\in\mathcal{R}_{\mathcal{C}}$ we
have

$x_{r}>0\quad\implies\quad
c_{r}(x_{r})=\lambda_{\mathcal{C}}(\boldsymbol{\mu})\leq
c_{r}^{\prime}(x_{r}^{\prime}).$

Since
$\sum_{r\in\mathcal{R}_{\mathcal{C}}}x_{r}=\sum_{h\in\mathcal{C}}\mu^{h}=\mu_{\mathcal{C}}$,
this shows that the vector
$\bar{\boldsymbol{x}}=(x_{r})_{r\in\mathcal{R}_{\mathcal{C}}}$ is a single-
commodity equilibrium for $\mathcal{G}_{\mathcal{C}}$ with demand
$\mu_{\mathcal{C}}$. It follows that $\lambda_{\mathcal{C}}(\boldsymbol{\mu})$
is in fact a function of the aggregate demand $\mu_{\mathcal{C}}$ and so we
can write it as $\lambda_{\mathcal{C}}(\mu_{\mathcal{C}})$.

(b) By the result in (a), for each $r\in\mathcal{R}_{\mathcal{C}}$ and
$\boldsymbol{\mu}\in\Gamma^{\precsim}$ the equilibrium load
$x_{r}(\boldsymbol{\mu})$ coincides with the unique equilibrium in the single-
commodity game $\mathcal{G}_{\mathcal{C}}$ with demand $\mu_{\mathcal{C}}$,
and therefore it is a function of the aggregate demand $\mu_{\mathcal{C}}$.
Now, according to (Cominetti et al.,, 2021, proposition 3.12) every single-
commodity game on a series-parallel network has a nondecreasing selection of
equilibria, so that $x_{r}(\boldsymbol{\mu})$ is a nondecreasing function of
$\mu_{\mathcal{C}}$. The equivalence with the comonotonicity of the maps
$\boldsymbol{\mu}\mapsto x_{r}(\boldsymbol{\mu})$ for
$r\in\mathcal{R}_{\mathcal{C}}$ throughout the region
$\boldsymbol{\mu}\in\Gamma^{\precsim}$, then follows from a known result (see
e.g., Dellacherie, (1971) and Landsberger and Meilijson, (1994)). Since we
could not find a proof of this latter result in the literature, we include one
in Lemma 12 in Appendix A. ∎

######  Remark 4.

By Remark 1, having strictly increasing costs ensures the uniqueness of
equilibria for $\mathcal{G}_{\mathcal{C}}$, as required in Theorem 5 (b).
Actually, it suffices that no two resources in $\mathcal{R}_{\mathcal{C}}$
have cost functions that are constant and equal on some (possibly different)
non-degenerate intervals. Moreover, for strictly increasing costs the
equilibrium loads $x_{r}(\boldsymbol{\mu})$ for
$r\in\mathcal{R}_{\mathcal{C}}$ and $\boldsymbol{\mu}\in\Gamma^{\precsim}$ are
strictly increasing with $\mu_{\mathcal{C}}$. Indeed, since
$\sum_{r\in\mathcal{R}_{\mathcal{C}}}x_{r}(\boldsymbol{\mu})=\mu_{\mathcal{C}}$,
a strict increase of $\mu_{\mathcal{C}}$ implies that some load
$x_{r}(\boldsymbol{\mu})$ and its corresponding cost
$c_{r}(x_{r}(\boldsymbol{\mu}))$ must strictly increase. However, across
$\Gamma^{\precsim}$ the equilibrium costs of all the resources
$r\in\mathcal{R}_{\mathcal{C}}$ remain equal, so that all their loads
$x_{r}(\boldsymbol{\mu})$ must strictly increase simultaneously.

######  Remark 5.

Theorem 5 (b) implies that comonotonicity fails across different cost classes
$\mathcal{C}\neq\mathcal{C}^{\prime}$: if $\mu_{\mathcal{C}}$ increases and
$\mu_{\mathcal{C}^{\prime}}$ decreases, the equilibrium loads of the resources
$\mathcal{R}_{\mathcal{C}}$ and $\mathcal{R}_{\mathcal{C}^{\prime}}$ will move
in opposite directions. On the contrary, if both aggregate demands move in the
same direction, the same holds for the corresponding equilibrium loads.

######  Remark 6.

The comonotonicity in Theorem 5 (b) may fail when $\mathcal{G}_{\mathcal{C}}$
has multiple equilibria. Consider for instance a variant of Example 1 with
costs $c_{1}(x)=c_{3}(x)=1$ and $c_{2}(x)=x$. When the demand is
$\boldsymbol{\mu}=(2,0)$ the equilibrium sends 1 unit of flow through $r_{1}$
and $r_{2}$, and zero on $r_{3}$. Instead, at demand $\boldsymbol{\nu}=(0,2)$
nothing is sent through $r_{1}$, with 1 unit of traffic on both $r_{2}$ and
$r_{3}$. Hence, despite the fact that at both $\boldsymbol{\mu}$ and
$\boldsymbol{\nu}$ all three resources have the same equilibrium cost equal to
1, the load on resource $r_{1}$ decreases when moving from $\boldsymbol{\mu}$
to $\boldsymbol{\nu}$, whereas the load on resource $r_{3}$ increases, so
these loads are not comonotonic. Theorem 5 (b) does not apply here because the
single-commodity game $\mathcal{G}_{\mathcal{C}}$ on the three resources and
aggregate demand 2 has multiple equilibria.

Although for all demands in $\Gamma^{\precsim}$ the commodities are always
ranked as in $\precsim$, the sets of active resources may vary within such a
region. We may then further decompose $\Gamma^{\precsim}$ into sub-regions
corresponding to different active regimes: for each tuple
$\boldsymbol{\varrho}\coloneqq\left(\varrho^{h}\right)_{h\in\mathcal{H}}$ with
$\varrho^{h}\subset\mathcal{R}^{h}$ we define the _sub-region with active
regime_ $\boldsymbol{\varrho}$ as

$\Gamma^{\precsim}_{\boldsymbol{\varrho}}\coloneqq\left\\{\boldsymbol{\mu}\in\Gamma^{\precsim}:\widehat{\boldsymbol{\mathcal{R}}}(\boldsymbol{\mu})=\boldsymbol{\varrho}\right\\}.$
(4.3)

######  Example 1.

(continued). Consider again the singleton congestion game in Fig. 3. In the
purple region characterized by $\lambda^{\alpha}=\lambda^{\beta}$, with a
single cost class $\mathcal{C}=\\{\alpha,\beta\\}$ and
$\mathcal{R}_{\mathcal{C}}=\\{r_{1},r_{2},r_{3}\\}$, there are three sub-
regions depending on the value of the total demand
$\mu_{\mathcal{C}}=\mu^{\alpha}+\mu^{\beta}$. When $\mu_{\mathcal{C}}\in(0,1)$
both $\alpha$ and $\beta$ use only the central link with active regime
$\varrho^{\alpha}=\varrho^{\beta}=\\{r_{2}\\}$ and equilibrium costs
$\lambda^{\alpha}=\lambda^{\beta}=\mu_{\mathcal{C}}$. For
$\mu_{\mathcal{C}}\in[1,3)$ we have
$\lambda^{\alpha}=\lambda^{\beta}=(1+\mu_{\mathcal{C}})/2$, with $\beta$ using
the central link $\varrho^{\beta}=\\{r_{2}\\}$ whereas $\alpha$ splits the
flow between the top and central link with
$\varrho^{\alpha}=\\{r_{1},r_{2}\\}$. Finally for $\mu_{\mathcal{C}}\geq 3$
the active regime is $\varrho^{\alpha}=\\{r_{1},r_{2}\\}$ and
$\varrho^{\beta}=\\{r_{2},r_{3}\\}$ with equilibrium costs
$\lambda^{\alpha}=\lambda^{\beta}=1+\mu_{\mathcal{C}}/3$. Similarly, the green
region is characterized by $\lambda^{\alpha}<\lambda^{\beta}$ with cost
classes $\mathcal{C}_{1}=\\{\alpha\\}$ and $\mathcal{C}_{2}=\\{\beta\\}$.
Throughout this green region the active regime for $\alpha$ is constant
$\varrho^{\alpha}=\\{r_{1}\\}$, whereas for $\beta$ we have
$\varrho^{\beta}=\\{r_{2}\\}$ if $\mu^{\beta}<2$ and
$\varrho^{\beta}=\\{r_{2},r_{3}\\}$ if $\mu^{\beta}\geq 2$.

The simple structure exhibited by the sub-regions actually holds more
generally: even if the cost functions are nonlinear, the sub-regions are
separated by hyperplanes defined by the aggregate demand of some cost class.
We recall that a _break point_ in a single commodity game is a demand
$\bar{\mu}$ at which the set of active resources changes, i.e., this set is
not constant on any interval $(\bar{\mu}-\varepsilon,\bar{\mu}+\varepsilon)$
with $\varepsilon>0$ (see Cominetti et al.,, 2021, definition 3.4).

######  Theorem 6.

Let $\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$ be a
singleton congestion game structure with strictly increasing costs, and
$\precsim$ a weak order on $\mathcal{H}$. Then, the boundary between the sub-
regions $\Gamma^{\precsim}_{\boldsymbol{\varrho}}$ coincides with the points
$\boldsymbol{\mu}\in\Gamma^{\precsim}$ satisfying at least one of the linear
equations

$\sum_{h\in\mathcal{C}}\mu^{h}=\bar{\mu},$

where $\mathcal{C}$ is a cost class for $\precsim$ and $\bar{\mu}$ is a break
point in the single-commodity game $\mathcal{G}_{\mathcal{C}}$.

###### Proof.

Consider any demand $\boldsymbol{\mu}\in\Gamma^{\precsim}$. By Theorem 5 (a),
the equilibrium loads can be partitioned by cost classes
$(x_{r}(\boldsymbol{\mu}))_{r\in\mathcal{R}_{\mathcal{C}}}$, the latter being
an equilibrium in the single-commodity game $\mathcal{G}_{\mathcal{C}}$. The
equilibrium cost for $\mathcal{G}_{\mathcal{C}}$ is a strictly increasing
function $\mu_{\mathcal{C}}\mapsto\lambda_{\mathcal{C}}(\mu_{\mathcal{C}})$ of
the aggregate demand $\mu_{\mathcal{C}}=\sum_{h\in\mathcal{C}}\mu^{h}$. It
then follows that each load
$x_{r}(\boldsymbol{\mu})=c_{r}^{-1}(\lambda_{\mathcal{C}}(\mu_{\mathcal{C}}))$
for $r\in\mathcal{R}_{\mathcal{C}}$ is also a strictly increasing function of
$\mu_{\mathcal{C}}$.

If $\boldsymbol{\mu}\in\Gamma^{\precsim}$ is on the boundary between two or
more sub-regions $\Gamma^{\precsim}_{\boldsymbol{\varrho}}$, the set of active
resources changes locally at $\boldsymbol{\mu}$ and then there must exist a
cost class $\mathcal{C}$ whose set of active resources also changes locally at
$\mu_{\mathcal{C}}$, which is therefore a break point in the single-commodity
game $\mathcal{G}_{\mathcal{C}}$. ∎

######  Example 2.

$\mathsf{O}$$\mathsf{D}$$x^{2}+1$$x^{2}$$x^{2}+2$

Figure 4. An example with quadratic costs. The first commodity uses the two
top links, and the second commodity uses the bottom two. The three colors
represent the regions $\Gamma^{\precsim}$ for the possible orders $\precsim$
of the equilibrium costs. The straight lines within each region separate sub-
regions corresponding to different active regimes. The regions
$\Gamma^{\precsim}$ are not convex, but the boundary between sub-regions is
still affine.

Consider the variant of Example 1 with quadratic costs as in Fig. 4. The
regions $\Gamma^{\precsim}$ are no longer convex, but the sub-regions for
different active regimes are still delimited by the hyperplanes described in
Theorem 6. In the purple region where $\lambda^{\alpha}=\lambda^{\beta}$ with
a single cost class $\mathcal{C}=\\{\alpha,\beta\\}$ and
$\mathcal{R}_{\mathcal{C}}=\\{r_{1},r_{2},r_{3}\\}$, the equilibrium loads of
all the resources are strictly increasing functions of the total demand
$\mu_{\mathcal{C}}=\mu^{\alpha}+\mu^{\beta}$, and the active regimes present
break points at $\mu_{\mathcal{C}}=1$ and $\mu_{\mathcal{C}}=1+\sqrt{2}$, that
is,

$\begin{cases}\varrho^{\alpha}=\\{r_{2}\\}\text{ and
}\varrho^{\beta}=\\{r_{2}\\}&\text{if }~{}\mu_{\mathcal{C}}\in[0,1),\\\
\varrho^{\alpha}=\\{r_{1},r_{2}\\}\text{ and
}\varrho^{\beta}=\\{r_{2}\\}&\text{if
}~{}\mu_{\mathcal{C}}\in[1,1+\sqrt{2}),\\\
\varrho^{\alpha}=\\{r_{1},r_{2}\\}\text{ and
}\varrho^{\beta}=\\{r_{2},r_{3}\\}&\text{if
}~{}\mu_{\mathcal{C}}\in[1+\sqrt{2},\infty).\end{cases}$ (4.4)

Similarly, in the green region where $\lambda^{\alpha}<\lambda^{\beta}$ with
cost classes $\mathcal{C}_{1}=\\{\alpha\\}$ and $\mathcal{C}_{2}=\\{\beta\\}$,
we have $\varrho^{\beta}=\\{r_{2}\\}$ for $\mu^{\beta}<\sqrt{2}$ and
$\varrho^{\beta}=\\{r_{2},r_{3}\\}$ for $\mu^{\beta}\geq\sqrt{2}$, whereas
$\varrho^{\alpha}=\\{r_{1}\\}$ is constant.

######  Remark 7.

The monotonicity result in Cominetti et al., (2021, proposition 3.12) implies
that the number of active regimes in a single-OD routing game on a series-
parallel network is at most the number of paths. This bound does not hold for
multiple commodities. In a singleton congestion game there are
$\prod_{h\in\mathcal{H}}\left(2^{\left\lvert\mathcal{R}^{h}\right\rvert}-1\right)$
potential combinations for
$\widehat{\boldsymbol{\mathcal{R}}}(\boldsymbol{\mu})$, and this bound may be
attained (see Example 3 below). This is not the case for single-commodity
routing games: if we consider a subnetwork composed by only two paths, it is
always series-parallel and only two of the three nonempty subsets of paths can
actually correspond to an active regime
$\widehat{\boldsymbol{\mathcal{R}}}(\mu)$ for some $\mu\in[0,+\infty)$.

######  Example 3.

Let us build a multi-commodity routing game that attains the maximal bound for
the number of active regimes. Take $m$ a positive integer and consider a
routing game on a parallel network with $m$ resources (links)
$\mathcal{R}=\\{1,\ldots,m\\}$ with cost functions

$(\forall i=1,\dots,m)\quad c_{i}(x_{i})=x_{i}+i,$

and $m+1$ commodities where each commodity $i=1,\ldots,m$ can only use one
player-specific resource $\mathcal{R}^{i}=\\{i\\}$, whereas commodity $(m+1)$
can use all the resources $\mathcal{R}^{m+1}=\mathcal{R}$.

We claim that $\widehat{\boldsymbol{\mathcal{R}}}(\boldsymbol{\mu})$ assumes
the maximum number
$\prod_{i=1}^{m+1}\left(2^{\left\lvert\mathcal{R}^{i}\right\rvert}-1\right)=2^{m}-1$
of possible active regimes as the demands $\boldsymbol{\mu}$ vary. Indeed, for
each commodity $i\leq m$ the active regime is always $\\{i\\}$, whereas every
nonempty subset $\varrho^{m+1}\subset\mathcal{R}$ is the active regime of the
$(m+1)$-th commodity for some demand $\boldsymbol{\mu}$. Namely, let
$i_{\max}=\max\\{i\in\varrho^{m+1}\\}$ and consider the demand

$\displaystyle(\forall i\leq m)\quad\mu^{i}$
$\displaystyle=\begin{cases}0&\text{if }i\in\varrho^{m+1},\\\
i_{\max}&\text{if }i\notin\varrho^{m+1},\\\ \end{cases}$
$\displaystyle\mu^{m+1}$ $\displaystyle=\sum_{i\in\varrho^{m+1}}(i_{\max}-i).$

Then, the unique equilibrium is such that commodity $(m+1)$ allocates
$i_{\max}-i$ to each resource $i\in\varrho^{m+1}$ with cost $i_{\max}$,
whereas every resource $i\notin\varrho^{m+1}$ has a cost
$i_{\max}+i>i_{\max}$, so that the active regime for commodity $(m+1)$ is
exactly $\varrho^{m+1}$.

##  5\. Beyond Singleton Congestion Games

In this section we consider more general nonatomic congestion games, and we
discuss a possible extension of the fact that for single-commodity routing
games over a _series-parallel network_ the equilibrium edge loads are
nondecreasing in the traffic demand (Cominetti et al.,, 2021, proposition
3.12). For single-commodity routing games this is basically the most one can
expect, since every network which is not series-parallel contains a Braess
subnetwork for which it is well known that there exists costs that produce
equilibrium loads that decrease on some ranges of the demand (see Fig. 2).

Unfortunately, for multi-commodity routing games the topology of the network
alone does not provide a criterion for the monotonicity of edge loads. To
better understand this general case, we start defining the class of
constrained routing games.

######  Definition 7.

A constrained routing game (CRG) is a triple
$({G},c,\boldsymbol{\mathcal{P}})$ where

  * •

${G}=(\mathcal{V},\mathcal{E})$ is a directed multigraph with vertex set
$\mathcal{V}$ and edge set $\mathcal{E}$,

  * •

$\boldsymbol{c}=(c_{e})_{e\in\mathcal{E}}$ is a vector of edge cost functions,

  * •

$\boldsymbol{\mathcal{P}}=(\mathcal{P}^{h})_{h\in\mathcal{H}}$ with
$\mathcal{P}^{h}$ a nonempty set of paths between an origin
$\mathsf{O}^{h}\in\mathcal{V}$ and a destination
$\mathsf{D}^{h}\in\mathcal{V}$ for a finite family of commodities
$\mathcal{H}$.

This defines a congestion game structure with resource set
$\mathcal{R}=\mathcal{E}$ with costs
$\boldsymbol{c}=(c_{e})_{e\in\mathcal{E}}$, and commodity set $\mathcal{H}$
with strategies $\mathcal{S}^{h}=\mathcal{P}^{h}$. Notice that in our setting
different commodities could share the same OD pair and have some common paths.
In a _standard routing game_ each OD pair corresponds to a single commodity
and $\mathcal{P}^{h}$ includes all the paths from $\mathsf{O}^{h}$ to
$\mathsf{D}^{h}$. All the examples in Section 4 are in fact constrained
routing games, including the Braess’ network in Fig. 2, which is a standard
routing game.

Although restricting the paths to a subset might seem a minor detail, it is in
fact a flexible feature that allows to represent any congestion game as a
constrained routing game. Furthermore, we can also turn this routing game into
a _common- OD_ where all commodities have the same origin and destination, by

  * •

adding a super-source $\mathsf{O}$ connected to each $\mathsf{O}^{h}$ by a
zero-cost edge $(\mathsf{O},\mathsf{O}^{h})$,

  * •

adding a super-sink $\mathsf{D}$ connected through zero-cost edges
$(\mathsf{D}^{h},\mathsf{D})$, and

  * •

appending the edges $(\mathsf{O},\mathsf{O}^{h})$ and
$(\mathsf{D}^{h},\mathsf{D})$ to each path of commodity $h$.

The next proposition shows directly that every congestion game is equivalent
to a common-OD routing game over an extremely simple network, and all the
complexity of the game is in fact encoded into the feasible sets of paths.

Formally, two congestion games $\mathcal{G}$ and $\breve{\mathcal{G}}$ are
said to be _equivalent_ if there exist one-to-one correspondences
$h\leftrightarrow\breve{h}$ between their commodities and
$s\leftrightarrow\breve{s}$ between strategies, such that for each demand
$\boldsymbol{\mu}$ and every feasible flow $\boldsymbol{f}$ for the first
game, the flow $\breve{\boldsymbol{f}}$ defined as
$\breve{f}_{\breve{s}}=f_{s}$ is feasible in the second game and the strategy
costs coincide
$\breve{c}_{\breve{s}}(\breve{\boldsymbol{f}})=c_{s}(\boldsymbol{f})$. In this
case the equilibria of both games are also in one-to-one correspondence.

######  Proposition 8.

Every congestion game is equivalent to a common-OD constrained routing game
over a series-parallel network.

###### Proof.

Consider a congestion game structure with resources
${\mathcal{R}}=\\{r_{1},\dots,r_{m}\\}$. Consider the series-parallel network
in the figure below,

$\mathsf{O}$$\mathsf{D}$

$c_{r_{1}}(x)$$c_{r_{2}}(x)$$0$$0$$\dots$$\dots$$c_{r_{m}}(x)$$0$

where each resource is represented by two parallel edges: one of them has the
original resource cost $c_{r}(\,\cdot\,)$, and the other edge provides a
bypass with zero cost. Any strategy $s\subseteq{\mathcal{R}}$ can be
represented as a path joining $\mathsf{O}$ to $\mathsf{D}$ that takes the top
edge for each resource in $s$, and the bypass otherwise. We can then represent
the commodities of the congestion game in the routing game by prescribing that
they all have the same origin $\mathsf{O}$ and same destination $\mathsf{D}$,
whereas the feasible paths correspond to their feasible strategies in the
original congestion game. ∎

Regarding the previous result, one may naturally ask whether a given nonatomic
congestion game is equivalent to an _unconstrained_ nonatomic routing game. We
are not aware of any result on this question, apart from the somewhat related
result by Milchtaich, (2013), who showed that every finite game can be
represented as a _weighted_ atomic routing game.

As mentioned above, for multi-OD routing games a series-parallel network
topology does not suffice to guarantee the monotonicity of the equilibrium
loads. Indeed, Examples 4 and 5 below show that there exist common-OD
constrained routing games such that:

  * •

${G}$ is series-parallel;

  * •

every commodity uses paths $\mathcal{P}^{h}$ that form a series-parallel
subnetwork;

  * •

the equilibrium loads $\boldsymbol{x}(\boldsymbol{\mu})$ are unique; but

  * •

the map $\boldsymbol{\mu}\mapsto\boldsymbol{x}(\boldsymbol{\mu})$ is not a
MES.

######  Example 4.

Consider Fisk’s network and add bypass edges $e_{4},e_{5}$ with zero cost as
in Fig. 5(b), producing commodities $h_{1}$, $h_{2}$, $h_{3}$ where
$\mathsf{O}^{h}=a$, $\mathsf{D}^{h}=c$ for every commodity $h$, and
$\mathcal{P}^{h_{1}}=\\{(e_{1},e_{5})\\}$,
$\mathcal{P}^{h_{2}}=\\{(e_{4},e_{2})\\}$, and
$\mathcal{P}^{h_{3}}=\\{(e_{1},e_{2}),e_{3}\\}$. This defines an equivalent
common-OD constrained routing game. As noted in the introduction, an increment
in the demand of $h_{1}$ pushes commodity $h_{3}$ to divert more flow towards
the direct path $e_{3}$, thus reducing the load on $e_{2}$ (see Fisk,, 1979).

$e_{1}$$e_{2}$$e_{3}$$a$$b$$c$$x$$x+90$$x$ (a) Fisk’s Network.

$a$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$b$$c$$x$$x+90$$x$$0$$0$ (b) An
embedding of Fisk’s network in a series-parallel common-OD network.

Figure 5. Fisk’s multi-commodity network can be embedded in a series-parallel
network with a common-OD, by adding two edges with zero cost.

######  Example 5.

Monotonicity can also fail in a single-OD constrained routing game, even on a
series-parallel graph. Indeed, the standard Braess’ routing game in Fig. 2
corresponds to the single-commodity congestion game structure
$(\mathcal{E},\boldsymbol{c},\\{\mathsf{O}\,v_{1}\,v_{2}\mathsf{D},\mathsf{O}\,v_{1}\mathsf{D},\mathsf{O}\,v_{2}\mathsf{D}\\})$.
Using Proposition 8 this is equivalent to a single-OD constrained routing game
on a series parallel network, for which the MES property fails.

These examples show that in addition to a series-parallel topology we need to
impose further conditions on how the commodities overlap. To this end we
introduce the notions of _product_ and _union_ of two congestion games
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$. Informally, the product can be seen
as a connection in series in which we consider all combinations of a commodity
$i\in\mathcal{H}_{1}$ followed by a commodity $j\in\mathcal{H}_{2}$ to form a
product commodity $i\otimes j$. Similarly, the union game can be seen as a
parallel connection that includes all the original commodities
$\mathcal{H}_{1}\cup\mathcal{H}_{2}$, without introducing any new commodity
that picks resources simultaneously from $\mathcal{R}_{1}$ and
$\mathcal{R}_{2}$.

######  Definition 9.

Let
$\mathcal{G}_{1}=(\mathcal{R}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{S}}_{1})$
and
$\mathcal{G}_{2}=(\mathcal{R}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{S}}_{2})$
be two congestion games with disjoint resource sets
$\mathcal{R}_{1}\cap\mathcal{R}_{2}=\varnothing$. The _product_ and _union_ of
these games are both defined on the resource set
$\mathcal{R}=\mathcal{R}_{1}\cup\mathcal{R}_{2}$ with their original cost
functions. Specifically:

  * •

The _product game_ $\mathcal{G}_{1}\otimes\mathcal{G}_{2}$ includes all the
commodities $i\otimes j$ for $(i,j)\in\mathcal{H}_{1}\times\mathcal{H}_{2}$,
defined by the strategy sets $\mathcal{S}^{i\otimes j}=\\{s_{1}\cup
s_{2}:(s_{1},s_{2})\in\mathcal{S}_{1}^{i}\times\mathcal{S}_{2}^{j}\\}$.

  * •

The _union game_ $\mathcal{G}_{1}\cup\mathcal{G}_{2}$ is the congestion game
with commodities $\mathcal{H}=\mathcal{H}_{1}\cup\mathcal{H}_{2}$ with their
original strategy sets $\mathcal{S}_{1}^{i}$ for $i\in\mathcal{H}_{1}$ and
$\mathcal{S}_{2}^{j}$ for $j\in\mathcal{H}_{2}$.

  * •

A _product-union_ game is a congestion game which can be constructed starting
from singleton congestion games and applying a finite number of product or
union operations between games already constructed.

######  Theorem 10.

Every product-union congestion game has a MES.

###### Proof.

By induction and Theorem 3, it suffices to show that the MES property is
preserved under product and union of games. To this end, let $\mathcal{G}_{1}$
and $\mathcal{G}_{2}$ be two congestion game structures with MES’s
$\boldsymbol{\mu}_{1}\mapsto\boldsymbol{x}_{1}(\boldsymbol{\mu}_{1})$ and
$\boldsymbol{\mu}_{2}\mapsto\boldsymbol{x}_{2}(\boldsymbol{\mu}_{2})$
respectively. Then we prove the two parts:

  * (a)

_The product game $\mathcal{G}_{1}\otimes\mathcal{G}_{2}$ has a MES_. Let
$\boldsymbol{\mu}=(\mu^{i\otimes
j})_{i\in\mathcal{H}_{1},j\in\mathcal{H}_{2}}$ with $\mu^{i\otimes j}$ the
demand for the commodity $i\otimes j$ in the product game. An equilibrium for
$\boldsymbol{\mu}$ can be obtained by superposing
$\boldsymbol{x}_{1}(\boldsymbol{\mu}_{1})$ on the resources $\mathcal{R}_{1}$
and $\boldsymbol{x}_{2}(\boldsymbol{\mu}_{2})$ on the resources
$\mathcal{R}_{2}$, computed respectively with demands $\boldsymbol{\mu}_{1}$
and $\boldsymbol{\mu}_{2}$ given by

$(\forall i\in\mathcal{H}_{1})\hskip
8.61108pt\mu_{1}^{i}=\sum_{j\in\mathcal{H}_{2}}\mu^{i\otimes
j}\quad;\quad(\forall j\in\mathcal{H}_{2})\hskip
8.61108pt\mu_{2}^{j}=\sum_{i\in\mathcal{H}_{1}}\mu^{i\otimes j}.$ (5.1)

Since an increase of any demand $\mu^{i\otimes j}$ induces an increase in the
demands $\mu_{1}^{i}$ and $\mu_{2}^{j}$, the loads in
$\boldsymbol{x}_{1}(\boldsymbol{\mu}_{1})$ and
$\boldsymbol{x}_{2}(\boldsymbol{\mu}_{2})$ increase, so that this superposed
equilibrium provides a MES for the product game.

  * (b)

_The union game $\mathcal{G}_{1}\cup\mathcal{G}_{2}$ has a MES_. For each
demand $\boldsymbol{\mu}=(\boldsymbol{\mu}_{1},\boldsymbol{\mu}_{2})$ in the
union game we can directly find an equilibrium by superposing
$\boldsymbol{x}_{1}(\boldsymbol{\mu}_{1})$ on the resources $\mathcal{R}_{1}$
and $\boldsymbol{x}_{2}(\boldsymbol{\mu}_{2})$ on the resources
$\mathcal{R}_{2}$. Since the loads in these two equilibria are monotone with
respect to each individual demand, the same holds for their superposition
which provides a MES for the union game. ∎

######  Remark 8.

The common-OD constrained routing game of Example 4, in which Fisk’s network
is embedded, is not a product-union congestion game: the strategy set of
$h_{3}$ cannot be obtained as a strategy set of a previously present commodity
when doing the union game. For a different reason, the common-OD series-
parallel constrained routing game in Example 5 is not a product/union game
either. Indeed, its network would be made of 5 two-link parallel network in
series, each one associated to a resource, i.e., an edge of the Braess’
network. The classical Braess’ routing game has a single commodity with three
strategies, and a strategy set with cardinality 3 cannot be obtained as the
Cartesian product of the strategy sets of the 5 two-link parallel networks
connected in series. A series of Pigou’s has strong limitations, for example,
a commodity with a number of paths divisible by a prime larger than 2 is not
constructible as in Definition 9.

Whereas product-union games were defined for general congestion games, they
can also be described as constrained routing games with a specific structure.
The following representation is also more natural compared to the one in
Proposition 8.

######  Theorem 11.

Every product-union congestion game
$\mathcal{G}=(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}})$ is
equivalent to a common-OD constrained routing game
$({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ such that

  1. (i)

the graph ${G}$ is series-parallel,

  2. (ii)

for each commodity $h$ all the paths in $\mathcal{P}^{h}$ visit the same
vertices in the same order,

  3. (iii)

for every two paths $p_{1},p_{2}\in\mathcal{P}^{h}$ and edges $e_{1}\in p_{1}$
and $e_{2}\in p_{2}$ connecting two subsequent vertices, the paths obtained
from $p_{1}$ and $p_{2}$ by exchanging $e_{1}$ with $e_{2}$ also belong to
$\mathcal{P}^{h}$.

Furthermore, every common-OD constrained routing game satisfying (i), (ii),
(iii), is a product-union congestion game.

###### Proof.

Every product-union game is constructed starting with singleton congestion
games and applying a finite number of product or union operations. We start by
noting that every singleton congestion game is equivalent to a constrained
routing game on a parallel network with two vertices connected by links
corresponding to the resources of the singleton congestion game, and any such
game satisfies (i), (ii), (iii). Hence, it suffices to show that these
properties are preserved under product and union operations.

Consider two congestion games
$\mathcal{G}_{1}=(\mathcal{R}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{S}}_{1})$
and
$\mathcal{G}_{2}=(\mathcal{R}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{S}}_{2})$
which are respectively equivalent to common-OD constrained routing games
$({G}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{P}}_{1})$ and
$({G}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{P}}_{2})$ satisfying (i),
(ii), (iii).

The product game $\mathcal{G}_{1}\otimes\mathcal{G}_{2}$ is then equivalent to
the constrained routing game
$(\widetilde{G},\widetilde{\boldsymbol{c}},\widetilde{\boldsymbol{\mathcal{P}}})$
where $\widetilde{G}$ is obtained by joining in series the graphs ${G}_{1}$
and ${G}_{2}$, the costs $\widetilde{\boldsymbol{c}}$ are the cost functions
given by $\boldsymbol{c}_{1}$ and $\boldsymbol{c}_{2}$ on the corresponding
edges, and the commodities are given by the sets of paths obtained choosing
commodities $h_{1}$ for
$({G}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{P}}_{1})$ and $h_{2}$ for
$({G}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{P}}_{2})$, and joining every
path in $\mathcal{P}^{h_{1}}$ with every path in $\mathcal{P}^{h_{2}}$ to
construct paths in $\widetilde{G}$. Moreover,
$(\widetilde{G},\widetilde{\boldsymbol{c}},\widetilde{\boldsymbol{\mathcal{P}}})$
satisfies (i), (ii), (iii) because
$({G}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{P}}_{1})$ and
$({G}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{P}}_{2})$ do.

Similarly, the union game $\mathcal{G}_{1}\cup\mathcal{G}_{2}$ is equivalent
to the constrained routing game
$(\bar{G},\bar{\boldsymbol{c}},\bar{\boldsymbol{\mathcal{P}}})$ where
$\bar{G}$ is obtained joining in parallel ${G}_{1}$ and ${G}_{2}$, the costs
$\bar{\boldsymbol{c}}$ are the cost functions given by $\boldsymbol{c}_{1}$
and $\boldsymbol{c}_{2}$ on the corresponding edges, and the commodities are
given by the commodities of
$({G}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{P}}_{1})$ and
$({G}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{P}}_{2})$. Also in this
case, the routing game
$(\bar{G},\bar{\boldsymbol{c}},\bar{\boldsymbol{\mathcal{P}}})$ satisfies (i),
(ii), (iii) because
$({G}_{1},\boldsymbol{c}_{1},\boldsymbol{\mathcal{P}}_{1})$ and
$({G}_{2},\boldsymbol{c}_{2},\boldsymbol{\mathcal{P}}_{2})$ do.

This completes the proof of the first claim of the theorem.

Conversely, notice that every series-parallel graph ${G}$ is constructed
starting with parallel networks and joining them in series or in parallel for
a finite number of times. Suppose that a common-OD constrained routing game
$({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ satisfies (i), (ii), (iii).

If the graph ${G}$ is obtained by joining in series two graphs ${G}_{1}$ and
${G}_{2}$, we can endow them with cost functions which associate costs to
edges as in $\boldsymbol{c}$. Furthermore, given a commodity $h$ for
$({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ we can define commodities
$h_{1}$ on ${G}_{1}$ and $h_{2}$ on ${G}_{2}$ by determining for $i=1,2$ the
set of paths

$\mathcal{P}^{h_{i}}=\\{p\text{ path in }{G}_{i}\text{ s.t. }p\text{ is part
of a path in }\mathcal{P}^{h}\\}.$

Since $({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ satisfies (iii), we have
$\mathcal{P}^{h}=\mathcal{P}^{h_{1}}\times\mathcal{P}^{h_{2}}$, so that
$({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ is the product game of the two
constrained routing game just defined on ${G}_{1}$ and ${G}_{2}$.

If the graph ${G}$ is obtained by joining in parallel two graphs ${G}_{1}$ and
${G}_{2}$, then we can assume that the direct links from the origin and the
destination of ${G}$ are all contained in one of the two. We can again endow
${G}_{1}$ and ${G}_{2}$ with cost functions which associate costs to edges as
in $\boldsymbol{c}$. Furthermore because of property (ii), for every commodity
$h$ of $({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ the paths in
$\mathcal{P}^{h}$ all belong to one between ${G}_{1}$ and ${G}_{2}$. This
allows to define for each commodity of
$({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$, a commodity either in
${G}_{1}$ or ${G}_{2}$, so that
$({G},\boldsymbol{c},\boldsymbol{\mathcal{P}})$ is the union game of the two
constrained routing game just defined on ${G}_{1}$ and ${G}_{2}$. ∎

######  Remark 9.

Note that Braess’ classical example in Fig. 2 satisfies (ii) and (iii), but
does not satisfy (i). Fisk’s network embedding of Example 4 satisfies (i) and
(iii) but does not satisfy (ii). Finally, the constrained routing game of
Example 5, obtained by embedding Braess’ commodity in a series-parallel graph
as in Proposition 8, satisfies (i) and (ii), but does not satisfy (iii).

######  Remark 10.

Conditions (i), (ii), (iii) in Theorem 11 can be equivalently stated by
requiring that all feasible paths for a commodity $h$ visit a specific ordered
sequence of nodes; between successive nodes only a specific subset of parallel
links are allowed; and $\mathcal{P}^{h}$ includes all possible paths in this
subnetwork. Still another equivalent description is to require that for any
two paths $p_{1},p_{2}\in\mathcal{P}^{h}$ the mixed path where we follow
$p_{1}$ up to an intermediate node and then continue with $p_{2}$ is also in
$\mathcal{P}^{h}$.

##  6\. Summary and open problems

This paper studied the monotonicity of equilibrium travel times and
equilibrium loads in response to variations of the demands, identifying
conditions under which the paradoxical phenomena of non-monotonicity cannot
happen. We considered the general setting of congestion games, with a special
focus on multi-commodity singleton congestion games for which we established
in Theorem 3 the monotonicity of equilibrium loads with respect to the demand
of every single commodity.

We next explored the notion of comonotonicity, which captures the idea that
different resource loads jointly increase or decrease after variations of the
demands. Theorem 5 described how comonotonicity is connected to the structure
of equilibria in terms of how the commodities are ranked by cost and how the
resources become active or inactive as the demands vary. Theorem 6
complemented this by a structural result on the regions of the space of
demands for which the same sets of resources are used at equilibrium.

Theorem 10 extended the study of monotonicity from singleton congestion games
to the larger class of congestion games having a product-union structure,
reminiscent of the concept of a series-parallel network. Finally, we derived
an embedding that maps congestion games into constrained routing games (see
Proposition 8) and characterized the classes of congestion games with good
monotonicity properties by embedding them into routing games (see Theorem 11).
This last result sheds light on the features that produce the paradoxes and
showcases the difference between the single and multiple OD networks. When the
network has a single OD pair, its topology is the sole relevant factor to
guarantee the monotonicity of equilibrium loads. In the multiple OD case the
structure of the available routes for each OD pair also plays a crucial role.

A first open question not addressed in this paper, and which could be
interesting to explore, is how the structural results on the regions
$\Gamma^{\precsim}$ and sub-regions $\Gamma^{\precsim}_{\varrho}$ for the
different active regimes might be exploited to devise an algorithm for
building a curve of equilibria along a demand curve, analog to the path-
following method for piece-wise affine costs developed by Klimm and Warode,
(2022). A basic question here is to investigate the geometry of the regions
$\Gamma^{\precsim}$ for specific classes of cost functions. For the special
case of Bureau of Public Roads (BPR) costs, we conjecture that the boundaries
between these regions are asymptotic to straight lines through the origin.
This would imply that when the demands are scaled proportionally, the regimes
will not repeat and the curve will eventually enter into a particular
asymptotic region $\Gamma^{\precsim}$ and remain there forever. The latter
could inspire a path following algorithm to build a curve of equilibria.

A second open problem is to find an algorithm to recognize product-union
congestion games. In this regard, one could be tempted to use the equivalent
game in Proposition 8 for which (i) and (ii) in Theorem 11 hold trivially, so
that only (iii) would need to be checked. Unfortunately, the product-union
property is not preserved under equivalence: for instance, a singleton
congestion game with only one commodity is product-union by definition, but
its equivalent representation in Proposition 8 is not because property (iii)
fails. This suggests that recognizing product-union congestion games is not
straightforward. As a possible starting point to address this question, one
might try to adapt the existing algorithms for recognizing series-parallel
networks (see Valdes et al.,, 1982, He and Yesha,, 1987, Eppstein,, 1992).

### Acknowledgments

Valerio Dose and Marco Scarsini are members of GNAMPA-INdAM. Their work was
partially supported by the GNAMPA project CUP_E53C22001930001 _“Limiting
behavior of stochastic dynamics in the Schelling segregation model”_ , and by
the MIUR PRIN 2017 Project ALGADIMAR _“Algorithms, Games, and Digital
Markets”_. Roberto Cominetti’s research was supported by Proyecto Anillo
ANID/PIA/ACT192094.

##  Appendix A Supplementary proofs

###### Proof of Proposition 1.

Let $(\mathcal{R},\boldsymbol{c},\mathcal{S})$ be a nonatomic congestion game
structure. For every demand $\boldsymbol{\mu}\in\mathbb{R}_{+}^{k}$, let
$V(\boldsymbol{\mu})$ be the minimum value of the Beckmann potential as in Eq.
2.5, that is,

$V(\boldsymbol{\mu})=\min_{\boldsymbol{x}\in\mathcal{X}_{\boldsymbol{\mu}}}\sum_{r\in\mathcal{R}}C_{r}(x_{r}).$
(A.1)

We obtain the result as a consequence of convex duality. Consider the function
$\varphi_{\boldsymbol{\mu}}:\mathbb{R}^{n}\times\mathbb{R}^{\mathcal{H}}\to\mathbb{R}\cup\\{+\infty\\}$
given by

$\varphi_{\boldsymbol{\mu}}(\boldsymbol{f},\boldsymbol{z})=\begin{cases}\sum_{r\in\mathcal{R}}C_{r}\left(\sum_{s^{\prime}\ni
r}f_{s^{\prime}}\right)&\text{if }\boldsymbol{f}\geq\boldsymbol{0},\
\sum_{s\in\mathcal{S}^{h}}f_{s}=\mu^{h}+z^{h}\text{ for every
}h\in\mathcal{H},\\\ +\infty&\text{otherwise},\end{cases}$ (A.2)

which is a proper closed convex function. Letting
$v_{\boldsymbol{\mu}}(\boldsymbol{z})$ denote the optimal value function of
the primal problem

$(\mathsf{P}_{\boldsymbol{\mu}})\quad\inf_{\boldsymbol{f}}\varphi_{\boldsymbol{\mu}}(\boldsymbol{f},\boldsymbol{z}),$
(A.3)

we have
$V(\boldsymbol{\mu}+\boldsymbol{z})=v_{\boldsymbol{\mu}}(\boldsymbol{z})$ and,
in particular, $V(\boldsymbol{\mu})=v_{\boldsymbol{\mu}}(\boldsymbol{0})$.

Since $\varphi_{\boldsymbol{\mu}}$ is convex, we have that
$\boldsymbol{z}\mapsto
v_{\boldsymbol{\mu}}(\boldsymbol{z})=V(\boldsymbol{\mu}+\boldsymbol{z})$ is
also convex, from which we deduce that $\boldsymbol{\mu}\rightarrow
V(\boldsymbol{\mu})$ is convex. Moreover, the perturbed function
$\varphi_{\boldsymbol{\mu}}$ yields a corresponding dual

$(\mathsf{D}_{\boldsymbol{\mu}})\quad\min_{\lambda\in\mathbb{R}^{\mathcal{H}}}\varphi_{\boldsymbol{\mu}}^{*}(\boldsymbol{0},\boldsymbol{\lambda}),$
(A.4)

where $\varphi_{\boldsymbol{\mu}}^{*}$ is the Fenchel conjugate function, that
is,

$\begin{split}\varphi_{\boldsymbol{\mu}}^{*}(\boldsymbol{0},\boldsymbol{\lambda})&=\sup_{\boldsymbol{f},\boldsymbol{z}}~{}\langle\boldsymbol{0},\boldsymbol{f}\rangle+\langle\boldsymbol{\lambda},\boldsymbol{z}\rangle-\varphi_{\boldsymbol{\mu}}(\boldsymbol{f},\boldsymbol{z})\\\
&=\sup_{\boldsymbol{f}\geq\boldsymbol{0}}\sum_{h\in\mathcal{H}}\left(\lambda^{h}\left(\sum_{s\in\mathcal{S}^{h}}f_{s}-\mu^{h}\right)\right)-\sum_{r\in\mathcal{R}}C_{r}\left(\sum_{s^{\prime}\ni
r}f_{s^{\prime}}\right).\end{split}$ (A.5)

Since $V(\boldsymbol{\mu}^{\prime})$ is finite for all
$\boldsymbol{\mu}^{\prime}\in\mathbb{R}_{+}^{\mathcal{H}}$, it follows that
$v_{\boldsymbol{\mu}}(\boldsymbol{z})=V(\boldsymbol{\mu}+\boldsymbol{z})$ is
finite for $\boldsymbol{z}$ in some interval around $\boldsymbol{0}$, and then
the convex duality theorem implies that there is no duality gap and the
subgradient $\nabla v_{\boldsymbol{\mu}}(\boldsymbol{0})$ at
$\boldsymbol{z}=\boldsymbol{0}$ coincides with the optimal solution set
$\mathsf{S}(\mathsf{D}_{\boldsymbol{\mu}})$ of the dual problem, that is,
$\nabla V(\boldsymbol{\mu})=\nabla
v_{\boldsymbol{\mu}}(0)=\mathsf{S}(\mathsf{D}_{\boldsymbol{\mu}})$.

We claim that the dual problem has a unique solution, which is exactly the
vector of equilibrium costs $\lambda(\mu)$. Indeed, fix an optimal solution
$\widehat{f}$ for $v_{\mu}(0)=V(\mu)$ and recall that this is just a Wardrop
equilibrium. The dual optimal solutions are precisely the $\lambda$’s in
$\mathbb{R}^{\mathcal{H}}$ such that

$\varphi_{\mu}(\widehat{f},0)+\varphi_{\mu}^{*}(0,\lambda)=0.$

This equation can be written explicitly as

$\sum_{r\in\mathcal{R}}C_{r}\left(\sum_{s\ni
r}\widehat{f}_{s}\right)+\sup_{f\geq
0}\sum_{h\in\mathcal{H}}\left(\lambda^{h}\left(\sum_{s\in\mathcal{S}^{h}}f_{s}-\mu^{h}\right)\right)-\sum_{r\in\mathcal{R}}C_{r}\left(\sum_{s^{\prime}\ni
r}f_{s^{\prime}}\right)=0,$

from which it follows that $f=\widehat{f}$ is an optimal solution in the
latter supremum. The corresponding optimality conditions are

$\displaystyle\lambda^{h}-\sum_{r\in s}c_{r}\left(\sum_{s^{\prime}\ni
r}\widehat{f}_{s^{\prime}}\right)=0,$ $\displaystyle\quad\text{ if
}\widehat{f}_{s}>0,h\in\mathcal{H},s\in\mathcal{S}^{h},$
$\displaystyle\lambda^{h}-\sum_{r\in s}c_{r}\left(\sum_{s^{\prime}\ni
r}\widehat{f}_{s^{\prime}}\right)\leq 0,$ $\displaystyle\quad\text{ if
}\widehat{f}_{s}=0,h\in\mathcal{H},s\in\mathcal{S}^{h},$

which imply that $\lambda^{h}$ is the equilibrium cost of the OD pair $h$ for
the Wardrop equilibrium, that is, $\lambda^{h}=\lambda^{h}(\boldsymbol{\mu})$
for every $h\in\mathcal{H}$. It follows that the subgradient $\nabla
V(\boldsymbol{\mu})=\\{\lambda(\boldsymbol{\mu})\\}$ so that
$\boldsymbol{\mu}\mapsto V(\boldsymbol{\mu})$ is not only convex but also
differentiable with gradient $\nabla
V(\boldsymbol{\mu})=\lambda(\boldsymbol{\mu})$. The conclusion follows by
noting that every convex differentiable function is automatically of class
$C^{1}$ and its gradient is monotone, in the sense that $\langle\nabla
V(\boldsymbol{\mu}_{1})-\nabla
V(\boldsymbol{\mu}_{2}),\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\rangle\geq
0$ for every
$\boldsymbol{\mu}_{1},\boldsymbol{\mu}_{2}\in\mathbb{R}_{+}^{\mathcal{H}}$,
which in particular implies that $\lambda^{h}$ is nondecreasing in the
variable $\mu^{h}$.

The continuity of the equilibrium resource costs
$\tau_{r}=\tau_{r}(\boldsymbol{\mu})$ is a consequence of Berge’s maximum
theorem (see, e.g., Aliprantis and Border,, 2006, Section 17.5). Indeed, as
explaind in Fukushima, (1984), the equilibrium resource costs are optimal
solutions for the strictly convex dual program (2.6). Hence, since the
objective function is jointly continuous in
$(\boldsymbol{\tau},\boldsymbol{\mu})$, Berge’s theorem implies that the
optimal solution correspondence is upper-semicontinous. However, in this case
the optimal solution is unique, so that the optimal correspondence is single-
valued, and, as a consequence, the equilibrium resource costs
$\tau_{r}(\boldsymbol{\mu})$ are continuous. ∎

######  Remark 11.

A similar analysis where we reformulate the primal problem by including
resource load variables $x_{r}$ and considering perturbations in the flow
balance equations $x_{r}=\sum_{s\ni r}f_{s}+z_{r}$, yields the dual problem
(2.6), which characterizes the equilibrium costs $\tau_{r}$.

Perhaps a more direct argument is as follows. Let us rewrite the flow balance
equations $\widehat{x}_{r}=\sum_{s\ni r}\widehat{f}_{s}$ in vector form as
$\widehat{\boldsymbol{x}}=\sum_{s\in\mathcal{S}}\widehat{f}_{s}\boldsymbol{\eta}^{s}$
where $\boldsymbol{\eta}^{s}=(\eta^{s}_{r})_{r\in\mathcal{R}}$ denotes the
indicator vector with

$\eta_{r}^{s}=\mathds{1}_{\\{r\in s\\}}.$ (A.6)

Since $\mu_{h}=\sum_{s\in\mathcal{S}^{h}}\widehat{f}_{s}$, by letting
$\widehat{\alpha}^{h}_{s}=\widehat{f}_{s}/\mu^{h}$ for all
$s\in\mathcal{S}^{h}$ we have that
$\sum_{s\in\mathcal{S}^{h}}\alpha^{h}_{s}=1$ and $\alpha^{h}_{s}\geq 0$, the
latter inequality being strict only for the optimal strategies for commodity
$h$. With these notations, we can write

$\widehat{\boldsymbol{x}}=\sum_{s\in\mathcal{S}}\widehat{f}_{s}\boldsymbol{\eta}^{s}=\sum_{h\in\mathcal{H}}\mu_{h}\sum_{s\in\mathcal{S}^{h}}\alpha^{h}_{s}\boldsymbol{\eta}^{s}.$
(A.7)

Now, for each $h\in\mathcal{H}$ the super-differential of the _concave_
function
$\Theta_{h}(\boldsymbol{\tau})\coloneqq\min_{s\in\mathcal{S}^{h}}\sum_{r\in
s}\tau_{r}$ is given by convex hull of the indicators of optimal strategies,
namely

$\partial\Theta_{h}(\boldsymbol{\tau})=\operatorname{co}\left\\{\boldsymbol{\eta}^{s}:s\in\mathcal{S}^{h},~{}\sum_{r\in
s}\tau_{s}=\Theta_{h}(\boldsymbol{\tau})\right\\},$ (A.8)

so that from (A.7) we derive

$\widehat{\boldsymbol{x}}=\sum_{h\in\mathcal{H}}\mu_{h}\sum_{s\in\mathcal{S}^{h}}\alpha^{h}_{s}\boldsymbol{\eta}^{s}\in\sum_{h\in\mathcal{H}}\mu_{h}\,\partial\Theta(\boldsymbol{\tau}).$
(A.9)

Finally, letting
$\Phi(\boldsymbol{x})\coloneqq\sum_{r\in\mathcal{R}}C_{r}(x_{r})$ and
$\tau_{r}=c_{r}(\widehat{x}_{r})$ we clearly have
$\boldsymbol{\tau}=\nabla\Phi(\widehat{\boldsymbol{x}})$, which is equivalent
to $\widehat{\boldsymbol{x}}\in\partial\Phi^{*}(\boldsymbol{\tau})$ where the
Fenchel’s conjugate is given by
$\Phi^{*}(\boldsymbol{\tau})=\sum_{r\in\mathcal{R}}C^{*}_{r}(\tau_{r})$. Since
all the involved functions are finite and continuous, using standard
subdifferential calculus rules, (A.9) is equivalent to
$0\in\partial\Psi(\boldsymbol{\tau})$ for the convex function
$\Psi(\boldsymbol{\tau})=\Phi^{*}(\boldsymbol{\tau})-\sum_{h\in\mathcal{H}}\mu_{h}\Theta_{h}(\boldsymbol{\tau})$
which is precisely the objective function in (2.6).

For the sake of completeness we include the following characterization of
comonotonicity. This is a folk result (see e.g., Landsberger and Meilijson,
(1994)), but its proof is not easy to find in the literature.

######  Lemma 12.

Consider a finite family of functions $\psi_{i}:\Omega\to\mathbb{R}$ for
$i=1,\ldots,m$ and let $s(\omega)\coloneqq\sum_{i=1}^{m}\psi_{i}(\omega)$.
Then, the family $\\{\psi_{i}:i=1,\ldots,m\\}$ is comonotonic if and only if
there exist nondecreasing functions $F_{i}:\mathbb{R}\to\mathbb{R}$ such that
$\psi_{i}(\omega)=F_{i}(s(\omega))$ for all $\omega\in\Omega$ and
$i=1,\ldots,m$.

###### Proof.

Since the _“if”_ implication holds trivially, it suffices to prove the _“only
if”_. Suppose that the $\psi_{i}$’s are comonotonic. For $z\in\mathbb{R}$
define $F_{i}(z)=\sup_{\omega\in\Omega}\\{\psi_{i}(\omega):s(\omega)\leq z\\}$
if there is some $\omega\in\Omega$ with $s(\omega)\leq z$, and
$F_{i}(z)=\inf_{\omega\in\Omega}\psi_{i}(\omega)$ otherwise. Clearly the
functions $F_{i}$ are nondecreasing and $\psi_{i}(\omega)\leq
F_{i}(s(\omega))$, whereas comonotonicity implies that the latter holds with
equality for all $i=1,\ldots,m$ and $\omega\in\Omega$.

It remains to show that the $F_{i}$’s are everywhere finite. Indeed, if
$F_{i}(z)=\infty$ for some $z\in\mathbb{R}$ we can find a sequence
$\omega_{n}\in\Omega$ with $s(\omega_{n})\leq z$ such that
$\psi_{i}(\omega_{n})$ increases to $\infty$. However, by comonotonicity, the
latter implies $s(\omega_{n})\to\infty$ which is a contradiction. Now, if
$F_{i}(z)=-\infty$ we must be in the case
$F_{i}(z)=\inf_{\omega\in\Omega}\psi_{i}(\omega)=-\infty$ and comonotonicity
implies $\inf_{\omega\in\Omega}s(\omega)=-\infty$, so we may find
$\omega\in\Omega$ with $s(\omega)\leq z$ which yields the contradiction
$F_{i}(z)\geq\psi_{i}(\omega)>-\infty$. ∎

##  Appendix B List of symbols

$c_{r}$ |  cost function of resource $r$
---|---
$c_{s}$ |  cost function of strategy $s$, defined in (2.3)
$\boldsymbol{c}$ |  vector of cost functions; it can be indexed both by elements in $\mathcal{E}$ or $\mathcal{P}$
$c^{\varepsilon}_{r}(x_{r})$ |  $c_{r}(x_{r})+2\varepsilon x_{r}$, perturbed cost
$C_{r}(x_{r})$ |  $\int_{0}^{x_{r}}c_{r}(z)\ \textup{d}z$
$C_{r}^{*}(\,\cdot\,)$ |  Fenchel conjugate of $C_{r}(\,\cdot\,)$
$\mathcal{C}$ |  subset of commodities having the same equilibrium cost
$\mathsf{D}^{h}$ |  destination for OD pair $h$
$(\mathsf{D}_{\boldsymbol{\mu}})$ |  dual problem, defined in (A.4)
$\mathcal{E}$ |  set of edges
$\boldsymbol{e}^{h}$ |  $h$-th vector of the canonical basis of $\mathbb{R}^{\mathcal{H}}$
$f_{s}^{h}$ |  flow on strategy $s$ in commodity $h$
$\boldsymbol{f}^{h}$ |  $\left(f_{s}^{h}\right)_{s\in\mathcal{S}^{h}}$, flow vector of commodity $h$
$\mathcal{F}_{\boldsymbol{\mu}}$ |  set of feasible flows for the demand vector $\boldsymbol{\mu}$
${G}$ |  directed multigraph
$\mathcal{G}$ |  $\left(\mathcal{R},\boldsymbol{c},\boldsymbol{\mathcal{S}}\right)$, congestion game structure
$\mathcal{G}^{\varepsilon}$ |  $(\mathcal{R},\boldsymbol{c}^{\varepsilon},\boldsymbol{\mathcal{S}})$, perturbed congestion game structure
$\mathcal{G}_{\mathcal{C}}$ |  $(\mathcal{R}_{\mathcal{C}},\boldsymbol{c},\mathcal{S}_{\mathcal{C}})$, defined in Definition 4
$\mathcal{G}_{1}\otimes\mathcal{G}_{2}$ |  product game
$\mathcal{G}_{1}\cup\mathcal{G}_{2}$ |  union game
$h$ |  commodity
$\mathcal{H}$ |  set of commodities
$k$ |  number of elements in $\mathcal{H}$
$n^{h}$ |  the number of elements in $\mathcal{P}^{h}$
$\mathsf{O}^{h}$ |  origin for OD pair $h$
$(\mathsf{P}_{\boldsymbol{\mu}})$ |  primal problem, defined in (A.3)
$\widehat{\mathcal{P}}(\mu)$ |  set of paths that attain equilibrium cost at equilibrium with demand $\mu$
$\mathcal{P}^{h}$ |  the set of paths of commodity $h$
$\boldsymbol{\mathcal{P}}$ |  $(\mathcal{P}^{h})_{h\in\mathcal{H}}$
$r$ |  resource
$\mathcal{R}$ |  set of resources
$\widehat{\mathcal{R}}^{h}(\boldsymbol{\mu})$ |  set of active resources for commodity $h\in\mathcal{H}$
$\widehat{\boldsymbol{\mathcal{R}}}(\boldsymbol{\mu})$ |  $(\widehat{\mathcal{R}}^{h}(\boldsymbol{\mu}))_{h\in\mathcal{H}}$, active regime
$\mathcal{R}_{0}$ |  set of resources such that $c_{r}(x_{r}(\boldsymbol{\mu}_{0}))=\lambda^{h}(\boldsymbol{\mu}_{0})$
$\mathcal{R}_{0}^{+}$ |  $\\{r\in\mathcal{R}_{0}\colon x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})>x_{r}(\boldsymbol{\mu}_{0})\\}$, defined in (3.1)
$\mathcal{R}_{0}^{-}$ |  $\\{r\in\mathcal{R}_{0}\colon x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})<x_{r}(\boldsymbol{\mu}_{0})\\}$, defined in (3.2)
$\mathcal{R}_{0}^{=}$ |  $\\{r\in\mathcal{R}_{0}\colon x_{r}(\boldsymbol{\mu}_{0}+t\boldsymbol{e}^{h})=x_{r}(\boldsymbol{\mu}_{0})\\}$, defined in (3.3)
$\mathcal{R}_{\mathcal{C}}$ |  $\left(\cup_{h\in\mathcal{C}}\mathcal{R}^{h}\right)\setminus\left(\cup_{h^{\prime}\succ\mathcal{C}}\mathcal{R}^{h^{\prime}}\right)$, defined in (4.2)
$\mathcal{S}^{h}$ |  set of feasible strategies for commodity $h$
$\boldsymbol{\mathcal{S}}$ |  $\times_{h\in\mathcal{H}}{\mathcal{S}^{h}}$, set of strategy profiles
$\mathsf{S}(\mathsf{D}_{\boldsymbol{\mu}})$ |  optimal solution set of the dual problem
${\operatorname{\mathsf{SC}}}(\boldsymbol{\mu})$ |  $\sum_{h\in\mathcal{H}}\mu^{h}\lambda^{h}(\boldsymbol{\mu})$, social cost
$v_{\boldsymbol{\mu}}(\boldsymbol{z})$ |  $\inf_{\boldsymbol{f}}\varphi_{\boldsymbol{\mu}}(\boldsymbol{f},\boldsymbol{z})$, defined in (A.3)
$V(\boldsymbol{\mu})$ |  $\min_{\boldsymbol{x}\in\mathcal{X}_{\boldsymbol{\mu}}}\sum_{r\in\mathcal{R}}C_{r}(x_{r})$, defined in (A.1)
$\mathcal{V}$ |  set of vertices
$x_{r}$ |  load of resource $r$, defined in (2.2)
$\boldsymbol{x}$ |  $(x_{r})_{r\in\mathcal{R}}$, load vector
$\mathcal{X}_{\boldsymbol{\mu}}$ |  set of load profiles induced by all feasible flows $\boldsymbol{f}\in\mathcal{F}_{\boldsymbol{\mu}}$
$\Gamma^{\precsim}$ |  $\left\\{\boldsymbol{\mu}\in\mathbb{R}_{+}^{\mathcal{H}}\colon\lambda^{h}(\boldsymbol{\mu})\leq\lambda^{h^{\prime}}(\boldsymbol{\mu})\iff h\precsim h^{\prime}\text{ for all }h,h^{\prime}\in\mathcal{H}\right\\}$, defined in (4.1)
$\Gamma^{\precsim}_{\boldsymbol{\varrho}}$ |  $\left\\{\boldsymbol{\mu}\in\Gamma^{\precsim}:\widehat{\boldsymbol{\mathcal{R}}}(\boldsymbol{\mu})=\boldsymbol{\varrho}\right\\}$, defined in (4.3)
$\eta_{r}^{s}$ |  $\mathds{1}_{\\{r\in s\\}}$, defined in (A.6)
$\boldsymbol{\eta}^{s}$ |  $(\eta^{s}_{r})_{r\in\mathcal{R}}$
$\lambda^{h}$ |  equilibrium cost of commodity $h$, defined in (2.4)
$\boldsymbol{\lambda}$ |  $\left(\lambda^{h}\right)_{h\in\mathcal{H}}$, equilibrium cost vector
$\mu^{h}$ |  demand for commodity $h$
$\boldsymbol{\mu}$ |  $\left(\mu^{h}\right)_{h\in\mathcal{H}}$ demand vector
$\mu_{\mathcal{C}}$ |  aggregate demand on $\mathcal{C}$
$\boldsymbol{\varrho}$ |  $\left(\varrho^{h}\right)_{h\in\mathcal{H}}$, regime
$\varrho^{h}$ |  subset of $\mathcal{P}^{h}$
$\tau_{r}$ |  equilibrium cost of resource $r$
$\varphi_{\boldsymbol{\mu}}$ |  defined in (A.2)
$\varphi_{\boldsymbol{\mu}}^{*}$ |  Fenchel conjugate of $\varphi_{\boldsymbol{\mu}}$, defined in (A.5)

## References

  * Acemoglu and Ozdaglar, (2007) Acemoglu, D. and Ozdaglar, A. (2007).  Competition and efficiency in congested markets.  Math. Oper. Res., 32(1):1–31.
  * Aliprantis and Border, (2006) Aliprantis, C. D. and Border, K. C. (2006).  Infinite Dimensional Analysis.  Springer, Berlin, third edition.
  * Attouch, (1996) Attouch, H. (1996).  Viscosity solutions of minimization problems.  SIAM J. Optim., 6(3):769–806.
  * Auslender et al., (1997) Auslender, A., Cominetti, R., and Haddou, M. (1997).  Asymptotic analysis for penalty and barrier methods in convex and linear programming.  Math. Oper. Res., 22(1):43–62.
  * Beckmann et al., (1956) Beckmann, M. J., McGuire, C. B., and Winsten, C. B. (1956).  Studies in the Economics of Transportation.  Yale University Press, New Haven, CT.
  * Bilò and Vinci, (2017) Bilò, V. and Vinci, C. (2017).  On the impact of singleton strategies in congestion games.  In 25th European Symposium on Algorithms, volume 87 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 17, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern.
  * Borchers et al., (2015) Borchers, M., Breeuwsma, P., Kern, W., Slootbeek, J., Still, G., and Tibben, W. (2015).  Traffic user equilibrium and proportionality.  Transportation Res. Part B, 79:149–160.
  * Braess, (1968) Braess, D. (1968).  Über ein Paradoxon aus der Verkehrsplanung.  Unternehmensforschung, 12:258–268.
  * Braess et al., (2005) Braess, D., Nagurney, A., and Wakolbinger, T. (2005).  On a paradox of traffic planning.  Transportation Sci., 39(4):446–450.
  * Castiglioni et al., (2019) Castiglioni, M., Marchesi, A., Gatti, N., and Coniglio, S. (2019).  Leadership in singleton congestion games: what is hard and what is easy.  Artificial Intelligence, 277:103177, 31.
  * Cominetti, (1999) Cominetti, R. (1999).  Nonlinear averages and convergence of penalty trajectories in convex programming.  In Théra, M. and Tichatschke, R., editors, Ill-posed Variational Problems and Regularization Techniques, pages 65–78, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Cominetti et al., (2021) Cominetti, R., Dose, V., and Scarsini, M. (2021).  The price of anarchy in routing games as a function of the demand.  Math. Program., forthcoming.
  * Cominetti et al., (2023) Cominetti, R., Dose, V., and Scarsini, M. (2023).  Phase transitions of the price-of-anarchy function in multi-commodity routing games.  Technical report, arXiv:2305.03459.
  * Dafermos and Nagurney, (1984) Dafermos, S. and Nagurney, A. (1984).  On some traffic equilibrium theory paradoxes.  Transportation Res. Part B, 18(2):101–110.
  * Dellacherie, (1971) Dellacherie, C. (1971).  Quelques commentaires sur les prolongements de capacités.  In Séminaire de Probabilités, V (Univ. Strasbourg, année universitaire 1969–1970), Lecture Notes in Math., Vol. 191, pages 77–81. Springer, Berlin.
  * Deori et al., (2017) Deori, L., Margellos, K., and Prandini, M. (2017).  On the connection between Nash equilibria and social optima in electric vehicle charging control games.  IFAC-PapersOnLine, 50(1):14320–14325.
  * Eppstein, (1992) Eppstein, D. (1992).  Parallel recognition of series-parallel graphs.  Inform. and Comput., 98(1):41–55.
  * Fisk, (1979) Fisk, C. (1979).  More paradoxes in the equilibrium assignment problem.  Transportation Res. Part B, 13(4):305–309.
  * Fisk and Pallottino, (1981) Fisk, C. and Pallottino, S. (1981).  Empirical evidence for equilibrium paradoxes with implications for optimal planning strategies.  Transportation Res. Part A, 15(3):245–248.
  * Fotakis et al., (2009) Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., and Spirakis, P. (2009).  The structure and complexity of Nash equilibria for a selfish routing game.  Theoret. Comput. Sci., 410(36):3305–3326.
  * Fukushima, (1984) Fukushima, M. (1984).  On the dual approach to the traffic assignment problem.  Transportation Res. Part B, 18(3):235–245.
  * Gairing and Schoppmann, (2007) Gairing, M. and Schoppmann, F. (2007).  Total latency in singleton congestion games.  In Deng, X. and Graham, F. C., editors, Internet and Network Economics, pages 381–387, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Gonczarowski and Tennenholtz, (2016) Gonczarowski, Y. A. and Tennenholtz, M. (2016).  A hydraulic approach to equilibria of resource selection games.  In Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, page 477, New York, NY, USA. Association for Computing Machinery.
  * Hall, (1978) Hall, M. A. (1978).  Properties of the equilibrium state in transportation networks.  Transportation Sci., 12(3):208–216.
  * Harks and Klimm, (2012) Harks, T. and Klimm, M. (2012).  On the existence of pure Nash equilibria in weighted congestion games.  Math. Oper. Res., 37(3):419–436.
  * Harks et al., (2019) Harks, T., Schröder, M., and Vermeulen, D. (2019).  Toll caps in privatized road networks.  European J. Oper. Res., 276(3):947–956.
  * Harks and Timmermans, (2017) Harks, T. and Timmermans, V. (2017).  Equilibrium computation in atomic splittable singleton congestion games.  In Integer Programming and Combinatorial Optimization, volume 10328 of Lecture Notes in Comput. Sci., pages 442–454. Springer, Cham.
  * He and Yesha, (1987) He, X. and Yesha, Y. (1987).  Parallel recognition and decomposition of two terminal series parallel graphs.  Inform. and Comput., 75(1):15–38.
  * Hoerl, (1959) Hoerl, A. E. (1959).  Optimum solution of many variables equations.  Chemical Engineering Progress, 55:69–78.
  * Hoerl, (1962) Hoerl, A. E. (1962).  Application of ridge analysis to regression problems.  Chemical Engineering Progress, 58:54–59.
  * Hoerl and Kennard, (1970) Hoerl, A. E. and Kennard, R. W. (1970).  Ridge regression: Biased estimation for nonorthogonal problems.  Technometrics, 12(1):55–67.
  * Josefsson and Patriksson, (2007) Josefsson, M. and Patriksson, M. (2007).  Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design.  Transportation Res. Part B, 41(1):4 – 31.
  * Klimm and Warode, (2022) Klimm, M. and Warode, P. (2022).  Parametric computation of minimum-cost flows with piecewise quadratic costs.  Math. Oper. Res., 47(1):812–846.
  * Konishi, (2004) Konishi, H. (2004).  Uniqueness of user equilibrium in transportation networks with heterogeneous commuters.  Transportation Sci., 38(3):315–330.
  * Landsberger and Meilijson, (1994) Landsberger, M. and Meilijson, I. (1994).  Co-monotone allocations, Bickel-Lehmann dispersion and the Arrow-Pratt measure of risk aversion.  Ann. Oper. Res., 52:97–106.
  * Ma et al., (2013) Ma, Z., Callaway, D. S., and Hiskens, I. A. (2013).  Decentralized charging control of large populations of plug-in electric vehicles.  IEEE Trans. Control Syst. Technol., 21(1):67–78.
  * Mehr and Horowitz, (2020) Mehr, N. and Horowitz, R. (2020).  How will the presence of autonomous vehicles affect the equilibrium state of traffic networks?  IEEE Trans. Control Netw. Syst., 7(1):96–105.
  * Meunier and Pradeau, (2014) Meunier, F. and Pradeau, T. (2014).  The uniqueness property for networks with several origin-destination pairs.  European J. Oper. Res., 237(1):245–256.
  * Milchtaich, (2000) Milchtaich, I. (2000).  Generic uniqueness of equilibrium in large crowding games.  Math. Oper. Res., 25(3):349–364.
  * Milchtaich, (2005) Milchtaich, I. (2005).  Topological conditions for uniqueness of equilibrium in networks.  Math. Oper. Res., 30(1):225–244.
  * Milchtaich, (2013) Milchtaich, I. (2013).  Representation of finite games as network congestion games.  Internat. J. Game Theory, 42(4):1085–1096.
  * Nimalsiri et al., (2020) Nimalsiri, N. I., Mediwaththe, C. P., Ratnam, E. L., Shaw, M., Smith, D. B., and Halgamuge, S. K. (2020).  A survey of algorithms for distributed charging control of electric vehicles in smart grid.  IEEE Trans. Intell. Transportation Syst., 21(11):4497–4515.
  * Patriksson, (2004) Patriksson, M. (2004).  Sensitivity analysis of traffic equilibria.  Transportation Sci., 38(3):258–281.
  * Pradeau, (2014) Pradeau, T. (2014).  Congestion Games with Player-Specific Cost Functions.  Phd thesis, Université Paris-Est.
  * Rossi et al., (1989) Rossi, T., McNeil, S., and Hendrickson, C. (1989).  Entropy model for consistent impact-fee assessment.  J. Urban Plann. Develop., 115:51–63.
  * Tikhonov, (1943) Tikhonov, A. N. (1943).  On the stability of inverse problems.  C. R. (Doklady) Acad. Sci. URSS (N.S.), 39:176–179.
  * Tikhonov, (1963) Tikhonov, A. N. (1963).  On the solution of ill-posed problems and the method of regularization.  Dokl. Akad. Nauk SSSR, 151:501–504.
  * Tikhonov and Arsenin, (1977) Tikhonov, A. N. and Arsenin, V. Y. (1977).  Solutions of Ill-Posed Problems.  Scripta Series in Mathematics. V. H. Winston & Sons, Washington, D.C.; John Wiley & Sons, New York-Toronto, Ont.-London.
  * Valdes et al., (1982) Valdes, J., Tarjan, R. E., and Lawler, E. L. (1982).  The recognition of series parallel digraphs.  SIAM J. Comput., 11(2):298–313.
  * van de Klundert et al., (2023) van de Klundert, J., Cominetti, R., Liu, Y., and Kong, Q. (2023).  The interdependence between hospital choice and waiting time – with a case study in urban China.  Technical report, arXiv:2306.16256v1.
  * Wan, (2016) Wan, C. (2016).  Strategic decentralization in binary choice composite congestion games.  European J. Oper. Res., 250(2):531–542.

  *[OD]: origin-destination
  *[ODs]: origin-destination
  *[SP]: series-parallel
  *[MES]: monotonic equilibrium selection
  *[CRG]: constrained routing game
  *[ OD]: origin-destination
  *[BPR]: Bureau of Public Roads