Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (1): 261-268.DOI: 10.11772/j.issn.1001-9081.2023010024

• Advanced computing • Previous Articles    

Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding

Peiyao ZHANG, Xiaodong FU()   

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

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

张佩瑶, 付晓东()   

  1. 昆明理工大学 信息工程与自动化学院,昆明 650500
  • 通讯作者: 付晓东
  • 作者简介:张佩瑶(1998—),女,安徽铜陵人,硕士研究生,主要研究方向:服务计算、智能决策;
    第一联系人:付晓东(1975—),男,云南镇雄人,教授,博士,CCF会员,主要研究方向:服务计算、智能决策。
  • 基金资助:
    国家自然科学基金资助项目(61962030);云南省科技人才与平台计划项目(202005AC160036);云南省院士(专家)工作站项目(202105AF150013)

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: