Randomness is sometimes necessary for coordination

Computer Science > Artificial Intelligence [Submitted on 7 May 2026] Randomness is sometimes necessary for coordination Rohan Patil, Jai Malegaonkar, Henrik I. Christensen Full parameter sharing is standard in cooperative multi-agent reinforcement learning (MARL) for homogeneous agents. Under permutation-symmetric observations, however, a shared deterministic policy outputs identical action distributions for every agent, making role differentiation impossible. This failure can theoretically be resolved using symmetry breaking among anonymous identical processors, which requires randomness. We propose Diamond Attention, a cross-attention architecture in which each agent samples a scalar random number per timestep, inducing a transient rank ordering that masks lower-ranked peers from agent-to-agent attention while leaving task attention fully unmasked. This realizes a random-bit coordination protocol in a single broadcast round, and the set-based attention enables zero-shot deployment to teams of different sizes. We evaluate across three regimes that isolate when structured randomness matters. On the perfectly symmetric XOR game, our method achieves 1.0 success while all deterministic baselines plateau near 0.5. On control coordination tasks, a policy trained on N=4 generalizes zero-shot to N \in [2,8]. On SMACLite cross-scenario transfer, we achieve zero-shot transfer where standard baselines cannot transfer due to structural limitations. Furthermore, replacing the structured mask with standard dropout-based randomness results in a 0\% win rate, confirming that protocol-space structure, not stochastic noise, is the operative ingredient. this https URL Subjects: Artificial Intelligence (cs.AI); Robotics (cs.RO) Cite as: arXiv:2605.06825 [cs.AI]   (or arXiv:2605.06825v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.06825 Focus to learn more Submission history From: Rohan Patil [view email] [v1] Thu, 7 May 2026 18:27:15 UTC (909 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs cs.RO References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)