<figure><img src="image_1.png" /></figure>

HAL
open science

# On the impact of coordinated fleets size on traffic efficiency

Tommaso Toso, Francesca Parise, Paolo Frasca, Alain Kibangou

<figure><img src="image_2.png" /></figure>

## To cite this version:

Tommaso Toso, Francesca Parise, Paolo Frasca, Alain Kibangou. On the impact of coordinated fleets size on traffic efficiency. CDC 2024 - 63rd IEEE Conference on Decision and Control, IEEE, Dec 2024, Milan, Italy. pp.1-6. [hal-04878839](https://hal.science/hal-04878839v1)

HAL Id: hal-04878839

https://hal.science/hal-04878839v1

Submitted on 10 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the impact of coordinated fleets size on traffic efficiency

Tommaso Toso, Student Member, IEEE, Francesca Parise, Member, IEEE, Paolo Frasca, Senior Member, IEEE, Alain Y. Kibangou, Member, IEEE

**Abstract**— We investigate a traffic assignment problem on a transportation network, considering both the demands of individual drivers and of a large fleet controlled by a central operator (minimizing the fleet's average travel time). We formulate this problem as a two-player convex game and we study how the size of the coordinated fleet, measured in terms of share of the total demand, influences the Price of Anarchy (PoA). We show that, for two-terminal networks, there are cases in which the fleet must reach a minimum share before actually affecting the PoA, which otherwise remains unchanged. Moreover, for parallel networks we prove that, under suitable assumptions, the PoA is monotonically non-increasing in the fleet share.

**Index Terms**— Transportation networks, Game theory, Traffic control.

## I. INTRODUCTION

Traffic assignment problems typically assume that traffic demand consists of drivers exhibiting selfish behavior to minimize travel time. However, technological advancements have introduced new services (ride-hailing services, navigation apps) that, due to their widespread adoption, can influence the behavior of a substantial portion of drivers, potentially leading to a paradigm shift. Specifically, the providers of such services may leverage their position to minimize overall fleet metrics, such as total travel time, rather than optimizing individual user experiences. This approach, while potentially disadvantaging some users, aims to attract and retain users by providing lower travel times on average. In the following, we refer to groups of vehicles controlled by a central operator aiming to minimize the fleet's average travel time as *coordinated fleets*. This work aims to study the impact that the presence of a coordinated fleet has on traffic efficiency in terms of the price of anarchy (PoA).

**Contribution:** We formulate the problem as a two-player game, with one player associated with the individual users and the other with the coordinated fleet. We study this game by using a well-known reformulation in terms of solution to a Variational Inequality (VI) (see [1], [2]). Specifically, we establish conditions ensuring that the operator of the VI associated to our game is strongly monotone. On the one hand, strong monotonicity ensures equilibrium uniqueness. On the

other hand, this property allows for providing meaningful insights about the relationship between traffic efficiency and the share of the coordinated fleet in two-terminal networks. Using the Price of Anarchy (PoA) as a measure of traffic efficiency [3], we prove that the unique equilibrium and the PoA are Lipschitz continuous functions of the fleet share. Additionally, we derive sufficient conditions for the existence of a minimum share below which the presence of a coordinated fleet has no effect on traffic efficiency. Finally, for parallel networks, we show that under suitable assumptions, the PoA is monotonically non-increasing in the fleet share.

**Related work:** The multi-class traffic assignment problem was initially defined in [4]. Coordination among users of the same class was introduced in [5], where sufficient conditions for equilibrium existence and uniqueness are established, and then extended to more general settings in [6]. The impact on efficiency of coordinated classes was first considered in [7] for a three-class problem with *individual users*, aiming at reducing individual travel time, a *coordinated fleet*, aiming at reducing overall fleet travel time; and a *system-optimal fleet*, aiming at reducing the system's average travel time. Numerical simulations in [7] show that sufficiently large coordinated and system-optimal fleets can lead to system optimality even in the presence of individual users.

Two-class problems are considered in [8]–[12]. Specifically, [8]–[10] consider a two-class problem, with individual users and a system-optimal fleet: [8] and [9] derived methods to compute the minimum share of system-optimal users necessary to induce system optimality, while [10] studied the trade-off between the magnitude of the improvement and the cost of deployment for the network manager.

More closely related to our contribution, [11] and [12] both consider a two-class problem with individual users and one coordinated fleet. In [11], the authors derive sufficient conditions for equilibrium existence and uniqueness weaker than those used in our paper. These conditions do not guarantee strong monotonicity, which is essential for our analysis. Their work also introduces two algorithms for computing the equilibrium and a control scheme for achieving equilibrium in a dynamic framework.

In [12], the authors also examine the impact of coordinated fleets on traffic efficiency, demonstrating that these fleets can reduce efficiency in networks with multiple origin-destination pairs. They analyze the minimum fleet size required for system optimality and the maximum size where user equilibrium still holds, providing mathematical programs to compute these values. Additionally, they offer

This work has been partly supported by the French National Research Agency in the framework of the "Investissements d'avenir" program ANR-15-IDEX-02 and the LabEx PERSYVAL ANR-11-LABX-0025-01. T. Toso thanks the support of an outgoing mobility grant from Univ. Grenoble Alpes.

Tommaso Toso, Paolo Frasca and Alain Kibangou are with Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, GIPSA-lab, 38000 Grenoble, France (e-mail:firstname.lastname@gipsa-lab.grenoble-inp.fr). Alain Kibangou is also with Univ. of Johannesburg (Auckland Park Campus), Johannesburg 2006, South Africa. Francesca Parise is with the School of Electrical and Computer Engineering, Cornell University, Ithaca, NY, USA (e-mail: fp264@cornell.edu).
analytical results on the threshold effect of fleet size on efficiency, but only for parallel networks. In contrast, our work provides conditions under which a minimum fleet size impacts the PoA for general networks with a single origin-destination pair and derives results on the monotonicity of the PoA in parallel networks.

**Paper organization:** The model and the main concepts are defined in Section II. Strong monotonicity, existence and uniqueness conditions are given in Section III. Section IV discusses the effect of a coordinated fleet on traffic efficiency as a function of the fleet size. Section V contains numerical studies and provides interesting insights about extending this work to more general settings. Section VI contains concluding remarks and future perspectives. Due to space limitations, proofs of some auxiliary results are omitted and can be found in [13].

## II. A TWO-CLASS ROUTING GAME

The transportation network is modeled as a directed graph $\mathcal{G} = (\mathcal{N}, \mathcal{L})$, with node set $\mathcal{N}$ and link set $\mathcal{L}$, with links representing roads of the network and nodes representing junctions between them. Let $\mathcal{O} \subseteq \mathcal{N}$, called origins, be the subset of nodes from which exogenous traffic demands can access the network. Analogously, let $\mathcal{D} \subseteq \mathcal{N}$, called destinations, be the subset of nodes through which traffic can exit the network. Define the set of origin-destination pairs (OD pairs) $\mathcal{K} = \{(o,d) | o \in \mathcal{O}, d \in \mathcal{D}\}$. Let $\mathcal{P}_k$ denote the set of paths associated with OD pair $k$ and let $\mathcal{P} := \cup_{k \in \mathcal{K}} \mathcal{P}_k$. Let $N, L, K, P_k$ and $P$ be the cardinalities of $\mathcal{N}, \mathcal{L}, \mathcal{K}, \mathcal{P}_k$ and $\mathcal{P}$, respectively. Let $A$ be the link-path incidence matrix defined as

$$A_{lp} = \begin{cases} 1, & l \in p \\ 0, & l \notin p. \end{cases} \quad (1)$$

Suppose now that $\mathcal{G}$ supports two classes of demand, namely class $S$ and class $C$. Class $S$ consists of selfish individual users, whereas class $C$ consists of a coordinated fleet. Let $D^i$ be the total demand of class $i$, $i = S, C$. Each OD pair $k$ is associated with a fraction $D_k^i > 0$, $i = S, C$, of the total demand, i.e, $\sum_{k \in \mathcal{K}} D_k^i = D^i$. Let $D := D^S + D^C$ be the total demand. For each class $i \in \{S, C\}$, we define the flow vector of class $i$ $z^i \in \mathbb{R}_{\ge 0}^P$ representing the traffic assignment of traffic demand $D^i$ over the network paths. The set of feasible flows of class $i$ is

$$\mathcal{Z}^i := \left\{ z^i \in \mathbb{R}_{\ge 0}^P : \sum_{p \in \mathcal{P}_k} z^p = D_k^i, \forall k \in \mathcal{K} \right\}$$

and let $\mathcal{L} = \mathcal{L}^S \times \mathcal{L}^C$. Each flow vector $z^i$ is associated with the load vector of class $i$ ($f^i := Az^i$, $i = S, C$) representing the load of each link of the network for class $i$. Then, the set of feasible loads of class $i$ is

$$\mathcal{F}^i := \{f^i \in \mathbb{R}_{\ge 0}^L : f^i = Az^i, \text{ for some } z^i \in \mathcal{Z}^i\}$$

and let $\mathcal{F} = \mathcal{F}^S \times \mathcal{F}^C$. Let the flow vector $z := (z^S, z^C)$ and the load vector $f := (f^S, f^C)$ be the concatenations of the flow and load vectors of the two classes and let $Z := z^S +$

$z^C$, $F := f^S + f^C$ be the aggregate flow and load vectors, respectively. The assignment of the two classes of vehicles is determined by the link delay functions.

**Definition 1 (Delay functions):** For every $l \in \mathcal{L}$, the delay $d_l: \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ of link $l$ is a non-negative, strictly increasing and $C^2([0, +\infty))$ function with $d'_l(0) > 0$, depending on the aggregate load $F_l$ on link $l$ only. Moreover, for every $p \in \mathcal{P}$, the function $d_p: \mathbb{R}_{\ge 0}^L \to \mathbb{R}_{\ge 0}$ is the delay of path $p$ and equals the sum of the delays of the links included in $p$:

$$d_p(F) = \sum_{l \in \mathcal{L}} A_{lp} d_l(F_l). \quad (2)$$

The fact that link delays depend only on the aggregate load means that the two classes of vehicles affect the link delays in the same way.

We are interested in characterizing the equilibrium loads of the traffic assignment problem emerging from the interaction of the vehicle classes $S$ and $C$. To do this, we reformulate the problem as a two-player game, by associating each class to a strategic player. The strategy of each player corresponds to the load vector $f^i$ with strategy set $\mathcal{F}^i$, $i = S, C$, respectively. The cost functions that player $S$ and player $C$ have to minimize in order to attain the goals of the traffic assignment problem are the following:

$$U^S(f) := \sum_{l \in \mathcal{L}} \int_0^{f_l^S} d_l(r + f_l^C) dr, \quad (3)$$

$$U^C(f) := \sum_{l \in \mathcal{L}} f_l^C \cdot d_l(F_l). \quad (4)$$

In deriving the cost function for player $S$ we used a well-known reformulation of the Wardrop equilibrium of strategic agents in class $S$ as an optimization problem (with potential function as in (3)), [3, Chapter 18]. The cost of the player $C$ instead is the total travel time of vehicles in class $C$.

**Definition 2 (Equilibria):** An equilibrium load is a load vector $f^* = (f^{S*}, f^{C*})$ such that

$$f^{S*} := \arg\min_{f^{S} \in \mathcal{F}^{S}} U^{S}(f^{S}, f^{C*}), \quad f^{C*} := \arg\min_{f^{C} \in \mathcal{F}^{C}} U^{C}(f^{S*}, f^{C}). \quad (5)$$

All the feasible flows $z^* = (z^{S*}, z^{C*})$ such that $f^{i*} = Az^{i*}$, $i = S, C$ are called equilibrium flows.

Note that

$$f_l^C \cdot d_l(F_l) = \int_0^{f_l^C} (d_l(f_l^S + r) + r \cdot d_l(f_l^S + r)) dr.$$

Hence (4) can be rewritten as

$$U^C(f) = \sum_{l \in \mathcal{L}} \int_0^{f_l^C} (d_l(f_l^S + r) + r \cdot d_l(f_l^S + r)) dr. \quad (6)$$

The functions inside the integral in (6), that is,

$$m_l(f_l) := d_l(F_l) + f_l^C \cdot d'_l(F_l) \quad (7)$$

are known as marginal delay functions [3, Chapter 18].

We prove that under appropriate assumptions on the marginal delays $m_l(f_l)$, the game in (5) is convex.
**Lemma 1:** $U^S(f)$ is convex in $f^S$ for any $f^C$. Moreover, if

$$ \frac{\partial m_l(f_l)}{\partial f_l^C} > 0, \quad \forall f_l^S, f_l^C \ge 0, \forall l \in \mathcal{L}, \quad (8) $$

then $U^C(f)$ is convex in $f^C$ for any $f^S$.

**Remark 1:** The convexity of the cost functions (3) and (4) implies that any equilibrium flow $z^*$ must satisfy the following Wardrop conditions:

$$ z_p^{S*} > 0 \Rightarrow \sum_{l \in \mathcal{L}} A_{lp} d_l(F_l^*) \le \sum_{l \in \mathcal{L}} A_{lr} d_l(F_l^*), \forall r \in \mathcal{P}, \quad (9) $$

$$ z_p^{C*} > 0 \Rightarrow \sum_{l \in \mathcal{L}} A_{lp} m_l(f_l^*) \le \sum_{l \in \mathcal{L}} A_{lr} m_l(f_l^*), \forall r \in \mathcal{P}. \quad (10) $$

In words, at equilibrium, each vehicle in class S uses a path among those of shortest delay, whereas each vehicle in class C uses a path among those of shortest marginal delay. Conditions (9) and (10) will be of key importance when proving the results in Section IV.

### III. VARIATIONAL INEQUALITY FORMULATION AND STRONG MONOTONICITY

Under condition (8), the two-class routing game is convex and is equivalent to the following variational inequality (VI) [1, Proposition 1.4.2]:

$$ (\phi - f^*)^\top H(f^*) \ge 0, \quad \forall \phi \in \mathcal{F}, \quad (11) $$

where

$$ H(f) = ((d_l(F_l))_{l \in \mathcal{L}}, (m_l(f_l))_{l \in \mathcal{L}}), \quad (12) $$

that is, equilibria of the two-class routing game correspond to solutions of (11).

The main result of this section consists in providing sufficient conditions for the operator $H$ to be strongly monotone on $\Omega := [0, D]^{2L} \supset \mathcal{F}$, that is, for guaranteeing that

$$ \exists c > 0 : (H(x) - H(y))^\top (x - y) \ge c ||x - y||^2, \forall x, y \in \Omega. \quad (13) $$

The strong monotonicity of $H$ not only ensures the uniqueness of the solution of (11) [1, Theorem 2.3.3], but also allows us to assess the impact of the fleet size onto traffic efficiency, as we shall demonstrate in the next section.

**Proposition 1:** The operator $H$ in (12) is strongly monotone on $\Omega$ if (8) holds and

$$ d_l^\prime(F_l) > \frac{1}{4} \frac{\partial m_l(f_l)}{\partial f_l^C}, \quad \forall f_l^S, f_l^C \ge 0, \forall l \in \mathcal{L}. \quad (14) $$

The strong monotonicity of $H$ ensures the uniqueness of the solution of (11), that is, of the equilibrium load $f^*$. In [11], weaker conditions similar to (14) were derived to ensure the uniqueness of the equilibrium load. Our slightly stronger conditions are needed to guarantee that $H$ is strongly monotone and that thus the following assumption holds.

**Assumption 1:** Suppose that the operator $H$ in (12) is Lipschitz and strongly monotone in $\Omega = [0, D]^{2L}$. Again, sufficient conditions for strong monotonicity to hold are given in Proposition 1, whereas Lipschitz continuity follows from the smoothness of delay and marginal delay functions (defined on a compact set).

**Remark 2:** A class of delay functions that satisfy conditions (8) and (14), ensuring strong monotonicity of (12), includes polynomial functions of degree up to 3 with non-negative coefficients and strictly positive derivatives on $[0, +\infty)$ (see [11] for similar examples). This indicates that assuming strong monotonicity is not overly restrictive, as it applies to a significant class of delay functions.

### IV. PRICE OF ANARCHY

The total delay experienced by all the vehicles traveling across the network is defined as

$$ T(f) := \sum_{l \in \mathcal{L}} F_l \cdot d_l(F_l). \quad (15) $$

A feasible load minimizing $T(f)$ is called an optimal load (denoted by $F^\omega \in \mathcal{F}$). Then, the Price of Anarchy is defined as the ratio between the total delay attained at the (unique under Assumption 1) equilibrium $f^*$ and the minimum total delay:

$$ \text{PoA} := \frac{\sum_{l \in \mathcal{L}} F_l^* \cdot d_l(F_l^*)}{\sum_{l \in \mathcal{L}} F_l^\omega \cdot d_l(F_l^\omega)} \ge 1. \quad (16) $$

We aim to study how the size of the coordinated fleet affects the PoA. From now on, we focus our attention on two-terminal networks.

**Assumption 2:** The network has a single OD pair. Let $D^S = (1 - \alpha)D$ and $D^C = \alpha D$ represent the demand of class S and C entering the network from its unique origin, where $\alpha$ is the share of class C, which we refer to as the fleet share.

We present three main results in this section. First, we show that the equilibrium load and the PoA are Lipschitz continuous functions of the fleet share $\alpha$. Second, we establish a sufficient condition for a minimum fleet share below which the coordinated fleet has no effect on the PoA. Finally, we prove that under suitable assumptions the PoA is a non-increasing function of $\alpha$ for parallel networks. To clarify their dependence on $\alpha$, we denote the feasible set by $\mathcal{F}(\alpha)$, the equilibrium load by $f^*(\alpha)$, and the PoA, delay, and marginal delay functions at equilibrium by PoA($\alpha$), $d_l(\alpha)$, and $m_l(\alpha)$, respectively.

#### A. Lipschitz continuity

**Proposition 2:** Let Assumptions 1 and 2 hold. The equilibrium load $f^*(\alpha)$ is Lipschitz continuous in $\alpha$, i.e., there exists $k > 0$ such that

$$ \forall \alpha_1, \alpha_2, \quad \|f^*(\alpha_2) - f^*(\alpha_1)\| \le k|\alpha_2 - \alpha_1|. \quad (17) $$

Since the PoA is Lipschitz continuous in the equilibrium load and loads are defined on a bounded set, the PoA is also a Lipschitz continuous function of $\alpha$.

#### B. Critical fleet share

A first question that one may ask is if introducing a coordinated fleet always reduces the PoA. In this section, we show that this is not necessarily the case. We derive a sufficient condition for the existence of a positive minimum fleet size required to affect the PoA.
**Theorem 1 (Critical fleet size):** Let $\mathcal{P}^i(z(\alpha))$ indicate the set of paths used by class $i$ at the equilibrium flow $z(\alpha)$, $i=C,S$, respectively. Let Assumptions 1 and 2 hold. Suppose that $\exists \tilde{\alpha} \in (0,1)$ such that $f^*(\tilde{\alpha})$ admits an equilibrium flow $z^*(\tilde{\alpha})$ such that $\mathcal{P}^C(z^*(\tilde{\alpha})) \subseteq \mathcal{P}^S(z^*(\tilde{\alpha}))^1$. Then,

$$f^*(\alpha) = \left( f^{S^*}(\tilde{\alpha}) + \frac{\tilde{\alpha} - \alpha}{\tilde{\alpha}} f^{C^*}(\tilde{\alpha}), \frac{\alpha}{\tilde{\alpha}} f^{C^*}(\tilde{\alpha}) \right), \quad (18)$$

and $\text{PoA}(\alpha) = \text{PoA}(0), \forall \alpha \in [0, \tilde{\alpha}]$.

*Proof:* Consider the equilibrium load $f^*(\tilde{\alpha})$ and the associated equilibrium flow $z^*(\tilde{\alpha})$. Clearly,

$$ \begin{aligned} z_p^{S^*}(\tilde{\alpha}) > 0 &\Rightarrow \sum_{l \in \mathcal{L}} A_{lp} d_l(\tilde{\alpha}) \le \sum_{l \in \mathcal{L}} A_l \gamma d_l(\tilde{\alpha}), \quad \forall \gamma \in \mathcal{P}, \\ z_p^{C^*}(\tilde{\alpha}) > 0 &\Rightarrow \sum_{l \in \mathcal{L}} A_{lp} m_l(\tilde{\alpha}) \le \sum_{l \in \mathcal{L}} A_l \gamma m_l(\tilde{\alpha}), \quad \forall \gamma \in \mathcal{P}. \end{aligned} \quad (19) $$

Consider the following feasible flow (obtained by moving part of the flow from C to S):

$$z^*(\alpha) = \left( z^{S^*}(\tilde{\alpha}) + \frac{\tilde{\alpha} - \alpha}{\tilde{\alpha}} z^{C^*}(\tilde{\alpha}), \frac{\alpha}{\tilde{\alpha}} z^{C^*}(\tilde{\alpha}) \right). \quad (20)$$

We show that $z^*(\alpha)$ is an equilibrium flow when the fleet share is $\alpha$, i.e.,

$$ \begin{aligned} z_p^{S^*}(\alpha) > 0 &\Rightarrow \sum_{l \in \mathcal{L}} A_{lp} d_l(\alpha) \le \sum_{l \in \mathcal{L}} A_l \gamma d_l(\alpha), \quad \forall \gamma \in \mathcal{P}, \\ z_p^{C^*}(\alpha) > 0 &\Rightarrow \sum_{l \in \mathcal{L}} A_{lp} m_l(\alpha) \le \sum_{l \in \mathcal{L}} A_l \gamma m_l(\alpha), \quad \forall \gamma \in \mathcal{P}. \end{aligned} \quad (21) $$

We prove each of the above conditions. The first easily follows after noticing that i) $z^*(\alpha)$ and $z^*(\tilde{\alpha})$ induce the same aggregate load, i.e., $F_l^*(\alpha) = F_l^*(\tilde{\alpha})$, so none of the path delays has changed, and ii) the set of paths used by vehicles in class S is the same, i.e., $\mathcal{P}^S(z^*(\tilde{\alpha})) = \mathcal{P}^S(z^*(\alpha))$ (since $\mathcal{P}^C(z^*(\tilde{\alpha})) \subseteq \mathcal{P}^S(z^*(\tilde{\alpha}))$). Hence, the first inequality in (19) ensures that all vehicles in class S still use shortest delay paths. As for the second condition, similarly, one has to prove that vehicles in class C still use shortest marginal delay paths. Because of the expression of (20), one can observe that:

* $\mathcal{P}^C(z^*(\alpha)) = \mathcal{P}^C(z^*(\tilde{\alpha})) \subseteq \mathcal{P}^S(z^*(\tilde{\alpha}))$;

* for every $p \in \mathcal{P}$, since the aggregate loads have not changed, the marginal delay is

$$m_p(\alpha) = \sum_{l \in \mathcal{L}} A_{lp} \left( d_l(\tilde{\alpha}) + \frac{\alpha}{\tilde{\alpha}} f_l^{C^*}(\tilde{\alpha}) d_l'(\tilde{\alpha}) \right),$$

By multiplying the first inequality in (19) by $1 - \alpha/\tilde{\alpha}$, the second one by $\alpha/\tilde{\alpha}$, then summing them, one obtains

$$ \begin{aligned} m_p(\alpha) = & \sum_{l \in \mathcal{L}} A_{lp} \left( d_l(\tilde{\alpha}) + \frac{\alpha}{\tilde{\alpha}} f_l^{C^*}(\tilde{\alpha}) d_l'(\tilde{\alpha}) \right) \le \\ & \sum_{l \in \mathcal{L}} A_{l\gamma} \left( d_l(\tilde{\alpha}) + \frac{\alpha}{\tilde{\alpha}} f_l^{C^*}(\tilde{\alpha}) d_l'(\tilde{\alpha}) \right) = m_\gamma(\alpha), \end{aligned} \quad (22) $$

$\forall p \in \mathcal{P}^C(z^*(\alpha)), \forall \gamma \in \mathcal{P}$. Hence, every $\mathcal{P}^C(z^*(\alpha))$ is still a shortest marginal delay path. Therefore, $z^*(\alpha)$ is a

equilibrium flow when the fleet share is equal to $\alpha$. The equilibrium load associated with $z^*(\alpha)$ is

$$f^*(\alpha) = \left( f^{S^*}(\tilde{\alpha}) + \frac{\tilde{\alpha} - \alpha}{\tilde{\alpha}} f^{C^*}(\tilde{\alpha}), \frac{\alpha}{\tilde{\alpha}} f^{C^*}(\tilde{\alpha}) \right),$$

which must correspond to the unique equilibrium of the problem. To conclude, notice that for all $\alpha \in [0, \tilde{\alpha}]$ all links have the same aggregate load. Hence $\text{PoA}(\alpha) = \text{PoA}(0)$ for all $\alpha \in [0, \tilde{\alpha}]$. ■

### C. PoA monotonicity for Parallel Networks

In this section, we study the dependence of the PoA on the fleet share $\alpha$ under the following assumptions.

**Assumption 3:** The network $\mathcal{G}$ is a parallel, thus it consists of an OD pair connected by finitely many links, all directed from the origin to the destination. Let $\alpha$ be the fleet share.

**Assumption 4:** The delay function $d_l$ is convex, $\forall l \in \mathcal{L}$. The assumption of parallel networks simplifies the analysis as, in that case, the notion of link and path coincides. Let $\mathcal{L}^i(\alpha)$ indicate the set of links used by class $i$ at the equilibrium $f^*(\alpha)$, $i = S, C$. The convexity of the delay functions instead ensures that $d_l'(F_l)$ is non-decreasing in $F_l$. Note that this implies the following monotonicity property

$$\bar{F}_l > F_l \text{ and } \bar{f}_l^C > f_l^C \quad \Rightarrow \quad m_l(\bar{f}_l) > m_l(f_l). \quad (23)$$

Let $\theta(\alpha)$ and $\mu(\alpha)$ indicate the minimum delay and the minimum marginal delay realised at equilibrium when the fleet share is $\alpha$, respectively. Observe that, since links and paths coincide, the equilibrium condition implies

$$l \in \mathcal{L}^S(\alpha) \Rightarrow d_l(F_l^*(\alpha)) = \theta(\alpha),$$

$$l \in \mathcal{L}^C(\alpha) \Rightarrow m_l(f_l^*(\alpha)) = \mu(\alpha).$$

**Proposition 3:** Let Assumptions 1, 3 and 4 hold. Suppose there exists $\alpha_1, \alpha_2 \in (0,1)$ such that $\alpha_1 < \alpha_2$ and $\mathcal{L}^S(\alpha_1) = \mathcal{L}^S(\alpha_2)$ and $\mathcal{L}^C(\alpha_1) = \mathcal{L}^C(\alpha_2)$. Then,

1) $\theta(\alpha_1) \ge \theta(\alpha_2)$;

2) $\mu(\alpha_1) \le \mu(\alpha_2)$;

3) $f_l^{S^*}(\alpha_1) \ge f_l^{S^*}(\alpha_2), \forall l \in \mathcal{L}$;

4) $f_l^{C^*}(\alpha_1) \le f_l^{C^*}(\alpha_2), \forall l \in \mathcal{L}$.

*Proof:* Since $\mathcal{L}^i(\alpha_1) = \mathcal{L}^i(\alpha_2)$, $i=S, C$, let us indicate both as $\mathcal{L}^i$, $i=S, C$ for convenience. Along with them, consider also the set $\mathcal{L}^{C\setminus S} := \mathcal{L}^C \setminus (\mathcal{L}^S \cap \mathcal{L}^C)$, corresponding to the set of links used by class C only. Notice that also this set remains constant in passing from $\alpha_1$ to $\alpha_2$. Also, since it is used by vehicles of class C only,

$$f_l^{C^*}(\alpha_i) = F_l^*(\alpha_i), \forall i \in \mathcal{L}^{C\setminus S}, i = 1, 2. \quad (24)$$

If $\mathcal{L}^{C\setminus S} = \emptyset$ the conclusion follows from Theorem 1. We next discuss the case in which $\mathcal{L}^{C\setminus S} \neq \emptyset$.

1) By contradiction, suppose that $\theta(\alpha_1) < \theta(\alpha_2)$. This implies that the aggregate load increased on all links in $\mathcal{L}^S$, i.e., $F_l^*(\alpha_1) < F_l^*(\alpha_2)$, $\forall l \in \mathcal{L}^S$. Now, since the demand of class S decreased, there must exist a link $j \in \mathcal{L}^S$ such that the load of class S on it decreased, i.e., $f_j^{S^*}(\alpha_1) > f_j^{S^*}(\alpha_2)$. The latter fact, combined with the increase of the aggregate loads on all link in $\mathcal{L}^S$, implies that the load of class C

<footnote n="1">¹Verifying this hypothesis can be difficult in practice. The derivation of alternative assumptions in left as future work.</footnote>
on link $j$ increased, i.e., $f_j^{C^*}(\alpha_1) < f_j^{C^*}(\alpha_2)$. By (23), the increase of both the aggregate load and the load of class $C$ on link $j$ implies that its marginal delay increased. Hence, $\mu(\alpha_1) < \mu(\alpha_2)$.

On the other hand, the increased load on links in $\mathcal{L}^S$ implies higher demand towards $\mathcal{L}^S$ and lower demand towards $\mathcal{L}^{C\setminus S}$. Then, there must be at least one link $e \in \mathcal{L}^{C\setminus S}$ whose aggregate load decreased, i.e., $F_e^*(\alpha_1) > F_e^*(\alpha_2)$. From (24), this is equivalent to $f_e^{C^*}(\alpha_1) > f_e^{C^*}(\alpha_2)$, which implies that $\mu(\alpha_1) > \mu(\alpha_2)$, contradicting what proved above. Therefore, $\theta(\alpha_1) \ge \theta(\alpha_2)$.

2) From 1), $\theta(\alpha_1) \ge \theta(\alpha_2)$, which implies that the aggregate load on none of the links in $\mathcal{L}^S$ can increase. Hence, the aggregate demand toward $\mathcal{L}^S$ cannot increase, which is equivalent to say that the aggregate demand toward $\mathcal{L}^{C\setminus S}$ cannot decrease. From (24), it follows that the demand associated with class $C$ directed toward $\mathcal{L}^{C\setminus S}$ did not decrease. Hence, there exists $e \in \mathcal{L}^{C\setminus S}$ such that $f_e^{C^*}(\alpha_1) \le f_e^{C^*}(\alpha_2)$. Thus, $\mu(\alpha_1) \le \mu(\alpha_2)$.

3) By contradiction, suppose that $\exists l \in \mathcal{L}^S | f_l^{S^*}(\alpha_1) < f_l^{S^*}(\alpha_2)$. Since on all links in $\mathcal{L}^S$ the aggregate load did not increase ($F_l(\alpha_1) \ge F_l(\alpha_2)$), the above implies that $f_l^{C^*}(\alpha_1) > f_l^{C^*}(\alpha_2)$. This implies $\mu(\alpha_1) > \mu(\alpha_2)$, contradicting point 2).

4) Suppose that there $\exists l \in \mathcal{L}^C | f_l^{C^*}(\alpha_1) > f_l^{C^*}(\alpha_2)$. By point 3) we also know that $f_l^{S^*}(\alpha_1) \ge f_l^{S^*}(\alpha_2)$. Hence $F_l(\alpha_1) > F_l(\alpha_2)$. By (23), this implies $\mu(\alpha_1) > \mu(\alpha_2)$, which contradicts 2). ■

**Remark 3:** The result above and its proof implicitly assume that $(\mathcal{L}^S \cap \mathcal{L}^C) \neq \emptyset$. To see that this is always true, assume by contradiction that $(\mathcal{L}^S \cap \mathcal{L}^C) = \emptyset$. Then, it follows

$$ \forall l \in \mathcal{L}^S(\alpha), \quad m_l(f_l^*(\alpha)) = d_l(F_l^*(\alpha)) = \theta(\alpha), $$

$$ \forall e \in \mathcal{L}^C(\alpha), \quad m_e(f_e^*(\alpha)) > d_e(F_e^*(\alpha)) \ge \theta(\alpha), $$

which is impossible as vehicles in class $C$ at equilibrium must use links of minimal marginal delay.

**Proposition 4:** Let Assumptions 1, 3 and 4 hold. Suppose there exists $\alpha_1, \alpha_2 \in (0, 1)$ such that $\alpha_1 < \alpha_2$ and $\mathcal{L}^S(\alpha_1) = \mathcal{L}^S(\alpha_2)$ and $\mathcal{L}^C(\alpha_1) = \mathcal{L}^C(\alpha_2)$. Then, $\text{PoA}(\alpha_1) \ge \text{PoA}(\alpha_2)$.

*Proof:* First of all, notice that it suffices to consider only the numerator (15) of PoA, as its denominator is constant. The numerator (15) can be written as follows:

$$ T(f^*(\alpha)) = \sum_{l \in \mathcal{L}} f_l^{S^*}(\alpha) \cdot d_l(\alpha) + \sum_{l \in \mathcal{L}} f_l^{C^*}(\alpha) \cdot d_l(\alpha) $$

From 1) of Proposition 3,

$$ \begin{aligned} \sum_{l \in \mathcal{L}} f_l^{S^*}(\alpha_2) \cdot d_l(\alpha_2) &= \theta(\alpha_2) \sum_{l \in \mathcal{L}} f_l^{S^*}(\alpha_2) \le \\ &\le \theta(\alpha_1) \sum_{l \in \mathcal{L}} f_l^{S^*}(\alpha_2) = \sum_{l \in \mathcal{L}} f_l^{S^*}(\alpha_2) \cdot d_l(F_l^*(\alpha_1)). \end{aligned} \quad (25) $$

Moreover, because of 3) of Proposition 3, one can observe that $f^{C^*}(\alpha_1) + (f^{S^*}(\alpha_1) - f^{S^*}(\alpha_2)) \in \mathcal{F}^C(\alpha_2)$. Therefore, if one defines $\varphi := f^{S^*}(\alpha_1) - f^{S^*}(\alpha_2) \ge 0$:

$$ \sum_{l \in \mathcal{L}} f_l^{C^*}(\alpha_2) \cdot d_l(F_l^*(\alpha_2)) \le \sum_{l \in \mathcal{L}} (f_l^{C^*}(\alpha_1) + \varphi) \cdot d_l(F_l^*(\alpha_1)), \quad (26) $$

where the inequality follows from the fact $f_l^{C^*}(\alpha_2)$ minimizes $\sum_{l \in \mathcal{L}} f_l^C \cdot d_l(f_l^{S^*}(\alpha_2) + f_l^C)$. The proof is concluded after noticing that summing the inequalities (25) and (26) one gets

$$ \begin{aligned} T(f^*(\alpha_2)) &\le \sum_{l \in \mathcal{L}} (f_l^{S^*}(\alpha_1) + f_l^{C^*}(\alpha_1)) \cdot d_l(F_l^*(\alpha_1)) = \\ &= \sum_{l \in \mathcal{L}} F_l^*(\alpha_1) \cdot d_l(F_l^*(\alpha_1)) = T(f^*(\alpha_1)). \end{aligned} $$

Finally, we study the monotonicity of the PoA under the following additional assumption.

**Assumption 5:** The sets $\mathcal{L}^S(\alpha)$ and $\mathcal{L}^C(\alpha)$ of active links change a finite number of times as functions of the fleet share $\alpha$ in $[0, 1]$.

**Theorem 2 (PoA monotonicity):** Let Assumptions 1, 3, 4 and 5 hold. PoA($\alpha$) is non-increasing in the fleet share $\alpha$.

*Proof:* Since: i) it follows from Proposition 2 that the PoA is Lipschitz continuous, ii) by Proposition 4, the PoA is non-increasing with $\alpha$ for any interval in which the support does not change, and iii) by Assumption 5, the support changes in a finite number of points, one can conclude that the PoA is non-increasing with $\alpha$ everywhere. ■

## V. EXAMPLES

In the following, we present two examples: the first considers a parallel network as studied in the previous section, while the second explores which results might extend to more general contexts and which may not.

**Example 1:** Consider the example in Figure 1. The plots show the evolution of the PoA($\alpha$), the equilibrium loads $f_l^*(\alpha)$, $l = 1, 2, 3$, $i = S, C$, and the link delays $d_l(\alpha)$, $l = 1, 2, 3$, as functions of $\alpha$, for $\alpha$ varying in $[0, 1]$. The three plots demonstrate that the PoA, the loads of class $S$ and the minimum delay at equilibrium are non-increasing in $\alpha$, while the loads of class $C$ are non-decreasing in $\alpha$. Notice also that, as long as $\alpha \le \tilde{\alpha} \approx 0.25$, the support of $C$ is included in that of $S$ and PoA($\alpha$) = PoA(0) for any $\alpha \le \tilde{\alpha}$, consistently with Theorem 1. Hence this is an example in which a minimum fleet size ($\tilde{\alpha}$) is needed for affecting the PoA.

**Example 2:** Consider the example in Figure 2. The plots depict the behavior of the PoA($\alpha$), the unique equilibrium path flows $z_p^*(\alpha)$, $p = 1, 2, 3, 4$, $i = S, C$ and the path delays $d_p(\alpha)$, $p = 1, \dots, 4$, as functions of $\alpha$, for $\alpha$ varying in $[0, 1]$. Although uniqueness of the equilibrium flow $z^*(\alpha)$ is not guaranteed in general, in this case, it follows from the uniqueness of the equilibrium load $f^*(\alpha)$ for all $\alpha \in [0, 1]$. This is because each path in the network (Figure 2) includes a link not shared with any other path, so the load on that link determines the flow on the corresponding path. Since the equilibrium load is unique, so is the equilibrium flow. As in the parallel network case, the PoA, equilibrium flows for class $S$, and the minimum path delay are non-increasing in $\alpha$. However, the path flows for class $C$ in this simulation are not necessarily monotone (e.g., the flow on path 4). Whether monotonicity of the PoA can be proven in this more general case remains an open question.
<figure><img src="image_4.png" /><figcaption>Fig. 1: A parallel network with link delays labeled. Here, $D = 4$. Violet, green, and light-blue lines represent top, middle, and bottom links, respectively. Solid and dashed lines denote loads for classes *S* and *C*, respectively. Vertical gray dashed lines indicate changes in vehicle class support as $\alpha$ varies.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 2: A network with seven links and four paths. Link delays labeled. Here, $D = 3$. Blue, orange, yellow, and magenta lines represent Paths 1, 2, 3, and 4, respectively. Solid and dashed lines denote flows for classes *S* and *C*, respectively. Vertical gray dashed lines indicate changes in vehicle class support as $\alpha$ varies.</figcaption></figure>

## VI. CONCLUSION

This paper shed lights on how coordinated routing influences the efficiency of transportation networks. We uncover two key phenomena in two-terminal networks. First, we identify

scenarios where the coordinated fleet must reach a certain size before impacting the PoA of the unique equilibrium load. Second, we demonstrate that in parallel networks, under suitable assumptions, the PoA weakly decreases as the size of the coordinated fleet increases.

We plan to explore several future directions. First, we aim to more precisely characterize the threshold phenomenon related to the share of the coordinated fleet by establishing clear conditions under which this phenomenon occurs. Additionally, we intend to investigate whether the monotonicity of the PoA holds in more general two-terminal networks, as suggested by the final example in Section V. Lastly, we aim to extend our analysis to networks with multiple origins and destinations. For this setting, we remark that [12] already proved that PoA monotonicity does not hold in general. Yet, we believe that establishing sufficient network conditions guaranteeing that the presence of coordinated fleets improves network efficiency would represent an important future contribution. Future work will also be dedicated to investigate the monotonicity of the PoA with more general delay functions, beyond the constraint in equation (14).

## REFERENCES

[1] F. Facchinei and J.-s. Pang, *Finite-dimensional variational inequalities and complementarity problems*. Springer New York, 2003.

[2] G. Scutari, D. P. Palomar, F. Facchinei, and J.-s. Pang, "Convex optimization, game theory, and variational inequality theory," *IEEE Signal Processing Magazine*, vol. 27, no. 3, pp. 35–49, 2010.

[3] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, *Algorithmic Game Theory*. Cambridge University Press, 2007.

[4] S. C. Dafermos, "The traffic assignment problem for multiclass-user transportation networks," *Transportation Science*, vol. 6, no. 1, pp. 73–87, 1972.

[5] P. T. Harker, "Multiple equilibrium behaviors on networks," *Transportation Science*, vol. 22, no. 1, pp. 39–46, 1988.

[6] T. Boulogne, E. Altman, H. Kameda, and O. Pourtallier, "Mixed equilibrium (ME) for multiclass routing games," *IEEE Transactions on Automatic Control*, vol. 47, no. 6, pp. 903–916, 2002.

[7] H. Yang, X. Zhang, and Q. Meng, "Stackelberg games and multiple equilibrium behaviors on networks," *Transportation Research Part B: Methodological*, vol. 41, no. 8, pp. 841–861, 2007.

[8] G. Sharon, M. Albert, T. Rambha, S. Boyles, and P. Stone, "Traffic optimization for a mixture of self-interested and compliant agents," *Proceedings of the AAAI Conference on Artificial Intelligence*, vol. 32, no. 1, 2018.

[9] Z. Chen, X. Lin, Y. Yin, and M. Li, "Path controlling of automated vehicles for system optimum on transportation networks with heterogeneous traffic stream," *Transportation Research Part C: Emerging Technologies*, vol. 110, pp. 312–329, 2020.

[10] K. Zhang and Y. M. Nie, "Mitigating the impact of selfish routing: An optimal-ratio control scheme (ORCS) inspired by autonomous driving," *Transportation Research Part C: Emerging Technologies*, vol. 87, pp. 75–90, 2018.

[11] G. Nilsson, P. Grover, and U. Kalabić, "Assignment and control of two-tiered vehicle traffic," in *2018 IEEE Conference on Decision and Control (CDC)*, 2018, pp. 1023–1028.

[12] M. Battifarano and S. Qian, "The impact of optimized fleets in transportation networks," *Transportation Science*, vol. 57, no. 4, pp. 1047–1068, 2023.

[13] T. Toso, F. Parise, P. Frasca, and A. Y. Kibangou, "On the impact of coordinated fleets size on traffic efficiency," *arXiv preprint arXiv:2408.15742*, 2024.