三方眾包市場中的發(fā)包方平臺博弈機(jī)制設(shè)計(jì)

何雨橙 丁堯相 周志華

(計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)) 南京 210023)

隨著機(jī)器學(xué)習(xí)任務(wù)的規(guī)模逐漸增大，人們迫切需要對大規(guī)模數(shù)據(jù)進(jìn)行收集.眾包(crowdsourcing)作為低成本高效率的數(shù)據(jù)收集方式，受到了廣泛歡迎.

眾包研究的基本問題之一是設(shè)計(jì)有效的機(jī)制以使得參與者在競爭中實(shí)現(xiàn)共贏.當(dāng)前，眾包機(jī)制設(shè)計(jì)研究往往基于兩方眾包模型：發(fā)包方(requester)發(fā)布任務(wù)并支付標(biāo)注者(workers)費(fèi)用；標(biāo)注者完成任務(wù)并收取報(bào)酬[1].該模型的重要假設(shè)在于發(fā)包方和標(biāo)注者可以直接進(jìn)行交互.而現(xiàn)實(shí)應(yīng)用中，如圖1所示，發(fā)包方和標(biāo)注者的交互往往以平臺(platform)為中介，構(gòu)成三方眾包市場.其中，發(fā)包方將任務(wù)和報(bào)酬發(fā)布給平臺，平臺雇傭標(biāo)注者進(jìn)行標(biāo)記，進(jìn)而在將標(biāo)記結(jié)果反饋給發(fā)包方的同時(shí)，賺取支付給標(biāo)注者的費(fèi)用和發(fā)包方支付給自己的費(fèi)用之間的差價(jià).顯然，傳統(tǒng)的兩方眾包模型無法對該過程進(jìn)行建模，因此需要引入全新的三方眾包模型進(jìn)行研究.

Fig. 1 The three-party crowdsourcing market圖1 三方眾包市場示意圖

相比于兩方眾包，三方眾包的核心問題是發(fā)包方與平臺之間的博弈：發(fā)包方希望支付較少的報(bào)酬同時(shí)獲取準(zhǔn)確率較高的標(biāo)記；而平臺則希望降低雇傭標(biāo)注者的成本，同時(shí)從發(fā)包方處獲取較多的報(bào)酬.這之中存在著復(fù)雜的博弈關(guān)系.一方面，發(fā)包方和平臺既有合作也有競爭：雙方都希望最大化標(biāo)記的準(zhǔn)確率，但在最小化或最大化發(fā)包方支付這一點(diǎn)上有沖突.另一方面，發(fā)包方和平臺各自只能掌握自身信息，而無法直接觀測到對方信息.在不完全信息下采取最優(yōu)策略，對雙方都是相當(dāng)具有挑戰(zhàn)性的問題.

本文開啟三方眾包市場中的發(fā)包方-平臺博弈機(jī)制設(shè)計(jì)研究，主要貢獻(xiàn)有4點(diǎn)：

1) 提出不完全信息博弈[2]模型CrowdMarket對三方眾包市場進(jìn)行建模，并證明通過設(shè)計(jì)合適的在線學(xué)習(xí)策略可以近似達(dá)到該博弈的Nash均衡；

2) 在單發(fā)包方設(shè)定下，證明了EXP3算法[3]為發(fā)包方的最優(yōu)策略，進(jìn)而本文設(shè)計(jì)了基于反事實(shí)遺憾最小化(counterfactual regret minimization, CFR)技術(shù)[4-5]的平臺策略，證明該策略能夠充分利用平臺方的有效信息，具有比直接應(yīng)用傳統(tǒng)在線學(xué)習(xí)方法更強(qiáng)的理論保證；

3) 將單發(fā)包方的策略拓展到多發(fā)包方的情形，并給出了多發(fā)包方情形下的理論分析；

4) 通過合成及真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了方法的有效性.

1 相關(guān)工作

眾包研究的核心問題之一在于如何平衡標(biāo)記質(zhì)量和支付費(fèi)用[6-7].現(xiàn)有研究中，實(shí)現(xiàn)這一目標(biāo)的方式可以分成2類：設(shè)計(jì)更好的標(biāo)記推斷方法以及設(shè)計(jì)更好的眾包機(jī)制.標(biāo)記推斷已經(jīng)有了豐富的研究，例如文獻(xiàn)[8-11].本文則著力于探討機(jī)制設(shè)計(jì)問題.

兩方眾包機(jī)制設(shè)計(jì)已經(jīng)得到了充分研究，其中包括任務(wù)與報(bào)酬的分配機(jī)制設(shè)計(jì)[12-15]，以及利用提供線索[16]或跳過選項(xiàng)[17-19]等方式提升高難度樣本的標(biāo)記質(zhì)量.由于這些機(jī)制都是針對標(biāo)注者的，因此這些策略同樣可以應(yīng)用于三方眾包市場中作為平臺與標(biāo)注者之間的博弈機(jī)制.并且由于這方面的研究相對成熟，本文不再對此進(jìn)行深入探討.同時(shí)，也有大量的研究關(guān)注如何設(shè)計(jì)合適的支付策略以激勵(lì)標(biāo)注者給出高質(zhì)量的標(biāo)記.這方面的代表性工作包括文獻(xiàn)[20-23].在我們的問題設(shè)定中，這些激勵(lì)機(jī)制可以被平臺用于激勵(lì)標(biāo)注者給出更準(zhǔn)確的標(biāo)記，但是不能直接用于處理平臺和發(fā)包方之間的博弈.

近期以來，一些工作也開始從應(yīng)用的角度關(guān)注三方眾包市場.例如文獻(xiàn)[24]提出了一種聲譽(yù)評價(jià)方法以防止發(fā)包方和標(biāo)注者的欺騙行為，而文獻(xiàn)[25]則將眾包市場建模為一個(gè)3層的優(yōu)化問題以最大化平臺的健康度.但這些工作均不涉及博弈機(jī)制設(shè)計(jì)研究，因而它們的研究動機(jī)與本文有著顯著的差異.

當(dāng)前，將眾包形式化為博弈問題，特別是預(yù)算有限條件下的收益最大化問題，是一個(gè)重要的理論研究方向[26-28].這個(gè)方向上的現(xiàn)有研究主要集中于傳統(tǒng)兩方設(shè)定，本文所提出的三方眾包模型，對拓展這一方向的研究內(nèi)容可能起到有益的作用.此外，近期也有工作研究如何在廣告市場中利用機(jī)器學(xué)習(xí)方法從數(shù)據(jù)中學(xué)習(xí)有效的三方博弈機(jī)制[29].本文的研究也為將這種新方法引入眾包博弈問題提供了有益啟示.

2 CrowdMarket模型

2.1 基本定義

本節(jié)提出三方眾包模型CrowdMarket，將三方眾包市場形式化為發(fā)包方、平臺以及標(biāo)注者三方的不完全信息博弈[2].本節(jié)討論單發(fā)包方情形，第4節(jié)中將對多發(fā)包方情形進(jìn)行討論.

單發(fā)包方情形下的CrowdMarket模型為持續(xù)T輪的博弈，在第t輪下：

1) 發(fā)包方發(fā)送一個(gè)包含b個(gè)任務(wù)的任務(wù)包，以及支付報(bào)酬xt∈(0,1]給平臺.本文假設(shè)發(fā)包方只能從有限數(shù)量的K個(gè)報(bào)酬選項(xiàng)X1,X2,…,XK中選擇合適的報(bào)酬.

2) 在收到報(bào)酬和任務(wù)包之后，平臺選擇mt個(gè)標(biāo)注者完成標(biāo)注任務(wù).

3) 標(biāo)注者各自選擇采取低等級的努力或者高等級的努力以完成任務(wù).高努力下準(zhǔn)確率為p*>1/2；而低努力下標(biāo)注者隨機(jī)猜測以返回標(biāo)記，準(zhǔn)確率為1/2.之后每位標(biāo)注者各自獨(dú)立地為每個(gè)任務(wù)進(jìn)行標(biāo)注，并將結(jié)果反饋給平臺.

4) 平臺將每位標(biāo)注者給出的標(biāo)記通過多數(shù)投票法進(jìn)行集成，并將集成后標(biāo)記返回給發(fā)包方.集成后標(biāo)記的實(shí)際平均準(zhǔn)確率記為at.發(fā)包方從返回的標(biāo)記中得到的收益取決于該準(zhǔn)確率以及支付給平臺的報(bào)酬，因此可以表示為at-xt.

5) 平臺從發(fā)包方的支付中取出一部分作為參與了本輪標(biāo)注的標(biāo)注者的報(bào)酬，其余作為自己的收益.

為了激勵(lì)標(biāo)注者給出高質(zhì)量的標(biāo)記，平臺需要得知標(biāo)注者給出的標(biāo)記的準(zhǔn)確程度，這就需要發(fā)包方向平臺提供反饋.因此，我們引入了這樣一個(gè)步驟：發(fā)包方在每一輪結(jié)束之后會向平臺反饋該輪標(biāo)記的準(zhǔn)確率.參考文獻(xiàn)[17]，可以設(shè)計(jì)激勵(lì)機(jī)制來確保發(fā)包方會誠實(shí)地反饋標(biāo)記準(zhǔn)確率，在3.1節(jié)中我們將會給出該激勵(lì)機(jī)制并進(jìn)行分析.另外，本文假設(shè)平臺只能有部分輪次得到真實(shí)標(biāo)記.因此，平臺不能在任意輪次中直接推斷出標(biāo)記準(zhǔn)確率.

