Nash Flows Over Time with Tolls
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Bicriteria Nash flows over timeGames and Economic Behavior, 2024
- In Congestion Games, Taxes Achieve Optimal ApproximationOperations Research, 2024
- Long-Term Behavior of Dynamic Equilibria in Fluid Queuing NetworksOperations Research, 2022
- On the uniqueness of equilibrated dynamic traffic flow patterns in unidirectional networksTransportation Research Procedia, 2017
- Dynamic Equilibria in Fluid Queueing NetworksOperations Research, 2015
- Multiple equilibria in a dynamic traffic networkTransportation Research Part B: Methodological, 2011
- Nash Equilibria and the Price of Anarchy for Flows over TimeTheory of Computing Systems, 2010
- Constructing Maximal Dynamic Flows from Static FlowsOperations Research, 1958