MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities
MaxSAT Encoding for MC-Net-Based Coalition Structure Generation Problem with Externalities
复制标题
DOI：
10.1587/transinf.e97.d.1781
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Xiaojuan Liao;Miyuki Koshimura;H. Fujita;R. Hasegawa
中科院分区：
文献类型：
--
作者：
Xiaojuan Liao;Miyuki Koshimura;H. Fujita;R. Hasegawa
联盟结构生成（CSG）是联盟博弈领域的一个重要研究课题.大多数现有的作品假设，一个联盟的价值是独立的联盟结构中的其他人。最近，人们对更现实的环境产生了兴趣，在这种环境中，一个联盟的价值受到其他联盟形成的影响。这种影响被称为外部性。本文的重点是利用最大可满足性（MaxSAT）来解决可能存在外部性的CSG问题。为了减少CSG问题中可能的解决方案的数量呈指数级增长，我们遵循以前的工作，将CSG问题表示为MC-网（无外部性）和嵌入式MC-网（有外部性）中的规则集。具体来说，启发以前的MC-网为基础的算法利用规则关系之间的约束来解决CSG问题，我们编码这些约束到加权部分MaxSAT（WPM）公式。实验结果表明，一个现成的MaxSAT求解器实现了显着的改善相比，以前的算法相同的问题实例集。关键词：联盟结构生成，外部性，加权部分MaxSAT，合作博弈
Coalition Structure Generation (CSG) is a main research issue in the domain of coalition games. A majority of existing works assume that the value of a coalition is independent of others in the coalition structure. Recently, there has been interest in a more realistic settings, where the value of a coalition is affected by the formation of other coalitions. This effect is known as externality. The focus of this paper is to make use of Maximum Satisfiability (MaxSAT) to solve the CSG problem where externalities may exist. In order to reduce the exponentially growing number of possible solutions in the CSG problem, we follow the previous works by representing the CSG problem as sets of rules in MC-nets (without externalities) and embedded MC-nets (with externalities). Specifically, enlightened by the previous MC-net-based algorithms exploiting the constraints among rule relations to solve the CSG problem, we encode such constraints into weighted partial MaxSAT (WPM) formulas. Experimental results demonstrate that an off-the-shelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances. key words: coalition structure generation, externality, weighted partial MaxSAT, cooperative games