Solving Coalition Structure Generation Problems over Weighted Graph
Solving Coalition Structure Generation Problems over Weighted Graph
复制标题
DOI：
10.1007/978-3-030-33792-6_21
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Emi Watanabe;Miyuki Koshimura;Y. Sakurai;M. Yokoo
中科院分区：
文献类型：
--
作者：
Emi Watanabe;Miyuki Koshimura;Y. Sakurai;M. Yokoo
联盟结构生成（CSG）是联盟博弈领域的一个领先研究问题，它将智能体划分为详尽且不相交的联盟以优化社会福利。本文研究了加权无向图上的 CSG 问题，其中任意两个连接代理之间的边上的权重表示它们在联盟中协同工作的程度。权重可以是正值，也可以是负值。我们研究两类问题。一种是对联盟数量没有任何限制的CSG，另一种是具有预先确定的k个联盟的CSG。我们提出了两种方法来解决这些问题：ILP 公式和 MaxSAT 编码。
Coalition Structure Generation (CSG), which is a leading research issue in the domain of coalitional games, divides agents into exhaustive and disjoint coalitions to optimize social welfare. This paper studies CSG problems over weighted undirected graphs in which the weight on an edge between any two connecting agents represents how well they work together in a coalition. The weight can have either a positive or a negative value. We examine two types of problems. One is a CSG without any restrictions on the number of coalitions, and another is a CSG with k coalitions wherekis determined in advance. We present two methods to solve these problems: ILP formulation and MaxSAT encoding.