芮蘭蘭 張 攀 黃豪球 邱雪松

?

一種面向眾包的基于信譽(yù)值的激勵(lì)機(jī)制

芮蘭蘭 張 攀*黃豪球 邱雪松

(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 100876)

眾包是互聯(lián)網(wǎng)帶來的一種分布式問題解決模式。然而，由于工作者和任務(wù)發(fā)布者具有自私特性并且致力于獲得自身效益的最大化，使得在眾包應(yīng)用中，存在內(nèi)部的激勵(lì)問題。該文主要完成以下工作：首先，基于重復(fù)博弈，提出一種基于信譽(yù)值的激勵(lì)模型，用于激勵(lì)理性工作者高質(zhì)量地完成任務(wù)；其次，該激勵(lì)模型中同時(shí)設(shè)置了懲罰機(jī)制，將針對惡意工作者做出相應(yīng)懲罰。仿真結(jié)果表明，即使在自私工作者比例為0.2的條件下，只要合理選擇懲罰參數(shù)，均可有效激勵(lì)理性工作者的盡力工作，眾包平臺的整體性能可以提升至90%以上。

眾包平臺；激勵(lì)模型；懲罰機(jī)制；重復(fù)博弈

1 引言

眾包是指一個(gè)公司或機(jī)構(gòu)把過去由員工執(zhí)行的工作任務(wù)，以自由自愿的形式包給非特定的大眾網(wǎng)絡(luò)的做法[1,2]。在眾多的眾包平臺中，比如Yahoo Answers[3]以及Amazon Mechanical Turk[4]，用戶通過完成小任務(wù)獲取一定報(bào)酬。眾包平臺中的典型任務(wù)有設(shè)計(jì)圖形，征集營銷方案，圖像標(biāo)記等。為了便于說明，將一個(gè)眾包平臺的用戶分為兩類：在平臺上發(fā)布任務(wù)的用戶稱為任務(wù)發(fā)布者，完成任務(wù)的用戶稱為工作者。許多眾包平臺呈現(xiàn)出相似的架構(gòu)，即任務(wù)發(fā)布者將一個(gè)任務(wù)的描述信息，連同這個(gè)任務(wù)的報(bào)酬值一起，發(fā)布在眾包平臺上。工作者提交對于這個(gè)任務(wù)的解決方案，并且由任務(wù)發(fā)布者對答案進(jìn)行篩選，最終被選中答案對應(yīng)的工作者會(huì)得到相應(yīng)的報(bào)酬。

眾包的工作方式，可以幫助任務(wù)發(fā)布者獲得大量自由工作者，通過利用這些工作者的智慧解決實(shí)際問題。然而，由于工作者和任務(wù)發(fā)布者具有自私特性并且致力于獲得自身效益的最大化，這樣的情況導(dǎo)致工作者所提交的結(jié)果中包含大量隨意甚至虛假的答案，即在眾包平臺中，存在內(nèi)部的激勵(lì)問題。因此，如何激勵(lì)工作者盡力完成任務(wù)，從而保障在眾包平臺中結(jié)果數(shù)據(jù)的質(zhì)量，成為優(yōu)化眾包服務(wù)的重要環(huán)節(jié)。

目前針對眾包的研究工作主要集中在以下3個(gè)方面：(1)基于眾包的信任機(jī)制設(shè)計(jì)。將信譽(yù)值作為眾包平臺識別和懲罰惡意工作者的重要指標(biāo),并且基于工作者的可信程度和用戶偏好為任務(wù)分配提供決策支持；(2)激勵(lì)機(jī)制設(shè)計(jì)。通過設(shè)計(jì)合適的激勵(lì)機(jī)制，保證工作者的工作動(dòng)力，這對于保障眾包平臺的性能至關(guān)重要；(3)結(jié)果質(zhì)量評估方法的研究。目的是通過各種方法對工作者提交的結(jié)果進(jìn)行評估，以此來識別惡意工作者；并將這個(gè)評估結(jié)果作為觸發(fā)對工作者惡意行為進(jìn)行懲罰的重要條件。

