金 星，李明楚，孫曉梅，郭 成

(大連理工大學(xué) 軟件學(xué)院,遼寧 大連 116620)

1 引 言

近年來，隨著互聯(lián)網(wǎng)和移動(dòng)網(wǎng)絡(luò)的飛速發(fā)展，基于網(wǎng)絡(luò)合作的協(xié)作系統(tǒng)已大量出現(xiàn)在了我們的生活中.在這類系統(tǒng)中，雖然每一個(gè)個(gè)體的能力都是有限的，但是通過個(gè)體之間的合作行為，人們可以實(shí)現(xiàn)一系列復(fù)雜困難的任務(wù).然而，由于個(gè)體理性的存在，參與者往往會(huì)選擇背叛行為，從而造成了合作困境.一個(gè)典型的例子就是P2P文件共享系統(tǒng)里用戶的搭便車現(xiàn)象[1].

為了促進(jìn)用戶的合作行為，保證協(xié)作系統(tǒng)的有效運(yùn)行，引入激勵(lì)機(jī)制已經(jīng)成為了必不可少的選擇.通過研究之前的文獻(xiàn)，可以發(fā)現(xiàn)：在考慮策略花費(fèi)這一實(shí)際場景下，互惠策略會(huì)占優(yōu)無條件背叛策略，無條件背叛策略會(huì)占優(yōu)無條件合作策略，無條件合作策略會(huì)占優(yōu)互惠策略[2-4]，這種互相占優(yōu)關(guān)系會(huì)導(dǎo)致無條件合作策略抑制合作產(chǎn)生的這一奇怪現(xiàn)象.為了解決上述現(xiàn)象，本文在推薦合作激勵(lì)模型[4]基礎(chǔ)上引入了用戶的理性背叛機(jī)制，最后理論和實(shí)驗(yàn)都證明了該機(jī)制在促進(jìn)合作方面的有效性能.

2 相關(guān)工作

為了解決合作困境，研究者們進(jìn)行了大量的激勵(lì)機(jī)制研究.根據(jù)之前的文獻(xiàn)，激勵(lì)機(jī)制研究主要包含兩方面的內(nèi)容：金錢獎(jiǎng)勵(lì)機(jī)制和互惠機(jī)制.在金錢獎(jiǎng)勵(lì)機(jī)制中，合作者可以通過提供服務(wù)獲取物質(zhì)報(bào)酬，因其高效性和簡單性，該機(jī)制已廣泛應(yīng)用于實(shí)際的協(xié)作系統(tǒng)中，例如：滴滴網(wǎng)約車平臺(tái)，亞馬遜在線工人平臺(tái)，等等.在很多沒有設(shè)置金錢獎(jiǎng)勵(lì)的協(xié)作系統(tǒng)里，互惠機(jī)制發(fā)揮了極其重要的作用.根據(jù)交互對(duì)象的特點(diǎn)，互惠機(jī)制可以分為：直接互惠和間接互惠.在直接互惠中，交互雙方是保持不變的，其核心思想是“我?guī)椭?，你幫助我?一報(bào)還一報(bào)策略(Tit-for-Tat strategy，TFT)[5]是目前最知名的直接互惠策略，TFT策略使用者首先會(huì)采用合作行為，而在之后的交互中會(huì)采取對(duì)手上一輪的行為.為了增加TFT策略的魯棒性，TF2T(Tit-for-Two-Tats)[6]策略和GTFT(Generous TFT)[7]策略隨后也被提了出來.在Nowak的文章[8]中，贏留輸改(Win-Stay Lose-Shift,WSLS)策略被提了出來，該策略使用者會(huì)保留一個(gè)收益期望值，如果當(dāng)前收益不低于該期望值，則保留當(dāng)前行為，否則，就更改當(dāng)前行為，實(shí)驗(yàn)證明WSLS取得了比TFT更好的性能.在間接互惠中，交互雙方是動(dòng)態(tài)變化的，其核心思想是“我?guī)椭鷦e人，別人幫助我”.針對(duì)大規(guī)模P2P文件共享場景，F(xiàn)eldman提出了Mirror策略[9]，當(dāng)該策略使用者接收到一個(gè)服務(wù)請(qǐng)求后，他/她會(huì)計(jì)算該交互對(duì)手為別人提供服務(wù)的概率，然后以相同的概率為該交互對(duì)手提供服務(wù).隨后，Zhao等人[2]提出了Proportion策略，該策略使用者會(huì)計(jì)算交互對(duì)手提供的服務(wù)數(shù)量與其獲得的服務(wù)數(shù)量的比例，并以該比例值作為自己與他人進(jìn)行合作的概率，理論和實(shí)驗(yàn)證明，相比Mirror策略，Proportion策略能夠更好地促進(jìn)合作.Wang等人[3]研究了花費(fèi)對(duì)Proportion策略性能的影響.Li等人[4]提出了基于推薦的合作激勵(lì)策略(Recommendation Incentive Mechanism，RIM),該策略使用者在推薦機(jī)制的幫助下提高了自身與合作性節(jié)點(diǎn)交互的可能性，進(jìn)而可以獲得更高的收益，理論和實(shí)驗(yàn)證明，相比WSLS，Mirror和Proportion策略，RIM策略具有更好地促進(jìn)合作的性能.在文獻(xiàn)[4]的基礎(chǔ)上，本文進(jìn)一步引入了理性背叛機(jī)制，以解決互惠策略被無條件合作策略所抑制的這一問題，進(jìn)而希望可以進(jìn)一步促進(jìn)合作的涌現(xiàn).

另一方面，網(wǎng)絡(luò)結(jié)構(gòu)對(duì)參與者合作行為的影響目前也引起了廣泛的關(guān)注，研究者們發(fā)現(xiàn)在網(wǎng)格網(wǎng)絡(luò)[10]，無標(biāo)度網(wǎng)絡(luò)[11]，小世界網(wǎng)絡(luò)[12]等結(jié)構(gòu)化的網(wǎng)絡(luò)中合作行為可以得到一定程度的促進(jìn).

3 模型構(gòu)建

3.1 演化博弈

Maynard Smith在1982年提出了演化博弈理論模型[13]，相比于傳統(tǒng)的博弈論，它具有以下兩個(gè)特性：

1)考慮了參與者的有限理性.由于在現(xiàn)實(shí)的復(fù)雜場景里，信息往往不能被完全感知，因此，參與者無法事先就做出最優(yōu)的、最理性的策略決策，這就是參與者的有限理性假設(shè).

2)動(dòng)態(tài)的博弈結(jié)果展示.在傳統(tǒng)的博弈論中，博弈結(jié)果往往是通過納什均衡進(jìn)行體現(xiàn)，然而這是一個(gè)靜態(tài)的結(jié)果，有時(shí)人們對(duì)博弈結(jié)果的生成過程也很感興趣.在演化博弈中，人們不僅可以獲得博弈的最終結(jié)果，也可以了解結(jié)果的產(chǎn)生過程，從而對(duì)博弈模型有更多的了解.

基于以上兩個(gè)特點(diǎn)，本文將使用演化博弈作為模型的基礎(chǔ)框架來描述大規(guī)模協(xié)作系統(tǒng)里用戶的交互過程.

3.2 推薦機(jī)制框架

基于用戶交互的反饋信息，筆者之前文獻(xiàn)[4]通過Eigentrust算法構(gòu)建了一個(gè)合作性用戶推薦系統(tǒng)，使用該系統(tǒng)的用戶能夠以一個(gè)更高的概率與高合作度用戶進(jìn)行交互，進(jìn)而提高了獲得服務(wù)的可能性.

3.3 策略集

假設(shè)系統(tǒng)中存在N個(gè)用戶，每一個(gè)用戶都會(huì)從策略集S中選擇一個(gè)策略si作為自己與他人進(jìn)行交互時(shí)的行為準(zhǔn)則.在演化博弈中，使用了相同策略的參與者可以統(tǒng)稱為一個(gè)種群(Population).

具體而言，本文模型考慮了下列三個(gè)純策略.

無條件合作策略(ALLways Cooperate,ALLC)：該策略使用者會(huì)一直為交互對(duì)手提供服務(wù)，模型中將該策略記為s1.

無條件背叛策略(ALLways Defect，ALLD)：該策略使用者不會(huì)為其他用戶提供服務(wù),模型中將該策略記為s2.

推薦機(jī)制策略(Recommendation，R)：該策略是一種有條件的合作策略，他/她會(huì)根據(jù)交互對(duì)象的類型決定自己的行為.當(dāng)與ALLD策略用戶進(jìn)行交互時(shí)，他/她會(huì)選擇拒絕為其提供服務(wù).當(dāng)與其他R策略用戶進(jìn)行交互時(shí)，他/她會(huì)選擇提供服務(wù).當(dāng)與ALLC策略用戶進(jìn)行交互時(shí)，他/她會(huì)以f(f∈[0,1])的概率為其提供服務(wù).當(dāng)f=1時(shí)，就是筆者之前模型[4]里考慮的場景，此時(shí)會(huì)出現(xiàn)無條件合作策略抑制合作涌現(xiàn)的現(xiàn)象.本文考慮了推薦合作機(jī)制中的理性背叛場景，即f∈[0,1).特別地，當(dāng)f=0時(shí)，R策略將不會(huì)給ALLC策略提供服務(wù).模型中將該策略記為s3.

基于上述策略設(shè)定，本文引入一個(gè)3×3矩陣P=[pij]來描述策略間的交互行為:

其中元素pij表示策略si為策略sj提供服務(wù)的概率.

3.4 策略收益

收益是博弈模型中的一個(gè)重要元素，它直接說明了策略的好與壞.在計(jì)算策略收益前，先描述一下本文模型的交互場景：

1)一次機(jī)會(huì).本文將協(xié)作系統(tǒng)建模成一個(gè)時(shí)間離散型模型，在一個(gè)時(shí)間步里，每一個(gè)用戶平均意義上都有一次機(jī)會(huì)發(fā)起一個(gè)服務(wù)請(qǐng)求.

2)混合均勻的網(wǎng)絡(luò)結(jié)構(gòu)(Well-mixed topology).此時(shí)，每一個(gè)用戶都是互相連接的，且能夠以相同的概率進(jìn)行交互.

3)一個(gè)請(qǐng)求者與一個(gè)提供者.本文假設(shè)每一個(gè)服務(wù)請(qǐng)求者會(huì)選擇其他一個(gè)用戶作為其服務(wù)提供者.比如，在百度云文件共享平臺(tái)里，文件下載者會(huì)從一個(gè)云用戶處獲得完整的資源.單請(qǐng)求者多提供者模型可以參考其他文獻(xiàn)[4,14].

首先計(jì)算ALLC策略的期望收益.

當(dāng)ALLC用戶作為服務(wù)請(qǐng)求者時(shí)，在混合均勻網(wǎng)絡(luò)結(jié)構(gòu)假設(shè)下，他她會(huì)分別以x1,x2,x3的概率選擇ALLC，ALLD，R用戶作為其交互對(duì)象.由各個(gè)策略的性質(zhì)可得，ALLC策略的期望收獲可以表示為：

=α(x1+fx3)

(1)

其中α>0表示獲得一個(gè)服務(wù)時(shí)用戶的收益.

當(dāng)ALLC用戶作為服務(wù)提供者時(shí)，在一個(gè)時(shí)間步里，他/她會(huì)為ALLC和ALLD用戶分別提供x1和x2次服務(wù).基于交互歷史，推薦系統(tǒng)[4]會(huì)將N1個(gè)ALLC用戶和N3個(gè)R用戶判定為合作性參與者，因?yàn)镽用戶會(huì)從合作性用戶那里請(qǐng)求服務(wù)，所以平均意義上，每個(gè)ALLC服務(wù)提供者會(huì)以x3/(x1+x3)的次數(shù)為R用戶提供服務(wù).綜上，ALLC策略的期望損失為：

(2)

其中β>0表示提供一次服務(wù)時(shí)用戶的損失.

總而言之，t時(shí)刻ALLC策略的期望收益可以表示為：

(3)

同理，可以計(jì)算出t時(shí)刻ALLD和R策略的期望收益為：

(4)

(5)

其中γ>0表示用戶采用R策略時(shí)需要為推薦系統(tǒng)支付的額外花費(fèi).

隨后，通過公式(6)，可以計(jì)算出t時(shí)刻系統(tǒng)的平均收益：

=(α-β)(x1+x3)-(α-β)(1-f)x1x3

(6)

在本文模型中，α，β和γ需要滿足下面的關(guān)系：首先，α>β需要成立，即獲得服務(wù)的收益要大于提供服務(wù)的損失，否則，合作將無法產(chǎn)生；其次，γ<α-β需要成立，否則，推薦花費(fèi)過高將導(dǎo)致R策略無法在系統(tǒng)中存活.

3.5 演化過程

基于策略的收益，本文中引入了兩種學(xué)習(xí)機(jī)制：全局平均學(xué)習(xí)(Global Mean Learning Mechanism,GMLM)[2-4]和當(dāng)前最優(yōu)學(xué)習(xí)(Current Best Learning Mechanism,CBLM)[2-4]來描述種群的演化過程.

3.5.1 GMLM學(xué)習(xí)機(jī)制

在交互完成后，用戶會(huì)隨機(jī)選擇一個(gè)鄰居，并與其進(jìn)行收益的比較，如果自己的收益高于所選鄰居的收益，則保持當(dāng)前策略不變，反之，將自己的策略改變成鄰居的策略，這就是GMLM學(xué)習(xí)機(jī)制.B?rgers等人[15]證明在GMLM學(xué)習(xí)機(jī)制下，種群的演化過程可以使用復(fù)制動(dòng)力學(xué)方程(Replicator equations)[2-4,12-14]進(jìn)行表示，于是本文模型中，t時(shí)刻后ALLC，ALLD和R策略比例的變化可以描述為：

(7)

其中，λ表示策略的學(xué)習(xí)率，而且各個(gè)策略收益與平均收益的差可以具體由公式(8)～公式(10)表示：

(8)

(α-β)(1-f)x1x3

(9)

(1-f)x1(β+(α-β)x3)

(10)

定義1.在收益指導(dǎo)下，如果si策略能夠最終被所有理性用戶選擇，即xi=1，那么可稱si策略占優(yōu)了整個(gè)系統(tǒng).

推論1.在GMLM下，ALLC策略不能占優(yōu)整個(gè)系統(tǒng).

證明:這里使用反證法.假設(shè)ALLC策略能夠占優(yōu)整個(gè)系統(tǒng)，那么在x1→1，x2→0，x3→0時(shí)，下列3個(gè)不等式將會(huì)成立：

推論2.在GMLM下，ALLD策略不能占優(yōu)整個(gè)系統(tǒng).

證明：這里使用反證法.假設(shè)ALLD策略能夠占優(yōu)整個(gè)系統(tǒng)，那么在x1→0，x2→1，x3→0時(shí)，下列3個(gè)不等式將會(huì)成立：

推論3.在GMLM下，當(dāng)f≥1-γ/α?xí)r，R策略不能占優(yōu)整個(gè)系統(tǒng).

證明：這里使用反證法.假設(shè)當(dāng)f≥1-γ/α?xí)r，R策略能夠占優(yōu)整個(gè)系統(tǒng).那么在x1→0，x2→0，x3→1時(shí)，下列3個(gè)不等式將會(huì)成立：

下面本文將討論兩種特殊的情況：f=1和f=0.

推論4.在GMLM下，當(dāng)f=1時(shí)，那么ALLC，ALLD和R策略都不能占優(yōu)整個(gè)系統(tǒng).

證明：參見推論1、推論2和推論3.

推論5.在GMLM下，當(dāng)f=0時(shí)，那么R策略會(huì)占優(yōu)整個(gè)系統(tǒng).

證明：此時(shí)可以計(jì)算ALLD策略與ALLC策略的收益差為：

所以，與ALLD策略相比，ALLC策略是一個(gè)嚴(yán)格的劣策略，根據(jù)博弈論中重復(fù)剔除劣策略方法，可將ALLC從策略集中刪除，即令x1=0.然后，可以計(jì)算R策略與ALLD策略的收益差為：

3.5.2 CBLM學(xué)習(xí)機(jī)制

(11)

為了方便起見，在討論模型在CBLM機(jī)制下的演化特性時(shí)，本文這里只考慮了f=0時(shí)的場景，此時(shí)有：

(12)

推論6.在CBLM下，ALLC策略不能占優(yōu)整個(gè)系統(tǒng).

證明：這里使用反證法.假設(shè)在CBLM下，ALLC策略能夠占優(yōu)系統(tǒng)，那么有：

推論7.在CBLM下，ALLD策略不能占優(yōu)整個(gè)系統(tǒng).

證明：這里使用反證法.假設(shè)在CBLM下，ALLD策略能夠占優(yōu)系統(tǒng)，那么有：

推論8.在CBLM下，當(dāng)x2+x3>(β+γ)/α?xí)r，R策略能夠占優(yōu)整個(gè)系統(tǒng).

≥α(x2+x3)-β-γ

4 一些實(shí)際問題

4.1 非完美推薦

第3章在構(gòu)建模型時(shí)只考慮了完美推薦機(jī)制場景，即推薦系統(tǒng)能夠準(zhǔn)確地分辨出用戶的合作屬性，進(jìn)而R策略用戶在每次交互中都能成功地獲得服務(wù).然而，由于數(shù)據(jù)獲取時(shí)的噪聲以及數(shù)據(jù)稀疏性等因素的影響，推薦系統(tǒng)往往不能做到100%的準(zhǔn)確，因此，為了符合實(shí)際場景，還需要考慮在非完美推薦下本文模型的表現(xiàn).

在非完美推薦下，系統(tǒng)可能會(huì)發(fā)生兩種類型的錯(cuò)誤：其一，是將背叛性用戶誤判成合作性用戶；其二，是將合作性用戶誤判成背叛性用戶.由于在現(xiàn)實(shí)場景里，背叛性用戶會(huì)使用共謀、洗白等方法以提高自己被誤判成合作性用戶的概率，進(jìn)而可以獲得更多的服務(wù)，因此討論理性背叛模型在第一種推薦錯(cuò)誤下的性能是十分有必要的事情.

為了刻畫第一類錯(cuò)誤，本文引入?yún)?shù)δ∈[0,1]表示ALLD用戶被誤認(rèn)為是合作性用戶的概率.那么此時(shí)，R策略用戶選取交互對(duì)象的規(guī)模就從N1+N3擴(kuò)大為了N1+δN2+N3.

接下來，計(jì)算在第一類錯(cuò)誤模型下各個(gè)策略的期望收益.首先是ALLC策略的期望收益.

當(dāng)ALLC用戶作為服務(wù)請(qǐng)求者時(shí)，他/她仍然能以100%和f的概率從ALLC和R交互對(duì)象中獲得服務(wù)，故其期望收獲保持不變，如公式(1)所示.當(dāng)ALLC用戶作為服務(wù)提供者時(shí)，其被R用戶訪問到的次數(shù)將變化為：

與之相對(duì)應(yīng)地，ALLC策略的期望損失更新為：

綜上，在第一類錯(cuò)誤模型下，ALLC策略的期望收益為：

(13)

在計(jì)算ALLD策略期望收益時(shí)，此處考慮了最壞的情況，即ALLD策略會(huì)以δ的概率被誤判為R策略，此時(shí)ALLD策略的期望收益可以表示為：

(14)

由于第一類錯(cuò)誤的存在，以(x1+x3)/(x1+δx2+x3)的概率，R用戶會(huì)獲得服務(wù)，以fx1+δx2+x3/(x1+δx2+x3)的次數(shù)，R用戶給其他用戶提供服務(wù)，因此，R策略的期望收益可以表示為：

(15)

在非完美推薦場景下，模型的魯棒性是一個(gè)值得關(guān)注的問題.具體而言，本文希望可以找到錯(cuò)誤概率δ的臨界值δc，當(dāng)錯(cuò)誤概率高于該臨界值時(shí)，ALLD策略會(huì)占優(yōu)整個(gè)系統(tǒng).筆者之前的工作[4]討論了f=1時(shí)，δc的近似解.本文將進(jìn)一步討論f=0時(shí)，δc的求解.

當(dāng)f=0時(shí)，各個(gè)策略的期望收益如下所示：

ALLD策略占優(yōu)整個(gè)系統(tǒng)的充要條件為：

由于：

此時(shí)有：δ≥1-(β+γ)/α?xí)rALLD策略能夠占優(yōu)整個(gè)系統(tǒng).故δc=1-(β+γ)/α.注意該臨界值是一個(gè)近似解，它表示了ALLD策略能夠占優(yōu)整個(gè)系統(tǒng)的充分條件.

4.2 ALLC與R策略的識(shí)別

如果每個(gè)用戶都如實(shí)地公布自己所選擇的策略，那么服務(wù)提供者就可以很清楚地根據(jù)對(duì)手類型，從而做出相應(yīng)的反饋.然而，在更多的實(shí)際場景里，用戶往往是不會(huì)公布自己的策略，此時(shí)，就需要根據(jù)用戶間的交互歷史來推斷用戶的類型.在之前的文獻(xiàn)[4]里，筆者基于Eigentrust算法實(shí)現(xiàn)了用戶合作度的評(píng)估，然而，這種方法不能直接用作ALLC和R策略的識(shí)別，因?yàn)樗麄兊暮献鞫瓤赡芏紩?huì)很高.為了解決這一問題，本文提出了一種基于相似度的策略識(shí)別法.

