[2M4-OS-11b] OS-11

[2M4-OS-11b-04] An Improvement of MaxSAT Encoding for Coalition Structure Generation with Externaliies

Haruto Kinoshita¹, 〇Yuko Sakurai¹, Miyuki Koshimura², Makoto Yokoo² (1. Nagoya Institute of Technology, 2. Kyushu University)

Keywords:Cooperative games, Coalition structure generation problem, MaxSAT

The Coalition Structure Generation (CSG) problem involves dividing the set of agents to maximize the sum of coalition values, and various algorithms have been proposed to address it. We propose an improvement that enables more efficient solving of the CSG problem, where externalities exist between coalitions, compared to the conventional MaxSAT encoding. Computational experiments demonstrate that our approach can reduce CPU computation time compared to traditional methods.