Publikation
GCS-Q: Quantum Graph Coalition Structure Generation
Supreeth Venkatesh; Antonio Macaluso; Matthias Klusch
In: ICCS 2023 Conference Proceedings. International Conference on Computational Science (ICCS-2023), July 3-5, Prague, Czech Republic, Springer, 2023.
Zusammenfassung
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 known to be NP-hard. Though there are algorithmic solutions with high computational complexity available for this combinatorial optimization problem, it is unknown whether quantum-supported solutions may outperform classical algorithms. In this paper, we propose a novel quantum-supported solution for coalition structure generation in Induced Subgraph Games (ISGs). Our hybrid classical-quantum algorithm, called GCS-Q, iteratively splits a given n-agent graph game into two nonempty subsets in order to obtain a coalition structure with a higher coalition value. The GCS-Q solves the optimal split problem O(n) times, exploring O(2^n) partitions at each step. In particular, the optimal split problem is reformulated as a QUBO and executed on a quantum annealer, which is capable of providing the solution in linear time with respect to n. We show that GCS-Q outperforms the currently best classical and quantum solvers for coalition structure generation in ISGs with its runtime in the order of n^2 and an expected approximation ratio of 93% on standard benchmark datasets.