A Characterization of Complexity in Public Goods Games
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909183258918912 |
|---|---|
| author | Gilboa, Matan |
| author_facet | Gilboa, Matan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_11580 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Characterization of Complexity in Public Goods Games Gilboa, Matan Computer Science and Game Theory 91A68 (Primary), 68Q17 (Secondary) F.2.0 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. |
| title | A Characterization of Complexity in Public Goods Games |
| topic | Computer Science and Game Theory 91A68 (Primary), 68Q17 (Secondary) F.2.0 |
| url | https://arxiv.org/abs/2301.11580 |