Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals
Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
中科院分区：
文献类型：
--
作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
有效地将任务分配给工作人员是众包中的一个核心问题。在本文中，我们考虑一个特殊的设置灵感来自空间众包平台，工人和任务动态到达。此外，我们假设所有的任务都是异质的，每个工作任务分配都会带来不同的回报。自然的挑战在于如何将工人和任务到达的不确定性纳入我们的在线分配策略中，以使总的预期回报最大化。为了应对这一挑战，我们假设工人“类型”和任务“类型”的到达模式不是不稳定的，并且可以从历史数据中预测。更具体地说，我们考虑有限的时间范围T，并假设在每个时间步中，对单个工人和任务进行采样（即，“到达”），并且该采样过程对于整个T个在线时间步长相同且独立地重复。我们的模型，称为在线任务分配与双边到达（OTA-TSA），是一个显着的推广经典的在线任务分配的任务集被假定为离线。对于一般版本的OTA-TSA，我们提出了一个最佳的非自适应算法，实现了0.295的在线竞争比。对于OTA-TSA的特殊情况下，奖励是一个功能的工人类型，我们提出了一种改进的算法（这是自适应的），并实现了至少0.343的竞争比。在硬度方面，沿着表明通过我们的非自适应算法获得的比率是所有非自适应算法中最好的，我们进一步表明没有（自适应）算法可以实现优于$0.581的比率（无条件地），即使对于具有同质任务的OTA-TSA的特殊情况（即，所有的奖励都是一样的）。我们分析的核心是一个新的技术工具（这是一个关于生灭过程的精炼概念），称为两阶段生灭过程，这可能是独立的兴趣。最后，我们对从众包平台获得的两个真实世界的数据集进行数值实验，以补充我们的理论结果。
Efficient allocation of tasks to workers is a central problem in crowdsourcing. In this paper, we consider a special setting inspired from spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogeneous and each worker-task assignment brings a distinct reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected rewards are maximized. To attack this challenge, we assume the arrival patterns of worker "types'' and task "types'' are not erratic and can be predicted from historical data. To be more specific, we consider a finite time horizon T and assume in each time-step, a single worker and task are sampled (i.e., "arrive'') from two respective distributions independently, and this sampling process repeats identically and independently for the entire T online time-steps. Our model, called Online Task Assignment with Two-Sided Arrival (OTA-TSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTA-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OTA-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.343. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all non-adaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than $0.581 (unconditionally), even for the special case of OTA-TSA with homogenous tasks (i.e., all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process), called the two-stage birth-death process, which may be of independent interest. Finally, we perform numerical experiments on two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.