The Price of Anarchy for Instantaneous Dynamic Equilibria

Abstract

We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order $\mathcal {O}(U\cdot \tau )$ for single-sink instances, where U denotes the total inflow volume and $\tau$ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order $\varOmega (U\cdot \log \tau )$.

1 Introduction

Dynamic flows have gained substantial interest over the last decades in modeling dynamic network systems such as urban traffic or the Internet. A widely used model for describing dynamic flows is based on the fluid queueing model due to Vickrey  [23]. There is a directed graph $G=(V,E)$, where edges $e\in E$ are associated with a queue with positive rate capacity $\nu _e\in \mathbb {R}_+$ and a physical transit time $\tau _e\in \mathbb {R}_+$. If the total inflow into an edge $e=vw\in E$ exceeds the rate capacity $\nu _e$, a queue builds up and arriving flow particles need to wait in the queue before they are forwarded along the edge. The total travel time along e is thus composed of the waiting time spent in the queue plus the physical transit time $\tau _e$.

Due to the decentralized nature of the above mentioned applications, the physical flow model needs to be complemented by a behavioral model prescribing the actions of flow particles. Most works in the transportation science literature as well as recent works in the mathematics and computer science literature adopt the full information model, i.e., all flow particles have complete information on the state of the network for all points in time (including the future evolution of all flow particles) and based on this information travel along a shortest path. This leads to the concept of dynamic equilibrium (Nash equilibrium) and has been analyzed in the transportation science literature for decades, see Friesz et al.  [7], Meunier and Wagner  [18], Zhu and Marcotte  [24] and the more recent works by Koch and Skutella  [16] and Cominetti, Correa and Larré  [3]. The full information assumption has been justified by assuming that the game is played repeatedly and a dynamic equilibrium is then an attractor of a learning process. In light of the wide-spread use of navigation devices, this concept may not be completely realistic anymore, because drivers are informed in real-time about the current traffic situation and, if beneficial, reroute instantaneously no matter how good or bad that route was in hindsight. This aspect is also discussed in Marcotte et al.  [17], Hamdouch et al.  [12] and Unnikrishnan and Waller  [22].

Instead of the (classical) dynamic equilibrium, we consider in this paper instantaneous dynamic equilibria (IDE), where for every point in time and at every decision node, flow only enters those edges that lie on a currently shortest path towards the respective sink. This concept assumes far less information (only the network-wide queue length which are continuously measured) and leads to a distributed dynamic using only present information that is readily available via real-time information. IDE have been proposed already in the late 80’s (cf. Ran and Boyce  [19, § VII-IX], Boyce, Ran and LeBlanc  [2, 20], Friesz et al.  [8]) and it is known that IDE do exist under quite general conditions, see Graf, Harks and Sering  [11].

Price of Anarchy. In comparison to dynamic equilibrium, an IDE flow behaves quite differently and several fundamental aspects of IDE are not well understood. There are, for instance, simple single-source single-sink instances in which the unique IDE flow exhibits cycling behavior, that is, some flow particles travel along cycles before they reach the sink. This behavior is impossible for dynamic equilibria as every particle chooses a path once and never gets into a cycle. This raises the question of the (time) price of anarchy of IDE flows.

Question (PoA): Assuming single-sink instances with constant inflow rates for a finite time interval, what is the maximum time needed so that every flow particle reaches the sink?¹

1.1 Our Results and Proof Techniques

We study the termination time of IDE flows for single-sink instances and derive the first quantitative upper bound on the termination of IDE flows. Our bound is parameterized in the numbers U and $\tau$ denoting the total flow volume injected into the sources and the sum of physical travel times, respectively. We denote by $\mathrm {PoA}(U,\tau )$ the price of anarchy over the family of instances parameterized by U and $\tau$.

We prove this bound by first deriving a general termination bound for acyclic graphs. Using this bound, we then show that there exist so-called sink-like subgraphs that can effectively be treated as acyclic graphs. This way, we can argue that at all times a sufficiently large flow volume enters the current sink-like subgraph and, by the bound for acyclic graphs, reaches the sink within the claimed time. The proof technique and the bound itself are completely different to those for dynamic equilibria in [4].

We then turn to lower bounds on the termination time (PoA) of IDE flows.

