武利琴，王金環(huán)，徐 勇

(河北工業(yè)大學(xué)理學(xué)院，天津 300401)

一種基于半張量積的多層網(wǎng)絡(luò)演化博弈方法

武利琴，王金環(huán)，徐 勇

(河北工業(yè)大學(xué)理學(xué)院，天津 300401)

針對多層網(wǎng)絡(luò)演化博弈，采用半張量積方法，遵循短視最優(yōu)響應(yīng)策略更新原則，將博弈動態(tài)過程進(jìn)行公式化并研究其策略最優(yōu)問題。首先，通過半張量積將多層網(wǎng)絡(luò)演化博弈轉(zhuǎn)化成代數(shù)公式的形式，建立相應(yīng)的轉(zhuǎn)化算法;其次，基于該公式，討論了博弈的動態(tài)行為;最后，通過增加偽玩家到博弈中來研究策略最優(yōu)問題，目的是設(shè)計(jì)自由控制序列來最大化偽玩家的平均收益，從而得到最優(yōu)控制序列。并舉例驗(yàn)證了研究結(jié)果的有效性。

多層網(wǎng)絡(luò)演化博弈；代數(shù)公式；策略最優(yōu)；半張量積

0 引言

近年來，隨著復(fù)雜網(wǎng)絡(luò)的興起與發(fā)展，網(wǎng)絡(luò)演化博弈也被眾多學(xué)者廣泛研究。與此同時，半張量積這種新型有效的方法也成功地應(yīng)用到網(wǎng)絡(luò)演化博弈中[1]。例如對經(jīng)典網(wǎng)絡(luò)演化博弈模型的代數(shù)公式化與策略一致性等問題的研究[2-5]。結(jié)合實(shí)際問題，演化博弈又針對支付函數(shù)非對稱以及有向布爾網(wǎng)絡(luò)方面進(jìn)行了討論[6-7]。在網(wǎng)絡(luò)演化博弈中，一個最基本的問題就是根據(jù)所有玩家的行為來分析演化趨勢，如局部物流節(jié)點(diǎn)之間合作競爭關(guān)系的演化博弈分析[8]。但大多數(shù)的研究主要集中在單層網(wǎng)絡(luò)，而現(xiàn)實(shí)中許多復(fù)雜系統(tǒng)的節(jié)點(diǎn)具有多種功能，并且相互連接和作用，而這多種功能有質(zhì)的區(qū)別，不能疊加，從而就構(gòu)成了多層網(wǎng)絡(luò)[9]。于是學(xué)者們對多層網(wǎng)絡(luò)博弈的研究也逐漸增加，如多層網(wǎng)絡(luò)中傳染病的傳播與免疫[10-11]，相互依存網(wǎng)絡(luò)上的囚徒困境博弈[12-13]。但傳統(tǒng)的方法都是基于蒙特卡羅和其他類似的數(shù)值仿真來研究博弈演化的趨勢，很難用于更一般化的情形，例如非對稱網(wǎng)絡(luò)。本文從理論方面入手，研究了多層網(wǎng)絡(luò)演化博弈模型的代數(shù)公式化與策略最優(yōu)問題。

本文借鑒文獻(xiàn)[8]中物流的合作競爭關(guān)系模型，在文獻(xiàn)[4]的基礎(chǔ)上進(jìn)行了推廣。結(jié)合實(shí)際應(yīng)用，對網(wǎng)絡(luò)中的節(jié)點(diǎn)按照一定的原則進(jìn)行分層。每個節(jié)點(diǎn)在不同層之間扮演的角色不一樣，比如在社會網(wǎng)絡(luò)中，每個人對待親近之人與陌生人的態(tài)度、容忍度都有很大差別，并不全然相同。因此，假設(shè)同一層中玩家相互博弈的支付矩陣是對稱的，不同層之間玩家相互博弈的支付矩陣是非對稱的。本文運(yùn)用矩陣半張量積，從理論上構(gòu)建了多層網(wǎng)絡(luò)演化博弈的代數(shù)模型，并針對策略最優(yōu)問題進(jìn)行了研究，獲得不唯一的自由控制序列，更加符合實(shí)際應(yīng)用。原文獻(xiàn)[4]中的博弈就是該多層網(wǎng)絡(luò)博弈中層數(shù)為1的一種特殊情況。

1 矩陣的半張量積

本節(jié)給出關(guān)于半張量積的常用符號、定義和基本性質(zhì)。

定義1[1]設(shè)A∈Mm×n，B∈Mp×q，l=lcm{n，p}為n與p的最小公倍數(shù)，那么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)設(shè)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)設(shè)A∈Mm×n，那么W[m，n]Vr(A)=Vc(A)，W[n，m]Vc(A)=Vr(A);

(3)設(shè)X∈Rt和A∈Rm×n，則XA=(It?A)X，這稱為偽交換性質(zhì)。

(1)

引理3[3]1)網(wǎng)絡(luò)演化博弈的動態(tài)行為中長度為s環(huán)的數(shù)量用Cs表示，歸納如下:

