基于逆向拍賣模型的群智感知激勵機制①

胡婷婷，朱曉娟

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院，安徽 淮南)

0 引 言

近些年來，隨著無線傳感網(wǎng)絡(luò)和社交網(wǎng)絡(luò)的快速發(fā)展，大量的智能手機、智能手環(huán)、pad等手持移動設(shè)備的激增，催生出了一種可以對物理世界進行數(shù)據(jù)收集的感知范式-----群智感知( Crowd Sensing， CS)[1]。群智感知利用大規(guī)模用戶的移動設(shè)備上搭載的傳感器來進行數(shù)據(jù)的感知和采集工作。移動用戶可以將收集到的數(shù)據(jù)上傳到服務(wù)器而不會產(chǎn)生任何重大成本。例如，用戶可以利用社交網(wǎng)站(例如大眾點評)來點評對商家的滿意度等指標。群智感知在物聯(lián)網(wǎng)的很多領(lǐng)域都有著重要的應(yīng)用，如環(huán)境監(jiān)測、智能交通、城市管理等[2]。用戶在參與感知任務(wù)的過程中由于受到設(shè)備的電量、存儲空間的限制,有些感知任務(wù)可能會造成位置隱私泄露問題，這就會導(dǎo)致有些用戶不愿意參與到感知任務(wù)中來[3]。因此，設(shè)計一種可以激發(fā)用戶積極性的激勵機制，吸引更多用戶來參與感知任務(wù)尤為重要。

目前的激勵形式主要分為報酬激勵和非報酬激勵[4]。報酬激勵即利用金錢來鼓勵參與者參與任務(wù)；非報酬激勵則采用諸如虛擬積分、社交關(guān)系等方式來吸引一批有共同愛好和興趣的人參與進來?，F(xiàn)有的激勵機制大多以平臺為中心[5]，側(cè)重于如何選擇用戶來進行報酬支付以最大化平臺效益為核心，而忽略了用戶考慮到自身利益不愿意積極參與感知任務(wù)而導(dǎo)致任務(wù)分配率不高的問題。在保障用戶利益的前提下，提高參與人數(shù)的同時保證服務(wù)器平臺所需任務(wù)是有待研究的重點。為此，提出了一種基于逆向拍賣的激勵機制來解決以上問題。

1 相關(guān)工作

近些年來，國內(nèi)外學(xué)者對群智感知激勵機制做了大量的研究。Luo[6]基于用戶之間的協(xié)作任務(wù)，提出了一種合作眾包拍賣機制實現(xiàn)最小化支付；Duan[7]等人通過建立Stackelberg博弈模型，基于用戶間的協(xié)作行為而制定了一套獎勵機制；Peng[8]等人從用戶上傳數(shù)據(jù)質(zhì)量的角度出發(fā)來避免無效、低質(zhì)數(shù)據(jù)，再利用最大似然估計和貝葉斯算法來選擇高質(zhì)量用戶，最大化平臺收益；以上機制中平臺占據(jù)主動權(quán)，用戶處于被動狀態(tài)，這種情況下往往參與率不高。Ke[9]等人考慮從用戶敏感位置隱私安全的角度進行著手，來促進用戶參與的積極性；Yang[10]等人則是分別從以平臺為中心和以用戶為中心建立了兩種模型機制，一種以平臺為中心利用 stackelberg game 設(shè)計激勵機制，根據(jù)用戶的時間因子來進行判斷；第二種則以用戶為中心建立逆向拍賣機制Msensing，相比于前者增大了用戶的主動性，但在優(yōu)勝者選擇的時候采用貪心法，任務(wù)覆蓋率考慮不足。

以上的激勵機制從用戶質(zhì)量、信譽獎勵和隱私等不同的角度去激勵用戶積極參與感知項目。文中則側(cè)重從提高用戶效用的角度出發(fā)，刺激參與人數(shù)的增長，從而起到提高用戶參與率并且希望用戶上傳的數(shù)據(jù)符合平臺要求任務(wù)的目的。

2 系統(tǒng)模型及問題描述.

逆向拍賣又被稱為反向拍賣和荷蘭式拍賣，不同于正向拍賣一個賣家叫價，多個買家競拍的模式，逆向拍賣則和正向拍賣相反，是一個買家和多個賣家的競拍方式。對應(yīng)到群智感知系統(tǒng)中，買家就是服務(wù)器平臺，而賣家則為持有感知任務(wù)的用戶，見圖1。服務(wù)器平臺進行廣播所需要的感知任務(wù)，用戶則根據(jù)手上平臺所需數(shù)據(jù)來參與競拍，服務(wù)器平臺再根據(jù)用戶提報的競標價和任務(wù)本身的價值來進行綜合考慮，最終給予符合條件的用戶報酬激勵。

