Nashification is the problem of converting any given non-equilibrium routing into a Nash equilibrium without increasing the social cost. Our first result is an O(nm ²) time algorithm for Nashification. This algorithm can be used in combination with any approximation algorithm for the routing problem to compute a Nash equilibrium of the same quality. In particular, this approach yields a PTAS for the computation of a best Nash equilibrium. Furthermore, we prove a lower bound of $ \Omega \left( {2^{\sqrt n } } \right) $ \Omega \left( {2^{\sqrt n } } \right) and an upper bound of O(2n) for the number of greedy selfish steps for identical link capacities in the worst case.

In the second part of the paper we introduce a new structural parameter which allows us to slightly improve the upper bound on the coordination ratio for pure Nash equilibria in [3]. The new bound holds for the individual coordination ratio and is asymptotically tight. Additionally, we prove that the known upper bound of $ \frac{{1 + \sqrt {4m - 3} }} {2} $ \frac{{1 + \sqrt {4m - 3} }} {2} on the coordination ratio for pure Nash equilibria also holds for the individual coordination ratio in case of mixed Nash equilibria, and we determine the range of m for which this bound is tight.