岳朝躍,田有亮,張鐸,王琳杰,王纘

1.貴州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,貴陽 550025

2.貴州大學(xué) 公共大數(shù)據(jù)國家重點(diǎn)實(shí)驗(yàn)室,貴陽 550025

3.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴陽 550025

1 引言

在當(dāng)今以數(shù)據(jù)為中心的世界中,為了提供更優(yōu)質(zhì)的服務(wù),許多應(yīng)用程序會收集大量的用戶數(shù)據(jù).然而,處理所收集的數(shù)據(jù)往往是一項(xiàng)非常復(fù)雜的任務(wù),這要求處理數(shù)據(jù)的公司或者個(gè)體必須具備強(qiáng)大的計(jì)算能力.隨著分布式計(jì)算和云計(jì)算的快速發(fā)展,出現(xiàn)了新型的計(jì)算模式:分包計(jì)算及外包計(jì)算.這類計(jì)算模式將任務(wù)外包給遠(yuǎn)程服務(wù)器使得公司或個(gè)體不再受自身計(jì)算和存儲能力的限制.它已成為云計(jì)算時(shí)代解決此類問題的主要方案.在外包計(jì)算中,面臨兩個(gè)主要問題:一是計(jì)算結(jié)果的完整性,對用戶而言,服務(wù)器可能返回一些虛假的計(jì)算結(jié)果,如作弊計(jì)算、猜測結(jié)果等;二是計(jì)算任務(wù)的隱私性,對不可信的第三方,云服務(wù)器獲取了用戶的輸入及輸出,如何保證用戶隱私信息的安全性.

目前,在傳統(tǒng)外包計(jì)算方案中,為了驗(yàn)證計(jì)算結(jié)果的完整性、可靠性,已經(jīng)設(shè)計(jì)了許多驗(yàn)證機(jī)制.但對于傳統(tǒng)的外包計(jì)算主要是基于計(jì)算復(fù)雜性理論和基于密碼技術(shù)構(gòu)造.基于計(jì)算復(fù)雜性的外包計(jì)算方案構(gòu)造中主要應(yīng)用的工具是交互式證明系統(tǒng)[1,2]、PCP定理[3]等.基于密碼技術(shù)構(gòu)造的外包計(jì)算方案中,使用的密碼工具主要有全同態(tài)加密[4,5]、同態(tài)MAC/簽名[6]等.在這些傳統(tǒng)的外包計(jì)算方案中,用戶需要依據(jù)服務(wù)器的可靠證據(jù)對計(jì)算結(jié)果進(jìn)行驗(yàn)證.但是,一般驗(yàn)證過程很復(fù)雜且通信復(fù)雜度較高.同時(shí),傳統(tǒng)的外包計(jì)算一般都是假設(shè)參與者要么是誠實(shí),要么是惡意的行為.然而,在實(shí)際生活中,參與者都具有一定的偏好取向.因此,引入理性參與者,通過效用函數(shù)來保證服務(wù)器計(jì)算結(jié)果的完整性,構(gòu)造外包計(jì)算博弈模型更具有實(shí)際意義和研究價(jià)值.

