Constrained coalition formation on valuation structures: Formal framework, applications, and islands of tractability

摘要

Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected.