Polynomial Time Algorithms for Stable Coalition Formation

30 concepts22 papers1 proposal

In multi-agent systems, agents often need to form teams—or coalitions—to accomplish tasks that they cannot complete alone. Whether coordinating a fleet of autonomous delivery drones, distributing resources in a communication network, or matching buyers and sellers in a market, the core challenge is deciding who should work with whom, and how the resulting rewards should be divided.

From a game-theoretic perspective, we want these groupings to be stable. A coalition structure is stable if no individual agent or subgroup of agents has an incentive to break away and form a new team. However, finding these stable configurations is notoriously difficult. Because the number of ways to partition $n$ agents grows exponentially with the number of agents (governed by Bell numbers), searching for an optimal or stable partition quickly becomes computationally intractable.

To deploy these systems in the real world, researchers have developed techniques to bypass this combinatorial explosion. By imposing structural constraints, relaxing stability criteria, and exploiting specific utility structures, it is possible to design algorithms that find stable coalitions in polynomial time.

Bounding the Search Space via Structural Constraints

The most direct way to turn an exponential search problem into a polynomial one is to mathematically restrict the types of coalitions allowed. If agents are free to form groups of any size, an algorithm must evaluate up to $2^n$ combinations. However, in many practical scenarios, massive coalitions are unnecessary or physically impossible.

In Task Allocation Via Coalition Formation Among Autonomous Agents, Onn Shehory et al. demonstrated that if you impose a fixed upper bound $k$ on the maximum number of members allowed in any single group, the search space collapses from exponential to polynomial complexity. Instead of evaluating all subsets, the algorithm only needs to consider combinations up to size $k$, reducing the complexity to $O(n^k)$. This heuristic allows large-scale multi-agent systems to find high-quality task allocations quickly.

This size-bounding principle applies across diverse domains. For instance, in defensive multi-robot games, Rui Yan et al. showed in Multiplayer Homicidal Chauffeur Reach-Avoid Games: A Pursuit Enclosure Function Approach that complex multi-robot coordination can be simplified by proving that any evader can be successfully blocked by a coalition of at most two pursuers. By limiting cooperating groups to a small constant, task allocation becomes real-time and scalable.

Similarly, when agents are allowed to split their resources across multiple groups at once, the problem becomes even more complex. To manage this, Tianyu Wang et al. proved in Overlapping Coalition Formation Games for Emerging Communication Networks that restricting either the number of coalitions an agent can join or the total number of available tasks isolates tractable subclasses. These constraints enable decentralized, polynomial-time algorithms to reach stable outcomes in dense communication networks.

Relaxing Stability: From Global to Local Agreements

Another powerful lever for achieving tractability is changing the definition of "stability" itself. Traditional game-theoretic concepts like the Core require that no possible subgroup wants to deviate. Verifying this requires checking an exponential number of potential defections.

If we relax this requirement to focus on local or conditional deviations, the computational burden drops dramatically. In Coalition Formation Methods in Multi-Agent Environments, Onn Shehory introduced "polynomial Kernel-stability." By utilizing a relaxed stability criterion, agents can verify group membership and payoff distributions via an "anytime" algorithm, allowing them to reach beneficial partnerships even if negotiation is abruptly interrupted.

A similar breakthrough was achieved by Haris Aziz et al. in Stable partitions in additively separable hedonic games. While checking for Core stability is NP-hard, the authors provided a polynomial-time algorithm to compute a contractually individually stable partition. Under this concept, an agent can only move to a new coalition if both the agent prefers the move and the departure is approved by the old coalition while the arrival is welcomed by the new one. This localizes the verification step to immediate neighbors, bypassing global evaluation.

Strict Core Stability         Contractual Individual Stability
  (Check all 2^n groups)            (Check immediate local swaps)
       [Hard]                             [Tractable]
    O(Exponential)                       O(Polynomial)

When exact stability is mathematically impossible or too expensive, approximate stability offers an alternative route. In Multi-Leader Congestion Games with an Adversary, Tobias Harks et al. demonstrated that approximate stable configurations can be identified in polynomial time using incremental assignment algorithms, guaranteeing near-optimal resource distributions even in volatile, adversarial environments.

Exploiting Structured Utilities and Graph Reductions

The way agents calculate their rewards—their utility functions—profoundly shapes the complexity of coalition formation. When utilities are completely arbitrary, the problem is intractable. But when utilities follow structured mathematical patterns, we can map coalition formation directly onto efficient graph algorithms.

Consider peer-averaged preferences, where an agent's happiness depends on the average benefit provided by their peers. In Stable outcomes in modified fractional hedonic games, Gianpiero Monaco et al. showed that under these modified fractional hedonic models, finding both the social optimum and core-stable partitions becomes computationally efficient. The peer-averaging structure simplifies the mathematical landscape, allowing polynomial-time algorithms to find stable outcomes that capture a significant fraction of maximum social welfare.

For cooperative games where rewards show diminishing returns or submodular properties, we can leverage classic network optimization. In Computing Least Cores of Supermodular Cooperative Games, Daisuke Hatano et al. proved that computing robust value distributions (the least core) for supermodular games on hypergraphs can be achieved in polynomial time. They achieved this by reducing the search for deviating coalitions to a standard minimum cut problem, translating an exponential search over coalitions into a highly optimized network flow calculation.

Supermodular Game Stability  ───►  Minimum Cut Problem  ───►  Polynomial Time
 (Exponential Coalitions)          (Network Flow Graph)          (Max-Flow/Min-Cut)

Even in complex resource exchange markets, structural properties can unlock tractability. In An impossibility result for housing markets with fractional endowments, Haris Aziz et al. designed the Fractional Top Trading Cycles (FTTC) algorithm. This framework proves that finding stable allocations within the stochastic dominance core is computationally tractable for large-scale applications, even when ownership of resources is split into fractional shares.

Iterative Pairing and Greedy Pruning

In decentralized environments, agents lack a global view of the system. To form coalitions efficiently without a central coordinator, agents can use iterative pairing and greedy pruning algorithms. Instead of computing the globally perfect partition in one shot, agents make local, sequential improvements that guarantee immediate utility gains.

In Forming Coalitions in the Face of Uncertain Rewards, Steven P. Ketchpel proposed decentralized, iterative pairing algorithms that reduce computational complexity to cubic time ($O(n^3)$) relative to the number of agents. By using localized two-agent auctions, the system determines leadership and reward distribution incrementally, offering a massive scalability advantage over traditional exponential-time game-theoretic approaches.

This concept of step-by-step optimization is vital for modern distributed machine learning. In Decentralized Dynamic Cooperation of Personalized Models for Federated Continual Learning, Danni Yang et al. utilized iterative partitioning optimization to manage the complexity of grouping distributed learning agents. By pruning the search space and focusing exclusively on group transitions that provide immediate utility gains, their approach identifies stable, cooperative model assignments in polynomial time.

Efficient Oracles for Payoff Distributions

Once a coalition structure is chosen, the next hurdle is deciding how to distribute the collective payout fairly among the members. Classic solution concepts like the Shapley value or the nucleolus provide mathematically rigorous definitions of fairness, but calculating them typically requires evaluating the performance of every possible sub-coalition.

To make fair payoff distribution practical, researchers design specialized algorithmic "oracles" that compute these values without exhaustive enumeration. For example, in Computing the nucleolus of weighted voting games, Dmitrii V. Pasechnik et al. established a general algorithmic principle: the nucleolus of a game can be computed in polynomial time if the top distinct deficits for a payoff vector can be identified efficiently. By using a dynamic programming-based separation oracle, they shifted the problem from theoretical intractability to practical feasibility for real-world multi-agent systems.

The complexity of these distribution methods is also heavily influenced by externalities—how the actions of one coalition affect outside groups. In Complexity of Computing the Shapley Value in Games with Externalities, Oskar Skibski demonstrated that while general externalities make computing fair rewards #P-complete, restricting the scope of externalities (such as only considering partitions involving at most two groups) keeps the calculations computationally tractable across various compact representations.

Finally, understanding why a game is hard can reveal hidden paths to tractability. In Complexity of Determining Nonemptiness of the Core, Vincent Conitzer et al. proved that the hardness of finding a stable core outcome often stems entirely from the difficulty of calculating what the "grand coalition" of all agents can achieve, rather than the strategic negotiation among the agents themselves. If the maximum utility of the grand coalition is provided as an explicit input, the strategic aspect of finding a stable allocation can be solved in polynomial time.

Summary

The transition from exponential to polynomial-time coalition formation relies on a shared philosophy: trade global perfection for local or structured tractability. Whether by bounding coalition sizes, relaxing the stability criteria to local rules, or mapping utilities to graph algorithms, these techniques allow autonomous agents to reap the benefits of strategic cooperation without getting trapped in combinatorial explosion.

Key Foundational Work

Coalition Formation Methods in Multi-Agent Environments (1994) — contributed 2 concept elements to this direction.
Task Allocation Via Coalition Formation Among Autonomous Agents (1995) — contributed 2 concept elements to this direction.
Forming Coalitions in the Face of Uncertain Rewards (1994) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_polynomial_time_coalition_formation_67a6e26b,
  title = {polynomial-time coalition formation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-time-coalition-formation/rdr_67a6e26bfe0e43e68d625b823377d31d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_polynomial_time_coalition_formation_67a6e26b_v1,
  title = {polynomial-time coalition formation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-time-coalition-formation/rdr_67a6e26bfe0e43e68d625b823377d31d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake