Budgeted online assignment in crowdsourcing markets: Theory and practice

We consider the following budgeted online assignment (BOA) problem motivated by crowdsourcing. We are given a set of offline tasks that need to be assigned to workers who come online from the pool of types {1, 2, ., n}. For a given time horizon {1, 2, ., T}, at each instant of time t, a worker j arrives from the pool in accordance with a known probability distribution [pJt] such that J2jPit li has a known subset N(j) of the tasks that it can complete, and an assignment of one task i to j (if we choose to do so) should be done before task i's deadline. The assignment e = (i, j) (of task i e N(j) to worker j) yields a profit we to the crowdsourcing provider and requires different quantities of K distinct resources, as specified by a cost vector ae 6 [0, 1]; these resources could be client-centric (such as their budget) or worker-centric (e.g., a driver's limitation on the total distance traveled or number of hours worked in a period). The goal is to design an online-assignment policy such that the total expected profit is maximized subject to the budget and deadline constraints.