On the Price of Anarchy for Flows over Time

Description

Dynamic network flows, or network flows over time, constitute an important model for real-world situations where steady states are unusual, such as urban traffic and the Internet. In order to describe the temporal evolution of such systems one has to consider the propagation of flow across the network by tracking the position of each particle along time. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective.

In this talk I will discuss dynamic equilibria in the deterministic fluid queuing model in single-source single-sink networks, arguably the most basic model for flows over time. I will then present the main ideas behind the result that if we could reduce the inflow of the network in a dynamic equilibrium, then the Price of Anarchy is bounded by a factor, parameterized by the longest path length, that converges to e/(e-1) = 1.582. I will mention some other results we found and finish with some intriguing open questions.

This is joint work with José Correa and Andrés Cristi.

Period	27 Nov 2019
Held at	Universidad de Chile, Chile
Degree of Recognition	International