TY - JOUR
AU - Yu, Sixie
AU - Zhou, Kai
AU - Brantingham, Jeffrey
AU - Vorobeychik, Yevgeniy
PY - 2020/04/03
Y2 - 2021/02/26
TI - Computing Equilibria in Binary Networked Public Goods Games
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 02
SE - AAAI Technical Track: Game Theory and Economic Paradigms
DO - 10.1609/aaai.v34i02.5609
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5609
SP - 2310-2317
AB - <p> 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. Due to space limitation, some proofs are deferred to the extended version<sup>1</sup>.</p>
ER -