Parametric computation of equilibria and flows

Network flows can be used to model numerous real world applications, such as flows in physical networks like electrical, gas, or water networks, flows in traffic networks, or flows of goods in logistic networks. More precisely, many of these applications can be modeled either as minimum cost flows or equilibria of network games, sometimes even both. In this thesis, we study the computational complexity of computing these flows and develop algorithms solving this task. In contrast to the basic static flow models that are widely studied in the literature, we mainly focus on parametric flow models. In particular, we consider settings where the demands, i.e., the external in- and outflow rates, are parametrized by a one-dimensional value. The solution to a parametric flow problem is no longer one static flow but a function mapping the parameter to a static flow satisfying the respective demands. The parametric model allows to analyze the sensitivity of static flows with respect to the in- and outflow. This thesis is subdivided into two parts. The first part is concerned with the minimum cost flow problem with convex costs, with and without parametric demands. We characterize optimal solutions via optimal potentials, analyze the parametric minimum cost flows and its derivatives, and develop an output-polynomial algorithm that can compute solution functions to the parametric minimum cost flow problem for piecewise quadratic cost functions. We extend the algorithm such that it can also be used to approximate the parametric solution for the minimum cost flow problem with more general, convex costs. Since our algorithms can handle the undirected and directed setting, it can be applied to many real-world problems. In a computational study, we test two different algorithms for the computation of parametric minimum cost flows on several traffic and gas instances and find that the algorithms are also applicable in practice. In the second part, we study the parametric computation of Nash equilibria in an atomic splittable congestion games, a special form of network congestion games. We characterize equilibria and show that their computation is a PPAD-complete problem. As a byproduct of our analysis, we also obtain algorithms for the parametric and non-parametric computation of equilibria in atomic splittable congestion games.

Author dc:creator

• Warode, Philipp

Advisor dc:contributor.advisor

• Max, Klimm

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc/4.0/

Language dc:language.iso

en

Identifier URI

http://dx.doi.org/10.14279/depositonce-15362

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/16585