Coalition Structure Generation In Multi-Agent Systems With Mixed Externalities

Document Type

Conference Proceeding

Publication Date

5-10-2010

School

Computing Sciences and Computer Engineering

Abstract

Coalition structure generation (CSG) for multi-agent systems is a well-studied problem. A vast majority of the prevous work and the state-of-the-art approaches to CSG assume a characteristic function form of the coalition values, where a coalition's value is independent of the other coalitions in the coalition structure. Recently, there has been interestin the more realistic partition function form of coalition values, where the value of a coalition is affected by how the other agents are partitioned, via externalities. We argue that in domains with externalities, a distributed/adaptive approach to CSG may be impractical, and that a centralized approach to CSG is more suitable. However, the most recent studies in this direction have focused on cases where all externalities are either always positive or always negative, and results on coalition structure generation in more general settings (in particular, mixed externalities) are lacking. In this paper we propose a framework based on agent-types that incorporates mixed externalities and demonstrate that it includes the previous settings as special cases. We also generalize some previous results in anytime CSG, showing that those results are again special cases. In particular, we extend the existing branch and bound algorithm to this new setting and show empirically that significant pruning can be achieved when searching for the optimal coalition structure. This extends the state-of-the-art in CSG for multi-agent systems.

Publication Title

Proceedings of 9th International Conference on Autonomous Agents and Multiagent Systems

First Page

175

Last Page

182

Link to Full Text

Share

COinS