A Markov Decision Process Framework for Predictable Job Completion Times on Crowdsourcing Platforms

Chandrashekar Lakshminarayanan, Ayush Dubey, Shalabh Bhatnagar, Chithralekha BalamuruganHCOMP 2014 · DOI

Abstract

Crowdsourcing platforms often suffer from "task starvation," where completion times are highly volatile due to unobservable crowd dynamics. This paper presents a Markov Decision Process (MDP) framework designed to achieve predictable job completion times by dynamically adjusting task pricing. By using the completion times of recently finished tasks as a proxy for the hidden state of the crowd, we derive an optimal pricing policy that minimizes a cost function accounting for both monetary expense and completion time variance. Experimental results on CrowdFlower demonstrate that our dynamic policy outperforms a fixed-price baseline, providing faster and more consistent completion times at a lower overall cost.

Introduction

In crowdsourcing environments such as Amazon Mechanical Turk, requesters frequently encounter significant variance in task completion times. A batch of tasks might be completed in minutes or remain untouched for hours, a phenomenon known as task starvation. This volatility presents a major obstacle for organizations requiring steady, predictable workflows.

The speed of completion is primarily driven by "crowd dynamics"—factors such as the number of active workers and their current motivation—which are not directly observable by the requester. Consequently, requesters often overpay to ensure speed or underpay and suffer long delays. This research proposes a middle ground: a dynamic pricing strategy that leverages a Crowd Behavior MDP (CBMDP) to provide predictability without excessive expenditure.

Methodology

The pricing challenge is modeled as a CBMDP where the requester adjusts prices based on the perceived state of the crowd.

State and Action Spaces

Since the true state of the crowd is hidden, we utilize the average completion times of recently finished tasks as a proxy. The state space $s$ is partitioned into $k=9$ discrete bins representing different ranges of average completion times. To account for information delay, a lag factor is incorporated into the state calculation. The action space $A$ consists of three pricing tiers for a batch of 120 CAPTCHAs: 3, 4, or 6 cents.

Cost Function and Optimization

The objective function is designed to prioritize predictability. The cost $g$ is defined as a linear combination of the offered price and the worst-case completion time (defined as the mean plus two standard deviations). This explicitly penalizes high variance. Model parameters were learned from a 48-hour dataset collected on CrowdFlower, and the optimal policy $u^*(s)$ was computed using policy iteration.

Table 1: The optimal pricing policy $u^*(s)$ derived from the CBMDP framework.

As shown in Table 1, the optimal policy dynamically adjusts the price based on the current state. For instance, when the crowd is highly active (low completion times in states 1-4), the model maintains a low price of 3 cents. It increases the price to 6 cents when the crowd becomes sluggish (states 5, 6, and 9) to mitigate starvation.

Experimental Results

The optimal MDP policy ($u^*$) was evaluated against a baseline policy ($u^2$) that paid a constant 4 cents per task over four 24-hour test periods.

Performance Comparison

The MDP policy demonstrated superior performance across all key metrics:

  • Better Predictability: The standard deviation of completion times was reduced from 29 minutes (baseline) to 21 minutes.
  • Faster Completion: The mean completion time improved from 58 minutes to 54 minutes.
  • Lower Cost: Despite utilizing the 6-cent premium rate when necessary, the MDP policy's total expenditure was less than 460 cents, compared to 480 cents for the fixed-price baseline.
Figure 1: Cumulative Distribution Function (CDF) of completion times for the optimal policy $u^*$ versus the fixed-price baseline $u^2$.

The Cumulative Distribution Function (CDF) in Figure 1 illustrates these gains. The curve for the optimal policy $u^*$ is steeper and shifted to the left compared to the baseline $u^2$, indicating that a higher percentage of tasks are completed within shorter timeframes with significantly less variance.

Conclusion

This study demonstrates that crowd behavior on platforms like CrowdFlower is not merely random but exhibits states that can be proxied and managed. By treating predictability as a primary objective within an MDP framework, requesters can achieve more reliable workflows. Dynamic pricing proves to be a "win-win" strategy, offering better performance for the requester while efficiently allocating rewards to the crowd.

Summary updated

BibTeX
@inproceedings{lakshminarayanan2014markov,
  author = {Chandrashekar Lakshminarayanan and Ayush Dubey and Shalabh Bhatnagar and Chithralekha Balamurugan},
  title = {{A Markov Decision Process Framework for Predictable Job Completion Times on Crowdsourcing Platforms}},
  booktitle = {HCOMP},
  year = {2014},
  doi = {10.1609/hcomp.v2i1.13183},
}
Figure