《网络博弈合作的进化.ppt》由会员分享，可在线阅读，更多相关《网络博弈合作的进化.ppt（18页珍藏版）》请在三一文库上搜索。
1、网络博弈：合作的进化,张博宇 北京师范大学数学科学学院 2014年6月30日,概述,1.社会困局 Social dilemma 2.演化动态 Evolutionary dynamics 3.网络博弈 Network game 4.网络上的合作 Cooperation on network,囚徒困境,囚徒困境博弈(Prisoners Dilemma game)： 合作 C，支付c，对手获得b，其中bc； 背叛 D，不支付。 背叛是唯一的纳什均衡对策，但是合作对于群体更加有利。,公用品博弈,公共品博弈(Public goods game) 每名参与者可贡献他的一些私人资金作为公共经费，这些资金乘以
2、系数r后平均分给所有N名参与者。 如果参与者i贡献ci，他的收益为： 当1rN时，每名参与者的最优对策均为不贡献(D)，尽管贡献全部资金(C)对于整个群体更加有利。 社会困局(Social dilemma) 个体追求利益最大化导致了社会利益最小化。,一些符号 nC, nD, pC, fC, fD, hC, hD, , 其中fX=1- +hX. 基本假设 (1) 种群充分大。 (2) 无性繁殖。 (3) 个体两两随机相遇。 (4) 个体间无差异。 复制方程 (Replicator dynamics) 进化选择了背叛者。,演化动态,演化和学习,个体并非完全理性，模仿其他有更高收益的个体的行为。 成
3、对模仿 (Pairwise comparison) 从种群中随机挑选两个个体i 和j，i为模仿者，j为被模仿者。若i个体观测到j个体有更高的收益，则他会以概率(fj - fi)+模仿j个体的行为。 学习动态（Learning dynamics） 演化动态的性质 (1) 纳什均衡一定是复制方程/学习动态的平衡点。 (2) 复制方程/学习动态的稳定平衡点一定是纳什均衡。,有限种群中的合作,种群大小固定为N。 随机相遇： 在完全随机相遇的固定大小种群中，合作者有更大的概率遇到背叛者。 小种群有利于背叛者的演化。,有限种群的演化动态,一步过程 每个时间步从种群中随机挑选一个个体i作为模仿者，再随机挑选
4、一个个体j作为被模仿者。若i个体观测到j个体有更高的收益，则他会以概率(fj - fi)+模仿j个体的行为。 转移概率 演化动态,合作的进化,Sigmund K,Nowak MA,亲缘选择,群体选择,直接互惠,间接互惠,网络博弈,网络博弈,有限种群 大小为N的种群分布在一张N个节点的网络上。每个节点或者是合作者(C)，或者是背叛者(D)。 网络博弈 每个个体只与他的邻居进行博弈。一个个体的收益是他和所有邻居博弈获得收益的总和。 成对模仿 每个时间步从种群中随机挑选一个 个体i作为模仿者，再从他的邻居中 随机挑选一个个体j作为被模仿者。 i个体模仿j个体的行为的概率为,网络上的合作,为什么网络结
5、构能够促进合作? 合作者聚集可以获得更高的收益，而背叛者聚集会降低收益。,网络博弈,网络特征： 网络节点集合 ：I=1,N. 节点i 的度数 ：ki . 度数为k的节点的比例：p(k). 网络的平均度数： 网络度数分布的方差： 博弈特征： 节点i的行为：si . 节点i的A邻居和B邻居的个数：ki,A , ki,B . A行为个体在网络中所占的权重： AA边的比例：AA. A节点的一个邻居为A和B的概率：qA|A, qA|B.,网络博弈的演化动态,暂态均衡(Temporal equilibrium) 当选择强度较弱时，网络上会形成暂态均衡状态。在此暂态均衡有qA|A-qA|B=1/(z-1)，
6、即度数为k的A个体平均比度数为k的B个体多k/(z-1)个A邻居。 演化动态,网络上的囚徒困境博弈,囚徒困境博弈 演化动态 规则网络(var(k)=0)不能促进合作。 合作(C)成为全局稳定的条件为 网络的方差越大越有利于合作的进化。当方差充分大时，合作产生的条件为b/cz-1.,网络上的合作,var(k)=187, var(k)=275,var(k)=15, var(k)=18,总结,完全随机相遇的种群中合作无法进化。 种群越小越不利于合作。 网络可以促进合作 网络的平均度数越小、方差越大，越有利于合作。 为什么网络可以促进合作？ 由于网络结构的存在，合作者间和背叛者间都更容易聚集，这种聚集会提高合作者的收益，降低背叛者的收益。 人类社会中，网络结构可以促进合作么？,现有的几个网络博弈实验表明，网络结构对人类间的合作没有明显促进作用。 条件合作(Conditional cooperation) 玩家每一轮的选择依赖于上一轮自身的选择和周围邻居的选择。 当更新规则为条件合作时，网络不能促进合作。,实验结果,网络对博弈的影响仍有很多未解决的问题，需要进一步的研究。,谢谢大家！,