[Big Data 2016] PAYG Crowdsourcing: Solving "Bob's Dilemma" in Object Identification

TL;DR

In this paper, researchers from HKUST address a fundamental inefficiency in crowdsourcing: the "all-or-nothing" payment model. By introducing a Pay-As-You-Go (PAYG) paradigm for Object Identification (OI), they provide a framework that pays workers per discovery, uses Adaptive Greedy Algorithms to minimize redundancy, and applies EM-based verification to ensure accuracy.

Bob's Dilemma: The Core Motivation

Imagine "Bob," a PhD student needing to proofread a paper. If he hires three people simultaneously, they might all find the same five obvious typos, and Bob pays triple for the same result. If he hires them one by one, he misses his deadline. This is the Object Identification (OI) challenge: how do we find the maximum number of "objects" (errors, tags, features) at minimum cost and time?

The authors argue that current platforms like Amazon Mechanical Turk are ill-suited for this because:

1. Incentive Misalignment: Workers have no reason to find "just one more" error if the reward is flat.
2. Redundancy: Multiple workers often identify the same easy-to-spot objects.
3. Context Sensitivity: You can't just split a paper into sentences for different workers; they need the whole context to find logic errors.

Methodology: Intelligence via Adaptive Submodularity

The researchers define the Probabilistic Worker Assignment (PWA) problem. Since they prove it is NP-hard, they turn to the mathematical beauty of Submodularity—the principle of diminishing returns.

1. The Adaptive Greedy Algorithm

Instead of picking workers all at once (static), the Adaptive Greedy Algorithm picks a batch, observes what they find, and then updates the probability distribution of remaining objects before picking the next set of workers. This ensures that the next worker assigned is the one most likely to find new objects that haven't been discovered yet.

Table: Key notations used in the PWA formulation.

2. Quality Control: When to Stop?

A significant contribution is the Termination Criteria. For every object a worker claims to find, the system must verify it. Instead of blindly trusting a worker, the system uses a majority voting mechanism. It keeps asking more workers to verify an object until a specific confidence threshold ($heta$) is reached.

The individual reliability of workers is estimated using an Expectation-Maximization (EM) algorithm, which accounts for the fact that we don't know the absolute "ground truth" of the file beforehand.

Experimental Insights

The authors tested their approach on gMission, a spatial crowdsourcing platform.

• The Power of Adaptive Selection: As seen in the figures below, the adp greedy algorithm (pink line) consistently finds objects faster and with fewer workers than random assignment (rand).
• Effect of Batch Size (k): The study reveals a trade-off. Choosing workers one by one ($k=1$) is the most cost-efficient but the slowest. Increasing $k$ speeds up the process but slightly increases the total cost due to unavoidable overlap.

Performance of Greedy vs. Adaptive Greedy under different crowd accuracy (Pcr) settings.

Critical Analysis & Conclusion

Takeaway

The shift to Pay-As-You-Go is a win-win. Requesters stop paying for redundant work, and high-performing workers are rewarded for their thoroughness. The use of adaptive submodularity provides a robust mathematical guarantee (the $1-1/e$ approximation ratio) that this isn't just a heuristic, but a near-optimal strategy.

Limitations

The model assumes we have some "prior knowledge" of worker capabilities (e.g., from historical data or qualification tests). In a "cold start" scenario where all workers are new, the system's efficiency would initially drop as it learns worker profiles.

Future Outlook

As datasets grow in complexity (e.g., identifying "deepfakes" or labeling nuanced medical data), these adaptive selection techniques will be vital to prevent the "cost explosion" of human-in-the-loop systems.