The lower bound is based on a quite complex instance (see Fig. 2) that works roughly as follows. We combine two gadgets: A “cycling gadget” consisting of a large cycle made of edges with capacity ${\approx }U$ and a “blocking gadget” consisting of paths with low capacity and length of about $\tau$ connecting the nodes on the cycle to the sink node. An IDE flow within this graph can then alternate between two different phases: A “charging phase”, wherein the main amount of flow travels once around the big cycle, loosing a small amount of flow to each of the paths leading towards the sink, and a “blocking phase”, in which the particles traveling along the paths form queues again and again in just the right way as to keep the main amount of flow traveling around on the large cycle without loosing any more flow. In order to derive a lower bound on the price of anarchy we then augment this instance in such a way that the optimal flow can just bypass the two gadgets and reach the sink in constant time while any IDE flow gets diverted into the cycling gadget.

1.2 Further Related Work

The concept of flows over time was studied by Ford and Fulkerson  [5]. Shortly after, Vickrey  [23] introduced a game-theoretic variant using a deterministic queueing model. Since then, dynamic equilibria have been studied extensively in the transportation science literature, see Friesz et al.  [8]. New interest in this model was raised after Koch and Skutella  [16] gave a novel characterization of dynamic equilibria in terms of a family of static flows (thin flows). Cominetti, Correa and Omar  [3] refined this characterization and Koch and Sering  [21] incorporated spillbacks in the fluid queuing model.

Regarding the price of anarchy of dynamic equilibria, Koch and Skutella  [16] derived the first results on the price of anarchy for dynamic equilibria, which were recently improved by Correa, Cristi and Oosterwijk  [4] devising a tight bound of $\frac{e}{e-1}$, provided that a certain monotonicity conjecture holds. Israel and Sering  [14] investigated the price of anarchy for the model with spillbacks. Bhaskar, Fleischer and Anshelevich  [1] devised Stackelberg strategies in order to improve the efficiency of dynamic equilibria. Recently, Frascaria and Olver  [6] considered a flexible departure choice model from an optimization point of view and derived insights into devising tolls for improving the performance of dynamic equilibria.

Ismaili  [13] considered a discrete version of IDEs and investigated the price of anarchy. He used the utilitarian social cost (not the makespan as we do) and derived lower bounds of order $\varOmega (|V|+n)$ for the setting that only simple paths are allowed. Here n denotes the number of discrete players in the game. For general multi-commodity instances allowing also cycles, he proves that the price of anarchy is unbounded. Similarly, Graf, Harks and Sering  [11] showed that for the continuous version multi-commodity IDE flows may cycle forever and, thus, the price of anarchy is infinity. For IDE flows in single-sink networks, on the other hand, they showed that termination is always guaranteed. However, due to the non-constructive nature of their proof they could not derive any explicit bound on the termination time or the price of anarchy for those instances.

2 Model

Let be a network consisting of a directed graph $G=(V,E)$, edge capacities $\nu _e \in \mathbb {N}^*$, edge travel times $\tau _e \in \mathbb {N}^*$,² a single sink node $t \in V$ reachable from every other node and for every node a corresponding integrable (network) inflow rate $u_v: \mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}$. The idea then is that, at all times $\theta \in \mathbb {R}_{\ge 0}$ infinitesimal small agents enter the network at node v at a rate according to $u_v(\theta )$ and start traveling through the graph towards the common sink t. Such a dynamic can be described by a flow over time, a tuple $f = (f^+,f^-)$ where $f^+,f^-: E \times \mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}$ are integrable functions. For any edge $e \in E$ and time $\theta \in \mathbb {R}_{\ge 0}$ the value $f^+_e(\theta )$ describes the (edge) inflow rate into e at time $\theta$ and $f^-_e(\theta )$ is the (edge) outflow rate from e at time $\theta$.

For any such flow over time f we define the cumulative (edge) in- and outflow rates $F^+$ and $F^-$ as

respectively. The queue length of edge e at time $\theta$ is then defined as

(1)

We call such a flow f a feasible flow for a given set of network inflow rates $u_v: \mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}$ for each node $v \in V \setminus \{t\}$, if it satisfies the following constraints (2) to (5). The flow conservation constraints are modeled for all nodes $v \ne t$ as

$$\begin{aligned} \sum _{e \in \delta ^+_v}f^+_e(\theta ) - \sum _{e \in \delta ^-_v}f^-_e(\theta ) = u_v(\theta )&\quad \text { for all } \theta \in \mathbb {R}_{\ge 0}, \end{aligned}$$

