具有異質(zhì)增益因子的超圖上的演化公共品博弈*

陳蔚穎 潘建臣 韓文臣 黃昌巍3)?

1) (廣西大學(xué)計算機與電子信息學(xué)院,南寧 530004)

2) (四川師范大學(xué)物理與電子工程學(xué)院,成都 610101)

3) (廣西大學(xué),廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室,南寧 530004)

1 引言

利他(合作)行為廣泛存在于自然界和人類社會[1].然而,根據(jù)達爾文自然選擇理論,理性個體在面臨個人利益和群體利益的兩難選擇沖突困境時,個體將會選擇能夠最大化自身利益的利己(背叛)行為.社會困境中自私個體合作行為的自發(fā)涌現(xiàn)和維持吸引了物理、數(shù)學(xué)、生物和信息等領(lǐng)域研究學(xué)者的廣泛關(guān)注,博弈理論被發(fā)現(xiàn)能夠為解釋群體中合作行為的涌現(xiàn)和維持背后的機制提供強有力的理論框架.在經(jīng)典演化博弈理論中,通常假設(shè)群體中的個體以相同的概率進行接觸并發(fā)生相互作用.通過平均場理論分析發(fā)現(xiàn),囚徒困境博弈情境下合作行為無法在充分混合群體中存在[2].然而,Nowak 和May[3]考慮具有空間結(jié)構(gòu)的網(wǎng)絡(luò)上進行演化博弈的開創(chuàng)性研究工作表明,群體中的合作者能夠自發(fā)地形成緊湊的合作團簇,從而抵御背叛者的入侵,合作行為通過網(wǎng)絡(luò)互惠機制得到了促進.此后,伴隨著網(wǎng)絡(luò)科學(xué)的蓬勃發(fā)展,復(fù)雜網(wǎng)絡(luò)上的演化博弈吸引了國內(nèi)外學(xué)者的廣泛關(guān)注和研究[4-6].

作為經(jīng)典多人博弈模型,公共品博弈是刻畫多人囚徒困境博弈最常用的模型.目前,學(xué)者們對復(fù)雜網(wǎng)絡(luò)上的演化公共品博弈進行了大量的研究.一方面,已有很多研究工作關(guān)注于復(fù)雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)對于空間公共品博弈中合作演化的影響.例如,Santos 等[7]探究了BA 無標度網(wǎng)絡(luò)上的演化公共品博弈,對比規(guī)則網(wǎng)絡(luò)上公共品博弈的合作演化結(jié)果,網(wǎng)絡(luò)異質(zhì)性進一步增強了公共品博弈中合作行為的涌現(xiàn);Rong 和Wu[8]研究了無標度網(wǎng)絡(luò)上節(jié)點度的相關(guān)性對公共品博弈中合作演化的影響;Battiston 等[9]討論了多層網(wǎng)絡(luò)上的公共品博弈中各層網(wǎng)絡(luò)重疊程度和增益因子對群體合作演化的影響;Huang 等[10]考慮了具有非對稱相互作用和策略學(xué)習(xí)環(huán)境的雙層網(wǎng)絡(luò)上的公共品博弈,研究發(fā)現(xiàn),相互作用網(wǎng)絡(luò)和策略學(xué)習(xí)網(wǎng)絡(luò)的重疊邊比例會顯著影響群體中的合作行為.另一方面,為理解公共品博弈困境下群體合作行為的涌現(xiàn)機制,各種促進公共品博弈中合作涌現(xiàn)的具體機制被提出并得到了廣泛研究.包括獎勵與懲罰機制[11-16]、異質(zhì)投資[17,18]、排斥策略[19,20]、個體遷移[21]、容忍策略[22,23]、從眾機制[24]、收益再分配[25]等.此外,異質(zhì)增益因子對公共品博弈中合作演化的影響同樣受到了關(guān)注.Shi 等[26,27]探究了方格子網(wǎng)絡(luò)上公共品博弈中異質(zhì)增益因子對群體合作演化的影響,發(fā)現(xiàn)異質(zhì)群體增益因子的引入對群體合作行為的涌現(xiàn)具有促進作用.Chen 等[28]和Weng 等[29]討論了隨時間改變的異質(zhì)增益因子對公共品博弈中合作演化的影響,他們發(fā)現(xiàn)動態(tài)變化的增益因子能夠顯著地提高群體合作水平.

上述研究工作都是基于普通圖上的空間公共品博弈討論群體的合作演化,而普通圖中的連邊通常只能表征節(jié)點兩兩之間的相互作用關(guān)系.隨著社會經(jīng)濟和信息技術(shù)的快速發(fā)展,現(xiàn)實生活中社會成員及群體之間的關(guān)系表現(xiàn)出了越來越復(fù)雜和多元化的特點,考慮到普通圖在刻畫個體間相互作用關(guān)系上的局限性,能夠更好描述個體之間復(fù)雜多元關(guān)系的超圖模型得到了越來越多學(xué)者的關(guān)注[30-33].最近,Burgio 等[34]探究了高階相互作用下群體的合作演化.Alvarez-Rodriguez 等[35]較為系統(tǒng)地研究了具有不同網(wǎng)絡(luò)拓撲特征的超圖上的公共品博弈,并通過科技論文合作者實證數(shù)據(jù)分析了群體合作如何依賴于群體規(guī)模.受到以上研究工作的啟發(fā),本文構(gòu)建了引入異質(zhì)增益因子的超圖上的演化公共品博弈模型.基于均勻隨機超圖,研究了不同網(wǎng)絡(luò)階數(shù)對具有特定增益因子分布的公共品博弈中合作演化的影響.我們發(fā)現(xiàn),特定增益因子分布的均勻超圖上的公共品博弈中網(wǎng)絡(luò)階數(shù)的增大能夠促進群體合作行為的涌現(xiàn).進一步地,本文探究了給定階數(shù)的均勻超圖中服從不同分布的異質(zhì)增益因子對群體合作行為的影響.最后,討論了超圖上不同超邊數(shù)目對系統(tǒng)合作演化的影響.

2 超圖上具有異質(zhì)增益因子的公共品博弈模型

不同于普通圖上一條邊只能連接兩個節(jié)點,超圖上的邊(又稱為超邊)可以連接不少于 2 的任意數(shù)量的節(jié)點.每條超邊連接的節(jié)點數(shù)量都相同且為g的超圖稱為g階超圖,當g=2 時超圖即退化為普通圖.基于Alvarez-Rodriguez 等[35]的研究工作,我們建立了g階超圖上的演化公共品博弈模型.超圖上的節(jié)點表征博弈個體,個體之間的相互作用關(guān)系通過超邊進行刻畫.初始時,群體中個體隨機選擇采取合作或背叛策略.在每個時間步,采取合作策略的個體(合作者)將在所參與的博弈群組單元進行的公共品博弈中做出一個投資c(不失一般性,設(shè)定c=1),而采取背叛策略的個體(背叛者)將不會做出任何的投資.在一個博弈群組單元中所有合作者的投資總和將會乘以增益因子R,然后再均分給該博弈群組單元中的所有個體.在g階均勻隨機超圖上,基本博弈群組單元規(guī)模為g.因此,在由g個個體組成的博弈群組單元公共品博弈中,合作者和背叛者獲得的收益可以分別表示為πC=RcwC/g-c和πD=RcwC/g,其中wC為該博弈群組單元中合作者的數(shù)目,R為增益因子.

與普通圖上的空間公共品博弈不同,超圖上的空間公共品博弈以超邊內(nèi)個體組成的群組作為基本博弈群組單元.本模型考慮超圖上的節(jié)點規(guī)模為N=1000,超邊數(shù)目為L.對于均勻隨機超圖,存在臨界超邊數(shù)目Lc=(N/g)lnN使得超圖全連通.為保證超圖的連通性,L≥Lc.系統(tǒng)根據(jù)包含以下基本步驟的標準蒙特卡羅模擬過程進行演化.首先,從整個群體中隨機選擇一個個體i以及該個體所在的一條超邊li,j(即包含i個體的第j條超邊),超邊中所有個體參與他們各自所在的所有超邊中個體組成的基本博弈群組單元里的公共品博弈并累積收益.如圖1所示,以 9 個節(jié)點和 4 條超邊構(gòu)成的 3 階均勻超圖為例,假設(shè)從群體中隨機選擇的一個個體i為n3,同時隨機選擇了n3所在的一條超邊l2,超邊l2中的所有個體要參與他們各自所在的每條超邊中個體構(gòu)成的博弈群組中的公共品博弈,即n3將參與其所在的l1和l2群組中的公共品博弈,n4將參與其所在的l2群組中的公共品博弈,n5將參與其所在的l2,l3以及l(fā)4群組中的公共品博弈.超邊li,j中個體i的累積收益表示為

圖1 3 階均勻隨機超圖上的空間公共品博弈Fig.1.The spatial public goods game on uniform random hypergraph with hyperlinks of order equal to g=3.

其中,ki為節(jié)點i的超度,個體i參與其所在的第h條超邊中個體組成的博弈群組的公共品博弈獲得的收益表示為

其中,Δ為整個群體中個體之間可能的最大收益差的絕對值.N次包含上述兩個基本步驟的演化過程,構(gòu)成一個完整的蒙特卡羅模擬過程,即在一個蒙特卡羅時間步中,平均每個個體具有一次更新自身策略的機會.

其中參數(shù)a為函數(shù)ξ的振幅(a=0,系統(tǒng)回到原始模型,博弈群組增益因子都為r0),上述3 種分布中的χ都是服從 [0,1] 均勻分布的一個隨機數(shù),并且這保證了整個群體中ξ的均值為0.因此,服從上述3 種不同分布的都滿足關(guān)系式=r0,即博弈群組單元異質(zhì)增益因子的均值都相同并且為r0.原始和a=1 時ξ服從上述3 種特殊分布的超邊數(shù)目為L=500 的超圖上的空間公共品博弈中,不同超邊對應(yīng)的博弈群組的增益因子分布情況如圖 2 所示,可以看到,原始模型中所有博弈群組的增益因子都相同,ξ為冪律分布時對應(yīng)的群體中增益因子的異質(zhì)性最強(即少數(shù)超邊對應(yīng)的博弈群組的增益因子非常大,而大多數(shù)超邊對應(yīng)的博弈群組的增益因子很小),ξ為均勻分布時引起的增益因子異質(zhì)性在除原始模型外的3 種特殊分布中最弱,指數(shù)分布介于冪律分布和均勻分布之間.

圖2 r0=1.0 和 a=1.0 時4 種分布情況下的群體增益因子 rl=r0(1+ξ) 的分布 (a) 原始模型;(b) 均勻分布;(c) 指數(shù)分布;(d) 冪律分布Fig.2.Distributions of synergy factors rl=r0(1+ξ) for r0=1.0and a=1.0 of the four cases:(a) Original model;(b) uniform distribution;(c) exponential distribution;(d) power-law distribution.

3 數(shù)值模擬結(jié)果與分析

本節(jié)對上述g階均勻超圖上的空間公共品博弈模型進行蒙特卡羅模擬,討論和分析網(wǎng)絡(luò)階數(shù)g和不同增益因子分布模式對超圖上空間公共品博弈中合作演化的影響.群體合作水平fC定義為fC=NC/N,其中N和NC分別代表博弈群體總?cè)藬?shù)和群體中采取合作策略的人數(shù).超圖節(jié)點規(guī)模為N=1000,除特別標注外,超圖上的超邊數(shù)目為L=Lc=(N/g)lnN.3 種異質(zhì)分布的振幅取值為a=1.特定參數(shù)下系統(tǒng)的演化結(jié)果都是系統(tǒng)在經(jīng)過足夠長的演化時間進入穩(wěn)定狀態(tài)后并通過不少于 10 次不同初始條件下系綜平均得到的結(jié)果.

圖3 給出了包含原始經(jīng)典模型在內(nèi)的4 種增益因子分布情況下,不同階數(shù)g的超圖上的群體合作水平fC隨增益因子均值r0的變化情況.定義臨界增益因子均值rc,即群體合作水平fC=0.5 時對應(yīng)的r0值.r0≥rc時群體中合作策略占主導(dǎo),而r0＜rc時群體中背叛策略占主導(dǎo).從圖 3 可以看到,無論是在具有同質(zhì)增益因子的超圖上的公共品博弈(原始模型)中,或是在增益因子服從均勻分布、指數(shù)分布和冪律分布的超圖上的公共品博弈中,任意g值下系統(tǒng)的合作水平fC都隨增益因子均值r0的增大而增大.此外,在上述任意一種給定增益因子分布的空間公共品博弈中,臨界增益因子閾值rc隨著超圖階數(shù)g的增大而減小.并且,隨著博弈群組增益因子異質(zhì)性的增強(如增益因子服從冪律分布時),超圖階數(shù)g值的增大對合作的促進作用越顯著.由于以上結(jié)果是基于超邊數(shù)目為L=Lc=(N/g)lnN的超圖上的公共品博弈得到的演化結(jié)果,隨著g的減小,超圖上超邊的數(shù)目將增大.而超圖連邊變得更為稠密,將使得超圖上的博弈群體趨向于完全混合的情況,不利于群體中合作行為的涌現(xiàn).

圖3 4 種增益因子分布情況下,不同階數(shù) g 的超圖上群體合作水平 fC 隨 r0 的變化 (a) 原始模型;(b) 均勻分布;(c) 指數(shù)分布;(d) 冪律分布Fig.3.Fraction of cooperators fC as a function of r0 for hypergraphs with different orders g :(a) Original model;(b) uniform distribution;(c) exponential distribution;(d) power-law distribution.

進一步地,為更加直觀地展示超圖上不同增益因子分布模式對群體合作演化的影響,在圖 4中給出了階數(shù)g分別為2,3,4 和5 時的均勻超圖上具有不同增益因子分布模式的空間公共品博弈中群體合作水平隨增益因子均值r0的變化情況.從圖 4可以看到,隨著r0逐步增大,系統(tǒng)合作水平從 0 單調(diào)增大到 1 .同時,在確定階數(shù)的均勻超圖上,具有越強博弈群組增益因子異質(zhì)性的群體中合作策略占主導(dǎo)地位對應(yīng)的臨界增益因子均值rc越小.相對于博弈群組增益因子都相同的原始模型上的演化結(jié)果,在r0較小時,博弈群組增益因子的異質(zhì)性能夠極大地促進群體的合作行為.尤其是在階數(shù)g比較大的超圖上,異質(zhì)增益因子能夠顯著地提高系統(tǒng)的合作水平,博弈群組增益因子的異質(zhì)性越強越有利于博弈群體中合作行為的涌現(xiàn).

圖4 不同超圖階數(shù) g 值情況下,4 種增益因子分布對應(yīng)的群體合作水平 fC 隨 r0 的變化 (a) g=2 ;(b) g=3 ;(c) g=4 ;(d)g=5Fig.4.Fraction of cooperators fC as a function of r0 on hypergraphs with (a) g=2,(b) g=3,(c) g=4 and (d) g=5 for the four situations.

在具有異質(zhì)增益因子的博弈群體中,由于博弈群組增益因子的不均勻性,群體中部分博弈群組將具有較大的增益因子.參與具有較大增益因子的博弈群組公共品博弈的個體將更傾向于采取合作策略,從而更容易形成穩(wěn)定的合作團簇.尤其是在增益因子服從異質(zhì)性最強的冪律分布情況下,即使在增益因子均值r0比較小時,也能夠使得群體中產(chǎn)生部分增益因子很大的博弈群組.該部分博弈群組的存在,將極大促進群體中合作行為的涌現(xiàn)和維持.圖 5 給出了r0=0.35 時 5 階均勻超圖上空間公共品博弈演化到穩(wěn)態(tài)時群體中各個博弈群組單元中合作者數(shù)目wC的分布情況.可以看到,對于原始模型或增益因子異質(zhì)性比較弱的均勻分布情況,所有博弈群組中合作者數(shù)目都為 0,群體中個體無法維持合作行為.而在異質(zhì)性比較強的指數(shù)分布情況下,能夠存在少數(shù)博弈群組,群組中部分個體依然能夠維持合作策略.另外,在異質(zhì)性更強的冪律分布情況下,多數(shù)群組中能夠存在一定數(shù)目的合作者,甚至出現(xiàn)了較高比例的wC=5 的博弈群組,即群組中個體都采取合作策略.上述4 種分布中,博弈群組增益因子均值都為r0=0.35 .在原始模型中,群體中所有群組的增益因子都為r0,這種情況下,任何一個博弈群組都無法維持合作行為.而在冪律分布情況下,群體中博弈群組增益因子的分布將是大部分群組的增益因子都小于r0,而只有少數(shù)群組的增益因子大于r0.顯然,如果沒有少數(shù)具有較大增益因子的博弈群組的存在,占大多數(shù)的增益因子小于r0的群組中不可能有個體能夠維持合作行為.

圖5 參數(shù)取 g=5 與 r0=0.35 時博弈群組單元中合作者數(shù)目 wC 的分布Fig.5.Distribution of the numbers of cooperators in the group wC for g=5 and r0=0.35 .

為了更好地理解上述演化結(jié)果以及更全面地展示系統(tǒng)的演化過程,圖 6 給出了對應(yīng)圖 5 演化結(jié)果的群體合作水平fC和群組中不同合作者數(shù)目wC對應(yīng)的博弈群組比例f(wC) 的演化時間序列.如圖 6(a)和圖 6(b)所示,系統(tǒng)演化的暫態(tài)時間非常短,wC=3,4,5,對應(yīng)的初始合作者數(shù)目較多的博弈群組比例隨著系統(tǒng)演化開始后迅速下降為 0,即使初始時該部分群組中合作者策略是多數(shù)策略,但群組中的個體依然不能維持自身的合作行為.該部分群組中合作者數(shù)目逐步減少,使得wC=1,2 的群組比例在演化初始階段有所上升,但此后依舊逐步減小到 0,群體的合作水平最終減小為 0 .在異質(zhì)性較強的指數(shù)分布情況下,如圖 6(c)所示,系統(tǒng)演化的暫態(tài)時間有所增長,雖然f(wC=3),f(wC=4)和f(wC=5) 隨著演化的開始依舊比較快地下降,但最終依然能夠存在一定比例的wC=1,wC=2,wC=3 甚至wC=4 的博弈群組,穩(wěn)態(tài)時系統(tǒng)能夠維持一定的合作水平.在圖 6(d)對應(yīng)的異質(zhì)性最強的冪律分布情況下,系統(tǒng)的演化過程出現(xiàn)了本質(zhì)的改變,系統(tǒng)暫態(tài)時間大大增長.wC=3,4,5 對應(yīng)的初始合作者占多數(shù)的博弈群組比例隨著系統(tǒng)演化的進行先緩慢減小到一個最低值后逐步上升到一定水平,增益因子的異質(zhì)性對群體合作行為的涌現(xiàn)、維持和傳播起到了重要的促進作用.在冪律分布情況下,具有較小增益因子的博弈群組,即使同樣存在初始合作策略占多數(shù)的群組中的個體逐步轉(zhuǎn)變?yōu)楸撑颜?由于存在少數(shù)具有非常高增益因子的群組,該部分群組中個體多數(shù)采取合作策略,形成了穩(wěn)定的合作團簇.形成穩(wěn)定合作團簇的群組能夠?qū)⒑献鞑呗韵蛑車航M中的個體傳播,更多群組逐步被合作者占據(jù),使得群體中合作個體比例在減小到一定值后能夠最終逐步升高到一個較高的合作水平.

