GCS-Q: Quantum Graph Coalition Structure Generation

Abstract

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 $\mathcal{O}(n)$ times using a quantum annealing device, exploring $\mathcal{O}(2^n)$ partitions at each step. We show that GCS-Q outperforms the currently best classical solvers with its runtime in the order of $n^2$ and an expected worst-case approximation ratio of $93\%$ on standard benchmark datasets.

6 pages, 3 figures

References in corpus (2)

• Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
• BILP-Q: Quantum Coalition Structure Generation

Cited by in corpus (10)

• Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation
• MAQA: A Quantum Framework for Supervised Learning
• Qubit-efficient Variational Quantum Algorithms for Image Segmentation
• Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
• Enabling Non-Linear Quantum Operations through Variational Quantum Splines
• Quantum Annealing-Based Algorithm for Efficient Coalition Formation Among LEO Satellites
• i-QLS: Quantum-supported Algorithm for Least Squares Optimization in Non-Linear Regression
• Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games
• Quantum-Assisted Correlation Clustering
• Toward Quantum Utility in Finance: A Robust Data-Driven Algorithm for Asset Clustering