Greedy-OT: Optimizing Spatial Crowdsourcing via Historical Threshold Learning

TL;DR

In the world of spatial crowdsourcing (think Uber or Gigwalk), the platform must match workers to tasks in real-time without knowing who will show up next. This paper introduces the BOA (Budget-aware Online task Assignment) problem and solves it using Greedy-OT, an algorithm that learns from historical data to set a "price ceiling" (travel cost threshold). This prevents early, expensive matches from eating the entire budget, significantly increasing the total number of tasks completed.

The Problem: The "Short-Sighted" Greedy Trap

Standard online assignment typically uses a simple Greedy approach: when a worker appears, match them to the nearest available task.

However, in a budget-constrained environment, this is dangerous. Imagine an "Adversarial Model" where the first few workers are very far from their tasks. A simple greedy algorithm will match them, spend a huge portion of the budget, and leave nothing for the hundreds of workers arriving later who might be much closer to other tasks.

The core challenge is: How do we know which matches are "too expensive" to accept without seeing the future?

Methodology: Pruning via Historical Insight

The researchers' key insight is that human mobility is periodic. Traffic patterns on a Wednesday in New York are remarkably similar to the previous Wednesday.

1. From Offline Optimal to Online Guidance

The authors first define the Offline Optimal (OPT) using a Minimum-Cost Maximum-Flow reduction. While OPT is impossible in real-time (as it requires knowing all future worker locations), it provides a perfect "history lesson."

2. The Greedy-OT Algorithm

Instead of guessing a threshold (as in their baseline Greedy-RT), Greedy-OT performs the following:

• Learn: Run the OPT algorithm on historical data (e.g., yesterday's workers and tasks).
• Extract: Identify the maximum travel cost ($c_{max}^{\ast }$) among the matches in that optimal set.
• Apply: Use this $c_{max}^{\ast }$ as a strict threshold for today's real-time matching. If a worker-task pair's cost exceeds this, the platform rejects it, saving the budget for potentially better future matches.

Figure 1: High-level view of spatial crowdsourcing dynamics.

Experiments and Results

The authors tested their approach using both synthetic data and the Uber Trip Dataset (4.5 million pickups in NYC).

Performance in Adversarial Scenarios

In scenarios designed to trick greedy algorithms (workers arriving from furthest to nearest), Greedy-OT remained stable, while the simple greedy performance plummeted.

Scalability and Robustness

• Matching Size: Greedy-OT consistently achieved 70%+ of the theoretical maximum performance.
• Efficiency: Because it only checks a simple threshold condition, the inference time is nearly instantaneous ($O(|T|)$), making it suitable for high-frequency platforms.
• Threshold Stability: The optimal threshold was found to be remarkably robust, fluctuating less than 15% even when the number of workers varied significantly across different days of the week.

Figure 2: Performance metrics across varying worker counts, task counts, and budgets.

Critical Insights & Future Outlook

The beauty of Greedy-OT lies in its Inductive Bias. By assuming that the "optimal cost distribution" is a stable property of a city's geography and task density, it avoids the need for complex, black-box deep learning models for many real-time routing tasks.

Limitations: The method relies on the "similarity" of distributions. In the event of an anomaly (e.g., a sudden city-wide protest or a major storm), the historical threshold might become invalid. Future iterations could benefit from a "Hybrid" model that adjusts the threshold dynamically if real-time distributions deviate too far from historical norms.

Takeaway for Practitioners: If you are building a matching engine for delivery or ride-sharing, don't just optimize for the immediate match. Look at your historical logs to find the "efficiency frontier" and use it as a guardrail for your real-time agents.