As CAV technology continues to develop, drivers are expected to cede commute decisions such as routing [1], presenting the opportunity for large-scale control to improve transportation systems. Transportation networks are often modeled as population games [2], [3], [4] to capture the dynamic behavior of non-cooperative agents making selfish decisions. Here, agents represent drivers on a roadway network, with populations defined by origin-destination (OD) pairs and vehicle types (regular or autonomous), each with its own mass. Agents in each population choose strategies corresponding to paths from a shared set and update their choice at each time-step to minimize their individual travel times. The strategy revision process follows an evolutionary dynamics model, where we consider the class of impartial pairwise comparison (IPC) dynamics.
Each strategy corresponds to a payoff representing the negative of the path travel time, and system states are defined by the mass of drivers selecting a particular strategy. In this context, the Nash equilibrium corresponds to the state where no driver can unilaterally improve their travel time by switching paths [5]. Stability of the equilibrium for dynamic traffic models was first studied in [6] using a Lyapunov approach to analyze convergence of a continuous-time routing process for homogenous traffic. Assuming a monotonically increasing and continuously differentiable payoff function, the routing dynamics were proved to be globally asymptotically stable. R. Lee, J. Scruggs, and Y. Yin are with the Department of Civil & Environmental Engineering, University of Michigan, Ann Arbor, MI, 48109. email: leerich@umich.edu, jscruggs@umich.edu, yafeng@umich.edu Passivity methods for population games have been studied in [7], [8], [9], while [10], [11] studied passivity specifically over networks. Reference [12] presents passivity techniques that prove global asymptotic stability of the socalled mean closed-loop model. This system consists of a feedback interconnection between strategy updates described by the evolutionary dynamics model (EDM) and the payoffs dynamics model (PDM). Stability conditions derived from the concept of δ-dissipativity are described in terms of the derivative of the system input and the derivative and the system output. mixed traffic is commonly modeled as a weighted congestion game parameterized by the headway ratio of CAVs to RVs [13]- [16]. This model assumes CAVs follow all other vehicles with a uniform headway. Under this assumption, [12] leverages δ-dissipativity using a potential function to prove global asymptotic stability of the mean closed-loop model described by the EDM and the PDM. However, mixed traffic models for which the CAV headway behavior may be non-uniform between following vehicle types are of interest. In this general mixed traffic setting, no such potential function is believed to exist.
Discrete-time dynamics have also garnered interest. Routing algorithms for convergence to an exact equilibrium on a network with monotone latency functions are studied in [17], while [18] proposes a controller for convergence to an approximate routing equilibrium under time-varying delays. In transportation networks, discrete-time systems may provide a more realistic model of traffic flow evolution due to day-to-day event variations [19], [20]. These discrete-time analyses typically model the traffic evolution process with an Euler approximation of continuous time EDMs. These models constrain the time-step parameter to ensure that states remain non-negative over time. Furthermore, it is unclear if these models satisfy δ-dissipativity.
This paper thus proposes a new discrete-time EDM which preserves state feasibility for any size of the time-step parameter. Additionally, we show that our model satisfies a discrete analogy to the δ-dissipativity methods presented in [12], and we use this property to derive sufficient conditions for global asymptotic stability of the routing equilibrium for both the single-class traffic setting and the mixed traffic setting with uniform CAV headway. We then consider a more realistic mixed traffic model from [21] where the CAV headway depends on the vehicle type being followed. We propose a control algorithm for the CAV payoff vector and present sufficient conditions under which there exists a stabilizing controller ensuring global stability to the Nash equilibrium set. We then optimize the control design to improve the convergence rate.
The paper is outlined as follows: Section II introduces the modeling notation for the EDM and the PDM, describes key assumptions used in the model, and presents the novel discrete-time EDM. Section III applies discrete-time dissipativity techniques to the proposed EDM and analyzes the routing stability homogenous traffic and for mixed traffic where autonomous and regular vehicles have uniform headways. Section IV presents a model for mixed traffic in which vehicle headways are dependent on the type of vehicle being followed. We present sufficient conditions for existence of a dynamic CAV payoff algorithm which guarantees global convergence to Nash equilibrium, and we formulate an optimization problem for the control design to optimize the convergence rate. Section V presents experimental results to illustrate the effectiveness of our controller. Section VI provides some brief conclusions. To enhance readability, all proofs are relegated to the appendix.
We assume the congestion game has ρ populations indexed by r ∈ {1, ..., ρ}, where each population corresponds to a particular combination of OD pair and vehicle type. Associated with each population r is the state vector at time k, given by x r k ∈ X r ⊂ R n r ⪰0 . Entries of the state vector x r i,k correspond to the mass of each population m r choosing the i th strategy (route/path) for strategies i ∈ {1, ..., n r }. The corresponding state space is then given by
Concatenating the state vector for each population yields the complete state vector x k ∈ R n , where n represents the total number of paths in the network
Each population has an associated payoff vector p r k ∈ R n r where entries p r i,k represent the incentive rewarded for each strategy i ∈ {1, ..., n r }. The total payoff vector includes payoffs for all populations, i.e.,
We consider a static payoff mechanism F : X → R n which determines the p k from the current state x k
We assume F (•) is continuously differentiable.
C. Nash Equilibrium Definition 1: The set N F associated with a memoryless payoff mechanism F (x) is the set of all states x ∈ X such that the following condition holds:
As such, N F is the set of all Nash equilibria associated with F . This set can be shown to be nonempty and closed.
Strategies for each population are traditionally assumed to evolve according to EDMs of the form
where τ is the time-step and each ν r is assumed to be a Lipschitz continuous function. The vector ν is the concatenation of population EDMs:
We consider a particular class of dynamics ν r adhering to the IPC protocol, for which
where pr ij,k ≜ p r i,k -p r j,k and where the IPC protocol is characterized by comparison functions ϕ r i such that ϕ i (p r ij,k ) > 0 for pr ij,k > 0 and ϕ(p r ij,k ) = 0 for pr ij,k ≤ 0. Even when entries of x k are non-negative, entries of x k+1 may become negative if the time-step τ is sufficiently large, leading to infeasible states. Furthermore, it is unclear that δ-dissipativity can be used to analyze (7). This motivates the need for an EDM which preserves state feasibility. Therefore, we propose a modification to the EDM in (7).
Theorem 1: Suppose population strategies evolve according to an EDM of the form
where ν r i is an IPC protocol. Then, it follows that if x k ∈ X, then x k+1 ∈ X for any time-step τ ∈ R >0 .
Remark 1: In addition to preserving feasibility, a key property of the EDM in Theorem 1 is that discrete-time δ-dissipativity methods can be used for stability analysis. Meanwhile, it is unclear if the model ( 8) has this property.
Definition 2: An EDM ν is said to satisfy Nash stationarity if the following equivalence holds for all x ∈ X and p ∈ R n :
This section presents a discrete-time analogy to the methods presented in [12] and derives sufficient conditions for stability of homogeneous traffic and mixed traffic with uniform CAV headway.
A. δ-dissipativity Definition 3: An EDM ν is called δ-dissipative if there exists a continuously differentiable storage function S(x, p) :
and supply rate function s(x, p) which satisfy the dissipation inequality given by
and where the supply rate is a function characterized by Π = Π T of the form
and where
, Theorem 2: Let ν be an IPC EDM of the form (9), and let θ r j denote the maximum slope magnitude of the comparison function ϕ r j . Suppose that the functions ϕ r j are monotonically nondecreasing. Then the EDM ν as in ( 9) is δ-dissipative with storage function and dissipation functions
and supply rate
where
Remark 2: For the EDM we propose in ( 9), the expressions S(x, p), σ(x, p), and s(x, p) used to show δdissipativity have similar forms to those used in continuous time models. In contrast, it is unclear how to show δdissipativity for the model (6).
Theorem 3: Suppose the EDM ν is δ-dissipative and exhibits Nash stationarity. Suppose further that payoff p k satisfies the following inequality for all k:
Then the set N F is globally asymptotically stable.
Let R denote the path-link incidence matrix for a network, i.e., let R ij = 1 if path x i contains link j ∈ {1, ..., L} and let R ij = 0 otherwise. The link flow vector z is given by:
For homogenous traffic (where each vehicle has the same headway), the travel time T j,k for link j on day k can be assumed to be a separable function of the link flow z j,k .
where Φ j is monotonically increasing and continuously differentiable with respect to z j ∈ R ≥0 . In this case, the static payoff mechanism is given by
Theorem 4: Suppose the EDM ν exhibits Nash stationarity and is δ-dissipative. Let γ j denote the maximum slope magnitude of the link travel time Φ j . Suppose further that the static payoff mechanism F satisfies:
where
Then the set N F is globally asymptotically stable.
Without loss of generality, we assume the state vector is now partitioned as:
where x A and x R are the autonomous and regular vehicle population vectors corresponding to each strategy, respectively. Respective state vectors for the each population (i.e., OD pair) are denoted by x Ar and x Rr , for r ∈ {1, . . . , ϱ} with ϱ ≜ ⌊n/2⌋. For i ∈ {1, . . . , n r } we assume components x Ar i and x Rr i correspond to the same strategy (i.e., route) for the two populations. The augmented incidence matrix R for both vehicle types is therefore partitioned as
The link flows for the CAVs and RVs, respectively, are
The travel time associated with a link j ∈ {1, . . . , L} is in general an independent function of both z A and z R , i.e.,
where Φ j : R ⩾0 ×R ⩾0 → R >0 is a monotonically increasing function of either argument with the other argument fixed.
Formulating the payoff as the negative of the travel time for each strategy, we have that
We consider here the special case where the link travel time Φ can be reduced to a function of the form
where Φj : R ⩾0 → R >0 is an increasing function. In the above expression µ is the ratio of the headway of CAVs, to that of RVs. It is assumed that this ratio is uniform for all links and is the same irrespective of which type of vehicle the autonomous vehicle follows. Suppose that S in ( 14) and σ in ( 15) are modified such that all terms corresponding to CAV populations x Ar are multiplied by µ. It then follows that the system is δdissipative with supply rate parameter
where M A and M R are respective block diagonal matrices corresponding to CAV and RV populations, with entries M r as described in (20). Theorem 5: Suppose the EDM ν is δ-dissipative with parameter Π as defined in (33) and z A , z R as in (29). Assume both CAVs and RVs follow the static payoff p k = F (x k ) defined by
Let ω j denote the maximum slope of the link travel time Φj (z j ) and with z j ≜ µz A j + z R j . Assume Φj satisfies
where
Then the set N F is globally asymptotically stable.
IV. CASE WITH NON-UNIFORM CAV HEADWAY This section applies dissipativity techniques to more realistic models for link travel time, where the flow variable z j may not necessarily reduce to a linear function of z A j and z R j . In particular, [21] presents a model for link travel time based on the well known BPR function where the CAV headway depends on the vehicle type being followed:
where z j is now given by
and where {h R j , h C j , h A j } ⊂ R >0 with h A j ⩾ h R j ⩾ h C j . These constants are the critical time headways, respectively, for CAVs following RVs, RVs, and CAVs following each other. In this section we study conditions under which a stabilizing controller exists by proposing a dynamic payoff mechanism for CAV populations.
Suppose that RVs retain the static payoff mechanism (24):
For CAV populations, we propose a dynamic feedback mechanism of the form:
We assume G : X×R ⌊n/2⌋ is such that the augmented system
has a solution (x k , p A k ) for all initial conditions (x 0 , p A 0 ) ∈ X × R ⌊n/2⌋ , and all k.
Definition 4: The Extended Nash equilibrium associated with the pair of payoff mechanisms (G, F R ) is characterized by all ordered pairs (x, pA ) ∈ X × R ⌊n/2⌋ for which
We denote the extended Nash equilibrium set associated with G and F R as E G,F R . Theorem 6: Suppose that EDM ν exhibits Nash stationarity, and is δ-dissipative with supply rate parameter Π. Let (G, F R ) be a pair of payoff mechanisms as described above, and satisfying
where
Then E G,F R is a globally asymptotically stable set, with respect to the difference equation (41).
Suppose the payoff dynamics are linearly related to the state dynamics, i.e.,
We now relate the static payoff evolution δp R k to the state dynamics δx k . By convexity of feasible flow variables z j , there exists a path between z A j,k and z A j,k+1 and a path between z R j,k and z R j,k+1 given by:
Integrating the link flow gradient with respect to each vehicle type along this line yields
with
We express the variables β j in matrix form as
which yields
where
These relationships are now used to present conditions for which Theorem 6 ensures the existence of a globally stabilizing controller. Theorem 7: Let the EDM ν be δ-dissipative and satisfy Nash stationarity. Assume RVs follow the static payoff mechanism
where
Assume the CAV populations follow a dynamic payoff of the form
Suppose that the population payoffs δp A k , δp R k satisfy:
Then, there exists a set of controllers (G A , G R ) ensuring global asymptotic stability of the extended Nash equilibrium set.
The proof is sketched here with additional details in the appendix. The analysis for δp A k , δp R k is used to express the supply rate matrix Π in terms of the strategy dynamics δx A k , δx R k . We denote the new supply rate matrix by Π. Thus, Theorem 6 is equivalent to showing that Π is negative semidefinite. We note Π depends on the following parameters:
The matrix Π can be decomposed such that the condition of Theorem 3 is equivalent to a linear matrix inequality (LMI) of the form:
where (•) H denotes the Hermitian transpose, G = G A G R , and P , Q, and Y are decomposition matrices. By a matrix result from [22], the LMI (59) holds if and only if the matrix Y is positive semidefinite with respect to the null spaces of Q and P . It can then be shown that the null space condition is satisfied if and only if (57) holds.
Given that the controller is not unique, it is natural to seek a particular control pair (G A , G R ) to enhance system performance. We propose minimizing the trace of the supply rate matrix Π as a heuristic measure to optimize the convergence rate. The control design is then formulated as the solution to the following optimization problem
The resulting optimization problem is convex, and the control design can be determined with a single offline calculation.
We apply our proposed controller and show stabilization for the mixed traffic case with non-uniform CAV headways. Tests were simulated on the Nguyen-Dupuis network [23] with 4 OD pairs, 19 links, and 25 paths. RVs obey the Smith protocol, where ϕ r j (p r j,k -p r i,k ) = max[p r j,k -p r i,k , 0]. The headway parameters are taken as h A j = 3, h R j = 1.5, and h C j = 0.6 for each link. The time-step τ is taken as 10 -5 . Demand volumes were chosen such that each OD pair has a uniform ratio of CAVs to RVs, and initial conditions were randomly generated. The supply rate terms M r are taken as in (20) with θ = 1 for each population, and the matrices BA , BR are respectively upper bounded by the maximum gradient of the link travel time function with respect to z A and z R . The convex optimization for control design (60) was solved using the CVX package in Matlab [24].
In the figures below, solid lines depict CAV flows for a particular path while dashed lines depict RV flows for a particular path. The legend is condensed for clarity. Figure 1 depicts strategy oscillations in the uncontrolled case when all vehicles select paths according to the static payoff defined by Φ. Figure 2 illustrates our controller successfully stabilizing the same path flows, where CAVs follow the proposed dynamic payoff mechanism and RVs adjust strategies according to the static payoff. Note that while only three path flows are illustrated for clarity, the behavior is similar for all strategies.
This paper presents a novel EDM which preserves state feasibility and satisfies a discrete-time notion of δdissipativity. Dissipativity techniques are then applied to present sufficient conditions under which global convergence to Nash equilibrium is achieved for homogenous traffic and for mixed-autonomy traffic with uniform CAV headway. We then consider a mixed traffic model in which the CAV headway depends on the vehicle type being followed and formulate existence conditions for a globally stabilizing feedback control law. The controller takes the form of a dynamic feedback mechanism governing CAV route choice and is optimized for convergence rate. Finally, we present numerical results showing that our controller ensures global asymptotic stability of the population strategies. APPENDIX Note that the proofs to Theorems 3, 5, and 6 are nearly identical to proofs for corresponding theorems given in continuous-time, in [25]. For brevity we refer the reader to this paper for details regarding these results.
k is ordered such that p r k is in decreasing order. (9) can then be expressed in vector form as: where
and where
The system can then be expressed by:
where the matrix I -τ Φ(p r k ) has all positive diagonal components and non-positive off-diagonal components. For all matrices of this class, components of the inverse are nonnegative. [26]. As such, if the components of x r k are nonnegative, then so are those of x r k+1 . Flow conservation follows by summing each population dynamic over all strategies and applying a change of index.
Consider that if the functions ϕ r i are monotonically nondecreasing, then
It follows that
where
By redefining summation indices, it follows that σ r (x r k+1 , p r k ) ≤ 0. Now, consider the term on the second line of (66). Using θ r j to bound the expression yields
where we use δ ij as the Kronecker delta to define
which yields
Applying the Gershgorin inequality shows that
which shows the system is δ-dissipative.
With the static payoff mechanism F (x k ), the payoff evolution δp k is given by
As the functions Φ j (z j,k ) are monotonically nondecreasing functions with maximum slopes γ j , it follows that for each z j,k , z j,k-1 ∈ R, there exists a secant slope α l,k ∈ [0, γ j ] such that
which yields
Bounding the secant slopes α j with maximum slope magnitudes γ j and evaluating the supply rate yields
It is now straightforward to show that Theorem 3 is satisfied if and only if
D. Proof of Theorem 7
Using equations ( 45) and (52), we simplify Π and analyze its Hermitian component
where we define the following due to space constraints
Splitting the above matrix into three terms by dependence on τ , dependence on both τ and G, and dependence on neither, and then applying the Schur complement formula yields
Now, after separating the above matrix by controllable and uncontrollable parts, it follows that the inequality on Π is equivalent to an LMI of the form
where
Now, by Lemma 7.2 of [22], it follows that the above LMI holds if and only if
where N P and N Q are the respective basis matrices for the null spaces of P and Q. It is straightforward to show that
which always holds. Now consider the condition on N P . Taking a Schur complement and simplifying shows that
which completes the proof.
Authorized licensed use limited to: University of Michigan Library. Downloaded on May 05,2026 at 01:54:02 UTC from IEEE Xplore. Restrictions apply.