  We extend the study of the complexity of finding an $\eps$-approximate Nash
equilibrium in congestion games from the case of positive delay functions to
delays of arbitrary sign. We first prove that in symmetric games with
$\alpha$-bounded jump the $\eps$-Nash dynamic converges in polynomial time when
all delay functions are negative, similarly to the case of positive delays. We
then establish a hardness result for symmetric games with $\alpha$-bounded jump
and with arbitrary delay functions: in that case finding an $\eps$-Nash
equilibrium becomes $\PLS$-complete.
