一种基于半张量积的多层网络演化博弈方法

2017-12-19武利琴王金环

复杂系统与复杂性科学 2017年3期

关键词：代数收益动态

武利琴，王金环，徐勇

(河北工业大学理学院，天津 300401)

一种基于半张量积的多层网络演化博弈方法

武利琴，王金环，徐勇

(河北工业大学理学院，天津 300401)

针对多层网络演化博弈，采用半张量积方法，遵循短视最优响应策略更新原则，将博弈动态过程进行公式化并研究其策略最优问题。首先，通过半张量积将多层网络演化博弈转化成代数公式的形式，建立相应的转化算法;其次，基于该公式，讨论了博弈的动态行为;最后，通过增加伪玩家到博弈中来研究策略最优问题，目的是设计自由控制序列来最大化伪玩家的平均收益，从而得到最优控制序列。并举例验证了研究结果的有效性。

多层网络演化博弈；代数公式；策略最优；半张量积

0 引言

近年来，随着复杂网络的兴起与发展，网络演化博弈也被众多学者广泛研究。与此同时，半张量积这种新型有效的方法也成功地应用到网络演化博弈中[1]。例如对经典网络演化博弈模型的代数公式化与策略一致性等问题的研究[2-5]。结合实际问题，演化博弈又针对支付函数非对称以及有向布尔网络方面进行了讨论[6-7]。在网络演化博弈中，一个最基本的问题就是根据所有玩家的行为来分析演化趋势，如局部物流节点之间合作竞争关系的演化博弈分析[8]。但大多数的研究主要集中在单层网络，而现实中许多复杂系统的节点具有多种功能，并且相互连接和作用，而这多种功能有质的区别，不能叠加，从而就构成了多层网络[9]。于是学者们对多层网络博弈的研究也逐渐增加，如多层网络中传染病的传播与免疫[10-11]，相互依存网络上的囚徒困境博弈[12-13]。但传统的方法都是基于蒙特卡罗和其他类似的数值仿真来研究博弈演化的趋势，很难用于更一般化的情形，例如非对称网络。本文从理论方面入手，研究了多层网络演化博弈模型的代数公式化与策略最优问题。

本文借鉴文献[8]中物流的合作竞争关系模型，在文献[4]的基础上进行了推广。结合实际应用，对网络中的节点按照一定的原则进行分层。每个节点在不同层之间扮演的角色不一样，比如在社会网络中，每个人对待亲近之人与陌生人的态度、容忍度都有很大差别，并不全然相同。因此，假设同一层中玩家相互博弈的支付矩阵是对称的，不同层之间玩家相互博弈的支付矩阵是非对称的。本文运用矩阵半张量积，从理论上构建了多层网络演化博弈的代数模型，并针对策略最优问题进行了研究，获得不唯一的自由控制序列，更加符合实际应用。原文献[4]中的博弈就是该多层网络博弈中层数为1的一种特殊情况。

1 矩阵的半张量积

本节给出关于半张量积的常用符号、定义和基本性质。

定义1[1]设A∈Mm×n，B∈Mp×q，l=lcm{n，p}为n与p的最小公倍数，那么A与B的半张量积定义为

定义2(Khatri-Rao积)A∈Mp×n，B∈Mq×n。它们的Khatri-Rao积，记A*B，定义为

A*B=[Col1(A)⊗Col1(B)Col2(A)⊗Col2(B)…Coln(A)⊗Coln(B)]∈Mpq×n。

命题1[1](1)设X∈Rm及Y∈Rn为两列向量，则

W[m，n]XY=YX，W[n，m]YX=XY，

其中,mn×mn矩阵W[m，n]被称为换位矩阵，且W[n，n]∶=W[n];

(2)设A∈Mm×n，那么W[m，n]Vr(A)=Vc(A)，W[n，m]Vc(A)=Vr(A);

(3)设X∈Rt和A∈Rm×n，则XA=(It⊗A)X，这称为伪交换性质。

(1)

引理3[3]1)网络演化博弈的动态行为中长度为s环的数量用Cs表示，归纳如下:

2 多层网络演化博弈模型的代数公式与策略最优问题

2.1 多层网络演化博弈模型

一个多层网络正规有限博弈，由3个基本元素组成:

