Extension of MC-net-based coalition structure generation: Handling negative rules and externalities

Forming effective coalitions is a major research challenge in AI and multi-agent systems. A Coalition Structure Generation (CSG) problem involves partitioning a set of agents into coalitions so that the social surplus is maximized. Ohta et al introduce an innovative direction for solving CSG, i.e., by representing a characteristic function as a set of rules, a CSG problem can be formalized as the problem of finding a subset of rules that maximizes the sum of rule values under certain constraints. This paper considers two significant extensions of the formalization/algorithm of Ohta et al, i.e., (i) handling negative value rules and (ii) handling externalities among coalitions.