• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2022-11-11 10:49:50何雨橙丁堯相周志華
      計(jì)算機(jī)研究與發(fā)展 2022年11期
      關(guān)鍵詞:發(fā)包方報(bào)酬情形

      何雨橙 丁堯相 周志華

      (計(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)方法研究與論文撰寫支持.

      猜你喜歡
      發(fā)包方報(bào)酬情形
      沒有西瓜的夏天,就像沒有報(bào)酬的加班
      避免房地產(chǎn)繼承糾紛的十二種情形
      四種情形拖欠勞動報(bào)酬構(gòu)成“拒不支付”犯罪
      公民與法治(2020年4期)2020-05-30 12:31:34
      離岸IT外包中如何降低發(fā)包方的知識保護(hù):基于社會交換理論的觀點(diǎn)
      出借車輛,五種情形下須擔(dān)責(zé)
      公民與法治(2016年9期)2016-05-17 04:12:18
      醫(yī)生的最佳報(bào)酬
      海外星云(2015年15期)2015-12-01 04:17:39
      建設(shè)項(xiàng)目發(fā)包方的工程索賠管理研究
      擬分裂情形下仿射Weyl群Cn的胞腔
      誰沒領(lǐng)到報(bào)酬
      淺析成本加酬金合同模式下發(fā)包方的成本管理問題
      建湖县| 南召县| 诸暨市| 吴堡县| 中阳县| 宣化县| 肇东市| 平原县| 夹江县| 积石山| 长葛市| 开远市| 扎赉特旗| 垦利县| 永兴县| 那曲县| 宁蒗| 城步| 沿河| 温宿县| 彭水| 西和县| 兴海县| 仁布县| 石阡县| 建水县| 滨海县| 友谊县| 泰和县| 翼城县| 青河县| 阳新县| 辽源市| 福贡县| 黄冈市| 遂昌县| 彰化县| 宣汉县| 阿鲁科尔沁旗| 延边| 黔南|