The complexity of approximate Nash equilibrium in congestion games with   negative delays
  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. 
Frederic Magniez and Michel de Rougemont and Miklos Santha and Xavier   Zeitoun
cs.GT cs.CC cs.DS