A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results

Onn Shehory, Sarit KrausAAAI 1996 · OpenReview

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.

The added value to agents increases significantly as more coalitions are formed.

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.

Negotiation time grows as a function of the number of agents, following an exponential trend but staying within practical limits for the tested range.

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

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.
BibTeX
@inproceedings{shehory1996kernel,
  author = {Onn Shehory and Sarit Kraus},
  title = {{A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
  url = {https://openreview.net/forum?id=SkVCNJZ_Wr},
}
Figure