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

李 娜,李佳美,馬婧瑛

(寧夏大學(xué) 數(shù)學(xué)統(tǒng)計(jì)學(xué)院,寧夏 銀川 750021)

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

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

1 預(yù)備知識(shí)

1.1 雙矩陣博弈

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

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

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

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

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

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

1.2 問題提出

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

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

對(duì)于群組IN,分別給出兩個(gè)個(gè)體的聚合和群組聚合的定義.

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

根據(jù)定義2,當(dāng)兩個(gè)個(gè)體在某時(shí)刻狀態(tài)相等時(shí),它們將聚合為一個(gè)個(gè)體,此時(shí)群組中的個(gè)體數(shù)量減少1個(gè).令nk表示k時(shí)刻群組IN中個(gè)體數(shù)量.容易得到,當(dāng)nk=1時(shí),該群組完成聚合.

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

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

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

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

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

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

(2)

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

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

(3)

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

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

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

表1 博弈G的策略對(duì)、狀態(tài)更新規(guī)則和效用

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

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

和

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

假設(shè)2f(ξmax(0))

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

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

步驟3個(gè)體i和個(gè)體j進(jìn)行博弈G,若發(fā)生聚合,則聚合為一個(gè)個(gè)體.若沒有發(fā)生聚合,則聚合失敗.

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

2 完全信息個(gè)體情況下的聚合問題

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

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

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

完全信息的參與者會(huì)根據(jù)博弈規(guī)則做出使其效用最大化的決策.因此,在k時(shí)刻,當(dāng)參與者i被選定后,它將依據(jù)期望效用最大化原則選擇對(duì)手j.

定理2如果所有個(gè)體是完全信息個(gè)體,當(dāng)i被首先選中作為參與者,i會(huì)選擇與其距離最近的個(gè)體為對(duì)手,即

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

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

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

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

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

證明當(dāng)假設(shè)2成立時(shí),存在常數(shù)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時(shí)刻沒有參與博弈的其他個(gè)體i′∈IN{i,j}在下一時(shí)刻的狀態(tài)則滿足

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 不完全信息個(gè)體情況下的聚合問題

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

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

此時(shí),可以得到如下結(jié)論.

當(dāng)一個(gè)完全信息個(gè)體i在k時(shí)刻被選為博弈的第一參與者時(shí),它會(huì)按照下列方式選擇對(duì)手.

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

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

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

4 群組仿真實(shí)驗(yàn)

對(duì)一個(gè)具有20個(gè)個(gè)體的群組的演化過程進(jìn)行仿真實(shí)驗(yàn).這些個(gè)體的狀態(tài)為R2上的點(diǎn),個(gè)體i在時(shí)刻k的坐標(biāo)用向量[xi(k),yi(k)]T表示,則所有個(gè)體的初始狀態(tài)可用矩陣

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

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

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

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

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

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

圖2 4個(gè)完全信息個(gè)體和16個(gè)不完全信息個(gè)體情況下,最終聚合個(gè)體數(shù)和聚合時(shí)間與R的關(guān)系

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

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

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

(a) 集合個(gè)體數(shù)量的頻率與完全信息個(gè)體數(shù)的關(guān)系 (b) 平均聚合時(shí)間與完全信息個(gè)體數(shù)的關(guān)系

5 總結(jié)

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