第12讲复杂网络上的博弈演化

《第12讲复杂网络上的博弈演化》由会员分享，可在线阅读，更多相关《第12讲复杂网络上的博弈演化（73页珍藏版）》请在金锄头文库上搜索。

1、 1、博弈2、复杂网络上的演化博弈 2.1、网络演化博弈的策略更新规则 2.2、网络拓扑对合作的影响 2.3、记忆对网络博弈中的影响 2.4、博弈动力学与网络拓扑共演化 2.5、学习机制导致合作的涌现3、展望博弈研究的对象是游戏(Game)，更确切的说，是指在具有双方相互竞争对立的环境条件下，参与者依靠所掌握的信息，在一定的规则约束下， 各自选择策略并取得相应结果(或收益)的过程。博弈论就是使用数学模型研究冲突对抗条件下最优决策问题的理论。博弈论被认为是研究自然和人类社会中普遍存在的合作行为 最为有力的手段。一、博弈论博弈模型反映了自私的个体之间的合作竞争关系，能够 很好地刻画生物系统中生物体

2、之间的相互作用关系及演 化动力学。不论在自然或是社会系统中，经典博弈论告诉我们自私个 体博弈的结果必然是背叛。显然是一个和实际情况不完全吻合 结论。社会经济活动中的绝大多数任务不可能由单人完成， 需要群体的分工和合作。问题: 为什么自私的个体组成的群体会产生合作行为， 存在什么样的机制，以及什么样的条件才会有合作行为涌现？通常博弈由以下4个部分所组成:(l)博弈个体：在一个博弈中至少有两位决策者(agent)参与博弈.(2)策略集：个体的博弈策略可以是纯策略，也可以是混合策略博弈的策略集由参与博弈的个体所有可能采用的策略所组成.(3)收益矩阵：当博弈个体选定好自己的策略后，其所获取的收益由收益

3、矩阵中的相应元素来确定.(4)策略演化: 在多轮博弈过程中，博弈个体遵循自身收益最大化的最终目标，即以此目标为指导原则来进行策略调整。纳什均衡 真实生活中的博弈问题是很复杂的，可能会有很多的参与者，每个参与者都有不同的策略。当参与者们在 进行一项博弈的时候，他们应该选择什么样的策略?是否有办法预言出他们的策略组合(s1，s2，sN)?纳什(Nash)均衡：其核心思想是对于两人或多人博弈，个体的策略演化会趋向于一个均衡态，在此均衡态下所 有的个体会同时采取“纳什均衡策略”。Nash认为，博弈问题的解应该是这样的一组策略，在这组策略中，每一个参与者都无法通过单独改变自己的策略而 获得更多的收益。这

4、样的状态就被称作纳什均衡态.实际上纳什均衡态对所有的参与者来说，不一定是最好的结局。下面以囚徒困境博弈和雪堆博弈为例来阐述纳什均衡经典博弈模型囚徒困境博弈: 两个小偷A和B合伙作案，被捕后被隔离审讯.如果双方都拒绝坦白同伴的罪行，两人将会被轻判1年徒刑;为此，警方设计了一个机制:如果A揭发B的罪行，B拒不供认A的罪行，则A将无罪释放，而B将被重判5年徒刑;如果A、B都揭发对方罪行，则双方均被判刑3年.在此情况下，自私的个体应如何做出抉择?合作(Cooperate-C) or 背叛(defect一D)不论对手采取哪种策略，选择背叛策略都是最佳的，即理 性的个体最终会处于相互背叛的状态(注意到此时

5、的集体收益低于两人同时选择合作时的情况). 这种相互背叛的状态(D，D)就是系统的纳什均衡态。对于两人博弈，收益矩阵元通常用(R、S、T、P)来表示相互合作则二人同获得较大收益R，相互背叛则同获较小收益P，一方合作一方背叛，则背叛者获得最高收益T，而合作者获得最低收益S，即参数满足关系:TR P S，此外2RT+S，即相互合作能获得集体最高收益.在一个风雪交加的夜晚，两人开车相向而行，被一个雪堆所阻，如图所示.白色和灰色分别表示合作策略与背叛策略.与囚徒困境博弈不同，对于雪堆博弈，收益矩阵元满足关系: TR S P 雪堆博弈假设铲除这个雪堆使道路通畅需要付出的劳动量为c， 道路通畅则带给每个人

6、的好处量化为b(c)。如果两人一齐动手铲雪，则他们的收益为R=b一c/2(分别承担劳动量c/2);如果只有一人下车铲雪，虽然两人都能及时回家，但是背叛者逃避了劳动，它的收益为T=b，而合作者的收益为S=b一c;如果两人都选择不合作，则两人都无法及时回家，其收益量化为P=0.雪堆模型的收益矩阵可表示为:那么，理性个体的最优选择是什么呢?如果对方选择背叛策略(呆在车中)，那么另一方的最佳 策略是下车铲雪(因为按时回家的利益b一c好于呆在车中的 背叛收益0);反之，如果对方下车铲雪，则自己的最佳策略是呆在 舒服的车中.所以，不同于囚徒困境博弈，在雪堆博弈中存 在两个纳什均衡态：(C，D)和(D，C)

7、.即雪堆博弈中的NE为 两人均以概率r选择背叛，概率1-r选择合作，其r=c/(2b-c)称 为损益比。雪堆模型与囚徒困境不同：遇到背叛者时合作者的收益高于双方相互背叛的收益.因此,一个人的最佳策略取决于对手的策略： 如果对手选择合作， 他的最佳策略是背叛； 反过来， 如果对手选背叛， 那么他的最佳策略是合作。 这样合作在系统中不会消亡， 而与囚徒困境相比， 合作更容易在雪堆博弈中涌现。 演化博弈论传统博弈论中，常常假定参与人是完全理性的，且参与人在完全信息条件下进行。而演化博弈理论并不要求参与人是完全理性的，也不要求完全信息的条件。演化博弈论是把博弈理论分析和动态演化过程分析结合起来的一种理

8、论。根据演化博弈理论，博弈双方的 策略最终收敛到演化稳定策略（evolutionarily stablestragegy，ESS）上。1. 演化网络博弈基本定义要讨论合作的涌现，必须涉及相当数量的个体（局 中人），而且合理地认为这些局中人以及他们之间的关系 构成一个复杂网络，随着时间的演化，每个局中人都在和 他的邻居进行博弈，这就称为演化网络博弈，它的定义可 以表述为：（1）数量N的局中人位于一个复杂网络上。（2）每个时间演化步，按一定法则选取的一部分局中人 以一定频率匹配进行博弈。 （3）局中人采取的对策可以按一定法则更新，所有 局中人的策略更新法则相同。这种法则称为“策略的策 略”。然而，

9、法则更新比博弈频率慢得多，使得局中人 可以根据上一次更新对策成功与否选择、调整下一次的 更新。 （4）局中人可以感知环境、吸取信息，然后根据自 己的经验和信念，在策略更新法则下更新策略。 （5）策略更新法则可能受到局中人所在网络拓扑结构 的影响。2 演化网络博弈研究内容第一，研究网络拓扑结构对博弈演化动力学的影响。第二，探索一些可能的支持合作行为涌现的动力学机制 。第三，研究博弈动力学和网络拓扑结构的共演化，即个 体策略和网络拓扑结构协同演化的情形。3. 促进合作行为涌现的机制重复博弈（争锋相对、冷酷策略）、巴普洛夫策略、 亲缘选择、直接互惠、间接互惠（声誉）、网络互惠以 及群选择。公共利益博

10、弈（复杂网络基础 P306）演化稳定策略的提出最初是为了精炼纳什均衡 ,通过借助生物界进化论中优胜劣汰的思想 ,丢弃参与者完全理性的假设 ,认为均衡是有限理性的个体随时间的推移寻求优化这一目标的长期结果。 因此 ,演化稳定策略具有鲁棒性 ,可以抑制噪声 ,它是纳什均衡的精炼。演化博弈论着重研究是在一个动态过程中有限理性的个体如何在重复博弈过程中，通过自适应学习来实现自身收益最大化的问题。它把均衡看作是过程调整的结果。 演化稳定策略必须满足的条件：如果几乎所有的个体都采取该策略，那么该策略的个体适应度要比任何可能的变异策略要大。 经典博弈论到演化博弈论的3个关键概念的内涵式改变（演化博弈论与经典

