{'fraction_non_alphanumeric': 0.052276795703736854, 'fraction_numerical': 0.00950995748489595, 'mean_word_length': 3.5343056436271403, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Stackelberg Strategy for Routing Flow over Time

Routing games are used to to understand the impact of individual users' decisions on network efficiency. Most prior work on routing games uses a simplified model of network flow where all flow exists simultaneously, and users care about either their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of a user's traffic through the network. We attempt a more direct study of how competition affects network efficiency by examining routing games in a flow over time model. We give an efficiently computable Stackelberg strategy for this model and show that the competitive equilibrium under this strategy is no worse than a small constant times the optimal, for two natural measures of optimality.


Introduction
In routing games, players route a fixed amount of flow in a network. A player suffers a cost, which depends on its routing and the routing chosen by the other players. A flow in a routing game is an equilibrium flow if no player can choose a different routing and reduce its cost.
Routing games model a variety of problems, including routing on roads [3,32], computer networks [10,24,28], and scheduling tasks on machines [22]. For many measures of the quality of a routing, the equilibrium in routing games is known to be inefficient compared to a routing which optimizes the measure. This inefficiency is quantified by the price of anarchy [25]: the worst ratio of the objective evaluated for the equilibrium flow, to the optimal flow. There is considerable interest in obtaining bounds on the price of anarchy in routing games.
Players in a routing game have a bottleneck objective if a player's cost is the maximum delay on the edges it uses [5]. The bottleneck objective models applications where a player's cost depends largely on the performance of the worst resource it uses. This objective ignores the effect of delay on edges besides the bottleneck edge, which can lead to the counterintuitive situation where players fail to distinguish between two strategies which have the same bottleneck, but have considerably different delays. This behavior may result in an unbounded price of anarchy, e.g., [2,5,10]. In many of these bad instances, the price of anarchy would be 1 if player costs depended on edges besides the bottleneck edge. Models where a player takes into account the delays on all edges have an improved price of anarchy [10].
Even models where a player's cost is an aggregation of the cost on each edge assume that the flow is static: every edge has flow on it instantaneously and simultaneously and, once established, a flow continues indefinitely. However, the flow in networks is often transient. Flow enters a network, uses it for some time, and then exits, and the flow on an edge changes with time.
This time-varying nature of flows is captured by flows over time, introduced in [14]. In this model, flow traverses the path in finite time, and exits the network at the sink. Thus, the flow on each edge of the network varies with time. Every edge has a capacity which limits the flow rate on the edge.
We consider routing games for flows over time. Every player controls infinitesimal flow, and in contrast to previous models where users care about either their maximum delay or their total delay, in our model the cost of a player is the time at which it arrives at the sink. A player's strategy is a path from the source to the destination. On every edge, the flow follows first-in, first-out (FIFO). While the network is capacitated, the model allows the inflow on an edge to be larger than the capacity of the edge ‡ . The excess flow forms a queue at the tail of the edge, and must wait for the preceding flow to exit before it can exit the edge. Although the capacities and the edge-delays are fixed, the total delay on an edge varies with the size of the queue on the edge. The queue size seen by flow arriving at the edge varies with time; hence the total delay along any path varies with time. This game, which we call a temporal routing game, follows the model of selfish routing of flows over time used in [20]. The model possesses a number of interesting characteristics. It follows FIFO, which is a standard assumption in traffic routing literature. The model is based on dynamic queueing, first used in [33]. ‡ Thus, unlike the static flow model considered in [11], the ability to reduce capacities is not sufficient to enforce the optimal flow. Further, the equilibrium flow over time can be characterized in terms of special static flows [20], described in §2.
In flows over time, similar to static flows, various objectives may be used to compare the performance of the equilibrium flow to the optimal flow. A natural objective is the total delay: the sum of the costs of the players. The flow which minimizes the total delay is the earliest arrival flow, which maximizes the flow that arrives at the destination by time θ, for every time θ. We call the ratio of the total delay of the worst equilibrium flow to the total delay of earliest arrival flow the total delay price of anarchy. A different objective is the time taken to route a fixed amount of flow to the sink. This is called the completion time, and is minimized by a quickest flow. The earliest arrival flow is also a quickest flow. The ratio of the time taken by the worst equilibrium flow, to the time taken by the quickest flow to route a fixed amount of flow is called the time price of anarchy. A third objective is the amount of flow that reaches the destination by time θ. The ratio of amount of flow which reaches the destination by time θ in the worst equilibrium flow to the amount of flow which reaches the sink in the earliest arrival flow is called the evacuation price of anarchy.
In the Stackelberg model introduced in [31], different players in a game have different priorities. A leader picks a strategy first, and then the followers pick their strategies. Importantly, the leader commits to a strategy before the followers pick theirs. In their 1982 book on noncooperative game theory [6], Basar and Olsder describe a general form of Stacklberg games where players may have different strategy spaces. We embrace this general definition. In our setting, the network manager is the leader. Given some physical limit on the capacity of each edge, the network manager acting as leader picks a capacity for each edge which does not exceed this physical limit. The remaining players, acting as followers, then pick a route from source to sink as their strategy.
Our Contribution. We study the equilibrium flow in temporal routing games. We show that small constant bounds on the efficiency loss of equilibrium flow in temporal routing games can be enforced. In particular, • We give a polynomial-time computable Stackelberg strategy to enforce a bound of e/(e − 1) on the time price of anarchy in temporal routing games; and • We show the same strategy also enforces a bound of 2e/(e − 1) on the total delay price of anarchy.
The strategy we describe is based on the following key result.
• In temporal routing games where the edge capacities satisfy certain properties with respect to the quickest flow, the time price of anarchy is bounded by e/(e − 1).
The bound of e/(e − 1) on the time price of anarchy stated above is tight, as there is a matching example in [20]. Our results are in sharp contrast to two previous results. In [20], the authors show that the evacuation price of anarchy is Θ(log n), where n is the number of vertices. Further, [23] considers the maximum time taken by any player to travel through the network. They show that for this objective, the price of anarchy is Ω(n).
We restrict our analysis to single-source, single-sink networks with constant inflow. In this case, the quickest flow is known to be a temporally repeated flow (see §2). There are variable inflows for which this is not true. Equilibrium for temporal routing games with a single source and single sink exist [20]. Further, in settings with constant inflow, they can be described in terms of static flows with special properties [20]. These properties are crucially used in our proofs.

Related Work.
For selfish routing of static flows, the literature is vast; see [7,26,32] for early results on the equilibrium in selfish routing. The term price of anarchy was first used in [25] to describe the efficiency loss caused by the absence of a controlling authority. Since then, the price of anarchy has been widely used as a measure of how system performance degrades if resources are used selfishly. For results on the price of anarchy for static flows, see [28].
Stackelberg strategies have been used in computer science literature to manage the efficiency loss at equilibrium [21,27,29]. Here, the network manager is a player with flow which she routes with the objective of reducing efficiency loss. Coordination mechanisms, introduced in [8], refer to a choice of system parameters by the designer to influence equilibria. The term is used to describe situations both where the system parameters are chosen before the market power of the players is known, and where the market power of the players is known beforehand. In the latter situation, this concept fits within the notion of a Stackelberg game as defined by Basar and Olsder [6]. Our approach in this paper may also be viewed as a coordination mechanism with the market power of players known. Coordination mechanisms and related results are further discussed in [9].
Ford and Fulkerson [14] introduce flows over time. They consider the problem of maximizing the amount of the flow which can be sent from a source s to a destination t by a given time T ; the flow which achieves this is called the maximum dynamic flow. A related problem is the quickest flow problem: find the dynamic flow which routes a fixed amount of flow M from s to t in minimum time. The earliest arrival flow problem generalizes the maximum flow and the quickest flow problems. For a single source and destination, earliest arrival flows exist [15], however the flow over time obtained may have a description of size exponential in the size of the input [34]. These and other problems on flows over time are considered in [12,13,17,18,19].
Temporal routing games are analyzed by Koch and Skutella in [20] and are based on deterministic queueing models used earlier in traffic simulation [30,33]. The authors in [20] show that if all edges have zero delay, the time price of anarchy is 1. In contrast, they show the evacuation price of anarchy is Θ(log n). Macko et al. study the existence of Braess's paradox in temporal routing games [23]. They show that the maximum delay suffered by any player can be arbitrarily worse than for an optimal flow over time which minimizes the maximum delay. Anshelevich and Ukkusuri [4] analyze a different discrete-time model of selfish routing. In their model, the delay of an edge e at any timestep t is a function of the flow entering the edge at t and the history of the edge, which is an encoding of the flow entering the edge in timesteps before t. However, in their model, edges are uncapacitated; and in instances with multiple sources and sinks, the equilibrium may not exist. In single-source, single-sink instances an equilibrium exists and can be computed efficiently. However the time price of anarchy may be large. Hoefer et al. [16] consider a different model where they consider flow controlled by players as tasks and edges as machines. A player's task corresponds to a significant amount of flow, rather than infinitesimal as in the models discussed previously, and must be routed on a single path.

Model, Notation and Definitions
Let G = (V, E) be a directed acyclic graph with two special vertices s and t called the source and sink. Each edge in the graph has a nonnegative capacity c e and a nonnegative edge-delay d e . An s-t path in the graph is a sequence of edges (v 0 , w 0 ), . . . , (v l , w l ) such that v 0 = s, w l = t, w i = v i+1 and v i = v j for i = j. We abuse notation slightly and define d p := e∈p d e for any path p.
Static Flows. In a directed graph G = (V, E) with capacities c e on the edges and source s and sink t, a static flow f is an assigment of nonnegative values f uv that satisfy f uv = 0 for (u, v) ∈ E and capacity constraints (1) and flow conservation (2) The value of a static flow f is |f | = v f sv . A path flow f p on a path p is a flow on p of value |f p |. For an acyclic graph, a static flow f can be decomposed into the sum of path flows on a set of paths P so that f e = p∈P:e∈p |f p | [1]. We use f = {f p } p∈P to denote a flow decomposition of flow f , where P is the set of paths with strictly positive flow.  (4):

Flows over Time. A flow over time is denoted
∀θ ∈ R + The net flow rate leaving s and entering t must be positive.
. The rate of flow entering an edge f + e (θ) may be larger than the capacity of the edge. In this case, the excess flow forms a queue at the tail of the edge and must wait for the flow before it in the queue, before it starts traversing the edge. Define the total flow entering and exiting edge e by time θ to be F + e (θ) = θ 0 f + e (ν)dν and F − e (θ) = θ 0 f − e (ν)dν respectively. The edge-delay d e is the time taken by flow to traverse the edge if there is no queue on the edge. Then ∀e ∈ E, θ ∈ R + , To ensure that flow entering an edge at any time also leaves the edge after finite time, the flow over time must satisy, ∀e ∈ E, θ ∈ R + , The queuing-delay q e (θ) on edge e at time θ is the minimum time flow entering the edge at time θ must wait before it starts traversing the edge: When flow leaves the queue, the time taken to traverse the edge is the edge-delay d e . The total-delay at e of flow entering edge e at time θ is d e + q e (θ). By (9), flow entering an edge at time θ must allow all the flow which entered earlier to exit the edge before it can exit, hence flow on an edge follows FIFO.
Flow enters the graph at the source s at a constant rate c 0 . The total amount of flow to be routed to the sink is M . The completion time is the time when M units of flow arrive at the sink.
Optimal Flows Over Time. The maximum flow-over-time problem with time horizon T is to maximize the amount of the flow sent from s to t by time T . Ford and Fulkerson [14] show that the maximum dynamic flow can be obtained in polynomial time by computing the static flowf which maximizes (T + 1)|f | − e d efe . Thusf is a minimum cost static flow with the cost of edges being the edge-delays. For a flow decomposition {f p } p∈P off , the maximum dynamic flow sends flow at rate |f p | along path p from time 0 to T − d p . Such a dynamic flow, obtained by repeating a static flow over time, is called a temporally repeated flow. For a maximum dynamic flow, we call the static flow repeated over time the underlying static flow.
The quickest flow problem for flow M is to find the flow over time which minimizes the time taken to send M units of flow from s to t. The quickest flow problem can be solved by a binary search to find the minimum time T for a maximum dynamic flow to route at least M units of flow. Thus, the quickest flow problem can be solved by a temporally repeated flow.
The earliest arrival flow problem is to find a flow over time which maximizes the flow that arrives at the destination by time θ, for every time θ. An earliest arrival flow is also a maximum flow-over-time and a quickest flow, but the converse may not be true. Thus, the earliest arrival flow may not be a temporally repeated flow. For a single source and destination, earliest arrival flows exist [15].
Temporal Routing Games. The tuple Γ = (G, s, t, c, d, c 0 , M ) forms an instance of the temporal routing game. Every player in this game controls infinitesimal flow. A player's cost is the time its flow arrives at the sink. A player's strategy is a path from s to t. We assume an arbitrary ordering on the players which corresponds to the order in which their flow arrives at the source. Lemma 1 ([20]). For any edge e ∈ E, the function θ + q e (θ) is monotonically increasing in θ.
By (9), the earliest time that flow entering an edge at time θ can exit the edge is θ + d e + q e (θ). It follows from Lemma 1 that in a temporal routing game, flow does not wait on an edge unless the edge has a queue. Equilibrium Flow. Informally, a flow over time is an equilibrium flow if every player minimizes its cost, given the strategies of the other players. To formalize this, for every vertex v the label function l v (θ) is the earliest time that flow starting from s at time θ can reach v. Thus l s (θ) = θ, and From Lemma 1 and the definition of the label functions: Lemma 2. For each node v ∈ V , the function l v is monotonically increasing and continuous.
For a fixed θ and given the queues on the edges, the labels on all the vertices can be found in the following manner: l s (θ) = θ and l v (θ) = ∞ for v = s. Then n − 1 times, for each e = (u, v) ∈ E set l v (θ) = min{l v (θ), l u (θ) + d uv + q uv (l u (θ))}. The correctness of the labels obtained after n − 1 repetitions follows from the correctness of the Bellman-Ford algorithm.
The shortest-path network at time θ, G θ , is the subgraph induced by the set of edges Flow is sent over current shortest paths if for every edge (u, v) ∈ E and for all θ ∈ R + , if l v (θ) < l u (θ) + d e + q uv (l u (θ)) then f + e (l u (θ)) = 0.  Every temporal routing game has an equilibrium [20]. For a temporal routing game Γ, (f + (Γ), f − (Γ)) is the equilibrium flow, and EQ(Γ) is the completion time of the equilibrium flow. If the instance is clear from context, we simply use (f + , f − ) and EQ.
Price of Anarchy. In this paper we consider two separate objectives. In Section 4 and Section 6, our objective is to minimize the completion time. For this objective, the optimal flow is a quickest flow. Since a quickest flow can be represented as a temporally repeated static flow, we usef (Γ) to denote the underlying static flow for the quickest flow for a temporal routing game Γ, andT (Γ) to denote the completion time of the quickest flow. The time price of anarchy is then defined as max Γ EQ(Γ)/T (Γ). If the instance is clear, we usef to refer to the underlying static flow andT for the completion time.
We say the static flow underlying the quickest flow saturates every edge of the graph if for all e ∈ E, f e = c e and vf sv = c 0 . We show that if this condition holds, then the price of anarchy is small.
Instead of flow entering the graph at the source s at a constant rate c 0 , another way to think of the model is that all flow is present at the same time at a node s ′ , and there is an initial edge (s ′ , s) of capacity c 0 and delay 0. Then the arrival time at t for a player is also its delay. In Section 5, the objective is to minimize the total delay of a flow over time which routes a fixed amount of flow M from the source to the destination. The total delay of a flow over time in a temporal routing instance is the sum of the arrival times at t of the players. For a flow (f + , f − ) and instance Γ with completion time T , the total delay D((f + , f − )) = T 0 f + t (θ)θdθ. In this case the earliest arrival flow is the optimal flow since it maximizes the flow at t at every time θ. For a temporal routing game Γ, let (g + (Γ), g − (Γ)) be the earliest arrival flow. The total delay price of anarchy is defined as max Γ D(f + (Γ), f − (Γ))/D(g + (Γ), g − (Γ)).
In the appendix, we give an example of a temporal routing game and its equilibrium flow.

The Structure of Equilibria
Equilibria in temporal routing games can be characterized in terms of static flows with certain properties, called rate flows. We use the properties of rate flows to obtain our bounds on the price of anarchy. In this section, we introduce some of these properties, as well as an algorithm for computing equilibria. Both rate flows and the algorithm we discuss are described in [20].

Rate Flows.
For edge e = (v, w) ∈ E and time θ ∈ R + , define x + e (θ) := F + e (l v (θ)) and x − e (θ) := F − e (l w (θ)). Let x e (θ) := x + e (θ). At equilibrium, it follows by integrating (4) over time and from Theorem 4 that for every θ ∈ R + , x e (θ) is a static flow in the uncapacitated network G. For θ such that x(θ) is differentiable, For any time θ, the flow x(θ) given by x e (θ) on every edge is called the static flow underlying the equilibrium flow. Let x ′ e (θ) := dxe(θ) dθ where the differential exists. The following theorem describes some properties of x ′ (θ). For θ ∈ R + , define E 1 (θ) := {(v, w) ∈ E : q vw (l v (θ)) > 0} as the set of edges which have positive queues on them at time θ.

Theorem 5 ([20]). For an equilibrium flow in a temporal routing game
Then (x ′ e (θ)) e∈G θ is a static flow of value c 0 in the uncapacitated graph. Further, the static flow (x ′ e (θ)) e∈G θ satisfies The static flow (x ′ e (θ)) e∈G θ is called a rate flow. By (10), x ′ vw (θ) exists iff l ′ v (θ) and l ′ w (θ) exist. If at times θ and θ ′ ∈ R + the shortest-path networks and the set of edges with positive queues are the same, i.e., G θ = G θ ′ and E 1 (θ) = E 1 (θ ′ ), then the rate flow x ′ (θ) and l ′ v (θ) satisfy the conditions of Theorem 5 at time θ ′ as well.
Computing Equilibria. In [20], the authors describe an algorithm to compute equilibrium flow. The algorithm divides the time from θ = 0 to θ = M/c 0 into a number of phases, with phases divided by events. Note that θ = M/c 0 is the time the last flow leaves the source; the time this flow reaches the sink is the completion time. An event can be of two kinds. A queue-event occurs at time θ if for some edge e = (u, v), the queue decreases to zero at time l u (θ). That is, the queueing delay q e (l u (θ)) = 0 and for some δ > 0 and every 0 < ǫ ≤ δ, q e (l u (θ − ǫ)) > 0. A path-event occurs at time θ if some edge e = (u, v) enters the shortest-path network at time θ, i.e., l v (θ) = l u (θ) + d e + q e (l u (θ)) and for some δ > 0 and every 0 < ǫ ≤ δ, l v (θ) > l u (θ) + d e + q e (l u (θ)). Queue events and path events are collectively termed events. Note that in determining the time an event occurs, we are using the source as a frame of reference. While the event actually occurs at a later time θ ′ , we say an event occurs at time θ if flow leaving the source at time θ reaches the tail of the edge in the queue-event or path-event at time θ ′ .
For a given instance, we order the events occurring in an equilibrium flow by the time of the occurrence (using the source as the frame of reference) and index them, starting from 0 to r. The event r is a special event, corresponding to the last flow leaving the source, thus the equilibrium flow ends at event r. We define θ i as the time event i occurs, and τ i := l t (θ i ). Thus, θ r = M/c 0 and τ r = EQ.
A phase is the time interval between two events. Phase i as the time between events i − 1 and i. Thus, time θ is in phase i if θ i−1 < θ < θ i . We exclude the event times θ i since the vertex labels are l v (θ) and the static flow x(θ) are not differentiable at these times. Within a phase, the shortest-path network and the set of edges with queues on them remain constant. Hence the rate flow x ′ (θ) and the rate of change of vertex labels l ′ v (θ) exist and are fixed for θ within a phase. The first phase, phase 1, is the time between θ 0 = 0 and θ 1 . Thus, for a phase i, we define the following notation: • G i denotes the shortest-path network in phase i.
•c i is the capacity of the shortest path network in phase i.
• △ i is the change in capacity of the shortest path network when event i occurs, thus △ i =c i −c i−1 .
Note that △ i = 0 if event i − 1 is a queue event, or i − 1 is a path event but the capacity of shortest path network does not change; this could happen if a minimum cut is unaffected by the edge added to the shortest path network in a path event.
Since the rate of change of vertex labels l ′ v (θ) is fixed for θ within a phase, the vertex labels l v (θ) are fixed linear functions of θ within a phase; and thus within a phase l ′ v is well-defined for all v. Thus, we can define: • We use x ′ i to denote the rate flow in phase i.
For the notation above, if the phase is clear from context, for simplicity we omit the phase. Thus the rate flow would be denoted by x ′ .
For edge (v, w) in the shortest path network at time θ, q ′ vw (θ) : Since the rate of change of the vertex labels is constant, we define for phase i: • For an s-t path p, we abuse notation slightly to define q i p ′ := e∈p q i e ′ .

A Stackelberg Strategy for the Time Price of Anarchy
In Section 6, we prove our main technical result: In general instances of the temporal routing game where the rate of equilibrium flow may exceed the optimal flow on some edges, a bound on the time price of anarchy is unknown. However, in any temporal routing game, we show how to use Theorem 6 to obtain a simple Stackelberg strategy to enforce a bound of e/(e − 1) on the price of anarchy. The Stackelberg strategy is then as follows. The network manager, acting as the leader, reduces the capacity on each edge so that the new capacities c ′ are the value of the static flow on each edge in Γ: c ′ e =f e . It is easy to see that the quickest flow remains unchanged; further on each edge with the modified capacities,f e saturates every edge. By Theorem 6, the price of anarchy is now bounded by e/(e − 1).
Thus in any instance of the temporal routing game, by reducing the capacity of edges, the completion time of equilibrium flow can be bounded by e/(e − 1) times the completion time of the optimal flow.

The Total Delay Price of Anarchy
We now obtain bounds on the total delay price of anarchy of temporal routing games. The total delay price of anarchy is the maximum over all instances, of the ratio of total delay of the equilibrium flow to the minimum total delay. Since the cost of a player is the time it arrives at the sink, for a flow over time (f + , f − ) with completion time T the total delay D((f + , f − )) = T 0 θ f + t (θ)dθ. We first show that in temporal routing games which satisfy the same assumption as in Theorem 6, the total delay price of anarchy is bounded by a small constant.
Theorem 8. For a temporal routing game where the static flow underlying the quickest flow saturates every edge of the graph, the total delay price of anarchy is 2e/(e − 1).
The following lemma gives a lower bound on the total delay of the earliest arrival flow. The proof, and all missing proofs, are given in the appendix.
The result now follows from (11) and Lemma 9.
Similar to the proof of Theorem 7, Theorem 8 can be used to give a Stackelberg strategy for enforcing a bound of 2e/(e − 1) on the total delay price of anarchy in any general instance.

The Time Price of Anarchy
In this section, we prove Theorem 6. We assume that on every edge,f e = c e . For a path decomposition {f p } p∈P off along paths p ∈ P, by our assumption, p∈Pf p = c 0 .
Conceptually, we show that for an instance Γ of the temporal routing game, the ratio of EQ toT is worst if every event either occurs at time 0, or occurs at a fixed time µ. Thus, we modify an instance Γ to obtain an instance Γ ′ where every event either occurs at time 0 or time µ. We then obtain a bound on EQ T in this simpler instance.
This conceptual view is simplified; it may not always be possible to preserve the events if we insist on every event occuring at either time 0 or time µ. However, we show a bound on EQ T can be obtained in Γ by following the same steps analytically: Step 1: For any path p, get a lower bound on d p in terms of {θ i } r i=0 and the queues on the path p (Lemma 14).
Step 2: Use the bound in step 1 to obtain an upper bound on EQ T in terms of the event times {θ i } r i=0 and the queues on the edges (Lemma 15 and Corollary 16).
Step 3: Show that there is some event k ≤ r so that if all the events before and including k happen at time 0, and all events after k occur at the same time, then the upper bound on EQ T in this modified instance also bounds EQ T in the original instance (Lemma 17).
Step 4: Evaluate the upper bound on EQ T for this modified, simpler instance (Lemma 18 and Theorem 6). Our first step is to show a relation between the label on t and the rate of flow into t.

Lemma 11
. Let (f + , f − ) be the equilibrium flow for a temporal routing game Γ with inflow c 0 and corresponding labels l. Then We first show Lemma 11 for a path in the graph, and then use path decompositions of x ′ (θ) in conjunction with (10) to get the result. .
Proof of Lemma 11. Let x ′ and l ′ v be the rate flow and rate of change of labels at time θ. Let {x ′ p } p∈P be a path decomposition of x ′ where P is the set of paths with positive flow. Instead of the graph G = (V, E), we consider the equilibrium flow in a graphḠ = (V,Ē) withĒ = E × P. Every edge a ∈Ē corresponds to a pair (e, p) with e ∈ E and p ∈ P, with capacity c a = c e x ′ p x ′ e and delay d a = d e . We obtain an equilibrium flow inḠ and show that the labels on the vertices at any time φ are the same in G andḠ.
Define a modified flow over time ce . Thus, q a (φ) = q e (φ) via (9). Since d a = d e and l s (φ) = φ, it follows that the labels on the vertices inḠ for the flow over time (f + ,f − ) are equal to the labels on the corresponding vertices in G for the equilibrium flow (f + , f − ), for every time φ ∈ R + . It is easy to verify the conditions for equilibrium flow in Definition 3 for We show that at time θ, l ′ t = c 0 f + t (lt(θ)) in H. Since the node labels are the same for (f + , f − ) and (f + ,f − ), and f + v (φ) =f + v (φ) for every vertex v and time φ ∈ R + , this proves the lemma. Since (f + ,f − ) is an equilibrium flow inḠ, the flow y ′ with y ′ e = x ′ e ca ce is a rate flow in graphḠ at time θ. Consider a path p ∈ P; there is a corresponding s-t path q inḠ consisting of all the edges which correspond to path p. By our construction, on every edge a of path q, y ′ a = x ′ p . On consecutive edges (u, v), (v, w) in q, y ′ uv = l ′ vf − uv (l v (θ)) and y ′ vw = l ′ vf + vw (l v (θ)). Since y ′ uv = y ′ vw , it follows thatf − uv (l v (θ)) =f + vw (l v (θ)). Then by Lemma 12, l ′ tf − v k t (l t (θ)) =f + sv 1 (l s (θ)). Since this is true for all paths p ∈ P, we can sum over all these paths to obtain l ′ Figure 2: An instance of a temporal routing game Lemma 17 is used to partition the events into two sets, with events in the first set occurring at time θ = 0 and events in the second set occurring at time θ r : Lemma 17. For 0 ≤ i ≤ r and λ i , y i ∈ R, if 0 ≤ y 0 ≤ y 1 ≤ · · · ≤ y r , then r i=0 λ i y i ≤ y r max k r i=k λ i .
By Lemma 17, ∃k ≤ r : r i=0 λ i τ i ≤ τ r i≥k λ i . Then since τ r = EQ, substituting in Corollary 16, Evaluating i≥k λ i , we obtain i≥k λ i =c r − c 0 if k = 0 and i≥k λ i =c r − c 0 +c k c 0 (13) becomesT EQ ≥c r c 0 − 1 c 0 (c r − c 0 ) = 1 and hence in this case,T = EQ. If k > 0, since by assumption, c e =f e on every edge. Proof of Theorem 6. Let w =c k /c 0 . Then from (14) and Lemma 18,T EQ ≥ 1 − w ln 1 w . Let z = w ln 1 w , then z is maximized when w = 1/e. Hence,T EQ ≥ 1 − 1/e = e−1 e . Observing thatT EQ is the inverse of the price of anarchy, completes the proof.
Note that we did not use any properties of the optimal flow over time in our proof. Instead of the optimal flow over time, we could obtain the same results for any temporally repeated static flow, withf being the static flow.

A An Example
We present a brief example to demonstrate an equilibrium flow over time. For the temporal routing game in Figure 2, M = 5.5, c 0 = 3, and each edge is marked (c e , d e ). In the example, the equilibrium flow is calculated as follows. Given the shortest-path network and the set of edges with queues at the start of a phase, we choose the rate low x i ′ so that there exist labels l i v ′ which satisfy the conditions of Theorem 5.
Given the rate flow x i ′ and the vertex labels l i v ′ within a phase, the equilibrium flow within the phase can be obtained by (10). A phase ends when either a path event or queue event occurs, or there is no more flow at the source.
In Phase 3 all the edges are in the shortest path network. The queues do not change on any edge, and this phase continues until the completion time. In this phase x ′ e 1 = 2, x ′ e 2 = x ′ e 3 = 1, and x ′ e 4 = 1. On all vertices, the labels l ′ v = 1. The rate of flow arrival at the sink as a function of time for this example is plotted in Figure 3. θ g + t (θ) + (T − θ) g + t (T − θ) ≥ T /2 (g + t (θ) + g + t (T − θ)).

C Proofs from Section 5
Proof of Theorem 10. The strategy for enforcing an equilibrium flow over time of total delay at most 2e/(e − 1) times the total delay of the earliest arrival flow in general graphs is now exactly the algorithm described in the proof of Theorem 7. In particular, for an instance Γ instead of looking at the earliest-arrival flow which may have an exponential-sized description, we only need to consider the quickest flow which can be computed in polynomial time. The network manager, as the leader, then reduces the capacities of every edge to equal the flow on the edge in the static flow underlying the quickest flow. By Theorem 8, the equilibrium flow obtained following the action of the leader has total delay at most 2e/(e − 1) times the minimum total delay of any flow in the original instance.

D Proofs from Section 6
Proof of 12. Let x ′ and l ′ denote the rate flow and rate of change of vertex labels at time θ. For consecutive edges (u, v), (v, w) in p, x ′ uv = l ′ v f − uv (l v (θ)) and x ′ vw = l ′ v f + vw (l v (θ)) by (10). From the conditions of the lemma, it follows that x ′ uv = x ′ vw , and hence x ′ e = f + sv 1 (θ) for every edge in the path. The proof is by induction on the size of the path. For the base case, p is a single edge e = (s, v). If e has a queue on it at time θ, then f − e (l v (θ)) = c e and l ′ v = x ′ e /c e = f + sv (θ)/f − e (l v (θ)), and hence the lemma is true. If e does not have a queue, l v (θ) = l s (θ) + d e , and hence l ′ v = l ′ s = 1. Since if e does not have a queue f − e (l v (θ)) = f + e (θ), the lemma is true for the base case. Let p = (s, v 1 , v 2 , . . . , v k ) be a path in G θ of length k and let e = (v k−1 , v k ). If e has a queue on it at time l v k−1 (θ), then f − e (l v k (θ)) = c e and l ′ v k = x ′ e /c e = f + sv 1 (θ)/f − e (l v k (θ)). If edge e does not have a queue on it, where the second equality follows from the inductive hypothesis. By the conditions of the lemma, f − v k−2 v k−1 (l v k−1 (θ)) = f + e (l v k−1 (θ)). Since edge e does not have a queue on it, f + e (l v k−1 (θ)) = f − e (l v k (θ)), and hence l ′ v k = f + sv 1 (ls(θ)) f − e (lv k (θ)) .
Proof of Corollary 16. From Lemma 14 and observing that pf p = c 0 , and by rearranging terms, p∈Pf proving the lemma.
Proof of Lemma 18. Since we now concentrate on a single phase k, we simplify notation and use x ′ e , l ′ v and q ′ e to denote the rate flow, rate of change vertex labels and rate of change of queue in phase k. E 1 denotes the set of edges with strictly positive queues at the start of phase k. By definition for an edge e = (v, w), q ′ e = l ′ w − l ′ v if e is in the shortest path network and q ′ e = 0 otherwise. Thus c e q ′ e = x ′ e (1 − l ′ v l ′ w ) since if e is not in the shortest-path network, q ′ e = x ′ e = 0. If e is in the shortest-path network and q ′ e = 0, l ′ v = l ′ w , and if q ′ e = 0, e ∈ E 1 and hence x ′ e = c e l ′ w . Thus e c e q ′ e = e=(v,w) x ′ e 1 − l ′ v l ′ w . Let {x ′ p } p∈P be a path decomposition of x ′ . Then