《演化博弈理论及囚徒困境在网络中的应用毕业论文》由会员分享，可在线阅读，更多相关《演化博弈理论及囚徒困境在网络中的应用毕业论文（48页珍藏版）》请在金锄头文库上搜索。
1、演化博弈理论及囚徒困境在网络中的应用毕业论文目录摘要IIAbstractIII目录IV1绪论11.1演化博弈理论及囚徒困境11.1.1博弈论概述11.1.2“囚徒困境”模型11.1.3传统博弈论的局限31.1.4演化博弈论31.2复杂网络41.2.1规则网络41.2.2随机网络51.2.3小世界网络61.2.4无标度网络62囚徒困境博弈在随机网络中的演化82.1复杂系统及合作现象82.2合作的演化82.2.1均匀混合体系中的合作演化82.3囚徒困境在随机网络中的演化102.4引入信用的作用后合作的演化113模拟结果的分析与讨论124总结与展望14参考文献15参考文献（宋体，加粗，小二号字，居中
2、）16致谢（宋体，加粗，小二号字，居中）17附录（宋体，加粗，小二号字，居左）18 .专业.专注. 1 绪论1.1 演化博弈理论及囚徒困境1.1.1 博弈论概述经典博弈论是研究依据其他参与者的效用情况，理性参与者策略之间相互作用的一门科学。博弈的思想自古就有，但是真正的博弈论开始于20世纪20年代。1928年，冯诺依曼证明了博弈论的基本原理，宣告了博弈论的诞生。1944年，冯诺依曼和摩根斯坦的论著博弈论与经济行为将二人博弈推广到多人博弈的情形，奠定了博弈理论的基础，并形成理论体系。1950年至1951年，约翰福布斯纳什在他的两篇开创性的论文n人博弈的均衡点，非合作博弈中给出了纳什均衡概念，利用
3、不动点定理证明了均衡点的存在，这个均衡点又叫纳什均衡点。纳什均衡理论为博弈论的数学化和一般化奠定了坚实的基础。此外，些其他的科学家比如赛尔顿、哈桑尼也对博弈论的发展起到很大的推动作用。如今，博弈论已经成为一门比较完善的学科。博弈论的要素有两点：参与博弈者的目标或利益的相互冲突，以及博弈者为理性人。博弈论就是想表明：在所有参与博弈的博弈个体都想获胜或者希望收益最大化的情况下，博弈个体可以通过借助博弈理论分析计算后找到一种最好的方法，也叫最优策略。博弈的结果不仅取决于参与博弈的博弈个体的策略，同时也取决于其他所有参加博弈的个体的策略。1.1.2 “囚徒困境”模型“囚徒困境”是博弈论中一个非常著名的
4、例子，它是由美国普林斯顿数学家阿尔伯特塔克在1950年提出来的，它的提出奠定了非合作博弈论的理论基础1。曼昆的经济学原理中说：囚徒困境，两个被捕的囚徒之间的一种特殊博弈，说明为什么甚至在合作对双方都有利时，保持合作也是非常困难的。图1.1“囚徒困境”示意图资料来源: W. K. Harold (editor), 1997，Classics in game theory, Princeton, NJ: Princeton University Press具体的“囚徒困境”模型说的是，两个犯罪嫌疑人甲和乙作案后被抓后，分别被警察关在不同的屋子里审讯。警察告诫他们:如果他们两个人都认罪，各判3年;如
5、果两个人都保持沉默，各判1年(可能是由于证据不足);如果其中一个认罪另一个沉默，认罪的放出去，不认罪的判刑5年。甲沉默甲认罪乙沉默二人同服刑1年乙服刑5年，甲即时获释乙认罪甲服刑5年，乙即时获释二人同服刑3年图 1.2 惩罚表格示意图图1.2中的表格给出了“囚徒困境”博弈矩阵。这里，每个囚徒有两种策略:沉默或认罪。在这个模型中，如果甲沉默，那么乙认罪比沉默所获的罪刑少；如果甲认罪，那么乙还是认罪获刑比沉默获刑较少。也就是说无论甲做出什么样的选择，对于乙来说他的最优策略是认罪。同样的，对于甲来说他的最优策略也是认罪。也就是说在这个“囚徒困境”博弈中，双方都认罪是纳什均衡。从“囚徒困境”博弈中我们
6、很容易发现，如果两个人都沉默，各判一年，比两个人都认罪，各判3年好。但是由于他们都从自身的利益处分，所以并没有选择对双方都有利的策略。所以，“囚徒困境”模型反映了个体理性与集体理性的矛盾。在讨论囚徒困境时，我们经常把单独背叛成功所得令为T（temptation 背叛诱惑）；共同合作所得令为R（reward 合作报酬）；共同背叛所得（punishment 背叛惩罚）；被单独背叛所获（suckers 受骗支付）。并且有TRPS,以及2RT+S。在单轮博弈中，博弈个体都背叛是纳什均衡。但是重复博弈的结果将会跟单轮博弈的不同，在重复囚徒困境中，由于两个个体间的博弈可以重复进行，所以博弈参与者将会有机会
7、对前面背叛他的个体实施惩罚，这样欺骗的动机可能被受到惩罚的威胁所克服，从而提高整体的合作水平。1.1.3 传统博弈论的局限在传统或者经典博弈论中，所有的博弈参与者都是完全理性的，也就是所有参与者的策略组合以及相应的利益将会作为一种常识。某件事成为常识，并非像我们日常生活中理解的那样，只要所有的人知道就可以了。在博弈论中，常识意味着你知道，他也知道，你知道他知道，他也知道你也知道。某事成为常识需要信息充分地交流，但是要实现还是不是想象中的那么简单。但是在现实生活中，人们做一件事或做一个决定并不是当作单独博弈进行的，他可能会考虑长远的利益，也会受个人的习惯、信仰、理念影响，还会受社会道德、伦理等很
8、多因素的影响。并且在博弈时，博弈参与者们所得到的信息也是不对等的，也就是由于知识背景、信息收集掌握程度等一系列原因，他们可能做出不同的判断。所以说传统博弈论是将博弈规则简单化、抽象化后想成的一种理论。这种理论在分析情况比较简单的博弈时效果还是不错的，但是要分析复杂问题时，比如生物学、经济学等领域的问题可能就会太过简化而与现实背离。1.1.4 演化博弈论演化博弈理论思想是源于对生态现象的解释，生态学家发现在很多情况下动植物的进化结果都可以用博弈论的纳什均衡来解释。在经典博弈中都是假定博弈个体是充分理性的，但是生物不具有理性，生态的演化是基于达尔文的“优胜劣汰”环境选择进化理论。这种巧合意味着我们
9、可以假定博弈者并不是是充分理性的。1973年至1974年，生态学家斯密斯（Maynard Smith）和普瑞斯（Price）提出了演化稳定策略（Evolutionarily stable strategy ESS）标志着演化博弈理论的诞生。斯密斯和普瑞斯没有假定生物体是充分理性的，而是假定生物体是有限理性的，生物的演化就是生物体间相互竞争，并且根据环境实现自身进化的过程。他们的工作使人们对经典博弈中理性的认识更加深入，此后，演化博弈理论又经过其他一些科学家的发展，比如萨缪尔森、克瑞斯曼等，现在演化博弈理论已经成为体系，也相对完善，在分析解决经济问题中起到了重大作用。一般的演化博弈理论是以随着时
10、间变化的某一群体为研究对象的，以理解群体演化的动态过程，并解释说明为何群体将达到这一状态以及如何达到为研究探索的目的。影响群体变化的因素既有一定的随机性和突变，又有通过演化过程中的选择机制而呈现出来的规律性。大部分演化博弈理论的预测力在于具有一定惯性的群体选择过程，但是同时，这个过程也应该具有突变的动力，这样才能不断更新种族特征。几乎所有的演化博弈模型都是建立在选择和突变这两个方面。选择是指能够获得较高支付，以及以后将会被更多种群中的其他个体采用的策略。而突变是种群中的少数个体以随机的方式选择与群体不同的策略。突变其实是试错过程，也是学习与模仿的过程，在这个过程中，个体的适应性是不断改变的，适
11、应性强的个体可以生存和繁殖，适应性差的个体就将会不淘汰。所以说本质上突变也是一种选择，只不过没是有悖于常理的选择，但是只有好的策略才能生存下来。总之，演化博弈理论是建立在一下三个基本原则上的：（1）异质性，即每个个体并不是完全相同的，不同种群间，同种群的不同个体间都是不同的；（2）适应性，即符合达尔文的自然选择原理的，只有适合当时环境的个体才能生存和延续；（3）选择性，即适者生存的。演化博弈模型有如下几个特征：第一，以参与人群体为研究对象，分析动态的演化过程，解释群体为何达到以及如何达到目前的这一状态；第二，群体的演化既有选择过程也有突变过程；第三，经群体选择下来的行为具有一定的惯性。1.2
12、复杂网络在一个系统中，或者在多人参与的演化博弈中，个体间总是相互作用的。那怎样描述个体间的相互关系呢？网络成为描述博弈个体间相互作用的做好方法。就博弈论而言，参与博弈的个体就可以抽象表示为网络中的节点；而个体间的相互关系或相互作用就可以抽象为网络的边。虽然节点和边可以具体表达很多特性，但我们通常只关心节点之间有没有边相连，而不考虑节点的位置，以及边的长短、形状等等。我们把网络这种不依赖于节点的具体位置和边的其体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。但是，真实网络到底是怎么样的呢？从古至今人们从来没有停止去探索。随着计算机技术的迅猛发展，人们发现大量的真实网络具
13、有小世界效应和无标度效应。美国康奈尔大学的Watts 及其Strogatz教授在Nature上发表了题为“小世界”网络的集体动力学的文章，阐述了复杂网络的小世界效应，并建立了相应的模型。美国Notre Dame大学的Barabasi教授及其博士生Albert在science上发表随机网络中标度的涌现一文，阐述了复杂网络的无标度特性，并建立了相应的模型。至今，复杂网络主要有规则网络、随机网络、无标度网络、小世界网络这四种基本模型。1.2.1 规则网络节点按照确定的规则连接起来，这样得到的网络就称为规则网络。规则网络又被称为格图或d一格。一个d一格是带标号、无权、无方向的简单图。规则网络具有均匀的
14、度分布，并且具有较大的聚类系数和较小的平均路径长度。如图1.1，列举了两种规则网络:图（a）一个个体对应着四个邻居 （b）一个个体对应着三个邻居图1.1 规则网络示意图资料来源: Christoph Hauert & Michael Doebeli Spatial structure often inhibits the evolution of cooperation in the snowdrift game, Nature 428，643(2004)1.2.2 随机网络在本文中主要是研究“囚徒困境”模型在随机网络上演化产生的自适应行为，所以，本文就主要介绍随机网络。随机网络的几何性质以及
15、模型，是由Paul Erds，Alfrd Rnyi 和Bla Bollobs在五六十年代提出的。它的模型建立如下：首先生成n个节点，这n个节点中的任意两个之间以概率p连接起来形成一条边。这个模型看起来非常简单，但是当时的提出还是非常困难的。随机网络的特征是平均聚集程度低而平均路程长度较短，但大规模的随机网络没有聚类特性。并且随机网络的结构和性质都是随着概率p的变化而变化的，它的很多重要性质都是在某个临界p值处突然涌现出来。图1.2节点数N=10，连接概率分别为0.1、0.3、0.8生成的随机网络资料来源:Hisashi Ohtsuki，ChristoPh Hauert，Erez Lieberman & Martin A. Nowak. A simple rule for the evolution of cooperation on graphs and social networks，Nature441，502(2006)1.2.3 小世界网络从真实的世界来看，真实网络不可能像上述的规则网络那样完全规则，也不可能像随机网络那样完全随机。就比如在人类社会中，人们总会跟自己的亲人和朋友一起形成一个小团体，即有一定的聚类特性；但同时，人
