Beyond Blind Assignment: Maximizing Acceptance in Rejection-Aware Crowdsourcing

TL;DR

Most spatial crowdsourcing systems assume workers are passive agents who accept whatever task is pushed to them. This paper challenges that "perfect obedience" assumption by introducing the MA-SC (Maximizing Acceptance in Spatial Crowdsourcing) problem. By modeling the probability that a worker will actually interest themselves in a task, the authors provide a suite of algorithms—led by a highly efficient Greedy approach—that maximizes system throughput even when workers have the power to say "no."

Background: The Price of Rejection

In platforms like Uber or DoorDash, rejections are not just an anomaly; they are a standard part of the workflow. Drivers reject rides because of distance, poor pay, or inconvenient destinations. When a server ignores these preferences, it results in wasted time and a "cold" system where tasks remain unvisited.

The core challenge lies in the Inductive Bias of previous models: they optimized for distance or coverage but ignored the human element. This paper treats acceptance as a probabilistic event, turning task assignment into a complex combinatorial optimization problem.

Methodology: The Math of "Interest"

The authors define $p_{ij}$ as the probability that worker $w_i$ is interested in task $t_j$. The expected acceptance for a single worker receiving a set of $k$ tasks ($T_{w_i}$) is calculated as:

$E(x_i)=1-{\prod }_{t_j\in T_{w_i}}(1-p_{ij})$

The goal is to partition the task set such that the sum of these expectations across all workers is maximized. Because this is proven to be NP-hard, the paper explores a hierarchy of solutions:

1. Exact Solutions: Dynamic Programming (DP) and Depth-First Search (DFS) with pruning for small-scale scenarios.
2. Guided Random Sampling (GRS): Using weighted sampling to find promising regions of the solution space.
3. Local Search (LS): Iteratively swapping tasks between workers to climb towards a local optimum.
4. Greedy Algorithm: Picking the best task-worker pair in each step—a method that surprisingly outperforms more complex heuristics.

Experiments & Results

The evaluation focused on two dimensions: Expected Acceptance (how many tasks actually get done) and Efficiency (how fast the server can decide).

Small-Scale Performance

With $n=4$, DFS proved significantly faster than DP because its pruning strategies could eliminate sub-optimal assignment branches early. Most approximation methods kept pace with the optimal solution, proving their reliability.

Large-Scale Scalability

When scaled to 3,000 workers, the Greedy algorithm became the "SOTA" choice. It maintained a high acceptance rate (approx. 0.5 ratio) while keeping computation costs low. Interestingly, Parallel Search (pSearch) offered competitive speed but struggled slightly more with task collisions.

Critical Insights & Conclusion

This work marks a shift from Server-Centric to Worker-Centric crowdsourcing. By acknowledging that workers are autonomous agents with preferences, the system becomes more resilient.

Key Takeaways:

• Simplicity Wins: The Greedy algorithm's performance suggests that in high-dimensional task spaces, making locally optimal choices regarding worker interest is a robust strategy.
• The Scalability Gap: While exact solutions are mathematically elegant, they are practically useless for real-time city-scale applications, highlighting the need for the $O(n{m}^2)$ or better approximations explored here.

Limitations: The model assumes $p_{ij}$ is known or easily mineable from historical data. In highly dynamic or "cold-start" scenarios where worker behavior is unknown, the model would need to be coupled with a Multi-Armed Bandit (MAB) framework to learn preferences on the fly.