Truthful mechanism for crowdsourcing task assignment in social network

doi:10.11772/j.issn.1001-9081.2020020174

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (10): 3019-3024.DOI: 10.11772/j.issn.1001-9081.2020020174

• Computer software technology • Previous Articles Next Articles

Truthful mechanism for crowdsourcing task assignment in social network

QIN Haiyan¹, ZHANG Yonglong², LI Bin²

1. Guanglin College, Yangzhou University, Yangzhou Jiangsu 225000, China;
2. School of Information Engineering, Yangzhou University, Yangzhou Jiangsu 225000, China

Received:2020-03-04 Revised:2020-05-10 Online:2020-10-10 Published:2020-05-21
Supported by:
This work is partially supported by the Cooperation Science and Technology Fund of Yangzhou City and Yangzhou University (YZU201803), the City and School Cooperation Project of Yangzhou (YZ2018140), the Natural Science Research Project of Guangling College of Yangzhou University (ZKYB180020).

社会网络下分配众包任务的真实机制

秦海燕¹, 章永龙², 李斌²

1. 扬州大学广陵学院, 江苏扬州 225000;
2. 扬州大学信息工程学院, 江苏扬州 225000

通讯作者: 李斌
作者简介:秦海燕(1992-),女,江苏丹阳人,助教,硕士研究生,主要研究方向:机制设计、虚拟机迁移;章永龙(1976-),男,江西高安人,讲师,博士,主要研究方向:云计算、机制设计、虚拟机迁移;李斌(1965-),男,江苏靖江人,教授,博士,CCF会员,主要研究方向:人工智能、多智能体系统、面向服务的计算。
基金资助:
扬州市扬州大学合作科技基金资助项目（YZU201803）；扬州市市校合作专项（YZ2018140）；扬州大学广陵学院自然科学研究项目（ZKYB180020）。

Abstract

Abstract: There are more and more macrotasks on the crowdsourcing platforms. Macrotasks require the professional skills of the workers and the collective contributions of the teams. Social networks provide a platform for cooperation among social workers. In fact, there are few studies paying close attention to the social network between crowdsourcing workers. The problem of task assignment in crowdsourcing is NP-hard and the participants may misreport their prices in order to gain more utilities. Therefore, a Truthful Mechanism for Crowdsourcing task assignment in Social Network (TMC-SN) was proposed. The problem of crowdsourcing task assignment in social network was modeled as an auction, where the task requester is the buyer, the workers are the sellers, and the crowdsourcing platform is served as an auctioneer. In order to find the most suitable team, TMC-SN measured worker fitness to the team from both marginal contribution and team cohesion. Theoretical analysis verifies that TMC-SN has economic properties such as truthfulness, individual rationality, and budget balance. Experimental results show that TMC-SN has certain advantages in social welfare, and can improve the utilities of workers.

Key words: crowdsourcing, mechanism design, auction, task assignment, social network, truthfulness

摘要： 众包平台上出现了越来越多的宏任务，而这些宏任务需要工人的专业技能和团队的集体贡献。社会网络为社会工作者之间的合作提供了一个可用的平台。事实上，很少有研究关注众包工人之间的社会网络。在社会网络下的众包任务分配问题是NP难问题，并且社会网络中会存在参与者为了提高自己的效用而谎报要价的情况，因此提出一种社会网络下分配众包任务的真实机制（TMC-SN）。在社会网络下的众包任务分配问题被模拟成一个拍卖，其中任务请求者是买家，工人是卖家，众包平台充当拍卖者。为了找出最合适的团队，TMC-SN从边际贡献和团队凝聚力两个方面来衡量工人对团队的适应性。理论分析证明，TMC-SN具有真实性、个体理性、预算平衡等经济属性。实验结果表明，TMC-SN在社会福利方面具有一定的优势，并且能够提升工人的效用。

关键词: 众包, 机制设计, 拍卖, 任务分配, 社会网络, 真实性

CLC Number:

TP393

QIN Haiyan, ZHANG Yonglong, LI Bin. Truthful mechanism for crowdsourcing task assignment in social network[J]. Journal of Computer Applications, 2020, 40(10): 3019-3024.

秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.

References

[1] DUCH J,WAITZMAN J S,NUNES AMARAL L A. Quantifying the performance of individual players in a team activity[J]. PLoS One,2010,5(6):No. e10937.
[2] CHITTILAPPILLY A I,CHEN L,AMER-YAHIA S. A survey of general-purpose crowdsourcing techniques[J]. IEEE Transactions on Knowledge and Data Engineering,2016,28(9):2246-2266.
[3] YU X,LI G,ZHENG Y,et al. CrowdOTA:an online task assignment system in crowdsourcing[C]//Proceedings of the IEEE 34th International Conference on Data Engineering. Piscataway:IEEE,2018:1629-1632.
[4] 冯剑红, 李国良, 冯建华. 众包技术研究综述[J]. 计算机学报, 2015,38(9):1713-1726.(FENG J H,LI G L,FENG J H. A survey on crowdsourcing[J]. Chinese Journal of Computers,2015, 38(9):1713-1726.)
[5] DE WEERDT M,ZHANG Y,KLOS T. Distributed task allocation in social networks[C]//Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems. New York:ACM,2007:No. 76.
[6] UL HASSAN U,CURRY E. Efficient task assignment for spatial crowdsourcing[J]. Expert Systems with Applications,2016,58:36-56.
[7] CHENG P,LIAN X,CHEN L,et al. Task assignment on multiskill oriented spatial crowdsourcing[J]. IEEE Transactions on Knowledge and Data Engineering,2016,28(8):2201-2215.
[8] TAO Q,DU B,SONG T,et al. Finding optimal team for multi-skill task in spatial crowdsourcing[C]//Proceedings of the 2017 AsiaPacific Web (APWeb) and Web-Age Information Management (WAIM) Joint Conference on Web and Big Data,LNCS 10612/LNISA 10612. Cham:Springer,2017:185-194.
[9] LIU J,XU K. Budget-aware online task assignment in spatial crowdsourcing[J]. World Wide Web,2019,23(1):289-311.
[10] LIU Q,LUO T,TANG R,et al. An efficient and truthful pricing mechanism for team formation in crowdsourcing markets[C]//Proceedings of the 2015 IEEE International Conference on Communications. Piscataway:IEEE,2015:567-572.
[11] YUE T,ALI S,WANG S. An evolutionary and automated virtual team making approach for crowdsourcing platforms[M]//LI W, HUHNS M N,TSAI W T,et al. Croudsourcing:Cloud-based Software Development, PROIS. Berlin:Springer, 2015:113-130.
[12] XU J,LI H,LI Y,et al. Incentivizing the biased requesters:truthful task assignment mechanisms in crowdsourcing[C]//Proceedings of the 14th Annual IEEE International Conference on Sensing,Communication,and Networking. Piscataway:IEEE, 2017:1-9.
[13] SCHMITZ H, LYKOURENTZOU I. It's about time:online macrotask sequencing in expert crowdsourcing[EB/OL].[2019-11-10]. https://arxiv.org/pdf/1601.04038.pdf.
[14] WANG W, HE Z, SHI P, et al. Strategic social team crowdsourcing:forming a team of truthful workers for crowdsourcing in social networks[J]. IEEE Transactions on Mobile Computing,2019,18(6):1419-1432.
[15] MYERSON R B. Optimal auction design[J]. Mathematics of Operations Research,1981,6(1):58-73.
[16] YANG H L,TANG J H. Team structure and team performance in IS development:a social network perspective[J]. Information and Management,2004,41(3):335-349.

Truthful mechanism for crowdsourcing task assignment in social network

社会网络下分配众包任务的真实机制

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	MA Hua, CHEN Yuepeng, TANG Wensheng, LOU Xiaoping, HUANG Zhuoxuan. Survey of research progress on crowdsourcing task assignment for evaluation of workers’ ability [J]. Journal of Computer Applications, 2021, 41(8): 2232-2241.
[2]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[3]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Event description generation based on generative adversarial network [J]. Journal of Computer Applications, 2021, 41(5): 1256-1261.
[4]	LI Bei, ZHANG Wenyin, WANG Jiuru, ZHAO Wei, WANG Haifeng. Sealed-bid auction scheme based on blockchain [J]. Journal of Computer Applications, 2021, 41(4): 999-1004.
[5]	RAN Jiamin, NI Zhiwei, PENG Peng, ZHU Xuhui. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution [J]. Journal of Computer Applications, 2021, 41(3): 794-802.
[6]	ZHU Yongjin, YIN Fei, DOU Longlong, WU Kun, ZHANG Zhiwei, QIAN Zhuzhong. Adaptive network transmission mechanism based on forward error correction [J]. Journal of Computer Applications, 2021, 41(3): 825-832.
[7]	SUN Heli, XU Tong, HE Liang, JIA Xiaolin. Personalized social event recommendation method integrating user historical behaviors and social relationships [J]. Journal of Computer Applications, 2021, 41(2): 324-329.
[8]	LI Xiangkun, JIA Caiyan. Collaborative filtering method fusing overlapping community regularization and implicit feedback [J]. Journal of Computer Applications, 2021, 41(1): 53-59.
[9]	SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612.
[10]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[11]	YANG Shuxin, LIANG Wen, ZHU Kaili. Reverse influence maximization algorithm in social networks [J]. Journal of Computer Applications, 2020, 40(7): 1944-1949.
[12]	NIE Xichan, ZHANG Yang, YU Dunhui, ZHANG Xingsheng. Spatial crowdsourcing task allocation algorithm for global optimization [J]. Journal of Computer Applications, 2020, 40(7): 1950-1958.
[13]	YI Dongyi, DENG Genqiang, DONG Chaoxiong, ZHU Miaomiao, LYU Zhouping, ZHU Suisong. Medical insurance fraud detection algorithm based on graph convolutional neural network [J]. Journal of Computer Applications, 2020, 40(5): 1272-1277.
[14]	FENG Liping, HAN Qi, ZHOU Zhigang, BAI Zengliang. Bad information diffusion modeling and optimal control strategy influenced by social networks [J]. Journal of Computer Applications, 2020, 40(3): 735-739.
[15]	YU Dunhui, YUAN Xu, ZHANG Wanshan, WANG Chenxu. Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold [J]. Journal of Computer Applications, 2020, 40(3): 658-664.