2 多層網(wǎng)絡(luò)演化博弈模型的代數(shù)公式與策略最優(yōu)問題

2.1 多層網(wǎng)絡(luò)演化博弈模型

一個多層網(wǎng)絡(luò)正規(guī)有限博弈，由3個基本元素組成:

2)一個兩人基本博弈G∶=(S，A)∪(S，B)，其中S={s1，s2，…，sk}是策略集。設(shè)同一層玩家之間的支付矩陣A=(aij)k×k是對稱的，不同層玩家之間的支付矩陣B=(bij)k×k是非對稱的。aij和bij分別表示同層和不同層中任意玩家采用策略si，它的對手采用策略sj所對應(yīng)的收益。令aij，bij分別滿足如下條件:

假設(shè)博弈可無限次地重復(fù)。每一次玩家只與他的鄰居進(jìn)行博弈，對應(yīng)合計(jì)收益pi:SUi+1→R是通過與所有鄰居博弈獲得的收益總和，滿足:

(2)

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

3)策略更新原則F∶={f1，f2，…fn}。本文采用短視最優(yōu)響應(yīng)策略更新規(guī)則，即每個玩家預(yù)測它的對手將會重復(fù)上一次的策略，并在當(dāng)前時刻選擇應(yīng)對鄰居上一時刻策略的最優(yōu)策略。基于該策略更新原則，在時刻t玩家i的策略xi(t)采取形式

(3)

若玩家i的最優(yōu)應(yīng)對策略不止一個，即|Hi|>1時，定義如下優(yōu)先策略規(guī)則:對于?si，sj∈S，si>sj?i>j。因此玩家i根據(jù)如下規(guī)則選擇策略:

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

(4)

博弈的最終動態(tài)行為只有兩種情況。一是所有玩家的策略保持固定在某一個局勢上，稱為穩(wěn)定點(diǎn);二是當(dāng)周期s≥2時，一些策略局勢能被周期性地選擇，稱為長度為s的環(huán)。

2.2 博弈的代數(shù)公式化

根據(jù)策略更新原則式(3)，多層網(wǎng)絡(luò)演化博弈可看作是一個k值邏輯網(wǎng)絡(luò)博弈，因此通過使用k值邏輯矩陣表達(dá)式可將動態(tài)行為轉(zhuǎn)化為代數(shù)形式。根據(jù)短視最優(yōu)響應(yīng)原則，玩家i在時刻t的策略是應(yīng)對鄰居上一時刻策略的最優(yōu)選擇。因此，分兩步構(gòu)造多層網(wǎng)絡(luò)演化博弈的代數(shù)公式:1)通過構(gòu)造支付函數(shù)的結(jié)構(gòu)矩陣將玩家的收益函數(shù)轉(zhuǎn)化為代數(shù)形式;2)比較所得結(jié)構(gòu)矩陣的組成元素來確定每個玩家的最優(yōu)策略。

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

其中，Mpi∈R1×kn是pi的結(jié)構(gòu)矩陣，xi(t)∈Δk是玩家i在時刻t的策略，且

最后，尋找使玩家i收益最大化的最優(yōu)響應(yīng)策略，即找出Mpi里每一塊中最大元素的列指標(biāo)。對于所有的l=1，2，…，kn-1，令ξl為列指標(biāo)，滿足

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

基于以上分析，可構(gòu)建如下算法將多層網(wǎng)絡(luò)演化博弈轉(zhuǎn)化成代數(shù)形式。

算法11)計(jì)算每個玩家i∈N的收益函數(shù)pi的結(jié)構(gòu)矩陣Mpi，有

(5)

2)將Mpi分為kn-1相同的塊，有

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

(6)

對于所有的l=1，2，…，kn-1，找出相應(yīng)列指標(biāo)ξl，滿足

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

3)構(gòu)建多層網(wǎng)絡(luò)博弈的代數(shù)形式

x(t+1)=Lx(t)

(7)

根據(jù)以上算法可知，博弈的所有特征可由代數(shù)形式(7)中的轉(zhuǎn)移矩陣L完全顯示?？赏ㄟ^研究L的性質(zhì)來分析博弈動態(tài)過程。主要優(yōu)勢就是可通過代數(shù)公式研究博弈的動態(tài)行為，分析其演化趨勢。

2.3 博弈的策略最優(yōu)問題

本小節(jié)通過增加偽玩家到博弈中，研究其策略最優(yōu)問題。根據(jù)實(shí)際情況選擇某一層中的某一玩家作為偽玩家，代表外部控制輸入。不失一般性，假設(shè)玩家1(假設(shè)位于Nm層)為可自由采取策略的偽玩家。設(shè)u(t)∈Δk為偽玩家在時刻t的策略，xi(t)∈Δk為玩家i∈{2，3，…，n}在時刻t的策略。給出一個充要條件，使從任意初始策略局勢開始的博弈動態(tài)過程均可收斂到最優(yōu)策略局勢。同時，設(shè)計(jì)一個自由控制序列來最大化長期運(yùn)行下偽玩家的平均收益:

(8)

其中，

