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 resourcejhas a cost c(j) and the cost that each player incurs when usingjis given by c(j)/x(beta) for some constant beta > 0 , wherexis the number of players usingj. Observe that, for beta = 1, we obtain the fundamental Shapley cost sharing method. We design a parametric distributed algorithm for computing alpha-approximate Nash equilibria. The complexity of this algorithm depends on alpha, being polynomial for alpha = Omega(p(beta)), for every fixed beta > 0, withpbeing 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 alpha > 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.