{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T11:39:20Z","timestamp":1763552360856,"version":"3.45.0"},"reference-count":38,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T00:00:00Z","timestamp":1763337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100013209","name":"European Union\u2014NextGenerationEU","doi-asserted-by":"publisher","award":["15430"],"award-info":[{"award-number":["15430"]}],"id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Identifying effective coalitions of agents for task execution within large multiagent settings is a challenging endeavor. The problem is exacerbated by the presence of coalitional value uncertainty, which is due to uncertainty regarding the values of synergies among the different collaborating agent types. Intuitively, in such environments, a hypergraph can be used to concisely represent coalition\u2013task pairs in the form of hyperedges, along with their associated rewards. Therefore, this paper proposes harnessing the power of Hypergraph Neural Networks (HGNNs) that fit generic hypergraph-structured historical representations of coalitional task executions to learn the unknown values of coalitional configurations undertaking the tasks. However, the fitted model by itself cannot be used to provide suggestions on which coalitions to form; it can only be queried for the values of given coalition\u2013task configurations. To actually provide coalitional suggestions, this work relies on informed search approaches that incorporate the output of the HGNN as an indicator of the quality of the proposed coalition configurations. The resulting approach is illustrated, via simulation results, to be able to effectively capture the uncertain values of multiagent synergies and thus suggest highly rewarding coalitional configurations. Specifically, the proposed novel hybrid approach can outperform competing baseline approaches and achieve close to 80% performance of the theoretical maximum in this setting.<\/jats:p>","DOI":"10.3390\/a18110724","type":"journal-article","created":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T11:17:27Z","timestamp":1763551047000},"page":"724","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hypergraph Neural Networks for Coalition Formation Under Uncertainty"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8236-1843","authenticated-orcid":false,"given":"Gerasimos","family":"Koresis","sequence":"first","affiliation":[{"name":"School of Electrical and Computer Engineering, Technical University of Crete, 73100 Chania, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0785-4036","authenticated-orcid":false,"given":"Charilaos","family":"Akasiadis","sequence":"additional","affiliation":[{"name":"School of Electrical and Computer Engineering, Technical University of Crete, 73100 Chania, Greece"},{"name":"Institute of Informatics and Telecommunications, NCSR \u2018Demokritos\u2019, 15341 Aghia Paraskevi, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0716-2972","authenticated-orcid":false,"given":"Georgios","family":"Chalkiadakis","sequence":"additional","affiliation":[{"name":"School of Electrical and Computer Engineering, Technical University of Crete, 73100 Chania, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2025,11,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0004-3702(98)00045-9","article-title":"Methods for task allocation via agent coalition formation","volume":"101","author":"Shehory","year":"1998","journal-title":"Artif. Intell."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/s10458-010-9157-y","article-title":"Sequentially optimal repeated coalition formation under uncertainty","volume":"24","author":"Chalkiadakis","year":"2012","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"ref_3","unstructured":"Chalkiadakis, G., and Boutilier, C. (2004, January 19\u201323). Bayesian reinforcement learning for coalition formation under uncertainty. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004), New York, NY, USA."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yokoo, M., Conitzer, V., Sandholm, T., Ohta, N., and Iwasaki, A. (September, January 31). A new solution concept for coalitional games in open anonymous environments. Proceedings of the New Frontiers in Artificial Intelligence\u2014Joint JSAI 2005 Workshop Post-Proceedings, Ulm, Germany. LNCS.","DOI":"10.1007\/11780496_6"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.aiopen.2021.01.001","article-title":"Graph neural networks: A review of methods and applications","volume":"1","author":"Zhou","year":"2020","journal-title":"AI Open"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Liu, Y., Wang, W., Hu, Y., Hao, J., Chen, X., and Gao, Y. (2020, January 7\u201312). Multi-agent game abstraction via graph attention neural network. Proceedings of the AAAI Conference on Artificial Intelligence, New York, NY, USA.","DOI":"10.1609\/aaai.v34i05.6211"},{"key":"ref_7","first-page":"3558","article-title":"Hypergraph Neural Networks","volume":"33","author":"Feng","year":"2019","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_8","unstructured":"Aponte, R., Rossi, R.A., Guo, S., Hoffswell, J., Lipka, N., Xiao, C., Chan, G., Koh, E., and Ahmed, N. (2022). A hypergraph neural network framework for learning hyperedge-dependent node embeddings. arXiv."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., and Wooldridge, M. (2011). Computational Aspects of Cooperative Game Theory, Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-01558-8"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1038\/nature14236","article-title":"Human-level control through deep reinforcement learning","volume":"518","author":"Mnih","year":"2015","journal-title":"Nature"},{"key":"ref_11","unstructured":"Li, H., Zhao, Y., Mao, Z., Qin, Y., Xiao, Z., Feng, J., Gu, Y., Ju, W., Luo, X., and Zhang, M. (2024). Graph Neural Networks in Intelligent Transportation Systems: Advances, Applications and Trends. arXiv."},{"key":"ref_12","first-page":"95","article-title":"Intelligent logistics management robot path planning algorithm integrating transformer and gcn network","volume":"2","author":"Luo","year":"2024","journal-title":"IECE Trans. Internet Things"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Sadeghi, M., and Erol-Kantarci, M. (2021, January 13\u201315). Deep Reinforcement Learning Based Coalition Formation for Energy Trading in Smart Grid. Proceedings of the 2021 IEEE 4th 5G World Forum (5GWF), Montreal, QC, Canada.","DOI":"10.1109\/5GWF52925.2021.00042"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G. (2007). A Bayesian Approach to Multiagent Reinforcement Learning and Coalition Formation Under Uncertainty. [Ph.D. Thesis, University of Toronto].","DOI":"10.1145\/1329125.1329203"},{"key":"ref_15","unstructured":"Gebrekidan, T.Z., Stein, S., and Norman, T.J. (2024, January 6\u201310). Deep Reinforcement Learning with Coalition Action Selection for Online Combinatorial Resource Allocation with Arbitrary Action Space. Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, Auckland, New Zealand. AAMAS \u201924."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Dai, W., Bidwai, A., and Sartoretti, G. (2024, January 13\u201317). Dynamic Coalition Formation and Routing for Multirobot Task Allocation via Reinforcement Learning. Proceedings of the 2024 IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan.","DOI":"10.1109\/ICRA57147.2024.10611244"},{"key":"ref_17","unstructured":"Koresis, G., Plataniotis, S., Bakopoulos, L., Akasiadis, C., and Chalkiadakis, G. (2025, January 3\u20135). Privacy-Aware Deep RL for Sequential Coalition Formation Decisions under Uncertainty. Proceedings of the 37th International Conference on Tools with Artificial Intelligence (ICTAI-2025), Athens, Greece."},{"key":"ref_18","unstructured":"Dieckmann, T., and Schwalbe, U. (1998). Dynamic Coalition Formation and the Core, National University of Ireland."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Markakis, E., and Boutilier, C. (2007, January 14\u201318). Coalition formation under uncertainty: Bargaining equilibria and the Bayesian core stability concept. Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-07), Honolulu, HI, USA.","DOI":"10.1145\/1329125.1329203"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Christianos, F., and Chalkiadakis, G. (2016). Employing hypergraphs for efficient coalition formation with application to the V2G problem. ECAI 2016, IOS Press.","DOI":"10.3233\/978-1-61499-672-9-1604"},{"key":"ref_21","unstructured":"Egan, M., and Jakob, M. (2014). A profit-aware negotiation mechanism for on-demand transport services. ECAI-14, IOS Press."},{"key":"ref_22","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":"Service","year":"2011","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Sharaf, M.A., and Alghamdi, T.G. (2025). Balanced Teams Formation using Hybrid Graph Convolution Networks and MILP. Appl. Sci., 15.","DOI":"10.20944\/preprints202501.0931.v1"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Kim, S., Lee, S.Y., Gao, Y., Antelmi, A., Polato, M., and Shin, K. (2024, January 25\u201329). A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York, NY, USA. KDD \u201924.","DOI":"10.1145\/3637528.3671457"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Criado Pacheco, N., Carrascosa, C., Osman, N., and Juli\u00e1n Inglada, V. (2017). Efficient Multi-criteria Coalition Formation Using Hypergraphs (with Application to the V2G Problem). Multi-Agent Systems and Agreement Technologies, Springer.","DOI":"10.1007\/978-3-319-59294-7"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"4599","DOI":"10.1109\/TNNLS.2024.3368111","article-title":"Formulating and representing multiagent systems with hypergraphs","volume":"36","author":"Yu","year":"2024","journal-title":"IEEE Trans. Neural Networks Learn. Syst."},{"key":"ref_27","unstructured":"(2025, January 24\u201328). Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding. Proceedings of the Submitted to The Fourteenth International Conference on Learning Representations, Singapore."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Wang, W., Bera, A., and Min, B.C. (2025, January 19\u201323). Hypergraph-Based Coordinated Task Allocation and Socially-Aware Navigation for Multi-Robot Systems. Proceedings of the 2025 IEEE International Conference on Robotics and Automation (ICRA), Atlanta, GA, USA.","DOI":"10.1109\/ICRA55743.2025.11128092"},{"key":"ref_29","unstructured":"Veloso, M.M. (2007, January 6-12). Coalitional Bargaining with Agent Type Uncertainty. Proceedings of the IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India."},{"key":"ref_30","unstructured":"Shrot, T., Aumann, Y., and Kraus, S. (2010, January 10\u201314). On agent types in coalition formation problems. Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1-Volume 1. Citeseer, Toronto, ON, Canada."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/978-1-4684-8941-5_21","article-title":"Genetic algorithms and adaptation","volume":"16","author":"Holland","year":"1984","journal-title":"Adapt. Control -Ill-Defin. Syst."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Holland, J.H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, MIT Press.","DOI":"10.7551\/mitpress\/1090.001.0001"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Yuan, Y., Wang, W., Coghill, G.M., and Pang, W. (2021). A novel genetic algorithm with hierarchical evaluation strategy for hyperparameter optimisation of graph neural networks. arXiv.","DOI":"10.1109\/CEC45853.2021.9504717"},{"key":"ref_35","unstructured":"Ouyang, K., and Fu, S. (2024). Graph Neural Networks Are Evolutionary Algorithms. arXiv."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/S0165-1889(00)00038-5","article-title":"The importance of the number of different agents in a heterogeneous asset-pricing model","volume":"25","year":"2001","journal-title":"J. Econ. Dyn. Control"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1287\/mnsc.1050.0502","article-title":"Optimal mechanisms with finite agent types","volume":"52","author":"Lovejoy","year":"2006","journal-title":"Manag. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"107637","DOI":"10.1016\/j.patcog.2020.107637","article-title":"Hypergraph convolution and hypergraph attention","volume":"110","author":"Bai","year":"2021","journal-title":"Pattern Recognit."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/11\/724\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T11:30:58Z","timestamp":1763551858000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/11\/724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,17]]},"references-count":38,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2025,11]]}},"alternative-id":["a18110724"],"URL":"https:\/\/doi.org\/10.3390\/a18110724","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,17]]}}}