Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)

Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)

Gianluigi Greco, Antonella Guzzo

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Journal track. Pages 5612-5616. https://doi.org/10.24963/ijcai.2018/795

Coalition structure generation is considered in a setting where feasible coalition structures must satisfy constraints of two different kinds modeled in terms of a 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. It is shown that valuation structures can be used to model a number of relevant problems in real-world applications. Moreover, complexity issues arising with them are studied, by focusing in particular on identifying islands of tractability based on topological properties of the underlying interaction graph. Stability issues on valuation structures are studied too.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Agent-based and Multi-agent Systems: Coordination and Cooperation
Knowledge Representation and Reasoning: Computational Complexity of Reasoning