On The Performance Of User Equilibrium In Traffic Networks

According to Wardrop's first principle, drivers in a traffic network choose their routes selfishly; that is, they travel on a shortest path under the prevailing traffic conditions between their respective origin and destination. This behavior is captured by the Nash equilibrium of the underlying non-cooperative game, commonly called user equilibrium in this context. Because Nash equilibria do usually not optimize any global criterion per se, there is no apparent reason why a user equilibrium should be close to a system optimum, which is a solution of minimal total (and, therefore, average) travel time. In this paper, we extend recent positive results on the efficiency of user equilibria in simple networks to models that are more realistic. First, we introduce and analyze user equilibria in capacitated networks. In particular, we show that the worst ratio of the total travel time of the best user equilibrium to the total travel time of the system optimum does not change if capacities are included in the model. Second, we propose to compare the efficiency of user equilibria to a more restricted version of system optimum. In fact, the ordinary system optimum typically treats some drivers unfairly in that it assigns them to considerably longer paths than others. For this reason, a system optimum is often considered inadequate for purposes of traffic planning. We analyze the performance guarantee of user equilibria when compared to constrained system optima, which are designed to be more fair, and establish improved bounds in this setting. Keywords: Traffic Networks, User Equilibria.