圖1 正向拍賣與逆向拍賣的區(qū)別

圖2 基于逆向拍賣模型

2.1 系統(tǒng)模型

服務(wù)器平臺發(fā)布任務(wù)后，賣家根據(jù)自身設(shè)備收集到的數(shù)據(jù)來參與競標。如圖2所示。服務(wù)器平臺發(fā)布感知任務(wù)集Γ={τ1,τ2,…τm,},m為平臺發(fā)布的總?cè)蝿?wù)數(shù)，τi為彼此獨立的任務(wù)。并且定義平臺發(fā)布的任務(wù)集合所對應(yīng)的價值集合為V={v1,v2,…vm};對任務(wù)感興趣的用戶U={u1,u2,…un,}參與競價，用戶ui(i=1,2,…n)所提交的任務(wù)子集Γi?Γ和自己的競標任務(wù)對Bi=(Γi，bi)，其中bi為用戶提交的競標價格；設(shè)用戶在參與競標中耗費的成本為ci,且成本只有自己知道，對用戶和平臺都是不透明(ci≥0且ci≤bi)。任務(wù)平臺來選擇優(yōu)勝者集合，即贏標用戶集W?U,并將優(yōu)勝結(jié)果告知參與用戶；贏標者上傳平臺所需的感知任務(wù)，感知平臺為每個優(yōu)勝者根據(jù)用戶ui完成的任務(wù)Γi支付勝出者報酬pi(pi≥bi)。

2.2 問題描述

激勵機制通過贏標者候選和贏標者支付兩個步驟來實現(xiàn)，在選擇贏標者階段，通過每個任務(wù)都至少對應(yīng)一位成功執(zhí)行任務(wù)的用戶來進行判決贏標者。當完成某個任務(wù)的用戶數(shù)量僅為一人時，則直接選出優(yōu)勝者集合W′；當完成某個任務(wù)的 人數(shù)大于等于2時,選擇出的優(yōu)勝者集合記為W″;平臺將W′和W″的集合并在一起給總的贏標者集合W進行報酬支付。最后從計算的效率、個體理性、可行性和真實性來判斷該機制的性能和效用。

其中用戶ui的效用可以表示為平臺的支出報酬pi與用戶消耗的感知成本ci之間的的差值，即

(1)

其中W為贏標者集合；當用戶落選贏標集時，效用則為0。落選的用戶可以選擇退出或進行下一輪任務(wù)的競拍，多輪競拍的情況這里不做考慮。

服務(wù)器平臺的效用u0則為優(yōu)勝者W完成任務(wù)的總價值與支付贏標者報酬之間的差值，即

(2)

2.2.1 贏標者候選階段

在逆向拍賣機制中，參與者的競價bi要參考在參與任務(wù)中的消耗成本ci，而任務(wù)發(fā)布平臺則要考慮到以最大化平臺效益選取贏標者集合來進行支付，在之前的研究中，已經(jīng)被證明此類型為NP-Hard問題[11]，即無法在多項式內(nèi)得到最優(yōu)解集合。需要換個思路來解決這個問題，當任務(wù)集覆蓋的競標用戶數(shù)量ni=1時，只要用戶的上報競標價格bi與其提供的任務(wù)總價值vi的比值小于1，則該用戶就為此任務(wù)的優(yōu)勝者；當任務(wù)集覆蓋的競標用戶數(shù)量ni≥2時，對用戶的競標價格bi與其提供的任務(wù)總價值vi的比值進行一個排序，且小于1的用戶作為優(yōu)勝者集合，最終選出符合條件的贏標者集合W。

公式如式(3)：

(3)

