2025/10/15 by Rosner, Shaul, Schröder, Marc, Koch, Laura Vargas
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2510.13518
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.