防恶意竞价的众包多任务分配激励机制

doi:10.11772/j.issn.1001-9081.2023010024

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (1): 261-268.DOI: 10.11772/j.issn.1001-9081.2023010024

• 先进计算 • 上一篇

防恶意竞价的众包多任务分配激励机制

张佩瑶, 付晓东()

昆明理工大学信息工程与自动化学院，昆明 650500

收稿日期:2023-01-11 修回日期:2023-04-23 接受日期:2023-04-24 发布日期:2023-06-06 出版日期:2024-01-10
通讯作者: 付晓东
作者简介:张佩瑶（1998—），女，安徽铜陵人，硕士研究生，主要研究方向：服务计算、智能决策；
第一联系人：付晓东（1975—），男，云南镇雄人，教授，博士，CCF会员，主要研究方向：服务计算、智能决策。
基金资助:
国家自然科学基金资助项目(61962030);云南省科技人才与平台计划项目(202005AC160036);云南省院士（专家）工作站项目(202105AF150013)

Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding

Peiyao ZHANG, Xiaodong FU()

School of Information Engineering and Automation，Kunming University of Science and Technology，Kunming Yunnan 650500，China

Received:2023-01-11 Revised:2023-04-23 Accepted:2023-04-24 Online:2023-06-06 Published:2024-01-10
Contact: Xiaodong FU
About author:ZHANG Peiyao， born in 1998， M. S. candidate. Her research interests include services computing， intelligent decision making.
Supported by:
National Natural Science Foundation of China(61962030);Yunnan Provincial Science and Technology Talent and Platform Plan Project(202005AC160036);Yunnan Provincial Academician （Expert） Workstation Project(202105AF150013)

摘要/Abstract

摘要：

众包的飞速发展丰富了任务执行者的阅历和技能，使他们更加了解任务且倾向于同时完成多种任务，因此根据执行者对任务的主观偏好进行分配成为一种常见的任务分配方式；但是出于个人利益，执行者可能采取恶意竞价行为换取更高的收益，这对众包平台的发展是不利的。为此，提出一种防恶意竞价的众包多任务分配激励机制GIMSM（Greedy Incentive Mechanism for Single-Minded）。该机制定义了一个线性比值作为分配依据，再根据贪心策略从执行者比值递增的序列中依次选取并分配任务，最后按照支付函数对分配算法选中的任务执行者进行支付，得到最终的任务分配结果。在Taxi and Limousine Commission Trip Record Data数据集上进行实验。相较于TODA（Truthful Online Double Auction mechanism）、TCAM（Truthful Combinatorial Auction Mechanism）和FU方法，GIMSM在不同工人数下的任务结果平均质量水平分别提高了25.20、13.20和4.40个百分点，GIMSM在不同任务数下的任务结果平均质量水平分别提高了26.17、16.17和9.67个百分点。此外，GIMSM满足个体理性和激励相容，可在线性时间内得到任务分配结果。实验结果表明GIMSM具有良好的防恶意竞价性能，在具有大量数据的众包平台上有更好的表现。

关键词: 众包, 任务分配, 激励机制, 拍卖, 恶意竞价

Abstract:

The rapid development of crowdsourcing has enriched workers’ experience and skills of workers， making them more aware of tasks and tend to complete multiple tasks at the same time. Therefore， assigning tasks according to workers’ subjective preferences has become a common way of task assignment. However， out of personal interests， workers may take malicious bidding behaviors to obtain higher utility. It is detrimental to the development of crowdsourcing platforms. To this end， an incentive mechanism of crowdsourcing multi-task assignment against malicious bidding was proposed， named GIMSM （Greedy Incentive Mechanism for Single-Minded）. First， a linear ratio was defined as the allocation basis by this mechanism. Then， according to the greedy strategy， from a sequence of increasing worker ratios， tasks were selected and assigned. Finally， the workers selected by allocation algorithm were paid according to payment function， and the result of task assignment was obtained. The experiments were conducted on Taxi and Limousine Commission Trip Record Data dataset. Compared to TODA （Truthful Online Double Auction mechanism）， TCAM （Truthful Combinatorial Auction Mechanism） and FU method， GIMSM’s average quality level of task results under different numbers of workers increased by 25.20 percentage points， 13.20 percentage points and 4.40 percentage points， respectively. GIMSM’s average quality level of task results under different numbers of tasks increased by 26.17 percentage points， 16.17 percentage points and 9.67 percentage points， respectively. In addition， the proposed mechanism GIMSM satisfies individual rationality and incentive compatibility， and can obtain task assignment results in linear time. The experimental results show that the proposed mechanism GIMSM has good anti-malicious bidding performance， and has a better performance on the crowdsourcing platforms with a large amount of data.

Key words: crowdsourcing, task assignment, incentive mechanism, auction, malicious bidding

中图分类号:

TP311

张佩瑶, 付晓东. 防恶意竞价的众包多任务分配激励机制[J]. 计算机应用, 2024, 44(1): 261-268.

