{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:58:53Z","timestamp":1760241533881,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,5,5]],"date-time":"2018-05-05T00:00:00Z","timestamp":1525478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper focuses on the rational distribution of task utilities in coalition skill games, which is a restricted form of coalition game, where each service agent has a set of skills and each task agent needs a set of skills in order to be completed. These two types of agents are assumed to be self-interested. Given the task selection strategy of service agents, the utility distribution strategies of task agents play an important role in improving their individual revenues and system total revenue. The problem that needs to be resolved is how to design the task selection strategies of the service agents and the utility distribution strategies of the task agents to make the self-interested decisions improve the system whole performance. However, to the best of our knowledge, this problem has been the topic of very few studies and has not been properly addressed. To address this problem, a task allocation algorithm for self-interested agents in a coalition skill game is proposed, it distributes the utilities of tasks to the needed skills according to the powers of the service agents that possess the corresponding skills. The final simulation results verify the effectiveness of the algorithm.<\/jats:p>","DOI":"10.3390\/a11050064","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T03:12:21Z","timestamp":1525662741000},"page":"64","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Utility Distribution Strategy of the Task Agents in Coalition Skill Games"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0849-5346","authenticated-orcid":false,"given":"Ming Lan","family":"Fu","sequence":"first","affiliation":[{"name":"School of Computers and Information, Hefei University of Technology, Hefei 230009, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computers and Information, Hefei University of Technology, Hefei 230009, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bao Fu","family":"Fang","sequence":"additional","affiliation":[{"name":"School of Computers and Information, Hefei University of Technology, Hefei 230009, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,5]]},"reference":[{"key":"ref_1","unstructured":"Bachrach, Y., and Rosenschein, J.S. (2008, January 12\u201316). Coalitional skill games. Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril, Portugal."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2013.07.005","article-title":"Computing cooperative solution concepts in coalitional skill games","volume":"204","author":"Bachrach","year":"2013","journal-title":"Artif. Intell."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Bachrach, Y., Meir, R., Jung, K., and Kohli, P. (2010, January 11). Coalitional Structure Generation in Skill Games. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), Atlanta, GA, USA.","DOI":"10.1609\/aaai.v24i1.7620"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.artint.2015.08.004","article-title":"Coalition structure generation: A survey","volume":"229","author":"Rahwan","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/s10846-007-9150-0","article-title":"Coalition formation: From software agents to robots","volume":"50","author":"Vig","year":"2007","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10458-010-9123-8","article-title":"Coalition formation for task allocation: Theory and algorithms","volume":"22","author":"Adams","year":"2011","journal-title":"Auton. Agents Multi Agent Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1017\/S0263574713000192","article-title":"Game theory-based negotiation for multiple robots task allocation","volume":"31","author":"Cui","year":"2013","journal-title":"Robotica"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1177\/0278364904045564","article-title":"A formal analysis and taxonomy of task allocation in multi-robot systems","volume":"23","author":"Gerkey","year":"2004","journal-title":"Int. J. Robot. Res."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Swenson, B., Kar, S., and Xavier, J. (arXiv, 2015). A computationally efficient implementation of fictitious play for large-scale games, arXiv.","DOI":"10.1109\/EUSIPCO.2015.7362542"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1393","DOI":"10.1109\/TSMCB.2009.2017273","article-title":"Cooperative control and potential games","volume":"39","author":"Marden","year":"2009","journal-title":"IEEE Trans. Syst. Man Cybern. Part B"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Marden, J.R., Arslan, G., and Shamma, J.S. (2007, January 14\u201318). Regret based dynamics: Convergence in weakly acyclic games. Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, Honolulu, Hawaii.","DOI":"10.1145\/1329125.1329175"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Genin, T., and Aknine, S. (September, January 31). Coalition formation strategies for self-interested agents in task oriented domains. Proceedings of the 2010 IEEE\/WIC\/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), Toronto, ON, Canada.","DOI":"10.1109\/WI-IAT.2010.275"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"e4178","DOI":"10.1002\/cpe.4178","article-title":"An intelligent agent-based method for task allocation in competitive cloud environments","volume":"30","author":"Kong","year":"2017","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_14","unstructured":"Barile, F., Rossi, A., Staffa, M., Napoli, C.D., and Rossi, S.A. (2015, January 17\u201319). Market Mechanism for QoS-aware Multi-Robot Task Allocation. Proceedings of the 16th Workshop \u201cFrom Objects to Agents\u201d (WOA15), Naples, Italy."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1093\/comjnl\/bxv061","article-title":"An auction-based approach for group task allocation in an open network environment","volume":"59","author":"Kong","year":"2016","journal-title":"Comput. J."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Service, T.C., Sen, S.D., and Adams, J.A. (2014, January 5\u20138). A simultaneous descending auction for task allocation. Proceedings of the 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), San Dieg, CA, USA.","DOI":"10.1109\/SMC.2014.6973937"},{"key":"ref_17","unstructured":"Lin, L., and Zheng, Z. (2005, January 18\u201322). Combinatorial bids based multi-robot task allocation method. Proceedings of the IEEE International Conference on Robotics and Automation, Barcelona, Spain."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1007\/s11390-016-1688-5","article-title":"Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games","volume":"31","author":"Liu","year":"2016","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_19","unstructured":"Aziz, H., and De Keijzer, B. (2011, January 2\u20136). Complexity of coalition structure generation. Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, TaiPei, Taiwan."},{"key":"ref_20","unstructured":"Tran-Thanh, L., Nguyen, T.D., Rahwan, T., Rogers, A.R., and Jennings, N. (2013, January 3\u20139). An efficient vector-based representation for coalitional games. Proceedings of the IJCAI\u201913, Twenty-Third International Joint Conference on Artificial Intelligence, Beijing, China."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0377-2217(96)00170-1","article-title":"PSPLIB\u2014A project scheduling problem library: OR software-ORSEP operations research software exchange program","volume":"96","author":"Kolisch","year":"1997","journal-title":"Eur. J. Op. Res."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Myszkowski, P.B., Skowronski, M.E., and Sikora, K. (2015, January 13\u201316). A new benchmark dataset for Multi-Skill Resource-Constrained Project Scheduling Problem. Proceedings of the 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), Lodz, Poland.","DOI":"10.15439\/2015F273"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"3599","DOI":"10.1007\/s00500-014-1455-x","article-title":"Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem","volume":"19","author":"Myszkowski","year":"2015","journal-title":"Soft Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1061\/(ASCE)0733-9364(2000)126:6(414)","article-title":"Algorithm for scheduling with multiskilled constrained resources","volume":"126","author":"Hegazy","year":"2000","journal-title":"J. Constr. Eng. Manag."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Gaspar-Cunha, A., Takahashi, R., Schaefer, G., and Costa, L. (2011). On the multi-mode, multi-skill resource constrained project scheduling problem\u2014A software application. Soft Computing in Industrial Applications, Springer.","DOI":"10.1007\/978-3-642-20505-7"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/j.ijdrr.2017.06.010","article-title":"Agent-based task allocation under uncertainties in disaster environments: An approach to interval uncertainty","volume":"24","author":"Hooshangi","year":"2017","journal-title":"Int. J. Disaster Risk Reduct."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1109\/TRO.2006.878948","article-title":"Multi-robot coalition formation","volume":"22","author":"Vig","year":"2006","journal-title":"IEEE Trans. Robot."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"6486","DOI":"10.1016\/j.eswa.2010.11.097","article-title":"Balancing task allocation in multi-robot systems using K-means clustering and auction based mechanisms","volume":"38","author":"Elango","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_29","first-page":"121","article-title":"A group task allocation strategy in open and dynamic grid environments","volume":"Volume 638","author":"Fukuta","year":"2016","journal-title":"Recent Advances in Agent-based Complex Automated Negotiation. Studies in Computational Intelligence"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1080\/01691864.2013.805471","article-title":"Game-based pursuit evasion for nonholonomic wheeled mobile robots subject to wheel slips","volume":"27","author":"Tian","year":"2013","journal-title":"Adv. Robot."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ins.2013.06.039","article-title":"Stochastic finite-state systems in control theory","volume":"251","author":"Zadeh","year":"2013","journal-title":"Inf. Sci."},{"key":"ref_32","first-page":"261","article-title":"Simple strategies versus optimal schedules in multi-agent patrolling","volume":"Volume 9079","author":"Paschos","year":"2015","journal-title":"Algorithms and Complexity. CIAC 2015. Lecture Notes in Computer Science"},{"key":"ref_33","first-page":"1","article-title":"Game theory models for multi-robot patrolling of infrastructures","volume":"10","author":"Cerro","year":"2013","journal-title":"Int. J. Adv. Robot. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/64\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:03:25Z","timestamp":1760195005000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,5]]},"references-count":33,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["a11050064"],"URL":"https:\/\/doi.org\/10.3390\/a11050064","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,5,5]]}}}