在信任機(jī)制的設(shè)計(jì)方面，文獻(xiàn)[5]提出在眾包平臺中，采用信譽(yù)值解決惡意工作者的方法是可行的，同時(shí)，基于可信程度的任務(wù)分配機(jī)制，可能會(huì)提升整個(gè)眾包平臺的總體效用。文獻(xiàn)[6]考慮將信任機(jī)制引入到移動(dòng)網(wǎng)絡(luò)的內(nèi)容發(fā)現(xiàn)和緩存中，構(gòu)建了一個(gè)用于內(nèi)容發(fā)現(xiàn)和緩存的系統(tǒng)Figaro，同時(shí)采用博弈論的方法證明了使用上述信任機(jī)制可以有效激勵(lì)移動(dòng)用戶間的合作。但是在傳統(tǒng)的信任機(jī)制研究中，總是旨在盡可能精準(zhǔn)地計(jì)算和識別出一個(gè)最可信的服務(wù)提供結(jié)點(diǎn)，并且是基于如下兩個(gè)假設(shè)：(1)在一個(gè)時(shí)間單元內(nèi)，每個(gè)服務(wù)提供結(jié)點(diǎn)可以響應(yīng)數(shù)量無上限的服務(wù)請求，(2)在完成一個(gè)任務(wù)時(shí)，只需要在若干服務(wù)提供結(jié)點(diǎn)中選擇一個(gè)結(jié)點(diǎn)。然而，在眾包平臺中，上述的兩個(gè)假設(shè)都是不成立的。

在基于眾包的激勵(lì)機(jī)制設(shè)計(jì)的研究方面，一類工作研究的激勵(lì)機(jī)制是依賴于金錢報(bào)酬的方法。當(dāng)工作者完成任務(wù)后，由任務(wù)發(fā)布者以現(xiàn)金的形式支付給工作者作為報(bào)酬。另外，還有一類是研究基于信譽(yù)的激勵(lì)機(jī)制，比如，文獻(xiàn)[9]分別在以平臺為中心和以手機(jī)用戶為中心的2種不同的感知系統(tǒng)模型中設(shè)計(jì)了與模型相適應(yīng)的激勵(lì)機(jī)制。文獻(xiàn)[10]研究基于信譽(yù)的激勵(lì)機(jī)制，利用博弈論中相關(guān)理論建立效用矩陣，并通過建立馬爾科夫過程，分析和證明上述方法能有效激勵(lì)工作者進(jìn)行合作。除了上述兩種方法外，還有基于拍賣的激勵(lì)機(jī)制研究，比如，文獻(xiàn)[11]基于質(zhì)量驅(qū)動(dòng)的拍賣理論，提出了一種針對于移動(dòng)群智感知環(huán)境的激勵(lì)機(jī)制QDA，同時(shí)從理論證明了該機(jī)制的真實(shí)性，滿足個(gè)體理性以及平臺可盈利。但是在上述研究中，缺乏對于眾包平臺中可能產(chǎn)生的工作者惡意行為，比如，惡意誹謗攻擊等的處理和懲罰機(jī)制研究[6,12]。

結(jié)果質(zhì)量評估方法的研究方面，最簡單的一種方法就是使用黃金標(biāo)準(zhǔn)數(shù)據(jù)評估工作者完成的質(zhì)量，通過將工作者提交的結(jié)果與標(biāo)準(zhǔn)數(shù)據(jù)進(jìn)行比較，可以檢測出欺騙類型工作者，并拒絕他們提交的結(jié)果[1]。本文將不會(huì)對質(zhì)量評估的具體方法進(jìn)行研究。但是由于在任務(wù)發(fā)布者一側(cè)對于工作者提交的答案進(jìn)行質(zhì)量判定，得到的結(jié)論可能會(huì)有失偏頗，甚至?xí)嬖趷阂庹u謗攻擊等行為，本文將會(huì)針對這類攻擊行為的處理和懲罰機(jī)制進(jìn)行深入的研究。

由此可見，目前基于眾包的信任機(jī)制和激勵(lì)機(jī)制的設(shè)計(jì)方面，仍存在著缺陷。為了解決上述問題，建立完善的信任和激勵(lì)機(jī)制，本文首先為系統(tǒng)中的每個(gè)工作者分配信譽(yù)值，并建立相應(yīng)的信譽(yù)值計(jì)算模型；其次設(shè)計(jì)了一種懲罰和反饋機(jī)制，使得在任務(wù)發(fā)布者收到了工作者的答案后，向眾包平臺反饋，并以此為依據(jù)決定是否觸發(fā)懲罰；然后對傳統(tǒng)任務(wù)分配機(jī)制進(jìn)行擴(kuò)展，提出了針對眾包平臺的任務(wù)分配算法；最后采用重復(fù)博弈的方法，證明了在合理選擇懲罰參數(shù)的基礎(chǔ)上，可以有效激勵(lì)理性工作者的盡力工作。

