  We present a fully polynomial-time approximation scheme (FPTAS) for computing
equilibria in congestion games, under smoothed running-time analysis. More
precisely, we prove that if the resource costs of a congestion game are
randomly perturbed by independent noises, whose density is at most $\phi$, then
any sequence of $(1+\varepsilon)$-improving dynamics will reach an
$(1+\varepsilon)$-approximate pure Nash equilibrium (PNE) after an expected
number of steps which is strongly polynomial in $\frac{1}{\varepsilon}$,
$\phi$, and the size of the game's description. Our results establish a sharp
contrast to the traditional worst-case analysis setting, where it is known that
better-response dynamics take exponentially long to converge to
$\alpha$-approximate PNE, for any constant factor $\alpha\geq 1$. As a matter
of fact, computing $\alpha$-approximate PNE in congestion games is PLS-hard.
  We demonstrate how our analysis can be applied to various different models of
congestion games including general, step-function, and polynomial cost, as well
as fair cost-sharing games (where the resource costs are decreasing). It is
important to note that our bounds do not depend explicitly on the cardinality
of the players' strategy sets, and thus the smoothed FPTAS is readily
applicable to network congestion games as well.
