一種多維度的防護策略信任機制

一種多維度的防護策略信任機制

1子消費會展中的信任模型由于移動設(shè)備的廣泛應(yīng)用，計算請求的想法變得越來越真實。在通用計算應(yīng)用程序中，用戶以自組織的方式聚集在一起，用戶之間沒有先驗知識。信任模型在動態(tài)創(chuàng)建用戶關(guān)系方面發(fā)揮著重要作用。當(dāng)用戶熟悉另一個未知用戶時，交互式操作可以限制在有良好聲譽的用戶之間。如果用戶要求從其他未知用戶獲得服務(wù)，請向相鄰用戶請求相關(guān)服務(wù)提供商的推薦信息。如果計算出的服務(wù)提供商的信任低于安全訪問閾值，則用戶決定遠離服務(wù)商，而不是互動。然而在普適計算開放環(huán)境中,移動設(shè)備及用戶屬于不同的所有人或組織,大量應(yīng)用的激增更加劇了這種趨勢.大部分實體僅關(guān)注自身的利益,其唯一目標(biāo)就是最大化自身的利益,普適計算環(huán)境中這種實體的自私性導(dǎo)致信任模型在獲取推薦信息時遇到了困難.一是由于不愿消耗自身有限的資源,自私用戶不愿意提供推薦信息;二是推薦信息可能不真實,用戶可能為“同伙”提供較高的推薦值或為潛在的競爭者提供較低的推薦值.這兩種問題被稱為被動攻擊安全問題,極大地影響了信任模型的正常功能運作,而傳統(tǒng)的安全解決方式并不能解決此類問題.為達到促使推薦者積極提供真實推薦信息的目的,需要對自私用戶采取激勵措施.考慮以下場景:在一個大型的電子消費展覽會上,來自世界各地的參展者在整個大會期間時不時地隨機相遇并交換最新歌曲、游戲以及消息等.由于一些用戶可能在分享數(shù)據(jù)時傳播病毒或者木馬,信任模型被安裝在參展者的移動設(shè)備上并從以往的直接交互記錄及他人的推薦信息中計算每個用戶的信任值.信任模型的作用是決定可以同哪些用戶交互以及拒絕同不信任用戶交互.以往很多普適計算環(huán)境中的信任模型往往假定推薦信息是真實的,這將導(dǎo)致用戶在采納很多虛假推薦后做出錯誤的交互決定并遭受巨大的損失.因此,非常有必要將激勵機制應(yīng)用于信任模型中促使推薦者給出真實信息.此外,參展用戶共處交互的時間并不長,往往交換完數(shù)據(jù)或信息后就分開.此種情況下,很難讓推薦者長時停留、等到觀測實際交互結(jié)果與推薦信息是否一致時再給其激勵積分.這就要求激勵機制必須具有快速支付能力,推薦用戶的激勵積分須在實際交互結(jié)果可被觀測前獲得.為解決以上問題,本文借鑒經(jīng)濟學(xué)和政治學(xué)研究領(lǐng)域中的防護策略概念予以解決.在選舉或者拍賣時,每個選舉者(或者拍賣者)展現(xiàn)個人偏好,即給出優(yōu)先的候選者(或者出售物品)的報價.基于所有個人偏好,機制進行公共決策,得到一個被稱為社會選擇的全局結(jié)果.防護策略特性是指機制做出的社會選擇不能被某些用戶通過策略性虛假展現(xiàn)個人偏好隨意更改.實現(xiàn)防護策略特性的一種方法是設(shè)計魯棒性機制,即使用戶謊報個人偏好,社會選擇仍無法改變,這樣的機制被稱作不可篡改或抵抗篡改的.另一種實現(xiàn)方法是通過提供用戶激勵以促使用戶報告其真實信息,用戶只有在展現(xiàn)真實個人偏好時才能實現(xiàn)個體利益的最大化.這種機制被稱作激勵相容機制.一般地,針對自私用戶多采用設(shè)計激勵相容機制的方法實現(xiàn)策略防護特性.本文中,通過將信任決策過程看作公共決策過程,提出一個信任機制用以獲得自私用戶的真實推薦信息.該機制是一種基于具有防護策略特性的VCG(Vickrey-Clarke-Groves)機制.在決策過程中,推薦請求者向若干推薦者征求意見,這些意見反應(yīng)出推薦者對服務(wù)提供者的信任值,該信任值被看作是用戶的私有信息.當(dāng)獲得推薦意見后,請求者給予推薦者一定的激勵積分并依據(jù)所有推薦意見做出是否同服務(wù)提供者交互的最終決策.推薦者的收益包括兩部分:一是估值,表示對決策過程結(jié)果的評估;二是來自請求者的激勵積分.VCG機制保證推薦者只有在提供真實推薦信息時才能最大化自身的利益,因此對推薦者而言最好的選擇就是暴露自己的真實信任值.推薦者在自己獲取推薦過程中也可以使用積分激勵其他用戶提供真實推薦信息.文中提出的機制可以應(yīng)用于連續(xù)信任值信任模型,也可以應(yīng)用于二元離散信任值信任模型.此外,該機制也是一種快速機制,即積分是在交互結(jié)果可被觀測前支付.即使所有推薦者都提供真實推薦信息,也可能由于不同用戶存在不同信任評價標(biāo)準(zhǔn)導(dǎo)致對服務(wù)提供者的信任值不如預(yù)期一樣精確.本文應(yīng)用連續(xù)多數(shù)加權(quán)算法(weightedmajoritycontinuousalgorithm)來調(diào)整不同推薦值的權(quán)重從而減輕由于評價標(biāo)準(zhǔn)不同而導(dǎo)致的不精確問題.本文還從博弈論的角度研究了一般性的信任決策機制,討論了當(dāng)信任模型導(dǎo)出的社會選擇函數(shù)滿足何種特性時存在激勵相容的信任機制.應(yīng)用該機制,原有的信任模型可以保證用戶真實給出推薦信息.本文提出的基于VCG機制的防護策略信任機制可以被應(yīng)用在很多已有的信任模型中,促使推薦者給出真實推薦信息.本文第2節(jié)簡要介紹相關(guān)工作;第3節(jié)概述機制設(shè)計和VCG機制;第4節(jié)對基于VCG機制的信任機制進行詳細的闡述;第5節(jié)對一般信任決策機制進行討論;第6節(jié)通過模擬結(jié)果顯示機制的有效性;第7節(jié)總結(jié)全文.2信任模型求解策略類似如何從推薦者處獲得真實推薦信息,獲得真實私有信息的問題還出現(xiàn)在在線評分系統(tǒng)、拍賣系統(tǒng)和專家預(yù)測系統(tǒng)領(lǐng)域當(dāng)中.這里主要介紹在沒有中心服務(wù)器的分布式環(huán)境中,信任模型方面的相關(guān)工作.文獻的信任模型采用可傳遞信任的概念,即提供優(yōu)質(zhì)服務(wù)的實體也被認(rèn)為提供真實的推薦信息.然而,當(dāng)其推薦被認(rèn)為真實無誤時,優(yōu)秀的服務(wù)提供者也可能給其競爭者較低的評價.為了解決這種問題,許多信任模型將推薦信譽度同服務(wù)信譽度區(qū)分開,但仍無法從根本上改變推薦信息不真實的情況.當(dāng)前有3種方式來解決推薦信息不真實的問題.第1類解決方法的目的是減輕虛假推薦造成的偏差.Yu等人提出一種應(yīng)用多Agent系統(tǒng)的信任模型,該模型應(yīng)用D-S理論處理推薦反饋并應(yīng)用連續(xù)多數(shù)加權(quán)算法調(diào)整虛假推薦的比重,從而將虛假推薦的影響降至最低.虛假推薦的判定是通過比較推薦信息與實際直接交互結(jié)果得出的.然而,該信任模型假定惡意推薦者始終保持相同的行為模式并且僅考慮4種欺騙方式.第2類解決方法通過識別惡意推薦者并對其懲罰或隔離的方法實現(xiàn)真實推薦激勵.Liu等人提出普適計算環(huán)境中的激勵相容的beta信譽模型,該模型應(yīng)用beta分布計算二元事件的后驗概率.beta信譽模型同時考慮服務(wù)信譽度與推薦信譽度,前者通過服務(wù)提供者的聲明與實際經(jīng)驗的一致程度計算,后者反映出推薦信息的幫助程度.通過這兩種信譽度,實體被分成真實推薦者、惡意推薦者、懶惰真實推薦者、懶惰惡意推薦者和新用戶幾類.所有真實推薦者對待不同類推薦請求者的操作都是不同的,從而實現(xiàn)懶惰和惡意推薦者不能獲得足夠多且有效的推薦信息.盡管該機制十分有效,但仍然需要經(jīng)歷一段時間,懶惰和惡意推薦者才能被隔離,并不是真正意義上的激勵相容,即用戶必須每次給出真實推薦信息才不會被處罰.此外,該機制僅對二元信任模型有效.Chang等人也提出了一種同時包含服務(wù)信譽度與推薦信譽度的模型.同文獻中一樣,不同用戶也被分類并接受區(qū)別對待,如針對惡意推薦者采用以概率形式提供推薦信息.該信任模型的問題是新用戶容易被識別為懶惰用戶并難以獲得其他用戶的推薦信息.前兩類方法我們稱之為啟發(fā)式方法.啟發(fā)式方法是有效的,但未必是最優(yōu)的,即系統(tǒng)設(shè)計者無法通過形式化證明給出特定時刻的系統(tǒng)狀態(tài),只能保證經(jīng)過一段時間后,系統(tǒng)趨向一個理想的較優(yōu)態(tài)(大部分惡意節(jié)點被隔離或遭受懲罰).最后一類解決方法應(yīng)用經(jīng)濟學(xué)中博弈論與機制設(shè)計的方法對自私用戶進行分析并規(guī)范其行為操作.Papakonstantinou等人提出一種基于恰當(dāng)?shù)梅址▌t的機制從多個提供者處獲取并融合評價值.該機制具有兩個階段,實現(xiàn)了激勵相容與個體理性約束.然而,該機制需要中心服務(wù)器的存在而且支付是發(fā)生在實際結(jié)果觀測之后的.Abrams等人提出一種機制可以保證用戶不提供虛假推薦信息,然而該機制僅能保證用戶欺騙時不會獲得更大的收益,不能保證用戶誠實推薦時可以實現(xiàn)利益最大化.Jurca等人提出了一種基于二元信任值的信譽模型,該模型也滿足激勵相容約束.一個被稱作R實體的特殊代理者,向?qū)嶓w出售有關(guān)服務(wù)提供者的評價信息,并從其它實體那里購買其它的評價信息.購買時,代理僅在觀察并獲得到與報告一致反饋時才付給出售實體報酬.該方案的問題是實體可以因為服務(wù)提供者的表現(xiàn)改變而被認(rèn)為報告不實.另外一個主要問題是僅適用于二元信任系統(tǒng).Wang等人提出了一種類VCG機制的信譽系統(tǒng)用以激勵對等實體給出真實評價.該方案使用參考推薦網(wǎng)絡(luò)來推斷終端節(jié)點的可信度,網(wǎng)絡(luò)既包含功能信任也包含推薦信任.推薦的真實程度是由類VCG機制保證的,但該方案僅僅適用于可傳遞信任系統(tǒng)并且需要推薦網(wǎng)絡(luò)支持.此外,文獻提出一種基于VCG機制的防策略攻擊的信任模型,但該文獻僅提供了概念模型,并沒有給出實現(xiàn)細節(jié),也沒有對防策略攻擊的性質(zhì)進行證明.綜上所述,在信任模型中的真實推薦信息獲取方面,已有的研究成果仍存在一定局限性和依賴性,或者僅適用于二元信任系統(tǒng),或者需要推薦網(wǎng)絡(luò)的支持,或者不具有激勵支付的快速性,并不能完全滿足普適計算信任模型的策略防護性要求.3個體偏好、激勵形機制、個體社會策略本節(jié)簡要介紹機制設(shè)計與VCG機制的相關(guān)概念,更多內(nèi)容說明可參考文獻.機制設(shè)計研究的是如何設(shè)計一個博弈機制以實現(xiàn)期望的社會選擇.社會選擇是指整個社會群體性的選擇結(jié)果,此結(jié)果由諸多獨立博弈者通過表達各自偏好而聚集得出.社會選擇結(jié)果反過來會影響每個獨立博弈者的收益.如政治選舉中,每個選民表達自己的意愿偏好,選擇一位候選者當(dāng)選,所有選民的偏好聚集在一起共同決定了哪位候選者當(dāng)選,候選者上任后政策的實施會反過來影響選民的切身利益.從社會全局角度而言,希望達到所有個體成員利益之和最大.而從個體角度而言,只希望實現(xiàn)自己利益的最大化,個體可能通過謊報他人無法知道的私有偏好信息的方式達到操縱社會選擇結(jié)果并獲取更大自身利益的目的.激勵機制中使用支付來促使個體用戶真實報告其私有偏好信息.定義1.機制(mechanism).機制由兩部分組成,一是社會選擇函數(shù)(socialchoicefunction)f:V1×…×Vn→A將個體偏好映射為社會結(jié)果,二是支付函數(shù)向量(p1,…,pn),其中pi:V1×…×Vn→R代表個體付給機制的支付數(shù)額.定義2.估值函數(shù)(valuationfunction)、效用(utility)、支付(payment).個體偏好使用估值函數(shù)vi:A→R表示,函數(shù)值vi(a)∈R表示個體i在社會結(jié)果為a∈A時獲得的價值.個體的利潤用效用ui表示,是個體想要最大化的目標(biāo).效用的計算為ui=vi(a)-pi(vi,v-i),其中pi(vi,v-i)表示個體給機制的支付,由個體自身偏好和他人偏好v-i共同決定,也記作pi(v1,…,vn)或pi.定義3.激勵相容(incentivecompatible)約束、個體理性(individualrationality)約束、防護策略(strategy-proof)約束.對于每個個體i及每個偏好v1∈V1,…,vn∈Vn,個體i報告真實偏好vi時社會結(jié)果為a=f(vi,v-i),報告虛假偏好v′i時社會結(jié)果為a′=f(v′i,v-i),如果機制(f,p1,…,pn)對所有個體i滿足vi(a)-pi(vi,v-i)≥vi(a′)-pi(v′i,v-i),則該機制滿足激勵相容約束.如果所有個體的效用始終非負,即ui≥0,則該機制滿足個體理性約束.如果機制同時滿足激勵相容約束與個體理性約束,該機制被稱為滿足防護策略約束.在機制設(shè)計領(lǐng)域中,一個有名的激勵相容機制是VCG機制,該機制的社會選擇目標(biāo)是最大化社會福利,即全體參與個體的價值估值之和∑ivi(a).定義4.VCG(Vickrey-Clarke-Groves)機制.如果一個機制的社會選擇函數(shù)和支付函數(shù)滿足以下兩個條件,就被稱作VCG機制:(1)社會選擇函數(shù)最大化社會財富,即a=f(v1,?,vn)∈argmaxa∈A∑ivi(a).(2)對所有社會成員偏好vi∈V1,…,vn∈Vn,支付函數(shù)滿足以下形式:pi(v1,…,vn)=hi(v-i)-∑j≠ivj(a),其中hi:V-i→R是與個體偏好vi無關(guān)的函數(shù).通過將支付函數(shù)定義成與個體偏好聲明無關(guān)的形式,VCG機制實現(xiàn)了個體效用與整體社會財富的一致性,即個體僅在真實報告其私有偏好時才能實現(xiàn)個人效用最大化,同時實現(xiàn)社會財富最大化.如果社會選擇函數(shù)允許賦予不同偏好權(quán)值,則被稱作加權(quán)VCG機制.定義5.Clarke樞軸規(guī)則(Clarkepivotrule).Clarke樞軸規(guī)則定義了hi(v-i)=maxb∈A∑j≠ivi(b),則支付函數(shù)的形式為pi(v1,?,vn)=maxb∈A∑j≠ivj(b)-∑j≠ivj(a).Clarke樞軸規(guī)則規(guī)定了每個個體必須支付當(dāng)它參與和不參與時的社會財富之差,即它對其它參與者造成的損失.Clarke樞軸規(guī)則保證了VCG機制滿足個體理性約束且支付值非負,即ui≥0和pi≥0.4基于vcg機制的保護戰(zhàn)略的信任機制4.1推薦者的成本函數(shù)本小節(jié)給出防護策略信任機制并證明其是VCG機制.以共享音樂信息的普適計算應(yīng)用為例,每個用戶的移動設(shè)備運行信任模型,從直接交互與他人推薦結(jié)果計算出用戶的信任值.信任值ti∈,是從區(qū)間中任意取值的連續(xù)變量.由于信任值被當(dāng)作私有信息,如無明確請求,個體用戶間不會傳遞復(fù)制信任信息.當(dāng)請求者向推薦者詢問其對服務(wù)提供者的信任值時,推薦者將包含其私有偏好(即信任值)的推薦信息返給推薦者并獲得一定的積分.基于從鄰居用戶獲得的推薦值,推薦者做出基于服務(wù)提供者信任值的交互決策.當(dāng)同服務(wù)提供者交互時,請求者分享所有其他用戶對服務(wù)者的信任值以便服務(wù)提供者可以依據(jù)這些反饋意見進行服務(wù)改進.值得注意的是,文獻中推薦信息同時包括服務(wù)提供者的積極與消極觀察結(jié)果,從多個推薦者獲得的評估被認(rèn)為是相互關(guān)聯(lián)的并且不適合應(yīng)用VCG機制.與其不同,本文中盡管推薦信息都與同一個服務(wù)提供者相關(guān),但被看作不同推薦者的主觀意見,因此這些推薦意見之間是相互獨立的.在決策過程中,請求者合計自己對服務(wù)者的信任值tr與n個推薦值,得到一個總體信任值T,當(dāng)總體信任值大于某信任等級時,請求者決定同服務(wù)提供者交互,反之不然.信任等級以λ表示,總體信任值的計算方式為Τ=p(n∑i=1kiti)+qtr(1)其中ki,p,q分別是每個推薦、總推薦和自己信任值的權(quán)重,并且n∑iki=1,ki>0,p+q=1,p>0,q≥0.由于請求者進行交互時,服務(wù)者會獲得所有對它的評價.推薦者所給的推薦信息,尤其當(dāng)其為較低信任評價時,會使自己面對由于服務(wù)交互而產(chǎn)生的風(fēng)險損失,如服務(wù)提供者不共享音樂、對推薦者惡意低評或收取相應(yīng)額外積分的報復(fù).這種損失被看作一種成本,由線性成本函數(shù)表示ci=fci(ti)=μiti+ηi,μi<0,ci≥0(2)其中μi,ηi用來描述推薦者對這種風(fēng)險損失的重視程度.成本函數(shù)意味著推薦值越低,成本越高.這個假設(shè)是基于文獻中觀測的事實:(1)較高的推薦并不會惹惱服務(wù)提供者,因此推薦者傾向于提供較高的評價;(2)真實的低分評價往往基于長期交互,需要較多經(jīng)歷才能獲得;(3)給出低評時會有較高概率遭受報復(fù)打擊.本文假設(shè)每個用戶都采納相同的成本函數(shù)且為共同知識,即μi=μ,ηi=η.給定推薦的成本函數(shù),每個推薦用戶的推薦意愿可用推薦意見vi表示,其計算方式為vi=-ci=-μiti-ηi,μi<0,vi≤0(3)請求者獲得的推薦信息實際指其推薦意見vi,而非原始的信任值.推薦者的估值函數(shù)vi(a)在請求者決定同服務(wù)者交互時等于vi,在決定不交互時等于0.由于推薦會給推薦者帶來成本,請求者會付給推薦者一定的積分作為補償,此時,作為由推薦者付給機制執(zhí)行者(即請求者)的支付(payment)應(yīng)為負值.推薦者的效用可以表示為ui=vi(a)-pi(v1,?,vn),pi(v1,?,vn)≤0(4)當(dāng)決定交互時,請求者的估值是固定值-C,C<0,當(dāng)決定不交互時為0,C值的確定將稍后討論.此時,包括請求者和推薦者在內(nèi)的所有參與者的社會財富為∑ivi(a)-C,其值在交互與不交互兩種情況下分別等于∑ivi-C和0.整個信任決策過程可被看作一個社會選擇過程,其中所有推薦者表達個體推薦意見vi,并由請求者產(chǎn)生一個社會選擇結(jié)果a,即同服務(wù)提供者交互或者不交互.將個體推薦意見映射成為社會結(jié)果的社會選擇函數(shù),表示為a=f(v1,?,vn)={Ι?Τ≥λΝΙ?Τ<λ(5)其中,I表示社會選擇結(jié)果為交互,NI為不交互.為簡化問題,假設(shè)請求者為每個推薦賦予同樣的權(quán)值,即ki=k=1/n.值得注意的是,即使沒有這個假設(shè),該信任機制也是VCG機制.定理1.社會選擇函數(shù)f(v1,…,vn)實現(xiàn)了社會財富的最大化.證明.將式(1)代入到社會選擇函數(shù)f的條件中,得到p(n∑i=1kti)+qtr≥λ,n∑i=1ti≥λ-qtrkp.依據(jù)式(3),條件可變?yōu)?n∑i=1-μti-η)≥μqtr-λμkp-nη.令C=μqtr-λμ-npkηkp,則n∑i=1vi-C≥0(6)考慮社會財富在交互與不交互兩種情況下分別等于∑ivi-C和0.當(dāng)式(6)成立時,社會選擇函數(shù)f選擇交互的結(jié)果,達到更大的社會財富∑ivi-C.當(dāng)∑ivi-C<0,社會選擇函數(shù)f選擇不交互的結(jié)果,得到了較大的社會財富0.因此,式(5)中的社會選擇函數(shù)實現(xiàn)了社會財富的最大化.證畢.在獲得推薦信息做出決定后,請求者在與服務(wù)者交互前就將積分作為激勵返給推薦者.由于不需要觀測與服務(wù)者的交互結(jié)果,快速支付使得推薦獲取效率大為提高,更適合于普適計算環(huán)境用戶移動性的特點.給予的積分?jǐn)?shù)值等于支付的絕對值,積分被存儲起來用于推薦者以后從其他用戶處獲得真實推薦信息.由于估值及支付都是負值,Clarke樞軸規(guī)則不能直接應(yīng)用于信任機制,根據(jù)其原理,支付函數(shù)定義如下:pi(v1,?,vn)=maxb∑j≠ivj(b)-∑j≠ivj(a)+K,j=1,…,n+1(7)其中K=C保證支付是負值.基于不同的意見聲明(v1,…,vn)并考慮到vi<0,一共存在3種支付情形,如表1所示.依據(jù)不同個體聲明意見間的關(guān)系判定每種情形.只有在第Ⅲ種情行下,推薦者i稱為樞軸用戶,如沒有其參與,決策結(jié)果是進行交互,則maxb∑vi(b)=∑j≠ivj-C,如果其參與評價,請求者將決定不進行交互,則∑j≠ivi(a)=0.因此,此時推薦者i的支付為pi(v1,…,vn)=∑j≠ivj.當(dāng)推薦者i不是樞軸用戶時,其支付為C.考慮到∑ivi-C<0和∑ivi<0,請求者永遠不會成為樞軸用戶也不對自己進行支付.值得注意的是,在支付函數(shù)中,第n+1個用戶指請求者,并且a=I,vn+1(a)=-C.定理2.信任機制(f,p1,…,pn)滿足防護策略約束.證明.(激勵相容約束)對于信任值為ti,推薦意愿為vi的參與者i,須證明其聲明真實推薦意見vi時獲得的效用大于聲明虛假推薦意見v′i時的效用.這種情況下社會結(jié)果為a=f(vi,v-i)和a′=f(v′i,v-i).給予真實推薦時效用為ui=vi(a)-pi(vi,v-i)=vi(a)-maxb∑j≠ivj(b)+∑j≠ivj(a)-C=∑ivi(a)-C-maxb∑j≠ivj(b).給予虛假推薦時效用為u′i=vi(a′)-pi(v′i,v-i)=∑ivi(a′)-C-maxb∑j≠ivj(b).由于a=f(vi,v-i)最大化所有參與者的社會財富∑ivi(a)-C且maxb∑j≠ivj(b)與vi獨立無關(guān),所以ui>u′i.(個體理性約束)考慮3種支付情形,注意到C<0和vi≤0,則在第Ⅰ和第Ⅲ種情形中效用是非負的.對第Ⅱ種情形,∑ivi-C≥0,則∑ivi-C-∑j≠ivj≥-∑j≠ivj,注意到vj≤0,則vi-C≥0.所以,該機制滿足個體理性約束.證畢.對于激勵相容的信任機制,個體理性約束意味著如果一個推薦者做出推薦,不管決策結(jié)果如何,它都能從請求者處獲得積分.這有別于標(biāo)準(zhǔn)拍賣機制中,如果競標(biāo)失敗,不會發(fā)生任何支付.該性質(zhì)可以激勵推薦者分享其信任信息.4.2加權(quán)vcg信任機制由于只有報告真實推薦值時才能最大化自身利益,推薦者的最佳選擇就是誠實推薦,則請求者可認(rèn)為所有理性推薦者所做的推薦都是真實的.然而,對于提高決策預(yù)測準(zhǔn)確率而言僅僅滿足真實性要求還不夠,仍須考慮推薦者和請求者對服務(wù)者的信任判斷標(biāo)準(zhǔn).某些請求者認(rèn)為不好的服務(wù)者從推薦者信任的標(biāo)準(zhǔn)來看可能是可信的,這就會出現(xiàn)這樣的情況,即使所有推薦者都給出真實信息,信任預(yù)測結(jié)果對請求者而言還是不理想的.為此,須考慮請求者與推薦者的信任判定標(biāo)準(zhǔn)的相似性并調(diào)整不同推薦信息的權(quán)值.這里采用多數(shù)加權(quán)算法(WeightedMajorityAlgorithm,WMA)的變型算法連續(xù)多數(shù)加權(quán)算法(ContinuousWeightedMajorityAlgorithm,WMC)來調(diào)整權(quán)值.WMA算法首先定義一次實驗,在其中對于同一個實例,每個被稱為目標(biāo)函數(shù)的個體預(yù)測算法產(chǎn)生一個預(yù)測結(jié)果,一個設(shè)計的主算法為每個預(yù)測分配權(quán)值并將所有預(yù)測合計為一個總體預(yù)測.通過實際觀測或計算,主算法得到一個結(jié)果,稱作標(biāo)簽.所有權(quán)值通過乘上一個由個體預(yù)測和標(biāo)簽差異計算得出的因子實現(xiàn)更新.與WMA算法中個體預(yù)測與總體預(yù)測僅能取二元值不同,WMC算法允許從區(qū)間進行取值.對于信任機制,每個推薦者的信任值可被看作個體預(yù)測,實例即特定的服務(wù)提供者,也叫做上下文.每次信任決策是一次實驗,主算法是請求者計算總體信任的函數(shù),標(biāo)簽是同服務(wù)者進行交互后觀測計算的對服務(wù)者的直接信任值.令tis表示第i個用戶在實驗s中的預(yù)測,ρs表示實驗s的標(biāo)簽.由于每次涉及到的推薦者不同,主算法會不時發(fā)生改變,因此需引入絕對權(quán)值的概念,記作ωˉ(i,k)(i=1,?,n),表示獨立于主算法的推薦者i對服務(wù)者k預(yù)測的權(quán)值.初始時,所有絕對權(quán)值都設(shè)置為1.對于固定的主算法,令ωis(i=1,…,n)表示相對權(quán)值或標(biāo)準(zhǔn)權(quán)值,主算法可表示成Τ=p(∑i=1nωistis)+qtr.在上下文k下,相對權(quán)值的計算為ωis=ωˉ(i,k)∑inωˉ(i,k),i=1,?,n(8)令ωˉ(i,k)(s)(i=1,?,n)表示實驗s前的絕對權(quán)值,ωˉ(i,k)(s+1)(i=1,?,n)表示實驗s后的絕對權(quán)值.如果請求者交互后得出的標(biāo)簽為ρs,則絕對權(quán)值以以下方式進行更新ωˉ(i,k)(s)=θωˉ(i,k)(s+1)(9)其中,θ是任何滿足以下條件的因子β|tis-ρ(s)|≤θ≤1-(1-β)|tis-ρ(s)|(10)β(0≤β<1)是固定因子.這里選擇下界作為更新因子θ的值.由新的總體信任值計算方式Τ=p(∑i=1nωistis)+qtr得出的機制被叫作基于加權(quán)VCG的防護策略信任機制.可以看出,前面介紹的基于VCG的防護策略信任機制是當(dāng)僅存在一次實驗且對于任何主算法沒有權(quán)值更新的特例情況.對于加權(quán)VCG信任機制,式(5)中定義的社會選擇函數(shù)最大化的社會財富為∑iωisvi(a)-C′,其中C′=μqtr-λμp-η∑iωis.從請求者角度看,這意味著最大化那些較多推薦貢獻(權(quán)值較大)的推薦者的估值之和.加權(quán)VCG信任機制中支付函數(shù)的定義為pi(v1,?,vn)=maxb1ωis∑j≠iωjsvj(b)-1ωis∑j≠iωjsvj(a)+K′,j=1,…,n+1(11)其中Κ′=C′ωmin,ωmin=min{ω1s,?,ωn+1s}保證支付值為負值.加權(quán)VCG信任機制也是策略防護的,其證明過程與VCG信任機制一樣,故此省略.4.3主要情形下,各推薦者需要有足夠的支付函數(shù)請求者的估值是-C,而它付給所有推薦者的積分總和為-∑ipi,下面討論這兩者間的關(guān)系.定理3.當(dāng)有不少于2個推薦者時,請求者支付的積分總和一定不會小于其估值.證明.考慮情行Ⅲ中兩者間的大小-∑ipi-(-C)=-∑i(∑j≠ivj)+C=-∑i(∑jvj-vi)+C=(1-n)(∑ivi-C)+(2-n)C.考慮到此種情形下∑ivi-C<0,該值在不少于兩個推薦者時大于0.在情形Ⅰ和Ⅱ時,當(dāng)有不少于兩個推薦者時,-∑ipi-(-C)=(1-n)C>0,因此結(jié)論成立.證畢.支付的積分總和與估值之差可被看作推薦獲取過程的成本.該差值實際是由支付函數(shù)的形式?jīng)Q定.實際上,由于支付函數(shù)是由社會選擇函數(shù)唯一決定的,不存在可以消除差值的支付函數(shù).在文獻中證明了如果社會選擇函數(shù)最大化了社會財富,則使機制滿足防護策略約束的支付函數(shù)一定等同于依據(jù)Clarke樞軸規(guī)則得出的支付函數(shù).5一般信任和評估機制5.1信任決策機制設(shè)計下面從博弈論的角度給出信任決策機制的一般形式.定義6.信任決策機制(TrustedbasedDecisionMechanism,TDM).對于n個參與人,信任決策機制包含以下部分:(1)參與人的私有信任值空間T1,…,Tn;(2)參與人的意見空間X1,…,Xn;(3)參與人的判別策略函數(shù)si:Ti→Xi,該函數(shù)決定當(dāng)信任值為ti時所要報告的意見;(4)決策集A包含所有可能的決策結(jié)果;(5)參與人的估值函數(shù)vi:Ti×A→R;(6)用于做出決策的決策結(jié)果函數(shù)a:X1×…×Xn→A;(7)支付函數(shù)p1,…,pn,其中pi=X1×…×Xn→R.需要注意的是,TDM的一般形式中,參與人意見空間為k維的歐幾里德空間,即xi=(p1i,…,pki),p1i,…,pki∈R,其中p1i,…,pki代表k個相互獨立的信任評估參數(shù).例如,2維意見定義為xi=(Si,NSi),其中Si表示同特定服務(wù)提供者的成功交互次數(shù),NSi為不成功次數(shù).定義7.推薦游戲.對于給定的一個TDM,其對應(yīng)的推薦游戲由信任值空間Ti、意見空間Xi、判別策略si和效用函數(shù)ui:Ti×Xi×…×Xn→R共同組成,其中意見xi可看作參與者i的私有信任值為ti時采取的行動.如果對于所有的ti、s′i和x-i,ui(ti,si(ti),x-i)≥ui(ti,s′i(ti),x-i)都成立,則判別策略si叫做占優(yōu)策略.如果每個參與者的判別策略都是占優(yōu)策略,則策略組合s=(s1,…,sn)被稱作占優(yōu)(策略)均衡.定義8.信任決策函數(shù)(TrustbasedDecisionFunction,TDF).信任決策函數(shù)g:T1×…×Tn→A合計個體的信任值并做出一個(交互)決策.TDF是信任合計函數(shù)h與決策決定函數(shù)ψ的復(fù)合函數(shù),其中信任合計函數(shù)h:T1×…×Tn→T將個人信任值合計為總體信任值,決策決定函數(shù)ψ:T→A依據(jù)總體信任值做出決定并給出社會結(jié)果.定義9.實施.給定一個TDF,如果在一個TDM對應(yīng)的推薦游戲中,存在某個占優(yōu)均衡s=(s1,…,sn),使得對于所有的信任值t1,…,tn,g(t1,…,tn)=a(s1(t1),…,sn(tn)),則稱TDM實施了TDF,或TDF可由TDM實施.信任決策機制設(shè)計的目的就是構(gòu)造一個TDM,使其以下列方式實現(xiàn)TDF的實施:令n個參與人加入推薦游戲,報告各自的意見并接受支付.具有私有信任值的理性參與人選擇一個合適的判別策略以實現(xiàn)效用的最大化.如果所有參與人選擇占優(yōu)策略并導(dǎo)致占優(yōu)均衡,基于報告的意見,一個預(yù)定義的結(jié)果函數(shù)導(dǎo)出一個結(jié)果.那么,該結(jié)果一定同TDF以私有信任值為輸入得出的結(jié)果完全一致.下面以基于VCG的防護策略信任機制為例闡明信任決策機制的設(shè)計.在信任信譽系統(tǒng)中,需被實施的TDF定義如下:g(t1,?,tn)={Ι?Τ≥λΝΙ?Τ<λ(12)信任合計函數(shù)如式(1)中所示,是一個加權(quán)求和函數(shù),決策決定函數(shù)是一個簡單的二元決策函數(shù),當(dāng)總體信任大于閾值時選擇二元中的一個結(jié)果,否則選擇另一個結(jié)果.此外,還可以類似的方式構(gòu)造多元決策決定函數(shù).根據(jù)上節(jié)的描述,實施式(12)中TDF的基于VCG的信任決策機制可以如下構(gòu)造:信任值空間Ti和意見空間Xi都是取值范圍為區(qū)間的一維參數(shù),意見xi的值等于式(3)中計算的vi值.每個參與人的判別策略si都相同且為共同知識,也由式(3)定義.值得注意的是,基于VCG的信任決策機制中,判別策略是基于內(nèi)源的風(fēng)險成本給出的.在其它信任決策機制中,可以由其它的策略或者機制實現(xiàn).參與者可以選擇欺騙判別策略s′i而非真實判別策略si,就其私有信任值欺騙請求者,比如s′i(ti)=si(0.9ti).結(jié)果函數(shù)等同于以下社會選擇函數(shù):a(v1,?,vn)={Ι?∑ivi-C≥0ΝΙ?∑ivi-C<0(13)最后,支付函數(shù)如式(7)中所示.一般形式的信任決策機制是一種非直接顯示機制,這是因為僅有參與人的行動可以被觀測到,而不是其內(nèi)部狀態(tài),即私有信任信息.而滿足激勵相容約束的信任機制是一種直接顯示機制,因為報告的估值直接表示其內(nèi)在狀態(tài).但當(dāng)對于一般形式的信任決策機制存在占優(yōu)均衡時,每個參與者可以不考慮其他人的內(nèi)部狀態(tài)而進行選擇.這就意味著在一般形式的TDM實施TDF與信任決策滿足激勵相容約束間存在著對應(yīng)性,這種對應(yīng)性稱作信任機制的顯示原理.定義10.社會選擇函數(shù).當(dāng)判別策略si對每個參與人是公共知識時,對應(yīng)的社會選擇函數(shù)定義為TDF與逆函數(shù)s-1i的符合函數(shù),即f=g。si-1:V1×…×Vn→A,f(v1,…,vn)=(gue0c9s-1i)(v1,…,vn)=g(s-11(v1),…,g(sn-1(vn)).命題1.信任機制顯示原理.如果存在一般性的TDM以占優(yōu)策略實施了TDF,那么就存在一個滿足激勵相容約束的信任機制實施了對應(yīng)的社會選擇函數(shù).激勵相容信任機制中的支付函數(shù)與TDM均衡中得到的支付函數(shù)等同.由于信任機制顯示原理同普通機制顯示原理的證明十分相似,故此省略.5.2單參域vi本節(jié)討論信任決策機制的特性,特別的,考察哪些TDF可被TDM以占優(yōu)均衡的方式實施,這樣的TDF被稱作是可實施的.根據(jù)信任機制顯示原理,這個問題等同考察哪些對應(yīng)的社會選擇函數(shù)可以被激勵相容信任機制實施.社會選擇函數(shù)的可實現(xiàn)性取決于函數(shù)的輸入域,即偏好Vi的取值域.對于不同的偏好取值域,可實施的特性是不同的.對一個k維偏好vi=(p1i,…,pki),如果p1i,…,pki可取任何實數(shù)值,偏好取值域Vi被稱作非限制域并記為Vi=R|A|.如果取值域上有限制條件,偏好取值域被稱作受限域.如果整個偏好向量vi完全由一個參數(shù)決定,偏好取值域稱為單維域,單維域是一種受限域,因為僅有一個保留參數(shù),其它參數(shù)不允許取任何值并都被TDF忽略.在基于VCG的激勵相容信任機制及其它很多信任機制中,參與人的偏好是單維域,也稱為單參域.定義11.單參域.令集合I?A表示共知的交互集合,該集合中的結(jié)果元素表示同服務(wù)提供者進行交互.單參域Vi由集合I與取值范圍[s0,s1]定義.Vi是滿足如下條件的vi的集合:對所有a∈I,vi(a)=s,s0≤s≤s1,對所有的a?I,vi(a)=0,即Vi={v1|vi(a)=s∧a∈I∨vi(a)=0∧a?I}.由于信任決策機制與普通機制的特性是等同的,這里引用普通機制中的可實施特性理論加以說明.單參域的可實施特性由文獻給出,特性包括對社會選擇函數(shù)與支付函數(shù)的要求:信任機制(f,p1,…,pn)滿足激勵相容約束的充要條件為:(1)對每個vi社會選擇函數(shù)f滿足單調(diào)性要求;(2)如果結(jié)果a∈I,每個樞軸用戶須給予關(guān)鍵值數(shù)量的支付.非限制領(lǐng)域上的可實施特性由Robert規(guī)則給出,值得注意的是,Robert規(guī)則考慮的拍賣與選舉的場景下,社會結(jié)果的基數(shù)與個人偏好的基數(shù)需相同,而信任決策機制中,不存在這種要求.對于非限制域與單參域間的受限域的特性,依據(jù)偏好取值域的不同,特性也隨之不同,普通機制特性的部分結(jié)果可以在文獻找到.通過研究可實施特性,如果社會選擇函數(shù)滿足這些要求,則可以設(shè)計出一個實施其的激勵相容信任機制.因此,如果以特定的信任模型為目標(biāo),希望信任模型的推薦者都真實報告其私有信息,首先依據(jù)目標(biāo)信任模型中的信任合計函數(shù)與決策決定函數(shù)構(gòu)造TDF,其次檢驗TDF對應(yīng)的社會選擇函數(shù)是否滿足可實施特性,如果滿足,則可以構(gòu)造一個滿足激勵相容約束的信任機制,將其與目標(biāo)信任模型結(jié)合以實現(xiàn)真實信任推薦的目的.6多次推薦的評估較以往無法確定特定時刻系統(tǒng)狀態(tài)、有效但未必最優(yōu)的啟發(fā)式解決方法而言,基于機制設(shè)計的VCG信任機制可以保證對自私用戶,系統(tǒng)始終處于最優(yōu)狀態(tài),即任意時刻系統(tǒng)內(nèi)所有誠實用戶實現(xiàn)占優(yōu)均衡,且社會財富始終最大化,理論上說明了機制的最優(yōu)性.限于篇幅,本節(jié)主要通過模擬實驗結(jié)果顯示機制的最優(yōu)有效性.驗證應(yīng)用JIST/SWANS模擬器對普適計算環(huán)境底層的移動自組織網(wǎng)絡(luò)(MobileAdhocNetworks,MANETs)進行模擬.模擬面積為400m×400m的場所中包含40個用戶節(jié)點,移動性以最低速2m/s、最高速10m/s的隨機路徑點模型表示.節(jié)點都被編號,21號節(jié)點和30號節(jié)點為服務(wù)提供者,19號節(jié)點為請求者,1號到10號節(jié)點都是推薦者且只有1號為欺騙節(jié)點,策略性地給出虛假推薦.所有虛假推薦意見的偏差類型總結(jié)在表2之中,如2型偏差指節(jié)點1的匯報意見比其真實信任值高0.1.節(jié)點的匯報