category: literaturenote citekey: grafstochasticpredictionequilibriumdynamic2024 title: Stochastic Prediction Equilibrium for Dynamic Traffic Assignment authors: "Graf, Lukas; Harks, Tobias; Markl, Michael" year: 2024 date: 2024-00-00 2024 url: "https://arxiv.org/abs/2409.12650v1" zotero_key: GR39H3WB zotero_storage: WV6KHBFZ collections: transpordi_planeerimine folder: 001_artiklid firstAuthor: "Graf, Lukas"

status: converted

Stochastic Prediction Equilibrium for Dynamic Traffic Assignment

Lukas Graf, Tobias Harks, and Michael Markl

University of Passau

{lukas.graf, tobias.harks, michael.markl}@uni-passau.de

Stochastic effects significantly influence the dynamics of traffic flows. Many dynamic traffic assignment (DTA) models attempt to capture these effects by prescribing a specific ratio that determines how flow splits across different routes based on the routes' costs.

In this paper, we propose a new framework for DTA that incorporates the interplay between the routing decisions of each single traffic participant, the stochastic nature of predicting the future state of the network, and the physical flow dynamics. Our framework consists of an edge loading operator modeling the physical flow propagation and a routing operator modeling the routing behavior of traffic participants. The routing operator is assumed to be set-valued and capable to model complex (deterministic) equilibrium conditions as well as stochastic equilibrium conditions assuming that measurements for predicting traffic are noisy. As our main results, we derive several quite general equilibrium existence and uniqueness results which not only subsume known results from the literature but also lead to new results. Specifically, for the new stochastic prediction equilibrium, we show existence and uniqueness under natural assumptions on the probability distribution over the predictions.

| 1. | Introduction
1.1.
Our Contribution
1.2.
Related Work | 3
3
4 | | |----|----------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------|--| | 2. | Model
2.1.
Physical Flow Model
2.2.
Behavioural model
| 5
5
6 | | | 3. | Existence and Uniqueness
3.1.
Existence

3.2.
Uniqueness
| 7
7
11 | | | 4. | Stochastic Prediction Equilibrium
4.1.
Deterministic Prediction Equilibrium
4.2.
Prescriptive Routing Operators
4.3.
Noisy Predictions | 13
14
17
18 | | | 5. | Conclusion | 25 | | | | References | | | | | A. Some Technical Results from Topology | 29 | | | | B. Vickrey Queuing and Affine-Linear Volume-Delay Dynamics
B.1. Vickrey's Queuing Model

B.2. Affine-Linear Volume-Delay Dynamics
| | | | | C. Comments on [BKPS19, Lemma 3.3] | | | | | D. List of Symbols | 34 | |

1. Introduction

Understanding traffic flows is an important task that possibly impacts billions of commuters, with key challenges including managing congestion and carbon emissions. Congestion phenomena and resulting increased emissions are heavily impacted by the routing decisions of individual drivers, which are influenced by (ML-based) predictions for the delays of road segments (see, for instance, Jiang and Luo [JL21] for an overview of convolutional and graph neural network based approaches). A key aspect in modelling traffic flows is the underlying complex and self-referential system: the routing decisions depend on and, at the same time, influence the forecasting models, because they directly change the underlying signature of traffic flows.

In this paper, we address this interplay focusing on the popular dynamic traffic assignment (DTA) framework, on which there has been substantial work over the past decades (see the book of Ford and Fulkerson [FF62], or the more recent surveys by Friesz and Han [FH19] and Skutella [Sku08]).

Such DTA models typically consist of two main parts: A physical model describing how the traffic flow propagates through the network and, in particular, creates and is affected by congestion, and a behavioural model capturing how individual drivers choose their routes though the network. The latter can be either prescriptive or descriptive: A prescriptive behavioural model consists of rules declaring explicitly how, under any given state of the network, the flow splits over the available routes. These rules then have to be chosen such that they replicate the actual observed traffic flow. As an example, Bayen et al. [BKPS19] considered adaptive node routing protocols based on realtime traffic predictions. A descriptive behavioural model, on the other hand, describes the possible equilibrium states resulting from the assumed behaviour – typically as some variant of Wardrop's first principle [War52, p. 345], which states that in an equilibrium all used routes have the same and minimal perceived cost. Here, "perceived costs" can be the current travel times, the actual (future) travel times or some other predictions about those future travel times.

These equilibrium models typically assume that all predictions are deterministic. However, especially for models with limited information, this assumption seems to be unrealistic as, in reality, both measurements of the current state of the network and predictions about the future evolution will come with some random noise. Because of this noise, the perceived cost will vary among agents so that a shortest route may be different from one agent to another.

1.1. Our Contribution

We present a new DTA framework that integrates both prescriptive and descriptive routing models. The main ingredients of our model are two operators: an edge loading operator and a routing operator. The former determines the resulting edge outflows under given edge inflows and serves as a proxy for the underlying physical model and subsumes several well-known physical models. The latter operator determines the precise outflow splits for a node given the node inflows. The routing operator is assumed to be set-valued and, thus, can model prescriptive routing behaviour (via single-valued routing operators), complex equilibrium conditions (via possibly multi-valued operators) and also stochastic models where measurements for predicting traffic are noisy. Within this framework, we postulate the notion of coherent flows, which are dynamic flows that comply with both the given edge-loading and routing operator. As our main results we show the following:

1. We prove existence of coherent flows under natural continuity conditions (see Theorems 3.1 and 3.5). This generalizes various existence results from the literature, e.g., the results of Bayen et al. [BKPS19] for prescriptive routing operators, the result of Graf et al. [GHKM23] for prediction based equilibria and the general existence result for full information equilibria by Cominetti, Correa and Larré [CCL15]. Our results strictly generalize these existing results since we allow a larger class of physical flow models.
2. For prescriptive operators, we show that coherent flows are unique, if the operators fulfil a Lipschitz condition on arbitrarily small extension intervals (see Theorem 3.14). This result uses an idea proposed by Bayen et al. [BKPS19]. We generalize their result to a larger class of physical models and routing operators that are not volume-based.

Finally, we introduce a new equilibrium concept called stochastic prediction equilibrium that generalizes the dynamic prediction equilibrium to allow for random measurement errors in the predictions (see Definition 4.12). We show that the corresponding routing operator is prescriptive and that a unique such equilibrium exists, if the random distribution is well-behaved (see Theorem 4.21).

The rest of this paper is organized as follows: In Section 2 we formally introduce our abstract framework and define our central object of study: Coherent flows. Next, in Section 3, we provide several results on the existence and uniqueness of coherent flows. Finally, in Section 4 we demonstrate how these results apply to dynamic prediction equilibria, prescriptive routing operators and the new concept of stochastic prediction equilibria.

1.2. Related Work

Substantial effort has been made to use AI-based methods for traffic predictions. Due to the high number of relevant papers, we can only highlight a few and refer the reader to [Sha+22] and [JL21] for an overview on AI-based methods and their challenges in traffic prediction, and on the use of graph neural networks, respectively. Yu, Yin and Zhu [YYZ18] model the temporal dependency as so-called spatio-temporal graph convolutional networks. Also, graph attention networks, introduced by Velickovic et al. [Vel+18], have been used for traffic predictions by Zheng et al. [ZFWQ20]. Graf et al. [GHKM23] discuss the integration of such traffic predictions into dynamic traffic assignment models.

Similarly, there is a vast amount of literature on integrating stochastic effects of predicting travel times into traffic assignment models.

Static Models. Daganzo and Sheffi [DS77] introduced the concept of a (static) stochastic user equilibrium (SUE). A SUE is defined as a static path-based flow wherein each (infinitesimal) traveller chooses a path that minimizes their perceived travel time. While the actual travel time cannot be observed by the individual travellers, the perceived travel time is a random variable that depends on the actual travel time and that may have different outcomes for every traveller.

In [SP82], an equivalent minimization problem was formulated which allowed the authors to prove that a unique SUE exists under natural assumptions on the probability distributions and the travel time-flow relationship, and to propose an algorithm computing SUE.

Baillon and Cominetti [BC06] formulated a concept called Markovian traffic equilibrium (MTE) that generalizes SUE and the deterministic user equilibrium concept in a common framework. They proposed an edge-based formulation, where travellers update their route choice at every intermediate node of their journey where, at each node, a new outcome of the believed random travel time is revealed.

Cantarella and Watling [CW16] presented an asymptotic analysis of a day-to-day learning dynamic for static stochastic and deterministic user equilibria.

Dynamic Models. Dynamic equilibrium flows have been studied extensively in the transportation science community, see Han, Friesz and Yao [HFY13] and Friesz and Han [FH19] for a survey. Starting with the work of Koch and Skutella [KS11], the mathematics and computer science community focused (mostly) on the Vickrey queueing model and investigated several research questions for different behavioral models covering equilibrium existence (cf. Cominetti, Correa and Larré [CCL15], Graf, Harks and Sering [GHS20] and Graf and Harks [GH24]), the computational complexity of equilibrium computation (cf. Kaiser [Kai22] and Graf and Harks [GH23a]) and the price of anarchy (cf. Correa, Cristi and Oosterwijk [CCO22] and Graf and Harks [GH23b]).

Han [Han03] introduced a variant of the SUE that incorporates time-dependent flows and travel times to model within-day dynamics. They use as underlying physical model the Vickrey model together with a logit-based route assignment model, and present a solution method to compute these equilibria. Paz Guala et al. [PCHR24] formulated an arc-based dynamic stochastic user equilibrium inspired by [BC06] with a logit-based adaptive route-choice model, and compared this approach with the one in [Han03].

Logit-based models, however, exhibit unnatural behaviour as they assume independence of travel times of overlapping paths which was first pointed out by Schneider [Sch73] and also discussed in Baillon and Cominetti [BC06]. In order to mitigate this effect, Szeto, Jiang and Sumalee [SJS11] considered a C-logit model instead, which uses a commonality-factor for overlapping paths. They proposed an algorithm to compute such equilibria in a cell transmission model. The motivation for these models is usually to describe the behaviour of agents having stochastic errors in their predictions of travel times. The models above are all prescriptive in nature as they explicitly prescribe how the flow has to split over the available routes.

2. Model

Let G = (V, E) be a directed graph and I a (finite) set of commodities. Each commodity i ∈ I comes with a sink node tⁱ ∈ V and a network inflow rate uv,i ∈ R for every node v ∈ V . Here, R denotes the set of rate functions defined as the subset of non-negative, locally p-integrable functions in L p loc(R) that vanish for negative values. Throughout this work, we assume 1 < p < ∞.

A (dynamic) flow is a vector f ∈ R^E×I×{+,−} where f + e,i denotes the inflow rate (over time) and f − e,i the outflow rate of commodity i at edge e.

Notation 2.1. Unless specified otherwise, we use the norm ∥f∥ := maxi∈[d]∥fi∥^p on the product space L p (J) d for d ∈ N and measurable J ⊆ R with ∥fi∥^p := (R J |f| ^p dλ) ¹/p. Here, λ denotes the Lebesgue measure. We say that two vectors of locally integrable functions coincide until time T ∈ R^∞ ≥0 if 1[0,T) · f = 1[0,T) · g is fulfilled. Here, R^∞ ^≥⁰ denotes ^R^≥⁰ ∪ {∞} and ¹^J (θ) := 1, if ^θ ^∈ ^J, and 1^J (θ) := 0, otherwise.

For a node v ∈ V , let δ ⁺(v) and δ ⁻(v) denote the set of outgoing and incoming edges of v, respectively.

2.1. Physical Flow Model

A physical flow model is given by an edge loading operator

$$\Phi: \mathcal{R}^{E \times I} \to \mathcal{R}^{E \times I}$$

mapping vectors f ⁺ = (f + e,i) of edge inflow rates to vectors f ⁻ = (f − e,i) of edge outflow rates.

Definition 2.2. A flow f is consistent with the physical model Φ until time T ∈ R^∞ ≥0 if it satisfies f e,i(θ) = Φ(f ⁺)e,i(θ) for all e ∈ E, i ∈ I and almost all θ < T.

The above definition determines how particles flow through the edges of the network. Flowconservation at nodes prescribes that particles entering a node must leave the node again without waiting.

Definition 2.3. A flow f fulfils flow conservation until time T ∈ R^∞ ≥0 if

$$\sum{e \in \delta^+(v)} f{e,i}^+(\theta) = \mathbb{1}_{v \neq ti} \cdot f{v,i}^+(\theta)$$

holds for all i ∈ I, v ∈ V and almost all θ < T where

$$f{v,i}^+(\theta) \coloneqq u{v,i}(\theta) + \sum{e \in \delta^-(v)} f{e,i}^-(\theta)$$

denotes the inflow rate of commodity i into node v.

Important properties of a physical flow model include causality and local boundedness.

Notation 2.4. For a finite T ∈ R≥⁰ and an edge-loading operator Φ, let Φ^T denote the mapping

$$\Phi_T: \mathcal{R}_T^{E\times I} \to \mathcal{R}T^{E\times I}, \quad f^+ \mapsto \mathbb{1}{[0,T]} \cdot \Phi(f^+),$$

where R^T is the set of functions in R vanishing on R \ [0, T]. Note that R^T ⊆ L p (R).

Definition 2.5. We call an edge-loading operator Φ locally bounded if for any finite T ∈ R≥⁰ there exists some B′ ^T ∈ R≥⁰ such that ∥1[0,T] · Φ(f ⁺)∥ ≤ B′ ^T holds for all flows f.

Definition 2.6. An edge loading operator Φ is called causal if whenever two edge inflow vectors f ⁺ and g ⁺ coincide until some time T, then there exists some α ∈ R≥⁰ such that Φ(f ⁺) and Φ(g +) coincide until T + α. If α may always be chosen strictly positively, we call Φ strictly causal. If α may be chosen strictly positively and independently of g ⁺, we call Φ uniformly strictly causal.

Many well-known physical models are included in this model – in particular, the ones resulting from the following two widely used edge-dynamics: Vickrey's model [Vic69; CCL15] with non-negative freeflow travel times and positive edge capacities, and the affine-linear volume-delay dynamics (see e.g. [ZM00; BKPS19]) with positive free-flow travel times and positive volume-coefficients. Both models are causal and locally bounded, and, if all free-flow travel times are positive, even uniformly strictly causal. We refer to Appendix B for a formal introduction and discussion of these models.

2.2. Behavioural model

Based on these physical constraints, the behavioural model describes how particles are routed to their destination. Whenever particles arrive at a node v ̸= tⁱ , they have to decide which edge to enter next based on the past, current, and potentially future state of the network.

We say that a behavioural model is given by a routing operator: To reflect that particles may have multiple options of equal quality, we introduce the concept of a set-valued routing operator:

Definition 2.7. Let R be a set-valued mapping of the form

$$\mathscr{R}: \mathcal{R}^{E \times I \times {+,-}} \rightrightarrows L^p_{\mathrm{loc}}(\mathbb{R})^{E \times I}$$

that maps flows f to sets of allowed flow splits at nodes r ∈ R(f). We say R is a routing operator if all r ∈ R(f) satisfy re,i ≥ 0 and P e∈δ+(v) re,i = 1v̸=tⁱ for all nodes v ∈ V , edges e ∈ δ ⁺(v) and commodities i ∈ I.

In other words, given a flow f, an element r of R(f) describes for every time θ and node v ̸= tⁱ how the incoming flow rate into node v splits over the outgoing edges of v. In general, this flow-split will originate from the particles' decisions that may depend on the flow f and its induced (past and/or future) travel times, or might be enforced by some infrastructure operator.

Naturally, we want to study flows that are consistent with a given routing operator:

Definition 2.8. A flow f is consistent with a routing operator R until time T if there exists some r ∈ R(f) such that

$$f{e,i}^+(\theta) = r{e,i}(\theta) \cdot \sum{e' \in \delta^+(v)} f{e',i}^+(\theta)$$

holds for all i ∈ I, e = vw ∈ E and almost all θ < T.

Similar to the physical model, we first define a few key characteristics of behavioural models.

Notation 2.9. For a routing operator R and a time T ∈ R^≥0, we define

$$\mathbb{1}{[0,T]}\cdot \mathscr{R}(f) := {\,\mathbb{1}{[0,T]}\cdot r \mid r\in \mathscr{R}(f)\,}$$

for all f ∈ R^E×I×{+,−}, and we denote R^T as the mapping

$$\mathscr{R}_T: \mathcal{R}T^{E \times I \times {+,-}} \rightrightarrows L^p(\mathbb{R})^{E \times I}, \quad f \mapsto \mathbb{1}{[0,T]} \cdot \mathscr{R}(f).$$

Definition 2.10. A routing operator R is called causal if whenever two flows f and g coincide until some time T, then there exists some α ∈ R≥⁰ with 1[0,T ⁺α] · R(f) = 1[0,T ⁺α] · R(g). If α may always be chosen strictly positively, we call the operator strictly causal. If α may be chosen strictly positively and independently of g, we call it uniformly strictly causal.

Keimer and Bayen [KB20] study predefined routing policies defining the "laws of routing". Adopting this perspective means that particles arriving at some intersections are routed according to prescriptive rules. These rules are modelled as the class of prescriptive routing operators1

Definition 2.11. We call a routing operator R prescriptive if for every flow f the set R(f) consists of exactly one element. In this case, we denote this unique element by r(f).

Finally, we are interested in flows that are consistent with both a given physical and behavioural model Φ and R.

Definition 2.12. Let Φ be an edge-loading operator and R a routing operator. A flow f is called Φ-R-coherent until time T ∈ R^∞ ≥0 if f is consistent with Φ and R until time T and fulfils flow conservation until time T. If Φ and R are clear from the context, we say f is coherent until T.

3. Existence and Uniqueness

In this section we provide several sufficient properties of edge-loading and routing operators to guarantee existence and – in the second part – uniqueness of coherent flows.

3.1. Existence

We start this subsection by showing that for finite time horizons, coherent flows exist given that Φ and R fulfil a continuity condition. We then extend this result to the infinite time horizon if either the models ensure that all relevant flows terminate at some point in time or if both operators are causal. For the latter case, we show that the time horizon of a coherent flow may always be strictly extended if the operators are continuous on a (small enough) extension interval, and we conclude existence until ∞ using Zorn's Lemma.

The graph of a set-valued function Γ : M ⇒ N is defined as graph(Γ) := { (x, y) ∈ M × N | y ∈ Γ(x) }.

Theorem 3.1. Let T ∈ R^≥⁰ and let Φ be a locally bounded edge-loading operator such that Φ^T is sequentially weak-weak-continuous and let R be a routing operator such that R^T has a sequentially weakly closed graph and non-empty and convex values.

Then, there exists a flow f ∈ RE×I×{+,−} ^T which is coherent until time T.

For this central existence result, we rely on the Kakutani-Fan-Glicksberg Fixed-Point Theorem (cf. [AB06a, Corollary 17.55]).

Theorem 3.2 (Kakutani-Fan-Glicksberg Fixed-Point Theorem). Let X be a locally convex Hausdorff space, K ⊆ X non-empty, convex and compact. Moreover, let Γ : K ⇒ K be a set-valued function with closed graph and non-empty, convex images Γ(x) for x ∈ K.

Then the set of fixed points of Γ is non-empty and compact, where x ∈ K is called a fixed point of Γ if x ∈ Γ(x).

Proof of Theorem 3.1. We define the constant B^T := max^v |δ ⁻(v)| · B′ ^T + ¹[0,T] · u ⁺ ^T where ^B′ is given by the local boundedness of Φ. We then define the following set of candidates for consistent flows

$$K := \left{ (f^+, f^-, r) \in \mathcal{R}_T^{(E \times I)^3} \mid ||(f^+, f^-, r)|| \le B_T, r \le 1 \right}$$

¹Note that Bayen et al. [BKPS19] originally introduced the term "routing operator" only for what we call a prescriptive routing operator.

and the correspondence

$$\Gamma: K \rightrightarrows K, (f,r) \mapsto \left{ \begin{array}{ll} (g,r') \in K & g^- = \PhiT(f^+), \ g^+{e,i} = r{e,i} \cdot \left(u{v,i} + \sum{e \in \delta^-(v)} g^-{e,i}\right), \ r' \in \mathscr{R}_T(f) \end{array} \right}.$$

Clearly, the fixed points (f, r) of Γ are exactly the coherent flows f until time T (together with their corresponding routing mapping r). We now want to show that Γ has such a fixed point by applying Theorem 3.2. Hence, we have to show that the requirements of this theorem are satisfied:

Claim 1. K is non-empty, convex and weakly closed and compact.

Proof. K non-empty: K contains at least the zero vector.

K convex: Clear.

K weakly closed: K is strongly closed and convex and, thus, weakly closed by [Hun13, Theorem 7.10].

K weakly compact: K is a subset of the (norm-)closed ball with radius B^T in L p (R) E×I×{ +,−,r } The latter is weakly compact since L p (R) E×I×{ +,−,r } is reflexive (cf. [AB06a, Theorem 6.25]). Hence, as a weakly closed subset of a weakly compact set, K is weakly compact as well. ■

Claim 2. Γ has non-empty and convex values.

Proof. Fix any (f, r) ∈ K. Then, we have:

Γ(f, r) non-empty: Define g ⁻ := Φ^T (f ⁺) and g + e,i := re,i · uv,i + P e∈δ−(v) g e,i and choose any r ′ ∈ R^T (f) (which is possible since R^T (f) is always non-empty by assumption). We then have

$$\begin{aligned} |g{e,i}^{+}| &\leq |r{e,i}| \cdot \left( |\mathbb{1}{[0,T]} \cdot u{v,i}| + \sum{e \in \delta^{+}(v)} |g{e,i}^{-}| \right) \leq |\mathbb{1}{[0,T]} \cdot u{v,i}| + \sum{e \in \delta^{-}(v)} |\Phi{T}(f^{+})| \ &\leq |\mathbb{1}{[0,T]} \cdot u| + \left|\delta^{-}(v)\right| \cdot B{T}' \leq B_{T} \end{aligned}$$

and, therefore,

$$\left|\left(g^{-},g^{+},r'\right)\right|=\max\left{\,\left|g^{-}\right|,\left|g^{+}\right|,\left|r'\right|\,\right}\leq\max\left{\,B{T}',B{T},T\,\right}=B_{T}.$$

Hence, we get (g, r′ ) ∈ K.

Γ(f, r) convex: This follows directly from the convexity of R^T (f). ■

Claim 3. Γ has a weakly closed graph.

Proof. Since K × K is a weakly closed set by Claim 1, it suffices to show that graph(Γ) is weakly closed in K × K. By Proposition A.1, this is equivalent to showing that graph(Γ) is sequentially weakly closed. Hence, fix some sequence (f (n) , r(n) , g(n) , r′(n) )ⁿ weakly converging to (f, r, g, r′ ) in K × K.

This implies that (f (n),⁺)ⁿ is weakly converging to f ⁺ and, therefore, Φ^T (f (n),⁺) is weakly converging to Φ^T (f ⁺) by the sequential weak-weak continuity of Φ^T . As g ⁻ is the weak limit of g (n),⁻ = Φ^T (f (n),⁺), we must have g ⁻ = Φ^T (f ⁺). Similarly, r (n) e,i · (uv,i + P e∈δ+(v) g (n),− e,i ) weakly converges to re,i · (uv,i + P e∈δ+(v) g − e,i) and g ⁺ is the weak limit of g (n),⁺ which, together, implies g + e,i = re,i ·(uv,i + P e∈δ+(v) g e,i). Finally, (f (n) , r′(n) ) converges weakly to (f, r′ ) and, as the graph of R^T is sequentially weakly closed, we must have r ′ ∈ R^T (f).

Altogether, this shows (f, r, g, r′ ) ∈ graph(Γ) which completes the proof. ■

Using the previous three claims, Theorem 3.2 now guarantees the existence of a fixed point of Γ, i.e. a pair (f, r) ∈ K with (f, r) ∈ Γ(f, r). This pair then fulfils

f ⁻ = Φ^T (f ⁺), implying that f is consistent with Φ until T,
f + e,i = re,i · uv,i + P e∈δ−(v) f e,i and r ∈ R^T (f), which together imply that f fulfils flow conservation until T and is consistent with the routing operator R until T.

The previous theorem shows existence of coherent flows up to any finite time horizon in continuous models. For some models (like certain full information equilibria) this is already enough to guarantee existence of a coherent flow for all times as one can just choose a large enough time horizon T such that all coherent flows terminate before that time (cf. Corollary 3.8). For other models, this may not be possible (e.g. due to infinitely lasting network inflow rates or because coherent flows allow cycling behaviour – see, for example, [GHS20, Theorem 6.1]). Here, under the additional assumption of causality, we can still reach an infinite time horizon (cf. Theorem 3.5) by following an extensionbased approach similar to the one used in [Gra24, Section 4.1].

Definition 3.3. A pair of an edge-loading operator Φ and a routing operator R fulfils the extension existence property, if for all T ∈ R≥⁰ and for every flow f that is coherent until time T, there exists some α ∈ R>⁰ and a flow g that coincides with f until time T and is coherent until T + α.

Lemma 3.4. Assume that Φ is locally bounded and that Φ and R are causal and fulfil the extension existence property. Then, there exists a flow that is coherent until time ∞.

Proof. We call the pair (f, T) of a flow f and a time T ∈ R^∞ ≥0 a partially coherent flow if f is coherent until time T and ess supp(f) ⊆ [0, T]. On the set of all partially coherent flows, we define the partial order ⪯ such that (f, T) ⪯ (g, T′ ) is equivalent to T ≤ T ′ and f = 1[0,T] · g. We now use Zorn's Lemma ([AB06a, Lemma 1.7]) to show that there exists a maximal element. By the extension existence property, the horizon of this maximal element must then be ∞.

To apply Zorn's Lemma, we need to show that any arbitrary chain C has an upper bound. If C is the empty chain, then (0, 0) is an upper bound. Otherwise, let (f (n) , T(n) )n∈N≥¹ be a non-decreasing (w.r.t. ⪯) sequence in C such that limn→∞ T (n) = T ^∗ where T ∗ := sup(f,T)∈^C T. We define

$$f \coloneqq \sum{n \in \mathbb{N}{\geq 1}} \mathbb{1}_{\left[T^{(n-1)}, T^{(n)}\right)} \cdot f^{(n)}$$

with T (0) := 0. We first show that (every entry of) f is locally p-integrable: If T = ∞ holds, this is clear (on a bounded interval, f is equal to some f (n) for large enough n). Otherwise T < ∞ and by the local boundedness of Φ we have

$$BT' \geq \lim{n \to \infty} \left| \mathbbm{1}{[0,T^{(n)}]} \cdot \Phi(f^{(n),+}) \right| \stackrel{\text{\tiny (*)}}{=} \lim{n \to \infty} \left| \mathbbm{1}{[0,T^{(n)}]} \cdot f^{(n),-} \right| = \left| \mathbbm{1}{[0,T]} \cdot f^- \right|,$$

where we use the fact that (f (n) , T(n) ) is partially coherent at (∗). Moreover, f fulfils flow conservation until T (as all f (n) do) and, thus, ∥f∥ ≤ ∥u| [0,T] ∥ + maxv∈^V |δ ⁺(v)| · B′ T . By the causality of Φ and R, f is consistent with Φ and R until T and therefore (f, T) is a partially coherent flow and, in particular, an upper bound of the chain C.

The extension existence property holds if the operators are continuous on the extension time period. For this purpose, we define the following setsof functions: For any (finite) time horizon T ∈ R^≥0, α ∈ R>⁰ and flow f ∈ R^E×I×{+,−} T , we define the set of possible extensions of the inflow rates f ⁺ as

$$\Omega{T,\alpha}^{+}(f^{+}) \coloneqq { g^{+} \in \mathcal{R}{T+\alpha}^{E \times I} \mid \mathbb{1}{[0,T]} \cdot g^{+} = \mathbb{1}{[0,T]} \cdot f^{+} }$$

and the set of flow extensions of f as

$$\Omega{T,\alpha}(f) := { g \in \mathcal{R}{T+\alpha}^{E \times I \times {+,-}} \mid \mathbb{1}{[0,T]} \cdot g = \mathbb{1}{[0,T]} \cdot f }.$$

Theorem 3.5. Let Φ be a locally bounded and causal edge-loading operator and let R be a causal routing operator such that for every flow f that is coherent until some time T ∈ R^≥⁰ there exists some α ∈ R>⁰ such that

(i) the mapping Φ^T ⁺α|^Ω T,α(f+) is sequentially weak-weak continuous, and
(ii) the mapping R^T ⁺α|^ΩT,α(f) has a sequentially weakly closed graph and non-empty, convex values. Then, Φ and R fulfil the extension existence property and there exists a flow that is coherent until ∞.

Proof. Let h be a flow that is coherent until time T. We show that there exists a flow f that is coherent until time T + α and coincides with h until T.

For this purpose, we adjust the proof of Theorem 3.1: We use the set K and correspondence Γ as defined there but with all occurrences of T replaced by T + α. As h satisfies flow conservation and is consistent with R until T, let r ^∗ ∈ R(h) be given such that h + e,i(θ) = r ∗ e,i(θ) · P e ′∈δ+(v) h + e ,i(θ) = r ∗ e,i(θ) · (uv,i(θ) + P e ′∈δ−(v) h − e ,i(θ)) holds for almost all θ < T. We then add the constraints ¹[0,T] · (f ⁺, f ⁻) = 1[0,T] · h and 1[0,T] · r = 1[0,T] · r ∗ to the set K (and restrict the domain and values of Γ to the new K and subsets of the new K, respectively). First, note that K is still non-empty (since 1[0,T] · (h, r^∗ ) is in K), convex and weakly compact. To see the latter, note that K is still strongly closed (convergence in norm implies convergence almost everywhere, cf. [RF10, Section 7.3, Riesz-Fischer-Theorem]) and convex and thus weakly closed.

Every Γ(f, r) is non-empty as the same witness g with g ⁻ := Φ^T ⁺α(f ⁺), g + e,i := re,i · (uv,i + P e ′∈δ−(v) g − e ,i) also fulfils the newly added constraints of K: By causality of Φ and as f ⁺ and h + coincide until T, it follows that

$$\mathbb{1}{[0,T]} \cdot g^- = \mathbb{1}{[0,T]} \cdot \Phi(f^+) = \mathbb{1}{[0,T]} \cdot \Phi(h^+) = \mathbb{1}{[0,T]} \cdot h^-.$$

Using the constraint of K on r we also get

$$\mathbb{1}{[0,T]} \cdot g{e,i}^+ = \mathbb{1}{[0,T]} \cdot r{e,i} \cdot \left( u{v,i} + \sum{e' \in \delta^+(v)} g{e,i}^- \right) = \mathbb{1}{[0,T]} \cdot r{e,i}^* \cdot \left( u{v,i} + \sum{e' \in \delta^+(v)} h{e,i}^- \right) = \mathbb{1}{[0,T]} \cdot h{e,i}^+$$

Furthermore, by the causality of R and the fact that f and h coincide until T, there exists some r ′ ∈ R^T ⁺α(f) such that 1[0,T] · r ′ = 1[0,T] · r ∗ . Hence, (g, r′ ) is in K.

Clearly, the values of Γ remain convex. Finally, with the same arguments as in the proof of Claim 3, the graph of Γ is again weakly closed.

Hence, by Theorem 3.1 there exists a fixed point (f, r) of Γ. The flow f does not only fulfil the desired properties until time T + α, but as (f, r) is an element of K, coincides with h until time T.

Therefore, h is an extension of f proving the extension existence property for Φ and R. The existence of a coherent flow until ∞ then follows immediately by Lemma 3.4.

If the model satisfies strict causality, then the extension existence property holds even without the continuity assumptions of the previous theorem:

Lemma 3.6. Assume Φ and R are strictly causal and assume that R has non-empty values. Then, Φ and R fulfil the extension existence property.

If, additionally, Φ is locally bounded, then there exists a flow that is coherent until time ∞.

Proof. Let T ∈ R≥⁰ and let f be a flow that is coherent until T. Choose any element r ∈ R(f) witnessing the consistency of f with R until T and define g ⁻ := Φ^T +1(f ⁺) and g + e,i := re,i · (uv,i + P e∈δ+(v) g − e,i) for e ∈ E, i ∈ I. Since f is consistent with Φ until T, this implies that f and g conincide until time T. Hency, by strict causality, there exists some α ∈ R>⁰ (without loss of generality assume α ≤ 1) such that 1[0,T ⁺α] ·R(g) = 1[0,T ⁺α] ·R(f) ∋ 1[0,T ⁺α] ·r and 1[0,T ⁺α] ·Φ(g ⁺) = 1[0,T ⁺α] ·Φ(f ⁺) = g ⁻ hold. Then, g is coherent until T + α.

The additional part of the lemma then follows immediately by Lemma 3.4.

For non-causal models, on the other hand, extensions of the form used in the proof of Lemma 3.4 do not work as extending a partially coherent flow can also affect whether or not the flow is coherent before the extension interval.2 Here, one instead often argues (see, e.g., [CCL15, Lemma 3]) that

²The thin-flow extensions used in [CCL15, Section 4] within the (non-causal) full information setting are a different type of extension as these extensions determine the whole trajectory of the involved particles from source to sink.

there exists some large but finite time horizon T such that for any coherent flow until T all flow particles have already left the network and, thus, it can be extended by the zero flow to a coherent flow for all times.

Definition 3.7. A flow f terminates until time T if the essential support of f and the essential support of Φ(f ⁺) are contained in [0, T].

Corollary 3.8. Suppose the assumptions of Theorem 3.1 hold for some T ∈ R≥⁰ and assume the following two conditions:

(i) The essential support of u is contained in [0, T].
(ii) Any flow in R E×I×{+,−} T that is coherent until time T and fulfils flow conservation until time ∞ is already consistent with Φ until time ∞.

Then, there exists a flow which is coherent until time ∞.

Condition (ii) is fulfilled if every flow in R E×I×{+,−} T that is coherent until time T and fulfils flow conservation until time ∞ terminates until time T.

Proof. Theorem 3.1 gives us the existence of a flow f ∈ R^E×I×{+,−} T that fulfils the desired properties until time T. Clearly, the flow also fulfils flow conservation and consistency with R after time T as nothing flows into or out of any node then. Hence, due to condition (ii), it is consistent with Φ until time ∞ as well.

Assume now that every flow in R E×I×{+,−} T that is consistent with Φ and R until time T and fulfils flow conservation until time ∞ terminates until time T. Let f be a flow in R E×I×{+,−} that is consistent with Φ and R until time T and fulfils flow conservation until time ∞. Then, f terminates until time T. Hence, both f and Φ(f ⁺) vanish outside [0, T] and, therefore, f is consistent with Φ until time ∞.

3.2. Uniqueness

In many models, coherent flows are not unique: For example, neither dynamic Nash equilibria nor instantaneous dynamic equilibria (see Section 4.1) are unique in general as the simple example of two parallel edges with the same flow-independent travel times shows. However, for the linear-edge delay model and a class of prescriptive and causal routing operators, Bayen et al. [BKPS19, Theorem 3.4] state3 that if the routing operator fulfils a Lipschitz condition, the resulting flow is in fact unique. We generalize this uniqueness result to abstract physical models and a more general class of prescriptive and causal routing operators. Similar to the last subsection, we use an extension-based approach.

We begin by defining the unique extension property that we aim to show.

Definition 3.9. A pair of an edge-loading operator Φ and a routing operator R fulfils the unique extension property, if for any two flows f and g that coincide until some time T and that are coherent until some later time T ′ > T, there exists an α > 0 such that f and g coincide until time T + α.

Lemma 3.10. Assume Φ and R fulfil the unique extension property. Then, for every T ∈ R^∞ ≥0 , any two flows that are coherent until time T coincide until time T.

In particular, there is at most one flow that is coherent until ∞.

Proof. Assume for the contrary that there are two flows f and g which are both coherent up to some time T ′ but do not coincide up to that time. We then have

$$T \coloneqq \inf \left{ \theta \le T \mid \mathbb{1}{[0,\theta)} \cdot f \ne \mathbb{1}{[0,\theta)} \cdot g \right} < T'.$$

Then, f and g coincide until T and are coherent until T ′ > T. Hence, the unique extension property guarantees the existence of some α > 0 such that f and g coincide until T +α. This, however, is then a contradiction to the choice of T.

³While their proof is based on an incorrect lemma (see Appendix C), we show here that the statement itself is correct and their idea to use the Banach Fixed-Point Theorem as underlying machinery is valid.

If the operators are strictly causal and R is prescriptive, the unique extension property can be shown without requiring a fixed-point theorem:

Lemma 3.11. Assume that Φ and R are strictly causal and that R is prescriptive. Then Φ and R fulfil the unique extension property.

In particular, if, additionally, Φ is locally bounded, then there exists a unique flow that is coherent until time ∞.

Proof. Let T ∈ R>⁰ and let f and g be two flows coinciding until T and that are coherent until some later time T ′ > T. Let α be the minimum of the two values for α obtained by applying strict causality of Φ and R. This implies 1[0,T ⁺α] · r(f) = 1[0,T ⁺α] · r(g) and 1[0,T ⁺α] · Φ(f) = 1[0,T ⁺α] · Φ(g). Then we have g ⁻(θ) = f ⁻(θ) and, consequently,

$$f{e,i}^+(\theta) = r{e,i}(f)(\theta) \cdot \mathbbm{1}_{v \neq ti} \cdot f{v,i}^+(\theta) = r{e,i}(g)(\theta) \cdot \mathbbm{1}{v \neq ti} \cdot g{v,i}^+(\theta) = g_{e,i}^+(\theta)$$

for almost all θ < min { T + α, T′ } and all e ∈ E, i ∈ I. Thus, f and g coincide until min { T + α, T′ } > T.

The additional part of the lemma then follows immediately by Lemma 3.10 together with Lemma 3.6.

If, however, our operators are only causal (but not strictly causal) we can instead require a stronger continuity property on the mapping Ψ that maps (for some extension interval) inflow rates g ⁺ to new inflow rates that are induced by the flow (g ⁺, Φ(g ⁺)) acting on the routing operator R. This allows us to apply the famous Banach Fixed-Point Theorem ([AB06a, Theorem 3.48]) which guarantees the existence of a unique fixed point. Afterwards we will show that Ψ satisfies this property whenever both the edge-loading and routing operator satisfy a certain Lipschitz-continuity on small extension intervals.

Theorem 3.12 (Banach Fixed-Point Theorem). A map Ψ : X → X on a non-empty, complete metric space (X, d) has a unique fixed point x ∗ if Ψ is a contraction, which means that there exists some κ < 1 such that d(Ψ(x), Ψ(y)) ≤ κ · d(x, y) for all x, y ∈ X.

Lemma 3.13. For a pair (Φ, R) of a causal edge-loading operator and a prescriptive and causal routing operator, we introduce the following so-called contraction property (C):

$$\Psi^{f}{T,\alpha}: \Omega^{+}{T,\alpha}(f^{+}) \rightarrow \Omega^{+}{T,\alpha}(f^{+}), \ \ \Psi^{f}{T,\alpha}(g^{+}){e,i} := \mathbb{1}{[0,T+\alpha]} \cdot (u{v,i} + \sum{e' \in \delta^{-}(v)} \Phi(g^{+}){e',i}) \cdot r{e,i}(g^{+}, \Phi(g^{+}))$$

If (C) is fulfilled, then Φ and R satisfy both the unique extension property and the extension existence property. In particular, if Φ is, additionally, locally bounded, there exists a unique flow that is coherent until time ∞.

Proof. Note that the mapping Ψ f T ,α is well-defined for every α > 0 and flow f that is coherent until time T due to the causality of Φ and R. Therefore, for any such f, there exists an α such that the contraction Ψ f T ,α admits a unique fixed point by the Banach Fixed-Point Theorem.

We first show the unique extension property. Let f and g be two flows that coincide until time T and that are coherent until T ′ > T. Let α ∈ R>⁰ be given by the contraction property (w.r.t. f and T). Then, for any α ′ ∈ (0, α], also the mapping Ψ f T ,α′ is a contraction. Thus, we may assume α ≤ T ′ − T. Clearly, both 1[0,T ⁺α] · g ⁺ and 1[0,T ⁺α] · f ⁺ are in Ω + T ,α(f ⁺) and, as both f and g are coherent until T + α, they are both fixed points of Ψ f T ,α. Since the fixed point is unique, f and g must coincide until time T + α.

We now show the extension existence property. Let T ∈ R^≥⁰ and let f be a flow that is coherent until time T. Let α be given as described in the contraction property and let g ⁺ be a fixed point of Ψ. Then, g := (g ⁺, Φ(g ⁺)) is coherent until T + α and coincides with f until time T by the causality of Φ and R.

The additional part of the lemma now follows again immediately using Lemmas 3.6 and 3.10.

Theorem 3.14. Let Φ be a causal edge-loading operator and let R be a causal, prescriptive routing operator. Assume that all network inflow rates uv,i are contained in L^∞ loc(R) for ^v ^∈ V, i ^∈ ^I, and assume that for all flows f that are coherent until time T there exists some α > 0 such that

(i) the mapping Φ^T ⁺α|^Ω T,α(f+) is essentially bounded, i.e. supg+∈^Ω T,α(f+) ∥Φ^T ⁺α(g ⁺)∥^∞ < ∞, and
(ii) the mapping Φ^T ⁺α|^Ω T,α(f+) is Lipschitz continuous (with respect to the p-norm), and
(iii) the mapping r^T ⁺α|^ΩT,α(f) is Lipschitz continuous from (ΩT ,α(f), ∥ · ∥¹ ) to (R E×I T +α , ∥ · ∥^p ).

Then, Φ and R satisfy the contraction property (C).

In particular, if additionally Φ is locally bounded, there exists a unique flow that is coherent until time ∞.

Note that the conditions (ii) and (iii) of Theorem 3.14 are trivially fulfilled if Φ and R are uniformly strictly causal, respectively.

Proof of Theorem 3.14. Let α be given as in the assumptions above and choose M ∈ R>⁰ such that M is an upper bound of ∥1[0,T ⁺α] ·(uv,i + P ^e∈δ+(v) Φ(g ⁺)e,i)∥^∞ for all g ⁺ ∈ Ω + T +α (f) and v ∈ V , i ∈ I. Let L¹ and L² be Lipschitz constants of Φ^T ⁺α|^Ω T,α(f+) and r^T ⁺α|^ΩT,α(f) , respectively. Without loss of generality, assume L¹ ≥ 1, L² > 0.

We prove that Ψ := Ψ^f T ,α˜ is a contraction w.r.t. any fixed α˜ ≤ α satisfying α˜ ^q < (M · L¹ · L2) −1 where q is the conjugate of p fulfilling ¹/^p + ¹/^q = 1. Let f ⁺ and g ⁺ be arbitrary in Ω + T + ˜α (f). We deduce

$$\begin{aligned} \left| \Psi{e,i}(f^+) - \Psi{e,i}(g^+) \right|p &\leq M \cdot \left| \mathbb{1}{[0,T+\tilde{\alpha}]} \cdot (r{e,i}(f^+, \Phi(f^+)) - r{e,i}(g^+, \Phi(g^+))) \right|p \ &= M \cdot \left| r{T+\tilde{\alpha}}(f^+, \Phi(f^+)){e,i} - r{T+\tilde{\alpha}}(g^+, \Phi(g^+))_{e,i} \right|_p. \end{aligned}$$

Applying the Lipschitz continuity of r^T ⁺α|ΩT,α(f) yields

$$|\Psi{e,i}(f^+) - \Psi{e,i}(g^+)|_p \le M \cdot L_2 \cdot \max(|f^+ - g^+|1, |\Phi{T+\tilde{\alpha}}(f^+) - \Phi_{T+\tilde{\alpha}}(g^+)|_1),$$

where the second inequality holds because of the Lipschitz-continuity of r. As f and g coincide until time T and as Φ is causal, it suffices to only the interval [T, T + ˜α] for the norms. By applying Hölder's inequality, we obtain

$$|\Psi{e,i}(f^+) - \Psi{e,i}(g^+)|_p \le M \cdot L_2 \cdot \tilde{\alpha}^q \cdot \max(|f^+ - g^+|p, |\Phi{T+\tilde{\alpha}}(f^+) - \Phi_{T+\tilde{\alpha}}(g^+)|_p).$$

Finally, with the Lipschitz-continuity of Φ^T + ˜^α (and as L¹ ≥ 1) we obtain

$$|\Psi{e,i}(f^+) - \Psi{e,i}(g^+)|_p \le M \cdot L_1 \cdot L_2 \cdot \tilde{\alpha}^q \cdot |f^+ - g^+|_p$$

Since we have M · L¹ · L² · α˜ ^q < 1, this shows that Ψ is a contraction on Ω + T ,α(f ⁺).

4. Stochastic Prediction Equilibrium

In this section, we first show how the known concepts of (deterministic) dynamic prediction equilibria as well as flows defined by prescriptive routing operators fall within our framework and how our existence and uniqueness results from the previous section apply to them. Then, we use our framework to define the new concept of a stochastic prediction equilibrium. The idea here is to augment predictions of agents with random noise so that the effective cost predictor of agents becomes a random variable. As our main result, we show existence and uniqueness of stochastic prediction equilibria under mild assumptions.

4.1. Deterministic Prediction Equilibrium

We first analyse deterministic prediction equilibria where particles choose their path by minimizing the predicted travel cost neglecting any random noise. We use the model proposed in [GHKM23], and show that it fits into the concept of routing operators.

For each pair of nodes v, w ∈ V , we denote the finite set of simple v-w-paths by Pv,w. We assume that the sets Pv,tⁱ are non-empty for all commodities i ∈ I and all nodes v ∈ V . Each commodity is associated with a cost predictor Cˆ i,p : R×R^E×I×{+,−} → R≥⁰ for each simple path p where Cˆ i,p(θ, f) is the predicted cost of traversing path p when entering the path at time θ as predicted at the same time θ using the flow f. We assume that Cˆ i,p(· , f) is measurable for any cost predictor Cˆ i,p and flow f.

For a commodity i ∈ I, an edge e = vw with v ̸= tⁱ is called active at time θ for commodity i, if e is the first edge of an optimal path in Pv,tⁱ when starting at v at time θ as predicted at the same time θ according to Cˆ i ; in formulas:

$$\exists p \in \mathcal{P}_{v,t_i} : \quad p1 = e \land p \in \operatorname{argmin}{q \in \mathcal{P}_{v,ti}} \hat{C}{i,q}(\theta, f).$$

We denote the set consisting of all active edges of commodity i at time θ by Eˆ ⁱ(θ, f); we denote the set of active times of an edge e and a commodity i by Θˆ e,i(f).

Definition 4.1. A flow f only uses active edges w.r.t. Cˆ until time T ∈ R^∞ ≥0 if for all e ∈ E, i ∈ I and almost all θ < T it holds that

$$f_{e,i}^+(\theta) > 0 \implies e \in \hat{E}_i(\theta, f).$$

Definition 4.2. A flow f is a dynamic prediction equilibrium (DPE) until time T if f is consistent with Φ, fulfils flow conservation, and only uses active edges w.r.t. Cˆ until time T.

The cost predictors Cˆ i,p are often based on the (actual) travel time functions c^e : R×RE×I×{+,−} → R^≥⁰ on the edges e ∈ E of the network, where ce(θ, f) is the travel time of edge e as induced by the flow f when entering e at time θ. Based on these, we can define τe(θ, f) := θ + ce(θ, f) as the exit time when entering edge e at time θ given flow f. Usually, the travel time functions c^e are induced by the underlying physical model.

As described by Graf et al. [GHKM23], several well-studied equilibrium concepts fall into the class of dynamic prediction equilibria by choosing appropriate cost predictors. These concepts include dynamic (Nash) equilibria (DE) and instantaneous dynamic equilibria (IDE).

A dynamic Nash equilibrium models the situation in which particles have full access to (future) information, which here means that they may use the future evolution of c^e to minimize their actual travel time. This is achieved by the use of the so-called perfect predictor, i.e.

$$\hat{C}_p(\theta, f) := \taup(\theta, f) - \theta = (\tau{ek}(\,\boldsymbol{\cdot}\,, f) \circ \, \cdots \, \circ \, \tau{e_1}(\,\boldsymbol{\cdot}\,, f))(\theta) - \theta$$

which predicts the travel time when entering path p = (e1, . . . , ek) at time θ exactly as it will constitute w.r.t. the flow f.

An instantaneous dynamic equilibrium reflects the situation in which particles only have instantaneous information on the current travel times on every edge (at the time the particle takes any decision). Here, the particles choose an edge that minimizes their instantaneous travel time by using the so-called constant predictor

$$\hat{C}p(\theta, f) := \sum{e \in p} c_e(\theta, f)$$

where the predictions no longer depends on the future evolution of f.

The flexibility of this framework also allows the use of more advanced cost predictors that are based on ML-algorithms, as it is often the case for today's navigation devices. These ML-based predictors (as well as the constant predictor) are then examples of causal predictors, i.e. predictors Cˆ for which whenever two flows f and g coincide until some time T, then Cˆ(· , f) and Cˆ(· , g) also coincide until T.

We now show that for given cost predictors, there exists a routing operator for which a flow is coherent if and only if it is a dynamic prediction equilibrium.

Lemma 4.3. Let f be a flow, T ∈ R^∞ ≥0 and let Cˆ be cost predictors. Then, f only uses active edges w.r.t. Cˆ until time T if and only if f is consistent until T with the routing operator

$$\mathscr{R}(f) \coloneqq \left{ \begin{array}{ll} \forall e, i: & r{e,i} \ge 0, \ \forall v, i: & \sum{e \in \delta^+(v)} r{e,i} = \mathbb{1}{v \ne ti}, \ \forall e, i, \forall{a.a.} \theta: & r_{e,i}(\theta) > 0 \implies e \in \hat{E}_i(\theta, f) \end{array} \right}. \tag{1}$$

Proof. Assume f only uses active edges up to time T. For a commodity i ∈ I and an edge e = vw with v ̸= tⁱ we define

$$r{e,i}(\theta) := \begin{cases} \frac{f{e,i}^+(\theta)}{\sum{e \in \delta^+(v)} f{e,i}^+(\theta)}, & \text{if } \sum{e \in \delta^+(v)} f{e,i}^+(\theta) > 0 \land \theta < T, \ \frac{1{\Theta{e,i}(f)}(\theta)}{|\delta^+(v) \cap \hat{E}_i(\theta,f)|}, & \text{otherwise,} \end{cases}$$

and re,i(θ) := 0 for v = tⁱ . Note that re,i is a well-defined measurable function since 1 ≤ |δ ⁺(v) ∩ Eˆ ⁱ(θ, f)| = P ^e∈δ+(v) ¹Θˆ e,i(f) (θ) holds. Clearly, re,i is locally p-integrable, re,i(θ) must be in the interval [0, 1] and we have P e∈δ+(v) re,i(θ) = 1v̸=tⁱ for all e ∈ E, v ∈ V, i ∈ I and almost all θ ∈ R. Finally, re,i(θ) > 0 can only hold if θ ∈ Θˆ e,i(f) or if f + e,i(θ) > 0 with θ < T hold. The latter (also) implies e ∈ Eˆ ⁱ(θ, f) as f only uses active edges up to T. In conclusion, this shows that r ∈ R(f). By construction of r, we also have f + e,i(θ) = re,i(θ)· P e∈δ+(v) f + e,i(θ) for all i ∈ I, e = vw ∈ E and almost all θ < T, and thus f is consistent with R up to time T.

For the other direction, assume that f is consistent with R up to time T and let r ∈ R(f) be such that f + e,i(θ) = re,i(θ) · P e∈δ+(v) f + e,i(θ) for all i ∈ I, e = vw ∈ E and almost all θ ∈ [0, T). Then, f + e,i(θ) can only be positive whenever ^re,i is positive, in which case ^e ^∈ ^E^ˆ ⁱ(θ, f) holds. Therefore, f only uses active edges up to time T.

We continue by showing that the graph of R^T is sequentially weakly closed under certain conditions. This allows us to then apply the existence results from the previous section to dynamic prediction equilibria.

Lemma 4.4. Let T ∈ R^≥0. Assume that for any sequence of flows f (n) in R E×I×{+,−} converging weakly to some flow f, we have

$$\lim{n \to \infty} \lambda \left( \hat{\Theta}{e,i}(f^{(n)}) \setminus \hat{\Theta}_{e,i}(f) \right) = 0.$$

Then, the graph of R^T is sequentially weakly closed where R is the routing operator defined in eq. (1). Proof. Let (f (n) , r(n) ) be a sequence in the graph of R^T converging weakly to some (f, r). We aim to show r ∈ R^T (f).

The first two conditions in eq. (1) hold as the weak limit of a sequence of functions in L p ([0, T]) that are bounded a.e. by some constant c is also bounded a.e. by c: Assume r (n) e,i (θ) ≤ c for almost all θ and let M be the set of θ such that re,i(θ) > c. By the weak convergence, we have

$$c \cdot \lambda(M) \geq \int r_{e,i}^{(n)} \cdot \mathbb{1}M \, \mathrm{d}\lambda \to \int r{e,i} \cdot \mathbb{1}_M \, \mathrm{d}\lambda \geq c \cdot \lambda(M),$$

which implies R re,i · 1^M dλ = c · λ(M) < ∞ and, thus, re,i(θ) = c for almost all θ ∈ M, and therefore λ(M) = 0. The lower bound case works analogously.

For the third condition we aim to show that re,i vanishes on the set Θˆ e,i(f) ^c where S ^c denotes the set complement S c := [0, T] \ S. For this, we consider the weak closure Kⁿ of the set Kⁿ := conv({r (k) | k ≥ n}), where conv denotes the convex hull operator. Note that as Kⁿ is again a convex set, it is also closed with respect to the norm topology (cf. [Hun13, Theorem 7.10]). In particular, for each n ∈ N, the set Kⁿ contains r, and thus there exists a sequence in each Kⁿ that converges strongly to r. From these, we can construct a sequence (g (n) )ⁿ such that g (n) ∈ Kⁿ holds for all n ∈ N and g (n) converges to r in norm. By passing to a subsequence, g (n) converges almost everywhere to r (cf. [RF10, Section 7.3, Riesz-Fischer-Theorem]). Note that g (m) e,i vanishes almost everywhere on the set Mⁿ := T ^k≥ⁿ Θˆ e,i(f (k) ) c for every m ≥ n. Therefore, r vanishes almost everywhere on the set M := S ⁿ∈^N Mn.

We now bound the measure of the inactive times w.r.t. f that are not in Mn:

$$\lambda(\hat{\Theta}_{e,i}(f)^{\mathsf{c}} \setminus Mn) = \lambda(\hat{\Theta}{e,i}(f)^{\mathsf{c}} \setminus \bigcap{k \geq n} \hat{\Theta}{e,i}(f^{(k)})^{\mathsf{c}}) = \lambda(\bigcup{k \geq n} \hat{\Theta}{e,i}(f)^{\mathsf{c}} \setminus \hat{\Theta}_{e,i}(f^{(k)})^{\mathsf{c}})$$

$$\leq \sum{k \geq n} \lambda(\hat{\Theta}{e,i}(f)^{\mathsf{c}} \setminus \hat{\Theta}{e,i}(f^{(k)})^{\mathsf{c}}) = \sum{k \geq n} \lambda(\hat{\Theta}{e,i}(f^{(k)}) \setminus \hat{\Theta}{e,i}(f)).$$

By passing to a subsequence of (f (k) , r(k) )^k such that λ(Θˆ e,i(f (k) ) \ Θˆ e,i(f)) ≤ 1/2 ^k holds for all k ∈ N, the above sum is bounded from above by 1/2 n−1 . Therefore, λ(Θˆ e,i(f) ^c \ M) = 0 is fulfilled which concludes the proof.

Lemma 4.5. Let T ∈ R≥⁰ and let Cˆ i,p be a collection of cost predictors. If Cˆ i,p(θ, ·) is sequentially weak-strong continuous from R E×I×{+,−} T to R for all i ∈ I, p ∈ P and almost all θ < T, then the graph of the routing operator R^T defined in (1) has a sequentially weakly closed graph.

Proof. Let f (n) be a sequence weakly converging to f in R E×I×{+,−} T and consider only times θ where Cˆ i,p(θ, f(n) ) converges to Cˆ i,p(θ, f). If θ ∈ Θˆ e,i(f (n) ) holds for infinitely many n ∈ N, then there exists some path p starting with e = vw that minimizes Cˆ i,p(θ, f(n) ) over all paths in Pv,tⁱ for infinitely many n ∈ N. Therefore, Cˆ i,p(θ, f(n) ) converges to minq∈Pe,i Cˆ i,q(θ, f) and, thus, θ ∈ Θˆ e,i(f). Clearly, this implies λ(Θˆ e,i(f (n) ) \ Θˆ e,i(f)) → 0, and we can apply Lemma 4.4.

Corollary 4.6. Let Φ be a locally bounded edge-loading operator and let Cˆ i,p be a set of cost predictors.

(i) If, for some T ∈ R^≥0, Φ^T is sequentially weak-weak continuous and all f 7→ Cˆ i,p(θ, f) are sequentially weak-strong continuous from R E×I×{+,−} T to R for almost all θ < T, then there exists a dynamic prediction equilibrium until T.
(ii) If, for all T ∈ R^≥0, Φ^T is sequentially weak-weak continuous, and all f 7→ Cˆ i,p(θ, f) are sequentially weak-strong continuous from R E×I×{+,−} T to R for almost all θ < T, and if Φ and all Cˆ i,p are causal, then there exists a dynamic prediction equilibrium until ∞.

Proof. Note first, that the routing operator R defined in (1) always has non-empty (with witness rvw,i := 0, for v = tⁱ , and ^rvw,i := ¹Θˆ vw,i(f) / P ^e∈δ+(v) ¹Θˆ e,i (f), for v ̸= ti) and convex values. Therefore, with Lemma 4.5, we can apply Theorem 3.1 to get existence of a Φ-R-coherent flow until time T. Lemma 4.3 then ensures that this is also a dynamic prediction equilibrium until T.

Under the additional assumption that all predictors Cˆ i,p are causal, we immediately get causality of R. Together with the assumption that Φ is causal as well, we can, hence, apply Theorem 3.5 to obtain the extension existence property for Φ and R. Lemma 3.4 then guarantees the existence of a coherent flow (and, hence, a dynamic prediction equilibrium) until ∞.

Remark 4.7. If f 7→ ce(· , f) is sequentially weak-strong continuous from R E×I×{+,−} T to C([0, T], R^≥0) for all e ∈ E (which is the case for both Vickrey's model and the affine-linear volume-delay dynamics), then both the perfect predictor and the constant predictor become continuous in the sense of Corollary 4.6. Therefore, Corollary 4.6 (i) subsumes the existence results of dynamic Nash equilibria for Vickrey's model ([CCL15, Theorem 8]) and the affine-linear volume-delay model ([ZM00, Theorem 4.2]). Similarly, Corollary 4.6 generalizes the existence results for instantaneous dynamic equilibria, which can be found for Vickrey's model in [GHS20, Theorem 5.6], and the existence results for dynamic prediction equilibria in [GHKM23, Theorem 15]. Additionally, the above result can also be applied to new predictors obtained by combining the predictors mentioned so far. For example, a perfect predictor with limited time horizon where perfect predictions are used until some fixed finite time horizon and constant predictions afterwards.

4.2. Prescriptive Routing Operators

As a prerequisite of the uniqueness result for stochastic prediction equilibria in the next subsection, we first summarize our results on prescriptive operators R where we write r(f) for the single element of R(f). For this, we need the following variant of the closed-graph theorem:

Lemma 4.8. Let R be a prescriptive routing operator. Then, for every T ∈ R≥0, the graph of R^T is sequentially weakly closed if and only if r^T is sequentially weak-weak continuous, where we define r^T : R E×I×{+,−} ^T → L p (R) E×I by f 7→ 1[0,T] · r(f).

Proof. Note, that the graph of R^T coincides with the graph of r^T . Assume that this graph is sequentially weakly closed, and let (f (n) ) be a sequence in R E×I×{+,−} T converging weakly to f. Because L p (R) E×I is a reflexive Banach space, the ball with radius T around 0 is weakly compact (cf. [AB06a, Theorem 6.25]). Thus, the sequence (r^T (f (n) )) has a weakly converging subsequence. We pass to this subsequence, and let r ^∗ be its weak limit. As the graph of R^T is sequentially weakly closed, we must have r ^∗ = r^T (f).

Conversely, assume that r^T is sequentially weak-weak continuous, and let (f (n) , r(n) ) be a sequence in the graph of R^T converging weakly to (f, r^∗ ). Clearly, the weak limit of (r^T (f (n) )) is r^T (f) and thus r ^∗ = r^T (f).

Corollary 4.9. Let Φ be a locally bounded edge-loading operator and let R be a prescriptive routing operator.

(i) If, for some T ∈ R^≥0, Φ^T and r^T are sequentially weak-weak continuous, then there exists a coherent flow until T.
(ii) If, for all T ∈ R^≥0, Φ^T and r^T are sequentially weak-weak continuous, and Φ and r are causal, there exists a coherent flow until ∞.
(iii) If both Φ and r are strictly causal, there exists a unique coherent flow until ∞.
(iv) If Φ is uniformly strictly causal and essentially bounded, r is causal, and r^T is Lipschitzcontinuous w.r.t. ∥ · ∥¹ and ∥ · ∥^p on domain and codomain, respectively, for all T ∈ R^≥0, and u ∈ L^∞ loc(R) V ×I , then there exists a unique coherent flow until ∞.

Proof. We apply Theorem 3.1, Lemma 3.4 with Theorem 3.5, Lemma 3.6 together with Lemma 3.11, and Theorem 3.14 in this order and all together with Lemma 4.8.

Remark 4.10. This corollary generalizes the existence and uniqueness results for prescriptive operators presented by Bayen et al. [BKPS19]: They consider causal operators and show (a) existence for "continuous" such operators on finite horizons where their continuity assumption is stronger than the one specified in Corollary 4.9 (i)and (ii), (b) unique existence for so-called "delay-type" routing operators that are special cases of uniformly strictly causal operators and, thus, included in (iii), and (c) unique existence for "Lipschitz-continuous" operators with a condition similar to the Lipschitz condition in (iv).

One tempting question is whether, for a given set of cost predictors, there exists a prescriptive routing operator for which the set of coherent flows are exactly the dynamic prediction equilibria or at least a subset of the dynamic prediction equilibria. Of course, for any given dynamic prediction equilibrium f, we can "a posteriori" construct a prescriptive routing operator as re,i = f + e,i/( P e ′∈δ+(v) f + e,i) (whenever well-defined) such that (only) f is coherent with respect to this operator. However, the use of the equilibrium solution f in the definition of the behavioural model is not satisfying as usually we want to find f as the solution to the model.

Assuming all cost predictors are causal, another attempt would be to choose for every node and every possible set of outgoing edges some fixed flow-split over the active outgoing edges. Such a routing operator would then still be prescriptive, and any coherent flow would be a dynamic prediction equilibrium. In fact, for IDE, this is exactly what Bayen et al. [BKPS19, Routing 4.10] propose where they define a routing operator that equally distributes flow over all outgoing edges starting a currently shortest path. Any coherent flow would then be an IDE.

However, as already noted in [BKPS19], this routing operator does not satisfy the continuity conditions introduced there (nor the ones used in this paper) and, hence, they cannot show existence of such flows. In fact, it is not hard to see that coherent flows w.r.t. such a routing operator need not exist in general:

Example 4.11. Consider a single-source, single-sink network with two parallel paths consisting of two edges each. We use the Vickrey queueing model to define the physical model. All edges have a free flow travel time of 1. The edges on one path have service rates of 4 and 2, respectively, while the edges on the bottom path have service rates of 2 both (cf. Figure 1).

Figure 1: A network in Vickrey's model with edge labels (νe, c⁰ e ) with capacity ν^e and free-flow travel time c e

For a constant network inflow rate of 6, this network has a unique IDE. It starts with a flow split in a ratio of 4 : 2 between the upper and the lower paths. Starting at time 1 a queue builds up on the second edge of the upper path at a rate of 2 and the only possible flow split is 2 : 4. At time 2 the queue length on the second edge of the upper path remains constant at 2, while the first edge of the lower path has a queue length of 2 at time 2. Thus, the split changes back to 4 : 2 until time 3.

Note that the flow distribution at node s changes multiple times even though at all times both outgoing edges are active. Hence, no choice of a fixed flow distribution over active edges can lead to the existence of a flow with consistent the resulting routing operator.

4.3. Noisy Predictions

In reality, the predictions of an agent are usually subject to noise, for example due to measurement errors. We model this noise by assuming that the cost predictor Cˆ i,p is no longer fixed (as it is for dynamic prediction equilibria) but rather a random variable.

More specifically, a particle of commodity i that arrives at a node v ̸= tⁱ at some time ¯θ is assigned a cost predictor

$$\hat{C}: \mathbb{R} \times \mathcal{R}^{E \times I \times {+,-}} \to \mathbb{R}^{\mathcal{P}}, \quad (\theta, f) \mapsto (\hat{C}p(\theta, f)){p \in \mathcal{P}}$$

according to the random distribution of a probability measure Pⁱ over such prediction functions. The particle then evaluates the cost Cˆ p( ¯θ) for every v-ti-path p and chooses to enter an edge that lies on a path minimizing this value.

Let E˜ ⁱ(θ, f, Cˆ) denote this set of perceived active edges at time θ w.r.t. flow f and predictor Cˆ. Then, for any time θ ∈ R, any node v ∈ V , any commodity i ∈ I and any subset of edges M ⊆ δ ⁺(v) leaving v the probability that M is perceived as the set of active edges leaving v by particles of commodity i at time θ is defined as

$$\pi_{v,M,i}(\theta,f) := \mathbb{P}_i({\hat{C} \mid M = \tilde{E}_i(\theta,f,\hat{C}) \cap \delta^+(v)}),$$

We assume that all particles of commodity i carry out the same experiment independently of each other and, thus, among all particles of commodity i entering node v, the proportion of arriving particles of that commodity perceiving the set M as the set of active outgoing edges at time θ is exactly πv,M,i(θ, f). Let E denote the set of all pairs (M, e) of the form M ⊆ δ ⁺(v) and e ∈ M for any v ∈ V . We can then define the following routing operator

$$\mathscr{R}(f) := \left{ \left( \sum{M \ni e} r{M,e,i} \right){e,i} \middle| \begin{array}{c} (r{M,e,i}){(M,e,i)} \in L^p{\text{loc}}(\mathbb{R})^{\mathcal{E} \times I} : \ \forall M, e, i : \quad r{M,e,i} \ge 0, \ \forall v, M \ne \emptyset, i : \quad \sum{e \in M} r{M,e,i} = \pi{v,M,i}(\cdot, f) \end{array} \right}.$$ (2)

Here, rM,e,i is the share of the particles entering node v that perceive M as their set of active edges and choose the edge e as their next edge.

Definition 4.12. A stochastic prediction equilibrium (SPE) until time T is a flow that is coherent (until T) with respect to a given physical model Φ and the routing operator in (2).

Throughout this section, we will assume that the mapping (C, θ ˆ ) 7→ Cˆ ^p(θ, f) is (Pⁱ ⊗λ)-measurable for every flow f, path p and commodity i. This ensures that πv,M,i(· , f) is measurable and, thus, that R is well-defined:

Proposition 4.13. If (C, θ ˆ ) 7→ Cˆ ^p(θ, f) is (Pⁱ ⊗ λ)-measurable for all paths p, then πv,M,i(· , f) is measurable.

Proof. The function (C, θ ˆ ) 7→ minp∈^P Cˆ ^p(θ, f) is (Pⁱ ⊗ λ)-measurable for any P ⊆ Pv,tⁱ . Let P^e denote the subset of paths p ∈ Pv,tⁱ that use e as their first edge. Then, the function he(C, θ ˆ ) := minp∈P^e Cˆ ^p(θ, f) − minp∈Pv,ti Cˆ ^p(θ, f) is measurable as well as the set Θ^e := h −1 e (0) (which is the set of pairs (C, θ ˆ ) for which e is perceived active at time θ).

Now, for any specific θ we have

$${\hat{C} \mid M = \tilde{E}i(\theta, f, \hat{C}) \cap \delta^+(v)} = \left(\left(\bigcap{e \in M} Ae\right) \setminus \bigcup{e \in \delta^+(v) \setminus M} \Thetae\right){\theta} =: (\ThetaM){\theta},$$

where we denote S^θ := { Cˆ | (C, θ ˆ ) ∈ S } for any subset S of the product space. As Θ^M is measurable, the function πv,M,i(· , f) = θ 7→ Pi((ΘM)θ) is also measurable (cf. [Kle20, Theorem 14.19]).

Observation 4.14. If all Pⁱ are trivial probability measures assigning a single prediction function Cˆ i the probability 1, then the stochastic prediction equilibrium routing operator in (2) coincides with the dynamic prediction equilibrium routing operator (1) induced by (Cˆ i)i

Before diving into the properties of stochastic prediction equilibria, we give a natural example of a distribution over the predictors Cˆ inducing a stochastic version of instantaneous dynamic equilibria:

Example 4.15. We introduce a stochastic variant of instantaneous dynamic equilibria: In this model, every time a particle arrives at an intermediate node, it retrieves the current, instantaneous travel times of each edge disturbed by a stochastic measurement error. Let ce(θ, f) denote the (actual) travel time of edge e when entering e at time θ. Then, the particle retrieves the value cˆe(θ, f, εe,i) := ce(θ, f) + εe,i where the measurement error εe,i is distributed according to some random distribution Ue,i. The particles now aim to minimize their travel time according to the instantaneous, erroneous path costs Cˆ p,i(θ, f, ε) = P e∈p cˆe(θ, f, εe,i) where ε denotes the error vector (εe,i)e. Accordingly, the distributions (Ue,i)^e induce the probability measure Pⁱ . To ensure that R is well-defined, we assume that ce(· , f) are measurable functions. A flow that is coherent w.r.t. a given physical model Φ and this routing operator is called a stochastic IDE.

We now analyse the properties of stochastic prediction equilibria. We start by providing an equivalent description of the routing operator R defined in (2) which will allow us to show that R^T has a sequentially weakly closed graph under certain additional conditions, which we need, in turn, to prove existence of stochastic prediction equilibria.

Notation 4.16. We abbreviate the notation of sets of predictors Cˆ by writing { A(Cˆ) } instead of { Cˆ | A(Cˆ) } for any predicate A.

Lemma 4.17. For every v ∈ V , M ⊆ δ ⁺(v) and i ∈ I, define

$$\rho_{v,M,i}(\theta,f) := \mathbb{P}_i({\tilde{E}_i(\theta,f,\hat{C}) \cap \delta^+(v) \subseteq M})$$

denoting the probability that all edges in δ ⁺(v) perceived as active by particles of commodity i at time θ are contained in M. Then we have

$$\mathscr{R}(f) = \left{ (r{e,i}){(e,i)} \in L^p{\mathrm{loc}}(\mathbb{R})^{E \times I} \middle| \begin{array}{c} \forall e, i : \quad r{e,i} \ge 0, \ \forall v, i : \quad \sum{e \in \delta^+(v)} r{e,i} = \mathbb{1}_{v \ne t_i}, \ \forall i, v \ne ti, M \subseteq \delta^+(v) : \quad \sum{e \in M} r{e,i} \ge \rho{v,M,i}(\cdot, f) \end{array} \right}. \tag{3}$$

Proof. Let r ∈ R(f). Then, for every e ∈ E, i ∈ I, the entry re,i is of the form P M∋e rM,e,i with (M, e) ∈ E. For all v ∈ V it holds that

$$\sum{e \in \delta^+(v)} r{e,i} \ = \ \sum{e \in \delta^+(v)} \sum{\substack{M \subseteq \delta^+(v) \ M \ni e}} r{M,e,i} \ = \ \sum{\substack{M \subseteq \delta^+(v) \ M \neq \emptyset}} \sum{e \in M} r{M,e,i} \ = \ \sum{\substack{M \subseteq \delta^+(v) \ M \neq \emptyset}} \pi{v,M,i}(\boldsymbol{\cdot},f) \ = \ \mathbbm{1}_{v \neq t_i}$$

Furthermore, for v ̸= tⁱ and for every M ⊆ δ ⁺(v) we have

$$\begin{split} \sum{e \in M} r{e,i} &= \sum{e \in M} \sum{\substack{M' \subseteq \delta^+(v) \ M' \ni e}} r{M',e,i} \geq \sum{e \in M} \sum{\substack{M' \subseteq M \ M' \ni e}} r{M',e,i} = \sum{\substack{M' \subseteq M \ M' \neq \emptyset}} r{M',e,i} = \sum{\substack{M' \subseteq M \ M' \neq \emptyset}} \pi{v,M',i}(\cdot,f) \ &= \mathbb{P}_i( { \hat{C} \mid \tilde{E}i(\theta,f,\hat{C}) \cap \delta^+(v) \subseteq M }) = \rho{v,M,i}(\theta,f) \end{split}$$

where the second to last equation holds because E˜ ⁱ(θ, f, Cˆ) ∩ δ ⁺(v) cannot be the empty set.

For the other direction, let r be an element of the right-hand side of (3). We use the max-flow min-cut theorem to show that a suitable "partition" of each re,i exists. For this, fix some θ ∈ R, v ∈ V , and i ∈ I. We need to determine suitable rates rM,e,i(θ) for M ⊆ δ ⁺(v) and e ∈ M such that re,i(θ) = P M∋e rM,e,i(θ), for every e ∈ δ ⁺(v), and P ^e∈^M rM,e,i = πv,M,i(θ, f), for every M ⊆ δ ⁺(v) with M ̸= ∅, hold. If v = tⁱ , we simply set rM,e,i := 0. This is possible as re,i = 0 holds for every e ∈ δ ⁺(v), and for every M ̸= ∅ we have πv,M,i(θ, f) = 0.

Otherwise, v ̸= tⁱ . We build an artificial network (V, A) to apply the max-flow min-cut theorem (see Figure 2). In this network, we refer to the directed edges A as arcs and to the nodes V as vertices to avoid confusion with the "natural" edges and nodes of our traffic network. The network is a directed acyclic graph consisting of four layers of vertices: In the first layer, there is only a single artificial source vertex s. The second layer consists of a vertex for each subset M of δ ⁺(v); each such vertex has an incoming arc from s with capacity πv,M,i(θ, f). The third layer consists of a vertex for each edge in δ ⁺(v); for each subset M ⊆ δ ⁺(v) there is an arc from M's vertex to e's vertex for every e ∈ M. These arcs have infinite capacity (and thus never occur in a min-cut). Finally, the fourth layer consists only of a single artificial sink vertex t. For every edge e there is an arc from e to t with capacity re,i(θ).

We show that the maximum flow value is 1; then setting the value rM,e,i(θ) to the flow on the arc from M to e of any maximum flow would satisfy the requirements: As the maximum flow value is 1 = P M⊆δ+(v) πv,M,i(θ, f) and πv,∅,i = 0, every vertex of a subset M must have incoming (and outgoing) flow of value πv,M,i(θ, f). Therefore, we must have P ^e∈^M rM,e,i(θ) = πv,M,i(θ, f) for every M ̸= ∅. Furthermore, due to the capacity constraints, we must have re,i(θ) ≥ P M∋e rM,e,i(θ) for each e ∈ δ ⁺(v). As, additionally, P e re,i(θ) = 1 = P M P e rM,e,i(θ), we must have equality in the previous sentence.

P We now show that the minimum s-t-cut of this artificial network has value 1. Clearly, 1 = ^M πv,M,i(θ, f) is an upper bound (by considering the cut S = {s}). Let S be a minimal cut. Note, that M ∈ S implies e ∈ S for every e ∈ M (as the arc from M to e has infinite capacity). We consider the set M := {e ∈ δ ⁺(v) | e ∈ S}. Note that the previous observation tells us that every

Figure 2: An example for how the auxiliary network (right) used in the proof of Lemma 4.17 is constructed for some node v with outgoing edges δ ⁺(v) (left). The labels on the arcs of the auxiliary network indicate their capacities.

M′ ⊆ δ ⁺(v) that is not a subset of M is not contained in S (as there is an edge e in M′ which is not in S). By possibly removing all subsets of M and all edges in M from S, we obtain the cut {s} and the following inequality (where cap(S) denotes the capacity of cut S):

$$\operatorname{cap}(S) \leq \operatorname{cap}(S \setminus ({M' \mid M' \subseteq M} \cup M)) \leq \operatorname{cap}(S) + \sum{M' \subseteq M} \pi{v,M',i}(\theta,f) - \sum{e \in M} r{e,i}, \quad (4)$$

or, equivalently, P ^e∈^M re,i ≤ P ^M′⊆^M πv,M′ ,i(θ, f). As the latter equals ρv,M,i(θ, f) and as the flipped inequality is fulfilled, the inequalities in (4) must hold with equality. Furthermore, as the cut in the middle of the chain is {s} with value 1, the value of S must also be 1.

We use the Measurable Maximum Theorem (cf. [AB06a, Theorem 18.19]) to show that there exists a measurable selector of the maximum s-t-flows, and thus, measurable functions (rM,e,i)M,e,i satisfying the constraints in R(f). To apply this theorem, we show that the mapping ϕ : R ⇒ [0, 1]^|A^| , which maps a time θ to the polytope of the feasible s-t-flows w.r.t. the constraints at time θ, is a measurable correspondence. Note that, for every θ, the constraints of the polytope are of the form gk(x) ≤ ck(θ) where g^k is a continuous function from [0, 1]^|A^| to R and c^k is a measurable function on R. For each such constraint, we define the correspondence ϕk(θ) = { x ∈ [0, 1]^|A^| | gk(x) ≤ ck(θ) }. Then, ϕ^k is a measurable correspondence, because for every closed set S ⊆ [0, 1]^|A^| the set { θ | ∃x ∈ S : gk(x) ≤ ck(θ) } = { θ | minx∈^S gk(x) ≤ ck(θ) } is measurable due to the measurability of ck. Then, ϕ is a measurable correspondence as it is the intersection of the correspondences ϕ^k (cf. [AB06a, Lemma 18.4]).

Lemma 4.18. Let T ∈ R^≥⁰ and let R be the routing operator defined in (2). If the mapping f 7→ Cˆ ^p(θ, f) is sequentially weak-strong continuous from R E×I×{+,−} T to R for Pi-almost all Cˆ and for almost all θ < T, then R^T has a sequentially weakly closed graph.

Proof. Let (f (n) , r(n) ) be a sequence in the graph of R^T weakly converging to (f, r). We aim to show r ∈ R^T (f).

Claim 4. For almost every θ < T, the mappings ρv,M,i(θ, ·) : R E×I×{+,−} ^T → [0, 1] are sequentially lower-semicontinuous w.r.t. the weak topology on the domain, i.e. for every sequence f (n) converging weakly to some f it holds that lim infn→∞ ρv,M,i(θ, f(n) ) ≥ ρv,M,i(θ, f).

Proof. Let f (n) → f be a weakly convergent sequence in R E×I×{+,−} . By the lemma's assumption, we have Cˆ ^p(θ, f(n) ) → Cp(θ, f) for Pi-almost all Cˆ and all p ∈ P. Therefore, for Pi-almost all Cˆ, there exists some ⁿC^ˆ such that ^E˜ ⁱ(θ, f(m) , Cˆ) ⊆ E˜ ⁱ(θ, f, ^Cˆ) holds for all ^m ^≥ ⁿC^ˆ. This means, for every M ⊆ δ ⁺(v), n ∈ N, and m ≥ n we have

$$\mathbb{P}i({n{\hat{C}} = n \wedge \tilde{E}_i(\theta, f^{(m)}, \hat{C}) \cap \delta^+(v) \subseteq M}) \geq \mathbb{P}i({n{\hat{C}} = n \wedge \tilde{E}_i(\theta, f, \hat{C}) \cap \delta^+(v) \subseteq M}).$$

By taking the limit inferior on the left side and summing over all n ∈ N we get

$$\sum{n \in \mathbb{N}} \liminf{m \to \infty} \mathbb{P}i({n{\hat{C}} = n \, \wedge \, \tilde{E}i(\theta, f^{(m)}, \hat{C}) \cap \delta^+(v) \subseteq M }) \ge \rho{v,M,i}(\theta, f).$$

The superadditivity of the limit inferior yields our claim. ■

Fix any v ∈ V , M ⊆ δ ⁺(v) and i ∈ I. According to Lemma 4.17 we then have P ^e∈^M r (n) e,i (θ) ≥ ρv,M,i(θ, f(n) ) for all n ∈ N and almost all θ ∈ [0, T]. We aim to show that we have P ^e∈^M re,i(θ) ≥ ρv,M,i(θ, f) for almost all θ ∈ [0, T] as well.

We continue with a similar argument as in the proof of Lemma 4.4. For this, let Kⁿ denote the weak closure of the set Kⁿ := conv({r (k) | k ≥ n}). Because Kⁿ is convex, it is closed w.r.t. the norm topology. Therefore, there exists a sequence g (n) such that g (n) ∈ Kⁿ and g (n) → r (strongly) hold. After passing to a subsequence, g (n) converges almost everywhere to r (cf. [RF10, Section 7.3, Riesz-Fischer-Theorem]). As g (n) is a convex combination of the form g (n) = P m∈Iⁿ λ (n) ^m · r (m) with Iⁿ ⊆ N^≥ⁿ for each n, we can deduce

$$\sum{e \in M} r{e,i}(\theta) = \lim{n \to \infty} \sum{e \in M} g{e,i}^{(n)}(\theta) = \lim{n \to \infty} \sum{e \in M} \sum{m \in I_n} \lambdam^{(n)} \cdot r{e,i}^{(m)} = \lim{n \to \infty} \sum{m \in I_n} \lambdam^{(n)} \cdot \sum{e \in M} r_{e,i}^{(m)}$$

$$\geq \liminf{n \to \infty} \sum{m \in I_n} \lambdam^{(n)} \cdot \rho{v,M,i}(\theta, f^{(m)}) \geq \liminf{n \to \infty} \min{m \in In} \rho{v,M,i}(\theta, f^{(m)}) \stackrel{\text{Cl. 4}}{\geq} \rho_{v,M,i}(\theta, f).$$

By Lemma 4.17, this implies r ∈ R(f).

With this lemma we can now apply Theorem 3.1 or Lemma 3.4 together with Theorem 3.5 to derive existence results for stochastic prediction equilibria. For a uniqueness result, we show that if Cˆ ^p(θ, f) and Cˆ ^q(θ, f) coincide almost never for any two distinct p, q ∈ Pv,tⁱ , the probabilities πv,M,i(θ) are almost always zero for any M containing more than one edge and, hence, the resulting routing-operator is prescriptive. Thus, we can apply Corollary 4.9 (iv) once we show that r^T fulfils a Lipschitz condition (under natural assumptions on Pi).

Proposition 4.19. Assume Pi({ Cˆ ^p(θ, f) = Cˆ ^q(θ, f) }) = 0 holds for all flows f, p, q ∈ Pv,tⁱ with p ̸= q, i ∈ I, v ∈ V and for almost all θ ∈ R. Then the routing operator defined in (2) is prescriptive.

Proof. Under the given assumption, the set of active outgoing edges E˜ ⁱ(θ, f, Cˆ) has exactly one element almost surely for all i ∈ I, v ∈ V and almost all θ ∈ R. Therefore, πv,M,i(θ, f) = 0 holds whenever |M| ̸= 1 and we have re,i(θ) = πv,{e},i(θ, f) for all r ∈ R(f).

In particular, this means that R is prescriptive if for all flows f, paths p ̸= q and almost all θ, the random variable Zˆ p,q(θ, f) := Cˆ ^p(θ, f) − Cˆ ^q(θ, f) has a probability density function (p.d.f.) w.r.t. every Pⁱ , i.e. there exists a function δ with Pi({Zˆ^f p,q(θ, f) ∈ S }) = R S δ dλ for every measurable S ⊆ R.

Lemma 4.20. Let T ∈ R>⁰ and assume that there exists some B ∈ R>⁰ such that Zˆ p,q(θ, f) has a p.d.f. essentially bounded by B for all f ∈ R^E×I×{+,−} , i ∈ I, v ∈ V and p, q ∈ Pv,tⁱ with p ̸= q and almost all θ < T. Furthermore, assume that for Pi-almost all Cˆ and almost all θ ∈ [0, T], the mapping f 7→ 1[0,T] · Cˆ(θ, f) is Lipschitz continuous with common constant L from (R E×I×{+,−} T , ∥ · ∥¹ ) to R. Then, r^T is Lipschitz continuous w.r.t. the 1-norm and the p-norm on the domain and codomain, respectively.

Proof. We show Lipschitz-continuity in every coordinate of r^T . Thus, let e = vw ∈ E and i ∈ I be given. For v = tⁱ , we have r(f)e,i ≡ 0 for all f ∈ R^E×I×{+,−} . Hence, going forward, we assume v ̸= tⁱ

Claim 5. There exists L ′ > 0 such that

$$\mathbb{P}{i}\left(\left{\hat{C}{p}(\theta, f) \leq \hat{C}{q}(\theta, f)\right} \Delta \left{\hat{C}{p}(\theta, g) \leq \hat{C}{q}(\theta, g)\right}\right) \leq L' \cdot |f - g|{1}$$

holds for any f, g ∈ R^E×I×{+,−} T , p, q ∈ Pv,tⁱ and almost all θ ∈ [0, T].

Proof. The statement is trivial for p = q. By expanding the definition of the symmetric difference, the left-hand side equals

$$\mathbb{P}{i} \left( \left{ \hat{Z}{p,q}(\theta, f) \leq 0 < \hat{Z}{p,q}(\theta, g) \right} \right) \cup \left{ \hat{Z}{p,q}(\theta, f) > 0 \geq \hat{Z}_{p,q}(\theta, g) \right} \right). \tag{5}$$

We bound the probability of each of these sets separately (but analogously). Thus, assume wlog. that Zˆ p,q(θ, f) ≤ 0 < Zˆ p,q(θ, g) holds. Clearly, h 7→ Zˆ p,q(θ, h) is Lipschitz continuous with constant 2 · L. Therefore, Zˆ p,q(θ, g) − Zˆ p,q(θ, f) ≤ 2 · L · ∥f − g∥¹ and thus 0 < Zˆ p,q(θ, g) ≤ 2 · L · ∥f − g∥¹ In particular, {Zˆ p,q(θ, f) ≤ 0 < Zˆ p,q(θ, g)} ⊆ {Zˆ p,q(θ, g) ∈ [0, 2L∥f − g∥¹ } and thus, the probability of the former set is bounded by 2 · B · L · ∥f − g∥¹ . Doing this for both sets in (5), the considered probability of the claim is bound by L ′ · ∥f − g∥¹ with L ′ := 4 · B · L. ■

Claim 6. There exists L ′′ > 0 such that

$$\mathbb{P}{i}\left(\left{\,\forall q\in\mathcal{P}{v,t{i}}:\hat{C}{p}(\theta,f)\leq\hat{C}{q}(\theta,f)\,\right}\,\Delta\,\left{\,\forall q\in\mathcal{P}{v,t{i}}:\hat{C}{p}(\theta,g)\leq\hat{C}{q}(\theta,g)\,\right}\right)\leq L''\cdot\left|f-g\right|{1}$$

holds for all f, g ∈ RE×I×{+,−} T , p ∈ Pv,tⁱ and almost all θ.

Proof. Let L ′ denote the constant given by Claim 5. Because the symmetric difference of intersections ( T ^j∈^J A^j ) ∆(T ^j∈^J B^j ) is a subset of S j∈J (A^j ∆ B^j ) (for arbitrary J, A^j , B^j ), the described probability is bounded from above by

$$\sum{q \in \mathcal{P}{v,t_i}} \mathbb{P}_i \left( \left{ \left. \hat{C}_p(\theta,f) \leq \hat{C}_q(\theta,f) \right. \right} \Delta \left{ \left. \hat{C}_p(\theta,g) \leq \hat{C}q(\theta,g) \right. \right} \right) \leq \left| \mathcal{P}{v,t_i} \right| \cdot L' \cdot \left| f - g \right|_1.$$

By (the proof of) Proposition 4.19, we know πv,M,i(θ, f) = 0 for |M| ̸= 1 and therefore re,i(f)(θ) equals πv,{e},i(θ, f), i.e. the probability that {e} is the set of perceived active outgoing edges of v. This is exactly the probability that there exists a path in Pv,tⁱ starting with e that minimizes the perceived cost Cˆ p,i(θ, f) over all alternatives in Pv,tⁱ

$$r_{e,i}(f)(\theta) = \mathbb{P}i \Big( \bigcup{\substack{p \in \mathcal{P}_{v,t_i} \ p1 = e}} { \forall q \in \mathcal{P}{v,t_i} : \hat{C}_p(\theta, f) \leq \hat{C}_q(\theta, f) } \Big)$$

Now, let f, g ∈ M be arbitrary. Using the fact that |P(A) − P(B)| ≤ P(A ∆ B) holds for arbitrary A and B, Claim 6 as well as the fact that ( S ^j∈^J A^j ) ∆(S ^j∈^J B^j ) ⊆ S j∈J (A^j ∆ B^j ) holds for arbitrary J, A^j , B^j , we deduce (for almost all θ ∈ [0, T]) that

$$|r{e,i}(f)(\theta) - r{e,i}(g)(\theta)| \le \sum{\substack{p \in \mathcal{P}{v,t_i} \ p_1 = e}} L'' \cdot ||f - g||1 \le |\mathcal{P}{v,t_i}| \cdot L'' \cdot ||f - g||_1 =: L''' \cdot ||f - g||_1.$$

Clearly, this implies that

$$|\mathbf{1}{[0,T]} \cdot r{e,i}(f) - \mathbf{1}{[0,T]} \cdot r{e,i}(g)|{p} \le T \cdot L''' \cdot |f - g|{1}.$$

Theorem 4.21. Let Φ be a locally bounded edge-loading operator and Pⁱ be probability measures on cost predictors.

(i) If, for some T ∈ R≥0, Φ^T is sequentially weak-weak continuous and f 7→ Cˆ ^p(θ, f) is sequentially weak-strong continuous from R E×I×{+,−} T to R for Pi-almost all Cˆ for almost all θ < T, then there exists a stochastic prediction equilibrium until time T.
(ii) If, for all T ∈ R≥0, Φ^T is sequentially weak-weak continuous and f 7→ Cˆ ^p(θ, f) is sequentially weak-strong continuous from R E×I×{+,−} to R for Pi-almost all Cˆ for almost all θ < T, and if Φ as well as Pi-almost all Cˆ are causal, then there exists a stochastic prediction equilibrium until time ∞.
(iii) If Φ is uniformly strictly causal and essentially bounded, u ∈ L^∞ loc(R) V ×I , Cˆ is causal for Pialmost all Cˆ, there exists some B > 0 such that for every two distinct paths p, q, flow f, almost all θ, the random variable Zˆ p,q(θ, f) has a p.d.f. bounded by B (w.r.t. every Pi), and if for all T ∈ R≥⁰ there exists some L > 0 such that for Pi-almost all Cˆ, the mapping f 7→ 1[0,T] ·Cˆ(θ, f) is Lipschitz continuous with constant L w.r.t. the 1-norm on the domain R E×I×{+,−} T for almost all θ ∈ [0, T], then there exists a unique stochastic prediction equilibriumuntil ∞.

Proof. For (i)and (ii) we apply Theorem 3.1 and Theorem 3.5, respectively. In both cases, Lemma 4.18 shows that R^T has a sequentially weakly closed graph. For (iii) note that the routing operator is prescriptive (Proposition 4.19) and thus (iii) follows from Corollary 4.9 (iv) where Lemma 4.20 proves the required Lipschitz property.

We conclude by exemplarily applying the gained insights to the stochastic IDE model.

Corollary 4.22. Let Φ be a locally bounded edge-loading operator and let εe,i denote the random variables of the stochastic IDE model.

(i) If Φ^T is sequentially weak-weak continuous and f 7→ Ce(θ, f) is sequentially weak-strong continuous from R E×I×{+,−} T to R for almost all θ < T, then there exists a stochastic IDE until time T.
(ii) If Φ^T is sequentially weak-weak continuous and f 7→ Ce(θ, f) is sequentially weak-strong continuous from R E×I×{+,−} T to R for almost all θ < T for all T ∈ R^≥0, and if Φ and C^e are causal, then there exists a stochastic IDE until time ∞.
(iii) If Φ is uniformly strictly causal and essentially bounded, u ∈ L^∞ loc(R) V ×I , C^e is causal, and all εe,i are independent with bounded probability densities, and the mapping f 7→ 1[0,T] · Ce(θ, f) is Lipschitz continuous with constant L w.r.t. the 1-norm on the domain for almost all θ ∈ [0, T], then there exists a unique stochastic IDE until ∞.

Proof. Statements (i) and (ii) follow directly from Theorem 4.21 (i) and Theorem 4.21 (ii), respectively. For statement (iii), we need to show that for distinct paths p, q the random variable Zˆ p,q(θ, f) has a p.d.f. bounded by some fixed B (w.r.t. every Pi) in order to apply Theorem 4.21 (iii). However, this is the case since Zˆ p,q(θ, f) is the sum of a constant and a non-trivial linear combination of independent and random variables with bounded probability densities.

Remark 4.23. Since the prediction functions (as well as the routing operators) are often defined in terms of the cumulative flow functions (i.e. F ± e,i : θ 7→ R θ f ± e,i dλ) instead of the flow rates, it can be helpful to observe that the continuity assumption on the mapping f 7→ 1[0,T] · ce(θ, f) in Corollary 4.22 (iii) can be replaced by the following (slightly stronger) assumption: The map F 7→ ce(θ, F˙) is Lipschitz continuous from the space of absolutely continuous functions (with the uniform norm) to R for almost all θ ∈ [0, T]. This is, because for any two functions f, g ∈ L ([a, b]) we have

$$\left| \int f \, \mathrm{d}\lambda - \int g \, \mathrm{d}\lambda \right|{\infty} = \sup{\theta \in [a,b]} \left| \int_a^\theta f \, \mathrm{d}\lambda - \inta^\theta g \, \mathrm{d}\lambda \right| \leq \sup{\theta \in [a,b]} \int_a^\theta |f-g| \, \mathrm{d}\lambda \leq \int_a^b |f-g| \, \mathrm{d}\lambda = |f-g|_1$$

Similar adjustments can be made in Theorem 4.21 (iii), Corollary 4.9 (iv) and Theorem 3.14 (iii).

5. Conclusion

In this paper we introduced a general framework for the analysis of dynamic traffic assignment with adaptive route choice that incorporates both the well-known descriptive behavioural models stemming from game-theoretic perspectives, such as the (full-information) Nash equilibrium and the dynamic prediction equilibrium models, as well as prescriptive models including those that assume a logit-based route choice. We showed that, under certain continuity assumptions on the edge-loading and routing operators, a coherent flow exists up to any finite time horizon and, under the additional assumption of causality, it exists on the whole R. Moreover, we can guarantee uniqueness of the coherent flow if the operators are uniformly strictly causal or fulfil a Lipschitz-condition.

Since our framework uses abstract edge-loading and routing operators, that can be instantiated with various models from the literature, our results generalize established findings including the existence of dynamic Nash flows, dynamic prediction equilibria, and the existence and uniqueness of coherent flows with prescriptive routing operators. The logit-based operators of the latter model class are motivated by stochastic noise in the predictions of the perceived travel times that may vary from user to user. We modeled these stochastic effects descriptively as what we call the stochastic prediction equilibrium and showed that such an equilibrium exists under mild assumptions on the continuity of the prediction functions. If we assume that the distribution of the noise has a bounded probability density function, then stochastic prediction equilibria are even unique.

Open Questions. Concerning the special case of stochastic IDE it is not hard to see that if the distribution of the measurement errors is supported on a small interval around zero, then the resulting stochastic IDE is also an ε-approximate IDE in the sense of [GHKM23]. Hence, a natural question to ask is whether a sequence of such stochastic IDE converges to an exact IDE if the support of the measurement error distribution shrinks to zero. If this is the case and we are in a model with unique stochastic IDE, then this limit point would, in some sense, be a canonical choice within the set of IDE for a given instance. Furthermore, our existence result for stochastic IDE even provides a natural way of (numerically) computing such equilibria, as the Banach Fixed Point theorem used for the extension step also guarantees that the standard fixed point iteration converges to a fixed point.

Finally, even though our framework is already quite general, there are still certain, more complex phenomena in traffic assignment for which it is not clear upfront whether they can be incorporated in our model. One such aspect would be spillback effects, where congestion on one road section leads to congestion on a previous road section (see, e.g., [SV18]). Other potential extensions would be allowing departure time choice or elastic demand scenarios.

Acknowledgements. We thank Julian Schwarz and Alexander Keimer for helpful discussions on the topics of this paper.

References

[AB06a] Charalambos D. Aliprantis and Kim C. Border. Infinite Dimensional Analysis. A Hitchhiker's Guide. 3rd ed. Springer Berlin, Heidelberg, 2006. doi: 10.1007/3-540-29587-9.
[AB06b] Charalambos D. Aliprantis and Owen Burkinshaw. Positive Operators. Springer Netherlands, 2006. isbn: 9781402050084. doi: 10.1007/978-1-4020-5008-4.
[BC06] J.-B. Baillon and R. Cominetti. "Markovian traffic equilibrium". In: Mathematical Programming 111.1–2 (Dec. 2006), pp. 33–56. issn: 1436-4646. doi: 10.1007/s10107-006- 0076-2.
[BKPS19] Alexandre Bayen, Alexander Keimer, Emily Porter and Michele Spinola. "Time-Continuous Instantaneous and Past Memory Routing on Traffic Networks: A Mathematical Analysis on the Basis of the Link-Delay Model". In: SIAM Journal on Applied Dynamical Systems 18.4 (Jan. 2019), pp. 2143–2180. issn: 1536-0040. doi: 10.1137/19m1258980.
[CCL15] Roberto Cominetti, José Correa and Omar Larré. "Dynamic Equilibria in Fluid Queueing Networks". In: Operations Research 63.1 (2015), pp. 21–34. doi: 10.1287/opre.2015. 1348.
[CCO22] José Correa, Andrés Cristi and Tim Oosterwijk. "On the Price of Anarchy for Flows over Time". In: Math. Oper. Res. 47.2 (2022), pp. 1394–1411.
[CW16] Giulio E. Cantarella and David P. Watling. "A general stochastic process for day-to-day dynamic traffic assignment: Formulation, asymptotic behaviour, and stability analysis". In: Transportation Research Part B: Methodological 92 (2016). Special issue Day-to-Day Dynamics in Transportation Networks, pp. 3–21. issn: 0191-2615. doi: 10.1016/ j.trb.2016.05.005. url: https://www.sciencedirect.com/science/article/pii/ S0191261516302776.
[DS77] Carlos F. Daganzo and Yosef Sheffi. "On Stochastic Models of Traffic Assignment". In: Transportation Science 11.3 (Aug. 1977), pp. 253–274. issn: 1526-5447. doi: 10.1287/ trsc.11.3.253.
[FF62] L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
[FH19] Terry L. Friesz and Ke Han. "The mathematical foundations of dynamic user equilibrium". In: Transportation Research Part B: Methodological 126 (Aug. 2019), pp. 309– 328. issn: 0191-2615. doi: 10.1016/j.trb.2018.08.015.
[GH23a] Lukas Graf and Tobias Harks. "A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows". In: Mathematical Programming 197 (1st Feb. 2023), pp. 761– 792. doi: 10.1007/s10107- 022- 01772- 0. Also available on arXiv: https://arxiv. org/abs/2007.07808v3.
[GH23b] Lukas Graf and Tobias Harks. "The Price of Anarchy for Instantaneous Dynamic Equilibria". In: Mathematics of Operations Research 48.4 (2023), pp. 2167–2195. doi: 10. 1287/moor.2022.1336.
[GH24] Lukas Graf and Tobias Harks. "Side-Constrained Dynamic Traffic Equilibria". In: Operations Research 0.0 (2024), null. doi: 10.1287/opre.2023.0577.
[GHKM23] Lukas Graf, Tobias Harks, Kostas Kollias and Michael Markl. "Prediction Equilibrium for Dynamic Network Flows". In: Journal of Machine Learning Research 24.310 (2023), pp. 1–33. url: http://jmlr.org/papers/v24/22-1446.html.
[GHS20] Lukas Graf, Tobias Harks and Leon Sering. "Dynamic flows with adaptive route choice". In: Mathematical Programming 183 (2020), pp. 309–335. doi: 10.1007/s10107-020- 01504-2. Also available on arXiv https://arxiv.org/abs/1811.07381v4.
[Gra24] Lukas Graf. Dynamic Network Flows with Adaptive Route Choice based on Current Information. Mathematische Optimierung und Wirtschaftsmathematik | Mathematical Optimization and Economathematics. Springer Spektrum Wiesbaden, 2024. doi: 10. 1007/978-3-658-44948-3.
[Han03] Sangjin Han. "Dynamic traffic modelling and dynamic stochastic user equilibrium assignment for general road networks". In: Transportation Research Part B: Methodological 37.3 (2003), pp. 225–249. issn: 0191-2615. doi: 10.1016/S0191-2615(02)00009-7. url: https://www.sciencedirect.com/science/article/pii/S0191261502000097.
[HFY13] Ke Han, Terry L. Friesz and Tao Yao. "Existence of simultaneous route and departure choice dynamic user equilibrium". In: Transportation Research Part B: Methodological 53 (July 2013), pp. 17–30. doi: 10.1016/j.trb.2013.01.009.
[Hun13] Dirk Hundertmark. Lecture Notes Functional Analysis WS 2012/2013. Feb. 2013. url: https://www.math.kit.edu/iana1/lehre/funcana2012w/media/fa-lecturenotes. pdf.
[JL21] Weiwei Jiang and Jiayun Luo. "Graph Neural Network for Traffic Forecasting: A Survey". In: CoRR abs/2101.11174 (2021). arXiv: 2101.11174. url: https://arxiv.org/abs/ 2101.11174.
[Kai22] Marcus Kaiser. "Computation of Dynamic Equilibria in Series-Parallel Networks". In: Mathematics of Operations Research 47.1 (2022), pp. 50–71. doi: 10.1287/moor.2020. 1108.
[KB20] Alexander Keimer and Alexandre Bayen. "Routing on Traffic Networks Incorporating Past Memory up to Real-Time Information on the Network State". In: Annual Review of Control, Robotics, and Autonomous Systems 3.1 (May 2020), pp. 151–172. issn: 2573- 5144. doi: 10.1146/annurev-control-091319-125444.
[Kle20] Achim Klenke. Probability Theory: A Comprehensive Course. Springer International Publishing, 2020. isbn: 9783030564025. doi: 10.1007/978-3-030-56402-5.
[Kre89] Erwin Kreyszig. Introductory functional analysis with applications. Wiley classics library ed. Wiley classics library. New York [u.a.]: Wiley, 1989. 688 pp. isbn: 0471507318.
[KS11] Roland Koch and Martin Skutella. "Nash Equilibria and the Price of Anarchy for Flows over Time". In: Theory of Computing Systems 49 (2011), pp. 71–97. doi: 10 . 1007 / s00224-010-9299-y.
[PCHR24] Ricardo de la Paz Guala, Cristián E. Cortés, Benjamin G Heydecker and Pablo Rey. "A Markovian approach for stochastic dynamic traffic assignment". In: SSRN Electronic Journal (2024). issn: 1556-5068. doi: 10.2139/ssrn.4680654.
[RF10] Halsey Royden and Patrick Fitzpatrick. Real Analysis. Fourth Edition. Prentice Hall, 2010, p. 614. isbn: 9780131437470.
[Sch73] Morton Schneider. "Probability maximization in networks". In: Proceedings of the International Conference on Transportation Research. 1. 1973. doi: 10.22004/AG.ECON. 318285.
[Sha+22] Maryam Shaygan, Collin Meese, Wanxin Li, Xiaoliang (George) Zhao and Mark Nejad. "Traffic prediction using artificial intelligence: Review of recent advances and emerging opportunities". In: Transportation Research Part C: Emerging Technologies 145 (2022), p. 103921. issn: 0968-090X. doi: 10.1016/j.trc.2022.103921. url: https://www. sciencedirect.com/science/article/pii/S0968090X22003345.
[SJS11] W.Y. Szeto, Y. Jiang and A. Sumalee. "A Cell-Based Model for Multi-class Doubly Stochastic Dynamic Traffic Assignment: A cell-based model for multi-class doubly stochastic DTA". In: Computer-Aided Civil and Infrastructure Engineering 26.8 (Mar. 2011), pp. 595– 611. issn: 1093-9687. doi: 10.1111/j.1467-8667.2011.00717.x.
[Sku08] Martin Skutella. "An Introduction to Network Flows over Time". In: Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany. 2008, pp. 451–482.
[SP82] Yosef Sheffi and Warren B. Powell. "An algorithm for the equilibrium assignment problem with random link times". In: Networks 12.2 (June 1982), pp. 191–207. issn: 1097- 0037. doi: 10.1002/net.3230120209.
[SV18] Leon Sering and Laura Vargas Koch. "Nash Flows over Time with Spillback". In: CoRR abs/1807.05862 (2018). arXiv: 1807.05862. url: http://arxiv.org/abs/1807.05862.
[Vel+18] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò and Yoshua Bengio. "Graph Attention Networks". In: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. 2018. url: https://openreview.net/forum?id=rJXMpikCZ.
[Vic69] William S. Vickrey. "Congestion Theory and Transport Investment". In: The American Economic Review 59.2 (1969), pp. 251–260. issn: 00028282. url: http://www.jstor. org/stable/1823678.
[War52] John Glen Wardrop. "Some Theoretical Aspects of Road Traffic Research". In: Proceedings of the Institution of Civil Engineers 1.3 (1952), pp. 325–362. doi: 10.1680/ipeds. 1952.11259.
[YYZ18] Bing Yu, Haoteng Yin and Zhanxing Zhu. "Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting". In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden. 2018, pp. 3634–3640.
[ZFWQ20] Chuanpan Zheng, Xiaoliang Fan, Cheng Wang and Jianzhong Qi. "GMAN: A Graph Multi-Attention Network for Traffic Prediction". In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020. 2020, pp. 1234–1241. url: https://aaai. org /ojs/index.php/AAAI/ article/view/5477.
[ZM00] Daoli Zhu and Patrice Marcotte. "On the Existence of Solutions to the Dynamic User Equilibrium Problem". In: Transportation Science 34.4 (2000), pp. 402–414.

A. Some Technical Results from Topology

Proposition A.1. Let X be a reflexive, separable Banach space over R. Let K ⊆ X be a norm bounded subset, i.e. there is some B ∈ R with ∥x∥ ≤ B for all x ∈ K. Then, K is weakly metrizable, i.e. the subspace topology on K induced by the weak topology on X is metrizable. In particular:

(i) A set K′ ⊆ K is weakly closed in K if and only if it is sequentially weakly closed in K.
(ii) If K is closed, then K′ ⊆ K is weakly closed in X if and only if it is sequentially weakly closed in X.

Proof. Clearly, as X is reflexive, its continuous dual X′ is reflexive as well. As the dual of X′ is the separable space X, X′ is also separable (cf. [Kre89, Theorem 4.6-8]). Therefore, the closed unit ball U1(0) in X is weakly metrizable (cf. [AB06a, Theorem 6.31], [AB06b, Theorem 3.35]). Then, the closed ball around 0 ∈ X with radius B is also weakly metrizable (by scaling the arguments of the metric with 1/B). Restricting this metric to K gives the desired metric.

For statement (i), see [AB06a, Lemma 3.3]; (ii) follows directly from (i).

Proposition A.2. Let E ⊆ R be a measurable set, d ∈ N and 1 < p < ∞. Then:

(i) The Banach space (L p (E) d , ∥·∥) is reflexive and separable.
(ii) The continuous dual space of L p (E) d is L q (E) ^d with 1/p + 1/q = 1.
(iii) The weak topology of L p (E) d is the d-wise product topology of the weak topology of L p (E), and thus a locally convex Hausdorff space.

Proof. As we assume 1 < p < ∞, the continuous dual of the space L p (E) is indeed L q (E) (cf. [AB06a, Theorem 13.26]) and, thus, L p (E) is reflexive and separable (cf. [RF10, Chapter 7, Theorem 11]).

A finite product of separable spaces is again separable. Moreover, the continuous dual space of a finite product of Banach spaces is the product of the continuous dual spaces.

B. Vickrey Queuing and Affine-Linear Volume-Delay Dynamics

Two widely used physical models are the Vickrey queueing model and the affine-linear volume delays. For the convenience of the reader we provide here their formal definitions and collect some of their important properties.

B.1. Vickrey's Queuing Model

A physical model that has been proposed by Vickrey [Vic69] is the Vickrey queuing model, sometimes also called the deterministic fluid queuing model. In this model, every edge e ∈ E is assigned a capacity ν^e ∈ R>⁰ as well as a free-flow travel time c ^e ∈ R^≥0. Whenever the inflow into an edge exceeds the capacity, a point queue builds up in front of the edge. Particles entering an edge must first wait in this queue before they can traverse the edge which then takes another c 0 e time units.

More formally, for a flow f, the queue length z^e at edge e is defined as

$$z_e(\theta, f) := \int_0^\theta f_e^+ \, \mathrm{d}\lambda - \int_0^{\theta + c_e^0} f_e^- \, \mathrm{d}\lambda,$$

where f + e := P i∈I f + e,i and f − e := P i∈I f e,i denote the aggregate inflow rate. The travel time for a particle entering at time θ is then given by

$$c_e(\theta, f) \coloneqq \frac{z_e(\theta, f)}{\nu_e} + c_e^0,$$

and its exit time is τe(θ, f) := θ + ce(θ, f).

A flow f is called a Vickrey flow until time T if it fulfils the following two conditions: First, its queue operates at capacity until T, i.e. for almost all θ < T we have

$$f_e^-(\theta + c_e^0) = \begin{cases} \nu_e, & \text{if } z_e(\theta, f) > 0, \ \min{f_e^+(\theta), \nu_e}, & \text{otherwise.} \end{cases}$$

Second, its queue operates fairly until T, i.e. for almost all θ < T we have

$$f_{e,i}^-(\theta) = \begin{cases} f_e^-(\theta + ce^0) \cdot \frac{f{e,i}^+(\xi_\theta)}{fe^+(\xi\theta)}, & \text{if } fe^+(\xi\theta) > 0, \ 0, & \text{otherwise,} \end{cases}$$

where ξ^θ is chosen such that ξ^θ + ce(ξθ) = θ + c e

It is a well-known result that for any given set of edge inflow rates f ⁺ ∈ R^E×^I there exists a unique set of outflow rates f ⁻ ∈ R^E×^I such that (f ⁺, f ⁻) is a Vickrey flow, and moreover, this mapping is causal (cf. [Gra24, Corollaries 3.43 and 3.46]):

Lemma B.1. For any inflow rates vector f ⁺ ∈ R^E×^I , there exists a unique vector f ⁻ ∈ R^E×^I such that (f ⁺, f ⁻) is a Vickrey flow. Let Φ denote the resulting mapping from edge inflow to edge ourflow rates. Then, Φ is always causal and, if all free-flow travel times are strictly positive, even uniformly strictly causal.

Clearly, due to the capacity constraints, Φ is also locally bounded. Moreover, it is a well-known result that Φ^T is sequentially weak-weak continuous for every T ∈ R^≥⁰ even if we allow c 0 ^e = 0.

Lemma B.2 ([Gra24, Corollaries 3.45, 3.46]). For the edge loading operator Φ of Vickrey's model, Φ^T is sequentially weak-weak continuous. Furthermore, the induced travel time function f 7→ ce(· , f) is sequentially weak-strong continuous from R E×I×{+,−} T to C([0, T], R^≥0) for arbitrary T ∈ R^≥0.

B.2. Affine-Linear Volume-Delay Dynamics

A closely related and also frequently used physical model is that of affine-linear volume-based edge dynamics. This model is studied in more detail, e.g., by Zhu and Marcotte [ZM00] and also used by Bayen et al. [BKPS19]. Here, the travel time on a link depends affine-linearly on the flow volume on the edge at the time the edge is entered.

More specifically, for each edge e ∈ E, we are given a positive free-flow travel time c ^e and a positive capacity νe. The travel time on e at time θ is then given by

$$c_e(\theta, f) := c_e^0 + \frac{X_e(\theta, f)}{\nu_e},\tag{6}$$

where Xe(θ, f) := R θ f + ^e dλ − R θ f − ^e dλ is the flow volume on edge e at time θ.

We say that a flow f respects travel times (ce)^e until T if R ^θ f + e,i dλ = R ^τe(θ,f) f − e,i dλ holds for all θ < T with τe(θ, f) := θ + ce(θ, f). Note that for a flow f that respects travel times induced by an affine-linear volume-delay function, the exit time functions τ^e are strictly increasing with τe(θ, f) ≥ θ + c ^e and therefore their inverse functions (τe(· , f))⁻¹ exist and both τe(· , f) and (τe(· , f))⁻¹ are differentiable almost everywhere with positive derivative. The fact that f respects travel times is equivalent to f + e,i(θ) = f e,i(τe(θ, f)) · (τe(· , f))′ (θ) for almost all θ. Thus, if τe(· , f) is strictly increasing, this can be equivalently formulated as

$$f{e,i}^{-}(\theta) = \frac{f{e,i}^{+}(\tau{e}(\,\cdot\,,f)^{-1}(\theta))}{\tau{e}(\,\cdot\,,f)'(\tau{e}(\,\cdot\,,f)^{-1}(\theta))} = f{e,i}^{+}(\tau{e}(\,\cdot\,,f)^{-1}(\theta)) \cdot (\tau{e}(\,\cdot\,,f)^{-1})'(\theta)$$

Therefore, given some edge inflow rate vector f ⁺ ∈ R^E×^I , the set of outflow rate vectors f ⁻ ∈ R^E×^I such that f = (f ⁺, f ⁻) respects these travel times correspond one-to-one to the function vectors (Xe,i)e,i : R → R E×I for which τe[X] : θ 7→ θ + c ^e + νe · P ⁱ∈^I Xe,i(θ) is strictly increasing with τeX > θ and which solve the following system of delay differential equations (DDE):

$$X'{e,i}(\theta) = f^{+}{e,i}(\theta) - f^{-}_{e,i}X$$

$$f^{-}{e,i}X := f^{+}{e,i}(\tau{e}[X]^{-1}(\theta)) \cdot (\tau{e}[X]^{-1})'(\theta)$$

$$X_{e,i}(0) = 0$$

This system of DDE can be solved in a stepwise fashion (as was done by [BKPS19, Theorem 2.9], and [ZM00, Theorem 2.2]) which yields in the following theorem.

Theorem B.3. Let νe, c⁰ ^e ∈ R>⁰ for all e ∈ E. For each inflow edge inflow rate vector f ⁺ ∈ R^E×^I , there exists a unique outflow rate vector f ⁻ ∈ R^E×^I such that the flow (f ⁺, f ⁻) respects the travel times (c)^e from (6). Hence, the physical model Φ that maps inflow rates to such outflow rates is well-defined.

By thoroughly analysing the proof of Theorem B.3, we can extract the following uniqueness property:

Proposition B.4. Let νe, c⁰ ^e ∈ R>⁰ for all e ∈ E. Let fe, · = (f + e, · , f ⁻ e, · ) and ge, · = (g + e, · , g⁻ e, · ) be two vectors in R^I×{+,−} with Xe,i(θ, h) ≥ 0 for all θ ∈ R, i ∈ I, h ∈ {f, g}. Assume that f + e, · and g + e, · coincide until T. We write T h := min { θ | τe(θ, h) = T }, and assume that fe, · and ge, · respect the travel times in (6) until T ′ f and until T ′ g , respectively. Then T ′ ^f = T ′ ^g holds, and f e, · and g e, · coincide until T.

In particular, Φ is uniformly strictly causal.

We continue by showing that Φ^T is sequentially weak-weak continuous. Note that a similar continuity result was presented in [ZM00, Theorem 3.2] where the edge inflow rates are assumed to be essentially bounded and instead of weak convergence, a convergence in an integral sense is used.

Theorem B.5. Let Φ denote the edge loading operator induced by a set of affine-linear volumedelay functions. Then, Φ^T is sequentially weak-weak continuous for every T ∈ R^≥0. Furthermore, f 7→ ce(· , f) is sequentially weak-strong continuous from R E×I×{+,−} T to C([0, T], R^≥0).

Proof. We show the sequential weak-weak continuity for (f + e, · ) 7→ (Φ^T (f ⁺))e, · for each edge e ∈ E separately. To reduce noise, we will omit the edge index e for all relevant functions and constants.

Let (f n,+)ⁿ be a sequence of vectors in R^I T that converges weakly to f ⁺. We show that f n,⁻ := Φ^T (f n,+) converges weakly to f ⁻ := Φ^T (f ⁺). For that, note that f n,⁻ are contained in the weakly compact set { g ∈ R^I T | gⁱ ≤ ν^e }. Thus, the sequence f n,⁻ has a weakly convergent subsequence, and we pass to this subsequence with weak limit f ^∗.⁻.

Because the operator J : L p ([0, T]) → C([0, T]), f 7→ (θ 7→ R θ 0 f dλ) is compact, the cumulative flow rate functions F n,+ i : θ 7→ R θ 0 f n,+ i dλ and F n,− i : θ 7→ R θ 0 f n,− i dλ converge uniformly as functions in C(R). Therefore, also the sequence of edge volume functions Xi(· , f ⁿ) and the sequence of travel time functions c(· , f ⁿ) and exit time functions τ (· , f ⁿ) converge uniformly to X(· , f ^∗ ), c(· , f ^∗ ) and τ (· , f ^∗ ), respectively, in C(R) where f ⁿ := (f n,⁺, f n,⁻) and f ∗ := (f ⁺, f ^∗,⁻). Thus, the composition F n,⁻ ◦ τ (· , f ⁿ) converges pointwise to F ^∗,⁻ ◦ τ (· , f ^∗ ) and f ∗

Note that the function τ (· , f ⁿ) coincides with τ (· ,((f n,⁺, Φ(f n,⁺)))) on (−∞, T]. Therefore, τ (· , f ⁿ) is bijective and f n i respects travel times until τ (· , f ⁿ) −1 (T). Let T ′ := min { θ | τ (θ, f ^∗ ) = T } (which exists as Xi(· , f ^∗ ) are non-negative), and let θ < T′ . Then, for large enough n, we have τ (θ, f ⁿ) < T, and we can deduce F +,n i (θ) = F −,n i (τ (θ, f ⁿ)). In the limit, this shows that f ∗ respects travel times until T ′ . From Proposition B.4 it follows that f ^∗,⁻ and f ⁻ must coincide on [0, T].

C. Comments on [BKPS19, Lemma 3.3]

As mentioned in Section 3.2, we briefly discuss counterexamples for the statement in [BKPS19, Lemma 3.3] which serves the authors as a building block for their uniqueness and existence proof of coherent flows with Lipschitz-continuous, prescriptive routing operators (see [BKPS19, Proof of Theorem 3.4]). The lemma is stated as follows:

Lemma C.1 ([BKPS19, Lemma 3.3]). Let n ∈ N, L, T ∈ R>0, and Ω ⊆ C([0, T], R ⁿ) closed in the induced topology be given. Let Ψ : Ω → Ω be a Lipschitz-continuous self-mapping for which there exists some α > 0 such that for all t ∈ [0, T] and x, x˜ ∈ Ω we have

$$|\Psi(x)|{[0,t]} - \Psi(\tilde{x})|{[0,t]}| \le L \cdot t^{\alpha} \cdot |x|{[0,t]} - \tilde{x}|{[0,t]}|.$$

Then, there exists a unique fixed-point x ^∗ ∈ Ω of Ψ.

However, the assumptions of this lemma neither guarantee existence of a fixed point nor their uniqueness.

Counterexample for existence. We consider the following counterexample: We define n := 1, Ω := C([0, 1], R≥0), and Ψ as the mapping

$$\Psi: \Omega \to \Omega, \ x \mapsto (t \mapsto t \cdot x(t) + 1).$$

Then, Ω is closed in C([0, 1], R) and Ψ is a Lipschitz-continuous self-mapping with Lipschitz-constant 1. Moreover, for any t ∈ [0, 1], x, x˜ ∈ Ω we have

$$\left| \left. \Psi(x) \right|{[0,t]} - \left. \Psi(\tilde{x}) \right|{[0,t]} \right| = \sup{t' \in [0,t]} |t' \cdot (x(t') - \tilde{x}(t'))| \leq t \cdot \left| \left. x \right|{[0,t]} - \left. \tilde{x} \right|_{[0,t]} \right|.$$

Hence, choosing L := α := 1, Ψ fulfils the assumptions of the lemma.

Now, assume that x ∗ is a fixed point of Ψ. Then, for all t ∈ [0, 1] we must have x ∗ (t) = t· x ∗ (t) + 1, which implies 0 = 1 for t = 1, a contradiction. Thus Ψ does not have any fixed point.

Counterexample for uniqueness. Again, we define n := 1, Ω := C([0, 1], R^≥0). Here, Ψ is the mapping

$$\Psi:\Omega\to\Omega,\ x\mapsto t\mapsto \begin{cases} 0, & \text{if } t<\frac{1}{2},\ \min{t-\frac{1}{2},x(t)}, & \text{if } t\geq\frac{1}{2}. \end{cases}$$

Clearly, Ω is closed in C([0, 1], R) and Ψ is a Lipschitz-continuous self-mapping with Lipschitzconstant 1. Furthermore, for t ∈ [0, 1 2 ], x, x˜ ∈ Ω we have ∥Ψ(x)| [0,t] − Ψ(˜x)| [0,t] ∥ = 0 and for t ∈ ( , 1] we have

$$\begin{split} \left| \left. \Psi(x) \right|{[0,t]} - \left. \Psi(\tilde{x}) \right|{[0,t]} \right| &= \sup{t' \in [\frac{1}{2},t]} \left| \min{t' - \frac{1}{2}, x(t')} - \min{t' - \frac{1}{2}, \tilde{x}(t')} \right| \ &\leq \left| \left. x \right|{[0,t]} - \left. \tilde{x} \right|{[0,t]} \right| \leq 2 \cdot t^1 \cdot \left| \left. x \right|{[0,t]} - \left. \tilde{x} \right|_{[0,t]} \right|. \end{split}$$

Choosing L := 2 and α := 1, Ψ again fulfils the assumptions of the lemma. However, for every λ ∈ [0, 1], the function x ∗ (t) := λ · 1 1 ,1 · (t − ) is a fixed point of Ψ.

Comment. As we have seen, the assumptions of the lemma do not guarantee existence nor uniqueness of a fixed point of Ψ : Ω → Ω. However, since the continuity assumption on Ψ implies that it is causal, i.e. for all x, x˜ ∈ Ω and t ∈ [0, T] we have that x| [0,t] = ˜x| [0,t] implies Ψ(x)| [0,t] = Ψ(˜x)| [0,t] we can "restrict" Ψ to functions defined on smaller subintervals [0, T′ ] ⊆ [0, T]. Then, one can show that this restriction Ψ′ is guaranteed to have a unique fixed point for small enough intervals [0, T′ More specifically, for any T ′ < ( 1 L ) ¹/α, we define Ψ′ as the mapping

$$\Psi': \Omega|{[0,T']} \to \Omega|{[0,T']}, f \mapsto \Psi(\tilde{f})\Big|_{[0,T']}$$

where Ω| [0,T′ := {f| [0,T′ | f ∈ Ω} and ˜f is any extension of f in Ω (by causality, the exact choice of ˜f does not matter). Then, Ψ′ has a unique fixed point in Ω| [0,T′ by the Banach Fixed-Point Theorem, as (by the assumptions of the lemma and the choice of ′ ) Ψ′ is a contraction with contraction constant L · T ′^α < 1. 4

Bayen et al. [BKPS19] also used this observation in the first (correct) part of their proof of Lemma C.1. However, they then (incorrectly) claim that this step may be applied iteratively in order to "extend" the fixed point of Ψ′ to a fixed point of Ψ. Hence, under the assumptions of this lemma its conclusion only holds for restrictions of Ψ to small enough intervals.

Nevertheless, as we show here in Lemma 3.13, this weaker version of Lemma C.1 still suffices to show the unique extension property as well as the extension existence property and, hence, the unique existence of coherent flows. Thus, the conclusion Bayen et al. draw from Lemma C.1 (namely [BKPS19, Theorem 3.4]) remains true (with some adjustments of the proof).

⁴For example, for the Ψ defined in the existence-counterexample, the unique fixed point of Ψ′ (for any T ′ < 1) is given by x ^∗(t) = 1/(1 − t).

D. List of Symbols

Symbol	Description
1J	the indicator function of a set J ⊆ R
1v̸=t i	equal to 1 if v ̸= ti and to 0 otherwise
p loc(R) L	set of locally p-integrable functions on R (with 1 < p < ∞)
(R) p L	set of p-integrable functions on R (with 1 < p < ∞)
∥f∥p	p-norm of f (with 1 ≤ p < ∞)
R f dλ J	integral of f over J ⊆ R with respect to the Lebesgue measure λ
T	a time horizon T ∈ R∞ ≥0 = R≥0 ∪ { ∞ }
R	set of rate functions, i.e. the set of all non-negative, locally p-integrable p loc(R) with (essential) support in R≥0 functions in L
RT	subset of rate functions with (essential) support in [0, T]
G = (V, E)	directed graph with node set V and edge set E
+(v) δ	set of edges leaving node v
−(v) δ	set of edges towards node v
Pv,w	set of simple v, w-paths
I	finite set of commodities
uv,i	network inflow rate of commodity i at node v
e,i, f − + f = (f e,i)	+ − dynamic flow consisting of edge inflow rates f e,i and edge outflow rates f e,i for every edge e ∈ E and every commodity i ∈ I
Φ	an edge loading operator mapping a vector of edge inflow rates to a vector of edge outflow rates
ΦT	the restricted edge loading operator (cf. Notation 2.4)
R	a routing operator mapping flows to sets of allowed flow splits
RT	the restricted routing operator (cf. Notation 2.9)
+ +) Ω T ,α(f	+ of a flow with time horizon set of possible extensions of the inflow rates f T on the interval [T, T + α]
ΩT ,α(f)	set of possible extensions of a flow f with time horizon T on the interval [T, T + α]
Cˆ i,p	predicted cost of entering path p when entering at time θ under flow f
Eˆ i(θ, f)	active edges of commodity i at time θ under flow f
Θˆ e,i(f)	times at which edge e is active for commodity i under flow f
ce(θ, f)	travel time induced by flow f on edge e when entering at time θ
τe(θ, f)	exit time from edge e when entering at time θ under flow f
Pi	probability measure over prediction functions for commodity i
E˜ i(θ, f, Cˆ)	set of percieved active edges at time θ w.r.t. flow f and predictor Cˆ

grafstochasticpredictionequilibriumdynamic2024.md 137 KB

Histórico Raw

status: converted

Stochastic Prediction Equilibrium for Dynamic Traffic Assignment

Contents

1. Introduction

1.1. Our Contribution

1.2. Related Work

2. Model

2.1. Physical Flow Model

2.2. Behavioural model

3. Existence and Uniqueness

3.1. Existence

Claim 3. Γ has a weakly closed graph.

3.2. Uniqueness

4. Stochastic Prediction Equilibrium

4.1. Deterministic Prediction Equilibrium

4.2. Prescriptive Routing Operators

4.3. Noisy Predictions

5. Conclusion

References

A. Some Technical Results from Topology

B. Vickrey Queuing and Affine-Linear Volume-Delay Dynamics

B.1. Vickrey's Queuing Model

B.2. Affine-Linear Volume-Delay Dynamics

C. Comments on [BKPS19, Lemma 3.3]

D. List of Symbols

grafstochasticpredictionequilibriumdynamic2024.md 137 KB Histórico Raw

status: converted

Stochastic Prediction Equilibrium for Dynamic Traffic Assignment

Contents

1. Introduction

1.1. Our Contribution

1.2. Related Work

2. Model

2.1. Physical Flow Model

2.2. Behavioural model

3. Existence and Uniqueness

3.1. Existence

Claim 3. Γ has a weakly closed graph.

3.2. Uniqueness

4. Stochastic Prediction Equilibrium

4.1. Deterministic Prediction Equilibrium

4.2. Prescriptive Routing Operators

4.3. Noisy Predictions

5. Conclusion

References

A. Some Technical Results from Topology

B. Vickrey Queuing and Affine-Linear Volume-Delay Dynamics

B.1. Vickrey's Queuing Model

B.2. Affine-Linear Volume-Delay Dynamics

C. Comments on [BKPS19, Lemma 3.3]

D. List of Symbols

grafstochasticpredictionequilibriumdynamic2024.md 137 KB

Histórico Raw