近年來,從理性的視角出發(fā)研究理性參與者的外包計(jì)算受到越來越多學(xué)者的關(guān)注.為了確保計(jì)算結(jié)果的完整性,1999年,Monrose[7]等設(shè)計(jì)了一個(gè)驗(yàn)證方案,要求重新執(zhí)行部分計(jì)算任務(wù).2011年,Canetti[8]等利用多個(gè)代理人的冗余來驗(yàn)證外包計(jì)算結(jié)果,要求至少有一個(gè)代理人是誠實(shí)的.2014年,Vaidya[9]等設(shè)計(jì)了一個(gè)博弈論框架來改進(jìn)現(xiàn)有的驗(yàn)證機(jī)制,該機(jī)制只考慮到服務(wù)器的決策模型,沒有考慮到用戶的策略.Pham[10]等從經(jīng)濟(jì)學(xué)的角度對外包驗(yàn)證計(jì)算進(jìn)行研究,并建立了確定外包合同價(jià)格最優(yōu)模型,分析了一個(gè)和多個(gè)服務(wù)器的情況,要求服務(wù)器完全誠實(shí),但這并不完全符合實(shí)際情況.為此,Khouzani[11]等進(jìn)一步研究了在允許多服務(wù)器共謀情況下設(shè)計(jì)了外包驗(yàn)證方案的最佳設(shè)置,該文獻(xiàn)也未考慮用戶可以容許有一定錯(cuò)誤率.2017年,Pejó[12]等設(shè)計(jì)了一個(gè)外包計(jì)算博弈論框架,并使外包商的效益最大化,同時(shí)確保外包計(jì)算的完整性達(dá)到所期望滿足的完整性水平,要求在檢測結(jié)果沒有錯(cuò)誤時(shí)強(qiáng)制執(zhí)行罰款,且罰款為事先給定的常數(shù),這導(dǎo)致不能很好的激勵(lì)服務(wù)器誠實(shí)計(jì)算,并且要保證計(jì)算結(jié)果滿足用戶期望的完整性,用戶必須驗(yàn)證該返回的結(jié)果.

針對目前研究現(xiàn)狀中,懲罰函數(shù)設(shè)計(jì)不足以及服務(wù)器返回結(jié)果必須要經(jīng)過本地驗(yàn)證等問題.本文將外包計(jì)算與博弈論相結(jié)合提出理性外包計(jì)算的新模型.在博弈論框架下,分析外包計(jì)算中用戶和服務(wù)器的偏好,提出了外包計(jì)算的擴(kuò)展式博弈,定義了一個(gè)新的支付矩陣和效用函數(shù),根據(jù)博弈的納什均衡給出了理性外包計(jì)算模型的形式化定義;并通過實(shí)驗(yàn)仿真分析了理性外包計(jì)算模型中線性函數(shù)的選取條件,確保參與者達(dá)到納什均衡時(shí)用戶不再驗(yàn)證外包計(jì)算結(jié)果,也可以確保服務(wù)器計(jì)算的結(jié)果滿足用戶期望的完整性水平.

本文的結(jié)構(gòu)如下:第2節(jié)簡要介紹博弈論、外包計(jì)算擴(kuò)展式博弈;第3節(jié)基于外包計(jì)算擴(kuò)展式博弈,定義一個(gè)新的支付矩陣和效用函數(shù);第4節(jié)理性外包計(jì)算模型的形式化定義;第5節(jié)對外包計(jì)算博弈模型進(jìn)行仿真實(shí)驗(yàn)與分析;第6節(jié)總結(jié)全文內(nèi)容.

2 準(zhǔn)備知識

本節(jié)概述博弈和擴(kuò)展式博弈、納什均衡[13]等基礎(chǔ)知識.

2.1 博弈概念

定義1(博弈)博弈表達(dá)的基本形式由局中人P、策略空間S和效用函數(shù)u三個(gè)要素組成,即G={P,S,u},其中P={P1,P2,···,Pn},S={S1,S2,···,Sn},u={u1,u2,···,un}.效用函數(shù)ui:S→R(代表實(shí)數(shù)空間),它表示第i位局中人在不同策略組合下所得到的效益.

2.2 擴(kuò)展式博弈

一個(gè)擴(kuò)展式博弈(extensive game)是一個(gè)五元組(P,Q,p,(Ii)i∈p,(≤i)i∈p),其中,

(1)P代表參與者集合;

(2)Q代表行動序列集合,且滿足如下的性質(zhì):

若q是有限行動序列即a是一個(gè)行動,則q·a記為行動a為q的直接后繼行動.如果q∈Q行動是無限的或者它的直接后繼行動為?,則稱其為終端(termianal).由終端序列組成的集合記為Z.對于任意的q∈Q,A(q)={a:q·a∈Q}為q的所有可能后繼行動組成的集合.

(3)p是參與者函數(shù),它賦給每一個(gè)非終端序列(q∈Q的元素)一個(gè)P的元素.

(4)Ii代表參與者i∈P的信息集,它表示參與者進(jìn)行選擇時(shí)所知道的信息.

(5)≤i代表參與者的偏好關(guān)系:對于每一個(gè)i∈P有一個(gè)Z上的偏序關(guān)系.

擴(kuò)展博弈的解釋如下:每一個(gè)Q中行動序列代表博弈的可能歷史.空序列?代表博弈的開始節(jié)點(diǎn).當(dāng)達(dá)到任何非終端行動序列q∈Q后,參與者p(q)從A(q)中選擇行動a,從而序列q被行動a擴(kuò)展,此時(shí)博弈的歷史變成q·a.終端集合Z代表博弈所有可能的結(jié)果(outcome).若q,q′∈Z和q≤i q′,則參與者i∈P更偏向于q′.參與者的偏序關(guān)系依其效用函數(shù)而定:一個(gè)實(shí)向量y(q)=(yi(q))i∈P被賦值到每一個(gè)終端序列下,并有任意q,q′∈Z和i∈P,q≤i q′,當(dāng)且僅當(dāng)y(q)≤i y(q′).

通常來說,一個(gè)擴(kuò)展博弈可以看成一棵博弈樹,博弈樹的邊和節(jié)點(diǎn)分別對應(yīng)博弈行動和行動序列.空序列?代表該樹的根.博弈始于空序列及終于終端節(jié)點(diǎn)(也稱樹葉).參與者p(q)從A(q)中選擇行動,從而序列q被行動a擴(kuò)展,此時(shí)博弈的歷史變成q·a.當(dāng)一個(gè)行動序列達(dá)到終端節(jié)點(diǎn)時(shí),則博弈結(jié)束.終端節(jié)點(diǎn)(葉子)用收益向量標(biāo)識以代表參與者之間的偏好關(guān)系.

2.3 納什均衡

定義2(納什均衡)一個(gè)策略組合s?=()是博弈G={P,S,u}的一個(gè)納什均衡,如果對于每一個(gè)局中人Pi(i=1,···,n),對于所有的sj∈Si,不等式都成立.

直觀理解,如果每一個(gè)參與者i/=j遵從策略,則參與者j也不會背離,因?yàn)樗畴x該策略得不到任何好處.一般情況下,一個(gè)博弈可能存在多個(gè)納什均衡.

3 外包計(jì)算博弈模型

3.1 模型參數(shù)

本文中使用的模型參數(shù)如表1所示.

表1 本文所使用的參數(shù)Table 1 Parameters used in this study

假設(shè)用戶擁有計(jì)算任務(wù)A和計(jì)算函數(shù)f(·).計(jì)算任務(wù)A的價(jià)值為B.用戶將計(jì)算任務(wù)外包給服務(wù)器,服務(wù)器誠實(shí)計(jì)算該任務(wù)的成本為M.計(jì)算輸出的結(jié)果為0＜K∈Z,這些輸出結(jié)果由用戶單獨(dú)驗(yàn)證,如在推薦算法[14,15]中,這K個(gè)結(jié)果表示服務(wù)器為用戶最終預(yù)測的結(jié)果.從博弈論的觀點(diǎn)來看,理性外包計(jì)算實(shí)際上用戶和服務(wù)器之間的博弈.將這問題轉(zhuǎn)化為模型化,用戶的一方希望不需要驗(yàn)證就可以保證計(jì)算結(jié)果滿足用戶期望的完整性,而服務(wù)器一方希望通過誠實(shí)計(jì)算獲得更大的獎(jiǎng)勵(lì)或者節(jié)約成本以來實(shí)現(xiàn)自己利益最大化.由于用戶和服務(wù)器之間處于信息不對稱狀態(tài),用戶無法對服務(wù)器的行為進(jìn)行監(jiān)管和控制,也無法觀測到服務(wù)器的作弊程度.基于此我們分別考慮用戶和服務(wù)器的驗(yàn)證策略a和作弊策略b,假設(shè)a,b為輸出K個(gè)結(jié)果的百分比,記為

