复杂网络上的博弈演化.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无标度网络对合作涌现的作用(下图),认为由于无标度网络中节点之间的度存在极大地差异,合作行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 复杂 网络 博弈 演化
链接地址:https://www.31doc.com/p-2561235.html