  Optimizing traffic flow is essential for easing congestion. However, even
when globally-optimal, coordinated and individualized routes are provided,
users may choose alternative routes which offer lower individual costs. By
analyzing the impact of selfish route-choices on performance using the cavity
method, we find that a small ratio of selfish route-choices improves the global
performance of uncoordinated transportation networks, but degrades the
efficiency of optimized systems. Remarkably, compliant users always gain in the
former and selfish users may gain in the latter, under some parameter
conditions. The theoretical results are in good agreement with large-scale
simulations. Iterative route-switching by a small fraction of selfish users
leads to Nash equilibria close to the globally optimal routing solution. Our
theoretical framework also generalizes the use of the cavity method, originally
developed for the study of equilibrium states, to analyze iterative
game-theoretical problems. These results shed light on the feasibility of
easing congestion by route coordination when not all vehicles follow the
coordinated routes.
