# Public Goods Games in Directed Networks

arXiv: https://arxiv.org/abs/2106.00718 · HTML: https://mlsanity.com/paper/2106.00718/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2021.

## Built on by (most cited first, 2 of 2)

- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations](https://mlsanity.com/paper/2610.19690/) (2026)

## Abstract (arXiv)

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.