一種基于半張量積的多層網絡演化博弈方法

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

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

一種基于半張量積的多層網絡演化博弈方法

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

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

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

多層網絡演化博弈；代數公式；策略最優(yōu)；半張量積

0 引言

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

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

1 矩陣的半張量積

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

定義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)網絡演化博弈的動態(tài)行為中長度為s環(huán)的數量用Cs表示，歸納如下:

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

2.1 多層網絡演化博弈模型

一個多層網絡正規(guī)有限博弈，由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}。本文采用短視最優(yōu)響應策略更新規(guī)則，即每個玩家預測它的對手將會重復上一次的策略，并在當前時刻選擇應對鄰居上一時刻策略的最優(yōu)策略?；谠摬呗愿略瓌t，在時刻t玩家i的策略xi(t)采取形式

(3)

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

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

(4)

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

2.2 博弈的代數公式化

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

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

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

最后，尋找使玩家i收益最大化的最優(yōu)響應策略，即找出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的性質來分析博弈動態(tài)過程。主要優(yōu)勢就是可通過代數公式研究博弈的動態(tài)行為，分析其演化趨勢。

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

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

(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)成立。證畢。

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

(13)

(14)

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

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

圖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];演化規(guī)則為短視最優(yōu)響應原則。

其中,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)

其中，博弈轉移矩陣

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

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

(16)

根據一個簡單的計算

根據引理4，上述多層網絡的演化過程在自由控制序列

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

4 結束語

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

[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].統(tǒng)計物理和復雜系統(tǒng)研究前沿進展專題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

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

武利琴(1992-)，女，山西呂梁人，碩士研究生，主要研究方向為網絡演化博弈。

徐勇(1971-)，男，山東蒙陰人，博士，教授，主要研究方向為非線性系統(tǒng)、復雜網絡。

(責任編輯耿金花)