Computing Equilibria in Binary Networked Public Goods Games

2019/11/13 by Sixie Yu, Kai Zhou, Yu, Sixie +5
Decision Sciences · Social Sciences · #Computer Science and Game Theory (cs.GT) #Evolutionary Game Theory and Cooperation #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications

paper · pdf · doi:10.48550/arxiv.1911.05788

openalex publication_date 2019/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• The Complexity of Computing a Nash Equilibrium
• Public goods in networks

Related

• A Refined Study of the Complexity of Binary Networked Public Goods Games
• On Parameterized Complexity of Binary Networked Public Goods Game
• On Binary Networked Public Goods Game with Altruism
• Public Goods Games in Directed Networks
• Inducing Equilibria in Networked Public Goods Games through Network Structure Modification