Complexity of Public Goods Games on Graphs

Abstract

We study the computational complexity of ``public goods games on networks''. In this model, each vertex in a graph is an agent that needs to take a binary decision of whether to ``produce a good'' or not. Each agent's utility depends on the number of its neighbors in the graph that produce the good, as well as on its own action. This dependence can be captured by a ``pattern'' T:\backslashmathrm\I\backslash!N\\backslashrightarrow \backslash\0,1\backslash\T:IN\textrightarrow\0,1þat describes an agent's best response to every possible number of neighbors that produce the good. Answering a question of [Papadimitriou and Peng, 2021], we prove that for some simple pattern T the problem of determining whether a non-trivial pure Nash equilibrium exists is NP-complete. We extend our result to a wide class of such T, but also find a new polynomial time algorithm for some specific simple pattern T. We leave open the goal of characterizing the complexity for all patterns.