The Impact of Spillback on the Price of Anarchy for Flows over Time

Abstract

Flows over time enable a mathematical modeling of traffic that changes as time progresses. In order to evaluate these dynamic flows from a game theoretical perspective we consider the price of anarchy (PoA). In this paper we study the impact of spillback effects on the PoA, which turn out to be substantial. It is known that, in general, the PoA is unbounded in the spillback setting. We extend this by showing that it is still unbounded even when considering networks with unit edge capacities and that the Braess ratio can be arbitrarily large.

In contrast to that, we show that on a fixed network the PoA as a function of the flow amount is bounded by a constant and also upper bound the PoA for the set of networks where the outflow capacities satisfy certain constraints depending on the quickest flow. This upper bound only depends on the worst spillback factor of the Nash flows over time of the given network. It therefore provides a way to quantify the impact of spillback to the quality of the dynamic equilibria.

In addition, we show the surprising fact that the introduction of spillback behavior can actually speed up dynamic equilibria in some networks.

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Grant BR 4744/2-1 and Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

Related Version: A full version of this paper including all proofs is available at https://arxiv.org/abs/2007.04218.

1 Introduction

Road traffic is an integral part of modern societies, which consists of many users with individual behaviors and goals. For this reason traffic dynamics are very hard to predict and can barely be controlled. However, through recent technologies such as intelligent navigation systems it might be possible to positively affect the behavior of traffic, steering it towards shorter travel times leading to less pollution and an overall improved quality of life.

In the following research work we focus on a mathematical traffic flow model called flows over time with spillback. Here, the network is depicted as a graph with a source and a sink, and the traffic flow can progress in continuous time from one vertex over an edge to the next vertex. We consider flow as a continuous stream affected by two types of temporal factors. First, flow does not travel instantaneously through the network but needs actual time to traverse an edge, and second, flow on an edge may change over time. Compared to static network flows these temporal components enable us to model traffic realistically through different congestion levels. To model road constraints within the network, we equip each edge with an inflow and an outflow capacity governing with which rate flow can enter and leave the edge, a length characterizing the time it takes a flow-particle to travel from the tail to the head of the edge, and finally, a storage capacity which describes how much flow volume fits on the edge. If the desired outflow exceeds the outflow capacity of an edge the excess flow queues up in front of the bottle-neck at the head of the edge. If at any point in time the queue of an edge is so large that the amount of flow traversing the edge plus the amount of flow in the queue equals the storage capacity, the edge is considered full and new flow can only enter if at least as much flow leaves at the same time. With this mechanic it is possible to model spillback, i.e., the phenomenon that traffic congestion at one street can block exits or intersections further upstream. The ability to model spillback within the framework of flows over time is a very recent discovery  [22], which has not been studied much yet.

As we experience in our everyday lives traffic is not performing optimal most of the time, but rather consists of agents that behave egoistically. Thus, we are interested in game theoretic aspects of this flow model, particularly in the price of anarchy (PoA), the ratio of the worst uncoordinated behavior described via a dynamic equilibrium, and the optimal flow behavior measured by some social cost function. In real-world scenarios that ratio could give us an idea of how much one can possibly improve traffic through optimized traffic control, for example through modern navigation systems or autonomous driving. Even though it has been shown in  [22] that the PoA in networks with spillback is unbounded in general we investigate the dependency of the PoA on several parameters, for example, the minimal spillback factor, which measures how much the capacities of an edge are reduced due to spillback. Another interesting phenomenon of selfish road users we study is the well known Braess paradox  [2]. It states that the overall travel time of all users might decrease if a frequently used road segment gets closed. In reverse, this means that building new roads between heavily used section of the network might cause more congestion and longer travel times.

Related Work. Flows over time were first introduced by Ford and Fulkerson  [8] in the context of an optimization problem to route as much flow as possible in a given time horizon. Gale  [9] proved the existence of earliest arrival flows which optimize the amount of flow routed to the sink simultaneously for all points in time and Wilkinson  [26] later presented an algorithm to compute these flows. For an overview on flows over time from an optimization point of view we refer to the survey by Skutella  [23]. From a game theoretic point of view, flows over time were first considered by Vickrey  [24] in the setting of transportation research. In the last years the theory of Nash equilibria for flow models has been advanced significantly. From the introduction of the price of anarchy by Koutsoupias and Papadimitriou [13, 16] and the congestion games studied by Roughgarden and Tardos  [18, 19] (both for static flows), over existence results concerning the dynamic (i.e., time dependent) model by Meunier and Wagner  [15], to the constructive approach to dynamic equilibria by Koch and Skutella  [12]. Here, the authors present a novel notion of dynamic equilibria, called Nash flows over time, which enabled a whole set of proceeding research. This new research includes the study of existence, uniqueness and the long-term behavior of Nash flows over time by Cominetti et al.  [4,5,6], the work by Macko et al.  [14] about the Braess paradox for flows over time as well as the extension to multi-terminal settings  [21]. Of special interest to the paper at hand are the results by Bhaskar et al.  [1] and very recently by Correa et al.  [7] about the PoA for flows over time. Since it was already shown that the evacuation-PoA (maximizing the flow amount within some time horizon) is unbounded  [12], they focus on the time-PoA (minimizing the completion time for a given flow amount) for which they establish an upper bound of $\frac{e}{e-1}$ under some constraints on the capacities of the network. Sering and Vargas Koch  [22] generalized the flows over time model in order to represent spillback and transferred the results about dynamic equilibria to this extension. Very recently, Graf et al.  [10] characterized an alternative equilibrium concept for flows over time, where particles do not predict the future evolution of the flow but instead reconsider their route choice on every node. In addition, there is a active research line on packet routing models, where traffic is represented by atomic vehicles that traverses the network in discrete time steps. Recent progress in this area is due to Cao et al.  [3], Scarsini et al.  [20], Harks et al.  [11] and Peis et al.  [17].

Contribution and Outline. We study the price of anarchy of flows over time with spillback introduced in  [22], which is known to be unbounded in general. After introducing the model in Sect. 2, we show in Sect. 3 that the PoA stays unbounded even if we restrict the set of networks to a specific topology but allow arbitrary capacity, or in reverse if we only allow unit capacities but therefore more complex graph structures. Furthermore, we show that the Braess ratio can be arbitrarily large depending only on the minimum edge capacity. Even though it seems that the addition of full edges and spillback only increases completion times this is not a general rule, as we show that there are examples where the completion time of Nash flows over time is larger when disabling spillback. In contrast to the above lower bounds we show in Sect. 4 that if we consider the case of temporal routing games on a fixed network, i.e., only the flow amount that gets routed through the network varies, the PoA is bounded by a constant. In the end we translate the ideas of  [1] to the model with spillback and prove an upper bound of $\frac{\mathsf {c}^{}_{} e}{\mathsf {c}^{}_{} e - 1}$ on the PoA in networks with specific conditions on the capacities in dependency of a maximal flow over time. This upper bound only depends on the worst spillback factor $\mathsf {c}^{}_{}$ of the Nash flows over time of the given network, and therefore provides a way to quantify the impact of spillback to the PoA (note that e denotes the Euler constant here). Finally, we give a brief conclusion and outlook for further research in Sect. 5.

2 The Model

In the following we want to recall the essential definitions of the flow over time model with deterministic queuing. We consider the extended version that handles spillback effects, as introduced in  [22] and mainly stick to the same notation.

Flow Dynamics. We consider a network $\varGamma = (G, s, t, r_0, \tau , \nu ^+, \nu ^-, \sigma )$ given by a directed graph $G = (V, E)$ with a single source s and a single sink t, such that every vertex is reachable from s. We have a network inflow rate of $r_0 >0$ determining the constant rate of flow entering the network from time 0 onward. Furthermore, every edge $e \in E$ is equipped with a transit time $\tau _e \ge 0$, an in- and outflow capacity $\nu _e^+ > 0$ and $\nu _e^- > 0$ as well as a storage capacity $\sigma _e > 0$. In order to avoid undefined flow behavior, we require that traversing flow alone can never fill up an edge, i.e., $\sigma _e > \nu _e^+ \cdot \tau _e$ and that the total transit time of every directed cycle is strictly positive. For technical reason we furthermore assume that all properties are rational numbers.

A flow over time is given by a family of locally integrable and bounded functions $f = (f_e^+, f_e^-)_{e \in E}$, where $f_e^+, f_e^- :\mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}$ denote the in- and outflow rate of edge e at every point in time. The cumulative in- and outflow and the queue size are given by

We require that flow is preserved at every edge e (non-deficit constraint) and at every vertex $v \in V \setminus \{t\}$ (conservation constraint), which means, for every point in time $\theta$ we have

