[4N2-J-7] Agents: social multiagents

[4N2-J-7-04] Coalition structure generation problem in cooperative graph games

〇Emi Watanabe¹, Miyuki Koshimura¹, Yuko Sakurai², Makoto Yokoo^1,3 (1. Graduate School of Information Science and Electrical Engineering, Kyushu University, 2. National Institute of Advanced Industrial Science and Technology, AIRC, 3. RIKEN, Center for Advanced Intelligence Project AIP)

Keywords:Game Theory, Cooperative Game, Coalition Structure Generation

In this paper, we consider coalition structure generation problem in cooperative graph games. The cooperative graph game is known as one of typical concise representation for cooperative games by using weighted undirected graph. We develop IP formalization and MaxSAT encoding to nd the optimal coalition structure in cooperative graph games. The feature of our formalization is to introduce the symmetry breaking constraints and sort the agents into decreasing order of the sum of weights of the edges each agent belongs. Our experimental results showthat the commercial solver GUROBI for IP formalization outperforms MaxSAT solver.