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

doi:10.11772/j.issn.1001-9081.2020020174

计算机应用 ›› 2020, Vol. 40 ›› Issue (10): 3019-3024.DOI: 10.11772/j.issn.1001-9081.2020020174

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

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

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

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

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).

摘要/Abstract

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

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

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

中图分类号:

TP393

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

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[2]	孙鹤立, 孙玉柱, 张晓云. 基于生成对抗网络的事件描述生成[J]. 计算机应用, 2021, 41(5): 1256-1261.
[3]	李蓓, 张问银, 王九如, 赵伟, 王海峰. 基于区块链的密封式投标拍卖方案[J]. 计算机应用, 2021, 41(4): 999-1004.
[4]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[5]	祝永晋, 尹飞, 豆龙龙, 吴昆, 张志伟, 钱柱中. 基于前向纠错的自适应网络传输机制[J]. 计算机应用, 2021, 41(3): 825-832.
[6]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[7]	聂茜婵, 张阳, 余敦辉, 张兴盛. 面向全局优化的时空众包任务分配算法[J]. 计算机应用, 2020, 40(7): 1950-1958.
[8]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[9]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[10]	孙鹤立, 孙玉柱, 张晓云. 基于事件描述的社交事件参与度预测[J]. 计算机应用, 2020, 40(11): 3101-3106.
[11]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[12]	赵威, 林煜明, 黄涛贻, 李优. 成本约束下自适应众包标注的用户观点抽取[J]. 计算机应用, 2019, 39(5): 1351-1356.
[13]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[14]	孙子力, 彭舰, 仝博. 社会网络中基于社群衰减的影响力最大化算法[J]. 计算机应用, 2019, 39(3): 834-838.
[15]	陈友玲, 左丽丹, 牛禹霏, 王龙. 基于知识相似度的产品开发任务分配方法[J]. 计算机应用, 2019, 39(2): 323-329.