Restoring Pure Equilibria to Weighted Congestion Games*

Congestion games model several interesting applications, including routing and network formation games, and also possess attractive theoretical properties, including the existence of and convergence of natural dynamics to a pure Nash equilibrium. Weighted variants of congestion games that rely on sharing costs proportional to players ’ weights do not generally have pure-strategy Nash equilibria. We propose a new way of assigning costs to players with weights in congestion games that recovers the important properties of the unweighted model. This method is derived from the Shapley value, and it always induces a game with a (weighted) potential function. For the special cases of weighted network cost-sharing and weighted routing games with Shapley value-based cost shares, we prove tight bounds on the price of stability and price of anarchy, respectively. Key words: price of anarchy; price of stability; Shapley value; congestion game