(2)

where and are the sets of outgoing edges from v and incoming edges into v, respectively. For the sink node t we require

$$\begin{aligned} \sum _{e \in \delta ^+_{t}}f^+_e(\theta ) - \sum _{e \in \delta ^-_{t}}f^-_e(\theta ) \le 0 \end{aligned}$$

(3)

and for all edges $e \in E$ we always assume

(4)

Finally we assume that the queues operate at capacity which can be modeled by

(5)

Termination Time for Flows over Time. We will now introduce some additional notation in order to formally define the termination time of a feasible flow. Since termination is only relevant for flows with finitely lasting inflow rates, from here on we will always assume that there exists some time $\theta _0$, such that the supports of all network inflow rates $u_v$ are contained in $[0,\theta _0]$.

Following [21], for any feasible flow f and every edge $e \in E$ we define the edge load function $F^{\varDelta }_{e}$ that gives us for any time $\theta$ the total amount of flow currently on edge e (either waiting in its queue or traveling along the edge):

$$\begin{aligned} F^{\varDelta }_{e} : \mathbb {R}_{\ge 0} \rightarrow \mathbb {R}_{\ge 0}, \theta \mapsto F^+_e(\theta )-F^-_e(\theta ). \end{aligned}$$

The function $F^{\varDelta } (\theta ) := \sum _{e \in E}F^{\varDelta }_{e} (\theta )$ then gives the total amount of flow in the network at time $\theta$. It is a straightforward calculation to show that after $\theta _0$ the function $F^{\varDelta }$ is monotonically decreasing.

Lemma 1

Let f be a feasible flow. Then for all $\theta _2 \ge \theta _1 \ge \theta _0$, we have $F^{\varDelta } (\theta _2) \le F^{\varDelta } (\theta _1).$ In particular, for $\hat{\theta } \ge \theta _0$ with $F^{\varDelta } (\hat{\theta }) = 0$, we have $F^{\varDelta } (\hat{\theta }) = 0$ for all $\theta \ge \hat{\theta }$.

This motivates the following definition of termination time.

Definition 1

A feasible flow over time f terminates if it satisfies

We then say that is the termination time of f or f terminates by time $\varTheta$. Lemma 1 then implies $F^{\varDelta } (\theta ) = 0$ for all $\theta > \varTheta$.

IDE Flows and their PoA. Following [11] we define an IDE flow as a feasible flow with the property that whenever a particle arrives at a node $v \ne t$, it can only enter an edge that is the first edge on a currently shortest v-t path. Here, the current or instantaneous travel time is defined for any edge e and time $\theta$ as

(6)

We then define time dependent node labels $\ell _{v}(\theta )$ corresponding to current shortest path distances from v to the sink t. For the sink t we set $\ell _t(\theta )=0$ for all times $\theta \in \mathbb {R}_{\ge 0}$, while for all other nodes and $\theta \in \mathbb {R}_{\ge 0}$ we recursively define $\ell _v(\theta ) = \min \limits _{e=vw\in E} \{\ell _{w}(\theta )+c_{e}(\theta )\}$. We say that an edge $e=vw$ is active at time $\theta$, if $\ell _{v}(\theta ) = \ell _{w}(\theta )+c_{e}(\theta )$ and we denote the set of active edges by $E_\theta \subseteq E$. We call a v-t path P an active v-t path at time $\theta$, if all edges of P are active for i at $\theta$ or, equivalently, $\sum _{e \in P}c_e(\theta ) = \ell _{v}(\theta )$. For differentiation we call paths that are minimal with respect to the transit times $\tau$ physical shortest paths.

Definition 2

A feasible flow over time f is an instantaneous dynamic equilibrium (IDE), if for all $\theta \in \mathbb {R}_{\ge 0}$ and $e\in E$ it satisfies

$$\begin{aligned} f_{e}^+(\theta )>0 \Rightarrow e\in E_\theta . \end{aligned}$$

(7)

Since in an IDE flow particles act selfishly and without cooperation we should expect that the termination time of an IDE flow is not optimal. To quantify this difference between termination times of IDE flows and optimal flows we will use the price of anarchy, which we define as follows: For any instance we define the worst case termination time of an IDE flow in $\mathcal {N}$ as

and the optimal termination time in $\mathcal {N}$ as

Definition 3

