社交網(wǎng)絡(luò)中多領(lǐng)導(dǎo)者觀點(diǎn)的博弈建模分析

閆曉雪，紀(jì)志堅(jiān)

(青島大學(xué) a.自動化學(xué)院;b.山東省工業(yè)控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島 266071)

0 引言

隨著信息技術(shù)特別是人工智能、互聯(lián)網(wǎng)、大數(shù)據(jù)、云計(jì)算和移動通訊等的快速發(fā)展，“信息—物理—人類(CPH)”三個(gè)系統(tǒng)之間的耦合越來越密切，為人機(jī)融合網(wǎng)絡(luò)系統(tǒng)中的調(diào)控帶來一系列新挑戰(zhàn)。社交網(wǎng)絡(luò)是多智能體系統(tǒng)[1]和復(fù)雜網(wǎng)絡(luò)系統(tǒng)[2]理論中一個(gè)重要的研究方向。通過對觀點(diǎn)動力學(xué)模型[3-4]的研究闡述了人類行為，進(jìn)而預(yù)測一個(gè)社交網(wǎng)絡(luò)中觀點(diǎn)的演變，同時(shí)闡明了個(gè)人的動態(tài)如何塑造復(fù)雜的團(tuán)體行為。因此，觀點(diǎn)動態(tài)和決策這兩個(gè)復(fù)雜的社會過程是深刻交織在一起的，分析博弈關(guān)系能有效揭示生物種群間和生物體間的行為規(guī)律以及人類相互作用的行為規(guī)律。近年來，人們把工作聚焦在多主體博弈行為的研究上，將博弈控制作為社交網(wǎng)絡(luò)研究的一個(gè)切入點(diǎn)。博弈控制系統(tǒng)[5]將博弈論與控制論結(jié)合為一個(gè)具有層級結(jié)構(gòu)的調(diào)控系統(tǒng)，上層為宏觀調(diào)控變量，下層為相互關(guān)聯(lián)且功能不盡相同的多個(gè)主體?？刂普搫?chuàng)始人諾伯特-維納在1948年出版的奠基性著作《控制論》[6]中論述過博弈過程中學(xué)習(xí)與適應(yīng)的重要性。從自適應(yīng)控制理論發(fā)展的半個(gè)多世紀(jì)來看，它為自適應(yīng)博弈理論的研究提供了基礎(chǔ)，近年來相關(guān)研究也不斷展開[7-10]。此外，納什均衡概念[11]為一般博弈系統(tǒng)的研究提供了重要工具。多主體博弈控制系統(tǒng)是多個(gè)智能體組成的集合，它的目標(biāo)是將大而復(fù)雜的系統(tǒng)轉(zhuǎn)化成若干個(gè)小的且彼此相互通信協(xié)調(diào)、易于管理的系統(tǒng)。本文利用動態(tài)規(guī)劃最優(yōu)性原理，推導(dǎo)出性能泛函的極小值滿足的條件—哈密爾頓-雅克比-貝爾曼(HJB)方程[12-14]，通過求解該方程得到最優(yōu)控制。主要工作為三部分：1)對社交網(wǎng)絡(luò)群體提出了一種新的劃分方式，根據(jù)智能體在社交網(wǎng)絡(luò)中擔(dān)任不同的角色進(jìn)行劃分，再通過模擬評估每個(gè)智能體對問題討論的綜合影響力更新智能體的社會影響力；2)簡要回顧經(jīng)典的DeGroot模型和Friedkin-Johnsen模型，在此基礎(chǔ)上加入多領(lǐng)導(dǎo)者博弈控制策略，提出了一個(gè)新的觀點(diǎn)動力學(xué)模型；3)為使問題獲得最優(yōu)的解決方案，建立了耦合的HJB方程，通過求解使得新建的動力學(xué)模型獲得最優(yōu)控制策略，最終收斂后達(dá)到預(yù)設(shè)目標(biāo)。

1 預(yù)備知識

1.1 圖論

1.2 DeGroot模型和Friedkin-Johnsen模型

經(jīng)典的DeGroot模型描述了n個(gè)智能體觀點(diǎn)形成的過程，每個(gè)智能體的意見代表了他/她對某一問題的認(rèn)知取向，由xi=[x1,x2,…,xn]T表示，交互的社交網(wǎng)絡(luò)用非負(fù)影響矩陣W表示。動力學(xué)系統(tǒng)模型為

(1)

其中，W=(wij)∈Rn×n，wij>0表示vj對vi觀點(diǎn)的影響程度；wij=0表示vi沒有從vj獲得關(guān)于觀點(diǎn)的信息。

引理1(本原矩陣[15]) 圖G(W)是強(qiáng)連通非周期的,當(dāng)且僅當(dāng)W是本原矩陣。

定義1(收斂性[3]) 若模型(1)滿足對任意初始觀念x(0)，存在極限

(2)

則模型(1)是收斂的。即如果對于任意初始條件x(0)有x1(∞)=…=xn(∞)，則這個(gè)模型達(dá)成共識。

對于所有初始觀念x(0)，如果系統(tǒng)(2)收斂到x(∞)=α1n,α∈R，則意見最終達(dá)成一致。在文獻(xiàn)[16]中總結(jié)了模型(1)的收斂條件。

DeGroot模型的一個(gè)推廣模型是在文獻(xiàn)[17-18]中提出的Friedkin-Johnsen(F-J)模型。表示為

xi(k+1)=ΛWxi(k)+(In-Λ)xi(0),i=1,2,…,n

(3)

其中，對角線矩陣Λ=diag(ξ),ξ=(ξ1,ξ2,…,ξn)，ξi∈[0,1]代表智能體i對社交網(wǎng)絡(luò)影響的敏感度，當(dāng)Λ=In時(shí)，F(xiàn)-J模型將變成DeGroot模型。對于強(qiáng)連通網(wǎng)絡(luò)，有以下收斂結(jié)構(gòu)。

引理3[19]假設(shè)圖G(W)是強(qiáng)連通的，并對?i,j∈{1,…,n}有ξi,ξj<1，那么ρ(In-ΛW)<1且式(3)收斂至

(4)

矩陣V(In-ΛW)-1(In-Λ)是行隨機(jī)矩陣。因此，x*的觀點(diǎn)為x(0)的凸組合。

2 動態(tài)社交網(wǎng)絡(luò)模型

2.1 模型的建立

根據(jù)術(shù)業(yè)有專攻的特點(diǎn)，讓擅長者擔(dān)任領(lǐng)導(dǎo)者去做主導(dǎo)工作，其他個(gè)體作為跟隨者提供改進(jìn)和完善工作，這樣設(shè)計(jì)符合實(shí)際社交網(wǎng)絡(luò)的設(shè)定。在F-J模型中加入博弈策略，并設(shè)計(jì)成以多個(gè)領(lǐng)導(dǎo)者為主體的博弈控制系統(tǒng)，使其觀點(diǎn)形成的解決方案能更好地解決問題。系統(tǒng)動力學(xué)模型表述如式(5)：

(5)

其中,W∈Rn×n,B∈Rn×m,C∈Rm×n,Xi∈Rn表示智能體i的觀點(diǎn)向量，γ=diag(β),βi∈[0,1]表示智能體i對社交網(wǎng)絡(luò)影響的敏感度，Ui∈Rm是領(lǐng)導(dǎo)者i的控制輸入策略，Υi∈Rm將領(lǐng)導(dǎo)者的觀點(diǎn)不斷提取出來。

為便于分析，借鑒Stackelberg-Nash均衡博弈的特點(diǎn)，預(yù)先確定理想目標(biāo)Zi∈Rm定義誤差矢量δi為

δi=Zi-Yi

(6)

(7)

為保證定義2多領(lǐng)導(dǎo)者博弈控制可獲得問題的最佳解決方案，本文建立多個(gè)領(lǐng)導(dǎo)者為主體對智能體進(jìn)行新的劃分，將大而復(fù)雜的系統(tǒng)轉(zhuǎn)化成若干個(gè)具有強(qiáng)連通結(jié)構(gòu)的觀點(diǎn)群體系統(tǒng)。

2.2 智能體的劃分

由圖1來模擬一個(gè)有限個(gè)個(gè)體的實(shí)際社交網(wǎng)絡(luò)交互情況，每個(gè)智能體根據(jù)觀點(diǎn)和相互之間的拓?fù)浣Y(jié)構(gòu)圖來確定其角色。藍(lán)色、綠色和灰色分別表示領(lǐng)導(dǎo)者、跟隨者和外圍跟隨者。此外，系統(tǒng)模擬智能體的觀點(diǎn)被多個(gè)領(lǐng)導(dǎo)者采納，經(jīng)驗(yàn)證這不會產(chǎn)生沖突也不會改變觀點(diǎn)的性質(zhì)，僅使結(jié)構(gòu)圖交互變得更復(fù)雜，解決辦法是被幾個(gè)領(lǐng)導(dǎo)者采納就將該智能體看作幾個(gè)節(jié)點(diǎn)，進(jìn)行拆分。

圖1 由11個(gè)智能體組成的交互社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

為便于分析，圖2就是對拓?fù)鋱D進(jìn)行等價(jià)拆分,化簡為若干個(gè)以每個(gè)領(lǐng)導(dǎo)者和與之相關(guān)聯(lián)的跟隨者形成的強(qiáng)連通圖，當(dāng)不同的領(lǐng)導(dǎo)者采納了同一個(gè)跟隨者的觀點(diǎn)時(shí)，該跟隨者將參與到不同領(lǐng)導(dǎo)者小組的討論中。

圖2 領(lǐng)導(dǎo)者-跟隨者影響網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

由圖1寫出加有外圍跟隨者的拓?fù)浣Y(jié)構(gòu)圖的影響矩陣A為

當(dāng)結(jié)構(gòu)不足寫出方陣時(shí)矩陣右側(cè)補(bǔ)零，可得含外圍跟隨者的影響矩陣A的緊湊形式。

(8)

引理4[4]假設(shè)領(lǐng)導(dǎo)者—跟隨者形成的矩陣W滿足ξi>0且G(W)中不包含完全由非固執(zhí)節(jié)點(diǎn)組成的獨(dú)立強(qiáng)連通分支，則F-J模型在問題上能達(dá)到一致,當(dāng)且僅當(dāng)圖G(W)中存在一個(gè)部分固執(zhí)節(jié)點(diǎn)，該節(jié)點(diǎn)具有到其他所有部分固執(zhí)節(jié)點(diǎn)的有向路徑。

根據(jù)引理3和4可得推論1和定理1。

定理1當(dāng)影響矩陣G(W)具有公式(8)的結(jié)構(gòu)時(shí)，它的主導(dǎo)左特征向量的取值只與塊矩陣Wlif有關(guān)，與塊矩陣Wliff無關(guān)。

證明：將矩陣(8)的緊湊形式展開為矩陣(9)構(gòu)成下三角結(jié)構(gòu)的分塊矩陣，其中s為領(lǐng)導(dǎo)者的個(gè)數(shù)。

(9)

由分塊三角矩陣的性質(zhì)可得，分塊三角矩陣的特征值等于對角線上矩陣的特征值。假設(shè)A的主導(dǎo)左特征向量與塊矩陣W有關(guān)。下面將主對角分塊矩陣化簡為W=diag([Wl1f…Wlsf])，Wlif存在一個(gè)特征值為1且其左特征向量為主導(dǎo)左特征向量，即滿足ξiWlif=ξi

(10)

(11)

因此，每個(gè)Wlif塊矩陣形成,通過線性組合將式(10)推到式(11)。假設(shè)成立。

假設(shè)A的主導(dǎo)左特征向量的取值與塊矩陣Wliff有關(guān),且保證每一個(gè)塊矩陣Wliff是方陣，那么可得

因此，當(dāng)塊矩陣Wliff是方陣時(shí)，系統(tǒng)的左特征向量ξliff為零。故A的主導(dǎo)左特征向量的取值與塊矩陣Wliff無關(guān)，且每一個(gè)塊矩陣Wliff不必須是方陣，符合實(shí)際的社交網(wǎng)絡(luò)。綜上所述，定理1成立。

由引理1可得對于一個(gè)具有強(qiáng)連通結(jié)構(gòu)的行隨機(jī)矩陣，存在一個(gè)單特征值為1且與特征值1相關(guān)的特征向量是矩陣的主導(dǎo)左右特征向量。由圖1和矩陣A可以看出外圍跟隨者對產(chǎn)生觀點(diǎn)的智能體進(jìn)行了評估，可得如果社交網(wǎng)絡(luò)系統(tǒng)出現(xiàn)外圍跟隨者，加零矩陣補(bǔ)齊為方陣形成行列相等的行隨機(jī)矩陣(8)。又因?yàn)閮H使用左特征向量不能完全公正地表達(dá)出該社交網(wǎng)絡(luò)中智能體的相對貢獻(xiàn)。由此引出定義3。

定義3在一個(gè)包含外圍跟隨者的社交網(wǎng)絡(luò)中，將包含領(lǐng)導(dǎo)者—跟隨者的加權(quán)有向圖G(Wlif)的左特征向量ξi和包含外圍跟隨者的加權(quán)有向圖G(Wliff)進(jìn)行凸組合，表達(dá)整個(gè)社交網(wǎng)絡(luò)中產(chǎn)生觀點(diǎn)的智能體i對社交網(wǎng)絡(luò)影響的敏感度，即對角陣γ

(12)

其中，γ=diag(β),βi∈[0,1]，i表示產(chǎn)生觀點(diǎn)的智能體，m為每個(gè)強(qiáng)分支中外圍跟隨者的數(shù)目。

2.3 問題的最優(yōu)同步解決方案

這一部分的研究目的是從動態(tài)規(guī)劃和最優(yōu)控制[20]中推導(dǎo)出最優(yōu)控制策略。

通過系統(tǒng)(5)建立耦合形式的HJB方程，求得定理2中的最佳領(lǐng)導(dǎo)者響應(yīng)策略。根據(jù)極小值原理可寫出哈密爾頓函數(shù)：

(13)

由于Q2是正定矩陣，得

(14)

(15)

終端條件

(16)

聯(lián)立公式(5)和公式(15)可得方程(17)：

(17)

λ=PXi-Γ

(18)

其中，P和Γ是λ關(guān)于Xi的變換矩陣，P是n×n維矩陣，Γ是n×1維矩陣。

(19)

Γ是下列一階微分方程的解，且必須滿足式(16)的終端條件可得：

(20)

解出P和Γ，將式(18)代入式(14)可求得：

(21)

基于Friedkin-Johnsen模型漸進(jìn)穩(wěn)定的條件，矩陣W是行隨機(jī)矩陣，對角陣γ滿足0<γ

(22)

3 仿真結(jié)果

將第2節(jié)圖1的交互社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖進(jìn)一步完善，如圖3所示。

圖3 社交網(wǎng)絡(luò)由外部控制器(紅色節(jié)點(diǎn))驅(qū)動領(lǐng)導(dǎo)者1、6的拓?fù)浣Y(jié)構(gòu)圖