本文的創(chuàng)新點(diǎn)如下：

(1)設(shè)計(jì)了一種基于工作者歷史行為的懲罰機(jī)制。其中，懲罰期長度與工作者的歷史行為相關(guān)，當(dāng)工作者是初次或是偶爾進(jìn)入懲罰期時(shí)，其信譽(yù)值恢復(fù)的速度較快；而當(dāng)工作者具有惡意行為時(shí)，則其信譽(yù)值恢復(fù)速度越來越小。

(2)對任務(wù)發(fā)布者的反饋進(jìn)行可信度的判定，提出了消極反饋率的概念，采用消極反饋率可以有效鑒別任務(wù)發(fā)布者消極反饋的可信度。

(3)采用基于上述信譽(yù)值計(jì)算模型的重復(fù)博弈方法，證明了在合理選擇懲罰參數(shù)的基礎(chǔ)上，可以有效激勵(lì)理性工作者的盡力工作。所提方法彌補(bǔ)了基于馬爾科夫過程的激勵(lì)機(jī)制研究中，缺乏對眾包平臺中可能產(chǎn)生的惡意行為如惡意誹謗攻擊等進(jìn)行處理的缺陷。

本文第2節(jié)詳細(xì)分析眾包信任機(jī)制，給出了基于信譽(yù)值的激勵(lì)模型，并提出了基于用戶歷史行為的懲罰機(jī)制；第3節(jié)針對眾包平臺進(jìn)行重復(fù)博弈分析，并得到激勵(lì)一致性的條件；第4節(jié)詳細(xì)分析了我們的實(shí)驗(yàn)結(jié)果，驗(yàn)證了在合理選擇懲罰參數(shù)的情況下，可以有效激勵(lì)理性工作者盡力完成工作，平臺的整體性能和效益可以相應(yīng)提升；第5節(jié)為結(jié)束語。

2 基于信譽(yù)值的激勵(lì)機(jī)制

2.1 問題定義

(1)用戶：眾包平臺的用戶包含任務(wù)發(fā)布用戶集合以及工作者集合。對于任意任務(wù)發(fā)布者，在時(shí)刻發(fā)布的一個(gè)任務(wù)，需要被分解為個(gè)子任務(wù)進(jìn)行處理。通常來說，同一個(gè)分解的個(gè)子任務(wù)可以視作是相同類型的。同一時(shí)間內(nèi)，一個(gè)工作者可以完成一個(gè)或多個(gè)子任務(wù)，然而，受制于工作者的能力，存在一個(gè)單位時(shí)間內(nèi)完成子任務(wù)數(shù)量的上限，這里記作。這個(gè)參數(shù)主要用在平臺在對工作者進(jìn)行任務(wù)分配時(shí)，單位時(shí)間內(nèi)可以分配的最大數(shù)量。

(2)信譽(yù)值計(jì)算模型：本文的信譽(yù)值計(jì)算模型包含兩個(gè)部分：信譽(yù)值計(jì)算方法，信譽(yù)值集合Rep。眾包平臺為每個(gè)工作者賦予信譽(yù)值，用參數(shù)rp表示。rp是集合中的元素，其中表示最大信譽(yù)值。初始設(shè)置所有工作者的信譽(yù)值均為，隨著交易過程的發(fā)生，工作者的信譽(yù)值發(fā)生變化，高信譽(yù)值反應(yīng)了工作者在執(zhí)行任務(wù)時(shí)表現(xiàn)良好。根據(jù)任務(wù)發(fā)布者對于本次交易過程的滿意程度，眾包平臺對工作者的信譽(yù)值進(jìn)行更新。

式(1)中，參數(shù)定義如表1所示。

表1 參數(shù)定義

2.2 懲罰激勵(lì)機(jī)制

