A note on a parameter relating traffic equilibria and system optimal routing

摘要

In this note we extend results from Roughgarden et al. [T. Roughgarden, E. Tardos, How bad is selfish routing? J. ACM 49(2) (2002) 236–259] and Correa et al. [J.R. Correa, A. Schulz, N.E. Stier-Moses, Selfish routing in capacitated networks, Math. Oper. Res. 29(4) (2004) 961–976] concerning the total travel time in traffic equilibria. We focus on convex latency functions and derive bounds for a basic parameter β (introduced in [Correa et al., 2004]) using simple geometrical ideas. The upper bound is expressed in terms of the elasticity of the latency function. For the special case of piecewise linear convex latency functions we give an efficient algorithm for calculating this parameter exactly.