# A Game-Theoretic Model and Best-Response Learning Method for Ad Hoc Coordination in Multiagent Systems

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2015.

## Built on by (most cited first, 30 of 44)

- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [Scaling Multi-Agent Reinforcement Learning with Selective Parameter Sharing](https://mlsanity.com/paper/2102.07475/) (2021)
- [A Survey of Ad Hoc Teamwork Research](https://mlsanity.com/paper/2202.10450/) (2022)
- [Generating Teammates for Training Robust Ad Hoc Teamwork Agents via Best-Response Diversity](https://mlsanity.com/paper/2207.14138/) (2022)
- [Mava: a research library for distributed multi-agent reinforcement learning in JAX](https://mlsanity.com/paper/2107.01460/) (2021)
- [Parameter Sharing with Network Pruning for Scalable Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/2303.00912/) (2023)
- [Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learning](https://mlsanity.com/paper/2302.02792/) (2023)
- [Optimal Behavior Prior: Data-Efficient Human Models for Improved Human-AI Collaboration](https://mlsanity.com/paper/2211.01602/) (2022)
- [Adaptive parameter sharing for multi-agent reinforcement learning](https://mlsanity.com/paper/2312.09009/) (2023)
- [ROTATE: Regret-driven Open-ended Training for Ad Hoc Teamwork](https://mlsanity.com/paper/2505.23686/) (2025)
- [Learning Task Embeddings for Teamwork Adaptation in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2207.02249/) (2022)
- [Ensemble Value Functions for Efficient Exploration in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.03439/) (2023)
- [Conditionally Optimistic Exploration for Cooperative Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2303.09032/) (2023)
- [Factorised Active Inference for Strategic Multi-Agent Interactions](https://mlsanity.com/paper/2411.07362/) (2024)
- [Partner Modelling Emerges in Recurrent Agents (But Only When It Matters)](https://mlsanity.com/paper/2505.17323/) (2025)
- [Communication-Efficient Desire Alignment for Embodied Agent-Human Adaptation](https://mlsanity.com/paper/2505.22503/) (2025)
- [Shapley Machine: A Game-Theoretic Framework for N-Agent Ad Hoc Teamwork](https://mlsanity.com/paper/2506.11285/) (2025)
- [Deep Reinforcement Learning for Multi-Agent Interaction](https://mlsanity.com/paper/2208.01769/) (2022)
- [Revisiting the Gumbel-Softmax in MADDPG](https://mlsanity.com/paper/2302.11793/) (2023)
- [CAMMARL: Conformal Action Modeling in Multi Agent Reinforcement Learning](https://mlsanity.com/paper/2306.11128/) (2023)
- [Unsupervised Partner Design Enables Robust Ad-hoc Teamwork](https://mlsanity.com/paper/2508.06336/) (2025)
- [Temporal Induced Self-Play for Stochastic Bayesian Games](https://mlsanity.com/paper/2108.09444/) (2021)
- [Simulation of Attacker Defender Interaction in a Noisy Security Game](https://mlsanity.com/paper/2212.04281/) (2022)
- [On Diagnostics for Understanding Agent Training Behaviour in Cooperative MARL](https://mlsanity.com/paper/2312.08468/) (2023)
- [Hierarchical Message-Passing Policies for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2507.23604/) (2025)
- [Learning Practical Communication Strategies in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.01288/) (2022)
- [Goals are Enough: Inducing AdHoc cooperation among unseen Multi-Agent systems in IMFs](https://mlsanity.com/paper/2310.17416/) (2023)
- [The Price of Pessimism for Automated Defense](https://mlsanity.com/paper/2409.19237/) (2024)
- [Constant-Memory Strategies in Stochastic Games: Best Responses and Equilibria](https://mlsanity.com/paper/2505.07008/) (2025)
- [From Grunts to Lexicons: Emergent Language from Cooperative Foraging](https://mlsanity.com/paper/2505.12872/) (2025)

## Abstract (arXiv)

The ad hoc coordination problem is to design an autonomous agent which is able to achieve optimal flexibility and efficiency in a multiagent system with no mechanisms for prior coordination. We conceptualise this problem formally using a game-theoretic model, called the stochastic Bayesian game, in which the behaviour of a player is determined by its private information, or type. Based on this model, we derive a solution, called Harsanyi-Bellman Ad Hoc Coordination (HBA), which utilises the concept of Bayesian Nash equilibrium in a planning procedure to find optimal actions in the sense of Bellman optimal control. We evaluate HBA in a multiagent logistics domain called level-based foraging, showing that it achieves higher flexibility and efficiency than several alternative algorithms. We also report on a human-machine experiment at a public science exhibition in which the human participants played repeated Prisoner's Dilemma and Rock-Paper-Scissors against HBA and alternative algorithms, showing that HBA achieves equal efficiency and a significantly higher welfare and winning rate.