MDP-Based Budget Allocation for Efficient Cooperative Task Solving

In order to facilitate crowdsourcing-based task solving, complex tasks are decomposed into interdependent subtasks that can be executed cooperatively by individual workers. Aiming to maximize the quality of the final solution subject to the self-interested worker's utility maximization, a key challenge is to allocate the limited budget among the subtasks as the rewards for workers having various levels of abilities. This study is the first attempt to show the value of Markov decision processes (MDPs) for the problem of optimizing the quality of the final solution by dynamically determining the budget allocation on sequentially dependent subtasks under the budget constraints and the uncertainty of the workers' abilities. Our simulation-based approach verifies that compared to some offline methods where workers' abilities are fully known, our proposed MDP-based payment planning is more efficient at optimizing the final quality under the same limited budget.