基于囚徒困境策略的改进HK网络上的合作博弈

2018-07-20邓云生杨洪勇

智能系统学报 2018年3期

邓云生，杨洪勇

（鲁东大学信息与电气工程学院，山东烟台 264025）

随着复杂网络研究的兴起，许多现实世界中的系统都可以使用复杂网络进行描述。系统中的元素被视为网络中的节点，节点的边用来表示元素之间的相互作用和关系。例如，现实社会中的演员合作网、交通运输网、Internet网等都可以用复杂网络进行描述。现实网络规模巨大，节点间联系多而复杂的拓扑结构引起许多学者的极大兴趣，对其进行了大量的研究。

1 网络博弈研究现状

最为成功的复杂网络模型当属WS小世界网络模型[1]和BA无标度网络模型[2]。许多复杂网络方面的研究都是基于这两个模型而展开的。然而这两个模型都有不足之处，不能真实再现现实中的网络结构。WS模型具有与现实网络相符合的高聚类系数特征，但其度分布为泊松分布，这与现实网络不符。BA模型的度分布具有与现实相符的幂律特点，但其聚类系数却很低，这一特征与现实网络尤其是社会网络的特征相去甚远。

有鉴于此，Holmes和Kim[3]构造了一种可调聚类系数的网络模型(HK模型)，该模型利用一个可调参数 pt通过不断构造网络的局部三角形结构，最终形成一个同时具有高聚类特性和幂律分布特性的网络。其基本思想是，考虑到聚类系数实际上描述的是第3个节点与前两个节点一起形成三角形的概率，因此在网络的形成过程中故意增大形成三角形的可能，则可实现改变聚类系数的目的。HK网络模型提出后，许多学者在此基础上对其进行了改进和研究。文献[4]在HK网络的基础上，通过引进新增节点所应具备的连接动态性，改进了HK模型的局部特性；文献[5]提出了度分布和聚类系数均可调的扩展HK模型，将HK网络模型中的三角形结构扩展到旧的节点之间；文献[6]在HK模型基础上引入加速增长机制，再现了真实网络中低阶幂律集团度分布特性；文献[7]提出的改进HK网络模型综合考虑了“优先连接”、“三角结构”、“内部演化”等机制；文献[8]研究了基于HK模型的交通网络，在此基础上提出了一种新的路由算法，有效缓解了交通拥堵，大大提高了交通运输的负载能力；文献[9]进一步推广了HK网络，改进了HK网络构造过程中两步的连接方式，对同一时间内采用度优先连接的节点数量及其被连接的邻居数量进行限制，构造出一种新的具有幂律分布且平均聚类系数可调的网络模型；文献[10]研究了HK网络上聚类系数对级联故障的影响，研究结果表明，具有过高或过低聚类系数的网络在面对蓄意攻击时表现出脆弱性的一面，而具有适度聚类系数的网络能更好地抵御级联故障的传播；文献[11]研究了聚类系数在相互关联的两个HK网络面临蓄意攻击时的作用，研究发现高聚类系数会增大网络的脆弱性；文献[12]提出了一个改进的在线社交网络谣言传播模型，并在HK网络环境上进行仿真实验，实验结果发现，谣言的传播能力会随着网络聚类系数的增加而得到抑制；文献[13]在HK网络模型上，采用Susceptible-Infective-Removal(SIR)模型进行传播影响力的仿真实验，得出了网络聚类系数的改变会对节点中心性指标的准确性产生重要影响的结论。

复杂网络上的博弈研究始于Nowak和May[14]研究的囚徒困境博弈在规则方格网络上的动态演化，研究发现合作者在方格网络上可以通过聚集来抵抗背叛策略入侵。受此影响，许多学者采用不同的博弈模型在不同的网络结构上进行研究，得到了丰富的理论成果。例如，文献[15]研究了可调聚类系数的无标度网络上的合作现象，研究发现高聚类系数有利于网络中合作行为的演化；文献[16]研究了齐次网络上的囚徒困境博弈，研究结果表明改变收益矩阵中的参数确实会影响系统的演化过程；Li等[17]在3种规则网络上研究了雪堆博弈，研究发现在复制动力学策略调整规则下可以抑制合作行为的参数区间；Zhang等[18]研究了随机规则网络上的雪崩博弈，研究发现当雪崩博弈成本收益率较小时，系统演化为全面合作状态，反之合作与背叛在系统中共生；文献[19]研究了基于记忆效应的囚徒博弈在相互依存网络中的合作现象，发现了与记忆长度和依赖程度相关的最优参数区间，可以极大地促进网络中合作现象的涌现；文献[20]研究了加权网络空间上的囚徒博弈，通过仿真实验发现网络中合作者密度会随网络耦合程度的升高而变大；文献[21]研究双复杂网络上的囚徒博弈，可以提高合作的水平，同时也揭示双网络模型下背叛领袖对合作水平的影响及其与合作领袖的互动机理。

受以上研究启发，本文提出了一种改进的HK网络模型，改进后的模型在服从幂律分布且幂律可调的情况下与HK网络模型相比具有更高的聚集系数。由于网络结构的改变是影响演化博弈的一个重要因素，本文在改进的HK网络模型上采用囚徒博弈模型，进一步研究了网络结构对博弈中合作行为的影响。

2 改进的HK网络模型

2.1 网络模型内部演化机制

现实的社会网络中，相识的两个人可能同时认识一个新的朋友，进而有一定的机率同时认识这个新朋友的朋友，本文提出的改进后的HK模型正是反映了这种情况。

HK网络构造过程如下。

1)初始状态：网络初始状态有m0个全连通节点。

2)增长机制：每一个时间步，向网络中加入一个带有 m条边的节点i 。连接过程中，节点i的第一条边按照度优先规则连接到网络中已存在的节点 j，即选择节点 j 的概率为

3)其余 m −1 条边以概率 p 随机连接到节点 j的邻居上，否则以概率1 −p使用度优先规则在网络中择优连接。

在此基础上，本文提出了如下改进HK网络模型(EHK)的演化机制。

1)初始状态: 网络初始状态有 m0个全连通节点。

2)增长机制: 每一个时间步，加入两个连接在一起的节点，每个节点有 m 条边。这两个节点的每一条边进行两两配对，共有 m 对边与网络中已经存在的节点进行相连。这两个节点之中的第一对边按度优先规则与网络中已存在节点(例如选中节点j)进行连接。

3)其余 m −1 对边，首先考虑以概率 p连接到节点 j的邻节点上。在此过程中，若有 le n≥m−1 ( l e n为节点 j的邻居节点数目)，可将 m −1对边随机无重复连接到i的邻节点上，否则 j的邻节点全部与新加入的节点相连，多出的 m −1−len对边在全局按照度优先规则进行连接。

4)若 m −1 对边未能以概率 p 与节点 j的邻节点相连，则这 m −1对边在全局按照度优先规则进行连接。

5)终止条件: 重复 2)、3)、4)步，直至网络规模N达到设定值。

2.2 EHK网络模型演化动力学分析

根据EHK网络模型演化机制，经过t步，点i在t+1时刻的度ki的动力学方程满足:

式中 kj1,kj2,···,kjv为节点i的邻居。

网络中的节点每增加一条连边，网络中的度增加2。每一时刻网络中增加2个节点，网络中增加2m+1 条连边，网络的度增加4 m +2。

解该方程:

将节点i看作 ti时刻进入网络的节点，则 ki=m+1；将 ki代入式(3)得

节点i的度为

假设等时间间隔向网络中增加节点，则 ti的概率密度

进而有

由式 (7 )可知，当 t → ∞时， p (k)≈ 2m2k−3−m1。

这表明，本文提出的EHK模型的度分布近似服从幂指数 γ =3+m−1的幂律分布。幂指数 γ ∈(3,4]，这意味着EHK模型是一个非均匀的异质网络。随着 γ增大，EHK的度分布的均匀性也不断增加。故EHK模型同时也是一个幂指数可调的幂律度分布网络模型。

由网络模型的构造算法可看出每一个时间步引入的节点与网络中已存在的节点每进行一次成功连接，必然构造出一个局部三角形结构，通过聚类系数的定义直观上可以看出由该演化机制构造的网络模型必然具有更高的聚类系数。

2.3 仿真分析

为验证2.2节中的结论，检验提出的EHK网络模型是否会继承HK网络模型度分布服从幂律分布这一特性，本文通过仿真实验做出EHK网络的度分布图(见图1)。图1中网络初始状态为 m0=100，m=80， p =0.8 最终生成的网络规模大小 N =11 000。由生成的结果度分布图可看出EHK网络的度分布具有幂律分布的特点，即绝大部分的节点度相对较低，但存在少量度值相对很高的节点，这类度值高的节点通常也被称为hub节点。这类度分布服从幂律分布的网络也被称为幂律网络。

图1 EHK网络节点度分布图Fig. 1 Degree distribution of EHK networks

此外，网络中节点i的聚类系数Ci的几何定义为

对网络所有节点的聚类系数 Ci取平均值,就得到整个网络的平均聚类系数CC，即

网络的平均聚类系数CC可以用来描述网络中节点之间形成三角形结构的趋势。其值反映了网络中三角结构连接的密度。由网络模型的构造算法可看出，每一个时间步引入的节点与网络中已存在的节点每进行一次成功连接，必然构造出一个局部三角形结构。通过聚类系数的定义直观上可以看出，由该演化机制构造的网络模型必然具有更高的聚类系数。

图2中的仿真结果显示了本文提出的网络模型的聚类系数与HK模型平均聚类系数的比较，初始条件为 m0=10， m =4 ，最终生成网络规模 N =5 000，图中每一个数据是10组运算取平均值后所得到的结果。

图2 EHK网络与HK网络平均聚类系数对比Fig. 2 Comparison of the average clustering coefficient between EHK and HK

由仿真结果可见，相同条件下，聚类系数的值随可调节概率 p 的值增加而增加；概率 p相同时，采用新算法生成网络的聚类系数要高于HK算法生成网络的聚类系数。此外，在求得各个节点的聚类系数基础上，还可以进一步定义度为k的节点的聚类系数平均值并将其表示为节点度的函数，即

其中 ωkik定义为

研究表明，许多真实网络的 C (k)分布服从幂律分布，即 C (k)∼ k−γ(γ ＞ 0)。对图1中的网络，做出其聚类系数与节点度相关性曲线(见图3)。由图3仿真结果可知，EHK网络中节点的平均聚类系数随着节点度数 k的增大而减小，即EHK网络中度数大的节点具有较小的平均聚类系数，而度数小的节点的平均聚类系数较大。这也说明，EHK网络中度数较小的节点及其邻接点之间的联系更加紧密。

图3 平均聚类系数C (K)与度的关系Fig. 3 Relation between the average clustering coefficient and degree k

真实世界的网络往往为幂律网络，且具有高聚类的特性。由图1和图2的分析可知，本文构建的网络模型成功再现了这两个特征，并且图3的仿真结果也说明本文构建的网络符合现实网络的特征，由此可见本文所构建的网络模型能够很好地描述真实网络结构特性。

3 EHK网络上囚徒博弈

3.1 囚徒博弈模型

在囚徒困境博弈模型(prisoner’s dilemma game，PDG)中，每个人都有两种选择合作(cooperation，C)与背叛 (defection，D)。其收益矩阵为

式中：最左侧一列代表自己的选择；最上面一行代表对方的选择；R为相互合作的奖励，即(C, C)策略组合中，选择C策略所获得的个体收益；S为给傻瓜的报酬，即(C, D)策略组合中选择D策略所获得的个体收益；T为背叛的诱惑(temptation to defect)，即(D, C)策略组合中，选择D策略的个体收益；P为相互背叛的惩罚，即(D, D)策略组合中，采用D 策略的个体收益，且满足 T ＞R＞P＞S，2R＞T+S。在上述情形下，理性的参与者总是会选择背叛策略作为自己的最佳策略，但从总体而言只有都选择合作策略才能使收益达到最大。然而当理性的参与者相互背叛时，没有参与者愿意单方面改变自己的策略，因为这样做会降低自身的收益，因此相互背叛状态(D, D)就构成了囚徒博弈的纳什均衡状态。

本文提出的EHK网络中每一个节点代表一个博弈个体。采用由Nowak和May提出的简化的单参数囚徒博弈模型，其收益矩阵为式中 b ＞1。令 S代表博弈个体的策略类型，其取值为[1 0]T( 代表合作)或 [0 1]T( 代表背叛)；个体i与其邻居 j进行一次博弈所得收益 ui可以表示为 ui=STiPSj，在每一轮博弈过程中，每个博弈个体都与自己直接相连的邻居进行博弈，将博弈个体i得到的收益总和记为

式中 Ωi为 i的所有邻居节点集合。然后所有个体更新它们的策略，即个体i 随机选择自己的邻居 j，比较它们的收益，若有 ui≥uj，则个体i在下一轮中采取的博弈策略不变；否则个体i将以概率 pi←j采取其邻居j的策略进行下一轮博弈。其中

此外合作者密度 ρc(t)是用来刻画网络博弈行为的重要物理量，其定义为采取合作策略的博弈个体占所有博弈个体的比例，即 ρc(t)=nc(t)N−1， nc(t)表示t博弈时采用合作策略的博弈个体数量。在网络科学研究的过程中通常会关注某一类节点的整体行为。当网络博弈进行的某一时刻，网络中采取合作策略的节点比例趋于稳定不再发生变化，则称这些采取合作策略的节点达到合作稳定状态。这种多数节点的合作稳定状态也正是本文需要研究的内容。博弈初始时刻，采用合作策略和背叛策略的博弈个体均以50%的比例随机存在于生成的EHK网络中，每个博弈个体根据其初始策略和收益矩阵按照式(1)计算其收益总和，然后根据策略更新规则式(15)更新其策略，更新完后的策略作为博弈个体下一轮博弈中使用的策略。每一次博弈策略的更新会使合作者密度 ρc(t)在下一次博弈之前发生变化，随着博弈的不断进行，合作者密度 ρc(t)会逐渐达到动态平衡状态。博弈演化流程如图4所示。

3.2 仿真分析

3.2.1 高聚类特性对合作行为的影响

由第2节的研究可知，相同条件下可调节概率p的值越大，其生成网络的聚类系数越高，故可直接用 p值对网络动力学特征进行讨论。在由 m0=m=2、T=1.5生成 N =1 000的EHK网络上进行博弈，初始时采用合作策略的个体和采用背叛策略的个体均以50%的比例随机存在于网络中，博弈演化规则如图4所示，博弈次数1 000次，取最后50次博弈中合作者密度的平均值为达到动态平衡时的合作者密度，记为 fc仿真结果如图5所示。

图4 博弈演化流程Fig. 4 Process of game evolution

图5 合作者比例随聚类系数变化Fig. 5 Variation in the partner proportion and clustering coefficient

图5 中每个数据是相同初始条件下10次重复实验所得到的平均值。由图5仿真结果可知合作者比例维持在0.75以上，这充分表明EHK网络对合作行为具有较大的促进作用。其原因是，EHK网络是高聚类异质网络，其中必然会存在许多具有多三角形结构的高连接度的hub节点，若hub节点选择合作策略，由于其采用累计收益的计算方式，会使hub节点获得较高的收益，由式(15)可知其所采用的合作策略容易被其低收益的邻居节点采纳。由式(13)可知采用(C, C)策略的双方收益都为1，而hub节点采用累计收益的计算方式，会使其始终成为被模仿的对象，这有利于合作行为在网络中进行传播。

若hub节点初始采用背叛策略，则由累计收益的计算方式和式(13)可知，hub节点会从其大量采用合作策略的邻居中获得较高的收益，由博弈演化策略可知，这些采用背叛策略的邻居在进行策略调整时会模仿hub节点的背叛策略，而由式(13)可知采用(D, D)策略的双方收益为零，故在下一次的网络博弈中hub节点的收益会随着采用背叛策略邻居增多而大幅下降。

随着网络博弈的进行，hub节点的收益会下降到使其本身所采用的背叛策略不再是其邻居节点模仿的对象，进而在某一时刻hub节点会模仿其邻居的合作策略，此时利用其hub节点本身具有的多连接的资源优势随着网络博弈的进一步演化会逐渐使其采用的合作策略成为被邻居节点模仿的对象。

由上述分析可知合作策略容易占据网络中的高度连接的hub节点，进而影响其周围邻居也采用合作策略，促进在EHK网络上合作现象的涌现。

3.2.2 背叛的诱惑对合作行为的影响

本节考虑收益矩阵式(13)中参数 b(背叛的诱惑)增大时，对网络上博弈个体的合作行为的影响。在初始状态为 m0=m=2 ，规模 N =1 000的EHK网络上进行80次博弈后的仿真结果(见图6)。由图6可见，无论可调概率 P 值取多大，当诱惑参数 b值增大时，群体中合作者的均衡密度 fc都呈现出减小的趋势。这是因为，当诱惑参数 b增大时节点采取背叛策略将得到更大的收益，而采取合作策略的节点的收益并没有增加。由策略调整式(14)可知，这将会增大两者收益之差，进而会加大合作者模仿背叛者的概率，从而在宏观上表现为合作者的密度 fc的值下降。然而，合作者均衡密度虽然整体呈现下降趋势，但下降幅度并不大，这种较小的降幅主要是因为EHK网络的空间结构对合作行为在囚徒博弈上的影响。过高的聚类系数使得网络中节点的联系更加密切，必然会使得低连接度的节点在高连接度的节点周围形成三角结构，这种三角结构会使得当高度节点偶尔采用背叛策略时，低度节点仍然保持合作策略不变[14]。大量的这种三角形结构会在空间集结成簇，共同抵御背叛策略的入侵。