首先，由算法1可得博弈的代數(shù)形式

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

(9)

定理1考慮多層網(wǎng)絡(luò)演化博弈的代數(shù)形式(9)，則有

(10)

換句話說，一旦每個玩家i∈{2，3，…，n}在時刻t都采用策略sk，令偽玩家也采用策略sk，那么對于玩家i∈{2，3，…，n}將會永遠(yuǎn)保持策略sk。

(11)

因此式(10)成立。證畢。

為了確保博弈的演化過程全局收斂到最優(yōu)策略局勢，需要保證最優(yōu)策略局勢在最優(yōu)控制序列下全局可達(dá)。對任意的t∈Z+，有

(13)

(14)

定理2如果條件式(13)成立，則在自由控制序列(14)下，博弈演化過程能夠全局收斂到最優(yōu)策略局勢，且在長期運(yùn)行下偽玩家能獲得最大平均收益

另外，本文的目的是引入偽玩家控制演化過程使博弈達(dá)到一個適當(dāng)?shù)木?。?dāng)一個偽玩家不能實(shí)現(xiàn)這個目標(biāo)時，可以考慮引入更多的偽玩家，使其達(dá)到穩(wěn)定的均衡狀態(tài)。

圖1 多層網(wǎng)絡(luò)示意圖(M=3)Fig.1 Multi-layer network diagram(M=3)

圖2 三層網(wǎng)Fig.2 Three-layer network

3 舉例分析

例1考慮多層網(wǎng)絡(luò)演化博弈:5個玩家，用N={1，2，3，4，5}表示，且N1={1}，N2={2，3}，N3={4，5}每個玩家都有相同的策略集S={s1，s2};5個玩家的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖如圖2所示;同層玩家之間的對稱支付矩陣A=[3 2;2 6]，不同層玩家之間的非對稱支付矩陣B=[2 1;0 5];演化規(guī)則為短視最優(yōu)響應(yīng)原則。

其中,Mpi是pi的結(jié)構(gòu)矩陣，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))。

根據(jù)式(5)，建立如下的博弈代數(shù)形式，計(jì)算每個玩家的收益函數(shù):

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]

因此，博弈的代數(shù)形式

x(t+1)=Lx(t)

(15)

其中，博弈轉(zhuǎn)移矩陣

第三步:考慮博弈的策略最優(yōu)問題。設(shè)第N1層中玩家1為偽玩家，通過算法1可得博弈的代數(shù)形式

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

(16)

根據(jù)一個簡單的計(jì)算

根據(jù)引理4，上述多層網(wǎng)絡(luò)的演化過程在自由控制序列

上述三層網(wǎng)絡(luò)演化博弈中，運(yùn)用半張量積方法將博弈過程抽象為動態(tài)方程，由博弈結(jié)構(gòu)矩陣可知，演化博弈最終以穩(wěn)定狀態(tài)呈現(xiàn)，沒有出現(xiàn)周期性狀態(tài)。在此基礎(chǔ)上考慮將玩家1作為偽玩家，設(shè)計(jì)了不同控制序列，使其達(dá)到平均收益最大的目的，進(jìn)一步驗(yàn)證了本文關(guān)于多層網(wǎng)絡(luò)演化博弈研究方法的有效性。因此該方法可用于更多層數(shù)的網(wǎng)絡(luò)演化博弈分析。

4 結(jié)束語

本文對博弈發(fā)生網(wǎng)絡(luò)上的節(jié)點(diǎn)進(jìn)行分層，假設(shè)同一層玩家之間的支付矩陣是對稱的，不同層玩家之間的支付矩陣是非對稱的。通過半張量積方法和短視最優(yōu)響應(yīng)原則，對該類多層網(wǎng)絡(luò)演化博弈的代數(shù)公式化與策略最優(yōu)問題進(jìn)行了研究。首先，將多層網(wǎng)絡(luò)演化博弈的動態(tài)行為轉(zhuǎn)化成代數(shù)公式的形式，建立了相應(yīng)的算法。其次，基于博弈代數(shù)公式，討論了多層網(wǎng)絡(luò)演化上的動態(tài)行為。最后，通過增加偽玩家到博弈中來研究策略最優(yōu)問題，目的是設(shè)計(jì)自由控制序列最大化偽玩家的平均收益，且控制序列不唯一，非常切合實(shí)際應(yīng)用。

[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]陸君安. 從單層網(wǎng)絡(luò)到多層網(wǎng)絡(luò)的——結(jié)構(gòu)、動力學(xué)和功能[J].統(tǒng)計(jì)物理和復(fù)雜系統(tǒng)研究前沿進(jìn)展專題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

O151.21

A

2016-12-21；

2017-06-19

國家自然科學(xué)基金(61203142), 河北省自然科學(xué)基金(F2014202206)

武利琴(1992-)，女，山西呂梁人，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)演化博弈。

徐勇(1971-)，男，山東蒙陰人，博士，教授，主要研究方向?yàn)榉蔷€性系統(tǒng)、復(fù)雜網(wǎng)絡(luò)。

(責(zé)任編輯耿金花)