何雨橙 丁尧相 周志华

(计算机软件新技术国家重点实验室(南京大学) 南京 210023)

随着机器学习任务的规模逐渐增大，人们迫切需要对大规模数据进行收集.众包(crowdsourcing)作为低成本高效率的数据收集方式，受到了广泛欢迎.

众包研究的基本问题之一是设计有效的机制以使得参与者在竞争中实现共赢.当前，众包机制设计研究往往基于两方众包模型：发包方(requester)发布任务并支付标注者(workers)费用；标注者完成任务并收取报酬[1].该模型的重要假设在于发包方和标注者可以直接进行交互.而现实应用中，如图1所示，发包方和标注者的交互往往以平台(platform)为中介，构成三方众包市场.其中，发包方将任务和报酬发布给平台，平台雇佣标注者进行标记，进而在将标记结果反馈给发包方的同时，赚取支付给标注者的费用和发包方支付给自己的费用之间的差价.显然，传统的两方众包模型无法对该过程进行建模，因此需要引入全新的三方众包模型进行研究.

Fig. 1 The three-party crowdsourcing market图1 三方众包市场示意图

相比于两方众包，三方众包的核心问题是发包方与平台之间的博弈：发包方希望支付较少的报酬同时获取准确率较高的标记；而平台则希望降低雇佣标注者的成本，同时从发包方处获取较多的报酬.这之中存在着复杂的博弈关系.一方面，发包方和平台既有合作也有竞争：双方都希望最大化标记的准确率，但在最小化或最大化发包方支付这一点上有冲突.另一方面，发包方和平台各自只能掌握自身信息，而无法直接观测到对方信息.在不完全信息下采取最优策略，对双方都是相当具有挑战性的问题.

本文开启三方众包市场中的发包方-平台博弈机制设计研究，主要贡献有4点：

1) 提出不完全信息博弈[2]模型CrowdMarket对三方众包市场进行建模，并证明通过设计合适的在线学习策略可以近似达到该博弈的Nash均衡；

2) 在单发包方设定下，证明了EXP3算法[3]为发包方的最优策略，进而本文设计了基于反事实遗憾最小化(counterfactual regret minimization, CFR)技术[4-5]的平台策略，证明该策略能够充分利用平台方的有效信息，具有比直接应用传统在线学习方法更强的理论保证；

3) 将单发包方的策略拓展到多发包方的情形，并给出了多发包方情形下的理论分析；

4) 通过合成及真实数据集上的实验验证了方法的有效性.

1 相关工作

众包研究的核心问题之一在于如何平衡标记质量和支付费用[6-7].现有研究中，实现这一目标的方式可以分成2类：设计更好的标记推断方法以及设计更好的众包机制.标记推断已经有了丰富的研究，例如文献[8-11].本文则着力于探讨机制设计问题.

两方众包机制设计已经得到了充分研究，其中包括任务与报酬的分配机制设计[12-15]，以及利用提供线索[16]或跳过选项[17-19]等方式提升高难度样本的标记质量.由于这些机制都是针对标注者的，因此这些策略同样可以应用于三方众包市场中作为平台与标注者之间的博弈机制.并且由于这方面的研究相对成熟，本文不再对此进行深入探讨.同时，也有大量的研究关注如何设计合适的支付策略以激励标注者给出高质量的标记.这方面的代表性工作包括文献[20-23].在我们的问题设定中，这些激励机制可以被平台用于激励标注者给出更准确的标记，但是不能直接用于处理平台和发包方之间的博弈.

近期以来，一些工作也开始从应用的角度关注三方众包市场.例如文献[24]提出了一种声誉评价方法以防止发包方和标注者的欺骗行为，而文献[25]则将众包市场建模为一个3层的优化问题以最大化平台的健康度.但这些工作均不涉及博弈机制设计研究，因而它们的研究动机与本文有着显著的差异.

当前，将众包形式化为博弈问题，特别是预算有限条件下的收益最大化问题，是一个重要的理论研究方向[26-28].这个方向上的现有研究主要集中于传统两方设定，本文所提出的三方众包模型，对拓展这一方向的研究内容可能起到有益的作用.此外，近期也有工作研究如何在广告市场中利用机器学习方法从数据中学习有效的三方博弈机制[29].本文的研究也为将这种新方法引入众包博弈问题提供了有益启示.

2 CrowdMarket模型

2.1 基本定义

本节提出三方众包模型CrowdMarket，将三方众包市场形式化为发包方、平台以及标注者三方的不完全信息博弈[2].本节讨论单发包方情形，第4节中将对多发包方情形进行讨论.

单发包方情形下的CrowdMarket模型为持续T轮的博弈，在第t轮下：

1) 发包方发送一个包含b个任务的任务包，以及支付报酬xt∈(0,1]给平台.本文假设发包方只能从有限数量的K个报酬选项X1,X2,…,XK中选择合适的报酬.

2) 在收到报酬和任务包之后，平台选择mt个标注者完成标注任务.

3) 标注者各自选择采取低等级的努力或者高等级的努力以完成任务.高努力下准确率为p*>1/2；而低努力下标注者随机猜测以返回标记，准确率为1/2.之后每位标注者各自独立地为每个任务进行标注，并将结果反馈给平台.

4) 平台将每位标注者给出的标记通过多数投票法进行集成，并将集成后标记返回给发包方.集成后标记的实际平均准确率记为at.发包方从返回的标记中得到的收益取决于该准确率以及支付给平台的报酬，因此可以表示为at-xt.

5) 平台从发包方的支付中取出一部分作为参与了本轮标注的标注者的报酬，其余作为自己的收益.

为了激励标注者给出高质量的标记，平台需要得知标注者给出的标记的准确程度，这就需要发包方向平台提供反馈.因此，我们引入了这样一个步骤：发包方在每一轮结束之后会向平台反馈该轮标记的准确率.参考文献[17]，可以设计激励机制来确保发包方会诚实地反馈标记准确率，在3.1节中我们将会给出该激励机制并进行分析.另外，本文假设平台只能有部分轮次得到真实标记.因此，平台不能在任意轮次中直接推断出标记准确率.

每一轮中参与者可能选择的动作组成的集合称为动作集.具体而言，发包方的动作集为Areq={(x,a′):x∈{X1,X2,…,XK},a′∈[0,1]}，其中x代表支付给平台的报酬，a′代表汇报的准确率；平台的动作集为Apla=(m,c):m∈{1,2,…,N},c∈N}，其中m代表平台选择标注的人数，c代表为每一位标注者支付的报酬组成的向量(m

2.2 CrowdMarket博弈的分解

CrowdMarket模型是一个多方非零和博弈[30]，这是博弈论中最难分析的博弈类型.但是，该模型有特殊的结构：发包方和标注者之间并没有直接的交互.利用这一点，我们可以将CrowdMarket模型分解成2个部分：发包方和平台之间的博弈以及平台和标注者之间的博弈.其中，平台和标注者之间的博弈与传统的两方众包中发包方和标注者之间的博弈是类似的，因此平台需要设计机制以激励标注者采取高等级的努力.并且，需要同时引入激励机制使发包方诚实反馈准确率.

3 平台激励机制设计

本节介绍平台需要采用2个激励机制：1)激励发包方诚实反馈准确率信息的机制；2)激励标注者采取高等级努力的机制.

3.1 激励发包方诚实反馈的机制

在CrowdMarket模型中，平台可以获得发包方反馈的准确率信息a′t.但是，发包方可能会试图通过反馈一个虚假的准确率a′t进行欺诈.为了防止这一点，受到文献[17]中“没有免费的午餐”(no-free-lunch)原则的启发，我们为平台设计了一个惩罚机制以防止发包方欺诈.

本文假设在CrowdMarket博弈过程中，平台可以随机选取某些轮次通过第三方得到真实标记,进而在这些轮次中对发包方反馈的标记准确率进行验证.如果验证发现发包方反馈的准确率不正确，即发包方在该轮进行了欺诈，那么平台将会对发包方进行一定的惩罚.

我们首先定义指示变量序列yt,t=1,2,…,T如下：

