Stackelberg Games in Mobile Crowdsourcing: Optimizing Multiple Collaborative Tasks

TL;DR

Mobile crowdsourcing relies on user participation, but why would a rational user drain their battery or data for a server? This paper introduces a Stackelberg game-based framework specifically designed for multiple collaborative tasks. Unlike previous works that look at tasks in isolation, this model considers the interdependencies between tasks and provides four distinct incentive mechanisms to ensure both the server and the users achieve a Nash Equilibrium (NE).

The "Collaboration" Gap in Crowdsourcing

Most existing incentive designs assume a "one-user-one-task" (independent) or "many-users-one-task" (single collaborative) structure. However, real-world scenarios—like building a Wi-Fi fingerprint database or localized speech recognition—require multiple tasks, each needing a minimum threshold ($m_j$) of participants to be valid.

The challenge lies in the interrelation:

• Resource Constraints: Users have limited capacity and must choose which tasks to prioritize.
• Incentive Interaction: How should a server distribute a total budget among different tasks to ensure all reach their minimum participant thresholds?

Methodology: The Two-Stage Stackelberg Game

The authors model the interaction as a leader-follower game:

1. Stage I (Server): The server acts as the leader, announcing the total reward ($R$) and task thresholds ($W$).
2. Stage II (Users): Users act as followers. Based on their private costs ($c_i$) and task capacities, they decide which tasks to perform to maximize their individual utility (Reward - Cost).

The paper tackles this across two dimensions of information:

• Complete Information: The server knows exact user costs (useful for long-term historical data).
• Incomplete Information: The server only knows the Cumulative Distribution Function (CDF) of costs, representing a more realistic, privacy-preserving scenario.

Reward Functions

Two strategies for splitting the "pie":

• NU (Number of Users): Reward is proportional to the number of participants required ($m_j$).
• VT (Value of Tasks): Reward is proportional to the inherent value ($v_j$) the task provides to the server.

Figure 1: The interaction model between the server and mobile users.

Real-Time Adaptation: Online Mechanisms

In the real world, users don't all show up at once. The authors introduce an Online Incentive Mechanism using a Markov Model to handle user mobility (Poisson arrivals and departures). The server periodically updates the reward strategy based on available users in that "window," ensuring the system stays computationally efficient—critical for "location-sense" apps where user attention spans are short.

Experimental Insights

The simulations revealed several key technical intuitions:

• The Competition Effect: As the number of users ($N$) increases, competition drives the cost threshold ($c^{\ast }$) down. This allows the server to achieve higher utility because the "asking price" from the user side drops.
• Threshold Sensitivity: If task thresholds ($m_j$) are set too high, the reward required to attract enough users can quickly eclipse the task's value, leading to zero utility for the server.
• NU vs. VT: The NU function is a "profit-maximizer" for the server, while VT is perceived as "fairer" to users who contribute to high-value objectives.

Figure 2: Impact of task thresholds on reward equilibrium.

Critical Analysis & Future Outlook

While the paper provides a rigorous mathematical foundation for collaborative tasks, it primarily assumes costs are proportional to the number of tasks. In reality, multi-tasking might introduce sub-linear costs (e.g., one trip to a location can satisfy multiple sensing tasks).

Takeaway: This work moves crowdsourcing theory away from "simple auctions" toward "complex collaborative ecosystems." For developers of mobile sensing apps, the lesson is clear: don't just pay per task; pay based on the collective threshold required to make the data meaningful.

Limitations

• Static Task Values: The model assumes task values ($v_j$) are fixed, whereas in reality, a task's value might diminish as more users contribute (diminishing marginal utility).
• User Honesty: The model assumes users provide accurate results once incentivized, but it does not account for malicious "sybil attacks" or low-quality data reporting.