{'fraction_non_alphanumeric': 0.03695584090197307, 'fraction_numerical': 0.006666368395150105, 'mean_word_length': 4.542276221175304, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stability and bifurcations in transportation networks with heterogeneous users

A critical aspect in strategic modeling of transportation systems is user heterogeneity. In many real-world scenarios, e.g., when tolls are charged and drivers have different trade-offs between time and money, or when they get informed about current congestion by different routing apps, modeling users as rational decision makers with homogeneous utility functions becomes too restrictive. While global asymptotic stability of user equilibria in homogeneous routing games is known to hold for a broad class of evolutionary dynamics, the stability analysis of user equilibria in heterogeneous routing games is a largely open problem. In this work we study the logit dynamics in heterogeneous routing games on arbitrary network topologies. We show that the dynamics may exhibit bifurcations as the noise level of the dynamics varies, and provide sufficient conditions for asymptotic stability of user equilibria.


I. INTRODUCTION
Due to the rising congestion level of urban areas and the fast-increasing pervasiveness of novel intelligent technology that is having a huge impact on the transportation system, the analysis, design, and control of traffic networks have received renewed attention. A key aspect to be properly addressed in this research is the fact that routing apps and other information technology systems are completely reshaping users' behaviour. Given the increasing amount of available information and the selfish and often competing objectives of the users, it is natural to incorporate game-theoretic aspects in traffic models.
An important aspect in game-theoretic traffic models is concerned with the user preferences. The most popular model assumes homogeneity, i.e., that all users make decisions based on identical utility functions, given their available information [1]. However, this assumption may prove too restrictive to model many real-world scenarios of interest, e.g., when drivers use different routing apps [2], [3], when fuel consumption or monetary tolls constitute a nonnegligible fraction of the cost and users have different tradeoffs between time and money [4], [5], or when users have different knowledge on the available routes [6]. Homogeneous models have been first generalized in [7] to account for heterogeneity of the utility functions. From now on, we shall refer to heterogeneous routing games to denote Leonardo  game-theoretic models that incorporate user heterogeneity, in contrast with homogeneous routing games, which do not consider this aspect.
Besides user heterogeneity, another crucial aspect in gametheoretic models is the evolution of network flows under evolutionary dynamics, which describe how users revise their strategies. The distinction between homogeneous and heterogeneous routing games has several implications on the properties of the game, in particular on the stability of the user equilibria under evolutionary dynamics. While global asymptotic stability of user equilibria in homogeneous routing games is known to hold for a broad class of evolutionary dynamics [8], their stability in heterogeneous routing games is a largely open issue. Besides the theoretical interest, stability of equilibria has practical implications and paves the way for control applications. Indeed, since heterogeneous routing games may admit multiple user equilibria [9], understanding whether the network flows will converge to an equilibrium, and identifying which one will be selected by the dynamics in case of non-uniqueness, are fundamental questions for a system planner that aims at optimizing the transportation network performance.
In most of the literature dealing with user heterogeneity, a big effort is spent to analyse the static properties of the equilibria, but the stability of such equilibria is typically not investigated [2], [3], [4], [10], [11], implicitly assuming that the network flows converge to the equilibria of the game. However, this assumption is not always justified and requires to be further motivated. To the best of our knowledge, the only stability result in heterogeneous routing games states that a sufficient condition for global asymptotic stability of the equilibria is that the graph has parallel routes, or it is the series composition of graphs with parallel routes [12].
In this work we investigate the behaviour of the logit dynamics, which models users that aim at choosing optimal routes, but due to imperfect information or incomplete rationality may sometimes select suboptimal ones. We establish novel results that hold for every heterogeneous routing game, independently of the network topology. Our contribution is the following. We first characterize the set of fixed points of the logit dynamics (the expression fixed points is used in this context to avoid any source of confusion between equilibrium points of the logit dynamics and user equilibria of the routing game), and prove that such a set approaches a subset of the Wardrop equilibria of the game (called limit equilibria) in the vanishing noise limit. We then show that all the strict equilibria of the game (i.e., equilibrium flows under which every population uses a single route and all the other routes are strictly suboptimal) belong to the set of limit equilibria, and prove their local asymptotic stability under the logit dynamics. We also show that, in the large noise limit, the logit dynamics admits a globally asymptotically stable equilibrium in every heterogeneous routing games. Finally, we conduct numerical simulations to validate our theoretical results, and show that the dynamics may exhibit bifurcations as the noise varies, in contrast with the behaviour observed in homogeneous routing games.
The rest of the paper is organized as follows. In Section II we define heterogeneous routing games, introduce the logit dynamics, and discuss a motivating example. In Section III we establish our novel results on the logit dynamics in heterogeneous routing games. Finally, in the conclusive Section IV, we summarize the results and discuss future research lines.

Notation
Let R and R + denote the set of real numbers and nonnegative reals. Given a finite set X , we let R X the space of real-valued vectors whose elements are indexed by X , and |X | denote the cardinality of X . Let δ (i) , 1, 0, and I denote the vector with 1 in position i and 0 in all the other positions, the vector of all ones, the matrix of all zeros, and the identity matrix, respectively, where the size may be deduced from the context. The distance between a point y in R n and a set X ⊆ R n is defined as

II. MODEL
In this section we define the model and discuss a motivating example. Specifically, in Section II-A we describe heterogeneous routing games. Then, in Section II-B, we introduce the logit dynamics and provide numerical simulations of the dynamics in a heterogeneous routing game.

A. Heterogeneous routing games
We model the transportation network as a directed multigraph G = (N , E), with node set N and link set E. We consider a finite set P of users populations. Let each population p in P have an origin-destination pair (o p , d p ) in N × N and let v p ≥ 0 denote the throughput of population p. We then stack all throughput values in a vector v ∈ R P + . Let R p denote the set of routes from o p to d p , indicate the set of the admissible route flows for population p, and Z denote the product of such sets. Every route flow z ∈ Z induces a unique link flow via where A p ∈ R E×Rp is the link-route incidence matrix, with entries A p er = 1 if the link e belongs to the route r, or 0 otherwise. The populations differ in the origin-destination pair and in the delay functions according to which they make decisions. Let τ p e : R + → R + denote the delay function of link e ∈ E for population p ∈ P, which is assumed a nondecreasing function of f e to take into account congestion effects. We also assume that τ p e ∈ C 1 . The cost of a route r is defined as the sum of the delay functions of the links belonging to the route, i.e., where, given z ∈ Z, the link flow f is computed via (1). Definition 1: A heterogeneous routing game is a quadruple (G, P, τ, v), where τ is the vector collecting the delay functions of every link and population.
We assume that the users behave as players in a gametheoretic setting, taking route with minimal cost. This behaviour is captured by the notion of Wardrop equilibrium.
Definition 2 (Wardrop equilibrium): A Wardrop equilibrium is an admissible route flow z ∈ Z such that for every population p ∈ P and route r ∈ R p In other words, under Wardrop equilibrium flow, no user can unilaterally decrease her cost by changing route, because every used route by a population is optimal for that population. An equilibrium is called strict if every population uses one route only and the other routes are strictly suboptimal. We let Z * and Z * s denote the set of Wardrop equilibria and strict Wardrop equilibria of a routing game, respectively. It is proved in [8, Theorem 2.1.1] that Z * is never empty, i.e., there exists at least a Wardrop equilibrium. Moreover, standard arguments allow to state that Z * is also compact.

B. Logit dynamics
While the description made so far is completely static, we now endow routing games with evolutionary dynamics. These are continuous-time dynamical systems that describe how users revise their decisions. In this work we focus on the logit dynamics. The logit dynamics arises from the mean-field limit (in the spirit of Kurtz's theorem [13]) of the noisy best response dynamics of classical game theory, which describes users that aim at choosing optimal routes, but sometimes select suboptimal ones due to the presence of noise. Formally, the logit dynamics reads, for every p ∈ P and i ∈ R p ,ż where η ∈ (0, +∞) is the noise level. We refer to logit(η) to denote the continuous-time dynamical system (4) for a given value of η. The value of η describes how suboptimal the choices of the users are. As η → +∞, the users select routes with uniform probability distribution, independently of the route cost, i.e.,ż A heterogeneous routing games possessing multiple Wardrop equilibria [14].
As the noise η decreases, the users tend to assign a larger probability to routes with smaller cost. In the limit of vanishing η, the dynamics converge to the best response dynamics, where users sample uniformly random among the optimal routes and choose suboptimal ones with zero probability.
It is known that, for homogeneous routing games, i.e., when |P| = 1, for every η > 0 the logit dynamics admit a globally asymptotically stable fixed point z η and that such z η converges to the set of Wardrop equilibria as η tends to vanish, i.e., lim η→0 + dist(z η , Z * ) = 0 . In contrast, the following example illustrates how much more complex behaviors can emerge in case of heterogeneous congestion games, i.e., when |P| ≥ 2.
Example 1: Consider the heterogeneous routing game in Figure 1 (due to [14]). We assume that all the populations have the same origin-destination pair (o, d), and let   defined in this example, since all the populations have same origin-destination pair and route set). As η = 10 6 (large noise limit) both the trajectories converge to a fixed point in which all the populations distribute uniformly over the route set. As the noise decreases (η = 1/2), the asymptotic state of the system varies, but the trajectories still converge to a unique fixed point. For smaller η, the system exhibits a bifurcation. Specifically, the two trajectories converge to different fixed points, which approach the two strict equilibria of the game as η decreases. We observe from Figure 3 that the system exhibits a pitchfork bifurcation. By numerical simulations one can observe that the critical value for the bifurcation is η * ≃ 0.31. If η > η * , the system admits a globally asymptotically stable fixed point. If η < η * , such a fixed point becomes unstable, and two stable fixed points approaching the strict equilibria arise. The unstable fixed point converges to the third Wardrop equilibrium as η tends to vanish, thus showing that all the Wardrop equilibria are accumulation points of sequence of fixed points of the dynamics, despite the third one being unstable. In the next section we shall provide our theoretical results, which formalize some of the observations of this section.

III. MAIN RESULTS
In this section we present our main results characterizing the fixed points of the logit dynamics and their stability in heterogeneous routing games.
Our first result shows that the set of the fixed points is non-empty and compact for every noise level, and that the fixed points approach a subset of Wardrop equilibria of the game (called limit equilibria) in the limit of vanishing noise. Moreover, we show that every strict equilibrium belongs to the set of the limit equilibria. In order to formulate the results properly, for every η ∈ (0, +∞) we let Ω η ⊆ Z denote the set of fixed points of logit(η), and let Ω 0 denote the set of accumulation points of convergent sequences of fixed points of the logit dynamics as the noise vanishes, i.e., Ω 0 = {z ∈ Z : ∃ (η n ) n , η n → 0, z n ∈ Ω ηn , z n → z} .
Theorem 1: Let Z * ⊆ Z be the set of Wardrop equilibria of a heterogeneous routing game, and consider the associated dynamics logit(η) defined in (4). Then: (i) Ω η is non-empty and compact for every η > 0; (ii) Ω 0 is a non-empty compact subset of the Wardrop equilibria, i.e., Ω 0 ⊆ Z * ; (iii) all strict Wardrop equilibria (if any) belong to Ω 0 , i.e., Moreover, for every strict equilibrium z * ∈ Z * s , there existsη > 0 and a family of vectors (z η ) η<η ⊆ Z such that lim with z η asymptotically stable fixed point of logit(η). Proof: See Appendix I. Throughout the paper, we shall refer to Ω 0 as the set of limit equilibria of the routing game. Theorem 1 states that the set of limit equilibria is a nonempty compact subset of Wardrop equilibria that includes all strict Wardrop equilibria (if any). Moreover, in addition to being approximated by fixed points of the logit dynamics, strict equilibria are also locally asymptotically stable under the dynamics in the vanishing noise limit.
Remark 1: This result must be compared with the existing literature. It is known that interior evolutionary stable states z of populations game admit a neighborhood of z such that, for large enough η, there exists one and only one fixed point of logit(η) [8,Theorem 8.4.6]. Moreover, such fixed points are locally asymptotically stable in the limit of vanishing noise. Although strict equilibria are evolutionary stable states, they are not interior, thus violating one of the assumptions of [8,Theorem 8.4.6] and making our result original.
In the next part of this section we investigate the asymptotic behaviour of the logit dynamics in the large noise limit. The next result states that in this regime the logit dynamics admits a globally exponentially stable fixed point for every routing game.
Proof: See Appendix II. The results established in Theorems 1-2 characterize the behaviour of the logit dynamics in heterogeneous routing games independently of the network topology, and explain the numerical simulations of Example 1. In particular, the theorems suggest that, if a heterogeneous routing game admits multiple strict equilibria, then the logit dynamics admit a bifurcation, as shown in Example 1. We conclude this section with some remarks.

Remark 2:
The behaviour of the logit dynamics in heterogeneous routing games must be compared with stability results in homogeneous routing games. The asymptotic global stability of equilibria in homogeneous routing games relies on the fact that homogeneous routing games admit a convex potential function V (z) [15], i.e., Wardrop equilibriã z correspond to solutions of the convex program z ∈ arg min z∈Z V (z).
The existence of a convex potential implies that is a strictly convex Lyapunov function of logit(η), hence the unique minimizer of V η , denoted by z η , is globally attractive for the dynamics. As η tends to vanish, lim η→0 + dist(z η , Z * ) = 0, i.e., the asymptotically globally stable fixed of the dynamics converges to the set of the Wardrop equilibria of the game. Observe that, since the potential V (z) is convex, the set of the Wardrop equilibria is convex. However, as stated for heterogeneous routing games in Theorem 1-(ii), the fixed points of the dynamics approach the set of the Wardrop equilibria of the game as the noise vanishes, but not every Wardrop equilibrium is an accumulation point of fixed points of the logit dynamics. Strict equilibria play a special role also in homogeneous routing games. Indeed, if a homogeneous routing game game admits a strict equilibriumz, thenz is isolated and Z * is a singleton. Therefore, if a homogeneous routing game admits a strict equilibriumz, thenz is globally asymptotically stable in the vanishing noise limit. Observe that the local asymptotic stability of strict equilibria in heterogeneous routing games established in Theorem 1-(iii) is a weaker result compared to the global asymptotic stability established for homogeneous routing games. We remark that this limitation is an intrinsic property of heterogeneous routing games. Indeed, as illustrated in Example 1, heterogeneous routing games may admit multiple strict equilibria, hence global asymptotic stability of strict equilibria does not hold in general. Remark 3: Similar considerations as in Remark 2 apply to heterogeneous routing games that admit a convex potential. While in general heterogeneous routing games do not admit a potential function [8], [16], if the delay functions satisfy the symmetry condition then the game admits a potential function. Such a condition is satisfied for instance if the populations differ only in the origin-destination pair, or if constant tolls are charged and the populations differ in the toll sensitivity, i.e., the delay functions (including tolls) are in the form τ p e (f e ) = τ e (f e ) + α p ω e .
Indeed, one can prove that is a convex potential function for this class of games. While in [4], [5] the existence and characterization of optimal tolls for this class of heterogeneous games are provided, the existence of a convex potential function guarantees that optimal flows are globally asymptotically stable under the logit dynamics when optimal tolls are charged. The existence of a potential function is lost if tolls are in feedback form instead of constant.

IV. CONCLUSIONS AND FUTURE RESEARCH
In this paper we investigate the asymptotic behaviour of the logit dynamics in heterogeneous routing games. We show that fixed points of the logit dynamics converge to a subset of Wardrop equilibria (called limit equilibria) in the vanishing noise limit, and that the set of the limit equilibria include all the strict equilibria of the game. Additionally, we show that strict equilibria are locally asymptotically stable in the vanishing noise limit. Finally, we show that the dynamics admits a globally asymptotically stable fixed point in the large noise limit. Those results together suggest that if a heterogeneous routing game admits multiple strict equilibria, then the logit dynamics exhibits a bifurcation as the noise varies, as shown in the numerical example of Example 1.
Future research lines include the complete characterization of the limit equilibria in the vanishing noise limit. Our conjecture is that every connected component of equilibria admits one and only one limit equilibrium of the logit dynamics. While strict equilibria have been proven to be locally asymptotically stable, another open issue is a complete characterization of the asymptotically stable equilibria of heterogeneous routing game.
Another interesting direction is the application of our theoretical results for the analysis of multi-scale dynamics, the design of dynamic feedback tolls, and the optimization of network interventions in heterogeneous congestion games. While these problems have been addressed, e.g., in [17], [18], and [19], respectively, for homogeneous preferences, we are not aware of extensions of these results to the heterogeneous case.
follows from the implicit function theorem applied to the function g in (z, 0) [21]. To prove the asymptotic stability of this family of fixed points, notice that J g,z (z, η) = J G,z (z, η) − I.

APPENDIX II PROOF OF THEOREM 2
We first establish a result on contractive systems. The result is not original and may be found in [22]. Still, we provide an alternative and more intuitive proof. Our proof borrows techniques from [23,Lemma 5], where the authors prove that every monotone diagonally dominant system is l 1 -contractive. Proposition 1 generalizes this result, proving that the Jacobian with negative diagonally dominant columns is a sufficient condition for l 1 -contractivity.
Proposition 1: Letẋ = g(x) be a continuous-time dynamical system. Assume that g : R n → R n is continuously differentiable in X ⊆ R n . Let J(x) denote the Jacobian of g, and let max j∈{1,...,n} Assume that X is g-invariant, and let x(t) and y(t) denote the trajectories at time t corresponding to initial conditions x(0) = x 0 ∈ X and y(0) = y 0 ∈ X , respectively. Then, 1) for every t ≥ 0 ||x(t) − y(t)|| 1 ≤ e −ct ||x 0 − y 0 || 1 , 2) There exists a globally exponentially stable fixed point in X . Proof: For simplicity of notation we omit the dependence on t. By definition of the l 1 -norm and the linearity of the derivative, we get d dt where x = y + h. From It holds that i sign(h i ) j ∂gi ∂yj h j is equal to Plugging this in (20), we get which implies (19). For point 2) we refer to [22,Theorem 13].
We can now proceed to the proof of Theorem 2. Similarly to what done in the proof of Theorem 1-iii), we write logit(η) in the formż = g(z, η) = G(z, η) − z, and the Jacobian of g as J g,z (z, η) = J G,z (z, η) − I.
Since J(z, η) is continuously differentiable in η, it follows that for every k ∈ (0, 1] there exists η k ≥ 0 such that for every z ∈ Z and η ∈ [η k , +∞), Let η 0 be the largest η > 0 such that Thus, the existence of a globally exponentially stable fixed point for every η ∈ (η, +∞) follows from Proposition 1 and from identifying η with η 0 .