Talks & activities

On the Price of Anarchy for Flows over Time

Activity: Talk or presentation (speaker at event)Talk or presentationAcademic

Associated researcher

27 Nov 2019

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.

Associated organisations

View graph of relations

Details

External organisation

NameUniversidad de Chile