A Truthful Budget Feasible Multi-Armed Bandit Mechanism for Crowdsourcing Time Critical Tasks
A Truthful Budget Feasible Multi-Armed Bandit Mechanism for Crowdsourcing Time Critical Tasks
复制标题
DOI：
--
复制
发表时间：
2015-05
期刊：
影响因子：
--
通讯作者：
Arpita Biswas;Shweta Jain;Debmalya Mandal;Y. Narahari
中科院分区：
文献类型：
--
作者：
Arpita Biswas;Shweta Jain;Debmalya Mandal;Y. Narahari
基于现代众包平台上服务请求者面临的分配和定价问题，研究了一个具有以下特征的多臂强盗（MAB）问题：（a）请求者希望众包多个任务，但有固定的预算，这导致在分配任务时需要权衡成本和质量;（B）每个任务都有一个固定的截止日期，并且分配给任务的工作人员在该截止日期之前是不可用的;（c）拥挤工作人员的质量（在截止日期内成功完成任务的概率）是未知的;以及（d）拥挤工作人员对他们的成本是有策略的。我们提出了一种机制，最大限度地提高预期数量的成功完成的任务，确保预算的可行性，激励相容性，和个人的理性。我们建立了一个上限为O（B2/3（Kln（KB））1/3）的预期遗憾的建议机制相对于一个适当的基准算法，其中B是总预算和K是工人的数量。接下来，我们提供了任何确定性的真实机制，解决上述问题的一个特征，并使用此特征建立一个Ω的下限（B2= 3 K1 =3）的预期遗憾的任何预算的MAB机制满足上述性质。
Motivated by allocation and pricing problems faced by service requesters on modern crowdsourcing platforms, we study a multi-armed bandit (MAB) problem with several real-world features: (a) the requester wishes to crowdsource a number of tasks but has a fixed budget which leads to a trade-off between cost and quality while allocating tasks to workers; (b) each task has a fixed deadline and a worker who is allocated a task is not available until this deadline; (c) the qualities (probability of completing a task successfully within deadline) of crowd workers are not known; and (d) the crowd workers are strategic about their costs. We propose a mechanism that maximizes the expected number of successfully completed tasks, assuring budget feasibility, incentive compatibility, and individual rationality. We establish an upper bound of O(B2/3(K ln(KB))1/3) on the expected regret of the proposed mechanism with respect to an appropriate benchmark algorithm, where B is the total budget and K is the number of workers. Next, we provide a characterization of any deterministic truthful mechanism that solves the above class of problems and use this characterization to establish a lower bound of Ω(B2=3K1=3) on the expected regret for any budgeted MAB mechanism satisfying the above properties.