Coalition formation among autonomous agents: Strategies and complexity

Abstract

Autonomous agents are designed to reach goals that were pre-defi ned by their operators. An important way to execute tasks and to maximize payoff is to share resources and to cooperate on task execution by creating coalitions of agents. Such coalitions will take place if, and only if, each member of a coalition gains more if he joins the coalition than he could gain before. There are several ways to create such coalitions and to divide the joint payoff among the members. Variancein these methods is due to diff erent environments,different settings in a specific environment, and different approaches to a specific environment with specific settings. In this paper we focus on the cooperative (super-additive) environment, and suggest two different algorithms for coalition formation and payoff distribution in this environment. We also deal with the complexity of both computation and communication of each algorithm, and we try to give designers some basic tools for developing agents for this environment.