基于雙矩陣博弈的群組聚合模型

李 娜,李佳美,馬婧瑛

(寧夏大學 數學統計學院,寧夏 銀川 750021)

對群體智能的研究起源于人們對生物界群居性生物群體的觀察和研究[1].人們發現弱小個體總是通過協同工作完成捕食、遷徙和躲避天敵等工作,如魚類群游、蟻群的聚集、獸群的圍捕等.這些現象的共同特征是具有有限能力的簡單個體通過信息交換和協同合作最終在集體層面上呈現出高效、強大和復雜的群體智能,從而完成復雜的任務.群體智能行為由于其在社會[2]、經濟[3-4]、生物學[5]和工程學[6-8]等領域的廣泛應用而得到越來越多學者的關注.

智能體群組通過協同與博弈,呈現出的群體智能行為包括一致性[5]、包圍[9]、領航者涌現[10]、群體的聚合[11-13]等.聚合是微觀層面常見的自然和社會現象,是指微小單元通過交互作用聯結成一個更大的聯合體的過程,它是一類常見的群體智能行為[11].聚合在自然界和社會中非常普遍,它是指N個粒子在一個連通圖上隨機游走并通過兩兩聚合,最終組成一個聯合體的過程[12-13].文獻[14]研究了社交網絡上用戶觀點的聚合問題,作者利用非光滑分析理論證明了,只要用戶的初始觀點差異在一定范圍內,觀點最終會聚合為一個觀點.然而,當個體具有自主意識,他們的交互與協調往往是一個復雜的過程.因此,文獻[15]將個體間的交互建模為二人雙矩陣博弈,并研究了N個個體的聚合問題.受上述參考文獻的啟發,本文研究存在不完全信息個體的情況下群組的聚合問題.

1 預備知識

1.1 雙矩陣博弈

則策略對(ri*,cj*)就稱為二人矩陣博弈(A,B)的純策略納什均衡解.而(ai*j*,bi*j*)稱為純策略納什均衡.

在很多情況下,純策略納什均衡是不存在的.令Γ1={r1,r2}和Γ2={c1,c2}表示參與者P1和P2的策略空間,令α=[α1,α2]T是一個非負向量且滿足α1+α2=1,其中αi表示參與者P1選擇策略ri的概率.顯然,α是策略空間Γ1的概率分布,即α是參與者P1的混合策略.同理,β=[β1,β2]T(β1+β2=1)被稱為參與者P2的混合策略.(α,β)被稱為二人雙矩陣博弈(A,B)的一個混合策略.顯然,在混合策略(α,β)下,參與者P1的效用的期望值為U1(α,β)=αTAβ.因此,將U1(α,β)稱為參與者P1在混合策略(α,β)下的效用.類似的,稱U2(α,β)=αTBβ是參與者P2在混合策略(α,β)下的效用.二人矩陣博弈(A,B)的混合策略納什均衡可定義如下.

定義1[16]雙矩陣博弈(A,B)的一個混合策略對(α,β):如果對任意混合策略(α,β)滿足

(α*)TAβ*≥αTAβ*,

(α*)TBβ*≥(α*)TBβ.

則稱(α*,β*)為博弈(A,B)的混合策略納什均衡.

1.2 問題提出

對于一個由N個個體1,2,…,N組成的群組IN,設個體i在時刻k的狀態記為xi(k)(k=0,1,….),xi(k)∈Rm.

假設1個體在0時刻,具有各不相同的初始狀態,即xi(0)≠xj(0)對任意i≠j成立.

對于群組IN,分別給出兩個個體的聚合和群組聚合的定義.

