公共品博弈的空间效应研究

1、毕业论文开题报告理论物理公共品博弈的空间效应研究一、选题的背景与意义无论对于生物界种群的进化述是人类社会的发展，合作都扮演着至关重要的 角色。然而，口私个体z间的无私利他行为与达尔文的物竞天择理论是相互抵触 的。在寻求这一问题的答案的过程中，博弈论以及演化博弈论扮演了重要角色并 提供了强有力的理论框架。社会和自然界中复杂系统的结构形态和系统结构可以从网络的角度进行描 述。近年来，复杂网络研究的兴起与发展，使得人们对各种现实网络的结构演化、 复杂性有了比较清晰的认识。而复朵网络理论为描述博弈个体z间的博弈关系提 供了方便的系统框架。网络上的节点表示博弈个体，边代表与其邻居的博弈关系。 这样一来，

2、就可以利用复杂网络拓扑关系，来研究一些复杂的博弈关系下的博弈。 由于真实系统中的个体或要素之间存在策略依赖关系，所以可在复杂网络上建立 空间博弈模型。在复杂网络上建立的空间博弈模型更加客观真实，更加符合实际 的演化规则，更加贴切生活，使得复杂网络的演化博弈方兴未艾。随着演化博弈 动力学行为与复杂网络之间的关系逐渐清晰，空间博弈必定会推动复杂网络中其 他领域的发展。而木文将在了解公共品模型的研究现状和数值方法基础上，通过 数值方法研究个体的各类空间效应，探索各类空间效应对公共品博弈中合作行为 的彩响，从而得到相应的研究成果。二、研究的基木内容与拟解决的主要问题1、对公共品模型的研究现状和数值方法

3、进行文献调研2、在了解前人的模型工作的基础上，独立进行模型建立3、对所建立的模型进行计算分析，得到研究结果4、对研究结果进行总结分析，撰写出实验论文三、研究的方法与技术路线1、在公共品模型框架下，分析各种町能的空间行为，基于相关文献及前人模 型工作z上独立建立模型2、对所建立模型通过数值方法研究个体的各类空间效应从而得到研究结果四、研究的总体安排与进度2010.12.15完成基本文献的阅读，了解基本原理和研究背景2010.12.16-2011.1.15熟悉基本数值方法，并捉岀自己新的模型2011.2.-2011.3进行模型计算和分析2011.4进行总结并撰写论文，准备答辩五、主要参考文献1、n

4、owak m a and sigmund k, 2004 science 303, 7932、szabo g and fath g, 2007 phys. rep. 446, 973、doebeli m, hauert c and killingback t, 2004 science 306, 8594、nowak m a and may r m, 1992 nature 359, 8265、hauert c and doebeli m, 2004 nature 428, 6436、santos f c and pacheco j m, 2005 phys. rev. lett. 95, 0

5、981047、复杂网络上的演化博弈 智能系统学报167324785 (2007)02200012108、复杂网络上博弈行为的研究进展 电子测量技术第30卷第4期tp399、复杂网络演化博弈理论研究综述 复杂系统与复杂性科学第5卷第4期毕业论文文献综述物理学 公共品博弈的空间效应研究 摘要：傅弈理论在社会、经济、生物以及生态等系统中存在着广泛的应用，复杂 网络理论则是研究复杂系统全新而有力的工具，因此将博弈理论与复杂网络理 论相结合成为研究复杂系统一个新的热点概述国内外当丽关于复杂网络上博弈 动力学的研究情况和发展动态，包括基本的博弈模型、主要关注的问题、以及网 络结构和博弈动力学的相互作用等，

6、最后探讨进一步的研究课题。关键词：复杂网络 演化傅弈 合作行为 正文：我阅览了大量关于复杂网络和博弈的相关文献资料。不管是书目、期刊、论 文，在这两方面的研究都始终是蓬勃发展硕果累累的。然而关于博弈的问题最终 都要归结到对于合作的探究。根据博弈论，合作能给种群内的其他成员带来好处, 却常常会损害个体自身的利益。根据达尔文进化论最适者生存的自然法则，有益 于种群内所冇成员的合作行为应该灭绝。然而，事实并非如此。在真实的生物、 社会等复杂系统中在生物和社会等科学领域，合作是一种普遍存在的现象。从单 细胞的微生物到高级哺乳动物，从社会性昆虫到人类社会。生物个体之间的合作, 增加了整个种群的生存机会。

7、那么自私个体间合作是如何产生和维持的，成为人 们讨论的热点问题。为了理解合作行为是如何从自私的个体之间演化产生的，近 年来，一些可能的合作机理。如群体选择、亲缘选择、直接（间接）互惠、空间 互惠、声望与惩罚等得到一定的探讨。口从alelrod利用迭代囚徒困境博弈研究合 作的演化以來，演化博弈论为研究合作演化提供了方便的数学框架，受到越來越 多的关注，1人i徒困境博弈和雪堆博弈是被研究者广泛采用的研究合作行为的两个 范例。在经典博弈论屮，个体被假定是超理性的（所冇个体都知道英他个体也是理 性的，并且会按照理性行事），且个体对收益矩阵元的信息完全了解。在这种机 制下，所有个体最终都会采取纳什平衡策

8、略。但是这种个体的超理性会导致机体 的非理性（因为相互合作时集体的收益最大）。一-般而言，在复杂的环境屮个体 没有充分的能力去选择最佳策略以最大化收益。此时，个体通常根据其所掌握的 局部信息采取启发式的方法，做出令其“满意”的决策，这种选择过程表明个体 是有限理性的。演化博弈理论着重研究有限性的个体如何在重复博弈过程屮，通 过口适应学习来实现口身收益的最大化问题。复杂网络理论为描述博弈个体z间的博弈关系捉供给了方便的框架。由于真 实系统中的个体或要素z间存在策略依赖关系，所以可在复朵网络上建立空间博 弈模型。这样就可以利用复杂网络拓扑关系來研究一些复杂博弈关系下的博弈。 由于真实的社会网络比一

9、些模型网络复杂，而后者通常只是前者的i个特性或某 些特性的反映，因此研究真实社会网络上的演化博弈对揭示合作的演化具有重要 意义。而小世界效应、无标度性质等对网络上演化博弈的影响自然受到了研究者 的关注，成为了有意义的课题。公共品博弈是以公共品为博弈对象的博弈，这种博弈广泛存在于发杂网络之 屮。一般来说，公共品是指在消费过程屮具有非竞争性和非排他性的物品。因为 公共品具有这样的性质，所以集体中的每个人都会希望由其他人来提供，而自己 坐享其成，这种行为被称为搭便车。搭便车问题使集体行动变得难以实现每 个人都想搭便车的结杲，就是没有便车可搭。搭便车问题的存在，解释了很多 社会困境。例如，恶劣的环境无

10、人清理，不合理的制度人人抱怨却无人抵制。公共品博弈的理论结果和现实的差异是巨大的。大量的实验研究表明，集体 成员的搭便车动机是有限的，合作能够达到一个客观口稳定的水平。这就表明， 在重复公共品博弈过程屮，个体不仅要考虑自身收益，还受到很多外在因素的影 响，如激励与惩罚，而且社会系统中的个体还貝有某种异质性称为社会偏好, 这种社会偏好使得个体会考虑他人的选择，具体表现为互惠、不平等厌恶、学习 和迁移等。很显然，这些外在因素的存在会降低个体搭便车的动机，并提高合作 水平。关于公共品博弈的研究贯穿各个方而，在生物与科淫领域的研究尤为显著。 我主要列举了一卜三种说法：群体选择学说：群体选择学说将种群看

11、作一个进化的单位，在群体层次上考 虑公共詁博弈。在群体屮，那些对种群有利的特征之所以能够保存下来，是因为 在进化过程中，虽然群选择与个体选择的方向是相反的，但是个体的选择可能导 致种群的灭亡，这种來口于外部的压力促使个体间相互合作。互惠和强互惠效应：互惠机制包括直接互惠和间接互惠。直接互惠中的个体 之所以冒着可能会被背叛的风险去跟其他个体合作是因为希望在日后与该个体 再次进行i専弈时能够取得更大的收益，所以冋报才是互惠利他主义者的真正目 的。间接互惠的基础是“声誉”。个体选择跟英他个体进行合作是期望捉高自己 的声誉，得到更多个体的合作，但是这种合作是不稳定的。直接互惠和间接互惠 都无法很好的解

12、决公共品闿弈中的合作现象，这种情况下，强互惠理论应运而生。强互惠理论认为，人类之所以能维持比其他物种更高度的合作关系，在于许 多人都具有这样一种行为倾向：在i才i休中与别人合作，并不惜花费个人成本去惩 罚那些破坏群体规范的人，即使这些成本并不能被预期得到补偿。强互惠能够冇 效的抑制团体中的背叛、逃避责任和搭便车行为，提高合作水平。但实施这种行 为需要个人承扒成本，这样就带來一个新的问题，成本出谁來负担？每一个合作 者都会寄希望于其它合作者承担这个成木，即所谓“二阶搭便车问题”。解决这 个问题乂产生了许多讨论，包括合作惩罚以及制度的制定等。空间效应：由丁真实系统中的个体或耍素z间存在策略依赖关系

13、，我们可 以在各种网络上建立空间博弈模型，这样又发现了许多空间因素的影响。比如说 公共品博弈中独立者的引入独立者是在公共品博弈模型中引入不参与博弈， 但会每局收到少而固定的收益的独立者。这样，在一定r下，就会出现-种动态 平衡。除此之外还有很多各种各样的影响，如网络的影响（不同的网络对于合作 的促进作用也是不同的）、策略的改变（在博弈屮引入学习和迁移的策略，个体 在博弈中有一定的几率改变策略和交换位置）等等，也会明显影响博弈的结果。复杂网络上的演化博弈研究是近年来随着复杂网络研究兴起而逐渐引起关 注的一个重要研究领域。口前大部分工作都集小在i人i徒困境博弈或雪堆博弈研究 上，其他类型的傅弈还缺

