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.

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\Re}{\mathrm{Re}} \newcommand{\Im}{\mathrm{Im}} \newcommand{\clos}[1]{\overline{#1}} \newcommand{\inte}[1]{\mathring{#1}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\small\raise{-1pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\tPmax}{\tau(P_{\max})} \newcommand{\PoA}{\mathrm{PoA}} \)
~WINE 2020~

The Price of Anarchy for Instantaneous Dynamic Equilibria


Lukas Graf1, Tobias Harks1
1 Augsburg University
v w x y z t

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

v w x y z t u_v = \Ind_{[-2,-1]} u_x = 3\cdot \Ind_{[-2,-1]} u_z = 2\cdot \Ind_{[-1,-0.5]}+7\cdot \Ind_{[-0.5,0]} q_{xt}(\theta)=2 q_{xt}(\theta)=1.5
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$.

k= 5 4 3 2 1 0 P_{\max} q_e(\theta) = U t

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

v t H G
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)

t cycling blocking
s t cycling blocking

Lower Bound

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

$\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