A Truthful Budget Feasible Multi-Armed Bandit Mechanism for Crowdsourcing Time Critical Tasks

Motivated by allocation and pricing problems faced by service requesters on modern crowdsourcing platforms, we study a multi-armed bandit (MAB) problem with several realworld 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(B 2/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 Ω(B 2/3 K 1/3) on the expected regret for any budgeted MAB mechanism satisfying the above properties.