Coalition Formation

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).

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.