ﻻ يوجد ملخص باللغة العربية
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.
Productive societies feature high levels of cooperation and strong connections between individuals. Public Goods Games (PGGs) are frequently used to study the development of social connections and cooperative behavior in model societies. In such game
Cancer cells obtain mutations which rely on the production of diffusible growth factors to confer a fitness benefit. These mutations can be considered cooperative, and studied as public goods games within the framework of evolutionary game theory. Th
We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our m
Recently, Press and Dyson have proposed a new class of probabilistic and conditional strategies for the two-player iterated Prisoners Dilemma, so-called zero-determinant strategies. A player adopting zero-determinant strategies is able to pin the exp
We study natural strategic games on directed graphs, which capture the idea of coordination in the absence of globally common strategies. We show that these games do not need to have a pure Nash equilibrium and that the problem of determining their e