Abstract
We consider a generalization of the task allocation problem. A finite number of human resources are dynamically available to try to accomplish tasks. For each assigned task, the resource can fail or complete it correctly. Each task must be completed a number of times, and each resource is available for an independent number of tasks. Resources, tasks, and the probability of a correct response are modeled using Item Response Theory. The task parameters are known, while the ability of the resources must be learned through the interaction between resources and tasks. We formalize such a problem and propose an algorithm combining shadow test replanning to plan under uncertain knowledge, aiming to allocate resources optimally to tasks while maximizing the number of completed tasks. In our simulations, we consider three scenarios that depend on knowledge of the ability of the resources to solve the tasks. Results are presented using real data from the Mathematics and its Technologies test of the Brazilian Baccalaureate Examination (ENEM).
This study was partially supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) - Finance Code 001, by the São Paulo Research Foundation (FAPESP) grant #2021/06867-2 and the Center for Artificial Intelligence (C4AI-USP), with support by FAPESP (grant #2019/07665-4) and by the IBM Corporation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Abrams, D.S., Yoon, A.H.: The luck of the draw: using random case assignment to investigate attorney ability. Univ. Chic. Law Rev. 74(4), 1145–1177 (2007). http://www.jstor.org/stable/20141859
Ali, I., Chang, R.Y., Hsu, C.H.: SOQAS: distributively finding high-quality answerers in dynamic social networks. IEEE Access 6, 55074–55089 (2018)
Aydin, B.I., Yilmaz, Y.S., Demirbas, M.: A crowdsourced “who wants to be a millionaire?’’ player. Concurr. Comput. Pract. Exp. 33(8), e4168 (2017)
Ben Rjab, A., Kharoune, M., Miklos, Z., Martin, A.: Characterization of experts in crowdsourcing platforms. In: Vejnarová, J., Kratochvíl, V. (eds.) BELIEF 2016. LNCS (LNAI), vol. 9861, pp. 97–104. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45559-4_10
Bezerra, C.M., Araújo, D.R., Macario, V.: Allocation of volunteers in non-governmental organizations aided by non-supervised learning. In: 2016 5th Brazilian Conference on Intelligent Systems (BRACIS), pp. 223–228 (2016)
Birnbaum, A.: Some latent trait models and their use in inferring an examinee’s ability. In: Lord, F.M., Novick, M.R. (eds.) Statistical Theories of Mental Test Scores, Reading, Charlotte, NC, pp. 397–479. Addison-Wesley (1968)
Bock, R.D., Aitkin, M.: Marginal maximum likelihood estimation of item parameters: application of an EM algorithm. Psychometrika 46(4), 443–459 (1981)
Difallah, D.E., Demartini, G., Cudré-Mauroux, P.: Pick-a-crowd: tell me what you like, and i’ll tell you what to do: A crowdsourcing platform for personalized human intelligence task assignment based on social networks. In: WWW 2013 - Proceedings of the 22nd International Conference on World Wide Web, pp. 367–377 (2013)
Ekman, P., Bellevik, S., Dimitrakakis, C., Tossou, A.: Learning to match. In: 1st International Workshop on Value-Aware and Multistakeholder Recommendation (2017)
Fan, J., Li, G., Ooi, B.C., Tan, K.l., Feng, J.: iCrowd: an adaptive crowdsourcing framework. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1015–1030. Association for Computing Machinery (2015)
Horowitz, D., Kamvar, S.D.: The anatomy of a large-scale social search engine. In: Proceedings of the 19th International Conference on World Wide Web - WWW 2010, Raleigh, North Carolina, USA, p. 431. ACM Press (2010)
Huang, Y.M., Lin, Y.T., Cheng, S.C.: An adaptive testing system for supporting versatile educational assessment. Comput. Educ. 52(1), 53–67 (2009)
INEP: Instituto nacional de educação e pesquisas educacionais anísio teixeira - entenda sua nota no enem (2012). http://download.inep.gov.br/educacao_basica/enem/guia_participante/2013/guia_do_participante_notas.pdf. Accessed 19 June 2021
Krstikj, A., Esparza, C.R.M.G., Mora-Vargas, J., Escobar, H.L.: Volunteers in lockdowns: decision support tool for allocation of volunteers during a lockdown. In: Regis-Hernández, F., Mora-Vargas, J., Sánchez-Partida, D., Ruiz, A. (eds.) Humanitarian Logistics from the Disaster Risk Reduction Perspective: Theory and Applications, pp. 429–446. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-90877-5_15
Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. (NRL) 2(1), 83–97 (1955)
Benedetto, L., Cappelli, A., Turrin, R., Cremonesi, P.: R2DE: a NLP approach to estimating IRT parameters of newly generated questions. In: Proceedings of the 10th International Conference on Learning Analytics and Knowledge (2020)
van der Linden, W.J.: Constrained adaptive testing with shadow tests. In: van der Linden, W.J., Glas, G.A. (eds.) Computerized Adaptive Testing: Theory and Practice, New York, Boston, Dordrecht, London, Moscow, pp. 27–52. Kluwer Academic Publishers (2000)
van der Linden, W.J., Jiang, B.: A shadow-test approach to adaptive item calibration. Psychometrika Soc. 85(2), 301–321 (2020)
van der Linden, W.J., Veldkamp, B.P.: Constraining item exposure in computerized adaptive testing with shadow tests. J. Educ. Behav. Stat. 29(3), 273–291 (2004)
Liu, C., Gao, X., Wu, F., Chen, G.: QITA: quality inference based task assignment in mobile crowdsensing. In: Pahl, C., Vukovic, M., Yin, J., Yu, Q. (eds.) ICSOC 2018. LNCS, vol. 11236, pp. 363–370. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03596-9_26
Mislevy, R.J.: Bayes modal estimation in item response models. Psychometric 51, 177–195 (1986)
Mitchell, S., Kean, A., Mason, A., O’Sullivan, M., Phillips, A., Peschiera, F.: Optimization with pulp (2009). https://coin-or.github.io/pulp/index.html. Accessed 20 June 2021
Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)
Mwamikazi, E., Fournier-Viger, P., Moghrabi, C., Barhoumi, A., Baudouin, R.: An adaptive questionnaire for automatic identification of learning styles. In: Ali, M., Pan, J.-S., Chen, S.-M., Horng, M.-F. (eds.) IEA/AIE 2014. LNCS (LNAI), vol. 8481, pp. 399–409. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07455-9_42
Negishi, K., Ito, H., Matsubara, M., Morishima, A.: A skill-based worksharing approach for microtask assignment. In: 2021 IEEE International Conference on Big Data (Big Data), pp. 3544–3547 (2021)
Paschoal, A.F.A., et al.: Pirá: A bilingual portuguese-english dataset for question-answering about the ocean. In: Demartini, G., Zuccon, G., Culpepper, J.S., Huang, Z., Tong, H. (eds.) CIKM 2021: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, 1–5 November 2021, pp. 4544–4553. ACM (2021). https://doi.org/10.1145/3459637.3482012
Shekhar, G., Bodkhe, S., Fernandes, K.: On-demand intelligent resource assessment and allocation system using NLP for project management. In: AMCIS 2020 Proceedings, vol. 8 (2020)
Tran-Thanh, L., Stein, S., Rogers, A., Jennings, N.: Efficient crowdsourcing of unknown experts using bounded multi-armed bandits. Artif. Intell. 214, 89–111 (2014)
Tu, J., Cheng, P., Chen, L.: Quality-assured synchronized task assignment in crowdsourcing. IEEE Trans. Knowl. Data Eng. 33(3), 1156–1168 (2021)
Veldkamp, B.P.: Bayesian item selection in constrained adaptive testing using shadow tests. Psicologica 31(1), 149–169 (2010)
Yu, D., Wang, Y., Zhou, Z.: Software crowdsourcing task allocation algorithm based on dynamic utility. IEEE Access 7, 33094–33106 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
da Silva, J., Peres, S., Cordeiro, D., Freire, V. (2023). Allocating Dynamic and Finite Resources to a Set of Known Tasks. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14195. Springer, Cham. https://doi.org/10.1007/978-3-031-45368-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-45368-7_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-45367-0
Online ISBN: 978-3-031-45368-7
eBook Packages: Computer ScienceComputer Science (R0)