Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:About the Price of Anarchy for Flows over Time
Speaker:Tim Oosterwijk
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:Tim Oosterwijk received his PhD last January from Maastricht University. From March until August, he was a postdoc at the Universidad de Chile, and until February he is a postdoc here. His main research areas are algorithmic game theory and approximation algorithms. His research interests include, but are not limited to, the design and analysis of (approximation) algorithms, computational complexity, congestion games, flows over time, mechanism design, operations research and scheduling.
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 13 September 2018
Duration:30 Minutes
Building:E1 4
A major drawback of congestion games as well as static s,t-flows is the absence of the dimension of time: A player or a flow particle is either using a resource or an edge or it's not, disregarding the possibility that it's only using the resource or edge during a certain time interval. To study the actual flow dynamics in a network, the fluid queuing network is one of the most natural models to use. In this single-source single-sink network, every arc has a free-flow transit time, and a capacity that models the units of flow that can traverse the edge each unit of time. If the inflow exceeds the capacity, a queue is built.

Although the model has been defined decades ago, only recently results have been found regarding existence and characterization of equilibria, and one of the major open questions is to bound the price of anarchy for this model. Bhaskar, Fleischer and Anshelevich proved a Price of Anarchy of e/(e-1) if you are first allowed to decrease the capacity of all edges. In this talk I will introduce the model and the equilibrium behavior, and show that the Price of Anarchy is e/(e-1) if you can change only the capacity of the edge incoming to the source. We strongly believe the result is also true without this extra assumption, but at the moment that proof still eludes us.

This is based on joint work with José Correa and Andrés Cristi from the Universidad de Chile.

Name(s):Tim Oosterwijk
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Algorithmic Game Theory; Flows over Time; Equilibrium; Price of Anarchy
Attachments, File(s):

Tim Oosterwijk, 09/10/2018 04:07 PM
Last modified:
Uwe Brahm/MPII/DE, 09/13/2018 11:41 AM
  • Tim Oosterwijk, 09/10/2018 04:08 PM
  • Tim Oosterwijk, 09/10/2018 04:07 PM -- Created document.