Harmonizing Incentives: A Stable Matching Approach to Combined Crowdsourcing Tasks

TL;DR

In the world of crowdsourcing, workers and requesters are often at odds. Researchers from USTC have developed a new multi-task auction mechanism that uses Stable Matching theory to ensure everyone is satisfied. By accounting for Task Complementarity (e.g., doing two nearby tasks is cheaper than doing them separately), the model ensures participants "stay in the game" while maximizing the number of completed tasks.

Background: Beyond Social Welfare

Most crowdsourcing systems focus on "Social Welfare Maximization"—trying to get the most work done for the least total cost. However, in the real world, participants are selfish. If a worker feels they can get a better deal elsewhere, or a requester thinks they can swap a worker for a cheaper one, the system becomes unstable.

The core challenge addressed here is: How do we create an assignment where no worker and no crowdsourcer want to "break up" with their current partners to form a better pair?

The Intuition: Complementarity and Stability

The authors introduce two key concepts:

1. Spatiotemporal Complementarity: If Bob is already at a location to take a photo of a building (Task A), the cost for him to report the traffic on the adjacent street (Task B) is negligible. Standard models treat these as independent costs; this paper treats them as a Combination.
2. Many-to-Many Matching: Unlike previous "one-to-many" models, this framework realizes that workers can handle multiple types of tasks simultaneously, and each task type might require multiple workers.

Methodology: The Devised Deferred Acceptance Algorithm

The solution is a modification of the classical Gale-Shapley algorithm, adapted for a combinatorial auction setting.

How it works:

• Proposing: Workers propose task combinations that maximize their utility based on current "bids" (payments from requesters).
• Filtering: Crowdsourcers (requesters) receive these bids and sort them. They accept the best workers until they hit their Budget Constraint or Quantity Constraint.
• Bidding Down: If a worker is rejected, they lower their price (bid) for the next round, trying to become more attractive to the crowdsourcer until they either get accepted or their utility hits zero.

The algorithm ensures Individual Rationality (no one loses money), Fairness (no "Type I" blocking pairs), and Non-wastefulness (all budgets are used efficiently).

Experimental Insights

The researchers compared their stable algorithm against a standard "Greedy" algorithm.

• Success in Stability: While the Greedy algorithm has slightly higher total Social Welfare (as its only goal is optimization), it fails to keep participants happy.
• Worker Benefits: The stable algorithm results in significantly higher Average Worker Utility. This is crucial for platform retention.
• Scalability: As the number of task types increases (from 6 to 10), the number of tasks completed increases steadily, proving the "Combined" approach works.

Critical Perspective

The trade-off presented is fascinating: Stability vs. Efficiency. By sacrificing a small percentage of total system efficiency, the platform gains "Strong Stability."

Limitations: The model assumes that the quality of work is uniform across all workers. In reality, skill levels vary, which would add another layer of complexity to the preference rankings. Future work may need to integrate a "Quality of Service" (QoS) metric into the stable matching preferences.

Conclusion

This paper provides a robust mathematical foundation for the next generation of mobile crowdsourcing platforms (like Uber, Meituan, or task-based sensing apps). By treating task assignment as a stable matching problem with complementarity, we move closer to "fair" gig economies where the system's goals and the workers' interests are naturally aligned.