Scaling Crowdsourcing through Social Influence: A Truthful Auction Approach

TL;DR

Crowdsourcing platforms often struggle with the "cold-start" problem—not having enough workers to complete large-scale tasks. This paper proposes a solution by turning existing users into "task diffusers" through social networks. By using MTD-L and MTD-IC (two auction-based mechanisms), the authors ensure that these diffusers are paid fairly and truthfully while minimizing the platform's total cost.

Background: The Participation Bottleneck

Despite the success of platforms like Amazon Mechanical Turk (AMT), the "long tail" of tasks often remains uncompleted due to a lack of interested workers. Traditional incentive mechanisms focus on performing the task but ignore the recruitment cost. The core insight of this paper is that Social Influence—leveraging the connections of registered users—can be the engine for large-scale worker recruitment.

Methodology: The Core Diffusion Engines

The authors move beyond simple sharing and define two rigorous mathematical models for how tasks spread:

1. Linear Task Diffusion Model (MTD-L): In this model, influence is cumulative. If three of your friends share a task with you, the probability of you participating increases linearly.
2. Independent Cascade Task Diffusion Model (MTD-IC): Here, each diffuser has a single chance to influence a neighbor. The influence depends on the joint probability of being reached by at least one winner.

Architectural Flow

The system follows a sealed reverse auction process where the platform acts as the auctioneer and registered users are the bidders.

Predicting Influence

A critical challenge is: How do we know how many people a user can actually recruit? The authors propose three estimators:

• TIE (Topology-based): Uses Jaccard Similarity to see how many mutual friends you share.
• HIE (History-based): Looks at past performance (retweets/conversions) to estimate task-specific influence.
• GIE (Global Influence): Uses K-shell decomposition to identify users at the "core" of the social network who have massive reach beyond their immediate neighbors.

Mechanism Design: Why it's Truthful

The "Strategic User" is a major hurdle in auction design. If users can lie about their effort/cost to get a higher payment, the system becomes inefficient. The paper proves that their greedy selection rule is monotone and utilizes critical value payments. In simple terms: bidding your true cost is the only way to maximize your utility.

Experiments & Results

Using real-world Twitter data, the researchers tested their mechanisms against "Fast-Selector," a common greedy baseline.

1. Cost Efficiency

The GIE-based mechanism (Global Influence) resulted in the lowest social cost because it identifies "super-nodes" capable of diffusing tasks widely with fewer incentives.

2. Task Completion Rate

While GIE is cheap, HIE (History-based) is the most effective at actually getting tasks done. HIE-based mechanisms achieved a completion rate roughly 3x higher than GIE in certain settings, proving that past behavior is a better predictor of future Influence than network position alone.

Critical Insight & Conclusion

The main takeaway for the industry is the Trade-off between Cost and Quality.

• If you are a startup with a strict budget, use GIE (Topology/K-shell) to find broad connectors.
• If you are a high-stakes platform requiring guaranteed results, use HIE (History) to select users with a proven track record of conversion.

Limitations: The Global Influence Estimation (GIE) has high computational complexity ($O(|V{|}^3)$), making it difficult to scale to massive networks like the full Twitter or Facebook graph without further optimization.

Takeaway: This work shifts the paradigm from "paying workers to work" to "incentivizing influencers to grow the workforce," solving the fundamental scalability issue of modern crowdsourcing.