# Tackling Cooperative Incompatibility for Zero-Shot Human-AI Coordination

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 68 references that are in the map.
- First posted on arXiv 5 Jun 2023.

## Builds on (most cited first, 30 of 33)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [Population Based Training of Neural Networks](https://mlsanity.com/paper/1711.09846/) (2017)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [The Hanabi Challenge: A New Frontier for AI Research](https://mlsanity.com/paper/1902.00506/) (2019)
- [Open-Ended Learning Leads to Generally Capable Agents](https://mlsanity.com/paper/2107.12808/) (2021)
- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games](https://mlsanity.com/paper/1703.10069/) (2017)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Towards Playing Full MOBA Games with Deep Reinforcement Learning](https://mlsanity.com/paper/2011.12692/) (2020)
- [Maximum Entropy Population-Based Training for Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2112.11701/) (2021)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [Towards Open Ad Hoc Teamwork Using Graph-based Policy Learning](https://mlsanity.com/paper/2006.10412/) (2020)
- [Learning Zero-Shot Cooperation with Humans, Assuming Humans Are Biased](https://mlsanity.com/paper/2302.01605/) (2023)
- [Cooperative Open-ended Learning Framework for Zero-shot Coordination](https://mlsanity.com/paper/2302.04831/) (2023)
- [Honor of Kings Arena: an Environment for Generalization in Competitive Reinforcement Learning](https://mlsanity.com/paper/2209.08483/) (2022)
- [Evaluating the Robustness of Collaborative Agents](https://mlsanity.com/paper/2101.05507/) (2021)
- [PECAN: Leveraging Policy Ensemble for Context-Aware Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2301.06387/) (2023)
- [Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems](https://mlsanity.com/paper/2102.07659/) (2021)
- [Order Matters: Agent-by-agent Policy Optimization](https://mlsanity.com/paper/2302.06205/) (2023)
- [Generalization in Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2202.00104/) (2022)
- [A Generalised Method for Empirical Game Theoretic Analysis](https://mlsanity.com/paper/1803.06376/) (2018)
- [Generating and Adapting to Diverse Ad-Hoc Cooperation Agents in Hanabi](https://mlsanity.com/paper/2004.13710/) (2020)
- [Heterogeneous Multi-agent Zero-Shot Coordination by Coevolution](https://mlsanity.com/paper/2208.04957/) (2022)
- [A General Learning Framework for Open Ad Hoc Teamwork Using Graph-based Policy Learning](https://mlsanity.com/paper/2210.05448/) (2022)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [PantheonRL: A MARL Library for Dynamic Training Interactions](https://mlsanity.com/paper/2112.07013/) (2021)

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

- [ProAgent: Building Proactive Cooperative Agents with Large Language Models](https://mlsanity.com/paper/2308.11339/) (2023)
- [ZSC-Eval: An Evaluation Toolkit and Benchmark for Multi-agent Zero-shot Coordination](https://mlsanity.com/paper/2310.05208/) (2023)
- [Virtual Agent Economies](https://mlsanity.com/paper/2509.10147/) (2025)
- [Mutual Theory of Mind in Human-AI Collaboration: An Empirical Study with LLM-driven AI Agents in a Real-time Shared Workspace Task](https://mlsanity.com/paper/2409.08811/) (2024)
- [Leveraging Dual Process Theory in Language Agent Framework for Real-time Simultaneous Human-AI Collaboration](https://mlsanity.com/paper/2502.11882/) (2025)
- [Aligning Individual and Collective Objectives in Multi-Agent Cooperation](https://mlsanity.com/paper/2402.12416/) (2024)
- [Autonomous Goal Detection and Cessation in Reinforcement Learning: A Case Study on Source Term Estimation](https://mlsanity.com/paper/2409.09541/) (2024)
- [Who is Helping Whom? Analyzing Inter-dependencies to Evaluate Cooperation in Human-AI Teaming](https://mlsanity.com/paper/2502.06976/) (2025)
- [Efficient Generation of Diverse Cooperative Agents with World Models](https://mlsanity.com/paper/2506.07450/) (2025)
- [CoWork-X: Experience-Optimized Co-Evolution for Multi-Agent Collaboration System](https://mlsanity.com/paper/2602.05004/) (2026)
- [AT-Drone: Benchmarking Adaptive Teaming in Multi-Drone Pursuit](https://mlsanity.com/paper/2502.09762/) (2025)
- [Multi-Robot Open Adaptive Teaming Across Unseen Environments, Partners, and Scales](https://mlsanity.com/paper/2607.04972/) (2026)

## Abstract (arXiv)

Securing coordination between AI agent and teammates (human players or AI agents) in contexts involving unfamiliar humans continues to pose a significant challenge in Zero-Shot Coordination. The issue of cooperative incompatibility becomes particularly prominent when an AI agent is unsuccessful in synchronizing with certain previously unknown partners. Traditional algorithms have aimed to collaborate with partners by optimizing fixed objectives within a population, fostering diversity in strategies and behaviors. However, these techniques may lead to learning loss and an inability to cooperate with specific strategies within the population, a phenomenon named cooperative incompatibility in learning. In order to solve cooperative incompatibility in learning and effectively address the problem in the context of ZSC, we introduce the Cooperative Open-ended LEarning (COLE) framework, which formulates open-ended objectives in cooperative games with two players using perspectives of graph theory to evaluate and pinpoint the cooperative capacity of each strategy. We present two practical algorithms, specifically algo and algoR, which incorporate insights from game theory and graph theory. We also show that COLE could effectively overcome the cooperative incompatibility from theoretical and empirical analysis. Subsequently, we created an online Overcooked human-AI experiment platform, the COLE platform, which enables easy customization of questionnaires, model weights, and other aspects. Utilizing the COLE platform, we enlist 130 participants for human experiments. Our findings reveal a preference for our approach over state-of-the-art methods using a variety of subjective metrics. Moreover, objective experimental outcomes in the Overcooked game environment indicate that our method surpasses existing ones when coordinating with previously unencountered AI agents and the human proxy model.