
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

MaxSAT Encoding for MCNetBased Coalition Structure Generation Problem with Externalities
Xiaojuan LIAO Miyuki KOSHIMURA Hiroshi FUJITA Ryuzo HASEGAWA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E97D
No.7
pp.17811789 Publication Date: 2014/07/01 Online ISSN: 17451361
DOI: 10.1587/transinf.E97.D.1781 Type of Manuscript: PAPER Category: Information Network Keyword: coalition structure generation, externality, weighted partial MaxSAT, cooperative games,
Full Text: PDF(384.1KB)>>
Summary:
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 MCnets (without externalities) and embedded MCnets (with externalities). Specifically, enlightened by the previous MCnetbased 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 offtheshelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances.

