Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14438
For citation please use:
Main Title: Nash Equilibria and the Price of Anarchy for Flows Over Time
Author(s): Koch, Ronald
Skutella, Martin
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15665
http://dx.doi.org/10.14279/depositonce-14438
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges change over time. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community. We present a novel characterization of Nash equilibria for flows over time. It turns out that Nash flows over time can be seen as a concatenation of special static flows. The underlying flow over time model is a variant of the so-called deterministic queuing model that is very popular in road traffic simulation and related fields. Based upon this, we prove the first known results on the price of anarchy for flows over time.
Subject(s): Nash equilibria
flows over time
price of anarchy
deterministic queuing model
static routing games
Issue Date: 2009
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2009, 14
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-014-2009.pdf
Format: Adobe PDF | Size: 227.71 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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