Summary
Finding stable strategies, called Nash equilibria, in games with many players is usually very hard. Games where two players compete zero-sum have faster ways to find these strategies, but more complex multiplayer games have been tricky to solve efficiently. The authors study a special type of multiplayer game where many players interact in pairs and propose a new method for updating their strategies. Their method quickly converges to a stable solution, and importantly, this stability appears at the last step they compute, making it practical and reliable. This work extends known fast techniques from simple two-player games to more complex multiplayer scenarios.
Nash equilibriumMarkov gameszero-sumpolicy optimizationlast-iterate convergencemultiplicative weights updateentropy regularizationmulti-player gamesdynamic programminggame theory
Abstract
Solving Nash equilibria for general multi-player Markov games is computationally intractable, while two-player zero-sum Markov games admit fast last-iterate policy-optimization methods. Finite-horizon zero-sum networked separable Markov games occupy an important middle ground: they retain global competition structure through pairwise interactions, while preserving computational tractability of Nash equilibria (NE) in the full-information and known-transition setting. Existing algorithms for this class either proceed through equilibrium-collapse arguments for a simplified setting where a single controller determines the transition probability, or backward dynamic programming that relies on equilibrium solvers at each stage. However, the design and analysis of direct policy-update approaches remain inadequate. To address this issue, we propose the entropy-regularized optimistic multiplicative weights update (ER-OMWU), a complementary single-loop policy dynamic that updates players' policies symmetrically and returns an approximate NE in the last iteration. We provide a first last-iterate convergence analysis of policy dynamics in the games of interest: after $\widetilde{O}(1/ε)$ iterations, the returned policy is an $ε$-approximate Nash equilibrium. The result preserves the near-linear convergence rate achieved by policy optimization in two-player zero-sum Markov games, but extends the policy-dynamics viewpoint to a more complicated but structured multi-player setting.