Reproduce “Efficiently Computing Nash Equilibria in Adversarial Team Markov Games” on OpenResearch

About this paper

Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Vaggos Chatziafratis, Stelios Stavroulakis

This work introduces adversarial team Markov games, a new class that unifies two-player zero-sum and Markov potential games by modeling interactions where a team cooperates against an adversary. The paper presents IPGmax, the first polynomial-time algorithm for computing approximate stationary Nash equilibria in these games, achieving decentralized team play and polynomial complexity in all relevant game parameters.

Key insights

• An $\epsilon$-nearly stationary point of the team's objective function can be extended to an $O(\epsilon)$-approximate Nash equilibrium by constructing the adversary's policy via a carefully formulated linear program.
• The analysis leverages the Moreau envelope and the concept of $\epsilon$-nearly stationary points for weakly convex, non-smooth functions to prove convergence of IPGmax.
• The Arrow-Hurwicz-Uzawa constraint qualification (AHU-CQ) is applied to a Quadratic Nonlinear Program (Q-NLP) to establish KKT conditions, enabling the characterization of Lagrange multipliers as discounted state-action visitation measures for the adversary's best response.

Summary by alphaXiv.