1、1毕业论文开题报告理论物理公共品博弈的空间效应研究一、选题的背景与意义无论对于生物界种群的进化还是人类社会的发展，合作都扮演着至关重要的角色。然而，自私个体之间的无私利他行为与达尔文的物竞天择理论是相互抵触的。在寻求这一问题的答案的过程中，博弈论以及演化博弈论扮演了重要角色并提供了强有力的理论框架。社会和自然界中复杂系统的结构形态和系统结构可以从网络的角度进行描述。近年来,复杂网络研究的兴起与发展,使得人们对各种现实网络的结构演化、复杂性有了比较清晰的认识。而复杂网络理论为描述博弈个体之间的博弈关系提供了方便的系统框架。网络上的节点表示博弈个体,边代表与其邻居的博弈关系。这样一来,就可以利用复
2、杂网络拓扑关系,来研究一些复杂的博弈关系下的博弈。由于真实系统中的个体或要素之间存在策略依赖关系,所以可在复杂网络上建立空间博弈模型。在复杂网络上建立的空间博弈模型更加客观真实，更加符合实际的演化规则，更加贴切生活，使得复杂网络的演化博弈方兴未艾。随着演化博弈动力学行为与复杂网络之间的关系逐渐清晰，空间博弈必定会推动复杂网络中其他领域的发展。而本文将在了解公共品模型的研究现状和数值方法基础上，通过数值方法研究个体的各类空间效应，探索各类空间效应对公共品博弈中合作行为的影响，从而得到相应的研究成果。二、研究的基本内容与拟解决的主要问题1、对公共品模型的研究现状和数值方法进行文献调研2、在了解前人
3、的模型工作的基础上，独立进行模型建立3、对所建立的模型进行计算分析，得到研究结果4、对研究结果进行总结分析，撰写出实验论文三、研究的方法与技术路线1、在公共品模型框架下，分析各种可能的空间行为，基于相关文献及前人模型工2作之上独立建立模型2、对所建立模型通过数值方法研究个体的各类空间效应从而得到研究结果四、研究的总体安排与进度20101215完成基本文献的阅读，了解基本原理和研究背景201012162011115熟悉基本数值方法，并提出自己新的模型2011220113进行模型计算和分析20114进行总结并撰写论文，准备答辩五、主要参考文献1、NOWAKMAANDSIGMUNDK,2004SCI
4、ENCE303,7932、SZABOGANDFATHG,2007PHYSREP446,973、DOEBELIM,HAUERTCANDKILLINGBACKT,2004SCIENCE306,8594、NOWAKMAANDMAYRM,1992NATURE359,8265、HAUERTCANDDOEBELIM,2004NATURE428,6436、SANTOSFCANDPACHECOJM,2005PHYSREVLETT95,0981047、复杂网络上的演化博弈智能系统学报167324785200702200012108、复杂网络上博弈行为的研究进展电子测量技术第30卷第4期TP399、复杂网络演化博
5、弈理论研究综述复杂系统与复杂性科学第5卷第4期10、博弈M白波,郭兴文哈尔滨出版社20053毕业论文文献综述物理学公共品博弈的空间效应研究摘要博弈理论在社会、经济、生物以及生态等系统中存在着广泛的应用,复杂网络理论则是研究复杂系统全新而有力的工具,因此将博弈理论与复杂网络理论相结合成为研究复杂系统一个新的热点概述国内外当前关于复杂网络上博弈动力学的研究情况和发展动态,包括基本的博弈模型、主要关注的问题、以及网络结构和博弈动力学的相互作用等,最后探讨进一步的研究课题。关键词复杂网络演化博弈合作行为正文我阅览了大量关于复杂网络和博弈的相关文献资料。不管是书目、期刊、论文，在这两方面的研究都始终是蓬
6、勃发展硕果累累的。然而关于博弈的问题最终都要归结到对于合作的探究。根据博弈论，合作能给种群内的其他成员带来好处，却常常会损害个体自身的利益。根据达尔文进化论最适者生存的自然法则，有益于种群内所有成员的合作行为应该灭绝。然而，事实并非如此。在真实的生物、社会等复杂系统中在生物和社会等科学领域，合作是一种普遍存在的现象。从单细胞的微生物到高级哺乳动物，从社会性昆虫到人类社会。生物个体之间的合作，增加了整个种群的生存机会。那么自私个体间合作是如何产生和维持的，成为人们讨论的热点问题。为了理解合作行为是如何从自私的个体之间演化产生的，近年来，一些可能的合作机理。如群体选择、亲缘选择、直接（间接）互惠、
7、空间互惠、声望与惩罚等得到一定的探讨。自从ALELROD利用迭代囚徒困境博弈研究合作的演化以来，演化博弈论为研究合作演化提供了方便的数学框架，受到越来越多的关注，囚徒困境博弈和雪堆博弈是被研究者广泛采用的研究合作行为的两个范例。在经典博弈论中，个体被假定是超理性的（所有个体都知道其他个体也是理性的，并且会按照理性行事），且个体对收益矩阵元的信息完全了解。在这种机制下，所有个体最终都会采取纳什平衡策略。但是这种个体的超理性会导致机体的非理性（因为相互合作时集体的收益最大）。一般而言，在复杂的环境中个体4没有充分的能力去选择最佳策略以最大化收益。此时，个体通常根据其所掌握的局部信息采取启发式的方法
8、，做出令其“满意”的决策，这种选择过程表明个体是有限理性的。演化博弈理论着重研究有限性的个体如何在重复博弈过程中，通过自适应学习来实现自身收益的最大化问题。复杂网络理论为描述博弈个体之间的博弈关系提供给了方便的框架。由于真实系统中的个体或要素之间存在策略依赖关系，所以可在复杂网络上建立空间博弈模型。这样就可以利用复杂网络拓扑关系来研究一些复杂博弈关系下的博弈。由于真实的社会网络比一些模型网络复杂，而后者通常只是前者的一个特性或某些特性的反映，因此研究真实社会网络上的演化博弈对揭示合作的演化具有重要意义。而小世界效应、无标度性质等对网络上演化博弈的影响自然受到了研究者的关注，成为了有意义的课题。
9、公共品博弈是以公共品为博弈对象的博弈，这种博弈广泛存在于发杂网络之中。一般来说，公共品是指在消费过程中具有非竞争性和非排他性的物品。因为公共品具有这样的性质，所以集体中的每个人都会希望由其他人来提供，而自己坐享其成，这种行为被称为搭便车。搭便车问题使集体行动变得难以实现每个人都想搭便车的结果，就是没有便车可搭。搭便车问题的存在，解释了很多社会困境。例如，恶劣的环境无人清理，不合理的制度人人抱怨却无人抵制。公共品博弈的理论结果和现实的差异是巨大的。大量的实验研究表明，集体成员的搭便车动机是有限的，合作能够达到一个客观且稳定的水平。这就表明，在重复公共品博弈过程中，个体不仅要考虑自身收益，还受到很
10、多外在因素的影响，如激励与惩罚，而且社会系统中的个体还具有某种异质性称为社会偏好，这种社会偏好使得个体会考虑他人的选择，具体表现为互惠、不平等厌恶、学习和迁移等。很显然，这些外在因素的存在会降低个体搭便车的动机，并提高合作水平。关于公共品博弈的研究贯穿各个方面，在生物与科学领域的研究尤为显著。我主要列举了一下三种说法群体选择学说群体选择学说将种群看作一个进化的单位，在群体层次上考虑公共品博弈。在群体中，那些对种群有利的特征之所以能够保存下来，是因为在进化过程中，虽然群选择与个体选择的方向是相反的，但是个体的选择可能导5致种群的灭亡，这种来自于外部的压力促使个体间相互合作。互惠和强互惠效应互惠机
11、制包括直接互惠和间接互惠。直接互惠中的个体之所以冒着可能会被背叛的风险去跟其他个体合作是因为希望在日后与该个体再次进行博弈时能够取得更大的收益，所以回报才是互惠利他主义者的真正目的。间接互惠的基础是“声誉”。个体选择跟其他个体进行合作是期望提高自己的声誉，得到更多个体的合作，但是这种合作是不稳定的。直接互惠和间接互惠都无法很好的解决公共品博弈中的合作现象，这种情况下，强互惠理论应运而生。强互惠理论认为，人类之所以能维持比其他物种更高度的合作关系，在于许多人都具有这样一种行为倾向在团体中与别人合作，并不惜花费个人成本去惩罚那些破坏群体规范的人，即使这些成本并不能被预期得到补偿。强互惠能够有效的抑
12、制团体中的背叛、逃避责任和搭便车行为，提高合作水平。但实施这种行为需要个人承担成本，这样就带来一个新的问题，成本由谁来负担每一个合作者都会寄希望于其它合作者承担这个成本，即所谓“二阶搭便车问题”。解决这个问题又产生了许多讨论，包括合作惩罚以及制度的制定等。空间效应由于真实系统中的个体或要素之间存在策略依赖关系，我们可以在各种网络上建立空间博弈模型，这样又发现了许多空间因素的影响。比如说公共品博弈中独立者的引入独立者是在公共品博弈模型中引入不参与博弈，但会每局收到少而固定的收益的独立者。这样，在一定R下，就会出现一种动态平衡。除此之外还有很多各种各样的影响，如网络的影响（不同的网络对于合作的促进
13、作用也是不同的）、策略的改变（在博弈中引入学习和迁移的策略，个体在博弈中有一定的几率改变策略和交换位置）等等，也会明显影响博弈的结果。复杂网络上的演化博弈研究是近年来随着复杂网络研究兴起而逐渐引起关注的一个重要研究领域。目前大部分工作都集中在囚徒困境博弈或雪堆博弈研究上，其他类型的博弈还缺乏系统的研究。因此有必要进一步考虑多人博弈的情形，如公用品博弈本文所主要研究的课题，或多策略的博弈等。如石头剪刀布ROCKSCISSORSPAPER博弈近来一些学者开始关注这些问题,也得到了一些有趣的结果。对于自然界中广泛存在的合作行为的理解，以及如何又到自私个体之间产生合作一直是数学、物理、生物、管理乃至工
14、程学科的学者关注的话题。随着复杂6网络的兴起，人们对于字儿按揭中复杂系统的组织结构有了新的认识。从网络结构的角度研究演化博弈行为是一个既具有理论意义又有工程实践价值的课题。目前很多工作只是一些数值仿真结果,由于数学工具的不足,对复杂网络上的博弈动力学进行解析分析是非常困难的,目前的一些近似方法,如平均场方法、对估计方法在异质程度很大的网络很有可能失效因此寻求有效的数学工具,探求更好的理论结果,将一些数值结果命题化、严格化,将是十分有意义的。该课题将在了解公共品模型的研究现状和数值方法基础之上，通过数值方法研究个体的各类空间效应，探索各类空间效应对公共品博弈中合作行为的影响，从而得出在各种因素之
15、间多人博弈情况下的合作行为的发生情况。现实中，公共品博弈普遍存在，当然也存在很多社会困境。考虑到影响公共品博弈的各种因素，如何更有效的促进合作行为的产生成为我们现在研究的主要方向。希望该项研究不仅能在理论方面，更能对真实系统中公共品博弈提供建设性的意见和建议。参考文献1、NOWAKMAANDSIGMUNDK,2004SCIENCE303,7932、SZABOGANDFATHG,2007PHYSREP446,973、DOEBELIM,HAUERTCANDKILLINGBACKT,2004SCIENCE306,8594、NOWAKMAANDMAYRM,1992NATURE359,8265、HAUE
16、RTCANDDOEBELIM,2004NATURE428,6436、SANTOSFCANDPACHECOJM,2005PHYSREVLETT95,0981047、复杂网络上的演化博弈智能系统学报167324785200702200012108、复杂网络上博弈行为的研究进展电子测量技术第30卷第4期TP399、复杂网络演化博弈理论研究综述复杂系统与复杂性科学第5卷第4期10、博弈M白波,郭兴文哈尔滨出版社20057本科毕业设计（20届）公共品博弈的空间效应研究8摘要【摘要】本文基于复杂网络下的公共品博弈演化模型，研究各类空间效应对合作演化动态的影响以及引入奖励机制后合作行为演化的方向。通过允许对
17、合作个体的奖励作为一种积极因素促进合作的产生，结果表明奖励可以通过提供一个避免相互背叛情况出现的方式促进合作的产生。然而与惩罚相比，奖励无法使合作稳定下来，却提高了稳定的合作者的数目。最后分析了复杂网络上公共品演化博弈论的未来发展方向与应用前景。【关键词】公共品；复杂网络；演化博弈；奖励机制ABSTRACT【ABSTRACT】BASEDONTHEPUBLICGOODSGAME,THISTHESISPRESENTSAMODELINWHICHINDIVIDUALSAREREWARDEDWHOCONTRIBUTETOTHEPUBLICGOODSITISSHOWNTHATREWARDISCAPABLE
18、OFPROMOTINGCOOPERATIONBYPROVIDINGANESCAPEHATCHOUTOFSTATESTHATWEDEFECTEACHOTHERMUTUALLYREWARD,CONTRASTWITHPUNISHMENT,ISUNABLETOSTABILIZECOOPERATIONALTHOUGHITGIVESRISETOAPERSISTENTMINORITYOFCOOPERATORSFINALLYUNRESOLVEDOPENPROBLEMSANDFUTURERESEARCHDIRECTIONSANDPOSSIBLEAPPLICATIONAREASFORPUBLICEVOLUTION
19、ARYGAMEONCOMPLEXNETWORKSAREPOINTEDOUT【KEYWORDS】PUBLICGOODS；COMPLEXNETWORKS；EVOLUTIONARYGAMES；INCENTIVESYSTEM9目录摘要8ABSTRACT8目录81研究背景1011博弈论10111经典博弈论、博弈模型与纳什均衡10112从经典博弈到演化博弈1212复杂网络13121复杂网络的特征度量14122复杂网络的分类14123复杂网络上的演化博弈152公共品博弈背景简介621背景简介1722群选择学说1723互惠与强互惠效应1824空间效应193模型建立2131模型介绍2132现象及描述2233结语
20、244结论与展望24参考文献6致谢错误未定义书签。附录错误未定义书签。101研究背景无论对于生物界种群的进化还是人类社会的发展，合作都扮演着至关重要的角色。自私个体之间是如何产生合作的一直是物理、生物、数学乃至工程科学的学者关注的话题。然而，依据达尔文主义，自然选择是基于竞争的，个体将自私的最大化自身的利益，这显然不能解释处处可见的合作行为。为了理解合作行为是如何从自私的个体之间演化产生的，近年来，一些可能的合作机理，如群体选择GROUPSELECTION、亲缘选择KINSELECTION、直接（间接）互惠DIRECT/INDIRECTRECIPROCITY、空间互惠SPATIALRECIPR
21、OCITY、声望与惩罚REPUTATIONANDPUNISHMENT等得到了一定的探讨。而博弈论在寻求这一问题答案的过程中扮演了重要角色并提供了强有力的理论框架。随着计算机技术的飞速发展，对复杂网络的研究也不断深入，人们对现实世界中复杂系统的组织结构有了新的认识。在复杂网络的基础上研究博弈行为成为一个既具有理论意义又有现实价值的话题，受到人们越来越多的关注。11博弈论111经典博弈论、博弈模型与纳什均衡博弈论，又称对策论，主要是研究依据参与博弈的其他个体的策略情况，理性个体所采取的策略之间交互作用下的个体的行为演化。在交互作用中，个体所获得的收益不是纯粹由其自身所采取的策略决定，而是受到很多其
22、他方面的影响，如其他个体的策略、博弈规则等等。博弈论主要是由匈牙利数学家冯诺依曼所创立的，在20世纪40年代作为一门正式的学科发展起来。1944年冯诺依曼和摩根斯坦出版的著作博弈论和经济行为，标志着现代系统博弈论的初步形成。早期的博弈论过于抽象，实用性不强，而且人们对博弈论的研究知之甚少，影响力有限。随着现代博弈论的不断研究发展，它作为一种数学理论被广泛应用于经济、政治、生物、信息等许多领域，日渐成为非常重要且有用的分析工具，为解决不同实体的冲突和合作提供了一种有效的方法。近十多年来，诺贝尔经济学奖先后授予研究博弈论的科学家NASH、SELTEN等人也说明，博弈论越来越受到更多人的重视，也得到
23、了越来越广泛的承认。通常一个博弈由以下5个部分所组成（1）博弈主体，即博弈过程中进行独立决策的个体，在一轮博弈中至少要有两位决策者参与博弈（2）博弈信息，博弈个体所掌握的有利于11策略选择的各方面信息，在博弈中占重要地位，根据博弈个体对参与博弈所有个体收益信息的掌握程度可将博弈分为完全信息博弈与非完全信息博弈（3）策略集，参与博弈的个体可选择的所有可能策略的集合，根据该集合是有限还是无限，可分为有限博弈和无限博弈，其中无限博弈又表现为连续对策、重复博弈和微分对策等（4）收益矩阵，策略选定后，博弈个体所获得的收益是由相应的收益函数或收益矩阵来确定的，根据博弈个体的不同收益情况可以分为零和博弈与变
24、和博弈（5）策略演化，在重复博弈过程中，博弈个体以自身收益最大化为目标进行策略调整。就某一轮博弈而言，当所有个体的策略选定以后，我们可以用集合的形式来描述，S（S1,S2,），其中每一项代表了所对应个体采取的策略，进而得到某种策略概况下个体所获得的收益U。经典博弈论中的一个重要概念纳什均衡（NASHEQUILIBRIUM，是美国科学家约翰纳什在二十世纪提出来的，从实质上说是一种非合作博弈状态。所谓纳什均衡指的是给定参与博弈的其他个体的策略时，任何一个个体都不能通过单方面改变策略而使自身获得更高的收益。换言之，在纳什均衡中，个体所选的策略是该状态下个体的最优策略。纳什均衡在于解释没有外在约束条件
25、下，参与博弈的个体均选择其最优策略而形成的一种均衡结果。首先这种假设是基于参与博弈个体完全理性以及具有共同信息的基础之上的，但是真实系统的复杂性和异质性使得这一点就很难达到；其次，纳什均衡是静态的，其结果没有受到其他任何因素的影响，所以在真实系统中形成的纳什均衡可能是不稳定的；最后，在很多博弈中包含不只一种均衡状态，纳什均衡不能解决多重均衡存在时的选择问题。下面我们以经典的囚徒困境博弈模型为例简要的阐述下纳什均衡的意义。囚徒困境博弈（PRISONERSDILEMMAGAME小偷甲和乙合伙作案，被捕后，警方将两人分别置于两个房间内进行审讯。警方给出的政策是如果双方都拒绝坦白同伴的罪行，两人将会被
26、轻判1年徒刑；如果甲（乙）坦白（背叛）罪行，而乙（甲）拒不供认（合作）罪行，则甲（乙）将无罪释放，而乙（甲）将被重判5年徒刑；如果甲、乙互相揭发对方罪行，则双方均被判刑3年。该博弈的收益矩阵可列表如下甲/乙合作背叛合作1,15,0背叛0,53,3从上表我们可以看出，如果甲选择坦白，即选择“背叛”（DEFECTD乙，则乙也应该选择坦白因为如果此时乙选择合作，甲将被无罪释放，而乙会被重判5年，而如果此时乙也选择背叛，则将会跟甲均判3年，显然，对乙来说，背叛总是最佳策略。反之，对甲来说也是如此。但是整体来看，甲乙的最优策略应该是选择跟对方合作，此时两人均被判1年。这样就陷入了两难困境，那么这种情况下
27、，甲乙两个体应如何做出抉择从理性个体自身利益最12大化为目标来看，相互合作的情况不会发生，对甲乙来说，因为不论对方采取哪种策略，背叛始终是自身的最佳策略（注意到此时集体的收益最低）。所以当双方都选择背叛时，没有个体会主动选择改变策略（因为单方面改变策略使自身收益降低），此时这种相互背叛的状态就是该系统的纳什均衡状态。现实生活中，类似囚徒困境的例子很多，也揭示出各种社会困境。上面所述的是单次发生的囚徒困境，但是在重复囚徒困境中，参与博弈的个体可以通过记忆或学习、或者采取某种报复措施对背叛者进行惩罚，那么在合适的机制下，合作将会作为均衡的结果出现并逐渐占据优势，从而有利于合作策略的涌现与维持。在接
28、近无限次的博弈中，纳什均衡会趋向于帕累托最优（PARETOOPTIMALITY，PAVLOV策略是属于更一般的WSLS的策略模型，指个体如果现在的策略获得的收益大于某个期望水平，那么下次博弈保持该策略不变，否则就改变策略）。112从经典博弈到演化博弈经典博弈论中，个体被假定是超理性的完全信息博弈，而且所有个体都知道其他个体也是理性的，并且会按照理性行事。这种机制下，博弈最终会达到纳什均衡状态，即所有的个体最终都会采取纳什均衡策略。从囚徒困境的例子可以看出，这种个体的超理性会导致集体的非理性（因为相互合作时集体的收益最大）。但是，在真实的复杂社会系统中，个体没有充分的能力去选择能最大化其收益的最
29、佳策略。此时，个体通常根据其掌握的局部信息来做出其相对满意的策略非完全信息博弈，这种选择过程表明个体是有限理性（BOUNDEDRATIONALITY的。演化博弈理论（EVOLUTIONARYGAMETHEORY着重研究重复博弈过程中有限理性的博弈个体之间怎样涌现出合作行为以及博弈个体如何通过自适应学来实现自身收益最大化的问题。演化博弈论（EVOLUTIONARYGAMETHEORY）以达尔文的进化论和拉马克的遗传基因理论为思想基础，将博弈理论与动态演化过程分析结合起来，分析从个体到群体行为的行为机制，研究种群的进化趋势及稳定性，为描述个体之间的相互作用提供了一种通用数学框架。参与博弈的个体采取
30、一定的策略，获得一定的收益（该收益依赖于个体本身的策略跟参与博弈的其他个体的策略）。在每一轮博弈中，博弈个体以某种策略更新规则更新自己的策略，最终达到一种演化稳定策略（EVOLUTIONARILYSTABLESTRATEGY,ESS）所有参与博弈的个体在重复博弈中选择的某个最优的、稳定的策略，即演化博弈中的均衡点。与经典博弈中所讨论的纳什均衡不同，演化稳定策略是一种更加严格的均衡，该策略所对应的收益相对变异者来说是占优势的，而且演化稳定策略只是一种初始状态的优势策略，并不是演化的结果状态。演化稳定策略最大的不足之处就在于它把影响系统的因素都看成是一个个的孤立事件，而在现实中系统常常会受到各种冲
31、击。复杂网络上的演化博弈研究主要是在结构化的群体结构上，考13虑复杂网络上所刻画的博弈者之间的相互作用关系。正是由于这种复杂的拓扑结构，使得复杂网络上的演化博弈呈现出更为复杂的动力学性质。博弈论最早体现在真实的生物学领域中，也最早的应用来解释生物科学中的问题。1973年SMITH和PRICE发表的动物冲突的逻辑，是博弈论第一次被正式的应用于生物学中，也是演化稳定策略的来源。该文运用博弈论的思想从个体选择的角度解释了动物间的争斗为什么从来都是有限且非恶性的。从经典博弈论发展到演化博弈论，其中有3个关键性的内涵发生了转变。第一个是策略内涵的转变。经典博弈论中，博弈个体被假定是超理性的，所有可能选择
32、的不同策略构成策略集。在演化博弈论中个体的超理性被达尔文的“适者生存”规则所代替。那些不采取“理性”策略的个体会在漫长的演化过程中趋于灭绝。第二个是均衡意义的转变。在演化博弈论中，经典博弈论中的纳什均衡被演化稳定策略所代替。演化稳定策略可以是纯策略，也可以是混合策略。与纳什均衡相比，演化稳定策略是一种更严格的均衡。第三个是个体交互作用内涵的转变。经典博弈论中，博弈个体只进行一次博弈，或者与相同的个体进行多次博弈。而在演化博弈论中，博弈个体随机选配成对进行多次博弈，且假定再次遇到相同对手的概率很小。上述3个重要概念的内涵转变，使得演化博弈理论从一个静态的过程成为一个动态演变的理论，更着重于对演化
33、稳定策略的研究，能够描述动态系统的局部动态性质，预测个体行为。12复杂网络最近二十多年来，网络的研究有了突飞猛进的进展。这主要得益于计算机和通信网络技术的巨大进步。借助于它们，我们可以收集和分析以往难以想象的海量的网络数据，并可以研究数以百万计甚至数以亿计大小的网络。通过对真实世界大量复杂系统的研究，人们发现它们的结构不能简单的用规则图或完全随机图来描述。但另一方面，这些复杂的结构有很多共性，比如小的平均距离，高成团系数以及连接度为幂律分布等拓扑性质。人们把这类介于规则图和完全随机图之间的网络称之为复杂网络COMPLEXNETWORKS。复杂网络是研究复杂系统的一门新兴学科,近几年受到研究学者
34、的广泛关注。自然界中的任何复杂系统都可以抽象成为由相互作用的个体组成的网络,如互联网、万维网、航空网、电力网、蛋白质相互作用网以及各种合作网络等。对于复杂网络的研究极大的改变了人们对复杂外部世界的认识，让人们认识到了以前的理论尚未涉及到的问题，也迅速引起了诸多领域中科研工作者的兴14趣，特别是物理学界、生物学界，复杂网络理论得到了充分的探索和发展。研究这些网络不仅对于人们的工作和生活至关重要,而且对于揭示自然界特别是生物系统的奥秘也至关重要。121复杂网络的特征度量随着对复杂网络研究的不断深入，人们提出了许多概念和度量方法来表示复杂网络，这里主要主要介绍节点的度、簇系数和平均路径长度。1、节点
35、的度度是描述网络局部特性的基本参数，指的是与该节点连接的其他节点的数量。度分布（DEGREEDISTRIBUTION，则表示节点度的概率分布。如果某一节点的度分布函数为P（K，表示该节点恰好有K条边的概率。目前度分布较为常见的有两种，一种是指数分布，另一种是幂律分布。度分布函数反应了网络系统的宏观统计特征。2、簇系数（CLUSTERINGCOEFFICIENT，又称为集聚系数，指与同一个节点相连接的一对节点相连接的概率，衡量网络的集团化程度。全连通的网络中，簇系数为1，一般均小于1。3、平均路径长度（AVERAGEPATHLENGTH,APL，指网络中所有节点与节点之间平均的最短距离。节点间的
36、距离是通过从一个节点到另一个节点所经历的边的最小数目来计算的。复杂网络研究中一个重要发现就是大部分真实系统中的平均路径程度都远比想象中小，我们称之为小世界效应。除上述度分布、簇系数和平均路径长度三个最基本的结构特性外，复杂网络还有其他许多度量特征，如介数（反映了相应的节点或边在整个网络中的作用和影响力，具有很强的现实意义）、网络弹性（指网络节点的删除对连通度的影响）等。122不同类型复杂网络简介根据复杂网络的特性不同，衍生出很多不同的类型，由于真实社会网络具有小世界和无标度等特性，所以这里我们也主要介绍这两种网络。随机网络是最简单的复杂网络，在20世纪50年代由匈牙利的两位数学家提出的。在ER
37、随机网络模型中，首先给定网络中的节点数目，然后让任意两节点之间以相同的概率连接在一起完全随机地构成网络。该模型自提出后被广泛应用于社会与生态学的研究。小世界网络模型，由WATTS和STROGATZ提出的，这个模型构建在一维格子基础上，是对一个临近节点耦合的规则网络进行随机化重连之后所能生成的网络模型。与随机网络相比，其显著特性是簇系数大、平均路径长度小。小世界网络上的空间纯策略主要分为两类一类是基于环的小世界网络，另一类是基于方格的小世界网络。根据网络中度的变化特性又可将15小世界网络分为同质与异质。123复杂网络上的演化博弈人们对网络的研究由来已久，图论是最早涉足网络研究的数学理论。图论中网
38、络被称为图，图是网络的数学表达形式，它由顶点和边构成。图论的起源很早，瑞士数学家EUL目在1736年解决了著名的哥尼斯城堡七桥问题，从而使他成为图论和拓扑学的创始人。此后开展的研究工作大多基于网格等规则网络，直到上世纪五十年代，匈牙利数学家EFDOS和RYI创造性的将概率论引入图论并成功地提出了第一个随机图模型一ER模型。在过去几十年中，ER模型已成为随机图论的研究基础并一直占据着复杂网络研究的主导地位。近年来，以还原论和整体论相结合为重要特色的复杂性科学的兴起，促使人们开始关注复杂网络的拓扑结构及其产生机理诸如因特网等大量新型网络的相继出现使得人们对复杂网络性质的了解变得越来越迫切；计算机技
39、术的飞速发展为大规模复杂网络的研究提供了有效的工具，使得人们可以对那些包含上百万乃至于上千万个顶点的网络进行分析，而这在若干年前还是不可想象的事情；不同领域中反映复杂网络拓扑结构的数据库相继出现为复杂网络的研究提供了可靠的实验数据，使得研究者能够对不同类型的数据进行分析进而发现复杂网络所具有的共同特征；上述因素加之各学科间的相互融合使得大规模复杂网络的研究得以快速发展。总体来说，对于复杂网络上的演化博弈的研究主要集中在三个方面一是研究网络拓扑结构对博弈演化动力学的影响，即增加相互作用结构的复杂性，研究其对合作行为的影响；二是在不同的网络结构下探讨各种演化规则对演化的动态影响；三是网络拓扑和博弈
40、动力学的共同演化对合作机制的影响，主要是自适应网络上的博弈动力学，即网络拓扑调整受博弈动力学的影响。下面我们简要的介绍几种网络系统中常用的策略演化规则。1、模仿最优秀者（BESTTAKESOVER）每一轮博弈过后，个体采取与其博弈的个体中最大收益的个体的策略进行下一轮博弈；2、模仿优胜者PROPORTIONALUPDATING个体在进行策略更新时，与跟其进行博弈的其他个体比较，并以某种正比于收益的概率采取收益比自身高的个体的策略进行下一轮博弈；3、配对比较（MATCHPAIRINGCOMPARISION个体随机选择参与博弈的其他个体进行收益比较，并以某种概率（通常是两个体收益差的函数）转变为对
41、方的策略。以上三种是复杂系统中比较常用的策略更新方法。现在大部分研究中采用的更科学的策略更新规则是16式中等号左边表示的是节点X模仿邻居节点Y策略的概率，M代表节点的累计收益，T表示节点的理性程度。当T0时，表示节点完全理性；当T趋向于无穷时，表示节点毫无理性，随机选择；易知，存在一个适当的T使得合作达到最高水平。网络中参与博弈的个体比较多时，策略的更新又受到一个先后秩序的影响，我们称之为同步更新与随机更新。同步更新是指所有参与博弈的个体同时进行策略的更新，通常应用在生物模型中；随机更新也叫非同步更新，是指在网络中随机选择参与博弈的个体进行策略的更新，这种更新规则很好的反应了真实社会系统，因而
42、受到了更多的关注。但在很多情况下，这两种更新方式对博弈的结果并没有明显的影响。172公共品博弈背景简介21背景简介由于现实生活中往往不只是两个个体间的博弈，而是多人之间的博弈，因此有必要将囚徒困境模型扩展为一个多人博弈的模型，这就是本文研究的新的网络模型之一公共品博弈模型。公共品博弈是以公共品为博弈对象的博弈，这种博弈广泛存在于复杂网络之中。一般来说，公共品是指在消费过程中具有非竞争性和非排他性的物品。因为公共品具有这样的性质，所以集体中的每个人都会希望由其他人来提供，而自己坐享其成，这种行为被称为搭便车。搭便车问题使集体行动变得难以实现集体成员存在搭便车的动机，随着集体中社会成员数量的增加，
43、这种动机会更强烈，导致合作水平降低。搭便车问题的存在，解释了很多社会困境。例如，恶劣的环境无人清理，不合理的制度人人抱怨却无人抵制。在公共品博弈中，合作者C的贡献A经过一个R倍的放大后在全体参与者N中平均分配,如果NNC，这所有参与者的收益都将提高R倍。但如果N中出现了背叛者D，不贡献A而同样轩参与分配（搭便车），则可获得比合作者更高的净收益PDARNC/N。从纳什均衡的角度看，公共品博弈中，背叛将始终是最佳策略。从演化均衡的角度看，D将侵入C所组成的团体，并最终取代C。然而，公共品博弈的理论结果与现实的差异很大。大量的实验研究表明，集体成员的搭便车动机是有限的，合作能够达到一个客观且稳定的水
44、平。这就表明，在重复公共品博弈过程中，个体不仅要考虑自身收益，还受到很多外在因素的影响，如激励与惩罚（本文通过引入一个积极因素奖励，来研究其对合作演化的影响），而且社会系统中的个体还具有某种异质性称为社会偏好，这种社会偏好使得个体会考虑他人的选择，具体表现为互惠、不平等厌恶、学习和迁移等。很显然，这些外在因素的存在会降低个体搭便车的动机，并提高合作水平。22群选择学说在群选择学说中，把种群看做一个进化的单位在群体层次上起作用。那些对种群有利但对个体不利的特征之所以能够保存下来，是因为种群的选择会使这一特征出现的频率增加，而个体选择服从群体的利益，是为避免群体被淘汰。公共品博弈与此相似，搭便车行
45、为虽然使个体的收益提高了，但是却损害了集体的利益，导致集体被淘汰，于是，在外界压力下，18个体选择合作来避免此情况的发生。23互惠与强互惠效应互惠机制包括直接互惠和间接互惠。直接互惠中的个体之所以冒着被背叛的风险去与其他个体合作是因为希望在日后与受惠者再次相遇时有可能得到回报，以便获益更大。回报才是互惠利他主义者的真正目的，这次利他是想在下次更有益于自己。直接互惠虽然有利于合作的而建立，但也可能陷入相互背叛的困境。间接互惠的基础是“声誉”。B帮助A是为了提高声誉，以期待第三方C的帮助。在这种情况下，由于报复策略的制约，合作可能因为一个背信行为而导致合作的失败。因为第一个受背叛者的报复行为要经过
46、许多回合之后才会打击到始作佣者，这样许多无辜者会受到惩罚，合作是不稳定的。直接互惠和间接互惠都无法很好的解决公共品博弈中的合作现象，这种情况下，强互惠理论应运而生。强互惠理论认为，人类之所以能维持比其他物种更高度的合作关系，在于许多人都具有这样一种行为倾向在团体中与别人合作，并不惜花费个人成本去惩罚那些破坏群体规范的19人，即使这些成本并不能被预期得到补偿。强互惠能抑制团体中的背叛、逃避责任和搭便车行为，从而有效提高团体成员的福利水平，但实施这种行为需要个人承担成本。这样就带来一个新的问题，既然这种强互惠行为所提高的是团队的收益，那么这个成本由谁来负担每一个合作者都会寄希望于其它合作者承担这个
47、成本，这就是所谓的“二阶搭便车问题”。解决这个问题又产生了许多讨论，包括合作惩罚以及制度的制定等。24空间效应由于真实系统中的个体或要素之间存在策略依赖关系，我们可以在各种网络上建立空间博弈模型，这样又发现了许多空间因素的影响。A独立者的引入在公共品博弈模型中引入不参与博弈，但会每局收到少而固定的收益的独立者。这样，在一定R下，就会出现一种动态平衡。当群体较小时，合作者占优势地位；群体较大时，背叛者占优势地位。B网络的影响不同的网络（规则网络，无标度网络，小世界网络）对于合作的促进作用是不同的。20C策略的改变在博弈中引入学习和迁移的策略。使个体在博弈中有一定几率交换位置会明显影响博弈的结果。
48、213模型建立31模型介绍本文所建立的模型是基于复杂网络的公共品演化博弈模型。模型中只考虑个体与其最近邻的博弈。模型大小为1010的网络，节点数N10000，其中每个节点分别与其最近邻的8个节点（称为节点的度，即博弈半径R1下面我们讨论L取不同值时对合作演化的动态影响。32现象及描述我们取R40时为例A取T01时，概率的演化情况如下图（1）所示23（图1）图（1）表明，合作者概率随局数M（时间的演化状况，开始时呈现震荡变化，随着局数的增加，概率逐渐稳定在确定的数值不再变化。（B下图（2）表示的是合作者概率随随T占总收益的不同比例（T0109）的变化情况（图2）24图（2）表明，随T的单位变化，
49、PC在01之间震荡。C当增益系数R（R20100）变化时，对应的合作者概率随T的变化情况如下I（图3）33结语有关模型结果的理论分析及解释需等待后续工作的完成，在此不再详述。4结论与展望复杂网络上的演化博弈研究是近年来随着复杂网络研究兴起而逐渐引起关注的一个研究领域。关于公共品博弈还缺乏系统的研究，大多数的工作只是一些数值仿真结果。由于数学工具的不足，对复杂网络上的博弈动力学进行解析是非常困难的。目前的一些近似方法，如平均场方法、对估计方法对异质程度很大的网络很有可能失效。因此，寻求有效的数学工具，探求更好的理论结果，将一些数值结果命题化、严格化、一般化，将是十分有意义的。在演化博弈上的博弈动力学还没有得到充分的研究，因此研究网络拓扑和博弈动力学的共同演化将是一个非常有前景的方向。另外，还可以对个体的异质性进行进一步的探究，使得模型更合理的描述、反映现实，解决一些社会、经济中的公开问题。对合作机制的研究，目前还没有统一的认识，依然是演化博弈中最重要的方向，也是当前演化博弈的焦点问题，除了要考虑可能的内在机制外，我们还应考虑下复杂网络上的其他动力学行为，应用演化博弈的思想解决一些实际问题，如“传染病传播问题”、“生物进化”、“市场经济行为规律”等25等。目前关于博弈模型的研究大多集中在囚徒困境模型、雪堆博弈模型等，应拓展我们的研究范围，研究不同类型下的博弈模型，例如本文的公共品