每一輪中參與者可能選擇的動作組成的集合稱為動作集.具體而言，發(fā)包方的動作集為Areq={(x,a′):x∈{X1,X2,…,XK},a′∈[0,1]}，其中x代表支付給平臺的報(bào)酬，a′代表匯報(bào)的準(zhǔn)確率；平臺的動作集為Apla=(m,c):m∈{1,2,…,N},c∈N}，其中m代表平臺選擇標(biāo)注的人數(shù)，c代表為每一位標(biāo)注者支付的報(bào)酬組成的向量(m

2.2 CrowdMarket博弈的分解

CrowdMarket模型是一個(gè)多方非零和博弈[30]，這是博弈論中最難分析的博弈類型.但是，該模型有特殊的結(jié)構(gòu)：發(fā)包方和標(biāo)注者之間并沒有直接的交互.利用這一點(diǎn)，我們可以將CrowdMarket模型分解成2個(gè)部分：發(fā)包方和平臺之間的博弈以及平臺和標(biāo)注者之間的博弈.其中，平臺和標(biāo)注者之間的博弈與傳統(tǒng)的兩方眾包中發(fā)包方和標(biāo)注者之間的博弈是類似的，因此平臺需要設(shè)計(jì)機(jī)制以激勵(lì)標(biāo)注者采取高等級的努力.并且，需要同時(shí)引入激勵(lì)機(jī)制使發(fā)包方誠實(shí)反饋準(zhǔn)確率.

3 平臺激勵(lì)機(jī)制設(shè)計(jì)

本節(jié)介紹平臺需要采用2個(gè)激勵(lì)機(jī)制：1)激勵(lì)發(fā)包方誠實(shí)反饋準(zhǔn)確率信息的機(jī)制；2)激勵(lì)標(biāo)注者采取高等級努力的機(jī)制.

3.1 激勵(lì)發(fā)包方誠實(shí)反饋的機(jī)制

在CrowdMarket模型中，平臺可以獲得發(fā)包方反饋的準(zhǔn)確率信息a′t.但是，發(fā)包方可能會試圖通過反饋一個(gè)虛假的準(zhǔn)確率a′t進(jìn)行欺詐.為了防止這一點(diǎn)，受到文獻(xiàn)[17]中“沒有免費(fèi)的午餐”(no-free-lunch)原則的啟發(fā)，我們?yōu)槠脚_設(shè)計(jì)了一個(gè)懲罰機(jī)制以防止發(fā)包方欺詐.

本文假設(shè)在CrowdMarket博弈過程中，平臺可以隨機(jī)選取某些輪次通過第三方得到真實(shí)標(biāo)記,進(jìn)而在這些輪次中對發(fā)包方反饋的標(biāo)記準(zhǔn)確率進(jìn)行驗(yàn)證.如果驗(yàn)證發(fā)現(xiàn)發(fā)包方反饋的準(zhǔn)確率不正確，即發(fā)包方在該輪進(jìn)行了欺詐，那么平臺將會對發(fā)包方進(jìn)行一定的懲罰.

我們首先定義指示變量序列yt,t=1,2,…,T如下：

懲罰機(jī)制可以表示為指示變量序列的一個(gè)函數(shù)f(y1,y2,…,yT)：在眾包博弈結(jié)束后，發(fā)包方需要支付f(y1,y2,…,yT)給平臺作為欺詐的懲罰.為了確保公平性，懲罰機(jī)制需要滿足2個(gè)基本條件：

第1個(gè)條件是平臺不能在沒有發(fā)現(xiàn)發(fā)包方欺詐的情形下進(jìn)行懲罰；相反，如果發(fā)包方被發(fā)現(xiàn)在每輪都作弊了，那么需要支付最大數(shù)額的懲罰金額Fmax.該條件可以形式化為定義1.

定義1.如果懲罰機(jī)制f滿足:

1) 若yt≠1對所有t=1,2,…,T成立且存在t使得yt=-1，則f(y1,y2,…,yT)=Fmax.

2) 若yt=1對所有t=1,2,…,T成立，則f(y1,y2,…,yT)=0.

則稱f滿足“沒有免費(fèi)的午餐”條件.

第2個(gè)條件是發(fā)包方應(yīng)該支付懲罰當(dāng)且僅當(dāng)其被發(fā)現(xiàn)有欺詐行為.該條件可形式化為定義2.

定義2.如果懲罰機(jī)制f滿足:對于任意輪次t∈{1,2,…,T}以及任意

(y1,…,yt-1,yt+1,…,yT)∈{-1,0,1}T-1

都有

f(y1,…,yt-1,1,yt+1,…,yT)=
f(y1,…,yt-1,0,yt+1,…,yT)≤
f(y1,…,yt-1,-1,yt+1,…,yT)，

那么稱f滿足“激勵(lì)相容”條件.

基于這2個(gè)條件，我們提出如下機(jī)制：

(1)

其中，I(yt≠-1)為指示函數(shù).

式(1)表明：如果被發(fā)現(xiàn)在眾包過程中有欺詐行為，發(fā)包方會支付最大數(shù)額的懲罰.顯然，式(1)所述的機(jī)制滿足我們提出的2個(gè)條件.我們可以進(jìn)一步證明定理1成立，定理1表明了由式(1)定義的懲罰機(jī)制是滿足我們所要求的2個(gè)條件的唯一機(jī)制.

定理1.當(dāng)Fmax≥T2時(shí)，式(1)機(jī)制是唯一滿足“沒有免費(fèi)的午餐”條件和“激勵(lì)相容”條件的機(jī)制,且發(fā)包方最優(yōu)策略是每輪誠實(shí)反饋收益信息.

證明.假設(shè)f是同時(shí)滿足定理要求的2個(gè)條件的機(jī)制.我們只需要證明：當(dāng)所有的指示變量yi≠-1時(shí)f(y1,y2,…,yT)=0，否則f(y1,y2,…,yT)=T即可.

1) 當(dāng)?i∈[t]:yi≠-1時(shí)，我們假設(shè)y1,y2,…,yT中有k個(gè)1和T-k個(gè)0.不失一般性地，可以假設(shè)前k個(gè)變量取值為1，其余變量取值為0.由“沒有免費(fèi)的午餐”可知：

2) 平臺僅在第t輪進(jìn)行了1次檢查，且yt=-1.根據(jù)“沒有免費(fèi)的午餐”條件，該情況下懲罰為Fmax.又由“激勵(lì)相容”條件易知，任何存在yi≠-1,i=1,2,…,T的情況下，懲罰均不應(yīng)小于該情況，也為Fmax.

綜上即是該機(jī)制為唯一滿足條件的機(jī)制.

接下來考慮該機(jī)制下發(fā)包方作弊能得到的額外收益.考慮極端情況：發(fā)包方只需要在其中1輪作弊，未被發(fā)現(xiàn)即可得到最大收益R，被發(fā)現(xiàn)則要另外支付懲罰T.再設(shè)發(fā)包方不作弊得到的收益為r，平臺檢查的輪數(shù)所占比例為p.由于平臺至少檢查1次，因此p≥1/T.對發(fā)包方而言，不作弊是最優(yōu)策略當(dāng)且僅當(dāng)

p(R-Fmax)+(1-p)R≤r，

解不等式得p≥(R-r)/Fmax.由于在CrowdMarket模型中，R-r≤T，因而上述不等式恒成立.這表明誠實(shí)反饋是發(fā)包方的最優(yōu)策略.

證畢.

3.2 激勵(lì)標(biāo)注者采取高等級努力的機(jī)制

標(biāo)注者i獲得的總收益為

(2)

式(2)采用了一個(gè)簡單的機(jī)制：如果被發(fā)現(xiàn)在標(biāo)注過程中有采取低等級努力行為，標(biāo)注者將無法得到該輪報(bào)酬，否則等價(jià)于每一次標(biāo)注都得到報(bào)酬ci.由于標(biāo)注者的目標(biāo)是最大化其收益，因而有定理2：

定理2.在式(2)機(jī)制下，標(biāo)注者的最佳策略為在所有輪次均采取高等級努力進(jìn)行標(biāo)注.

證明. 由于標(biāo)注者的目標(biāo)為最大化其收益，在任意t≤T輪中,顯然只有當(dāng)標(biāo)注者采取高等級努力時(shí)，所收獲的單輪回報(bào)最大，進(jìn)而知定理結(jié)論成立.

證畢.

注意到，由于標(biāo)注者所標(biāo)記的樣本是有限的，因而通過標(biāo)注是否正確判斷其努力程度存在一定錯(cuò)誤的可能性.在實(shí)際問題中，不難通過允許用戶對自身努力程度被錯(cuò)判的情況進(jìn)行申訴，來消除該錯(cuò)誤.

在本節(jié)給出的激勵(lì)機(jī)制的保證之下，平臺可以保證在每一輪中：1)發(fā)包方誠實(shí)匯報(bào)準(zhǔn)確率；2)標(biāo)注者選擇高等級努力，因而給出的標(biāo)記的準(zhǔn)確率為p*；3)平臺向每位被分配任務(wù)的標(biāo)注者支付報(bào)酬ci,由于標(biāo)注者之間相互等價(jià)(能力與標(biāo)注策略均相同)，每位標(biāo)注者的報(bào)酬均相同.在上述標(biāo)注者策略已經(jīng)固定的情況下，后文將集中研究如何設(shè)計(jì)發(fā)包方和平臺之間的博弈策略.另一方面，不妨將發(fā)包方與平臺已經(jīng)確定的動作從動作集中移除，以重點(diǎn)研究還未確定的動作：發(fā)包方-平臺博弈的每一輪中，發(fā)包方的動作是選擇支付給平臺的報(bào)酬，平臺的動作是選擇分配的標(biāo)注者人數(shù).為此，在下文中我們重新定義發(fā)包方和平臺的動作集分別為Areq={X1,X2,…,XK}，Apla={1,2,…,N}.發(fā)包方和平臺的策略空間也相應(yīng)地重新定義.

4 發(fā)包方-平臺博弈策略設(shè)計(jì)

本節(jié)介紹發(fā)包方和平臺在CrowdMarket博弈中采取的博弈策略.在4.1節(jié)我們證明發(fā)包方和平臺可以使用在線學(xué)習(xí)算法最小化自身遺憾；4.2節(jié)和4.3節(jié)分別給出發(fā)包方和平臺基于在線學(xué)習(xí)算法的策略.

4.1 基于在線學(xué)習(xí)的博弈策略

每個(gè)參與者的目標(biāo)均為最大化自身的累計(jì)收益，這等價(jià)于最小化自身的“遺憾”：

證明.首先以平臺為例進(jìn)行證明.由ε-最優(yōu)性的定義有

進(jìn)而，由于平臺收益是線性函數(shù)，我們可以得出：

發(fā)包方的效用函數(shù)可類似地表示為策略的線性函數(shù)，從而同理可證

證畢.

由于Nash均衡狀態(tài)代表了各方策略同時(shí)達(dá)到穩(wěn)定狀態(tài)，因而定理1表明，博弈各方只需采用能夠?qū)z憾進(jìn)行最小化的學(xué)習(xí)策略，就能在競爭中合作共贏.

4.2 發(fā)包方策略

注意到發(fā)包方可以將博弈過程建模為賭博機(jī)(bandit)在線學(xué)習(xí)問題：發(fā)包方可能選擇的支付動作Areq可視為賭博機(jī)搖臂，博弈產(chǎn)生的收益可以作為選擇特定搖臂之后得到的收益.進(jìn)而，發(fā)包方可以采用文獻(xiàn)[3]提出的EXP3算法作為其策略.下面的定理給出了任何發(fā)包方策略的遺憾下界，進(jìn)而驗(yàn)證了EXP3策略的最優(yōu)性.

證明.考慮這樣一種情況，標(biāo)注者能力p=1，即標(biāo)注者總是返回真實(shí)標(biāo)記；平臺通過以一定概率隨機(jī)反轉(zhuǎn)集成后標(biāo)記的方式控制返回給發(fā)包方的標(biāo)記準(zhǔn)確率.假設(shè)當(dāng)發(fā)包方選擇支付給平臺的報(bào)酬為x時(shí)，平臺翻轉(zhuǎn)標(biāo)記的概率為1-q(x)，即平臺提供的標(biāo)記的期望準(zhǔn)確率為a=q(x).

考慮函數(shù)q(x)=x+α+εI(x=x0)，I()表示指示函數(shù)，并且α足夠小從而使得q(x)∈[0,1].顯然此時(shí)發(fā)包方的期望收益u=q(x)-x=α+εI(x=x0)滿足以上條件.

證畢.

這與EXP3的遺憾上界同階，因而EXP3是發(fā)包方在缺乏信息的條件下所能采用的最優(yōu)策略.值得注意的是，平臺也可以由定理4得知發(fā)包方會使用EXP3策略.在4.3節(jié)我們會展示這一優(yōu)勢是如何幫助平臺制定策略的.

4.3 平臺策略

此時(shí)信息很不充足，對標(biāo)注者能力的估計(jì)誤差會很大.解決該挑戰(zhàn)的思路是，在每輪博弈中基于文獻(xiàn)[4]提出的CFR技術(shù)模擬之后的博弈過程.基于CFR的平臺博弈策略(以下簡稱CFR策略)如算法1所示：

算法1.CFR策略.

① 初始化置信區(qū)間I1=[0,1],P1={p:p∈I1}；

② 初始化歷史記錄H=?；

③ fort=1,2,…,T

⑥ 完成眾包并接收發(fā)包方反饋的收益at；

⑦ 將(mt,at)添加到H之中；

⑩ 更新It+1為

則有

(3)

其中,N為平臺最多可選擇的標(biāo)注者人數(shù).

另一方面，直接應(yīng)用原始的CFR算法無法達(dá)到理想效果.這是由于對于平臺而言，標(biāo)注者能力在博弈開始是未知的，必須通過對標(biāo)注者能力進(jìn)行有效估計(jì)，才能加快CFR算法的收斂速度.為了能更精確地得到對標(biāo)注者能力的估計(jì)，算法1中引入了標(biāo)注者能力估計(jì)步驟，利用Hoeffding不等式逐漸縮小標(biāo)注者能力的可能取值范圍(算法1行⑤～，行⑩中b為每輪任務(wù)數(shù)，δ為置信系數(shù)).隨著博弈輪數(shù)的增加，參數(shù)區(qū)間會越來越緊，從而起到逐漸縮小標(biāo)注者能力的可能取值集合的效果(算法1行).下述定理表明應(yīng)用該策略可以達(dá)到更緊的遺憾界.

定理5.當(dāng)博弈總輪數(shù)T充分大時(shí)，以至少1-δ的概率，算法1中的策略的期望遺憾上界為O(logT).

(4)

(5)

其中,εt表示模擬過程和真實(shí)過程之間有差異的平均概率.結(jié)合式(4)和式(5)可知，總的遺憾上界為

當(dāng)t

證畢.

定理5說明算法1的遺憾界顯著優(yōu)于EXP3策略，表明該策略充分利用了前文所述的額外信息.

5 多發(fā)包方情形下的策略

本節(jié)討論多發(fā)包方CrowdMarket模型的博弈機(jī)制.如果標(biāo)注者群體可以同時(shí)為所有的發(fā)包方提供服務(wù)，那么平臺只需要和每一個(gè)發(fā)包方單獨(dú)進(jìn)行CrowdMarket博弈，此時(shí)多發(fā)包方和單發(fā)包方的情形是完全一致的.但是如果標(biāo)注者群體在同一時(shí)間只能為部分發(fā)包方提供服務(wù)，那么發(fā)包方之間需要競爭服務(wù)的使用權(quán).因此，本節(jié)針對后一種情況進(jìn)行研究.

不失一般性，假設(shè)一共有n個(gè)發(fā)包方參與博弈，平臺在每一輪中為出價(jià)最高的發(fā)包方提供服務(wù).同時(shí)，假設(shè)單個(gè)發(fā)包方只能知道自己是否成功獲得服務(wù)，而無法得知其他發(fā)包方的出價(jià)以及任務(wù)完成準(zhǔn)確率信息.易知，在任何一輪當(dāng)中，出價(jià)最高而得到服務(wù)的發(fā)包方的收益和單發(fā)包方的情形相同，而未得到服務(wù)的發(fā)包方的收益則為0.

與單發(fā)包方條件下類似，在多發(fā)包方條件下，發(fā)包方仍然面臨著缺乏決策信息的問題：不僅無法得知平臺如何雇傭工人，而且無法得知其他發(fā)包方的情況.因而，可以類似地證明發(fā)包方的最優(yōu)策略為使用EXP3算法.接下來我們證明：平臺也仍可以使用CFR策略模擬多發(fā)包方的情形，以優(yōu)化自身的遺憾.

定理6.在有n個(gè)發(fā)包方情形下，當(dāng)博弈總輪數(shù)T充分大時(shí)，以至少1-δ的概率，CFR策略的期望遺憾上界為O(n(logn+logT)).

當(dāng)T≥nT1時(shí)，至少有一個(gè)發(fā)包方在至少T1輪贏得服務(wù)，而對于贏得服務(wù)小于T1輪的發(fā)包方，與其博弈的遺憾界是常數(shù)階.進(jìn)而知以至少1-δ的概率有

證畢.

6 實(shí)驗(yàn)驗(yàn)證

本節(jié)對發(fā)包方-平臺策略性能進(jìn)行驗(yàn)證.具體而言，本節(jié)實(shí)驗(yàn)對3點(diǎn)進(jìn)行驗(yàn)證：1)對于發(fā)包方，當(dāng)平臺使用強(qiáng)對抗性的策略時(shí)，EXP3策略是否有好的表現(xiàn)；2)對于平臺，CFR策略是否能利用額外信息給出更好的結(jié)果；3)對于多發(fā)包方的情形，發(fā)包方EXP3策略及平臺CFR策略是否依然適用.實(shí)驗(yàn)中發(fā)包方和平臺的動作集設(shè)定為：1)發(fā)包方可能的支付選項(xiàng)為{0.1,0.2,0.3}；2)平臺可能選擇的標(biāo)注者人數(shù)為{1,3,5}；3)平臺雇傭每個(gè)標(biāo)注者的成本C=0.01.

本節(jié)實(shí)驗(yàn)使用8個(gè)二分類真實(shí)數(shù)據(jù)集：1)BM數(shù)據(jù)集[33]，該數(shù)據(jù)集中標(biāo)注者對語料給出正面或負(fù)面情緒標(biāo)記；2)TEMP數(shù)據(jù)集[34]，該數(shù)據(jù)集中標(biāo)注者對2件事是否是先后發(fā)生的進(jìn)行標(biāo)記；3)WVSCM數(shù)據(jù)集[8]，該數(shù)據(jù)集中標(biāo)注者對圖片中人臉是否微笑進(jìn)行標(biāo)記；4)WB數(shù)據(jù)集[35]，該數(shù)據(jù)集中標(biāo)注者對圖片中的水鳥是否是鴨子進(jìn)行標(biāo)記；5)SpamCF數(shù)據(jù)集[36]，該數(shù)據(jù)集中標(biāo)注者對一個(gè)AMT平臺上的任務(wù)是否是垃圾任務(wù)進(jìn)行標(biāo)注；6)MediaEval數(shù)據(jù)集[36]，該數(shù)據(jù)集中標(biāo)注者對給定圖片是否和時(shí)尚有關(guān)進(jìn)行標(biāo)注；7)MEHCB數(shù)據(jù)集[37-38]，該數(shù)據(jù)集中標(biāo)注者對搜索請求和網(wǎng)頁是否有關(guān)進(jìn)行標(biāo)記；8)RTE數(shù)據(jù)集[34]，該數(shù)據(jù)集中標(biāo)注者對文本之間是否有蘊(yùn)含關(guān)系進(jìn)行標(biāo)注.實(shí)驗(yàn)所用8個(gè)數(shù)據(jù)集的相關(guān)信息如表1所示.

Fig. 2 The cumulative rewards of requester strategies under the single requester setting圖2 單發(fā)包方情形下發(fā)包方策略的累計(jì)收益對比

6.1 單發(fā)包方策略驗(yàn)證

本節(jié)在單發(fā)包方情形下，將發(fā)包方EXP3策略與ε-貪心策略(ε=0.05)及固定策略(始終固定在最高支付)進(jìn)行性能對比.同時(shí)，假設(shè)平臺使用高對抗性甚至是作弊性質(zhì)的策略，因?yàn)槲覀冃枰?yàn)證即便在最壞情形下EXP3策略仍然有效.

Table 1 Information About Datasets表1 實(shí)驗(yàn)所用數(shù)據(jù)集的相關(guān)信息

在我們的實(shí)驗(yàn)中，平臺和發(fā)包方用各自的策略進(jìn)行持續(xù)T輪的CrowdMarket博弈.輪次上限T的取值分別設(shè)定為10,15,…,40.本實(shí)驗(yàn)中假設(shè)平臺可獲取真實(shí)的標(biāo)注者能力p*，從而可以通過以一定概率翻轉(zhuǎn)標(biāo)記的方式準(zhǔn)確控制返回給發(fā)包方的標(biāo)記準(zhǔn)確率.并且，平臺會采用如下強(qiáng)對抗性的策略以誘導(dǎo)發(fā)包方提高支付：平臺以一定的概率q翻轉(zhuǎn)標(biāo)記，之后如果平臺收到了更高的報(bào)酬則會逐漸降低q的取值.平臺采用的這一策略要求發(fā)包方逐漸提高支付的報(bào)酬而不能只用貪心策略.本次實(shí)驗(yàn)中設(shè)定初始輪次中q=0.50,每次收到更高報(bào)酬后q的降低量分別設(shè)為0.02,0.03,0.04,0.05.在每組參數(shù)下我們重復(fù)實(shí)驗(yàn)50次并匯報(bào)平均累計(jì)收益.實(shí)驗(yàn)結(jié)果如圖2所示，實(shí)驗(yàn)結(jié)果可見，當(dāng)平臺使用強(qiáng)對抗性的策略時(shí)，發(fā)包方使用EXP3策略獲得的累計(jì)收益總是比ε-貪心策略和固定策略要好，這表明了EXP3策略的有效性.

6.2 多發(fā)包方策略驗(yàn)證

本節(jié)驗(yàn)證了3個(gè)發(fā)包方情形下，發(fā)包方使用EXP3策略的有效性.博弈過程的參數(shù)設(shè)定同6.1節(jié).

為了驗(yàn)證EXP3策略的有效性，在實(shí)驗(yàn)中我們令3個(gè)發(fā)包方分別使用EXP3策略、ε-貪心(ε=0.05)策略和固定策略，平臺使用的策略為CFR策略.我們令3個(gè)發(fā)包方在CrowdMarket博弈中使用不同策略相互競爭，勝出的發(fā)包方所使用的策略就是這3個(gè)策略中最優(yōu)的策略.為了保證公平性，所有發(fā)包方使用的數(shù)據(jù)集都是一樣的，以確保標(biāo)注者能力對于所有發(fā)包方是一致的.我們在8個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，每個(gè)數(shù)據(jù)集上重復(fù)10次.發(fā)包方累計(jì)收益的平均值如圖3所示.可以發(fā)現(xiàn)，使用EXP3策略在絕大多數(shù)時(shí)間內(nèi)都能獲得最多的收益，這表明EXP3策略在多發(fā)包方的情形下依然適用.

Fig. 3 The cumulative rewards of requester strategies under the multiple requester setting圖3 多發(fā)包方情形下各發(fā)包方策略的累計(jì)收益對比

6.3 平臺策略驗(yàn)證

為了驗(yàn)證平臺在單發(fā)包方與多發(fā)包方情形下使用CFR策略的性能，我們將CFR策略和EXP3策略、ε-貪心(ε=0.05)策略以及固定策略進(jìn)行了對比，發(fā)包方的策略固定為EXP3策略.博弈過程的參數(shù)設(shè)置與6.1節(jié)相同.單發(fā)包方情形下我們在8個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，在多發(fā)包方情形下則測試了2組發(fā)包方數(shù)據(jù)集的組合，所有實(shí)驗(yàn)結(jié)果如圖4所示.每張子圖展示了平臺的累計(jì)收益.實(shí)驗(yàn)結(jié)果顯示：無論在哪個(gè)數(shù)據(jù)集上，性能最好的策略均為CFR策略，其次是EXP3策略，再次是ε-貪心策略，排名最后的是固定策略.這表明利用到了額外信息的CFR策略確實(shí)能取得更好的效果.

Fig. 4 The cumulative rewards of the platform strategies under the single requester and multiple requester settings圖4 單發(fā)包方與多發(fā)包方情形下的平臺策略累計(jì)收益對比

表2展示了單發(fā)包方情形下，當(dāng)平臺使用不同策略，發(fā)包方使用EXP3策略時(shí)，40輪之后平臺和發(fā)包方的合計(jì)累計(jì)收益.結(jié)果表明平臺使用CFR策略可以使得雙方的累計(jì)收益達(dá)到最大.綜合上述結(jié)果可知，CFR策略是最適合于合作的策略.注意到平臺使用CFR策略是在發(fā)包方反饋準(zhǔn)確率信息時(shí)的最優(yōu)策略，而平臺使用EXP3策略是在發(fā)包方不反饋準(zhǔn)確率信息時(shí)的最優(yōu)策略.因此，表2中平臺使用CFR策略時(shí)，累計(jì)收益超過EXP3策略，這表明2.1節(jié)中引入的反饋步驟可以提升雙方的累計(jì)收益，對于雙方的合作有促進(jìn)作用.

Table 2 Total Rewards of Platform and Requester After 40 Round with Different Strategies of Platform

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

在本節(jié)中，我們利用仿真數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，對本文提出的基于在線學(xué)習(xí)方法的三方眾包市場發(fā)包方-平臺博弈策略進(jìn)行了驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，在符合CrowdMarket模型假設(shè)的條件下，本文提出的單發(fā)包方及多發(fā)包方策略不僅能優(yōu)化自身的累計(jì)收益，而且能達(dá)到促進(jìn)博弈雙方合作共贏的目的.這驗(yàn)證了本文提出策略的有效性.另一方面，在實(shí)際應(yīng)用中，也可能存在數(shù)據(jù)不符合CrowdMarket模型假設(shè)的情況.由于相關(guān)數(shù)據(jù)集的缺乏，難以驗(yàn)證在這一條件下本文方法的實(shí)際效果.我們會在未來研究中探索這一問題.

7 結(jié)束語

本文針對三方眾包市場中的發(fā)包方-市場機(jī)制設(shè)計(jì)問題進(jìn)行理論研究，提出三方眾包市場模型CrowdMarket.在該模型的基礎(chǔ)上，針對單發(fā)包方和多發(fā)包方的設(shè)定，研究平臺和發(fā)包方的策略設(shè)計(jì)和理論分析.真實(shí)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)驗(yàn)證了本文所提出的策略的有效性.我們相信本文的研究結(jié)果可以激發(fā)更多針對三方眾包市場的研究，有助于更好地理解現(xiàn)實(shí)應(yīng)用中眾包產(chǎn)業(yè)的市場行為.

作者貢獻(xiàn)聲明：何雨橙調(diào)研整理文獻(xiàn)，實(shí)施方法研究，完成實(shí)驗(yàn)，撰寫論文;丁堯相設(shè)計(jì)研究方案，實(shí)施方法研究，修訂論文;周志華提出研究選題，指導(dǎo)方法研究與論文撰寫支持.