Distributed Coalition Structure Generation with Positive and Negative Externalities

摘要

One research challenge in multi-agent systems is how to partition a set of agent into coalition structures. The number of different coalitions for a set of agents grows exponential with the number of agents and the number of different partitions grows even faster. The common approach for this problem is to search for the coalition structure that maximizes the system outcome (denoted CS~?). Until recently, most algorithms that solve this problem considered that the value of a coalition is given by a characteristic function, in where those values are not influenced by factors that are external to the coalition. More recently, several authors have focused on problems that consider the presence of externalities. In this case, centralized algorithms were developed to search for the CS~?, but no algorithm was developed to work in a distributed environment. This paper presents a distributed algorithm for searching coalition structures under presence of externalities.