簡單來看,可以將理性外包計(jì)算模型分成兩部分,即用戶和服務(wù)器.建立外包計(jì)算博弈機(jī)制的目的就是保證外包計(jì)算結(jié)果的完整性和可靠性,同時(shí)及時(shí)檢測服務(wù)器的作弊情況,并將服務(wù)器的作弊率降到最低.這一過程中可能會出現(xiàn)以下的情況,服務(wù)器作弊了,但是用戶未檢測到P0,我們稱為檢測率.反之為檢測到作弊的概率記為P1,下面我們在方程式(1)分別定義了用戶沒有檢測到服務(wù)器作弊的概率P0(a,b)和檢測到作弊的概率P1(a,b)為:

在外包計(jì)算任務(wù)中保證計(jì)算結(jié)果正確性和可靠性是“沒有免費(fèi)的午餐”,我們必須付出一定的“代價(jià)”而得到相應(yīng)的安全計(jì)算服務(wù).對于用戶來說,有些不重要的計(jì)算任務(wù)容許有一定作弊計(jì)算,設(shè)該容忍度為用戶的容忍率θ.為保證計(jì)算質(zhì)量,用戶需要給予適當(dāng)?shù)膱?bào)酬來激勵(lì)服務(wù)器誠實(shí)計(jì)算.設(shè)用戶給服務(wù)器的支付費(fèi)用為W(b),其中W(b)是關(guān)于b的線性單調(diào)減函數(shù);同時(shí)為了保證計(jì)算結(jié)果的正確性、可靠性.用戶可能選取部分結(jié)果在本地執(zhí)行驗(yàn)證,這里的驗(yàn)證是指用戶重新計(jì)算,驗(yàn)證的成本V(a)為是關(guān)于a線性增函數(shù),且滿足V(0)=0,V(1)=M.為了保證用戶愿意外包計(jì)算任務(wù),假設(shè)B-V(a)-W(b)≥0.否則就會失去外包計(jì)算的意義.對于服務(wù)器而言,它可能通過節(jié)約成本或者誠實(shí)計(jì)算獲得的獎(jiǎng)勵(lì)來增加自己的收益.我們設(shè)置了一個(gè)懲罰機(jī)制,以防止服務(wù)器有作弊的動機(jī).假設(shè)F(b)是用戶在驗(yàn)證返回的結(jié)果中發(fā)生作弊時(shí)對服務(wù)器的懲罰,其中罰款是關(guān)于服務(wù)器作弊概率b的增函數(shù).如果合同本身沒有約束力,這種罰款可以通過引入第三方來強(qiáng)制執(zhí)行.

服務(wù)器作弊計(jì)算,對于用戶來說就會存在一定的損失,我們稱為用戶的損失因子.如果作弊被捕獲到,我們設(shè)捕獲到作弊時(shí)對用戶利益的損失設(shè)為km(b),即用戶此時(shí)的利益為B-km(b);如果作弊未被捕獲到時(shí)對用戶利益的損失設(shè)為λm(b),即用戶此時(shí)的利益為B-λm(b),其中λm(b)和km(b)都是關(guān)于b的線性單調(diào)增函數(shù),且滿足km(0)=λm(0)=0,λm(1)≥km(1)≥m,即沒有作弊就沒有損失;完全作弊(b=1)的損失至少是用戶的純收入m,同時(shí)這里還必須滿足:對于任意的b∈[0,1],有km(b)≤λm(b),如果未捕獲到作弊的損失因子λm(b)小于捕獲到作弊的損失因子km(b),即是“無知就是幸?！?這是不切實(shí)際的.

