  Public goods games study the incentives of individuals to contribute to a
public good and their behaviors in equilibria. In this paper, we examine a
specific type of public goods game where players are networked and each has
binary actions, and focus on the algorithmic aspects of such games. First, we
show that checking the existence of a pure-strategy Nash equilibrium is
NP-complete. We then identify tractable instances based on restrictions of
either utility functions or of the underlying graphical structure. In certain
cases, we also show that we can efficiently compute a socially optimal Nash
equilibrium. Finally, we propose a heuristic approach for computing approximate
equilibria in general binary networked public goods games, and experimentally
demonstrate its effectiveness.
