Gastvortrag: Computation and Improvement of Wardop Equilibria with Unknown Demands

Mittwoch, 30.01.2019, 15.00 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9222

 

Vortragender: Max Klimm 

Abstract: Wardrop equilibria are a fundamental solution concept for selfish flows that captures among others the behavior of road and Internet traffic. In the basic model, we are given a graph with fixed demands between pairs of nodes and edges with flow-dependent cost functions. A multi-commodity flow is a Wardrop equilibrium if each flow particle is routed on a cheapest path from its source to its destination. While for given flow demands, the computation of Wardrop equilibria and their basic properties are well understood, in many scenarios the actual demands are uncertain putting the existing theory under scrutiny. In the first part of the talk, we develop an algorithm that computes all Wardrop equilibria in a given graph with piece-wise linear cost functions as a function of the flow demand. The algorithm is output-polynomial and performs computationally cheap Simplex-like pivot steps in non-degenerate instances. In the second part of the talk, we discuss the limitations of marginal cost pricing for instances with unknown demands. We show that when the flow demand is not known marginal cost pricing may actually decrease the performance of the flow. We characterize instances where optimal tolls can be found even when the flow demand is unknown and show how to compute them. (The first part of the talk is joint work with Philipp Warode and the second part is joint work with Riccardo Colini-Baldeschi and Marco Scarsini.)