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.
Research on flows over time has been conducted mainly in two separate and mainly independent approaches, namely \emph{discrete} and \emph{continuous} models, depending on whether a discrete or continuous representation of time is used. Recently, Borel flows have been introduced to build a bridge between these two models.
In this paper, we consider the maximum Borel flow problem formulated in a network where capacities on arcs are given as Borel measures and storage might be allowed at the nodes of the network. This problem is formulated as a linear program in a space of measures. We define a dual problem and prove a strong duality result. We show that strong duality is closely related to a MaxFlow-MinCut Theorem.
We consider the dynamic shortest path problem in the continuous-time model because of its importance. This problem has been extensively studied in the literature. But so far, all contributions to this problem are based on the assumption that all transit times are strictly positive. However, in order to study dynamic network flows it is essential to support negative transit times since they occur quite naturally in residual networks.
In this paper we extend the work of Philpott [SIAM Control Opt.,~1994, pp.~538--552] to the case of arbitrary (also negative and irrational) transit times. We study a corresponding linear program in a space of measures and give a full characterization of its extreme points. In particular, we show a one-to-one correspondence between extreme points and dynamic paths.
This paper concerns the shortest path problem for a network in which arc costs can vary with
time, each arc has a transit time, parking with a corresponding
time-varying cost is allowed at the nodes, and time is modeled as a continuum. The resulting problem is called the {\em continuous-time dynamic shortest path problem}, which is well studied in the literature. However, the problem appears as a subproblem when one wishes to test, via an algorithm for dynamic shortest paths, the presence of negative cycles in the residual network in order to develop continuous-time analogues of several well-known optimality conditions for continuous-time dynamic network flow problems. But, in general, the residual network contains arcs with negative transit times and hence the results in the literature are useless for these purposes since all results are based on the assumption of positive transit times.
In this paper, we relax this condition to allow negative transit times. We study a corresponding linear program in space of measures and prove the existence of an optimal extreme point solution. Moreover, we define a dual problem and establish a strong duality result that shows under certain assumptions that the value of the linear program equals the value of the dual problem and both values are attained. We also present counterexamples to show that strong duality only holds under these assumptions.
Dynamic network flow problems model the temporal evolution of flows over time and also consider changes of network parameters such as capacities, costs, supplies, and demands over time. These problems have been extensively studied in the past because of their important role in real world applications such as transport, traffic, and logistics. This has led to many results, but the more challenging continuous time model still lacks some of the key features such as network related optimality conditions and algorithms that are available in the static case.
The aim of this paper is to advance the state of the art for dynamic network flows by developing the continuous time analogues of several well-known optimality conditions for static network flows. Specifically, we establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of dynamic
network flows. The underlying idea is to construct a dual feasible solution that proves optimality when the residual network (with respect to a given flow) contains no dynamic cycles with negative cost. We also discuss a generic negative cycle-canceling algorithm resulting from the corresponding optimality criterion and point out promising directions for future research.
Network flows over time form a fascinating area of research. They model the temporal
dynamics of network flow problems occurring in a wide variety of
applications. Research in this area has been pursued in two different and mainly independent
directions with respect to time modeling: discrete and continuous time models.
In this paper we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each
suitable subset a real value, interpreted as the amount of
flow entering the arc over the subset. We focus on the maximum flow problem formulated in a network where capacities on arcs are also given as Borel measures and storage might be allowed at the nodes of the network. We generalize the concept of cuts to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.