$$z_e(\theta ) \ge 0 \qquad \text { and } \qquad \sum _{e \in \delta _v^+} f_e^+(\theta ) - \sum _{e \in \delta _v^-} f_e^-(\theta ) = {\left\{ \begin{array}{ll} 0 &{} \text { for } v \in V \setminus \{s, t\},\\ r_0 &{} \text { for } v = s. \end{array}\right. } $$

Here, $\delta _v^-$ is the set of all incoming and $\delta _v^+$ the set of all outgoing edges of node v. An edge e is full at time $\theta$ if the total amount of flow on e, called edge load, reaches the storage capacity $\sigma _e$. The inflow bound $b_e^+(\theta )$ denotes that current inflow capacity, which might be smaller than $\nu _e^+$ due to spillback, and the push rate $b_e^-(\theta )$ specify the current desired outflow rate, which is reached whenever there are no restrictions of following links. Formally, we have

A flow over time f is feasible if for all edges e and all times $\theta$ it satisfies $f_e^+(\theta ) \le b_e^+(\theta )$ (inflow condition) and if there exists a $c_v \in (0, 1]$ for every $v\in V$ such that for every $e\in \delta ^-(v)$ $f_e^-(\theta ) = \min \{b_e^-(\theta ), \nu _e^- \cdot c_v\}$ (fair allocation condition). Furthermore, we require for all time $\theta$ that every vertex v with an incoming edge $e_1 \in \delta _v^-$ with $f_{e_1}^-(\theta ) < b_{e_1}^-(\theta )$ (called throttled edge) there exists an outgoing edge $e_2 \in \delta _v^+$ with $f_{e_2}^+(\theta ) = b_{e_2}^+(\theta )$ (no-slack condition). Finally, the set of full edges should be cycle free at every point in time (no-deadlock condition).

For a given $v\in V$ the maximal value c that satisfies the fair allocation condition at a given point in time $\theta$ is called spillback factor denoted by $c_v(\theta )$. This value denotes the reduction of the outflow capacity due to spillback leading to the effective outflow capacity of $\nu _e^- \cdot c_v(\theta )$. If the outflow rate $f_{uv}^-(\theta )$ of an incoming edge is strictly smaller than the push rate $b_{uv}^-(\theta )$, this edge is throttled implying $c_v(\theta ) < 1$, which means that there is spillback at v. In this case the no-slack condition ensures that there is a reason for the spillback in form of an outgoing exhausted edge vw: $f_{vw}^+(\theta ) = b_{vw}^+(\theta )$. The spillback factor will play an important role throughout this paper. For more details and further intuition on the definitions of a feasible flow over time in this setting we refer to  [22].

Nash Flows Over Time. In order to define Nash flows over time we need to define the arrival time of every particle of the flow. To simplify the notation we identify every particle with the point in time $\theta$ when it enters the network at the source. For every edge e we define the waiting time function $q_e :\mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}$ by , i.e., $q_e(\theta )$ denotes the time a particle entering e at time $\theta$ waits in the queue. For every vertex v the earliest arrival time function $\ell _v :\mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}$ denotes the earliest point in time the particle $\theta$ (which enters the network at time $\theta$) can reach v:

For a given particle $\theta$ the current shortest path network $G'_\theta = (V, E'_\theta )$ is the network of all edges $e = uv$ that are active for $\theta$, i.e., for which $\ell _v(\theta ) = \ell _u(\theta ) + \tau _e + q_e(\ell _u(\theta )).$ It contains all s-v-paths that particle $\theta$ can use to be at v at the earliest possible point in time. Furthermore, we denote the resetting edges $E^*_\theta$ as the set of edges for which particle $\theta$ encounters a queue when taking a current shortest path and $\bar{E}_\theta$ denotes the set of edges which are full when particle $\theta$ reaches its tail. More precisely, and .

Definition 1 (Nash flow over time)

We call a feasible flow over time f a Nash flow over time, or dynamic equilibrium, if almost every particle uses a current shortest s-t-path, i.e., if $f_e^+(\theta ) > 0$ implies $\theta \in \ell _u(\varTheta _e)$ for all $e = uv \in E$ and almost all $\theta \in \mathbb {R}_{\ge 0}$, where denotes all particles for which e is active.

Equivalently, it has been shown  [22, Lemma 4.1] that a feasible flow over time is a dynamic equilibrium if and only if $F^+_e(\ell _u(\theta )) = F^-_e(\ell _v(\theta ))$ for all $e = uv \in E$ and all $\theta \in \mathbb {R}_{\ge 0}$. By setting we observe that $(x_e(\theta ))_{e \in E}$ form a static s-t-flow of value $r_0 \cdot \theta$. Since the $x_e$ are absolute continuous, their derivatives

$$\begin{aligned} x'_e(\theta ) = f_e^+(\ell _u(\theta )) \cdot \ell '_u(\theta ) = f_e^-(\ell _v(\theta )) \cdot \ell '_v(\theta ) \end{aligned}$$

(1)

exist almost everywhere and can be seen as the strategy of particle $\theta$ (as for every $\theta$ it is a static s-t-flow of value $r_0$). For a fixed $\theta$ the derivatives and together with the spillback factors are called spillback thin flows and with for all $e = uv$ satisfy the following equations:

$$\begin{aligned} \begin{array}{llll} \ell '_s &{}= 1, &{}&{}\\ \ell '_v &{}= \mathop {\min }\limits _{e = uv \in E'_\theta } \rho _e\left( \ell '_u, x'_e, c_v\right) \quad &{}&{} \text { for } v \in V \setminus \{s\},\\ \ell '_v &{}= \rho _e\left( \ell '_u, x'_e, c_v\right) &{}&{} \text { for } e = uv \in E'_\theta \text { with } x'_e > 0,\\ \ell '_v &{}\ge \mathop {\max }\limits _{e = vw \in E'_\theta } \frac{x'_e}{b_e^+} &{}&{} \text { for } v \in V,\\ \ell '_v &{}= \mathop {\max }\limits _{e = vw \in E'_\theta } \frac{x'_e}{b_e^+} &{}&{} \text { for } v \in V \text { with } c_v < 1, \end{array} \end{aligned}$$

where

It turns out that the particles of a Nash flow over time f can be divided into intervals, so called phases, for which the derivatives (and thus the inflow and outflow rates) stay constant. We denote the set of phases by $\mathcal {I}_{f}$. The transition points between two phases correspond to one or multiple events: A new edge (and therefore new s-t-paths) can become active, a queue can deplete, an edge can become full or the outflow rate (and hence the inflow bound) of a full edge might change. Note however, that an event at edge $e = uv$ for a particle $\theta$ does not happen at time $\theta$ itself but rather at time $\ell _u(\theta )$ when the particle entering the network at time $\theta$ reaches vertex u (while taking a shortest s-u path).

Games, Optimal Flows and the Price of Anarchy. For a temporal routing game we consider a finite volume of flow $M \in (0, \infty )$ entering the network. For a Nash flow over time f the last particle enters the network at time $\frac{M}{r_0}$ and leaves the network at time $\ell _t(\frac{M}{r_0})$. As the network satisfy the first-in-first-out-principle (FIFO), $\ell _t$ is non-decreasing, which means that denotes the completion time when the entire flow of volume M has reached t. Most of the time we identify a network $\varGamma$ with its corresponding temporal routing game (i.e., $\varGamma$ and M). In contrast to dynamic equilibria, optimal quickest flows can be computed by determining a time horizon T with $\ell _t(\frac{M}{r_0}) = T$ by applying a binary search framework to the maximum flow over time problem. Hereby, a maximum flow over time for time horizon T can be constructed via a feasible static flow $y$ maximizing $T \cdot \left|y \right| - \sum _{e \in E} \tau _e \cdot y_e$. This underlying static flow $y$ is then temporally repeated, which means a rate of $y_p$ is sent into every s-t path $p \in \mathcal {P}_{st}$ over time $[0, T - \tau _p]$. The arrival time of the last particle at t (i.e., the optimal completion time) is denoted by $T_\text {opt}(M)$. For more details on optimal flows over time we refer to Skutella’s survey  [23].

In this paper we consider the time price of anarchy (which we simply refer to as “price of anarchy”). For a given temporal routing game $\varGamma$ it measures the worst ratio between the arrival time at t for the last particle in a Nash flow over time and the arrival time in an optimal flow: .¹ As it is unknown whether the arrival time functions $\ell _t$ are unique over all Nash flows over time, we need to consider the worst dynamic equilibrium, i.e., , where $\mathcal {F}({\varGamma })$ denotes the set of Nash flows over time in $\varGamma$.

Further Notation. We enumerate the event points by the order of their occurrence seen by particles at the source, i.e., $\theta _i < \theta _{i + 1}$ and say phase i is given by $(\theta _{i -1}, \theta _i)$ (using $\theta _0 = 0$).² In addition, we consider the point in time $\frac{M}{r_0}$ when the last particle enters the network as the last event r, i.e., . Since the edge sets $E'_\theta$, $E^*_\theta$, $\bar{E}_\theta$, the inflow bound, and hence, the spillback thin flow stay constant within each phase i we use the following notation for $\theta \in (\theta _{i - 1}, \theta _i)$

The inflow at the sink is also constant in a phase. We denote this by the capacity for some $\theta \in (\theta _{i -1}, \theta _i)$ where we use . Finally, the derivatives of the waiting times $(q_e(\ell _u(\theta )))'$ stay constant within a phase as they are either $\ell '_v(\theta ) - \ell '_u(\theta )$ if $e = uv$ is active or 0 otherwise. For $\theta \in (\theta _{i - 1}, \theta _i)$ we write and for an s-t path p.

3 Lower Bounds on the Price of Anarchy

We first show in 3 that the PoA can be unbounded even on very simple graphs (an observation first made in  [22]) and that the same is true for graphs with unit capacities. Afterwards, in 3 and 3, we use similar constructions to investigate the Braess paradox for flows over time with spillback and to show that there exist networks on which Nash flows over time with spillback are faster than their respective counterparts without spillback.

PoA Depending on Graph Structure or Capacities. Consider the network $\varGamma$ given in Fig. 1 and a Nash flow over time f of it. Since in the first phase the shortest path is $(e_1,e_2)$, edge $e_2$ fills up quickly. Once this happens flow already queues up at the end of edge $e_1$, and thus, $e_3$ is never used by f. An optimal flow can use $e_3$ and therefore routes flow to the sink much faster, resulting in an unbounded PoA. This construction can easily be generalized to all graphs that have the graph given in Fig. 1 as a minor.

Theorem 1

(cf.  [22, introductary example]) Let G be any graph that has the graph given in Fig. 1 as a minor, then there exists a temporal routing game $\varGamma$ on G with $\text {PoA}(\varGamma ) \in \varOmega (\frac{1}{\nu ^-_{\text {min}}})$ where .

Fig. 1.

This is a network on which Nash flows over time with spillback have unbounded price of anarchy (see Theorem 1). A similar example was first given in  [22, Fig. 2].

To avoid the above unboundedness one could ask for the PoA for temporal routing games on graphs with restricted edge capacities. By constrictions of the model we have to set the inflow and storage capacities of all edges $e\in \delta ^+(s)$ to $\nu ^+_{e} > r$ and $\sigma _e = \infty$, respectively. We say a network has unit edge capacities if for all edges $e\notin \delta ^+(s)$ it holds that $\nu ^+_{e} = \nu ^-_{e} = \sigma _e = 1$ and further for all edges $e\in \delta ^+(s)$ also $\nu ^-_{e}=1$. Unfortunately, even when restricting to networks with unit edge capacities the PoA is unbounded.

Theorem 2

capacities There exists a family of networks with unit edge capacities and $\tau _e \in \{0,1\}$ for all edges for which the PoA is linear in the number of edges.

This can be seen by considering the network given in Fig. 1 and exchanging $e_1$ and $e_3$ with bunches of unit-capacity parallel edges and setting $\nu ^-_{e_2} = \sigma _{e_2} = 1$. If we use enough parallel edges we can generate a similar flow behavior as we encountered when lowering the capacity of edge $e_2$ in the proof of Theorem 1.

Nevertheless, we show another way of constraining edge capacities to achive an interesting upper bound on the PoA in Sect. 4.2.

Braess Ratio. In his work on selfish routing with static flows  [2] Braess showed that there are networks where adding an edge can paradoxically increase congestion leading to a worse equilibrium. In line with the paper of Macko et al.  [14] we define the Braess ratio for flows over time with spillback as follows. Let $\varGamma$ be a temporal routing game on a graph G and let $\varGamma (H)$ be the same instance restricted to some subgraph $H\subseteq G$. Then the Braess ratio of $\varGamma$ is

$$\begin{aligned} \text {BR}(\varGamma ) = \max _{H\subseteq G} \frac{T_\text {EQ}(\varGamma )}{T_\text {EQ}(\varGamma (H))}. \end{aligned}$$

We say graph G admits a Braess paradox if there is a temporal routing game $\varGamma$ on G with $\text {BR}(\varGamma ) > 1$. In  [14] it is shown that the Braess ratio for flows over time without spillback (for a slightly different cost function instead of the last completion time) is arbitrarily large depending linearly on the number of edges of the underlying graph. The authors furthermore show that a graph G or its transpose (the graph where every edge uv is replaced by the edge vu and s and t are swapped) admit a Braess paradox if and only if G contains at least one of the following graphs as a topological minor.

When considering flows over time with spillback and the graph in Fig. 1 it is easy to see that this graph admits a Braess paradox with arbitrarily large Braess ratio even though it does not have one of the graphs above as a topological minor (and neither does its transpose). To see this choose H to be the subgraph where from the graph in Fig. 1 we delete edge $e_{2}$.

Corollary 1

For any $a \in \mathbb {R}$ there exists a temporal routing game $\varGamma$ on the graph given in Fig. 1 such that the Braess ratio satisfies $\text {BR}(\varGamma ) > a$.

Spillback Can Improve Completion Time. The following proposition shows that there are temporal routing games where Nash flows with spillback perform better than Nash flows without spillback. This might at first be surprising, as spillback seems to only be obstructive to routing flow fast. But it is indeed possible to construct networks where spillback leads to shorter completion times. In the network depicted in Fig. 2 there are two parallel edges, namely $e_3$ and $e_{3^\prime }$, for which it holds that the completion time of a Nash flow is worse if the edges are present compared to the same network without those edges. We exploit this in our construction: In the spillback model one of these ‘bad’ edges becomes full nearly instantaneously yielding the other ‘bad’ edge to never get active. Thus, the spillback Nash flow routes flow only over one of those ‘bad’ edges. Since in the Koch-Skutella model without spillback both of these parallel edges get active at some point, the Nash flow over time here uses both of them resulting in a worse completion time.

Fig. 2.

This example shows that Nash flows over time with spillback can be faster than Nash flows over time without spillback, see Proposition 1.

Proposition 1

In the network $\varGamma$ given in Fig. 2 the completion time of any Nash flow over time with spillback is less than the completion time of the Nash flow over time without spillback on the same network using .

4 Upper Bounds on the Price of Anarchy

In the following we prove two upper bounds on the price of anarchy. First, we show that for a single, fixed network the PoA is bounded by a constant in the long run. After that we show that if for a given network we are allowed to decrease the outflow capacities by a certain amount then the PoA only depends on the worst spillback factor of the Nash flows over time.

4.1 Price of Anarchy for a Fixed Network

Until now we have studied the PoA depending on the structure of the underlying graph or its capacities. For both questions we constructed games satisfying strong constraints that still have unbounded PoA. Now we are interested in the PoA of a network where every parameter is fixed except for the target amount M, i.e., we ask the question of how the PoA behaves in the long run on a single network.

Lemma 1

For a temporal routing game $\varGamma$ on a fixed network the completion time of the optimal flow depending on the target amount M is bounded by $T_\text {opt}(M) \in \varTheta (M)$.

This result is mainly due to the fact that the optimal flow does not build up any queues. Therefore its completion time depends mainly on M and the minimum edge-capacity, which we consider to be fixed.

For the classification of the asymptotic long term behavior of $T_\text {EQ}(M)$ we use the following auxiliary lemma that gives us a lower bound on the spillback factors of a Nash flow. The lemma follows by an application of  [22, Lemma 3].

Lemma 2

For a temporal routing game $\varGamma$ there exists an $\varepsilon > 0$ such that for any Nash flow over time $f\in \mathcal {F}({\varGamma })$ the spillback factors satisfy $\min \{c_v(\theta ) : v\in V, \theta \in \mathbb {R}_{\ge 0}\} > \varepsilon$.

To get an asymptotic bound on $T_\text {EQ}(M) = \sup _{f\in \mathcal {F}({\varGamma })} T_{f}(M)$ we first argue that seen as a function in M, $T_{f}$ is a piece-wise linear and non-decreasing function. We can then use Lemma 2 to bound its derivative and with that obtain the desired result.

Theorem 3

For a temporal routing game $\varGamma$ on a fixed network the completion time of any Nash flow over time $f\in \mathcal {F}({\varGamma })$ is bounded by $T_{f}(M) \in \varTheta (M)$.

We can now use Lemma 1 and Theorem 3 and the fact that $\text {PoA}(M) = \frac{T_\text {EQ}(M)}{T_\text {opt}(M)}$ to bound the PoA for a fixed network. In order to do so we consider the PoA as a function of the target flow amount M.

Theorem 4

For a temporal game $\varGamma$ on a fixed network, i.e. when treating everything except the amount of flow M as a constant, the price of anarchy is bounded by a constant, $\text {PoA}(M) \in \varTheta (1)$.

4.2 Bound on the Price of Anarchy for Saturated Graphs

In this section we focus on networks with an additional constraint on the edge capacities. Given a game $\varGamma$ we know that the quickest flow of $\varGamma$ is also a temporally repeated flow, i.e., it has an underlying static flow $y$. We say that $y$ saturates every edge of the given graph if for each edge the outflow capacity is exhausted by $y$, i.e., for each $e\in E$ we have $\nu ^-_{e} = y_e$ and additionally it holds that $|y|=\sum _{sv\in \delta ^+(s)} y_{sv} = r_0$. We call the underlying graph of such a game a saturated graph. Even though restricting attention to saturated graphs may seem harsh, note, that every network can be made saturated by lowering the edge capacities. This can be imagined to be done by a system operator in a Stackelberg strategy-like scenario  [25] and is applicable in many real-world examples. For one, streets can be narrowed down by a city administration in practice.

For temporal routing games on saturated graphs we will show that the PoA can be bounded by a value that is only dependent on the worst spillback factor of all Nash flows over time. In order to do that we adapt the idea of the proofs given by Bhaskar et al.  [1] for the Koch-Skutella model to the spillback model. Note, however, that the proofs given in  [1] implicitly assume only finitely many phases, which has not been proven for any of the two models. Our generalization also holds for the case of an infinite number of phases in both models.³

In principle the proof works as follows. For a given game $\varGamma$ the relation of the completion time of any Nash flow over time of $\varGamma$ to the optimal completion time can be determined by examining the capacity of the current shortest path network and the derivatives of the waiting times for a single phase of the Nash flow. One can then bound the derivatives of the waiting times and use the fact that the PoA is the maximum over the relation of the optimal completion time to the completion times of all Nash flows. This achieves the desired bound.

Bound on the Derivatives of the Waiting Times. We start by proving a relation between the derivative of the label-function at the sink and the inflow into the sink. Our proof of this result uses a different idea than the one given in  [1] and is considerably shorter.

Lemma 3

(cf. [1, Lemma 15]) Let $\varGamma$ be a temporal routing game and let $f\in \mathcal {F}({\varGamma })$ with corresponding labels $\ell$. Then for any $\theta \le \frac{M}{r_0}$ we have

$$\begin{aligned} \ell ^\prime _{t}(\theta ) = \frac{r_0}{f^+_{t}(\ell _t(\theta ))}. \end{aligned}$$

Proof

Let $\theta \le \frac{M}{r_0}$ be arbitrary. Using that $x^\prime _{}(\theta )$ is a static s-t flow of value $r_0$ and $x^\prime _{vt}(\theta ) = f^-_{vt}(\ell _t(\theta )) \cdot \ell ^\prime _{t}(\theta )$ from Eq. (1) we obtain

$$\begin{aligned} r_{0} = \sum _{vt\in \delta ^-(t)} x^\prime _{vt}(\theta ) = \sum _{vt\in \delta ^-(t)} f^-_{vt} (\ell _t(\theta )) \cdot \ell ^\prime _{t}(\theta ) = \ell ^\prime _{t} (\theta ) \cdot f^+_{t}(\ell _t(\theta )). \end{aligned}$$

Since $f^+_{t}(\ell _t(\theta ))>0$ for all $\theta$, rearranging terms give the desired result.    $\square$

We now proceed with a path-wise bound on the derivatives of the waiting times $q_{i,p}^\prime$ for a single phase of the Nash flow over time i using the capacities $\kappa _{i}$.

Lemma 4

(cf. [1, Lemma 18]) Let $\varGamma$ be a temporal routing game where the static flow underlying the quickest flow saturates every edge and let $f\in \mathcal {F}({\varGamma })$. For any s-t path p, the travel time is bounded by

$$\begin{aligned} \tau _p \ge \ell _t(\theta _{r}) - \sum _{i\in \mathcal {I}_{f}} ( 1 + q_{i,p}^\prime ) \cdot \frac{\kappa _{i}}{r_0} \cdot (\ell _t(\theta _{i}) - \ell _t(\theta _{i-1})). \end{aligned}$$

In the proof we first establish a dependence of the length of a phase as it is experienced at the source and at the sink, respectively. Then we express $\tau _{p}$ in terms of the label functions $\ell$ and the waiting times q and their derivatives. The result then follows from applying Lemma 3.

Relation of the Completion Times of Nash Flow and Quickest Flow. The following lemma enables us to give a first relation of the completion times of the optimal quickest flow and a Nash flow over time.

Lemma 5

(cf.  [1, Lemma 19]) Let $\varGamma$ be a temporal routing game where the static flow $y$ underlying the quickest flow saturates every edge and let $f\in \mathcal {F}({\varGamma })$. Then, the completion time $T_\text {opt}$ of the optimal flow and the completion time $T_{f}$ of the Nash flow f are related as

$$\begin{aligned} r_0 \cdot T_\text {opt}= \sum _{p\in \mathcal {P}_{s,t}} y_p \tau _p + \sum _{i\in \mathcal {I}_{f}} \kappa _{i} \cdot (\ell _t(\theta _{i}) - \ell _t(\theta _{i-1})), \end{aligned}$$

where $\mathcal {P}_{s,t}$ is the set of all simple s-t paths in G and $\ell _t(\theta _{r}) = T_{f}$.

The proof idea is to compare the arrival rates of both flows at the sink t where we use a flow decomposition along paths for the optimal flow and a decomposition by phases for the Nash flow over time.

By combining the previous two lemmas we can now derive a lower bound on the inverse of the PoA that we will afterwards use to achieve an upper bound on the actual PoA. But in order to proof that we first need the following.

Lemma 6

Let for each phase $i\in \mathcal {I}_{f}$. Then,

$$\begin{aligned} \sum _{i\in \mathcal {I}_{f}} \lambda _i \cdot (\ell _t(\theta _{i})-\ell _t(\theta _{i-1})) \le (\ell _t(\theta _{r})-\ell _t(\theta _{0})) \cdot \sup _{i\in \mathcal {I}_{f}} \lambda _i. \end{aligned}$$

In the proof we first establish that the set $\{\lambda _i : i\in \mathcal {I}_{f}\}$ is bounded and then use this and the telescoping principle to bound the left hand side.

The next lemma establishes the aforementioned bound on the inverse of the PoA. It is in this proof that the number of $\alpha$-extension phases comes into play. If we assume that the supremum in the statement of Lemma 6 is attained by some phase $i\in \mathcal {I}_{f}$, which is in particular true if there are only finitely many phases, then we can prove Lemma 7 without the $\varepsilon$ error and the proofs go through similar to  [1]. But since it is still an open problem whether the number of those phases is always finite (in the Koch-Skutella model as well as the spillback model), we prove it here for the case of infinitely many $\alpha$-extension phases.

Lemma 7

Let $\varGamma$ be a temporal routing game where the static flow $y$ underlying the quickest flow saturates every edge and let $f\in \mathcal {F}({\varGamma })$. Then for every $\varepsilon > 0$ there exists a phase i of f such that

$$\begin{aligned} \frac{T_\text {opt}}{T_{f}} + \varepsilon \ge 1 - \frac{\kappa _{i}}{{r_0}^2} \sum _{e\in E} \nu ^-_{e} q_{i,e}^\prime . \end{aligned}$$

The proof idea is to sum $y_p \tau _p$ over all paths $p\in \mathcal {P}_{s,t}$ and using Lemma  4 to bound this from below. Afterwards, we use Lemmas 5 and 6 to obtain a lower bound on $\frac{T_\text {opt}}{T_{f}}$ in terms of a supremum of the capacities and derivatives of the queuing delay over all phases. Since we do not know whether this supremum is attained we have to inject the $\varepsilon$ error and after rearranging terms we obtain the desired result.

Upper Bound for Saturated Graphs. We can now turn the lower bound in Lemma 7 into an upper bound on the price of anarchy by proving a bound on the sum of the right-hand side of the expression given in Lemma 7. Here for the first time the spillback factors of the Nash flow over time play an important role.

Lemma 8

Let $\varGamma$ be a temporal routing game and $f\in \mathcal {F}({\varGamma })$. In any phase i of f where $\frac{r_0}{\kappa _{i}}\ge 1$ we have

$$\begin{aligned} \sum _{e\in E} \nu ^-_{e} q_{i,e}^\prime \le \frac{r_0}{\mathsf {c}^{f}_{i}} \ln \left( \frac{r_0}{\kappa _{i}}\right) , \end{aligned}$$

where is the minimal $c_v$ of f in phase i.

The proof utilizes  [7, Claim 12] and follows the line of argumentation in  [1] but incorporates the added complexity of the spillback model. We obtain that $c_v \nu ^-_{e} q^\prime _{e} = x^\prime _{e} \cdot (1- \frac{\ell ^\prime _{u}}{\ell ^\prime _{v}})$ for every edge $e=uv$ and then sum this expression over all edges in the graph. Rearranging and plugging in the above expression then yields the desired result.

We can now obtain the desired upper bound on the price of anarchy.

Theorem 5

Let $\varGamma$ be a temporal routing game where the static flow $y$ underlying the quickest flow saturates every edge of the graph. If the minimal spillback factor satisfies , then the price of anarchy is bounded by $\frac{T_\text {EQ}}{T_\text {opt}} \le \frac{\mathsf {c}^{}_{} e}{\mathsf {c}^{}_{} e - 1}.$

Proof

For any $f\in \mathcal {F}({\varGamma })$ with completion time $T_{f}$ we know that $f^+_{t}(\theta ) = \sum _{vt\in \delta ^-(t)} f^-_{vt}(\theta ) \le r_0$ for all $\theta \in \mathbb {R}_{\ge 0}$ since we only consider saturated graphs. Thus, we have $\frac{r_0}{\kappa _{i}} \ge 1$ in all phases of f. From Lemmas 7 and 8 we obtain that for every $\varepsilon > 0$ there exists a phase i of f such that

$$\begin{aligned} \frac{T_\text {opt}}{T_{f}} + \varepsilon \ge 1 - \frac{\kappa _{i}}{{r_0}^2} \sum _{e\in E} \nu ^-_{e} q_{i,e}^\prime \ge 1 - \frac{\kappa _{i}}{{r_0}^2} \frac{r_0}{\mathsf {c}^{f}_{i}} \cdot \ln \left( \frac{r_0}{\kappa _{i}}\right) = 1 - \frac{a_{i}}{\mathsf {c}^{}_{}} \cdot \ln \left( \frac{1}{a_{i}}\right) , \end{aligned}$$

where and .

Simple calculus shows that the term $\frac{a_{i}}{\mathsf {c}^{}_{}} \cdot \ln \left( \frac{1}{a_{i}}\right)$ is maximized for $a_{i} = \frac{1}{e}$. Using the above inequality, derived from some phase i, for any $\varepsilon > 0$ we obtain

$$\begin{aligned} \frac{T_\text {opt}}{T_{f}} + \varepsilon \ge 1 - \frac{1}{\mathsf {c}^{}_{} e} = \frac{\mathsf {c}^{}_{} e - 1}{\mathsf {c}^{}_{} e}. \end{aligned}$$

Since by assumption we have $\mathsf {c}^{}_{} > \frac{1}{e}$ we can take the inverse of the inequality to obtain $\frac{T_{f}}{T_\text {opt}} \le \frac{\mathsf {c}^{}_{} e}{\mathsf {c}^{}_{} e - 1}.$ We finish by noting that $T_\text {EQ}= \sup _{f\in \mathcal {F}({\varGamma })} T_{f}$.    $\square$

5 Conclusions

Our work shows that the PoA is highly dependent on spillback effects. Although, even in restricted network classes the completion times of dynamic equilibria can be arbitrarily bad compared to a quickest flow, the PoA can still be bounded in terms of the spillback factors under some constraints on the edge capacities. Transferred to real-world traffic this means the interplay between selfish traffic users is critical in particular in high congested areas.

Even though we give a substantial analysis of the PoA in the flow over time model with spillback, there are still some open problems remaining. Is the bound we establish in Theorem 5 tight? Are there any bounds in the case of $\mathsf {c}^{}_{} \le \frac{1}{e}$ or is it possible to enforce $\mathsf {c}^{}_{} > \frac{1}{e}$ through some Stackelberg-like strategy? Do the results of the recent work of Correa et al.  [7] also transfer to the spillback setting? On the more applied side of the research it would also be very interesting to algorithmically identify street segments (edges) which are especially vulnerable for spillback. In the long run this could help road administrations to decide which roads should be expanded (increasing the storage capacity) or which roads should be narrowed or closed (due to the Braess effect).