On the computation of probabilistic coalition structures

Abstract In Coalition Structure Generation (CSG), one seeks to form a partition of a given set of agents into coalitions such that the sum of the values of each coalition is maximized. This paper introduces a model for Probabilistic CSG (PCSG), which extends the standard CSG model to account for the stochastic nature of the environment, i. e. , when some of the agents considered at start may be finally defective. In PCSG, the goal is to maximize the expected utility of a coalition structure. We show that the problem is \({\mathsf{NP}}^{\mathsf {PP}}\) -hard in the general case, but remains in \({\mathsf{NP}}\) for two natural subclasses of PCSG instances, when the characteristic function that gives the utility of every coalition is represented using a marginal contribution network (MC-net). Two encoding schemes are presented for these subclasses and empirical results are reported, showing that computing a coalition structure with maximal expected utility can be done efficiently for PCSG instances of reasonable size. This is an extended and revised version of the paper entitled “Probabilistic Coalition Structure Generation” published in the proceedings of KR’18, pages 663–664 [ 33 ].

Authors

• Nicolas Schwind National Institute of Advanced Industrial Science and Technology
• Tenda Okimoto
• Pierre Marquis Univ. Artois, CNRS, CRIL, Lens, France Institut Universitaire de France

Keywords

• Coalition Structure Generation
• Uncertainty
• Computational complexity
• Marginal contribution networks