當(dāng)工作者的信譽(yù)值降低到閾值PL，并且再一次收到了負(fù)面評價(jià)后，工作者的信譽(yù)值會(huì)被清零，進(jìn)而進(jìn)入到懲罰期。在懲罰期中，工作者只有通過參與交易并且獲得正面評價(jià)才可以獲得信譽(yù)恢復(fù)1，直到信譽(yù)值恢復(fù)到后，重新置為閾值PL，之后工作者可以開始正常參與交易。同時(shí)，工作者在懲罰期中參與交易不能得到報(bào)酬，并且如果在懲罰期內(nèi)，工作者仍然選擇不盡力工作，那么，該工作者將會(huì)被驅(qū)逐出該眾包平臺。因此，即使是始終選擇不盡力工作的自私工作者，在進(jìn)入了懲罰期后，也只能選擇盡力工作以盡快脫離懲罰期。

其中，設(shè)定一次交易行為的交易階段時(shí)長不必相等但是不可小于某一固定閾值，令表示懲罰期的階段數(shù)量，那么工作者接受的懲罰期時(shí)長不小于。懲罰期包含的階段數(shù)量成為懲罰計(jì)數(shù)因子。懲罰-激勵(lì)機(jī)制通過調(diào)整區(qū)分對于不同偏離行為的懲罰力度，其中的取值與工作者在本次交易之前的歷史交易行為有關(guān)[16]。本文中的計(jì)算方法是令，即當(dāng)工作者是初次或是偶爾進(jìn)入懲罰期時(shí)，其信譽(yù)值恢復(fù)的速度較快；而當(dāng)工作者具有惡意行為時(shí)，則其信譽(yù)值恢復(fù)速度越來越小。因而實(shí)現(xiàn)了根據(jù)工作者的歷史行為決定懲罰力度這一特點(diǎn)。

2.3 反饋可信度判定

由上述建立的信譽(yù)計(jì)算模型可知，任務(wù)發(fā)布者對于工作者的反饋消息對工作者的信譽(yù)狀況以及是否觸發(fā)懲罰有著決定性作用。然而，由于任務(wù)發(fā)布者對于工作者的評價(jià)可能有失公正，甚至可能存在惡意誹謗從而達(dá)到擾亂系統(tǒng)秩序的惡意行為，有必要對任務(wù)發(fā)布者的反饋進(jìn)行可信度的判定。

首先引入消極反饋率的概念，其定義如下：

3 基于眾包平臺的重復(fù)博弈分析

3.1 單階段博弈模型

在眾包平臺上，工作者在選擇盡力工作時(shí)，存在資源占用及消耗等成本，記作，在不盡力工作時(shí)，認(rèn)為成本為0；當(dāng)工作者盡力工作，任務(wù)發(fā)布者可以收到任務(wù)委托方價(jià)值為的報(bào)酬；此外，任務(wù)發(fā)布者需要支付給工作者的報(bào)酬值為。

設(shè)為階段博弈，在眾包平臺的用戶之間的長期行為是階段博弈的無限次重復(fù)博弈，記作,為貼現(xiàn)因子。工作者的行為選擇策略集合為{H, L}，分別表示用戶節(jié)點(diǎn)選擇{盡力工作，不盡力}；任務(wù)發(fā)布者的行為選擇策略集合為{Pay, No Pay}，分別表示任務(wù)發(fā)布者選擇支付和不支付工作者的報(bào)酬。則任意一對任務(wù)發(fā)布者和工作者，在某一時(shí)刻的交互中收益矩陣的定義如表2所示。

表2 眾包平臺協(xié)作收益矩陣

從表1中可知，在只考慮一輪博弈的情況下，其納什均衡為(No Pay, L)，即平臺中將不存在任何的合作行為，且所有用戶的收益均為0，這就形成了包平臺中的“囚徒困境”。

3.2 重復(fù)博弈分析

重復(fù)博弈是指同樣結(jié)構(gòu)的博弈重復(fù)許多次，其中的每次博弈稱為“階段博弈”[17]。在任何重復(fù)博弈中，參與人行動(dòng)的有序性意味著他們在本回合中采取的策略取決于前一回合中的行動(dòng)，這樣的策略被稱為是條件策略[17]。

在上述階段博弈的一次性博弈有唯一的純策略納什均衡(No Pay, L)，此時(shí)雙方得益為(0, 0)，顯然該納什均衡并不是帕雷特效率意義上的最佳策略組合，最佳策略組合是(Pay, H)，然而(Pay, H)在一次博弈中不會(huì)出現(xiàn)，因?yàn)槊總€(gè)人都有改變策略的動(dòng)力。

第2階段是信譽(yù)值為PL時(shí)，工作者仍然選擇了不盡力完成工作，但是此時(shí)進(jìn)入懲罰期。這個(gè)階段獲得的收益為

這里考慮多重博弈的博弈階段數(shù)量為工作者接受的懲罰期的階段數(shù)，為。令，則收益1可以表示為

考慮相反的情形，若工作者選擇盡力完成工作，其收益2為

式(7)可以簡化為

為了激勵(lì)工作者的盡力工作，必須保證在考慮重復(fù)博弈的情況下，選擇盡力工作的預(yù)期收益不低于采取不盡力工作時(shí)的預(yù)期收益。因此，為了保證，即

在理性工作者做出決策之前，都會(huì)對將來的預(yù)期收益進(jìn)行評估，如果式(9)成立，則結(jié)點(diǎn)必將選擇盡力完成任務(wù)。作為平臺設(shè)計(jì)者，可以針對不同的設(shè)置相應(yīng)的值，使式(9)成立，從而促進(jìn)用戶的協(xié)作。從式(9)中可以看出，懲罰機(jī)制是靠引入負(fù)收益來實(shí)現(xiàn)的，懲罰的力度取決于，并且文中的值是由該工作者的歷史行為決定的，是動(dòng)態(tài)變化的。將式(9)化簡，可得

4 仿真測試與分析

本文提出了基于信譽(yù)值的激勵(lì)機(jī)制，綜合考慮了工作者的歷史交易行為，采用多重博弈的思想，理論上求解出了滿足激勵(lì)一致性的條件。為驗(yàn)證本文提出機(jī)制的有效性，在MyEclipse[8]實(shí)驗(yàn)環(huán)境下進(jìn)行了仿真實(shí)驗(yàn)，并對結(jié)果進(jìn)行了比較和分析。

4.1 仿真設(shè)置與仿真方法

在MyEclipse實(shí)驗(yàn)環(huán)境中模擬20個(gè)工作者和1個(gè)任務(wù)發(fā)布者。其中工作者的類型分為兩類：理性工作者和自私工作者。其中理性工作者通過判斷當(dāng)前自身是否滿足激勵(lì)一致性的條件，決定是否盡力完成工作。自私工作者不受激勵(lì)的影響，在非懲罰期的階段，始終選擇不盡力完成工作。

在實(shí)驗(yàn)中，為了模擬實(shí)際的眾包平臺，設(shè)定即使理性工作者通過判別滿足了一致性的條件，也并不一定選擇盡力工作，而是以某種概率選擇盡力工作，并且這個(gè)概率和當(dāng)前眾包平臺中設(shè)置的貼現(xiàn)相關(guān)聯(lián)，越大，值相應(yīng)設(shè)置越高。

重復(fù)博弈模型中的相關(guān)參數(shù)設(shè)置如下：= 2;0=3;=1;=7為了模擬實(shí)際的眾包平臺，設(shè)定工作者的初始懲罰次數(shù)隨機(jī)取0~4。自私工作者所占的比例默認(rèn)為0.2。

參數(shù)的設(shè)置在表3中給出，其中懲罰期基數(shù)0和懲罰力度因子已在表1中進(jìn)行了定義，收益參數(shù)和消耗參數(shù)已在表2中進(jìn)行了定義。

表3 眾包平臺參數(shù)設(shè)置

在仿真過程中，每類實(shí)驗(yàn)進(jìn)行5次，每次試驗(yàn)由10個(gè)交易階段組成，仿真結(jié)果取5次實(shí)驗(yàn)的平均值。在下面的仿真實(shí)驗(yàn)中，重點(diǎn)考察激勵(lì)一致性條件(式(10))中涉及到的參數(shù)，以及自私工作者所占比例和懲罰次數(shù)初值等因素對高質(zhì)量工作完成比例的影響，進(jìn)而驗(yàn)證激勵(lì)機(jī)制的有效性。另外，為了驗(yàn)證2.3節(jié)中反饋可信度判定機(jī)制的有效性，針對該機(jī)制對高質(zhì)量完成工作比例的影響，本文同樣進(jìn)行了仿真實(shí)驗(yàn)。這里定義高質(zhì)量工作完成的比例：用戶盡力完成的工作的數(shù)量與完成工作總數(shù)量的比值。定義信譽(yù)值的最大值為式(10)中的。定義信譽(yù)值閾值與信譽(yù)值最大值的比值為。

4.2 實(shí)驗(yàn)結(jié)果與分析

通過以上環(huán)境設(shè)置，在MyEclipse中進(jìn)行仿真。將得到的評價(jià)指標(biāo)數(shù)據(jù)輸出到MATLAB R2014a中，進(jìn)行比較分析。

(1)激勵(lì)一致性條件中涉及到的參數(shù)： 由圖1(a)可知，當(dāng)，隨著的增加，高質(zhì)量工作完成的比例顯著增加，并且逐漸趨于穩(wěn)定狀態(tài)。這是由于，根據(jù)激勵(lì)一致性條件，當(dāng)變大，工作者選擇合作帶來的長期收益相應(yīng)增加，更有可能被激勵(lì)產(chǎn)生高質(zhì)量的工作。

圖1 和對高質(zhì)量工作完成比例的影響

(2)自私工作者所占比例對于完成工作質(zhì)量的影響： 圖2給出了當(dāng)，隨著自私工作者所占比例上升帶來的高質(zhì)量工作完成比例的變化，呈下降趨勢。因?yàn)樽运焦ぷ髡呖偸遣荒鼙患?lì)的，所以自私工作者所占比例上升會(huì)導(dǎo)致完成工作質(zhì)量下降。同時(shí)，當(dāng)自私結(jié)點(diǎn)比例為1時(shí)，高質(zhì)量工作完成比例只依賴于和，與無關(guān)。

圖2 自私結(jié)點(diǎn)所占比例對高質(zhì)量工作完成比例的影響

(3)懲罰次數(shù)初值對于完成工作質(zhì)量的影響：

圖3給出了不同懲罰次數(shù)初值下的仿真結(jié)果，可以看出，隨著懲罰次數(shù)初值增加，高質(zhì)量工作完成比例增加，這是由于，根據(jù)激勵(lì)一致性條件，當(dāng)初始懲罰期變長，理性工作者選擇合作帶來的長期收益相應(yīng)增加，更有可能被激勵(lì)產(chǎn)生高質(zhì)量的工作。同時(shí)觀察得到，懲罰次數(shù)的初值為0,1,2時(shí)，高質(zhì)量工作完成的比例變化顯著并且相對不穩(wěn)定，這是由于，在懲罰期的初值較小時(shí)，對于促使激勵(lì)條件成立的作用較小，容易受,與變化的影響，并且在本文中，理性工作者選擇盡力工作的概率是隨機(jī)的，因而，高質(zhì)量工作完成的比例變化顯著并且相對不穩(wěn)定。當(dāng)懲罰次數(shù)的初值大于2后，,與等參數(shù)的變化帶來的影響下降，所以圖3的4種情況中，高質(zhì)量工作的完成比例趨于相同，并且變化平緩。

圖3 懲罰次數(shù)初值對高質(zhì)量工作完成比例的影響

(4)反饋可信度判定機(jī)制對于完成工作質(zhì)量的影響： 該實(shí)驗(yàn)中，系統(tǒng)不存在自私工作者，全部都是理性工作者，但是設(shè)定在系統(tǒng)中，20%的工作者將會(huì)參與到惡意誹謗攻擊中，即，工作者始終向平臺反饋錯(cuò)誤的評價(jià)信息。同時(shí)設(shè)置=10,=0.7,=0.55。在仿真實(shí)驗(yàn)中，參與惡意誹謗攻擊的工作者始終堅(jiān)持誹謗，不受系統(tǒng)中信譽(yù)機(jī)制和懲罰機(jī)制的影響。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 反饋可信度判定機(jī)制對高質(zhì)量工作完成比例的影響

從實(shí)驗(yàn)結(jié)果中可以看到，當(dāng)系統(tǒng)中20%的工作者參與到惡意誹謗攻擊中，并且不存在反饋可信度判定機(jī)制時(shí)，高質(zhì)量完成工作的比例逐漸下降。這其中的原因是，部分正常的理性工作者雖然高質(zhì)量地完成了工作，系統(tǒng)卻按照惡意的反饋信息將該工作判定為低質(zhì)量，導(dǎo)致系統(tǒng)高質(zhì)量完成工作的比例下降(從系統(tǒng)計(jì)算得到的結(jié)果來看)。同時(shí)，會(huì)導(dǎo)致這部分理性工作者的信譽(yù)值降低。隨著交易過程的持續(xù)，正常的理性工作者將會(huì)反復(fù)被懲罰進(jìn)入到懲罰期內(nèi)，即，正常的理性工作者即使高質(zhì)量完成工作，仍然不能得到對應(yīng)的信譽(yù)值，眾包平臺的正常秩序被打亂。

相反，在反饋可信度判定機(jī)制存在的情況下，即使存在20%的參與誹謗攻擊的工作者，系統(tǒng)高質(zhì)量工作完成的比例和不存在誹謗攻擊時(shí)的比例相差不大。該實(shí)驗(yàn)證明，2.3節(jié)中提出的反饋可信度判定機(jī)制是有效的。

(5)本文中的激勵(lì)模型與QDA[11]機(jī)制的對比：

圖5 本文激勵(lì)模型與QDA機(jī)制的對比

5 結(jié)束語

本文基于重復(fù)博弈，提出了一種基于信譽(yù)值的激勵(lì)模型，用于激勵(lì)理性工作者高質(zhì)量地完成任務(wù)；此外，本文針對惡意工作者做出相應(yīng)的懲罰。最后通過仿真實(shí)驗(yàn)證明了激勵(lì)機(jī)制的有效性，仿真結(jié)果表明，通過合理選擇懲罰參數(shù)，可以有效激勵(lì)理性工作者高質(zhì)量完成工作，提高眾包平臺的高質(zhì)量工作完成比例。

接下來的工作將考慮文中提出的基于信譽(yù)值進(jìn)行分配的任務(wù)調(diào)度算法進(jìn)行實(shí)現(xiàn)，進(jìn)一步提高眾包平臺的效率和用戶滿意度。

[1] 張志強(qiáng), 逄居升, 謝曉芹, 等. 眾包質(zhì)量控制策略及評估算法研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(8): 1636-1649. doi: 10.3724/ SP.J.1016.2013.01636.

ZHANG Z Q, PANG J S, XIE X Q,. Research on crowdsourcing quality control strategies and evaluation algorithm[J]., 2013, 36(8): 1636-1649. doi: 10.3724/SP.J.1016.2013.01636.

[2] HOSSEINI M, PHALPK, TAYLOR J,. The four pillars of crowdsourcing: A reference model[C]. 2014 IEEE Eighth International Conference on Research Challenges in Information Science (RCIS), Marrakech, 2014: 1-12. doi: 10. 1109/RCIS.2014.6861072.

[3] SHEN H, LI Z, LIU J,.. Knowledge sharing in the online social network of Yahoo! answers and its implications [J]., 2014, 64(6): 1715-1728. doi: 10.1109/TC.2014.2322598.

[4] WU H, CORNEY J, and GRANT M. Relationship between quality and payment in crowdsourced design[C]. Proceedings of the 2014 IEEE 18th International Conference on Computer Supported Cooperative Work in Design (CSCWD), Hsinchu, 2014: 499-504. doi: 10.1109/CSCWD.2014.6846895.

[5] DOAN A, RAMAKRISHNAN R, and HALEVY A, Crowdsourcing systems on the World-Wide Web[J]., 2011, 54(4): 86-96. doi: 10. 1145/1924421.1924442.

[6] MALANDRINO F, CASETTI C, and CHIASSERINI C. Content discovery and caching in mobile networks with infrastructure[J]., 2012, 61(10): 1507-1520. doi: 10.1109/TC.2011.216.

[7] 謝曉蘭, 劉亮, 趙鵬. 面向云計(jì)算基于雙層激勵(lì)和欺騙檢測的信任模型[J]. 電子與信息學(xué)報(bào), 2012, 34(4): 812-817. doi: 10.3724/SP.J.1146.2011.00787.

XIE X L, LIU L, and ZHAO P. Trust model based on double incentive and deception detection for cloud computing [J].&, 2012, 34(4): 812-817. doi: 10.3724/SP.J.1146.2011.00787.

[8] 楊明, 劉元安, 馬曉雷, 等. 一種基于定價(jià)與信任的網(wǎng)絡(luò)資源分配算法[J]. 電子與信息學(xué)報(bào), 2010, 32(4): 846-851. doi: 10.3724/SP.J.1146.2009.00435.

