Coalition Structure Generation (CSG) is an NP-Hard problem in which agents are partitioned into mutually exclusive groups to maximize their social welfare. In this work, we propose QuACS, a novel hybrid quantum classical algorithm for Coalition Structure Generation in Induced Subgraph Games (ISGs). Starting from a coalition structure where all the agents belong to a single coalition, QuACS recursively identifies the optimal partition into two disjoint subsets. This problem is reformulated as a QUBO and then solved using QAOA. Given an $n$-agent ISG, we show that the proposed algorithm outperforms existing approximate classical solvers with a runtime of $\mathcal{O}(n^2)$ and an expected approximation ratio of $92\%$. Furthermore, it requires a significantly lower number of qubits and allows experiments on medium-sized problems compared to existing quantum solutions. To show the effectiveness of QuACS we perform experiments on standard benchmark datasets using quantum simulation.
翻译:联盟结构生成(CSG)是一种NP-难问题,其目的是将代理划分为相互独立的组,以最大化其社会福利。在本文中,我们提出了 QuACS,一种用于引导子图博弈(ISG)中联盟结构生成的新型混合量子经典算法。从一个代理全部属于单个联盟的联盟结构开始,QuACS 递归地确定了两个不相交子集的最优划分。该问题被重新格式化为QUBO,然后使用QAOA求解。对于一个$n$-代理ISG,我们表明所提出的算法优于现有的近似经典解法,其运行时间为 $\mathcal{O}(n^2)$,期望的近似比为 $92\%$。此外,它需要更少的量子比特,并允许在中等大小的问题上进行实验,比现有的量子解决方案更有效。为了展示QuACS的有效性,我们在标准基准数据集上使用量子模拟进行实验。