Keywords

Introduction

Equilibrium problems have been studied over four decades and their formulation has become fairly complex. Most papers in the literature to date are concerned with the equilibrium states of these problems, where equilibrium is defined depending on the context of the problem: Wardrop [5, 15, 16, 27], Nash-Cournot [10, 11, 21, 27], market [4, 20, 27], physical/mathematical equilibrium [1, 2, 23, 25] and many others. The classes of equilibrium problems have been shown to be equivalent to different types of variational inequality problems both finite- and infinite-dimensional, as is the case in all cited papers above. Variational inequalities are well-studied mathematical constructs that allow substantial qualitative studies of equilibrium states of various problems. In their finite-dimensional form, they provide a (collection of) solution(s) to an equilibrium problem.

Time-dependent equilibrium problems (TDEP) (see, for instance, [1, 16, 19]) are those whose data depend on a parameter, usually taken to mean physical time. For instance, in a traffic network problem, the flows on routes will be time-dependent, and thus the demands on those routes can be thought of varying with time. In a game setting (see [10, 11]), strategies, as well as players’ utilities or payoffs can be time-dependent. Infinite-dimensional variational inequalities provide a mathematical framework for studying equilibrium states of TDEP which are described as a succession of equilibrium states over a time interval of interest, generically denoted by t ∈ [0, T].

Much studies have been devoted to identifying and computing—theoretically and algorithmically—the equilibrium states of such problems (see for instance [18, 22] and the references therein). We argue here that the continual drive for finding equilibria is an incomplete venue of investigation in the class of TDEP since such privileged states are not necessarily observed. For instance, in a classic traffic network equilibrium problem the non-equilibrium states are given by flow patterns on the network that do not satisfy the Wardrop-type conditions. To complete the investigation of TDEP, we propose to study their evolving states.

To this end, we associate to a TDEP a nonsmooth (projected) differential equation on a subset of the space \(L^{2}([0,T], \mathbb{R}^{k})\) whose stationary solutions also describe market equilibria, traffic equilibria, Nash/Cournot equilibria, etc. [8–11, 14]. Consequently, any non-stationary solution of the projected equation represents a time-dependent, evolving state of the underlying problem.

In this paper we show how non-equilibrium states of a TDEP can be computed with the help of the associated projected differential equation, and with the help of a selection of initial conditions for this equation. While it is known that, in theory, the projected equation on a specific type of Lebesgue integrable function space describes the dynamic evolution of an initial state of a problem towards later states at t > 0 (see [8, 12] where this was first introduced as double layer dynamics), there is no formalized approach to compute and visualize these evolutions in the literature to date.

The organization of this paper is as follows: We start by recalling several important concepts in section “PrDE.” In section “TDEP,” we briefly review (TDEPs) and their relation to projected differential equations. Section “Evolution Solutions of TDEP” outlines our computational method and section “Examples and Discussion” shows the method applied to several types of TDEP. We close with a few concluding remarks.

Preliminaries

PrDE

We start by recalling several concepts which are related to monotonicity. Let X be a Hilbert space of arbitrary dimension, let \(\mathbb{K} \subset X\) be a non-empty, closed and convex set and let \(F: \mathbb{K} \rightarrow X\) a mapping.

Definition 1.

The problem of finding a point \(x^{{\ast}}\in \mathbb{K}\) so that

$$\displaystyle{\langle F(x^{{\ast}}),y - x^{{\ast}}\rangle \geq 0,\,\forall y \in \mathbb{K}}$$

is called a variational inequality problem. The set of points \(x^{{\ast}}\in \mathbb{K}\) satisfying the inequality above is the solution set of the variational inequality, denoted by \(SOLV I(F, \mathbb{K})\).

Since their introduction in the 1960s [6, 26], VI problems have been extensively used in the study of Wardrop, Nash, Walras, Cournot and mathematical physics equilibrium problems. A classic result on the existence of solutions x ∗ as in Definition 1 is that of a compact set \(\mathbb{K}\) and a continuous mapping F [25].

Definition 2.

The tangent cone to a point \(x \in \mathbb{K}\) is defined to be

$$\displaystyle{ T_{\mathbb{K}}(x) = \overline{\bigcup _{\delta>0}\frac{1} {\delta } \left (\mathbb{K} - x\right )}. }$$

In general a VI problem can be associated with the following differential equation (see [1, 12, 17, 27]):

Definition 3.

Consider the VI problem of Definition 1. The discontinuous ordinary differential equation,

$$\displaystyle{ \frac{dx(\tau )} {d\tau } = P_{T_{\mathbb{K}}(x(\tau ))}(-F(x(\tau ))):=\varPi _{\mathbb{K}}(x(\tau ),-F(x(\tau ))),\;\;x(0) \in \mathbb{K}, }$$
(1)

where \(P_{T_{\mathbb{K}}(z)},\,z \in X\) is the closest element mapping from X to the set \(T_{\mathbb{K}}(z) \in X\), is called a projected differential equation (PrDE).

It is known that Eq. (1) has unique solutions \(x \in AC(\mathbb{R}_{+}, \mathbb{K})\) for each initial point \(x(0) \in \mathbb{K}\) [1, 12, 13, 17]. Moreover, this equation has the property (see [1, 12, 13, 17] for proofs):

$$\displaystyle{x^{{\ast}}\in SOL(V I(F, \mathbb{K})) \Leftrightarrow \varPi _{ \mathbb{K}}(x^{{\ast}},-F(x^{{\ast}})) = 0,}$$

That is, a solution of the VI problem is a stationary (or equilibrium) point of the PrDE and vice versa.

TDEP

A time-dependent equilibrium problem is an equilibrium problem whose data (variables, constraints) depend on time, t, taken to mean physical time. A state variable of such a problem is typically denoted by \(x \in \mathbb{K}\), where \(\mathbb{K}\) is traditionally thought of as a subset of \(X:= L^{p}([0,T], \mathbb{R}^{q})\). As t varies over [0, T], the data of the equilibrium problem vary with t and thus a state x is taken to belong to a constraint (feasible) set \(\mathbb{K}\) given by

$$\displaystyle{ \mathbb{K} =\Big\{ x \in L^{p}([0,T], \mathbb{R}^{q})\mid \lambda (t) \leq x(t) \leq \mu (t),\,A(t)x(t) =\rho (t),\,\text{ for}\ \text{a.a. }\ t \in [0,T]\Big\}, }$$
(2)

where \(\lambda,\mu \in L^{p}([0,T], \mathbb{R}^{q})\), \(A \in L^{p}([0,T], \mathbb{R}^{l\times q})\) and \(\rho \in L^{p}([0,T], \mathbb{R}^{l})\). Such a set \(\mathbb{K}\) is closed, convex and bounded in X, provided that good conditions on \(\lambda,\mu,A\) and ρ are considered.

There is a wide array of TDEPs (in the sense defined in this section) whose constraint sets amount to a subset of \(L^{p}([0,T], \mathbb{R}^{q})\) of the form (2) (models of time-dependent traffic network problems, spatial equilibrium problems, financial equilibrium problems, as well as oligopolies and dynamic games: [4, 10, 11, 16, 21] and the references therein).

It is also known that steady states \(x^{{\ast}}\in \mathbb{K}\) of TDEP can be found by formulating the problem as an evolutionary variational inequality (EVI) (see [3, 16, 19]):

$$\displaystyle{ \text{find }\ x^{{\ast}}\in \mathbb{K}\mbox{ such that }\int _{ 0}^{T}\langle F(t,x^{{\ast}}(t)),v(t) - x^{{\ast}}(t)\rangle \geq 0,\,\,\forall v \in \mathbb{K}, }$$
(3)

where \(F: [0,T] \times \mathbb{K} \rightarrow \left (L^{p}([0,T], \mathbb{R}^{q})\right )^{{\ast}}\) is taken to be Lipschitz continuous with respect to the state variable belonging to \(\mathbb{K}\); or equivalently as the variational problem:

$$\displaystyle\begin{array}{rcl} \text{ for}\ \text{a.a.}\ t\,\in \,[0,T],\text{ find }\ x^{{\ast}}(t)\,\in \,\mathbb{K}(t)\mbox{ such}\text{that }& & \langle F(t,x^{{\ast}}(t)),v(t) - x^{{\ast}}(t)\rangle \,\geq \,0, \\ & & \quad \forall v(t) \in \mathbb{K}(t). {}\end{array}$$
(4)

The questions of existence, uniqueness and regularity of solutions to problems (3) and (4) are studied in detail in several works (see, for instance, [3, 4, 16, 19] and the references therein).

As in the case of a generic VI problem (see Definition 1 of section “Preliminaries”), we can associate a projected differential equation with an EVI problem (3) for p = 2:

$$\displaystyle{ \frac{dx(\cdot,\tau )} {d\tau } = P_{T_{\mathbb{K}}(x(\cdot,\tau ))}(-F(x(\cdot,\tau ))),\,\,x(\cdot,0) \in \mathbb{K} \subset L^{2}([0,T], \mathbb{R}^{q}), }$$
(5)

where a solution of this equation is given by absolutely continuous functions \([0,\infty ) \ni \tau \mapsto x(\cdot,\tau ) \in \mathbb{K}\) (see []) with \(\mathbb{K}\) of the form (2).

In [14] the association between a PrDE and an EVI as above is called double layered dynamics (DLD). Results on existence, uniqueness and stability of solutions to DLD (5) may be found in [8, 9, 14].

Evolution Solutions of TDEP

In this section we present a new framework for modeling evolution solutions of TDEPs. Unless otherwise mentioned, we consider a TDEP modeled on a constraint set as in (2) (with a possible modification as in Corollary 1 below).

In general, in the class of TDEP, much use is being made of existence results that ensure uniqueness of equilibrium states at almost all time moments t ∈ [0, T]. It is easy to see why, since most TDEP require a computational approach for finding approximates of their equilibrium states. In order to ensure that point-wise computed equilibria [typically using a formulation based on (4)] are meaningful to interpolate, uniqueness of point-wise states is required (see, for instance, [3, 14, 16, 27], etc.). Consequently, the current literature is concerned with imposing monotonicity type or pseudo-monotonicity conditions (strict or strong) specifically to ensure that a TDEP has a unique curve x ∗ of equilibrium states.

Given that we are not computing equilibrium states of TDEP we have no need for such restrictions, and in fact we highlight (as we did in previous works in related contexts [7, 24]) that dropping monotonicity-type conditions makes the dynamics of a problem much richer, but not complex enough to be intractable. Using the computational method which we present below in section “Computing Evolution Trajectories” completely removes the need to impose uniqueness of point-wise steady states and opens up the possibilities of finding perhaps several curves of steady states (i.e., non-unique points in the solution set of an EVI problem), periodic behaviour (evolution trapped in a periodic cycle, which has no counterpart in any VI or EVI model), or simply finding an estimate of the evolution of a particular initial state of TDEP into a later one. This is a completely novel approach as are the examples that we present to illustrate the method.

Evolution Solutions of TDEP

Definition 4.

An evolution solution of a TDEP is \(x(\cdot,\cdot ) \in AC([0,\infty ), \mathbb{K})\) such that \(\frac{dx(\cdot,\tau )} {d\tau } = P_{T_{\mathbb{K}}(x(\cdot,\tau ))}(-F(x(\cdot,\tau )))\neq 0\) for at least some time interval [0, τ], τ > 0.

We remark that given an evolution solution x as in Definition 4, for each arbitrarily fixed \(\tau \in [0,\infty ]\), the point \(x(\cdot,\tau ) \in \mathbb{K}\). Thus, for each such τ, the mapping t ↦ x(t, τ) describes the evolution of states for t ∈ [0, T] at τ. We note here that Eq. (5) can be solved, as long as an initial distribution of flows x(⋅ , 0) is given.

However, in applications, identifying an initial distribution of states of the problem over the interval [0, T] cannot be realistically expected. Thus we show next that the amount of initial information regarding states of a modelled equilibrium problem can be significantly small, without imposing an obstacle to simulating and testing its evolution from these states into further ones.

Proposition 1.

Assuming the following properties on the functions \(\lambda,\mu,\,A,\,\rho\) [introduced in ( 2 )] are satisfied:

  1. 1.

    \(\lambda\) is convex and μ is concave in t;

  2. 2.

    A is a constant coefficient matrix, ρ is linear in t,

then there exists an initial distribution of states \(x(t,0) \in \mathbb{K}\) extrapolated from a finite number of discrete observation points {x(0,0),x(t 1 ,0),…,x(t k = T,0)} over the interval of interest [0,T] given by

