Restoring Pure Equilibria to Weighted Congestion Games

Abstract

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 worst-case inefficiency of equilibria. For weighted network cost-sharing games, we precisely calculate the price of stability for any given player weight vector, while for weighted routing games, we precisely calculate the price of anarchy, as a parameter of the set of allowable cost functions.