首先引入Rij和Pij分別表示當(dāng)前時(shí)間步t里用戶i接收到的來自于用戶j的服務(wù)請(qǐng)求數(shù)量和用戶i為用戶j提供服務(wù)的數(shù)量.那么用戶i對(duì)用戶j的合作度可以表示為：

(16)

基于此，可以構(gòu)建出一個(gè)衡量用戶間合作度關(guān)系的N×N維的矩陣C=[cij].由于ALLC是一個(gè)無條件合作者，他/她會(huì)為任何用戶都提供服務(wù)，而R策略是不會(huì)為ALLD策略提供服務(wù)的，因此，可以通過衡量用戶之間的行為相似度來幫助R策略使用者進(jìn)行策略識(shí)別.

本文采用余弦相似度來計(jì)算任意兩個(gè)用戶i和j之間的行為相似度sim(i，j)：

sim(i,j)=

(17)

其中，comn(i,j)表示共同向用戶i和j發(fā)起過服務(wù)請(qǐng)求的用戶集合.隨后，本文引入一個(gè)閾值θ，當(dāng)兩個(gè)用戶的行為相似度大于θ時(shí)，可認(rèn)為二者采用了相同的策略，否則，可認(rèn)為二者采用了不同的策略.綜上，在本文提出的理性背叛模型中，R策略的行為可以由算法1表示.

算法1.基于相似度識(shí)別法的R策略行為決策

輸入：

i：R策略的服務(wù)提供者

j:服務(wù)請(qǐng)求者

輸出：

p：i對(duì)j提供服務(wù)的概率

1.基于文獻(xiàn)[4]，對(duì)j的合作度進(jìn)行衡量

2.ifj是一個(gè)背叛性用戶

3.p=0

4.else

5. 使用公式(17)計(jì)算i與j的相似度sim(i,j)

6.ifsim(i,j)>θ

7.p=1

8.else

9.p=f

10.returnp

5 實(shí)驗(yàn)及分析

本節(jié)將使用數(shù)值實(shí)驗(yàn)和仿真實(shí)驗(yàn)說明本文理性背叛模型的有效性，并對(duì)本文的理論分析進(jìn)行了驗(yàn)證.

5.1 參數(shù)設(shè)置

實(shí)驗(yàn)中的參數(shù)設(shè)置如表1所示.在本文模型里，獲得一個(gè)服務(wù)的收益α大于提供一次服務(wù)的損失β，為了和文獻(xiàn)[2-4,14]保持一致，實(shí)驗(yàn)取α=7和β=1.R策略采取推薦服務(wù)時(shí)需要付出一定的花費(fèi)γ，為了與筆者之前的文獻(xiàn)[4]保持一致，實(shí)驗(yàn)取γ=0.7.在本文提出的理性背叛模型中，R策略與ALLC策略進(jìn)行合作的概率為f，該值是一個(gè)從0到1的連續(xù)值.因?yàn)樵诂F(xiàn)實(shí)場景里，只有很小部分的用戶會(huì)及時(shí)去感知收益并進(jìn)行策略更新，因此實(shí)驗(yàn)設(shè)置學(xué)習(xí)率λ=0.01.在仿真實(shí)驗(yàn)中，系統(tǒng)中的用戶數(shù)量被設(shè)置為1000.在基于相似度的策略識(shí)別法里，實(shí)驗(yàn)將閾值θ分別設(shè)置為0.4,0.5,0.6和0.7.

表1 參數(shù)設(shè)置
Table 1 Parameters setting

參數(shù)定 義值α獲得一個(gè)服務(wù)的收益7β提供一個(gè)服務(wù)的損失1γ采用推薦服務(wù)的花費(fèi)0.7fR給ALLC提供服務(wù)的概率[0,1]λ學(xué)習(xí)率0.01N系統(tǒng)中的用戶數(shù)量1000θ相似度閾值0.4,0.5,0.6,0.7

5.2 f對(duì)模型的影響

