Graph Representations for Multi Agent Synergy and Coordination

16 concepts11 papers1 proposal

When multiple agents must work together, the space of possible collaborations grows exponentially. If you have a pool of $N$ agents, finding the optimal team structure requires searching through an astronomical number of possible partitions. Similarly, if you are training an artificial intelligence agent to cooperate with unfamiliar partners, evaluating its compatibility against every possible strategy becomes an intractable problem.

To overcome this combinatorial explosion, a powerful paradigm has emerged: mapping multi-agent interactions to graph structures. By representing individual agents, roles, or strategies as nodes, and their mutual synergies, preferences, or payoffs as edges, we can compress exponential search spaces into tractable, quadratic representations. This graph-theoretic lens allows researchers to leverage structural network properties—such as independent sets, topology bounds, and node centrality—to optimize team formation, guarantee stability, and achieve robust zero-shot coordination.

Compressing Coalitions into Pairwise Edges

In traditional cooperative game theory, the utility of a team or coalition is defined by a characteristic function that assigns a value to every possible subset of agents. Because enumerating these values requires exponential space, researchers use graphs to compactly encode how agents interact.

The intuition behind this approach is that total group utility can often be broken down into the sum of local, pairwise relationships. Kohli et al. formalize this by modeling agents as nodes in a graph where edges represent pairwise synergies. A positive edge weight indicates beneficial cooperation, while a negative weight represents conflict. Instead of evaluating an arbitrary black-box function for every subset, the utility of any team is simply computed as the sum of the edge weights within that group.

[Agent A] <--- (+5 Synergy) ---> [Agent B]
   \                                /
    \--- (-3 Conflict) ---> [Agent C]

This pairwise decomposition makes it possible to reason about the global stability of groups. For instance, Branzei et al. introduce coalitional affinity games, where directed edge weights quantify how much an agent likes or dislikes another. By structuring preferences as a graph, the authors prove that the "stability gap"—the potential loss in social welfare when forcing a group to be stable rather than optimal—is strictly bounded by a factor of two for symmetric relationships.

Reducing interactions to pairwise graph edges also provides a powerful heuristic for practical engineering challenges. In complex computer games, Price et al. map functional character roles (such as Defenders or Strikers) to a synergy graph. By using empirical trials to weight the edges between roles, they successfully prune millions of character combinations into a manageable search space.

However, relying on pairwise graphs also introduces vulnerabilities to strategic behavior. When agents must report their own relationships, the underlying network structure can be manipulated. Barr et al. demonstrate how strategic agents can misreport their graph connections to manipulate team formation algorithms, highlighting the computational complexity of preventing such exploitation.

Exploiting Graph Topology for Tractability

Once a multi-agent system is mapped to a graph, the structural topology of the network can be exploited to solve otherwise NP-hard coordination and scheduling problems.

Consider the challenge of organizing group activities when participants care about the presence of their friends or enemies. Kerkmann et al. and Kerkmann et al. study altruism in coalition formation by encoding agent preferences as networks of friends and enemies. This abstraction simplifies complex preference profiles into a structural topology, allowing researchers to evaluate stability notions like the core or Nash stability using graph-theoretic properties.

Similarly, Eiben et al. tackle the Comprehensive Activity Selection problem by analyzing an "association graph" of social ties. They show that while grouping participants based on size preferences and social constraints is generally intractable, identifying specific structural properties within the association graph reveals clear boundaries where the problem becomes computationally tractable.

   [Action A]               [Action B]
       \                       /
        \--- (Conflict Edge) -/

This structural mapping is equally effective for physical asset coordination. In disaster response scenarios, Han et al. coordinate heterogeneous agents—such as UAVs, vehicles, and human workers—by constructing a weighted graph where nodes represent potential agent actions. Collaborative benefits are modeled as node weights, while conflicting operational constraints are represented as edges between them. By transforming a chaotic scheduling problem into a classic graph-theoretic problem—finding the maximum weight independent set—the authors enable real-time, optimal decision-making in post-disaster environments.

Even in mechanism design, graph structures provide a path to tractability. Lavi et al. model the private values of multiple principals hiring a common agent using correlation graphs. This graph-theoretic approach identifies specific alignment conditions under which welfare-maximizing, truth-telling contracts are guaranteed to exist.

Strategy Graphs and Centrality for Zero-Shot Coordination

The power of graph representations extends beyond static agent attributes into the dynamic space of agent behaviors. A premier example of this is Zero-Shot Coordination (ZSC), where an AI agent must successfully collaborate with a human or an unfamiliar AI partner without the luxury of prior communication or pre-established conventions.

To train an agent for ZSC, one must understand how a vast population of different strategies interact. Li et al. (2023) and Li et al. (2024) pioneer a framework that models an entire population of strategies as a directed graph. In this strategy graph, each node represents a distinct policy, and the edge weights reflect the expected cross-play payoff when two policies are paired together.

   [Strategy 1] --(High Payoff)--> [Strategy 2] (High Centrality / Globally Compatible)
        ^                               ^
        |                               |
   [Strategy 3] --(Low Payoff)----------/

Why is this representation so powerful? By treating a population of behaviors as a social network, researchers can apply standard network centrality measures—such as PageRank or Shapley values—to evaluate strategic compatibility:

  • Identifying Incompatibility: A node that exhibits low centrality signifies a strategy that is isolated or difficult for other policies to coordinate with, exposing a critical gap in the population's overall robustness.
  • Discovering Universal Partners: Conversely, a node with high centrality represents a strategy that occupies a highly compatible, central position in the strategy space. This strategy is a universally preferred partner because it yields high cooperative utility across a broad, diverse range of behaviors.

The Cooperative Open-ended Learning (COLE) framework developed by Li et al. (2023) leverages this insight. By mathematically profiling coordination patterns through node centrality, the framework iteratively identifies weak coordination gaps and drives the agent toward the center of the strategy graph. This ensures the agent becomes a universally compatible teammate, capable of seamless coordination with both novel AI policies and human partners.

This application of centrality to strategy spaces builds upon foundational insights into cooperative game structures. Procaccia et al. previously demonstrated that the complex web of interactions in cooperative games can be mapped into a signed graph by measuring how one agent's presence alters another's individual power (Shapley value). By viewing multi-agent systems through graph topology and centrality, modern AI frameworks can systematically navigate the intricate dynamics of human-AI collaboration.

Key Foundational Work

Coalitional Affinity Games and the Stability Gap (2009) — contributed 1 concept elements to this direction.
Team Formation with Heterogeneous Agents in Computer Games (2010) — 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_cooperative_centrality_4c429812,
  title = {cooperative centrality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cooperative-centrality/rdr_4c42981244bf47439189c8f5cde4c7c9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_cooperative_centrality_4c429812_v1,
  title = {cooperative centrality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cooperative-centrality/rdr_4c42981244bf47439189c8f5cde4c7c9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake