基于獎勵因子的囚徒困境博弈模型研究

陳維春,尚麗輝

(上海理工大學 光電信息與計算機工程學院,上海　200093)

?

基于獎勵因子的囚徒困境博弈模型研究

陳維春,尚麗輝

(上海理工大學 光電信息與計算機工程學院,上海200093)

摘要針對合作演化問題,通過引入獎勵因子。根據演化博弈論,研究在空間囚徒困境博弈中,獎勵因子和記憶長度對策略改變的影響。先后分析了合作率與對背叛誘惑之間的關系圖,合作率與記憶長度的關系圖以及臨界值和獎勵因子變化的關系圖等。研究發(fā)現,與傳統(tǒng)囚徒困境博弈模型相比,增加獎勵因子或減少記憶長度能有效促進合作的演化。

關鍵詞囚徒困境博弈;獎勵因子;收益系數

Research on Prisoner’s Dilemma Game Based on Reward Factor

CHEN Weichun,SHANG Lihui

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractThe evolution of cooperation is discussed according to the evolutionary game theory.We study the reward factor and memory during the strategy update process by introducing the reward factor in the spatial Prisoner’s Dilemma Game.Firstly,we analyze the rate of cooperation and the temptation of betrayal,the relationship cooperative rate and memory length,and the relationship diagram of critical value and reward factor.A comparison with traditional Prisoner’s Dilemma Game Model shows that increasing the reward factor or reducing the memory length effectively promotes the evolution of cooperation.

Keywordsprisoner’s dilemma game;reward factor;coefficient

在自然界和人類社會中廣泛存在著合作行為[1-9]。在傳統(tǒng)的囚徒困境博弈模型中[10],每個參與者均有兩種策略選擇:合作或者背叛。若兩個參與者均選擇合作,則每個人可得到較高收益,記為R;若兩個參與者均選擇背叛,則每個人會得到較低的收益,記為P;而如果一個參與者選擇合作而另一個選擇背叛,則合作者會得到最低的傻瓜式報酬,記為S,而背叛者可得到最高的收益,即對背叛的誘惑,記為T。因此,可得到T>R>P>S。可以看出,自私的個體會選擇背叛,而不會考慮對手的選擇。因而,這種困境行為會導致背叛者大量出現。

本文通過引入獎勵因子的概念,研究空間囚徒困境博弈中,獎勵因子和記憶長度對策略改變的影響。若參與者能將自身的策略連續(xù)M代或M代以上逐代傳給其的后代而不間斷,就給予適當的獎勵。在博弈進行之前,為每個參與博弈的個體設置相同的收益系數,記為φx(t),其會使博弈返回到傳統(tǒng)的博弈模型,在演化的過程中,隨著策略和記憶長度的改變,每個參與者的收益系數也會隨之發(fā)生變化。

1模型

不妨假設參與者位于L×L周期性邊界條件x點的平方格子上,初始時,參與者在點x處作為合作者(ss=C)或背叛者(sx=D)的概率是相等的,收益系數φx(t)=1.0也相等。為研究方便,調整收益矩陣[11-13]:對背叛的誘惑T=b,相互合作時的收益R=1,相互背叛時的收益P和傻瓜式的報酬S都等于0,在此取1≤b≤2。根據Monte Carlo(MC)仿真,首先,參與者通過與其最近的4個鄰居進行博弈,獲得本輪收益Px,然后通過表達式(1)計算其的總收益φx

φx=φx(t)·Px

(1)

其次,隨機選擇一個鄰居,記為y,以同樣的方法計算φy。最后,下一輪中參與者x采取y的概率可根據物理學中的費米函數計算

(2)

這里K描述了環(huán)境的噪聲因素。在本模型中,若參與者能將自身的策略逐代地傳給其的后代連續(xù)進行M或M代以上,而中間不改變其策略,就給予適當的獎勵,且在x的收益系數φx(t)將會以表達式(3)發(fā)生變化,即

φx(t+1)=(1+α)·φx(t)

(3)

這里α(0≤α≤1)即為獎勵因子,否則收益系數φx(t)保持不變。若參與者在連續(xù)M代以內的某一子代改變了其策略,即采用其鄰居的策略,就不再給其獎勵,并將那一代看作是第一代重新計算,這一過程反復進行,直至收益系數重新返回到1.0為止。

2仿真結果及分析

文中考慮節(jié)點在50×50的網格上,設定MCS為1.1×104,為保證結果的準確度,每個仿真結果均為進行100次仿真并取平均值的結果。

首先,觀察在M保持不變的情況下,獎勵因子α與合作演化之間的關系。如圖1所示,仿真了當M=3,獎勵因子分別取α=0,0.01,0.02,0.03,0.04時,合作率ρc與對背叛的誘惑b之間的關系,這里取K=0.1。

