betaFeedback

WorksMathematics

On the Nash equilibrium for a model of traffic flow

Abstract

The paper consider a conservation law model of traffic flow on a highway, where each driver chooses an optimal departure time τdτ^d, based on a departure cost φ(τd)φ(τ^d) and an arrival cost ψ(τa)ψ(τ^a). Nash equilibria are studied, where no driver can reduce his own cost by changing his departure time. The first results provide continuity estimates on the arrival time, depending on the distribution of departures. In terms of the L1{\bf L}^1 distance, we show that the corresponding map is Hölder continuous with exponent 1/21/2 in Lagrangian variables (labelling individual drivers), and Lipschitz continuous in Eulerian space variables. Concerning the regularity of the a Nash equilibrium, our results show that, when the total number of drivers is sufficiently large, a queue alway forms at the entrance of the highway and the corresponding traffic density contains a shock. Moreover, for any number of drivers (possibly small), we prove that for generic C2\mathcal C^2 cost functions φ,ψφ, ψ the Nash equilibrium solution still contains a shock. In the last section of the paper, assuming that the initial departure rate is not a Nash equilibrium, we consider an evolution equation for the departure rate, where each driver keeps changing his daily departure time in order to reduce his own cost. It is proved that this nonlocal integro-differential evolution equation admits a unique solution, globally in time. This provides some theoretical support to earlier numerical simulations, which indicated the dynamic instability of the Nash equilibrium and the possible existence of a chaotic attractor.

Introduction

Following a model introduced in [17] we consider a group of drivers that, on a daily basis, travel along a highway: starting from a residential neighborhood and reaching a workplace in the city center. As in the classic Lighthill-Whitham-Richards model of traffic flow [28, 29], the traffic density ρ(τ,ξ)\rho(\tau,\xi) on the highway will be described by the conservation law

ρτ+(ρv(ρ))ξ = 0.\begin{equation} \rho_\tau+\bigl(\rho v(\rho)\bigr)_\xi~=~0. \tag*{(1.1)} \end{equation}

Here τ\tau is time, ξ\xi is the space variable labeling points on the highway, and v(ρ)v(\rho) is a decreasing function describing how the velocity of cars depends on the traffic density.

Given a cost φ(τd)\varphi(\tau^{d}) for early departure and a cost ψ(τa)\psi(\tau^{a}) for late arrival, we consider the optimization problem for each driver, who needs to choose his departure time in order to minimize the sum of the two costs. Of course, the arrival time depends on the overall traffic density, and hence on the departure choices of all other drivers. We say that a departure rate is a Nash equilibrium if no driver can lower his total cost by choosing a different departure time. In this setting, the existence and uniqueness of the Nash equilibrium was proved in [17].

In the present paper, several new results in this direction will be given. In § 2 we introduce the basic definitions and assumptions, and review the construction of solutions to the conservation law via the Lax formula.

§ 3 and § 4 analyze the departure-to-arrival time map: τd↦τa\tau^d\mapsto\tau^a in Lagrangian and Eulerian variables, respectively. More precisely, let κ\kappa be the total number of drivers and let β∈[0,κ]\beta\in[0,\kappa] be the Lagrangian variable labeling one particular driver. In Theorem (?) we consider the map τd(β)↦τa(β)\tau^d(\beta)\mapsto\tau^a(\beta). By the Lax formula, this corresponds to a sup-convolution. A detailed analysis shows that the departure-to-arrival time map is Hölder continuous with exponent 1/21/2 as a map from L1([0,κ]){\bf L}^1\bigl([0,\kappa]\bigr) into itself. On the other hand, in Theorem (?) we consider a departure rate uˉ∈L1(R)\bar u\in {\bf L}^1(\mathbb{R}), so that ∫abuˉ(x)dx\int_a^b \bar u(x) dx yields the amount of drivers who depart at a time x∈[a,b]x\in [a,b]. Calling yuˉ(x)y^{\bar u}(x) the arrival time of a driver departing at time x∈Rx\in\mathbb{R}, we prove that the map uˉ(⋅)↦yuˉ(⋅)\bar u(\cdot)\mapsto y^{\bar u}(\cdot),

[departure rate]↦[arrival time function]\hbox{[departure rate]} \quad\mapsto\quad \hbox{[arrival time function]}

is Lipschitz continuous w.r.t. the L1{\bf L}^1 distance. The proof is first achieved for a class of piecewise constant departure rates, where a homotopy argument can be used. Then it is extended by continuity to all uˉ\bar u with bounded L1{\bf L}^1 norm and bounded support.

§ 5 reviews the concept of Nash equilibrium departure rate, and provides an explicit example where this departure rate is smooth. In § 6 we derive some properties of the Nash equilibrium, and show some numerical simulations.

The following § 7 and § 8 analyze the possible emergence of shocks in the Nash equilibrium solution. According to Proposition (?), if the total number of drivers is large enough, then a queue necessarily forms at the entrance of the highway. At the time when the queue is depleted, a shock appears in the solution. On the other hand, if the total number of drivers is sufficiently small, no queue is formed. However, this does not rule out the later emergence of shocks.

§ 8 begins by establishing the one-sided Lipschitz continuity of the Nash equilibrium departure rate. It turns out that this regularity is optimal. Indeed, as shown by Theorem (?), for generic departure and arrival cost functions φ,ψ∈C2\varphi, \psi\in {\mathcal C}^2 (i.e., ranging in an open dense set), the traffic pattern determined by the Nash equilibrium contains a shock, no matter how small is the total number of drivers.

Finally, in § 9 we consider an evolutionary model for the departure rate uˉ\bar u, originally introduced in [18]. Roughly speaking, assume that on day 1 the departure rate differs from the equilibrium. Then the following day some of the drivers may decide to change their departure time, seeking a lower individual cost. If this pattern is repeated day after day, will the departure rate oscillate chaotically or will it approach the unique Nash equilibrium? As a first step to understand this challenging problem, in Theorem 9.1 we prove the well posedness of the integro-differential evolution equation (9.2). Namely, for any initial departure rate uˉ∈L1∩L∞\bar u\in {\bf L}^1\cap {\bf L}^\infty with bounded support, a unique solution exists, depending continuously on the initial data in the L1{\bf L}^1 distance. This provides theoretical support to the simulations performed in [18], which suggest the dynamic instability of the Nash equilibrium and the possible existence of a chaotic attractor.

For an introduction to conservation laws we refer to [16, 21, 27]. More generally, for models of traffic flow also on networks we refer to [25]. See [23, 24] for an alternative perspective with engineering applications. Results on the structure of generic solutions to conservation laws can be found in [19, 30].

The basic model

Throughout the following we focus on the boundary value problem, where the incoming flux of cars at the beginning of the highway is assigned as a function of time (see Figure 1). This can be formulated as a Cauchy problem, by switching the roles of the variables. Together with ((1.1)) we thus consider the conservation law

ut+f(u)x = 0(t,x)∈[0,L]×R,\begin{equation} u_t +f(u)_x~=~0 \qquad\qquad (t,x) \in [0,L]\times \mathbb{R}, \tag*{(2.1)} \end{equation}

where xx corresponds to the previous time variable, while t∈[0,L]t\in [0,L] describes points along a highway of total length LL. The dependent variable u=u(t,x)u=u(t,x) denotes the flux of cars at time xx across the point tt on the highway (see Figure 1).

Figure 1. A departure rate and the corresponding arrival rate of cars traveling along a highway of length LL.

The function u↦f(u)=ρu\mapsto f(u) = \rho is a partial inverse of the smooth, concave function ρ↦ρv(ρ)=u\rho\mapsto \rho v(\rho) =u (see Figure 2). This is defined for u∈[0,M]u\in [0,M], where

M = max⁡ρ ρ v(ρ)M~=~\max_\rho \,\rho\, v(\rho)

