Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding

doi:10.11772/j.issn.1001-9081.2023010024

Abstract

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

摘要：

众包的飞速发展丰富了任务执行者的阅历和技能，使他们更加了解任务且倾向于同时完成多种任务，因此根据执行者对任务的主观偏好进行分配成为一种常见的任务分配方式；但是出于个人利益，执行者可能采取恶意竞价行为换取更高的收益，这对众包平台的发展是不利的。为此，提出一种防恶意竞价的众包多任务分配激励机制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具有良好的防恶意竞价性能，在具有大量数据的众包平台上有更好的表现。

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

CLC Number:

TP311

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

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

Figures/Tables 7

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

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

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

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

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

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

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

References 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]	Jingyi WANG, Chao LI, Heng SONG, Di LI, Junwu ZHU. Spectrum combinatorial auction mechanism based on random walk algorithm [J]. Journal of Computer Applications, 2023, 43(8): 2352-2357.
[2]	Yanan PAN, Qingxian PAN, Zhaoyi YU, Jiajing CHU, Song YU. Online incentive mechanism based on quality perception in spatio-temporal crowdsourcing [J]. Journal of Computer Applications, 2023, 43(7): 2091-2099.
[3]	Yanan SUN, Jiehong WU, Junling SHI, Lijun GAO. Multi-UAV collaborative task assignment method based on improved self-organizing map [J]. Journal of Computer Applications, 2023, 43(5): 1551-1556.
[4]	Kun YOU, Qinhui WANG, Xin LI. General multi-unit false-name-proof auction mechanism for cloud computing [J]. Journal of Computer Applications, 2023, 43(11): 3351-3357.
[5]	Fangxing GENG, Zhuo LI, Xin CHEN. Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game [J]. Journal of Computer Applications, 2023, 43(11): 3551-3558.
[6]	Peng PENG, Zhiwei NI, Xuhui ZHU. Task allocation method of spatial crowdsourcing based on user satisfaction utility [J]. Journal of Computer Applications, 2022, 42(10): 3235-3243.
[7]	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.
[8]	LI Congdong, HUANG Hao, ZHANG Fanshun. Knowledge sharing behavior incentive mechanism for lead users based on evolutionary game [J]. Journal of Computer Applications, 2021, 41(6): 1785-1791.
[9]	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.
[10]	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.
[11]	WU Guangfu, WANG Yingjun. Secure storage and sharing scheme of internet of vehicles data based on hybrid architecture of blockchain and cloud-edge computing [J]. Journal of Computer Applications, 2021, 41(10): 2885-2892.
[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]	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.
[14]	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.
[15]	YANG Zhengqing, ZHOU Zhaorong, YUAN Shu. Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system [J]. Journal of Computer Applications, 2019, 39(9): 2778-2783.