cs.GT cs.CC cs.DS
On Parameterized Complexity of Binary Networked Public Goods Game. In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP complete. We provide fine grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show either W 1 hardness or exhibit an FPT algorithm. We finally exhibit some special graph classes, for example path, cycle, bi clique, complete graph, etc., which always have a PSNE if the utility function of the players are fully homogeneous.