Coordination Graphs

Each agent in the system is represented as a vertex (node) in the graph. The set of vertices defines the scope of the coordination problem. The graph's structure determines which agents must coordinate directly; agents not connected by an edge can act independently, assuming their payoff functions are separable.

An edge between two agents indicates a direct coordination dependency. This means the payoff (or cost) for the involved agents depends on their joint action. The global payoff function is the sum of these local payoff functions defined over edges (and potentially individual nodes). This factorization is what makes solving the global problem computationally tractable.

• Example: In a traffic network, an edge connects two autonomous vehicles at an intersection, as their joint action (go/wait) determines safety and flow.

Associated with each edge (and sometimes each node) is a local payoff function. This function maps the joint action of the connected agents to a real-valued utility or reward. The core assumption is that the global payoff is additive over these local functions. Formally, if agents are in states and take actions, the total payoff is: U_total = Σ_(i,j)∈E f_ij(a_i, a_j), where E is the set of edges.

The topology of the graph—whether it's a chain, tree, or a general graph with cycles—fundamentally impacts the complexity of finding the optimal joint action. Tree-structured graphs allow for efficient exact solution via message-passing algorithms like Variable Elimination or Max-Plus. Dense graphs with many cycles require approximate solutions, linking this component to Distributed Constraint Optimization Problems (DCOPs).

Coordination is achieved through distributed message-passing algorithms run on the graph. The Max-Plus algorithm is a canonical example, where agents iteratively exchange messages along edges containing the estimated utility of their actions. These messages propagate through the network, allowing agents to compute a locally optimal joint action that maximizes the global sum of payoffs without centralized control.

The output of the coordination process is a joint policy or a selected joint action for the agent team. In one-shot problems, this is a single action vector. In sequential decision-making (e.g., within a Dec-POMDP framework), the coordination graph is used to factor the Q-function, and the process repeats at each timestep to select a coordinated action based on the current state.

In automated fulfillment centers, robots must navigate shared aisles and coordinate pick-up/drop-off actions without collisions. A Coordination Graph models each robot's local payoff (e.g., shortest path) and pairwise dependencies (collision avoidance). Algorithms like Max-Plus or Variable Elimination compute a joint policy, allowing robots to negotiate right-of-way and optimize global throughput. This replaces centralized traffic control with scalable, decentralized decision-making.

A network of surveillance sensors (acoustic, visual, radar) must collectively track multiple targets. The global objective is tracking accuracy, but each sensor has limited field of view and battery. A Coordination Graph decomposes the problem:

• Node functions: Represent a sensor's local utility for focusing on a specific target.
• Edge functions: Represent the synergistic payoff when two sensors coordinate to triangulate a target's position. Distributed message passing allows sensors to autonomously negotiate focus, maximizing coverage while conserving energy.

At an unsignalized intersection, connected autonomous vehicles must negotiate crossing order. A Coordination Graph is constructed where:

• Each vehicle is a node with a local payoff (minimizing its own delay).
• An edge exists between any two vehicles on conflicting trajectories, with a penalty for simultaneous entry. Vehicles exchange messages to find the joint action (sequence) that maximizes the sum of all payoffs, ensuring safety and minimizing total wait time without a central traffic light.

In a smart grid, distributed energy resources (DERs) like solar panels and batteries must coordinate to balance supply and demand. A Coordination Graph connects neighboring DERs in the distribution network. The local payoff for a DER is its operational cost, while edges represent the cost of power flow between nodes. Using Distributed Constraint Optimization (DCOP) algorithms, DERs iteratively adjust their output to find a globally efficient configuration, preventing overloads and voltage violations.

In partially observable, imperfect-information games like poker, a team of AI players (e.g., in a tournament) can use a Coordination Graph to exploit opponents without explicit cheating. While each AI acts based on its private cards (local state), edges between teammate AIs can model coordinated betting strategies to manipulate the pot odds for shared opponents. The graph structure limits explicit communication to legally permissible signals, optimizing the team's expected value within the game's rules.

A hedge fund runs multiple autonomous trading agents, each specializing in a different asset class or strategy. To manage overall portfolio risk (e.g., avoid correlated exposures), a Coordination Graph is used. Nodes are agents with local profit objectives. Edges between agents impose a cost function that penalizes highly correlated trades. Through distributed optimization, agents adjust their positions to maximize aggregate risk-adjusted return, acting as a decentralized risk manager.

A Distributed Constraint Optimization Problem is the primary computational framework solved using Coordination Graphs. It models a scenario where:

• Multiple agents control individual variables.
• A global objective function must be optimized.
• Constraints exist between agents' variables, defining local payoff dependencies.

Coordination Graphs provide the graphical structure to represent these agent interactions, decomposing the complex global DCOP into manageable local subproblems for efficient solution finding.

A Dec-POMDP is a more general sequential decision-making model that subsumes the single-step DCOP framework. Key distinctions include:

• Sequentiality: Agents make a series of decisions over time.
• Partial Observability: Each agent has a limited, local view of the global state.
• Uncertainty: Actions have stochastic outcomes.

While Coordination Graphs excel in single-step cooperative DCOPs, solving Dec-POMDPs typically requires more complex algorithms like dynamic programming or approximate planning to handle the added dimensions of time and uncertainty.

Variable Elimination is a fundamental exact inference algorithm used to solve the coordination optimization problem defined by a Coordination Graph. The process is:

1. An elimination order for agents/variables is chosen.
2. Agents are eliminated sequentially. When an agent is eliminated, its neighboring agents compute a new joint payoff function that internalizes the optimal choice for the removed agent.
3. This creates a new, smaller graph.
4. After all eliminations, the optimal joint action is determined by back-substitution.

VE provides optimal solutions but can be computationally intensive for graphs with high treewidth.

The Max-Plus algorithm is an approximate, message-passing solution for Coordination Graphs, inspired by belief propagation. Its operation involves:

• Agents iteratively exchange messages along the edges of the graph.
• Each message encodes the sender's current view of the optimal action for the receiver.
• Agents update their local action preferences based on incoming messages.

Unlike Variable Elimination, Max-Plus is distributed and can run asynchronously. It is guaranteed to converge to the optimal solution on tree-structured graphs but provides high-quality approximations on general loopy graphs.

This is the core representational principle of a Coordination Graph. The technique involves:

• Taking a complex, global payoff function for the team, U(a1, a2, ..., an), which is exponential in the number of agents.
• Decomposing it into a sum of local payoff functions, each dependent on only a small subset of agents: U = Σ fᵢ(Dᵢ), where Dᵢ is the domain of function fᵢ.
• The edges in the Coordination Graph connect the agents within each local function's domain Dᵢ.

This decomposition is what makes efficient coordination possible, as optimization can focus on local interactions.

Coordination Graphs are closely linked to concepts in cooperative game theory, which studies how coalitions form and distribute value. Key connections include:

• The global payoff function represents the characteristic function of the grand coalition.
• The Shapley Value is a solution concept for fairly distributing the total payoff based on each agent's marginal contribution, which can be computed efficiently using the graph structure.
• The graph defines which agents can directly interact, influencing potential coalition structures.

This theoretical foundation provides formal notions of fairness and stability in the solutions derived from Coordination Graphs.