基于复杂网络的演化策略博弈及其应用
摘要
本文主要研究基于复杂网络的演化博弈问题,其主要研究内容如下：
1.首先研究在格子网络中博弈个体采取相应博弈策略的问题。在WSLS (Win-Stay-Lose-Shift)策略的基础上,提出了一个新的博弈策略,即：如果博弈个体的收益大于他的邻居,那么他就保持自己的博弈策略不变。否则的话,他将随机采取和他有博弈关系邻居中的一个人的策略。一旦采取这种演化博弈策略,通过计算机仿真,发现演化博弈的结果和收益矩阵中参数b有关系。并且随着参数b的增加,演化博弈中合作者的平均水平也会增加。
2.考虑了囚徒困境上博弈的惩罚因素(对于博弈双方都选择背叛策略时的收益)的作用。为了更好的研究这个问题,我们首先提出了一个能反映外部环境对博弈双方影响的策略。通常来说,由于惩罚因素的存在(对于博弈双方都选择背叛策略是囚徒困境模型的纳什均衡,因而双方都选择背叛策略是稳定的从而使得合作策略无法出现)但由于采取这个特殊的博弈策略,通过仿真,我们发现D—D(背叛——背叛)结构并不能够保持稳定。实际上,这个博弈策略主要是通过影响C—D(合作——背叛)结构。并且我们还发现在C—D结构在网络上达到一定比例的时候,惩罚因素会使C—D结构保持稳定并阻止C—D结构向C—C(合作——合作)结构的转化。进一步地,从稳定性方面考虑,我们发现概率还可以影响博弈的结果。
3.对小世界网络上的变拓扑结构的惩罚和反馈机制进行研究。依据策略改变的原则,提出了一个新的惩罚反馈机制：网络中的所有个体都要先进行一次n轮的演化博弈,然后对于选择背叛策略最多的个体,他的两个邻居将对他进行惩罚,断开和他的博弈关系并自己建立相应的博弈关系。这个机制会使得网络中整体的度数下降,得到这种机制能够帮助合作者在博弈过程中生存下来避免被背叛者完全消灭。通过研究,我们发现前n轮博弈的次数对博弈结果产生的影响可以忽略,而网络的规模和平均度连接数则能影响博弈过程和结果。
This paper studies the application of the evolution game based on the complex network. The main contents and contributions of this paper are stated as follows:
1. Consider the problem of the strategy adopted by individuals in the vertices of the network for evolution on the lattice of the Prisoner's Dilemma Game. Based on the WSLS strategy (Win-Stay-Lose-Shift), then propose a new strategy that if the payoff of the individual is larger than the neighbor's, it will keep its strategy, otherwise, it will imitate the strategy of the directly interacted individual of its neighbors randomly. As the imitating strategy rule adopted, though the simulations, find that the results of the evolution game are related to the parameter b which is the element of the payoff matrix. Furthermore, with the value of b being increased, the percentage of the cooperators in the network will also raise. This situation is opposite to the previous concept that the higher the b is, the smaller the fraction of the cooperator is.
2. Present the problem about the effect of the punishment (the payoff for the two players both choose defection) in the Prisoner's Dilemma Game. In order to study it. we propose a new evolution strategy rule which can reflect the external factor for both players in the evolution game. For generally, if the punishment exists, the D (Defection)-D (Defection) structure (the two players both choose D strategy) which is the Nash equilibrium for the game can keep stable and never let the cooperation emerge. With the particular evolution strategy rule adopted, though the simulations, we find that the D-D structure can not keep stable and it will decrease during the game for the evolution strategy rule. Actually the punishment mainly affects the C (Cooperation)-D (Defection) structure in the network. After the fraction of the C-D structure achieved some levels, the punishment can keep the C-D structure stable and prevent it transforming to C (Cooperation)-C (Cooperation) structure. Moreover, from the aspect of the stability of structure and though the payoff the individual gains, we also find that the probability which is related to the payoff can affect the result of the evolution game.
3. Present the problem about the punishment and feedback mechanism with the topology changed on small-world network. Base on the strategy updating rule, then propose a new punishment and feedback mechanism that all the individuals in the network will play a n-round Prisoner's Dilemma Game firstly and then for the most defectors, its neighbors will punish it and break the connecting tie with it and set up the connecting for themselves. The mechanism can make the degree of the whole network decrease. And find that the mechanism can help keeping the cooperators surviving and avoiding them wiped out by the defectors. With the mechanism adopted, the number of n-round PDG almost has no effect for the evolution game. Furthermore, the probability, the average connecting and the scale of the network are related to the result of the evolution game.
1.首先研究在格子网络中博弈个体采取相应博弈策略的问题。在WSLS (Win-Stay-Lose-Shift)策略的基础上,提出了一个新的博弈策略,即：如果博弈个体的收益大于他的邻居,那么他就保持自己的博弈策略不变。否则的话,他将随机采取和他有博弈关系邻居中的一个人的策略。一旦采取这种演化博弈策略,通过计算机仿真,发现演化博弈的结果和收益矩阵中参数b有关系。并且随着参数b的增加,演化博弈中合作者的平均水平也会增加。
2.考虑了囚徒困境上博弈的惩罚因素(对于博弈双方都选择背叛策略时的收益)的作用。为了更好的研究这个问题,我们首先提出了一个能反映外部环境对博弈双方影响的策略。通常来说,由于惩罚因素的存在(对于博弈双方都选择背叛策略是囚徒困境模型的纳什均衡,因而双方都选择背叛策略是稳定的从而使得合作策略无法出现)但由于采取这个特殊的博弈策略,通过仿真,我们发现D—D(背叛——背叛)结构并不能够保持稳定。实际上,这个博弈策略主要是通过影响C—D(合作——背叛)结构。并且我们还发现在C—D结构在网络上达到一定比例的时候,惩罚因素会使C—D结构保持稳定并阻止C—D结构向C—C(合作——合作)结构的转化。进一步地,从稳定性方面考虑,我们发现概率还可以影响博弈的结果。
3.对小世界网络上的变拓扑结构的惩罚和反馈机制进行研究。依据策略改变的原则,提出了一个新的惩罚反馈机制：网络中的所有个体都要先进行一次n轮的演化博弈,然后对于选择背叛策略最多的个体,他的两个邻居将对他进行惩罚,断开和他的博弈关系并自己建立相应的博弈关系。这个机制会使得网络中整体的度数下降,得到这种机制能够帮助合作者在博弈过程中生存下来避免被背叛者完全消灭。通过研究,我们发现前n轮博弈的次数对博弈结果产生的影响可以忽略,而网络的规模和平均度连接数
This paper studies the application of the evolution game based on the complex network. The main contents and contributions of this paper are stated as follows:
1. Consider the problem of the strategy adopted by individuals in the vertices of the network for evolution on the lattice of the Prisoner's Dilemma Game. Based on the WSLS strategy (Win-Stay-Lose-Shift), then propose a new strategy that if the payoff of the individual is larger than the neighbor's, it will keep its strategy, otherwise, it will imitate the strategy of the directly interacted individual of its neighbors randomly. As the imitating strategy rule adopted, though the simulations, find that the results of the evolution game are related to the parameter b which is the element of the payoff matrix. Furthermore, with the value of b being increased, the percentage of the cooperators in the network will also raise. This situation is opposite to the previous concept that the higher the b is, the smaller the fraction of the cooperator is.
2. Present the problem about the effect of the punishment (the payoff for the two players both choose defection) in the Prisoner's Dilemma Game. In order to study it. we propose a new evolution strategy rule which can reflect the external factor for both players in the evolution game. For generally, if the punishment exists, the D (Defection)-D (Defection) structure (the two players both choose D strategy) which is the Nash equilibrium for the game can keep stable and never let the cooperation emerge. With the particular evolution strategy rule adopted, though the simulations, we find that the D-D structure can not keep stable and it will decrease during the game for the evolution strategy rule. Actually the punishment mainly affects the C (Cooperation)-D (Defection) structure in the network. After the fraction of the C-D structure achieved some levels, the punishment can keep the C-D structure stable and prevent it transforming to C (Cooperation)-C (Cooperation) structure. Moreover, from the aspect of the stability of structure and though the payoff the individual gains, we also find that the probability which is related to the payoff can affect the result of the evolution game.
3. Present the problem about the punishment and feedback mechanism with the topology changed on small-world network. Base on the strategy updating rule, then propose a new punishment and feedback mechanism that all the individuals in the network will play a n-round Prisoner's Dilemma Game firstly and then for the most defectors, its neighbors will punish it and break the connecting tie with it and set up the connecting for themselves. The mechanism can make the degree of the whole network decrease. And find that the mechanism can help keeping the cooperators surviving and avoiding them wiped out by the defectors. With the mechanism adopted, the number of n-round PDG almost has no effect for the evolution game. Furthermore, the probability, the average connecting
引文
[1]A. M. Colman, "Game Theory and Its Applications in the Social and Biological Sciences'" Butterworth-Heinemann, Oxford,1995.
[2]L. A. Bach, T. Helvik, and F. B. Christiansen. The evolution of n-player cooperation-threshold games and ESS bifurcations. J. Theor. Biol.238,2006,426-434.
[3]M. Doebeli and N. Knowlton. The evolution of inter-specific mutualism. Proc.Natl. Acad. Sci. U.S.A.95,1998,8676-8680.
[4]M. Doebeli, C. Hauert, and T. Killingback. The evolutionary origin of cooperators and defectors. Science 306,2004,859-862.
[5]A. Dreber, D. G. Rand, D. Fudenberg. and M. A. Nowak. Winners don't punish. Nature 452, 2008,348-351.
[6]R. Durrett and S. Levin. Spatial aspects of inter-specific competition. Theor. Pop. Biol.53, 1998,30-43.
|7] I. Erev and A. Rapoport. Provision of step-level public goods:The sequential contribution mechanism. J. Conflict Res.34.1990.401-425.
[8]W. J. Ewens. Mathematical Population Genetics,2nd ed.. Springer-Verlag, New York, 2004.
[9]E. Fehr and S. Gachter. Altruistic punishment in humans. Nature 415,2002,137-140.
[10]E. Fehr and U. Fischbacher. The nature of human altruism. Nature 425,2003,785-791.
[11]E. Filotas, M. Grant, L. Parrott, and P. A. Rikvold. Community-driven dispersal in an individual-based predator-prey model. Ecol. Complex.5.2008,238-251.
[12]S. A. Frank. Foundations of Social Evolution. Princeton University Press, Princeton, NJ, 1998.
[13]C. Hauert. A. Traulsen,H. Brandt. M. A. Nowak, and K. Sigmund. Via freedom to coercion:the emergence of costly punishment. Science 316,2007,1905-1907.
[14]M. D. Hauser. The Evolution of Communication. Harvard University Press, Cambridge, Massachusetts,1996.
[15]D. Helbing and W.-J. Yu. The outbreak of cooperation among successdriven individuals under noisy conditions. Proc. Natl. Acad. Soc. U.S.A.106,2009,3680-3685.
[16]B. Herrmann, C. Thoni, and S. Gachter. Antisocial punishment across societies. Science 319,2008,1362-1367.
[17]C. Hilbe and K. Sigmund. Incentives and opportunism:from the carrot to the stick. Proc. R. Soc. B 277,2010.2427-2433.
[18]E. Pennisi, "How did Cooperative Behavior Evolve?", Science,309,2005,93.
[19]M. Olson, "The Logic of Collective Action:Public Goods and the Theory of Groups", Harvard University Press. Cambrigdge, MA,1965.
[20]W. Poundstone. "The Prisoner's Delimma," Doubleday, New York,1992.
[21]M.A. Nowak and R.M. May. "Evolutionary Games and Spatial Chaos," Nature 359, 1992,826-829.
[22]F. Fu, X.J. Chen, L.H. Liu and L. Wang, "Social Dilemmas in an Online Social Network:The Structure and Evolution of Cooperation," Phys. Lett. A 371,2007,58-64.
[23]F. Fu, X.J. Chen. L.H. Liu and L. Wang, "Promotion of Cooperation Induced by the Interplay Between Structure and Game Dynamics," Phys. A 383,2007,651-659.
[24]H. Ishibuchi and N. Namikawa, "Evolution of Iterated Prisoner's Dilemma Game Strategies in Structured Demes Under Random Pairing in Game Playing," IEEE Tranactions on Evolutionary Computation. Vol.9, No.6,2005,552-561.
[25]M. Tomassini, L.Luthi and M.Giacobini, "Hawks and Doves on Small-World Networks," Phys. Rev. E 73,2006,016132.
[26]M. Bagnoli and M. Mckee. Voluntary contribution games:Efficient private provision of public goods. Econ. Inq.29,1991,351-366.
[27]C.Blackwell and M. Mckee. Only for my own neighborhood? Preferences and voluntary provision of local and global public goods. J. Econ. Behav. Organ.52,2003,115-131.
[28]L. E. Blume. The statistical mechanics of strategic interaction. Games Econ. Behav.5, 1993,387-424.
[29]R. M. Burlando and F. Guala. Heterogeneous agents in public goods experiments. Exp. Econ.8,2005,35-54.
[30]C. B. Cadsby and E. Maynes. Gender and free riding in a threshold public goods game: Experimental evidence. J. Econ. Behav. Org.34,1998,603-620.
[31]C. Hauert, A. Traulsen. H. Brandt, M. A. Nowak, and K. Sigmund. Public goods with punishment and abstaining in finite and infinite populations. Biol. Theor.3,2008,114-122.
[32]C. Hauert, J. Y. Wakano, and M. Doebeli. Ecological public goods games:Cooperation and bifurcation. Theor. Pop. Biol.73.2008.257-263.
[33]C. B. Cadsby. R. Croson, M. Marks, and E. Maynes. Step return versus net reward in the voluntary provision of a threshold public good:An adversarial collaboration. Public Choice 135,2008,277-289.
[34]J. Wang, B. Wu, X.J. Chen and L. Wang. "Evolutionary Dynamics of Pubilc Goods Games with Diverse Contributions in Finite Populations", Phys., Rev. E 81.2010,056103.
[35]J. Wang, F. Fu and L. Wang. "Effects of Heterogeneous Wealth Distribution on Pubilic Cooperation with Collective Risk",Phys., Rev. E 82,2010,016102.
[36]M. Perc and A. Szolnoki, "Social Diversity and Promotion of Cooperation in the Spatial Prisoner's Dilemma Game." Eur. Phys. J. B 61,2008,505C509.
[37]C.P. Roca, J.A. Cuesta and A. Sanchez, "Effect of Spatial Structure on the Evolution of Cooperation," Phys. Rev. E 80,2009,046106.
[38]M.A. Nowak and R.M. May, "The Spatial Dilemmas of Evolution." Int. J. Bifurcat. Chaos 3,1993,35-78.
[39]J. Vukov, G. Szabo and A. Szolonoki, "Cooperation in Noisy Case:Prisoner's Dilemma Game on Two Types of Regular Random Graphs," Phys. Rev. E 73,2006,067103.
[40]C.K. Chan and K.Y. Szcto "Decay of Invincible Clusters of Cooperators in the Evolutionary Prisoner's Dilemma Game," Lecture Notes in Computer Science, Vol.5484 2009, 243-252.
Bo Liu, Xiaoliang Kou, Jie Zhang, The Imitating Strategy Rule about Prisoner's Dilemma Game on Lattice. (El, Proceedings-20125th International Conference on Intelligent Computation Technology and Automation. ICICTA 2012. p 719-722. 2012,)
Bo Liu, Xiaoliang Kou, Jie Zhang, The Effect of Punishment about Prisoner Dilemma Game on Lattice with the Particular Evolution Rule(2011年中国自动化大会)(已接收)
Bo Liu, Xiaoliang Kou, Jie Zhang, The Punishment Mechanism with the Topology Changed for the Evolution Game on Small-World Network(2011年中国自动化大会)(已接收)
Jie Zhang, Xiaoliang Kou, Bo Liu, The Representation Theorem on the Category of FTML(L). (EI, Advances in Intelligent and Soft Computing, v 100, p 659-666,2011. Nonlinear Mathematics for Uncertainty and its Applications)
[2]L. A. Bach, T. Helvik, and F. B. Christiansen. The evolution of n-player cooperation-threshold games and ESS bifurcations. J. Theor. Biol.238,2006,426-434.
[3]M. Doebeli and N. Knowlton. The evolution of inter-specific mutualism. Proc.Natl. Acad. Sci. U.S.A.95,1998,8676-8680.
[4]M. Doebeli, C. Hauert, and T. Killingback. The evolutionary origin of cooperators and defectors. Science 306,2004,859-862.
[5]A. Dreber, D. G. Rand, D. Fudenberg. and M. A. Nowak. Winners don't punish. Nature 452, 2008,348-351.
[6]R. Durrett and S. Levin. Spatial aspects of inter-specific competition. Theor. Pop. Biol.53, 1998,30-43.
|7] I. Erev and A. Rapoport. Provision of step-level public goods:The sequential contribution mechanism. J. Conflict Res.34.1990.401-425.
[8]W. J. Ewens. Mathematical Population Genetics,2nd ed.. Springer-Verlag, New York, 2004.
[9]E. Fehr and S. Gachter. Altruistic punishment in humans. Nature 415,2002,137-140.
[10]E. Fehr and U. Fischbacher. The nature of human altruism. Nature 425,2003,785-791.
[11]E. Filotas, M. Grant, L. Parrott, and P. A. Rikvold. Community-driven dispersal in an individual-based predator-prey model. Ecol. Complex.5.2008,238-251.
[12]S. A. Frank. Foundations of Social Evolution. Princeton University Press, Princeton, NJ, 1998.
[13]C. Hauert. A. Traulsen,H. Brandt. M. A. Nowak, and K. Sigmund. Via freedom to coercion:the emergence of costly punishment. Science 316,2007,1905-1907.
[14]M. D. Hauser. The Evolution of Communication. Harvard University Press, Cambridge, Massachusetts,1996.
[15]D. Helbing and W.-J. Yu. The outbreak of cooperation among successdriven individuals under noisy conditions. Proc. Natl. Acad. Soc. U.S.A.106,2009,3680-3685.
[16]B. Herrmann, C. Thoni, and S. Gachter. Antisocial punishment across societies. Science 319,2008,1362-1367.
[17]C. Hilbe and K. Sigmund. Incentives and opportunism:from the carrot to the stick. Proc. R. Soc. B 277,2010.2427-2433.
[18]E. Pennisi, "How did Cooperative Behavior Evolve?", Science,309,2005,93.
[19]M. Olson, "The Logic of Collective Action:Public Goods and the Theory of Groups", Harvard University Press. Cambrigdge, MA,1965.
[20]W. Poundstone. "The Prisoner's Delimma," Doubleday, New York,1992.
[21]M.A. Nowak and R.M. May. "Evolutionary Games and Spatial Chaos," Nature 359, 1992,826-829.
[22]F. Fu, X.J. Chen, L.H. Liu and L. Wang, "Social Dilemmas in an Online Social Network:The Structure and Evolution of Cooperation," Phys. Lett. A 371,2007,58-64.
[23]F. Fu, X.J. Chen. L.H. Liu and L. Wang, "Promotion of Cooperation Induced by the Interplay Between Structure and Game Dynamics," Phys. A 383,2007,651-659.
[24]H. Ishibuchi and N. Namikawa, "Evolution of Iterated Prisoner's Dilemma Game Strategies in Structured Demes Under Random Pairing in Game Playing," IEEE Tranactions on Evolutionary Computation. Vol.9, No.6,2005,552-561.
[25]M. Tomassini, L.Luthi and M.Giacobini, "Hawks and Doves on Small-World Networks," Phys. Rev. E 73,2006,016132.
[26]M. Bagnoli and M. Mckee. Voluntary contribution games:Efficient private provision of public goods. Econ. Inq.29,1991,351-366.
[27]C.Blackwell and M. Mckee. Only for my own neighborhood? Preferences and voluntary provision of local and global public goods. J. Econ. Behav. Organ.52,2003,115-131.
[28]L. E. Blume. The statistical mechanics of strategic interaction. Games Econ. Behav.5, 1993,387-424.
[29]R. M. Burlando and F. Guala. Heterogeneous agents in public goods experiments. Exp. Econ.8,2005,35-54.
[30]C. B. Cadsby and E. Maynes. Gender and free riding in a threshold public goods game: Experimental evidence. J. Econ. Behav. Org.34,1998,603-620.
[31]C. Hauert, A. Traulsen. H. Brandt, M. A. Nowak, and K. Sigmund. Public goods with punishment and abstaining in finite and infinite populations. Biol. Theor.3,2008,114-122.
[32]C. Hauert, J. Y. Wakano, and M. Doebeli. Ecological public goods games:Cooperation and bifurcation. Theor. Pop. Biol.73.2008.257-263.
[33]C. B. Cadsby. R. Croson, M. Marks, and E. Maynes. Step return versus net reward in the voluntary provision of a threshold public good:An adversarial collaboration. Public Choice 135,2008,277-289.
[34]J. Wang, B. Wu, X.J. Chen and L. Wang. "Evolutionary Dynamics of Pubilc Goods Games with Diverse Contributions in Finite Populations", Phys., Rev. E 81.2010,056103.
[35]J. Wang, F. Fu and L. Wang. "Effects of Heterogeneous Wealth Distribution on Pubilic Cooperation with Collective Risk",Phys., Rev. E 82,2010,016102.
[36]M. Perc and A. Szolnoki, "Social Diversity and Promotion of Cooperation in the Spatial Prisoner's Dilemma Game." Eur. Phys. J. B 61,2008,505C509.
[37]C.P. Roca, J.A. Cuesta and A. Sanchez, "Effect of Spatial Structure on the Evolution of Cooperation," Phys. Rev. E 80,2009,046106.
[38]M.A. Nowak and R.M. May, "The Spatial Dilemmas of Evolution." Int. J. Bifurcat. Chaos 3,1993,35-78.
[39]J. Vukov, G. Szabo and A. Szolonoki, "Cooperation in Noisy Case:Prisoner's Dilemma Game on Two Types of Regular Random Graphs," Phys. Rev. E 73,2006,067103.
[40]C.K. Chan and K.Y. Szcto "Decay of Invincible Clusters of Cooperators in the Evolutionary Prisoner's Dilemma Game," Lecture Notes in Computer Science, Vol.5484 2009, 243-252.
Bo Liu, Xiaoliang Kou, Jie Zhang, The Imitating Strategy Rule about Prisoner's Dilemma Game on Lattice. (El, Proceedings-20125th International Conference on Intelligent Computation Technology and Automation. ICICTA 2012. p 719-722. 2012,)
Bo Liu, Xiaoliang Kou, Jie Zhang, The Effect of Punishment about Prisoner Dilemma Game on Lattice with the Particular Evolution Rule(2011年中国自动化大会)(已接收)
Bo Liu, Xiaoliang Kou, Jie Zhang, The Punishment Mechanism with the Topology Changed for the Evolution Game on Small-World Network(2011年中国自动化大会)(已接收)
Jie Zhang, Xiaoliang Kou, Bo Liu, The Representation Theorem on the Category of FTML(L). (EI, Advances in Intelligent and Soft Computing, v 100, p 659-666,2011. Nonlinear Mathematics for Uncertainty and its Applications)