算法一:任務(wù)選擇算法輸入:任務(wù)集Γ,價值集V,所有競標用戶上報的任務(wù)集Γ',競標任務(wù)對Bi=(Γi,bi),贏標集W= I;輸出:贏標者集合W,贏標者集合中所覆蓋的任務(wù)集合Γ''1:for allτi in Γ' do2:if (ni=1&bi≤vi)then3: W'←W'∪ui ,?！濉！濉圈觟 /* W'為從競標者數(shù)量ni=1的任務(wù)集中選出的優(yōu)勝者*/4: if (ni≥2)then5: Sort(bi/vi)升序排列,見公式(3)6: 記,bs/vs←argmin(bi/vi)/* bs/vs為bi/vi中的最小值*/7: bh/vh←argmax(bi/vi)/*bh/vh為bi/vi中的最大值*/8: and if bivi≤1 then9: W″←W″∪ui ,Γ'←?！濉圈觟 * W″為從競標者數(shù)量ni≥2的任務(wù)集中選出的優(yōu)勝者*/10: W←W'∪W″11:Endfor

2.2.2 贏標者支付階段

選擇完贏標者后，接下來要對其進行報酬的支付。根據(jù)梅爾森[12]的理論可知拍賣機制要符合以下兩點要求：1)選擇規(guī)則是單調(diào)的：如果用戶i通過出價bi贏得拍賣，它則也通過出價bi’≤bi贏得。 2)每個贏標者都獲得了關(guān)鍵價值：用戶出價不會高于平臺設(shè)定的某個閾值，則贏得競標。

但目前的獎勵措施大多采用統(tǒng)一支付的方式，不利于區(qū)分用戶貢獻?；诖?，采取在多人競標的優(yōu)勝者集合W''里選取bi/vi比值最高者(后面統(tǒng)稱為第一名)附加獎勵的方式來進行報酬支付；其他的贏標者Wvi則采取統(tǒng)一支付的方式。由算法一第6行和第7行可知bs/vs為排序中的最小值，bh/vh為排序中的最大值?？梢愿鶕?jù)以下函數(shù)來設(shè)定獎勵金：

TWs=vs(bh/vh-bs/vs)

(4)

其中TWs為第一名的附加獎勵支付函數(shù)，vs為第一名提供的任務(wù)價值。

(5)

其中pi為總的支付函數(shù)?？梢钥闯?，在支付階段沒有采用統(tǒng)一支付的方式，而是給予了候選階段中排序最低的bs/vs附加獎勵，這種方式可以刺激更多的用戶積極參與競標任務(wù)。偽代碼實現(xiàn)過程見算法二：

算法二:贏標者支付算法輸入:贏標者集合W,贏標者集合中所覆蓋的任務(wù)集合Γ'',贏標者集合中覆蓋任務(wù)集的總價值獎勵VΓ'', bi/vi中的最大值bh/vh支付報酬pi1:for all τiin Γ'' do2:計算3: if(bi/vi=bs/vs)then4: 根據(jù)(4)式計算出TWs的值5: for all ui∈W6: 根據(jù)(5)式計算出pi7:p=∑ui∈wpi/*p為支付的總報酬*/8:if (p>VΓ'') then 9: W‖p|010:輸出pi11: endfor

2.3 性能分析

根據(jù)文獻[13]可知，基于競拍的模型激勵機制的設(shè)計要滿足計算效率、個體理性、可行性和真實性這四個指標。

(1)計算效率：指設(shè)計的方案可以使問題可以在多項式內(nèi)解決。

(2)個體理性：用戶的回報要高于付出的成本。

(3)可行性：服務(wù)器平臺要保證自身效益非負，所支付的報酬小于任務(wù)的總價值。

(4)真實性：沒有一個用戶可以用不同于自身價值的競價去提高自身效用。

證明1 該激勵機制滿足計算效率

由算法一可知在對任務(wù)τi進行遍歷的for循環(huán)里的時間復(fù)雜度為O(m)，對bi/vi的排序算法的時間復(fù)雜度為O(nlogn)，所以總的算法復(fù)雜度應(yīng)為(mnlogn)；算法二里對任務(wù)〗τi和用戶ui進行for循環(huán)遍歷，其時間復(fù)雜度分別為O(m)和O(n)。綜上可見，算法都是在多項式時間內(nèi)進行求解的，所以該機制是滿足計算效率的。

證明2 該激勵機制滿足個體理性

用戶競標失敗的情況下，則成本ci和報酬pi都為0，用戶沒有損失；而如果競標成功的情況下，用戶的報酬支付由(5)計算可以得到且ci≤bi,用戶效用是非負的，所以該機制是滿足個體理性的。

證明3 該激勵機制滿足可行性

若W=0，則沒有符合的競標參與者，用戶U則為0；若W≠0，由算法二第8行可知，只有當平臺需要支付的總報酬p大于贏標者提供任務(wù)的價值VΓ'時，才會啟動程序，從而保證平臺的效用非負，所以該機制是滿足可行性的。

