Coalition formation meets information theory
Conference Paper
Overview
Additional Document Info
Other
View All
Overview
abstract
The process of coalition formation, where distinct autonomous agents come together to act as a coherent group is an important form of interaction in multi-agent systems. Previous work has focused on developing coalition formation algorithms which seek to maximize some coalition structure valuation function V(CS). However, for many real-world systems, evaluation of V(CS) must be done empirically, which can be time-consuming, and when evaluation of V(CS) becomes too expensive, value-based coalition formation algorithms can become unattractive. In this work we present a algorithm for forming high value coalition structures when direct evaluation of V(CS) is not feasible. We present the IBCF (Information-Based Coalition Formation) algorithm, which does not try to directly maximize V(CS), but instead seeks to form coalitions which possess maximum amounts of information about how environmental states and agent actions relate to external reward. Such information maximization strategies have been found to work well in other areas of artificial intelligence, and we evaluate the performance of the IBCF algorithm on two multi-agent control domains (multi-agent pole balancing and the SysAdmin network management problem) and compare the performance of IBCF against relevant state-of-the-art algorithms in each domain. Copyright 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
