  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.
