BOSS: A Bi-directional Search Technique for Optimal Coalition Structure Generation with Minimal Overlapping (Student Abstract)

Authors

  • Narayan Changder National Institute of Technology, Durgapur
  • Samir Aknine LIRIS, Lyon 1 University, France.
  • Sarvapali D. Ramchurn University of Southampton, UK.
  • Animesh Dutta National Institute of Technology, Durgapur

DOI:

https://doi.org/10.1609/aaai.v35i18.17879

Keywords:

Multiagent Systems, Optimization, Game Theory, Coalition Structure Generation, Coalition Formation

Abstract

In this paper, we focus on the Coalition Structure Generation (CSG) problem, which involves finding exhaustive and disjoint partitions of agents such that the efficiency of the entire system is optimized. We propose an efficient hybrid algorithm for optimal coalition structure generation called BOSS. When compared to the state-of-the-art, BOSS is shown to perform better by up to 33.63% on benchmark inputs. The maximum time gain by BOSS is 3392 seconds for 27 agents.
AAAI-21 Proceedings Cover

Downloads

Published

2021-05-18

How to Cite

Changder, N., Aknine, S., Ramchurn, S. D., & Dutta, A. (2021). BOSS: A Bi-directional Search Technique for Optimal Coalition Structure Generation with Minimal Overlapping (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 35(18), 15765-15766. https://doi.org/10.1609/aaai.v35i18.17879

Issue

Vol. 35 No. 18: AAAI-21 Student Papers and Demonstrations

Section

AAAI Student Abstract and Poster Program