On the performance of approximate equilibria in congestion games

games with polynomial latency functions. We consider how much the
price of anarchy worsens and how much the price of stability improves
as a function of the approximation factor $\epsilon$. We give almost
tight upper and lower bounds for both the price of anarchy and the
price of stability for atomic and non-atomic congestion games. Our
results not only encompass and generalize the existing results of
exact equilibria to $\epsilon$-Nash equilibria, but they also provide
a unified approach which reveals the common threads of the atomic and
non-atomic price of anarchy results. By expanding the spectrum, we
also cast the existing results in a new light. For example, the Pigou
network of two parallel links, which gives tight results for exact
Nash equilibria of selfish routing, remains tight for the price of
stability of $\epsilon$-Nash equilibria but not for the price of
anarchy.