Loading…
Unter Berücksichtigung allgemein anerkannter Aspekte werden in dieser Dissertation Routingspiele über die Zeit von Grund auf entwickelt. Zu diesen Zweck wird auch die Theorie von Flüssen über die Zeit erweitert, was zu einem verallgemeinerten Flussmodell führt. Ausgehend von natürlichen Annahmen an das Flussverhalten definieren wir Routingspiele über die Zeit exakt. In diesem Szenario charakterisieren und analysieren wir Nash-Gleichgewichte für ein direktes Flussmodell und für das populäre deterministische Warteschlangenmodell. Aufgrund der Komplexität des Themas konzentrieren wir uns auf Szenarien, in denen der gesamte Fluss von einer Quelle zu einer Senke gesendet wird. In dieser Dissertation sind viele verschiedene mathematische Bereiche wie Lebesgue-messbare Funktionen, Funktionalanalysis, Lineare Algebra, statische Flüsse und Spieltheorie miteinander verknüpft.
In his famous work, Nash shows in 1951 that every game admits an equilibrium which is stable in the sense that no player has an incentive to change his strategy for improving his personal situation. Roughgarden and Tardos analyze in 2002 the performance of these Nash equilibria for routing games based on static flows. One main drawback of this class of routing games is the nonconsideration of time. Ford and Fulkerson introduce flows over time representing time-varying flow behavior in 1958. Combining game theory and flows over time leads to the notion of routing games over time. Since the seminal work of Friesz et al. in 1993, the number of publications in this area increases enormously. Nevertheless, compared with the static counterpart, quite less is still known about the flow behavior in routing games over time. Using common knowledge, the theory of routing games over time is built from scratch in this thesis. Even the theory of flows over time is completely revised resulting in a quite general model. Imposing natural assumptions on the flow behavior, we give a precise notion of routing games over time. In this setting, we characterize and analyze Nash equilibria for the direct flow over time and the popular deterministic queuing model. Because of the high complexity of this topic, we focus on single commodity scenarios where each flow particle wants to travel from a unique source to a unique sink. Throughout this thesis, we make use of many different mathematical fields; including Lebesgue measurable functions, functional analysis, linear algebra, static flow theory, and game theory.
