MDP-Based Budget Allocation for Efficient Cooperative Task Solving

JIANG Huan; ZUO Min; MATSUBARA Shigeo

doi:10.1049/cje.2017.08.001

Volume 26 Issue 5

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(5): 966-972

JIANG Huan, ZUO Min, MATSUBARA Shigeo, “MDP-Based Budget Allocation for Efficient Cooperative Task Solving,” Chinese Journal of Electronics, vol. 26, no. 5, pp. 966-972, 2017, doi: 10.1049/cje.2017.08.001

Citation:

JIANG Huan, ZUO Min, MATSUBARA Shigeo, “MDP-Based Budget Allocation for Efficient Cooperative Task Solving,” Chinese Journal of Electronics, vol. 26, no. 5, pp. 966-972, 2017, doi: 10.1049/cje.2017.08.001

Citation:

PDF( 376 KB)

MDP-Based Budget Allocation for Efficient Cooperative Task Solving

doi: 10.1049/cje.2017.08.001

1.
School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China;
2.
Department of Social Informatics, Kyoto University, Kyoto 606-8501, Japan

Funds: This work is supported by the National Science and Technology Pillar Program (No.2015BAK36B04), the Young Teacher Program of BTBU (No.QNJJ2016-20), and a Grant-in-Aid for Scientific Research (S) from Japan Society for the Promotion of Science (JSPS) (No.24220002).

More Information

Corresponding author: ZUO Min (corresponding author) was born in 1973. He received the Ph.D. degree in computer application from University of Science and Technology Beijing. He is now a professor and a master supervisor at Beijing Technology and Business University. His research interests include intelligent management and artificial intelligence. (Email:zuomin1234@163.com)
Received Date: 2016-05-10
Rev Recd Date: 2017-01-14
Publish Date: 2017-09-10

Abstract

Abstract

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.
- Budget allocation,
- Markov decision processes (MDPs),
- Cooperative task solving,
- Task quality optimization,
- Crowdsourcing

FullText(HTML)

References(21)

References

M.S. Bernstein, G. Little, R.C. Miller, et al., "Soylent:A word processor with a crowd inside", Commun. ACM, Vol.58, No.8, pp.85-94, July 2015.

A. Kulkarni, M. Can and B. Hartmann, "Collaboratively crowdsourcing workflows with turkomatic", Proc. of the ACM 2012 Conference on Computer Supported Cooperative Work, Seattle, Washington, USA, pp.1003-1012, 2012.

A.P. Kulkarni, M. Can and B. Hartmann, "Turkomatic:Automatic recursive task and workflow design for mechanical turk",CHI'11 Extended Abstracts on Human Factors in Computing Systems, Vancouver, BC, Canada, pp.2053-2058, 2011.

P.G. Ipeirotis, "Analyzing the amazon mechanical turk marketplace", XRDS:Crossroads, The ACM Magazine for Students, Vol.17, No.2, pp.16-21, 2010.

C.J. Ho and J.W. Vaughan, "Online task assignment in crowdsourcing markets", Proc. of the 26th AAAI Conference on Artificial Intelligence, Toronto, Canada, pp.45-51, 2012.

D. Liu, C. Huang, W.B. Wang, et al., "Resource allocation in high energy-efficient cooperative spectrum sharing communication networks", Chinese Journal of Electronics, Vol.25, No.4, pp.768-773, 2016.

A. Azaria, Y. Aumann and S. Kraus, "Automated strategies for determining rewards for human work", Proc. of the 26th AAAI Conference on Artificial Intelligence, Toronto, Canada, pp.1514-1521, 2012.

D.R. Karger, S. Oh and D. Shah, "Budget-optimal task allocation for reliable crowdsourcing systems", Operations Research, Vol.62, No.1, pp.1-24, 2014.

L. Tran-Thanh, S. Stein, A. Rogers, et al., "Efficient crowdsourcing of unknown experts using bounded multi-armed bandits", Proc. of the 20th European Conference on Artificial Intelligence, Montpellier, France, pp.768-773, 2014.

L. Tran-Thanh, M. Venanzi, A. Rogers, et al., "Efficient budget allocation with accuracy guarantees for crowdsourcing classification tasks", Proc. of the 2013 International Conference on Autonomous Agents and Multiagent Systems, Saint Paul, Minnesota, USA, pp.901-908, 2013.

L. Tran-Thanh, T.D. Huynh, A. Rosenfeld, et al., "Budgetfix:Budget limited crowdsourcing for interdependent task allocation with quality guarantees", Proc. of the 2014 International Conference on Autonomous Agents and Multiagent Systems, Paris, France, pp.477-484, 2014.

X.L. Yang, Y.H. Tong, J.J. Yang, et al., "Improved IAMB with expanded Markov blanket for high-dimensional time series prediction", Chinese Journal of Electronics, Vol.25, No.2, pp.264-269, 2016.

P. Dai, C.H. Lin, D.S. Weld, et al., "POMDP-based control of workflows for crowdsourcing", Artificial Intelligence, Vol.202, No.9, pp.52-85, 2013.

F. Liu, C.J. Wang and B. Luo, "A probability-based value iteration on optimal policy algorithm for POMDP", Acta Electronica Sinica, Vol.44, No.5, pp.1078-1084, 2016. (in Chinese)

J. Wang and P. Ipeirotis, "Quality-based pricing for crowdsourced workers", NYU Working paper No.2451/31833, available at SSRN:http://ssrn.com/abstract=2283000, 2013.

H. Jiang and S. Matsubara, "Efficient task decomposition in crowdsourcing", PRIMA 2014:Principles and Practice of Multi-Agent Systems, Vol.8861, pp.65-73, 2014.

M.L. Cheng and Y. Han, "A modified cobb-douglas production function model and its application", IMA Journal of Management Mathematics, Vol.25, No.3, pp.948-950, 2014.

L. Kocsis and C. Szepesvári. "Bandit based monte-carlo planning", Machine Learning:ECML 2006, pp.282-293, 2006.

A. Dwarakanath, N.C. Shrikanth, K. Abhinav, et al., "Trustworthiness in enterprise crowdsourcing:A taxonomy and evidence from data", Proc. of the 38th International Conference on Software Engineering Companion, Austin, Texas, USA, pp.41-50, 2016.

A. Kittur, B. Smus, S. Khamkar, et al., "Crowdforge:Crowdsourcing complex work", Proc. of the 24th Annual ACM Symposium on User Interface Software and Technology, New York, NY, USA, pp.43-52, 2011.

J. Noronha, E. Hysen, H.Q. Zhang, et al., "Platemate:Crowdsourcing nutritional analysis from food photographs", Proc. of the 24th Annual ACM Symposium on User Interface Software and Technology, New York, NY, USA, pp.1-12, 2011.

Relative Articles

Supplements(0)

Cited By

Proportional views