On the Price of Anarchy for Flows over Time

Abstract: 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.

Date: Nov 27, 2019 at 02:30:00 h
Venue: Sala 33, Av. República 701.
Speaker: Tim Oosterwijkich
Affiliation: Maastricht U.
Coordinator: Prof. José Verschae
More info at:
Event website

Posted on Nov 25, 2019 in ACGO, Seminars