We study a new class of Markov games (MGs), \textit{Multi-player Zero-sum Markov Games} with {\it Networked separable interactions} (MZNMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define an MZNMG as a model where {the payoffs of the auxiliary games associated with each state are zero-sum and} have some separable (i.e., polymatrix) structure across the neighbors over some interaction network. We first identify the necessary and sufficient conditions under which an MG can be presented as an MZNMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses to the set of Markov Nash equilibrium (NE) in these games, in that the {product of} per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov \emph{stationary} CCE in infinite-horizon discounted MZNMGs is \texttt{PPAD}-hard, unless the underlying network has a ``star topology''. Then, we propose fictitious-play-type dynamics, the classical learning dynamics in normal-form games, for MZNMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov \emph{non-stationary} NE and provide finite-iteration guarantees for a series of value-iteration-based algorithms. We also provide numerical experiments to corroborate our theoretical results.

我们研究了一类新的马尔可夫博弈模型，即具有网络可分离相互作用的多人零和马尔可夫博弈，用于建模非合作多智体序贯决策中的局部交互结构。我们提出了多人零和马尔可夫博弈的必要和充分条件，并证明了在这些博弈中，马尔可夫粗相关均衡集合等同于马尔可夫纳什均衡集合。此外，我们提出了一种模拟正规形式博弈中的经典学习动态的方法，并在星形网络结构下证明了收敛性保证。最后，针对计算马尔可夫非稳态纳什均衡的难题，我们提供了一系列基于值迭代的算法，并通过数值实验验证了我们的理论结果。

多玩家零和马尔可夫网络分离交互博弈