An Improved Approximation Algorithm for Wage Determination and Online Task Allocation in Crowd-Sourcing

Crowd-sourcing has attracted much attention due to its growing importance to society, and numerous studies have been conducted on task allocation and wage determination. Recent works have focused on optimizing task allocation and workers' wages, simultaneously. However, existing methods do not provide good solutions for real-world crowd-sourcing platforms due to the low approximation ratio or myopic problem settings. We tackle an optimization problem for wage determination and online task allocation in crowd-sourcing and propose a fast 1-1/(k+3)^(1/2)-approximation algorithm, where k is the minimum of tasks' budgets (numbers of possible assignments). This approximation ratio is greater than or equal to the existing method. The proposed method reduces the tackled problem to a non-convex multi-period continuous optimization problem by approximating the objective function. Then, the method transforms the reduced problem into a minimum convex cost flow problem, which is a well-known combinatorial optimization problem, and solves it by the capacity scaling algorithm. Synthetic experiments and simulation experiments using real crowd-sourcing data show that the proposed method solves the problem faster and outputs higher objective values than existing methods.

Authors

• Yuya Hikima The University of Tokyo
• Yasunori Akagi NTT Human Informatics Labratories, NTT Corporation
• Hideaki Kim NTT Human Informatics Labratories, NTT Corporation NTT Communication Science Laboratories, NTT Corporation
• Taichi Asami NTT Human Informatics Laboratories, NTT Corporation

Keywords

• CSO: Applications
• CSO: Constraint Optimization
• CSO: Mixed Discrete/Continuous Optimization
• HAI: Crowdsourcing