定義2(兩個個體的聚合)對于群組IN中的個體i和j(i

根據定義2,當兩個個體在某時刻狀態相等時,它們將聚合為一個個體,此時群組中的個體數量減少1個.令nk表示k時刻群組IN中個體數量.容易得到,當nk=1時,該群組完成聚合.

定義3(群組聚合)對于群組IN,如果存在一個時刻K0,使得從K0時刻起,nk=1,(k≥K0)即個體1,2,…,N聚合為一個聯合體,則稱該群組完成聚合,并稱K0為聚合時間.

為了使群組完成聚合,文獻[15]將個體交互過程建模為如下的雙矩陣博弈.

定義4[15]二人博弈G的參與者為兩個個體,記為i和j.i和j博弈前的狀態分別為xi(k)和xj(k),i和j通過博弈,決定其狀態更新策略,更新后的狀態分別為xi(k+1)和xj(k+1).每個參與者有兩個備選策略,分別為合作(C)和背叛(D).如果參與者選擇合作(C),則他將會改變自己的狀態以完成聚合.如果參與者選擇背叛(D),則無論是否能完成聚合,他都不會改變自己的狀態.假設兩個參與者獨立地、同時做出決策.則參與者的策略對有下列四種.

(i)(C,C),i,j都選擇合作,改變其狀態,則更新規則為

(ii)(C,D),i選擇合作,改變其狀態,j選擇背叛,不改變其狀態,則更新規則為

xi(k+1)=xj(k+1)=xj(k).

(2)

(iii)(D,C),i選擇背叛,不改變其狀態,j選擇合作,改變其狀態,則更新規則為

xi(k+1)=xj(k+1)=xi(k).

(3)

(iv)(D,D),i,j都選擇背叛,保持狀態不變,則無法聚合,更新規則為

對于參與者i和j來說,博弈的效用可分解為如下兩個部分.

(i)如果xi(k+1)=xj(k+1),i和j完成聚合,則得到獎勵R.

表1 博弈G的策略對、狀態更新規則和效用

由于f(·)是嚴格單調遞增函數,如果存在ξ0>0,使得f(ξ0)=R,則當ξ(k)>ξ0時,f(ξ(k))>R.從表1不難得到,當f(ξ(k))>R時,博弈G具有唯一的純納什均衡策略對(D,D), 即兩個參與者都會選擇策略D.此時,參與者保持原有狀態不變,從而無法完成兩個個體的聚合.當f(ξ(k))

定理1[15]如果f(ξ(k))

和

選擇策略C和策略D.參與者將以概率1-PD2聚合為一個新個體.

假設2f(ξmax(0))

文獻[15]中參與者選擇方式并沒有考慮個體被選擇的概率分布模型.借鑒文獻[16]的Gossip算法中交互對象選擇模型,將文獻[15]中的參與者選擇過程改進如下.

步驟2參與者i從群組IN中選擇博弈對象j;

步驟3個體i和個體j進行博弈G,若發生聚合,則聚合為一個個體.若沒有發生聚合,則聚合失敗.

此外,文獻[15]假設所有的個體都能夠獲得有關博弈G的全部信息,即假設個體為完全信息個體.然而現實中,個體并不一定能夠獲得全部信息.因此,考慮將群組中的個體按照是否能夠獲得博弈G的全部信息分為完全信息個體和不完全信息個體.因此,分別研究群組中包含不完全信息個體和不包含不完全信息個體的聚合問題.

2 完全信息個體情況下的聚合問題

令pk表示k時刻博弈G的兩個參與者聚合為一個個體的概率,即

pk=P(xi(k+1)=xj(k+1)).

由定理1可知,如果參與者可以獲得博弈所需的全部信息,即對手的狀態變量、博弈的效用等,那么參與者將會依據納什均衡做出決策,即當f(ξ(k))

完全信息的參與者會根據博弈規則做出使其效用最大化的決策.因此,在k時刻,當參與者i被選定后,它將依據期望效用最大化原則選擇對手j.

定理2如果所有個體是完全信息個體,當i被首先選中作為參與者,i會選擇與其距離最近的個體為對手,即

證明由假設2可知參與者i和對手會根據(5)式和(6)式確定其混合策略,從而個體i的期望效用為ξ(k)的函數

由假設2知,R-f(ξ(k))>0.容易得到,

定理3[15]如果假設2成立,且存在常數0

定理4如果假設2成立,則群組IN將以概率1聚合為一個個體,并且群組IN的聚合狀態xc一定落入群組IN的初始狀態圍成的凸包內,即

P(xc∈conv{x1(0),x2(0),…,xN(0)})=1.

證明當假設2成立時,存在常數0

xi(k+1)=axi(k)+(1-a)xj(k),xj(k+1)=bxi(k)+(1-b)xj(k),

其中

因此,無論博弈雙方如何選擇策略,都有a∈[0,1],b∈[0,1].從而

xi(k+1)∈Sk,xj(k+1)∈Sk,

(7)

其中

Sk=conv{x1(k),x2(k),…,xN(k)}.

而在k時刻沒有參與博弈的其他個體i′∈IN{i,j}在下一時刻的狀態則滿足

xi′(k+1)=xi′(k)∈Sk.

(8)

因此,由(7)式和(8)式可得

Sk+1=conv{x1(k+1),x2(k+1),…,xN(k+1)}?Sk.

P(xc∈S0)=1.

證畢.

3 不完全信息個體情況下的聚合問題

考慮群組IN中包含M(M≤N)個不完全信息個體的聚合問題.不完全信息個體是指無法獲取到其他個體的狀態信息以及博弈中的參數R和函數f(·)的有關信息的個體.假設這類不完全信息個體以下面的方式選擇對手和策略.

假設4一個不完全信息個體參與博弈G時,它選擇策略C或D的概率相等.

此時,可以得到如下結論.

當一個完全信息個體i在k時刻被選為博弈的第一參與者時,它會按照下列方式選擇對手.

定理6如果假設2成立,則存在M個不完全信息個體的群組IN聚合為一個個體的概率為1.并且,完成聚合后,群組的聚合狀態xc落入由群組IN的初始狀態圍成的凸包內的概率亦為1.

證明從定理5可知,在存在不完全信息個體的情況下,博弈G可能出現下面三種情況.

(i)兩個完全信息個體參與博弈.此時按照定理1,兩個個體均以(5)式和(6)式選擇策略C或D.根據定理3,存在兩個常數0

4 群組仿真實驗

對一個具有20個個體的群組的演化過程進行仿真實驗.這些個體的狀態為R2上的點,個體i在時刻k的坐標用向量[xi(k),yi(k)]T表示,則所有個體的初始狀態可用矩陣

例1圖1展示了由4個完全信息個體和16個不完全信息個體組成的群組的聚合過程,其中R=8.用藍色的點表示完全信息的個體,紅色的點表示非完全信息的個體,P1和P2分別表示博弈的第一個和第二個參與者.觀察圖1可發現,在38次博弈中,有15次博弈雙方均選擇策略D,這20次博弈中,博弈的參與者沒有改變狀態.進一步觀察會發現,經過38次博弈,群組聚合為兩個個體.此時,兩個個體的距離ξ(38)=77.398,相應的f(ξ(k))=8.798>R.因此,當k≥38時,每一次博弈的策略對都是(D,D),也就是說參與者在該次博弈中無法聚合為一個個體.這一結論與本文理論結果是相符合的。

圖1 14個完全信息個體和16個不完全信息個體的聚合過程

例2圖2展示了由4個完全信息個體和16個不完全信息個體組成的群組在不同的參數R下的仿真分析,其中R∈[7,15].對每一個R,重復進行20000次仿真實驗,圖2(a)展示了群組停止聚合時,每一種可能情況在20000次仿真中所占的比例與R的關系.圖2(b)展示了群組平均聚合時間與R的關系.

觀察圖2(a)可知,當R<10.37時,群組最終將聚合為1個、2個或3個個體,并且隨著R的增加,群組聚合為1個個體的比例逐漸增加;當R>10.37時,聚合為1個個體的頻率為100%,即20000次仿真實驗的結果全部為群組聚合為一個個體.這一現象與本文所得到的理論結果定理6是相符的.

觀察圖2(b)可知,隨著R的增加,群組完成聚合所需的平均時間逐漸減小,并且隨著R的增大,完成聚合的平均時間趨向于20秒.這一現象與本文所得到的理論結果定理6亦是相符的.

為了進一步驗證定理6的正確性,令R=12,重復進行20000次仿真,并將最終聚合狀態的分布情況展示在圖3中.觀察圖3可以得到,所有的最終狀態都在初始狀態圍成的多邊形內,這一結果與定理6的結論也是相符的.

圖2 4個完全信息個體和16個不完全信息個體情況下,最終聚合個體數和聚合時間與R的關系

圖3 4個不完全信息個體和16個完全信息個體的群組聚合狀態分布圖(R=12)

例3令R=9,群組中完全信息個體的個數分別為M個(M=0,1,…,20),對每個M的情況重復仿真20000次,圖4(a)展示了群組最終聚合的個體數在20000次仿真中所占的比例,圖4(b)則展示了隨著完全信息個體數量的變化,群組平均聚合時間的變化情況.

觀察圖4(b)可知,當完全信息個體的數量為0或1時,群組完成聚合的博弈次數是25次左右,并且隨著完全信息個體數量的增加,群組完成聚合的平均時間逐漸增加.隨著不完全信息個體數量的增加,群組完成聚合的平均時間逐漸減少.

(a) 集合個體數量的頻率與完全信息個體數的關系 (b) 平均聚合時間與完全信息個體數的關系

5 總結

研究了有限個體組成的群組的聚合過程.考慮并將個體間的聚合過程建模為二人雙矩陣博弈,并進一步考慮了群組中的個體均為完全信息個體的情況下的聚合問題和群組中存在不完全信息個體的情況下的聚合問題.證明了無論群組中是否存在不完全信息個體,當個體間最大初始距離小于一個給定的值時,群組完成聚合的概率為1,并且完成聚合后的狀態一定位于初始狀態張成的凸包內.最后,若干仿真算例驗證了本文所得到的理論結果的正確性,并進一步發現群體的聚合時間將隨著不完全信息個體數和R的增大而減少.未來的研究將集中在進一步分析聚合時間與不完全信息個體數量之間的定量關系.