Competitive variants of discrete and continuous flows over time

Vargas Koch, Laura; Triesch, Eberhard; Skutella, Martin; Peis, Britta

doi:HT020671155

Competitive variants of discrete and continuous flows over time

Vargas Koch, Laura^RWTH*

2020 & 2021

Verantwortlichkeitsangabevorgelegt von Laura Vargas Koch, Master of Science

ImpressumAachen 2020

Umfang1 Online-Ressource (xv, 211 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2020

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2021

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Peis, Britta (Thesis advisor)^RWTH* ; Skutella, Martin (Thesis advisor) ; Triesch, Eberhard (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2020-10-30

Online
DOI: 10.18154/RWTH-2020-11648
URL: https://publications.rwth-aachen.de/record/807846/files/807846.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
flows over time (frei) ; game theory (frei) ; traffic modeling (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Diese Arbeit beschäftigt sich mit diskreten und kontinuierlichen kompetitiven Flussmodellen. In solchen Modellen reisen egoistisch handelnde Akteure durch ein Netzwerk, in dem Kanten Reisezeiten und Kapazitäten haben. Dabei beeinflussen sie gegenseitig ihre Ankunftszeiten, da es auf Grund der beschränkten Kapazitäten der Kanten zu Überlastung kommen kann. Dies beschreibt eine Situation, wie sie auch im Straßenverkehr auftritt. Während es Simulationsprogramme gibt, die sehr detailreiche Verkehrsmodelle verwenden, dafür aber mathematisch kaum analysierbar sind, vereinfachen mathematische Modelle die Realität stark um analysierbar zu bleiben. Ziel der Arbeit ist es zur Entwicklung guter mathematischer kompetitiver Flussmodelle beizutragen. Dabei ist die große Herausforderung detailreiche und realistische analysierbare Modelle zu entwickeln und zu verstehen. Der erste Teil der Arbeit widmet sich der Entwicklung und Analyse eines diskreten kompetitiven Flussmodels, das sich kompetitives Paketrouting nennt. Die Grundlage dieses Models bildet ein Netzwerk, in dem jede Kante eine Reisezeit und eine Kapazität besitzt. Spieler betreten das Netzwerk an einem Startknoten und wählen einen Weg, auf dem sie so schnell wie möglich zu ihrem Zielknoten gelangen, wenn sie die Strategien der übrigen Spieler antizipieren. Es werden drei verschiedene Varianten untersucht, wie in diesem Modell Konflikte, die zwischen Spielern auftreten, gelöst werden können: durch spielerabhängige Regeln, durch kantenabhängige Regeln und durch randomisierte Regeln. Außerdem wird bei der Analyse zwischen symmetrischen Spielen, bei denen alle Spieler einen gemeinsamen Start- und Endknoten teilen und zwischen multi-commodity Spielen, bei welchen das nicht der Fall ist, unterschieden. In den verschiedenen Varianten des Spiels wird die Existenz und Berechenbarkeit von Gleichgewichtszuständen und deren Güte untersucht. Darüber hinaus beschäftigen wir uns mit der Berechnung möglichst guter Prioritätslisten. Im zweiten Teil dieser Arbeit werden zeitabhängige Nash-Flüsse analysiert, wie die Gleichgewichtszustände in dem kontinuierlichen kompetitiven Modell, welches hier präsentieret wird, genannt werden. Die Grundform des Models wurde von Koch und Skutella eingeführt. Auch hier bildet ein Netzwerk, in dem jede Kante eine Reisezeit und eine Kapazität hat, die Grundlage des Models. Der große Unterschied ist, dass unendlich kleine Partikel das Netzwerk an der Quelle mit einer bestimmten Rate betreten und dann jedes einzelne Partikel einen optimalen Weg zur gleichen Senke wählt. Wir erweitern dieses Modell durch die Einführung einer Einflusskapazität und durch die Beschränkung des Gesamtflusses einer Kante hin zum Spillback-Modell. So wird es ermöglicht Rückstau abzubilden. In einem nächsten Schritt fügen wir zudem eine Rückwärtsreisezeit zu den Eigenschaften der Kante hinzu. Damit können die Reaktionszeiten der Verkehrsteilnehmer berücksichtigt werden und der Verkehr verhält sich im Modell wellenähnlich, wie es auch im verstopften Stadtverkehr zu beobachten ist. Da sowohl der Rückstau als auch die wellenartige Bewegung des Verkehrs zu den Details gehören, die Verkehrssimulationsprogramme implementieren, ist diese Erweiterung relevant. Die bekannten Ergebnisse über die Existenz von Gleichgewichten werden auf die neuen Modelle übertragen und darüber hinaus werden die Eigenschaften der Gleichgewichte in den präsentierten Modellen analysiert. Abschließend wird der Zusammenhang zwischen einem diskreten und dem kontinuierlichen Flussmodell untersucht.

In this thesis, we examine discrete and continuous models of competitive flows over time. The general idea of these models is that selfishly acting players travel over time through some network and influence each other's arrival time. This happens since the network comes with some capacity constraints and thus congestion may occur. The described situation corresponds to the situation in a traffic scenario. While mathematical models for traffic scenarios are simplified but well-studied, there are simulation tools providing detailed models where equilibria are computable, but which are theoretically poorly understood. The goal of this thesis is to contribute to the development of mathematical competitive flow over time models towards more detailed, more realistic traffic models. In the first part, we introduce a competitive packet routing model, which is a discrete competitive flow over time model. Here, we consider a graph, where every arc is equipped with a transit time and a capacity. A set of players, each having an origin and a destination node, travel through the network and aim to reach their destination nodes as early as possible by anticipating the strategies of the other players. We examine three different variants of how conflicts that occur between the players for a unit of capacity are resolved. A player priority scheme, an arc priority scheme and a randomized priority scheme are presented. Furthermore, we distinguish in the analysis between symmetric instances where all players share the start and destination node and multi-commodity instances. In all different model variants, we analyze the existence and computability of Nash equilibria, we present bounds on the price of anarchy and stability, and we consider the design of good priority rules. In the second part of this thesis, we consider Nash flows over time which are equilibria in a continuous competitive flow over time model. We present the base model, introduced by Koch and Skutella, where again every arc is equipped with a transit time and a capacity. The big difference is that here infinitesimal small particles enter with some rate into the network and aim to travel as fast as possible to some destination node. We extend this model towards the spillback model by adding a storage capacity and an inflow capacity to every arc. This enables the model to depict spillback, a well-known phenomenon from every day traffic. Spillback denotes the situation when a road is full and thus cars spill back to preceding roads and might block upstream sideways. Moreover, we extend the spillback model to the kinematic wave model by introducing a backwards transit time on the arcs. In this way kinematic waves, another well-known real-world phenomenon, become representable. This is a relevant extension, since both spillback and kinematic waves are core features of recent traffic simulation tools. We transfer the results which prove the existence of Nash flows over time in the base model to the spillback model and to the kinematic wave model and analyze their properties. Lastly, we examine the connection of continuous and discrete competitive flow over time models.

OpenAccess:
PDF
(additional files)