Approximating Nash Equilibria in Finite-Horizon Multi-Adversarial Team Markov Games

Prasanna Maddila, Régis Sabbadin, Meritxell Vinyals
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4232-4251, 2026.

Abstract

Multi-Adversarial Team Games (MATGs) extend the canonical normal-form framework of von Stengel and Koller – where a team of players sharing a common objective but unable to coordinate faces a single adversary - to settings involving multiple independent adversaries. From an algorithmic perspective, MATGs are notable as one of the few game classes admitting polynomial-time algorithms for computing $\varepsilon$-{Nash} equilibria. However, no complexity or algorithmic guarantees are known for the finite-horizon Markovian generalisation of MATGs. This paper establishes positive and negative results for approximating \emph{non-stationary} {Nash} equilibria in finite-horizon Multi-Adversarial Team {Markov} Games. Specifically, we provide a polynomial-time algorithm for the single-adversary case, prove PPAD-hardness for the multiple-adversary case and present a polynomial-time algorithm for the multiple-adversary setting with additive transitions. We also provide an empirical evaluation of the proposed algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-maddila26a, title = {Approximating {Nash} Equilibria in Finite-Horizon Multi-Adversarial Team {Markov} Games}, author = {Maddila, Prasanna and Sabbadin, R\'{e}gis and Vinyals, Meritxell}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4232--4251}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/maddila26a/maddila26a.pdf}, url = {https://proceedings.mlr.press/v337/maddila26a.html}, abstract = {Multi-Adversarial Team Games (MATGs) extend the canonical normal-form framework of von Stengel and Koller – where a team of players sharing a common objective but unable to coordinate faces a single adversary - to settings involving multiple independent adversaries. From an algorithmic perspective, MATGs are notable as one of the few game classes admitting polynomial-time algorithms for computing $\varepsilon$-{Nash} equilibria. However, no complexity or algorithmic guarantees are known for the finite-horizon Markovian generalisation of MATGs. This paper establishes positive and negative results for approximating \emph{non-stationary} {Nash} equilibria in finite-horizon Multi-Adversarial Team {Markov} Games. Specifically, we provide a polynomial-time algorithm for the single-adversary case, prove PPAD-hardness for the multiple-adversary case and present a polynomial-time algorithm for the multiple-adversary setting with additive transitions. We also provide an empirical evaluation of the proposed algorithms.} }
Endnote
%0 Conference Paper %T Approximating Nash Equilibria in Finite-Horizon Multi-Adversarial Team Markov Games %A Prasanna Maddila %A Régis Sabbadin %A Meritxell Vinyals %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-maddila26a %I PMLR %P 4232--4251 %U https://proceedings.mlr.press/v337/maddila26a.html %V 337 %X Multi-Adversarial Team Games (MATGs) extend the canonical normal-form framework of von Stengel and Koller – where a team of players sharing a common objective but unable to coordinate faces a single adversary - to settings involving multiple independent adversaries. From an algorithmic perspective, MATGs are notable as one of the few game classes admitting polynomial-time algorithms for computing $\varepsilon$-{Nash} equilibria. However, no complexity or algorithmic guarantees are known for the finite-horizon Markovian generalisation of MATGs. This paper establishes positive and negative results for approximating \emph{non-stationary} {Nash} equilibria in finite-horizon Multi-Adversarial Team {Markov} Games. Specifically, we provide a polynomial-time algorithm for the single-adversary case, prove PPAD-hardness for the multiple-adversary case and present a polynomial-time algorithm for the multiple-adversary setting with additive transitions. We also provide an empirical evaluation of the proposed algorithms.
APA
Maddila, P., Sabbadin, R. & Vinyals, M.. (2026). Approximating Nash Equilibria in Finite-Horizon Multi-Adversarial Team Markov Games. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4232-4251 Available from https://proceedings.mlr.press/v337/maddila26a.html.

Related Material