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:\mathrm{I}\mathrm{N}\to \{0,1\}$ that 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.

To be published in 15th Symposium on Algorithmic Game Theory (SAGT 2022)