• search hit 4 of 9
Back to Result List

Nash Equilibria and the Price of Anarchy for Flows over Time

Please always quote using this URN:urn:nbn:de:0296-matheon-5309
  • We study Nash equilibria and the price of anarchy 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; on the other hand, there is a rich literature on game theoretic aspects of flows over time in the traffic community. In this paper, we present the first known results on the price of anarchy for flows over time. We also present algorithms for computing Nash flows over time. Those algorithms have to iteratively solve certain interesting and new static flow problems. Our results are based on a novel characterization of Nash equilibria for flows over time. 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ronald Koch, Martin Skutella
URN:urn:nbn:de:0296-matheon-5309
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2008/10/13
Release Date:2008/10/13
Tag:
Preprint Number:524
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.