Complexity of equilibria in binary public goods games on undirected graphs
share
We study the complexity of computing equilibria in binary public goods games on undirected graphs. In such a game, players correspond to vertices in a graph and face a binary choice of performing an action, or not. Each player's decision depends only on the number of neighbors in the graph who perform the action and is encoded by a per-player binary pattern. We show that games with decreasing patterns (where players only want to act up to a threshold number of adjacent players doing so) always have a pure Nash equilibrium and that one is reached from any starting profile by following a polynomially bounded sequence of best responses. For non-monotonic patterns of the form 10^k10^* (where players want to act alone or alongside k + 1 neighbors), we show that it is 𝖭𝖯-hard to decide whether a pure Nash equilibrium exists. We further investigate a generalization of the model that permits ties of varying strength: an edge with integral weight w behaves as w parallel edges. While, in this model, a pure Nash equilibrium still exists for decreasing patters, we show that the task of computing one is 𝖯𝖫𝖲-complete.
READ FULL TEXT