2)一个两人基本博弈G∶=(S，A)∪(S，B)，其中S={s1，s2，…，sk}是策略集。设同一层玩家之间的支付矩阵A=(aij)k×k是对称的，不同层玩家之间的支付矩阵B=(bij)k×k是非对称的。aij和bij分别表示同层和不同层中任意玩家采用策略si，它的对手采用策略sj所对应的收益。令aij，bij分别满足如下条件:

假设博弈可无限次地重复。每一次玩家只与他的邻居进行博弈，对应合计收益pi:SUi+1→R是通过与所有邻居博弈获得的收益总和，满足:

(2)

其中pij:S×S→R表示玩家i与它的邻居j博弈的收益。

3)策略更新原则F∶={f1，f2，…fn}。本文采用短视最优响应策略更新规则，即每个玩家预测它的对手将会重复上一次的策略，并在当前时刻选择应对邻居上一时刻策略的最优策略。基于该策略更新原则，在时刻t玩家i的策略xi(t)采取形式

(3)

若玩家i的最优应对策略不止一个，即|Hi|>1时，定义如下优先策略规则:对于∀si，sj∈S，si>sj⟺i>j。因此玩家i根据如下规则选择策略:

xi(t)=max{x|x∈Hi}，i∈N

(4)

博弈的最终动态行为只有两种情况。一是所有玩家的策略保持固定在某一个局势上，称为稳定点;二是当周期s≥2时，一些策略局势能被周期性地选择，称为长度为s的环。

2.2 博弈的代数公式化

根据策略更新原则式(3)，多层网络演化博弈可看作是一个k值逻辑网络博弈，因此通过使用k值逻辑矩阵表达式可将动态行为转化为代数形式。根据短视最优响应原则，玩家i在时刻t的策略是应对邻居上一时刻策略的最优选择。因此，分两步构造多层网络演化博弈的代数公式:1)通过构造支付函数的结构矩阵将玩家的收益函数转化为代数形式;2)比较所得结构矩阵的组成元素来确定每个玩家的最优策略。

∶=Mpix-i(t)xi(t)。

其中，Mpi∈R1×kn是pi的结构矩阵，xi(t)∈Δk是玩家i在时刻t的策略，且

最后，寻找使玩家i收益最大化的最优响应策略，即找出Mpi里每一块中最大元素的列指标。对于所有的l=1，2，…，kn-1，令ξl为列指标，满足

Colξl(Blkl(Mpi))≥Colξ(Blkl(Mpi))，∀ξ=1，…，k

基于以上分析，可构建如下算法将多层网络演化博弈转化成代数形式。

算法11)计算每个玩家i∈N的收益函数pi的结构矩阵Mpi，有

(5)

2)将Mpi分为kn-1相同的块，有

Mpi=[Blk1(Mpi)，…，Blkkn-1(Mpi)]

(6)

对于所有的l=1，2，…，kn-1，找出相应列指标ξl，满足

ξl=max{ξl|Colξl(Blkl(Mpi))=max1≤ξ≤kColξ(Blkl(Mpi))}

3)构建多层网络博弈的代数形式

x(t+1)=Lx(t)

(7)

根据以上算法可知，博弈的所有特征可由代数形式(7)中的转移矩阵L完全显示。可通过研究L的性质来分析博弈动态过程。主要优势就是可通过代数公式研究博弈的动态行为，分析其演化趋势。

2.3 博弈的策略最优问题

本小节通过增加伪玩家到博弈中，研究其策略最优问题。根据实际情况选择某一层中的某一玩家作为伪玩家，代表外部控制输入。不失一般性，假设玩家1(假设位于Nm层)为可自由采取策略的伪玩家。设u(t)∈Δk为伪玩家在时刻t的策略，xi(t)∈Δk为玩家i∈{2，3，…，n}在时刻t的策略。给出一个充要条件，使从任意初始策略局势开始的博弈动态过程均可收敛到最优策略局势。同时，设计一个自由控制序列来最大化长期运行下伪玩家的平均收益:

(8)

其中，

首先，由算法1可得博弈的代数形式

x(t+1)=Lu(t)x(t)

(9)

定理1考虑多层网络演化博弈的代数形式(9)，则有

(10)

换句话说，一旦每个玩家i∈{2，3，…，n}在时刻t都采用策略sk，令伪玩家也采用策略sk，那么对于玩家i∈{2，3，…，n}将会永远保持策略sk。

(11)

因此式(10)成立。证毕。

