MAPS: Maximizing Spatial Crowdsourcing Revenue via Matching-Based Dynamic Pricing

TL;DR

Spatial crowdsourcing platforms like Uber and DiDi face a complex balancing act: pricing tasks to attract requesters while managing a finite, mobile workforce. This paper formalizes the Global Dynamic Pricing (GDP) problem and introduces MAPS, a strategy that combines multi-armed bandit learning (UCB) with bipartite matching to solve the trilemma of unknown demand, limited supply, and dependent local markets.

Background: The Price of Locality

In traditional crowdsourcing, any worker can do any task. In spatial crowdsourcing, geography is the constraint. A taxi in Brooklyn cannot pick up a passenger in Queens simultaneously; however, its presence in Brooklyn affects the potential supply in Queens. Existing methods often use a unified price or simple supply-demand ratios, which fail to capture the "dependency" of supply—where one worker is a shared resource across multiple potential task regions.

The Core Challenge: Why is this NP-Hard?

The authors identify three hurdles:

1. Unknown Demand: We don't know how much a specific requester is willing to pay until we offer a price.
2. Limited Supply: Unlike cloud labor, physical workers are a scarce resource during peak hours.
3. Dependent Supply: A worker's movement links different local markets (grids), making the pricing of one grid dependent on the others.

Due to these interdependencies and the probabilistic nature of task acceptance, the GDP problem is proven to be NP-hard.

Methodology: The MAPS Framework

1. Learning the Demand (UCB-based Estimation)

Instead of assuming a known price-response curve, MAPS uses an Upper Confidence Bound (UCB) approach. It treats different prices as "arms" in a bandit problem, balancing the need to explore (test new prices to see acceptance) and exploit (use prices known to generate revenue).

2. Approximating Revenue with Limited Supply

The method models expected revenue by finding the intersection of:

• The Demand Curve: The expected revenue if supply were infinite.
• The Supply Curve: The maximum revenue achievable given $n$ workers.

3. Global Optimization via Bipartite Matching

To handle Dependent Supply, MAPS uses a greedy incremental matching algorithm. It builds a bipartite graph between workers and tasks. In each step, it identifies which grid would yield the "Largest Increase" in expected revenue if an additional worker were assigned there, then updates the price for that grid accordingly.

Experimental Validation

The authors tested MAPS against several baselines:

• BaseP: A unified base price for all grids.
• SDR/SDE: Heuristics based on Supply-Demand Ratios or exponential differences.
• CappedUCB: Pricing each grid as an independent market.

Key Findings:

• Revenue Supremacy: MAPS outperformed all baselines in both synthetic tests and real-world datasets (Beijing taxi data).
• Scalability: Even as the number of tasks reached $10^5$, the algorithm maintained linear time complexity growth, making it viable for city-scale deployment.

Depth Insight: The "Why" behind MAPS

The genius of MAPS lies in its recognition that local markets are not islands. By using a matching-based approach instead of purely local price adjustments, the platform can "route" the impact of a worker's availability across the entire map. This prevents scenarios where a local price spike in one grid inadvertently starves an adjacent grid of all its workers, leading to a net loss in global revenue.

Conclusion and Future Outlook

MAPS provides a robust theoretical and practical framework for dynamic pricing in the sharing economy. While the current model assumes $i.i.d.$ private valuations within a grid, future work could integrate transformer-based demand forecasting or handle more complex worker preferences (like destination constraints).

Final Takeaway: For spatial platforms, the winning strategy isn't just about finding the "right price"—it's about finding the right matching of prices across a globally connected map.