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.

## Chair for Discrete Mathematics, Optimization and Operations Research

### Algorithmic GameTheory Prof. Tobias Harks

### PostDocs   Dr. Anja Schedel Dr. Meenarli Scharma Dr. Prashant Palkar

### PhD students   Michael Markl Julian Schwarz Lukas Graf
A game consists of
• 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.

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

# Dynamic Flows with Adaptive Route Choice

Lukas Graf1, Tobias Harks1, Leon Sering2

1 Augsburg University, 2 ETH Zürich    ## ↑ Discrete Model

(unsplittable flow particles, discrete time steps)

## Continuous Model ↓

(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}$  ### Physical Model

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

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

Questions: Existence? Computation? Hardness? Quality? ...?
Question: Do all agents eventually reach their destination?

## Termination?

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

## Termination?-Part II

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