ODSS: Efficient Hybridization for Optimal Coalition Structure Generation

Authors

  • Narayan Changder National Institute of Technology Durgapur
  • Samir Aknine Lyon 1 University
  • Sarvapali Ramchurn University of Southampton
  • Animesh Dutta National Institute of Technology Durgapur

DOI:

https://doi.org/10.1609/aaai.v34i05.6194

Abstract

Coalition Structure Generation (CSG) is an NP-complete problem that remains difficult to solve on account of its complexity. In this paper, we propose an efficient hybrid algorithm for optimal coalition structure generation called ODSS. ODSS is a hybrid version of two previously established algorithms IDP (Rahwan and Jennings 2008) and IP (Rahwan et al. 2009). ODSS minimizes the overlapping between IDP and IP by dividing the whole search space of CSG into two disjoint sets of subspaces and proposes a novel subspace shrinking technique to reduce the size of the subspace searched by IP with the help of IDP. When compared to the state-of-the-art against a wide variety of value distributions, ODSS is shown to perform better by up to 54.15% on benchmark inputs.

Downloads

Published

2020-04-03

How to Cite

Changder, N., Aknine, S., Ramchurn, S., & Dutta, A. (2020). ODSS: Efficient Hybridization for Optimal Coalition Structure Generation. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7079-7086. https://doi.org/10.1609/aaai.v34i05.6194

Issue

Section

AAAI Technical Track: Multiagent Systems