📖
Approximating Nash Equilibria in Finite-Horizon Multi-Adversarial Team Markov Games
Prasanna Maddila, Sabbadin Régis, Meritxell Vinyals

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

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Approximating Nash Equilibria in Finite-Horizon Multi-Adversarial Team Markov Games
Author / Organization Prasanna Maddila, Sabbadin Régis, Meritxell Vinyals
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2026
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-128949
Original Source Link Visit Source Page on hal.science »