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.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Tim Oosterwijk

--email hidden

passcode not visible

logged in users only

Algorithmic Game Theory; Flows over Time; Equilibrium; Price of Anarchy