Online Coalitional Skill Formation
Authors: 
Saar Cohen, Noa AgmonAuthors Info & Claims
Pages 494 - 503
Abstract
Efficiently allocating heterogeneous tasks to agents that arrive dynamically and have diverse skills is a central problem in multi-agent systems called online task allocation. In many cases, a single agent does not meet the skill levels required by a particular task, which incentivizes the agents to form coalitions for handling it. In this paper, we propose a new framework, termed as online coalitional skill formation (OCSF), for handling online task allocation via coalition formation, where tasks require different skills for being successfully fulfilled, and each agent has different levels at mastering each skill. The goal of the organizer is therefore to assign agents that arrive online to a coalition responsible for performing some task, so as to optimally approach the desired skill levels of all tasks. Focusing on the case in which the set of possible mastering levels for each skill is discrete, we suggest different assignment algorithms based on the knowledge the organizer has on the arriving agents. When agents arrive i.i.d. according to some unknown distribution, we propose a greedy and adaptive scheme that assigns an agent to a task, proving a tight bound on the system's performance. If the distribution is known, we devise a novel correlation to Constrained Markov Decision Processes whose goal is maximizing the rate at which agents are assigned to each task while respecting their requirements. We then construct a non-adaptive approach that terminates when all the tasks' requirements are met. Finally, if the distribution is unknown, we provide two algorithms that learn it online. We have fully implemented the algorithms, showing that in many cases a higher diversity in skills may yield poor assignments.
References
[1]
Shipra Agrawal and Nikhil Devanur. 2016. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, Vol. 29 (2016).
[2]
Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce. 18--35.
[3]
Eitan Altman. 1999. Constrained Markov Decision Processes. Vol. 7. CRC Press.
[4]
Sepehr Assadi, Justin Hsu, and Shahin Jabbari. 2015. Online assignment of heterogeneous tasks in crowdsourcing markets. In Third AAAI Conference on Human Computation and Crowdsourcing.
[5]
Peter Auer, Thomas Jaksch, and Ronald Ortner. 2008. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, Vol. 21 (2008).
[6]
Peter Bartlett and Ambuj Tewari. 2009. REGAL: a regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference. AUAI Press, 35--42.
[7]
Senjuti Basu Roy, Ioanna Lykourentzou, Saravanan Thirumuruganathan, Sihem Amer-Yahia, and Gautam Das. 2015. Task assignment optimization in knowledge-intensive crowdsourcing. The VLDB Journal, Vol. 24, 4 (2015), 467--491.
[8]
Xiaohui Bei, Shengxin Liu, Chung Keung Poon, and Hongao Wang. 2022. Candidate selections with proportional fairness constraints. Autonomous Agents and Multi-Agent Systems, Vol. 36, 1 (2022), 1--32.
[9]
Dimitri P Bertsekas. 1988. The auction algorithm: A distributed relaxation method for the assignment problem. Annals of operations research, Vol. 14, 1 (1988), 105--123.
[10]
Allan Borodin and Ran El-Yaniv. 1998. Online computation and competitive analysis. cambridge university press.
[11]
S BoydandL. 2004. Vandenberghe, convex optimization.
[12]
Alessandro Bozzon, Marco Brambilla, Stefano Ceri, Matteo Silvestri, and Giuliano Vesci. 2013. Choosing the right crowd: expert finding in social networks. In Proceedings of the 16th international conference on extending database technology. 637--648.
[13]
Markus Brill, Jean-Francc ois Laslier, and Piotr Skowron. 2018. Multiwinner approval rules as apportionment methods. Journal of Theoretical Politics, Vol. 30, 3 (2018), 358--382.
[14]
Saar Cohen and Noa Agmon. 2023 a. Online Coalitional Skill Formation. https://www.cs.biu.ac.il/ agmon/CohenAAMAS23Sup.pdf.
[15]
Saar Cohen and Noa Agmon. 2023 b. Online Coalitional Skill Formation. https://github.com/saarcohen30/ocsf.
[16]
Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. 2011. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Proceedings of the 12th ACM conference on Electronic commerce. 29--38.
[17]
Nikhil R Devanur, Balasubramanian Sivan, and Yossi Azar. 2012. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce. 388--404.
[18]
John P Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2018. Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. 318--326.
[19]
Virginie Do, Jamal Atif, Jérôme Lang, and Nicolas Usunier. 2021. Online Selection of Diverse Committees. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. International Joint Conferences on Artificial Intelligence Organization, 154--160.
[20]
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. 2020. Exploration-exploitation in constrained mdps. arXiv preprint arXiv:2003.02189 (2020).
[21]
Ju Fan, Guoliang Li, Beng Chin Ooi, Kian-lee Tan, and Jianhua Feng. 2015. iCrowd: An adaptive crowdsourcing framework. In Proceedings of the 2015 ACM SIGMOD international conference on management of data. 1015--1030.
[22]
Brian P Gerkey and Maja J Mataric. 2002. Sold!: Auction methods for multirobot coordination. IEEE transactions on robotics and automation, Vol. 18, 5 (2002), 758--768.
[23]
Brian P Gerkey and Maja J Matarić. 2004. A formal analysis and taxonomy of task allocation in multi-robot systems. The International journal of robotics research, Vol. 23, 9 (2004), 939--954.
[24]
Bin Guo, Yan Liu, Leye Wang, Victor OK Li, Jacqueline CK Lam, and Zhiwen Yu. 2018. Task allocation in spatial crowdsourcing: Current state and future directions. IEEE Internet of Things Journal, Vol. 5, 3 (2018), 1749--1764.
[25]
Kai Han, Chi Zhang, and Jun Luo. 2015. Taming the uncertainty: Budget limited robust crowdsensing through online learning. Ieee/acm transactions on networking, Vol. 24, 3 (2015), 1462--1475.
[26]
Umair Ul Hassan and Edward Curry. 2014. A multi-armed bandit approach to online spatial task assignment. In 2014 IEEE 11th Intl Conf on Ubiquitous Intelligence and Computing and 2014 IEEE 11th Intl Conf on Autonomic and Trusted Computing and 2014 IEEE 14th Intl Conf on Scalable Computing and Communications and Its Associated Workshops. IEEE, 212--219.
[27]
Umair Ul Hassan, Sean O'Riain, and Edward Curry. 2013. Effects of expertise assessment on the quality of task routing in human computation. In 2nd International Workshop on Social Media for Crowdsourcing and Human Computation (SoHuman 2013) 2. 1--10.
[28]
Danula Hettiachchi, Vassilis Kostakos, and Jorge Goncalves. 2022. A survey on task assignment in crowdsourcing. ACM Computing Surveys (CSUR), Vol. 55, 3 (2022), 1--35.
[29]
Chien-Ju Ho and Jennifer Vaughan. 2012. Online task assignment in crowdsourcing markets. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 26. 45--51.
[30]
Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi. 2015. Tight bounds for online vector scheduling. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 525--544.
[31]
Jiuchuan Jiang, Bo An, Yichuan Jiang, Donghui Lin, Zhan Bu, Jie Cao, and Zhifeng Hao. 2018. Understanding crowdsourcing systems from a multiagent perspective and approach. ACM Transactions on Autonomous and Adaptive Systems (TAAS), Vol. 13, 2 (2018), 1--32.
[32]
C Ronald Kube and Hong Zhang. 1993. Collective robotics: From social insects to robots. Adaptive behavior, Vol. 2, 2 (1993), 189--218.
[33]
Harold W Kuhn. 2005. The Hungarian method for the assignment problem. Naval Research Logistics (NRL), Vol. 52, 1 (2005), 7--21.
[34]
Jérôme Lang and Piotr Skowron. 2018. Multi-attribute proportional representation. Artificial Intelligence, Vol. 263 (2018), 74--106.
[35]
John Langford and Tong Zhang. 2007. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, Vol. 20, 1 (2007), 96--1.
[36]
Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara. 2011. Multi-robot assignment algorithm for tasks with set precedence constraints. In 2011 IEEE International Conference on Robotics and Automation. IEEE, 2526--2533.
[37]
Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. 2012. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, Vol. 37, 4 (2012), 559--573.
[38]
Panagiotis Mavridis, David Gross-Amblard, and Zoltán Miklós. 2016. Using hierarchical skills for optimized task assignment in knowledge-intensive crowdsourcing. In Proceedings of the 25th International Conference on World Wide Web. 843--853.
[39]
Sabrina Klos née Müller, Cem Tekin, Mihaela van der Schaar, and Anja Klein. 2018. Context-aware hierarchical online learning for performance maximization in mobile crowdsourcing. IEEE/ACM Transactions on Networking, Vol. 26, 3 (2018), 1334--1347.
[40]
Lynne E Parker. 1998. ALLIANCE: An architecture for fault tolerant multirobot cooperation. IEEE transactions on robotics and automation, Vol. 14, 2 (1998), 220--240.
[41]
Chenxi Qiu, Anna C Squicciarini, Barbara Carminati, James Caverlee, and Dev Rishi Khare. 2016. CrowdSelect: increasing accuracy of crowdsourcing tasks through behavior prediction and user selection. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. 539--548.
[42]
Aviv Rosenberg and Yishay Mansour. 2019. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning. PMLR, 5478--5486.
[43]
Onn Shehory and Sarit Kraus. 1998. Methods for task allocation via agent coalition formation. Artificial intelligence, Vol. 101, 1--2 (1998), 165--200.
[44]
Rahul Singh, Abhishek Gupta, and Ness B Shroff. 2020. Learning in Markov decision processes under constraints. arXiv preprint arXiv:2002.12435 (2020).
[45]
Adish Singla and Andreas Krause. 2013. Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In Proceedings of the 22nd international conference on World Wide Web. 1167--1178.
[46]
Aleksandrs Slivkins and Jennifer Wortman Vaughan. 2014. Online decision making in crowdsourcing markets: Theoretical challenges. ACM SIGecom Exchanges, Vol. 12, 2 (2014), 4--23.
[47]
Ashwin Subramanian, G Sai Kanth, Sharayu Moharir, and Rahul Vaze. 2015. Online incentive mechanism design for smartphone crowd-sourcing. In 2015 13th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt). IEEE, 403--410.
[48]
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. 2022. Online Task Assignment Problems with Reusable Resources., Vol. 36, 1 (2022), 5199--5207.
[49]
Feilong Tang. 2020. Optimal Complex Task Assignment in Service Crowdsourcing. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20. International Joint Conferences on Artificial Intelligence Organization, 1563--1569.
[50]
Hien To, Gabriel Ghinita, Liyue Fan, and Cyrus Shahabi. 2016. Differentially private location protection for worker datasets in spatial crowdsourcing. IEEE Transactions on Mobile Computing, Vol. 16, 4 (2016), 934--949.
[51]
Elio Tuci, Muhanad HM Alkilabi, and Otar Akanyeti. 2018. Cooperative object transport in multi-robot systems: A review of the state-of-the-art. Frontiers in Robotics and AI, Vol. 5 (2018), 59.
[52]
Lovekesh Vig and Julie A Adams. 2006. Market-based multi-robot coalition formation. In Distributed Autonomous Robotic Systems 7. Springer, 227--236.
[53]
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. 2003. Inequalities for the L1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep (2003).
[54]
Andrew K Whitten, Han-Lim Choi, Luke B Johnson, and Jonathan P How. 2011. Decentralized task allocation with coupled constraints in complex missions. In Proceedings of the 2011 American Control Conference. IEEE, 1642--1649.
[55]
Dong Zhao, Xiang-Yang Li, and Huadong Ma. 2014a. How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications. IEEE, 1213--1221.
[56]
Qingwen Zhao, Yanmin Zhu, Hongzi Zhu, Jian Cao, Guangtao Xue, and Bo Li. 2014b. Fair energy-efficient sensing task allocation in participatory sensing with smartphones. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications. IEEE, 1366--1374.
[57]
Liyuan Zheng and Lillian Ratliff. 2020. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control. PMLR, 620--629.
[58]
Yudian Zheng, Jiannan Wang, Guoliang Li, Reynold Cheng, and Jianhua Feng. 2015. QASCA: A quality-aware task assignment system for crowdsourcing applications. In Proceedings of the 2015 ACM SIGMOD international conference on management of data. 1031--1046.
Index Terms
- Online Coalitional Skill Formation
Recommendations
Coalition Formation: From Software Agents to Robots
A problem that has recently attracted the attention of the research community is the autonomous formation of robot teams to perform complex multi-robot tasks. The corresponding problem for software agents is also known in the multi-agent community as ...
Methods for task allocation via agent coalition formation
Task execution in multi-agent environments may require cooperation among agents. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents that will perform the ...
Multi-robot coalition formation
As the community strives towards autonomous multi-robot systems, there is a need for these systems to autonomously form coalitions to complete assigned missions. Numerous coalition formation algorithms have been proposed in the software agent ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2023
3131 pages
ISBN:9781450394321
- General Chairs:
- Noa Agmon,
- Bo An,
- Program Chairs:
- Alessandro Ricci,
- William Yeoh
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 30 May 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Israel Science Foundation (ISF)
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 29 - June 2, 2023
London, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 45Total Downloads
- Downloads (Last 12 months)19
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in