Nash Flows Over Time with Tolls

We study a dynamic routing game motivated by traffic flows. The base model for an edge is the Vickrey bottleneck model. That is, edges are equipped with a free flow transit time and a capacity. When the inflow into an edge exceeds its capacity, a queue forms and the following particles experience a waiting time. In this paper, we enhance the model by introducing tolls, i.e., a cost each flow particle must pay for traversing an edge. In this setting we consider non-atomic equilibria, which means flows over time in which every particle is on a cheapest path, when summing up toll and travel time. We first show that unlike in the non-tolled version of this model, dynamic equilibria are not unique in terms of costs and do not necessarily reach a steady state. As a main result, we provide a procedure to compute steady states in the model with tolls.