Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria
Preprint
Abstract
The works of (Daskalakis et al., 2009, 2022; Jin et al., 2022; Deng et al., 2023) indicate that computing Nash equilibria in multi-player Markov games is a computationally hard task. This fact raises the question of whether or not computational intractability can be circumvented if one focuses on specific classes of Markov games. One such example is two-player zero-sum Markov games, in which efficient ways to compute a Nash equilibrium are known. Inspired by zero-sum polymatrix normal-form games (Cai et al., 2016), we define a class of zero-sum multi-agent Markov games in which there are only pairwise interactions described by a graph that changes per state. For this class of Markov games, we show that an $\epsilon$-approximate Nash equilibrium can be found efficiently. To do so, we generalize the techniques of (Cai et al., 2016), by showing that the set of coarse-correlated equilibria collapses to the set of Nash equilibria. Afterwards, it is possible to use any algorithm in the literature that computes approximate coarse-correlated equilibria Markovian policies to get an approximate Nash equilibrium.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Independent and Decentralized Learning in Markov Potential GamesIEEE Transactions on Automatic Control, 2025
- Gradient Play in Stochastic Games: Stationary Points, Convergence, and Sample ComplexityIEEE Transactions on Automatic Control, 2024
- On the complexity of computing Markov perfect equilibrium in general-sum stochastic gamesNational Science Review, 2022
- Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning2022
- Grandmaster level in StarCraft II using multi-agent reinforcement learningNature, 2019
- Mastering the game of Go without human knowledgeNature, 2017
- Heads-up limit hold’em poker is solvedScience, 2015
- Economic Networks: The New ChallengesScience, 2009
- Cooperative Multi-Agent Learning: The State of the ArtAutonomous Agents and Multi-Agent Systems, 2005
- Nonlinear programming and stationary equilibria in stochastic gamesMathematical Programming, 1991