重复囚徒困境博弈对网络拓扑结构影响的研究

《重复囚徒困境博弈对网络拓扑结构影响的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、重复囚徒困境博弈对网络拓扑结构影响的研究鲁东大学学报(自然科学版)LudongUniversityJoumal(NaturalScienceEdition)20日，29(7><1):29><>8-3<1重复囚徒困境博弈对网络拓扑结构影晌的研究王伊蕾(山东大学讨算机科学与技术学院，济南250<10<1)摘要:对Zach町网络采用了重复囚徒困境博弈的方法，提出了两种网络结构的演化算法，即随机算法和伪度优先算法，并对网络的度分布和聚集系数进行了分析，结果表明:经过n轮重复博弈，随机算法对网络拓扑结构的影响不大，伪度优先算法对网络拓扑结构的影响较大;经过演化后，网络的最大度明显增大，聚集系数也高于演

2、化前的网络;随机算法对网络的社团结构影响不明显，而伪度优先算法则对社团结构的影响较大1>.关键词:囚徒困境;纳什均衡;复杂网络;拓扑结构中图分类号:N94;F224文献标志码:A文章编号:<1673-<>8020(20<13)0<1-∞2<>8-04在现实社会中，很多系统都可以用复杂网络D).D策略个体利用C策略个体获得T<1&益，而C来描述，人们利用复杂网络认识了更加复杂的外获得S收益;双方都合作获得R;都背叛获得P，其部世界[<1-3J博弈论是依据其他参与者的效用中T>R>P>S,2R>T+S.在囚徒困境博弈中，两个博弈个体需要同时决定是否要与对于进(ut

3、ility)情况，研究理性参与者策略之间相互作用的一门科学[4<1总体上讲，复杂网络上的演化研行合作或背叛，收益矩阵IRSIb-c-c究有三条主线，其中很重要的一条是研究网络的A=I<1=<1TPIb0I拓扑结构对博弈演化动力学的影响，即增加相互作用结构的复杂性.文[5J首次研究了小世界网不失一般性，令P=O,b=<1>c>O.重复博络上进化囚徒困境博弈模型，个体采取确定性的弈就是相同的博弈在长期中不断地重复进行，博策略更新规则，每轮过后个体采取其邻居中收益弈的任何阶段实际上都是一个完全信息静态博最高的个体的策略.文[6J则研究了一个真实社弈，它和完全信息动态博弈的一个重

4、要区别在于会网络拓扑上的进化囚徒困境博弈，合作者策略博弈的任意一个阶段都会产生相应的收益.在囚频度的时间演化出现了非常复杂的行为，系统中徒困境中，采用(C，C)策略两者的收益最大，但出现了多个亚稳态，并在这些亚稳态之间进行跳是因为双方事前并不知道对方的策略，所以(D，转.应用进化囚徒困境博弈模型，文[7J比较了在D)是一个纳什均衡点.不同拓扑结构下，收益矩阵元参数和温度对合作命题<1如果阶段博弈G有唯一的纳什均行为维持的影响.本文基于重复囚徒困境的思想，衡，则对任意有限的T，重复博弈G(T)有唯一的提出了两种算法，研究在网络演化时，不同的演化子博弈完美均衡，即G的纳什均衡结果在每一个算法对于

5、网络结构的影响.阶段重复进行.根据命题<1可知，囚徒困境博弈重复有限次，那么唯一的均衡结果只能是(D，D).说明博弈双<1基于重复博弈的算法描述方如果单纯进行时间上重复的博弈，永远不可能通常情况下，博弈由下面几部分组成[<>8]博获得最大的收益(C，C).为了完成从(D，D)到(C，C)的转换，采用一报还一报策略(tit-for-tat),弈个体，博弈策略乱，收益函数U??1在囚徒困境博i它的定义如下:在第一阶段选择合作，在t><1的弈(prisoner'sdilemma)中，每个博弈个体有两种任意阶段选择的策略等于对于在t><1阶段选择策略:合作(cooperatio

6、凡C)与背叛(defection,收稿日期:20<12-09甸24;修回日期:20<12-<10-30作者简介:王伊蕾(I叨9一)，女，山东济南人。讲师，博士研究生，主要研究方向为复杂网络、博弈论、网络安全。8><#004699'>E-mail:机ran!Lyilei2删@<163.como第<1期王伊蕾:重复囚徒困境博弈对网络拓扑结构影响的研究29的策略.34，从p(r)中寻找s的背叛次数最多的邻居，将根据重复博弈的囚徒困境的思想，构造网络与该邻居的边断开，并且记录该邻居的列号h.模型演化的算法(随机算法):(i)初始网络G=(vii)Forq=<1:34，依次查找节点h中每一个邻居的度，

7、放人数组U中，变量u记录数组U的个数，(V,<#004699'>e)，这里V表示节点的集合，<#004699'>e表示各节点两两相连的边.采用Zachary网络[剖，如果两个俱乐部同时建立一个数组切，记录h的每一个邻居的行成员之间有联系，那么就有边相连，否则元边.因号以及度最小的邻居.(viii)从数组U中查找节为是一个无向图，所以用一个34x34的对称矩阵点h度最小的邻居，在w中查找它的行号，并且赋A来表示