Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task OrientedDomains

AAAI 1994

TL;DR

This paper introduces a novel mechanism for enabling self-interested agents to form beneficial coalitions in task-oriented domains. It leverages cryptographic techniques to ensure stability and efficiency, allowing sub-groups of agents to coordinate and achieve mutually beneficial agreements, even when not all agents are involved.

What Problem Does This Paper Address?

In multi-agent systems, agents often need to coordinate their actions to achieve their goals more efficiently. While much research has focused on bilateral negotiations or full group consensus, this paper tackles a more complex scenario: situations where beneficial agreements can be reached among sub-groups of agents, excluding others. This is particularly relevant in "Task Oriented Domains" (TODs) where agents have tasks to complete, and cooperation can reduce the overall cost. The challenge is to design mechanisms that allow these self-interested agents to form stable and efficient coalitions, ensuring that no agent has an incentive to deviate from a formed coalition.

Methods

The paper proposes a Shapley Value-based mechanism for subadditive TODs. The core idea is to allow agents to form an "all-or-nothing" deal where they all participate in the full coalition. The value generated by this coalition is then distributed among its members.

Key aspects of the method include:

  • Coalition Games: The problem is framed as a coalition game, where the "value" of a coalition is the total utility its members can achieve by coordinating.
  • Subadditive TODs: The mechanism is designed for domains where the cost of performing the union of tasks is less than or equal to the sum of the costs of performing each task set individually.
  • Shapley Value: This concept from game theory is used to determine a fair distribution of the coalition's value among its members. It represents the expected contribution of an agent to all possible coalitions.
  • Cryptographic Techniques: To ensure stability and prevent manipulation, the paper suggests using simple cryptographic methods for agents to agree on a random permutation of joining the coalition. This leads to the "Random Permutation Mechanism."
  • Concave TODs: For a specific class of subadditive domains called concave TODs, the mechanism is shown to satisfy not only individual and group rationality but also the stronger condition of coalition rationality, meaning no sub-group has an incentive to break away.

Datasets

Not discussed in the paper. The paper uses theoretical examples like the "Tileworld" and "Postmen Domain" to illustrate concepts.

Key Insights and Ideas

  • Beyond Full Consensus: The most significant insight is the recognition and formalization of coalition formation among sub-groups, moving beyond the assumption that all agreements must involve the entire set of agents.
  • Stability through Cryptography: The use of cryptographic techniques for random permutation generation is a clever way to ensure a fair and unpredictable process for coalition formation, preventing manipulation by sub-groups.
  • Shapley Value as a Fair Allocator: The Shapley Value emerges as a robust method for distributing the gains from cooperation, satisfying individual rationality and, in certain domain types, even coalition rationality.
  • Domain Properties Matter: The paper highlights how the properties of the domain (subadditivity, concavity) directly impact the stability and rationality guarantees of the coalition formation mechanism.

Key Results

  • A Shapley Value-based mechanism is proposed that is symmetric, efficient, and individually rational for subadditive TODs.
  • When the domain is also concave, this mechanism satisfies coalition rationality, ensuring long-term stability.
  • The "Random Permutation Mechanism" offers a computationally efficient alternative (linear complexity) to directly calculating the Shapley Value, while still providing the same expected utility.
  • The paper demonstrates through examples (like the unstable encounter in the Postmen Domain) why simpler mechanisms or payoff distributions can lead to instability, where agents have incentives to form sub-coalitions.

Limitations and Future Work

  • Non-Subadditive TODs: The current mechanism is designed for subadditive domains. Future research is needed for non-subadditive TODs.
  • Incentive Compatibility with Partial Information: The paper acknowledges that future work should investigate mechanisms that are incentive-compatible when agents have partial information about others' goals and can potentially deceive.
  • Computational Complexity: While the Random Permutation Mechanism improves efficiency, calculating the Shapley Value itself can still be computationally expensive for a large number of agents (exponential in the number of agents for evaluating all coalitions).
  • Real-world Applicability: The cryptographic mechanisms, while theoretically sound, would need practical implementation and testing in real-world multi-agent systems.

Summary updated

BibTeX
@inproceedings{1994coalition,
  title = {{Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task OrientedDomains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure