第八章复杂网络中的博弈课件.ppt

2． 演化网络博弈研究内容 第一，研究网络拓扑结构对博弈演化动力学的影响。 第二，探索一些可能的支持合作行为涌现的动力学机制。 第三，研究博弈动力学和网络拓扑结构的共演化，即个体策略和网络拓扑结构协同演化的情形。 8.3.3 基于囚徒窘境博弈模型的演化网络博弈 目前，学者们主要针对前面介绍过的囚徒窘境博弈和铲雪博弈来讨论复杂网络上发生的演化博弈行为和特性。主要原因是这两个博弈模型都是二局中人之间的博弈，从而上面介绍的演化博弈描述可以大大简化，而且博弈仅仅发生在节点和它的邻点之间。 1． 规则网络上的囚徒窘境博弈 1992 年Nowak 和May 首先扩展了囚徒窘境博弈模型，将参与博弈的个体置于二维网格上[50]，首先每个个体与直接相邻的4 个邻居进行博弈，并累计收益，然后在更新策略时，一个个体与它邻居比较本轮的收益，取收益最高者的策略作为下一轮博弈的策略，直到网络进入稳定状态为止 1． 规则网络上的囚徒窘境博弈 200×200 二维网格上的演化囚徒窘境博弈形成的斑图 1． 规则网络上的囚徒窘境博弈 99×99 二维网格上的演化囚徒窘境博弈形成的空间混沌 1． 规则网络上的囚徒窘境博弈 例题：对于上面提到的基于囚徒窘境模型的规则网络博弈，基于费米函数的策略更新规则，利用平均场近似理论分析采取合作策略的个体的密度ρ 随时间的演化。 2． 小世界网络上的囚徒窘境博弈 2001 年Abramson 和Kuperman 在期刊Physical Review E 第63 卷首先研究了WS 小世界网络上的囚徒窘境博弈。在他们的模型中，个体采用确定性策略更新规则：每个个体采用邻居中收益最高者的策略。底层的交互网络是一个由一维规则环进行断开重连得到的WS 小世界网络。 3． 无标度网络上的囚徒窘境博弈 2005 年Santos 和Pacheco 研究了BA 无标度网络上的囚徒窘境博弈。 规则网络与BA无标度网络中囚徒窘境博弈的合作演化的对比 8.3.4 基于铲雪博弈模型的演化网络博弈 1． 规则网络上的铲雪博弈 基于囚徒窘境的研究，人们普遍认为空间结构有利于合作的涌现。然而，2004年Hauert和Doebeli研究了二维规则网格中的铲雪博弈并发现二维网格却强烈压抑铲雪博弈中的合作[54]，这显然与Nowak和May的结果完全不同。他们在实验中将博弈个体置于100×100二维规则网格上，针对度为3（三角形）、4（方形）、6（六边形）、8（方形）的4种拓扑结构情况，根据铲雪博弈模型展开演化（初始条件为一半合作一半背叛），分别得到（a）-（d）所示的结果。 1． 规则网络上的铲雪博弈 规则网格上铲雪博弈的合作演化 规则网格上囚徒窘境博弈和铲雪博弈的合作者斑图比较 2． 小世界网络上的铲雪博弈 相对于囚徒窘境博弈，铲雪博弈受小世界网络结构的影响的研究较少。Tomassini等[55]基于雪堆博弈的等价模型变形—鹰鸽博弈（hawk-dove game）， 针对模仿者动态（replicator dynamics）、比例更新（propotional updating）和最优更新（best-takes-over）三种演化规则，研究了二维网格小世界网络上的合作行为。 2． 小世界网络上的铲雪博弈 在模仿者动态演化规则下鹰鸽博弈的合作频率和损益比的关系 3． 无标度网络上的铲雪博弈 除了囚徒窘境博弈，2005 年Santos 和Pacheeo 同时研究了铲雪博弈在无标度网络中的演化行为[53]，观察到图8.11 的现象（图中的斜直线对应全混合种群情形fc＝1－r），与图8.5 非常类似，这说明无标度特性同样有利于雪堆博弈中合作的涌现，从而再次验证了关于异质因素促进合作涌现的一般性结论，指出无标度网络为研究演化博弈理论提供了统一的理论框架。 8.4 复杂网络的攻击策略和抗毁性分析 8.4.1 复杂网络的抗毁性分析背景 8.4.2 复杂网络的抗毁性定义 8.4.3 复杂网络的抗毁性测度 8.4.4 复杂网络的抗毁性分析 8.4.1 复杂网络的攻击策略 通常，复杂网络面临两种攻击：随机性攻击(random attack）和选择性攻击（selectiveattack） 随机性攻击就是网络的节点或者边以一定的概率被随机的破坏或删除。 选择性攻击就是网络的节点或者边按一定的策略被破坏，例如一种可行的策略是按照节点的度大小依次去除节点。 通常来说，网络自身原因引起的故障属于随机性攻击，而蓄意的破坏则属于选择性攻击。 8.4.1 复杂网络的攻击策略 Holme 等针对蓄意攻击策略作了深入全面的仿真研究。他们将攻击策略分为基于节点的攻击与基于边的攻击两种方式。每种攻击又包括四种不同的策略： （1）ID（initial degree）移除策