اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExtortion under Uncertainty: Zero-Determinant Strategies in Noisy Games
138
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Repeated game theory has been one of the most prevailing tools for understanding the long-run relationships, which are footstones in building human society. Recent works have revealed a new set of zero-determinant (ZD) strategies, which is an important advance in repeated games. A ZD strategy player can exert a unilaterally control on two players payoffs. In particular he can deterministically set the opponents payoff, or enforce an unfair linear relationship between the players payoffs, thereby always seizing an advantageous share of payoffs. One of the limitations of the original ZD strategy, however, is that it does not capture the notion of robustness when the game is subjected to stochastic errors. In this paper, we propose a general model of ZD strategies for noisy repeated games, and find that ZD strategies have high robustness against errors. We further derive the pinning strategy under noise, by which the ZD strategy player coercively set the opponents expected payoff to his desired level, although his payoff control ability declines with the increase of noise strength. Due to the uncertainty caused by noise, the ZD strategy player cannot secure his payoff to be higher than the opponents, which implies strong extortions do not exist even under low noise. While we show that the ZD strategy player can still establish a novel kind of extortions, named weak extortions, where any increase of his own payoff always exceeds that of the opponents by a fixed percentage, and the conditions under which the weak extortions can be realized are more stringent as the noise becomes stronger.
قيم البحث
اقرأ أيضاً
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
ected 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.
Evolutionary game theory is used to model the evolution of competing strategies in a population of players. Evolutionary stability of a strategy is a dynamic equilibrium, in which any competing mutated strategy would be wiped out from a population. I
f a strategy is weak evolutionarily stable, the competing strategy may manage to survive within the network. Understanding the network-related factors that affect the evolutionary stability of a strategy would be critical in making accurate predictions about the behaviour of a strategy in a real-world strategic decision making environment. In this work, we evaluate the effect of network topology on the evolutionary stability of a strategy. We focus on two well-known strategies known as the Zero-determinant strategy and the Pavlov strategy. Zero-determinant strategies have been shown to be evolutionarily unstable in a well-mixed population of players. We identify that the Zero-determinant strategy may survive, and may even dominate in a population of players connected through a non-homogeneous network. We introduce the concept of `topological stability to denote this phenomenon. We argue that not only the network topology, but also the evolutionary process applied and the initial distribution of strategies are critical in determining the evolutionary stability of strategies. Further, we observe that topological stability could affect other well-known strategies as well, such as the general cooperator strategy and the cooperator strategy. Our observations suggest that the variation of evolutionary stability due to topological stability of strategies may be more prevalent in the social context of strategic evolution, in comparison to the biological context.
A formula is presented for designing zero-determinant(ZD) strategies of general finite games, which have $n$ players and players can have different numbers of strategies. To this end, using semi-tensor product (STP) of matrices, the profile evolution
ary equation for repeated finite games is obtained. Starting from it, the ZD strategies are developed for general finite games, based on the same technique proposed by Press and Dyson cite{pre12}. A formula is obtain to design ZD strategies for any player directly, ignoring the original ZD design process. Necessary and sufficient condition is obtained to ensure the effectiveness of the designed ZD strategies. As a consequence, it is also clear that player $i$ is able to unilaterally design $|S_i|-1$ dominating linear relations about the expected payoffs of all players. Finally, the fictitious opponent player is proposed for networked evolutionary networks (NEGs). Using it, the ZD-strategies are applied to NEGs. It is surprising that an individual in a network may use ZD strategies to conflict the whole rest network.
Since Press and Dysons ingenious discovery of ZD (zero-determinant) strategy in the repeated Prisoners Dilemma game, several studies have confirmed the existence of ZD strategy in repeated multiplayer social dilemmas. However, few researches study th
e evolutionary performance of multiplayer ZD strategies, especially from a theoretical perspective. Here, we use a newly proposed state-clustering method to theoretically analyze the evolutionary dynamics of two representative ZD strategies: generous ZD strategies and extortionate ZD strategies. Apart from the competitions between the two strategies and some classical strategies, we consider two new settings for multiplayer ZD strategies: competitions in the whole ZD strategy space and competitions in the space of all memory-1 strategies. Besides, we investigate the influence of level of generosity and extortion on the evolutionary dynamics of generous and extortionate ZD, which was commonly ignored in previous studies. Theoretical results show players with limited generosity are at an advantageous place and extortioners extorting more severely hold their ground more readily. Our results may provide new insights into better understanding the evolutionary dynamics of ZD strategies in repeated multiplayer games.
We consider the learning task of prediction of formation of core stable coalition structure in hedonic games based on agents noisy preferences. We have considered two cases: complete information (noisy preferences of all the agents are entirely known
) and partial information (noisy preferences over some coalitions are only known). We introduce a noise model that probabilistically scales the valuations of coalitions. The performance metric is the probability of our prediction conditioned on all or few noisy preferences of the agents be correct. The nature of our results is that this prediction probability is relatively low, including being zero, and rarely it is one. In the complete information two-agent model, in which each agent `retains or `inflates the values of its coalitions, we identify the expressions of the prediction probabilities in terms of the noise probability. We identify the interval of the noise probability such that the prediction probability is at least a user-given threshold. It turned out that, for some noisy games, the noise probability interval does not exist for a threshold as low as 0.1481, thus demonstrating that the prediction probabilities are generally low even in this model. In the partial information setup, we consider $n$ agent games with $l$ support of noise values, and such noisy preferences are available for some coalitions only. We obtain the bounds on the prediction probability of a partition to be $epsilon$-PAC stable in the noise-free game in the cases when the realized noisy game has or hasnt $epsilon$-PAC stable outcome.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
