Parametric computation of equilibria and flows
| dc.contributor.advisor | Max, Klimm | |
| dc.contributor.author | Warode, Philipp | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Max, Klimm | |
| dc.contributor.referee | Marc, Pfetsch | |
| dc.date.accepted | 2021-09-13 | |
| dc.date.accessioned | 2022-04-25T08:54:29Z | |
| dc.date.available | 2022-04-25T08:54:29Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | 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. | en |
| dc.description.abstract | Netzwerkflüsse können zur Modellierung zahlreicher Anwendungen verwendet werden, zum Beispiel für Flüsse in physikalischen Netzwerken wie Strom-, Gas- oder Wassernetzen, Flüsse in Verkehrsnetzwerken oder Warenflüsse in logistischen Netzwerken. Genauer gesagt können viele dieser Anwendungen entweder als minimale Kostenflüsse oder Gleichgewichte von Netzwerkspielen modelliert werden, manchmal sogar beides. In dieser Arbeit untersuchen wir die Komplexität der Berechnung dieser Flüsse und entwickeln Algorithmen für deren Berechnung. Im Gegensatz zu statischen Flussmodellen, die in der Literatur häufig untersucht werden, konzentrieren wir uns hauptsächlich auf parametrische Flussmodelle. Insbesondere betrachten wir Modelle, bei denen die Nachfragewerte an den Knoten, das heißt die externen Ein- und Ausflussraten, durch einen eindimensionalen Wert parametrisiert sind. Die Lösung eines parametrischen Flussproblems ist nicht mehr ein statischer Fluss, sondern eine Funktion, die jeden Parameter auf einen statischen Fluss für die entsprechende Nachfragen abbildet. Das parametrische Modell erlaubt es, die Sensitivität von statischen Flüssen in Bezug auf den Ein- und Ausfluss zu analysieren. Diese Arbeit gliedert sich in zwei Teile. Der erste Teil befasst sich mit dem minimalen Kostenflussproblem mit konvexen Kosten, sowohl mit und ohne parametrische Nachfragen. Wir charakterisieren optimale Lösungen über optimale Potentiale, analysieren die parametrischen minimalen Kostenflüsse und ihre Ableitungen und entwickeln einen output-polynomialen Algorithmus, der Lösungsfunktionen für das parametrische minimale Kostenflussproblem für stückweise quadratische Kostenfunktionen berechnen kann. Wir erweitern den Algorithmus, sodass er auch zur Approximation von parametrischen Lösungen für das minimale Kostenflussproblem mit allgemeineren, konvexen Kosten verwendet werden kann. Da unsere Algorithmen sowohl für ungerichtete als auch für gerichtete Netzwerke geeignet ist, kann er auf viele reale Probleme angewendet werden. In einer Rechenstudie testen wir zwei verschiedene Algorithmen auf mehreren Verkehrs- und Gasinstanzen und zeigen, dass die Algorithmen auch in der Praxis anwendbar sind. Im zweiten Teil untersuchen wir die parametrische Berechnung von Nash-Gleichgewichten in atomaren, teilbaren Auslastungsspiele (atomic splittable congestion games), einer speziellen Form von Netzwerkstauspielen. Wir charakterisieren Gleichgewichte und zeigen, dass ihre Berechnung ein PPAD-vollständiges Problem ist. Als Nebenprodukt unserer Analyse erhalten wir auch Algorithmen für die parametrische und nicht-parametrische Berechnung von Gleichgewichten. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/16585 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-15362 | |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc/4.0/ | en |
| dc.subject.ddc | 510 Mathematik | de |
| dc.subject.other | minimum-cost flows | en |
| dc.subject.other | Nash equilibria | en |
| dc.subject.other | parametric computation | en |
| dc.subject.other | potential based flow | en |
| dc.subject.other | network | en |
| dc.subject.other | Minimaler Kostenfluss | de |
| dc.subject.other | Nash-Gleichgewicht | de |
| dc.subject.other | parametrische Berechnung | de |
| dc.subject.other | potentialbasierter Fluss | de |
| dc.subject.other | Netzwerk | de |
| dc.title | Parametric computation of equilibria and flows | en |
| dc.title.translated | Parametrische Berechnung von Gleichgewichten und Flüssen | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Optimierung | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.group | FG Diskrete Optimierung | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |