Tight Inapproximability of Nash Equilibria in Public Goods Games
<|reference_start|>Tight Inapproximability of Nash Equilibria in Public Goods Games: 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$.<|reference_end|>
@article{dinh2024tight,
    title={Tight Inapproximability of Nash Equilibria in Public Goods Games},
    author={J'er'emi Do Dinh, Alexandros Hollender},
    journal={Information Processing Letters, 186:Article 106486 (2024)},
    year={2024},
    doi={10.1016/j.ipl.2024.106486},
    archivePrefix={arXiv},
    eprint={2402.14198},
    primaryClass={cs.GT cs.CC}
}