證明4 該激勵機制滿足真實性

根據(jù)Myerson的定律來進行證明

1)單調(diào)性：贏標者的條件由算法一第5行的排序可知是按照bi/vi排序大小的方式來的，即使用戶提出小于bi的競標價，但由于任務(wù)本身的價值vi并沒有發(fā)生改變，所以依然是符合單調(diào)性的。

綜上可知，所以該機制是滿足真實性的。

3 仿真實驗與分析

3.1 實驗設(shè)置

為了去評估激勵機制的效果，用Matlab進行了仿真實驗，并且與文獻[10]中的Msening算法進行了部分對比實驗，使得結(jié)果更加直觀可見。參數(shù)設(shè)置見表1。

表1 仿真參數(shù)設(shè)置

3.2 評估依據(jù)

將從平臺效用、用戶效用和任務(wù)覆蓋率這三個方面來進行比較分析。

(1)平臺效用：由式(2)可知為優(yōu)勝者W完成任務(wù)的總價值與支付贏標者報酬之間的差值。

(2)用戶效用：即所有贏標者總的效用與所有贏標者人數(shù)的比值。

(3)任務(wù)覆蓋率：贏標者所覆蓋的任務(wù)占到總?cè)蝿?wù)的比例。

3.3 實驗分析

1)平臺效用。如圖3(a)所示，隨著任務(wù)數(shù)m的增加，兩種激勵機制的平臺效應(yīng)也相應(yīng)的增加，這是因為用戶在任務(wù)選擇方面范圍廣，參與者為了增大自己的利益會選擇價值任務(wù)高的，這也使得平臺效用增加；由圖3(b)可以看出，相比于Msensing機制后期平臺效用略低的原因是，在報酬支付階段里涵蓋了給第一名優(yōu)勝者額外支付的成本當用戶數(shù)達到450-490的時候，任務(wù)基本分配，平臺效應(yīng)開始趨于穩(wěn)定。

圖3 (a)任務(wù)數(shù)與平臺效用

圖3 (b)用戶數(shù)與平臺效用

2)用戶效用。如圖4(a)所示當最開始發(fā)布任務(wù)的時候，競標者較多，贏標者數(shù)量增加，用戶效用也相應(yīng)的增加；隨著完成任務(wù)的增多，即完成率超過任務(wù)總數(shù)m的一半時，用戶完成任務(wù)的總價值已經(jīng)趨向于穩(wěn)定狀態(tài)，從而曲線呈平穩(wěn)狀態(tài)；圖4(b)中，用戶數(shù)目的增加，競爭越來越激烈，隨著任務(wù)完成率的提高，贏標者開始減少，用戶效用趨于穩(wěn)定。而機制中由于增加了用戶的盈利，從而提高了用戶參加任務(wù)的積極性。

圖4 (a)任務(wù)數(shù)與用戶效用

圖4 (b)用戶數(shù)與用戶效用

3)任務(wù)覆蓋。如圖5(a)所示。隨著任務(wù)數(shù)的增加，MSening的任務(wù)覆蓋率開始走低，主要是因為Msening在進行贏標者選擇的時候采用貪婪法，不停地選擇任務(wù)價值高和報價低的用戶，在進行支付的時候，想要找到任務(wù)覆蓋全的用戶就比較難了；圖5(b)中，隨著用戶的增多，當用戶數(shù)n>任務(wù)數(shù)m時，基本上平臺任務(wù)數(shù)已經(jīng)覆蓋完全，曲線趨于平滑。所以本機制在任務(wù)覆蓋方面也是占優(yōu)的。

圖5(a) 任務(wù)數(shù)與任務(wù)覆蓋率

圖5 (b)用戶數(shù)與任務(wù)覆蓋率

4 結(jié) 語

在針對用戶參與感知任務(wù)中積極性不高導(dǎo)致任務(wù)分配率不足的問題，而提出了以用戶為中心的逆向拍賣機制，最大化用戶效用的同時保證了平臺的效用。分別將競拍過程分為贏標者候選和贏標者支付兩個階段進行，優(yōu)勝者選擇階段過程中在多項式內(nèi)解決了問題，支付報酬階段則采取基于排序最高者的附加獎勵方式，激發(fā)了用戶參與積極性。實驗結(jié)果則驗證了此機制有效地提高了用戶效用、平臺效用和任務(wù)覆蓋等指標，最終驗證了該機制具有較好的激勵效果。