Coalition Formation

Agents form coalitions based on strategic rationality, seeking to maximize their individual utility from the coalition's collective payoff. The central problem is payoff distribution—dividing the coalition's total value among members in a stable way. Key solution concepts include:

• Core: A set of payoff distributions where no sub-coalition can defect and get a better deal.
• Shapley Value: A fair distribution based on each agent's marginal contribution to every possible coalition.
• Nucleolus: A distribution that minimizes the maximum dissatisfaction (excess) of any coalition.

A coalition structure is stable if no subset of agents has an incentive to break away and form their own coalition. The core is the set of payoff allocations that make the grand coalition stable. An allocation is in the core if no sub-coalition can achieve a higher total payoff for its members on its own. In many real-world settings with negative externalities or communication costs, the core may be empty, meaning no perfectly stable allocation exists, leading agents to form multiple, competing coalitions.

Coalitions are rarely static. Formation is a dynamic process often modeled as a negotiation game. Common algorithmic approaches include:

• Merge-and-Split: Agents locally merge into beneficial coalitions and split if members are dissatisfied.
• Coalition Structure Generation: Exhaustively or heuristically searching the space of all possible partitions to find the one that maximizes social welfare.
• Agent-based bargaining: Using offer/counter-offer protocols where agents negotiate membership and payoff terms. Dynamics are influenced by time constraints, outside options, and the evolving capabilities of members.

The standard model is the characteristic function game (CFG). It defines a characteristic function v(C) that assigns a value to every possible coalition C, representing the total payoff the coalition can guarantee itself, independent of outsiders. This assumes transferable utility (payoff is divisible) and often superadditivity (merging coalitions doesn't reduce value). Real-world limitations like communication costs or anti-trust rules lead to partition function games, where a coalition's value depends on how outsiders are organized.

Forming optimal coalitions is computationally challenging. The coalition structure generation problem is NP-hard. Agents face communication complexity limits—they cannot negotiate with every other agent simultaneously. Protocols must manage this via:

• Distributed algorithms that require only local neighbor communication.
• Mediated negotiation through a facilitator agent.
• Bounded-rationality approaches where agents use heuristics to find satisfactory, if not optimal, coalitions within realistic time and communication budgets.

Coalition formation models real-world multi-agent coordination problems:

• Task-Oriented Coalitions: In robotics, UAVs form ad-hoc coalitions for surveillance or delivery, where value v(C) is task completion capability.
• Resource Sharing: In cloud/edge computing, service providers form coalitions to share computational resources and bid on complex workloads.
• Buyer Coalitions: In e-commerce, buyers group together to achieve bulk discounts (e.g., Groupon model).
• Political & Legislative Bodies: Parties form coalition governments to achieve a majority, distributing ministerial portfolios (payoffs).

A coalitional game is the formal mathematical model underpinning coalition formation. It defines a set of players (N), a characteristic function (v) that assigns a value to every possible coalition, and a solution concept (like the core or Shapley value) for distributing payoffs. The characteristic function captures the synergy of cooperation, where v(S) represents the total utility coalition S can achieve independently.

• Key Property: Superadditivity, where the value of a merged coalition is at least the sum of its parts (v(S∪T) ≥ v(S) + v(T)), incentivizing larger coalitions.
• Solution Concepts answer 'who gets what?': The core contains payoff distributions where no sub-coalition has an incentive to break away, while the Shapley value allocates payoffs based on each agent's marginal contribution.

The core is the set of payoff distributions (imputations) in a coalitional game where no subgroup of agents can defect and achieve a higher total payoff for themselves. A payoff vector is in the core if it is:

• Individually Rational: Each agent receives at least what they could get alone (v({i})).
• Coalitionally Rational: For every possible coalition S, the sum of payoffs to its members is at least v(S).

An empty core indicates inherent instability—no distribution can prevent some subgroup from breaking away. The core is a strong solution concept but can be computationally hard to determine and is often empty in practice, leading to the use of related concepts like the least core or nucleolus.

The Shapley value is a unique solution concept for coalitional games that allocates payoffs based on an agent's average marginal contribution across all possible coalition permutations. It is defined axiomatically by properties of efficiency, symmetry, dummy player, and additivity.

• Calculation: For an agent i, it sums the marginal value [v(S ∪ {i}) - v(S)] for every coalition S not containing i, weighted by the probability of that coalition forming randomly.
• It provides a fair and predictable distribution, often used when the core is empty or large. However, it assumes all coalition permutations are equally likely and requires evaluating the characteristic function for all 2^|N| coalitions, making it computationally intensive for large agent sets.

The merge-and-split algorithm is a decentralized, heuristic approach for dynamic coalition formation where agents repeatedly reconfigure based on local payoff improvements. It operates in two phases:

1. Merge: Any set of coalitions can merge into a single coalition if the new coalition is Pareto superior—all members are at least as well off, and at least one is strictly better off.
2. Split: Any coalition can split into smaller coalitions if all resulting members are at least as well off, with one strictly better off.

The process iterates until a stable partition is reached where no more beneficial merges or splits exist. This algorithm is scalable and does not require a central coordinator, making it suitable for distributed multi-agent systems like wireless sensor networks or task-oriented agent swarms.

Hedonic coalition formation models scenarios where an agent's payoff depends solely on the membership of the coalition it belongs to, not on the structure of other coalitions. Agents have preferences over which coalitions they join.

• Key Construct: An agent's preference relation ranks all possible coalitions it could be a member of.
• Stability Concepts: A partition is Nash stable if no agent wants to unilaterally move to another existing coalition. It is core stable if no group of agents can deviate to form a new coalition that they all strictly prefer. This model is highly applicable to social network formation, club goods, and team formation where identity and composition matter more than a transferable monetary value.

Distributed Constraint Optimization (DCOP) is a fundamental framework for modeling coalition formation and multi-agent coordination problems. Agents control variables, have local constraints, and share a global objective function to optimize.

• In coalition formation, joining a coalition can be modeled as a variable assignment, with constraints ensuring exclusive membership and the global utility function representing the total value of the formed coalition structure.
• Algorithms like ADOPT (Asynchronous Distributed OPTimization) or DPOP (Dynamic Programming Optimization Protocol) provide complete, distributed solutions for finding the optimal coalition structure, but are often computationally complex (NP-hard). DCOP provides a rigorous, general-purpose formalism for reasoning about the trade-offs in collaborative problem-solving that underpin coalitional behavior.