EPTP: Balancing Revenue and Differential Privacy in Spatial Crowdsourcing

TL;DR

Spatial crowdsourcing platforms (like Uber or DoorDash) face a critical trade-off: providing efficient routes for workers while keeping user locations private. This paper presents EPTP, a framework that uses Geo-Indistinguishability to mask task locations. By combining a "long-term effect" scheduling strategy with a high-performance Dynamic Programming (DP) insertion algorithm, EPTP boosts platform revenue by 70% while ensuring robust differential privacy.

Background: The Privacy-Utility Tug-of-War

In the world of spatial crowdsourcing, "Task Planning" is the engine that decides which path a worker should take to complete a series of requests. However, location data is inherently sensitive. Existing solutions often ignore privacy, and those that do use basic obfuscation usually see a massive drop-off in "Utility" (platform revenue).

The core challenge is: How can a platform build a profitable route if it doesn't know exactly where the tasks are?

Methodology: Private but Profitable

The authors break the problem down into two primary phases:

1. The Privacy Mechanism (Laplacian Obfuscation)

The framework applies an $ϵ$-Geo-Indistinguishability mechanism. This means a requester's true location $lo{c}_t$ is perturbed to $lo{c}_t^{\prime }$ using a planar Laplacian distribution.

• The Insight: The authors proved that even with obfuscated locations, if a worker reaches the noisy point $lo{c}_t^{\prime }$, there is a calculable probability $1-(1+{ϵ}_{t}R)e^{-{ϵ}_{t}R}$ that the task is actually completed within its true radius $R$.

2. Task Planning with Long-Term Foresight

Instead of just looking at the nearest task (Greedy), the algorithm sorts tasks based on a new ratio: REMD / STHDD.

• REMD (Revenue per Empty Moving Distance): Focuses on immediate gain.
• STHDD (Spare Time per Heading Destination Distance): Focuses on urgency and future travel costs.

3. Efficiency via Dynamic Programming

Updating a worker's route every time a new task appears is computationally expensive ($O(n{m}^3)$). The authors introduced a DP-based Insertion method. By pre-calculating the "maximum tolerant extra traveling time" ($M{D}_w[k]$) for each point in a current route, the algorithm can determine if a new task can be squeezed in at $O(1)$ time per position, reducing total complexity to $O(mn\log m+m^2)$.

Figure 1: The EPTP framework overview showing the interaction between the obfuscation layer and the planning algorithm.

Experimental Performance

The researchers tested EPTP against baseline-Fast and baseline-Delay.

• Revenue: EPTP consistently outperformed baselines, especially when the number of workers increased. Because it considers "long-term effects," it doesn't just chase the closest task but plans for those that might expire soon.
• Efficiency: Despite the mathematical overhead of privacy, the DP technique allowed EPTP to process 5,000 workers/tasks in under 0.4 seconds—significantly faster than baseline-Fast.

Figure 2: Revenue and Time cost comparison. Note that EPTP (blue line) maintains high revenue with lower time growth.

Critical Insight & Conclusion

The true value of this paper lies in its Analysis Model. By moving beyond traditional competitive ratios (which assume exact locations) and adopting an "Expected Revenue" model, the authors provide a more realistic way to evaluate privacy-preserving algorithms.

However, there are limitations: the model assumes a unit speed for all workers and a uniform distribution of exact locations during the Bayesian update. In real-world urban environments (with varying traffic and non-uniform density), these assumptions might need further refinement. Regardless, EPTP serves as a robust blueprint for the next generation of privacy-aware GIS and crowdsourcing applications.