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

Files

Original bundle
Now showing 1 - 1 of 1
Name:
warode_philipp.pdf
Size:
1.86 MB
Format: