Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions

We consider the problem of computing approximate Nash equilibria in monotone congestion games (a class of games generalizing network congestion games) with polynomially decreasing cost functions. In particular, we consider the case in which each resource j has a cost c j and the cost that each player incurs when using j is given by / c j / x β for some constant >0 β > 0 , where x is the number of players using j. Observe that, for =1 β = 1 , we obtain the fundamental Shapley cost sharing method. We design a parametric distributed algorithm for computing α -approximate Nash equilibria. The complexity of this algorithm depends on α , being polynomial for =Ω() α = Ω ( p β ) , for every fixed >0 β > 0 , with p being the number of players. Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs. For the case of ring networks, we show that an approximate equilibrium can be polynomially computed for every fixed >1 α > 1 . On the negative side, we prove that the problem of computing a Nash equilibrium in Shapley network cost sharing games is PLS-complete even in undirected graphs, where previous hardness results where known only in the directed case.