3.2 參與者偏好

在理性外包計(jì)算中,參與者存在差異性和特殊性,因此必須遵守自身效益最大化這一原則.服務(wù)器誠實(shí)計(jì)算時(shí),用戶收益最大,即服務(wù)器不作弊時(shí)的收益高于欺騙時(shí)的收益.此時(shí),用戶的效用函數(shù)滿足如下不等式:

同時(shí),服務(wù)器也期望自己的收益最大.而服務(wù)器的收益來源于誠實(shí)計(jì)算時(shí)用戶給予的支付及節(jié)約的成本.因此,服務(wù)器作弊的概率不超過用戶的容忍率.即作弊概率為容忍率θ時(shí)的收益超過作弊概率?b≥θ的收益.此時(shí),服務(wù)器的效用函數(shù)滿足如下不等式:

3.3 博弈模型設(shè)計(jì)

兩方或者多方之間的外包計(jì)算可以看作是兩方或多方實(shí)體間并遵守一定規(guī)則的交互計(jì)算集合,在外包計(jì)算過程中,為了達(dá)到某種計(jì)算目的(如計(jì)算結(jié)果完整性、可靠性),他們必須一次或者多次遵守所規(guī)定的交互規(guī)則,若有實(shí)體違背這些規(guī)則,最終導(dǎo)致外包計(jì)算的目的失敗.我們把這樣的一個(gè)交互過程看成是一個(gè)擴(kuò)展式博弈,如圖1所示:

圖1 外包計(jì)算的擴(kuò)展式博弈Figure 1 Expansive game of outsourcing computing

在圖1中,頂點(diǎn)的實(shí)心圓代表初始?xì)v史,即博弈的起始點(diǎn).用戶首先行動,其邊的標(biāo)記是該行動的名稱.即開始用戶的行動就是外包(O)計(jì)算任務(wù)或者不外包(No)計(jì)算任務(wù),其后服務(wù)器的行動為拒絕(?R)或者接受(R)該外包任務(wù),b表示服務(wù)器作弊的概率,a表示用戶驗(yàn)證概率.其葉子端點(diǎn)代表收益向量.

我們分別把m,θ,B,C和km(b),λm(b),W(b),F(b)看作預(yù)先約定常數(shù)和函數(shù),只有驗(yàn)證率a和作弊率b當(dāng)作變量.同時(shí),用戶和服務(wù)器都是自私的非合作參與者,且它們都是風(fēng)險(xiǎn)中性的,即它們在期望效用和期望值的效用之間沒有嚴(yán)格偏好.根據(jù)外包計(jì)算的擴(kuò)展式博弈,我們把用戶和服務(wù)器的效用函數(shù)看成是花費(fèi)成本和收益的線性函數(shù).并定義了一個(gè)新的支付矩陣,結(jié)果和收益如表2所示:

表2 支付矩陣Table 2 Payoffmatrix

根據(jù)以上支付矩陣,定義參與者的效用函數(shù)如下:

用戶檢測到作弊時(shí)的期望收益是:

用戶沒有檢測到作弊時(shí)的期望收益是:

用戶總的期望收益是:

服務(wù)器被檢測作弊時(shí)的期望收益是:

服務(wù)器沒有被檢測作弊時(shí)的期望收益是:

服務(wù)器總的期望收益是:

4 理性外包計(jì)算的形式化定義

本節(jié)基于博弈的納什均衡給出理性外包計(jì)算的形式化定義.一個(gè)兩方的理性外包計(jì)算的過程可以看成是一些交互規(guī)則的集合,我們認(rèn)為外包計(jì)算結(jié)果的完整性與各參與方的效用函數(shù)相關(guān).各理性參與者為了獲得最佳收益就必須遵守這些規(guī)則,任何違背這些規(guī)則的參與者都會獲得較差的收益.這就和博弈論中納什均衡的概念是類似的.我們將據(jù)此先給出理性外包計(jì)算模型的形式化定義.

假設(shè)T={(A1,f1(·)),(A2,f2(·)),···}是用戶外包任務(wù)集合,其中每一個(gè)(Ai,fi(·))我們解釋如下:Ai代表用戶的計(jì)算任務(wù),f(·)代表外包任務(wù)的計(jì)算函數(shù).我們將依據(jù)納什均衡來構(gòu)造理性外包計(jì)算的交互博弈規(guī)則.

定義3(理性外包計(jì)算形式化定義)設(shè)T={(A1,f1(·)),(A2,f2(·)),···}是用戶的外包任務(wù)集合,用戶需要將該計(jì)算任務(wù)和計(jì)算函數(shù)外包給服務(wù)器,該外包計(jì)算的博弈記為(T),其中C代表用戶,S代表服務(wù)器,a表示用戶的驗(yàn)證概率,b表示服務(wù)器的作弊概率,T的計(jì)算結(jié)果是完整的當(dāng)且僅當(dāng):

(1)()是博弈(T)的納什均衡,且策略組合()產(chǎn)生的結(jié)果為o=(a,b),且a和b是使參與者收益取得最大值時(shí)相對應(yīng)的策略;

(2)對該博弈的任何納什均衡(s1,s2),都有ui(s1,s2)≤ui(),即()是納什均衡集中最佳的納什均衡集.

下面證明如下的事實(shí): 產(chǎn)生結(jié)果o=(a,b)的策略組合集合是外包計(jì)算博弈模型的納什均衡集; 該集合是最佳的納什均衡集,即上述條件(2)成立.

5 模型仿真與分析

基于以上的外包計(jì)算的擴(kuò)展式博弈,根據(jù)納什均衡條件,通過實(shí)驗(yàn)仿真與分析理性外包計(jì)算模型的最佳線性函數(shù)的選取.首先在保證理性外包計(jì)算激勵(lì)相容的前提條件下固定線性函V(a),W(b)數(shù)值,通過改變懲罰函數(shù)分析各參與者效用函數(shù)問題;其次,選取最佳的懲罰函數(shù),同樣固定W(b),分析驗(yàn)證成本對效用函數(shù)的變化情況,最后,通過分析得出最佳的V(a),F(b),進(jìn)一步分析支付成本對參與者效用函數(shù)的影響.為通過實(shí)驗(yàn)仿真選取最佳的線性參數(shù),下面我們做如下的假設(shè):

假設(shè)計(jì)算輸出的結(jié)果K=10000,B=3,M=1,這三個(gè)值都是用戶和服務(wù)器共同的知識.又設(shè)km(b)=(1+m)b,λm(b)=2(1+m)b,用戶容許服務(wù)器作弊的閾值θ=0.01,W(b)=k-b.1≤k≤3,k為常數(shù),V(a)=ha(h＞0,h為常數(shù))和懲罰F(b)=lb(l為常數(shù)).下面通過模型仿真與分析選取V(a),W(b),F(b)這三個(gè)線性函數(shù)最佳參數(shù)設(shè)置.

5.1 懲罰與效用函數(shù)的關(guān)系

定理1在上述的假設(shè)下,設(shè)W(b)=2.8-b,V(a)=如果懲罰函數(shù)F(b)=lb(l為一個(gè)常數(shù)),若l≥10000時(shí),則該理性外包計(jì)算模型存在納什均衡點(diǎn),并且達(dá)到納什均衡點(diǎn)時(shí)外包計(jì)算結(jié)果是完整.