为了确保博弈的演化过程全局收敛到最优策略局势，需要保证最优策略局势在最优控制序列下全局可达。对任意的t∈Z+，有

(13)

(14)

定理2如果条件式(13)成立，则在自由控制序列(14)下，博弈演化过程能够全局收敛到最优策略局势，且在长期运行下伪玩家能获得最大平均收益

另外，本文的目的是引入伪玩家控制演化过程使博弈达到一个适当的均衡。当一个伪玩家不能实现这个目标时，可以考虑引入更多的伪玩家，使其达到稳定的均衡状态。

图1 多层网络示意图(M=3)Fig.1 Multi-layer network diagram(M=3)

图2 三层网Fig.2 Three-layer network

3 举例分析

例1考虑多层网络演化博弈:5个玩家，用N={1，2，3，4，5}表示，且N1={1}，N2={2，3}，N3={4，5}每个玩家都有相同的策略集S={s1，s2};5个玩家的网络拓扑结构图如图2所示;同层玩家之间的对称支付矩阵A=[3 2;2 6]，不同层玩家之间的非对称支付矩阵B=[2 1;0 5];演化规则为短视最优响应原则。

其中,Mpi是pi的结构矩阵，Vr(A)=[3 2 2 6]，Vr(B)=[2 1 0 5]，xi(t)∈Δ2，i∈N，x(t)=(x1(t)，x2(t)，x3(t)，x4(t)，x5(t))。

根据式(5)，建立如下的博弈代数形式，计算每个玩家的收益函数:

Mp1=[2 0 1 5](Ed，2)3(W[2，8]+W[4，4])

=[4 0⋮4 0⋮4 0⋮4 0⋮3 5⋮3 5⋮3 5⋮3 5⋮3 5⋮3 5⋮3 5⋮3 5⋮2 10⋮2 10⋮2 10⋮2 10]

Mp2=[3 2 2 6](Ed，2)3W[4，4]+[2 0 1 5](Ed，2)3(W[2，8]+W[8，2])

=[7 2⋮7 2⋮6 7⋮6 7⋮6 6⋮6 6⋮5 11⋮5 11⋮6 7⋮6 7⋮5 12⋮5 12⋮5 11⋮5 11⋮4 16⋮4 16]

Mp3=[3 2 2 6](Ed，2)3W[4，4]+[2 0 1 5](Ed，2)3(W[2，8]+W[16，1])

=[7 2⋮6 7⋮7 2⋮6 7⋮6 6⋮5 11⋮6 6⋮5 11⋮6 7⋮5 12⋮6 7⋮5 12⋮5 11⋮4 16⋮5 11⋮4 16]

Mp4=[3 2 2 6](Ed，2)3W[16，1]+[2 0 1 5](Ed，2)3W[4，4]

=[5 2⋮4 6⋮5 2⋮4 6⋮4 7⋮3 11⋮4 7⋮3 11⋮5 2⋮4 6⋮5 2⋮4 6⋮4 7⋮3 11⋮4 7⋮3 11]

Mp5=[3 2 2 6](Ed，2)3W[16，1]+[2 0 1 5](Ed，2)3W[8，2]

=[5 2⋮4 6⋮4 7⋮3 11⋮5 2⋮4 6⋮4 7⋮3 11⋮5 2⋮4 6⋮4 7⋮3 11⋮5 2⋮4 6⋮4 7⋮3 11]

L1=δ2[1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2]

