Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

~WINE 2020~

# The Price of Anarchy for Instantaneous Dynamic Equilibria

Lukas Graf1, Tobias Harks1
1 Augsburg University     ## ↑ Discrete Model

(unsplittable flow particles, discrete time steps)

## Continuous Model ↓

(infinitesimal flow particles, continuous time)

### Physical Model

• A directed graph $G = (V,E)$
• Edge travel times $\tau_e \in \INs$ (here, mostly, $\tau_e=1$)
→ define $\tau \coloneqq \sum_{e \in E}\tau_e$
• Edge capacities $\nu_e \in \INs$ (here $\nu_e \in \Set{1,\infty}$)
• Single sink $t \in V$
• Network inflow rates $u_v: \IR \to \IR_{\geq 0}$
(finitely lasting, wlog last inflow at time $\theta = 0$)
→ define $U \coloneqq \sum_{v \in V}\int_{-\infty}^0 u_v(\theta) d\theta$
• Inflow $\gt$ capacity $\implies$ queues form
$f_e^+(\theta) \gt \nu_e$                       (length $q_e(\theta)$)

### Behavioral Model

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)

$\implies k=0,\theta=\tPmax+U$ yields:     $F_{\leq 0}(\tPmax+U) \geq U$.

## Upper Bound (General Networks)

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]$.

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)$.

$\bigO(U \tau)$

## Lower Bound

For $K,L \in \INs$ construct $G_{K,L}$ with $U \in \bigO(L3^K), \tau \in \bigO(3^{2K})$:
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)$.

$\Omega(U \log\tau)$

Lukas Graf
The PoA for IDE Flows - Introduction & Model Lukas Graf WINE 2020
The PoA for IDE Flows - An Upper Bound Lukas Graf WINE 2020
The PoA for IDE Flows - A Lower Bound Lukas Graf WINE 2020