Approximating Nash Equilibria in Finite-Horizon Multi-Adversarial Team Markov Games
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.
hal.science)
← / → 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 » |