LIN Li. Crowdsourcing Quality Evolution Principles in Hierarchically-organized Networks[J]. Journal of Beijing University of Technology, 2017, 43(2): 237-243. DOI: 10.11936/bjutxb2016070027
Citation:
LIN Li. Crowdsourcing Quality Evolution Principles in Hierarchically-organized Networks[J]. Journal of Beijing University of Technology, 2017, 43(2): 237-243. DOI: 10.11936/bjutxb2016070027
It is very important for crowdsourcing system to analyze crowdsourcing workers’ collaborative behaviors. In this paper, the evolutionary process of crowdsourcing quality was studied based on classic hierarchically-organized mode. By establishing an evolutionary game model for crowdsourcing task collaboration among different virtual organizations, the evolutionary stability of crowdsourcing systems was analyzed and the dynamics of crowdsourcing workers’ behaviors were discussed macroscopically. The key factors affecting the evolution of crowdsourcing system, including the economic benefits, consumer utilities from completing crowdsourcing tasks and risks from insecure participating, were suggested and how the factors work was presented. All these results together provide the theory basis for designing quality control methods of crowdsourcing system.
令Child
i和Child
j为Club
i和Club
j的任一对子点,对于某个时间段,记
U
k,
k=i,
j为该时间段内Child
i和Child
j都采取NonCoop时各方的正常效用,Δ
U
k,
k=i,
j为该时间段内Child
i和Child
j都采用Coop时所产生的额外效用. 其中,Δ
U
k可通过双方采用Coop时所获得的正效用PU
k和负效用NU
k之差来计算,即
Δ
U
k=PU
k-NU
k, k=i,j
其中
PU
i=B
-i+B
i,PU
j=B
-j+B
j
NU
i=C
-i+C
i,NU
j=C
-j+C
j
即PU
k分成2部分:子点Child
k从另一子点提交正确任务结果获取的好处
B
-k和自身提交正确任务结果获取的经济利益
B
k;NU
k也分成2部分:子点Child
k获得另一子点提交正确任务结果的代价
C
-k和完成众包任务承担的风险
C
k,如可体现为完成众包任务会泄露的个人隐私信息
[
13]
以及完成众包任务所产生的系统开销,这里
k=i,
j.
显然,
B
-k-C
-k表示Child
k担当众包任务需求者时,从Child
-k完成的任务结果中获取的效用,简称为消费者效用;
B
k-C
k表示Child
k担当众包任务完成者时,从自己完成任务上获取的利益,简称为提供者效用
. 由此,给出Club
i和Club
j间众包任务协作博弈的效用矩阵,如
表1所示
.
表
1
Club
i和Club
j间众包任务协作博弈的效用矩阵
Table
1.
Utility matrix between Club
i and Club
j in crowdsourcing collaboration game
d
x/d
t=x(
-U
iAverage)
=x[
-x-(1
-x)
]
=x(1
-x)[
-]
=x(1
-x)[
y(
U
i+
Δ
U
i)
+(1
-y)(
U
i+B
i-C
i)
+yU
i+
(1
-y)
U
i]
=x(1
-x)(
yΔ
U
i+B
i-C
i-yB
i+yC
i)
=x(1
-x)[
y(
B
-i+B
i-C
-i-C
i)
+B
i-C
i-yB
i+yC
i]
=x(1
-x)[
y(
B
-i-C
-i)
+B
i-C
i] (1)
方程(1)刻画了Club
i中所有子点众包任务协作行为的动态性,对其做渐近稳定性分析有如下结论
.
命题1 若
y=(
C
i-B
i)
/(
B
-i-C
-i),那么使用Coop的Club
i子点的任何比例都是稳定的
. 若
y≠(
C
i -B
i)
/(
B
-i- C
-i),那么:
1) 对于
B
-i-C
-i>
0的情形,当
y>(
C
i-B
i)
/(
B
-i-C
-i)时,
x
*=
1是稳定的,即Coop是ESS;当
y<(
C
i -B
i)
/(
B
-i-C
-i)时,
x
*=
0是稳定的,即NonCoop是ESS
.
2) 对于
B
-i-C
-i<
0的情形,当
y>(
C
i-B
i)
/(
B
-i-C
-i)时,
x
*=
0是稳定的,即NonCoop是ESS;当
y<(
C
i-B
i)
/(
B
-i-C
-i)时,
x
*=
1是稳定的,即Coop是ESS
.
证明:因为
y∈[0,1],故须对(
C
i -B
i)
/(
B
-i-C
-i)分类讨论:
1) 0
<(
C
i -B
i)
/(
B
-i-C
-i)
<1
如果
y=(
C
i -B
i)
/(
B
-i- C
-i),那么d
x/d
t=0始终成立,即Club
i中采用Coop子点的所有比例都不随时间变化,它们都是稳定状态
.
如果
y≠(
C
i -B
i)
/(
B
-i- C
-i),那么只有当
x=0和
x=1时才有d
x/d
t=0,即
x
*=
0和
x
*=
1是2个均衡状态
. 也就是说,当Club
i中的子点干扰使
x低于
x
*时,d
x/d
t>0必须成立;当Club
i中的子点干扰使
x高于
x
*时,d
x/d
t<0必须成立
. 对于
B
-i-C
-i>
0的情形,当
y>(
C
i-B
i)
/(
B
-i-C
-i)时,
x
*=
1处导数值为负,即Coop为ESS;当
y<(
C
i -B
i)
/(
B
-i-C
-i)时,
x
*=
0处导数值为负,即NonCoop是ESS
. 对于
B
-i-C
-i<
0的情形,结论正好相反
.
2) (
C
i -B
i)
/(
B
-i-C
-i)
>1
因为
y≠(
C
i-B
i)
/(
B
-i-C
-i)且
y<(
C
i-B
i)
/(
B
-i-C
-i),对于
B
-i-C
-i>
0的情形,
x
*=
0处导数值为负,即NonCoop为ESS;对于
B
-i-C
-i<
0的情形,
x
*=
1处导数值为负,即Coop为ESS
.
3) (
C
i -B
i)
/(
B
-i-C
-i)
<0
因为
y≠(
C
i-B
i)
/(
B
-i-C
-i)且
y>(
C
i-B
i)
/(
B
-i-C
-i),对于
B
-i-C
-i>
0的情形,
x
*=
1处导数值为负,即Coop为ESS
. 对于
B
-i-C
-i<
0的情形,
x
*=
0处导数值为负,即NonCoop为ESS
.
命题2 如果
x=(
C
j-B
j)
/(
B
-j-C
-j),那么Club
j中使用Coop的子点的任何比例都是稳定的
. 如果
x≠(
C
j-B
j)
/(
B
-j-C
-j),对于
B
-j-C
-j>
0的情形,当
x>(
C
j-B
j)
/(
B
-j-C
-j)时,
y
*=
1是稳定的,即Coop为Club
j的ESS;当
x<(
C
j-B
j)
/(
B
-j-C
-j)时,
y
*=
0是稳定的,即NonCoop为Club
j的ESS
. 对于
B
-j-C
-j<
0的情形,结论正好相反
.
1) 众包节点的消费者效用
B
-k-C
-k,
k=i,
j. 由
图3可以看到,当节点充当消费者角色时,随着各点消费效用的增加,
F点向左下移动,区域
PFQE的面积增加,众包系统演化到稳定点
E的可能性随之增加. 另外,当节点获得另一子点提交正确任务结果的代价
C
-k越小,它的消费效用就越高,而在众包任务协作系统中,节点获得另一子点提交正确任务结果的代价主要用于对其他节点参与众包任务协作的激励. 因此,当Club的汇点在为该Club中节点设计众包任务激励机制时,首先需要满足其子点消费效用的最大化. 尤其,当一个Club同时与多个Club存在众包任务协作博弈时,诸如生物领域的蛋白质折叠等众包任务,此时的激励机制设计必须在促使多方正确完成众包任务的同时,确保用户消费效用的提高.
2) 完成众包任务承担的风险
C
k. 风险
C
k与众包环境紧密相关,表现为节点选择合作策略后众包环境给其带来的风险水平,如可体现为完成众包任务会泄露的个人隐私信息
[
13]
以及完成众包任务所产生的系统开销. 这主要是基于对众包系统的数据安全和隐私保护的考虑. 由
图3可知,当
C
k增加时,
F点向右上移动,区域
PFQO的面积增加,即系统演化到所有节点都合作参与众包任务的可能性减少. 因此,需要从参与众包任务后系统资源的安全性和众包环境的可信性等方面来考虑如何降低风险. 由于相同的众包环境可能带来不同的风险水平,因而,汇点在决策Club间众包任务协作关系时,必须考虑发布任务者的可信度,降低众包任务协作给所有子点带来的风险.
3) 完成众包任务产生的利益
B
k. 由
图3可知,当参与众包任务带来的风险
C
k固定时,随着
B
k的增加,
F向左下移动,区域
PFQE的面积增加,即众包系统演化到稳定点
E的概率增加,越来越多的参与者会选择合作策略. 因此,在承担相同风险的前提下,汇点应该尽力保证提供参与者的利益极大化. 此外,由
图3也容易看出,当风险
C
k变化时,极大化参与者的利益
B
k并不一定总使得区域
PFQE的面积增加. 因此,汇点需要考虑众包环境的动态性,既关心本Club子点获得的利益,又关心其承担的风险,这样才能最终促进Club联盟建立稳定的众包任务协作关系,使众包质量朝最大化方向发展.
FENG JH,LI GL,FENG JH.Asurvey on crowdsourcing[J].Chinese Journal of Computer,2015,38(9):1713-1725. (in Chinese)
[2]
HOWEJ.The rise of crowdsourcing[J].Wired Magazine,2006,14(6):1-4.
[3]
MASON WA,WATTS DJ.Financial incentives and the “performance of crowds”[J].ACM SIGKDD Explorations Newsletter,2009,11(2):100-108.
[4]
CARSTENE,ARJEN PV.Increasing cheat robustness of crowdsourcing tasks[J].Information Retrieval,2013 (2):49-57.
[5]
FANYSUN HLZHU YMet al.A truthful online auction for tempo-spatial crowdsourcing tasksThe IEEE Symposium on Service-Oriented System Engineering. Washington, DC: IEEE Computer Society
2015332338
FANY,SUN HL,ZHU YM,et al.A truthful online auction for tempo-spatial crowdsourcing tasks[C]//The IEEE Symposium on Service-Oriented System Engineering. Washington, DC: IEEE Computer Society,2015:332-338.
[6]
XU AF,FENG XN,TIANY.Revealing, characterizing, and detecting crowdsourcing spammers: a case study in community Q&A[C]//The 34th IEEE Conference on Computer Communications. Amsterdam: Computer Communications,2015:2533-2541.
ZHANG ZQ,PANG JS,XIE XQ,et al.Research on crowdsourcing quality control strategies and evaluation algorithm[J].Chinese Journal of Computer,2013,36(8):1636-1649. (in Chinese)
HE YH,SUN LM,YANG WD,et al.Enhancing privacy preserving for crowdsourced monitoring—a game theoretic analysis based approach[J].Journal of Electronics & Information Technology,2016,38(2):340-346. (in Chinese)
[9]
YANG DJ,XUE GL,FANGX,et al.Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing[C]//The 18th Annual International Conference on Mobile Computing and Networking. New York: ACM,2012:173-184.
[10]
SUNJ,MAH.A behavior-based incentive mechanism for crowd sensing with budget constraints[C]//The IEEE International Conference on Communications. Washington, DC: IEEE Computer Society,2014:1314-1319.
[11]
LIJZHU YMHUA YQet al.Crowdsourcing sensing to smartphones: a randomized auction approachThe IEEE International Symposium on Quality of Service. Washington, DC: IEEE Computer Society
2015219224
LIJ,ZHU YM,HUA YQ,et al.Crowdsourcing sensing to smartphones: a randomized auction approach[C]//The IEEE International Symposium on Quality of Service. Washington, DC: IEEE Computer Society,2015:219-224.
[12]
RANGANATHANKRIPEANUMSARINAet al.Incentive mechanisms for large collaborative resource sharingThe 4th IEEE/ACM International Symposium on Cluster Computing and the Grid. Washington, DC: IEEE Computer Society
200418
RANGANATHANK,RIPEANUM,SARINA,et al.Incentive mechanisms for large collaborative resource sharing[C]//The 4th IEEE/ACM International Symposium on Cluster Computing and the Grid. Washington, DC: IEEE Computer Society,2004:1-8.
[13]
DASILVA LA,SRIVASTAVAV.Node participation in adhoc and peer-to-peer networks: a game-theoretic formulation[C]//The First Workshop on Games and Emergent Behaviors in Distributed Computing Environments With PPSN. New York: Springer,2004:1-8.
[14]
CHENF,ZHAN SB,SHI GJ,et al.Crowdsourcing leakage of personally identifiable information via Sina microblog[C]The First International Conference on Internet of Vehicles.New York:Springer International Publishing,2014:262-271.
[15]
SHENY,HUANG LS,LIL,et al.Towards preserving worker location privacy in spatial crowdsourcing[C]//The IEEE Global Communications Conference. Washington, DC: IEEE Computer Society,2015:1-6.
[16]
GONG YM,WEI LB,GUO YX,et al.Optimal task recommendation for mobile crowdsourcing with privacy control[J].IEEE Internet of Things Journal,2016,5(3):745-756.
[17]
ZHUB,ZHUS,LIU XJ,et al.A novel location privacy preserving scheme for spatial crowdsourcing[C]//The 6th IEEE International Conference on Electronics Information and Emergency Communication. Washington, DC: IEEE Computer Society,2016:34-37.
[18]
KOCHHARS,MAZZOCCHIS,PARITOSHP.The anatomy of a large-scale human computation engine[C]//The ACM SIGKDD Workshop on Human Computation. New York: ACM,2010:10-17.
[19]
SMITH JM.Evolution and the theory of games: Ⅲ [M].Cambridge:Cambridge University Press,1982.
[20]
FRIEDMAND.Evolutionary games in economics[J].Econometrica,1991,59(3):637-666.