Peiyao ZHANG, Xiaodong FU. Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding[J]. Journal of Computer Applications, 2024, 44(1): 261-268.

图/表 7

图1 GIMSM、TODA、TCAM和FU的防恶意竞价性能分析

Fig. 1 Anti-malicious bidding performance analysis among GIMSM， TODA， TCAM and FU

图2 GIMSM、TODA、TCAM和FU在不同条件下的赢家竞价和对比

Fig. 2 Comparison of sum of winning bids among GIMSM， TODA， TCAM and FU under different conditions

图3 在不同工人数、不同任务数下GIMSM与最优分配的近似度

Fig. 3 Approximation of GIMSM to optimal allocation under different numbers of workers and tasks

图4 GIMSM、TODA、TCAM、FU在任务数为10和工人数为35时任务完成质量水平对比

Fig. 4 Comparison of task completion quality level among GIMSM， TODA， TCAM and FU with 10 tasks and 35 workers

图5 GIMSM、TODA、TCAM和FU在任务数为10和工人数为35时的运行时间对比

Fig. 5 Runtime comparison among GIMS， TODA， TCAM and FU with 10 tasks and 35 workers

图6 GIMSM、TCAM和FU在任务数为20和工人数为150时的运行时间对比

Fig. 6 Runtime comparison among GIMSM， TCAM and FU with 20 tasks and 150 workers

图7 GIMSM和FU在任务数为20时的运行时间对比

Fig. 7 Runtime comparison between GIMSM and FU with 20 tasks

参考文献 26

1	HOWE J. The rise of crowdsourcing ［J］. Wired Magazine， 2006， 14： 1-4. 10.5860/choice.43-5329
2	冯剑红，李国良，冯建华.众包技术研究综述［J］.计算机学报， 2015， 38（9）： 1713-1726. 10.11897/SP.J.1016.2015.01713
	FENG J H， LI G L， FENG J H. A survey on crowdsourcing ［J］. Chinese Journal of Computers， 2015， 38（9）： 1713-1726. 10.11897/SP.J.1016.2015.01713
3	施战，辛煜，孙玉娥，等.基于用户可靠性的众包系统任务分配机制［J］.计算机应用， 2017， 37（9）： 2449-2453. 10.11772/j.issn.1001-9081.2017.09.2449
	SHI Z， XIN Y， SUN Y E， et al. Task allocation mechanism for crowdsourcing system based on reliability of users ［J］. Journal of Computer Applications， 2017， 37（9）： 2449-2453. 10.11772/j.issn.1001-9081.2017.09.2449
4	秦海燕，章永龙，李斌.社会网络下分配众包任务的真实机制［J］.计算机应用， 2020， 40（10）： 3019-3024. 10.11772/j.issn.1001-9081.2020020174
	QIN H Y， ZHANG Y L， LI B. Truthful mechanism for crowdsourcing task assignment in social network ［J］. Journal of Computer Applications， 2020， 40（10）： 3019-3024. 10.11772/j.issn.1001-9081.2020020174
5	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. 10.1109/tkde.2016.2555805
6	ROSS J， IRANI L， SILBERMAN M S， et al. Who are the crowdworkers？ shifting demographics in mechanical turk ［C］// Proceedings of the 28th International Conference on Human Factors in Computing Systems. New York： ACM， 2010： 2863-2872. 10.1145/1753846.1753873
7	HETTIACHCHI D， KOSTAKOS V， GONCALVES J. A survey on task assignment in crowdsourcing ［J］. ACM Computing Surveys， 2022， 55（3）： No.49. 10.1145/3494522
8	姜芸，何伟，崔立真，等.移动情景和用户轨迹感知的众包服务推荐［J］.计算机科学与探索， 2019， 13（9）： 1471-1480.
	JIANG Y， HE W， CUI L Z， et al. Mobile context and user trajectory awareness crowdsourcing service recommendation ［J］. Journal of Frontiers of Computer Science and Technology， 2019， 13（9）： 1471-1480.
9	徐天承，乔少杰，武俊，等.一种基于时空位置预测的空间众包任务分配方法［J］.计算机研究与发展， 2022， 59（2）： 310-328. 10.7544/issn1000-1239.20210875
	XU T C， QIAO S J， WU J， et al. A spatial crowdsourcing task assignment approach based on spatio-temporal location prediction ［J］. Journal of Computer Research and Development， 2022， 59（2）： 310-328. 10.7544/issn1000-1239.20210875
10	MASON W， WATTS D J. Financial incentives and the “performance of crowds” ［C］// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 77-85. 10.1145/1600150.1600175
11	付晓东，张佩瑶，刘骊，等.一种防恶意竞价的众包多任务分配方法： CN202210566622.5 ［P］. 2022-10-18.
	FU X D， ZHANG P Y， LIU L， et al. A multi-task assignment against malicious bidding for crowdsourcing： CN202210566622.5 ［P］. 2022-10-18.
12	C-J HO， JABBARI S， VAUGHAN J W. Adaptive task assignment for crowdsourced classification ［C］// Proceedings of the 30th International Conference on Machine Learning. New York： JMLR.org， 2013： 534-542.
13	TU J， CHENG P， CHEN L. Quality-assured synchronized task assignment in crowdsourcing ［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（3）： 1156-1168.
14	XIA J， ZHAO Y， LIU G， et al. Profit-driven task assignment in spatial crowdsourcing ［C］// Proceedings of the 28th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2019： 1914-1920. 10.24963/ijcai.2019/265
15	ZHAO Y， ZHENG K， LI Y， et al. Destination-aware task assignment in spatial crowdsourcing： a worker decomposition approach ［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（12）： 2336-2350. 10.1109/tkde.2019.2922604
16	LI X， ZHAO Y， ZHOU X， et al. Consensus-based group task assignment with social impact in spatial crowdsourcing ［J］. Data Science and Engineering， 2020， 5： 375-390. 10.1007/s41019-020-00142-0
17	ZHANG X， XUE G， YU R， et al. Truthful incentive mechanisms for crowdsourcing ［C］// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway： IEEE， 2015： 2830-2838. 10.1109/infocom.2015.7218676
18	ZHAO D， LI X-Y， MA H. How to crowdsource tasks truthfully without sacrificing utility： online incentive mechanisms with budget constraint ［C］// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway： IEEE， 2014： 1213-1221. 10.1109/infocom.2014.6848053
19	WANG H， GUO S， CAO J， et al. MeLoDy： A long-term dynamic quality-aware incentive mechanism for crowdsourcing ［J］. IEEE Transactions on Parallel and Distributed Systems， 2017， 29（4）： 901-914. 10.1109/tpds.2017.2775232
20	MOHAMMADI A， GOLPAYEGANI S A H. A financial incentive mechanism for truthful reporting assurance in online crowdsourcing platforms ［J］. Journal of Theoretical and Applied Electronic Commerce Research， 2021， 16（6）： 2014-2030. 10.3390/jtaer16060113
21	HURWICZ L， REITER S. Designing Economic Mechanisms ［M］. Cambridge： Cambridge University Press， 2006： 5-20. 10.1017/cbo9780511754258
22	LEHMANN D， OĆALLAGHAN L I， SHOHAM Y. Truth revelation in approximately efficient combinatorial auctions ［J］. Journal of the ACM， 2002， 49（5）： 577-602. 10.1145/585265.585266
23	PARKES D C， KALAGNANAM J， ESO M. Achieving budget-balance with Vickrey-based payment schemes in exchanges ［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann， 2001， 2： 1161-1168.
24	ROUGHGARDEN T. Twenty Lectures on Algorithmic Game Theory ［M］. Cambridge： Cambridge University Press， 2016： 3-6. 10.1017/cbo9781316779309
25	LIU S， YU Y， GUO L， et al. Truthful online double auctions for mobile crowdsourcing： an on-demand service strategy ［J］. IEEE Internet of Things Journal， 2022， 9（17）： 16096-16112. 10.1109/jiot.2022.3151924
26	CUI J， SUN Y-E， HUANG H， et al. TCAM： a truthful combinatorial auction mechanism for crowdsourcing systems ［C］// Proceedings of the 2018 IEEE Wireless Communications and Networking Conference. Piscataway： IEEE， 2018： 1-6. 10.1109/wcnc.2018.8377240

[1]	王菁怡, 李超, 宋衡, 李迪, 朱俊武. 基于随机游走算法的频谱组合拍卖机制[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2352-2357.
[2]	潘亚楠, 潘庆先, 于兆一, 褚佳静, 于嵩. 时空众包中基于质量感知的在线激励机制[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2091-2099.
[3]	孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1551-1556.
[4]	邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3833-3839.
[5]	耿方兴, 李卓, 陈昕. 基于多领导者Stackelberg博弈的分层联邦学习激励机制设计[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3551-3558.
[6]	游坤, 王钦辉, 李鑫. 通用的多元抵制假名的云计算拍卖机制[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3351-3357.
[7]	彭鹏, 倪志伟, 朱旭辉. 基于用户满意效用的空间众包任务分配方法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3235-3243.
[8]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2232-2241.
[9]	李从东, 黄浩, 张帆顺. 基于演化博弈的领先用户知识共享行为激励机制[J]. 计算机应用, 2021, 41(6): 1785-1791.
[10]	李蓓, 张问银, 王九如, 赵伟, 王海峰. 基于区块链的密封式投标拍卖方案[J]. 计算机应用, 2021, 41(4): 999-1004.
[11]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[12]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[13]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[14]	聂茜婵, 张阳, 余敦辉, 张兴盛. 面向全局优化的时空众包任务分配算法[J]. 计算机应用, 2020, 40(7): 1950-1958.
[15]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.

防恶意竞价的众包多任务分配激励机制

Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 26

相关文章 15

编辑推荐

Metrics