惩罚机制可以表示为指示变量序列的一个函数f(y1,y2,…,yT)：在众包博弈结束后，发包方需要支付f(y1,y2,…,yT)给平台作为欺诈的惩罚.为了确保公平性，惩罚机制需要满足2个基本条件：

第1个条件是平台不能在没有发现发包方欺诈的情形下进行惩罚；相反，如果发包方被发现在每轮都作弊了，那么需要支付最大数额的惩罚金额Fmax.该条件可以形式化为定义1.

定义1.如果惩罚机制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满足“没有免费的午餐”条件.

第2个条件是发包方应该支付惩罚当且仅当其被发现有欺诈行为.该条件可形式化为定义2.

定义2.如果惩罚机制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满足“激励相容”条件.

基于这2个条件，我们提出如下机制：

(1)

其中，I(yt≠-1)为指示函数.

式(1)表明：如果被发现在众包过程中有欺诈行为，发包方会支付最大数额的惩罚.显然，式(1)所述的机制满足我们提出的2个条件.我们可以进一步证明定理1成立，定理1表明了由式(1)定义的惩罚机制是满足我们所要求的2个条件的唯一机制.

定理1.当Fmax≥T2时，式(1)机制是唯一满足“没有免费的午餐”条件和“激励相容”条件的机制,且发包方最优策略是每轮诚实反馈收益信息.

证明.假设f是同时满足定理要求的2个条件的机制.我们只需要证明：当所有的指示变量yi≠-1时f(y1,y2,…,yT)=0，否则f(y1,y2,…,yT)=T即可.

1) 当∀i∈[t]:yi≠-1时，我们假设y1,y2,…,yT中有k个1和T-k个0.不失一般性地，可以假设前k个变量取值为1，其余变量取值为0.由“没有免费的午餐”可知：

2) 平台仅在第t轮进行了1次检查，且yt=-1.根据“没有免费的午餐”条件，该情况下惩罚为Fmax.又由“激励相容”条件易知，任何存在yi≠-1,i=1,2,…,T的情况下，惩罚均不应小于该情况，也为Fmax.

综上即是该机制为唯一满足条件的机制.

接下来考虑该机制下发包方作弊能得到的额外收益.考虑极端情况：发包方只需要在其中1轮作弊，未被发现即可得到最大收益R，被发现则要另外支付惩罚T.再设发包方不作弊得到的收益为r，平台检查的轮数所占比例为p.由于平台至少检查1次，因此p≥1/T.对发包方而言，不作弊是最优策略当且仅当

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

解不等式得p≥(R-r)/Fmax.由于在CrowdMarket模型中，R-r≤T，因而上述不等式恒成立.这表明诚实反馈是发包方的最优策略.

证毕.

3.2 激励标注者采取高等级努力的机制

标注者i获得的总收益为

(2)

式(2)采用了一个简单的机制：如果被发现在标注过程中有采取低等级努力行为，标注者将无法得到该轮报酬，否则等价于每一次标注都得到报酬ci.由于标注者的目标是最大化其收益，因而有定理2：

定理2.在式(2)机制下，标注者的最佳策略为在所有轮次均采取高等级努力进行标注.

证明. 由于标注者的目标为最大化其收益，在任意t≤T轮中,显然只有当标注者采取高等级努力时，所收获的单轮回报最大，进而知定理结论成立.

证毕.

注意到，由于标注者所标记的样本是有限的，因而通过标注是否正确判断其努力程度存在一定错误的可能性.在实际问题中，不难通过允许用户对自身努力程度被错判的情况进行申诉，来消除该错误.

在本节给出的激励机制的保证之下，平台可以保证在每一轮中：1)发包方诚实汇报准确率；2)标注者选择高等级努力，因而给出的标记的准确率为p*；3)平台向每位被分配任务的标注者支付报酬ci,由于标注者之间相互等价(能力与标注策略均相同)，每位标注者的报酬均相同.在上述标注者策略已经固定的情况下，后文将集中研究如何设计发包方和平台之间的博弈策略.另一方面，不妨将发包方与平台已经确定的动作从动作集中移除，以重点研究还未确定的动作：发包方-平台博弈的每一轮中，发包方的动作是选择支付给平台的报酬，平台的动作是选择分配的标注者人数.为此，在下文中我们重新定义发包方和平台的动作集分别为Areq={X1,X2,…,XK}，Apla={1,2,…,N}.发包方和平台的策略空间也相应地重新定义.

