Adversarial Team Games (ATG), as introduced by von Stengel and Koller, model strategic situations where a team of agents, sharing a common objective but unable to coordinate their actions, faces a single adversary. Recent advances have shown that computing an approximate Nash Equilibrium (NE) in ATGs is computationally tractable, establishing ATGs as one of the rare multi-agent game families where this holds. However, this tractability result is limited 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 addresses this gap by introducing the Multi-Adversarial Team Game (MATG) framework, a natural extension of ATGs to settings with multiple independent adversaries. Our main contribution is to prove that approximate NE computation remains tractable in this generalised setting. We achieve this by designing and analyzing a pseudo fully-polynomial time approximation scheme (pseudo-FPTAS) for computing NE in MATGs. Beyond our theoretical contributions, we provide the first implementation of this family of algorithms for NE computation in both ATGs and MATGs, demonstrating their empirical performance on a set of benchmark problems.

This article introduces a new model, Gaussian Factorial Explicit Duration Hidden Markov Model (G-F-ED-HMM), that overcomes two limiting assumptions of hidden Markov models by allowing for flexible choice of distributions for the sojourn time, introducing semi-Markov dynamics, and by explicitly modelling a multidimensional hidden state with factorial structure. The combination of these two extensions is relevant for the representation of complex dynamics that can occur in ecology as well as in signal analysis. We provide a novel Variational EM (VEM) algorithm for parameter estimation of a G-F-ED-HMM, which is computationally efficient because we choose a variational conditional distribution in the family of independent hidden chains. The consequence is that the VM step relies only on quantities related to a monochain hidden semi-Markov model, which are straightforward to compute. We illustrate the behaviour of the VEM algorithm on simulated data sets inspired from the problem of inferring the routes of migratory birds. These experiments demonstrate that our VEM algorithm recovers parameters with low error and performs faster than a Monte Carlo EM algorithm.