  This work studies the problem of ad hoc teamwork in teams composed of agents
with differing computational capabilities. We consider cooperative multi-player
games in which each agent's policy is constrained by a private capability
parameter, and agents with higher capabilities are able to simulate the
behavior of agents with lower capabilities (but not vice-versa). To address
this challenge, we propose an algorithm that maintains a belief over the other
agents' capabilities and incorporates this belief into the planning process.
Our primary innovation is a novel framework based on capability type
structures, which ensures that the belief updates remain consistent and
informative without constructing the infinite hierarchy of beliefs. We also
extend our techniques to settings where the agents' observations are subject to
noise. We provide examples of games in which deviations in capability between
oblivious agents can lead to arbitrarily poor outcomes, and experimentally
validate that our capability-aware algorithm avoids the anti-cooperative
behavior of the naive approach in these toy settings as well as a more complex
cooperative checkers environment.
