Coalition Structure Generation Algorithms

    Coalition Structure Generation Algorithms
Authors Mustansar Ali Ghazanfar
Year 2012
Publication
ISBN
Pages 68 pages
Size 693 KB
Format EPUB
Price 3 $ 0.6 $ Ben discount

Abstract

A coalition is a set of self-interested agents that agree to cooperate to achieve a set of goals. Coalition formation is an active area of research in multi-agent systems nowadays. Coalition structure generation is one of the most challenging problems in coalition formation in which agents determine which of the many possible coalitions to form in order to attain some goal. Generally speaking, agents would enumerate all possible coalitions, store them in memory, and then try to construct the coalition structure that maximizes the sum of the values of the coalitions. But this is not feasible when we have a large number of agents, and other constraints on execution time, and memory. Hence there is a need to develop an algorithm which can generate solutions rapidly for large number of agents while providing bounds on the value of solution as well. We propose two new heuristics, namely LocalSearch and GreedySearch (which is the extension of the LocalSearch), for generating the coalition structure which satisfy these properties. Furthermore, they have low computation complexity and returns solution by consuming small amount of memory as they load only one list of coalitions in memory at a time.These heuristics use a greedy approach and return ‘good-enough’ solutions quickly. In LocalSearch we visit each sub-space (only once) in the integer partition graph (proposed by [Rahwan et al., (2007)]), pick the maximum value from each coalition list, and construct a coalition structure from them. In GreedySearch approach, we pick the highest value from all the input values, select the sub-spaces that contain this value, and from these sub-spaces discover the one which can give us good value. Then we use the LocalSearch heuristic to construct a coalition structure from this selected sub-space. We empirically show that these heuristics are able to return very good solutions in very short time. Furthermore, they enhance the performance of state of the art algorithm, IP (proposed by [Rahwan et al., (2007)]) in the following ways. First, they improve the lower bounds computed by the IP algorithm drastically, which helps in pruning a lot of space without going into the search space. Second, they improve its anytime property. Third, they improve its solution quality and provide ‘good-enough’ solutions, at low cost, especially when we have a large number of agents.