Graph-Constrained Coalition Formation

58 concepts43 papers1 proposal

In cooperative game theory and multi-agent systems, a fundamental question is how self-interested agents should group themselves into teams, or coalitions, to maximize efficiency, stability, or fairness.

In a classic, unconstrained coalitional game, any arbitrary subset of agents can form a team. If you have a system of $n$ agents, this assumption creates an exponential explosion of $2^n$ possible coalitions. Searching through this space to find an optimal partition—a problem known as Coalition Structure Generation (CSG)—is notoriously NP-hard.

But in the real world, agents cannot cooperate with just anyone. Physical distance, social mistrust, or communication silos limit our options. You cannot carpool with someone who lives three states away, and a hospital cannot easily share sensitive patient data with a direct corporate rival.

Graph-Constrained Coalition Formation (GCCF) solves this computational and practical dilemma by overlaying a network topology onto the multi-agent system. In this framework, agents are nodes in a graph, and edges represent permissible interactions. A coalition is valid if and only if it satisfies a structural constraint—most commonly, that its members form a connected subgraph.

By grounding cooperation in network topology, this approach simultaneously models real-world limitations and exposes hidden "islands of tractability" that make otherwise impossible optimization problems solvable.

The Double-Edged Sword of Connectivity

Restricting coalitions to connected subgraphs changes the mathematical landscape in two opposing ways: it drastically prunes the search space, but it introduces complex topological dependencies.

1. Pruning the Search Space

From an engineering perspective, graph constraints are a powerful filter. By throwing out any group of agents that lack a direct or indirect communication path, algorithms can bypass billions of irrelevant combinations.

For instance, in social ridesharing systems, finding optimal carpools is highly complex. As shown by Alessandro Farinelli et al. in Sharing Rides with Friends: A Coalition Formation Algorithm for Ridesharing, forcing carpoolers to be connected through an underlying social network filters out socially infeasible groupings. This structural pruning allows optimization algorithms to scale to thousands of agents, providing high-quality solutions in minutes.

2. The Complexity Paradox

While connectivity constraints help prune the search space for optimization, they make proving group stability or fairness significantly harder. In a standard hedonic game (where players only care about who is in their own coalition), checking if an arrangement is stable is already difficult. When you add a graph constraint, you marry combinatorial preference matching with graph-theoretic connectivity.

Consider what happens when a disgruntled agent wants to leave their current team to join another. In an unconstrained game, they simply switch sides. In a graph-constrained game, their departure might break the remaining team into disconnected pieces, violating the connectivity rules.

As explored by Edith Elkind et al. in Hedonic Games with Graph-restricted Communication, while acyclic networks (trees) guarantee that stable partitions exist and can be found efficiently, finding stable outcomes like the Core or Nash stability remains computationally hard even on simple "star" graphs. Similarly, the authors of Group Activity Selection with Few Agent Types demonstrate that requiring activity groups to form connected subgraphs introduces severe computational hurdles, even when the social network structure is highly restricted.

Why Tree-Like Structures Unlock Tractability

If general graphs introduce a paradox of complexity, why does this research direction work? The answer lies in structural parameters like treewidth, which measures how closely a graph resembles a tree.

When an interaction network has a bounded treewidth, it means the complex web of agent dependencies can be decomposed into a tree-like hierarchy of small node clusters. This structural property allows researchers to deploy dynamic programming to solve otherwise intractable problems in linear or polynomial time.

   [General Graph]                  [Tree Decomposition]
    A --- B --- C                       [ A, B, D ]
    |   / |   / |                            |
    |  /  |  /  |                       [ B, C, D ]
    | /   | /   |                            |
    D --- E --- F                       [ C, E, F ]
(Complex cycles make global          (No cycles: decisions flow
 optimization NP-hard)               linearly via dynamic programming)

To understand why this works intuitively, imagine trying to partition a network of agents into optimal teams. In a graph with many overlapping cycles, a decision made on one side of the network ripples through the cycles and constrains decisions on the other side, forcing you to consider the entire network simultaneously.

But in a tree, there are no cycles. If you cut an edge, the graph splits into two completely independent subproblems. You can start at the leaves of the tree, calculate the optimal local coalitions for those small groups, and pass those optimized summaries up to the parent nodes.

This mechanism is the engine behind several key breakthroughs in the field:

Beyond Connectivity: Alternative Graph Topologies

While ensuring that agents can communicate via connected subgraphs is the most common framing, graph constraints can also enforce other relational rules, such as non-competition or absolute trust.

For example, in cross-silo federated learning, organizations want to collaborate to train machine learning models, but they must avoid sharing advantages with direct competitors. To solve this, Mengmeng Chen et al. in Free-Rider and Conflict Aware Collaboration Formation for Cross-Silo Federated Learning invert the problem framing. Instead of looking for connected subgraphs on a cooperation network, they construct a competition graph where edges represent rivalries. By restricting coalition formation to maximal cliques in the inverse of this competition graph, they mathematically guarantee that the largest possible collaborative groups are formed without ever placing two rivals in the same team.

Whether the goal is to optimize ridesharing routes, fairly divide land parcels, or coordinate distributed sensors, Graph-Constrained Coalition Formation provides a mathematically rigorous way to map real-world relationships directly into game-theoretic models. By replacing abstract, unconstrained action spaces with concrete network topologies, it turns intractable combinatorial nightmares into structured, localized problems that can be solved efficiently.

Key Foundational Work

Coalitional Structure Generation in Skill Games (2010) — contributed 2 concept elements to this direction.
Complexity of coalition structure generation (2011) — contributed 1 concept elements to this direction.
Social Distance Games (2011) — contributed 1 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_graph_constrained_coalition_formation_fbde2a41,
  title = {graph-constrained coalition formation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-constrained-coalition-formation/rdr_fbde2a41c94e4d8480b83cd1ae53d541},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_constrained_coalition_formation_fbde2a41_v1,
  title = {graph-constrained coalition formation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-constrained-coalition-formation/rdr_fbde2a41c94e4d8480b83cd1ae53d541/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake