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} ρ τ + ( ρ v ( ρ ) ) ξ = 0. (1.1)
Here τ \tau τ is time, ξ \xi ξ is the space variable labeling points on the highway, and v ( ρ ) v(\rho) v ( ρ ) is a decreasing function describing how the velocity of cars depends on the traffic density.
Given a cost φ ( τ d ) \varphi(\tau^{d}) φ ( τ d ) for early departure and a cost ψ ( τ a ) \psi(\tau^{a}) ψ ( τ 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 τ d ↦ τ a in Lagrangian and Eulerian variables, respectively. More precisely, let κ \kappa κ be the total number of drivers and let β ∈ [ 0 , κ ] \beta\in[0,\kappa] β ∈ [ 0 , κ ] be the Lagrangian variable labeling one particular driver. In Theorem (?) we consider the map τ d ( β ) ↦ τ a ( β ) \tau^d(\beta)\mapsto\tau^a(\beta) τ d ( β ) ↦ τ a ( β ) . 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 / 2 1/2 1/2 as a map from L 1 ( [ 0 , κ ] ) {\bf L}^1\bigl([0,\kappa]\bigr) L 1 ( [ 0 , κ ] ) into itself. On the other hand, in Theorem (?) we consider a departure rate u ˉ ∈ L 1 ( R ) \bar u\in {\bf L}^1(\mathbb{R}) u ˉ ∈ L 1 ( R ) , so that ∫ a b u ˉ ( x ) d x \int_a^b \bar u(x) dx ∫ a b u ˉ ( x ) d x yields the amount of drivers who depart at a time x ∈ [ a , b ] x\in [a,b] x ∈ [ a , b ] . Calling y u ˉ ( x ) y^{\bar u}(x) y u ˉ ( x ) the arrival time of a driver departing at time x ∈ R x\in\mathbb{R} x ∈ R , we prove that the map u ˉ ( ⋅ ) ↦ y u ˉ ( ⋅ ) \bar u(\cdot)\mapsto y^{\bar u}(\cdot) u ˉ ( ⋅ ) ↦ y u ˉ ( ⋅ ) ,
[departure rate] ↦ [arrival time function] \hbox{[departure rate]} \quad\mapsto\quad \hbox{[arrival time function]} [departure rate] ↦ [arrival time function]
is Lipschitz continuous w.r.t. the L 1 {\bf L}^1 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 u ˉ with bounded L 1 {\bf L}^1 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 φ , ψ ∈ C 2 \varphi, \psi\in {\mathcal C}^2 φ , ψ ∈ 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 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 ˉ ∈ L 1 ∩ L ∞ \bar u\in {\bf L}^1\cap {\bf L}^\infty u ˉ ∈ L 1 ∩ L ∞ with bounded support, a unique solution exists, depending continuously on the initial data in the L 1 {\bf L}^1 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
u t + 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} u t + f ( u ) x = 0 ( t , x ) ∈ [ 0 , L ] × R , (2.1)
where x x x corresponds to the previous time variable, while t ∈ [ 0 , L ] t\in [0,L] t ∈ [ 0 , L ] describes points along a highway of total length L L L . The dependent variable u = u ( t , x ) u=u(t,x) u = u ( t , x ) denotes the flux of cars at time x x x across the point t t t on the highway (see Figure 1 ).
Figure 1. A departure rate and the corresponding arrival rate of cars traveling along a highway of length L L L .
The function u ↦ f ( u ) = ρ u\mapsto f(u) = \rho u ↦ f ( u ) = ρ is a partial inverse of the smooth, concave function ρ ↦ ρ v ( ρ ) = u \rho\mapsto \rho v(\rho) =u ρ ↦ ρ v ( ρ ) = u (see Figure 2 ). This is defined for u ∈ [ 0 , M ] u\in [0,M] u ∈ [ 0 , M ] , where
M = max ρ ρ v ( ρ ) M~=~\max_\rho \,\rho\, v(\rho) M = ρ max ρ v ( ρ )
is the maximum possible flux for the conservation law ((1.1) ). Throughout the following we assume
The flux function f : [ 0 , M ] ↦ R f:[0,M]\mapsto\mathbb{R} f : [ 0 , M ] ↦ R is continuous, increasing, and strictly convex. It is three times continuously differentiable on the half-open interval [ 0 , M [ [0,\,M[\, [ 0 , M [ and satisfies f ( 0 ) = 0 , f ′ ( 0 ) = 1 v ( 0 ) > 0 , f ′ ( M − ) = + ∞ , f ′ ′ ( u ) ≥ ω 0 > 0 for 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,
f ( 0 ) = 0 , f ′ ( 0 ) = v ( 0 ) 1 > 0 , f ′ ( M − ) = + ∞ , f ′′ ( u ) ≥ ω 0 > 0 for 0 ≤ u < M , for some constant ω 0 \omega_0 ω 0 .
Figure 2. Left: the function ρ ↦ ρ v ( ρ ) \rho\mapsto
\rho\,v(\rho) ρ ↦ ρ v ( ρ ) describing the flux of cars. Middle: the function f f f , implicitly defined by f ( ρ v ( ρ ) ) = ρ f(\rho v(\rho)) = \rho f ( ρ v ( ρ )) = ρ for u ∈ [ 0 , M ] u\in [0,M] u ∈ [ 0 , M ] , and then extended according to ((2.15) ). Right: the Legendre transform f ∗ 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} u ( 0 , x ) = u ˉ ( x ) , (2.3)
where u ˉ ( x ) \bar u(x) u ˉ ( x ) determines the flux of cars arriving at the entrance of the highway at time x x x .
Since the flux cannot exceed M M M , if the boundary data happens to be u ˉ ( x ) > M \bar u(x)>M u ˉ ( x ) > M a queue is formed at the entrance of the highway. Cars enter at rate M M M until the queue is depleted. The actual solution is found by solving a Cauchy problem with an effective flux u ˉ e \bar u^e u ˉ e defined as follows (see Figure 3 ).
u ˉ e ( x ) ≐ { M if ∫ y x u ˉ ( s ) d s > 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} u ˉ e ( x ) ≐ ⎩ ⎨ ⎧ M u ˉ ( x ) if ∫ y x u ˉ ( s ) d s > M ( x − y ) for some y < x , otherwise. (2.4)
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] [ y , x ] is larger than the maximum possible entering flux. This is when a queue is formed.
Figure 3. Here u ˉ \bar u u ˉ is a departure rate, i.e. the rate at which cars arrive at the entrance of the highway. Since the flux cannot exceed M M M , the effective flux u ˉ e \bar u^e u ˉ e is a function constantly equal to M M M on the interval [ a , c ] [a,c] [ a , c ] . A queue at the entrance of the highway is formed at time a a a and depleted at time c c c , so that the two shaded regions have equal areas.
Lemma. The map u ˉ ↦ u ˉ e \bar u\mapsto \bar u^e u ˉ ↦ u ˉ e defined at ((2.4) ) is contractive w.r.t. the L 1 {\bf L}^1 L 1 distance.
Proof. 1. We claim that the map u ˉ ↦ u ˉ e \bar u\mapsto \bar u^e u ˉ ↦ 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} u ˉ ( x ) ≤ v ˉ ( x ) for all x ∈ R ⟹ u ˉ e ( x ) ≤ v ˉ e ( x ) for a.e. x ∈ R . (2.5)
Indeed, assume u ˉ ≤ v ˉ \bar u\leq \bar v u ˉ ≤ v ˉ . If
∫ y x u ˉ ( s ) d s > 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} ∫ y x u ˉ ( s ) d s > M ( x − y ) for some y < x , (2.6)
then
∫ y x v ˉ ( s ) d s > M ( x − y ) and hence u ˉ 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. ∫ y x v ˉ ( s ) d s > M ( x − y ) and hence u ˉ e ( x ) = v ˉ e ( x ) = M .
On the other hand, if x x x is a Lebesgue point of both u ˉ \bar u u ˉ and v ˉ \bar v v ˉ and ((2.6) ) does not hold, then u ˉ e ( x ) = u ˉ ( x ) ≤ M \bar u^e(x)=\bar u(x)
\leq M u ˉ e ( x ) = u ˉ ( x ) ≤ 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). u ˉ e ( x ) ≤ min { u ˉ ( x ) , M } ≤ min { v ˉ ( x ) , M } ≤ v ˉ e ( x ) .
2. Next, to prove L 1 {\bf L}^1 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\}. w + ( x ) ≐ max { u ˉ ( x ) , v ˉ ( x ) } , w − ( x ) ≐ min { u ˉ ( x ) , v ˉ ( x ) } .
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}. w − e ( x ) ≤ min { u ˉ e ( x ) , v ˉ e ( x ) } ≤ max { u ˉ e ( x ) , v ˉ e ( x ) } ≤ w + e ( x ) for all x ∈ R .
Therefore
∫ − ∞ + ∞ ∣ u ˉ e ( x ) − v ˉ e ( x ) ∣ d x ≤ ∫ − ∞ + ∞ ( w ‾ + e ( x ) − w ‾ − e ( x ) ) d x = ∫ − ∞ + ∞ ( w ‾ + ( x ) d x − w ‾ − ( x ) ) d x = ∫ − ∞ + ∞ ∣ u ˉ ( x ) − v ˉ ( x ) ∣ d x . \begin{array}{l} \displaystyle\int_{-\infty}^{+\infty} \Big|\bar u^e(x) - \bar v^e(x)\Big|\, dx ~\leq~\int_{-\infty}^{+\infty} \Big(\overline w^e_+(x) - \overline w^e_-(x)\Big)\, dx \\[4mm]
\displaystyle\quad =~
%\int_{-\infty}^{+\infty} \ov w_+(x) \, dx -\int_{-\infty}^{+\infty} \ov w_-(x) \, dx\\[4mm]
\displaystyle\int_{-\infty}^{+\infty} \Big(\overline w_+(x) \, dx -\overline w_-(x)\Big) \, dx~=~ \int_{-\infty}^{+\infty} \Big|
\bar u(x) -\bar v(x)\Big| \, dx\,.
\end{array} ∫ − ∞ + ∞ u ˉ e ( x ) − v ˉ e ( x ) d x ≤ ∫ − ∞ + ∞ ( w + e ( x ) − w − e ( x ) ) d x = ∫ − ∞ + ∞ ( w + ( x ) d x − w − ( x ) ) d x = ∫ − ∞ + ∞ u ˉ ( x ) − v ˉ ( x ) d x .
For ( t , x ) ∈ [ 0 , L ] × R (t,x)\in [0,L]\times \mathbb{R} ( t , x ) ∈ [ 0 , L ] × R , let u = u ( t , x ) u=u(t,x) u = u ( t , x ) be the entropy weak solution of the conservation law ((2.1) ), with initial data
u ( 0 , x ) = u ˉ e ( x ) , \begin{equation}
u(0,x)~=~\bar u^e(x), \tag*{(2.7)}
\end{equation} u ( 0 , x ) = u ˉ e ( x ) , (2.7)
where the effective incoming flux was defined at ((2.4) ). We denote by
κ = ∫ u ˉ ( x ) d x = ∫ u ˉ e ( x ) d x \kappa~=~\int \bar u(x)\, dx~=~\int \bar u^e(x)\, dx κ = ∫ u ˉ ( x ) d x = ∫ u ˉ e ( x ) d x
the total number of departing drivers. The Lagrangian variable β ∈ [ 0 , κ ] \beta\in [0,\kappa] β ∈ [ 0 , κ ] will be used to label one particular driver. For a.e. β ∈ [ 0 , κ ] \beta\in [0,\kappa] β ∈ [ 0 , κ ] the departure time and the arrival time of this driver are determined by
x d ( β ) = inf { x ; ∫ − ∞ x u ˉ ( s ) d s = β } , x a ( β ) = inf { x ; ∫ − ∞ x u ( L , s ) d s = β } . \begin{equation}
x^d(\beta) ~=~ \inf \left\{ x\,;~\int_{-\infty} ^x \bar u(s)\, ds =\beta\right\},\qquad\qquad
x^a(\beta) ~=~ \inf \left\{ x\,;~\int_{-\infty} ^x u(L,s)\, ds =\beta\right\}. \tag*{(2.8)}
\end{equation} x d ( β ) = inf { x ; ∫ − ∞ x u ˉ ( s ) d s = β } , x a ( β ) = inf { x ; ∫ − ∞ x u ( L , s ) d s = β } . (2.8)
The difference
ℓ ( β ) = x a ( β ) − x d ( β ) \ell(\beta)~=~x^a(\beta)-x^d(\beta) ℓ ( β ) = x a ( β ) − x d ( β )
is the duration of the journey of driver β \beta β . For a given κ \kappa κ , we have the a priori bounds
ℓ 0 ≤ ℓ ( β ) ≤ ℓ m a x , \begin{equation}
\ell_0~\leq~\ell(\beta)~\leq~\ell_{max}\,, \tag*{(2.9)}
\end{equation} ℓ 0 ≤ ℓ ( β ) ≤ ℓ ma x , (2.9)
Here ℓ 0 \ell_0 ℓ 0 is the time needed to cover the distance L L L at maximum speed, i.e. when ρ = 0 \rho=0 ρ = 0 and the road is empty. Namely,
ℓ 0 ≐ [length of the road] [maximum speed] = L v ( 0 ) = L f ′ ( 0 ) . \begin{equation}
\ell_0~\doteq~ {\hbox{[length of the road]}\over \hbox{[maximum speed]}}~=~{L \over v(0)}~=~L f'(0). \tag*{(2.10)}
\end{equation} ℓ 0 ≐ [maximum speed] [length of the road] = v ( 0 ) L = L f ′ ( 0 ) . (2.10)
To compute ℓ m a x \ell_{max} ℓ ma x , consider the worst possible scenario, where all drivers start their journey at the same time, say at x = 0 x=0 x = 0 . Then a queue of size κ \kappa κ is instantly formed at the entrance of the highway. The corresponding effective flux is
u ˉ e ( x ) = { M if x ∈ [ 0 , κ / M ] , 0 otherwise. \begin{equation}
\bar u^e(x)~=~\left\{\begin{array}{cl} M\quad &\hbox{if} ~~x\in [0, \kappa/M],\\[2mm]
0\quad &\hbox{otherwise.}\end{array}\right. \tag*{(2.11)}
\end{equation} u ˉ e ( x ) = { M 0 if x ∈ [ 0 , κ / M ] , otherwise. (2.11)
With reference to Figure 2 , left, let ρ ∗ \rho^* ρ ∗ be the density of cars corresponding to the maximum flux. We then have the simple estimate
ℓ m a x ≤ κ M + L v ( ρ ∗ ) . \begin{equation}
\ell_{max}~\leq~{\kappa\over M} + {L\over v(\rho^*)}\,. \tag*{(2.12)}
\end{equation} ℓ ma x ≤ M κ + v ( ρ ∗ ) L . (2.12)
Indeed, the last car needs to wait until time x = κ / M x=\kappa/M x = κ / M to clear the queue. After it starts moving, since the traffic density is ρ ≤ ρ ∗ \rho\leq \rho^* ρ ≤ ρ ∗ , the velocity is ≥ v ( ρ ∗ ) \geq v(\rho^*) ≥ v ( ρ ∗ ) . Hence any car needs at most time L / v ( ρ ∗ ) L/v(\rho^*) L / v ( ρ ∗ ) to reach the end of the highway.
Given a departure distribution u ˉ \bar u u ˉ , the arrival time y u ˉ ( x ) y^{\bar u}(x) y u ˉ ( x ) of a driver departing at time x ∈ R x\in\mathbb{R} x ∈ R can be determined as
y u ˉ ( x ) ≐ inf { y ≥ x + ℓ 0 ; ∫ − ∞ y u ( L , ξ ) d ξ ≥ ∫ − ∞ x u ˉ ( ξ ) d ξ } . \begin{equation}
y^{\bar u}(x)~\doteq~\inf\Big\{ y\geq x+\ell_0\,;~~\int_{-\infty}^y u(L,\xi)\, d\xi~\geq~\int_{-\infty}^x \bar u(\xi)\, d\xi\Big\}. \tag*{(2.13)}
\end{equation} y u ˉ ( x ) ≐ inf { y ≥ x + ℓ 0 ; ∫ − ∞ y u ( L , ξ ) d ξ ≥ ∫ − ∞ x u ˉ ( ξ ) d ξ } . (2.13)
Notice that the expression ((2.13) ) is meaningful also if u ˉ ( x ) = 0 \bar u(x)=0 u ˉ ( x ) = 0 . If the road is empty, the arrival time is x + ℓ 0 x+\ell_0 x + ℓ 0 . Otherwise, the arrival time is the earliest time when all cars starting before time x x x arrive to destination. The corresponding duration of the journey is
ℓ u ˉ ( x ) ≐ y u ˉ ( x ) − x . \begin{equation}
\ell^{\bar u}(x)~\doteq~y^{\bar u}(x)-x. \tag*{(2.14)}
\end{equation} ℓ u ˉ ( x ) ≐ y u ˉ ( x ) − x . (2.14)
As shown in Figure 2 , center, it is convenient to extend f f f to a function f : R ↦ R ∪ { + ∞ } f:\mathbb{R}\mapsto \mathbb{R}\cup \{+\infty\} f : R ↦ R ∪ { + ∞ } by setting
f ( u ) ≐ { f ′ ( 0 + ) u if u < 0 , + ∞ if u > M . \begin{equation}
f(u) ~\doteq~\left\{ \begin{array}{cl} f'(0+) u
\qquad &\hbox{if}~~u<0,
\cr
+\infty \qquad &\hbox{if}~~u>M.\end{array}\right. \tag*{(2.15)}
\end{equation} f ( u ) ≐ { f ′ ( 0 + ) u + ∞ if u < 0 , if u > M . (2.15)
The Legendre transform of this extended flux function (see Figure 2 , right) will be denoted by
f ∗ ( p ) ≐ max u { p u − f ( u ) } . \begin{equation}
f^*(p)~\doteq~ \max_u \bigl\{ pu-f(u)\bigr\}. \tag*{(2.16)}
\end{equation} f ∗ ( p ) ≐ u max { p u − f ( u ) } . (2.16)
Since f f f is convex, we can write
f ∗ ( p ) = p u ( p ) − f ( u ( p ) ) , \begin{equation}
f^*(p)~=~p u(p) - f\bigl(u(p)\bigr), \tag*{(2.17)}
\end{equation} f ∗ ( p ) = p u ( p ) − f ( u ( p ) ) , (2.17)
where u ( p ) u(p) u ( p ) is implicitly defined by
f ′ ( u ( p ) ) = p . \begin{equation}
f'\bigl(u(p)\bigr)~=~p. \tag*{(2.18)}
\end{equation} f ′ ( u ( p ) ) = p . (2.18)
In turn, this implies
∂ f ∗ ∂ p = u ( p ) + p ∂ u ∂ p − f ′ ( u ( p ) ) ∂ u ∂ p = u ( p ) , \begin{equation}
{\partial f^*\over \partial p} ~=~u(p) +p\,{\partial u\over\partial p} - f'\bigl(u(p)\bigr) {\partial u\over\partial p} ~=~u(p), \tag*{(2.19)}
\end{equation} ∂ p ∂ f ∗ = u ( p ) + p ∂ p ∂ u − f ′ ( u ( p ) ) ∂ p ∂ u = u ( p ) , (2.19)
∂ 2 ∂ p 2 f ∗ ( p ) = ∂ ∂ p u ( p ) = 1 f ′ ′ ( u ( p ) ) . \begin{equation}
{\partial^2 \over \partial p^2} f^*(p)~=~{\partial \over\partial p} u(p)~=~{1\over f''\bigl(u(p)\bigr)}. \tag*{(2.20)}
\end{equation} ∂ p 2 ∂ 2 f ∗ ( p ) = ∂ p ∂ u ( p ) = f ′′ ( u ( p ) ) 1 . (2.20)
Note that the last identity is obtained differentiating ((2.18) ) and observing that
f ′ ′ ( u ( p ) ) ⋅ ∂ u ∂ p = 1. f''(u(p))~\cdot {\partial u\over\partial p} ~=~1. f ′′ ( u ( p )) ⋅ ∂ p ∂ u = 1.
Next, consider the integrated function
U ( t , x ) ≐ ∫ − ∞ x u ( t , s ) d s . \begin{equation}
U(t,x)~\doteq~\int_{-\infty}^x u(t,s)\, ds\,. \tag*{(2.21)}
\end{equation} U ( t , x ) ≐ ∫ − ∞ x u ( t , s ) d s . (2.21)
By definition, U ( t , x ) U(t,x) U ( t , x ) describes the total flux through the point t t t on the highway during the time interval ] − ∞ , x ] ]-\infty, x] ] − ∞ , x ] . Equivalently, this is the total number of cars that have crossed the point t ∈ [ 0 , L ] t\in [0,L] t ∈ [ 0 , L ] before time x x x .
Integrating w.r.t. x x x , the conservation law ((2.1) ) can be equivalently written as a Hamilton-Jacobi equation [20 ]
U t + f ( U x ) = 0 , \begin{equation}
U_t+ f(U_x)~=~0\,, \tag*{(2.22)}
\end{equation} U t + f ( U x ) = 0 , (2.22)
with initial data
U ( 0 , x ) = U ‾ ( x ) ≐ ∫ − ∞ x u ˉ ( y ) d y . \begin{equation}
U(0,x)~=~\overline U(x)~\doteq~\int_{-\infty}^x \bar u(y)\, dy. \tag*{(2.23)}
\end{equation} U ( 0 , x ) = U ( x ) ≐ ∫ − ∞ x u ˉ ( y ) d y . (2.23)
It is well known that U = U ( t , x ) U=U(t,x) U = U ( t , x ) corresponds to the value function for a variational problem. This fact is exploited by the Lax formula:
U ( t , x ) = inf { t f ∗ ( x − z t ) + U ‾ ( z ) ; z ∈ R } . \begin{equation}
U(t,x)~=~\inf\, \left\{
t\,f^*\left(\frac{x-z}{t}\right)+ \overline U(z)~~;~~~z\in\mathbb{R}
\right\}. \tag*{(2.24)}
\end{equation} U ( t , x ) = inf { t f ∗ ( t x − z ) + U ( z ) ; z ∈ R } . (2.24)
Knowing U U U , one can then recover the density u ( t , x ) = U x ( t , x ) u(t,x)=U_x(t,x) u ( t , x ) = U x ( t , x ) at a.e. point.
Figure 4. Computing the arrival time y ( x ) y(x) y ( x ) of a car that departs at time x x x . Here y ( x ) y(x) y ( x ) and z ( x ) z(x) z ( x ) are determined by the conditions in ((2.31) ).
Based on the Lax formula, there is an appealing way to construct the arrival time of each driver, shown in Figure 4 . Given the departure distribution U ‾ ( ⋅ ) \overline U(\cdot) U ( ⋅ ) as in ((2.23) ), let β ∈ [ 0 , κ ] \beta\in [0, \kappa] β ∈ [ 0 , κ ] label a particular driver. The departure time of this driver is
x d ( β ) = min { x ; U ‾ ( x ) ≥ β } , \begin{equation}
x^d(\beta)~=~\min\bigl\{ x\,;~~\overline U(x)\geq \beta\bigr\}, \tag*{(2.25)}
\end{equation} x d ( β ) = min { x ; U ( x ) ≥ β } , (2.25)
while the arrival time is
x a ( β ) = min { y ; U ( L , y ) ≥ β } . \begin{equation}
x^a(\beta)~=~\min\bigl\{ y\,;~~ U(L,y)\geq \beta\bigr\}. \tag*{(2.26)}
\end{equation} x a ( β ) = min { y ; U ( L , y ) ≥ β } . (2.26)
Notice that
x a ( β ) ≤ y ⟺ U ( L , y ) ≥ β . x^a(\beta)\leq y\qquad\Longleftrightarrow\qquad U(L,y)\geq \beta. x a ( β ) ≤ y ⟺ U ( L , y ) ≥ β .
In other words: driver β \beta β arrives at some time ≤ y \leq y ≤ y if and only if at time y y y the number of drivers that have crossed the finish line at L L L is ≥ β \geq \beta ≥ β . Using ((2.24) ) with t = L t=L t = L , we find that this is true iff
β ≤ U ( L , y ) = inf { L f ∗ ( y − z L ) + U ‾ ( z ) ; z ∈ R } , \begin{equation}
\beta~\leq~U(L,y)~=~\inf\, \left\{
L\,f^*\left(\frac{y-z}{L}\right)+ \overline U(z)~~;~~~z\in\mathbb{R}
\right\}, \tag*{(2.27)}
\end{equation} β ≤ U ( L , y ) = inf { L f ∗ ( L y − z ) + U ( z ) ; z ∈ R } , (2.27)
where f ∗ f^* f ∗ is the Legendre transform of f f f . Hence the arrival time is
x a ( β ) = inf { y ; L f ∗ ( y − z L ) + U ‾ ( z ) ≥ β for all z ∈ R } = inf { y ; β − L f ∗ ( y − z L ) ≤ U ‾ ( z ) for all z ∈ R } . \begin{equation}
\begin{array}{rl}
x^a(\beta)&\displaystyle=~\inf\left\{ y\,;~~L\,f^*\left(\frac{y-z}{L}\right)+ \overline U(z)\geq\beta\quad\hbox{for all}~z\in\mathbb{R}\right\}
\\[4mm]
&\displaystyle=~\inf \left\{ y\,;~~\beta - L\,f^*\left(\frac{y-z}{L}\right)\leq \overline U(z)\quad\hbox{for all}~z\in\mathbb{R}\right\}
.\end{array} \tag*{(2.28)}
\end{equation} x a ( β ) = inf { y ; L f ∗ ( L y − z ) + U ( z ) ≥ β for all z ∈ R } = inf { y ; β − L f ∗ ( L y − z ) ≤ U ( z ) for all z ∈ R } . (2.28)
Consider the function (see again Figure 4 )
h ( s ) ≐ − L f ∗ ( − s / L ) . \begin{equation}
h(s)~\doteq~- Lf^*(-s/L). \tag*{(2.29)}
\end{equation} h ( s ) ≐ − L f ∗ ( − s / L ) . (2.29)
Note that
h ( s ) ↗ 0 as s ↗ − ℓ 0 ≐ − L f ′ ( 0 ) . h(s)\nearrow 0\qquad \hbox{as}\qquad s\nearrow -\ell_0~\doteq~-L f'(0). h ( s ) ↗ 0 as s ↗ − ℓ 0 ≐ − L f ′ ( 0 ) .
We can now write ((2.28) ) as
x a ( β ) = inf { y ; β + h ( z − y ) ≤ U ‾ ( z ) for every z ∈ R } . \begin{equation}
x^a(\beta)~=~\inf\Big\{ y\,;~\beta + h(z-y)\leq \overline U(z)~~\hbox{for every} ~z\in\mathbb{R}\Big\}. \tag*{(2.30)}
\end{equation} x a ( β ) = inf { y ; β + h ( z − y ) ≤ U ( z ) for every z ∈ R } . (2.30)
As shown in Figure 4 , one needs to shift the graph of the function x ↦ β + h ( x ) x\mapsto \beta+h(x) x ↦ β + h ( x ) horizontally, until it lies entirely below the graph of U ‾ \overline U U . In the figure, the size of this shift yields precisely the arrival time y ( x ) = x a ( β ) y(x)=x^a(\beta) y ( x ) = x a ( β ) .
In the smooth case, if x = x d ( β ) x=x^d(\beta) x = x d ( β ) is the departure time of driver β \beta β , then the arrival time y ( x ) = x a ( β ) y(x)=x^a(\beta) y ( x ) = x a ( β ) and the point z ( x ) z(x) z ( x ) , where equality in ((2.30) ) is achieved, are determined by the two identities (necessary conditions for minimality)
β + h ( z − y ) = U ‾ ( z ) , h ′ ( z − y ) = U ‾ ′ ( z ) . \begin{equation}
\beta + h(z-y) \,=\,\overline U(z),\qquad\qquad h'(z-y) \,=\,\overline U'(z). \tag*{(2.31)}
\end{equation} β + h ( z − y ) = U ( z ) , h ′ ( z − y ) = U ′ ( z ) . (2.31)
For future applications, we shall need to compute the arrival time y u ˉ ( x ) y^{\bar u}(x) y u ˉ ( x ) of a driver departing at time x x x , also in the case where u ˉ ( x ) = 0 \bar u(x)=0 u ˉ ( x ) = 0 . This is achieved by the formula
y u ˉ ( x ) = inf { y ≥ x + ℓ 0 ; U ‾ ( x ) + h ( z − y ) ≤ U ‾ ( z ) for every z ≤ x } . \begin{equation}
y^{\bar u}(x)~=~\inf\Big\{ y\geq x+\ell_0\,;~~\overline U(x) + h(z-y)\leq \overline U(z)~~
\hbox{for every} ~z\le x\Big\}. \tag*{(2.32)}
\end{equation} y u ˉ ( x ) = inf { y ≥ x + ℓ 0 ; U ( x ) + h ( z − y ) ≤ U ( z ) for every z ≤ x } . (2.32)
Figure 5. The functions h h h and h ∗ h^* h ∗ defined at ((2.29) ) and ((2.33) ) respectively.
Hölder continuous dependence of the arrival time function in the Lagrangian formulation
As before, we let κ \kappa κ be the total number of drivers, while L L L is the length of the road. The Lagrangian variable β ∈ [ 0 , κ ] \beta\in [0, \kappa] β ∈ [ 0 , κ ] labels one particular driver. Calling x d ( β ) x^d(\beta) x d ( β ) and x a ( β ) x^a(\beta) x a ( β ) respectively the departure time and the arrival time of driver β \beta β , we wish to understand the continuity properties of the map x d ( ⋅ ) ↦ x a ( ⋅ ) x^d(\cdot)\mapsto x^a(\cdot) x d ( ⋅ ) ↦ x a ( ⋅ ) , as a map from L 1 ( [ 0 , κ ] ) {\bf L}^1\bigl([0,\kappa]\bigr) L 1 ( [ 0 , κ ] ) into itself.
Theorem. Let the flux function f f f satisfy (A1). There exists a constant C ~ \widetilde C C , depending only on f f f and on the constants κ , L , B > 0 \kappa, L,B>0 κ , L , B > 0 , such that the following holds.
For any two nondecreasing departure time functions x 1 d , x 2 d : [ 0 , κ ] ↦ [ − B , B ] x_1^d,x_2^d:[0,\kappa]\mapsto [-B,B] x 1 d , x 2 d : [ 0 , κ ] ↦ [ − B , B ] , the arrival times x 1 a , x 2 a x^a_1,x_2^a x 1 a , x 2 a satisfy ∥ x 1 a − x 2 a ∥ L 1 ≤ C ~ ∥ x 1 d − x 2 d ∥ L 1 1 / 2 .
\|x^a_1-x^a_2\|_{{\bf L}^1}~ \le~ \widetilde C \|x^d_1-x^d_2\|_{{\bf L}^1}^{1/2}.
∥ x 1 a − x 2 a ∥ L 1 ≤ C ∥ x 1 d − x 2 d ∥ L 1 1/2 .
In view of the formula ((2.35) ) for the arrival time function, we first prove a general lemma on the Hölder continuity of the sup-convolution operator.
Given constants κ , B \kappa, B κ , B , let F {\mathcal F} F be the family of all nondecreasing functions ϕ : [ 0 , κ ] ↦ [ − B , B ] \phi:[0,\kappa]\mapsto [-B,B] ϕ : [ 0 , κ ] ↦ [ − B , B ] . For ϕ ∈ F \phi\in {\mathcal F} ϕ ∈ F , consider the function ψ = Ψ ( ϕ ) \psi = \Psi(\phi) ψ = Ψ ( ϕ ) , defined by
ψ ( x ) = sup 0 ≤ y ≤ x ϕ ( y ) + ℓ ( x − y ) . \begin{equation}
\psi(x)~=~\sup_{0\leq y\leq x} \phi(y)+\ell(x-y). \tag*{(3.2)}
\end{equation} ψ ( x ) = 0 ≤ y ≤ x sup ϕ ( y ) + ℓ ( x − y ) . (3.2)
The following properties follow immediately from the definition:
1 - Comparison:
ϕ 1 ≤ ϕ 2 ⟹ ψ 1 ≤ ψ 2 . \begin{equation}
\phi_1~\leq~\phi_2\qquad\Longrightarrow\qquad\psi_1\leq\psi_2\,. \tag*{(3.3)}
\end{equation} ϕ 1 ≤ ϕ 2 ⟹ ψ 1 ≤ ψ 2 . (3.3)
2 - Contractivity in L ∞ ( [ 0 , κ ] ) {\bf L}^\infty\bigl([0,\kappa]\bigr) L ∞ ( [ 0 , κ ] ) :
∥ ψ 1 − ψ 2 ∥ L ∞ ≤ ∥ ϕ 1 − ϕ 2 ∥ L ∞ . \begin{equation}
\|\psi_1-\psi_2\|_{{\bf L}^\infty}~\leq~\|\phi_1-\phi_2\|_{{\bf L}^\infty}\,. \tag*{(3.4)}
\end{equation} ∥ ψ 1 − ψ 2 ∥ L ∞ ≤ ∥ ϕ 1 − ϕ 2 ∥ L ∞ . (3.4)
Next, we seek continuity estimate of the map Ψ : ϕ ↦ ψ \Psi:\phi\mapsto \psi Ψ : ϕ ↦ ψ in terms of the L 1 {\bf L}^1 L 1 distance.
Example. To see that the map ϕ ↦ ψ \phi\mapsto\psi ϕ ↦ ψ may not be Lipschitz continuous from L 1 ( [ 0 , κ ] ) {\bf L}^1\bigl([0,\kappa]\bigr) L 1 ( [ 0 , κ ] ) into itself, take κ = 1 \kappa=1 κ = 1 , ℓ ( s ) = s \ell(s) = \sqrt s ℓ ( s ) = s . As shown in Figure 6 , consider the two functions ϕ 1 ( x ) = 0 , ϕ 2 ( x ) ≐ { − ε if x ∈ [ 0 , 2 ε [ , 0 if x ∈ [ 2 ε , 1 ] .
\phi_1(x)\,=\,0,\qquad\phi_{2}(x)~\doteq~\left\{\begin{array}{cl}
-\varepsilon\quad &\hbox{if}~~x\in [0, 2\varepsilon[\,,\\[1mm]
0\quad &\hbox{if}~~x\in [2\varepsilon,1].
\end{array}\right.
ϕ 1 ( x ) = 0 , ϕ 2 ( x ) ≐ { − ε 0 if x ∈ [ 0 , 2 ε [ , if x ∈ [ 2 ε , 1 ] . We then have ψ 1 ( x ) = x , ψ 2 ( x ) = max { x − ε , x − 2 ε } = x − ε for all x ∈ [ 0 , 1 ] . \psi_1(x)\,=\,\sqrt x\,,~~\qquad \psi_2(x)\,=\, \max\bigl\{ \sqrt x-\varepsilon, ~\sqrt{x-2\varepsilon}\bigr\}\,=\,\sqrt x - \varepsilon
\qquad \hbox{for all}~x\in [0,1]. ψ 1 ( x ) = x , ψ 2 ( x ) = max { x − ε , x − 2 ε } = x − ε for all x ∈ [ 0 , 1 ] . Hence ∥ ϕ 1 − ϕ 2 ∥ L 1 = 2 ε 2 , ∥ ψ 1 − ψ 2 ∥ L 1 = ε . \|\phi_1-\phi_2\|_{{\bf L}^1}\,=\,2\varepsilon^2,\qquad\qquad\|\psi_1-\psi_2\|_{{\bf L}^1}\,=~\varepsilon. ∥ ϕ 1 − ϕ 2 ∥ L 1 = 2 ε 2 , ∥ ψ 1 − ψ 2 ∥ L 1 = ε .
Figure 6. The functions ϕ 1 = 0 , ϕ 2 \phi_1=0, \phi_2 ϕ 1 = 0 , ϕ 2 and ψ 1 , ψ 2 \psi_1,\psi_2 ψ 1 , ψ 2 , considered in Example (?) .
The following lemma shows the map Ψ : ϕ ↦ ψ \Psi:\phi\mapsto \psi Ψ : ϕ ↦ ψ is in fact Hölder continuous with exponent α = 1 / 2 \alpha=1/2 α = 1/2 .
Lemma. Let κ , A , B > 0 \kappa,A,B>0 κ , A , B > 0 and ℓ : [ 0 , κ ] ↦ [ 0 , A ] \ell:[0,\kappa] \mapsto [0,A] ℓ : [ 0 , κ ] ↦ [ 0 , A ] and ϕ 1 , ϕ 2 : [ 0 , κ ] ↦ [ − B , B ] \phi_1,\phi_2:[0,\kappa]\mapsto[-B,B] ϕ 1 , ϕ 2 : [ 0 , κ ] ↦ [ − B , B ] be nondecreasing functions. Define the corresponding sup-convolutions ψ 1 , ψ 2 \psi_1,\psi_2 ψ 1 , ψ 2 as in ((3.2) ).
Then ∥ ψ 1 − ψ 2 ∥ L 1 2 ≤ 4 κ ( A + 4 B ) ∥ ϕ 1 − ϕ 2 ∥ L 1 .
\|\psi_1-\psi_2\|_{{\bf L}^1}^2 ~\le ~4\kappa(A+4B) \|\phi_1-\phi_2\|_{{\bf L}^1}.
∥ ψ 1 − ψ 2 ∥ L 1 2 ≤ 4 κ ( A + 4 B ) ∥ ϕ 1 − ϕ 2 ∥ L 1 .
Proof. By the comparison property ((3.3) ) it is not restrictive to assume ϕ 2 ≤ ϕ 1 \phi_2\le \phi_1 ϕ 2 ≤ ϕ 1 .
Since ϕ 1 \phi_1 ϕ 1 and ϕ 2 \phi_2 ϕ 2 are nondecreasing, for 0 < δ ≤ κ 0<\delta\le\kappa 0 < δ ≤ κ and s + δ ≤ κ s+\delta\le\kappa s + δ ≤ κ , it holds
ϕ 1 ( s ) − ϕ 2 ( s + δ ) ≤ 1 δ ∫ s s + δ ( ϕ 1 ( x ) − ϕ 2 ( x ) ) d x ≤ 1 δ ∥ ϕ 1 − ϕ 2 ∥ L 1 . \phi_1(s)-\phi_2(s+\delta)\le \frac1\delta \int_s^{s+\delta}(\phi_1(x)-\phi_2(x))dx \le \frac1\delta \|\phi_1-\phi_2\|_{{\bf L}^1}. ϕ 1 ( s ) − ϕ 2 ( s + δ ) ≤ δ 1 ∫ s s + δ ( ϕ 1 ( x ) − ϕ 2 ( x )) d x ≤ δ 1 ∥ ϕ 1 − ϕ 2 ∥ L 1 .
Then for x ≤ κ − δ x\le\kappa-\delta x ≤ κ − δ , it holds
ψ 1 ( x ) ≤ sup 0 ≤ y ≤ x { ϕ 2 ( y + δ ) + ℓ ( x − y ) } + 1 δ ∥ ϕ 1 − ϕ 2 ∥ L 1 ≤ sup δ ≤ y ≤ x + δ { ϕ 2 ( y ) + ℓ ( x + δ − y ) } + 1 δ ∥ ϕ 1 − ϕ 2 ∥ L 1 ≤ ψ 2 ( x + δ ) + 1 δ ∥ ϕ 1 − ϕ 2 ∥ L 1 . \begin{equation*}
\begin{split}
\psi_1(x) \le &~ \sup_{0\le y\le x} \{ \phi_2(y+\delta) + \ell(x-y) \} + \frac1\delta \|\phi_1-\phi_2\|_{{\bf L}^1} \\
\le &~ \sup_{\delta\le y\le x+\delta} \{ \phi_2(y) + \ell(x+\delta-y) \}+ \frac1\delta \|\phi_1-\phi_2\|_{{\bf L}^1} \\
\le &~ \psi_2(x+\delta)+ \frac1\delta \|\phi_1-\phi_2\|_{{\bf L}^1}.
\end{split}
\end{equation*} ψ 1 ( x ) ≤ ≤ ≤ 0 ≤ y ≤ x sup { ϕ 2 ( y + δ ) + ℓ ( x − y )} + δ 1 ∥ ϕ 1 − ϕ 2 ∥ L 1 δ ≤ y ≤ x + δ sup { ϕ 2 ( y ) + ℓ ( x + δ − y )} + δ 1 ∥ ϕ 1 − ϕ 2 ∥ L 1 ψ 2 ( x + δ ) + δ 1 ∥ ϕ 1 − ϕ 2 ∥ L 1 .
The function ψ 2 \psi_2 ψ 2 is nondecreasing and has oscillation at most A + 2 B A+2B A + 2 B . Also 0 ≤ ψ 1 − ψ 2 ≤ 2 B 0\le\psi_1-\psi_2\le 2B 0 ≤ ψ 1 − ψ 2 ≤ 2 B , by sup-norm contractivity. Therefore
∫ 0 κ ( ψ 1 − ψ 2 ) d x ≤ ∫ 0 κ − δ [ ψ 2 ( x + δ ) − ψ 2 ( x ) ] d x + κ δ ∥ ϕ 1 − ϕ 2 ∥ L 1 + 2 B δ ≤ ( A + 4 B ) δ + κ δ ∥ ϕ 1 − ϕ 2 ∥ L 1 . \begin{align*}
\int_0^\kappa(\psi_1-\psi_2)\,dx
&\le\int_0^{\kappa-\delta}\bigl[\psi_2(x+\delta)-\psi_2(x)\bigr]\,dx
+\frac{\kappa }{\delta}\|\phi_1-\phi_2\|_{{\bf L}^1}+2B\delta\\
&\le (A+4B)\delta+\frac{\kappa }{\delta}\|\phi_1-\phi_2\|_{{\bf L}^1}.
\end{align*} ∫ 0 κ ( ψ 1 − ψ 2 ) d x ≤ ∫ 0 κ − δ [ ψ 2 ( x + δ ) − ψ 2 ( x ) ] d x + δ κ ∥ ϕ 1 − ϕ 2 ∥ L 1 + 2 B δ ≤ ( A + 4 B ) δ + δ κ ∥ ϕ 1 − ϕ 2 ∥ L 1 .
Let δ = κ ∥ ϕ 1 − ϕ 2 ∥ L 1 / ( A + 4 B ) \delta=\sqrt{\kappa\|\phi_1-\phi_2\|_{{\bf L}^1}/(A+4B)} δ = κ ∥ ϕ 1 − ϕ 2 ∥ L 1 / ( A + 4 B ) . It holds δ ≤ κ \delta \le \kappa δ ≤ κ because ∥ ϕ 1 − ϕ 2 ∥ L 1 ≤ 2 B κ \|\phi_1-\phi_2\|_{{\bf L}^1}\le 2B\kappa ∥ ϕ 1 − ϕ 2 ∥ L 1 ≤ 2 B κ and therefore the result follows.
Proof of Theorem (?) . In view of the sup-convolution formula ((2.35) ) for the arrival time, it suffices to apply Lemma (?) with ℓ ( s ) ≐ h ∗ ( s ) ≐ − h − 1 ( − s ) \ell (s) \doteq h^*(s)\doteq -h^{-1}(-s) ℓ ( s ) ≐ h ∗ ( s ) ≐ − h − 1 ( − s ) (see Figure 5 ).
Lipschitz continuous dependence of the arrival time function in the Eulerian formulation
For future use, in this section we prove the Lipschitz continuous dependence of the arrival time in terms of the departure rate. Namely the map u ˉ ( ⋅ ) ↦ y u ˉ ( ⋅ ) \bar u(\cdot)\mapsto y^{\bar u}(\cdot) u ˉ ( ⋅ ) ↦ y u ˉ ( ⋅ ) in ((2.32) ) is Lipschitz continuous w.r.t. the L 1 {\bf L}^1 L 1 distance. Note that here we look at the rates of departures and arrivals as functions of x ∈ R x\in \mathbb{R} x ∈ R .
Theorem. Given any K > 0 K>0 K > 0 , there exists a Lipschitz constant L K L_K L K , depending only on K K K and on the flux function f f f , such that ∥ y u ˉ − y v ˉ ∥ L 1 ( R ) ≤ L K ∥ u ˉ − v ˉ ∥ L 1 ( R )
\bigl\| y^{\bar u} - y^{\bar v}\bigr\|_{{\bf L}^1(\mathbb{R})}
~\leq~L_K \bigl\| \bar u - \bar v\bigr\|_{{\bf L}^1(\mathbb{R})}
y u ˉ − y v ˉ L 1 ( R ) ≤ L K u ˉ − v ˉ L 1 ( R ) for every couple of non-negative departure rates such that ∥ u ˉ ∥ L 1 ≤ K \|\bar u\|_{{\bf L}^1}\leq K ∥ u ˉ ∥ L 1 ≤ K , ∥ v ˉ ∥ L 1 ≤ K \|\bar v\|_{{\bf L}^1}\leq K ∥ v ˉ ∥ L 1 ≤ K .
Proof. 1. By a density argument it suffices to prove the inequality ((4.1) ) in the case where
u ˉ , v ˉ \bar u, \bar v u ˉ , v ˉ are both piecewise constant, say with jumps at the points x 0 < x 1 < ⋯ < x n x_0<x_1<\cdots< x_n x 0 < x 1 < ⋯ < x n . Namely,
u ˉ ( x ) = u i , v ˉ ( x ) = v i for x i − 1 < x < x i . \begin{equation}
\bar u(x)\,=\,u_i,\qquad \bar v(x)\,=\, v_i\qquad\quad \hbox{for} ~x_{i-1}<x< x_i\,. \tag*{(4.2)}
\end{equation} u ˉ ( x ) = u i , v ˉ ( x ) = v i for x i − 1 < x < x i . (4.2) v ˉ ( x ) = u ˉ ( x ) \bar v(x)=\bar u(x) v ˉ ( x ) = u ˉ ( x ) for all x ∉ [ a , b ] x\notin [a,b] x ∈ / [ a , b ] , where [ a , b ] = [ x k − 1 , x k ] [a,b]=[x_{k-1}, x_k] [ a , b ] = [ x k − 1 , x k ] is one of the intervals where u ˉ \bar u u ˉ and v ˉ \bar v v ˉ are constant. For x ∈ [ a , b ] x\in [a,b] x ∈ [ a , b ] , the constant values of u ˉ ( x ) \bar u(x) u ˉ ( x ) and v ˉ ( x ) \bar v(x) v ˉ ( x ) will be denoted by σ u ≐ u k < σ v ≐ v k \sigma_u\doteq u_k<\sigma_v\doteq v_k σ u ≐ u k < σ v ≐ v k .
To justify this reduction we observe that, given any two piecewise constant functions u ˉ , v ˉ \bar u, \bar v u ˉ , v ˉ , one can construct a chain of finitely many piecewise constant functions u ˉ j \bar u_j u ˉ j , j = 0 , 1 , … , N j=0,1,\ldots, N j = 0 , 1 , … , N such that (see Figure 7 )
Figure 7. The departure rate u ˉ \bar u u ˉ can be transformed into v ˉ \bar v v ˉ , in 6 elementary steps.
u ˉ j − 1 ( x ) = u ˉ j ( x ) \bar u_{j-1} (x)=\bar u_j(x) u ˉ j − 1 ( x ) = u ˉ j ( x ) for all x ∉ [ a , b ] x\notin [a,b] x ∈ / [ a , b ] , where [ a , b ] [a,b] [ a , b ] is an interval where u ˉ j \bar u_{j} u ˉ j is constant.
We have
u ˉ 0 = u ˉ , u ˉ N = v ˉ , ∥ v ˉ − u ˉ ∥ L 1 = ∑ j = 1 N ∥ u ˉ j − u ˉ j − 1 ∥ L 1 . \begin{equation}
\bar u_0= \bar u, \qquad \bar u_N = \bar v,\qquad \| \bar v - \bar u\|_{{\bf L}^1}~=~\sum_{j=1}^N \|\bar u_j-\bar u_{j-1}\|_{{\bf L}^1}\,. \tag*{(4.3)}
\end{equation} u ˉ 0 = u ˉ , u ˉ N = v ˉ , ∥ v ˉ − u ˉ ∥ L 1 = j = 1 ∑ N ∥ u ˉ j − u ˉ j − 1 ∥ L 1 . (4.3)
This reduces the analysis to the basic case (i)-(ii) above, as shown in Figure 8 . The corresponding integrated functions U ‾ \overline U U and V ‾ \overline V V are shown in Figure 10 and Figure 11 . In this case, the inequality ((4.1) ) reduces to
∥ y u ˉ − y v ˉ ∥ L 1 ( R ) = O ( 1 ) ⋅ δ , δ ≐ ∥ u ˉ − v ˉ ∥ L 1 = ( b − a ) ( σ v − σ u ) . \begin{equation}
\bigl\| y^{\bar u} - y^{\bar v}\bigr\|_{{\bf L}^1(\mathbb{R})} ~=~{\mathcal O}(1)\cdot\delta,
\qquad \quad \delta\,\doteq\, \|\bar u-\bar v\|_{{\bf L}^1}\,=\,(b-a)(\sigma_v-\sigma_u). \tag*{(4.4)}
\end{equation} y u ˉ − y v ˉ L 1 ( R ) = O ( 1 ) ⋅ δ , δ ≐ ∥ u ˉ − v ˉ ∥ L 1 = ( b − a ) ( σ v − σ u ) . (4.4)
Figure 8. A piecewise constant departure rate u ˉ \bar u u ˉ and a perturbation v ˉ \bar v v ˉ of basic type.
Figure 9. Left: the function g g g at ((4.5) ). Right: the point y u ˉ ( x ) {\bf y}^{\bar u}(x) y u ˉ ( x ) and the contact point z u ˉ ( x ) z^{\bar u}(x) z u ˉ ( x ) , introduced at ((4.8) )-((4.9) ).
2. To simplify some of the computations, it will be convenient to introduce the points
y u ˉ ( x ) ≐ y u ˉ ( x ) − ℓ 0 . {\bf y}^{\bar u}(x)~\doteq~y^{\bar u}(x)- \ell_0\,. y u ˉ ( x ) ≐ y u ˉ ( x ) − ℓ 0 .
Since we trivially have
y v ˉ ( x ) − y u ˉ ( x ) = y v ˉ ( x ) − y u ˉ ( x ) , {\bf y}^{\bar v}(x)-{\bf y}^{\bar u}(x)~=~y^{\bar v}(x)- y^{\bar u}(x), y v ˉ ( x ) − y u ˉ ( x ) = y v ˉ ( x ) − y u ˉ ( x ) ,
we shall focus on the change in the values of y ( x ) {\bf y}(x) y ( x ) , which is easier to analyze. Consider the auxiliary function (see Figure 9 , left)
g ( s ) ≐ h ( s − ℓ 0 ) = − L f ∗ ( ℓ 0 − s L ) = − L f ∗ ( f ′ ( 0 ) − s L ) , s ≤ 0. \begin{equation}
g(s)~\doteq~h(s-\ell_0)~=\,- L \,f^*\left( \ell_0-s\over L\right)~=\,-L f^*\left(f'(0)- {s\over L}\right),\qquad\qquad s\leq 0. \tag*{(4.5)}
\end{equation} g ( s ) ≐ h ( s − ℓ 0 ) = − L f ∗ ( L ℓ 0 − s ) = − L f ∗ ( f ′ ( 0 ) − L s ) , s ≤ 0. (4.5)
This function satisfies
g ( 0 ) = g ′ ( 0 ) = 0 , g ′ ′ ( 0 ) < 0 , lim s → − ∞ g ′ ( s ) = lim p → + ∞ ∂ ∂ p f ∗ ( p ) = lim p → + ∞ u ( p ) = M . \begin{equation}
g(0) = g'(0)=0, \qquad g''(0) <0, \qquad\lim_{s\to -\infty} g'(s) ~=~\lim_{p\to +\infty} {\partial \over\partial p} f^*(p)
~=~\lim_{p\to +\infty} u(p)~=~M. \tag*{(4.6)}
\end{equation} g ( 0 ) = g ′ ( 0 ) = 0 , g ′′ ( 0 ) < 0 , s → − ∞ lim g ′ ( s ) = p → + ∞ lim ∂ p ∂ f ∗ ( p ) = p → + ∞ lim u ( p ) = M . (4.6)
Moreover, given κ > 0 \kappa>0 κ > 0 , we can find c κ > 0 c_\kappa>0 c κ > 0 such that
g ( s ) ∈ [ − κ , 0 ] ⟹ g ( s ) ≤ − c κ s 2 . \begin{equation}
g(s)\in [-\kappa, 0]\qquad\Longrightarrow\qquad g(s)~\leq~- c_\kappa s^2. \tag*{(4.7)}
\end{equation} g ( s ) ∈ [ − κ , 0 ] ⟹ g ( s ) ≤ − c κ s 2 . (4.7)
Let U ‾ , V ‾ \overline U, \overline V U , V be the integrated functions, as in ((2.23) ). As shown in Figure 9 , right, given a departure rate u ˉ ( ⋅ ) \bar u(\cdot) u ˉ ( ⋅ ) , the point y u ˉ ( x ) {\bf y}^{\bar u}(x) y u ˉ ( x ) can be computed by the formula
y u ˉ ( x ) = inf { y ≥ x ; U ‾ ( s ) ≥ U ‾ ( x ) + g ( s − y ) for all s ≤ x } . \begin{equation}
{\bf y}^{\bar u}(x)~=~\inf\Big\{ y\geq x\,;~~\overline U(s)\geq \overline U(x) + g(s-y)\quad\hbox{for all}~s\leq x\Big\}. \tag*{(4.8)}
\end{equation} y u ˉ ( x ) = inf { y ≥ x ; U ( s ) ≥ U ( x ) + g ( s − y ) for all s ≤ x } . (4.8)
In other words, we consider the graph of the function U ‾ ( x ) + g ( ⋅ − y ) \overline U(x) + g(\cdot -y) U ( x ) + g ( ⋅ − y ) , and slide it forward (i.e., to the right) until it lies entirely below the graph of U ‾ ( ⋅ ) \overline U(\cdot) U ( ⋅ ) . The contact point between the graphs of these two functions will be denoted by
z u ˉ ( x ) = max { s ≤ x ; U ‾ ( s ) = U ‾ ( x ) + g ( s − y u ˉ ( x ) } . \begin{equation}
z^{\bar u}(x)~=~\max\Big\{ s\leq x\,;~\overline U(s)=\overline U(x) + g\bigl( s- {\bf y}^{\bar u}(x)\Big\}. \tag*{(4.9)}
\end{equation} z u ˉ ( x ) = max { s ≤ x ; U ( s ) = U ( x ) + g ( s − y u ˉ ( x ) } . (4.9)
Notice that we have the implication
u ˉ ≤ v ˉ ⟹ y u ˉ ( x ) ≤ y v ˉ ( x ) for all x ∈ R . \begin{equation}
\bar u\leq \bar v\qquad\Longrightarrow\qquad {\bf y}^{\bar u}(x)\,\leq\,{\bf y}^{\bar v}(x)
\quad\hbox{for all}~x\in \mathbb{R}. \tag*{(4.10)}
\end{equation} u ˉ ≤ v ˉ ⟹ y u ˉ ( x ) ≤ y v ˉ ( x ) for all x ∈ R . (4.10)
Indeed, if V ‾ ( s ) ≥ V ‾ ( x ) + g ( s − y v ˉ ( x ) ) \overline V(s)\geq \overline V(x) +g\bigl(s-{\bf y}^{\bar v}(x)\bigr) V ( s ) ≥ V ( x ) + g ( s − y v ˉ ( x ) ) for all s < x s<x s < x , then
U ‾ ( s ) = V ‾ ( s ) + ( U ‾ ( s ) − V ‾ ( s ) ) ≥ V ‾ ( s ) + ( U ‾ ( x ) − V ‾ ( x ) ) ≥ U ‾ ( x ) + g ( s − y v ˉ ( x ) ) \overline U(s)~=~\overline V(s) + \bigl( \overline U(s)- \overline V(s)\bigr)~\geq~
\overline V(s) + \bigl( \overline U(x)- \overline V(x)\bigr)~\geq~
\overline U(x) + g\bigl( s- {\bf y}^{\bar v}(x)\bigr) U ( s ) = V ( s ) + ( U ( s ) − V ( s ) ) ≥ V ( s ) + ( U ( x ) − V ( x ) ) ≥ U ( x ) + g ( s − y v ˉ ( x ) )
for all s < x s<x s < x . By the definition ((4.8) ) this implies y u ˉ ( x ) ≤ y v ˉ ( x ) {\bf y}^{\bar u}(x)\,\leq\,{\bf y}^{\bar v}(x) y u ˉ ( x ) ≤ y v ˉ ( x ) .
3. We are now ready to estimate the L 1 {\bf L}^1 L 1 distance in ((4.1) ), where u ˉ , v ˉ \bar u, \bar v u ˉ , v ˉ are piecewise constant functions with the properties listed in (i)-(ii). Consider the point b ∗ ≐ sup { x : z v ˉ ( x ) < b } b^*\doteq \sup \{ x : z^{\bar v}(x)<b\} b ∗ ≐ sup { x : z v ˉ ( x ) < b } . For x ∈ R ∖ [ a , b ∗ ] x \in \mathbb{R}\setminus [a,b^*] x ∈ R ∖ [ a , b ∗ ] one has y v ˉ ( x ) = y u ˉ ( x ) {\bf y}^{\bar v} (x) = {\bf y}^{\bar u}(x) y v ˉ ( x ) = y u ˉ ( x ) . Therefore it is sufficient to consider x ∈ [ a , b ∗ ] x \in [a, b^*] x ∈ [ a , b ∗ ] .
Define the points
a ∗ ≐ inf { x : z v ˉ ( x ) > a } , b ′ ≐ sup { x : y v ˉ ( x ) < b } . \begin{equation}
a^*\doteq \inf \{ x: z^{\bar v}(x)>a\},
\qquad\qquad b' \doteq \sup \{ x : {\bf y}^{\bar v}(x)<b\}. \tag*{(4.11)}
\end{equation} a ∗ ≐ inf { x : z v ˉ ( x ) > a } , b ′ ≐ sup { x : y v ˉ ( x ) < b } . (4.11)
Since both cases a ∗ ≤ b ′ a^*\le b' a ∗ ≤ b ′ and b ′ < a ∗ b' < a^* b ′ < a ∗ are possible, in the next steps we estimate ∥ y v ˉ − y u ˉ ∥ L 1 \|{\bf y}^{\bar v}-{\bf y}^{\bar u}\|_{{\bf L}^1} ∥ y v ˉ − y u ˉ ∥ L 1 separately on the interval [ a , a ∗ ] [a,a^*] [ a , a ∗ ] , on the possibly empty interval [ a ∗ , b ′ ] [a^*,b'] [ a ∗ , b ′ ] , and on the interval [ max { a ∗ , b ′ } , b ∗ ] \bigl[\max\{a^*,b'\},\,b^* \bigr] [ max { a ∗ , b ′ } , b ∗ ] .
Figure 10. Left: for x > b ∗ x>b^* x > b ∗ one has z u ˉ ( x ) = z v ˉ ( x ) z^{\bar u}(x) = z^{\bar v}(x) z u ˉ ( x ) = z v ˉ ( x ) and y u ˉ ( x ) = y v ˉ ( x ) {\bf y}^{\bar u}(x) = {\bf y}^{\bar v}(x) y u ˉ ( x ) = y v ˉ ( x ) . Right: an example of the point a ∗ a^* a ∗ defined at ((4.11) ).
Figure 11. Left: an example where b ′ > a b'>a b ′ > a . Right: an example where b ′ < a b'<a b ′ < a .
4. Let C K > 0 C_K>0 C K > 0 be a constant such that, for every u ˉ ∈ L 1 ( R ) \bar u \in {\bf L}^1(\mathbb{R}) u ˉ ∈ L 1 ( R ) with ∥ u ˉ ∥ L 1 ( R ) ≤ K \|\bar u\|_{{\bf L}^1(\mathbb{R})}\le K ∥ u ˉ ∥ L 1 ( R ) ≤ K , there holds
y u ˉ ( x ) − z u ˉ ( x ) ∈ [ 0 , C K ] for all x ∈ R . {\bf y}^{\bar u}(x) - z^{\bar u}(x)\,\in \,[0, C_K]\qquad \hbox{for all}~x \in \mathbb{R}. y u ˉ ( x ) − z u ˉ ( x ) ∈ [ 0 , C K ] for all x ∈ R .
Then choose a constant c K > 0 c_K>0 c K > 0 such that
g ′ ′ ( s ) ≤ − c K for all s ∈ [ − C K , 0 ] . \begin{equation}
g''(s) \le - c_K \qquad \hbox{for all}~s \in [-C_K,0]. \tag*{(4.12)}
\end{equation} g ′′ ( s ) ≤ − c K for all s ∈ [ − C K , 0 ] . (4.12)
We claim that, for every x ∈ R x \in \mathbb{R} x ∈ R such that z v ˉ ( x ) < x z^{\bar v}(x)<x z v ˉ ( x ) < x , one has
y v ˉ ( x ) − y u ˉ ( x ) ≤ 2 c K ( y v ˉ ( x ) − z v ˉ ( x ) ) δ . \begin{equation}
{\bf y}^{\bar v}(x)-{\bf y}^{\bar u}(x) ~\le ~\frac{2}{c_K({\bf y}^{\bar v}(x)-z^{\bar v}(x))}\, \delta. \tag*{(4.13)}
\end{equation} y v ˉ ( x ) − y u ˉ ( x ) ≤ c K ( y v ˉ ( x ) − z v ˉ ( x )) 2 δ . (4.13)
Indeed, since
V ‾ ( x ) + g ( z v ˉ ( x ) − y v ˉ ( x ) ) ≥ U ‾ ( x ) + g ( z v ˉ ( x ) − y u ˉ ( x ) ) \overline V(x) + g(z^{\bar v}(x)- {\bf y}^{\bar v(x)}) \ge \overline U(x) + g(z^{\bar v}(x)- {\bf y}^{\bar u(x)}) V ( x ) + g ( z v ˉ ( x ) − y v ˉ ( x ) ) ≥ U ( x ) + g ( z v ˉ ( x ) − y u ˉ ( x ) )
then
δ ≥ V ‾ ( x ) − U ‾ ( x ) ≥ ∫ z v ˉ ( x ) z v ˉ ( x ) + y v ˉ ( x ) − y u ˉ ( x ) g ′ ( s − y v ˉ ( x ) ) d s ≥ ( y v ˉ ( x ) − y u ˉ ( x ) ) g ( z v ˉ ( x ) − y v ˉ ( x ) ) z v ˉ ( x ) − y v ˉ ( x ) ≥ ( y v ˉ ( x ) − y u ˉ ( x ) ) c K 2 ( y v ˉ ( x ) − z v ˉ ( x ) ) . \begin{array}{rl}
\delta& \ge ~\overline V(x) - \overline U(x) ~\ge \displaystyle~ \int_{z^{\bar v}(x)}^{z^{\bar v}(x)+ {\bf y}^{\bar v}(x) - {\bf y}^{\bar u}(x)}g'\bigl(s-{\bf y}^{\bar v}(x)\bigr)ds ~\ge ~\bigl( {\bf y}^{\bar v}(x) - {\bf y}^{\bar u}(x)\bigr) \frac{g\bigl(z^{\bar v(x)}- {\bf y}^{\bar v}(x) \bigr)}{z^{\bar v}(x)-{\bf y}^{\bar v}(x)} \\[4mm]
&\ge~ \bigl( {\bf y}^{\bar v}(x) - {\bf y}^{\bar u}(x)\bigr) \frac{c_K}2 \bigl({\bf y}^{\bar v}(x)-z^{\bar v}(x)
\bigr).
\end{array} δ ≥ V ( x ) − U ( x ) ≥ ∫ z v ˉ ( x ) z v ˉ ( x ) + y v ˉ ( x ) − y u ˉ ( x ) g ′ ( s − y v ˉ ( x ) ) d s ≥ ( y v ˉ ( x ) − y u ˉ ( x ) ) z v ˉ ( x ) − y v ˉ ( x ) g ( z v ˉ ( x ) − y v ˉ ( x ) ) ≥ ( y v ˉ ( x ) − y u ˉ ( x ) ) 2 c K ( y v ˉ ( x ) − z v ˉ ( x ) ) .
Figure 12. The points x ′ < z v ‾ ( x ) x'<z^{\overline v}(x) x ′ < z v ( x ) and y u ˉ ( x ) < y v ˉ ( x ) {\bf y}^{\bar u}(x)<{\bf y}^{\bar v}(x) y u ˉ ( x ) < y v ˉ ( x ) used in the proof of ((4.13) ).
5. Estimate on [ a , a ∗ ] [a,a^*] [ a , a ∗ ] . We define
σ ∗ ≐ g ′ ( a − y v ˉ ( a ∗ ) ) , V ∗ ≐ V ‾ ( a ∗ ) + g ( a − y v ˉ ( a ∗ ) ) ≤ V ‾ ( a ) . \sigma^*\,\doteq \, g'\bigl(a-{\bf y}^{\bar v}(a^*)\bigr),\qquad\quad V^*\,\doteq \,\overline V(a^*)+ g(a-{\bf y}^{\bar v}(a^*))\le \overline V(a). σ ∗ ≐ g ′ ( a − y v ˉ ( a ∗ ) ) , V ∗ ≐ V ( a ∗ ) + g ( a − y v ˉ ( a ∗ )) ≤ V ( a ) .
Observe that a ∗ − a ≤ y v ˉ ( a ∗ ) − a ≤ σ ∗ / c K a^*-a \le {\bf y}^{\bar v}(a^*) -a \le {\sigma^* / c_K} a ∗ − a ≤ y v ˉ ( a ∗ ) − a ≤ σ ∗ / c K .
By the definition of a ∗ a^* a ∗ at ((4.11) ) it follows that, for every x ∈ ] a , a ∗ [ x \in \,]a,a^*[\, x ∈ ] a , a ∗ [ , there holds
V ‾ ( x ) + g ( a − y v ˉ ( x ) ) ≤ V ∗ . \overline V(x) + g(a-{\bf y}^{\bar v}(x))~\le~ V^*. V ( x ) + g ( a − y v ˉ ( x )) ≤ V ∗ .
Moreover for every x ∈ ] a , a ∗ [ x \in \,]a,a^*[ x ∈ ] a , a ∗ [ it holds
V ‾ ( x ) ≥ V ‾ ( a ∗ ) + g ( x − y v ˉ ( a ∗ ) ) = V ∗ + g ( x − y v ˉ ( a ∗ ) ) − g ( a − y v ˉ ( a ∗ ) ) ≥ V ∗ + ( x − a ) g ( a − y v ˉ ( a ∗ ) ) a − y v ˉ ( a ∗ ) ≥ V ∗ + ( x − a ) σ ∗ c K 2 ∥ g ′ ′ ∥ L ∞ . \begin{array}{rl}
\overline V(x) &\ge ~ \overline V(a^*) + g(x-{\bf y}^{\bar v}(a^*)) ~
= ~ V^* + g(x-{\bf y}^{\bar v}(a^*)) - g(a-{\bf y}^{\bar v}(a^*)) \\[3mm]
&\displaystyle\ge ~ V^* + (x-a) {g(a-{\bf y}^{\bar v}(a^*)) \over a-{\bf y}^{\bar v}(a^*)} ~\ge ~ V^* + (x-a) \frac{\sigma^* c_K}{2 \|g''\|_{{\bf L}^\infty}}\,.
\end{array} V ( x ) ≥ V ( a ∗ ) + g ( x − y v ˉ ( a ∗ )) = V ∗ + g ( x − y v ˉ ( a ∗ )) − g ( a − y v ˉ ( a ∗ )) ≥ V ∗ + ( x − a ) a − y v ˉ ( a ∗ ) g ( a − y v ˉ ( a ∗ )) ≥ V ∗ + ( x − a ) 2∥ g ′′ ∥ L ∞ σ ∗ c K .
Therefore
∫ a a ∗ 1 y v ˉ ( x ) − z v ˉ ( x ) d x ≤ ∫ a a ∗ 1 y v ˉ ( x ) − a d x ≤ ∥ g ′ ′ ∥ L ∞ 2 ∫ a a ∗ 1 − g ( a − y v ˉ ( x ) ) d x ≤ ∥ g ′ ′ ∥ L ∞ 2 ∫ a a ∗ 1 V ‾ ( x ) − V ∗ d x ≤ ∥ g ′ ′ ∥ L ∞ 1 / 2 σ ∗ c K ∫ a a ∗ 1 x − a d x ≤ 2 ∥ g ′ ′ ∥ L ∞ c K . \begin{equation}
\begin{array}{l}\displaystyle
\int_a^{a^*}\frac1{{\bf y}^{\bar v}(x)-z^{\bar v}(x)}dx ~\le ~ \int_a^{a^*}\frac1{{\bf y}^{\bar v}(x)-a}
\,dx~\le~ \sqrt{\frac{\|g''\|_{{\bf L}^\infty}}{2} } \int_a^{a^*}\frac1{\sqrt{-g\bigl(a-{\bf y}^{\bar v}(x)\bigr)}}\,dx\\[4mm]
\quad\displaystyle\le ~ \sqrt{\frac{\|g''\|_{{\bf L}^\infty}}{2}} \int_a^{a^*}\frac1{\sqrt{\overline V(x)-V^*}}\,dx
~\le ~\frac{\|g''\|_{{\bf L}^\infty}^{1/2}}{\sqrt{\sigma^* c_K}} \int_a^{a^*} \frac1{\sqrt{x-a}}\,dx ~
\le ~ {2\|g''\|_{{\bf L}^\infty}\over c_K} \,.
\end{array} \tag*{(4.14)}
\end{equation} ∫ a a ∗ y v ˉ ( x ) − z v ˉ ( x ) 1 d x ≤ ∫ a a ∗ y v ˉ ( x ) − a 1 d x ≤ 2 ∥ g ′′ ∥ L ∞ ∫ a a ∗ − g ( a − y v ˉ ( x ) ) 1 d x ≤ 2 ∥ g ′′ ∥ L ∞ ∫ a a ∗ V ( x ) − V ∗ 1 d x ≤ σ ∗ c K ∥ g ′′ ∥ L ∞ 1/2 ∫ a a ∗ x − a 1 d x ≤ c K 2∥ g ′′ ∥ L ∞ . (4.14)
In view of ((4.13) ), this yields
∫ a a ∗ ∣ y v ˉ ( x ) − y u ˉ ( x ) ∣ d x ≤ 2 δ c K ∫ a a ∗ 1 y v ˉ ( x ) − z v ˉ ( x ) d x ≤ 4 ∥ g ′ ′ ∥ L ∞ c K 2 ⋅ δ . \begin{equation}
\int_a^{a^*}\bigl| {\bf y}^{\bar v}(x) - {\bf y}^{\bar u}(x)\bigr|\, dx ~\le~ {2\delta\over c_K} \int_a^{a^*}\frac1{{\bf y}^{\bar v}(x)-z^{\bar v}(x)}dx ~\leq~ \frac{4\|g''\|_{{\bf L}^\infty}}{c_K^2} \cdot \delta. \tag*{(4.15)}
\end{equation} ∫ a a ∗ y v ˉ ( x ) − y u ˉ ( x ) d x ≤ c K 2 δ ∫ a a ∗ y v ˉ ( x ) − z v ˉ ( x ) 1 d x ≤ c K 2 4∥ g ′′ ∥ L ∞ ⋅ δ . (4.15)
6. Estimate on [ a ∗ , b ′ ] [a^*, b'] [ a ∗ , b ′ ] . This case is nontrivial only if b ′ > a ∗ b' > a^* b ′ > a ∗ . We claim that
y v ˉ ( x ) − y u ˉ ( x ) ≤ 1 c K ( 1 + ∥ g ′ ′ ∥ L ∞ 2 c K 2 ) ( σ v − σ u ) for all x ∈ ] a ∗ , b ′ [ ⊂ [ a , b ] . \begin{equation}
{\bf y}^{\bar v}(x)-{\bf y}^{\bar u}(x)~\le~ \frac1{c_K}\left(1+ \frac{\|g''\|^2_{{\bf L}^\infty}}{c_K^2}\right)(\sigma_v-\sigma_u)\qquad \quad \hbox{for all}~~x \in \ ]a^*,b'[\ \subset [a,b]. \tag*{(4.16)}
\end{equation} y v ˉ ( x ) − y u ˉ ( x ) ≤ c K 1 ( 1 + c K 2 ∥ g ′′ ∥ L ∞ 2 ) ( σ v − σ u ) for all x ∈ ] a ∗ , b ′ [ ⊂ [ a , b ] . (4.16)
To prove (4.16) , consider any x ∈ ] a ∗ , b ′ [ x \in \ ]a^*, b' [ \, x ∈ ] a ∗ , b ′ [ . Then a < z v ˉ ( x ) < y v ˉ ( x ) < b a < z^{\bar v}(x) < {\bf y}^{\bar v}(x) < b a < z v ˉ ( x ) < y v ˉ ( x ) < b , hence y v ˉ ( x ) − z v ˉ ( x ) = Δ σ v {\bf y}^{\bar v}(x)-z^{\bar v}(x) = \Delta_{\sigma_v} y v ˉ ( x ) − z v ˉ ( x ) = Δ σ v with g ′ ( − Δ σ v ) = σ v g'(-\Delta_{\sigma_v})=\sigma_v g ′ ( − Δ σ v ) = σ v and − g ( − Δ σ v ) = σ v ( x − z v ˉ ( x ) ) -g(-\Delta_{\sigma_v})= \sigma_v (x- z^{\bar v}(x)) − g ( − Δ σ v ) = σ v ( x − z v ˉ ( x )) . Therefore
y v ˉ ( x ) = x + Δ σ v + g ( − Δ σ v ) σ v . {\bf y}^{\bar v}(x) \,=\, x + \Delta_{\sigma_v} + \frac{g(-\Delta_{\sigma_v})}{\sigma_v}. y v ˉ ( x ) = x + Δ σ v + σ v g ( − Δ σ v ) .
Similarly we obtain
y u ˉ ( x ) ≥ x + Δ σ u + g ( − Δ σ u ) σ u . {\bf y}^{\bar u}(x) \,\ge\, x + \Delta_{\sigma_u} + \frac{g(-\Delta_{\sigma_u})}{\sigma_u}. y u ˉ ( x ) ≥ x + Δ σ u + σ u g ( − Δ σ u ) .
In particular
y v ˉ ( x ) − y u ˉ ( x ) ≤ Δ σ v + g ( − Δ σ v ) σ v − Δ σ u − g ( − Δ σ u ) σ u = Δ σ v − Δ σ u + g ( − Δ σ v ) g ′ ( − Δ σ v ) − g ( − Δ σ u ) g ′ ( − Δ σ u ) ≤ ( 1 + ∥ g ′ ′ g ( g ′ ) 2 ∥ L ∞ ( [ − C K , 0 ] ) ) ( Δ σ v − Δ σ u ) ≤ ( 1 + ∥ g ′ ′ ∥ L ∞ 2 c K 2 ) ( Δ σ v − Δ σ u ) ≤ 1 c K ( 1 + ∥ g ′ ′ ∥ L ∞ 2 c K 2 ) ( σ v − σ u ) , \begin{split}
{\bf y}^{\bar v}(x) - {\bf y}^{\bar u}(x) \le &~ \Delta_{\sigma_v} + \frac{g(-\Delta_{\sigma_v})}{\sigma_v} - \Delta_{\sigma_u} - \frac{g(-\Delta_{\sigma_u})}{\sigma_u} \\
=&~ \Delta_{\sigma_v} - \Delta_{\sigma_u} + \frac{g(-\Delta_{\sigma_v})}{g'(-\Delta_{\sigma_v})} - \frac{g(-\Delta_{\sigma_u})}{g'(-\Delta_{\sigma_u})} \\
\le &~ \left(1+ \left\|\frac{g'' g}{(g')^2}\right\|_{{\bf L}^\infty([-C_K,0])}\right)(\Delta_{\sigma_v}-\Delta_{\sigma_u}) \\
\le &~ \left(1+ \frac{\|g''\|^2_{{\bf L}^\infty}}{c_K^2}\right)(\Delta_{\sigma_v}-\Delta_{\sigma_u}) \\
\le &~ \frac1{c_K}\left(1+ \frac{\|g''\|^2_{{\bf L}^\infty}}{c_K^2}\right)(\sigma_v - \sigma_u),
\end{split} y v ˉ ( x ) − y u ˉ ( x ) ≤ = ≤ ≤ ≤ Δ σ v + σ v g ( − Δ σ v ) − Δ σ u − σ u g ( − Δ σ u ) Δ σ v − Δ σ u + g ′ ( − Δ σ v ) g ( − Δ σ v ) − g ′ ( − Δ σ u ) g ( − Δ σ u ) ( 1 + ( g ′ ) 2 g ′′ g L ∞ ([ − C K , 0 ]) ) ( Δ σ v − Δ σ u ) ( 1 + c K 2 ∥ g ′′ ∥ L ∞ 2 ) ( Δ σ v − Δ σ u ) c K 1 ( 1 + c K 2 ∥ g ′′ ∥ L ∞ 2 ) ( σ v − σ u ) ,
where in the last inequality we used that the Lipschitz constant of ( g ′ ) − 1 (g')^{-1} ( g ′ ) − 1 is bounded by 1 c K 1\over c_K c K 1 . Thanks to ((4.16) ) we now have
∫ a ∗ b ′ ∣ y v ˉ ( x ) − y u ˉ ( x ) ∣ d x ≤ 1 c K ( 1 + ∥ g ′ ′ ∥ L ∞ 2 c K 2 ) ( b − a ) ( σ v − σ u ) = 1 c K ( 1 + ∥ g ′ ′ ∥ L ∞ 2 c K 2 ) δ . \begin{equation}
\int_{a^*}^{b'}\bigl|{\bf y}^{\bar v}(x)-{\bf y}^{\bar u}(x)\bigr| \,dx ~\le~ \frac1{c_K}\left(1+ \frac{\|g''\|^2_{{\bf L}^\infty}}{c_K^2}\right)(b-a)(\sigma_v - \sigma_u)~=~\frac1{c_K}\left(1+ \frac{\|g''\|^2_{{\bf L}^\infty}}{c_K^2}\right)\delta. \tag*{(4.17)}
\end{equation} ∫ a ∗ b ′ y v ˉ ( x ) − y u ˉ ( x ) d x ≤ c K 1 ( 1 + c K 2 ∥ g ′′ ∥ L ∞ 2 ) ( b − a ) ( σ v − σ u ) = c K 1 ( 1 + c K 2 ∥ g ′′ ∥ L ∞ 2 ) δ . (4.17)
7. Estimate on [ max { a ∗ , b ′ } , b ∗ ] \bigl[\max\{a^*,b'\},\,b^*\bigr] [ max { a ∗ , b ′ } , b ∗ ] . If max { a ∗ , b ′ } < x < b ∗ \max\{a^*,b'\}<x<b^* max { a ∗ , b ′ } < x < b ∗ , then z v ˉ ( x ) ∈ ] a , b [ z^{\bar v}(x) \in \,]a,b[\, z v ˉ ( x ) ∈ ] a , b [ and y v ˉ ( x ) ≥ b {\bf y}^{\bar v}(x)\ge b y v ˉ ( x ) ≥ b . In particular y v ˉ ( x ) − z v ˉ ( x ) = Δ σ v {\bf y}^{\bar v}(x) - z^{\bar v}(x)= \Delta_{\sigma_v} y v ˉ ( x ) − z v ˉ ( x ) = Δ σ v where g ′ ( − Δ σ v ) = σ v g'(-\Delta_{\sigma_v})=\sigma_v g ′ ( − Δ σ v ) = σ v . Therefore
b ∗ − max { a ∗ , b ′ } ≤ Δ σ v b^* - \max\{a^*,b'\} \,\le\, \Delta_{\sigma_v} b ∗ − max { a ∗ , b ′ } ≤ Δ σ v
and hence
∫ max { a ∗ , b ′ } b ∗ 1 y v ˉ ( x ) − z v ˉ ( x ) d x ≤ 1. \int_{\max\{a^*,b'\} }^{b^*} \frac1{{\bf y}^{\bar v}(x) - z^{\bar v}(x)} dx~ \le~ 1. ∫ m a x { a ∗ , b ′ } b ∗ y v ˉ ( x ) − z v ˉ ( x ) 1 d x ≤ 1.
In view of ((4.13) ), this yields
∫ max { a ∗ , b ′ } b ∗ ∣ y v ˉ ( x ) − y u ˉ ( x ) ∣ d x ≤ 2 δ c K ∫ max { a ∗ , b ′ } b ∗ 1 y v ˉ ( x ) − z v ˉ ( x ) d x ≤ 2 δ c K . \begin{equation}
\int_{\max\{a^*,b'\} }^{b^*} \bigl|{\bf y}^{\bar v}(x)-{\bf y}^{\bar u}(x)\bigr| \,dx
~\leq~ {2\delta\over c_K} \int_{\max\{a^*,b'\} }^{b^*} \frac1{{\bf y}^{\bar v}(x)-z^{\bar v}(x)}dx ~\leq~{2\delta\over c_K} \,. \tag*{(4.18)}
\end{equation} ∫ m a x { a ∗ , b ′ } b ∗ y v ˉ ( x ) − y u ˉ ( x ) d x ≤ c K 2 δ ∫ m a x { a ∗ , b ′ } b ∗ y v ˉ ( x ) − z v ˉ ( x ) 1 d x ≤ c K 2 δ . (4.18)
Together, ((4.15) ), ((4.17) ) and ((4.18) ) yield (4.1) , completing the proof.
Departure rates as Nash equilibria
We now consider a cost φ ( x ) \varphi(x) φ ( x ) for early departure and a cost ψ ( x ) \psi(x) ψ ( x ) for late arrival (see Figure 13 ). The main results will be obtained under the assumptions
For some constants L φ , L ψ L_\varphi,L_\psi L φ , L ψ , the cost functions φ , ψ \varphi,\psi φ , ψ satisfy − L φ ≤ φ ′ < 0 , φ ′ ′ ≥ 0 , ψ , ψ ′ ′ > 0 , 0 < ψ ′ < L ψ ,
-L_\varphi\leq \varphi'<0,\qquad \varphi''\,\geq\,0,\qquad\psi,\psi''~> ~0,\qquad 0<\psi'<L_\psi\,,
− L φ ≤ φ ′ < 0 , φ ′′ ≥ 0 , ψ , ψ ′′ > 0 , 0 < ψ ′ < L ψ , lim x → + ∞ ( φ ( x ) + ψ ( x ) ) = + ∞ .
\lim_{x\to +\infty}
\Big(\varphi(x)+ \psi(x)\Big)=+\infty.
lim x → + ∞ ( φ ( x ) + ψ ( x ) ) = + ∞.
Figure 13. The departure cost φ ( x ) \varphi(x) φ ( x ) , the arrival cost ψ ( x ) \psi(x) ψ ( x ) , and a lower bound on the total cost Φ 0 ( x ) = φ ( x ) + ψ ( x + ℓ 0 ) \Phi^0(x)=\varphi(x)+\psi(x+\ell_0) Φ 0 ( x ) = φ ( x ) + ψ ( x + ℓ 0 ) , according to the assumptions in (A2).
Given a departure rate u ˉ \bar u u ˉ , the total cost to a driver departing at time x x x is defined as
Φ u ˉ ( x ) ≐ φ ( x ) + ψ ( y u ˉ ( x ) ) , \begin{equation}
\Phi^{\bar u}(x)~\doteq~\varphi(x)+ \psi\bigl(y^{\bar u}(x)\bigr), \tag*{(5.3)}
\end{equation} Φ u ˉ ( x ) ≐ φ ( x ) + ψ ( y u ˉ ( x ) ) , (5.3)
where y u ˉ ( x ) y^{\bar u}(x) y u ˉ ( x ) is the arrival time defined at ((2.13) ).
We denote by ℓ 0 , ℓ m a x \ell_0, \ell_{max} ℓ 0 , ℓ ma x a lower and an upper bound for the duration of a trip, as in ((2.10) ) and ((2.12) ). These constants depend only on the flux function f f f and on the total number κ \kappa κ of drivers. For any departure rate u ˉ \bar u u ˉ with ∥ u ˉ ∥ L 1 = κ \|\bar u\|_{{\bf L}^1}=\kappa ∥ u ˉ ∥ L 1 = κ , the corresponding cost Φ u ( x ) \Phi^u(x) Φ u ( x ) to a driver departing at time x x x thus satisfies the bounds
Φ 0 ( x ) ≐ φ ( x ) + ψ ( x + ℓ 0 ) ≤ Φ u ˉ ( x ) ≤ φ ( x ) + ψ ( x + ℓ m a x ) ≐ Φ m a x ( x ) . \begin{equation}
\Phi^0(x)~\doteq ~\varphi(x) + \psi(x+\ell_0) ~\leq~\Phi^{\bar u}(x)~\leq ~\varphi(x) + \psi(x+\ell_{max})
~\doteq~\Phi^{max}(x). \tag*{(5.4)}
\end{equation} Φ 0 ( x ) ≐ φ ( x ) + ψ ( x + ℓ 0 ) ≤ Φ u ˉ ( x ) ≤ φ ( x ) + ψ ( x + ℓ ma x ) ≐ Φ ma x ( x ) . (5.4)
Let u ‾ ( ⋅ ) \overline u(\cdot) u ( ⋅ ) be a departure rate where all drivers incur the same total cost c c c . Calling
ℓ ( x ) = [duration of the journey of the driver that departs at time x ], \begin{equation}
\ell(x) ~=~\hbox{[duration of the journey of the driver that departs at time~$x$],} \tag*{(5.8)}
\end{equation} ℓ ( x ) = [duration of the journey of the driver that departs at time x ], (5.8)
this means
φ ( x ) + ψ ( x + ℓ ( x ) ) = c \begin{equation}
\varphi(x)+\psi\bigl(x+\ell(x)\bigr)~=~c \tag*{(5.9)}
\end{equation} φ ( x ) + ψ ( x + ℓ ( x ) ) = c (5.9)
for all times x x x at which some driver departs. Differentiating ((5.9) ) one obtains
φ ′ ( x ) + ψ ′ ( x + ℓ ( x ) ) ( 1 + ℓ ′ ( x ) ) = 0 , \begin{equation}
\varphi'(x) +\psi'\bigl(x+\ell(x)\bigr)\bigl(1+\ell'(x)\bigr)~=~0, \tag*{(5.10)}
\end{equation} φ ′ ( x ) + ψ ′ ( x + ℓ ( x ) ) ( 1 + ℓ ′ ( x ) ) = 0 , (5.10)
φ ′ ′ ( x ) + ψ ′ ′ ( x + ℓ ( x ) ) ( 1 + ℓ ′ ( x ) ) 2 + ψ ′ ( x + ℓ ( x ) ) ℓ ′ ′ ( x ) = 0. \begin{equation}
\varphi''(x) +\psi''\bigl(x+\ell(x)\bigr)\bigl(1+\ell'(x)\bigr)^2 + \psi'\bigl(x+\ell(x)\bigr)\ell''(x)~=~0. \tag*{(5.11)}
\end{equation} φ ′′ ( x ) + ψ ′′ ( x + ℓ ( x ) ) ( 1 + ℓ ′ ( x ) ) 2 + ψ ′ ( x + ℓ ( x ) ) ℓ ′′ ( x ) = 0. (5.11)
This yields
ℓ ′ ( x ) = − φ ′ ( x ) ψ ′ ( x + ℓ ( x ) ) − 1 , \begin{equation}
\ell'(x)~=~{-\varphi'(x)\over\psi'\bigl(x+\ell(x)\bigr)} -1, \tag*{(5.12)}
\end{equation} ℓ ′ ( x ) = ψ ′ ( x + ℓ ( x ) ) − φ ′ ( x ) − 1 , (5.12)
ℓ ′ ′ ( x ) = − φ ′ ′ ( x ) + ψ ′ ′ ( x + ℓ ( x ) ) ( 1 + ℓ ′ ( x ) ) 2 ψ ′ ( x + ℓ ( x ) ) ≤ 0. \begin{equation}
\ell''(x)~=~-{ \varphi''(x) +\psi''\bigl(x+\ell(x)\bigr)\bigl(1+\ell'(x)\bigr)^2 \over \psi'\bigl(x+\ell(x)\bigr)}~\leq~0. \tag*{(5.13)}
\end{equation} ℓ ′′ ( x ) = − ψ ′ ( x + ℓ ( x ) ) φ ′′ ( x ) + ψ ′′ ( x + ℓ ( x ) ) ( 1 + ℓ ′ ( x ) ) 2 ≤ 0. (5.13)
Figure 14. The duration of the trip ℓ ( x ) \ell(x) ℓ ( x ) as a function of the departure time. In a Nash equilibrium this is implicitly defined by ((5.9) ). By ((5.13) ) this function is concave down.
Observing that the map x ↦ x + ℓ ( x ) x\mapsto x+\ell(x) x ↦ x + ℓ ( x ) is increasing, and so is ψ ′ \psi' ψ ′ , we conclude that
All departures occur within a time interval [ a , b ] [a,b] [ a , b ] .
One has ℓ ( a ) = ℓ ( b ) = ℓ 0 \ell(a)=\ell(b) = \ell_0 ℓ ( a ) = ℓ ( b ) = ℓ 0 , the constant in ((2.10) ).
There exists x ^ ∈ ] a , b [ \widehat x\in \,]a,b[\, x ∈ ] a , b [ such that the duration ℓ ( x ) \ell(x) ℓ ( x ) of the journey is increasing on [ a , x ^ ] [a, \widehat x] [ a , x ] and decreasing on [ x ^ , b ] [\widehat x, b] [ x , b ] . The driver whose journey lasts longer is the one who arrives at the time x ^ + ℓ ( x ^ ) \widehat x +\ell(\widehat x) x + ℓ ( x ) , characterized by the relation
φ ′ ( x ^ ) + ψ ′ ( x ^ + ℓ ( x ^ ) ) = 0. \varphi'(\widehat x) +\psi'\bigl(\widehat x +\ell(\widehat x)\bigr)~=~0. φ ′ ( x ) + ψ ′ ( x + ℓ ( x ) ) = 0. At the endpoints, by ((5.12) ) we have
ℓ ′ ( a ) = − φ ′ ( a ) ψ ′ ( a + ℓ 0 ) − 1 > 0 , ℓ ′ ( b ) = − φ ′ ( b ) ψ ′ ( b + ℓ 0 ) − 1 < 0. \ell'(a)~=~{-\varphi'(a)\over \psi'(a+ \ell_0 )}-1~>~0,\qquad\qquad \ell'(b)~=~{-\varphi'(b)\over \psi'(b+ \ell_0 )}-1~<~0. ℓ ′ ( a ) = ψ ′ ( a + ℓ 0 ) − φ ′ ( a ) − 1 > 0 , ℓ ′ ( b ) = ψ ′ ( b + ℓ 0 ) − φ ′ ( b ) − 1 < 0.
Figure 15. Left: the function z ( x ) z(x) z ( x ) in ((6.17) ). Right: the characteristics and the car trajectories.
The construction of a Nash equilibrium performed in [17 ] goes as follows. For a fixed constant c c c , let Q c {\cal Q}_c Q c be the family of all bounded, non-decreasing departure distributions
Q ( x ) = ∫ − ∞ x u ˉ ( s ) d s \begin{equation}
Q(x)~=~\int_{-\infty}^x \bar u(s)\, ds \tag*{(5.14)}
\end{equation} Q ( x ) = ∫ − ∞ x u ˉ ( s ) d s (5.14)
for some integrable u ˉ : R ↦ R + \bar u:\mathbb{R}\mapsto\mathbb{R}_+ u ˉ : R ↦ R + , such that the corresponding solution satisfies
φ ( x d ( β ) ) + ψ ( x a ( β ) ) ≤ c for a.e. β ∈ [ 0 , Q ( + ∞ ) ] . \begin{equation}
\varphi(x^d(\beta))+\psi(x^a(\beta))~\leq ~c
\qquad\quad \hbox{for a.e.}~\beta\in [0, ~Q(+\infty)]\,. \tag*{(5.15)}
\end{equation} φ ( x d ( β )) + ψ ( x a ( β )) ≤ c for a.e. β ∈ [ 0 , Q ( + ∞ )] . (5.15)
In other words, Q c {\cal Q}_c Q c is the family of all departure distributions where every driver pays a total cost ≤ c \leq c ≤ c . Then the departure distribution defined as a pointwise maximum:
Q ∗ ( x ) ≐ sup { Q ( x ) ; Q ∈ Q c } \begin{equation}
Q^*(x)~\doteq~\sup\,\Big\{ Q(x)\,;~~Q\in {\cal Q}_c\Big\} \tag*{(5.16)}
\end{equation} Q ∗ ( x ) ≐ sup { Q ( x ) ; Q ∈ Q c } (5.16)
yields a Nash equilibrium.
An example of a Nash equilibrium.
Assume that the flux function satisfies
f ( u ) = u + u 2 2 for all u ∈ [ 0 , 1 ] . \begin{equation}
f(u)~=~u+{u^2\over 2}\qquad\hbox{for all}~u\in [0,1]. \tag*{(5.17)}
\end{equation} f ( u ) = u + 2 u 2 for all u ∈ [ 0 , 1 ] . (5.17)
To construct an explicit example of a smooth Nash equilibrium, we start by defining a departure rate
u ˉ ( x ) = { ε cos x if ∣ x ∣ < π / 2 , 0 if ∣ x ∣ ≥ π / 2. \begin{equation}
\bar u(x)~=~\left\{\begin{array}{cl} \varepsilon\,\cos x\qquad &\hbox{if} \quad |x|<\pi/2,\\[1mm]
0\qquad &\hbox{if} \quad |x|\geq \pi/2.\end{array}\right. \tag*{(5.18)}
\end{equation} u ˉ ( x ) = { ε cos x 0 if ∣ x ∣ < π /2 , if ∣ x ∣ ≥ π /2. (5.18)
Then we construct a departure and an arrival cost such that, with the departure rate u ˉ ( ⋅ ) \bar u(\cdot) u ˉ ( ⋅ ) , all drivers pay the same total cost.
Figure 16. Here y ( x ) y(x) y ( x ) is the arrival time of the driver departing at time x x x , while z ( x ) z(x) z ( x ) is the initial point of the backward characteristic through y ( x ) y(x) y ( x ) .
To fix ideas, let L = 1 L=1 L = 1 be the length of the road. Then the solution to the Cauchy problem ((5.17) )- ((5.18) ) is obtained by the method of characteristics:
u ( 1 , x + 1 + u ˉ ( x ) ) = u ˉ ( x ) , u\bigl(1,\, x+1+\bar u(x)\bigr)~=~\bar u(x), u ( 1 , x + 1 + u ˉ ( x ) ) = u ˉ ( x ) ,
provided that map x ↦ 1 + x + ε cos x x\mapsto 1+x+\varepsilon\cos x x ↦ 1 + x + ε cos x is smoothly invertible. This happens for 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 .
The arrival time y ( x ) y(x) y ( x ) of the driver starting at time x x x is implicitly determined by
∫ − ∞ x u ˉ ( s ) d s = ∫ − ∞ y ( x ) u ( 1 , s ) d s , \begin{equation}
\int_{-\infty}^{x} \bar u(s)\,ds \;=\; \int_{-\infty}^{y(x)} u(1,s)\,ds, \tag*{(5.19)}
\end{equation} ∫ − ∞ x u ˉ ( s ) d s = ∫ − ∞ y ( x ) u ( 1 , s ) d s , (5.19)
Denoting by
w ( ξ ) ≐ ξ + 1 + ε cos ξ w(\xi)\,\doteq\,\xi+1+\varepsilon\cos \xi w ( ξ ) ≐ ξ + 1 + ε cos ξ
the endpoint of the characteristic starting at ξ \xi ξ (see Figure 16 ), since u ( 1 , w ( ξ ) ) = u ˉ ( ξ ) u\bigl( 1, w(\xi)\bigr)=\bar u(\xi) u ( 1 , w ( ξ ) ) = u ˉ ( ξ ) , we have
∫ − ∞ w ( ξ ) u ( 1 , s ) d s = ∫ − ∞ ξ u ˉ ( ζ ) ⋅ d w d ζ d ζ . \begin{equation}
\int_{-\infty}^{w(\xi)} u(1,s)\, ds~=~ \int_{-\infty}^\xi \bar u(\zeta)\cdot {dw\over d\zeta}\, d\zeta. \tag*{(5.20)}
\end{equation} ∫ − ∞ w ( ξ ) u ( 1 , s ) d s = ∫ − ∞ ξ u ˉ ( ζ ) ⋅ d ζ d w d ζ . (5.20)
Calling ξ = z ( x ) \xi =z(x) ξ = z ( x ) the initial point of the backward characteristic through y ( x ) y(x) y ( x ) , so that y ( x ) = w ( ξ ) y(x)= w(\xi) y ( x ) = w ( ξ ) , in the particular case where u ˉ \bar u u ˉ is the function in ((5.18) ), from ((5.19) )-((5.20) ) we obtain
∫ − π / 2 x ε cos s d s = ∫ − π / 2 z ( x ) ε cos s ⋅ ( 1 − ε sin s ) d s , \int_{-\pi/2}^x\varepsilon\cos s\, ds~=~\int_{-\pi/2}^{z(x)} \varepsilon\cos s\cdot (1-\varepsilon\sin s)\, ds\,, ∫ − π /2 x ε cos s d s = ∫ − π /2 z ( x ) ε cos s ⋅ ( 1 − ε sin s ) d s ,
ε ( sin x + 1 ) = ε sin z ( x ) − ε 2 2 sin 2 z ( x ) + ε + ε 2 2 , \varepsilon\bigl(\sin x + 1\bigr)~= ~\varepsilon\sin z(x) - \frac{\varepsilon^{2}}{2}\sin^{2} z(x)
+ \varepsilon + \frac{\varepsilon^{2}}{2}\,, ε ( sin x + 1 ) = ε sin z ( x ) − 2 ε 2 sin 2 z ( x ) + ε + 2 ε 2 ,
This yields a quadratic equation for sin z ( x ) \sin z(x) sin z ( x ) which can then be solved explicitly:
ε 2 sin 2 z ( x ) − sin z ( x ) + ( sin x − ε 2 ) = 0. \begin{equation}
\frac{\varepsilon}{2}\sin^2 z(x) - \sin z(x)
+ \Bigl(\sin x - \frac{\varepsilon}{2}\Bigr) ~=~ 0 . \tag*{(5.21)}
\end{equation} 2 ε sin 2 z ( x ) − sin z ( x ) + ( sin x − 2 ε ) = 0. (5.21)
The root of this equation which lies inside [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] is computed by
sin z ( x ) = 1 − 1 + ε 2 − 2 ε sin x ε , z ( x ) = arcsin ( 1 − 1 + ε 2 − 2 ε sin x ε ) . \begin{equation}
\sin z(x)
\,=\, \frac{1-\sqrt{\,1+\varepsilon^{2}-2\varepsilon\sin x\,}}{\varepsilon}\,,
\qquad
z(x)\,=\,\arcsin\!\left(
\frac{1-\sqrt{\,1+\varepsilon^{2}-2\varepsilon\sin x\,}}{\varepsilon}
\right). \tag*{(5.22)}
\end{equation} sin z ( x ) = ε 1 − 1 + ε 2 − 2 ε sin x , z ( x ) = arcsin ( ε 1 − 1 + ε 2 − 2 ε sin x ) . (5.22)
In turn, the arrival time of the driver departing at time x x x is given by
y ( x ) = z ( x ) + 1 + ε cos z ( x ) . \begin{equation}
y(x)~=~z(x) + 1 + \varepsilon\cos z(x). \tag*{(5.23)}
\end{equation} y ( x ) = z ( x ) + 1 + ε cos z ( x ) . (5.23)
At this stage, any couple of functions φ , ψ \varphi,\psi φ , ψ such that
φ ( x ) + ψ ( y ( x ) ) { = c if ∣ x ∣ ≤ π / 2 , ≥ c if ∣ x ∣ > π / 2 , \varphi(x) + \psi(y(x))~\left\{ \begin{array}{rl} =\,c\quad\hbox{if} ~~|x|\leq \pi/2,\\[1mm]
\geq\,c\quad\hbox{if}~~ |x|> \pi/2,\end{array}\right. φ ( x ) + ψ ( y ( x )) { = c if ∣ x ∣ ≤ π /2 , ≥ c if ∣ x ∣ > π /2 ,
for some constant c c c would yield a Nash equilibrium. For example, we can start by choosing
ψ ( y ) = y for all arrival times y ∈ [ 1 − π 2 , 1 + π 2 ] , \psi(y)= y\qquad \hbox{for all arrival times} \quad y\in \left[1-{\pi\over 2}\,,~1+{\pi\over 2}\right], ψ ( y ) = y for all arrival times y ∈ [ 1 − 2 π , 1 + 2 π ] ,
and then define
φ ( x ) ≐ c − y u ‾ ( x ) ∣ x ∣ ≤ π / 2. \varphi(x)\doteq c-y^{\overline u}(x)\qquad\qquad |x|\leq \pi/2. φ ( x ) ≐ c − y u ( x ) ∣ x ∣ ≤ π /2.
We check that this definition yields a convex function φ \varphi φ . Indeed, when ψ ( x ) = x + c \psi(x)=x+c ψ ( x ) = x + c , by ((5.11) ) it follows
φ ′ ′ ( x ) = − ℓ ′ ′ ( x ) = − y ′ ′ ( x ) . \varphi''(x)~=~-\ell''(x)~=~-y''(x). φ ′′ ( x ) = − ℓ ′′ ( x ) = − y ′′ ( x ) .
It remains to check that
y ′ ′ ( x ) ≤ 0 for all ∣ x ∣ ≤ π / 2. \begin{equation}
y''(x)\leq 0\qquad\hbox{for all}~|x|\leq \pi/2. \tag*{(5.24)}
\end{equation} y ′′ ( x ) ≤ 0 for all ∣ x ∣ ≤ π /2. (5.24)
Calling S = sin z ( x ) S= \sin z(x) S = sin z ( x ) , for ∣ x ∣ < π / 2 |x|< \pi/2 ∣ x ∣ < π /2 we find
y ′ ( x ) = u ˉ ( x ) u ˉ ( z ( x ) ) = cos x cos z ( x ) > 0. y'(x)~=~{\bar u(x)\over\bar u(z(x))} ~=~{\cos x\over\cos z(x)}~>~0. y ′ ( x ) = u ˉ ( z ( x )) u ˉ ( x ) = cos z ( x ) cos x > 0.
Differentiating the balance of mass, we obtain
z ′ ( x ) = cos x cos z ( 1 − ε S ) , y ′ ′ ( x ) = S cos 2 x − sin x cos 2 z ( 1 − ε S ) cos 3 z ( 1 − ε S ) z'(x)= {\cos x\over \cos z(1-\varepsilon S)},\qquad y''(x) ~=~{S\cos^2 x - \sin x \cos^2 z(1-\varepsilon S)\over \cos^3 z(1-\varepsilon S)} z ′ ( x ) = cos z ( 1 − εS ) cos x , y ′′ ( x ) = cos 3 z ( 1 − εS ) S cos 2 x − sin x cos 2 z ( 1 − εS )
Using the identity sin x = S + ε 2 ( 1 − S 2 ) \sin x = S+{\varepsilon\over 2} (1-S^2) sin x = S + 2 ε ( 1 − S 2 ) one obtains
y ′ ′ ( x ) = − ( ε / 4 ) ( 1 − S 2 ) 2 ( 2 − ε S ) cos 3 z ( 1 − ε S ) < 0. y''(x)~=~{-(\varepsilon/4) (1-S^2)^2 (2-\varepsilon S)\over \cos^3 z(1-\varepsilon S)}~<~0. y ′′ ( x ) = cos 3 z ( 1 − εS ) − ( ε /4 ) ( 1 − S 2 ) 2 ( 2 − εS ) < 0.
Analysis of the Nash equilibrium
Let the function ℓ ( x ) \ell(x) ℓ ( x ) in be as in Figure 14 , with
ℓ ( a ) = ℓ ( b ) = ℓ 0 , ℓ ′ ′ ( x ) < 0 for a < x < b . \ell(a)~=~\ell(b)~=~\ell_0, \qquad\qquad \ell''(x)<0 \quad \hbox{for}~~a<x<b. ℓ ( a ) = ℓ ( b ) = ℓ 0 , ℓ ′′ ( x ) < 0 for a < x < b .
Note that there exists a < x ^ < b a<\widehat x<b a < x < b such that
{ ℓ ′ ( x ) ≥ 0 if x ∈ [ a , x ^ ] , ℓ ′ ( x ) ≤ 0 if x ∈ [ x ^ , b ] . \begin{equation}
\left\{\begin{array}{rl} \ell'(x)\geq 0\quad\hbox{if} ~~x\in [a,\widehat x],\\[1mm]
\ell'(x)\leq 0\quad\hbox{if} ~~x\in [\widehat x,b].\end{array}\right. \tag*{(6.1)}
\end{equation} { ℓ ′ ( x ) ≥ 0 if x ∈ [ a , x ] , ℓ ′ ( x ) ≤ 0 if x ∈ [ x , b ] . (6.1)
We need to construct a departure distribution u ( 0 , x ) = u ˉ ( x ) u(0,x)=\bar u(x) u ( 0 , x ) = u ˉ ( x ) supported on the time interval [ a , b ] [a,b] [ a , b ] , where the driver departing at time x x x arrives at time y ( x ) = x + ℓ ( x ) y(x)=x+\ell(x) y ( x ) = x + ℓ ( x ) .
As shown in Figure 15 , call z ( x ) z(x) z ( x ) the initial point of the characteristic reaching y ( x ) y(x) y ( x ) at t = L t=L t = L . We have the two basic equations
{ x + ℓ ( x ) = z ( x ) + L f ′ ( u ˉ ( z ( x ) ) ) , u ˉ ( x ) = ( 1 + ℓ ′ ( x ) ) u ˉ ( z ( x ) ) . \begin{equation}
\left\{\begin{array}{rl} x + \ell(x)&=~z(x) + L f'\bigl(\bar u(z(x))\bigr),\\[2mm] \bar u(x)&=
~\bigl(1+\ell'(x)\bigr) \bar u\bigl(z(x)\bigr).\end{array}\right. \tag*{(6.2)}
\end{equation} { x + ℓ ( x ) u ˉ ( x ) = z ( x ) + L f ′ ( u ˉ ( z ( x )) ) , = ( 1 + ℓ ′ ( x ) ) u ˉ ( z ( x ) ) . (6.2)
The second equation is obtained from the identity
∫ − ∞ x u ( 0 , s ) d s = ∫ − ∞ y ( x ) u ( L , s ) d s . \begin{equation}
\int_{-\infty}^x u(0,s)\, ds~=~\int_{-\infty}^{y(x)} u(L,s)\, ds. \tag*{(6.3)}
\end{equation} ∫ − ∞ x u ( 0 , s ) d s = ∫ − ∞ y ( x ) u ( L , s ) d s . (6.3)
Indeed, differentiating w.r.t. x x x and observing that the solution u u u is constant along characteristics, one obtains
u ( 0 , x ) = y ′ ( x ) u ( L , y ( x ) ) = ( 1 + ℓ ′ ( x ) ) u ( 0 , z ( x ) ) . \begin{equation}
u(0,x)~=~y'(x) u\bigl(L,y(x)\bigr)~=~\bigl(1+\ell'(x)\bigr) u\bigl(0, z(x)\bigr). \tag*{(6.4)}
\end{equation} u ( 0 , x ) = y ′ ( x ) u ( L , y ( x ) ) = ( 1 + ℓ ′ ( x ) ) u ( 0 , z ( x ) ) . (6.4)
If we fix an initial point x 0 ∈ ] a , b [ x_0\in \,]a,b[\, x 0 ∈ ] a , b [ and a value u ( x 0 ) = u 0 u(x_0)=u_0 u ( x 0 ) = u 0 , the two equations in ((6.2) ) yield a sequence of points ( x n , u n ) (x_n, u_n) ( x n , u n ) , with
x n − 1 = z ( x n ) , u n = u ˉ ( x n ) , n ∈ Z . \begin{equation}
x_{n-1}\,=\,z(x_n),\qquad u_n\,=\,\bar u(x_n),\qquad\qquad n\in {\mathbb Z}. \tag*{(6.5)}
\end{equation} x n − 1 = z ( x n ) , u n = u ˉ ( x n ) , n ∈ Z . (6.5)
By ((6.2) ), these can be inductively constructed by
{ x n − 1 + L f ′ ( u n − 1 ) = x n + ℓ ( x n ) , u n − 1 = u n 1 + ℓ ′ ( x n ) , \begin{equation}
\left\{\begin{array}{rl} x_{n-1}+ L f'(u_{n- 1})&\displaystyle=~x_n+ \ell(x_n) \,,\\[4mm]
u_{n-1}&=~ \displaystyle{u_n\over 1+\ell'(x_n)}\,,
\end{array}\right. \tag*{(6.6)}
\end{equation} ⎩ ⎨ ⎧ x n − 1 + L f ′ ( u n − 1 ) u n − 1 = x n + ℓ ( x n ) , = 1 + ℓ ′ ( x n ) u n , (6.6)
Ideally, we seek an initial value u 0 u_0 u 0 such that the above sequence satisfies
{ x n → a , u n → 0 as n → − ∞ , x n → b , u n → 0 as n → + ∞ . \begin{equation}
\left\{ \begin{array}{rl} x_n\to a,\qquad u_n\to 0\qquad\quad &\hbox{as}~~n\to -\infty,\\[1mm]
x_n\to b,\qquad u_n\to 0\qquad\quad &\hbox{as}~~n\to +\infty.\end{array}\right. \tag*{(6.7)}
\end{equation} { x n → a , u n → 0 x n → b , u n → 0 as n → − ∞ , as n → + ∞. (6.7)
Moreover, the sequence ( x n ) n ∈ Z (x_n)_{n\in{\mathbb Z}} ( x n ) n ∈ Z should be monotone increasing.
Figure 17. The construction in Remark 6.1 .
Recalling ((2.10) ), we write the Taylor expansion for f f f at u = 0 u=0 u = 0 and for ℓ \ell ℓ at x = a x=a x = a and at x = b x=b x = b :
f ( u ) = ℓ 0 L u + ω 2 u 2 + O ( 1 ) ⋅ u 3 , ℓ ( x ) = ℓ 0 + c 1 ( x − a ) + O ( 1 ) ⋅ ( x − a ) 2 , ℓ ( x ) = ℓ 0 − c 2 ( x − b ) + O ( 1 ) ⋅ ( x − b ) 2 , \begin{equation}
\begin{array}{rl} f(u)&\displaystyle=~{\ell_0\over L} u + {\omega\over 2} u^2+{\mathcal O}(1) \cdot u^3,
\\[4mm]
\ell(x) &\displaystyle=~\ell_0 + c_1 (x-a) + {\mathcal O}(1)\cdot (x-a)^2,\\[4mm]
\ell(x) &\displaystyle=~\ell_0 - c_2 (x-b) + {\mathcal O}(1)\cdot (x-b)^2,\end{array} \tag*{(6.11)}
\end{equation} f ( u ) ℓ ( x ) ℓ ( x ) = L ℓ 0 u + 2 ω u 2 + O ( 1 ) ⋅ u 3 , = ℓ 0 + c 1 ( x − a ) + O ( 1 ) ⋅ ( x − a ) 2 , = ℓ 0 − c 2 ( x − b ) + O ( 1 ) ⋅ ( x − b ) 2 , (6.11)
for some constants c 1 , c 2 , ω > 0 c_1,c_2,\omega>0 c 1 , c 2 , ω > 0 , c 1 < 1 c_1<1 c 1 < 1 .
Figure 18. A plot of the unstable manifold through ( a , 0 ) (a,0) ( a , 0 ) and the stable manifold through B = ( b , 0 ) B=(b,0) B = ( b , 0 ) . Here we choose φ ( t ) = − t \varphi(t)=-t φ ( t ) = − t , ψ ( t ) = e t \psi(t)=e^t ψ ( t ) = e t , f ( u ) = 1 − 1 − u f(u)= 1- \sqrt{1-u} f ( u ) = 1 − 1 − u , L = 3 L=3 L = 3 , c = 3 c=3 c = 3 .
Inserting ((6.11) ) in ((6.6) ), for x ≈ a x\approx a x ≈ a we obtain
{ x n − 1 ≈ x n + ℓ 0 + c 1 ( x n − a ) − L ℓ 0 L − L ω u n − 1 , u n − 1 ≈ u n 1 + c 1 \begin{equation}
\left\{ \begin{array}{rl} x_{n-1}&\displaystyle\approx x_n + \ell_0 + c_1 (x_n-a) - {L \ell_0\over L} - L \omega\, u_{n-1}\,,
\\[4mm]
u_{n-1}&\displaystyle\approx ~{u_n\over 1 + c_1}\end{array}\right. \tag*{(6.12)}
\end{equation} ⎩ ⎨ ⎧ x n − 1 u n − 1 ≈ x n + ℓ 0 + c 1 ( x n − a ) − L L ℓ 0 − L ω u n − 1 , ≈ 1 + c 1 u n (6.12)
In matrix notation, this can be written as
( x n − a u n ) ≈ ( 1 1 + c 1 L ω 1 + c 1 0 1 + c 1 ) ( x n − 1 − a u n − 1 ) . \begin{equation}
\begin{pmatrix} x_n-a \cr\cr
u_n\end{pmatrix}~\approx~
\begin{pmatrix}{1\over 1+c_1} && {L\omega\over 1+c_1}\cr\cr
0 && 1+c_1\end{pmatrix}\begin{pmatrix} x_{n-1}-a \cr\cr
u_{n-1}\end{pmatrix}. \tag*{(6.13)}
\end{equation} x n − a u n ≈ 1 + c 1 1 0 1 + c 1 L ω 1 + c 1 x n − 1 − a u n − 1 . (6.13)
Similarly, for x ≈ b x\approx b x ≈ b we obtain
{ x n − 1 ≈ x n + ℓ 0 − c 2 ( x n − b ) − L ℓ 0 L − L ω u n − 1 , u n − 1 ≈ u n 1 − c 2 \begin{equation}
\left\{ \begin{array}{rl} x_{n-1}&\displaystyle\approx x_n + \ell_0 - c_2 (x_n-b) - {L \ell_0\over L} - L \omega\, u_{n-1}\,,
\\[4mm]
u_{n-1}&\displaystyle\approx ~{u_n\over 1 - c_2}\end{array}\right. \tag*{(6.14)}
\end{equation} ⎩ ⎨ ⎧ x n − 1 u n − 1 ≈ x n + ℓ 0 − c 2 ( x n − b ) − L L ℓ 0 − L ω u n − 1 , ≈ 1 − c 2 u n (6.14)
In matrix notation, this can be written as
( x n − b u n ) ≈ ( 1 1 − c 2 L ω 1 − c 2 0 1 − c 2 ) ( x n − 1 − b u n − 1 ) . \begin{equation}
\begin{pmatrix} x_n-b \cr\cr
u_n\end{pmatrix}~\approx~
\begin{pmatrix}{1\over 1-c_2} && {L\omega\over 1-c_2}\cr\cr
0 && 1-c_2\end{pmatrix}\begin{pmatrix} x_{n-1}-b \cr\cr
u_{n-1}\end{pmatrix}. \tag*{(6.15)}
\end{equation} x n − b u n ≈ 1 − c 2 1 0 1 − c 2 L ω 1 − c 2 x n − 1 − b u n − 1 . (6.15)
We observe that both matrices in ((6.13) ) and ((6.15) ) have eigenvalues 0 < λ 1 < 1 < λ 2 0<\lambda_1<1<\lambda_2 0 < λ 1 < 1 < λ 2 . Hence the points A = ( a , 0 ) A=(a,0) A = ( a , 0 ) and B = ( b , 0 ) B=(b,0) B = ( b , 0 ) are both saddle points for the discrete dynamics. In a generic setting, we do not expect that the unstable manifold through A A A should coincide with the stable manifold through B B B . A precise result in this direction will be given in Theorem (?) .
If u ˉ ( x ) \bar u(x) u ˉ ( x ) is a departure rate yielding a Nash equilibrium, then for every x ∈ [ a , b ] x\in [a,b] x ∈ [ a , b ] we have
∫ a x u ˉ ( y ) d y = ∫ a + ℓ 0 x + ℓ ( x ) u ( L , ζ ) d ζ . \begin{equation}
\int_a^x \bar u(y)\, dy~=~\int_{a+ \ell_0 }^{x+\ell(x)} u(L,\zeta)\, d\zeta\,. \tag*{(6.16)}
\end{equation} ∫ a x u ˉ ( y ) d y = ∫ a + ℓ 0 x + ℓ ( x ) u ( L , ζ ) d ζ . (6.16)
Indeed, if the driver starting at time x x x arrives at time y ( x ) ≐ x + ℓ ( x ) y(x)\doteq x+\ell(x) y ( x ) ≐ x + ℓ ( x ) , that means that the total number of drivers departing before time x x x is the same as the total number of drivers arriving before time x + ℓ ( x ) x+\ell(x) x + ℓ ( x ) . Assuming that the solution u = u ( t , x ) u=u(t,x) u = u ( t , x ) remains smooth on the entire domain [ 0 , L ] × R [0,L]\times\mathbb{R} [ 0 , L ] × R , the arrival rate u ( L , ⋅ ) u(L,\cdot) u ( L , ⋅ ) can be computed by characteristics. 1. Let z ( x ) z(x) z ( x ) be the initial point of the characteristic that ends at y ( x ) ≐ x + ℓ ( x ) y(x)\doteq x+\ell(x) y ( x ) ≐ x + ℓ ( x ) , so that
z ( x ) = x + ℓ ( x ) − L f ′ ( u ˉ ( z ( x ) ) ) . \begin{equation}
z(x)~=~x+\ell(x)- L\,f'\bigl( \bar u(z(x))\bigr) . \tag*{(6.17)}
\end{equation} z ( x ) = x + ℓ ( x ) − L f ′ ( u ˉ ( z ( x )) ) . (6.17)
Applying the divergence theorem to the triangular region with vertices at ( 0 , z ( x ) ) (0,z(x)) ( 0 , z ( x )) , ( 0 , x ) (0,x) ( 0 , x ) and ( L , y ( x ) ) (L, y(x)) ( L , y ( x )) (see Figure 15 , right), we obtain
∫ z ( x ) x u ˉ ( s ) d s = L [ f ′ ( u ˉ ( z ( x ) ) ) u ˉ ( z ( x ) ) − f ( u ˉ ( z ( x ) ) ) ] . \begin{equation}
\int_{z(x)}^x \bar u(s)\, ds~=~L \Big[f'\bigl(\bar u(z(x))\bigr) \bar u(z(x))- f\bigl(\bar u(z(x))\bigr) \Big]. \tag*{(6.18)}
\end{equation} ∫ z ( x ) x u ˉ ( s ) d s = L [ f ′ ( u ˉ ( z ( x )) ) u ˉ ( z ( x )) − f ( u ˉ ( z ( x )) ) ] . (6.18)
Indeed, the flux across the car trajectory starting at x x x vanishes identically. 2. Solving the conservation law by characteristics, we find that the gradient satisfies
d d t u x ( t , x ( t ) ) = − f ′ ′ ( u ˉ ( x ( 0 ) ) ) u x 2 ( t , x ( t ) ) , d d t x ( t ) = f ′ ( u ) . {d\over dt} u_x(t, x(t))~=~- f''\bigl(\bar u(x(0))\bigr) u_x^2\bigl(t, x(t)\bigr),\qquad\qquad {d\over dt} x(t)~=~f'(u). d t d u x ( t , x ( t )) = − f ′′ ( u ˉ ( x ( 0 )) ) u x 2 ( t , x ( t ) ) , d t d x ( t ) = f ′ ( u ) .
u x ( t , x ( t ) ) = u ˉ x ( x ( 0 ) ) 1 + t f ′ ′ ( u ˉ ( x ( 0 ) ) ) u ˉ x ( x ( 0 ) ) t ∈ [ 0 , L ] . \begin{equation}
u_x(t, x(t))~=~{ \bar u_x(x(0))\over 1+ t f''\bigl(\bar u(x(0))\bigr) \bar u_x(x(0))}\qquad\qquad t\in [0,L]. \tag*{(6.19)}
\end{equation} u x ( t , x ( t )) = 1 + t f ′′ ( u ˉ ( x ( 0 )) ) u ˉ x ( x ( 0 )) u ˉ x ( x ( 0 )) t ∈ [ 0 , L ] . (6.19)
In particular, the density of arrivals at the time y ( x ) y(x) y ( x ) satisfies
u x ( L , y ( x ) ) = u ˉ x ( z ( x ) ) 1 + L f ′ ′ ( u ˉ ( z ( x ) ) ) u ˉ x ( z ( x ) ) . \begin{equation}
u_x(L, y(x))~=~{ \bar u_x(z(x)) \over 1+ L f''\bigl(\bar u(z(x))\bigr) \, \bar u_x(z(x))}\,. \tag*{(6.20)}
\end{equation} u x ( L , y ( x )) = 1 + L f ′′ ( u ˉ ( z ( x )) ) u ˉ x ( z ( x )) u ˉ x ( z ( x )) . (6.20)
3. Differentiating ((6.17) ) w.r.t. x x x , one obtains
z ′ ( x ) = 1 + ℓ ′ ( x ) − L f ′ ′ ( u ˉ ( z ( x ) ) ) u ˉ x ( z ( x ) ) z ′ ( x ) , \begin{equation}
z'(x)~=~1+\ell'(x) - L f''\bigl(\bar u(z(x))\bigr)\, \bar u_x(z(x))\, z'(x), \tag*{(6.21)}
\end{equation} z ′ ( x ) = 1 + ℓ ′ ( x ) − L f ′′ ( u ˉ ( z ( x )) ) u ˉ x ( z ( x )) z ′ ( x ) , (6.21)
z ′ ( x ) = 1 + ℓ ′ ( x ) 1 + L f ′ ′ ( u ˉ ( z ( x ) ) ) u ˉ x ( z ( x ) ) . \begin{equation}
z'(x)~=~{1+\ell'(x)\over 1+ L f''\bigl(\bar u(z(x))\bigr) \bar u_x(z(x))}\,. \tag*{(6.22)}
\end{equation} z ′ ( x ) = 1 + L f ′′ ( u ˉ ( z ( x )) ) u ˉ x ( z ( x )) 1 + ℓ ′ ( x ) . (6.22)
On the other hand, differentiating ((6.18) ) we find
u ˉ ( x ) − u ˉ ( z ( x ) ) z ′ ( x ) = L f ′ ′ ( u ˉ ( z ( x ) ) ) u ˉ x ( z ( x ) ) u ˉ ( z ( x ) ) z ′ ( x ) , \bar u(x) -\bar u(z(x)) z'(x) ~=~L f''(\bar u(z(x))) \bar u_x(z(x)) \bar u (z(x)) z'(x), u ˉ ( x ) − u ˉ ( z ( x )) z ′ ( x ) = L f ′′ ( u ˉ ( z ( x ))) u ˉ x ( z ( x )) u ˉ ( z ( x )) z ′ ( x ) ,
u ˉ ( x ) = [ 1 + L f ′ ′ ( u ˉ ( z ( x ) ) ) u ˉ x ( z ( x ) ) ] u ˉ ( z ( x ) ) ⋅ z ′ ( x ) = ( 1 + ℓ ′ ( x ) ) u ˉ ( z ( x ) ) . \begin{equation}
\bar u(x)~=~ \Big[1+ L f''\bigl( \bar u(z(x))\bigr) \,\bar u_x(z(x)) \Big] \bar u(z(x))\cdot z'(x)~=~
(1+\ell'(x))\, \bar u(z(x)). \tag*{(6.23)}
\end{equation} u ˉ ( x ) = [ 1 + L f ′′ ( u ˉ ( z ( x )) ) u ˉ x ( z ( x )) ] u ˉ ( z ( x )) ⋅ z ′ ( x ) = ( 1 + ℓ ′ ( x )) u ˉ ( z ( x )) . (6.23)
4. We now analyze what happens at the endpoints of the interval [ a , b ] [a,b] [ a , b ] . At x = a x=a x = a or x = b x=b x = b we have u ˉ = 0 \bar u=0 u ˉ = 0 . Therefore
u x ( L , a + ℓ 0 ) = α ~ ≐ 1 f ′ ′ ( 0 ) L + 1 α , u x ( L , b + ℓ 0 ) = β ~ ≐ 1 f ′ ′ ( 0 ) L + 1 β . u_x(L,a + \ell_0)~=~\widetilde\alpha~\doteq~{1\over f''(0) L+{1\over \alpha}},\qquad\qquad u_x(L,b + \ell_0)
~=~\widetilde\beta~\doteq~{1\over f''(0) L+{1\over \beta}}. u x ( L , a + ℓ 0 ) = α ≐ f ′′ ( 0 ) L + α 1 1 , u x ( L , b + ℓ 0 ) = β ≐ f ′′ ( 0 ) L + β 1 1 .
At x = a x=a x = a we have
z ( a ) = a , u ˉ ( a ) = 0 , z ′ ( a ) = 1 + ℓ ′ ( a ) 1 + L f ′ ′ ( 0 ) u ˉ x ( a ) . \begin{equation}
z(a)\,=\,a,\qquad \bar u(a)\,=\,0,\qquad \qquad z'(a)~=~{1+\ell'(a) \over 1+ L f''(0) \bar u_x(a)}\,. \tag*{(6.24)}
\end{equation} z ( a ) = a , u ˉ ( a ) = 0 , z ′ ( a ) = 1 + L f ′′ ( 0 ) u ˉ x ( a ) 1 + ℓ ′ ( a ) . (6.24)
Indeed, the first identity is clear, because the first driver encounters no traffic, hence travels with characteristic speed: ℓ ( a ) = ℓ 0 \ell(a)= \ell_0 ℓ ( a ) = ℓ 0 . The second identity follows by ((6.23) ), because ℓ ′ ( x ) ≠ 0 \ell'(x)\not= 0 ℓ ′ ( x ) = 0 . The third identity follows by ((6.22) ). Differentiating ((6.23) ) one obtains
u ˉ x ( a ) = ( 1 + ℓ ′ ( a ) ) u ˉ x ( a ) z ′ ( a ) , z ′ ( a ) = 1 1 + ℓ ′ ( a ) < 1 , \begin{equation}
\bar u_x(a)~=~(1+\ell'(a)) \bar u_x(a) z'(a),\qquad\qquad z'(a)~=~{1\over 1+\ell'(a)}~<~1, \tag*{(6.25)}
\end{equation} u ˉ x ( a ) = ( 1 + ℓ ′ ( a )) u ˉ x ( a ) z ′ ( a ) , z ′ ( a ) = 1 + ℓ ′ ( a ) 1 < 1 , (6.25)
1 + L f ′ ′ ( 0 ) u ˉ x ( a ) = 1 + ℓ ′ ( a ) z ′ ( a ) , u ˉ x ( a ) = ( 1 + ℓ ′ ( a ) ) 2 − 1 L f ′ ′ ( 0 ) > 0 . \begin{equation}
1+ L f''(0)\bar u_x(a) ~=~{1+\ell'(a)\over z'(a)},\qquad\qquad \bar u_x(a)~=~{(1+\ell'(a))^2-1\over L f''(0)}~>~0\,. \tag*{(6.26)}
\end{equation} 1 + L f ′′ ( 0 ) u ˉ x ( a ) = z ′ ( a ) 1 + ℓ ′ ( a ) , u ˉ x ( a ) = L f ′′ ( 0 ) ( 1 + ℓ ′ ( a ) ) 2 − 1 > 0 . (6.26)
Similarly, at x = b x=b x = b we have
u ˉ ( b ) = 0 , z ( b ) = b , z ′ ( b ) = 1 + ℓ ′ ( b ) 1 + L f ′ ′ ( 0 ) u ˉ x ( b ) . \bar u(b)\,=\,0,\qquad z(b)\,=\,b,\qquad\qquad z'(b)~=~{1+\ell'(b) \over 1+ L f''(0) \bar u_x(b)}\,. u ˉ ( b ) = 0 , z ( b ) = b , z ′ ( b ) = 1 + L f ′′ ( 0 ) u ˉ x ( b ) 1 + ℓ ′ ( b ) .
Differentiating ((6.23) ) one obtains
z ′ ( b ) = 1 1 + ℓ ′ ( b ) > 1 , u ˉ x ( b ) = ( 1 + ℓ ′ ( b ) ) 2 − 1 L f ′ ′ ( 0 ) < 0 . \begin{equation}
z'(b)~=~{1\over 1+\ell'(b)}~>~1,\qquad\qquad
\bar u_x(b)~=~{(1+\ell'(b))^2-1\over L f''(0)}~<~0\,. \tag*{(6.27)}
\end{equation} z ′ ( b ) = 1 + ℓ ′ ( b ) 1 > 1 , u ˉ x ( b ) = L f ′′ ( 0 ) ( 1 + ℓ ′ ( b ) ) 2 − 1 < 0 . (6.27)
Figure 19. Left: if x ♯ x^\sharp x ♯ is a point where a jump in the Nash departure rate occurs, then two distinct characteristics should meet at the arrival time y ( x ♯ ) y(x^\sharp) y ( x ♯ ) . Right: the initial points z 1 < z 2 z_1<z_2 z 1 < z 2 of these two characteristics correspond to the points where the function at ((6.31) ) is tangent to the graph of the integrated function U ‾ \overline U U .
Calling x ♯ ∈ ] x ^ , b [ x^\sharp\in \,]\widehat x, b[\, x ♯ ∈ ] x , b [ the position of this first shock, as shown in Figure 19 , left, there should be two distinct characteristics reaching y u ˉ ( x ♯ ) y^{\bar u}(x^\sharp) y u ˉ ( x ♯ ) , starting from two points
z 1 u ˉ ( x ♯ ) < z 2 u ˉ ( x ♯ ) . \begin{equation}
z^{\bar u}_1(x^\sharp)~<~z^{\bar u}_2(x^\sharp). \tag*{(6.28)}
\end{equation} z 1 u ˉ ( x ♯ ) < z 2 u ˉ ( x ♯ ) . (6.28)
This is the case if
z 1 u ˉ ( x ♯ ) + L f ′ ( u ˉ ( z 1 u ˉ ( x ♯ ) ) ) = z 2 u ˉ ( x ♯ ) + L f ′ ( u ˉ ( z 2 u ˉ ( x ♯ ) ) ) . \begin{equation}
z^{\bar u}_1(x^\sharp)+ L f' \Big(\bar u \big(z^{\bar u}_1(x^\sharp)\bigr)\Big)
~=~ z^{\bar u}_2(x^\sharp)+ L f' \Big(\bar u \big(z^{\bar u}_2(x^\sharp)\bigr)\Big). \tag*{(6.29)}
\end{equation} z 1 u ˉ ( x ♯ ) + L f ′ ( u ˉ ( z 1 u ˉ ( x ♯ ) ) ) = z 2 u ˉ ( x ♯ ) + L f ′ ( u ˉ ( z 2 u ˉ ( x ♯ ) ) ) . (6.29)
In addition, applying the divergence theorem on the triangle with vertices ( 0 , z 1 ) (0, z_1) ( 0 , z 1 ) , ( 0 , z 2 ) (0, z_2) ( 0 , z 2 ) and ( L , y ) (L,y) ( L , y ) , one obtains the identity
∫ z 1 z 2 u ˉ ( x ) d x = L [ u ˉ ( z 1 ) f ′ ( u ˉ ( z 1 ) ) − f ( u ˉ ( z 1 ) ) ] − L [ u ˉ ( z 2 ) f ′ ( u ˉ ( z 2 ) ) − f ( u ˉ ( z 2 ) ) ] . \begin{equation}
\int_{z_1}^{z_2} \bar u(x)\, dx~=~L\Big[ \bar u(z_1) f' \bigl(\bar u(z_1)\bigr)- f\bigl(\bar u(z_1)\bigr) \Big]
- L\Big[\bar u(z_2) f' \bigl(\bar u(z_2)\bigr)- f\bigl(\bar u(z_2)\bigr) \Big]. \tag*{(6.30)}
\end{equation} ∫ z 1 z 2 u ˉ ( x ) d x = L [ u ˉ ( z 1 ) f ′ ( u ˉ ( z 1 ) ) − f ( u ˉ ( z 1 ) ) ] − L [ u ˉ ( z 2 ) f ′ ( u ˉ ( z 2 ) ) − f ( u ˉ ( z 2 ) ) ] . (6.30)
In terms of the integrated function U ‾ \overline U U in ((2.21) ), this means that the function
s ↦ U ‾ ( x ♯ ) + h ( s − y u ˉ x ♯ ) ) \begin{equation}
s~\mapsto ~\overline U(x^\sharp) +h(s-y^{\bar u} x^\sharp)\bigr) \tag*{(6.31)}
\end{equation} s ↦ U ( x ♯ ) + h ( s − y u ˉ x ♯ ) ) (6.31)
is tangent from below to the graph of U ‾ \overline U U at the two distinct points ((6.28) ).
Emergence of a queue
Let the departure and arrival cost functions φ , ψ \varphi, \psi φ , ψ be given, as in (A2).
Let ρ \rho ρ be the density of cars, and let ρ v ( ρ ) \rho v(\rho) ρ v ( ρ ) be the flux function. Set
v 0 = v ( 0 ) , v ∗ = v ( ρ ∗ ) , v_0 = v(0),\qquad v^* = v(\rho^*), v 0 = v ( 0 ) , v ∗ = v ( ρ ∗ ) ,
where
ρ ∗ = arg max ρ ρ v ( ρ ) \rho^*\,=\,\hbox{arg}\!\max_\rho \rho v(\rho) ρ ∗ = arg ρ max ρ v ( ρ )
is the density which yields the maximum possible flux.
Moreover, set L L L = length of the road, κ = \kappa= κ = total number of drivers.
Proposition. There exist κ + > κ − > 0 \kappa^+>\kappa^->0 κ + > κ − > 0 such that:
Proof. 1. In this first step we claim that, if the total amount of cars κ \kappa κ is sufficiently large, then a queue must form at the entrance of the road.
Indeed, observe that the car speed is bounded above and below:
v ( t , x ) ∈ [ v ∗ , v 0 ] . v(t,x)~\in~[v^*, v_0]. v ( t , x ) ∈ [ v ∗ , v 0 ] .
Hence the travel time by any driver satisfies
T ∈ [ L v 0 , L v ∗ ] . T~\in~\left[ {L\over v_0}\,,~{L\over v^*}\right]. T ∈ [ v 0 L , v ∗ L ] .
By the assumptions (A2), there exists a departure time x 0 x_0 x 0 such that
x 0 = arg min x ∈ R { φ ( x ) + ψ ( x + L v ∗ ) } . \begin{equation}
x_0~=~\hbox{arg}\!\min_{x\in \mathbb{R}} \left\{ \varphi(x) + \psi\Big(x+{L\over v^*} \Big)\right\}. \tag*{(7.1)}
\end{equation} x 0 = arg x ∈ R min { φ ( x ) + ψ ( x + v ∗ L ) } . (7.1)
Any driver can choose to depart at time x 0 x_0 x 0 . If no queue is present, this driver will immediately enter the highway, without having to wait. In this case, he will arrive at time x a r r i v a l ≤ x 0 + L v ∗ x^{arrival} \leq x_0 +{L\over v^*} x a r r i v a l ≤ x 0 + v ∗ L . Hence his total cost will be
Φ ( x 0 ) ≤ C 0 ≐ φ ( x 0 ) + ψ ( x 0 + L v ∗ ) . \Phi(x_0)~\leq~C_0\doteq ~ \varphi(x_0) + \psi\Big(x_0+{L\over v^*} \Big). Φ ( x 0 ) ≤ C 0 ≐ φ ( x 0 ) + ψ ( x 0 + v ∗ L ) .
On the other hand, still by (A2), we can choose a constant K K K large enough so that
φ ( x ) + ψ ( x + L v 0 ) > C 0 for all x ∉ [ − K , K ] . \varphi(x)+ \psi\Big(x+{L\over v_0} \Big)~>C_0\qquad\qquad\hbox{for all}~x\notin [-K, K]. φ ( x ) + ψ ( x + v 0 L ) > C 0 for all x ∈ / [ − K , K ] .
That means: every driver who departs at a time x ∉ [ − K , K ] x\notin [-K, K] x ∈ / [ − K , K ] must pay a total cost > C 0 > C_0 > C 0 . This implies that in a Nash equilibrium all drivers must depart at a time x ∈ [ − K , K ] x\in [ -K,K] x ∈ [ − K , K ] .
But if the total number of drivers κ \kappa κ satisfies
κ > κ + ≐ 2 K ρ ∗ v ( ρ ∗ ) , \begin{equation}
\kappa~>~\kappa^+~\doteq~2K \rho^*v(\rho^*), \tag*{(7.2)}
\end{equation} κ > κ + ≐ 2 K ρ ∗ v ( ρ ∗ ) , (7.2)
this is not possible. Since the maximum flux at the entrance of the highway is M = ρ ∗ v ( ρ ∗ ) M=\rho^* v(\rho^*) M = ρ ∗ v ( ρ ∗ ) , the right hand side is the maximum number of drivers that can depart during a time interval of length 2 K 2K 2 K . We thus reached a contradiction. 2. By the previous step, if ((7.2) ) holds the flux u ˉ ( x ) \bar u(x) u ˉ ( x ) entering the highway reaches the maximum value M = ρ ∗ v ( ρ ∗ ) M=
\rho^* v(\rho^*) M = ρ ∗ v ( ρ ∗ ) at some time x ˉ \bar x x ˉ (see Figure 20 ). Consider the time
x ♯ ≐ sup { x ≥ x ˉ ; u ˉ ( x ) = M } . x^\sharp~\doteq~\sup~\bigl\{ x\geq \bar x\,;~\bar u(x)= M\bigr\}. x ♯ ≐ sup { x ≥ x ˉ ; u ˉ ( x ) = M } .
Since the characteristic speed satisfies f ′ ( M ) = + ∞ f'(M)=+\infty f ′ ( M ) = + ∞ , as shown in Figure 21 this implies that the solution contains a shock, originating at the point x ♯ x^\sharp x ♯ . This proves part (i) of the Proposition.
Figure 20. A departure rate in a Nash equilibrium. The dashed curve is the rate at which drivers start their journey, possibly joining the queue at the entrance of the highway. The solid curve is the flux of cars entering the highway. The queue is formed at time x ˉ \bar x x ˉ and depleted at time x ♯ x^\sharp x ♯ . The departure rate has downward jumps at points x 1 ♯ < x 2 ♯ < ⋯ x_1^\sharp<x_2^\sharp<\cdots x 1 ♯ < x 2 ♯ < ⋯ , determined as in Figure 21 .
Figure 21. The characteristic lines in the solution with initial data u ˉ \bar u u ˉ = flux entering the highway at time x x x , as in Figure 20 . Here a queue is formed at time x ‾ \overline x x and depleted at time x ♯ x^\sharp x ♯ . At time x ♯ x^\sharp x ♯ a shock is formed, moving along the curve γ \gamma γ . Here x 1 ♯ x_1^\sharp x 1 ♯ is the departure time of the driver whose arrival time y ( x 1 ♯ ) y(x_1^\sharp) y ( x 1 ♯ ) coincides with the terminal point along the shock. By the necessary conditions ((6.23) ), that the departure rate has a downward jump at a point x 1 ♯ x_1^\sharp x 1 ♯ . Hence a second shock initiates at this point. By induction, if γ j \gamma_j γ j is the shock curve starting at x j ♯ x_j^\sharp x j ♯ , let x j + 1 ♯ x_{j+1}^\sharp x j + 1 ♯ be the departure time of the driver whose arrival time y ( x j + 1 ♯ ) y(x_{j+1}^\sharp) y ( x j + 1 ♯ ) coincides with the terminal point along γ j \gamma_j γ j . By ((6.23) ) the departure rate has a further downward jump at a point x j + 1 ♯ x_{j+1}^\sharp x j + 1 ♯ .
3. To prove (ii) we observe that the formula ((2.28) ) for the arrival time implies the sharper uniform bound on the travel time:
ℓ 0 ≤ y u ˉ ( x ) − x ≤ h ∗ ( κ ) . \ell_0~\le~ y^{\bar u}(x)-x~\le ~h^*(\kappa). ℓ 0 ≤ y u ˉ ( x ) − x ≤ h ∗ ( κ ) .
Since h ∗ ( κ ) → ℓ 0 h^*(\kappa)\to\ell_0 h ∗ ( κ ) → ℓ 0 as κ ↓ 0 \kappa\downarrow 0 κ ↓ 0 , we have
0 ≤ Φ u ˉ ( x ) − Φ 0 ( x ) ≤ L ψ ( h ∗ ( κ ) − ℓ 0 ) → 0. 0~\le~\Phi^{\bar u}(x)-\Phi^0(x)
~\le ~L_\psi\bigl(h^*(\kappa)-\ell_0\bigr)~\to~0. 0 ≤ Φ u ˉ ( x ) − Φ 0 ( x ) ≤ L ψ ( h ∗ ( κ ) − ℓ 0 ) → 0.
The common cost to all drivers in the Nash equilibrium is the global minimum of Φ u ˉ \Phi^{\bar u} Φ u ˉ , so
min Φ 0 ≤ c ( κ ) ≤ min Φ 0 + L ψ ( h ∗ ( κ ) − ℓ 0 ) . \min\Phi^0\le c(\kappa)
\le\min\Phi^0+L_\psi\bigl(h^*(\kappa)-\ell_0\bigr). min Φ 0 ≤ c ( κ ) ≤ min Φ 0 + L ψ ( h ∗ ( κ ) − ℓ 0 ) .
By the strict convexity and the coercivity, the function Φ 0 \Phi^0 Φ 0 has a unique minimizer x 0 x_0 x 0 . As κ ↓ 0 \kappa\downarrow 0 κ ↓ 0 , the support of u ˉ \bar u u ˉ (i.e., the set of times when some driver actually departs) must be contained in a small neighborhood of x 0 x_0 x 0 . All the arrival times lie near x 0 + ℓ 0 x_0+\ell_0 x 0 + ℓ 0 .
The Oleinik estimate yields u ( L , s 2 ) − u ( L , s 1 ) ≤ ( s 2 − s 1 ) / ( ω 0 L ) u(L, s_2)-u(L,s_1)\le(s_2-s_1)/(\omega_0 L) u ( L , s 2 ) − u ( L , s 1 ) ≤ ( s 2 − s 1 ) / ( ω 0 L ) . If u ( L , s ) = r > 0 u(L,s)=r>0 u ( L , s ) = r > 0 , then
u ( L , s − h ) ≥ r − h ω 0 L , 0 ≤ h ≤ r ω 0 L . u(L, s-h)~\ge ~r-\frac{h}{\omega_0 L},\qquad
0\le h\le r\omega_0 L. u ( L , s − h ) ≥ r − ω 0 L h , 0 ≤ h ≤ r ω 0 L .
Integrating both sides of this inequality, since ∫ u ( L , s ) d s = κ \int u(L,s)\, ds=\kappa ∫ u ( L , s ) d s = κ we obtain
∥ u ( L , ⋅ ) ∥ L ∞ ≤ 2 κ ω 0 L . \bigl\|u(L,\cdot)\bigr\|_{{\bf L}^\infty}~\le~\sqrt{\frac{2\kappa}{\omega_0 L}}\,. u ( L , ⋅ ) L ∞ ≤ ω 0 L 2 κ .
On the support of the departure rate u ˉ \bar u u ˉ , the derivative y ′ ( x ) = − φ ′ ( x ) / ψ ′ ( y ( x ) ) y'(x)= -\varphi'(x)/\psi'(y(x)) y ′ ( x ) = − φ ′ ( x ) / ψ ′ ( y ( x )) is bounded by a constant R 0 R_0 R 0 , uniformly valid for all κ > 0 \kappa>0 κ > 0 sufficiently small. Recalling ((6.4) ) one obtains
u ˉ ( x ) = y ′ ( x ) u ( L , y ( x ) ) ≤ R 0 2 κ ω 0 L a.e. \bar u(x)~=~y'(x)u(L,y(x))~
\le ~R_0\sqrt{\frac{2\kappa}{\omega_0L}}
\quad\text{a.e.} u ˉ ( x ) = y ′ ( x ) u ( L , y ( x )) ≤ R 0 ω 0 L 2 κ a.e.
By choosing
κ < M 2 ω 0 L 2 R 0 2 \kappa\,<\,\frac{M^2\omega_0L}{2R_0^2} κ < 2 R 0 2 M 2 ω 0 L
the above inequality yields u ˉ ( x ) < M \bar u(x)<M u ˉ ( x ) < M showing that the departure rate must be < M < M < M almost everywhere. Hence no queue forms at the entrance of the highway.
We observe that Part (ii) does not rule out the presence of a shock in the solution.
Generic failure of regularity of the Nash equilibrium
Let u ˉ \bar u u ˉ be the departure rate in a Nash equilibrium where each driver pays the same total cost c c c . In this setting, the total number of drivers depends on c c c . It is strictly positive as soon as
c > min x ∈ R φ ( x ) + ψ ( x + ℓ 0 ) . \begin{equation}
c~>~\min_{x \in \mathbb{R}}\varphi(x) + \psi (x+\ell_0). \tag*{(8.1)}
\end{equation} c > x ∈ R min φ ( x ) + ψ ( x + ℓ 0 ) . (8.1)
As before, for every x ∈ [ a , b ] x \in [a,b] x ∈ [ a , b ] we denote by y ( x ) = x + ℓ ( x ) y(x)=x+\ell(x) y ( x ) = x + ℓ ( x ) the arrival time of the driver starting at time x x x . According to ((5.9) ), this function is implicitly defined by the identity
φ ( x ) + ψ ( y ( x ) ) = c for all x ∈ [ a , b ] . \begin{equation}
\varphi(x) + \psi\bigl(y(x)\bigr)\,=\,c\qquad \hbox{for all}~x\in [a,b]. \tag*{(8.2)}
\end{equation} φ ( x ) + ψ ( y ( x ) ) = c for all x ∈ [ a , b ] . (8.2)
Notice that under the assumptions (A2), we have that y ( x ) = ψ − 1 ( c − φ ( x ) ) y(x)= \psi^{-1}(c-\varphi(x)) y ( x ) = ψ − 1 ( c − φ ( x )) is a C 2 {\mathcal C}^2 C 2 concave function, with C 2 {\mathcal C}^2 C 2 inverse.
In this section we prove two main results: the first states the one-sided Lipschitz regularity of u ˉ \bar u u ˉ , the second states that Nash equilibria are generically not continuous.
Theorem. Let f , φ , ψ f, \varphi, \psi f , φ , ψ be as in (A1)-(A2) and, for a given c c c as in ((8.1) ), let u ˉ \bar u u ˉ be the Nash equilibrium departure rate where every driver has the same total cost c c c . Then u ˉ \bar u u ˉ is bounded with compact support. Moreover, the following one-sided Lipschitz estimate holds: u ˉ ( x 2 ) − u ˉ ( x 1 ) ≤ ( M ∥ y ′ ′ ∥ L ∞ + 1 ω 0 L ∥ y ′ ∥ L ∞ 2 ) ( x 2 − x 1 ) for a.e. x 1 < x 2 .
\bar u(x_2)-\bar u (x_1)~ \le~ \left(M\|y''\|_{{\bf L}^\infty} + {1\over \omega_0 L} \|y'\|^2_{{\bf L}^\infty}\right)(x_2-x_1) \qquad \text{for a.e. } x_1<x_2.
u ˉ ( x 2 ) − u ˉ ( x 1 ) ≤ ( M ∥ y ′′ ∥ L ∞ + ω 0 L 1 ∥ y ′ ∥ L ∞ 2 ) ( x 2 − x 1 ) for a.e. x 1 < x 2 . where ω 0 \omega_0 ω 0 is the constant in ((2.2) ).
Proof. For any x ˉ ∈ [ a , b ] \bar x\in [a,b] x ˉ ∈ [ a , b ] and δ > 0 \delta>0 δ > 0 , one has
U ‾ ( x ˉ + δ ) − U ‾ ( x ˉ ) = ∫ y ( x ˉ ) y ( x ˉ + δ ) u ( L , x ) d x . \begin{equation}
\overline U(\bar x + \delta) - \overline U(\bar x) ~= ~\int_{y(\bar x)}^{y(\bar x + \delta)}u(L,x) dx. \tag*{(8.4)}
\end{equation} U ( x ˉ + δ ) − U ( x ˉ ) = ∫ y ( x ˉ ) y ( x ˉ + δ ) u ( L , x ) d x . (8.4)
Since u ( L , x ) ≤ M u(L,x)\leq M u ( L , x ) ≤ M for all x x x , this implies that U ‾ \overline U U is Lipschitz and
0 ≤ U ‾ x ( x ) ≤ M ∥ y ′ ∥ L ∞ for all x ∈ [ a , b ] . 0~\leq~\overline U_x(x) ~\leq~M\, \|y'\|_{{\bf L}^\infty}\qquad\hbox{for all}~\quad x \in [a,b]. 0 ≤ U x ( x ) ≤ M ∥ y ′ ∥ L ∞ for all x ∈ [ a , b ] .
Since u u u solves the conservation law ((2.1) ) with strictly convex flux, by Oleinik’s one-sided Lipschitz estimate, for every x ∈ R x \in \mathbb{R} x ∈ R it holds
u ( L , y ( x + δ ) ) − u ( L , y ( x ) ) ≤ y ( x + δ ) − y ( x ) ω 0 L ≤ ∥ y ′ ∥ L ∞ ω 0 L δ . u\bigl(L,y( x +\delta)\bigr)-u\bigl(L,y( x)\bigr) ~\le~ { y( x +\delta)-y( x)\over \omega_0 L}~ \le~ \frac{\|y'\|_{{\bf L}^\infty}}{\omega_0 L} \delta. u ( L , y ( x + δ ) ) − u ( L , y ( x ) ) ≤ ω 0 L y ( x + δ ) − y ( x ) ≤ ω 0 L ∥ y ′ ∥ L ∞ δ .
Differentiating (8.4) w.r.t. x ˉ \bar x x ˉ , we obtain
( U ‾ ( x ˉ + δ ) − U ‾ ( x ˉ ) δ ) ′ ≤ 1 δ ( u ( L , y ( x ˉ + δ ) ) y ′ ( x ˉ + δ ) − u ( L , y ( x ˉ ) ) y ′ ( x ˉ ) ) = 1 δ ( u ( L , y ( x ˉ + δ ) ) y ′ ( x ˉ + δ ) − u ( L , y ( x ˉ + δ ) ) y ′ ( x ˉ ) ) + 1 δ ( u ( L , y ( x ˉ + δ ) ) y ′ ( x ˉ ) − u ( L , y ( x ˉ ) ) y ′ ( x ˉ ) ) ≤ M ∥ y ′ ′ ∥ L ∞ + ∥ y ′ ∥ L ∞ 2 1 ω 0 L . \begin{array}{rl}
\displaystyle\left( \frac{\overline U(\bar x + \delta)-\overline U(\bar x)}\delta\right)' & \le ~\displaystyle\frac1\delta\Big(u\bigl(L,y(\bar x + \delta)\bigr)y'(\bar x + \delta) - u\bigl(L,y(\bar x)\bigr)y'(\bar x)\Big) \\[4mm]
&\displaystyle=~ \frac1\delta\Big(u(L,y(\bar x + \delta))y'(\bar x + \delta) - u(L,y(\bar x + \delta))y'(\bar x)\Big)\\[4mm]
&\qquad \displaystyle+ {1\over\delta}\Big(u(L,y(\bar x + \delta))y'(\bar x)- u(L,y(\bar x))y'(\bar x) \Big)\\[4mm]
&\displaystyle\le ~ M \|y''\|_{{\bf L}^\infty} + \|y'\|_{{\bf L}^\infty}^2{1\over \omega_0 L}\,.
\end{array} ( δ U ( x ˉ + δ ) − U ( x ˉ ) ) ′ ≤ δ 1 ( u ( L , y ( x ˉ + δ ) ) y ′ ( x ˉ + δ ) − u ( L , y ( x ˉ ) ) y ′ ( x ˉ ) ) = δ 1 ( u ( L , y ( x ˉ + δ )) y ′ ( x ˉ + δ ) − u ( L , y ( x ˉ + δ )) y ′ ( x ˉ ) ) + δ 1 ( u ( L , y ( x ˉ + δ )) y ′ ( x ˉ ) − u ( L , y ( x ˉ )) y ′ ( x ˉ ) ) ≤ M ∥ y ′′ ∥ L ∞ + ∥ y ′ ∥ L ∞ 2 ω 0 L 1 .
An integration over the interval x ˉ ∈ [ x 1 , x 2 ] \bar x\in [x_1, x_2] x ˉ ∈ [ x 1 , x 2 ] yields
U ‾ ( x 2 + δ ) − U ‾ ( x 2 ) δ − U ‾ ( x 1 + δ ) − U ‾ ( x 1 ) δ ≤ ( M ∥ y ′ ′ ∥ L ∞ + ∥ y ′ ∥ L ∞ 2 ω 0 L ) ( x 2 − x 1 ) . \frac{\overline U( x_2 + \delta)-\overline U(x_2)}\delta-
\frac{\overline U(x_1 + \delta)-\overline U(x_1)}\delta~\leq~ \left( M \|y''\|_{{\bf L}^\infty} +{ \|y'\|_{{\bf L}^\infty}^2\over \omega_0 L}\right)(x_2-x_1). δ U ( x 2 + δ ) − U ( x 2 ) − δ U ( x 1 + δ ) − U ( x 1 ) ≤ ( M ∥ y ′′ ∥ L ∞ + ω 0 L ∥ y ′ ∥ L ∞ 2 ) ( x 2 − x 1 ) .
Taking the limit as δ → 0 \delta\to 0 δ → 0 we obtain ((8.3) ).
The previous result implies that u ˉ \bar u u ˉ has bounded variation and at most countably many jump discontinuities. It also implies that for small total cost c c c there is no queue. Indeed if
( b − a ) ( M ∥ y ′ ′ ∥ L ∞ + ∥ y ′ ∥ L ∞ 2 ω 0 L ) < M , (b-a) \left(M\|y''\|_{{\bf L}^\infty} + {\|y'\|^2_{{\bf L}^\infty} \over \omega_0 L}\right) ~<~M, ( b − a ) ( M ∥ y ′′ ∥ L ∞ + ω 0 L ∥ y ′ ∥ L ∞ 2 ) < M ,
then u ˉ ( x ) < M \bar u(x)< M u ˉ ( x ) < M for every x ∈ ] a , b [ x \in \,]a,b[ x ∈ ] a , b [ . The next result states that this regularity is generically optimal.
Theorem. For every f f f as in (A1) and c ∈ R c\in\mathbb{R} c ∈ R , the set J ( c ) \mathcal J(c) J ( c ) of couples ( φ , ψ ) (\varphi, \psi) ( φ , ψ ) for which the rate of departures u ˉ \bar u u ˉ of the Nash equilibrium has a jump type discontinuity is an open dense set in { ( φ , ψ ) ∈ C 2 ( R ) ; (A2) holds and min x ∈ R φ ( x ) + ψ ( x + ℓ 0 ) < c } , \left\{ (\varphi, \psi) \in {\mathcal C}^2(\mathbb{R})\,;~~ \hbox{{\bf (A2)} holds and}~ \min_{x\in \mathbb{R}}\ \varphi(x) + \psi(x+\ell_0) < c \right\}, { ( φ , ψ ) ∈ C 2 ( R ) ; (A2) holds and min x ∈ R φ ( x ) + ψ ( x + ℓ 0 ) < c } , w.r.t. the C 2 {\mathcal C}^2 C 2 topology.
In order to prove the result above we provide necessary conditions on the cost functions φ , ψ \varphi, \psi φ , ψ for having continuous Nash equilibria u ˉ \bar u u ˉ and then prove that generically are not satisfied. We observe that it suffices to consider the case where u ˉ ( x ) < M \bar u(x)<M u ˉ ( x ) < M for all x x x , since otherwise u ˉ \bar u u ˉ has a jump type discontinuity.
To state the necessary conditions for the continuity of u ˉ \bar u u ˉ , we consider the map g : Ω ⊂ R 2 → R 2 g: \Omega\subset \mathbb{R}^2 \to \mathbb{R}^2 g : Ω ⊂ R 2 → R 2 defined by
g ( x , v ) ≐ ( y ( x ) − L f ′ ( v y ′ ( x ) ) , v y ′ ( x ) ) , \begin{equation}
g(x,v)~\doteq~ \left(y(x) - Lf'\Big(\frac{v}{y'(x)}\Big),~ \frac{v}{y'(x)}\right), \tag*{(8.5)}
\end{equation} g ( x , v ) ≐ ( y ( x ) − L f ′ ( y ′ ( x ) v ) , y ′ ( x ) v ) , (8.5)
where y y y is extended to a C 2 {\mathcal C}^2 C 2 concave function with C 2 {\mathcal C}^2 C 2 inverse on the whole R \mathbb{R} R and
Ω ≐ { ( x , v ) : v y ′ ( x ) < M } . \begin{equation}
\Omega~\doteq ~\left\{ (x,v): \frac{v}{y'(x)}<M \right\}. \tag*{(8.6)}
\end{equation} Ω ≐ { ( x , v ) : y ′ ( x ) v < M } . (8.6)
The Jacobian matrix of g g g is
D g ( x , v ) = ( y ′ ( x ) + L f ′ ′ ( v y ′ ( x ) ) y ′ ′ ( x ) v ( y ′ ( x ) ) 2 − L f ′ ′ ( v y ′ ( x ) ) 1 y ′ ( x ) − v y ′ ′ ( x ) ( y ′ ( x ) ) 2 1 y ′ ( x ) ) \begin{equation}
Dg(x,v)~=~
\begin{pmatrix}
y'(x) +L f''(\frac{v}{y'(x)})\frac{y''(x)v}{(y'(x))^2}&& -L f''(\frac{v}{y'(x)})\frac1{y'(x)}\\[3mm]
-\frac{vy''(x)}{(y'(x))^2} && \frac1{y'(x)}
\end{pmatrix} \tag*{(8.7)}
\end{equation} D g ( x , v ) = y ′ ( x ) + L f ′′ ( y ′ ( x ) v ) ( y ′ ( x ) ) 2 y ′′ ( x ) v − ( y ′ ( x ) ) 2 v y ′′ ( x ) − L f ′′ ( y ′ ( x ) v ) y ′ ( x ) 1 y ′ ( x ) 1 (8.7)
Lemma. The map g g g is a C 1 {\mathcal C}^1 C 1 diffeomorphism on its image and has two hyperbolic fixed points ( a , 0 ) (a,0) ( a , 0 ) and ( b , 0 ) (b,0) ( b , 0 ) with a , b a,b a , b such that ℓ ( a ) = ℓ ( b ) = ℓ 0 \ell(a)=\ell(b)=\ell_0 ℓ ( a ) = ℓ ( b ) = ℓ 0 . The Jacobian matrix D g ( a , 0 ) Dg(a,0) D g ( a , 0 ) has eigenvalues 1 y ′ ( a ) , y ′ ( a ) \frac1{y'(a)}, y'(a) y ′ ( a ) 1 , y ′ ( a ) , while the matrix D g ( b , 0 ) Dg(b,0) D g ( b , 0 ) has eigenvalues 1 y ′ ( b ) , y ′ ( b ) \frac1{y'(b)}, y'(b) y ′ ( b ) 1 , y ′ ( b ) . Since 0 < y ′ ( b ) = − φ ′ ( b ) ψ ′ ( b + ℓ 0 ) < 1 < y ′ ( a ) = − φ ′ ( a ) ψ ′ ( a + ℓ 0 ) 0<y'(b)=\frac{-\varphi'(b)}{\psi'(b+\ell_0)}<1<y'(a)=\frac{-\varphi'(a)}{\psi'(a+\ell_0)} 0 < y ′ ( b ) = ψ ′ ( b + ℓ 0 ) − φ ′ ( b ) < 1 < y ′ ( a ) = ψ ′ ( a + ℓ 0 ) − φ ′ ( a ) , the two points ( a , 0 ) , ( b , 0 ) (a,0), (b,0) ( a , 0 ) , ( b , 0 ) are hyperbolic.
Proof. The Jacobian matrix of g g g has determinant equal to 1 1 1 for every ( x , v ) ∈ Ω (x,v)\in \Omega ( x , v ) ∈ Ω .
To prove that the map g = ( g 1 , g 2 ) g= (g_1,g_2) g = ( g 1 , g 2 ) is one-to-one, we observe that g ( x 1 , v 1 ) = g ( x 2 , v 2 ) g(x_1,v_1)=g(x_2,v_2) g ( x 1 , v 1 ) = g ( x 2 , v 2 ) implies v 1 y ′ ( x 1 ) = v 2 y ′ ( x 2 ) \frac{v_1}{y'(x_1)}=\frac{v_2}{y'(x_2)} y ′ ( x 1 ) v 1 = y ′ ( x 2 ) v 2 , hence y ( x 1 ) = y ( x 2 ) y(x_1)=y(x_2) y ( x 1 ) = y ( x 2 ) . Since y y y is invertible this implies x 1 = x 2 x_1=x_2 x 1 = x 2 and hence v 1 = v 2 v_1=v_2 v 1 = v 2 . The computation of eigenvalues is straightforward.
Given δ > 0 \delta>0 δ > 0 sufficiently small, we denote respectively by W δ s ( a , 0 ) W^s_\delta(a,0) W δ s ( a , 0 ) and W δ u ( a , 0 ) W^u_\delta(a,0) W δ u ( a , 0 ) , the intersections of the local stable and unstable manifolds through the point ( a , 0 ) (a,0) ( a , 0 ) , with the ball B δ ( ( a , 0 ) ) B_\delta((a,0)) B δ (( a , 0 )) centered at ( a , 0 ) (a,0) ( a , 0 ) with radius δ \delta δ . Similarly, W δ s ( b , 0 ) W^s_\delta(b,0) W δ s ( b , 0 ) , W δ u ( b , 0 ) W^u_\delta(b,0) W δ u ( b , 0 ) will denote the local stable and unstable manifolds through ( b , 0 ) (b,0) ( b , 0 ) , respectively.
Remark 15. It is easy to check that W δ u ( a , 0 ) = { ( x , 0 ) ; a − δ < x < a + δ } W^u_\delta(a,0) = \bigl\{ (x,0) ;\, a-\delta<x<a+ \delta\bigr\} W δ u ( a , 0 ) = { ( x , 0 ) ; a − δ < x < a + δ } and W δ s ( b , 0 ) = { ( x , 0 ) ; b − δ < x < b + δ } W^s_\delta(b,0) = \bigl\{ (x,0) ;\, b-\delta<x<b+ \delta\bigr\} W δ s ( b , 0 ) = { ( x , 0 ) ; b − δ < x < b + δ } . For our purpose, the relevant manifolds are W δ s ( a , 0 ) W^s_\delta(a,0) W δ s ( a , 0 ) and W δ u ( b , 0 ) W^u_\delta(b,0) W δ u ( b , 0 ) .
Lemma 8.5. Assume that the departure rate u ˉ ( ⋅ ) \bar u(\cdot) u ˉ ( ⋅ ) corresponding to a Nash equilibrium is continuous. Then u ˉ \bar u u ˉ is Lipschitz continuous with Lipschitz constant L i p ( u ˉ ) ≤ M ∥ y ′ ′ ∥ L ∞ + 1 ω 0 L ∥ y ′ ∥ L ∞ 2 .
\mathrm{Lip}(\bar u) ~\le ~M\|y''\|_{{\bf L}^\infty} + {1\over \omega_0 L} \|y'\|^2_{{\bf L}^\infty} \,.
Lip ( u ˉ ) ≤ M ∥ y ′′ ∥ L ∞ + ω 0 L 1 ∥ y ′ ∥ L ∞ 2 . Moreover there is a continuous increasing function z : [ a , b ] ↦ [ a , b ] z:[a,b]\mapsto [a,b] z : [ a , b ] ↦ [ a , b ] such that { y ( x ) = z ( x ) + L f ′ ( u ˉ ( z ( x ) ) ) , u ˉ ( x ) = y ′ ( x ) u ˉ ( z ( x ) ) , for all x ∈ [ a , b ] .
\left\{\begin{array}{rl}
y(x)&= ~z(x) + Lf'\bigl(\bar u(z(x))\bigr), \\[2mm]
\bar u (x) &= ~y'(x)\bar u (z(x)),
\end{array}\right.\qquad\qquad\hbox{for all}~x\in [a,b].
{ y ( x ) u ˉ ( x ) = z ( x ) + L f ′ ( u ˉ ( z ( x )) ) , = y ′ ( x ) u ˉ ( z ( x )) , for all x ∈ [ a , b ] . In particular for every x ∈ ] a , b [ x \in \,]a,b[\, x ∈ ] a , b [ one has g ( x , u ˉ ( x ) ) = ( z ( x ) , u ˉ ( z ( x ) ) ) g\bigl(x,\bar u (x)\bigr)=
\bigl(z(x), \bar u (z(x))\bigr) g ( x , u ˉ ( x ) ) = ( z ( x ) , u ˉ ( z ( x )) ) and
\begin{split}
W^s_+(a,0) \doteq &~ \bigcup_{ n \in {\mathbb N}\,} g^{-n}\bigl(W^s_\delta(a,0)\cap \{v>0\}\bigr)~ =~ \bigl\{(x,\bar u(x));\, x \in \,]a,b[\bigr\},\\
W^u_+(b,0) \doteq &~ \bigcup_{ n \in {\mathbb N}\,} g^{n}\bigl(W^u_\delta(b,0)\cap \{v>0\}\bigr)
~ = ~\big\{(x,\bar u(x)): x \in \,]a,b[\big\}.
\end{split}
Proof. 1. Differentiating the identity
∫ − ∞ x u ˉ ( s ) d s = ∫ − ∞ y ( x ) u ( L , s ) d s \int_{-\infty}^x\bar u(s)ds ~=~ \int_{-\infty}^{y(x)}u(L,s)ds ∫ − ∞ x u ˉ ( s ) d s = ∫ − ∞ y ( x ) u ( L , s ) d s
we obtain
u ˉ ( x ) = y ′ ( x ) u ( L , y ( x ) ) . \begin{equation}
\bar u(x) ~= ~y'(x) u\bigl(L,y(x)\bigr). \tag*{(8.11)}
\end{equation} u ˉ ( x ) = y ′ ( x ) u ( L , y ( x ) ) . (8.11)
Since the map x ↦ y ( x ) x\mapsto y(x) x ↦ y ( x ) is bi-Lipschitz on [ a , b ] [a,b] [ a , b ] and y ′ ( x ) > 0 y'(x)>0 y ′ ( x ) > 0 , this implies that u ( L , ⋅ ) u(L,\cdot) u ( L , ⋅ ) is continuous. We already proved that u ˉ \bar u u ˉ satisfies (8.3) . It remains to prove that u ˉ \bar u u ˉ also satisfies a downward Lipschitz estimate. Since u u u is a continuous solution of (2.1) on ] 0 , L [ × R \,]0,L[\, \times \mathbb{R} ] 0 , L [ × R , forward characteristics do not cross and hence
f ′ ( u ˉ ( x 2 ) ) − f ′ ( u ˉ ( x 1 ) ) ≥ − 1 L ( x 2 − x 1 ) for a.e. x 1 < x 2 . f'\bigl(\bar u(x_2)\bigr)-f'\bigl(\bar u(x_1)\bigr)~ \ge\, - \frac1L(x_2-x_1) \qquad \text{for a.e. }~~x_1<x_2\,. f ′ ( u ˉ ( x 2 ) ) − f ′ ( u ˉ ( x 1 ) ) ≥ − L 1 ( x 2 − x 1 ) for a.e. x 1 < x 2 .
In turn, this implies
u ˉ ( x 1 ) − u ˉ ( x 2 ) ≤ x 2 − x 1 ω 0 L for a.e. x 1 < x 2 , \bar u(x_1)-\bar u(x_2)~\leq~ {x_2-x_1\over \omega_0 L} \qquad \text{for a.e. }~x_1<x_2\,, u ˉ ( x 1 ) − u ˉ ( x 2 ) ≤ ω 0 L x 2 − x 1 for a.e. x 1 < x 2 ,
where ω 0 \omega_0 ω 0 is the constant in ((2.2) ). 2. Since u u u is constant along backward characteristics we also deduce that u ˉ ( z ( x ) ) = u ( L , y ( x ) ) \bar u \bigl(z(x)\bigr)= u\bigl(L,y(x)\bigr) u ˉ ( z ( x ) ) = u ( L , y ( x ) ) with z ( x ) = y ( x ) − L f ′ ( u ( L , y ( x ) ) ) z(x)= y(x)- Lf'\bigl(u(L,y(x))\bigr) z ( x ) = y ( x ) − L f ′ ( u ( L , y ( x )) ) . Combined with (8.11) , this proves (8.9) . 3. By the definition of g g g at ((8.5) ), for every x ∈ ] a , b [ x\in \,]a,b[\, x ∈ ] a , b [ one has g ( x , u ˉ ( x ) ) = ( z ( x ) , u ˉ ( z ( x ) ) ) g\bigl(x,\bar u (x)\bigr)=\bigl(z(x),\bar u(z(x))\bigr) g ( x , u ˉ ( x ) ) = ( z ( x ) , u ˉ ( z ( x )) ) . In order to deduce (8.10) it is sufficient to observe u ˉ ( a ) = u ˉ ( b ) = 0 \bar u (a)=\bar u(b)=0 u ˉ ( a ) = u ˉ ( b ) = 0 and that z : [ a , b ] ↦ [ a , b ] z:[a,b]\mapsto [a,b] z : [ a , b ] ↦ [ a , b ] is invertible and satisfies z ( x ) < x z(x)<x z ( x ) < x for every x ∈ ] a , b [ x \in \,]a,b[\, x ∈ ] a , b [ .
We are now ready for
Proof of Theorem (?) .
1. In order to prove that J ( c ) \mathcal J(c) J ( c ) is open it suffices to observe that u ˉ \bar u u ˉ depends continuously on the cost functions φ , ψ \varphi,\psi φ , ψ . Indeed if u ˉ n \bar u_n u ˉ n are continuous Nash equilibria for the costs functions φ n , ψ n \varphi_n,\psi_n φ n , ψ n and φ n → φ \varphi_n \to \varphi φ n → φ and ψ n → ψ \psi_n\to \psi ψ n → ψ in C 2 {\mathcal C}^2 C 2 , then the u n u_n u n are uniformly Lipschitz thanks to (8.8) and therefore u ˉ = lim n → ∞ u ˉ n \bar u = \lim_{n\to \infty}\bar u_n u ˉ = lim n → ∞ u ˉ n is Lipschitz as well. 2. Next, let φ , ψ \varphi, \psi φ , ψ be departure and arrival costs as in (A2), such that the corresponding Nash equilibrium u ˉ \bar u u ˉ is continuous. We will show that, for any ε > 0 \varepsilon>0 ε > 0 , there exists a perturbed arrival cost ψ ε \psi_\varepsilon ψ ε , with ∥ ψ ε − ψ ∥ C 2 < ε \|\psi_\varepsilon-\psi\|_{{\mathcal C}^2}<\varepsilon ∥ ψ ε − ψ ∥ C 2 < ε , for which the corresponding Nash equilibrium u ˉ ε \bar u_\varepsilon u ˉ ε is not continuous.
By Lemma 8.5 , u ˉ \bar u u ˉ is Lipschitz continuous. Let x ˉ \bar x x ˉ be a point where u ˉ \bar u u ˉ is differentiable and let δ ψ > 0 \delta_\psi>0 δ ψ > 0 be small enough so that
y ( z ( x ˉ ) ) < y ( x ˉ ) − δ ψ < y ( x ˉ ) + δ ψ < y ( z − 1 ( x ˉ ) ) . y\bigl(z(\bar x)\bigr)<y(\bar x) - \delta_\psi<y(\bar x)+\delta_\psi <y\bigl(z^{-1}(\bar x)\bigr). y ( z ( x ˉ ) ) < y ( x ˉ ) − δ ψ < y ( x ˉ ) + δ ψ < y ( z − 1 ( x ˉ ) ) .
For ε > 0 \varepsilon>0 ε > 0 , set
ψ ε = ψ + ε ψ ~ , \psi_\varepsilon= \psi + \varepsilon\tilde \psi, ψ ε = ψ + ε ψ ~ ,
for some smooth perturbation with compact support
ψ ~ ∈ C ∞ ( y ( x ˉ ) − δ ψ , y ( x ˉ ) + δ ψ ) , \tilde \psi \in {\mathcal C}^\infty(y(\bar x)-\delta_\psi, y(\bar x) + \delta_\psi), ψ ~ ∈ C ∞ ( y ( x ˉ ) − δ ψ , y ( x ˉ ) + δ ψ ) ,
to be chosen later.
Assume by contradiction that, for every ε > 0 \varepsilon>0 ε > 0 , the corresponding Nash equilibrium u ˉ ε \bar u_\varepsilon u ˉ ε is continuous. Then we would have
u ˉ ε ( x ) = u ˉ ( x ) for every x ∈ [ a , z ( x ˉ ) ] ∪ [ x ˉ , b ] \begin{equation}
\bar u_\varepsilon(x) = \bar u(x) \qquad \text{for every }~~x \in \bigl[a,z(\bar x)\bigr] \cup [\bar x, b] \tag*{(8.12)}
\end{equation} u ˉ ε ( x ) = u ˉ ( x ) for every x ∈ [ a , z ( x ˉ ) ] ∪ [ x ˉ , b ] (8.12)
because the corresponding stable and unstable manifolds do not depend on ε \varepsilon ε if x ∈ [ a , z ( x ˉ ) ] ∪ [ x ˉ , b ] x\in [a,z(\bar x)] \cup [\bar x, b] x ∈ [ a , z ( x ˉ )] ∪ [ x ˉ , b ] , namely
W + s , ε ( a , 0 ) ∩ { ( x , v ) ∈ ( a , z ( x ˉ ) ] × R } = W + s ( a , 0 ) ∩ { ( x , v ) ∈ ( a , z ( x ˉ ) ] × R } , W + u , ε ( b , 0 ) ∩ { ( x , v ) ∈ [ x ˉ , b ) × R } = W + u ( b , 0 ) ∩ { ( x , v ) ∈ [ x ˉ , b ) × R } . \begin{split}
W^{s,\varepsilon}_+(a,0)\cap \bigl\{ (x,v) \in (a, z(\bar x)]\times \mathbb{R}\bigr\} = &~ W^s_+(a,0)\cap
\bigl\{ (x,v) \in (a, z(\bar x)]\times \mathbb{R}\bigr\}, \\
W^{u,\varepsilon}_+(b,0)\cap \bigl\{ (x,v) \in [\bar x,b)\times \mathbb{R}\bigr\} = &~ W^u_+(b,0)\cap
\bigl\{ (x,v) \in [\bar x,b)\times \mathbb{R}\bigr\}.
\end{split} W + s , ε ( a , 0 ) ∩ { ( x , v ) ∈ ( a , z ( x ˉ )] × R } = W + u , ε ( b , 0 ) ∩ { ( x , v ) ∈ [ x ˉ , b ) × R } = W + s ( a , 0 ) ∩ { ( x , v ) ∈ ( a , z ( x ˉ )] × R } , W + u ( b , 0 ) ∩ { ( x , v ) ∈ [ x ˉ , b ) × R } .
3. Consider the map x ↦ y ε ( x ) x\mapsto y_\varepsilon(x) x ↦ y ε ( x ) implicitly defined by
φ ( x ) + ψ ε ( y ε ( x ) ) = c , \varphi(x) +\psi_\varepsilon\bigl(y_\varepsilon(x)\bigr)~=~c, φ ( x ) + ψ ε ( y ε ( x ) ) = c ,
where c c c is the common cost to all drivers. Equivalently, y ε ( x ) = ψ ε − 1 ( c − φ ( x ) ) y_\varepsilon(x)=\psi_\varepsilon^{-1}(c-\varphi(x)) y ε ( x ) = ψ ε − 1 ( c − φ ( x )) . A Taylor expansion yields
y ε ( x ) = y ( x ) − ε ψ ~ ( y ( x ) ) ψ ′ ( y ( x ) ) + O ( ε 2 ) ≐ y ( x ) + ε Δ y ( x ) + O ( ε 2 ) y ε ′ ( x ) = y ′ ( x ) + ε [ − ψ ~ ′ ( y ( x ) ) y ′ ( x ) ψ ′ ( y ( x ) ) + ψ ′ ′ ( y ( x ) ) y ′ ( x ) ψ ~ ( y ( x ) ) ( ψ ′ ( y ( x ) ) ) 2 ] + O ( ε 2 ) ≐ y ′ ( x ) + ε Δ y ′ ( x ) + O ( ε 2 ) . \begin{split}
y_\varepsilon(x)= &~ y(x) - \varepsilon\frac{\tilde \psi(y(x))}{\psi'(y(x))}+ {\mathcal O}(\varepsilon^2) \\
\doteq &~ y(x) + \varepsilon\Delta y(x) + {\mathcal O}(\varepsilon^2) \\
y_\varepsilon'(x)= &~ y'(x) +\varepsilon\left[ -\frac{\tilde \psi'(y(x))y'(x)}{\psi'(y(x))} + \frac{\psi''(y(x))y'(x) \tilde \psi(y(x))}{(\psi'(y(x)))^2}\right] + {\mathcal O}(\varepsilon^2)\\
\doteq &~ y'(x)+ \varepsilon\Delta y'(x) + {\mathcal O}(\varepsilon^2).
\end{split} y ε ( x ) = ≐ y ε ′ ( x ) = ≐ y ( x ) − ε ψ ′ ( y ( x )) ψ ~ ( y ( x )) + O ( ε 2 ) y ( x ) + ε Δ y ( x ) + O ( ε 2 ) y ′ ( x ) + ε [ − ψ ′ ( y ( x )) ψ ~ ′ ( y ( x )) y ′ ( x ) + ( ψ ′ ( y ( x )) ) 2 ψ ′′ ( y ( x )) y ′ ( x ) ψ ~ ( y ( x )) ] + O ( ε 2 ) y ′ ( x ) + ε Δ y ′ ( x ) + O ( ε 2 ) .
Therefore, for any v v v as in ((8.6) ), we have
v y ε ′ ( x ) = v y ′ ( x ) − ε v y ′ ( x ) 2 Δ y ′ ( x ) + O ( ε 2 ) . \frac{v}{y'_\varepsilon(x)}= \frac{v}{y'(x)}-\varepsilon\frac{v}{y'(x)^2}\Delta y'(x) + {\mathcal O}(\varepsilon^2). y ε ′ ( x ) v = y ′ ( x ) v − ε y ′ ( x ) 2 v Δ y ′ ( x ) + O ( ε 2 ) .
In addition, recalling ((8.5) ), the corresponding map g ε g_\varepsilon g ε satisfies
g ε ( x , v ) = g ( x , v ) + ε ( Δ y ( x ) + L f ′ ′ ( v y ′ ( x ) ) v y ′ ( x ) 2 Δ y ′ ( x ) , − v y ′ ( x ) 2 Δ y ′ ( x ) ) + O ( ε 2 ) . g_\varepsilon(x,v)= g(x,v) + \varepsilon\left( \Delta y(x) +Lf''\left(\frac{v}{y'(x)}\right)\frac{v}{y'(x)^2}\Delta y'(x)\,,~ -\frac{v}{y'(x)^2}\Delta y'(x) \right) + {\mathcal O}(\varepsilon^2). g ε ( x , v ) = g ( x , v ) + ε ( Δ y ( x ) + L f ′′ ( y ′ ( x ) v ) y ′ ( x ) 2 v Δ y ′ ( x ) , − y ′ ( x ) 2 v Δ y ′ ( x ) ) + O ( ε 2 ) .
4. Since x ˉ ∈ ] a , b [ \bar x \in \,]a,b[\, x ˉ ∈ ] a , b [ , we have u ˉ ( x ˉ ) > 0 \bar u(\bar x)>0 u ˉ ( x ˉ ) > 0 . Therefore, choosing ψ ~ ∈ C c ∞ ( y ( x ˉ ) − δ ψ , y ( x ˉ ) + δ ψ ) \widetilde\psi \in C^\infty_c(y(\bar x)-\delta_\psi, y(\bar x)+\delta_\psi) ψ ∈ C c ∞ ( y ( x ˉ ) − δ ψ , y ( x ˉ ) + δ ψ ) such that
ψ ~ ( y ( x ˉ ) ) = − L f ′ ′ ( u ˉ ( x ˉ ) y ′ ( x ˉ ) ) ψ ′ ( y ( x ˉ ) ) , ψ ~ ′ ( y ( x ˉ ) ) = y ′ ( x ˉ ) u ˉ ( x ˉ ) ) ψ ′ ( y ( x ˉ ) ) − L f ′ ′ ( u ˉ ( x ˉ ) y ′ ( x ˉ ) ) ψ ′ ′ ( y ( x ˉ ) ) , \widetilde\psi\bigl(y(\bar x)\bigr)\,=-Lf''\left(\frac{\bar u (\bar x)}{y'(\bar x)}\right) \psi'\bigl(y(\bar x)\bigr), \qquad \widetilde\psi'\bigl(y(\bar x)\bigr)\,=\, \frac{y'(\bar x)}{\bar u(\bar x))}\psi'\bigl(y(\bar x)\bigr) - Lf''\left(\frac{\bar u (\bar x)}{y'(\bar x)}\right) \psi''\bigl(y(\bar x)\bigr), ψ ( y ( x ˉ ) ) = − L f ′′ ( y ′ ( x ˉ ) u ˉ ( x ˉ ) ) ψ ′ ( y ( x ˉ ) ) , ψ ′ ( y ( x ˉ ) ) = u ˉ ( x ˉ )) y ′ ( x ˉ ) ψ ′ ( y ( x ˉ ) ) − L f ′′ ( y ′ ( x ˉ ) u ˉ ( x ˉ ) ) ψ ′′ ( y ( x ˉ ) ) ,
we obtain
{ Δ y ( x ˉ ) + L f ′ ′ ( u ˉ ( x ) y ′ ( x ˉ ) ) u ˉ ( x ˉ ) y ′ ( x ˉ ) 2 Δ y ′ ( x ˉ ) = 0 , − u ˉ ( x ˉ ) y ′ ( x ˉ ) 2 Δ y ′ ( x ˉ ) = 1. \left\{\begin{array}{cl}
\displaystyle\Delta y(\bar x) +Lf''\left(\frac{\bar u(x)}{y'(\bar x)}\right)\frac{\bar u(\bar x)}{y'(\bar x)^2}\,\Delta y'(\bar x)
&=~ 0, \\[4mm]
\displaystyle-\frac{\bar u(\bar x)}{y'(\bar x)^2}\Delta y'(\bar x)&=~1.\end{array}\right. ⎩ ⎨ ⎧ Δ y ( x ˉ ) + L f ′′ ( y ′ ( x ˉ ) u ˉ ( x ) ) y ′ ( x ˉ ) 2 u ˉ ( x ˉ ) Δ y ′ ( x ˉ ) − y ′ ( x ˉ ) 2 u ˉ ( x ˉ ) Δ y ′ ( x ˉ ) = 0 , = 1.
In turn, this implies
g ε ( x ˉ , u ˉ ( x ˉ ) ) = g ( x ˉ , u ˉ ( x ˉ ) ) + ( 0 , ε ) + O ( ε 2 ) . \begin{equation}
g_\varepsilon\bigl(\bar x, \bar u(\bar x)\bigr)~=~ g\bigl(\bar x,\bar u(\bar x)\bigr)
+ (0,\varepsilon) + {\mathcal O}(\varepsilon^2). \tag*{(8.13)}
\end{equation} g ε ( x ˉ , u ˉ ( x ˉ ) ) = g ( x ˉ , u ˉ ( x ˉ ) ) + ( 0 , ε ) + O ( ε 2 ) . (8.13)
By construction we now have g ( x ˉ , u ˉ ( x ˉ ) ) = ( z ( x ˉ ) , u ˉ ( z ( x ˉ ) ) ) g\bigl(\bar x, \bar u(\bar x)\bigr) = \bigl(z(\bar x), \bar u(z(\bar x))\bigr) g ( x ˉ , u ˉ ( x ˉ ) ) = ( z ( x ˉ ) , u ˉ ( z ( x ˉ )) ) . Moreover, by the assumption ((8.12) ), u ˉ ( x ˉ ) = u ˉ ε ( x ˉ ) \bar u(\bar x)=\bar u_\varepsilon(\bar x) u ˉ ( x ˉ ) = u ˉ ε ( x ˉ ) . This implies g ε ( x ˉ , u ˉ ( x ˉ ) ) ) = ( z ε ( x ˉ ) , u ˉ ε ( z ε ( x ˉ ) ) ) g_\varepsilon\bigl(\bar x, \bar u(\bar x))\bigr)=\bigl(z_\varepsilon(\bar x), \bar u_\varepsilon(z_\varepsilon(\bar x))\bigr) g ε ( x ˉ , u ˉ ( x ˉ )) ) = ( z ε ( x ˉ ) , u ˉ ε ( z ε ( x ˉ )) ) . Thanks to (8.13) , we have
z ε ( x ˉ ) − z ( x ˉ ) = O ( ε 2 ) , u ˉ ε ( z ε ( x ˉ ) ) − u ˉ ( z ( x ˉ ) ) = ε + O ( ε 2 ) . \begin{equation}
z_\varepsilon(\bar x)- z(\bar x)\,=\, {\mathcal O}(\varepsilon^2),\qquad\qquad \bar u_\varepsilon\bigl(z_\varepsilon(\bar x)\bigr) - \bar u\bigl(z(\bar x)\bigr) = \varepsilon+ {\mathcal O}(\varepsilon^2). \tag*{(8.14)}
\end{equation} z ε ( x ˉ ) − z ( x ˉ ) = O ( ε 2 ) , u ˉ ε ( z ε ( x ˉ ) ) − u ˉ ( z ( x ˉ ) ) = ε + O ( ε 2 ) . (8.14)
Since u ˉ ( z ( x ˉ ) ) = u ˉ ε ( z ( x ˉ ) ) \bar u (z(\bar x))= \bar u_\varepsilon(z(\bar x)) u ˉ ( z ( x ˉ )) = u ˉ ε ( z ( x ˉ )) we deduce that u ˉ ε ( z ε ( x ˉ ) ) − u ˉ ε ( z ( x ˉ ) ) = ε + O ( ε 2 ) \bar u_\varepsilon(z_\varepsilon(\bar x)) - \bar u_\varepsilon(z(\bar x)) = \varepsilon+ {\mathcal O}(\varepsilon^2) u ˉ ε ( z ε ( x ˉ )) − u ˉ ε ( z ( x ˉ )) = ε + O ( ε 2 ) . This contradicts the first bound in ((8.14) ), because by ((8.8) ) the functions u ˉ ε \bar u_\varepsilon u ˉ ε are uniformly Lipschitz continuous as ε → 0 \varepsilon\to 0 ε → 0 . This contradiction achieves the proof.
An evolution equation for the departure pattern
Given two functions φ , ψ \varphi,\psi φ , ψ , the total cost to a driver starting at time x x x is defined as
Φ u ( x ) ≐ φ ( x ) + ψ ( y u ( x ) ) . \begin{equation}
\Phi^u(x)~\doteq~\varphi(x)+\psi(y^u(x))\,. \tag*{(9.1)}
\end{equation} Φ u ( x ) ≐ φ ( x ) + ψ ( y u ( x )) . (9.1)
Notice that here the arrival time y u ( x ) y^u(x) y u ( x ) depends not only on the departure time x x x but also on the entire traffic pattern u ( ⋅ ) u(\cdot) u ( ⋅ ) . In particular, by ((2.13) ) it depends on the behavior of drivers that have departed at times earlier than x x x .
Following one of the models proposed in [18 ] we assume that drivers initially departing at time x x x switch to other times ξ ∈ R \xi\in\mathbb{R} ξ ∈ R , with probability proportional to the difference in cost. Calling u ( θ , x ) = Q x ( θ , x ) u(\theta,x)= Q_x(\theta,x) u ( θ , x ) = Q x ( θ , x ) the rate of departures at time x x x on day θ \theta θ , in continuum time this leads to
d d θ u ( θ , x ) = Λ ( u , x ) ≐ ∫ u ( ξ ) [ Φ u ( ξ ) − Φ u ( x ) ] + d ξ − ∫ u ( x ) [ Φ u ( x ) − Φ u ( ξ ) ] + d ξ . \begin{equation}
{d\over d\theta} u(\theta ,x) ~=~\Lambda(u,x)~\doteq~\int u(\xi)\Big[ \Phi^u(\xi) - \Phi^u(x)\Big]_+ d\xi
-\int u(x)\Big[ \Phi^u(x)-\Phi^u(\xi)\Big]_+ d\xi\,. \tag*{(9.2)}
\end{equation} d θ d u ( θ , x ) = Λ ( u , x ) ≐ ∫ u ( ξ ) [ Φ u ( ξ ) − Φ u ( x ) ] + d ξ − ∫ u ( x ) [ Φ u ( x ) − Φ u ( ξ ) ] + d ξ . (9.2)
Our first goal is to prove that the evolution equation (9.2) is well posed. Namely, for any initial departure pattern
u ( 0 , x ) = u ˉ ( x ) ≥ 0 , \begin{equation}
u(0,x)~=~\bar u(x)~\geq~0, \tag*{(9.3)}
\end{equation} u ( 0 , x ) = u ˉ ( x ) ≥ 0 , (9.3)
a unique solution exists, defined for all t ≥ 0 t\geq 0 t ≥ 0 . Our main result is
Theorem 9.1. Let the assumptions (A1)–(A2) hold. Assume that the initial departure rate u ˉ ∈ L 1 ( R ) ∩ L ∞ ( R ) \bar u\in {\bf L}^1(\mathbb{R})\cap{\bf L}^\infty(\mathbb{R}) u ˉ ∈ L 1 ( R ) ∩ L ∞ ( R ) has bounded support. Then the evolution problem ((9.2) ) has a unique solution u = u ( θ , x ) u=u(\theta, x) u = u ( θ , x ) , defined for all θ ≥ 0 \theta\geq 0 θ ≥ 0 . Its support remains uniformly bounded in time.
Proof. 1. We write ((9.2) ) as an abstract evolution equation in the Banach space L 1 ( R ) {\bf L}^1(\mathbb{R}) L 1 ( R ) ,
d d θ u ( θ ) = Λ ( u ( θ ) ) , u ( 0 ) = u ˉ . \begin{equation}
{d\over d\theta} u(\theta)~=~\Lambda\bigl(u(\theta)\bigr),\qquad\qquad u(0)=\bar u. \tag*{(9.4)}
\end{equation} d θ d u ( θ ) = Λ ( u ( θ ) ) , u ( 0 ) = u ˉ . (9.4)
By the standard theory of ODEs in Banach spaces, this Cauchy problem has unique local solution provided that the map u ↦ Λ ( u ) u\mapsto \Lambda(u) u ↦ Λ ( u ) is locally Lipschitz continuous w.r.t. the L 1 {\bf L}^1 L 1 norm. 2. We observe that an a priori bound on the support of u ( θ , ⋅ ) u(\theta,\cdot) u ( θ , ⋅ ) yields a bound on ∥ u ( t , ⋅ ) ∥ L ∞ \bigl\|u(t,\cdot)\bigr\|_{{\bf L}^\infty} u ( t , ⋅ ) L ∞ . Indeed, assuming that the solution u ( θ , ⋅ ) u(\theta,\cdot) u ( θ , ⋅ ) is supported inside an interval of length R R R , by the assumptions (A2) we have
d d θ ∥ u ( θ , ⋅ ) ∥ L ∞ ≤ sup x ∫ [ Φ u ( ξ ) − Φ u ( x ) ] + u ( θ , ξ ) d ξ ≤ sup ∣ x − ξ ∣ < R ∣ Φ u ( ξ ) − Φ u ( x ) ∣ ⋅ ∥ u ( θ , ⋅ ) ∥ L 1 ≤ C 0 ( 1 + R ) ∥ u ( θ , ⋅ ) ∥ L 1 , \begin{equation}
\begin{array}{rl} \displaystyle
{d\over d\theta} \bigl\|u(\theta,\cdot)\bigr\|_{{\bf L}^\infty} &\leq~\displaystyle\sup_x
\int \Big[ \Phi^u(\xi) - \Phi^u(x)\Big]_+ u(\theta, \xi) \,d\xi\\[4mm]
&\displaystyle\leq~\sup_{|x-\xi|< R} \bigl| \Phi^u(\xi) - \Phi^u(x)\bigr|\cdot \bigl\|u(\theta,\cdot)\bigr\|_{{\bf L}^1}\\[4mm]
&\displaystyle\leq~
C_0(1+R) \bigl\|u(\theta,\cdot)\bigr\|_{{\bf L}^1}\,,\end{array} \tag*{(9.5)}
\end{equation} d θ d u ( θ , ⋅ ) L ∞ ≤ x sup ∫ [ Φ u ( ξ ) − Φ u ( x ) ] + u ( θ , ξ ) d ξ ≤ ∣ x − ξ ∣ < R sup Φ u ( ξ ) − Φ u ( x ) ⋅ u ( θ , ⋅ ) L 1 ≤ C 0 ( 1 + R ) u ( θ , ⋅ ) L 1 , (9.5)
for some constant C 0 C_0 C 0 depending on the Lipschitz constants L φ , L ψ L_\varphi,L_\psi L φ , L ψ in ((5.1) ) and on the maximum travel time ℓ m a x \ell_{max} ℓ ma x in ((2.9) ). 3. For any u , v ≥ 0 u,v\geq 0 u , v ≥ 0 with ∥ u ∥ L 1 ≤ K \|u\|_{{\bf L}^1}\leq K ∥ u ∥ L 1 ≤ K , ∥ v ∥ L 1 ≤ K \|v\|_{{\bf L}^1}\leq K ∥ v ∥ L 1 ≤ K , by Proposition (?) we have
∥ Λ ( u ) − Λ ( v ) ∥ L 1 = ∫ a b ∣ Λ ( u , x ) − Λ ( v , x ) ∣ d x ≤ ∫ ∫ ∣ u ( ξ ) − v ( ξ ) ∣ [ Φ u ( ξ ) − Φ u ( x ) ] + d ξ d x + ∫ ∫ v ( ξ ) ∣ [ Φ u ( x ) − Φ u ( ξ ) ] + − [ Φ v ( x ) − Φ v ( ξ ) ] + ∣ d ξ d x + ∫ ∫ ∣ u ( x ) − v ( x ) ∣ [ Φ u ( x ) − Φ u ( ξ ) ] + d ξ d x + ∫ ∫ v ( x ) ∣ [ Φ u ( x ) − Φ u ( ξ ) ] + − [ Φ v ( x ) − Φ v ( ξ ) ] + ∣ d ξ d x ≤ ( b − a ) ⋅ ∥ u − v ∥ L 1 ⋅ ∥ Φ u ∥ L ∞ + ( b − a ) ∥ v ∥ L ∞ ⋅ 2 ∥ Φ u − Φ v ∥ L 1 + ( b − a ) ⋅ ∥ u − v ∥ L 1 ⋅ ∥ Φ u ∥ L ∞ + ( b − a ) ∥ v ∥ L ∞ ⋅ 2 ∥ Φ u − Φ v ∥ L 1 . \begin{equation}
\begin{array}{l}\displaystyle
\bigl\| \Lambda(u) - \Lambda(v)\bigr\|_{{\bf L}^1}\displaystyle~=~\int_a^b\big| \Lambda(u,x)-\Lambda(v,x)\bigr|\, dx\\[4mm]
\displaystyle\quad \leq ~\int\!\!\int\bigl| u(\xi)- v(\xi)\bigr| \Big[ \Phi^u(\xi) - \Phi^u(x)\Big]_+ d\xi \,dx \\[4mm]
\qquad \displaystyle+\int\!\!\int v(\xi)\bigg| \bigl[\Phi^u(x)-\Phi^u(\xi)\bigr]_+ - \bigl[\Phi^v(x)-\Phi^v(\xi)\bigr]_+ \bigg| d\xi\, dx\\[4mm]
\displaystyle\qquad +\int\!\!\int\bigl|u(x)-v(x)\bigr|\, \Big[ \Phi^u(x)-\Phi^u(\xi)\Big]_+ d\xi\, dx \\[4mm]
\displaystyle\qquad + \int\!\!\int v(x) \, \bigg| \Big[ \Phi^u(x)-\Phi^u(\xi)\Big]_+- \Big[ \Phi^v(x)-\Phi^v(\xi)\Big]_+\bigg|\, d\xi\, dx
\\[4mm]
\quad \leq~(b-a) \cdot \| u-v\|_{{\bf L}^1}\cdot \|\Phi^u\|_{{\bf L}^\infty} + (b-a) \|v\|_{{\bf L}^\infty} \cdot 2 \|\Phi^u-\Phi^v\|_{{\bf L}^1}
\\[2mm]
\qquad +(b-a) \cdot \| u-v\|_{{\bf L}^1}\cdot \|\Phi^u\|_{{\bf L}^\infty} + (b-a) \|v\|_{{\bf L}^\infty} \cdot 2 \|\Phi^u-\Phi^v\|_{{\bf L}^1}\,.
\end{array} \tag*{(9.6)}
\end{equation} Λ ( u ) − Λ ( v ) L 1 = ∫ a b Λ ( u , x ) − Λ ( v , x ) d x ≤ ∫ ∫ u ( ξ ) − v ( ξ ) [ Φ u ( ξ ) − Φ u ( x ) ] + d ξ d x + ∫ ∫ v ( ξ ) [ Φ u ( x ) − Φ u ( ξ ) ] + − [ Φ v ( x ) − Φ v ( ξ ) ] + d ξ d x + ∫ ∫ u ( x ) − v ( x ) [ Φ u ( x ) − Φ u ( ξ ) ] + d ξ d x + ∫ ∫ v ( x ) [ Φ u ( x ) − Φ u ( ξ ) ] + − [ Φ v ( x ) − Φ v ( ξ ) ] + d ξ d x ≤ ( b − a ) ⋅ ∥ u − v ∥ L 1 ⋅ ∥ Φ u ∥ L ∞ + ( b − a ) ∥ v ∥ L ∞ ⋅ 2∥ Φ u − Φ v ∥ L 1 + ( b − a ) ⋅ ∥ u − v ∥ L 1 ⋅ ∥ Φ u ∥ L ∞ + ( b − a ) ∥ v ∥ L ∞ ⋅ 2∥ Φ u − Φ v ∥ L 1 . (9.6)
We used here the elementary inequality
∣ [ Φ u ( x ) − Φ u ( ξ ) ] + − [ Φ v ( x ) − Φ v ( ξ ) ] + ∣ ≤ ∣ Φ u ( x ) − Φ v ( x ) ∣ + ∣ Φ u ( ξ ) − Φ v ( ξ ) ∣ . \bigg| \bigl[\Phi^u(x)-\Phi^u(\xi)\bigr]_+ - \bigl[\Phi^v(x)-\Phi^v(\xi)\bigr]_+ \bigg|~\leq~
\bigl| \Phi^u(x) - \Phi^v(x)\bigr| + \bigl| \Phi^u(\xi) - \Phi^v(\xi)\bigr| . [ Φ u ( x ) − Φ u ( ξ ) ] + − [ Φ v ( x ) − Φ v ( ξ ) ] + ≤ Φ u ( x ) − Φ v ( x ) + Φ u ( ξ ) − Φ v ( ξ ) .
Figure 22. Left: an initial data supported on [ a , b ] [a,b] [ a , b ] , but such that for θ > 0 \theta>0 θ > 0 the support contains points x < a x<a x < a . Right: a function u u u in the positively invariant set F {\mathcal F} F at ((9.12) ), with support contained in [ a , b ] [a,b] [ a , b ] .
4. In the next few steps we provide an a priori bound on the support of u ( θ , ⋅ ) u(\theta,\cdot) u ( θ , ⋅ ) . The fact that the support remains uniformly bounded in time is not trivial. Indeed, no matter how large we take the interval [ a , b ] [a,b] [ a , b ] , the set of all departure distributions supported on [ a , b ] [a,b] [ a , b ] is NOT positively invariant for the evolution ((9.2) ).
Example. As shown in Figure 22 , left, let
u ( x ) = { κ / ε if x ∈ [ a , a + ε ] , 0 otherwise. u(x)~=~\left\{\begin{array}{cl} \kappa/\varepsilon\quad &\hbox{if} ~~x\in [a, a+\varepsilon],\\[2mm]
0\qquad &\hbox{otherwise.}\end{array}\right. u ( x ) = { κ / ε 0 if x ∈ [ a , a + ε ] , otherwise.
Then all drivers departing at time x ∈ [ a + ε / 2 , a + ε ] x\in [a+\varepsilon/2, a+\varepsilon] x ∈ [ a + ε /2 , a + ε ] arrive after they have cleared the queue at the entrance of the highway, i.e. at time
y ( x ) > a + ( x − a ) κ / ε M + ℓ 0 ≥ a + κ 2 M + ℓ 0 . y(x) ~>~a+ (x-a) {\kappa/\varepsilon\over M}+\ell_0~\geq~ a + {\kappa\over 2M}+\ell_0\,. y ( x ) > a + ( x − a ) M κ / ε + ℓ 0 ≥ a + 2 M κ + ℓ 0 .
For ε > 0 \varepsilon>0 ε > 0 sufficiently small, since ψ ′ ( a ) > 0 \psi'(a)>0 ψ ′ ( a ) > 0 we obtain
φ ( x ) + ψ ( y ( x ) ) > φ ( x ) + ψ ( a + κ 2 M + ℓ 0 ) > φ ( a ) + ψ ( a + ℓ 0 ) \varphi(x) + \psi(y(x))~> ~\varphi(x) + \psi\Big( a + {\kappa\over 2M}+\ell_0\Big)~>~\varphi(a) + \psi(a+\ell_0) φ ( x ) + ψ ( y ( x )) > φ ( x ) + ψ ( a + 2 M κ + ℓ 0 ) > φ ( a ) + ψ ( a + ℓ 0 )
for all drivers departing at time x ∈ [ a + ε / 2 , a + ε ] x\in [a+\varepsilon/2, a+\varepsilon] x ∈ [ a + ε /2 , a + ε ] . As a consequence, all these drivers will have an advantage in departing before time a a a .
To establish an a priori bound on the support, we denote by ℓ 0 , ℓ m a x \ell_0, \ell_{max} ℓ 0 , ℓ ma x a lower and an upper bound on the duration of a trip, as in ((2.10) ), ((2.12) ). These constants depend only on the flux function f f f and on the total number κ \kappa κ of drivers. For any departure rate u ˉ \bar u u ˉ with ∥ u ˉ ∥ L 1 = κ \|\bar u\|_{{\bf L}^1}=\kappa ∥ u ˉ ∥ L 1 = κ , the corresponding cost Φ u ˉ ( x ) \Phi^{\bar u}(x) Φ u ˉ ( x ) to a driver departing at time x x x satisfies the bounds
Φ 0 ( x ) ≐ φ ( x ) + ψ ( x + ℓ 0 ) ≤ Φ u ˉ ( x ) ≤ φ ( x ) + ψ ( x + ℓ m a x ) ≐ Φ m a x ( x ) . \begin{equation}
\Phi^0(x)~\doteq ~\varphi(x) + \psi(x+\ell_0) ~\leq~\Phi^{\bar u}(x)~\leq ~\varphi(x) + \psi(x+\ell_{max})
~\doteq~\Phi^{max}(x). \tag*{(9.7)}
\end{equation} Φ 0 ( x ) ≐ φ ( x ) + ψ ( x + ℓ 0 ) ≤ Φ u ˉ ( x ) ≤ φ ( x ) + ψ ( x + ℓ ma x ) ≐ Φ ma x ( x ) . (9.7)
By the assumptions (A2) on φ , ψ \varphi,\psi φ , ψ , the map x ↦ Φ 0 ( x ) x\mapsto \Phi^0(x) x ↦ Φ 0 ( x ) is convex and satisfies
lim x → ± ∞ Φ 0 ( x ) = + ∞ . \lim_{x\to \pm \infty} \Phi^0(x)\,=\,+\infty. x → ± ∞ lim Φ 0 ( x ) = + ∞.
In particular, for any sufficiently large time b b b there exists a unique time a < b a<b a < b such that
Φ 0 ( a ) = Φ 0 ( b ) . \Phi^0(a)~=~\Phi^0(b). Φ 0 ( a ) = Φ 0 ( b ) .
Consider the upper bound on the second derivative
ω 2 ≐ sup u ∈ [ 0 , M / 2 ] f ′ ′ ( u ) , \omega_2~\doteq~\sup_{u\in [0,M/2]} f''(u), ω 2 ≐ u ∈ [ 0 , M /2 ] sup f ′′ ( u ) ,
and denote by L f / u L_{f/u} L f / u the Lipschitz constant of the function f ( u ) / u f(u)/u f ( u ) / u , restricted to the interval u ∈ [ 0 , M / 4 ] u\in [0, M/4] u ∈ [ 0 , M /4 ] . Choose δ > 0 \delta>0 δ > 0 so small that
κ ≤ 3 M 16 δ , δ < 1 2 ω 2 L , 1 2 δ > ℓ m a x , \begin{equation}
\kappa\,\leq \,{3M\over 16 \delta} \,,\qquad
\delta\,<\,{1\over 2\omega_2 L}\,,\qquad\qquad {1\over 2\delta} \,>\,\ell_{max}\,, \tag*{(9.8)}
\end{equation} κ ≤ 16 δ 3 M , δ < 2 ω 2 L 1 , 2 δ 1 > ℓ ma x , (9.8)
and, in addition,
δ < 3 M 16 L ( f ( M ) − f ( M / 4 ) ) , L Φ 8 δ ≥ L ψ ( ℓ m a x − ℓ 0 ) , \begin{equation}
\delta < \frac{3M}{16L(f(M)-f(M/4))}, \qquad \frac{L_\Phi}{8\delta} \geq L_\psi (\ell_{max}-\ell_0), \tag*{(9.9)}
\end{equation} δ < 16 L ( f ( M ) − f ( M /4 )) 3 M , 8 δ L Φ ≥ L ψ ( ℓ ma x − ℓ 0 ) , (9.9)
δ < 2 L ω 2 M , δ < L Φ L ψ L L f / u M . \begin{equation}
\delta < \frac{2}{L\omega_2M}, \qquad \delta < \frac{L_\Phi}{L_\psi L L_{f/u}M}. \tag*{(9.10)}
\end{equation} δ < L ω 2 M 2 , δ < L ψ L L f / u M L Φ . (9.10)
We introduce the additional points
a < a ′ < a ′ ′ < b ′ ′ < b ′ < b , a<a'<a''<b''<b'<b, a < a ′ < a ′′ < b ′′ < b ′ < b ,
determined by the identities
b ′ ′ = b − δ − 1 , Φ 0 ( a ′ ′ ) = Φ 0 ( b ′ ′ ) , a ′ = a + a ′ ′ 2 , b ′ = b + b ′ ′ 2 . \begin{equation}
b''= b-\delta^{-1},\qquad \Phi^0(a'') = \Phi^0(b''), \qquad a' = {a+a''
\over 2},\qquad b'={b+b''\over 2}\,. \tag*{(9.11)}
\end{equation} b ′′ = b − δ − 1 , Φ 0 ( a ′′ ) = Φ 0 ( b ′′ ) , a ′ = 2 a + a ′′ , b ′ = 2 b + b ′′ . (9.11)
We claim that, if the interval [ a , b ] [a,b] [ a , b ] is chosen large enough, then the family of all departure rates
F ≐ { u : [ a , b ] ↦ R + ; ∫ a b u ( x ) d x = κ , u ( x ) ≤ M ( x − a ) 4 ( a ′ ′ − a ) if x ∈ [ a , a ′ ′ ] , u ( x ) ≤ M ( b − x ) 4 ( b − b ′ ′ ) if x ∈ [ b ′ ′ , b ] } \begin{equation}
\begin{array}{rl} {\mathcal F}&\displaystyle\doteq~\bigg\{ u:[a,b]\mapsto\mathbb{R}_+\,;~~\int_a^b u(x)\, dx=\kappa,
\\[2mm]
&\displaystyle\qquad u(x)\leq {M(x-a)\over 4(a''-a)} ~~\hbox{if} ~~x\in [a, a''],\qquad u(x)\leq
{M(b-x)\over 4(b-b'')}~~\hbox{if~~} x\in [b'',b]\bigg\}
\end{array} \tag*{(9.12)}
\end{equation} F ≐ { u : [ a , b ] ↦ R + ; ∫ a b u ( x ) d x = κ , u ( x ) ≤ 4 ( a ′′ − a ) M ( x − a ) if x ∈ [ a , a ′′ ] , u ( x ) ≤ 4 ( b − b ′′ ) M ( b − x ) if x ∈ [ b ′′ , b ] } (9.12)
(see Figure 22 , right) is positively invariant. The positive invariance of the set F {\mathcal F} F will be proved by showing that, for any departure rate u ∈ F u\in{\mathcal F} u ∈ F , one has:
If x ∈ ] − ∞ , a ] ∪ [ b , + ∞ [ x\in \,]-\infty, a]\cup [b, +\infty[\, x ∈ ] − ∞ , a ] ∪ [ b , + ∞ [ , then Λ u ( x ) = 0 \Lambda^u(x)=0 Λ u ( x ) = 0 .
If x ∈ [ b ′ , b [ x\in [b', b[ x ∈ [ b ′ , b [ and u ( x ) = M ( b − x ) 4 ( b − b ′ ′ ) u(x)= {M(b-x)\over 4(b-b'')} u ( x ) = 4 ( b − b ′′ ) M ( b − x ) , then Λ u ( x ) < 0 \Lambda^u(x)< 0 Λ u ( x ) < 0 .
If x ∈ ] a , a ′ ] x\in \,]a, a'] x ∈ ] a , a ′ ] and u ( x ) = M ( x − a ) 4 ( a ′ ′ − a ) u(x)= {M(x-a)\over 4(a''-a)} u ( x ) = 4 ( a ′′ − a ) M ( x − a ) , then Λ u ( x ) < 0 \Lambda^u(x)<0 Λ u ( x ) < 0 .
If x ∈ [ b ′ ′ , b ′ [ x\in [b'', b'[ x ∈ [ b ′′ , b ′ [ and u ( x ) = M ( b − x ) 4 ( b − b ′ ′ ) u(x)= {M(b-x)\over 4(b-b'')} u ( x ) = 4 ( b − b ′′ ) M ( b − x ) , then Λ u ( x ) < 0 \Lambda^u(x)< 0 Λ u ( x ) < 0 .
If x ∈ ] a ′ , a ′ ′ ] x\in \,]a', a''] x ∈ ] a ′ , a ′′ ] and u ( x ) = M ( x − a ) 4 ( a ′ ′ − a ) u(x)= {M(x-a)\over 4(a''-a)} u ( x ) = 4 ( a ′′ − a ) M ( x − a ) , then Λ u ( x ) < 0 \Lambda^u(x)< 0 Λ u ( x ) < 0 .
5. As a preliminary, in this step we analyze the solution to ((2.1) ) with an initial data u ˉ ∈ F \bar u\in {\mathcal F} u ˉ ∈ F . We seek an upper bound on the cost Φ u ˉ \Phi^{\bar u} Φ u ˉ , sharper than the one in ((9.7) ).
Figure 23. Top: a departure rate u ˉ \bar u u ˉ as in ((9.12) ), and the corresponding effective rate u ˉ e \bar u^e u ˉ e in ((2.4) ). The function u ˉ ♯ ≥ u ˉ e \bar u^\sharp\geq \bar u^e u ˉ ♯ ≥ u ˉ e provides an upper bound for which the solution can be explicitly computed. Bottom: the rates of arrivals u ( L , x ) ≤ u ♯ ( L , x ) u(L,x)\leq u^\sharp(L,x) u ( L , x ) ≤ u ♯ ( L , x ) at the end of the highway.
Consider a departure rate u ˉ ∈ F \bar u\in {\mathcal F} u ˉ ∈ F . If u ˉ \bar u u ˉ takes values larger than the maximum flux M M M , we need to consider the effective rate u ˉ e \bar u^e u ˉ e , as shown in Figure 23 , top. Since the shaded area is ≤ κ \leq \kappa ≤ κ , if the first inequality in ((9.8) ) holds, this effective rate will satisfy
u ˉ e ( x ) = u ˉ ( x ) for x ∈ ] − ∞ , a ′ ′ ] ∪ [ b − 3 4 δ , + ∞ [ . \begin{equation}
\bar u^e(x)~=~\bar u(x)\qquad \hbox{for} \quad x\in \,]-\infty, a'']~\cup~\left[b-{3\over 4\delta}, ~+\infty\right[\,. \tag*{(9.13)}
\end{equation} u ˉ e ( x ) = u ˉ ( x ) for x ∈ ] − ∞ , a ′′ ] ∪ [ b − 4 δ 3 , + ∞ [ . (9.13)
To estimate the arrival time of various drivers, we use a comparison argument in terms of the departure rate
u ˉ ♯ ( x ) = { M ( x − a ) 4 ( a ′ ′ − a ) if x ∈ [ a , a ′ ′ ] , M ( b − x ) 4 ( b − b ′ ′ ) if x ∈ [ x ♯ ( 0 ) , b ] , M if x ∈ ] a ′ ′ , x ♯ ( 0 ) [ , 0 if x ∉ [ a , b ] . \begin{equation}
\displaystyle\bar u^\sharp(x)~=~\left\{ \begin{array}{cl}\displaystyle{M (x-a)\over 4(a''-a)} \qquad &\hbox{if} ~~x\in [a, a''],\\[4mm]
\displaystyle{M(b-x)\over 4(b-b'')}\qquad &\hbox{if~~} x\in [x^\sharp(0),b],\\[4mm]
M \qquad &\hbox{if~~} x\in \,\bigl]a'',\, x^\sharp(0)\bigr[\,,\\[4mm]
0 \qquad &\hbox{if~~} x\notin[a,b].\end{array}\right. \tag*{(9.14)}
\end{equation} u ˉ ♯ ( x ) = ⎩ ⎨ ⎧ 4 ( a ′′ − a ) M ( x − a ) 4 ( b − b ′′ ) M ( b − x ) M 0 if x ∈ [ a , a ′′ ] , if x ∈ [ x ♯ ( 0 ) , b ] , if x ∈ ] a ′′ , x ♯ ( 0 ) [ , if x ∈ / [ a , b ] . (9.14)
Here the point x ♯ ( 0 ) x^\sharp(0) x ♯ ( 0 ) is determined by the identity
∫ b ′ ′ x ♯ ( 0 ) ( M − M ( b − x ) 4 ( b − b ′ ′ ) ) d x = κ . \int_{b''}^{x^\sharp(0)} \left(M-{M (b-x)\over 4(b-b'')}\right) dx~=~\kappa. ∫ b ′′ x ♯ ( 0 ) ( M − 4 ( b − b ′′ ) M ( b − x ) ) d x = κ .
The above construction implies u ˉ ♯ ( x ) ≥ u ˉ e ( x ) \bar u^\sharp(x)\geq \bar u^e(x) u ˉ ♯ ( x ) ≥ u ˉ e ( x ) .
The solution of ((2.1) ) with initial data u ˉ ♯ \bar u^\sharp u ˉ ♯ can be constructed by characteristics:
u ♯ ( L , ξ + L f ′ ( u ˉ ♯ ( ξ ) ) ) = u ˉ ♯ ( ξ ) for ξ < a ′ ′ and for ξ > b ′ . u^\sharp\Big(L, \xi+ L f'\bigl(\bar u^\sharp(\xi)\bigr)\Big)\,=\,\bar u^\sharp(\xi)\qquad\qquad \hbox{for $\xi< a''$ and for $\xi>b'$.} u ♯ ( L , ξ + L f ′ ( u ˉ ♯ ( ξ ) ) ) = u ˉ ♯ ( ξ ) for ξ < a ′′ and for ξ > b ′ .
We observe that this solution also contains a shock, say located at x = x ♯ ( t ) x=x^\sharp(t) x = x ♯ ( t ) . Since the right state across the shock is ≤ M / 4 \leq M/4 ≤ M /4 , this shock has speed
x ˙ ♯ ( t ) ≤ f ( M ) − f ( M / 4 ) 3 M / 4 . \dot x^\sharp(t)~\leq~{f(M)-f(M/4)\over 3M/4}\,. x ˙ ♯ ( t ) ≤ 3 M /4 f ( M ) − f ( M /4 ) .
Choosing δ > 0 \delta>0 δ > 0 as in (9.8) we achieve
x ♯ ( L ) < b ′ = b − 1 2 δ . x^\sharp(L) ~<~ b'~=~b-{1\over 2\delta}\,. x ♯ ( L ) < b ′ = b − 2 δ 1 .
Moreover (see Figure 23 , bottom)
u ♯ ( L , x ) = 0 if x ∉ [ a + ℓ 0 , b + ℓ 0 ] . u^\sharp(L, x)~=~0\qquad\qquad \hbox{if}~~x\notin [a+\ell_0, \, b+\ell_0]. u ♯ ( L , x ) = 0 if x ∈ / [ a + ℓ 0 , b + ℓ 0 ] .
By the method of characteristics we obtain the inequalities
u ♯ ( L , x ) ≥ { λ ( x − a − ℓ 0 ) x ∈ [ a + ℓ 0 , a ′ ′ + ℓ 0 ] , μ ( b + ℓ 0 − x ) x ∈ [ b ′ + ℓ 0 , b + ℓ 0 ] , u^\sharp(L,x)~\geq~\left\{ \begin{array}{cl}\lambda (x-a-\ell_0) \qquad &x\in [a+\ell_0, a''+\ell_0],\\[1mm]
\mu (b+\ell_0 -x) \qquad &x\in [b'+\ell_0, b+\ell_0],\end{array}\right. u ♯ ( L , x ) ≥ { λ ( x − a − ℓ 0 ) μ ( b + ℓ 0 − x ) x ∈ [ a + ℓ 0 , a ′′ + ℓ 0 ] , x ∈ [ b ′ + ℓ 0 , b + ℓ 0 ] ,
for suitable constants
0 < λ ≤ δ ≤ μ . 0~<~\lambda~\leq~\delta~\leq~\mu. 0 < λ ≤ δ ≤ μ .
If the departure rate were u ˉ ♯ \bar u^\sharp u ˉ ♯ , the driver starting at x ∈ [ a , a ′ ] x\in [a,a'] x ∈ [ a , a ′ ] would arrive at time y ♯ ( x ) y^\sharp(x) y ♯ ( x ) implicitly determined by
∫ a x M ( s − a ) 4 ( a ′ ′ − a ) d s = ∫ a + ℓ 0 y ( x ) u ♯ ( L , s ) d s ≥ ∫ a + ℓ 0 y ( x ) λ ( s − a − ℓ 0 ) d s . \int_a^x {M(s-a)\over 4(a''-a)}\, ds~=~\int_{a+\ell_0}^{y(x)} u^\sharp(L, s) \, ds~\geq~\int_{a+\ell_0}^{y(x)} \lambda (s-a-\ell_0) \, ds. ∫ a x 4 ( a ′′ − a ) M ( s − a ) d s = ∫ a + ℓ 0 y ( x ) u ♯ ( L , s ) d s ≥ ∫ a + ℓ 0 y ( x ) λ ( s − a − ℓ 0 ) d s .
This yields
λ 2 ( y ( x ) − a − ℓ 0 ) 2 ≤ M 8 ( a ′ ′ − a ) ( x − a ) 2 , {\lambda\over 2}\bigl(y(x)-a-\ell_0\bigr)^2 ~\leq~ {M\over 8(a''-a)} (x-a)^2, 2 λ ( y ( x ) − a − ℓ 0 ) 2 ≤ 8 ( a ′′ − a ) M ( x − a ) 2 ,
and hence
y ( x ) − a − ℓ 0 ≤ M 4 λ ( a ′ ′ − a ) ⋅ ( x − a ) ≐ λ ^ ( x − a ) , \begin{equation}
y(x)-a-\ell_0~\leq~\sqrt{M\over 4\lambda(a''-a)} \cdot(x-a)~\doteq~\widehat\lambda (x-a), \tag*{(9.15)}
\end{equation} y ( x ) − a − ℓ 0 ≤ 4 λ ( a ′′ − a ) M ⋅ ( x − a ) ≐ λ ( x − a ) , (9.15)
Φ 0 ( x ) ≤ Φ u ˉ ( x ) ≤ Φ u ˉ ♯ ( x ) ≤ Φ 0 ( x ) + L ψ λ ^ ( x − a ) , for all x ∈ [ a , a ′ ] . \begin{equation}
\Phi^0(x)~\leq~\Phi^{\bar u}(x)~\leq~\Phi^{\bar u^\sharp}(x)~\leq~\Phi^0(x) + L_\psi \,\widehat\lambda (x-a),
\qquad\quad\hbox{for all}~x\in [a, a']. \tag*{(9.16)}
\end{equation} Φ 0 ( x ) ≤ Φ u ˉ ( x ) ≤ Φ u ˉ ♯ ( x ) ≤ Φ 0 ( x ) + L ψ λ ( x − a ) , for all x ∈ [ a , a ′ ] . (9.16)
An entirely similar argument yields
Φ 0 ( x ) ≤ Φ u ˉ ( x ) ≤ Φ u ˉ ♯ ( x ) ≤ Φ 0 ( x ) + L ψ μ ^ ( b − x ) , for all x ∈ [ b ′ , b ] . \begin{equation}
\Phi^0(x)~\leq~ \Phi^{\bar u}(x)~\leq~\Phi^{\bar u^\sharp}(x)~\leq~\Phi^0(x) + L_\psi \,\widehat\mu (b-x),
\qquad\quad\hbox{for all}~x\in [b', b]. \tag*{(9.17)}
\end{equation} Φ 0 ( x ) ≤ Φ u ˉ ( x ) ≤ Φ u ˉ ♯ ( x ) ≤ Φ 0 ( x ) + L ψ μ ( b − x ) , for all x ∈ [ b ′ , b ] . (9.17)
Using ((9.16) )-((9.17) ) we shall prove the claims (i)–(v), assuming that b b b is sufficiently large.
Figure 24. The total cost Φ u ˉ ( x ) \Phi^{\bar u}(x) Φ u ˉ ( x ) to drivers with departure time x x x . Here Φ 0 \Phi^0 Φ 0 is a lower bound, corresponding to an empty road. The upper bound Φ ♯ ≐ Φ u ˉ ♯ \Phi^\sharp \doteq \Phi^{\bar u^\sharp} Φ ♯ ≐ Φ u ˉ ♯ is obtained by a comparison with the departure rate ((9.14) ).
6. To prove (i), let u ˉ ∈ F \bar u\in {\mathcal F} u ˉ ∈ F and call
K ≐ Φ 0 ( a ) = Φ 0 ( b ) . \begin{equation}
K~\doteq~\Phi^0(a)~=~\Phi^0(b). \tag*{(9.18)}
\end{equation} K ≐ Φ 0 ( a ) = Φ 0 ( b ) . (9.18)
Since
Φ u ˉ ( x ) ≥ Φ 0 ( x ) ≥ K for all x ∉ ] a , b [ , \Phi^{\bar u}(x)~\geq~\Phi^0(x)~\geq~K\qquad\qquad\hbox{for all}~x\notin \,]a,b[\,, Φ u ˉ ( x ) ≥ Φ 0 ( x ) ≥ K for all x ∈ / ] a , b [ ,
it suffices to show that
Φ u ˉ ( x ) ≤ K for all x ∈ [ a , b ] . \begin{equation}
\Phi^{\bar u}(x)~\leq~K\qquad\qquad\hbox{for all}~x\in [a,b]. \tag*{(9.19)}
\end{equation} Φ u ˉ ( x ) ≤ K for all x ∈ [ a , b ] . (9.19)
We first prove (9.19) for x ∈ [ a ′ , b ′ ] x \in [a',b'] x ∈ [ a ′ , b ′ ] . By (5.6) and (5.7) , it is possible to choose K K K sufficiently large so that
\Phi^0_x (x) \le -{L_\varphi \over 2} \quad \hbox{for all}~x \le a'', \qquad \Phi^0_x (x) \ge {L_\Phi \over 2}\quad \mbox{and} \quad \psi'(x) > \frac{L_\psi}2 \quad \hbox{for all}~x \ge b''.
Therefore
1 δ = b − b ′ ′ ≤ 2 L Φ ( Φ 0 ( b ) − Φ 0 ( b ′ ′ ) ) = 2 L Φ ( Φ 0 ( a ) − Φ 0 ( a ′ ′ ) ) ≤ 2 L φ L Φ ( a ′ ′ − a ) \begin{equation}
\frac1\delta = b - b'' \le \frac2{L_\Phi}(\Phi^0(b)-\Phi^0(b'')) = \frac2{L_\Phi}(\Phi^0(a)-\Phi^0(a'')) \le \frac{2L_\varphi}{L_\Phi} (a''-a) \tag*{(9.20)}
\end{equation} δ 1 = b − b ′′ ≤ L Φ 2 ( Φ 0 ( b ) − Φ 0 ( b ′′ )) = L Φ 2 ( Φ 0 ( a ) − Φ 0 ( a ′′ )) ≤ L Φ 2 L φ ( a ′′ − a ) (9.20)
In particular for x ∈ [ a ′ , b ′ ] x \in [a',b'] x ∈ [ a ′ , b ′ ] it holds
Φ u ˉ ( x ) ≤ Φ 0 ( x ) + L ψ ( ℓ m a x − ℓ 0 ) ≤ max { Φ u ˉ ( a ′ ) , Φ u ˉ ( b ′ ) } + L ψ ( ℓ m a x − ℓ 0 ) . \Phi^{\bar u}(x)~\leq~ \Phi_0(x) +L_\psi(\ell_{max}-\ell_0)~\leq~\max\{ \Phi^{\bar u}(a'),\Phi^{\bar u}(b')\}
+ L_\psi(\ell_{max}- \ell_0). Φ u ˉ ( x ) ≤ Φ 0 ( x ) + L ψ ( ℓ ma x − ℓ 0 ) ≤ max { Φ u ˉ ( a ′ ) , Φ u ˉ ( b ′ )} + L ψ ( ℓ ma x − ℓ 0 ) .
We have
Φ u ˉ ( a ′ ) ≤ Φ 0 ( a ′ ) + L ψ ( ℓ m a x − ℓ 0 ) ≤ Φ 0 ( a ) − L φ 2 ( a ′ − a ) + L ψ ( ℓ m a x − ℓ 0 ) ≤ K − L Φ 8 δ + L ψ ( ℓ m a x − ℓ 0 ) ≤ K \Phi^{\bar u}(a') \le \Phi^0(a') + L_\psi (\ell_{max}-\ell_0) \le \Phi^0(a) - \frac{L_{\varphi}}2(a'-a) + L_\psi(\ell_{max}-\ell_0) \le K - \frac{L_\Phi}{8 \delta} + L_\psi (\ell_{max}-\ell_0) \le K Φ u ˉ ( a ′ ) ≤ Φ 0 ( a ′ ) + L ψ ( ℓ ma x − ℓ 0 ) ≤ Φ 0 ( a ) − 2 L φ ( a ′ − a ) + L ψ ( ℓ ma x − ℓ 0 ) ≤ K − 8 δ L Φ + L ψ ( ℓ ma x − ℓ 0 ) ≤ K
by (9.9) , and similarly
Φ u ˉ ( b ′ ) ≤ Φ 0 ( b ′ ) + L ψ ( ℓ m a x − ℓ 0 ) ≤ K − L Φ 2 ( b − b ′ ) + L ψ ( ℓ m a x − ℓ 0 ) = K − L Φ 4 δ + L ψ ( ℓ m a x − ℓ 0 ) ≤ K . \Phi^{\bar u}(b') \le \Phi^0(b') + L_\psi (\ell_{max}-\ell_0) \le K - \frac{L_\Phi}{2}(b-b') + L_\psi (\ell_{max}-\ell_0) = K - \frac{L_\Phi}{4\delta} + L_\psi (\ell_{max}-\ell_0) \le K. Φ u ˉ ( b ′ ) ≤ Φ 0 ( b ′ ) + L ψ ( ℓ ma x − ℓ 0 ) ≤ K − 2 L Φ ( b − b ′ ) + L ψ ( ℓ ma x − ℓ 0 ) = K − 4 δ L Φ + L ψ ( ℓ ma x − ℓ 0 ) ≤ K .
We now prove (9.19) for x ∈ [ a , a ′ ] x \in [a,a'] x ∈ [ a , a ′ ] . Since Φ u ˉ ( x ) ≤ Φ u ˉ ♯ ( x ) \Phi^{\bar u}(x) \le \Phi^{\bar u^\sharp} (x) Φ u ˉ ( x ) ≤ Φ u ˉ ♯ ( x ) , it is sufficient to prove that Φ u ˉ ♯ ( x ) ≤ K \Phi^{\bar u^\sharp} (x) \le K Φ u ˉ ♯ ( x ) ≤ K . It holds
Φ u ˉ ♯ ( x ) = φ ( x ) + ψ ( y ♯ ( x ) ) ≤ Φ 0 ( x ) + L ψ ( y ♯ ( x ) − x − ℓ 0 ) ≤ K − L φ 2 ( x − a ) + L ψ ( y ♯ ( x ) − x − ℓ 0 ) \Phi^{\bar u^\sharp}(x) = \varphi (x) + \psi (y^\sharp(x))\le \Phi^0(x) + L_\psi (y^\sharp(x)-x-\ell_0) \le K - \frac{L_{\varphi}}2(x-a) + L_\psi (y^\sharp(x)-x-\ell_0) Φ u ˉ ♯ ( x ) = φ ( x ) + ψ ( y ♯ ( x )) ≤ Φ 0 ( x ) + L ψ ( y ♯ ( x ) − x − ℓ 0 ) ≤ K − 2 L φ ( x − a ) + L ψ ( y ♯ ( x ) − x − ℓ 0 )
We now prove that y ♯ ( x ) − x − ℓ 0 ≤ L φ 2 L ψ ( x − a ) y^\sharp(x)-x-\ell_0 \le \frac{L_\varphi}{2L_\psi}(x-a) y ♯ ( x ) − x − ℓ 0 ≤ 2 L ψ L φ ( x − a ) . Notice that y ♯ ( x ) = y ♯ ( L , x ) y^\sharp (x)= y^\sharp(L,x) y ♯ ( x ) = y ♯ ( L , x ) where
y^\sharp(t,x)= x + \int_0^t \frac{f(u(s,y^\sharp(s,x)))}{u(s,y^\sharp(s,x))}ds \qquad \mbox{for }t \in [0,L].
By the method of characteristics, for every s ∈ [ 0 , L ] s \in [0,L] s ∈ [ 0 , L ] it holds u ( s , y ♯ ( s , x ) ) ∈ [ 0 , u ˉ ( x ) ] u(s,y^\sharp(s,x)) \in [0, \bar u(x)] u ( s , y ♯ ( s , x )) ∈ [ 0 , u ˉ ( x )] , therefore
y ♯ ( L , x ) = x + ℓ 0 + ∫ 0 L ( f ( u ( s , y ♯ ( s , x ) ) ) u ( s , y ♯ ( s , x ) ) − f ′ ( 0 ) ) d s ≤ x + ℓ 0 + L L f / u u ˉ ( x ) ≤ x + ℓ 0 + L L f / u M 4 ( a ′ ′ − a ) ( x − a ) ≤ x + ℓ 0 + L φ 2 L ψ ( x − a ) \begin{array}{rl}
y^\sharp (L,x) = &\displaystyle~ x + \ell_0 + \int_{0}^L \left(\frac{f(u(s,y^\sharp(s,x)))}{u(s,y^\sharp(s,x))} - f'(0)\right) ds \le x + \ell_0 + L L_{f/u} \bar u (x) \\[4mm]
\le &\displaystyle~ x+\ell_0 + L L_{f/u} \frac{M}{4(a''-a)}(x-a) \le ~ x+\ell_0 + \frac{L_\varphi}{2L_\psi}(x-a)
\end{array} y ♯ ( L , x ) = ≤ x + ℓ 0 + ∫ 0 L ( u ( s , y ♯ ( s , x )) f ( u ( s , y ♯ ( s , x ))) − f ′ ( 0 ) ) d s ≤ x + ℓ 0 + L L f / u u ˉ ( x ) x + ℓ 0 + L L f / u 4 ( a ′′ − a ) M ( x − a ) ≤ x + ℓ 0 + 2 L ψ L φ ( x − a )
provided δ < L Φ L ψ L L f / u M \delta < \frac{L_\Phi}{L_\psi L L_{f/u} M} δ < L ψ L L f / u M L Φ , thanks to (9.20) .
We prove (9.19) for x ∈ [ b ′ , b ] x \in [b',b] x ∈ [ b ′ , b ] .
Φ u ˉ ♯ ( x ) = φ ( x ) + ψ ( y ♯ ( x ) ) ≤ Φ 0 ( x ) + L ψ ( y ♯ ( x ) − x − ℓ 0 ) ≤ K − L Φ 2 ( b − x ) + L ψ ( y ♯ ( x ) − x − ℓ 0 ) \Phi^{\bar u^\sharp}(x) = \varphi (x) + \psi (y^\sharp(x))\le \Phi^0(x) + L_\psi (y^\sharp(x)-x-\ell_0) \le K - \frac{L_{\Phi}}2(b-x) + L_\psi (y^\sharp(x)-x-\ell_0) Φ u ˉ ♯ ( x ) = φ ( x ) + ψ ( y ♯ ( x )) ≤ Φ 0 ( x ) + L ψ ( y ♯ ( x ) − x − ℓ 0 ) ≤ K − 2 L Φ ( b − x ) + L ψ ( y ♯ ( x ) − x − ℓ 0 )
We now prove that y ♯ ( x ) − x − ℓ 0 ≤ L Φ 2 L ψ ( b − x ) y^\sharp(x)-x-\ell_0 \le \frac{L_\Phi}{2L_\psi}(b-x) y ♯ ( x ) − x − ℓ 0 ≤ 2 L ψ L Φ ( b − x ) . By the method of characteristics, for every s ∈ [ 0 , L ] s \in [0,L] s ∈ [ 0 , L ] it holds u ( s , y ♯ ( s , x ) ) ∈ [ u ˉ ( x ) , u ˉ ( x ~ ) ] u(s,y^\sharp(s,x)) \in [\bar u(x), \bar u (\tilde x)] u ( s , y ♯ ( s , x )) ∈ [ u ˉ ( x ) , u ˉ ( x ~ )] for x ~ ∈ [ b ′ ′ , b ] \tilde x \in [b'',b] x ~ ∈ [ b ′′ , b ] such that u ˉ ♯ ( L , y ♯ ( x ) ) = u ˉ ♯ ( x ~ ) \bar u^{\sharp}(L,y^\sharp(x))=\bar u^\sharp(\tilde x) u ˉ ♯ ( L , y ♯ ( x )) = u ˉ ♯ ( x ~ ) . In particular y ♯ ( x ) ≥ x + f ( u ˉ ( x ) ) u ˉ ( x ) L y^\sharp (x) \ge x + \frac{f(\bar u(x))}{\bar u(x)}L y ♯ ( x ) ≥ x + u ˉ ( x ) f ( u ˉ ( x )) L and therefore by the method of characteristics u ˉ ♯ ( L , y ♯ ( x ) ) = u ˉ ♯ ( x ~ ) \bar u^{\sharp}(L,y^\sharp(x))=\bar u^\sharp(\tilde x) u ˉ ♯ ( L , y ♯ ( x )) = u ˉ ♯ ( x ~ ) implies that
L ( f ′ ( u ˉ ♯ ( x ~ ) ) − f ( u ˉ ♯ ( x ) ) u ˉ ♯ ( x ) ) ≥ x − x ~ = 4 M δ ( u ˉ ♯ ( x ~ ) − u ˉ ♯ ( x ) ) . L\left(f'(\bar u^\sharp (\tilde x))- \frac{f(\bar u^\sharp(x))}{\bar u^\sharp(x)}\right) ~\ge ~x-\tilde x ~= ~\frac{4}{M\delta}(\bar u^{\sharp}(\tilde x) - \bar u^\sharp (x)) . L ( f ′ ( u ˉ ♯ ( x ~ )) − u ˉ ♯ ( x ) f ( u ˉ ♯ ( x )) ) ≥ x − x ~ = M δ 4 ( u ˉ ♯ ( x ~ ) − u ˉ ♯ ( x )) .
Therefore
4 M δ ( u ˉ ♯ ( x ~ ) − u ˉ ♯ ( x ) ) ≤ L ( f ′ ( u ˉ ♯ ( x ~ ) ) − f ( u ˉ ♯ ( x ) ) u ˉ ♯ ( x ) ) ≤ L ω 2 u ˉ ♯ ( x ~ ) , \frac4{M\delta}(\bar u^{\sharp}(\tilde x) - \bar u^\sharp (x)) ~ \le ~ L\left(f'(\bar u^\sharp (\tilde x))- \frac{f(\bar u^\sharp(x))}{\bar u^\sharp(x)}\right)~ \le ~L \omega_2 \bar u^\sharp (\tilde x) , M δ 4 ( u ˉ ♯ ( x ~ ) − u ˉ ♯ ( x )) ≤ L ( f ′ ( u ˉ ♯ ( x ~ )) − u ˉ ♯ ( x ) f ( u ˉ ♯ ( x )) ) ≤ L ω 2 u ˉ ♯ ( x ~ ) ,
which implies
\bar u^\sharp(\tilde x) \le \frac1{1-\frac{L\omega_2M\delta}4}\bar u^\sharp(x) \le 2 \bar u^\sharp(x) \qquad \mbox{for} \quad \delta < \frac{2}{L\omega_2M}.
We can then estimate
y ♯ ( x ) − x + ℓ 0 = x + ℓ 0 + ∫ 0 L ( f ( u ( s , y ♯ ( s , x ) ) ) u ( s , y ♯ ( s , x ) ) − f ′ ( 0 ) ) d s ≤ x + ℓ 0 + 2 L L f / u u ˉ ♯ ( x ) = x + ℓ 0 + 1 2 L L f / u M δ ( b − x ) ≤ L Φ 2 L ψ ( b − x ) , \begin{array}{rl}
y^\sharp(x)-x+\ell_0 &= \displaystyle~ x + \ell_0 + \int_0^L \left(\frac{f\bigl(u(s,y^\sharp(s,x))\bigr)}{u(s,y^\sharp(s,x))}-f'(0)\right)ds
\\[4mm]
&\displaystyle\le~ x + \ell_0 + 2L L_{f/u}\bar u^\sharp(x) \\[4mm]
&= ~ \displaystyle x + \ell_0 + \frac12L L_{f/u} M\delta (b-x) ~\le~ \frac{L_\Phi}{2L_\psi}(b-x),
\end{array} y ♯ ( x ) − x + ℓ 0 = x + ℓ 0 + ∫ 0 L ( u ( s , y ♯ ( s , x )) f ( u ( s , y ♯ ( s , x )) ) − f ′ ( 0 ) ) d s ≤ x + ℓ 0 + 2 L L f / u u ˉ ♯ ( x ) = x + ℓ 0 + 2 1 L L f / u M δ ( b − x ) ≤ 2 L ψ L Φ ( b − x ) ,
provided that δ < L Φ L ψ L L f / u M \delta < \frac{L_\Phi}{L_\psi L L_{f/u} M} δ < L ψ L L f / u M L Φ as in ((9.10) ).
7. To prove (iv), we observe that for x ∈ [ b ′ ′ , b ′ ] x\in [b'',b'] x ∈ [ b ′′ , b ′ ] by ((5.7) ) one has
Φ 0 ( x ) ≥ Φ 0 ( b ′ ′ ) = Φ 0 ( b − δ − 1 ) ≥ Φ 0 ( b ) − L Φ δ − 1 . \begin{equation}
\Phi^0(x)~\geq~\Phi^0(b'') ~=~ \Phi^0(b-\delta^{-1})~\geq~\Phi^0(b) - L_{\Phi}\delta^{-1}. \tag*{(9.21)}
\end{equation} Φ 0 ( x ) ≥ Φ 0 ( b ′′ ) = Φ 0 ( b − δ − 1 ) ≥ Φ 0 ( b ) − L Φ δ − 1 . (9.21)
For x ∈ [ b ′ ′ , b ′ ] x\in [b'', b'] x ∈ [ b ′′ , b ′ ] , assuming u ˉ ( x ) = M ( b − x ) 4 ( b − b ′ ′ ) \bar u(x)= {M(b-x)\over 4(b-b'')} u ˉ ( x ) = 4 ( b − b ′′ ) M ( b − x ) , the positive term on the right hand side of ((9.4) ) can thus be bounded as
Λ + u ˉ ( x ) ≤ ∫ a b u ˉ ( ξ ) [ Φ u ˉ ( ξ ) − Φ u ˉ ( x ) ] + d ξ ≤ κ [ Φ 0 ( b ) − Φ 0 ( b ′ ′ ) ] ≤ κ ⋅ L Φ δ − 1 . \begin{equation}
\Lambda^{\bar u}_+(x)~\leq~\int_a^b \bar u(\xi)\Big[ \Phi^{\bar u}(\xi)-\Phi^{\bar u}(x)\Big]_+\, d\xi~\leq~\kappa
\bigl[\Phi^0(b) - \Phi^0(b'')\Big]~\leq~\kappa\cdot L_\Phi \,\delta^{-1}. \tag*{(9.22)}
\end{equation} Λ + u ˉ ( x ) ≤ ∫ a b u ˉ ( ξ ) [ Φ u ˉ ( ξ ) − Φ u ˉ ( x ) ] + d ξ ≤ κ [ Φ 0 ( b ) − Φ 0 ( b ′′ ) ] ≤ κ ⋅ L Φ δ − 1 . (9.22)
On the other hand, the negative term can be estimated as
Λ − u ˉ ( x ) ≐ ∫ u ˉ ( x ) [ Φ u ( x ) − Φ u ˉ ( ξ ) ] + d ξ ≥ M 8 ⋅ ∫ [ Φ 0 ( b − δ − 1 ) − Φ m a x ( ξ ) ] + d ξ . \begin{equation}
\Lambda^{\bar u}_-(x)~\doteq~\int \bar u(x)\Big[ \Phi^u(x)-\Phi^{ \bar u}(\xi)\Big]_+\, d\xi~\geq~{M\over 8} \cdot\int\Big[ \Phi^0(b-\delta^{-1}) -
\Phi^{max}(\xi)\Big]_+\, d\xi. \tag*{(9.23)}
\end{equation} Λ − u ˉ ( x ) ≐ ∫ u ˉ ( x ) [ Φ u ( x ) − Φ u ˉ ( ξ ) ] + d ξ ≥ 8 M ⋅ ∫ [ Φ 0 ( b − δ − 1 ) − Φ ma x ( ξ ) ] + d ξ . (9.23)
Observe that the right hand side of ((9.22) ) is uniformly bounded regardless of the choice of K K K and hence of the interval [ a , b ] [a,b] [ a , b ] (see Figure 25 ). On the other hand, the loss term ((9.23) ) becomes arbitrarily large as K → ∞ K\to \infty K → ∞ . By choosing K K K large enough, the difference Λ + u ˉ ( x ) − Λ − u ˉ ( x ) \Lambda^{\bar u}_+(x)- \Lambda^{\bar u}_-(x) Λ + u ˉ ( x ) − Λ − u ˉ ( x ) can thus be rendered arbitrarily large and negative, uniformly for all x ∈ [ b ′ ′ , b ′ ] x\in [b'', b'] x ∈ [ b ′′ , b ′ ] . This proves (iv). The proof of (v) is entirely similar.
Figure 25. The positive and negative terms in ((9.22) )-((9.23) ) are proportional to the two shaded areas. As K → + ∞ K\to+\infty K → + ∞ , the gain term remains uniformly bounded while the loss term becomes arbitrarily large.
8. To prove (ii), let x ∈ [ b ′ , b [ x\in [b',b[\, x ∈ [ b ′ , b [ and assume u ˉ ( x ) = M ( b − x ) 4 ( b − b ′ ′ ) \bar u(x)= {M(b-x)\over 4(b-b'')} u ˉ ( x ) = 4 ( b − b ′′ ) M ( b − x ) . By (5.7) , in this case the gain term can be bounded by
Λ + u ˉ ( x ) = ∫ a b u ˉ ( ξ ) [ Φ u ˉ ( ξ ) − Φ u ˉ ( x ) ] + d ξ ≤ κ [ Φ 0 ( b ) − Φ 0 ( x ) ] + ≤ κ ⋅ L Φ ( b − x ) . \begin{equation}
\Lambda^{\bar u}_+(x)~=~\int_a^b \bar u(\xi) \Big[ \Phi^{\bar u}(\xi) - \Phi^{\bar u} (x)\Big]_+\, d\xi
~\leq~\kappa\Big[ \Phi^0(b)-\Phi^0(x)\Big]_+~\leq~\kappa \cdot L_\Phi (b-x). \tag*{(9.24)}
\end{equation} Λ + u ˉ ( x ) = ∫ a b u ˉ ( ξ ) [ Φ u ˉ ( ξ ) − Φ u ˉ ( x ) ] + d ξ ≤ κ [ Φ 0 ( b ) − Φ 0 ( x ) ] + ≤ κ ⋅ L Φ ( b − x ) . (9.24)
On the other hand, the loss term is
Λ − u ˉ ( x ) = u ˉ ( x ) ∫ a b [ Φ u ˉ ( x ) − Φ u ˉ ( ξ ) ] + d ξ ≥ M 4 ( b − b ′ ′ ) ( b − x ) ⋅ ∫ a b [ Φ 0 ( x ) − Φ m a x ( ξ ) ] + d ξ . \begin{equation}
\Lambda^{\bar u}_- (x)~=~\bar u(x) \int_a^b \Big[ \Phi^{\bar u}(x) - \Phi^{\bar u} (\xi)\Big]_+\, d\xi~\geq~
{M\over 4(b-b'')} (b-x) \cdot \int_a^b\Big[ \Phi^0(x) - \Phi^{max}(\xi)\Big]_+\, d\xi. \tag*{(9.25)}
\end{equation} Λ − u ˉ ( x ) = u ˉ ( x ) ∫ a b [ Φ u ˉ ( x ) − Φ u ˉ ( ξ ) ] + d ξ ≥ 4 ( b − b ′′ ) M ( b − x ) ⋅ ∫ a b [ Φ 0 ( x ) − Φ ma x ( ξ ) ] + d ξ . (9.25)
By choosing K K K large enough the integral on the right hand side of ((9.25) ) can be rendered arbitrarily large, uniformly for x ∈ [ b ′ , b ] x\in [b',b] x ∈ [ b ′ , b ] . This achieves the desired inequality Λ − u ˉ ( x ) > Λ + u ˉ ( x ) \Lambda^{\bar u}_- (x)> \Lambda^{\bar u}_+ (x) Λ − u ˉ ( x ) > Λ + u ˉ ( x ) , for all x ∈ [ b ′ , b [ x\in [b', b[\, x ∈ [ b ′ , b [ . The proof of (iii) is entirely similar. 9. Let an initial departure rate u ( 0 , ⋅ ) = u ˉ ∈ L 1 ( R ) ∩ L ∞ ( R ) u(0,\cdot)=\bar u\in {\bf L}^1(\mathbb{R})\cap{\bf L}^\infty(\mathbb{R}) u ( 0 , ⋅ ) = u ˉ ∈ L 1 ( R ) ∩ L ∞ ( R ) be given, with compact support. For any time interval θ ∈ [ 0 , T ] \theta\in [0,T] θ ∈ [ 0 , T ] , by the uniform boundedness of the support of u ( θ , ⋅ ) u(\theta,\cdot) u ( θ , ⋅ ) proved in steps 4–8, we can use ((9.5) ) and obtain
∥ u ( θ , ⋅ ) ∥ L ∞ ≤ exp { C 0 ( 1 + R ) T } ⋅ l ∥ u ˉ ∥ L ∞ for all θ ∈ [ 0 , T ] . \begin{equation}
\bigl\| u(\theta, \cdot)\bigr\|_{{\bf L}^\infty}~\leq~ \exp \bigl\{ C_0(1+R) T\bigr\}\cdot l\| \bar u\|_{{\bf L}^\infty}
\qquad\qquad\hbox{for all}~\theta\in [0,T]. \tag*{(9.26)}
\end{equation} u ( θ , ⋅ ) L ∞ ≤ exp { C 0 ( 1 + R ) T } ⋅ l ∥ u ˉ ∥ L ∞ for all θ ∈ [ 0 , T ] . (9.26)
If now u , v ∈ L 1 ( R ) ∩ L ∞ ( R ) u,v\in {\bf L}^1(\mathbb{R})\cap{\bf L}^\infty(\mathbb{R}) u , v ∈ L 1 ( R ) ∩ L ∞ ( R ) satisfy the same bounds as above, then
∥ Φ u − Φ v ∥ L 1 = O ( 1 ) ⋅ ∥ y u − y v ∥ L 1 = O ( 1 ) ⋅ ∥ u − v ∥ L 1 . \begin{equation}
\bigl\|\Phi^u-\Phi^v\bigr\|_{{\bf L}^1}~=~{\mathcal O}(1)\cdot \|y^u - y^v\|_{{\bf L}^1}~=~{\mathcal O}(1)\cdot \|u-v\|_{{\bf L}^1}\,. \tag*{(9.27)}
\end{equation} Φ u − Φ v L 1 = O ( 1 ) ⋅ ∥ y u − y v ∥ L 1 = O ( 1 ) ⋅ ∥ u − v ∥ L 1 . (9.27)
Indeed, the first inequality follows from ((9.1) ) and the Lipschitz continuity of the cost function ψ \psi ψ . The second inequality follows from ((4.1) ).
In turn, ((9.6) ) shows the Lipschitz continuity of the map u ↦ Λ ( u ) u\mapsto \Lambda(u) u ↦ Λ ( u ) , restricted to a domain of functions uniformly bounded in L 1 ( R ) ∩ L ∞ ( R ) {\bf L}^1(\mathbb{R})\cap{\bf L}^\infty(\mathbb{R}) L 1 ( R ) ∩ L ∞ ( R ) . By the standard theory of ODEs in Banach spaces (see for example [22 , 26 ] ), this yields the global existence of a unique solution to the Cauchy problem ((9.4) ).
Acknowledgments. The research of A. Bressan and D. L. Harmon was partially supported by NSF with grant DMS-2306926, “Regularity and approximation of solutions to conservation laws". The research of E. Marconi was partially supported by Gnampa - INDAM project 2026 “Discrete to continuum limit in traffic and related models".
The authors acknowledge the use of ChatGPT to check for misprints and inaccuracies. The manuscript was written entirely by the authors, who take full responsibility for its mathematical content and correctness.