复杂网络基础理论 作者 郭世泽 陆哲明课件第八章

第八章第八章 复杂网络中的博弈复杂网络中的博弈目录8.1 引言8.2 博弈论概述8.3 复杂网络中的演化博弈8.4 复杂网络的抗毁性分析8.5 复杂网络的抗毁性优化和修复策略8.1 引言广义上讲，复杂网络中的博弈问题包括：网络的攻击和安全防护（包括抗毁性分析和优化）、网络中的流行病（病毒、谣言）传播和抑制、网络的同步和牵制控制、网络的拥塞和拥塞控制、网络的级联故障和故障预防控制、网络中个体的合作和竞争本书主要关注狭义上的两方面复杂网络博弈问题：一个是网络中个体之间的合作和竞争问题，另一个是网络的攻击和防护问题。本章首先简要介绍博弈论，接着重点介绍复杂网络的演化博弈理论，然后介绍复杂网络中的攻击策略和抗毁性（鲁棒性）分析，最后简要介绍复杂网络的抗毁性优化和修复策略。8.2 博弈论概述8.2.1 博弈论基本概念以及发展历史8.2.2 博弈的分类8.2.3 完全信息静态博弈和纳什均衡8.2.4 完全信息动态博弈和子博弈精炼纳什均衡8.2.5 不完全信息静态博弈与贝叶斯纳什均衡8.2.6 不完全信息动态博弈与精炼贝叶斯纳什均衡经典博弈论（game theory）是现代数学的一个新分支，也是运筹学的一个重要组成部分。“博”在中国古语中有搏斗、赌博、拼搏、冒险等意思，“弈”就是下棋，因此博弈论就是根据一定规则和对手的情况来决定自己的策略，从而最大可能地获得自己最大利益的科学。简言之，博弈论就是研究互动决策的理论。一个完整的博弈（game）应当包括以下几个方面的内容：第一、参与博弈的个体，即博弈过程中独立决策的个体；第二、博弈个体的策略，每一个博弈个体都有自己的策略；第三、博弈规则和收益函数，博弈个体根据博弈的规则进行博弈并根据收益函数获取一定的收益；第四、在博弈过程中，博弈个体以自身的利益最大化为最高目标，并以此为原则更新自己的策略。8.2.1博弈论基本概念参与博弈的人通常称之为“局中人”，对其的基本假设是：1）完全理性，即具有完全的获取信息和分析推理的能力；2）完全自私，即进行博弈的目的完全在于使自己的利益最大化。在这样简单的假定下，博弈论进行完全逻辑推理性的分析，这一点与传统动力学相似。8.2.1博弈论基本概念局中人的策略可以是纯策略也可以是混合策略。局中人vi 的所有可能的策略组成其博弈策略集Si。在某一轮博弈中，每个局中人vi 都选择一个策略siSi，构成一个向量s（s1，s2，sN）T，称为一个策略组合。所有可能的策略组合可以组成一个集合Ss（s1，s2，sN）TsiSi，称为策略组合集合。每一轮博弈中，根据策略组合s，每个局中人vi 获得一定的收益ui（s）。8.2.1博弈论基本概念对于标准形式的有限次的双人博弈通常可以用收益矩阵U 描述，一个典型的例子如表所示8.2.2 博弈的分类1.合作博弈和非合作博弈如果参加博弈的局中人可以达成有约束力的合作协议，也就是说，在博弈中，局中人可以在相互信任的基础上共同寻求使大家都获利最大、损失最小的策略，且这种互相信任的约定一定会被遵守，则这种博弈叫做合作博弈。如果参与博弈的局中人不能或者不被允许达成有约束力的合作协议，或者虽达成协议但不被遵守，则把这种博弈称为非合作博弈。1.合作博弈与非合作博弈例题：请用囚徒窘境博弈来理解合作博弈和非合作博弈。囚徒窘境博弈的收益矩阵如下：2 完全信息博弈与不完全信息博弈上面的分析都假设两个局中人具有完全信息，即知道关于所有博弈局中人的可能策略、自己的每种策略和对手策略组合分别给各人带来的“收益”以及所有博弈对手的特征等一切有关博弈决策的知识，这就是完全信息博弈。但是，在实际中很少有这种理想情况，局中人通常必须在只有部分信息时就必须决策，这就是不完全信息博弈。3 静态博弈与动态博弈上面囚徒窘境例子中的局中人必须同时决策，或者虽然不同时决策但是不知道对手局中人乙的决策，类似于猜拳或“剪子、石头、布”。每个局中人必须依靠对所有策略组合及其收益的分析推理找出自己的最优策略。实际中也有另一种情况，例如下棋、打扑克、打乒乓球等，博弈是对手之间的一系列行为，每次博弈时，局中人可以而且必须根据对手的上一步策略决定自己的下一步策略，这就是动态博弈。4 四种非合作博弈及其均衡上述的三种分类可以构成四种非合作博弈类型，分别由纳什、塞尔屯和海萨尼提出了它们相应的均衡四种非合作博弈类型8.2.3 完全信息静态博弈与纳什均衡1 非合作博弈条件下具有“背叛”对称纳什均衡解的完全信息静态博弈例题：见义勇为博弈的收益矩阵8.2.3 完全信息静态博弈与纳什均衡2.具有“合作”对称纳什均衡解的完全信息静态博弈例题：铲雪博弈的收益矩阵8.2.3 完全信息静态博弈与纳什均衡3.具有不对称纳什均衡解的完全信息静态博弈例题：智猪博弈的收益矩阵8.2.4 完全信息动态博弈与子博弈精炼纳什均衡1 子博弈精炼纳什均衡动态博弈过程就像两个人下棋，中间要进行许多步。在每一步中，局中人都要根据对手刚刚采取的策略进行决策，称为博弈的“一轮”。一轮博弈就称作一个“子博弈”。只有动态博弈的每个子博弈都达到纳什均衡，整个动态博弈才被称为达到了精炼纳什均衡。只有去除了“不可信威胁”之后达到的子博弈纳什均衡才是精炼的。8.2.4 完全信息动态博弈与子博弈精炼纳什均衡2.博弈树例题：市场进入阻扰博弈树8.2.5 不完全信息静态博弈与贝叶斯纳什均衡贝叶斯纳什均衡就是在已知（包括自己的）全部局中人的类型概率分布情况下，分析得到的各个局中人最优策略组合。类似地，任何一个局中人变化策略都会导致损失，因此贝叶斯纳什均衡同样也会自然达到，也是会被自动遵守的僵局。前面讨论的市场进入阻挠博弈及其对称子博弈精炼纳什均衡仅仅适用于高成本在位者。例题：低成本在位者的市场进入阻扰博弈收益矩阵8.2.5 不完全信息静态博弈与贝叶斯纳什均衡3 不完全信息贝叶斯纳什均衡如果进入市场者不了解在位者的全部信息（经济、管理、技术实力等），只知道它属于高成本类型（选择默许）的概率为p，属于低成本类型（选择斗争）的概率为1p，则它进入市场的“期望利润”为40p10（1p)，不进入市场的“期望利润”为0。容易计算得到：只有当p0.2 时，进入市场的期望利润才大于不进入市场的期望利润，进入才是优策略。这样，最后的对称或不对称不完全信息贝叶斯纳什均衡解取决于p 是否大于这个阈值0.2，而且这个均衡解只能给出一个概率性的决策结果预言。8.2.6 不完全信息动态博弈与精炼贝叶斯纳什均衡不完全信息动态博弈是我们迄今为止讨论的四种非合作博弈中最复杂的一种。这种情况下达到的精炼贝叶斯纳什均衡解及其求解过程一般也比较繁难，因此在此不做过多介绍。8.3 复杂网络的演化博弈8.3.1 演化博弈简介8.3.2 演化网络博弈概述8.3.3 基于囚徒窘境博弈模型的演化网络博弈8.3.4 基于铲雪博弈模型的演化网络博弈8.3.1 演化博弈简介1973 年生态学家Smith 和Price 结合生物进化论与经典博弈论在研究生态演化的基础上提出演化博弈论的基本均衡概念演化稳定策略（evolutionarily stablestragegy，ESS），标志着演化博弈理论的诞生。此后，演化博弈理论逐渐被广泛地用于生态学、社会学和经济学等领域。2.演化博弈论与经典博弈论的区别首先是策略内涵的不同其次是均衡意义的不同第三是互相作用方式的不同3.促进合作行为涌现的机制8.3.2 演化网络博弈概述1.演化网络博弈基本定义既然要讨论合作的涌现，当然必须涉及相当数量的个体（局中人），而且合理地认为这些局中人以及他们之间的关系构成一个复杂网络，随着时间的演化，每个局中人都在和他的邻居进行博弈，这就称为演化网络博弈，它的定义可以表述为：（1）数量N的局中人位于一个复杂网络上。（2）每个时间演化步，按一定法则选取的一部分局中人以一定频率匹配进行博弈。（3）局中人采取的对策可以按一定法则更新，所有局中人的策略更新法则相同。这种法则称为“策略的策略”。然而，法则更新比博弈频率慢得多，使得局中人可以根据上一次更新对策成功与否选择、调整下一次的更新。（4）局中人可以感知环境、吸取信息，然后根据自己的经验和信念，在策略更新法则下更新策略。（5）策略更新法则可能受到局中人所在网络拓扑结构的影响。2 演化网络博弈研究内容第一，研究网络拓扑结构对博弈演化动力学的影响。第二，探索一些可能的支持合作行为涌现的动力学机制。第三，研究博弈动力学和网络拓扑结构的共演化，即个体策略和网络拓扑结构协同演化的情形。8.3.3 基于囚徒窘境博弈模型的演化网络博弈目前，学者们主要针对前面介绍过的囚徒窘境博弈和铲雪博弈来讨论复杂网络上发生的演化博弈行为和特性。主要原因是这两个博弈模型都是二局中人之间的博弈，从而上面介绍的演化博弈描述可以大大简化，而且博弈仅仅发生在节点和它的邻点之间。1 规则网络上的囚徒窘境博弈1992 年Nowak 和May 首先扩展了囚徒窘境博弈模型，将参与博弈的个体置于二维网格上50，首先每个个体与直接相邻的4 个邻居进行博弈，并累计收益，然后在更新策略时，一个个体与它邻居比较本轮的收益，取收益最高者的策略作为下一轮博弈的策略，直到网络进入稳定状态为止1 规则网络上的囚徒窘境博弈200200 二维网格上的演化囚徒窘境博弈形成的斑图1 规则网络上的囚徒窘境博弈9999 二维网格上的演化囚徒窘境博弈形成的空间混沌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的结果完全不同。他们在实验中将博弈个体置于100100二维规则网格上，针对度为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 的现象（图中的斜直线对应全混合种群情形fc1r），与图8.5 非常类似，这说明无标度特性同样有利于雪堆博弈中合作的涌现，从而再次验证了关于异质因素促进合作涌现的一般性结论，指出无标度网络为研究演化博弈理论提供了统一的理论框架。8.4 复杂网络的攻击策略和抗毁性分析8.4.1 复杂网络的抗毁性分析背景8.4.2 复杂网络的抗毁性定义8.4.3 复杂网络的抗毁性测