Promises as a Common Language for Zero-Shot Coordination

Zero-shot coordination (ZSC) requires agents to cooperate with unseen partners without prior joint training. Existing approaches typically seek behavioral diversity by varying training partners, environments, or action distributions, but such diversity does not necessarily yield behaviors that are useful for coordination. To address this limitation, we propose *Promise-based Partner Coordination* (PPC), which structures partner diversity through *promises*: explicit commitments to coordination-relevant behaviors. Inspired by Promise Theory, PPC leverages an LLM to generate executable promises from task descriptions and iteratively refine them through interaction-based feedback, enabling diverse coordination patterns without manually designing partner behaviors. We train a population of *Promisers* to follow different promises and a *Promisee* to coordinate with them based on their inferred trustworthiness. Across diverse ZSC environments, PPC substantially improves both self-play and cross-play performance over existing approaches and generalizes effectively to human partners. These results demonstrate the effectiveness of promises as a common language for coordination with unfamiliar partners.