首先進(jìn)行數(shù)值實(shí)驗(yàn)研究在完美推薦場景下f對(duì)模型的影響.圖1展示了GMLM學(xué)習(xí)機(jī)制下不同f值對(duì)應(yīng)的策略演化結(jié)果.從圖1(a)和圖1(b)中可知，當(dāng)f=0和f=0.8時(shí)，R策略都會(huì)占優(yōu)整個(gè)系統(tǒng)，使ALLD策略從系統(tǒng)中消失.而且，相比f=0.8場景，f=0時(shí)R策略可以獲得更好地收益，此時(shí)R策略可以更快地占優(yōu)整個(gè)系統(tǒng).如圖1(c)和圖1(d)所示，當(dāng)f≥0.9時(shí)，ALLC，ALLD，R會(huì)互相占優(yōu)并共存于系統(tǒng)之中.圖1的實(shí)驗(yàn)結(jié)果很好地驗(yàn)證了本文3.5節(jié)中提出的推論1至推論5.當(dāng)f取其他值時(shí)，策略演化結(jié)果是相似的，所以本文中就不進(jìn)行展示了.

圖1 GMLM學(xué)習(xí)機(jī)制下f對(duì)模型的影響[數(shù)值實(shí)驗(yàn)]Fig.1 Impact of f on the model with GMLM[numerical experiments]

圖2展示了CBLM學(xué)習(xí)機(jī)制下不同f值對(duì)應(yīng)的策略演化結(jié)果.與圖1(a)和圖1(b)相似，如圖2(a)和圖2(b)所示，在f=0和f=0.8設(shè)置下，R策略可以占優(yōu)整個(gè)系統(tǒng)，并且f值越小，R策略占優(yōu)系統(tǒng)所花費(fèi)的時(shí)間就越少.圖2(a)所展示的結(jié)果驗(yàn)證了本文3.5節(jié)中提出的推論6至推論8.與GMLM機(jī)制下的策略演化不同，如圖2(c)和圖2(d)所示，當(dāng)f=0.9和f=1.0時(shí)，ALLC，ALLD，R不僅會(huì)共存于系統(tǒng)之中，而且它們的比例會(huì)趨向于收斂.在之前的文獻(xiàn)[4]中，筆者已經(jīng)詳細(xì)地解釋了f=1.0時(shí)系統(tǒng)會(huì)進(jìn)行收斂的原因，此處就不贅述了.同樣地，當(dāng)f取其他值時(shí)，策略演化會(huì)呈現(xiàn)相似的結(jié)果，所以本文就不進(jìn)行展示了.

圖2 CBLM學(xué)習(xí)機(jī)制下f對(duì)模型的影響[數(shù)值實(shí)驗(yàn)]Fig.2 Impact of f on the model with CBLM[numerical experiments]

基于圖1和圖2兩個(gè)實(shí)驗(yàn)，可以發(fā)現(xiàn)：與不考慮理性背叛的模型(f=1.0)相比，考慮了理性背叛的模型(f<1)可以進(jìn)一步促進(jìn)合作的涌現(xiàn)，而且在本文參數(shù)設(shè)定下，當(dāng)f<0.9時(shí)，無論在GMLM還是CBLM學(xué)習(xí)機(jī)制下，ALLD策略都會(huì)從系統(tǒng)中消失，從而合作行為獲得了極大的激勵(lì).

為了驗(yàn)證數(shù)值實(shí)驗(yàn)的準(zhǔn)確性，本文還進(jìn)行了相應(yīng)的基于智能體的仿真實(shí)驗(yàn).圖3和圖4分別展示了用戶數(shù)量N=1000時(shí)，在GMLM和CBLM學(xué)習(xí)機(jī)制下，系統(tǒng)中策略的演化過程.通過對(duì)比可知，仿真實(shí)驗(yàn)取得了與數(shù)值實(shí)驗(yàn)一致的結(jié)果.當(dāng)N=5000，10000時(shí)，仿真實(shí)驗(yàn)也取得了相似的結(jié)果，本文就不進(jìn)行展示了.

圖3 GMLM學(xué)習(xí)機(jī)制下f對(duì)模型的影響[仿真實(shí)驗(yàn)]Fig.3 Impact of f on the model with GMLM[simulation experiments]

圖4 CBLM學(xué)習(xí)機(jī)制下f對(duì)模型的影響[仿真實(shí)驗(yàn)]Fig.4 Impact of f on the model with CBLM[simulation experiments]

5.3 非完美推薦

圖5 GMLM機(jī)制下的非完美推薦模型Fig.5 Imperfect recommendation model with CBLM

5.4 相似度策略識(shí)別

這里，通過仿真實(shí)驗(yàn)研究了本文機(jī)制在部署相似度策略識(shí)別法后的策略演化過程.如圖6(a)至圖6(d)所示,實(shí)驗(yàn)分別設(shè)置相似度閾值θ=0.4,0.5,0.6和0.7.此處設(shè)定用戶采用GMLM作為其策略學(xué)習(xí)機(jī)制.從圖6(a)和圖6(b)中可以發(fā)現(xiàn)，如果把閾值θ設(shè)置為一個(gè)較小的值時(shí)，R策略會(huì)大概率地將ALLC策略判斷成R策略(此時(shí)等價(jià)于將f設(shè)置成了一個(gè)較大的值)，并為他們提供服務(wù)，從而出現(xiàn)了如圖1(c)和圖1(d)所示的策略比例反復(fù)振蕩的現(xiàn)象.圖6(c)展示θ=0.6時(shí)的策略演化過程，在這種設(shè)定下，R策略可以較成功地進(jìn)行策略識(shí)別，所以剛開始時(shí)R策略的比例可以大幅度地增長，隨后，伴著ALLD策略的降低，R策略與ALLC策略的相似度會(huì)趨近于一致，因此R策略會(huì)大概率地將ALLC識(shí)別為R策略，進(jìn)而促進(jìn)了ALLC策略的增長.當(dāng)ALLC策略增長到一定程度后，ALLD策略會(huì)得到激勵(lì).最終也會(huì)出現(xiàn)策略比例反復(fù)震蕩的現(xiàn)象.從圖6(d)中可以發(fā)現(xiàn)，如果把閾值θ設(shè)置為一個(gè)較大的值時(shí)，R策略會(huì)出現(xiàn)自相傷害的情況，進(jìn)而不利于合作的產(chǎn)生.

圖6 基于余弦相似度的策略識(shí)別Fig.6 Strategy recognition based on cosine similarity

綜上，筆者認(rèn)為θ取0.6是一個(gè)比較好的選擇，在該設(shè)定下ALLD策略大部分時(shí)間內(nèi)都可以被很好地抑制.在未來的工作里，筆者在計(jì)算相似度時(shí)將引入時(shí)間等因素，希望可以進(jìn)一步提高策略識(shí)別的準(zhǔn)確性.

5.5 對(duì)比實(shí)驗(yàn)

這里，通過對(duì)比實(shí)驗(yàn)將本文提出的具有理性背叛屬性的推薦機(jī)制策略R與下列六種激勵(lì)策略進(jìn)行了性能比較：RIM[4],TFT[5],TF2T[6],WSLS[8],Mirror[9],Proportion[2].在比實(shí)驗(yàn)時(shí)，本文考慮了4500個(gè)用戶，每個(gè)策略初始化時(shí)都擁有500個(gè)用戶作為其策略種群.不失一般性，此處將R策略的合作參數(shù)f設(shè)置為0.如圖7所示，隨著系統(tǒng)的演化，R策略會(huì)逐漸戰(zhàn)勝其他六種激勵(lì)策略，并最終占優(yōu)整個(gè)系統(tǒng).在本文模型中，基于推薦機(jī)制，R策略能夠以更高的概率獲得服務(wù)，而且由于理性背叛機(jī)制的引入，R策略也避免了被ALLC策略所抑制，從而R策略可以在多策略對(duì)比實(shí)驗(yàn)中獲得不錯(cuò)的表現(xiàn).

圖7 多策略模型對(duì)比實(shí)驗(yàn)Fig.7 Performance comparison in a multi-strategies model

6 總結(jié)與展望

為了解決無條件合作策略對(duì)合作涌現(xiàn)的抑制現(xiàn)象，本文引入了理性背叛模型.在演化博弈框架下，針對(duì)兩種不同的用戶學(xué)習(xí)機(jī)制，本文研究了背叛概率對(duì)種群演化的影響，理論證明理性背叛機(jī)制的引入可以更好地促進(jìn)合作的產(chǎn)生.接著，針對(duì)實(shí)際場景，本文首先研究了非完美推薦下模型的魯棒性問題，然后，為了進(jìn)行策略區(qū)分，進(jìn)一步提出了基于相似度的策略識(shí)別法.數(shù)值實(shí)驗(yàn)和仿真實(shí)驗(yàn)都證明了理性背叛機(jī)制在合作促進(jìn)方面的有效性能.在部署相似度策略識(shí)別法時(shí)，發(fā)現(xiàn)在動(dòng)態(tài)演化的環(huán)境下準(zhǔn)確地判斷用戶類型不是有一件容易的事情，因此，筆者將會(huì)繼續(xù)對(duì)該問題進(jìn)行研究.