论文标题
GCS-Q：量子图联盟结构生成
GCS-Q: Quantum Graph Coalition Structure Generation
论文作者
论文摘要
为特定的理性代理联盟游戏产生最佳联盟结构的问题是找到一个最大化其社会福利的分区，并被称为NP-HARD。本文提出了GCS-Q，这是一种新型的量子支持解决方案，用于联盟结构生成中的诱导子图游戏（ISGS）。 GCS-Q首先将大联盟视为初始联盟结构，并通过将联盟划分为两个非空的子集，以获得具有较高联盟价值的联盟结构。特别是，给定$ n $ - 代理ISG，GCS-Q使用量子退火设备解决了最佳拆分问题$ \ MATHCAL {O}（n）$ times，并在每个步骤中探索$ \ Mathcal {O}（2^n）$分区。我们表明，GCS-Q的运行时以$ n^2 $的顺序优于当前最佳的古典求解器，并且在标准基准数据集中预期的最差案例近似值为$ 93 \％$。
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.