圖1　獎勵因子α與合作演化之間的關系圖

圖1所示,當α=0時,此博弈模型回歸傳統(tǒng)的囚徒困境博弈模型,在b較小時合作者就會消失。然而,隨著α的增加,有效地促進了合作的演化。當α=0.01時,可明顯看出在b較小時合作被有效地促進,就是合作占優(yōu)的策略。隨著α地持續(xù)增加,背叛者只有在b足夠大時才會存在。這些結果表明,當引入獎勵因子時,合作的出現與維持可被有效促進,增加獎勵因子會導致合作的演化。

接著觀察記憶長度M對合作演化的影響。在圖2中,仿真了當獎勵因子取α=0.02,M=1,3,6,9,12時,ρc與b的關系,取K=0.1。

圖2　合作率ρc與b的關系圖

圖2所示,隨著M值的減小,合作演化被有效地促進,隨著M值的減小,合作者的生存能力會單調增加。以上結果表明,當獎勵因子取定適當值時,隨著記憶長度M的減小,合作演化可被有效地促進。當獎勵因子取α=0.02,b=1.1,1.2,1.3,1.4時,ρc與M的關系如圖3所示,取K=0.1。

圖3　ρc與M的關系圖

如圖3所示,在一定范圍內,隨著b的減小,合作演化被有效地促進,在b=1.1時,可明顯看到是合作占優(yōu)的策略。當M值足夠大時,這種促進作用就會越來越微弱甚至消失。這從圖2中得到了驗證。

最后,考慮臨界值bc,就是使合作者消失時刻的值。當M=3,6,9,12時,bc隨α變化的關系如圖4所示,取K=0.1。

圖4　臨界值bc隨α變化的關系圖

圖4所示,與傳統(tǒng)的囚徒困境博弈模型(α=0)相比,隨著α的增大,bc單調增加,對不同的M值而言,合作者生存能力的健壯性是不同的,其定性的分析結果從圖1中可得到驗證。引入獎勵因子,可促進合作的演化;另一方面,隨著M值的減小,合作者的生存空間變的越來越廣泛,圖2中的結果也證實了這一結論。

3結束語

本文研究了在空間囚徒困境博弈中,獎勵因子和記憶長度對策略改變的影響。研究發(fā)現,這種獎勵機制能有效地促進合作。隨著獎勵因子的單調增加或記憶長度的減少,合作行為可明顯得到促進,通過合作的動態(tài)演化,也證實了該種獎勵機制能有效促進合作。

參考文獻

[1]Dugatkin L A.Cooperation among animals:an evolutionary perspective[M].Princetion,NJ:Oxford University Press,1997.

[2]Maynard Smith J,Szathmáry E.The major transitions in evolution[M].Princetion,NJ:Oxford University Press,1995.

[3]Axelrod R.The evolution of cooperation[M].New York:Basic Books,1984.

[4]Sigmund K.The calculus of selfishness[M].Princeton,NJ:Princeton University Press,2010.

[5]Nowak M A.Evolutionary dynamics:exploring the equations of life[M].Cambridge,MA:Belknap Press,2006.

[6]Hofbauer J,Sigmund K.Evolutionary games and population dynamics[M].Cambridge,UK:Cambridge University Press,1998.

[7]Colman A M.Game theory and its applications in the social and biological sciences[M].Oxford,UK:Butterworth-Heinemann,1995.

[8]Taylor M.The possibility of cooperation[M].Cambridge,UK:Cambridge University Press,1987.

[9]楊涵新,汪秉宏.復雜網絡上的演化博弈研究[J].上海理工大學學報,2012,34(2):166-171.

[10]汪小帆,李翔,陳關榮.網絡科學導論[M].北京:高等教育出版,2012.

[11]Tomochi M,Kono M.Spatial prisoner’s dilemma games with dynamic payoff matrices[J].Physical Review E,2002(65):026112-026119.

[12]Ashlock D,Kim E Y,Ashlock W.A fingerprint comparison of different prisoner’s dilemma payoff matrices[J].IEEE Transportations on Biological Science,2010(6):219-226.

[13]Li Z H,Wang B H,Liu R R,et al.Evolutionary prisoner’s dilemma game based on division of work[J].Chinese Physical Letters,2009,26(2):108701-108710.

中圖分類號F224.32

文獻標識碼A

文章編號1007-7820(2016)03-005-03

doi:10.16180/j.cnki.issn1007-7820.2016.03.002

作者簡介:陳維春(1988—),男,碩士研究生。研究方向:復雜網絡。尚麗輝(1977—),女,博士,講師。研究方向:復雜系統(tǒng)的分析與控制。

基金項目:國家自然科學基金資助項目(81101116)

收稿日期:2015- 07- 28