Efficiently Computing Approximate Nash Equilibria in Multi-Adversarial Team Games

Adversarial Team Games (ATG), as introduced by von Stengel and Koller, model strategic interactions in which a team of agents – sharing a common objective but unable to coordinate their actions – faces a single adversary. While computing an exact Nash Equilibrium (NE) in ATGs has been shown to be CLS-complete, a fully polynomial-time approximation scheme (FPTAS) has been developed, enabling the efficient computation of approximate NE in time polynomial in both the natural parameters of the game and the inverse of the approximation error. However, existing results only apply to single-adversary scenarios, leaving the common case of multiple independent adversaries — prevalent in applications such as anti-poaching, robotic planning, and hider-seeker games — largely unexplored. This paper bridges this gap by introducing the Multi-Adversarial Team Game (MATG) framework, a natural generalization of ATGs to scenarios involving several independent adversaries. Our main contribution is to generalize techniques from the single-adversary setting to develop an FPTAS for computing NE in the more general class of MATGs. Beyond our theoretical contributions, we present the first empirical evaluation of this family of algorithms in both ATGs and MATGs, demonstrating the scalability to many adversaries.

Authors

• Prasanna Maddila Université de Toulouse, INRAE – MIAT
• Régis Sabbadin Université de Toulouse, INRAE – MIAT
• Meritxell Vinyals Université de Toulouse, INRAE – MIAT

Keywords

• Multi Adversarial Team Games
• Nash Equilibria
• FPTAS