Chanwoo Park, Massachusetts Institute of Technology (MIT) 

Abstract:

We introduce a new class of  Markov games (MGs), Multi-player Zero-sum Markov Games with networked local 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 have some separable structure among 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 that the per-state marginalization of the former for each player yields the latter. Furthermore,  we show that finding approximate Markov stationary  CCE  in gamma-discounted infinite-horizon MZNMGs is PPAD-hard, unless the underlying network has a "star shape". 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 the star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov non-stationary NE and provide finite-iteration guarantees for an algorithm based on optimistic multiplicative weight updates. We also provide numerical experiments to corroborate our theoretical results.