Abstract
In this paper we present a model for coalition formation and payoff distribution in general environments. We focus on a reduced complexity kernel-oriented coalition formation model, and provide a detailed algorithm for the activity of the single rational agent. The model is partitioned into a social level and a strategic level, to distinguish between regulations that must be agreed upon and are forced by agent-designers, and strategies by which each agent acts at will. In addition, we present an implementation of the model and simulation results. From these we conclude that implementing the model for coalition formation among agents increases the benefits of the agents with reasonable time consumption. It also shows that more coalition formations yield more benefits to the agents.
Introduction
In multi-agent systems (MAS), agents often need to team up to achieve goals they couldn't reach alone. However, two major hurdles exist: coalition formation (determining which agents should work together) and payoff distribution (dividing rewards fairly to ensure stability). Classical game theory offers the "Kernel" as a solution—a set of payoff distributions where no agent has a justified objection against another. However, calculating the Kernel is typically an exponential-time problem, requiring the evaluation of $2^n$ possible coalitions for $n$ agents. This paper introduces a computationally efficient model that adapts the Kernel concept into a polynomial-time algorithm.
Methodology: The Coalition Negotiation Algorithm (CNA)
The proposed model bridges the gap between theoretical stability and practical computation through several key innovations:
- Social vs. Strategic Partitioning: The model distinguishes between a social level (fixed protocols agreed upon by designers) and a strategic level (individual agent strategies for payoff maximization).
- Polynomial-K-Stability: Instead of checking all possible coalitions, agents consider a polynomial subset within a specific size range $[K_1, K_2]$. This reduces complexity from exponential to $O(n^i)$.
- Anytime Negotiation: The CNA is an "anytime" algorithm. Agents iteratively propose and negotiate coalition offers. If the process is interrupted, the system still maintains a valid, stable configuration.
- Iterative Transfer Schemes: A modified version of Stearns’ transfer scheme is used to nudge payoff distributions toward the Kernel until a stability threshold ($\epsilon$) is reached.
Experimental Results
The model was evaluated through simulations involving 5 to 13 autonomous agents. These agents were assigned tasks and resources to test the algorithm's performance in various environments.
Profitability and Cooperation
A key finding is that the profitability of cooperation scales with the number of coalition formations. As agents successfully form more groups, the average added value per agent grows significantly, demonstrating the tangible benefits of the CNA model.
Computational Complexity
While negotiation time increases as more agents are added to the system, the polynomial approach keeps these times manageable. For example, in a system of 13 agents, the computation remained within a reasonable timeframe, even on older hardware.
Other Observations
- Logarithmic Participation: The number of agents in coalitions was found to be an increasing monotonic function of the average coalitional value, following a logarithmic curve.
- Individual Rationality: The algorithm consistently ensured that agents were never worse off joining a coalition than remaining alone.
Conclusion and Future Work
The CNA model successfully enables stable coalition formation with polynomial complexity. While it prioritizes stability over absolute Pareto optimality, it provides a practical framework for real-world multi-agent systems. Future work will explore scaling the model to "tens" of agents and testing its performance in non-super-additive environments where conflicts may hinder group formation.
Summary updated