WSMWT: Optimization for Multi-Worker Spatial Crowdsourcing

TL;DR

Most spatial crowdsourcing (SC) research assumes one task equals one worker. This paper breaks that mold by addressing Multi-Worker Tasks—scenarios like calling multiple Ubers for a large group or collecting diverse sensor data. By treating the problem as a variation of the Generalized Assignment Problem (GAP), the authors provide a greedy selection algorithm with a 2-approximation guarantee that significantly outperforms existing baselines.

Problem & Motivation: Beyond the "Single-Worker" Paradigm

In standard SC (e.g., TaskRabbit or basic Uber), a task is "done" when one person arrives. But consider a 20-person group needing five Uber XLs to reach a meeting on time:

• Interdependence: If only four cars arrive, the task is effectively failed (Binary Logic) or severely degraded (Linear Logic).
• Local Budgets: Unlike global budget models, each task requester has a specific limit they can pay.
• Complexity: Assigning workers to these tasks is APX-hard, meaning we cannot find an optimal solution in polynomial time, but we can get provably close.

Methodology: The Logic of Scoring

The authors define two key mathematical ways to value a task $S(t_j)$:

1. Linear Scoring: Success scales with the number of workers assigned until the requirement $N{W}_j$ is met.
2. Binary Scoring: A "cliff" effect; the score is zero unless at least $N{W}_j$ workers are present.

The core algorithm, WSMWT-LS, works in two phases:

• Pruning: Filter out workers who cannot physically reach the location within the deadline ($u_{ij}\le d_j$) or exceed the cost ($c_{ij}>B_j$).
• Sequencing & Conflict Resolution: Tasks are sorted by their "value density" (value per required worker). When two tasks compete for the same worker, the algorithm checks if the first task can substitute that worker for another available one without losing score.

In the figure above, lines represent potential pairings. The algorithm must navigate these connections to maximize the sum of scores across all tasks.

Experiments: Proving the 35% Gain

Using synthetic data scaled from the Foursquare dataset via the SCAWG toolbox, the authors compared WSMWT against MQA-Greedy (a state-of-the-art predictive assignment algorithm).

Key Insights:

• Worker Density: As the number of available workers increases, WSMWT scales significantly better than MQA because it actively manages the requirements of multi-worker tasks rather than treating them as independent single-worker units.
• Performance Boost: WSMWT-LS achieved a 35% improvement over MQA-Greedy. For binary tasks, the gap between WSMWT and random assignment was a staggering 75%.

The impact of the number of tasks on the total score: WSMWT consistently maintains a lead as the environment becomes more crowded.

Critical Analysis & Conclusion

Takeaway

The shift from "Single-Worker" to "Multi-Worker" makes spatial crowdsourcing models vastly more applicable to real-world logistics. The inclusion of conflict resolution in the greedy choice is a simple yet powerful heuristic that allows WSMWT to achieve high efficiency with a theoretical safety net (the 2-approximation).

Limitations & Future Work

• Dynamic Complexity: The current approach is primarily offline. Real-time SC would require handling workers who change their minds or tasks that appear mid-cycle.
• Network Flow: The authors suggest that treating the problem as a bipartite graph and applying network flow algorithms might yield an even better approximation ratio than the current greedy method.
• Incentive design: While budgets are fixed here, the transition to a dynamic auction where workers bid their costs would be a logical next step for this research.