$$\displaystyle{x(t,0):= \left \{\begin{array}{c} \frac{t_{1}-t} {t_{1}} x(0,0) + (1 -\frac{t_{1}-t} {t_{1}} )x(t_{1},0),\,\,t \in [0,t_{1}] \\ \frac{t_{2}-t} {t_{2}-t_{1}} x(t_{1},0) + (1 - \frac{t_{2}-t} {t_{2}-t_{1}} )x(t_{2},0),\,\,\,t \in (t_{1},t_{2}]\\ \ldots \ldots.. \\ \frac{T-t} {T-t_{k-1}} x(t_{k-1},0) + (1 - \frac{T-t} {T-t_{k-1}} )x(T,0),\,\,\,t \in (t_{k-1},T] \end{array} \right.}$$

with the property that the mapping \([0,T] \ni t\stackrel{x(\cdot,0)}{\mapsto }x(t,0)\) belongs to \(\mathbb{K}\).

Proof.

It is a quick check to see that by denoting \(\gamma _{i}:= \frac{t_{i}-t} {t_{i+1}-t_{i}} \in [0,1]\), for any \(t \in (t_{i},t_{i+1}]\), the function x(t, 0) is a convex combination of the end values x(t i , 0), x(t i+1, 0).

Let us now fix t ∈ [0, T] arbitrarily. Without loss of generality, we can consider \(t \in (t_{i},t_{i+1}]\) for some i ∈ { 0, …, k}. We can now check that

$$\displaystyle{x(t,0) \in \mathbb{K}(t):=\{ w \in \mathbb{R}^{q}\mid \lambda (t) \leq w \leq \mu (t),A(t)w =\rho (t)\},}$$

using the following facts: \(x(t_{i},0) \in \mathbb{K}(t_{i})\), \(x(t_{i+1},0) \in \mathbb{K}(t_{i+1})\) and \(\lambda,\mu,A,\rho\) are as in the hypothesis.

We thus have

$$\displaystyle{\lambda (t_{i}) \leq x(t_{i},0) \leq \mu (t_{i}),\,\,A(t_{i})x(t_{i},0) =\rho (t_{i})\ \text{ and }}$$
$$\displaystyle{\lambda (t_{i+1}) \leq x(t_{i+1},0) \leq \mu (t_{i+1}),\,\,A(t_{i+1})x(t_{i+1},0) =\rho (t_{i+1})}$$

Since \(\lambda,\mu\) are, respectively, convex and concave in t, then

$$\displaystyle{\lambda (\gamma _{i}x(t_{i},0) + (1 -\gamma _{i})x(t_{i+1},0)) \leq x(t,0) \leq \mu (\gamma _{i}x(t_{i},0) + (1 -\gamma _{i})x(t_{i+1},0)),}$$

which gives, given the expression of γ i above, the following:

$$\displaystyle{\lambda (t) \leq x(t,0) \leq \mu (t).}$$

Similarly, assuming A(t) = constant for any t, then \(A(t_{i}) = A(t_{i+1}) =: A\) and so

$$\displaystyle{\gamma _{i}Ax(t_{i},0) + (1 -\gamma _{i})Ax(t_{i+1},0) =\gamma _{i}\rho (t_{i}) + (1 -\gamma _{i})\rho (t_{i+1})\Rightarrow Ax(t,0) =\rho (t),}$$

by virtue of required linearity of ρ.

Corollary 1.

 

  1. 1)

    Assuming the hypothesis of Proposition  1 , but considering problems defined on a set \(\mathbb{K}\) where equality constraints are replaced with inequality constraints (i.e., A(t)x(t) ≤ρ(t)) then the conclusion of Proposition  1 holds for functions ρ which are concave on [0,T].

  2. 2)

    We can relax the linearity requirement of ρ in case of equality constraint by requiring a piecewise linear function, possibly with discontinuities at finite number of points.

Lats but not least, it seems that requiring some form of linearity on the right-hand side of constraint of \(\mathbb{K}\) might be a big restriction on the problem. However, in practice we might not have a priori knowledge of the shape or properties of this function, so, when it comes to estimating an initial condition x(t, 0) from a number of discrete points, we may benefit from using the information on discrete values of ρ(t) at the observation times. Then we can also estimate a shape of ρ(t) consistent with the values of x(t, 0). We illustrate this point in Examples 1, 3 in section “Examples and Discussion.”

Computing Evolution Trajectories

We present next our computational approach for tracking the evolution of a TDEP, starting from an initial curve x(t, 0), given, for instance, by a procedure highlighted in Proposition 1.

Assumptions.

 

  1. 1)

    We consider the problem (5) where F is Lipschitz in x with constant b, for all t ∈ [0, T].

  2. 2)

    Assume there exists t ↦ x(t, 0) a function in \(\mathbb{K}\), which is considered the initial condition of the problem (5).

  3. 3)

    Let \(\varDelta:\{ 0 \leq t_{1} \leq t_{2} \leq \ldots \leq T\}\) a division of [0, T].

    Step 1: :

    Evaluate x(t, 0) at points t k  ∈ Δ; Set the evolution time step for the projected equation to be \(\tau \leq \frac{l} {m}\), where \(l:= \frac{L} {\vert \vert F(x_{0}(\cdot,0))\vert \vert _{L^{2}}+bL}\), for a given L > 0, the radius of a ball \(B(x(\cdot,0),L) \in L^{2}([0,T], \mathbb{R}^{q})\), and a given m to represent the number of steps covering the interval [0, l].

    Step 2: :

    For each t k  ∈ Δ, generate at every time step δ: = nτ, 1 < n ≤ m, \(n \in \mathbb{Z}_{+}\) a new set of points (of a new curve):

    $$\displaystyle{x(t_{k},\delta ):= P_{\mathbb{K}(t_{k})}(x(t_{k},\delta -\tau ) -\tau F(x(t_{k},\delta -\tau )).}$$
    Step 3(optional): :

    Check if two consecutive sets of x values are close enough for a given tolerance TOL, i.e., check

    $$\displaystyle{ \vert \vert x(\cdot,\delta ) - x(\cdot,\delta -\tau )\vert \vert _{\infty }:=\max _{k}\{\vert x(t_{k},\delta ) - x(t_{k},\delta -\tau )\vert \}\leq TOL }$$
    (6)
    Step 4: :

    If inequality (6) holds true, then STOP. Otherwise, go back to Step 2.

Remark 1.

 

  1. 1.

    The step size τ is estimated according to the constructive proof from [12], adapted to the present context;

  2. 2.

    The computation of the projection of points in Step 2 can be implemented in multiple ways, as is the minimization of distance between the points \(x(t_{k},\delta -\tau ) -\tau F(x(t_{k},\delta -\tau )\) and the set \(\mathbb{K}(t_{k})\); the modeler has a wide choice for computing these points.

  3. 3.

    Generally, Step 3 is not necessary if all is needed is to track evolution for a finite number of steps τ.

    But Step 3 may be of interest in some cases, since it detects potential equilibrium states arising from evolution from an initial condition in finite τ time (see conditions and examples of finite time evolution in [8, 9, 14]).

    In this paper, we use it to check the viability of the proposed computational method: we check if the method above is able to find equilibria of TDEP, in known examples, where these equilibria are point-wise unique, global, finite-time attractors (in τ), thus they should be detected from any initial conditions of (5). When Step 3 is implemented we set our \(TOL = 10^{-5}\).

Examples and Discussion

Example 1.

We first solve a test TDEP problem, with known dynamic behaviour, to show that the proposed method finds the known equilibrium solutions of this TDEP. Since the TDEP problem satisfies very strong conditions, the dynamic behaviour of its states is relatively simple, namely, we expect all initial states \(x(t,0) \in \mathbb{K}\) to evolve, over a finite amount of time steps τ, to the unique equilibrium curve \(x^{{\ast}}\in \mathbb{K}\).

This example is presented in detail in [14]. Consider a transportation network with one OD pair, with two links; the flow on links is, respectively, x 1(t), x 2(t), t ∈ [120] so that

$$\displaystyle{\mathbb{K} =\{ x \in L^{2}([0,120]), \mathbb{R}^{2})\mid (0,0) \leq x(t) \leq (100,100),\,x_{ 1}(t) + x_{2}(t) =\rho (t)\ \text{ a.e.}\}}$$

and the cost on the links is \(F = (2x_{1}(t) + x_{2}(t) + 1,x_{1}(t) + x_{2}(t) + 2)\). It is shown that F is strongly monotone with degree α = 1 and as such the EVI model (4) of this network admits a unique, globally, finite-time attracting curve of equilibria given by \(x^{{\ast}}(t) = (1,\rho (t) - 1)\), with ρ a measurable function.

With this in mind, we apply our method above noticing that \(\lambda (t) = (0,0)\), μ(t) = (100, 100). We assume the following observation points:

$$\displaystyle{(x_{1}(t),x_{2}(t)) = \left \{\begin{array}{c} (50,20),\,t = 0 \\ (60,30),\,t = 20 \\ (35,40),\,t = 50 \\ (30,20),\,t = 70\\ \end{array} \right.}$$

We assume now that the initial condition for problem (5) in this case is the piecewise continuous function:

$$\displaystyle{(x_{1}(t),x_{2}(t)) = \left \{\begin{array}{c} (50,20),\,t \in [0,20] \\ (60,30),\,t \in (20,50] \\ (35,40),\,t \in (50,70] \\ (30,20),\,t \in (70,120]\\ \end{array} \right.}$$

Our Proposition 1 requires a linear function ρ(t), or at least a piecewise one. We thus simply employ \(\rho (t,0) = x_{1}(t,0) + x_{2}(t,0)\) to get values of {70, 90, 75, 50} on the respective time subintervals. Now we note that − F is Lipschitz with constant \(5 + \sqrt{3}\), and that \(\vert \vert - F(x(t,0))\vert \vert _{L^{2}} \approx 2882\), thus taking L = 200 we obtain l ≈ 0. 047. Taking a number m = 10 of τ steps to cover [0, l], we get τ ≈ 0. 0047. Finally, we sampled the time interval [0, 120] with 13 points.

From the previous dynamic analysis of this problem in [14] we know that the equilibrium curve will be reached in a finite number n of steps τ. Our simulations below give n ≈ 200 steps for the initial curves to reach the known equilibrium ones (Fig. 1):

Fig. 1
figure 1

We show here the evolution of the flows on this network, from initial piecewise values (blue curve) to the end equilibrium curve (yellow). Left panel represents x 1(t, τ) and right panel represents x 2(t, τ) over 200 τ steps. We see that \(x_{1}^{{\ast}}(t) = 1\) constant, as predicted (left) where as \(x_{2}^{{\ast}}(t) =\rho (t) - 1\)

Full size image

Example 2.

A related example to this one was first introduced in [24]. Here we adapt it to our context. Let us assume that a TDEP is given in a form of an EVI (4) where \(F(t,x(t)):= (-x_{1}(t) + ax_{2}(t),-ax_{1}(t) - x_{2}(t))\), where a ∈ [0, 1] and

$$\displaystyle{\mathbb{K}:=\{ u \in L^{2}([0,10], \mathbb{R}^{2})\mid - 1 \leq x_{ i}(t) \leq 1,\text{ a.a.}\ t \in [0,10],i =\{ 1,2\}\}.}$$

Here \(\lambda,\mu\) are constant functions. The matrix A(t) is the 0-matrix, so we do not have any equality constraints.

As stated above, we are interested in TDEP problems that may give rise to EVI problems whose F does not satisfy any monotonicity-type conditions. We can check right away that F above is not monotone, for any value of a (we get that \(\langle F(x_{1},x_{2}) - F(u,v),(x_{1} - u,x_{2} - v)\rangle\) = \(-(x_{1} - u)^{2} - (x_{2} - v)^{2}\)) and so all previous analyses based on variational inequalities theory are not of use here.

Let us now look at this TDEP as modelled by the projected equation (5). We have that \(-F(x_{1}(t),x_{2}(t)):= (x_{1}(t) - ax_{2}(t),ax_{1}(t) + x_{2}(t))\) is linear in x, thus it is Lipschitz continuous; for instance, \(b:= \sqrt{1 + a^{2}}> 0\) is an L-constant for F. Assume now that we have a few observation data points for the states x 1, x 2 at t ∈ { 0, 2, 4, 5, 7} as

$$\displaystyle{(x_{1}(t),x_{2}(t)) = \left \{\begin{array}{c} (0.5,0.5),\,t = 0 \\ (0.8,0),\,t = 2 \\ (0.9,-0.2),\,t = 4 \\ (0.4,0.3),\,t = 5 \\ (-0.1,0.3),\,t = 7 \end{array} \right.}$$

These points indicate that we can consider as initial value for Eq. (5) the curve x(t, 0) given by

$$\displaystyle{(x_{1}(t,0),x_{2}(t,0)) = \left \{\begin{array}{c} (0.5 + 0.15t,0.5 - 0.25t),\,t \in [0,2] \\ (0.7 + 0.05t,0.2 - 0.1t),\,t \in (2,4] \\ (2.9 - 0.5t,-2.2 + 0.5t),\,t \in (4,5] \\ (1.65 - 0.25t,1.8 - 0.3t),\,t \in (5,7] \\ (-0.1,0.3),\,t \in (7,10] \end{array} \right.}$$

This gives \(\vert \vert - F(x(t,0))\vert \vert _{L^{2}} \approx 5.43\) for a = 1 and 8. 589 for a = 2.

We choose L = 1 and thus \(l = \frac{L} {\vert \vert -F(x(t,0))\vert \vert _{L^{2}}+bL} = \frac{1} {4.75+\sqrt{1+a^{2}}}\). For values of a = 1, respectively a = 2 we get

$$\displaystyle{l = 0.1461,\,\text{ respectively }\ l = 0.1304\Rightarrow}$$

for a given m = 10 we have

$$\displaystyle{\tau = 0.0146,\text{ respectively }\ \tau = 0.013.}$$

We sampled the time interval [0, 10] with 21 points.

In Figs. 2 and 3 we present our simulations for a = 1, respectively, a = 2. Comparing the two rows of panels in Fig. 2, we see vastly different behaviour being displayed by the two curves x 1(t, 0) and x 2(t, 0) as τ increases. All four simulations have been run for 100 τ steps. Since we are unclear as to what type of dynamic behaviour we might expect, and exploiting the fact that this problem is 2-dimensional, we plotted in Fig. 3 the phase portraits of the evolutions, i.e. we eliminated t and plotted x 1(⋅ , τ) vs. x 2(⋅ , τ).

Fig. 2
figure 2

The upper two panels display the evolution of the initial curves for a = 1; the lower panels display the evolution for a = 2

Full size image
Fig. 3
figure 3

Here we follow the evolution of curves in phase portrait depiction. Left panel has a = 1, right panel has a = 2

Full size image

We note a much clearer picture emerging: when a = 1, the initial phase portrait at τ = 0 represents a spiral curve ending at (−1, 1) (Fig. 3, left panel, blue curve, filled in dots); it evolves into a different spiral curve ending at \((-1,-1)\) (Fig. 3, left panel, brown curve, marked with *).

However, for a = 2, we seem to evolve the initial curve into a periodic curve inside and around the boundary of [−1, 1] (Fig. 3, right panel). This indicates that there will be periodic behaviour arising in the TDEP, specifically, that there exists τ 1 > τ 2 > 0 so that a curve x(⋅ , τ 2) = x(⋅ , τ 1). So states in the TDEP may reoccur.

Example 3.

Let us now assume that we observe at discrete moments a traffic network over a time interval [0, 90 min]. We consider that the user traffic equilibrium states are generically described as in [16], between 1 origin (o1) and 3 destinations (d 1, d 2, d 3). We assume the flows are functions of time x 1(t), x 2(t), x 3(t), t ∈ [0, 90 min] (corresponding to pairs (o1, d 1, o1, d 2, respectively, o1, d 3). It is known that there exist demand functions ρ(t) and ψ(t) on certain combination of routes, such as \(x_{1}(t) + x_{2}(t) + x_{3}(t) =\rho (t)\) and \(x_{1}(t) + 1/2x_{2}(t) =\psi (t)\). Finally, we reasonably assume that there is a lower and upper bound for flows on each route, thus 0 ≤ x i (t) ≤ M for each i ∈ { 1, 2, 3}.

We assume known that the cost of traveling on the three routes is given by the function \(F: \mathbb{K} \rightarrow L^{2}([0,90], \mathbb{R}^{3})\), given by

$$\displaystyle{ F(x) = (3x_{1} - x_{2} + x_{3},\, \frac{3} {2}x_{1} - 4x_{2} + x_{3},\,2x_{1} - 7x_{2} + x_{3}). }$$

In general, such a traffic problem is modeled by an EVI problem (4) formulated on the constraint set:

$$\displaystyle\begin{array}{rcl} \mathbb{K}\,=\,\{x \in L^{2}([0,90], \mathbb{R}^{3})\,\mid \,0\,\leq \,x(t)\,\leq \,M,\,x_{ 1}(t)\,+\,x_{2}(t) + x_{3}(t)\,=\,\rho (t),\,x_{1}(t)\,+\,\frac{1} {2}x_{2}(t)\,=\,\psi (t)\},& & {}\\ \end{array}$$

and depending on monotonicity properties of F above it would be studied from the perspective of its user equilibrium states only, given certain demand functions ρ, ψ. A simple computation (see Appendix) shows that F is monotone on \(\mathbb{K}\) for any t, but it is not strictly monotone. Clearly from the Appendix, there are many points in each set \(\mathbb{K}(t)\) where F is not strictly monotone. It is at these points that we cannot employ the theoretical results from EVI theory, instead we rely on the double layer dynamics and evolution from initial states to study what happens to the traffic flows. We see that this example falls under the hypotheses of Proposition 1.

Moreover, given a set of discrete observation data points we extrapolate not only an initial curve of states for the traffic problem, but also demand functions ρ, ψ consistent with our observations. Unlike in the case of Example 1 above, we make here ρ, ψ linear and continuous.

We assume that we observe the traffic at 15-min intervals over a 90-min length of time, as follows:

$$\displaystyle{(x_{1}(t),x_{2}(t),x_{3}(t)) = \left \{\begin{array}{c} (10,20,25),\,t = 0 \\ (15,20,20),\,t = 15 \\ (20,25,25),\,t = 30 \\ (30,10,30),\,t = 45 \\ (30,20,30),\,t = 60 \\ (10,20,15),\,t = 75 \\ (10,10,10),\,t = 90 \end{array} \right.}$$

Given the structure of the demands on certain route combinations, we then deduce

\(\rho (t) = x_{1}(t) + x_{2}(t) + x_{3}(t))\)

\(\psi (t) = x_{1}(t) + \frac{1} {2}x_{2}(t)\)

55, t=0

20, t=0

55, t=0

25, t=15

75, t=30

32.5 t=30

70, t=45

70, t=45

80, t=60

40, t=60

45, t=75

20, t=75

30, t=90

15, t=90

Then the initial curve of states for this transportation problem, as well as estimates for the demand functions consistent with observations, is as given by Proposition 1:

(x 1(t, 0), x 2(t, 0), x 3(t, 0))

ρ(t)

ψ(t)

Time

(10+1/3t, 20,25−t/3)

55

20+t/3

t ∈ [0, 15]

(10+t/3,15+t/3,15+t/3)

40+t

17.5+0.5t

t ∈ (15, 30]

(2t/3,55−t, 15+t/3)

70

0.16t+27.5

t ∈ (30, 45]

(30, −20+2t/3, 30)

40+2t/3

20+0.334t

t ∈ (45, 60]

(110−4t/3, 20,90−t)

220−7t/3

120−4t/3

t ∈ (60, 75]

(10, 70−2t/3,40−t/3)

120−t

45−0.334t

t ∈ (75, 90]

For this initial curve, we compute \(\|-F(x(t,0))\|_{L^{2}} \approx 2476\) and b = 2. For L = 1000 we thus get \(l = \frac{L} {\|-F(x(t,0))\|_{L^{2}}+bL} \approx 0.22\); we thus choose \(m = 10\Rightarrow\tau:= 0.022\). Here we sampled the time interval [0, 90] with 46 points. Our simulations are presented in Fig. 4 above. We see that in 100 τ steps we evolve the initial curves to later ones, depicted with a dagger sign in all panels of Fig. 4.

Fig. 4
figure 4

We depict here the evolution of the initial states after 100 τ steps. Given that the demand functions are piecewise continuous, and given results in [3] we expect to see a piecewise continuous evolution

Full size image

To see how different initial observed states behave under this dynamics, let us consider that ρ, ψ are as in the above table, and assume that we observe a constant density flow x 1(t, 0) = 10, for any t. Then respecting the flow demands, we have \(x_{2}(t,0) = 2(\psi (t) - 10)\) and \(x_{3}(t,0) =\rho -(10 + x_{2}(t,0))\). This initial condition gives the following evolution over 100 τ steps, shown in Fig. 5 above.

Fig. 5
figure 5

We depict here the evolution of the initial states after 100 τ steps. The dark brown curves are the states of the problem the at end of simulated time. They are distinct than the ones obtained in Fig. 4, over the same length of simulated time

Full size image

We note that the flows have evolved in a distinct manner than for the previous initial condition of above table. This was expected, since we are not in possession of a global strict monotonicity condition for F over \(\mathbb{K}\).

Conclusions and Future Work

We addressed here an open problem in the projected dynamics and EVI areas, namely that of giving a method to track evolution solutions of TDEP problems. This is by no means a complete answer to the question of how such evolution should be studied, however our main point here is that it should be studied. Our proposed method was mainly guided by reasonable assumptions on how much data one may be in possession of, when one studies a TDEP, and how one might use this information to get a picture of the changes in the states of a TDEP. The method is specifically concerned with cases of TDEP for which well-known VI theory fails to give a clear picture of the potential dynamics.

We included here examples (Examples 1 and 3) drawn from traffic network equilibrium problems, however, the method need not be restricted to this TDEP class. In Example 2, one can easily reinterpret the data as coming from a continuous time dynamic game, with \(F:= (-\nabla _{x_{1}}U_{1},\nabla _{x_{2}}U_{2})\) being a gradient of a quadratic payoff, such as \(U_{1}:= x_{1}^{2} - ax_{1}x_{2} + t\), and \(U_{2}:= ax_{1}x_{2} - x_{2}^{2}/2 + t^{2}\), where each player wishes to maximize its U.

We hope that the reader will find it useful to apply and/or extend this method to specific classes of TDEP which fall under a generic formulation as variational inequality problems. One such application is currently concerning the evolution solutions of a dynamic casual encounters game. These are a sequence of repeated games between two potential sexual partners where one is HIV + and the other is HIV −. It is sought to quantify the potential increase in infection in a homosexual population using a double layer dynamics model.