Competitive variants of discrete and continuous flows over time

Vargas Koch, Laura; Peis, Britta (Thesis advisor); Skutella, Martin (Thesis advisor); Triesch, Eberhard (Thesis advisor)

Aachen (2020, 2021)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2020

Abstract

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.