Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3347
Main Title: Routing Games over Time
Translated Title: Routingspiele über die Zeit
Author(s): Koch, Ronald
Advisor(s): Skutella, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: 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.
URI: urn:nbn:de:kobv:83-opus-36935
http://depositonce.tu-berlin.de/handle/11303/3644
http://dx.doi.org/10.14279/depositonce-3347
Exam Date: 30-Apr-2012
Issue Date: 27-Sep-2012
Date Available: 27-Sep-2012
DDC Class: 510 Mathematik
Subject(s): Deterministisches Warteschlangenmodell
Direkte Flüsse über die Zeit
Konsistentes Flussmodell
Nash-Gleichgewichte über die Zeit
Consistent flows over time
Determinstic queuing model
Direct flows over time
Nash equilibria over time
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_13.pdf3,37 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.