Anytime coalition structure generation in multi-agent systems with positive or negative externalities

摘要

Much of the literature on multi-agent coalition formation has focused on Characteristic Function Games, where the effectiveness of a coalition is not affected by how the other agents are arranged in the system. In contrast, very little attention has been given to the more general class of Partition Function Games, where the emphasis is on how the formation of one coalition could influence the performance of other co-existing coalitions in the system. However, these inter-coalitional dependencies, called externalities from coalition formation, play a crucial role in many real-world multi-agent applications where agents have either conflicting or overlapping goals.