Papers › GCS-Q: Quantum Graph Coalition Structure Generation
GCS-Q: Quantum Graph Coalition Structure Generation
Supreeth Mysore Venkatesh, Antonio Macaluso, Matthias Klusch
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. In particular, given an n-agent ISG, the GCS-Q solves the optimal split problem 𝒪 (n) times using a quantum annealing device, exploring 𝒪(2ⁿ) partitions at each step. We show that GCS-Q outperforms the currently best classical solvers with its runtime in the order of n² and an expected worst-case approximation ratio of 93% on standard benchmark datasets.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections