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

Chair for Discrete Mathematics, Optimization and Operations Research

Algorithmic Game Theory


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
v w x y z t

↑ 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