复杂网络上的博弈演化课件

2009.11.21Qingdao复杂网络上的博弈演化1、博弈2、复杂网络上的演化博弈2.1、网络演化博弈的策略更新规则

2.2、网络拓扑对合作的影响2.3、记忆对网络博弈中的影响2.4、博弈动力学与网络拓扑共演化2.5、学习机制导致合作的涌现3、展望一个个性和另一个个性的联结对被联结的个性的命运具有多大的意义？你要知道，这是一生的事情，在我们的背后隐藏着无数的枝节。

——陀思妥耶夫斯基,《白痴》第501页博弈论被认为是研究自然和人类社会中普遍存在的合作行为最为有力的手段。一、博弈论博弈模型反映了自私的个体之间的合作竞争关系，能够很好地刻画生物系统中生物体之间的相互作用关系及演化动力学。不论在自然或是社会系统中，经典博弈论告诉我们自私个体博弈的结果必然是背叛。显然是一个和实际情况不完全吻合结论。社会经济活动中的绝大多数任务不可能由单人完成，需要群体的分工和合作。问题:

为什么自私的个体组成的群体会产生合作行为，存在什么样的机制，以及什么样的条件才会有合作行为涌现？通常博弈由以下4个部分所组成:(l)博弈个体：在一个博弈中至少有两位决策者(agent)参与博弈.(2)策略集：个体的博弈策略可以是纯策略，也可以是混合策略博弈的策略集由参与博弈的个体所有可能采用的策略所组成.(3)收益矩阵：当博弈个体选定好自己的策略后，其所获取的收益由收益矩阵中的相应元素来确定.(4)策略演化:在多轮博弈过程中，博弈个体遵循自身收益最大化的最终目标，即以此目标为指导原则来进行策略调整。纳什均衡真实生活中的博弈问题是很复杂的，可能会有很多的参与者，每个参与者都有不同的策略。当参与者们在进行一项博弈的时候，他们应该选择什么样的策略?是否有办法预言出他们的策略组合(s1，s2，…，sN)?纳什(Nash)均衡：其核心思想是对于两人或多人博弈，个体的策略演化会趋向于一个均衡态，在此均衡态下所有的个体会同时采取“纳什均衡策略”。Nash认为，博弈问题的解应该是这样的一组策略，在这组策略中，每一个参与者都无法通过单独改变自己的策略而获得更多的收益。这样的状态就被称作纳什均衡态.实际上纳什均衡态对所有的参与者来说，不一定是最好的结局。不论对手采取哪种策略，选择背叛策略都是最佳的，即理性的个体最终会处于相互背叛的状态(注意到此时的集体收益低于两人同时选择合作时的情况).这种相互背叛的状态(D，D)就是系统的纳什均衡态。对于两人博弈，收益矩阵元通常用(R、S、T、P)来表示相互合作则二人同获得较大收益R，相互背叛则同获较小收益P，一方合作一方背叛，则背叛者获得最高收益T，而合作者获得最低收益S，即参数满足关系:T>R>P

>S，此外2R>T+S，即相互合作能获得集体最高收益.在一个风雪交加的夜晚，两人开车相向而行，被一个雪堆所阻，如图所示.白色和灰色分别表示合作策略与背叛策略.与囚徒困境博弈不同，对于雪堆博弈，收益矩阵元满足关系:

T>R>S>P

雪堆博弈:假设铲除这个雪堆使道路通畅需要付出的劳动量为c，道路通畅则带给每个人的好处量化为b(>c)。如果两人一齐动手铲雪，则他们的收益为R=b一c/2(分别承担劳动量c/2);如果只有一人下车铲雪，虽然两人都能及时回家，但是背叛者逃避了劳动，它的收益为T=b，而合作者的收益为S=b一c;如果两人都选择不合作，则两人都无法及时回家，其收益量化为P=0.雪堆模型的收益矩阵可表示为那么，理性个体的最优选择是什么呢?演化博弈论传统博弈论中，常常假定参与人是完全理性的，且参与人在完全信息条件下进行。而演化博弈理论并不要求参与人是完全理性的，也不要求完全信息的条件。演化博弈论是把博弈理论分析和动态演化过程分析结合起来的一种理论。根据演化博弈理论，博弈双方的策略最终收敛到演化稳定策略上。演化稳定策略必须满足的条件：如果几乎所有的个体都采取该策略，那么该策略的个体适应度要比任何可能的变异策略要大。演化稳定策略的提出最初是为了精炼纳什均衡,通过借助生物界进化论中优胜劣汰的思想,丢弃参与者完全理性的假设,认为均衡是有限理性的个体随时间的推移寻求优化这一目标的长期结果。因此,演化稳定策略具有鲁棒性,可以抑制噪声,它是纳什均衡的精炼。演化博弈论着重研究是在一个动态过程中有限理性的个体如何在重复博弈过程中，通过自适应学习来实现自身收益最大化的问题。它把均衡看作是过程调整的结果。

经典博弈论到演化博弈论的3个关键概念的内涵式改变：（1）策略：不同行为到生物系统中的不同类型物种本身（2）均衡：纳什均衡到演化稳定策略(ESS)；（3）个体相互作用（博弈个体与博弈次数）二、复杂网络上的演化博弈复杂网络理论为描述博弈个体之间的博弈关系提供了方便的系统框架.网络上的节点表示博弈个体,边代表与其邻居的博弈关系.在每一时间步长,节点与其所有邻居进行博弈,累积博弈获得的收益,然后根据更新规则进行策略更新,如此这样重复迭代下去.在传统的演化博弈理论中通常假设个体间以均匀混合的方式交互，即所有个全部相互接触，然而，现实情况中个体间的接触总是有限的，个体仅与周围的少数其他个体接触.这样我们就可以在博弈理论中引入网络拓扑的概念。网络上的演化博弈研究主要集中于3个基本的方向:(l)研究网络拓扑结构对博弈动力学演化结果的影响;(2)一定的网络结构下，探讨各种演化规则对演化结果的影响;2.1网络演化博弈的策略更新规则：(l)模仿最优者：即在每轮博弈过后，个体采取其邻居中获得最高收益的个体的策略进行下一轮博弈。

(2)模仿优胜者：即个体在策略更新时，同时参考那些收益比自身高的邻居的策略，以正比于他们所得收益的概率进行策略转变。以上两种规则可以统称为模仿策略.模仿策略基本思想是个体的更新策略，根据邻居中收益最高的个体策略进行模仿，以期获得更高的收益。每个节点(对应博弈者假设为P1)随机的选取他的一个邻居节点(对应博弈者假设为P2)，P1以一定概率W模仿P2的策略，常用的演化规则如下其中，Ui表示Pi的累积收益，参数κ>0为噪音，代表了一种非理性行为的可能，一般是一个很小的值，常取0.1。当κ→∞时，表示所有的信息都被噪音淹没，策略进行完全随机的更新；当κ→0时，表示确定的模仿规则，即当P2的累积收益高于P1时，P1则采取P2的策略。(3)配对比较：即个体随机选择某一邻居进行收益的比较，以某个概率(为此两个体收益差的函数)转变为对方的策略!其中，kmax为P1与P2中较大度节点的度，P,T,S,R为2×2收益矩阵元素。另一类演化规则(4)随机过程方法：通常考虑Moran过程(birth一death)

(或者death一birth过程)，即在策略更新时，以正比于个体适应度(由收益来衡量)的概率产生一个新的个体，然后随机取代此个体的某个邻居。死生过程是Moran过程的一个自然推广，原始网络中存在合作“C”、背叛“D”两种策略，按照连边关系个体之间进行博弈，获得一个累计收益，其中b表示合作收益，即遇到对手采取合作时获得收益；c表示合作代价，即个体采取合作获得负收益。随机选择选择一个个体死亡(假设为位于中间位置的“D”节点)，则其所有的邻居按照正比于个体适应度的概率产生一个后代，填补个体死亡后留下的空位。重复这一过程，种群中的策略将达到动态平衡。探索由自私个体组成的群体中合作行为产生的机理是演化博弈研究关注的核心问题之一。2.2网络拓扑对合作的影响当个体均匀混合，即个体间的接触网络为全连通图时，相互背叛是唯一的稳定态，合作无法出现，那么改变网络结构能否导致合作行为的出现呢?一个影响深远的工作是Nowak和May在1992年所做的“空间博弈”研究。（1）规则网络上的博弈Nowak和May扩展了囚徒困境博弈模型，将参与博弈的个体置于二维格子上，每个个体与直接相邻的4个邻居进行博弈，并累计收益，然后在更新策略时，一个个体与它的邻居比较本轮的收益，取收益最高者得策略作为下一轮博弈的策略，直到网络进入稳定状态为止。规则网络—囚徒困境模型：为了便于理论分析,Nowak采用了弱囚徒困境博弈，即令T=b>1,R=1,P=S=0。Nowak指出这种弱化囚徒困境所得的演化结果与-1«S<0时的结果相同。Nowak发现引入空间结构后,通过演化,当b在一定范围之内(1≤b«2)，合作者可以通过结成紧密的簇来抵御背叛策略的入侵，如图：虽然这种合作簇并不固定,其形状也会随时间的改变而改变,但它并不会消亡,并且最终系统中合作者的比例(被称为合作频率,是衡量系统合作涌现程度的重要指标)会趋于稳定。规则格子上雪堆博弈的合作频率低于模仿者动态下的演化稳定策略——说明空间结构抑制了合作的产生。这是因为与囚徒困境的斑图不同,在雪堆博弈中合作者更容易聚成丝状簇（如图）这就导致了当损益比r较高时，背叛者容易入侵，使系统合作频率下降，这是雪堆博弈与囚徒困境在合作演化上的本质区别。Hauert的工作揭示了空间结构辩证的作用——一种博弈中促进合作的因素可能在另一种博弈中扮演了相反的角色。这促使人们重新发掘隐藏在空间结构背后的真正推动合作涌现的决定性因素。（2）小世界网络上的博弈小世界网络—囚徒困境Hauert和Szabo基于规则方格，在保持度分布的前提下，对生成的均匀小世界网络和随机均匀网络作了研究。他们应用一种被广泛采用的随机演化策略：一个节点x更新策略的时候，随机地在它的k个邻居中选择一个y，在下一轮中，x以概率选择y本轮的策略作为自己下一轮的策略。上述

公式来源于统计力学中的费米函数，ĸ为环境中的噪音等不确定因素，设为0.1；Px

