Using binary particle swarm optimization to search for maximal successful coalition

摘要

Coalitional Resource Games (CRGs) are a natural and formal framework in which agents wish to form coalitions to pool their scarce resources in order to achieve a set of goals that satisfy all members of a coalition. Thus far, many computational questions surrounding CRGs have been studied, but to our knowledge, a number of natural decision problems in CRGs have not been solved. Therefore, in this paper we investigate the possibility of using binary particle swarm optimization (BPSO) as a stochastic search process to search for Maximal Successful Coalition (MAXSC) in CRGs, which is a DP-complete problem. For this purpose, we develop a one-dimensional binary encoding scheme, propose strategies for encoding repair to ensure that each encoding in every iteration process is approximately valid and logicallsy consistent, and discuss some key properties of repair strategies. To evaluate the effectiveness of our algorithms, we compare them with the only other algorithm available in the literature for identifying MAXSC (due to Shrot, Aumann, and Kraus). The result shows that our algorithms are significantly faster especially for large-scale datasets.