Tight Inapproximability of Nash Equilibria in Public Goods Games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914695762411520 |
|---|---|
| author | Dinh, Jérémi Do Hollender, Alexandros |
| author_facet | Dinh, Jérémi Do Hollender, Alexandros |
| contents | We study public goods games, a type of game where every player has to decide whether or not to produce a good which is public, i.e., neighboring players can also benefit from it. Specifically, we consider a setting where the good is indivisible and where the neighborhood structure is represented by a directed graph, with the players being the nodes. Papadimitriou and Peng (2023) recently showed that in this setting computing mixed Nash equilibria is PPAD-hard, and that this remains the case even for $\varepsilon$-well-supported approximate equilibria for some sufficiently small constant $\varepsilon$. In this work, we strengthen this inapproximability result by showing that the problem remains PPAD-hard for any non-trivial approximation parameter $\varepsilon$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14198 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight Inapproximability of Nash Equilibria in Public Goods Games Dinh, Jérémi Do Hollender, Alexandros Computer Science and Game Theory Computational Complexity We study public goods games, a type of game where every player has to decide whether or not to produce a good which is public, i.e., neighboring players can also benefit from it. Specifically, we consider a setting where the good is indivisible and where the neighborhood structure is represented by a directed graph, with the players being the nodes. Papadimitriou and Peng (2023) recently showed that in this setting computing mixed Nash equilibria is PPAD-hard, and that this remains the case even for $\varepsilon$-well-supported approximate equilibria for some sufficiently small constant $\varepsilon$. In this work, we strengthen this inapproximability result by showing that the problem remains PPAD-hard for any non-trivial approximation parameter $\varepsilon$. |
| title | Tight Inapproximability of Nash Equilibria in Public Goods Games |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2402.14198 |