14、乏系统的研究。因此有必要进一步考虑多人博弈的情形, 如公用品博弈本文所主要研究的课题，或多策略的博弈等。如石头剪刀 布（rock-scissors-paper）博弈.近来一些学者开始关注这些问题，也得到了一些有 趣的结果。对于自然界中广泛存在的合作行为的理解，以及如何又到自私个体之间产生 合作一直是数学、物理、生物、管理乃至工程学科的学者关注的话题。随着复杂 网络的兴起，人们对于字儿按揭中复杂系统的组织结构有了新的认识。从网络结 构的角度研究演化博弈行为是一个既具冇理论意义又冇工程实践价值的课题。口前很多工作只是一些数值仿真结果,由于数学工具的不足，对复杂网络上的 i専弈动力学进行解析分析是非

15、常困难的，目前的一些近似方法，如平均场方法、对 估计方法在异质程度很大的网络很冇可能失效.因此寻求冇效的数学工具，探求 更好的理论结果，将一些数值结果命题化、严格化，将是十分有意义的。该课题将在了解公共品模型的研究现状和数值方法基础之上，通过数值方法 研究个体的各类空间效应，探索各类空间效应对公共品博弈屮合作行为的影响， 从而得出在各种因素之间多人i専弈情况下的合作行为的发生情况。现实中，公共 品博弈普遍存在，当然也存在很多社会困境。考虑到影响公共品博弈的各种因素, 如何更有效的促进合作行为的产生成为我们现在研究的主要方向。希望该项研究 不仅能在理论方面，更能对真实系统中公共品博弈提供建设性的

16、意见和建议。参考文献1> nowak m a and sigmund k, 2004 science 303, 7932、szabo g and fath g, 2007 phys. rep. 446, 973 doebeli m, hauert c and killingback e 2004 science 306, 8594、nowak m a and may r m, 1992 nature 359, 8265、hauert c and doebeli m, 2004 nature 428, 6436> santos f c and pacheco j m, 2005 ph

17、ys. rev. lett. 95, 0981047、复朵网络上的演化博弈智能系统学报167324785 (2007) 02200012108、复杂网络上博弈行为的研究进展电子测量技术笫30卷第4期tp399、复杂网络演化博弈理论研究综述复杂系统与复杂性科学笫5卷第4期10、博弈m白波，郭兴文哈尔滨出版社2005.本科毕业设计（20 届）公共品博弈的空间效应研究【摘要】本文基于复杂网络下的公共品博弈演化模型，研究各类空间效应对合作演化动态的影响以及引入 奖励机制后合作行为演化的方向。通过允许对合作个体的奖励作为一种积极因素促进合作的产生，结果表 明奖励可以通过提供一个避免相互背叛情况出现的方式

18、促进合作的产生。然而与惩罚相比，奖励无法使合 作稳定下来，却提高了稳定的合作者的数目。量后分析了复杂网络上公共品演化博弈论的未来发展方向与 应用前景。【关键词】公共品；复杂网络；演化博弈；奖励机制abstractabstract based on the public goods game, this thesis presents a model in which individuals are rewarded who con tribute to the public goods .it is show n that reward is capable of promoti ng coo

19、perati on by providi ng an escape hatch out of states that we defect each other mutually. reward, contrast with punishment, is unable to stabilize cooperation although it gives rise to a persistent minority of cooperators finally unresolved open problems and future research directions and possible a

20、pplication areas for public evolutionary game on complex networks are pointed out.【keywords public goods： complex networks ； evoluti on ary games ； incen tive system摘要8abstract8h录8i研究背景101. 1博弈论101. 1.1经典博弈论、博弈模型与纳什均衡101.1.2从经典聘弈到演化聘弈121.2复杂网络131.2. 1复杂网络的特征度量141.2.2复杂网络的分类141.2.3复杂网络上的演化博弈152公共品博弈背

21、景简介62.1背景简介172.2群选择学说172.3互惠与强互惠效应182.4空间效应193模型建立213. 1模型介绍213. 2现象及描述223. 3结语244结论与展望24参考文献6致谢错误！未定义书签。附录： 错误！未定义书签。1研究背景无论对于生物界种群的进化述是人类社会的发展，合作都扮演着至关重要的角色。自私 个休之间是如何产牛合作的一直是物理、牛物、数学乃至工程科学的学者关注的话题。然而, 依据达尔文主义，自然选择是基于竞争的，个体将自私的最大化自身的利益，这显然不能解 释处处可见的合作行为。为了理解合作行为是如何从占私的个体z间演化产住的，近年來, 些可能的合作机理，如群体选择

22、(group selection) >亲缘选择(kin selection) 直接(间 接)互惠(direct/indirectreciprocity) n 空间互惠(spatial reciprocity) > 声望与惩罚 (reputation and punishment)等得到了一定的探讨。而博弈论在寻求这一问题答案的过程 中扮演了重要角色并提供了强有力的理论框架。随着计算机技术的飞速发展，対复杂网络的 研究也不断深入，人们对现实世界中复杂系统的组织结构有了新的认识。在复杂网络的基础 上研究博弈行为成为一个既具有理论意义乂有现实价值的话题，受到人们越来越多的关注。1.1博弈

23、论1. 1. 1经典博弈论、博弈模型与纳什均衡博弈论，又称对策论，主要是研究依据参与博弈的其他个体的策略悄况，理性个体所采 取的策略之间交互作用下的个体的行为演化。在交互作用屮，个体所获得的收益不是纯粹由 其自身所采取的策略决定，而是受到很多其他方面的影响，如其他个体的策略、博弈规则等 等。博弈论主要是由匈牙利数学家冯-诺依曼所创立的，在20世纪40年代作为一门正式的学 科发展起来。1944年冯-诺依曼和摩根斯坦出版的著作博弈论和经济行为，标志着现代系 统博弈论的初步形成。早期的博弈论过于抽彖，实川性不强，而h人们对博弈论的研究知z 浜少，影响力有限。随着现代防弈论的不断研究发展，它作为一种数

24、学理论被广泛应用于经 济、政治、住物、信息等许多领域，fi渐成为非常重要且有用的分析工具，为解决不同实体 的冲突和合作提供了一种冇效的方法。近十多年来，诺贝尔经济学奖先后授予研究博弈论的 科学家nash、selten等人也说明，博弈论越来越受到更多人的重视，也得到了越来越广泛的 承认。通常一个博弈由以下5个部分所组成：(1)博弈主体，即陳弈过程屮进行独立决策的个 体，在一轮i専弈小至少要有两位决策者参与博弈(2)博弈信息，博弈个体所掌握的有利于 策略选择的各方而信息，在i専弈中占重要地位，根据博弈个体对参与博弈所有个体收益信息 的掌握程度口j将博弈分为完全信息博弈与非完全信息博弈（3）策略集，

25、参与博弈的个体口j 选择的所有可能策略的集合，根据该集合是有限还是无限，可分为有限聘弈和无限廨弈，其 小无限博弈乂表现为连续对策、更复博弈和微分对策等（4）收益矩阵，策略选定后，博弈 个体所获得的收益是山相应的收益函数或收益矩阵來确定的，根据博弈个体的不同收益情况 可以分为零和博弈与变和i専弈（5）策略演化，在重复i専弈过程中，i専弈个体以口身收益最 大化为冃标进行策略调整。就某一轮博弈而言，当所冇个体的策略选定以后，我们可以用集 合的形式来描述，s=（s1,s2,.）,其中每一项代表了所对应个体采取的策略，进而得到某 种策略概况下个体所获得的收益u。经典博弈论中的一个重要概念纳什均衡（nas

26、h equilibrium）,是美国科学家约翰-纳什在二十世纪捉岀来的，从实质上说是一种非合作博 弈状态。所谓纳什均衡指的是给定参与博弈的其他个体的策略时，任何一个个体都不能通过 单方面改变策略而使自身获得更高的收益。换言z,在纳什均衡中，个体所选的策略是该状 态下个体的最优策略。纳什均衡在于解释没何外在约束条件下，参与博弈的个体均选择其最 优策略而形成的一种均衡结果。首先这种假设是基于参与博弈个体完全理性以及具有共同信 息的基础之上的，但是真实系统的复朵性和界质性使得这一点就很难达到；其次，纳什均衡 是静态的，其结果没有受到其他任何因素的影响，所以在真实系统中形成的纳什均衡可能是 不稳定的；

27、最后，在很多博弈中包含不只一种均衡状态，纳什均衡不能解决多重均衡存在时 的选择问题。下面我们以经典的囚徒困境廨弈模型为例简要的阐述下纳什均衡的意义。囚徒困境博弈（prisoner，s dilemma game）:小偷甲和乙合伙作案,被捕后,警方将两人分 别置于两个房间内进行审讯。警方给出的政策是：如果双方都拒绝坦白同伴的罪行，两人将 会被轻判1年徙刑；如果甲（乙）坦口（背叛）罪行，而乙（甲）拒不供认（合作）罪行, 则甲（乙）将无罪释放，而乙（卩）将被重判5年徒刑；如果甲、乙互相揭发对方罪行，则 双方均被判刑3年。该博弈的收益矩阵可列表如下：甲/乙合作背叛合作1,15,0背叛0,53,3从上表我

28、们可以看出，如果甲选择坦白，即选择“背叛”（defect-d）乙，则乙也应该选择坦 白因为如果此时乙选择合作，甲将被无罪释放，阳乙会被重判5年，而如果此时乙也选 择背叛，则将会跟甲均判3年，显然，对乙来说，廿叛总是最佳策略。反z,对甲来说也是 如此。但是整休来看，甲乙的最优策略应该是选择跟对方合作，此时两人均被判1年。这样 就陷入了两难困境，那么这种情况下，甲乙两个体应如何做出抉择？从理性个体自身利益最 大化为冃标来看，相互合作的情况不会发生，对甲乙来说，因为不论对方采取哪种策略，背 叛始终是口身的最佳策略（注意到此时集体的收益最低）。所以当双方都选择背叛时，没有 个体会主动选择改变策略（i大

29、1为单方面改变策略使口身收益降低），此时这种相互巧叛的状 态就是该系统的纳什均衡状态。现实生活中，类似囚徒困境的例子很多，也揭示出各种社会 困境。上面所述的是单次发生的贝徒困境，但是在重复囚徒困境中，参与醇弈的个体町以通 过记忆或学习、或者采取某种报复措施对背叛者进行惩罚，那么在合适的机制卜合作将会 作为均衡的结果出现并逐渐占据优势，从而有利于合作策略的涌现与维持。在接近无限次的 博弈屮，纳什均衡会趋向于帕累托最优（pareto optimality, pavlov策略是属于更一般 的wsls的策略模型，指个体如果现在的策略获得的收益人于某个期望水平，那么 下次博弈保持该策略不变，否则就改变策

30、略）。1.1.2从经典博弈到演化博弈经典博弈论屮，个体被假定是超理性的一一完全信息博弈，而且所有个体都知道其他 个体也是理性的，并u会按照理性行事。这种机制下，博弈最终会达到纳什均衡状态，即所 有的个体最终都会采取纳什均衡策略。从囚徒困境的例子可以看出，这种个体的超理性会导 致集体的非理性（因为相互合作时集体的收益最大）。但是，在真实的复杂社会系统中，个 体没有充分的能力去选择能最大化其收益的最佳策略。此时，个体通常根据其掌握的局部信 息來做出具相对满意的策略一一非完全信息博弈，这种选择过程表明个体是有限理性 （bounded rationality）的。演化博弈理论（evolutionary

31、 game theory）着重研究重复博 弈过程中有限理性的博弈个体z间怎样涌现出合作行为以及博弈个体如何通过口适应学来 实现自身收益故大化的问题。演化博弈论（evolutionary game theory）以达尔文的进化论和拉马克的遗传基因理论为 思想基础，将烛弈理论与动态演化过程分析结合起來，分析从个体到群体行为的行为机制, 研究种群的进化遇势及稳定性，为描述个体之间的相互作用提供了一种通用数学框架。参与 博弈的个体采取一定的策略，获得一定的收益（该收益依赖于个体本身的策略跟参与博弈的 其他个体的策略）。在每一轮博弈中，博弈个体以某种策略更新规则更新自己的策略，最终 达到一种演化稳定策略

32、（evolutionarily stable strategy,ess） 所有参与博弈的个体在重复 博弈中选择的某个最优的、稳定的策略，即演化博弈中的均衡点。与经典博弈中所讨论的纳 什均衡不同，演化稳定策略是一种更加严格的均衡，该策略所对应的收益相対变界者來说是 占优势的，而且演化稳定策略只是-种初始状态的优势策略，并不是演化的结果状态。演化 稳定策略最大的不足z处就在于它把影响系统的因索都看成是一个个的孤立事件，而在现实 屮系统常常会受到各种冲击。复杂网络上的演化博弈研究上要是在结构化的群体结构上，考虑复杂网络上所刻画的膊弈者z间的相互作用关系。正是由于这种复朵的拓扑结构，使得复 杂网络上的

33、演化博弈呈现出更为复杂的动力学性质。博弈论最早体现在真实的生物学领域屮，也最早的应用来解释生物科学屮的问题。1973 年smith和price发表的动物冲突的逻辑，是烛弈论第一次被正式的应用于牛物学屮，也是 演化稳定策略的來源。该文运用博弈论的思想从个体选择的角度解释了动物间的争斗为什么 从来都是有限几非恶性的。从经典i専弈论发展到演化旳弈论，其中有3个关键性的内涵发生 了转变。第一个是策略内涵的转变。经典聘弈论中，博弈个体被假定是超理性的，所有可能选择 的不同策略构成策略集。在演化博弈论中个体的超理性被达尔文的“适者生存”规则所代替。 那些不采収“理性”策略的个体会在漫长的演化过程中趋于灭绝

34、。第二个是均衡意义的转变。在演化|専弈论中，经典博弈论中的纳什均衡被演化稳定策略 所代替。演化稳定策略可以是纯策略，也町以是混合策略。与纳什均衡相比，演化稳定策略 是一种更严格的均衡。第三个是个体交互作用内涵的转变。经典博弈论小，博弈个体只进行一次烛弈，或者与 相同的个体进行多次博弈。而在演化博弈论中，博弈个体随机选配成对进行多次博弈，且假 定再次遇到相同对手的概率很小。上述3个重要概念的内涵转变，使得演化博弈理论从一个静态的过程成为一个动态演变 的理论，更着重于对演化稳定策略的研究，能够描述动态系统的局部动态性质，预测个体行 为。1.2 复杂网络最近二十多年来，网络的研究有了突飞猛进的进展。

35、这主要得益于计算机和通信网络技 术的巨大进步。借助于它们，我们可以收集和分析以往难以想彖的海量的网络数据，并可以 研究数以百万计英至数以亿计大小的网络。通过对真实肌界大最复杂系统的研究，人们发现 它们的结构不能简单的用规则图或完全随机图來描述。但另一方面，这些复杂的结构有很多 共性，比如小的平均距离，高成团系数以及连接度为幕律分布等拓扑性质。人们把这类介于 规则图和完全随机图z间的网络称z为复杂网络(complex networks)。复杂网络是研究复杂 系统的一门新兴学科，近几年受到研究学者的广泛关注。自然界中的任何复杂系统都可以抽 象成为由相互作用的个体组成的网络，如互联网、万维网、航空网

36、、电力网、蛋白质相互作 用网以及各种合作网络等。对于复杂网络的研究极大的改变了人们对复杂外部世界的认识, 让人们认识到了以前的理论尚未涉及到的问题，也迅速引起了诸多领域中科研工作者的兴 趣，特别是物理学界、生物学界，复杂网络理论得到了充分的探索和发展。研究这些网络不 仅对于人们的工作和生活至关重要，而对于揭示自然界特别是生物系统的奥秘也金关重 要。1.2.1复杂网络的特征度量随着对复朵网络研究的不断深入，人们提出了许多概念和度量方法來表示复朵网络，这 里主要主要介绍节点的度、簇系数和平均路径长度。1、节点的度 度是描述网络局部特性的基木参数，指的是与该节点连接的其他节点的 数量。度分布(deg

37、ree distribution),则表示节点度的概率分布。如果某一节点的度分 布函数为p(k),表示该节点恰好有k条边的概率。目前度分布较为常见的有两种，一种是指 数分布，另-种是幕律分布。度分布函数反应了网络系统的宏观统计特征。2簇系数 (clustering coefficient),又称为集聚系数，指与同一个节点相连接的 一对节点相连接的概率，衡量网络的集团化程度。全连通的网络中，簇系数为1, 一般均小 于1。3、平均路径长度(average path length, apl),指网络中所有节点与节点之间平均的 最短距离。节点间的距离是通过从一个节点到另一个节点所经历的边的最小数目來计

38、算的。 复杂网络研究中一个重要发现就是大部分真实系统中的平均路径程度都远比想彖中小，我们 称之.为小世界效应。除上述度分布、簇系数和平均路径长度三个最基木的结构特性外，复杂网络还有其他许 多度量特征，如介数(反映了相应的节点或边在整个网络屮的作用和影响力，具有很强的现 实意义)、网络弹性(指网络节点的删除对连通度的影响)等。1.2.2不同类型复杂网络简介根据复杂网络的特性不同，衍生出很多不同的类型，由于真实社会网络具冇小世界和无 标度等特性，所以这里我们也主要介绍这两种网络。随机网络是最简单的复杂网络，在20世纪50年代由匈牙利的两位数学家提出的。在er 随机网络模型中，首先给定网络中的节点数

39、目，然后让任意两节点之间以相同的概率连接在 一起完全随机地构成网络。该模型口提出后被广泛应用于社会与生态学的研究。小世界网络模型，由watts>flistrogatz提出的，这个模型构建在一维格了基础上，是对 一个临近节点耦仑的规则网络进行随机化重连之麻所能生成的网络模型。与随机网络相比, 其显著特性是簇系数大、平均路径长度小。小世界网络上的空间纯策略主耍分为两类：一类 是基于环的小世界网络，另一类是基于方格的小世界网络。根据网络中度的变化特性乂可将小世界网络分为同质与界质。1.2.3复杂网络上的演化博弈人们对网络的研究由来己久，图论是最早涉足网络研究的数学理论。图论屮网络被称为 图，图

40、是网络的数学表达形式，它由顶点和边构成。图论的起源很早，瑞士数学家eul目在 1736年解决了箸名的哥尼斯城堡七桥问题，从而使他成为图论和拓扑学的创始人。此后开展 的研究工作大多基于网格等规则网络，直到上世纪五十年代，匈牙利数学家efdos和rgyi 创造性的将概率论引入图论并成功地捉出了第一个随机图模型一er模型。在过去几十年中， er模型已成为随机图论的研究基础并一玄占据着复杂网络研究的主导地位。近年来，以还原 论和整体论相结合为重要特色的复杂性科学的兴起，促便人们开始关注复杂网络的拓扑结构 及其产牛:机理:诸如因特网等人量新型网络的相继出现使得人们对复杂网络性质的了解变得 越来越迫切；计

41、算机技术的飞速发展为大规模复朵网络的研究提供了有效的丄具，使得人们 可以对那些包含上百万乃至于上千万个顶点的网络进行分析，而这在若于年前还是不可想彖 的事情；不同领域屮反映复杂网络拓扑结构的数据库相继出现为复杂网络的研究提供了可靠 的实验数据，使得研究者能够对不同类型的数据进行分析进而发现复杂网络所具有的共同特 征;上述因素加之各学科间的相互融合使得大规模复朵网络的研究得以快速发展。总体來说, 对于复杂网络上的演化弈的研究主要集中在三个方而：一是研究网络拓扑结构对陣弈演化 动力学的影响，即增加相互作用结构的复杂性，研究其对合作行为的影响；二是在不同的网 络结构下探讨各种演化规则对演化的动态影响

42、；三是网络拓扑和博弈动力学的共同演化对合 作机制的彩响，主要是h适应网络上的博弈动力学，即网络拓扑调整受博弈动力学的影响。 下而我们简要的介绍儿种网络系统中常用的策略演化规则。1、模仿最优秀者(best-takes-over)：每一伦博弈过后，个体采取与其博弈的个体中 最大收益的个体的策略进行下一轮博弈；2、模仿优胜者(proportional updating):个体在进彳亍策略更新时，与跟其进行陳弈的 其他个体比较，并以某种正比于收益的概率采取收益比白身高的个体的策略进行下一轮博 弈；3、配对比较(match-pairing comparision):个体随机选择参与博弈的其他个体进彳亍收

43、 益比较，并以某种概率(通常是两个体收益差的函数)转变为对方的策略。以上三种是复杂系统中比较常用的策略更新方法。现在人部分研究屮采用的更科学的策略更新规则是:_ 1%_為1+5（甌一"）7丁式中：等号左边表示的是节点x模仿邻居节点y策略的概率，m代表节点的累计收益，t表示节 点的理性程度。当*0时，表示节点完全理性；当t趋向于无穷时，表示节点毫无理性，随机 选择；易知，存在一个适当的t使得合作达到最高水平。网络屮参与博弈的个体比较多时，策略的更新又受到一个先后秩序的影响，我们称之 为同步更新与随机更新。同步更新是指所冇参与博弈的个体同时进行策略的更新，通常应川 在生物模型中；随机更新

44、也叫非同步更新，是指在网络屮随机选择参与陳弈的个体进行策略 的更新，这种更新规则很好的反应了真实社会系统，因而受到了更多的关注。但在很多情况 下，这两种更新方式对博弈的结果并没有明显的影响。2公共品博弈背景简介2.1背景简介山于现实生活中往往不只是两个个体间的博弈，而是多人之间的博弈，因此有必要将囚 徒困境模型扩展为一个多人博弈的模型，这就是本文研究的新的网络模型z 公共品陣 弈模型。公共品聘弈是以公共品为聘弈对象的廨弈，这种博弈广泛存在于复杂网络之屮。一般来 说，公共品是指在消费过程屮具有非竞争性和非排他性的物品。因为公共品具有这样的性质, 所以集体中的每个人都会希望由其他人来捉供，而自己坐

45、享其成，这种行为被称为搭便车。 搭便年问题使集体行动变得难以实现集体成员存在搭便午的动机，随着集体中社会成员 数量的增加，这种动机会更强烈，导致合作水平降低。搭便车问题的存在，解释了很多社会 困境。例如，恶劣的环境无人清理，不合理的制度人人抱怨却无人抵制。在公共品陳弈中， 合作者c的贡献a经过一个r倍的放人后在全体参与者n小平均分配，如果n二nc,这所有参 与者的收益都将提高r倍。但如果n中岀现了背叛者d,不贡献a而同样轩参与分配（搭便 车）,则可获得比合作者更高的净收益pd=a - r - nc/no从纳什均衡的角度看，公共品博弈 中，背叛将始终是最佳策略。从演化均衡的角度看，d将侵入c所组

46、成的团体，并最终取代 co然而，公共品博弈的理论结果与现实的差异很大。人量的实验研究表明，集体成员的搭 便车动机是有限的，合作能够达到一个客观11稳定的水平。这就表明，在重复公共站博弈过 程中，个体不仅要考虑口身收益，述受到很多外在因素的影响，如激励与惩罚（本文通过引 入一个积极因素奖励，來研究其对合作演化的影响），而社会系统中的个体还具冇某 种异质性称为社会偏好，这种社会偏好使得个体会考虑他人的选择，具体表现为互惠、 不平等厌恶、学习和迁移等。很显然，这些外在因索的存在会降低个体搭便车的动机，并提 高合作水平。2. 2群选择学说在群选择学说中，把种群看做一个进化的单位在群体层次上起作川。那些

47、对种群冇利但 对个体不利的特征之所以能够保存下来，是因为种群的选择会使这一特征出现的频率增加， 而个体选择服从群体的利益，是为避免群体被淘汰。公共品博弈与此相似，搭便车行为虽然 使个体的收益提髙了，但是却损害了集体的利益，导致集体被淘汰，于是，在外界压力下，个体选择合作来避免此情况的发生。2. 3互惠与强互惠效应互惠机制包括肓接互惠和间接互惠。直接互惠屮的个体z所口目若氷背叛的风险去与其他个体合作是因为希望在fi后与受次利他是弛惠者再次相谓，以应获f是互惠利他主义者的真正目的，这乍的而建立,但也可能陷入相互背己。直接i叛的因境。,以期待笫三方c的帮助。在这jk间接互惠的基础是“声巻”。b帮助a

48、是为了提高声誉个受背叛犁勺报复行为要 罚，合作是不稳定的。种情况下，由于报复策略的制约，合作町能因为一个背信行为而导致合作的失败。因为第一经过许多回合之后才会打击到始作佣者，这样许多无辜者会受到惩直接互惠和间接互惠都无法很好的解决公共品博弈中的合作现彖，这种悄况下，强互惠 理论应运而生。强互惠理论认为，人类z所以能维持比其他物种更高度的合作关系，在于许多人都具有这样-种行为倾向：在团体中与别人合作，并不惜花费个人成木去惩罚那些破坏群体规范的人，即使这些成本并不能被预期得到补偿。强互惠能抑制团体中的苗叛、逃避责任和搭便不 行为，从而冇效提高团体成员的福利水平，但实施这种行为需要个人承担成木。这样

49、就带來 一个新的问题，既然这种强互惠行为所提高的是团队的收益，那么这个成本由谁来负担？每 一个合作者都会寄希望于其它合作者承担这个成本，这就是所谓的“二阶搭便车问题”。解 决这个问题乂产纶了许多讨论，包括合作惩罚以及制度的制定等。9 4 牢问效 应 i- opbonalpubik a*i i j 八人 1 goods gimes m 叶，wmma “ popuu* tions the three equ»* 由于真实系绽關細湃或要蘆之期j存在策noting homoktn«om popubtions of coop*系，我们可以亦各种网络上建立空间博弈模型，这样换醐約多用间

50、if碾型中劝入不参写博弈但会每局收到少而固定的收益的deurte the rcpinutordymmia i *心a)独立者的引矗翩男砧 the mtcricr of独立者。这样，就g er only brief intennit* tent bursts o( cooper-群体较大时，背叛:蠶js删地位 hum port q ippen surrounded by dosed orthts. (c) with perfect mfocmation.莓 t beu rcpty dynamkn现一种动态平衡。当群体较小时，合作者占优势地位;q txconwt an attrador tht d

51、瓠* lines5? into thr«rtgiom wh«e cooptcmaon dtfktton. and loners domte. (d) indiv kjsized simuutions confirm the subiuty of the cycles in finite populations, if the strite of a randomly pitted individual is imiuted whenever it perfofim better. parametefs：n - 5；(a)r - 0.5; (b) to(d)f - 3.<

52、;r - 1; (d)popuhbon size. sooft numbero( intmktiom, 10*.figire 1 population structure and local neiboirhoods. a, regular graphs studied so far. htiich mimic spatially extended systems, b, sok free graphs' in which small world effects cocast with a iwge heierogenehy in neighbourhood size, cjhe fo

53、al indrvidiul (large" sphere) bdongs to different groups (neighbourhoods) of afterent azo in a heterogeneous gr申h. given his/her connectivity r 4. we ident © five neighbourhoods each centred on one of the memben o( the focalderives from the piyoff峡静爍的促进作川是aaumuuted in all fiveneighbourhood

54、s (x 仇 *6 and c).hoproductton <raco msetectkxi irate u)c）策略的改变:在博弈中引入学习和i策略。使中有一定几率交换位置会叨excriango (rata r)向|° the rules of the stockastbc model individuals of three com pctiny*species a < red )w b (biuc)> and c (yd low) occupy *he $itc& of a iacttoc. a ll>cy interact with their

55、 nearest neighbours through selection or reproduction, both of whk h react ion% occurproceme at rutekt 、<!nr%p<v1 ively selection rrileds cyclic dommance: a can kill rv yielding an empty site (black). in the same way» b invadcs c. and c in l um oulcompctcs a. reproduction of individual is

56、 cvily allowed on empty n eaghboureng sites, to mimic a finite cjrrydnft capacity of the system. we also endow individuals with mobility: nl ex change rate r> they are able to $wap position with a neighbouring individual or hop onio an empty ncighhouringsilc (cxchiinge). an example of the three p

57、roccy膏.taking place* on a j < 3 square lattice3x h1 x 10-51 x lo-<mobifty. mbtodh/orsityunrformrty3模型建立3.1模型介绍木文所建立的模型是基于复杂网络的公共品演化障弈模型。模型屮只考虑个体与其最近邻的博弈。(i, j)模型人小为10x10的网络，节点数n= 10000,其中每个节点分别与其最近邻的8个节点(称为节点的度，即博弈半径r<2)发生陣弈，包括节点木身在内的九个节点之间的博弈称 为节点的博弈环境。初始时刻网络中的节点等概率的随机选择策略c和d,在博弈的过程小 我们采取同步升级的博弈策略，即所有节点的新策略在下一吋刻同吋影响其他节点。我们模 拟时选择的蒙特r罗步数为20000,并选择最后500步的平均作为输出结果。每个节点都有 两种选择，合作(cooperation)或者背叛(defect