  We investigate the problem of heterogeneous task assignment in crowdsourcing
markets from the point of view of the requester, who has a collection of tasks.
Workers arrive online one by one, and each declare a set of feasible tasks they
can solve, and desired payment for each feasible task. The requester must
decide on the fly which task (if any) to assign to the worker, while assigning
workers only to feasible tasks. The goal is to maximize the number of assigned
tasks with a fixed overall budget.
  We provide an online algorithm for this problem and prove an upper bound on
the competitive ratio of this algorithm against an arbitrary (possibly
worst-case) sequence of workers who want small payments relative to the
requester's total budget. We further show an almost matching lower bound on the
competitive ratio of any algorithm in this setting. Finally, we propose a
different algorithm that achieves an improved competitive ratio in the random
permutation model, where the order of arrival of the workers is chosen
uniformly at random. Apart from these strong theoretical guarantees, we carry
out experiments on simulated data which demonstrates the practical
applicability of our algorithms.
