2020/12/03 by Maiti, Arnab, Dey, Palash
#68Q27 #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2012.01880
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.