GCS-Q: Quantum Graph Coalition Structure Generation

The problem of generating an optimal coalition structure for a given coalition game of rational agents is to find a partition that maximizes their social welfare and is known to be NP-hard. This paper proposes GCS-Q, a novel quantum-supported solution for Induced Subgraph Games (ISGs) in coalition structure generation. GCS-Q starts by considering the grand coalition as initial coalition structure and proceeds by iteratively splitting the coalitions into two nonempty subsets to obtain a coalition structure with a higher coalition value. The problem of coalition structure generation (CSG) is to find a partition of n rational agents into mutually disjoint coalitions such that the sum of the resulting coalition values for this coalition structure is maximized. For a given coalition game (A, v), the coalition structures CS are partitions of A into mutually disjoint, feasible coalitions C. The corresponding ISG is to find the optimal coalition structure CS In ISGs, the coalition values depend only on the pairwise interactions between nodes/agents.