Fuzzy Kernel-Stable Coalitions between Rational Agents

Abstract

A large variety of solutions exists for the problem of coalition formation among autonomous agents, at the theoretical level within game theory, and at the practical, algorithmic level, within multi-agent systems. However, one major underlying assumption of algorithmic solutions suggested to date is that the values of the coalitions are known and are certain at the time of coalition formation negotiation. In many practical cases such as in open, dynamically changing environments this assumption does not hold. In this paper we propose an algorithmic solution to the coalition formation problem that overcomes this limitation of previous solutions. Our solution supports fuzzy coalition values and allows agents to form stable coalition configurations. For this, we combine concepts from the theory of fuzzy sets with the game-theoretic stability concept of the Kernel to deduce the new concept of a fuzzy Kernel. We further provide a low-complexity algorithm for forming fuzzy Kernel stable coalitions among agents.