Public goods games in directed networks

卷:139

Article

关键词: PURE NASH EQUILIBRIA;    PRIVATE PROVISION;    COMPLEXITY;    STABILITY;   

DOI  :  10.1016/j.geb.2023.02.002

来源: SCIE

【 摘 要 】

Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range of public goods games have intractable equilibrium problems: The existence of pure Nash equilibria is NP-hard to decide, and mixed Nash equilibria are PPAD-hard to find. We define general utility public goods games, and prove a complexity dichotomy result for finding pure equilibria, and a PPAD-completeness proof for mixed Nash equilibria. Even in the divisible goods variant of the problem, where existence is easy to prove, finding the equilibrium is PPAD-complete. Finally, when the treewidth of the directed network is appropriately bounded, we prove that polynomial-time algorithms are possible.(c) 2023 Elsevier Inc. All rights reserved.

【 授权许可】

Free