Who Needs to Know? Minimal Knowledge for Optimal Coordination
This work addresses the challenge of minimal knowledge requirements for coordination in AI and multi-agent systems, offering a novel theoretical framework with practical efficiency gains.
The paper tackles the problem of identifying strategically relevant versus irrelevant information for optimal coordination in cooperative games, showing that this dichotomy has a compact representation and can be efficiently computed via a Bellman backup operator, with algorithms applied to Overcooked environments and found to be significantly more efficient than baselines.
To optimally coordinate with others in cooperative games, it is often crucial to have information about one's collaborators: successful driving requires understanding which side of the road to drive on. However, not every feature of collaborators is strategically relevant: the fine-grained acceleration of drivers may be ignored while maintaining optimal coordination. We show that there is a well-defined dichotomy between strategically relevant and irrelevant information. Moreover, we show that, in dynamic games, this dichotomy has a compact representation that can be efficiently computed via a Bellman backup operator. We apply this algorithm to analyze the strategically relevant information for tasks in both a standard and a partially observable version of the Overcooked environment. Theoretical and empirical results show that our algorithms are significantly more efficient than baselines. Videos are available at https://minknowledge.github.io.