YANG M, LIU Y A, MA X L,. A grid resource allocation algorithm based on pricing and trust[J].&, 2010, 32(4): 846-851. doi: 10.3724/SP.J.1146.2009.00435.

[9] YANG D, XUE G, FANG X,. Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing[C]. Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (MOBICOM 2012), New York, 2012: 173-184.

[10] ZHANG Y and SCHAAR M. Reputation-based incentive protocols in crowdsourcing applications[C]IEEE INFOCOM, Orlando, FL, 2012: 2140-2148. doi: 10.1109/INFCOM.2012. 6195597.

[11] WEN Y, SHI J, ZHANG Q,. Quality-driven auction- based incentive mechanism for mobile crowd sensing[J], 2014, 64(9): 4203-4214. doi: 10.1109/TVT.2014.2363842.

[12] TSUDA T, KOMAI Y, SSASKI Y,. Top-k query processing and malicious node identification against data replacement attack in MANETs[C]. IEEE 15th International Conference on Mobile Data Management (MDM), Brisbane, 2014: 279-288. doi: 10.1109/MDM.2014.40.

[13] XU Q, XIONG J, HUANG Q,. Online HodgeRank on random graphs for crowdsourceable QoE evaluation[J].,2014, 16(2): 373-386. doi: 10.1109/TMM.2013.2292568.

[14] ANEGEKUH L, SUN L, and IFEACHOR E. A screening methodology for crowdsourcing video QoE evaluation[C]IEEE Global Communications Conference (GLOBECOM), Austin, TX, 2014. doi: 10.1109/GLOCOM.2014.7036964.

[15] DANG D, LIU K, ZHANG Y, et. A crowdsourcing worker quality evaluation algorithm on MapReduce for big data applications[J]., 2015. doi: 10.1109/TPDS.2015. 2457924.

[16] 桂春梅. 虛擬計(jì)算環(huán)境下信譽(yù)機(jī)制關(guān)鍵技術(shù)研究[D]. [博士論文], 國防科技大學(xué), 2009.

[17] DIXIT A, REILEY D, and SKEATH S. Games of Strategy [M]. New York, US, W. W. Norton & Company, Inc., 2009: 345-354.

Reputation-based Incentive Mechanisms in Crowdsourcing

RUI Lanlan ZHANG Pan HUANG Haoqiu QIU Xuesong

(,,100876,)

Crowdsourcing is a new distributed problem solving pattern brought by the Internet. However, intrinsic incentive problems reside in crowdsourcing applications as workers and requester are selfish and aim to maximize their own benefit. In this paper, the following key contributions are made. A reputation-based incentive model is designed using repeated game theory, based on thorough analysis for current research on reputation and incentive mechanism; and a punishment mechanism is established to counter selfish workers. The experiment results show that the new established model can efficiently motivate the rational workers and counter the selfish ones. By setting punishment parameters appropriately, the overall performance of crowdsourcing system can be improved up to 90%, even if the fraction of selfish workers is 20%.

Crowdsourcing system; Incentive mechanisms; Punishment mechanisms; Repeated game

TP393

A

1009-5896(2016)07-1808-08

10.11999/JEIT151095

2015-09-25；改回日期：2016-04-22；網(wǎng)絡(luò)出版：2016-06-03

張攀 1483462789@qq.com

國家自然科學(xué)基金(61302078, 61372108)，國家自然科學(xué)基金創(chuàng)新研究群體科學(xué)基金(61121061)，北京高等學(xué)校青年英才計(jì)劃項(xiàng)目(YETP0476)

The National Natural Science Foundation of China (61302078, 61372108), The Funds for Creative Research Groups of China (61121061), Beijing Higher Education Young Elite Teacher Project (YETP0476)

芮蘭蘭： 女，1979年生，博士，副教授，研究方向?yàn)榫W(wǎng)絡(luò)和業(yè)務(wù)質(zhì)量管理、泛在網(wǎng)絡(luò)、大數(shù)據(jù)等.

張 攀： 女，1993年生，碩士生，研究方向?yàn)楸姲鼨C(jī)制.

黃豪球： 男，1985年生，博士，研究方向?yàn)樾畔⒅行木W(wǎng)絡(luò).

邱雪松： 男，1973年生，教授，博士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)管理和通信軟件等.