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.

Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.