Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPublic Goods Games in Directed Networks
83
0
0.0
(
0
)
Added by
Binghui Peng
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 games, contributions to the public good are made only by cooperators, while all players, including defectors, can reap public goods benefits. Classic results of game theory show that mutual defection, as opposed to cooperation, is the Nash Equilibrium of PGGs in well-mixed populations, where each player interacts with all others. In this paper, we explore the coevolutionary dynamics of a low information public goods game on a network without spatial constraints in which players adapt to their environment in order to increase individual payoffs. Players adapt by changing their strategies, either to cooperate or to defect, and by altering their social connections. We find that even if players do not know other players strategies and connectivity, cooperation can arise and persist despite large short-term fluctuations.
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. The population structure, benefit function and update rule all influence the evolutionary success of cooperators. We model the evolution of cooperation in epithelial cells using the Voronoi tessellation model. Unlike traditional evolutionary graph theory, this allows us to implement global updating, for which birth and death events are spatially decoupled. We compare, for a sigmoid benefit function, the conditions for cooperation to be favoured and/or beneficial for well mixed and structured populations. We find that when population structure is combined with global updating, cooperation is more successful than if there were local updating or the population were well-mixed. Interestingly, the qualitative behaviour for the well-mixed population and the Voronoi tessellation model is remarkably similar, but the latter case requires significantly lower incentives to ensure cooperation.
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 model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. More generally, if the feasibility constraints define an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on variants of the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. Our guarantees are meaningful even when there are fewer elements than the number of agents. As far as we are aware, our work is the first to approximate the core in indivisible settings.
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 expected payoff of the opponents or to enforce a linear relationship between his own payoff and the opponents payoff, in a unilateral way. This paper considers zero-determinant strategies in the iterated public goods game, a representative multi-player evolutionary game where in each round each player will choose whether or not put his tokens into a public pot, and the tokens in this pot are multiplied by a factor larger than one and then evenly divided among all players. The analytical and numerical results exhibit a similar yet different scenario to the case of two-player games: (i) with small number of players or a small multiplication factor, a player is able to unilaterally pin the expected total payoff of all other players; (ii) a player is able to set the ratio between his payoff and the total payoff of all other players, but this ratio is limited by an upper bound if the multiplication factor exceeds a threshold that depends on the number of players.
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 existence is NP-complete. The same holds for strong equilibria. We also exhibit some classes of games for which strong equilibria exist and prove that a strong equilibrium can then be found in linear time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
