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

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

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

1 引 言

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

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

2 相關工作

為了解決合作困境，研究者們進行了大量的激勵機制研究.根據之前的文獻，激勵機制研究主要包含兩方面的內容：金錢獎勵機制和互惠機制.在金錢獎勵機制中，合作者可以通過提供服務獲取物質報酬，因其高效性和簡單性，該機制已廣泛應用于實際的協作系統中，例如：滴滴網約車平臺，亞馬遜在線工人平臺，等等.在很多沒有設置金錢獎勵的協作系統里，互惠機制發揮了極其重要的作用.根據交互對象的特點，互惠機制可以分為：直接互惠和間接互惠.在直接互惠中，交互雙方是保持不變的，其核心思想是“我幫助你，你幫助我”.一報還一報策略(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更好的性能.在間接互惠中，交互雙方是動態變化的，其核心思想是“我幫助別人，別人幫助我”.針對大規模P2P文件共享場景，Feldman提出了Mirror策略[9]，當該策略使用者接收到一個服務請求后，他/她會計算該交互對手為別人提供服務的概率，然后以相同的概率為該交互對手提供服務.隨后，Zhao等人[2]提出了Proportion策略，該策略使用者會計算交互對手提供的服務數量與其獲得的服務數量的比例，并以該比例值作為自己與他人進行合作的概率，理論和實驗證明，相比Mirror策略，Proportion策略能夠更好地促進合作.Wang等人[3]研究了花費對Proportion策略性能的影響.Li等人[4]提出了基于推薦的合作激勵策略(Recommendation Incentive Mechanism，RIM),該策略使用者在推薦機制的幫助下提高了自身與合作性節點交互的可能性，進而可以獲得更高的收益，理論和實驗證明，相比WSLS，Mirror和Proportion策略，RIM策略具有更好地促進合作的性能.在文獻[4]的基礎上，本文進一步引入了理性背叛機制，以解決互惠策略被無條件合作策略所抑制的這一問題，進而希望可以進一步促進合作的涌現.

另一方面，網絡結構對參與者合作行為的影響目前也引起了廣泛的關注，研究者們發現在網格網絡[10]，無標度網絡[11]，小世界網絡[12]等結構化的網絡中合作行為可以得到一定程度的促進.

3 模型構建

3.1 演化博弈

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

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

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

基于以上兩個特點，本文將使用演化博弈作為模型的基礎框架來描述大規模協作系統里用戶的交互過程.

3.2 推薦機制框架

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

3.3 策略集

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

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

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

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

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

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

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

3.4 策略收益

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

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

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

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

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

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

=α(x1+fx3)

(1)

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

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

(2)

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

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

(3)

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

(4)

(5)

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

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

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

(6)

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

3.5 演化過程

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

3.5.1 GMLM學習機制

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

(7)

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

(8)

(α-β)(1-f)x1x3

(9)

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

(10)

定義1.在收益指導下，如果si策略能夠最終被所有理性用戶選擇，即xi=1，那么可稱si策略占優了整個系統.

推論1.在GMLM下，ALLC策略不能占優整個系統.

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

推論2.在GMLM下，ALLD策略不能占優整個系統.

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

推論3.在GMLM下，當f≥1-γ/α時，R策略不能占優整個系統.

證明：這里使用反證法.假設當f≥1-γ/α時，R策略能夠占優整個系統.那么在x1→0，x2→0，x3→1時，下列3個不等式將會成立：

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

推論4.在GMLM下，當f=1時，那么ALLC，ALLD和R策略都不能占優整個系統.

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

推論5.在GMLM下，當f=0時，那么R策略會占優整個系統.

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

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

3.5.2 CBLM學習機制

(11)

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

(12)

推論6.在CBLM下，ALLC策略不能占優整個系統.

證明：這里使用反證法.假設在CBLM下，ALLC策略能夠占優系統，那么有：

推論7.在CBLM下，ALLD策略不能占優整個系統.

證明：這里使用反證法.假設在CBLM下，ALLD策略能夠占優系統，那么有：

推論8.在CBLM下，當x2+x3>(β+γ)/α時，R策略能夠占優整個系統.

≥α(x2+x3)-β-γ

4 一些實際問題

4.1 非完美推薦

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

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

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

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

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

與之相對應地，ALLC策略的期望損失更新為：

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

(13)

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

(14)

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

(15)

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

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

ALLD策略占優整個系統的充要條件為：

由于：

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

4.2 ALLC與R策略的識別

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

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

(16)

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

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

sim(i,j)=

(17)

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

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

輸入：

i：R策略的服務提供者

j:服務請求者

輸出：

p：i對j提供服務的概率

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 實驗及分析

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

5.1 參數設置

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

表1 參數設置
Table 1 Parameters setting

參數定 義值α獲得一個服務的收益7β提供一個服務的損失1γ采用推薦服務的花費0.7fR給ALLC提供服務的概率[0,1]λ學習率0.01N系統中的用戶數量1000θ相似度閾值0.4,0.5,0.6,0.7

5.2 f對模型的影響

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

圖1 GMLM學習機制下f對模型的影響[數值實驗]Fig.1 Impact of f on the model with GMLM[numerical experiments]

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

圖2 CBLM學習機制下f對模型的影響[數值實驗]Fig.2 Impact of f on the model with CBLM[numerical experiments]

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

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

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

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

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

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

5.5 對比實驗

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

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

6 總結與展望

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