2026-07-23T03:28:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20216 2024-07-02T07:52:52Z ddc:004 open_access

A Characterization of Complexity in Public Goods Games Gilboa, Matan Nash Equilibrium Public Goods Computational Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matan Gilboa 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.73 urn:nbn:de:0030-drops-202164 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.73 eng https://creativecommons.org/licenses/by/4.0/legalcode