direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 14-2009

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Nash Equilibria and the Price of Anarchy for Flows Over Time
Authors
Classification
not available
Keywords
Nash Equilibria, Flows over Time, Price Of Anarchy, Deterministic Queuing Model
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.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe