Maximizing Acceptance: Making Spatial Crowdsourcing Rejection-Aware

TL;DR

Current spatial crowdsourcing systems (like Uber or gMission) often fail because they assume workers will always accept assigned tasks. This paper formally defines the Maximizing Acceptance in Spatial Crowdsourcing (MA-SC) problem, proves it is NP-hard, and provides a Greedy algorithm that is both theoretically grounded (0.5 approximation ratio) and practically efficient for massive real-world datasets.

The Reality Check: Workers Can Say "No"

In the typical Server Assigned Tasks (SAT) mode, a central server matches moving workers to location-specific tasks. Traditional models optimize for total tasks assigned or minimum travel distance, but they ignore the "Rejection" factor. If a worker finds the pay too low or the distance slightly too far, they reject the task, and that task remains unserved, wasting a matching cycle.

The Research Intuition: If we can model the probability of interest ($p_{ij}$) for every worker-task pair, we can optimize for the Expected Acceptance (EA). By maximizing the sum of probabilities that workers will say "yes," we naturally increase the system's total throughput.

Methodology: Mining Submodular Gold

The authors prove that the objective function—the total expected acceptance—is monotone and submodular.

1. The Exact Solutions

For small-scale problems, the authors propose:

• Dynamic Programming (DP): A bottom-up approach that is exhaustive but has a staggering complexity of $O(m{4}^m)$.
• Depth-First Search (DFS) with Pruning: By calculating a lower bound for rejections, the algorithm can "cut" branches of the search tree that cannot possibly beat the current best solution.

2. The Practical Winner: Greedy Algorithm

Since the objective is submodular, a Greedy approach is highly effective. In each step, the algorithm selects the worker-task pair $(w_i,t_j)$ that provides the maximum marginal increase in expected acceptance.

The objective function: Minimizing the product of "non-interest" probabilities to maximize total acceptance.

To make this scale to thousands of workers, the authors optimized the Greedy implementation to $O(n{m}^2)$ (and $O(m^2)$ in expectation) by maintaining a vector of maximum marginal gains for each row, avoiding redundant re-calculations.

Experimental Evidence

The authors validated their model using real-world data from Gowalla (check-ins) and Uber (NYC trip data).

• Correlation: They first proved on the gMission platform that "Expected Acceptance" is highly correlated with "Practical Acceptance," justifying their mathematical model.
• Scalability: While DFS dies out when the number of tasks $k$ per worker exceeds 2 or 3, the Greedy algorithm handles $n=10,000$ workers with ease.
• Acceptance Quality: Greedy and a heuristic called "Parallel Search" consistently outperformed sampling methods (GRS), capturing nearly the same value as the optimal brute-force solutions in small-scale tests.

Figure: In small-scale tests (n=4), the Greedy algorithm (Green) is virtually indistinguishable from the Optimal solution (Red).

Critical Insights & Future Outlook

This work fills a critical gap in crowdsourcing literature by moving away from "perfect worker" assumptions.

Key Takeaways:

1. Submodularity is Key: Many assignment problems in crowdsourcing can be reduced to submodular maximization, allowing us to use Greedy handles on NP-hard problems.
2. Estimation Matters: The system relies on a good $p_{ij}$ matrix. The authors suggest using Maximum Likelihood Estimation (MLE) based on historical worker behavior to "learn" what tasks a worker is likely to accept.

Limitations: The current model is "timestamp-based," meaning it processes batches of tasks. The next frontier is Online Rejection-Aware Assignment, where the server must decide instantly when a single worker appears, without waiting for a batch.

Senior Editor's Note: This paper is a foundational read for anyone building dispatching systems for gig-economy platforms where worker autonomy is a first-class citizen.