Results on the formation of multi-agent teams are reviewed and extended. Conditions are specified under which it is individually rational for agents to spontaneously form coalitions in order to engage in collective action. In a cooperative setting the formation of such groups is to be expected. Here we show that in non-cooperative environments—presumably a more realistic context for a variety of both human and software agents—self-organized coalitions are capable of extracting welfare improvements. The Nash equilibria of these coalitional formation games are demonstrated to always exist and be unique. Certain free rider problems in such group formation dynamics lead to the possibility of dynamically unstable Nash equilibria, depending on the nature of intra-group compensation and coalition size. Yet coherent groups can still form, if only temporarily, as demonstrated by computational experiments. Such groups of agents can be either long-lived or transient. The macroscopic structure of these emergent “bands” of agents is stationary in sufficiently large populations, despite constant adaptation at the agent level. It is argued that assumptions concerning attainment of agent-level (Nash) equilibrium, so ubiquitous in conventional economics and game theory, are difficult to justify behaviorally and highly restrictive theoretically, and are thus unlikely to serve either as fertile design objectives or robust operating principles for realistic multi-agent systems.
This paper was published in Proceedings of the First International Conference on Autonomous Agents and Multi-Agent Systems, 2002