# Self-Organized Polynomial-Time Coordination Graphs

arXiv: https://arxiv.org/abs/2112.03547 · HTML: https://mlsanity.com/paper/2112.03547/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 7 Dec 2021.

## Builds on (most cited first, 26 of 26)

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [TarMAC: Targeted Multi-Agent Communication](https://mlsanity.com/paper/1810.11187/) (2018)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [ROMA: Multi-Agent Reinforcement Learning with Emergent Roles](https://mlsanity.com/paper/2003.08039/) (2020)
- [RODE: Learning Roles to Decompose Multi-Agent Tasks](https://mlsanity.com/paper/2010.01523/) (2020)
- [Learning when to Communicate at Scale in Multiagent Cooperative and Competitive Tasks](https://mlsanity.com/paper/1812.09755/) (2018)
- [Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1702.08887/) (2017)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Off-Policy Multi-Agent Decomposed Policy Gradients](https://mlsanity.com/paper/2007.12322/) (2020)
- [Learning Nearly Decomposable Value Functions Via Communication Minimization](https://mlsanity.com/paper/1910.05366/) (2019)
- [Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.09207/) (2019)
- [Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2006.11438/) (2020)
- [How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction](https://mlsanity.com/paper/2001.11181/) (2020)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [Distributed Constraint Optimization Problems and Applications: A Survey](https://mlsanity.com/paper/1602.06347/) (2016)
- [The Emergence of Individuality](https://mlsanity.com/paper/2006.05842/) (2020)
- [Analysing Factorizations of Action-Value Networks for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1902.07497/) (2019)
- [Near-Optimal UGC-hardness of Approximating Max k-CSP_R](https://mlsanity.com/paper/1511.06558/) (2015)

## Built on by (most cited first, 15 of 15)

- [More Centralized Training, Still Decentralized Execution: Multi-Agent Conditional Policy Factorization](https://mlsanity.com/paper/2209.12681/) (2022)
- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [Non-Linear Coordination Graphs](https://mlsanity.com/paper/2211.08404/) (2022)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Semantically Aligned Task Decomposition in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.10865/) (2023)
- [Inferring Latent Temporal Sparse Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2403.19253/) (2024)
- [The Bandit Whisperer: Communication Learning for Restless Bandits](https://mlsanity.com/paper/2408.05686/) (2024)
- [Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.16606/) (2025)
- [Bandwidth-constrained Variational Message Encoding for Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2512.11179/) (2025)
- [Social Environment Design](https://mlsanity.com/paper/2402.14090/) (2024)
- [Action-Graph Policies: Learning Action Co-dependencies in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.17009/) (2026)
- [SDHN: Skewness-Driven Hypergraph Networks for Enhanced Localized Multi-Robot Coordination](https://mlsanity.com/paper/2504.06684/) (2025)
- [Do LLM-derived graph priors improve multi-agent coordination?](https://mlsanity.com/paper/2604.17191/) (2026)
- [SACHI: Structured Agent Coordination via Holistic Information Integration in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.08391/) (2026)
- [Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.17393/) (2026)

## Abstract (arXiv)

Coordination graph is a promising approach to model agent collaboration in multi-agent reinforcement learning. It conducts a graph-based value factorization and induces explicit coordination among agents to complete complicated tasks. However, one critical challenge in this paradigm is the complexity of greedy action selection with respect to the factorized values. It refers to the decentralized constraint optimization problem (DCOP), which and whose constant-ratio approximation are NP-hard problems. To bypass this systematic hardness, this paper proposes a novel method, named Self-Organized Polynomial-time Coordination Graphs (SOP-CG), which uses structured graph classes to guarantee the accuracy and the computational efficiency of collaborated action selection. SOP-CG employs dynamic graph topology to ensure sufficient value function expressiveness. The graph selection is unified into an end-to-end learning paradigm. In experiments, we show that our approach learns succinct and well-adapted graph topologies, induces effective coordination, and improves performance across a variety of cooperative multi-agent tasks.