为x本轮的累积收益。尚丽辉等针对现实生活中朋友关系网络的距离相关特性，研究了基于距离的空间小世界网络上的雪堆博弈，发现与规则网络相比，距离无关的小世界网络促进了合作的涌现；而距离相关的小世界网络中，幂指数增加导致了长程连接的减少和短程连接的增加，这使网络在损益比较大时抑制合作的产生。不同幂律指数下距离相关的小世界网络上的雪堆博弈合作曲线（3）无标度网络上的博弈无标度网络——囚徒困境实际生活中很多网络诸如因特网、航空网等都具有无标度的特性，其节点的度分布满足某种幂律的特性。Santos对比了规则格子、随机图、随机无标度网络和BA无标度网络对合作涌现的作用（下图），认为由于无标度网络中节点之间的度存在极大地差异，合作行为容易在大度节点之间的传播，进而带动了大量小度节点在无标度网络中传播，也就是说，无标度网络是目前最有利于合作涌现的网络结构。Gomez-Gardenes根据个体的稳定时的状态，将其划分为3类：纯策略者、纯背叛者和策略摇摆者。无标度网络——雪堆博弈Santos将研究无标度网络上囚徒困境的方法移植到雪堆博弈上，观察到类似于上图的现象，这说明无标度特性同样有利于雪堆博弈中合作的涌现。通过对小规模网络（128个节点）进行仿真，弱化了影响合作涌现的无标度网络其他统计学特性，着重突出了节点度的异质性的因素。再次验证了关于异质因素促进合作涌现的一般性结论。,指出无标度网络为研究演化博弈理论提供了统一的理论框架。荣智海等研究了无标度网络上的扩展雪堆博弈(即一种可从雪堆博弈连续变化到囚徒困境的博弈),发现无标度网络异质性的增加使得合作的稳定性增强。而且对于相同的纯合作比例,纯背叛者比例增加,策略摇摆者比例减少。这说明越异质的网络,个体越倾向于选择稳定策略.度相关性对两类博弈的影响Rong等首先研究了无标度网络的度一度相关性对合作行为的影响.研究表明:在囚徒困境中,中性网络(即呈现度不相关特性的网络,例如BA网络)的中心节点对于大度邻居与小度邻居的选择是最合理的,既与少量中心节点相连,又与他们共享很少量的邻居。所以其较之同配或异配网络的合作频率更高,最利于合作的涌现。当无标度的网络结构呈现同配性质，即连接度大的节点倾向于和连接度大的节点建立连接时，由于中心节点和边远节点(连接度一般较小)的“通讯渠道”的减少，使得中心节点的合作策略难以传播出去,网络总体的合作频率呈现下降的趋势。反之,如果无标度网络呈现度异配性时,中心节点之间的联系被切断,一方面不利于合作策略在中心节点之间扩散,抑制合作频率的上升;另一方面被孤立的中心节点可以和周围小度节点凝结成坚固的簇,即使背叛的诱惑非常大时也能有效抵御背叛策略的入侵。对于雪堆博弈,越同配的网络其背叛者拥有越小的平均度,这说明与囚徒困境博弈类似,由于网络变得同配后中心节点对于小度节点的控制能力减弱,进行雪堆博弈的背叛者也主要集中在小度节点。异配网络当r较小时,雪堆博弈的合作频率会低于均匀混合状态的均衡频率。可见,度相关性对于囚徒困境博弈的结论完全适用于雪堆博弈.两图的横坐标为背叛相对于合作的收益b,纵坐标为合作频率,rk

为度相关性系数。2.3、记忆对网络博弈中的影响在复杂网络博弈演化模型中，参与者在模仿周围邻居收益的时候，一般都假设参与者，也就是说在模型中并不考虑记忆效应.而在现实生活中，人们的收益并不对时间进行累加是不可能不参考以往的经验的，关于这些经验的记忆也不会迅速遗忘.尤其是在人们选择改变的时候，往往会更加谨慎的考虑这些经验，历史记忆的效应经常会扮演一种重要的角色。考虑到了人的有限记忆的特性，也就是人不可能记录以前发生的所有事情的信息，那么就需要记录最有用的信息。另一方面，人只能记录有限的时间段内所发生的事情，所以我们假设每个个体的记忆长度有限，长度为M，即为从上一时刻到M时刻以前的历史最佳策略.然后每个个体根据自身的历史记忆进行决策.为了简单起见，我们采用多数者规则，即采用C或D策略的概率正比于C和D在记忆中的数量:其中Nc和ND分别是C和D的数量.然后所有个体更新记忆。重复以上步骤，系统就会演化下去.WangWenxu等人考虑了一种基于记忆机制的空间雪堆博弈，并考察了记忆效应对有四个或者八个邻居的二维周期性格子网络和无标度网络中的雪堆模型的作用.考虑个体根据过去的博弈结果的记忆，选择最佳策略，记录当前博弈结果并更新记忆库。模拟的结果表明在不同的收益函数参数r下，记忆能力对网络中合作态密度的影响是不同的.(i)合作频率fc具有分段结构，分段个数对应节点的配位数;(ii)图像对于坐标点(0.5，0.5)呈180度旋转对称;(iii)记忆长度M并不影响分段点τc的值，但是对不同段fc有很大影响;(iv)对于很大的收益参数r，系统仍然表现出较高的合作水平，这与Hauert等人得到的结果有很大不同.这表明即使自私的个体为了使自身利益最大化而做出决策，合作在欺骗者受益很高的情况下仍然能够产生和持久。二维网格上的博弈行为在M=1的时候，系统中的合作行为表现出了大的震荡，如左图的插图所示4邻居和8邻居二维网格上合作水平与博弈模型参数的函数关系.插图中为合作水平与历史记忆长度的相关性以及在历史长度为1时的演化行为无标度网络上的博弈行为(i)与规则格子非常不同的是，fc是r的非单调函数，并存在一个最优值.这个有趣的现象说明适当鼓励自私的行为反而能够更好地促进合作;(ii)与规则格子上的情况相同，fc曲线的连续性被一些突然的增加打断。连续段的数目对应于平均度;(iii)两幅图都以坐标点(0.5，0.5)为180度旋转对称;(iv)记忆长度M不影响不连续点r的值，而只影响介的值。我们进一步细致研究了M如何影响fc。我们发现存在一段特殊的区域，在这段区域M对fc起不同的作用.当M=1时，系统同样存在大震荡无标度网络上的合作行为与博弈参数的函数关系，在交叉点处合作水平与记忆长度的关系以及不同策略个体所占据的节点平均度和博弈参数的关系模拟表明

，基于记忆的空间雪堆博弈中随着损益比的增加，合作频率呈现阶梯状下降，并给出了突变点处的损益比与规则网格中节点邻居数量的关系；而合作频率与记忆长度之间则存在比较复杂的关系，通常来说，记忆长度的增加有利于合作频率的提高，而尝过一定长度后，记忆对合作的影响逐渐减弱，甚至不利于提高合作频率.2.4、博弈动力学与网络拓扑共演化

大多数复杂网络上的演化博弈研究都是基于静态网络的，即网络拓扑从博弈一开始就固定不变了.而实际上真实网络是动态演化的，因此所考虑的静态网络只相当于真实网络的一张快照。复杂系统最本质的特点就是反馈，并利用反馈信息实现自适应和自组织.真实社会中的博弈不但会受到社会人际关系结构的影响，而且反过来也可以影响社会关系结构。换句话说，一方面网络的拓扑结构对其上的动力学过程会产生影响，另一方面这种影响又会反过来“塑造”网络结构本身,调整网络拓扑（或社会关系）。zimmermann等研究了动态网络上演化博弈:从一个随机网络开始，个体与邻居进行囚徒困境博弈，个体按照模仿最优者进行策略更新.在动力学的演化过程中，如果一个背叛者发现它模仿的背叛邻居的收益比自己高，则这个不满意的个体以概率p移走与被模仿的背叛者之间的作用边，重新在网络中随机选择一个节点连接，这样网络中的边数保持不变.研究表明只需要一个小概率p(≥0.01)就可以使动态网络中合作频率达到一个高值，此时网络呈现等级结构，而且随着移边概率p的增加，网络的聚类系数增加，网络异质性增强—这是由于越来越多的背叛者因“失道”而寡助，合作者因“得道”可以成为中心节点.作者指出合作者占据中心节点具有很强的鲁棒性:当网络演化到稳定状态时强行把网络中收益最高的合作者变为背叛者，会使网络合作频率出现短暂震荡，然而经过一段暂态过程后，网络演化为一个新的等级网络，合作者重新占据中心节点，动态网络的合作水平与震荡前相比没有明显变化.Pacheco等同样研究了个体策略与网络结构协同演化的网络博弈模型.在他们的模型中，结构演化和策略演化具有不同的时间尺度，分别记为Ta和Ts.当网络结构演化时，采取不同策略的个体以相应的概率建立连接，通过这些连接进行博弈并获取收益，策略演化则采取配对比较规则.当网络结构的演化速度远远慢于个体进行策略更新的速度时，此博弈模型等价于在静态网络结构上的博弈演化;而当网络结构演化速度远远快于个体策略更新速度时，上面的协同演化机制则导致博弈矩阵元的数值进行了不同标度的重整化.其直接的结果是矩阵元数值大小的排序关系发生改变，从而使得原先的博弈类型发生了本质性的转变，所产生的博弈动力学相当于博弈个体在一个全连接图上进行着另一种类型的博弈.博弈类型转变的直接结果是使得原先处于弱势的策略，例如囚徒困境博弈中的合作策略，有可能变成处于强势的策略，从而有利于合作策略的涌现与维持.考虑个体带简单记忆的网络拓扑与博弈共同演化的简单模型.初始网络从规则随机图开始，每个节点与其所有邻居连续进行囚徒困境博弈n轮，在每一轮，节点依据配对比较更新规则进行策略调整，同时记下邻居作弊次数.博弈完n轮后，随机选择m个个体进行邻居关系调整.被选中的个体将把连到作弊次数最多的邻居的边断开，然后随机重连到该邻居的一个邻居.参数n,m可以看成是博弈动力学和拓扑调整的时间尺度.在我们的模型中，策略更新采用同步方式，拓扑调整是异步的，因此，拓扑调整要比博弈动力学缓慢很多，这与现实是符合的.囚徒困境模型图中给出了网络拓扑随着个体调整邻居关系而变化的过程.从图(a)可以看出，演化的网络是异配的，即度大的节点倾向于与度小的节点相连.由于我们的拓扑调整规则是断开重连到邻居的邻居，在拓扑调整中度大的节点易于一般的节点被其它节点搜索连接上，因此网络呈现出异配性.同时，拓扑调整也造成了网络的异质性，图(b)显示了网络度的方差变化情况.可以看出，随着网络的演化，网络变得越来越异质，而异质性是利于合作产生的.因此在拓扑和博弈共同作用下，合作水平会慢慢增强，如图(c)所示.

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

结果表明了拓扑和博弈动力学共同演化是促进合作水平提高的一个重要机理.上面模型中假设个体断开与作弊次数最多的邻居相连的边，再重连到此邻居的邻居.事实上，更为合理的情形是，个体断边重连时，既可以与邻居的邻居形成新边，也可以与除邻居之外的节点相连.因此基于以上模型，我们假设个体断边重连时，以概率p连到邻居的邻居，反之，以l一p的概率随机选择除邻居之外的节点相连.这里参数p的大小表明个体与个体之间产生新边时的“有序性”与“随机性”的对比.当p→0时，个体随机选择除邻居之外的节点产生新边(完全随机性);当p→1时，个体选择邻居的邻居产生新边(有序性);当0<p<1时，个体重连的新边介于完全随机性与有序性之间.因此这个假侧良好地反映了现实情形中社会网络的演化特点:通常人们可以通过朋友介绍，认识朋友的朋友;也可以偶然地不通过朋友介绍结交一个新朋友。上图给出了合作水平随着参数p的变化情形.可以发现，在博弈关系和策略更新共同演化的情形下，断开旧边产生新边中的“有序性”的倾向越大，越不利于合作的产生.换言之，在共同演化情形下，断边重连到邻居的邻居并不利于合作.相反地，如果随机地选择除邻居之外的节点作为新的博弈对象，将会有助于合作现象的涌现.Santos等人考虑了网络拓扑调整与博弈演化之间的时间尺度的关系，并假设不满意博弈结果的节点以一定概率断开与邻居中背叛者的边，并随机重连到背叛者的邻居，发现存在时间尺度之比的临界值，一旦超过这个临界值，合作将会占上风。采用雪堆博弈模型，网络模型初始有m0=10个随机连接的节点，每个节点的初始状态随机赋予C或D。所有个体同时博弈并根据收益矩阵计算所得到得收益，然后任意一个节点i随机选择一个邻居j来更新自己的策略，i学习j

策略的概率由它们之间收益的差别决定，即雪堆博弈模型其中Mi和Mj是i和j的在上一轮博弈中的总收益。这里T刻画决策中的噪声，也即随机因素。注意：对于不同的网络结构噪声起不同的作用。因为网络规模是不断增加的，所以很难保证噪声起相同的作用，因此在模型的演化过程中将T固定为0.1.当个体策略更新结束后，一个新的个体加入到已有网络中，并且连接m个已有的老的个体，偏好连接的概率正比于已存在节点上个体的收益其中Mi和Mj是i和j在博弈过程中的总收益，W是一个可调参数，反映个体加入系统之初的原始资本，为简单起见，设W为常数。这种基于收益的偏好选择规则反映了社会系统中的富者越富的马太效应，同时也将博弈的演化动力学与网络结构的演化耦合在一起，这个新加入的个体随机选择策略，并且老的个体在下一轮博弈开始时保持原来的策略，重复以上步骤，网络规模就会增加。结果表明无