is the maximum possible flux for the conservation law ((1.1)). Throughout the following we assume

  • The flux function f:[0,M]↦Rf:[0,M]\mapsto\mathbb{R} is continuous, increasing, and strictly convex. It is three times continuously differentiable on the half-open interval [0, M[ [0,\,M[\, and satisfies f(0)=0 ,f′(0) = 1v(0) > 0,f′(M−)=+∞,f′′(u)≥ω0>0for  0≤u<M, f(0)=0\,,\quad f'(0)\,=\, {1\over v(0)}\,>\,0,\quad f'(M-)=+\infty,\quad f''(u)\geq \omega_0 >0\quad \hbox{for}~~0\leq u<M, for some constant ω0\omega_0.

Figure 2. Left: the function ρ↦ρ v(ρ)\rho\mapsto \rho\,v(\rho) describing the flux of cars. Middle: the function ff, implicitly defined by f(ρv(ρ))=ρf(\rho v(\rho)) = \rho for u∈[0,M]u\in [0,M], and then extended according to ((2.15)). Right: the Legendre transform f∗f^* defined at ((2.16)).

The equation (2.1) is supplemented by an initial condition

u(0,x) = uˉ(x),\begin{equation} u(0,x)~=~\bar u(x), \tag*{(2.3)} \end{equation}

where uˉ(x)\bar u(x) determines the flux of cars arriving at the entrance of the highway at time xx.

Since the flux cannot exceed MM, if the boundary data happens to be uˉ(x)>M\bar u(x)>M a queue is formed at the entrance of the highway. Cars enter at rate MM until the queue is depleted. The actual solution is found by solving a Cauchy problem with an effective flux uˉe\bar u^e defined as follows (see Figure 3).

uˉe(x) ≐ {Mif∫yxuˉ(s) ds>M(x−y)for some y<x,uˉ(x)otherwise.\begin{equation} \bar u^e(x)~\doteq~\left\{\begin{array}{rl} M\quad &\displaystyle\hbox{if}\quad\int_y^x \bar u(s)\,ds > M(x-y)\quad\hbox{for some}~y<x,\\[2mm] \bar u(x)&\hbox{otherwise.}\end{array}\right. \tag*{(2.4)} \end{equation}

Notice that the first alternative occurs if the total amount of cars arriving at the entrance of the highway during the time interval [y,x][y,x] is larger than the maximum possible entering flux. This is when a queue is formed.

Figure 3. Here uˉ\bar u is a departure rate, i.e. the rate at which cars arrive at the entrance of the highway. Since the flux cannot exceed MM, the effective flux uˉe\bar u^e is a function constantly equal to MM on the interval [a,c][a,c]. A queue at the entrance of the highway is formed at time aa and depleted at time cc, so that the two shaded regions have equal areas.

Lemma. The map uˉ↦uˉe\bar u\mapsto \bar u^e defined at ((2.4)) is contractive w.r.t. the L1{\bf L}^1 distance.

Proof. 1. We claim that the map uˉ↦uˉe\bar u\mapsto \bar u^e is monotone:

uˉ(x)≤vˉ(x)  for all x∈R⟹uˉe(x)≤vˉe(x)  for a.e. x∈R.\begin{equation} \bar u(x)\leq \bar v(x) ~~\hbox{for all}~x\in\mathbb{R}\qquad\Longrightarrow\qquad \bar u^e(x)\leq \bar v^e(x) ~~\hbox{for a.e.~} x\in\mathbb{R}. \tag*{(2.5)} \end{equation}

Indeed, assume uˉ≤vˉ\bar u\leq \bar v. If

∫yxuˉ(s) ds > M(x−y)for some y<x,\begin{equation} \int_y^x \bar u(s)\, ds~>~M(x-y) \qquad\hbox{for some}~y<x, \tag*{(2.6)} \end{equation}

then

∫yxvˉ(s) ds > M(x−y)and henceuˉe(x) = vˉe(x) = M.\int_y^x \bar v(s)\, ds~>~M(x-y) \qquad\hbox{and hence}\qquad \bar u^e(x)\,=\, \bar v^e(x)\,=\,M.

On the other hand, if xx is a Lebesgue point of both uˉ\bar u and vˉ\bar v and ((2.6)) does not hold, then uˉe(x)=uˉ(x)≤M\bar u^e(x)=\bar u(x) \leq M. In this case,

uˉe(x) ≤ min⁡{uˉ(x),M} ≤ min⁡{vˉ(x),M} ≤ vˉe(x).\bar u^e(x)~\leq~\min\{ \bar u(x), M\}~\leq~\min\{ \bar v(x),M\}~\leq~\bar v^e(x).

2. Next, to prove L1{\bf L}^1-contractivity, consider the functions

w‾+(x) ≐ max⁡{uˉ(x),vˉ(x)},w‾−(x) ≐ min⁡{uˉ(x),vˉ(x)}.\overline w_+(x)\,\doteq\,\max\bigl\{ \bar u(x), \bar v(x)\bigr\},\qquad\qquad \overline w_-(x)\,\doteq\,\min\bigl\{ \bar u(x), \bar v(x)\bigr\}.

By comparison,

w‾−e(x) ≤ min⁡{uˉe(x),vˉe(x)} ≤ max⁡{uˉe(x),vˉe(x)} ≤ w‾+e(x)for all x∈R.\overline w_-^e(x)~\leq~\min\bigl\{ \bar u^e(x), \bar v^e(x)\bigr\}~\leq~\max\bigl\{ \bar u^e(x), \bar v^e(x)\bigr\}~\leq~\overline w_+^e(x)\qquad\quad \hbox{for all}~x\in\mathbb{R}.

Therefore

References

  1. [16]A.\,Bressan, \it Hyperbolic systems of conservation laws. The one dimensional Cauchy problem . Oxford University Press, 2000.
  2. [17]A.\,Bressan and K.\,Han, Optima and equilibria for a model of traffic flow. \it SIAM J. Math. Anal. \bf 43 (2011), 2384--2417.
  3. [18]A.\,Bressan, C.\,J.\,Liu, W.\,Shen and F.\,Yu, Variational analysis of Nash equilibria for a model of traffic flow, \it Quarterly Appl. Math. \bf 70 (2012), 495--515.
  4. [19]A.\,Bressan and K.\,T.\,Nguyen, Generic solutions to controlled balance laws, \it J. Hyperbolic Diff. Equat. \bf 23 (2026), 35--59.
  5. [20]V.\,Caselles, Scalar conservation laws and Hamilton–Jacobi equations in one-space variable \it Nonlinear Anal. TMA , \bf 18 (1992), 461--469.
  6. [21]G.\,M.\,Coclite, \it Scalar conservation laws. SpringerBriefs in Mathematics, Singapore, 2024.
  7. [22]J.\,Dieudonné, \it Foundations of Modern Analysis , Academic Press, New York, 1960.
  8. [23]Terry L.\,Friesz and Ke Han, The mathematical foundations of dynamic user equilibrium, \it Transp. Res. Part B: Method. \bf 126 , (2019), 309--328.
  9. [24]Terry L.\,Friesz and Ke Han, \it Dynamic network user Equilibrium. Complex Networks and Dynamic Systems series, Springer International Publishing, 2023.
  10. [25]M.\,Garavello and B.\,Piccoli, \it Traffic flow on networks. Conservation laws models. AIMS Series on Applied Mathematics, Springfield, Mo., 2006.
  11. [26]R.\,H.\,Martin Jr., \it Nonlinear Operators and Differential Equations in Banach Spaces. Wiley, New York, 1976.
  12. [27]H.\,Holden and N.\,Risebro, \it Front tracking for hyperbolic conservation laws. Second Edition. Springer-Verlag, Berlin, 2015.
  13. [28]M.\,Lighthill and G.\,Whitham, On kinematic waves. II. A theory of traffic flow on long crowded roads. \it Proceedings of the Royal Society of London: Series A, \bf 229 (1955), 317--345.
  14. [29]P.\,I.\,Richards, Shock waves on the highway, \it Oper. Res. \bf 4 (1956), 42-51.
  15. [30]D.\,Schaeffer, A regularity theorem for conservation laws, \it Advances in Math. \bf 11 (1973), 368--386.

Paper details

vlnc:W_y5hxzm7g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents