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

Abstract

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 42 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.