證明:如圖2所示,縱坐標(biāo)表示效用值,橫坐標(biāo)表示為懲罰函數(shù)的系數(shù)l,加菱形的線條表示用戶的收益,加星形的線條表示服務(wù)器的收益.從圖像容易看出,隨著l的增大,用戶的效用函數(shù)沒有變化,即用戶沒有偏好的動機(jī),也就是說用戶收益達(dá)到最大.從表3易得出,用戶收益最大化時(shí)納什均衡點(diǎn)的驗(yàn)證策略a=0;對服務(wù)器來說,當(dāng)0＜l≤10000時(shí),隨著l的增大,服務(wù)器收益逐漸增大,它仍需要改變策略來最大化自己的收益.當(dāng)l≥10000時(shí),服務(wù)器的收益不再發(fā)生變化,即服務(wù)器改變自己的策略不會增加自己的收益.故服務(wù)器的收益已達(dá)到最大化,并且由表4可知,服務(wù)器收益最大時(shí)的最佳策略為b=0.綜上所述,當(dāng)l≥10000時(shí),參與方的收益達(dá)到納什均衡,且收益最大化的納什均衡點(diǎn)是用戶的驗(yàn)證率a=0,服務(wù)器的作弊率b=0,故外包結(jié)果是完整的.

表3 l與效用函數(shù)uC的關(guān)系Table 3 Relationship between l and utility function uC

表4 l與效用函數(shù)uS的關(guān)系Table 4 Relationship between l and utility function uS

圖2 l效用函數(shù)u的關(guān)系Figure 2 Relationship between l and utility function u

推論1在上述的假設(shè)下,如果懲罰函數(shù)F(b)=c(c為常數(shù)),若c＞10000時(shí),則該理性外包模型存在納什均衡點(diǎn),并且達(dá)到納什均衡點(diǎn)時(shí)外包計(jì)算結(jié)果是正確的.

5.2 驗(yàn)證成本與效用函數(shù)的關(guān)系

定理2在上述的假設(shè)下,設(shè)懲罰函數(shù)F(b)=10001b,W(b)=2.8-b,假設(shè)V(a)=ha(0＜h≤1的常數(shù)),若0＜h≤時(shí),則該外包計(jì)算博弈模型存在納什均衡,且達(dá)到納什均衡時(shí)服務(wù)器計(jì)算的結(jié)果滿足用戶期望滿足的水平.

證明:如圖3所示,縱坐標(biāo)表示效用值,橫坐標(biāo)表示為驗(yàn)證成本函數(shù)的系數(shù)h,加菱形的線條表示用戶的收益,加星形的線條表示服務(wù)器的收益.從圖像易看出,用戶的效用隨著h的增大而減小.故易得出當(dāng)0＜h≤時(shí),此時(shí)用戶的收益達(dá)到最大值,也就是說用戶收益達(dá)到納什均衡,由表5可知達(dá)到納什均衡時(shí)用戶最佳驗(yàn)證策略為a=0.同時(shí),服務(wù)器的收益也隨著h的增大而減小,當(dāng)0＜h≤,服務(wù)器的收益達(dá)到納什均衡.即h的取值滿足h∈(0,)時(shí),服務(wù)器選擇的策略為最佳策略.由表6易得,服務(wù)器收益達(dá)到納什均衡時(shí)服務(wù)器作弊策略b=0.01.由我們的假設(shè)用戶容忍的閾值為θ=0.01,服務(wù)器的作弊率b=0.01≤θ=0.01,故參與者收益達(dá)到納什均衡時(shí)時(shí)服務(wù)器計(jì)算的結(jié)果滿足用戶期望滿足的水平.

表5 h與效用函數(shù)uC的關(guān)系Table 5 Relationship between h and utility function uC

5.3 支付與效用函數(shù)的關(guān)系

定理3在上述假設(shè)下,設(shè)懲罰函數(shù)和驗(yàn)證成本分別為F(b)=10 001b,V(a)=,用戶的支付函數(shù)為W(b)=k-b(1≤k＜3的常數(shù)),若當(dāng)1≤k＜2時(shí),則該外包計(jì)算博弈模型達(dá)到納什均衡,且達(dá)到納什均衡時(shí)服務(wù)器計(jì)算的結(jié)果是正確的.

表6 h與效用函數(shù)uS的關(guān)系Table 6 Relationship between h and utility function uS

圖3 h與效用函數(shù)u的關(guān)系Figure 3 Relationship between h and utility function u

證明:如圖4所示,該圖的縱坐標(biāo)表示效用值,橫坐標(biāo)表示為變化常數(shù)k,加菱形的線條表示用戶的收益,加星形的線條表示服務(wù)器的收益.從圖像易看出,用戶的效用隨著的增大而減小.當(dāng)k=1時(shí),用戶的收益達(dá)到最大值,即用戶收益達(dá)到納什均衡,由表7(選取納什均衡點(diǎn)附近的點(diǎn))可知達(dá)到納什均衡時(shí)用戶最佳驗(yàn)證策略為a=0.對于服務(wù)器來說,它的收益也隨著h的增大而減小,當(dāng)k=1,服務(wù)器的收益也達(dá)到納什均衡.由表8(選取納什均衡點(diǎn)附近的點(diǎn))易得,服務(wù)器收益達(dá)到納什均衡時(shí)的服務(wù)器的作弊策略b=0.故參與者收益達(dá)到納什均衡時(shí)服務(wù)器計(jì)算的結(jié)果是正確的.

表7 k與效用函數(shù)uC的關(guān)系Table 7 Relationship between k and utility function uC

表8 k與效用函數(shù)uS的關(guān)系Table 8 Relationship between k and utility function uS

由定理1可以得出,當(dāng)懲罰足夠大的時(shí)候,服務(wù)器就沒有欺騙的動機(jī).從圖3、4仿真實(shí)驗(yàn)分析可知,只要懲罰很高的時(shí)候,服務(wù)器只要接受外包任務(wù),就可以保證服務(wù)器誠實(shí)計(jì)算外包計(jì)算的任務(wù),同時(shí),用戶也不用驗(yàn)證.故在該模型下外包計(jì)算結(jié)果是完整的.本文設(shè)計(jì)的模型不僅為用戶提供了一種預(yù)算設(shè)置,而且還能夠最大限度減少外包商的費(fèi)用.

圖4 k與效用函數(shù)u的關(guān)系Figure 4 Relationship between k and utility function u

6 總結(jié)

如今,將計(jì)算任務(wù)外包給云服務(wù)提供商是非常普遍的做法.保證這些計(jì)算結(jié)果的正確性通常由驗(yàn)證機(jī)制來完成.本文首先分析了理性外包計(jì)算中參與者的偏好;其次,根據(jù)博弈論的框架提出了一個(gè)理性外包計(jì)算擴(kuò)展式博弈,并定義一個(gè)新的支付矩陣和效用函數(shù);最后,通過設(shè)置效用函數(shù)中參數(shù)的最佳選擇條件,確保參與者達(dá)到納什均衡時(shí)用戶不需要驗(yàn)證外包計(jì)算結(jié)果,也可以確保服務(wù)器誠實(shí)計(jì)算.這就大大減少驗(yàn)證成本和通信復(fù)雜度.該模型還最大限度地減少了用戶的費(fèi)用.

本文中預(yù)先約定的函數(shù)都是假設(shè)為線性的,這種假設(shè)在現(xiàn)實(shí)中可能較為特殊,如用戶驗(yàn)證成本有可能隨著外包數(shù)據(jù)集的類型及外包算法等因素的影響可能是一個(gè)非線性的函數(shù).這種假設(shè)是文章的不足之處.因此,在未來研究中可以對預(yù)先確定的函數(shù)一般化,也可以通過引入聲譽(yù)系統(tǒng)來構(gòu)造外包計(jì)算的博弈模型.