理性背叛的推薦合作激勵機制

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

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

1 引 言

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

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

2 相關(guān)工作

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

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

3 模型構(gòu)建

3.1 演化博弈

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

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

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

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

3.2 推薦機制框架

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

3.3 策略集

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

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

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

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

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

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

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

3.4 策略收益

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

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

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

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

首先計算ALLC策略的期望收益.

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

=α(x1+fx3)

(1)

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

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

(2)

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

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

(3)

同理，可以計算出t時刻ALLD和R策略的期望收益為：

(4)

(5)

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

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

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

(6)

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

3.5 演化過程

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

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

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

(7)

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

(8)

(α-β)(1-f)x1x3

(9)

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

(10)

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

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

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

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

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

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

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

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

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

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

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

證明：此時可以計算ALLD策略與ALLC策略的收益差為：

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

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

(11)

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

(12)

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

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

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

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

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

≥α(x2+x3)-β-γ

4 一些實際問題

4.1 非完美推薦

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

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

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

接下來，計算在第一類錯誤模型下各個策略的期望收益.首先是ALLC策略的期望收益.

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

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

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

(13)

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

(14)

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

(15)

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

當f=0時，各個策略的期望收益如下所示：

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

由于：

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

4.2 ALLC與R策略的識別

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

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

(16)

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

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

sim(i,j)=

(17)

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

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

輸入：

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

j:服務(wù)請求者

輸出：

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

1.基于文獻[4]，對j的合作度進行衡量

2.ifj是一個背叛性用戶

3.p=0

4.else

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

6.ifsim(i,j)>θ

7.p=1

8.else

9.p=f

10.returnp

5 實驗及分析

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

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

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

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

參數(shù)定 義值α獲得一個服務(wù)的收益7β提供一個服務(wù)的損失1γ采用推薦服務(wù)的花費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對模型的影響

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

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

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

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

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

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

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

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

5.3 非完美推薦

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

5.4 相似度策略識別

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

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

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

5.5 對比實驗

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

圖7 多策略模型對比實驗Fig.7 Performance comparison in a multi-strategies model

6 總結(jié)與展望

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