復杂网络上的博弈演化.pptVIP

刘 伟 2009.11.21 Qingdao;1、博弈 2、复杂网络上的演化博弈 2.1、网络演化博弈的策略更新规则 2.2、网络拓扑对合作的影响 2.3、记忆对网络博弈中的影响 2.4、博弈动力学与网络拓扑共演化 2.5、学习机制导致合作的涌现 3、展望;一个个性和另一个个性的联结 对被联结的个性的命运具有多大的意义？ 你要知道，这是一生的事情， 在我们的背后隐藏着无数的枝节。 ——陀思妥耶夫斯基,《白痴》第501页;一个游戏：两人轮流向圆桌上放一元硬币， 谁无法再在圆桌上放硬币则判负，另一方获胜， 假设所有的硬币不允许重叠。你会先放还是后放， 以何种策略确保自己获胜?;博弈论被认为是研究自然和人类社会中普遍存在的合作行为 最为有力的手段。;通常博弈由以下4个部分所组成: (l)博弈个体：在一个博弈中至少有两位决策者(agent)参与博弈. (2)策略集：个体的博弈策略可以是纯策略，也可以是混合策略博弈的策略集由参与博弈的个体所有可能采用的策略所组成. (3)收益矩阵：当博弈个体选定好自己的策略后，其所获取的收益由收益矩阵中的相应元素来确定. (4)策略演化: 在多轮博弈过程中，博弈个体遵循自身收益最大化的最终目标，即以此目标为指导原则来进行策略调整。;纳什均衡;下面以囚徒困境博弈和雪堆博弈为例来阐述纳什均衡;不论对手采取哪种策略，选择背叛策略都是最佳的，即理性的个体最终会处于相互背叛的状态(注意到此时的集体收益低于两人同时选择合作时的情况). 这种相互背叛的状态(D，D)就是系统的纳什均衡态。;在一个风雪交加的夜晚，两人开车相向而行，被一个雪堆所阻，如图所示.白色和灰色分别表示合作策略与背叛策略.与囚徒困境博弈不同，对于雪堆博弈，收益矩阵元满足关系: TR S P ;如果两人一齐动手铲雪，则他们的收益为R=b一c/2(分别承担劳动量c/2);如果只有一人下车铲雪，虽然两人都能及时回家，但是背叛者逃避了劳动，它的收益为T=b，而合作者的收益为S=b一c;如果两人都选择不合作，则两人都无法及时回家，其收益量化为P=0.雪堆模型的收益矩阵可表示为;如果对方选择背叛策略(呆在车中)，???么另一方的最佳策略是下车铲雪(因为按时回家的利益b一c好于呆在车中的背叛收益0); 反之，如果对方下车铲雪，则自己的最佳策略是呆在舒服的车中.所以，不同于囚徒困境博弈，在雪堆博弈中存在两个纳什均衡态：(C，D)和(D，C).即雪堆博弈中的NE为两人均以概率r选择背叛，概率1-r选择合作，其r=c/(2b-c)称为损益比。;演化博弈论;演化稳定策略的提出最初是为了精炼纳什均衡 ,通过借助生物界进化论中优胜劣汰的思想 ,丢弃参与者完全理性的假设 ,认为均衡是有限理性的个体随时间的推移寻求优化这一目标的长期结果。 因此 ,演化稳定策略具有鲁棒性 ,可以抑制噪声 ,它是纳什均衡的精炼。;二、复杂网络上的演化博弈;每一个模型都可以分成几个模块，如使用的博弈模型、 更新规则、网络结构等。;2.1网络演化博弈的策略更新规则：;每个节点(对应博弈者假设为P1)随机的选取他的一个邻居节点(对应博弈者假设为P2)，P1以一定概率W模仿P2的策略，常用的演化规则如下;其中，kmax为P1与P2中较大度节点的度，P,T,S,R为2×2收益矩阵元素。;Moran过程是将Darwin的进化思想直接引入到演化博弈中。一个实际背景是种群中的变异入侵，以下图为例，种群中所有个体“C”，当某个个体发生变异后，变为”D”，以后每一步考虑随机移去一个个体，并以正比于原种群中“C”个体适应度的概率生成一个新的“C”个体，否则生成一个新的“D”个体。在适应度函数满足一定条件时，“D”个体可能完全侵占整个种群(Invade)，;死生过程是Moran过程的一个自然推广，原始网络中存在合作“C”、背叛“D”两种策略，按照连边关系个体之间进行博弈，获得一个累计收益，其中b表示合作收益，即遇到对手采取合作时获得收益；c表示合作代价，即个体采取合作获得负收益。随机选择选择一个个体死亡(假设为位于中间位置的“D”节点)，则其所有的邻居按照正比于个体适应度的概率产生一个后代，填补个体死亡后留下的空位。重复这一过程，种群中的策略将达到动态平衡。;探索由自私个体组成的群体中合作行为产生的机理是演化博弈研究关注的核心问题之一。;为了便于理论分析, Nowak采用了弱囚徒困境博弈，即令 T = b 1, R = 1, P = S = 0。Nowak指出这种弱化囚徒困境 所得的演化结果与-1?S 0时的结果相同。;他们发现当个体间的接触网络具有空间结构时，如方格网络，在囚徒困境博弈中合作行为能够出现并且稳定