圖6 4 種增益因子分布情況下,參數(shù)取 g=5 與 r0=0.35 時群體合作水平 fC 以及群組中合作者數(shù)目 wC 分別為0,1,2,3,4,5 的博弈群組比例的演化時間序列 (a) 原始模型;(b) 均勻分布;(c) 指數(shù)分布;(d) 冪律分布Fig.6.Time series for the evolution of the fraction of cooperators fC and the fractions of groups with wC=0,1,2,3,4,5 forg=5 and r0=0.35 :(a) Original model;(b) uniform distribution;(c) exponential distribution;(d) power-law distribution.

最后,研究4 種不同增益因子分布情況下,均勻超圖上超邊數(shù)目對臨界增益因子均值rc的影響.圖 7 給出了不同階數(shù)g的超圖上公共品博弈中rc隨超圖超邊數(shù)目與超圖全連通對應(yīng)超邊閾值的比值L/Lc的變化情況.從圖 7 可以看到,在給定增益因子分布和超邊數(shù)目比值L/Lc下,rc都會隨著g的增大而減小.同時,在給定增益因子分布下,對于每一個超圖階數(shù)g值,rc隨L/Lc的增大而增大.特別是在如圖 7(a) 所示的原始模型的演化結(jié)果中,rc隨L/Lc的增大而逐步增大到接近于 1,其他3 種特殊分布情況下同樣有此趨勢.rc=1 對應(yīng)著均勻混合群體公共品博弈中合作涌現(xiàn)的臨界增益因子[37].隨著超邊數(shù)目L的增大,超圖將更加趨向于全連接超圖,rc將更接近于 1 .此外,對比相同超邊數(shù)目L和階數(shù)g對應(yīng)的4 種增益因子分布的演化結(jié)果,可以發(fā)現(xiàn),rc值隨著增益因子分布異質(zhì)性的增強而減小,異質(zhì)增益因子能夠極大地促進超圖上公共品博弈中合作行為的涌現(xiàn).

圖7 4 種增益因子分布情況下,不同階數(shù) g 的超圖上臨界增益因子均值 rc 隨超邊數(shù)目 L 與閾值 Lc 的比值的變化 (a) 原始模型;(b) 均勻分布;(c) 指數(shù)分布;(d) 冪律分布Fig.7.Critical value of the synergy factor rc as a function of the ratio between the number of hyperlinks L and the critical value Lcin hypergraphs of different orders g :(a) Original model;(b) uniform distribution;(c) exponential distribution;(d) power-law distribution.

4 結(jié)論

本文考慮了公共品博弈中博弈群組增益因子的異質(zhì)性,建立了基于均勻超圖的具有不同增益因子分布的空間公共品博弈模型.除所有博弈群組具有相同增益因子的原始模型外,考慮了博弈群組增益因子具有相同均值并且分別服從均勻分布、指數(shù)分布和冪律分布的空間公共品博弈模型,研究了超圖階數(shù)以及增益因子異質(zhì)性對于系統(tǒng)合作演化的影響.數(shù)值模擬結(jié)果表明,基于超邊數(shù)目為L=Lc=(N/g)lnN的超圖,無論是在博弈群組具有相同增益因子的原始模型中,還是在博弈群組增益因子服從異質(zhì)性分布的空間公共品博弈中,對應(yīng)群體中合作行為占主導(dǎo)的臨界增益因子均值rc隨超圖階數(shù)g的增大而減小,超圖階數(shù)的增大有利于提高系統(tǒng)的合作水平.同時,對比原始模型,群體中博弈群組增益因子異質(zhì)性的引入能夠顯著促進群體中的合作行為.博弈群組增益因子的異質(zhì)性對群體中合作行為的涌現(xiàn)和維持以及合作策略在群體中的傳播起到了重要的促進作用.此外,基于上述模型,探究了超圖超邊數(shù)目對群體中合作演化的影響,發(fā)現(xiàn)臨界增益因子均值rc隨著超邊數(shù)目L的增大而增大.并且,在不同的有限超邊數(shù)目L值下,超圖階數(shù)g和增益因子異質(zhì)性對于群體合作行為的促進作用同樣存在.本文對考慮增益因子異質(zhì)性的超圖上空間公共品博弈中合作演化的研究,加深了對超圖上空間公共品博弈中合作涌現(xiàn)的理解.