A Characterization of Complexity in Public Goods Games

2023/01/27 by Gilboa, Matan
#68Q17 (Secondary) #91A68 (Primary) #Computer Science and Game Theory (cs.GT) #F.2.0 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2301.11580

Abstract

We complete the characterization of the computational complexity of equilibrium in public goods games on graphs. In this model, each vertex represents an agent deciding whether to produce a public good, with utility defined by a "best-response pattern" determining the best response to any number of productive neighbors. We prove that the equilibrium problem is NP-complete for every finite non-monotone best-response pattern. This answers the open problem of [Gilboa and Nisan, 2022], and completes the answer to a question raised by [Papadimitriou and Peng, 2021], for all finite best-response patterns.

Related

• Complexity of Public Goods Games on Graphs
• On Parameterized Complexity of Binary Networked Public Goods Game
• A Refined Study of the Complexity of Binary Networked Public Goods Games
• Public Goods Games in Directed Networks
• Computing Equilibria in Binary Networked Public Goods Games