Advertisement
Published in:
2009 | OriginalPaper | Chapter
Nash Equilibria and the Price of Anarchy for Flows over Time
Authors : Ronald Koch, Martin Skutella
Published in: Algorithmic Game Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 are time-dependent. 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 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.