2023/04/27 by Charles Jin, Zhang-Wei Hong, Jin, Charles +7
Computer Science · Social Sciences · #Access Control and Trust #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.2304.13957
openalex publication_date 2023/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.