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}
\)

Prof. Tobias Harks

Dr. Anja Schedel | Dr. Meenarli Scharma | Dr. Prashant Palkar |

Michael Markl | Julian Schwarz | Lukas Graf |

A *game* consists of

**Questions:** Do equilibria exist? Can we compute them? What is there quality? ...?

- set of agents/players
- for each agent a set of strategies
- for each agent an "outcome"-function:

strategy choices of all agents $\mapsto$ utility/cost

An *equilibrium* is a strategy choice for every agents such that no agent can improve by unilateral(!) deviation.

(unsplittable flow particles, discrete time steps)

(infinitesimal flow particles, continuous time)

\(s_1\)

\(u_1 = \Ind_{[0,1]}\)

\(v_2\)

\(v_1\)

\(v_3\)

\(s_2\)

\(u_2 = 3\cdot\Ind_{[0,1]}\)

\(t_{{\color{blue}1}/{\color{red}2}}\)

\((\tau_e, \nu_e)\)

\(f_e^+(\theta)=3\)

\(q_e(\theta) = 2\)

\(q_e(\theta) = 1\)

\(c_e(\theta)=1 + \frac{2}{1}\)

\(c_e(\theta)=1 + \frac{1}{1}\)

- Directed (Multi-)Graph \(G = (V,E)\)
- For all edges \(e \in E\): length \(\tau_e \in \IN\) and capacity \(\nu_e\)
- Commodities \(I\) with source node \(s_i\), sink node \(t_i\)

and constant inflow rate \(u_i: [a_i,b_i] \to \IR_{\geq 0}\) - Inflow \(\gt\) capacity \(\implies\) queues form

\(f_e^+(\theta) \gt \nu_e\) (length \(q_e(\theta)\))

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

\(s_1\)

\(v_2\)

\(v_1\)

\(s_3\)

\(u_3 = 6\cdot\Ind_{[1.5,2]}\)

\(s_2\)

\(t\)

\(H\)

The sink can never be part of a cycle.

The total amount of flow in the network is bounded.

In single-sink networks all IDE flows terminate.

Let \(H \subseteq G\) be the subgraph consisting of

the sink and all edges leading towards the sink.

\(\implies\) Volume of flow in \(H\) eventually stays small.

\(\implies\) All queues in \(H\) are small.

\(\implies\) \(H\) acts as a new sink.

Add to \(H\) all edges leading into \(H\).

the sink and all edges leading towards the sink.

\(\implies\) Volume of flow in \(H\) eventually stays small.

\(\implies\) All queues in \(H\) are small.

\(\implies\) \(H\) acts as a new sink.

Add to \(H\) all edges leading into \(H\).

There exists a multi-sink network where all IDE flows cycle forever.

\(s_1\)

\(t_1\)

\(s\)

\(s\)

\(s\)

Dynamic Flows with Adaptive Route Choice
Lukas Graf

Dynamic Flows with Adaptive Route Choice - Model
Lukas Graf

Dynamic Flows with Adaptive Route Choice - Termination?
Lukas Graf