L2=δ2[1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

L3=δ2[1 2 1 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

L4=δ2[1 2 1 2 1 2 1 2 2 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 2 2 2 2 2 2 2 2]

L5=δ2[1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2]

因此，博弈的代数形式

x(t+1)=Lx(t)

(15)

其中，博弈转移矩阵

第三步:考虑博弈的策略最优问题。设第N1层中玩家1为伪玩家，通过算法1可得博弈的代数形式

x(t+1)=Lu(t)x(t)

(16)

根据一个简单的计算

根据引理4，上述多层网络的演化过程在自由控制序列

上述三层网络演化博弈中，运用半张量积方法将博弈过程抽象为动态方程，由博弈结构矩阵可知，演化博弈最终以稳定状态呈现，没有出现周期性状态。在此基础上考虑将玩家1作为伪玩家，设计了不同控制序列，使其达到平均收益最大的目的，进一步验证了本文关于多层网络演化博弈研究方法的有效性。因此该方法可用于更多层数的网络演化博弈分析。

4 结束语

本文对博弈发生网络上的节点进行分层，假设同一层玩家之间的支付矩阵是对称的，不同层玩家之间的支付矩阵是非对称的。通过半张量积方法和短视最优响应原则，对该类多层网络演化博弈的代数公式化与策略最优问题进行了研究。首先，将多层网络演化博弈的动态行为转化成代数公式的形式，建立了相应的算法。其次，基于博弈代数公式，讨论了多层网络演化上的动态行为。最后，通过增加伪玩家到博弈中来研究策略最优问题，目的是设计自由控制序列最大化伪玩家的平均收益，且控制序列不唯一，非常切合实际应用。

[1] Cheng D Z, Xu T T, He F H, et al. Semi-tensor product approach to networked evolutionary games[J].Control Theory and Technology, 2014, 12(2):198-204.

[2]Cheng D Z, Xu T T, Qi H S. Evolutionary stability strategy of networked evolutionary games[J]. IEEE Transactions on Neural Networks and Learning Systems, 2013, 1641-1653.

[3]Cheng D Z, He F H, Qi H S, et al. Modeling analysis and control of networked evolutionary games[J].IEEE Transactions on Automatic Control, 2015, 60(9):2402-2415.

[4]Guo P L, Wang Y Z, Li H T. Algebraic formulation and strategy optimization for a class of evolutionary networked games via semi-tensor product method[J]. Automatic, 2013, 49:3384-3389.

[5]Ge M X, Li Y, Zhao J L, et al. Strategy consensus of networked evolutionary games[J]. Journal of Shandong University(Natural Science) , 2015, 50(11):113-118.

[6]Du W B, Cao X B, Hu M B. The effect of asymmetric payoff mechanism on evolutionary networked prisoner’s dilemma game[J]. Physic A:Statistical Mechanic and its Application, 2009, 388(24):5005-5012.

[7]Zhao Y, Li Z Q, Cheng D Z. Optimal control of logical control networks[J]. IEEE Transactions on Automatic Control, 2011, 56(56):1766-1776.

[8]Wang D Z, Lang M X, Sun Y. Evolutionary game analysis of co-opetition relationship between regional logistics nodes[J].Journal of Applied Research & Technology, 2014, 12(2):251-260.

[9]陆君安. 从单层网络到多层网络的——结构、动力学和功能[J].统计物理和复杂系统研究前沿进展专题II, 2015, 4(27):3-8.

Lu Junan. From single-layer network to multi-layer network-structure, dynamics and function[J]. Statistical Physics and Complex Systems Research Erontier Development TopicⅡ, 2015, 4(27):3-8.

[10] Gao B, Deng Z H, Zhao D W. Competing spreading processes and immunization in multiplex networks[J]. Chaos, Solitons and Fractals, 2016,93:175-181.

[11] Wu Q C, Lou Y J, Zhu W F. Epidemic outbreak for an SIS model in multiplex networks with immunization[J].Mathematical Biosciences, 2016,277:38-46.

[12] Luo C, Zhang X L, Liu H, et al. Cooperation in memory-based prisoner’s dilemma game on interdependent networks[J]. PhysicA,2016, 450:560-569.

[13] Meng X K, Xia C Y, Gao Z K, et al. Spatial prisoner’s dilemma games with increasing neighborhood size and individual diversity on two interdependent lattices[J].Physics Letters A, 2015, 379:767-773.

MultilayerEvolutionaryNetworkedGamesBaseonSemi-TensorProduct

WU Liqin, WANG Jinhuan, XU Yong

(School of Sciences, Hebei University of Technology, Tianjin 300401, China)

Using the semi-tensor product method, this paper investigates the algebraic formulation and strategy optimization for a class of multilayer evolutionary networked games with “myopic best response adjustment” rules. Firstly, the dynamics of the multilayer evolutionary networked game is converted to formulate for the game. Secondly, based on the algebraic form, the dynamic behavior of the multilayer evolutionary networked games is discussed. Finally, the strategy optimization problem is considered by adding a pseudo-player. The aim is to design optimal control sequence to maximize the average income of pseudo-players. An illustrative example shows the effectiveness of this paper.

multilayer evolutionary networked games; algebraic formulation; strategy optimiza-tion; semi-tensor product

1672-3813(2017)03-0068-07；

10.13306/j.1672-3813.2017.03.006