11、博弈论的区别）： （1）策略内涵的不同：不同行为 到生物系统中的不同类型物种本身，策略由物种的不同表现型来体现；（2）均衡意义的不同：纳什均衡到演化稳定策略(ESS)；（3）个体互相作用方式的不同（博弈个体与博弈次数）二、复杂网络上的演化博弈复杂网络理论为描述博弈个体之间的博弈关系提供了方便的系统框架. 网络上的节点表示博弈个体 ,边代表与其邻居的博弈关系.在每一时间步长 ,节点与其所有邻居进行博弈 ,累积博弈获得的收益 ,然后根据更新规则进行策略更新 ,如此这样重复迭代下去.在传统的演化博弈理论中通常假设个体间以均匀混合的 方式交互，即所有个体全部相互接触，然而，现实情况中个 体间的接触总是

12、有限的，个体仅与周围的少数其他个体接触 .这样我们就可以在博弈理论中引入网络拓扑的概念。网络上的演化博弈研究主要集中于3个基本的方向:(l)研究网络拓扑结构对博弈动力学演化结果的影响;(2) 一定的网络结构下，探讨各种演化规则对演化结果的影响;(3)网络拓扑和博弈动力学的共演化，主要是自 适应网络上博弈动力学 ,即网络拓扑调整受博弈动力学影响.每一个模型都可以分成几个模块，如使用的博弈模型、更新规则、网络结构等。(l)网络中所有的参与者与其网络上的邻居进行博弈，并 获得收益。每个参与者的收益为与其所有邻居发生博弈得到 收益的总和。(2)然后参与者将他的收益与他在网络上邻居的收益进 行比较，按照

13、一定规则改变自己的策略。虽然使用的博弈模型和具体的模拟细节各不相同，但基本的模拟过程是类似的，这个模拟过程是分回合进行的，每 个回合包含两步:2.1网络演化博弈的策略更新规则：(l)模仿最优者：即在每轮博弈过后，个体采取其邻居中获得最高收益的个体的策略进行下一轮博弈。(2)模仿优胜者：即个体在策略更新时，同时参考那些收益比自身高的邻居的策略，以正比于他们所得收益的概率进行策略转变。以上两种规则可以统称为模仿策略. 模仿策略的基本思想是个体的更新策略，根据邻居中收益最高的个体策略进行模仿，以期获得更高的收益。每个节点(对应博弈者假设为P1)随机的选取他的一个邻居节点(对应博弈者假设为P2)，P1

14、以一定概率W模仿P2的策略，常用的演化规则（统计力学的费米函数）如下：其中，Ui表示Pi的累积收益，参数0为噪音，代表了一种非理性行为的可能，一般是一个很小的值，常取0.1。当时，表示所有的信息都被噪音淹没，策略进行完全随机的更新 ；当0时，表示确定的模仿规则，即当P2的累积收益高于P1时，P1则采取P2的策略。(3)配对比较：即个体随机选择某一邻居进行收益的比较，以某个概率(为此两个体收益差的函数)转变为对方的策略!其中，kmax为P1与P2中较大度节点的度，P,T,S,R为22收益矩阵元素。另一类演化规则(4)随机过程方法：通常考虑Moran过程(birth一death) (或者death

15、一birth过程) ， 即在策略更新时，以正比于个体适应度(由收益来衡量)的概率产生一个新的个体，然后随机取代此个体的某个邻居。Moran过程是将Darwin的进化思想直接引入到演化博弈中。一个实际背景是种群中的变异入侵，以下图为例，种群中 所有个体“C”，当某个个体发生变异后，变为”D”，以后每一步考虑随机移去一个个体，并以正比于原种群中“C”个体适应度的概率生成一个新的“C”个体，否则生成一个新的“D”个体。在适应度函数满足一定条件时，“D”个体可能完全侵占整个种群(Invade)，Martin A.Nowak等人研究了这类种群侵占问题，将某种策略从种群中仅存在一个变异个体时，最终能侵占整

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