Coalition Formation: Towards Feasible Solutions

Issue title: Multiagent Systems (FAMAS'03)

Article type: Research Article

Authors: Shehory, Onn

Affiliations: IBM Research Lab in Haifa, Haifa Univ. Mount Carmel, Haifa, 31905 Israel

Abstract: Coalition formation research in the last decade has produced an array of coalition formation mechanisms. Although these address a variety of environments and settings, they are usually inadequate for practical applications. The major limitations of the proposed mechanisms that render them inapplicable are a high computational complexity, and unrealistic assumptions regarding the availability of information. In this article we present two recent coalition formation mechanisms that attempt to overcome these limitations. One of the mechanisms introduces a very low complexity, allowing scaling to thousands of agents, and the other mechanism does not assume complete information. Rather, it assumes private, subjective and inaccurate valuation of coalitions. These two mechanisms do not solve all of the problems present in the field, however they point at promising directions that might lead to fully applicable solutions in future research.

Keywords: coalition formation

Journal: Fundamenta Informaticae, vol. 63, no. 2-3, pp. 107-124, 2004