Scalable and Safe Multi-Agent Coordination with Reconstructed Level-k Monte Carlo Tree Search

Multi-agent coordination without central control requires balancing safety and computational efficiency. We present a novel framework that transforms Level-k cognitive reasoning from a descriptive model of bounded rationality into a constructive planning algorithm for agent coordination. Our key insight is to replace Level-k reasoning's assumption of random Level-0 behavior with safety-oriented baselines where all agents compute conservative trajectories. Safety emerges naturally from the recursive structure: each reasoning level inherits and strengthens the safety margins of lower levels, creating cascading conservatism that prevents collisions without explicit constraints. Beyond ensuring safety, this hierarchical conservatism also provides a natural foundation for efficient planning. By integrating this reconstructed hierarchy with Monte Carlo Tree Search (MCTS), we achieve significant computational advantages through two complementary mechanisms: a Dynamic Interaction Graph that constrains candidate interactions and reduces complexity from exponential to linear in agent count, and Safety-aware Pruning within MCTS that eliminates infeasible actions before evaluation. We evaluate our framework on symmetric multi-agent intersections, demonstrating collision-free coordination and real-time efficiency across scenarios of varying complexity, highlighting its scalability and robustness for safety-critical planning.