偏好匹配满意度最大化的众包任务分配

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (01): 16-26.

偏好匹配满意度最大化的众包任务分配

郭嘉宇1,付晓东1,2,岳昆3,刘骊1,冯勇1,刘利军1

（1.昆明理工大学信息工程与自动化学院,云南昆明 650500；

2.昆明理工大学云南省计算机技术应用重点实验室,云南昆明 650500；

3.云南大学信息学院,云南昆明 650504）

收稿日期:2020-11-16 修回日期:2021-03-20 接受日期:2022-01-25 出版日期:2022-01-25 发布日期:2022-01-13
基金资助:
国家自然科学基金(61962030,U1802271,61862036);云南省杰出青年科学基金(2019FJ011);云南省中青年学术和技术带头人基金(202005AC160036)

Task allocation of crowdsourcing for maximizing satisfaction with preference matching

GUO Jia-yu1,FU Xiao-dong 1,2,YUE Kun3,LIU Li1,FENG Yong1,LIU Li-jun1

(1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500;

2.Computer Technology Application Key Laboratory of Yunnan Province,
Kunming University of Science and Technology,Kunming 650500;

3.School of Information Science and Engineering,Yunnan University,Kunming 650504,China)

Received:2020-11-16 Revised:2021-03-20 Accepted:2022-01-25 Online:2022-01-25 Published:2022-01-13

摘要/Abstract

摘要： 众包任务分配机制对众包任务完成质量起着至关重要的作用，然而现有的分配方法未在稳定性条件下考虑众包用户双边偏好，分配结果的准确性有待提高，并且存在众包用户因不满意当前分配对象而导致众包任务完成质量较低的问题。为此提出一种基于偏好匹配的众包任务分配方法，该方法首先考虑众包任务与工人的双边偏好，根据偏好序计算任务与工人的满意度，生成满意度矩阵；其次，该方法借鉴稳定匹配思想在考虑分配主体偏好的基础上，使分配主体对当前分配对象尽可能满意，以保障分配结果的稳定性；然后，将众包任务分配问题建模为稳定匹配规则下寻找任务最大满意度的优化问题；最后，使用贪心算法对该问题进行求解，得到众包任务分配方案。通过实验验证了该方法的有效性，实验结果表明，该方法提高了分配方案的准确性，并有效减少了无效分配的数量，从而提高了众包任务完成质量。

关键词: 众包, 任务分配, 用户偏好, 稳定匹配, 贪心算法

Abstract: Task allocation mechanism plays an important role on crowdsourcing task quality. However, the existing allocation methods do not consider the bilateral user preferences of crowdsourcing, the accuracy of the allocation results remains to be improved, and there are many crowdsourcing users who are not satisfied with the current allocated crowdsourcing tasks, causing the phenomenon of low quality of crowdsourcing task accomplishment. Therefore a crowdsourcing task allocation method based on preference matching is proposed. Firstly, this method compute satisfaction and construct satisfaction matrix by using the preference of crowdsourcing tasks and workers. Secondly, by referring to the idea of stable matching and taking into account the bilateral preferences of crowdsourcing subjects, the method makes crowdsourcing subjects as satisfied as possible with the current allocation objects so as to guarantee the stability of the allocation results. Then, by using the idea of stable matching, the crowdsourcing task allocation problem is modeled as an optimization problem to find the maximum satisfaction of tasks under stable matching rules. Finally, greedy algorithm is used to solve the problem and a crowdsourcing task allocation scheme is obtained. The rationality and effectiveness of the method are verified by experiments, which shows that the method improves the accuracy of the allocation and effectively reduces the number of invalid allocations, thus improving the quality of crowdsourcing task allocation.

Key words: crowdsourcing, task allocation, user preference, stable matching, greedy algorithm

郭嘉宇, 付晓东, 岳昆, 刘骊, 冯勇, 刘利军. 偏好匹配满意度最大化的众包任务分配[J]. 计算机工程与科学, 2022, 44(01): 16-26.

GUO Jia-yu, FU Xiao-dong , YUE Kun, LIU Li, FENG Yong, LIU Li-jun. Task allocation of crowdsourcing for maximizing satisfaction with preference matching[J]. Computer Engineering & Science, 2022, 44(01): 16-26.

参考文献［26］

［1］	Feng Jian-hong,Li Guo-liang,Feng Jian-hua. A survey on crowdsourcing ［J］. Chinese Journal of Computers,2015,38(9):1713-1726. (in Chinese)
［2］	Karaliopoulos M, Telelis O, Koutsopoulos I. User recruitment for mobile crowdsensing over opportunistic networks［C］∥Proc of the 2015 IEEE Conference on Computer Communications (INFOCOM),2015:2254-2262.
［3］	Daniel F,Kucherbaev P,Cappiello C,et al. Quality control in crowdsourcing:A survey of quality attributes,assessment techniques,and assurance actions［J］. ACM Computing Surveys,2018,51(1):1-40.
［4］	Kittur A, Smus B, Khamkar S, et al. CrowdForge:Crowdsourcing complex work［C］∥Proc of the 24th Annual ACM Symposium on User Interface Software and Technology,2011:43-52.
［5］	Ho C J, Vaughan J W. Online task assignment in crowdsourcing markets［C］∥Proc of the 26th AAAI Confe- rence on Artificial Intelligence,2012:45-51.
［6］	Tong Y,Chen L,Zhou Z,et al. SLADE:A smart large-scale task decomposer in crowdsourcing［J］. IEEE Transactions on Knowledge and Data Engineering,2018,30(8):1588-1601.
［7］	Liu X,Lu M,Ooi B C,et al. CDAS:A crowdsourcing data analytics system［J］.Proceedings of the VLDB Endowment,2012,5(10):1040-1051.
［8］	Jiang J C, Zhou Y F, Jiang Y C,et al. Batch allocation for decomposition-based complex task crowdsourcing e-markets in social networks［J］. Knowledge-Based Systems,2020,194:105522.
［9］	Zhang Zhi-qiang, Pang Ju-sheng,Xie Xiao-qin, et al. Research on crowdsourcing quality control strategies and evaluation algorithm［J］. Chinese Journal of Computers,2013,36(8):1636-1649. (in Chinese)
［10］	Jiang Y C,Jiang J C. Contextual resource negotiation based task allocation and load balancing in complex software systems［J］. IEEE Transactions on Parallel & Distributed Systems,2009,20(5):641-653．
［11］	Jiang Yi-chuan, Jiang Jiu-chuan. Collective wisdom and mass outsourcing for complex tasks in social networks［J］. Communications of CCF,2018,14(11):25-30. (in Chinese)
［12］	Jiang J C,An B,Jiang Y C,et al. Context-aware reliable crowdsourcing in social networks［J］. IEEE Transactions on Systems,Man,and Cybernetics:Systems,2020,50(2):617-632.
［13］	Xiong H,Zhang D,Chen G,et al. Crowd tasker:Maximizing coverage quality in piggyback crowdsensing under budget constraint［C］∥Proc of the 2015 IEEE International Conference on Pervasive Computing and Communications,2015:55-62.
［14］	Lane N D,Chon Y,Zhou L,et al. Piggyback crowd sensing (PCS):Energy efficient crowdsourcing of mobile sensor data by exploiting smartphone app opportunities［C］∥Proc of the 11th ACM Conference on Embedded Networked Sensor Systems,2013:1-14.
［15］	Tong Y,She J,Ding B,et al. Online mobile micro-task allocation in spatial crowdsourcing［C］∥Proc of the 2016 IEEE 32nd International Conference on Data Engineering,2016:49-60.
［16］	Wang J,Wang Y,Zhang D,et al. Multi-task allocation in mobile crowd sensing with individual task quality assurance［J］. IEEE Transactions on Mobile Computing,2018,17(9):2101-2113.
［17］	Assadi S,Hsu J,Jabbari S. Online assignment of heterogeneous tasks in crowdsourcing markets［J］. Neural Computation,2015,27(11):2447-2475.
［18］	Yang J Y,Cheng X,Su S,et al. Collecting preference rankings under local differential privacy［C］∥Proc of the 2019 IEEE 35th International Conference on Data Engineering (ICDE),2019:1598-1601.
［19］	Kuhlman C, Doherty D,Nurbekova M,et al. Evaluating preference collection methods for interactive ranking analytics［C］∥Proc of the 2019 CHI Conference on Human Factors in Computing Systems,2019:1-11.
［20］	Liu Jia-jun. Research on user preference extraction based on multidimensional context in Mobile Internet［D］. Beijing:Beijing University of Posts and Telecommunications,2016. (in Chinese)
［21］	Fan Zhi-ping, Li Ming-yang, Yue Qi. Decision analysis method for two-sided satisfied matching considering stable matching condition ［J］. Chinese Journal of Management Science,2014,22(4):112-118. (in Chinese)
［22］	Gale D,Shaply L. College admissions and the stability of marriage［J］. American Mathematical Monthly,1962,69(1):9-15.
［23］	Mcvitie D G,Wilson L B. The stable marriage problem［J］. Communications of the ACM,1971,14(7):486-490.
［24］	Brin S,Page L. Reprint of:The anatomy of a large-scale hypertextual web search engine［J］. Computer Networks,2012,56(18):3825-3833.
［25］	Lu T,Boutilier C. Effective sampling and learning for Mallows models with pairwise-preference data［J］. Journal of Machine Learning Research,2014,15(1):3783-3829.
［26］	Kong De-cai,Jiang Yan-ping,Liang Hai-ming.Stable match- ing with fairness for two-sided agents［J］. Journal of Systems & Management,2015,24(3):397-404.(in Chinese)
	附中文参考文献：
［1］	冯剑红,李国良,冯建华. 众包技术研究综述［J］. 计算机学报,2015,38(9):1713-1726.
［9］	张志强,逄居升,谢晓芹，等. 众包质量控制策略及评估算法研究［J］. 计算机学报,2013,36(8):1636-1649.
［11］	蒋嶷川,蒋玖川. 社会网络中复杂任务的群智协同众包［J］. 中国计算机学会通讯,2018,14(11):25-30.
［20］	刘嘉俊. 移动互联网中基于上下文信息的用户偏好提取研究［D］. 北京:北京邮电大学,2016.
［21］	樊治平,李铭洋,乐琦.考虑稳定匹配条件的双边满意匹配决策方法［J］. 中国管理科学,2014,22(4):112-118.
［26］	孔德财,姜艳萍,梁海明.考虑双边主体公平性的稳定匹配决策方法［J］. 系统管理学报,2015,24(3):397-404.

[1]	侯占伟, 李鑫, 王辉, 申自浩, 刘琨, 刘沛骞. 面向路网的空间众包隐私保护任务分配算法[J]. 计算机工程与科学, 2023, 45(08): 1424-1432.
[2]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[3]	申晓宁, 许笛, 宋丽妍, 姚铖滨, 王玉芳, . 采用离散烟花算法的移动群智感知异构任务分配[J]. 计算机工程与科学, 2023, 45(02): 321-331.
[4]	梁志伟, 吴海健. RoboCup标准平台组中基于改进合同网协议的任务分配算法[J]. 计算机工程与科学, 2022, 44(01): 176-183.
[5]	薛建彬,安亚宁. 基于边缘计算的新型任务卸载与资源分配策略[J]. 计算机工程与科学, 2020, 42(06): 959-965.
[6]	周碧莹1，王爱平1，费长江2，虞万荣2，赵宝康2. 基于强化学习的卫星网络资源调度机制[J]. 计算机工程与科学, 2019, 41(12): 2134-2142.
[7]	严开1,2，李玲1,2,秦永彬1,2. 道路交通网络中的关键节点识别方法研究[J]. 计算机工程与科学, 2018, 40(11): 1983-1990.
[8]	宋洁琼,赵明. 一种基于元数据的众包图片效用最优选择算法[J]. 计算机工程与科学, 2018, 40(11): 2023-2032.
[9]	付慧敏1,2,徐扬2，何星星2,宁欣然1,2. 基于任务分配与调度的GSAT算法求解3-SAT问题[J]. 计算机工程与科学, 2018, 40(08): 1366-1374.
[10]	高志强，崔翛龙，周沙，袁琛. 本地差分隐私保护及其应用[J]. 计算机工程与科学, 2018, 40(06): 1029-1036.
[11]	孙佩歆. 无线传感器网络中干扰最小化问题的后悔贪心算法[J]. 计算机工程与科学, 2017, 39(12): 2217-2223.
[12]	郭伟，邱丹逸. 基于多Agent的众包任务推荐系统建模与仿真[J]. 计算机工程与科学, 2017, 39(05): 958-963.
[13]	陈振1，朱海滨2，盛寅3，高海波1. 基于E-CARGO模型的多任务分配算法[J]. 计算机工程与科学, 2016, 38(12): 2542-2551.
[14]	王艳春1，尚晓丽2，李会1. FCM-AFSA的无线传感器网络多目标跟踪节点任务分配方法[J]. J4, 2014, 36(07): 1262-1267.
[15]	姜永1，范庆涛2，赵卓峰1，丁维龙1. 应用托管环境下的虚拟机优化调度方法[J]. J4, 2014, 36(01): 44-50.