Skip to Main content Skip to Navigation
New interface
Conference papers

Robust Coalition Structure Generation

Abstract : How to form effective coalitions is an important issue in multi-agent systems. Coalition Structure Generation (CSG) involves partitioning a set of agents into coalitions so that the social surplus (i.e. the sum of the rewards obtained by each coalition) is maximized. In many cases, one is interested in computing a partition of the set of agents which maximizes the social surplus, but is robust as well, which means that it is not required to recompute new coalitions if some agents break down. In this paper, the focus is laid on the Robust Coalition Structure Generation (RCSG) problem. A formal framework is defined and some decision and optimization problems for RCSG are pointed out. The computational complexity of RCSG is then identified. An algorithm for RCSG (called AmorCSG) is presented and evaluated on a number of benchmarks
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien DELORME Connect in order to contact the contributor
Submitted on : Monday, June 20, 2022 - 5:16:21 PM
Last modification on : Thursday, June 23, 2022 - 9:50:28 AM
Long-term archiving on: : Thursday, September 22, 2022 - 10:57:11 AM


Files produced by the author(s)


  • HAL Id : hal-03300961, version 1



Tenda Okimoto, Nicolas Schwind, Emir Demirovic, Katsumi Inoue, Pierre Marquis. Robust Coalition Structure Generation. 21st International Conference on Principles and Practice of Multi-Agent Systems (PRIMA'18), Oct 2018, Tokyo, Japan. pp.140-157. ⟨hal-03300961⟩



Record views


Files downloads