05834649

a

05834649 Syrgkanis, Vasilis The complexity of equilibria in cost sharing games. Saberi, Amin (ed.), Internet and network economics. 6th international workshop, WINE 2010, Stanford, CA, USA, December 13--17, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17571-8/pbk). Lecture Notes in Computer Science 6484, 366-377 (2010). 2010 Berlin: Springer EN cost sharing PLS-completeness price of stability congestion games

doi:10.1007/978-3-642-17572-5_30

Summary: We study Congestion Games with non-increasing cost functions (Cost Sharing Games) from a complexity perspective and resolve their computational hardness, which has been an open question. Specifically we prove that when the cost functions have the form $f(x) = c _{r }/x$ (Fair Cost Allocation) then it is PLS-complete to compute a Pure Nash Equilibrium even in the case where strategies of the players are paths on a directed network. For cost functions of the form $f(x) = c _{r }(x)/x$, where $c _{r }(x)$ is a non-decreasing concave function we also prove PLS-completeness in undirected networks. Thus we extend the results of [7,1] to the non-increasing case. For the case of Matroid Cost Sharing Games, where tractability of Pure Nash Equilibria is known by [1] we give a greedy polynomial time algorithm that computes a Pure Nash Equilibrium with social cost at most the potential of the optimal strategy profile. Hence, for this class of games we give a polynomial time version of the Potential Method introduced in [2] for bounding the Price of Stability.