For any pair of whole numbers $(U,\tau )$ we define the Price of Anarchy (PoA) for instances with total flow volume U and total edge length $\tau$ as

Remark 1

At first it might seem strange that the $\mathrm {PoA}$ depends only on U and $\tau$ while being independent of the capacities $\nu _e$. However, this is only the case here because we always assume that all capacities are at least 1 throughout this paper. In order to transfer our results to networks with arbitrary capacities one has to rescale the network and, in particular, replace U by $\frac{1}{\nu _{\min }}U$, where .

3 Upper Bounds

In this section we will show an upper bound for the termination time of IDE flows in terms of and . From this we can then derive an upper bound for the $\mathrm {PoA}$. However, before we can turn to these general termination results we first have to look at acyclic graphs and give a termination bound for all feasible flows in such networks in terms of U and $\tau (P_{\max })$, where the latter denotes the physical length of a longest v-t path. Even though the bound may seem obvious its proof requires a quite lengthy and careful analysis which can be found in the full version of this paper [10].

Lemma 2

In an acyclic network, every feasible flow over time terminates before $\theta _0 + \tau (P_{\max })+ U$.

Similarly to the proof of termination in [11, Theorem 4.6] we will apply our result for feasible flows in acyclic graphs to IDE flows in general graphs by using the fact ( [11, Lemma 4.4]) that, whenever the total flow volume in a subgraph is small enough, only the physically shortest paths in this subgraph can be active. Since these edges form an acyclic subgraph, for an IDE flow we can then apply Lemma 2. For the following proof we will look at a particular type of subgraph, which we will call a sink-like subgraph: a subgraph containing all physically shortest paths from its nodes towards the sink, with a sufficiently low flow volume at the beginning of some interval as well as a low inflow into this subgraph over the course of said interval.

Definition 4

An induced subgraph $T \subseteq G$ is a sink-like subgraph on an interval $[\theta _1,\theta _2]$ with $\theta _1 \ge \theta _0$ if the following two properties hold:

• For each node $v \in V(T)$ all physically shortest v-t paths are contained in T.

• T satisfies .

Here denotes the set of edges entering the subgraph T. Using [11, Lemma 4.4] we can show that inside a sink-like subgraph only physically shortest paths towards the sink can be active (see [10] for the full proof).

Lemma 3

Let T be a sink-like subgraph on an interval $[\theta _1,\theta _2]$. Then during this interval only physically shortest paths towards t can be active.

Together with Lemmas 1 and 2 this implies that any IDE flow will terminate once the whole graph is sink-like.

Corollary 1

Let f be an IDE flow and $\tilde{\theta } \ge \theta _0$ such that the whole graph G is sink-like at time $\tilde{\theta }$. Then, the flow terminates before $\tilde{\theta } + \tau (P_{\max })+ \frac{1}{2}$.

To get an upper bound on the termination time of an IDE flow it now suffices to find a large enough time horizon such that it contains at least one point in time where the whole graph is sink-like. To determine such a time, we first show that if we have a sink-like subgraph over a sufficiently long period of time, we can extend this subgraph to a larger sink-like subgraph over a slightly smaller subinterval. Note, that the proof of [11, Theorem 4.6] uses a similar strategy, but is non-constructive and, therefore, only establishes the existence of a termination time without revealing anything about the length of this time. Thus, a more thorough analysis is needed here.

Lemma 4

Let $T \subsetneq G$ be an induced subgraph, v the closest node to t not in T and $T'$ the subgraph of G induced by . Let $\theta _1$ be some time after $\theta _0$, and .

If T is sink-like on $[\theta _1,\theta _2]$, then $T'$ is a sink-like subgraph on $[\theta _1,\theta '_2]$.

Proof

Since it is clear that $T'$ fulfills the first property of being sink-like (by the choice of v), we only need to show that $\mathrm {vol}_{T'}(\theta _1,\theta _2') \le \mathrm {vol}_{T}(\theta _1,\theta _2)$, from which the lemma follows immediately (as T is sink-like on $[\theta _1,\theta _2]$). More precisely we will show that the flow volume on edges between v and T (i.e. edges in $E(T') \setminus E(T) = (\delta _v^+ \cap \delta _T^-) \cup (\delta _v^- \cap \delta _T^+)$) at time $\theta _1$ as well as the inflow into v over the interval $[\theta _1,\theta _2']$ is already accounted for by the inflow into T on the interval $[\theta _1,\theta _2]$ via edges from v to T. This is formalized in the following three claims:

Fig. 1.

A sink-like subgraph T and a closest node $v \in V\setminus V(T)$ as in the statement of Lemma 4. By Claim 1 all flow on the dash-dotted edge from T to v will reach v before time $\theta _v$. By Claim 2 between $\theta _1$ and $\theta _v$ all flow reaching v (either via the dotted or via the dash-dotted edges) will travel towards T from there (i.e. enter one of the dashed edges). By Claim 3 the dashed edges will never carry a larger flow volume than $\frac{1}{2}$ between $\theta _1$ and $\theta _v$ and all flow particles using these edges within this time interval will reach T before $\theta _2$.

Claim 1

All flow on edges from T to v (dash-dotted edges in Fig. 1) at time $\theta _1$ reaches v before , i.e.

Claim 2

All flow reaching v (from T or $G\setminus T'$, i.e. via the dash-dotted or via the dotted edges in Fig. 1) between $\theta _1$ and $\theta _v$ will enter an edge towards T (dashed edges in Fig. 1), i.e.

Claim 3

For any edge from v to T (dashed edges in Fig. 1) the total amount of flow currently traveling on this edge at any time $\theta \in [\theta _1,\theta _v]$ is less than $\frac{1}{2}$, i.e.

$$\begin{aligned} F^{\varDelta }_{e} (\theta ) < \frac{1}{2} \text { for all } e \in \delta _v^+\cap \delta _T^- \text { and } \theta \in [\theta _1,\theta _v]. \end{aligned}$$

Additionally all this flow will reach T before $\theta _2$, i.e.

From Claims 1 to 3 we then directly get

implying . This shows that $T'$ is indeed sink-like on $[\theta _1,\theta _2']$. The proofs of the claims are relatively straightforward calculations (see [10]) using [11, Lemma 4.4] and a strengthened version of [11, Lemma 4.2]. Note, that the proofs have to be done in reverse order, as the proof of Claim 2 uses Claim 3 and the proof of Claim 1 uses both Claims 2 and 3.    $\square$

Theorem 1

For multi-source single-sink networks, any IDE flow over time terminates before .

Proof

Starting with the subgraph consisting only of the sink node t (which trivially contains all shortest paths towards t) and iteratively applying Lemma 4 we immediately get

Claim 4

If, after time $\theta _0$, the sink node t has a total cumulative inflow of less than $\frac{1}{2}$ for some interval of length $\sum _{e\in E}(\tau _e+\frac{1}{2\nu _e})$, then the whole graph is sink-like at the beginning of this interval.    $\blacksquare$

Since all flow reaching t vanishes from the network there can be at most 2U (pairwise disjoint) intervals of length $\sum _{e\in E}(\tau _e+\frac{1}{2\nu _e})$ with inflow of at least $\frac{1}{2}$ into t. Thus, there must be some time $\tilde{\theta } \le 2U \sum _{e\in E}(\tau _e+\frac{1}{2\nu _e})$ which is the beginning of an interval of length $\sum _{e\in E}(\tau _e+\frac{1}{2\nu _e})$ with total inflow of less than $\frac{1}{2}$ into t. So, by Claim 4, the whole graph is sink-like at $\tilde{\theta }$, which, by Claim 1, implies that the flow terminates before $\tilde{\theta } + \tau (P_{\max })+ \frac{1}{2} \le \hat{\theta }$.    $\square$

Remark 2

This means that for any single-sink network any IDE flow terminates within $\mathcal {O}\big (U\tau (G)\big )$.

Since $\varTheta _{\mathrm {OPT}}$ is trivially bounded below by $\theta _0+1$ this immediately leads to the following upper bound on the $\mathrm {PoA}$ for IDE flows:

Theorem 2

For any pair of integers $(U,\tau )$ we have $\mathrm {PoA}(U,\tau ) \in \mathcal {O}(U\tau )$.    $\square$

4 Lower Bounds on the Termination Time of IDE Flows

It is easy to see that a general bound for the termination time cannot be better than $\mathcal {O}(U+\tau (G))$, since any feasible flow in the network consisting of one source node with an inflow rate of U over the interval [0, 1], one sink node and a single edge between the two nodes with capacity 1 and some travel time $\tau$ terminates by $U+\tau (G)$. In the following, we will construct a family of instances, parameterized by $K,L \in \mathbb {N}^*$, that provide a lower bound on the termination time in single-sink networks of order $\varOmega (U\cdot \log (\tau (G)))$ – which is strictly larger than $\mathcal {O}(U+\tau (G))$.

For any given pair of positive integers $K,L \in \mathbb {N}^*$ the instance is of the form sketched in Fig. 2, with $u_{3^K+1}$ as source node and t as its sink. The graph has a “width” (i.e. length of the horizontal paths from $u_1$ to $u_{3^K+1})$ of ${\approx }3^{K+1}$ and a “height” (length of the vertical paths from nodes $u_i, v_i$ and $w_i$ to t) of ${\approx }K3^{K+1}$. All edges on the horizontal path (including the one edge back to $u_1$) have a capacity of 2U with $U \approx L3^{K+1}$, while all the edges on the vertical paths have capacities of either 1 or 3.

Fig. 2.

A network with a total edge travel time of ${\approx }3^{2K}$ that, given an inflow volume of ${\approx }L3^{K+1}$, has a termination time of more than $KL3^{K+1}$.

If we let flow enter at node $u_{3^K+1}$ at a rate of 2U over the interval $[-0.5,0]$, we will observe the following behavior: At first, all flow enters the direct downwards path towards the sink t until a queue of length 1 has built up on the first edge of this path. After that almost all flow will enter the edge towards $u_1$ and some flow will go downwards to keep the queue length constant. Assuming $U \gg 1$, most of the flow will travel towards $u_1$ and arrive there one time step later with a slightly lower inflow rate and over a slightly shorter interval as at $u_{3^K+1}$. At $u_1$ the same flow split happens again: First all flow enters the edge to $u'_1$ until a queue of sufficient length to induce a waiting time of 1 has formed, then most of flow travels towards the next node $v_1$. Similarly, at all the following nodes on the horizontal path, this pattern repeats, i.e., a small amount of flow (of volume ${\approx }3$) starts traveling downwards while most of the flow is diverted further to the right. Finally the main block of flow arrives at $u_{3^K+1}$ and is diverted back to $u_1$ (having lost a total volume of ${\approx }3^{K+1}$ to the downwards paths). By the time this flow arrives at $u_1$ again, the flow particles that traveled along the edges $u_1u'_1$, $v_1v'_1$ and $w_1w'_1$ join up again at node $x_1$ in such a way that they form a queue of length ${\approx }3$ on the edge $y_1z_1$. This queue is long enough to divert the main block of flow away towards $u_2$ (over the direct edge $u_1u_2$ of length 3). This pattern, again, repeats at all subsequent nodes $u_i$ until the main flow finally arrives at node $u_{3^K+1}$ (having lost no additional flow volume) and is again diverted back to $u_1$. This time, the flow particles from the queues on the edges $y_1z_1, y_2z_1$ and $y_3z_1$ met at node $z_1$ and now form a queue of length ${\approx }9$ on edge $a_1b_1$. Thus, our main flow can now be diverted away directly to node $u_4$ and so on. This way, the main amount of flow can travel along the horizontal path for ${\approx }K$ times without losing a significant amount of flow until all the flow on the vertical paths finally reaches the sink t. After that the pattern described until now repeats. Thus, flow remains in the network until at least time ${\approx }3^{K+1} K \frac{U}{3^{K+1}} = 3^{K+1} K L$.

Theorem 3

Given any pair $K,L \in \mathbb {N}^*$, there exists an instance $G_{K,L}$ with $\tau (G_{K,L}) \in \mathcal {O}(3^{2K})$ and $U_{K,L} \in \mathcal {O}(L3^{K})$ such that there exists an IDE flow that does not terminate before $LK(3^{K+1}+1)$.

Proof

The detailed construction as well as the formal proof of its correctness can be found in [10].    $\square$

In order to derive a lower bound on the price of anarchy from Theorem 3, we will slightly modify the instance used there in such a way that the termination time of the worst case IDE flow remains approximately the same, while there exists an optimal termination time in $\mathcal {O}(1)$.

Theorem 4

For any pair of positive integers $(U,\tau )$ satisfying $U \ge 2\tau$, we have $\mathrm {PoA}(U,\tau ) \in \varOmega (U\log \tau )$.

Proof

Wlog assume that there exist positive integers $L \ge 3^K$ such that $U = (L+3^K)3^K$ and $\tau = 3^{2K}$. Then we take the graph $G_{K,L}$ constructed in the proof of Theorem 3 and modify it by adding two new vertices s and v and four new edges as indicating in Fig. 3.

Fig. 3.

The instance from the proof of Theorem 3 (on the left), two additional nodes s and v as well as four new edges.

We now use s as our new source node and a constant inflow rate of $2U_{K,L}+1$ over the interval $[-0.5-\varepsilon ,0]$, where . The optimal termination time of the resulting network $\mathcal {N}$ is then at most 3, since we can just send all flow on the direct edge from s to t, where the last particle arrives 3 time steps later.

In an IDE flow, however, all flow particles travel first to v (as the path s-v-t is shorter than the path s-t), where they enter the edge towards t. This continues until a queue of length $\tau _{e_{3^K+1}}+3$ has built up at edge vt and the edge towards $u_{3^K+1}$ becomes active, which happens at time $\theta =0.5$. From there on, flow splits between the two edges, entering edge vt at a rate of 1 and edge $vu_{3^K+1}$ at a rate of $2U_{K,L}$ throughout the interval [0.5, 1]. Thus, over the interval [1.5, 2] flow arrives at node $u_{3^K+1}$ at a rate of $2U_{K,L}$. Continuing with the flow described before the statement of Theorem 3 is then again an IDE flow. This shows that $\varTheta _{\mathrm {IDE}} (\mathcal {N}) \ge LK(3^{K+1}+1)$.

From $\tau (\mathcal {N}) = \tau (G_{K,L}) + 4 \in \mathcal {O}(3^{2K})$ and $U_{\mathcal {N}} = \Big (\frac{1}{2}+\varepsilon \Big )(2U_{K,L} + 1) \in \mathcal {O}(L3^K + 3^{2K}) = \mathcal {O}(L3^K)$ we get $3^{2K} \in \varOmega (\tau (\mathcal {N}))$ and $L3^K \in \varOmega (U_{\mathcal {N}})$, which implies $\varTheta _{\mathrm {IDE}} (\mathcal {N}) \ge LK(3^K+1) \in \varOmega \big (U_{\mathcal {N}}\log \tau (\mathcal {N})\big )$. Thus, in particular, $\mathrm {PoA}(U,\tau ) \ge \frac{\varTheta _{\mathrm {IDE}} (\mathcal {N})}{\varTheta _{\mathrm {OPT}} (\mathcal {N})} \in \varOmega (U\log \tau )$.    $\square$

Remark 3

Expanding the network constructed in the proof of Theorem 4 into an acyclic network results in an instance with constant optimal termination time, but IDE termination time of $\tau (P_{\max })\gg \tau (P_{\min })$, where $\tau (P_{\min })$ is the physical length of a shortest path from the source to the sink node.

Together with the upper bound from Lemma 2 this implies the following bounds for the IDE price of anarchy for acyclic networks:

$$\begin{aligned} \mathrm {PoA}\big |_{\mathrm {acyclic}} \in \varOmega (\tau (P_{\max })) \cap \mathcal {O}(U + \tau (P_{\max })). \end{aligned}$$

5 Conclusions and Open Questions

We studied the efficiency of IDE flows and derived the first upper and lower bounds on the time price of anarchy of IDE flows. These bounds are of order $\mathcal {O}(U\tau )$ and $\varOmega (U\log \tau )$, respectively. Comparing these bounds to the constant bound of $\frac{e}{e-1}$ for dynamic equilibria (cf. Correa, Cristi and Oosterwijk  [4]) shows in some sense a “price of shortsightedness”. While instantaneous dynamic equilibria may be significantly less efficient than dynamic equilibria, in many situations this might be a price one has to pay as the full information needed for dynamic equilibria might just not be available.

Generally, it would be interesting to test the different equilibria on real instances and see how their efficiency compares there. A large-scale computational study seems more feasible for IDEs compared to dynamic equilibria, as already calculating a single $\alpha$-extension is much more difficult for the full information model, while it is easy for IDE flows using a simple water-filling procedure. Indeed, for calculating a single extension phase the only positive result for dynamic equilibria is based on a recent work of Kaiser [15] showing that for series-parallel graphs a single phase can be computed in polynomial time. The question of whether a finite number of such extensions is enough to compute a complete equilibrium flow is still open for dynamic equilibria, while we were able to answer this question positively for IDE flows in an upcoming paper [9].