  We present a general technique, based on a primal-dual formulation, for
analyzing the quality of self-emerging solutions in weighted congestion games.
With respect to traditional combinatorial approaches, the primal-dual schema
has at least three advantages: first, it provides an analytic tool which can
always be used to prove tight upper bounds for all the cases in which we are
able to characterize exactly the polyhedron of the solutions under analysis;
secondly, in each such a case the complementary slackness conditions give us an
hint on how to construct matching lower bounding instances; thirdly, proofs
become simpler and easy to check. For the sake of exposition, we first apply
our technique to the problems of bounding the prices of anarchy and stability
of exact and approximate pure Nash equilibria, as well as the approximation
ratio of the solutions achieved after a one-round walk starting from the empty
strategy profile, in the case of affine latency functions and we show how all
the known upper bounds for these measures (and some of their generalizations)
can be easily reobtained under a unified approach. Then, we use the technique
to attack the more challenging setting of polynomial latency functions. In
particular, we obtain the first known upper bounds on the price of stability of
pure Nash equilibria and on the approximation ratio of the solutions achieved
after a one-round walk starting from the empty strategy profile for unweighted
players in the cases of quadratic and cubic latency functions. We believe that
our technique, thanks to its versatility, may prove to be a powerful tool also
in several other applications.
