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 j pjt ≤ 1; j 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 ∈ 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 ∈ [0, 1] K ; 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. We propose and analyze two simple linear programming (LP)-based algorithms and achieve a competitive ratio of nearly 1/(+ 1), where is an upper bound on the number of non-zero elements in any ae. This is nearly optimal among all LP-based approaches.