Robust Constrained Markov Games: Multi-Agent Decision-Making under Model Uncertainty and Constraints

Abstract

Multi-agent decision-making under both uncertainty and constraints is a central challenge in safety-critical domains such as autonomous driving, where agents must coordinate in uncertain environments while ensuring feasibility with respect to safety and resource limits. However, there is limited theoretical and practical work that addresses this challenge. Therefore, we introduce a Robust Constrained Markov Game (RCMG), the first multi-agent framework that simultaneously captures adversarial transition uncertainty and cost constraints. We further propose a solution concept, the Robust and Feasible Nash Equilibrium (RFNE), and a principled relaxation that yields a tractable surrogate upper bound to the intractable problem of computing an exact RFNE. This surrogate enables both a fixed-point existence proof via Kakutani’s theorem and a decentralized algorithm that alternates robust dynamic programming with Lagrangian dual updates. In settings where the relaxation is tight, the method provably recovers an exact RFNE. A grid-world experiment illustrates consistency with the theoretical results and highlights the viability of RCMGs as a foundation for reliable multi-agent decision-making under uncertainty and constraints.