The current travel time at time \(\theta\) on edge \(e\) is: \[c_e(\theta) := \tau_e + q_e(\theta)/\nu_e\]
A flow is in Instantaneous Dynamic Equilibrium (IDE) if the following holds: Whenever positive flow enters an edge, this edge must lie on a currently shortest path towards the respective sink (w.r.t. \(c\)).
Price of Anarchy (PoA)
The termination time of a flow $f$ is defined as
\[\Theta(f) \coloneqq \inf\Set{\theta \geq 0 \,|\, \style{font-family:inherit;font-size:130%;}{\text{total flow volume in }}G\style{font-family:inherit;font-size:130%;}{\text{ is }}0}.\]
For given $U, \tau \in \IN$ we define the Price of Anarchy (PoA) by
\[\PoA(U,\tau) \coloneqq \sup\Set{\frac{\Theta(f)}{\Theta(f^{\mathrm{OPT}})}},\]
where the supremum is over all networks with total flow volume $U$, total edge travel time $\tau$ and all IDE $f$.
Question: What is the termination time/PoA of IDE in single-sink networks?
Upper Bound
Lower Bound
Upper Bound (Acyclic Networks)
Any IDE in an acyclic network $G$ terminates before $\color{red}\tPmax$$+\,\,\color{DodgerBlue}U$, where $\tPmax \coloneqq \max\Set{\sum_{e \in P}\tau_e \,\Big|\, P \style{font-family:inherit;font-size:130%;}{\text{ a source-sink path}}}$and $U \coloneqq \sum_{v \in V}\int_{-\infty}^0 u_v(\theta) d\theta$.
For any $k = \tPmax, \tPmax -1, \dots, 1, 0$ and any time $\theta$ define
$F_{\leq k}(\theta) \coloneqq$ total volume of all flow particles with pessimistic distance at most $k$ to $t$ at time $\theta$
Then $F_{\leq k}(\theta) \geq \min\Set{U,\theta-(\tPmax-k)}$ (by induction)
Any IDE in an acyclic network $G$ terminates before \(\tau_{\max}+U\).
Without queues IDE flows only use a static acyclic subgraph.
With only small queues IDE flows only use a static acyclic subgraph.
A subgraph \(H \subseteq G\) containing the sink \(t\) as well as all its shortest paths towards $t$
is a sink-like subgraph for some interval \([a,b]\) if the sum of
current flow volume within \(H\) at time $a$ and
the cummulative inflow into \(H\) over \([a,b]\)
is at most \(\frac{1}{2}\).
Let $H$ bis sink-like on $[a,b]$ and \(v \in G\setminus H\) be closest to \(t\).
Then \(H+v\) is sink-like for $\Big[a,b-\,$$\sum_{e \text{ edge between } v \text{ and } H}(\tau_e + \frac{1}{\nu_e})$$\Big]$.
vtHG
In single-sink networks any IDE terminates before $4U\tau$.
If \(H := \{t\}\) is sink-like for \([\theta,\theta +\tau+|E|]\) then $H \coloneqq G$ is sink-like for $[\theta,\theta]$and the flow terminates. \(\implies\) The sink has inflow of at least \(\frac{1}{2}\) all \(2\tau\) time steps.
In single-sink networks \(G\) the PoA for IDE flows is in \(\bigO\left(U\tau\right)\).
t
$\bigO(U \tau)$
Lower Bound (Idea)
tcyclingblocking
stcyclingblocking
Lower Bound
For $K,L \in \INs$ construct $G_{K,L}$ with $U \in \bigO(L3^K), \tau \in \bigO(3^{2K})$:
sstC_KB_K
In $G_{K,L}$ there exists an IDE flow which terminates after $LK(3^{K+1}+1)$.
For single-sink instances with parameters \(U\) and \(\tau\) the Price of Anarchy is in \(\Omega(U\log\tau)\).