Fair task assignment in spatial crowdsourcing
Fair task assignment in spatial crowdsourcing
复制标题
DOI：
10.14778/3407790.3407839
复制
发表时间：
2020-07
影响因子：
2.5
通讯作者：
Zhao Chen;Peng Cheng;Lei Chen;Xuemin Lin;C. Shahabi
中科院分区：
文献类型：
--
作者：
Zhao Chen;Peng Cheng;Lei Chen;Xuemin Lin;C. Shahabi
随着移动设备、无线宽带和共享经济的普及，空间众包正在成为我们日常生活的一部分。现有的空间众包研究主要集中在提升平台兴趣和客户体验上。然而，在这项工作中，我们研究了空间众包中工作人员的公平任务分配。也就是说，我们的目标是以公平的方式将被视为短缺资源的任务分配给各个空间工作者。在本文中，我们首先形式化地定义了一个在线双目标匹配问题，即公平有效的任务分配问题(FETA)，并定义了它的特例/变体，以捕捉最典型的空间众包场景。我们针对FETA的每一种变体提出了相应的解决方案。特别地，我们证明了动态序贯变量是已有公平调度问题的推广，它可以用O(N)公平代价界(n是工人总数)来求解，并且对于m大小的一般批次情形(m是最小批量)，我们给出了O(n/m)公平代价界。最后，我们在合成数据集和真实数据集上对算法的有效性和效率进行了评估。
With the pervasiveness of mobile devices, wireless broadband and sharing economy, spatial crowdsourcing is becoming part of our daily life. Existing studies on spatial crowdsourcing usually focus on enhancing the platform interests and customer experiences. In this work, however, we study the fair assignment of tasks to workers in spatial crowdsourcing. That is, we aim to assign tasks, considered as a resource in short supply, to individual spatial workers in a fair manner. In this paper, we first formally define an online bi-objective matching problem, namely the Fair and Effective Task Assignment (FETA) problem, with its special cases/variants of it to capture most typical spatial crowdsourcing scenarios. We propose corresponding solutions for each variant of FETA. Particularly, we show that the dynamic sequential variant, which is a generalization of an existing fairness scheduling problem, can be solved with an O(n) fairness cost bound (n is the total number of workers), and give an O(n/m) fairness cost bound for the m-sized general batch case (m is the minimum batch size). Finally, we evaluate the effectiveness and efficiency of our algorithm on both synthetic and real data sets.