# Certifying cooperation: a novel approach to cooperative multi-agent task generation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 57 references that are in the map.
- First posted on arXiv 6 Sep 2026.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?](https://mlsanity.com/paper/2011.09533/) (2020)
- [A Study on Overfitting in Deep Reinforcement Learning](https://mlsanity.com/paper/1804.06893/) (2018)
- [Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance](https://mlsanity.com/paper/2304.11127/) (2023)
- [A Review of Cooperation in Multi-agent Learning](https://mlsanity.com/paper/2312.05162/) (2023)
- [Generalization in Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2202.00104/) (2022)
- [Zero-Incentive Dynamics: a look at reward sparsity through the lens of unrewarded subgoals](https://mlsanity.com/paper/2507.01470/) (2025)

## Abstract (arXiv)

A shared reward gives agents a common objective, but leaves open when, how and even whether they must cooperate to succeed. We address these questions in the Laser Learning Environment, a multi-agent path-finding environment where cooperation materializes as one agent blocking a laser to let a teammate pass safely. We represent these interactions through temporal cooperation graphs whose timed edges connect helpers to beneficiaries, define six cooperation profiles as overlapping graph predicates, and prove that every cooperative trajectory satisfies at least one. By encoding the environment dynamics and profile predicates as propositional formulae, we distinguish tasks that admit}a profile in some winning trajectory from those that require it in every winning trajectory within a specified horizon. Used as filters, these queries turn a random layout sampler into a generator of tasks with certified cooperation requirements. Experiments with five multi-agent reinforcement learning algorithms show that training diversity improves joint success on unseen tasks when cooperation-free solutions exist. When cooperation is required, greater diversity improves individual-agent exits, but joint success remains near zero. Across five profile-certified pools, final exit rates averaged over algorithms separate the pools into four statistically distinguishable levels but this ordering primarily reflects partial completion: policies collect rewards for individual exits but rarely exhibit the profile required for joint success. Our framework exposes this gap between rewarded partial completion and realized cooperation by certifying what cooperation successful completion requires and using temporal cooperation graphs to reveal what policies exhibit.