复杂网络上的博弈演化.ppt

《复杂网络上的博弈演化.ppt》由会员分享，可在线阅读，更多相关《复杂网络上的博弈演化.ppt（58页珍藏版）》请在三一文库上搜索。

1、刘 伟 2009.11.21 Qingdao,复杂网络上的博弈演化,1、博弈 2、复杂网络上的演化博弈 2.1、网络演化博弈的策略更新规则 2.2、网络拓扑对合作的影响 2.3、记忆对网络博弈中的影响 2.4、博弈动力学与网络拓扑共演化 2.5、学习机制导致合作的涌现 3、展望,一个个性和另一个个性的联结 对被联结的个性的命运具有多大的意义？ 你要知道，这是一生的事情， 在我们的背后隐藏着无数的枝节。 陀思妥耶夫斯基,白痴第501页,一个游戏：两人轮流向圆桌上放一元硬币， 谁无法再在圆桌上放硬币则判负，另一方获胜， 假设所有的硬币不允许重叠。你会先放还是后放， 以何种策略确保自己获胜?,博弈研

2、究的对象是游戏(Game)，更确切的说， 是指在具有双方相互竞争对立的环境条件下， 参与者依靠所掌握的信息，在一定的规则约束下， 各自选择策略并取得相应结果(或收益)的过程。 博弈论就是使用数学模型研究冲突对抗条件下最优决策 问题的理论。,博弈论被认为是研究自然和人类社会中普遍存在的合作行为 最为有力的手段。,一、博弈论,博弈模型反映了自私的个体之间的合作竞争关系，能够 很好地刻画生物系统中生物体之间的相互作用关系及演 化动力学。,不论在自然或是社会系统中，经典博弈论告诉我们自私个体 博弈的结果必然是背叛。显然是一个和实际情况不完全吻合 结论。社会经济活动中的绝大多数任务不可能由单人完成， 需

3、要群体的分工和合作。,问题: 为什么自私的个体组成的群体会产生合作行为， 存在什么样的机制，以及什么样的条件才会有合作行为涌现？,通常博弈由以下4个部分所组成: (l)博弈个体：在一个博弈中至少有两位决策者(agent)参与博弈. (2)策略集：个体的博弈策略可以是纯策略，也可以是混合策略博弈的策略集由参与博弈的个体所有可能采用的策略所组成. (3)收益矩阵：当博弈个体选定好自己的策略后，其所获取的收益由收益矩阵中的相应元素来确定. (4)策略演化: 在多轮博弈过程中，博弈个体遵循自身收益最大化的最终目标，即以此目标为指导原则来进行策略调整。,纳什均衡,真实生活中的博弈问题是很复杂的，可能会有

4、很多的参与者，每个参与者都有不同的策略。当参与者们在进行一项博弈的时候，他们应该选择什么样的策略?是否有办法预言出他们的策略组合(s1，s2，sN)?,纳什(Nash)均衡：其核心思想是对于两人或多人博弈，个体的策略演化会趋向于一个均衡态，在此均衡态下所有的个体会同时采取“纳什均衡策略”。,Nash认为，博弈问题的解应该是这样的一组策略，在这组策略中，每一个参与者都无法通过单独改变自己的策略而获得更多的收益。这样的状态就被称作纳什均衡态.,实际上纳什均衡态对所有的参与者来说，不一定是最好的结局。,下面以囚徒困境博弈和雪堆博弈为例来阐述纳什均衡,经典博弈模型,囚徒困境博弈: 两个小偷A和B合伙作

5、案，被捕后被隔离审讯.如果双方都拒绝坦白同伴的罪行，两人将会被轻判1年徒刑;为此，警方设计了一个机制:如果A揭发B的罪行，B拒不供认A的罪行，则A将无罪释放，而B将被重判5年徒刑;如果A、B都揭发对方罪行，则双方均被判刑3年. 在此情况下，自私的个体应如何做出抉择?,合作(Cooperate-C) or 背叛(defect一D),不论对手采取哪种策略，选择背叛策略都是最佳的，即理性的个体最终会处于相互背叛的状态(注意到此时的集体收益低于两人同时选择合作时的情况). 这种相互背叛的状态(D，D)就是系统的纳什均衡态。,对于两人博弈，收益矩阵元通常用(R、S、T、P)来表示,相互合作则二人同获得较

6、大收益R，相互背叛则同获较小收益P，一方合作一方背叛，则背叛者获得最高收益T，而合作者获得最低收益S，即参数满足关系:TR P S，此外2RT+S，即相互合作能获得集体最高收益.,在一个风雪交加的夜晚，两人开车相向而行，被一个雪堆所阻，如图所示.白色和灰色分别表示合作策略与背叛策略.与囚徒困境博弈不同，对于雪堆博弈，收益矩阵元满足关系: TR S P,雪堆博弈:,假设铲除这个雪堆使道路通畅需要付出的劳动量为c，道路通畅则带给每个人的好处量化为b(c)。,如果两人一齐动手铲雪，则他们的收益为R=b一c/2(分别承担劳动量c/2);如果只有一人下车铲雪，虽然两人都能及时回家，但是背叛者逃避了劳动，

7、它的收益为T=b，而合作者的收益为S=b一c;如果两人都选择不合作，则两人都无法及时回家，其收益量化为P=0.雪堆模型的收益矩阵可表示为,那么，理性个体的最优选择是什么呢?,如果对方选择背叛策略(呆在车中)，那么另一方的最佳策略是下车铲雪(因为按时回家的利益b一c好于呆在车中的背叛收益0); 反之，如果对方下车铲雪，则自己的最佳策略是呆在舒服的车中.所以，不同于囚徒困境博弈，在雪堆博弈中存在两个纳什均衡态：(C，D)和(D，C).即雪堆博弈中的NE为两人均以概率r选择背叛，概率1-r选择合作，其r=c/(2b-c)称为损益比。,雪堆模型与囚徒困境不同：遇到背叛者时合作者的收益高于双方相互背叛的

8、收益.因此,一个人的最佳策略取决于对手的策略： 如果对手选择合作， 他的最佳策略是背叛； 反过来， 如果对手选背叛， 那么他的最佳策略是合作。 这样合作在系统中不会消亡， 而与囚徒困境相比， 合作更容易在雪堆博弈中涌现。,演化博弈论,传统博弈论中，常常假定参与人是完全理性的，且参与人在完全信息条件下进行。而演化博弈理论并不要求参与人是完全理性的，也不要求完全信息的条件。 演化博弈论是把博弈理论分析和动态演化过程分析结合起来的一种理论。根据演化博弈理论，博弈双方的策略最终收敛到演化稳定策略上。,演化稳定策略必须满足的条件：如果几乎所有的个体都采取该策略，那么该策略的个体适应度要比任何可能的变异策

9、略要大。,演化稳定策略的提出最初是为了精炼纳什均衡 ,通过借助生物界进化论中优胜劣汰的思想 ,丢弃参与者完全理性的假设 ,认为均衡是有限理性的个体随时间的推移寻求优化这一目标的长期结果。 因此 ,演化稳定策略具有鲁棒性 ,可以抑制噪声 ,它是纳什均衡的精炼。,演化博弈论着重研究是在一个动态过程中有限理性的个体如何在重复博弈过程中，通过自适应学习来实现自身收益最大化的问题。它把均衡看作是过程调整的结果。 经典博弈论到演化博弈论的3个关键概念的内涵式改变： （1）策略：不同行为 到生物系统中的不同类型物种本身 （2）均衡：纳什均衡到演化稳定策略(ESS)； （3）个体相互作用（博弈个体与博弈次数）

10、,二、复杂网络上的演化博弈,复杂网络理论为描述博弈个体之间的博弈关系提供了方便的系统框架. 网络上的节点表示博弈个体 ,边代表与其邻居的博弈关系.在每一时间步长 ,节点与其所有邻居进行博弈 ,累积博弈获得的收益 ,然后根据更新规则进行策略更新 ,如此这样重复迭代下去.,在传统的演化博弈理论中通常假设个体间以均匀混合的方式交互，即所有个全部相互接触，然而，现实情况中个体间的接触总是有限的，个体仅与周围的少数其他个体接触.这样我们就可以在博弈理论中引入网络拓扑的概念。,网络上的演化博弈研究主要集中于3个基本的方向: (l)研究网络拓扑结构对博弈动力学演化结果的影响; (2) 一定的网络结构下，探讨

11、各种演化规则对演化结果的影响;,每一个模型都可以分成几个模块，如使用的博弈模型、 更新规则、网络结构等。,(l)网络中所有的参与者与其网络上的邻居进行博弈，并获得收益。每个参与者的收益为与其所有邻居发生博弈得到收益的总和。 (2)然后参与者将他的收益与他在网络上邻居的收益进行比较，按照一定规则改变自己的策略。,虽然使用的博弈模型和具体的模拟细节各不相同，但基本的 模拟过程是类似的，这个模拟过程是分回合进行的，每个回 合包含两步:,(3)网络拓扑和博弈动力学的共演化，主要是自 适应网络上博弈动力学 ,即网络拓扑调整受博弈动力学影响.,2.1网络演化博弈的策略更新规则：,(l)模仿最优者：即在每轮

12、博弈过后，个体采取其邻居中获得最高收益的个体的策略进行下一轮博弈。 (2)模仿优胜者：即个体在策略更新时，同时参考那些收益比自身高的邻居的策略，以正比于他们所得收益的概率进行策略转变。 以上两种规则可以统称为模仿策略.,模仿策略基本思想是个体的更新策略，根据邻居中收益最高的个体策略进行模仿，以期获得更高的收益。,每个节点(对应博弈者假设为P1)随机的选取他的一个邻居节点(对应博弈者假设为P2)，P1以一定概率W模仿P2的策略，常用的演化规则如下,其中，Ui表示Pi的累积收益，参数0为噪音，代表了一种非理性行为的可能，一般是一个很小的值，常取0.1。当时，表示所有的信息都被噪音淹没，策略进行完全

13、随机的更新；当0时，表示确定的模仿规则，即当P2的累积收益高于P1时，P1则采取P2的策略。,(3)配对比较：即个体随机选择某一邻居进行收益的比较，以某个概率(为此两个体收益差的函数)转变为对方的策略!,其中，kmax为P1与P2中较大度节点的度，P,T,S,R为22收益矩阵元素。,另一类演化规则,(4)随机过程方法：通常考虑Moran过程(birth一death) (或者death一birth过程) ， 即在策略更新时，以正比于个体适应度(由收益来衡量)的概率产生一个新的个体，然后随机取代此个体的某个邻居。,Moran过程是将Darwin的进化思想直接引入到演化博弈中。一个实际背景是种群中的

14、变异入侵，以下图为例，种群中所有个体“C”，当某个个体发生变异后，变为”D”，以后每一步考虑随机移去一个个体，并以正比于原种群中“C”个体适应度的概率生成一个新的“C”个体，否则生成一个新的“D”个体。在适应度函数满足一定条件时，“D”个体可能完全侵占整个种群(Invade)，,Martin A.Nowak等人研究了这类种群侵占问题，将某种策略从种群中仅存在一个变异个体时，最终能侵占整个种群的概率定义为策略的扎根概率。当入侵策略的适应度为原策略的r倍时，则扎根概率,其中N为种群个体数量。,死生过程是Moran过程的一个自然推广，原始网络中存在合作“C”、背叛“D”两种策略，按照连边关系个体之间

15、进行博弈，获得一个累计收益，其中b表示合作收益，即遇到对手采取合作时获得收益；c表示合作代价，即个体采取合作获得负收益。随机选择选择一个个体死亡(假设为位于中间位置的“D”节点)，则其所有的邻居按照正比于个体适应度的概率产生一个后代，填补个体死亡后留下的空位。重复这一过程，种群中的策略将达到动态平衡。,探索由自私个体组成的群体中合作行为产生的机理是演化博弈研究关注的核心问题之一。,2.2 网络拓扑对合作的影响,当个体均匀混合，即个体间的接触网络为全连通图时，相互背叛是唯一的稳定态，合作无法出现，那么改变网络结构能否导致合作行为的出现呢?,一个影响深远的工作是Nowak和May在1992年所做的

16、 “空间博弈”研究。,（1）规则网络上的博弈,Nowak和May扩展了囚徒困境博弈模型，将参与博弈的个体置于二维格子上，每个个体与直接相邻的4个邻居进行博弈，并累计收益，然后在更新策略时，一个个体与它的邻居比较本轮的收益，取收益最高者得策略作为下一轮博弈的策略，直到网络进入稳定状态为止。,规则网络囚徒困境模型：,为了便于理论分析, Nowak采用了弱囚徒困境博弈，即令 T = b 1, R = 1, P = S = 0。Nowak指出这种弱化囚徒困境 所得的演化结果与-1S 0时的结果相同。,Nowak发现引入空间结构后,通过演化,当b在一定范围之内(1b2) ，合作者可以通过结成紧密的簇来抵

17、御背叛策略的入侵，如图：,虽然这种合作簇并不固定,其形状也会随时间的改变而改变,但它并不会消亡,并且最终系统中合作者的比例(被称为合作频率,是衡量系统合作涌现程度的重要指标)会趋于稳定。,他们发现当个体间的接触网络具有空间结构时，如方格网络，在囚徒困境博弈中合作行为能够出现并且稳定维持.其原因是在显著的空间结构效应下，合作者可以通过相互结成紧密的簇来抵御背叛者的入侵.这个发现首次指出了网络结构对博弈演化起着重要的作用.,规则网络雪堆模型 Hauert和Doebeli将博弈个体置于格子上,分别针对度为3, 4, 6, 8的4种拓扑结构情况,根据雪堆博弈模型展开演化，如图，得出不一样的结论：,规则

18、格子上雪堆博弈的合作频率低于模仿者动态下的演化稳定策略说明空间结构抑制了合作的产生。这是因为与囚徒困境的斑图不同,在雪堆博弈中合作者更容易聚成丝状簇（如图）,这就导致了当损益比r较高时，背叛者容易入侵，使系统合作频率下降，这是雪堆博弈与囚徒困境在合作演化上的本质区别。,Hauert的工作揭示了空间结构辩证的作用一种博弈中促进合作的因素可能在另一种博弈中扮演了相反的角色。这促使人们重新发掘隐藏在空间结构背后的真正推动合作涌现的决定性因素。,（2）小世界网络上的博弈,小世界网络囚徒困境,Hauert和Szabo基于规则方格，在保持度分布的前提下，对生成的均匀小世界网络和随机均匀网络作了研究。他们应

19、用一种被广泛采用的随机演化策略：一个节点x更新策略的时候，随机地在它的k个邻居中选择一个y，在下一轮中，x以概率,选择y本轮的策略作为自己下一轮的策略。上述 公式来源于统计力学中的费米函数，为环境中的噪音等不确定因素，设为0.1；P x 为x本轮的累积收益。,研究表明：均匀小世界网络和随机均匀网络比规则格子更有利于合作的涌现，这归因于长程边的作用。 Santos等也对均匀小世界网络与WS小世界网络作了对比性分析。与Hauert采取的策略取代规则不同，他们采用Schlag比例模仿策略，即如果Px Py，下一轮博弈中，x保持自己的策略不变，反之以概率 采取y的策略。 其中，kmax是x，y两节点中

20、的最大度。,基于此得到更一般的结果：异质因素促进合作的涌现。 1、小世界网络中通过移边产生的异质性使其比规则格子更利于合作的涌现； 2、具有度异质特征的WS小世界网络与度均匀分布的小世界网络比较，由于节点度变得异质导致了前者得合作频率比后者高，而后者合作频率的变化主要由长程边使网络中聚类系数的变化引起的。,小世界网络雪堆博弈 Tomassini等应用不同的演化规则作用在不同的重连概率的小世界网络上，细致地分析了小世界网络上的鹰鸽博弈。 发现小世界网络的合作行为与博弈采用演化规则，收益比以及小世界网络的重连概率息息相关。三者的交互作用使得空间结构时而促进合作的涌现，时而抑制合作的产生。,尚丽辉等

21、针对现实生活中朋友关系网络的距离相关特性，研究了基于距离的空间小世界网络上的雪堆博弈，发现与规则网络相比，距离无关的小世界网络促进了合作的涌现；而距离相关的小世界网络中，幂指数增加导致了长程连接的减少和短程连接的增加，这使网络在损益比较大时抑制合作的产生。,不同幂律指数下距离相关的小世界网络上的雪堆博弈合作曲线,（3）无标度网络上的博弈,无标度网络囚徒困境 实际生活中很多网络诸如因特网、航空网等都具有无标度的特性，其节点的度分布满足某种幂律的特性。 Santos对比了规则格子、随机图、随机无标度网络和BA无标度网络对合作涌现的作用（下图），认为由于无标度网络中节点之间的度存在极大地差异，合作行

22、为容易在大度节点之间的传播，进而带动了大量小度节点在无标度网络中传播，也就是说，无标度网络是目前最有利于合作涌现的网络结构。 Gomez-Gardenes根据个体的稳定时的状态，将其划分为3类：纯策略者、纯背叛者和策略摇摆者。,无标度网络雪堆博弈 Santos将研究无标度网络上囚徒困境的方法移植到雪堆博弈上，观察到类似于上图的现象，这说明无标度特性同样有利于雪堆博弈中合作的涌现。 通过对小规模网络（128个节点）进行仿真，弱化了影响合作涌现的无标度网络其他统计学特性，着重突出了节点度的异质性的因素。再次验证了关于异质因素促进合作涌现的一般性结论。,指出无标度网络为研究演化博弈理论提供了统一的理

23、论框架。,荣智海等研究了无标度网络上的扩展雪堆博弈(即一种可从雪堆博弈连续变化到囚徒困境的博弈 ),发现无标度网络异质性的增加使得合作的稳定性增强。 而且对于相同的纯合作比例 ,纯背叛者比例增加 ,策略摇摆者比例减少。 这说明越异质的网络 ,个体越倾向于选择稳定策略.,度相关性对两类博弈的影响,Rong等首先研究了无标度网络的度一度相关性对合作行为的影响.研究表明 :在囚徒困境中 ,中性网络 (即呈现度不相关特性的网络 ,例如 BA网络 )的中心节点对于大度邻居与小度邻居的选择是最合理的 ,既与少量中心节点相连 ,又与他们共享很少量的邻居。所以其较之同配或异配网络的合作频率更高 ,最利于合作的

24、涌现。 当无标度的网络结构呈现同配性质，即连接度大的节点倾向于和连接度大的节点建立连接时，由于中心节点和边远节点(连接度一般较小)的“通讯渠道”的减少，使得中心节点的合作策略难以传播出去,网络总体的合作频率呈现下降的趋势。 反之 ,如果无标度网络呈现度异配性时 ,中心节点之间的联系被切断 ,一方面不利于合作策略在中心节点之间扩散 ,抑制合作频率的上升 ;另一方面被孤立的中心节点可以和周围小度节点凝结成坚固的簇 ,即使背叛的诱惑非常大时也能有效抵御背叛策略的入侵。,对于雪堆博弈 ,越同配的网络其背叛者拥有越小的平均度 , 这说明与囚徒困境博弈类似 ,由于网络变得同配后中心节点 对于小度节点的控制

25、能力减弱 ,进行雪堆博弈的背叛者也主 要集中在小度节点 。 异配网络当 r较小时 ,雪堆博弈的合作 频率会低于均匀混合状态的均衡频率。 可见 ,度相关性对于 囚徒困境博弈的结论完全适用于雪堆博弈.,两图的横坐标为背叛相对于合作的收益 b, 纵坐标为合作频率 ,rk 为度相关性系数。,2.3、记忆对网络博弈中的影响,在复杂网络博弈演化模型中，参与者在模仿周围邻居收益的时候，一般都假设参与者，也就是说在模型中并不考虑记忆效应.而在现实生活中，人们的收益并不对时间进行累加是不可能不参考以往的经验的，关于这些经验的记忆也不会迅速遗忘.尤其是在人们选择改变的时候，往往会更加谨慎的考虑这些经验，历史记忆的

26、效应经常会扮演一种重要的角色。,考虑到了人的有限记忆的特性，也就是人不可能记录以前发生的所有事情的信息，那么就需要记录最有用的信息。另一方面，人只能记录有限的时间段内所发生的事情，所以我们假设每个个体的记忆长度有限，长度为M，即为从上一时刻到M时刻以前的历史最佳策略.然后每个个体根据自身的历史记忆进行决策.为了简单起见，我们采用多数者规则，即采用C或D策略的概率正比于C和D在记忆中的数量:,其中Nc和ND分别是C和D的数量.然后所有个体更新记忆。 重复以上步骤，系统就会演化下去.,Wang Wenxu等人考虑了一种基于记忆机制的空间雪堆博弈，并考察了记忆效应对有四个或者八个邻居的二维周期性格子

27、网络和无标度网络中的雪堆模型的作用.考虑个体根据过去的博弈结果的记忆，选择最佳策略，记录当前博弈结果并更新记忆库。模拟的结果表明在不同的收益函数参数r下，记忆能力对网络中合作态密度的影响是不同的.,(i)合作频率fc具有分段结构，分段个数对应节点的配位数; (ii)图像对于坐标点(0.5，0.5)呈180度旋转对称; (iii)记忆长度M并不影响分段点c的值，但是对不同段fc有很大影响; (iv)对于很大的收益参数r，系统仍然表现出较高的合作水平，这与Hauert等人得到的结果有很大不同.这表明即使自私的个体为了使自身利益最大化而做出决策，合作在欺骗者受益很高的情况下仍然能够产生和持久。,二维

28、网格上的博弈行为,在M=1的时候，系统中的合作行为表现出了大的震荡，如左图的插图所示,4邻居和8邻居二维网格上合作水平与博弈模型参数的函数关系.插图中为合作水平与历史记忆长度的相关性以及在历史长度为1时的演化行为,无标度网络上的博弈行为,(i)与规则格子非常不同的是，fc是r的非单调函数，并存在一个 最优值.这个有趣的现象说明适当鼓励自私的行为反而能够更好 地促进合作; (ii)与规则格子上的情况相同，fc曲线的连续性被一些突然的增 加打断。连续段的数目对应于平均度; (iii)两幅图都以坐标点(0.5，0.5)为180度旋转对称; (iv)记忆长度M不影响不连续点r的值，而只影响介的值。我们

29、 进一步细致研究了M如何影响fc。我们发现存在一段特殊的区域，在这段区域M对fc起不同的作用.,当M=1时，系统同样存在大震荡,无标度网络上的合作行为与博弈参数的函数关系，在交叉点处合作水平与记忆长度的关系以及不同策略个体所占据的节点平均度和博弈参数的关系,模拟表明 ，基于记忆的空间雪堆博弈中随着损益比的增加， 合作频率呈现阶梯状下降，并给出了突变点处的损益比与 规则网格中节点邻居数量的关系；而合作频率与记忆长度 之间则存在比较复杂的关系，通常来说，记忆长度的增加 有利于合作频率的提高，而尝过一定长度后，记忆对合作 的影响逐渐减弱，甚至不利于提高合作频率.,2.4、博弈动力学与网络拓扑共演化,

30、大多数复杂网络上的演化博弈研究都是基于静态网络的，即网络拓扑从博弈一开始就固定不变了.而实际上真实网络是动态演化的，因此所考虑的静态网络只相当于真实网络的一张快照。 复杂系统最本质的特点就是反馈，并利用反馈信息实现自适应和自组织.真实社会中的博弈不但会受到社会人际关系结构的影响，而且反过来也可以影响社会关系结构。换句话说，一方面网络的拓扑结构对其上的动力学过程会产生影响，另一方面这种影响又会反过来“塑造”网络结构本身,调整网络拓扑（或社会关系）。,zimmermann等研究了动态网络上演化博弈: 从一个随机网络开始，个体与邻居进行囚徒困境博弈，个体按照模仿最优者进行策略更新.在动力学的演化过程

31、中，如果一个背叛者发现它模仿的背叛邻居的收益比自己高，则这个不满意的个体以概率p移走与被模仿的背叛者之间的作用边，重新在网络中随机选择一个节点连接，这样网络中的边数保持不变.,研究表明只需要一个小概率p(0.01)就可以使动态网络中合作频率达到一个高值，此时网络呈现等级结构，而且随着移边概率p的增加，网络的聚类系数增加，网络异质性增强这是由于越来越多的背叛者因“失道”而寡助，合作者因“得道”可以成为中心节点.,作者指出合作者占据中心节点具有很强的鲁棒性:当网络演化到稳定状态时强行把网络中收益最高的合作者变为背叛者，会使网络合作频率出现短暂震荡，然而经过一段暂态过程后，网络演化为一个新的等级网络

32、，合作者重新占据中心节点，动态网络的合作水平与震荡前相比没有明显变化.,Pacheco等同样研究了个体策略与网络结构协同演化的网络博弈模型.在他们的模型中，结构演化和策略演化具有不同的时间尺度，分别记为Ta和Ts.当网络结构演化时，采取不同策略的个体以相应的概率建立连接，通过这些连接进行博弈并获取收益，策略演化则采取配对比较规则.,当网络结构的演化速度远远慢于个体进行策略更新的速度时，此博弈模型等价于在静态网络结构上的博弈演化; 而当网络结构演化速度远远快于个体策略更新速度时，上面的协同演化机制则导致博弈矩阵元的数值进行了不同标度的重整化.其直接的结果是矩阵元数值大小的排序关系发生改变，从而使

33、得原先的博弈类型发生了本质性的转变，所产生的博弈动力学相当于博弈个体在一个全连接图上进行着另一种类型的博弈. 博弈类型转变的直接结果是使得原先处于弱势的策略，例如囚徒困境博弈中的合作策略，有可能变成处于强势的策略，从而有利于合作策略的涌现与维持.,考虑个体带简单记忆的网络拓扑与博弈共同演化的简单模型.初始网络从规则随机图开始，每个节点与其所有邻居连续进行囚徒困境博弈n轮，在每一轮，节点依据配对比较更新规则进行策略调整，同时记下邻居作弊次数.博弈完n轮后，随机选择m个个体进行邻居关系调整.被选中的个体将把连到作弊次数最多的邻居的边断开，然后随机重连到该邻居的一个邻居.参数n, m可以看成是博弈动

34、力学和拓扑调整的时间尺度.在我们的模型中，策略更新采用同步方式，拓扑调整是异步的，因此，拓扑调整要比博弈动力学缓慢很多，这与现实是符合的.,囚徒困境模型,图中给出了网络拓扑随着个体调整邻居关系而变化的过程. 从图(a)可以看出，演化的网络是异配的，即度大的节点倾向于与度小的节点相连.由于我们的拓扑调整规则是断开重连到邻居的邻居，在拓扑调整中度大的节点易于一般的节点被其它节点搜索连接上，因此网络呈现出异配性.同时，拓扑调整也造成了网络的异质性， 图(b)显示了网络度的方差变化情况.可以看出，随着网络的演化，网络变得越来越异质，而异质性是利于合作产生的.因此在拓扑和博弈共同作用下，合作水平会慢慢增

35、强，如图(c)所示. 图(d)给出了网络中C一C/C一D/D一D边的比例变化情况.C一C边数不断增多，而C一D和D一D边最终受到抑制而消失.这说明拓扑调整加强了合作者和合作者之间的同配连接，削弱了C一D和D一D之间的连接，从而使得整个网络向有利于合作者的方向进行演化，最终使得合作者占上风.,上图给出了对应于不同b时，合作者的比例随着调整拓扑次数m的变化结果. 可以发现，在保持平均度、博弈轮数不变的情况下，对于固定的b，存在调整拓扑次数的临界值mc，当mmc时，合作者的比例将会演化到100%.同时，图中的插图给出了固定其它参数时mc随着b的变化情形. 即随着作弊收益b的增加，必须使调整拓扑次数相

36、应地增加，才能保证合作者占上风. 结果表明了拓扑和博弈动力学共同演化是促进合作水平提高的一个重要机理.,上面模型中假设个体断开与作弊次数最多的邻居相连的边，再重连到此邻居的邻居.事实上，更为合理的情形是，个体断边重连时，既可以与邻居的邻居形成新边，也可以与除邻居之外的节点相连.因此基于以上模型，我们假设个体断边重连时，以概率p连到邻居的邻居，反之，以l一p的概率随机选择除邻居之外的节点相连.这里参数p的大小表明个体与个体之间产生新边时的“有序性”与“随机性”的对比.当p0时，个体随机选择除邻居之外的节点产生新边(完全随机性);当p1时，个体选择邻居的邻居产生新边(有序性);当0p1时，个体重连

37、的新边介于完全随机性与有序性之间. 因此这个假侧良好地反映了现实情形中社会网络的演化特点:通常人们可以通过朋友介绍，认识朋友的朋友;也可以偶然地不通过朋友介绍结交一个新朋友。,上图给出了合作水平随着参数p的变化情形. 可以发现，在博弈关系和策略更新共同演化的情形下，断开旧边产生新边中的“有序性”的倾向越大，越不利于合作的产生.换言之，在共同演化情形下，断边重连到邻居的邻居并不利于合作.相反地，如果随机地选择除邻居之外的节点作为新的博弈对象，将会有助于合作现象的涌现.,Santos等人考虑了网络拓扑调整与博弈演化之间的时间尺度的关系，并假设不满意博弈结果的节点以一定概率断开与邻居中背叛者的边，并

38、随机重连到背叛者的邻居，发现存在时间尺度之比的临界值，一旦超过这个临界值，合作将会占上风。,采用雪堆博弈模型，网络模型初始有m0 =10 个随机连接的节点， 每个节点的初始状态随机赋予C或D。所有个体同时博弈并根据 收益矩阵计算所得到得收益，然后任意一个节点i 随机选择一个 邻居j来更新自己的策略，i学习j 策略的概率由它们之间收益的 差别决定，即,雪堆博弈模型,其中Mi和Mj是i和j的在上一轮博弈中的总收益。这里T刻画决策中的噪声，也即随机因素。,注意：对于不同的网络结构噪声起不同的作用。因为网络规模是不断增加的，所以很难保证噪声起相同的作用，因此在模型的演化过程中将T固定为0.1.,当个体

39、策略更新结束后，一个新的个体加入到已有网络中， 并且连接m个已有的老的个体，偏好连接的概率正比于已 存在节点上个体的收益,其中 Mi和Mj是i和j在博弈过程中的总收益，W是一个可调参数，反映个体加入系统之初的原始资本，为简单起见，设W为常数。,这种基于收益的偏好选择规则反映了社会系统中的富者越富的马太效应，同时也将博弈的演化动力学与网络结构的演化耦合在一起，这个新加入的个体随机选择策略，并且老的个体在下一轮博弈开始时保持原来的策略，重复以上步骤，网络规模就会增加。 结果表明无标度网络结构可以通过博弈与网络结构的共演化产生，这为无标度网络的产生提供了新的解释.,2.5、偏好学习机制导致合作的涌现

40、,采用BA模型生成无标度网络.每一个节点由一个个体占据。所有个体同它们的邻居同时进行博弈，并相应获得收益.在策略更新阶段，每个个体学习某一个邻居的策略来更新自身的策略.选择邻居的概率与邻居所在的节点度有关，即,其中是一个可调参数，求和范围为i所有的邻居。当 =0时，完全随机选择邻居，模型退化成了最初的随机更新规则.而当 0时，度大的节点有更大的概率被选中;相反，当 0时，度小的节点有更大的概率被选中。 在自然界和社会中，一些有很高声望和地位的个体具有相应的比较大的影响力，这种影响力可以很自然地用个体所在节点的度来反映。因此偏好选择机制旨在描述演化博弈中个体所具有的不同的影响力.,在选出某一个邻

41、居y之后，x采用y策略的概率由他们之间归一的收益之差决定，这一规则由Szabo等人提出,其中Mx和My是x和y总的收益。如前所述，这种选择概率考虑了自然和社会系统中个体有限理性的特点。Mx / kx为归一的收益。这种归一避免了节点度的差别造成的影响。,3、展望,复杂网络上的演化博弈研究是近年来随着复杂网络研究兴起而逐渐引起关注的一个重要研究领域.目前大部分工作都集中在囚徒困境博弈或雪堆博弈研究上，其它类型的博弈还缺乏系统地研究.因此有必要进一步考虑多人博弈的情形，如公用品博弈或多策略的博弈,加石头一剪刀一布博弈. 目前大多数工作只是一些数值仿真结果，由于数学工具的不足，对复杂网络上的博弈动力学

42、进行解析分析是非常困难的.目前的一些近似方法，如平均场方法、对估计方法对异质程度很大的网络很有可能失效.因此，寻求有效的数学工具，探求更好的理论结果，将一些数值结果命题化、严格化、一般化，将是十分有意义的.,相比于较成熟的网络结构对博弈动力学的影响的研究，以下两个方面的研究还仅仅处于起步的阶段: (l)设计适当的动力学演化机制使得合作行为在系统的演化过程中更容易涌现与稳定维持; (2)网络拓扑结构与博弈动力学的协同演化,另外，还应对个体的学习、记忆等能力上进行更为合理的描述，使得模型能更好地反映现实. 对于合作机制的研究依然是演化博弈研究中的一个重要方向.目前演化博弈主要集中在对合作行为的研究上.除此之外，还可以考虑复杂网络上的其它动力学行为，应用演化博弈的思想，解决一些实际问题，如在“路由设计”，“病毒扩散”，“生物进化”，“控制系统设计”，“市场经济行为”，“信息传播” 等问题上做进一步的探索将是十分有意义的.,