性能泛函中的權(quán)重矩陣Q0=diag{2.6;2.6}，Q1=diag{0.01;0.01}，Q2=diag{2;2}。所有產(chǎn)生觀點(diǎn)的智能體初始觀點(diǎn)矢量在0到10之間，隨機(jī)選擇Xi(0)=[7;5;4;5.5;5.5;7.5;4.2]T。

當(dāng)預(yù)設(shè)的理想目標(biāo)為同一目標(biāo)Zi=[8;8]時(shí)，系統(tǒng)觀點(diǎn)狀態(tài)Xi的收斂圖，如圖4所示；領(lǐng)導(dǎo)者控制策略Ui,i=1,6的變化曲線，如圖5 所示；系統(tǒng)誤差δi變化曲線，如圖6所示。在圖4中還可以看出跟隨者4、5為同一節(jié)點(diǎn)，當(dāng)被不同的領(lǐng)導(dǎo)者采納意見時(shí)，它們的觀點(diǎn)在融入過程中被采納了不同的部分，使得每一個(gè)以領(lǐng)導(dǎo)者為主體的觀點(diǎn)群體最終都獲得了理想目標(biāo)的最優(yōu)解決方案。

圖4 在同一目標(biāo)下，系統(tǒng)觀點(diǎn)狀態(tài)的收斂圖

圖5 在同一目標(biāo)下，領(lǐng)導(dǎo)者1,6控制策略的變化曲線

圖6 在同一目標(biāo)下，系統(tǒng)誤差變化曲線

當(dāng)預(yù)設(shè)的理想目標(biāo)為不同目標(biāo)Zi=[7;8.5]時(shí)，其他保持不變的情況下可得系統(tǒng)觀點(diǎn)狀態(tài)Xi的收斂圖，如圖7 所示；領(lǐng)導(dǎo)者控制策略Ui,i=1,6的變化曲線，如圖8所示；系統(tǒng)誤差δi變化曲線，如圖9 所示。圖7中還可看出領(lǐng)導(dǎo)者1的最初觀點(diǎn)和理想目標(biāo)一樣，但在結(jié)合跟隨者2、3、4的觀點(diǎn)進(jìn)行再優(yōu)化時(shí)產(chǎn)生了區(qū)分，最終分別為最佳解決方案提供了可采取的觀點(diǎn)。

圖7 在不同目標(biāo)下，系統(tǒng)觀點(diǎn)狀態(tài)的收斂圖

圖8 在不同目標(biāo)下，領(lǐng)導(dǎo)者1,6控制策略的變化曲線

圖9 在不同目標(biāo)下，系統(tǒng)誤差變化曲線

4 結(jié)語

本文通過多領(lǐng)導(dǎo)者博弈控制考慮了社會主體協(xié)作的影響力，對此進(jìn)行建模和仿真使其更有效地分析社會網(wǎng)絡(luò)中從局部交互到全局協(xié)調(diào)的情況。本文還對觀點(diǎn)的權(quán)重進(jìn)行分析，當(dāng)同一個(gè)觀點(diǎn)被不同的網(wǎng)絡(luò)群體中的領(lǐng)導(dǎo)者采納的時(shí)候會將觀點(diǎn)劃分到多個(gè)群體中，這種對智能體劃分的方式將為社交網(wǎng)絡(luò)打開一個(gè)新的視角，可以建立更加復(fù)雜的交互社交網(wǎng)絡(luò)。最后還實(shí)現(xiàn)了當(dāng)目標(biāo)控制器對不同的領(lǐng)導(dǎo)者有不同的標(biāo)準(zhǔn)時(shí)，系統(tǒng)也可以最終達(dá)到理想目標(biāo)獲得相應(yīng)的解決方案。將來會進(jìn)一步研究同一個(gè)智能體的觀點(diǎn)在不是非正即負(fù)的情況下如何更加細(xì)化拆分獲取信息，每個(gè)智能體在本次問題中的影響力在下一個(gè)問題討論時(shí)又會產(chǎn)生多大的影響，并建立反饋機(jī)制。