4 发包方-平台博弈策略设计

本节介绍发包方和平台在CrowdMarket博弈中采取的博弈策略.在4.1节我们证明发包方和平台可以使用在线学习算法最小化自身遗憾；4.2节和4.3节分别给出发包方和平台基于在线学习算法的策略.

4.1 基于在线学习的博弈策略

每个参与者的目标均为最大化自身的累计收益，这等价于最小化自身的“遗憾”：

证明.首先以平台为例进行证明.由ε-最优性的定义有

进而，由于平台收益是线性函数，我们可以得出：

发包方的效用函数可类似地表示为策略的线性函数，从而同理可证

证毕.

由于Nash均衡状态代表了各方策略同时达到稳定状态，因而定理1表明，博弈各方只需采用能够对遗憾进行最小化的学习策略，就能在竞争中合作共赢.

4.2 发包方策略

注意到发包方可以将博弈过程建模为赌博机(bandit)在线学习问题：发包方可能选择的支付动作Areq可视为赌博机摇臂，博弈产生的收益可以作为选择特定摇臂之后得到的收益.进而，发包方可以采用文献[3]提出的EXP3算法作为其策略.下面的定理给出了任何发包方策略的遗憾下界，进而验证了EXP3策略的最优性.

证明.考虑这样一种情况，标注者能力p=1，即标注者总是返回真实标记；平台通过以一定概率随机反转集成后标记的方式控制返回给发包方的标记准确率.假设当发包方选择支付给平台的报酬为x时，平台翻转标记的概率为1-q(x)，即平台提供的标记的期望准确率为a=q(x).

考虑函数q(x)=x+α+εI(x=x0)，I()表示指示函数，并且α足够小从而使得q(x)∈[0,1].显然此时发包方的期望收益u=q(x)-x=α+εI(x=x0)满足以上条件.

证毕.

这与EXP3的遗憾上界同阶，因而EXP3是发包方在缺乏信息的条件下所能采用的最优策略.值得注意的是，平台也可以由定理4得知发包方会使用EXP3策略.在4.3节我们会展示这一优势是如何帮助平台制定策略的.

4.3 平台策略

此时信息很不充足，对标注者能力的估计误差会很大.解决该挑战的思路是，在每轮博弈中基于文献[4]提出的CFR技术模拟之后的博弈过程.基于CFR的平台博弈策略(以下简称CFR策略)如算法1所示：

算法1.CFR策略.

① 初始化置信区间I1=[0,1],P1={p:p∈I1}；

② 初始化历史记录H=∅；

③ fort=1,2,…,T

⑥ 完成众包并接收发包方反馈的收益at；

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

⑩ 更新It+1为

则有

(3)

其中,N为平台最多可选择的标注者人数.

另一方面，直接应用原始的CFR算法无法达到理想效果.这是由于对于平台而言，标注者能力在博弈开始是未知的，必须通过对标注者能力进行有效估计，才能加快CFR算法的收敛速度.为了能更精确地得到对标注者能力的估计，算法1中引入了标注者能力估计步骤，利用Hoeffding不等式逐渐缩小标注者能力的可能取值范围(算法1行⑤～，行⑩中b为每轮任务数，δ为置信系数).随着博弈轮数的增加，参数区间会越来越紧，从而起到逐渐缩小标注者能力的可能取值集合的效果(算法1行).下述定理表明应用该策略可以达到更紧的遗憾界.

定理5.当博弈总轮数T充分大时，以至少1-δ的概率，算法1中的策略的期望遗憾上界为O(logT).

(4)

(5)

其中,εt表示模拟过程和真实过程之间有差异的平均概率.结合式(4)和式(5)可知，总的遗憾上界为

当t

证毕.

定理5说明算法1的遗憾界显著优于EXP3策略，表明该策略充分利用了前文所述的额外信息.

5 多发包方情形下的策略

本节讨论多发包方CrowdMarket模型的博弈机制.如果标注者群体可以同时为所有的发包方提供服务，那么平台只需要和每一个发包方单独进行CrowdMarket博弈，此时多发包方和单发包方的情形是完全一致的.但是如果标注者群体在同一时间只能为部分发包方提供服务，那么发包方之间需要竞争服务的使用权.因此，本节针对后一种情况进行研究.

不失一般性，假设一共有n个发包方参与博弈，平台在每一轮中为出价最高的发包方提供服务.同时，假设单个发包方只能知道自己是否成功获得服务，而无法得知其他发包方的出价以及任务完成准确率信息.易知，在任何一轮当中，出价最高而得到服务的发包方的收益和单发包方的情形相同，而未得到服务的发包方的收益则为0.

与单发包方条件下类似，在多发包方条件下，发包方仍然面临着缺乏决策信息的问题：不仅无法得知平台如何雇佣工人，而且无法得知其他发包方的情况.因而，可以类似地证明发包方的最优策略为使用EXP3算法.接下来我们证明：平台也仍可以使用CFR策略模拟多发包方的情形，以优化自身的遗憾.

定理6.在有n个发包方情形下，当博弈总轮数T充分大时，以至少1-δ的概率，CFR策略的期望遗憾上界为O(n(logn+logT)).

当T≥nT1时，至少有一个发包方在至少T1轮赢得服务，而对于赢得服务小于T1轮的发包方，与其博弈的遗憾界是常数阶.进而知以至少1-δ的概率有

证毕.

6 实验验证

本节对发包方-平台策略性能进行验证.具体而言，本节实验对3点进行验证：1)对于发包方，当平台使用强对抗性的策略时，EXP3策略是否有好的表现；2)对于平台，CFR策略是否能利用额外信息给出更好的结果；3)对于多发包方的情形，发包方EXP3策略及平台CFR策略是否依然适用.实验中发包方和平台的动作集设定为：1)发包方可能的支付选项为{0.1,0.2,0.3}；2)平台可能选择的标注者人数为{1,3,5}；3)平台雇佣每个标注者的成本C=0.01.

本节实验使用8个二分类真实数据集：1)BM数据集[33]，该数据集中标注者对语料给出正面或负面情绪标记；2)TEMP数据集[34]，该数据集中标注者对2件事是否是先后发生的进行标记；3)WVSCM数据集[8]，该数据集中标注者对图片中人脸是否微笑进行标记；4)WB数据集[35]，该数据集中标注者对图片中的水鸟是否是鸭子进行标记；5)SpamCF数据集[36]，该数据集中标注者对一个AMT平台上的任务是否是垃圾任务进行标注；6)MediaEval数据集[36]，该数据集中标注者对给定图片是否和时尚有关进行标注；7)MEHCB数据集[37-38]，该数据集中标注者对搜索请求和网页是否有关进行标记；8)RTE数据集[34]，该数据集中标注者对文本之间是否有蕴含关系进行标注.实验所用8个数据集的相关信息如表1所示.

Fig. 2 The cumulative rewards of requester strategies under the single requester setting图2 单发包方情形下发包方策略的累计收益对比

6.1 单发包方策略验证

本节在单发包方情形下，将发包方EXP3策略与ε-贪心策略(ε=0.05)及固定策略(始终固定在最高支付)进行性能对比.同时，假设平台使用高对抗性甚至是作弊性质的策略，因为我们需要验证即便在最坏情形下EXP3策略仍然有效.

Table 1 Information About Datasets表1 实验所用数据集的相关信息

在我们的实验中，平台和发包方用各自的策略进行持续T轮的CrowdMarket博弈.轮次上限T的取值分别设定为10,15,…,40.本实验中假设平台可获取真实的标注者能力p*，从而可以通过以一定概率翻转标记的方式准确控制返回给发包方的标记准确率.并且，平台会采用如下强对抗性的策略以诱导发包方提高支付：平台以一定的概率q翻转标记，之后如果平台收到了更高的报酬则会逐渐降低q的取值.平台采用的这一策略要求发包方逐渐提高支付的报酬而不能只用贪心策略.本次实验中设定初始轮次中q=0.50,每次收到更高报酬后q的降低量分别设为0.02,0.03,0.04,0.05.在每组参数下我们重复实验50次并汇报平均累计收益.实验结果如图2所示，实验结果可见，当平台使用强对抗性的策略时，发包方使用EXP3策略获得的累计收益总是比ε-贪心策略和固定策略要好，这表明了EXP3策略的有效性.

6.2 多发包方策略验证

本节验证了3个发包方情形下，发包方使用EXP3策略的有效性.博弈过程的参数设定同6.1节.

为了验证EXP3策略的有效性，在实验中我们令3个发包方分别使用EXP3策略、ε-贪心(ε=0.05)策略和固定策略，平台使用的策略为CFR策略.我们令3个发包方在CrowdMarket博弈中使用不同策略相互竞争，胜出的发包方所使用的策略就是这3个策略中最优的策略.为了保证公平性，所有发包方使用的数据集都是一样的，以确保标注者能力对于所有发包方是一致的.我们在8个数据集上进行了实验，每个数据集上重复10次.发包方累计收益的平均值如图3所示.可以发现，使用EXP3策略在绝大多数时间内都能获得最多的收益，这表明EXP3策略在多发包方的情形下依然适用.

Fig. 3 The cumulative rewards of requester strategies under the multiple requester setting图3 多发包方情形下各发包方策略的累计收益对比

6.3 平台策略验证

为了验证平台在单发包方与多发包方情形下使用CFR策略的性能，我们将CFR策略和EXP3策略、ε-贪心(ε=0.05)策略以及固定策略进行了对比，发包方的策略固定为EXP3策略.博弈过程的参数设置与6.1节相同.单发包方情形下我们在8个数据集上进行了实验，在多发包方情形下则测试了2组发包方数据集的组合，所有实验结果如图4所示.每张子图展示了平台的累计收益.实验结果显示：无论在哪个数据集上，性能最好的策略均为CFR策略，其次是EXP3策略，再次是ε-贪心策略，排名最后的是固定策略.这表明利用到了额外信息的CFR策略确实能取得更好的效果.

Fig. 4 The cumulative rewards of the platform strategies under the single requester and multiple requester settings图4 单发包方与多发包方情形下的平台策略累计收益对比

表2展示了单发包方情形下，当平台使用不同策略，发包方使用EXP3策略时，40轮之后平台和发包方的合计累计收益.结果表明平台使用CFR策略可以使得双方的累计收益达到最大.综合上述结果可知，CFR策略是最适合于合作的策略.注意到平台使用CFR策略是在发包方反馈准确率信息时的最优策略，而平台使用EXP3策略是在发包方不反馈准确率信息时的最优策略.因此，表2中平台使用CFR策略时，累计收益超过EXP3策略，这表明2.1节中引入的反馈步骤可以提升双方的累计收益，对于双方的合作有促进作用.

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

6.4 实验结果分析

在本节中，我们利用仿真数据集和真实数据集进行了实验，对本文提出的基于在线学习方法的三方众包市场发包方-平台博弈策略进行了验证.实验结果表明，在符合CrowdMarket模型假设的条件下，本文提出的单发包方及多发包方策略不仅能优化自身的累计收益，而且能达到促进博弈双方合作共赢的目的.这验证了本文提出策略的有效性.另一方面，在实际应用中，也可能存在数据不符合CrowdMarket模型假设的情况.由于相关数据集的缺乏，难以验证在这一条件下本文方法的实际效果.我们会在未来研究中探索这一问题.

7 结束语

本文针对三方众包市场中的发包方-市场机制设计问题进行理论研究，提出三方众包市场模型CrowdMarket.在该模型的基础上，针对单发包方和多发包方的设定，研究平台和发包方的策略设计和理论分析.真实数据集上进行的实验验证了本文所提出的策略的有效性.我们相信本文的研究结果可以激发更多针对三方众包市场的研究，有助于更好地理解现实应用中众包产业的市场行为.

作者贡献声明：何雨橙调研整理文献，实施方法研究，完成实验，撰写论文;丁尧相设计研究方案，实施方法研究，修订论文;周志华提出研究选题，指导方法研究与论文撰写支持.