复杂网络上的演化博弈
|
摘要
现实世界的复杂性系统可以用复杂网络来描述，博弈论在生物、经济等系统中有着广泛应用，因此复杂网络理论与博弈论的结合给出了一个研究复杂性系统的新思路。和传统的物理系统相比,复杂网络上的演化博弈给出了更为丰富的物理现象。
本文通过蒙特卡罗数值模拟方法研究了两个双层网络上的囚徒困境演化博弈模型，其中底层的相互作用网络为二维格子网络，顶层的策略学习网络为二维Newman-Watts小世界网络。两层网络之间的差异程度可以用p来衡量，即参与者有机会模仿除有直接相互博弈关系外的其它博弈者(捷径邻居)，而模仿捷径邻居的概率为p/(1+p)。值得注意的是，本文中顶层网络的选取与M.Ifti等和Wu等用到的学习网络有很大的不同。在他们的学习网络中，策略学习邻居随着获取信息能力的增大只能从最近邻开始依次增大到次近邻、次次近邻等。而在本文的Newman-Watts小世界网络网络中，捷径邻居可以是除最近邻外整个网络中任意一个可能的参与者，从这个角度来看本文的博弈者收集信息的能力要“强于”M.Ifti等和Wu等用到的网络，但是当p=1时，整个网络的捷径邻居数才和原相互作用邻居数相等，从这个角度说本文中的网络获得的信息量要“远少于”M.Ifti等和Wu等用到的网络。
模型Ⅰ为双层网络上的两策略的囚徒困境博弈模型。通过研究表明当模仿捷径邻居的概率提升到10%以上就能有效的提高合作态密度，即捷径邻居的存在有利于合作现象维持。模型Ⅱ为双层网络上的有志愿者参加的囚徒困境博弈模型。研究表明不存在捷径邻居时，且对较弱的背叛诱惑，随着噪声水平的变化合作态密度出现多个峰值，而较大的背叛诱惑值下只有一个极大值。当存在捷径邻居时，原来的多峰相干共振现象被单峰的共振现象代替，对于较大的背叛诱惑，当p足够大时，随着噪声水平的变化合作态密度会出现两个极大值。在足够大的背叛诱惑下，增大p使得各种策略密度发生剧烈的震荡直到进入只存在单一策略态的“僵态”。
We can describe complex systems of the real world by complex networks, game theoryapplied widely in the biological, economic and other systems. Thereby, the incorporation ofcomplex networks and game theory will give a new idea for researching complex systems.Evolutionary games on graphs presents more abundant physical phenomena compare with thetraditional physical systems.
In this paper, we study two models of evolutionary prisoner’s dilemma games on the two-layers networks by the Monte Carol numerical simulation method, where the lowerinteraction layer is a square lattice with Von Neumann neighborhood, the upper learning layeris the two-dimensional Newman-Watts small-world networks. The difference between thetwo layers of network can be measured the by the probability p of the Newman-Watts small-world networks, i.e. players have the chance to imitate one except interaction neighborhoods(shortcut neighbors), and the probability is p/(1+p). It is worth noting that our upper learninglayer is very different with one’s of M. Ifti etc or Wu etc. In their networks, increasing ofgetting information ability, the each player can learn form their nearest neighbors, nearest andnext-nearest neighbors, and so on. In the Newman-Watts small-world networks, shortcutneighbors can be anyone of the whole nodes except interaction neighborhoods, from this pointof view to consider, the ability of getting information in our network is stronger than one’s byM. Ifti etc or Wu etc. But when p=1the numbers of shortcut neighbors are equal to interactionneighborhoods, from this point of view to consider, the quantity of getting information in ournetwork is far less than one’s by M. Ifti etc or Wu etc.
The modelⅠis the evolutionary prisoner’s dilemma games on the two-layers networks.The research shows that it can effectively improve the cooperation when the probability ofimitating shortcut neighbors increasing above10%. The modelⅡ is the evolutionaryprisoner’s dilemma games with volunteering on the two-layers networks. The research showsthat the cooperation density have multi-pecks vs. the noise level on the smaller temptationvalue b, but one-pesky on the larger b when shortcut neighbors are absence, but the originalmulti-pecks are instead of one-pesk on the smaller b, on the larger b, it have two-pecks and all strategies density will sharply fluctuating until only one strategy to exist with increasing of pwhen shortcut neighbors are present.
本文通过蒙特卡罗数值模拟方法研究了两个双层网络上的囚徒困境演化博弈模型，其中底层的相互作用网络为二维格子网络，顶层的策略学习网络为二维Newman-Watts小世界网络。两层网络之间的差异程度可以用p来衡量，即参与者有机会模仿除有直接相互博弈关系外的其它博弈者(捷径邻居)，而模仿捷径邻居的概率为p/(1+p)。值得注意的是，本文中顶层网络的选取与M.Ifti等和Wu等用到的学习网络有很大的不同。在他们的学习网络中，策略学习邻居随着获取信息能力的增大只能从最近邻开始依次增大到次近邻、次次近邻等。而在本文的Newman-Watts小世界网络网络中，捷径邻居可以是除最近邻外整个网络中任意一个可能的参与者，从这个角度来看本文的博弈者收集信息的能力要“强于”M.Ifti等和Wu等用到的网络，但是当p=1时，整个网络的捷径邻居数才和原相互作用邻居数相等，从这个角度说本文中的网络获得的信息量要“远少于”M.Ifti等和Wu等用到的网络。
模型Ⅰ为双层网络上的两策略的囚徒困境博弈模型。通过研究表明当模仿捷径邻居的概率提升到10%以上就能有效的提高合作态密度，即捷径邻居的存在有利于合作现象维持。模型Ⅱ为双层网络上的有志愿者参加的囚徒困境博弈模型。研究表明不存在捷径邻居时，且对较弱的背叛诱惑，随着噪声水平的变化合作态密度出现多个峰值，而较大的背叛诱惑值下只有一个极大值。当存在捷径邻居时，原来的多峰相干共振现象被单峰的共振现象代替，对于较大的背叛诱惑，当p足够大时，随着噪声水平的变化合作态密度会出现两个极大值。在足够大的背叛诱惑下，增大p使得各种策略密度发生剧烈的震荡直到进入只存在单一策略态的“僵态”。
We can describe complex systems of the real world by complex networks, game theoryapplied widely in the biological, economic and other systems. Thereby, the incorporation ofcomplex networks and game theory will give a new idea for researching complex systems.Evolutionary games on graphs presents more abundant physical phenomena compare with thetraditional physical systems.
In this paper, we study two models of evolutionary prisoner’s dilemma games on the two-layers networks by the Monte Carol numerical simulation method, where the lowerinteraction layer is a square lattice with Von Neumann neighborhood, the upper learning layeris the two-dimensional Newman-Watts small-world networks. The difference between thetwo layers of network can be measured the by the probability p of the Newman-Watts small-world networks, i.e. players have the chance to imitate one except interaction neighborhoods(shortcut neighbors), and the probability is p/(1+p). It is worth noting that our upper learninglayer is very different with one’s of M. Ifti etc or Wu etc. In their networks, increasing ofgetting information ability, the each player can learn form their nearest neighbors, nearest andnext-nearest neighbors, and so on. In the Newman-Watts small-world networks, shortcutneighbors can be anyone of the whole nodes except interaction neighborhoods, from this pointof view to consider, the ability of getting information in our network is stronger than one’s byM. Ifti etc or Wu etc. But when p=1the numbers of shortcut neighbors are equal to interactionneighborhoods, from this point of view to consider, the quantity of getting information in ournetwork is far less than one’s by M. Ifti etc or Wu etc.
The modelⅠis the evolutionary prisoner’s dilemma games on the two-layers networks.The research shows that it can effectively improve the cooperation when the probability ofimitating shortcut neighbors increasing above10%. The modelⅡ is the evolutionaryprisoner’s dilemma games with volunteering on the two-layers networks. The research showsthat the cooperation density have multi-pecks vs. the noise level on the smaller temptationvalue b, but one-pesky on the larger b when shortcut neighbors are absence, but the originalmulti-pecks are instead of one-pesk on the smaller b, on the larger b, it have two-pecks and all strategies density will sharply fluctuating until only one strategy to exist with increasing of pwhen shortcut neighbors are present.
引文
[1]汪小帆，李翔，陈关荣，复杂网络理论及其应用，北京：清华大学出版社，1-33(2006).
[2] D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks,Nature393,440(1998).
[3] A. L. Barabási and R. Albert, Emergence of Scaling in RandomNetworks,Science286,509(1999)．
[4] S. H. Strogatz, Exploring complex networks, Nature410,268(2001)．
[5] S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Adv. Phys.51,1079(2002)．
[6] P. Erdos and A. Renyi, On random graphs, Publications Mathematicae6,290(1959)．
[7] P. Erdos and A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hung.Acad5,17(1960)．
[8] P. Erdos and A. Renyi, On the evolution of random graphs，Bull. Inst. Int. Stat38,343(1961)．
[9] M. E. J. Newman and D. J. Watts, Scaling and percolation in the small-worldnetwork model, Phys. Rev. E60,6:7332-7342(1999).
[10] A. Barrat and M.Weight, On the properties of small world networks, Eur. Phys. J.B13:547-560(2000).
[11] M. E. J. Newman, The structure and function of networks, Computer PhysicsCommunications147,40-45(2002).
[12] M. E. J. Newman and D. J. Watts, Renormalization group analysis of thesmall-world network model, Phys. Lett. A263:341-346(1999).
[13] M. E. J. Newman, C. Moore and D. J. Watts, Mean-Field Solution of the Small-World Network Model, Phys. Rev. Lett.84,3201(2000)．
[14] R. Cohen and S. Havlin, Scale-free networks are ultrasmall, Phys. Rev. Lett.90,058701(2003).
[15] R. Gibbons, Game Theory for Applied Economists, Princeton University Press,Princeton (1992).
[16]吴枝喜,荣智海,王文旭,复杂网络上的博弈,力学进展38,6(2008).
[17] R. C. Lewontin, Evolution and the theory of games, J. Theor. BioL1,382(1961).
[18] J. M. Smith and G. R. Price, The logic of animal conflict, Nature246,15(1973)．
[19] M. A. Nowak and K. Sigmund, Evolutionary Dynamics of Biological Games,Science303,793(2004)．
[20] G. Szabó and G. Fáth, Evolutionary games on graphs, Physics Reports446,97-216(2007).
[21] P. Taylor and L. Jonker, Evolutionary stable strategies and game dynamics, Math.Biosci.40,145-156(1978).
[22] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics,Cambridge University Press, Cambridge (1998).
[23] J. Hofbauer and K. Sigmund, Evolutionary game dynamics, Bull. Am. Math. Soc.40,479-519(2003).
[24] R. Cressman, Evolutionary Dynamics and Extensive Form Games, MIT Press,Cambridge, MA (2003).
[25] L.E. Blume, Population games, In: W.B. Arthur, D. Lane, S. Durlauf (Eds.), TheEconomy as a Complex Adaptive System II. Addison-Wesley, Reading, MA(1998).
[26] C.W. Gardiner, Handbook of Stochastic Methods,3rd ed. Springer, Berlin (2004).
[27] D. Helbing, A stochastic behavioral model and a microscopic foundation ofevolutionary game theory, Theor. Decis.40,149-179(1996).
[28] D. Helbing, Microscopic foundation of stochastic game dynamical equations, In:W. Leinfellner, E. Kohler (Eds.), Game Theory, Experience, Rationality, KluwerAcademic, Dordrecht, pp.211-224cond-mat/9805395(1998).
[29] M. Benaim and J. Weibull, Deterministic approximation of stochastic evolutionin games, Econometrica71,873-903(2003).
[30] W. Weidlich, Physics and social-science—the approach of synergetics, Phys.Rep.204,1-163(1991).
[31] M. A. Nowak and R. M. May, Evolutionary games and spatial chaos, Nature359,826(1992)．
[32] G. Szabó and C. T ke, Evolutionary prisoner’s dilemma game on a square lattice,Phys. Rev. E58,69(1998).
[33] W. Li, X. Zhang and G. Hu, How scale-free networks and large-scale collectivecooperation emerge in complex homogeneous social systems, Phys. Rev. E76,045102(R)(2007).
[34] Z. X. Wu, X. J. Xu, Z. G. Huang, S. J. Wang and Y. H. Wang, Evolutionaryprisoner’s dilemma game with dynamic preferential selection, Phys. Rev. E74,021107(2006).
[35] G. Szabó and G. ódor，Extended mean-field study of a stochastic cellularautomaton, Phys. Rev. E49,2764(1994)．
[36] G. Szabó and A. Szohoki, Generalized mean-field study of a driven lattice gas,Phys. Rev. E53,2196(1996)．
[37] M. Ifti, T. Killingback and M. Doebeli, Effects of neighbourhood size andconnectivity on the spatial Continuous Prisoner’s Dilemma, J. Theor. Biol.231,97(2004).
[38] Z. X. Wu and Y. H. Wang, Cooperation enhanced by the difference betweeninteraction and learning neighborhoods for evolutionary spatial prisoner’sdilemma games, Phys. Rev. E75,041114(2007).
[39] C. Hauert and G. Szabó, Game theory and physics, Am. J. Phys.73,405(2005)．
[40] C. Hauert and G. Szabó, Prisoner’s dilemma and public goods games in differentgeometries: compulsory versus voluntary interactions, Complexity8,31(2003)．
[41] G. Szabó and C. Hauert, Phase Transitions and Volunteering in spatial PublicGoods Games, Phys. Rev. Lett.89,11810l (2002)．
[42] G.Szabó and C.Hauert，Evolutionary prisoner’s dilemma games with voluntaryparticipation, Phys. Rev. E66,062903(2002)．
[43] G. Szabó and J. Vukov, Cooperation for volunteering and partially randompartnerships, Phys. Rev. E69,036107(2004).
[44] Z. X. Wu, X. J. Xu, Y. Chen and Y. H. Wang, Spatial prisoner’s dilemma gamewith volunteering in Newman-Watts small-world networks, Phys. Rev. E71,037103(2005).
[45] Z. X. Wu and P. Holme, Effects of strategy-migration direction and noise in theevolutionary spatial prisoner’s dilemma. Phys. Rev. E80,026108:1-8(2009).
[2] D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks,Nature393,440(1998).
[3] A. L. Barabási and R. Albert, Emergence of Scaling in RandomNetworks,Science286,509(1999)．
[4] S. H. Strogatz, Exploring complex networks, Nature410,268(2001)．
[5] S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Adv. Phys.51,1079(2002)．
[6] P. Erdos and A. Renyi, On random graphs, Publications Mathematicae6,290(1959)．
[7] P. Erdos and A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hung.Acad5,17(1960)．
[8] P. Erdos and A. Renyi, On the evolution of random graphs，Bull. Inst. Int. Stat38,343(1961)．
[9] M. E. J. Newman and D. J. Watts, Scaling and percolation in the small-worldnetwork model, Phys. Rev. E60,6:7332-7342(1999).
[10] A. Barrat and M.Weight, On the properties of small world networks, Eur. Phys. J.B13:547-560(2000).
[11] M. E. J. Newman, The structure and function of networks, Computer PhysicsCommunications147,40-45(2002).
[12] M. E. J. Newman and D. J. Watts, Renormalization group analysis of thesmall-world network model, Phys. Lett. A263:341-346(1999).
[13] M. E. J. Newman, C. Moore and D. J. Watts, Mean-Field Solution of the Small-World Network Model, Phys. Rev. Lett.84,3201(2000)．
[14] R. Cohen and S. Havlin, Scale-free networks are ultrasmall, Phys. Rev. Lett.90,058701(2003).
[15] R. Gibbons, Game Theory for Applied Economists, Princeton University Press,Princeton (1992).
[16]吴枝喜,荣智海,王文旭,复杂网络上的博弈,力学进展38,6(2008).
[17] R. C. Lewontin, Evolution and the theory of games, J. Theor. BioL1,382(1961).
[18] J. M. Smith and G. R. Price, The logic of animal conflict, Nature246,15(1973)．
[19] M. A. Nowak and K. Sigmund, Evolutionary Dynamics of Biological Games,Science303,793(2004)．
[20] G. Szabó and G. Fáth, Evolutionary games on graphs, Physics Reports446,97-216(2007).
[21] P. Taylor and L. Jonker, Evolutionary stable strategies and game dynamics, Math.Biosci.40,145-156(1978).
[22] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics,Cambridge University Press, Cambridge (1998).
[23] J. Hofbauer and K. Sigmund, Evolutionary game dynamics, Bull. Am. Math. Soc.40,479-519(2003).
[24] R. Cressman, Evolutionary Dynamics and Extensive Form Games, MIT Press,Cambridge, MA (2003).
[25] L.E. Blume, Population games, In: W.B. Arthur, D. Lane, S. Durlauf (Eds.), TheEconomy as a Complex Adaptive System II. Addison-Wesley, Reading, MA(1998).
[26] C.W. Gardiner, Handbook of Stochastic Methods,3rd ed. Springer, Berlin (2004).
[27] D. Helbing, A stochastic behavioral model and a microscopic foundation ofevolutionary game theory, Theor. Decis.40,149-179(1996).
[28] D. Helbing, Microscopic foundation of stochastic game dynamical equations, In:W. Leinfellner, E. Kohler (Eds.), Game Theory, Experience, Rationality, KluwerAcademic, Dordrecht, pp.211-224cond-mat/9805395(1998).
[29] M. Benaim and J. Weibull, Deterministic approximation of stochastic evolutionin games, Econometrica71,873-903(2003).
[30] W. Weidlich, Physics and social-science—the approach of synergetics, Phys.Rep.204,1-163(1991).
[31] M. A. Nowak and R. M. May, Evolutionary games and spatial chaos, Nature359,826(1992)．
[32] G. Szabó and C. T ke, Evolutionary prisoner’s dilemma game on a square lattice,Phys. Rev. E58,69(1998).
[33] W. Li, X. Zhang and G. Hu, How scale-free networks and large-scale collectivecooperation emerge in complex homogeneous social systems, Phys. Rev. E76,045102(R)(2007).
[34] Z. X. Wu, X. J. Xu, Z. G. Huang, S. J. Wang and Y. H. Wang, Evolutionaryprisoner’s dilemma game with dynamic preferential selection, Phys. Rev. E74,021107(2006).
[35] G. Szabó and G. ódor，Extended mean-field study of a stochastic cellularautomaton, Phys. Rev. E49,2764(1994)．
[36] G. Szabó and A. Szohoki, Generalized mean-field study of a driven lattice gas,Phys. Rev. E53,2196(1996)．
[37] M. Ifti, T. Killingback and M. Doebeli, Effects of neighbourhood size andconnectivity on the spatial Continuous Prisoner’s Dilemma, J. Theor. Biol.231,97(2004).
[38] Z. X. Wu and Y. H. Wang, Cooperation enhanced by the difference betweeninteraction and learning neighborhoods for evolutionary spatial prisoner’sdilemma games, Phys. Rev. E75,041114(2007).
[39] C. Hauert and G. Szabó, Game theory and physics, Am. J. Phys.73,405(2005)．
[40] C. Hauert and G. Szabó, Prisoner’s dilemma and public goods games in differentgeometries: compulsory versus voluntary interactions, Complexity8,31(2003)．
[41] G. Szabó and C. Hauert, Phase Transitions and Volunteering in spatial PublicGoods Games, Phys. Rev. Lett.89,11810l (2002)．
[42] G.Szabó and C.Hauert，Evolutionary prisoner’s dilemma games with voluntaryparticipation, Phys. Rev. E66,062903(2002)．
[43] G. Szabó and J. Vukov, Cooperation for volunteering and partially randompartnerships, Phys. Rev. E69,036107(2004).
[44] Z. X. Wu, X. J. Xu, Y. Chen and Y. H. Wang, Spatial prisoner’s dilemma gamewith volunteering in Newman-Watts small-world networks, Phys. Rev. E71,037103(2005).
[45] Z. X. Wu and P. Holme, Effects of strategy-migration direction and noise in theevolutionary spatial prisoner’s dilemma. Phys. Rev. E80,026108:1-8(2009).
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |