Multi-Player Zero-Sum Markov Games with Networked Separable Interactions
Authors: Chanwoo Park
Kaiqing Zhang
Asuman E. Ozdaglar
Venue: NeurIPS 2023 poster (2023)
Keywords: Markov Games
Local Interaction
PPAD-Hardness
Fictitious Play
TL;DR: A new class of Markov Game with networked separable interaction.

Abstract: We study a new class of  Markov games, \textit{(multi-player) zero-sum Markov Games} with {\it Networked separable interactions} (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG 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 a zero-sum NMG, 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 zero-sum NMGs 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 zero-sum NMGs, 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.

Multi-Player Zero-Sum Markov Games with Networked Separable Interactions
Chanwoo Park
Kaiqing Zhang? University of Maryland, College Park kaiqing umd.edu
Asuman Ozdaglar MIT asuman @ mit..eco edu
MIT spark97@mit..dd
Abstract
We study new class of Markov games, (multi-player) zero-sum Markov Games with Networked separable interactions (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as model where the payoff's of the auxiliary games associated with each state 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 MG can be presented as a zero-sum NMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses the that the product of per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov stationary CCE infinite-horizon discounted zero-sum NMGs is PPAD-hane hard, unless the underlying dynamics,
Markov Nash equilibrium (NE) in these games, in
network has "star topology". Then, we propose fictitious-play the classical learning dynamics in normal-form games, for zero-sum NMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus computing a Markov non con-ttationary NE and provide finite-iteration guarantees for a series of value-iteration- based algorithms. We also provide numerical experiments corroborate our theoretical results.
Introduction
Nash Equilibrium (NE) has been broadly used as a solution concept in game theory, since the seminal works of 21 Perhaps equally important, NE is also deeply rooted in the prediction and analysis of learming dynamics in multi-agent strategic environments: it may appear as a natural outcome of
many non-equilibrating learning processes of multiple agents interacting with each other [3] 4 A prominent example of such learning processes is fictitious play (FP) [5] 6). in which myopic agents estimate the opponents' play using history, and then choose a best-response action (based on their payoff matrix) against this estimate, as if the opponents use it as their stationary strategy. The focus of these studies has initially been on the convergence to NE in zero-sum games (see [5] 6 and also 774,, and in games with aligned objective (identical-intee -intrreell and potential games, see (8). Since then, FP has been shown converge to NE in more important classes of games, including 2xn games 10, "one-against-all"" games [11). and zero-sum polymatrix games [12] justifying the prediction games.
power NE in learning
Some of these results have recently been extended to the stochastic game (also known as the Markov game (MG) setting, model for multi-agent sequential decision-making with state transition dynamics, first introduced in [13.. In particular, [14] [5]
18] have studied best- best-response-tyee learning dynamics in two-player zero-sum MGs. and 99 have studied that in multi player
16
17
$ Allhaaettcca order.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

idettical-interest interestt games. Following the same path as studying matrix games, one natural question arises: Are there other classes of MGs beyond two-player zero-sum and identical interest cases that allow natural learning dynamics, e-g. fictitious play, to justify NE as the long-run emerging outcome?
On the other end of the spectrum, it is well-known that for general-sum normal-form games, the special case of MGs without the state transition dynamics, computing an NE is intractable [0] 21) Relaxed solution concepts as (coarse) correlated equilibrium ((C)CE) have thus been favored when it comes to equilibrium computation for general-sum, multi- games 22 [3. Encouragingly, when the interactions among players have some networked separable structure, also known as being polymatrix, computing NE may be made tractable even in multi-player settings. This has been instantiated in the seminal works [23] 24] in the normal-form game setting, which showed that any CCE collapses to the NE in such games when the payoffs are zero-sum. Thus, any algorithms that can efficiently compute the CCE in such games will lead to the efficient computation of the NE.
In fact, besides being of theoretical interest, multi-player zero-sum games with networked separable interactions also find a range of applications, including security games [24], fashion games [25] 26 27. and resource allocation problems (8 These examples, oftentimes, naturally involve some state transition that captures the dynamics of the evolution of the environment in practice. For example, in the security game, the protection level or immunity of a target increases as function of the number of past attacks, leading to a smaller probability of an attack on the target being successful. Hence, it is imperative to study such multi-player zero-sum games with state transitions. As eluded in the recent results (29] [0), such transition from stateless to stateful cases may not always yield straightforward and expected results, e.g., computing stationary CCE can be computationally intractable in stochastic games, in stark contrast to the normal-form case where CCE can be efficiently computed. This naturally prompts another question: Are there other types of (multi-player MGs that may circumvent the computational hardness of computing NE/CCE?
In an effort to address these two questions, we introduce a new class of Markov games caames-mmllll (mmllt--paarr) zero-sum Markov games with networked separable interactions (zero-sum NMGs). We summarize our contributions follows, and defer more detailed literature review to Appendix A
Contributions. First, we introduce new class of non- coopprateee Markov games: amulti-player) zero-sum MGs with Networked separable interactions (7ero-sum NMGs), wherein the payofts of the auxiliary- gamees associated with each state, i.e., the sum of instantaneous reward and expectation of any estimated state-value functions, possess the multi-player zero-sum and networked separable (i.e., polymatrix) structure as in [31 28 23, 24 for normal-form games, a strict generalization of the latter. We also provide structural results on the reward and transition dynamics of the game, as well as examples of this class of games. Specifically, for a Markov game to qualify as zero-sum NMG, if and only if its reward function has the zero-sum polymatrix structure, and its transition dynamics is an ensemble of multiple single-controller transition dynamics that are sampled randomly at each state (see Remark 3 for more details). This transition dynamics covers the common ones in the MG literature, including the single-controller and tum-basedd dynamics. Second, we show that Markov CCE and Markov NE collapse in that the product of per-state marginal distributions of the former yields the latter, making it sufficient to focus on the former in equilibrium computation. We then show the PPAD-hardness [32] of computing the Markov stationary equilibrium, a natural solution concept in infinite-horizon discounted MGs, unless the underlying network has a star-topology. This is in contrast to the normal-form case where CCE is always computationally tractable. Third, we study the fictitious-play property g of zero-sum NMGs, showing that the fictitious-play dynamics [6 19 converges to the Markov stationary NE, for zero-sum NMGs with a star-shaped network structure. Finally, in light of the hardness of computing stationary equilibria, we develop a series of value-iteration- based algorithms for computing a Markov non-stationary NE of zero-sum NMGs, with fnite-iteration guarantees. We also provide numerical experiments to corroborate our theoretical results in Section G interaction structure in non-cooperative Markov games.
We hope our results serve as a starting point for studying this networked separable
Notation. For real number e, we use (c)+ to denote max 0}. For an event E, we use 1(E) to denote the indicator function such that 1( = 1 if E is true, and (()) = otherwise. We define multinomial distribution with probability (wI) as Multinomial (asomial(((:))ee) ((w))...) We denote the uniform distribution over a set S as Unif(S). We denote the Bernoulli distribution with probability p as Bern(p). The sgn function is defined as sgn(x)) = 2 x 1(x 2 0) 1. The KL-divergence between two probability distributions y is denoted as KL g) = Ep(log(p/4)]] For graph G = (N, we denote the set of neighboring nodes of node i E A as E, (without including i). The maximum norm of matrix X E Rm denoted as mmxx is defined as ||X] == maxie(m) |
2

---

2
Preliminaries
2.1 Markov games
We define Markov game as tuple S,, (Pi)netm) (Tn,))ee(m) 7). where N = [n|] is the set of players, 8 is the state space with [S] = S, A, the action space for player with [Ai = A, and A = [1E A., H I oo is the length of the horizon, IP, S x A + (SS) captures the state transition dynamics at timestep h, Fh.s E [0, RR is the reward function for player i at timestep h, bounded by some R > 0, and y E (0, 1] is discount factor. An MG with finite horizon (H < oo) is also referred to as an episodic MG, while an MG with an infinite horizon (Hl = oo) and < 1 is referred to an infinite-horizon y-ddiscounted MG. When H = co, we will consider the transition dynamics and reward functions, denoted by IP and (ri)ieNs respectively, to be independent of h. Hereafter, we may use agent and player interchangeably.
Policy. Consider the stochastic Markov policy for player i, denoted by T₁ as n; == {Th, S + A(A.)) A joint Markov policy is a policy л == {TH, S A (A)))) where TA S + A(A) decides the joint action of all players that can be potentially correlated. A joint Markov policy is product Markov policy if T. :S - ILE (A,) for all h E [H] and denoted as т = T1 X T2 x x...X x nn- When the policy is independent of h. the policy is called stationary policy. We let a denote the joint action of all agents at timestep h. Unless otherwise noted, we will work with Markov policies throughout. We denote x xss) E (AA) as the joint policy at state E S.
Value function. For player i, the value function under joint policy π. at timestep h and state 5% is defined (s)) == E Ew=hh Th "N'""rr' "< ax:) sn], which denotes the expected cumulative reward for player at step h all players adhere to policy и. We also define (p) == Ex Vo,,())) for some state distribution p E ASS). We denote the Q-function for the i-th player under policy ग, at step h and state 8h as (s,, an) =- E. Eh > (she, axd) Sh, anl, which determines the expected cumulative reward for the i-th player at step h, when starting from the state-action pair (sh, as)) For the anfinie-hhorizn discounted setting, we also use V."t and Q, to denote VT, and Q7, for short, respectively.
Approximate equilibrium. Define an c-approximate Markov perfect Nash equilibrium as a product policy ग, which satisfies max maX (V (Viii" all p E A(S) and h E [H], where The represents the marginalized policy of all players ex- cept player i. Define an e-approximate Markov coarse correlated equilibrium as a joint policy T, which satisfies maxeN
(pp) (p) (P)( S c for
( (V '(p) (p), S c <for all p A(S) and h [M]. In the infinite-horizon setting, they can be equivalently defined as satisfying max,es max E. (V: (s)) S e. If the above conditions only hold for certain and = 1, we refer to them as Markov non-perfect NE and CCF, respectively. Unless otherwise noted, we hereafter focus Markov perfect equilibria, and sometimes refer to them simply as Markov equilibria when it is clear from the context. In the infinite-horizon setting, if additionally, the policy is stationary, then they are referred to a Markov stationary NE and CCE, respectively.
2.2 Multi-player zero-sum games with networked separable interactions
As generalization of two-player zero-sum matrix games, amulti-player zero-sum polymatrix games have been introduced in [31 28, 23 244.. A polymatrix game, also known as a separable network game is defined by a tuple (G (N, E,E,), = lli A., (rim))t.fee.)). Here, G is an undirected connected graph where . = [n] denotes the set of players and E, S W x N denotes the set of edges describing the rewards' networked structures, where the graph neighborhoods represent the interactions among players. For each edge, two-player game is defined for players i and j. with action sets A; and Aj. and reward functions ri.j : A, x Aj - IR and similarly for rj,g- The reward (a:)eeN E Ih A, is calculated the sum of the rewards
for player for a given joint action for all edges involving player i, that is, ra(a) Σ DEE, Fe,saa az). To be consistent with our terminology later, hereafter, we also refer to such games as (multi- muulti-player) Games with Networked separable interactions (NGs).
In a zero-sum polymatrix game (i.e., a (multi-playen) zero-sum Game with Networked separable interactions (zero-sum NG), the sum of rewards for all players at any joint action (at)seN IKE A, equals zero, i.e.. ΣiEN Tz(a)= = O. One can define the policy of agent i, i.e., n, E A(A.), so that the agent takes actions by sampling o; ~ mT(-). Note that m; can be viewed as the reduced case of the policy defined in Section 2.1 when S = @ and H 1. The expected reward for player i
3

---

under can then be computed as:
ri(T):: E E H. GEA.iaEE,
mig ()) .!T.,,
(I)
E RRlAilEE IAil and Then in this TT)T E RE Id, We define r := (rl: 22. ,2....,,;)) ,T)T E REEx IAi I4.1, 0 for any policy æ. See more prominent application examples of zero-sum polymatrix games in 23 24
where r; denotes the matrix pi == (Ti,),.. ( 0... л: := (TT ,g....,,,J))
have F((x)
3 Multi-Player (Zero-Sum) MGs with Networked Separable Interactions
We now introduce our model of multi-player zero-sum MGs with networked separable interactions.
3.1 Definitions
Definition 1. An infinite-horizon 7-discounted MG is called a (multi-player) MG with Networked
sepurable interactions (NMG) characterized by a tuple (g = (N, Eq), S, A, P.P. (ri)seN, 7) if for any function V S - IR, defining Q (s, a) == ri(8, a) + 7 = PP(s' 8, V,a), there and undirected connected graph G (N, (N, such that Q (s. - QY (s, az) holds for every i E N, 8 S, a E A, where Eq. denotes the neighbors of player i induced by the edge set &g (without including i). When it is clear from the context, represent the NMG tuple simply as G (N,Eq).
exist set of functions Ej
A finite-horizon MG is called (multi-player) MG with Networked separable interactions if for any set of functions V == (Vohee(H- where V, : S - R. defining (8, = (h, a) + + Eves Pi(s') v.a))i+1(s"), there exist set of functions (2%, (e such that QK, a) = EjjEo (K, as a₂) holds for every E N, E S A (multi-player) NMG is called (multi-player) zero-sum MG with Networked separable interactions (zero-sum NMG) if additionally (g = (N, A = llee Ai, (Ti,(s)= == 2 (s) (s))(E)))))) forms a zero-sum NG for all 8 E S in the infinite-horizon 7-discounted case, or (g = (N, EQ), = forms a zero-sum NG for all 8 E S and E [H] in the
h E [M], a E A.
ThE A., (fn,s.5(8) (s) == (+)) finite-horizon case.
Regarding the assumption that the above conditions hold under any (set of) functions V, one may understand this structural requirement to inherit the polymatrix structure in the Markov game case. It is natural since {QY kEN would play the role of the payoff matrix in the normal- formal-frm& case, when value-(ierration based algorithms are used solve the MG. As our hope to exploit the networked structure in the payoff matrices to develop efficient algorithms for solving such MGs, we do not know a priori which value function estimate V will be encountered the algorithm update, the networked structure may easily break if we do not assume them to hold for all possible V. Moreover, such a definition easily encompasses the normal-form case, by preserving the polymatrix structure of the reward functions (when substituting V to be a zero function). Some alternative definition (see Remark 2 may not necessarily preserve the polymatrix structure of even the reward functions in a consistent way (see Section B.4 for a concrete example). We thus focus on Definition! []
which at least covers the polymatrix structure of the reduced case regarding only reward functions.
Indeed, such a networked structure in Markov games may be fragile. We now propose both sufficient and necessary conditions for the reward function's structure and the transition dynamics of the MG, to be an NMG. Here we focus on the infinite-horian For fiiie-hhoiizo cases, similar statement holds, which deferred to Appendix [B] We also defer the full statement and proof of the following result to Appendix B We first introduce the definition of decomposability and the set Nc. which will be used establishing the conditions. For a graph G = (W, we define No == {i (i,5) E & for all j E WV, which may be an empty set if no such node i exists.
discounted setting for a simpler exposition.
non-negative function / XIPI R+ (0) is decomposable with respect to set D + 0 if there exists a set of non-negative functions (fi)ieD with fa X + R+ U (0). such that f(x) = EieD fi(2z) holds for any x E x(P), A non-negative function f: XPP| + R U {0} is decomposable with respect to set D = 0, if there exists a non-negative constant fo such that f(x) fo holds for any e IPI,
Definition 2 (Decomposability).
4

---

Proposition 1. For a given graph 9 = (Q)) an MG S.A.P. (Ti)sEN: 7) with more than two players is an NMG with respect to G if and only if: (s) a;, decomposable with respect to &q for each i E E,, 8 E S, E Ai, i.e., ri a) = =E E5 Tiis (z,aa) (z) for a set of functions (raj(s, ai, ais") Dieea.. and (2) the transition dynamics P(s s,-) is decomposable with respect to the set No of this G. ie.., P(s' s.a) [0))=x) = (s s. for a set of functions (5' s. >.eNN if NC * W, or P(s' s, a) = (s |)) for some constant function (of a) F,(s'1s if NN D. Moreover, an MG qualifies as a zero-sum NMG if and only if it satisfies an additional condition: the NG, characterized by A, (rin)s)) (L)) ), is a zero-sum NG for all & E S. In the case of two players, every (zero-sum) Markov game becomes a (zero-sum) NMG.
Remark 1 (Stronger sufficient condition). We note that for an MG (N, (rilie Y), for every agent i, rs -) decomposable with respect some & C Eq. and P(s' s, ( is decomposable with respect to some No C NC.. then one can still prove the if part, i.e. there exists some = &N) such that the game is an NMG with respect this G. See Figure I for the illustration. This is because by our definition, being decomposable with respect to subset implies being decomposable with respect to a larger set, as one can choose the functions f. for the in the complement of the subset to be simply zero, We chose to state as in Proposition L justt for the purpose of presenting both the if and only if conditions in concise and unified way.
Remark 2 (An alternative NMG definition). Another reasonable definition of NMG may be as follows: if for any policy æ, there exist set of functions (QT,) and an undirected connected graph G &&) such that Q7 (s, a) Ejeto.: QT (s. ai az) holds for every i E .N, S, E A. Note that such a definition can be useful in developing policy-based algorithms (while Definition i more amenable to developing value-basee algorithms),, e.g., policy iteration, policy gradient, actor-critic methods, where the Q-value under certain policy πT will appear the updates and may need to preserve certain decomposability structure, for any policy ι encountered in the algorithm updates. However, in this case, we cannot always guarantee the decomposability of P(s' ss.)) )) or ri .). For example, if we assume that r:(s, a) = 0 for every i E N, s E S, a E A, then QT = Ejeeq. and thus (7, .). is always decomposable regardless of (Ps' s, a). However, interestingly, we can show that the decomposability of the transition dynamics and the reward funetion as in Proposition [ can still be guaranteed, above do not occur. In particular, if there exist no i E EN and 8 E S such that Q; (s. a) is a constant function of a for any æ, then the results in Proposition and hence after still hold. We defer a detailed discussion on this alternative definition to Appendix B
long as some degenerate cases as
Remark 3 (Implication of decomposable transition dynamics), For an MG to be an NMG, by Propo- sition the transition dynamics should be decomposable, i.c., P(- s, a) = EjENe F5(- ((,1ssaa)) or |(||s, ss = Fo s). We first focus on the discussion of the former case. Define w,(s, a,) == Eves (('')8,ay). If we fix the value of a and a-j. then wy((s, az) has to be the same for dif- ferent values of aj due to the fact EjENe wy(s,a,) = 1. Also note that by definition, wy(s, a,) does not depend on the choice of this fixed a-j. Therefore, such wy,ss, az) can be written as (s)), where wi;ss) = Evees Fs 8, a;) for all a, E Ay. We can thus rewrite (F us- ing some actual probability distributions (P)) such that if (s) # O, then we rewrite FF, as F,(s'| (s,a)) =w)(s) P.
()()) s,a;), and if (s) = O, we rewrite F, as (6 (, = wy (s))) 8, ag) for an arbitrary probability distribution (, az)) Notice that Eves ( s, ag)
(s(())
for any No. Then, the decomposable transition dynamics can be repre- sented as PP( a, = EjeNe wy ( s, ag). i.e., an ensemble of the transition dynamics that is only controlled by single controllers. The model's transition dynamics thus act according to the follow- ing two steps: (1) sampling the controller according to the distribution Multinomial ( (w; (s) (s)).)))) and (2) transitioning the state following the sampled controller's 's dynamics. Such model has also been investigated under the name of transition dynamics with additive structures in (33. Note that our model is more general and thus covers the single-controller MG setting [34], where there is only one agent controlling the transition dynamics at all states. It also covers the setting of turn-based MGs 34, where in each round, depending on the current state the transition dynamics is by turns affected by only one of the agents. This can be captured by the proper choice of (w; (s)) ) that takes value 1 only for one agent at each state (while takes value 0 for all other non-controller agents at each state s). Additionally, the second case where P( s, a) = [o(s') s) corresponds to the one with ensemble of controller agents.
Proposition 2 (Decomposition of (Q) )iEN). For an infinite-horizon 7-discounted NMG with G (N,Eq) such that No * 0. if we know that PPs'' s.a) = ΣieNe F,(s' s, a4), and
5

---

2
2
2
3
5
4
4
5
4
E,
Exr. ENr.commeee commected
εq
Figure 1: Relationship between Ey. ENp cooonnnnee and Eg. Here, we define ENy. connneeee == i [(,,j
NN or ip,i + j}. ri di, -) is decomposable with respect to &r for all i E N, and IP(s' ( s,-) is decomposable with respect to Np (See Remark [ The transition dynamics is expressed as the ensemble of controllers in the set Np {5} while the NC in this case is {1,5}.
as, E Ejeeq (s, ai a4,ay) for some {E.EENo and (niJ)Gs)es then the QY given in Definition can be represented as Q% (s, o;. ri,(s, a,) )++)))))) Σ EE for any non-negative (A),(s)) (EEE) such that Ejeco Ac.(s) = 1, for all i E N and S. We call it the canonical decomposition of T HEN when QY can be represented above with (s) 1/(Eq,al al for E Eq The case with NC 0 is deferred Appendix B
7 (1 Nc) s.,,) E (N) s,a)) v(s)
We introduce this canonical decomposition since the representation of QY is in general not unique, and may use this canonical form to simplify the algorithm design later.
3.2 Examples of multi-player (zero-sum) NMGs
We now provide several examples of (multi-player) MGs with networked separable interactions here and in Section [.5
Example 1 (Markov fashion games). Fashion games are an intriguing class of games 25 26 27
that plays a vital role not only in Economics theory but also in practice. A fashion game is a networked
extension of the Matching Pennies game, in which each player has the action space A, = {- +1}. which means light and dark color fashions, respectively, for example. There are two types of players: conformists (c), who prefer to conform their neighbors' fashion (action), and rebels (t), who prefer to oppose their neighbors' fashion (action). Such interactions with the neighbors are exactly captured by polymatrix games. We denote the interaction network between players as = &N,
Such a game naturally involves the following state transition dynamics: we introduce the state E S Z by setting so 0 and 8t+1 St + Unif((or.eccc)), which indicates the fashion trend where C C N is the set of influencers. The fashion trend favors either light or dark colors if s 2 0 or < respectively. We can think of dynamics as the impact of the influencers on the fashion trend at time t. For each (s, a), the reward function for player i, depending on whether she is a conformist or rebel, are defined as Tc,a(s, a) Ejee, Te,ss (s, as a,) = -E (12, (ssgn(s) a.) 1(a; = a,)) a:) + 1(a; + a;)), respectively. Moreover, if the conformists and rebels constitute
and (s, a) Ejes, Te, (s, a,) Ejes, ( (sgn(s)
This is an NMG defined in Definition D bipartite graph, i.e., the neighbors of a conformist are all rebels and vice versa, it becomes multi- player constant-sum MG with networked separable interactions, and we can subtract the constant offset to make it a zero-sum NMG.
3.3 Relationship between CCE and NE in zero-sum NMGs
well-known property for zero-sum NGs is that marginalizing a CCE leads to NE, which makes it computationally tractable to find the NE [23 24). We now provide below a counterpart in the Markoy game setting, and provide more detailed statement of the result in Appendix B
Proposition 3. Given an e-approximate Markov CCE of an infinite-horizon discouunee zero-sum (n+1)
NMG, marginalizing it at each state results in an (I-7) (-approximate Markov NE of the zero-sum
NMG. The same argument also holds for the finite-horizon episodic setting with (1 - -y)-1 being replaced by H.

---

This result holds for both stationary and non non- stationary e-approximate Markov CCEs. We defer the proof of Proposition to Appendix [ This proposition suggests that if we can have some algorithms to find an approximate Markov CCE for zero-sum NMG, we can obtain an approximate Markov NE by marginalizing the approximate CCE at each state. We also emphasize that the Markovian property of the equilibrium policies is important for the result to hold, As result, the learning algorithm in [30], which learns an approximate Markov non-stationary CCE with polynomial time and samples, may thus be used to find an approximate Markov non-stationary NE in zero-sum NMGs. However, as the focus of [10 was the more challenging setting of model-free learning, the complexity therein has high dependence on the problem parameters, and the algorithm can only find non-perfect equilibria. When it comes to (perfect) equilibrium computation, one may exploit the multi-player zero-sum structure of zero-sum NMGs, and develop more natural and faster algorithms to find Markov non-stationary NE, Moreover, when it comes to stationary equilibrium computation, even Markov CCE is not tractable in general-sum cases zero-sum NMGs from these perspectives.
30 29
Hereafter, we will focus on approaching
4 Hardness for Stationary CCE Computation
Given the results in Section 3.3 it seems tempting and sufficient compute the Markov CCE of the zero-sum NMG. Indeed, computing CCE (and thus NE) in zero-sum polymatrix games is known to be tractable 23 24). It is thus natural to ask: Is finding Markov CCE computationally tractable? Next, we answer the question with different answers for finding stationary CCE (in infinite-horizon 7-discounted setting) and non-stationary CCE (in finite-horizon episodic setting), respectively.
For two-player hhriite-horizon y-discounted zero-sum MGs, significant progress in computing/leam-
ing the (Markov) stationary NE has been made recently [35] 36
37
38
39
40
41
42). On the
showed that computing (Markov) stationary CCE can be PPAD-hard and thus believed be computationally intractable. We next show that this hardness persists in most non-degenerate cases even if one enforces the zero-sum and networked interaction structures in the multi-player case. We state the formal result as follows, whose detailed proof is available in Section C
other hand, for multi-player general-sum MGs, recent results in 30 29
Theorem 1. There is a constant > 0 for which computing an e-approximate Markov perfect stationary CCE in infinite-horizon _ --discounted zero-sum NMGs, whose underlying network structure contains either triangle
3-path subgraph, is PPAD-hard. Moreover, given the PCP for PPAD conjecture [43. there is a constant c > O such that computing even an <-approximate Markov non-perfect stationary CCE in such zero-sum NMGs is PPAD-hard.
Proof Sketch of Theorem 7 Due to space constraints, we focus on the case with three players, and the underlying network structure has a triangle subgraph. Proof for the 3-path case is similar and can be found in Section [ We will show that for any general-sun two-player turn-based MG (A), the problem of computing its Markov stationary CCE, which is inherently a PPAD-han hard problem [30), can be reduced to computing the Markov stationary CCE of three-player zero-sum MG with a triangle structure networked separable interactions (B). Consider an MG (A) with two players, players 1 and 2, and reward functions (s, a1 02) and (s 02, a1), where a; is the action of the i-th player and r, is the reward function of the i-th player. The transition dynamics is given by IPs'| s, 01, 42). In even rounds, player 2's action space is limited Noop2, and in odd rounds, player I's action space is limited to Noop1, where Noop is an abbreviation of "no-operation", i.e., the player does not affect the transition dynamics or the reward in that round. We denote player I's action space in even rounds as A1oven and player 2's action space in odd rounds as A2, respectively.
Now, we construct a furee-player zero-sum NMG. with a triangle network structure. We set the reward function as (s, a) = EfØr (s, ag a,) and Fi, (s, a.)) = -5,,((s, aj. a;). The reward functions are designed so that Fi.5 = -Fy,s s.s. for all i. F1.2 + F1,3 = 71. and F2.1 F2.3 = 72. where T1,72 are the reward functions in game (A), by introducing a dummy player, player 3. In even rounds, player 2's action space is limited to Noop2, and in odd rounds, player I's action space is limited to Noop1. Player 3's action space is always limited to Noop3 in all rounds. The transition dynamics is defined as IP(s' s, 01, a2 ag) = P(s' s, a1, Oz). since ag is always chosen from Noop3. In other words, player 3's action does not affect the rewards of the other two players, nor the transition dynamics, and players 1 and 2 will receive the reward as the two-player turn-based MG. Also, note that due to the turn-based structure of the game (A), the transition dynamics satisfy the decomosasbe condition in our Proposition [] and is thus a zero-sum NMG. In fact, turn-based dynamics can be represented an ensemble of single controller dynamics, as we have discussed in Section 3
7

---

Dummy
Dummy
Dummy
3
3
4
2
center-player
T3.1
7,,
74.2
f1,3
2,3
F1.3
22,4
2
5
f1,2
T1,2
1,
Figure 2: (Left, Middle): PPAD-hardness reduction visualization of Eq. (Right): A star-shaped zero-sum NMG.
Note that the new game (B) is still turn-based game, and thus the Markov stationary CCE the same as the Markov stationary NE. Also, note that by construction, the equilibrium policies of players I and 2 at the Markov stationary CCE the game (B) constitute a Markov stationary CCE of the game (A). If the underlying network is more general than triangle, but contains triangle subgraph, we can specify the reward and transition dynamics of these three players as above, and specify all other players to be dummy players, whose reward functions are all zero, and do not affect the reward functions of these three players, nor the transition dynamics. This completes the proof.
Figure 2 briefly explains how we may reduce the equilibrium computation problem of (A) to that of (B). In fact, a connected graph that does not contain subgraph of triangle 3-path has to be a star-shaped network (Proposition 7)). which is proved in Section Hence, by Theorem [ we know that in the infinite-horizon discounted setting, finding Markov stationary NE/CE/CCE is computationally hard problem unless the underlying network is star-shaped. This may also imply that learning Markov stationary NE in zero-sum NMGs, e.g., using natural dynamics like fictitious play to reach the NE, can be challenging, unless in the star-shaped case. In turn, one may hope fictitious playy dynamics to converge for star-shaped zero-sum NMGs. We instantiate this idea next Section S Furthermore, in light of Theorem[] 1 we will shift gear to computing Markov con-stationary NE by utilizing the structure of networked separable interactions, to be detailed in Section 6
5 Fictitious- Play Property
In this section, we study the fictitious-play property of multi-player zero-sum games with networked separable interactions, for both the matrix and Markov game settings. Following the convention in [8]. we refer to the games in which aetitious-play dynamics converge to the NE as the games that have the fictitious-pla property. We defer the matrix game case results to Section D where we have also established convergence of the well-known variant of FP, smooth FP (7), in zero-sum NGs.
Echoing the computational intractability of computing CCE zero-sum NMG unless the underlying network structure is star-shaped in the infinite-horian now consider the FP property in such games. Note that by Proposition [ &q a star-shape if and only if the reward structure is a star shape and NC {1), where player 1 is the center of the star (Figure 2). or there are only two players in zero-sum NMG. There is already existing literature for the latter case 115 [6],
discounted setting (c.f. Theorem D
focus the former case, which is single-controller case where player 1 controls the transition dynamics, i.e., P(s s,a) Pi a1) for some P.. We now introduce the fictitious-play dynamics for such zero-sum NMGs.
Each player first initializes her beliefs of other players' policies uniform distributions, and also initializes her belief of the Q-value estimates with arbitrary values. Then, at iteration k, player i takes the best-response action based on her belief other players' policies (R(*) (s(Hi)) and their Q beliefs ²¹²² (s(K), a):
(k) E argmax (3((), Ca,, (s())))
=(k)
a;EA;
Then, player implements the action a observes other players' actions d and updates her
(k)
beliefs as follows: for each player E N, she updates her belief of the opponents' policies as
(k+1) (s) (k) (s) 1(s (1)) N(2) N
(e a
* (4)
for all E S, with stepsize a (s) > 0 where N(s) is the visitation count for the state s; then if = 1,
this player updates the belief of Q1. for all j E NN((1} and her own Q (s, a) for all S
8

---

215 (s,0,,a) = -11 az) + +1(s= = s(h) ((()) (r15(s,a1,8)) +7
Σ s'ES
Pi(s' s,a1)
(s)) (s, (s, (s)).
n n-1
which is based on the canonical decomposition given in Proposition 2 where (2()) (s)
maxa Ed, 21 (s, ea, # ( and BN(.) 2 is the stepsize. The agent then updates
" (s,a),a)) for all s S, E A. Otherwise, if i o then player i updates the belief of her Qi, a) for all S, Aas
Q(tt)) (s, a) Σjex/() Qit++
2 Q (8, az 01) Q = (s, ai, a1)
+ 1(ss = +1ss= -(0)) (r:, (1 + Piss' (1,8118,01) (x) (s,
FEES
where (s) max 0, (s, Ca. 2!?) (s)), and we let (u (s. @ (s, di a1) for these: o 1. The overall dynamics are summarized in Algorithm 4 which resembles the FP dynamics for two-player zero-sum [16] and centical-interes 19 MGs. Now we are ready to present the convergence guarantees.
Assumption The sequences of step sizes fa² E (0, 10,11]2a 220 and f E (0, 1]} A20 satisfy the Ex=o 8h co, and limg- a = lim 8 0; (2) limg--oo oF O, indicating that the rate at which the beliefs about Q-functions are updated is slower than the rate at which the beliefs about policies are updated.
following conditions: (1) Ex= a²
Theorem 2. Suppose Assumption hoolds and Algorithm visits every state infinitely often with probability 1. Then, for a star-shaped multi-player zero-sum NMG, the belief (f())))20 converges to Markov stationary NE and the belief (Q ((()))20 converges to the corresponding NE value of the zero-sum NMG with probability 1, as -> cc.
We defer the proof to Section D.2 due to space constraints. Note that to illustrate the idea, we only present the result for the model-based case, i.e., when the transition dynamics is known. With this result, it is direct extend to the model-free and learning case, where P is not known [6 19 [7],
still using the tool of stochastic approximation [4]. See Section D for more details.
Remark 4 (Challenges for analyzing general cases). One might ask why we had to focus on star-shaped structure. First, for general networked structures, even in the matrix-game case, is known that the NE values of zero-sum NG may not be unique (24). Hence, suppose one performs Nash-value iteration, i.c., solving for the NE of the stage game and conducting backward induction, this value iteration process does converge in general the number of backward steps increases, since the solution at each stage is not even unique, and there may not exist a unique fixed point. This in stark contrast to the max and max min operators in the value iteration updates for single-playe and two-player zero-sum cases, respectively. By exploiting a star-shaped structure, we managed to reformulate minimax optimization problem when solving each stage game, which makes the corresponding value iteration operator contructing, and thus iterating it infinitely converges to the unique fixed point. Second, suppose there exists some other network structure (other than star-shaped ones) that also leads to a contracting value iteration operator, then for a fixed constant 7, the fixed point (which corresponds to the Markov stationary CCE/NE of the zero-sum NMG) becomes unique and can be computed efficiently, which contradicts our hardness result in Theorem [] Indeed, it was the exclusion of star-shaped structure in Theorem [ that inspired us consider this structure in proving the convergence of FP dynamics. That being said, we note that having a contracting value iteration operator is only a sufficient condition for the FP dynamics to converge. would be interesting to explore other structures that enjoy the FP property for reasons beyond this contraction property. We leave this as an immediate future work.
Next, we present another positive result light of the hardness in Theorem regarding the computa- tion of non- stationnay equilibria in multi pulti-player zero-sum NMGs.

---

6 Non-Stationary NE Computation
We now focus computing an (approximate) Markov non-stationary equilibrium in zero-sum NMGs. In particular, we show that when relaxing the stationarity requirement, not only CCE, but NE, can be computed efficiently. Before introducing our algorithm, first recall the folklore result that approximating Markov non-stationary NE in infinite-horizon discounted settings can be achieved by finding approximate Markov NE in finite-horizon settings. with large enough horizon length (c.f. Proposition T0P. Hence, we will focus on the finite-horizon setting from now on.
Before delving into the details of our algorithm, we introduce the notation Qh,i(s) and (s( for E [ E N, & E as follows:
Quastt())) ..... (n..........n E RR 1all (s,)()) = (0n.)])=000..)))..00...1
Qn(s) = ((),.()))) ( (Q ( E RiEN (Ail IA:l,
Here, Q1,,, represents estimate of the equilibrium value function with canonical decomposition (Proposition 2). Hereafter, we similarly define the notation of QT, and Q7 Our algorithm is based on value iteration, and iterates three main steps from h = H to as follows: (1) Q-value computation: compute Qh,i.j. which estimates the equílibrium Q-value with a canonical decomposition form; in particular, when NC # 0. Quis is updated for all E S, (i,5) E Eq, 02 E Ai, and 0g E Aj:
(1,,,((,ar,;;) as,
1(1 (c) s, s,a.) 16 (N (s (s, Va+1,a(s'), [(1e 1 J'Cs
Σ
(2) Policy update; update TA (8) with an NE-ORACLE: finding (approximate) of some zero-sum NG (9, A, (Qn.., (().).)) for all s E S, and (3) Value function update: compute Vh, which esti- mates the equilibrium value function as follows for all s E S Vs,((s) = ~ (s) (s)
The overall procedure is summarized in Algorithm 6
NE-ORACLE and iteration complexity. The NE- in Algorithm 6 can be instantiated by several different algorithms that can find an NE in zero-sum NG. Depending on the algorithms, the convergence guarantees be either in terms of verrage-iterate best-iterate, last-iterate. Note that for algorithms with average-iterate convergence, one may additionally need to marginalize the output joint policy, i.e., the approximate CCE, and combine them product policy that is an approximate NE (Proposition (6. For those with best-/last-iteratt convergence, by contrast, the best-/last-iten already in product form, and one directly output it as an approximate NE. Moreover, last-iterate convergence is known to be a more favorable metric than the average-iterate one in learning in games 45 46 47 48 49) which is able to characterize the day-to-day behavior of the iterates and implies the stability of the update rule. Hence, one may prefer to have last-iterate convergence for solving zero-sum N(M) To this end, two algorithmic ideas may be useful: adding regularization the
is
payoff matrix 39 50 51 52), and/or using the idea of optimism (47 36 [53) Recent results 51 have instantiated the ideas of optimism-oni and optimism + regularization, respectively, for best-/last-iterate convergence in zero-sum polymatrix games. We additionally established results for the idea of regularization-on only obtaining last-iterate convergence in these games. Specifically, we propose to study the vanilla Multiplicative Weight Update (MWU) algorithm (55) in the regularized zero-sum NG, as tabulated in Algorithm 9 We have also introduced a variant with diminishing regularization, and summarize the update rule in Algorithm T0
Given the results above, aggregating e-approximate NE for the zero-sum NGs AG (Qn.i (s)) for the corresponding zero-sum NMG. We have the following formal result.
for all h E [H], E N, E S provides an He-approximate NE
Proposition 4. Suppose that for all h E [H] E N.s E S, (Onaa()))nneee) provides an ap.-aaprooimmate NE for the zero- sum NG AG (Qnss(())a.nee)) in Algorithm 6 Then, the output policy x in Algo- rithm 6 is an (EnejH) max,es aaproxiaie NE for the corresponding zero-sum NMG (G (V, Eq)) S.A, H. (Pn)ne(M) (Mr,g (s) (I.NEE.wEs))
NE- NE-ORACLE(G,A))
The proof of Proposition ii deferred Section F In light of Proposition 4nd Table we obtain Table which summarizes the iteration complexities required to find an cNE for zero-sum NMGs, with different NE-ORACLE subroutines. Note that the iteration complexities are all polynomial in H, n, (S), and inherit the order of dependencies on from Table [ for the matrix-game case. In particular, Algorithm 6 with the OMWU in [51] yields the fast rate of ((1/e) for the last iterate.
10

---

Acknowledgement
The authors would like thank the anonymous reviewers of NeurIPS for their helpful feedback. C.P. acknowledges support from the Xianhong Wu Fellowship, the Korea Foundation for Advanced Studies, and the Siebel Scholarship. K.Z. acknowledges support from the Northrop Grumman Maryland Seed Grant Program. A.O. acknowledges support from the MIT-Air Force Al Innovation Accelerator Grant and the MIT-DSTA grant 031017-00016.
References
[1] John Von Neumann and Oskar Morgenstem. Theory of games and economic behavior. Princeton University Press, 1947.
[2] John F Nash Jr. Equilibrium points in n-person games. Proceedings of the National Academy of sciences, 36(1):48-49) 1950.
[3] Nicolo University press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge
[4] Drew Fudenberg and David K Levine. The theory of learning in games, volume 2. MIT Press, 1998.
[5] George W Brown. Iterative solution games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951.
[6] Julia Robinson. An iterative method of solving game. Annals of mathematics, pages 296-301, 1951.
[7] Drew Fudenberg and David M Kreps. Learning mixed equilibria. Games and Economic Behavior, -67,0-36, 1993.
[8] Dov Monderer and Lloyd S Shapley. Fictitious play property for games with identical interests. Journal of economic theory, 68(1):258-265, 1996.
[9] Koichi Miyasawa. On the convergence of the learning process in a 2 x 2 non-zero-sum two-person game. Princeton University Press, 1961.
[10] Ulrich Berger. Fictitious play in 2 games. Journal of Economic Theory, 120(2):139-154, 2005.
[11] Aner Sela. Fictitious play in "one-against-all" multi-player games. 14(3):635-651, 1999.
Economic Theory,
[12] Christian Ewerhart and Kremena Valkanova. Fictitious play in networks. Games and Economic Behavior, 123:182-2066 2020.
[13] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):095-1110, 1953.
[14] David Leslie, Steven Perkins, and Zibo Xu. Best-response dynamics in zero-sum stochastic games. Journal of Economic Theory, 189:105099 2020.
[15] Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decen- tralized Q-learning in zero-sum Markov games. NeurlPS, 2021.
[16] Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. SIAM Journal on Control and Optimizationn (0(4):2095-2114 2022.
[17] Lucas Baudin and Rida Laraki. Fictitious play and best-response dynamics identical interest and zero-sum stochastic games. ICML, 2022.
[18] Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wierman. A finite-sample analysis of payoff-based independent learning zero-sum stochastic games. NeurIPS, 2023.
11

---

[19] Muhammed O Sayin, Kaiqing Zhang, and Asuman Ozdaglar. Fictitious play in markov games with single controller. EC, 2022.
[20] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009.
[21] Xi Chen, Xiaotie Deng, and Shang- Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1-57, 2009.
[22] Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi- player games. Journal of the ACM (JACM), 55(3):1-29, 2008.
[23] Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. SODA, 2011.
[24] Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero- sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41 41(2))648-655 2016.
[25] Zhigang Cao, Haoyu Gao, Xinglong Qu, Mingmin Yang, and Xiaoguang Yang. Fashion, cooperation, and social interactions. PLoS One, 8()):e49441, 2013.
[26] Zhigang Cao and Xiaoguang Yang. The fashion game: Network extension of matching pennies. Theoretical Computer Science, 540:169-181, 2014.
[27] Boyu Zhang, Zhigang Cao, Cheng- Zhong Qin, and Xiaoguang Yang. Fashion and homophily, Operations Research, 66(6):1486-1499) 2018.
[28] L LM Bergman and IN Fokin. On separable non-cooperative zero-sum games. Optimization, 44(1):69 84, 1998.
[29] Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infinite-horizon general- sum stochastic games. ITCS, 2022.
[30] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilibrium in stochastic games. COLT, 2023.
[31] I M. Bergman and I N Fokin. Methods of determining equilibrium situations in zero-sum polymatrix games. Optimizatsia, 40(57))70-82,, 1987.
[32] Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-533 1994.
[33] János Flesch, Frank Thuijsman, and Okko Jan Vrieze. Stochastic games with additive transi- tions. European Journal of Operational Research, (9(2))483-499, 2007.
[34] Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
[35] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. NeurlPS, 2020.
[36] Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in anfnite-horizon competitive Markov games. COLT, 2021.
[37] Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon S Du. Provably efficient policy gradient methods for two-player zero-sum markov games. AISTATS, 2022.
[38] Ziyi Chen, Shaocong Ma, and Yi Zhou. Sample efficient stochastic policy extragradient algorithm for zero-sum markov game. ICLR, 2021.
[39] Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. NeurIPS, 2021.
12

---

[40] Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum markov games. ICML, 2022.
[41] Sihan Zeng, Thinh T Doan, and Justin Romberg. Regularized gradient descent ascent for two-player zero-sum markov games. NeurIPS, 2022.
[42] Shicong Cen, Yuejic Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum markov games. ICLR, 2023.
[43] Yakov Babichenko, Christos Papadimitriou, and Aviad Rubinstein. Can almost everybody be al- most happy? pep for ppad and the inapproximability of nash. arXiv preprint lrXiv:1504.02411 2015.
[44] Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328-3444 2005.
[45] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. SODA, 2018.
[46] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. ICLR, 2018.
[47] Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. ITCS, 2019.
[48] James Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. EC, 2018.
[49] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. ICLR, 2019.
[50] Shicong Cen, Fan Chen, and Yuejie Chi. Independent natural policy gradient methods for potential games: Finite-time global convergence with entropy regularization. CDC, 2022.
[51] Ruicheng Ao, Shicong Cen, and Yuejic Chi. Asynchronous gradient play in zero-sum multi- agent games. ICLR, 2023.
[52] Sarath Pattathil, Kaiqing Zhang, and Asuman Ozdaglar. Symmetric (optimistic) natural policy gradient for multi-agent learning with parameter convergence. AISTATS, 2023.
[53] Chen-Yu Wei, Chung- Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. ICLR, 2022.
[54] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last- iterate convergence beyond zero-sum sum games. ICML, 2022.
[55] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012.
[56] Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multia- gent reinforcement learning. IEEE Transactions Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172 2008
[57] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[58] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. Machine learning proceedings 1994, pages 157-163, 1994.
[59] Michael L. Littman al. Friend-or-foe l-learning in general-sum games. ICML, 2001.
[60] Michael I. Littman. falue-function reinforcement learning in markov games. Cognitive systems research, 2(1):55-66, 2001.
13

---

[61] Junling Hu and Michael P Wellman. Nash q-learming for general-sum stochastic games. JMLR, 2003.
[62] Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. ICML, 2020.
[63] Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. AISTATS, 2020.
[64] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous-movt markov games using function approximation and correlated equilibrium. COLT, 2020.
[65] Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self play. NeurIPS, 2020.
[66] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of model-based reinforce- ment learning with self-play. ICML, 2021.
[67] Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. NeurIPS, 2020.
[68] Gen Li, Yuejic Chi, Yuting Wei, and Yuxin Chen. Minimax-optimal multi-agent rl in Markov games with generative model. NeurIPS, 2022.
[69] Jayakumar Subramanian, Amit Sinha, and Aditya Mahajan. Robustness and sample complexity of model-based MARL for general-sum Markov games. Dynamic Games and Applications, pages 1-33, 2023.
[70] Ziang Song, Song Mei, and Yu Bai. When can we learn general-sune markov games with large number of players sample-efficienlyy? ICLR, 2021.
[71] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, de- centralized algorithm for multiagent RL. ICLR 2022 workshop "Gamification and Multiagent Solutions" 2022.
[72] Weichao Mao, Lin Yang, Kaiging Zhang, and Tamer Basar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. ICML, 2022.
[73] Weichao Mao and Tamer Başar. Provably efficient reinforcement learning in decentralized general-sum Markov games. Dynamic Games and Applications, pages 1-22, 2022.
[74] Qiwen Cui, Kaiqing Zhang, and Simon S Du. Breaking the curse of multiagents in large state space: RL in Markov games with independent linear function approximation. COLT, 2023.
[75] Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably efficient decentralized multi-agent RL with function approximation. COLT, 2023.
[76] Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret mini- mization and convergence to equilibria in general-sum markov games. ICML, 2023.
[77] Aviad Rubinstein. Settling the complexity of computing approximate two-player Nash equilib- ria. ACM SIGecom Exchanges, 15(2):45-49 2017.
[78] Constantinos Daskalakis. Non-concave games: A challenge for game theory's 's next 100 years.
2022.
[79] Matthew O Jackson and Yves Zenou. Games on networks. In Handbook of game theory with economic applications, volume 4, pages 95-163. Elsevier, 2015.
[80] Michael Kearns, Michael L. Littman, and Satinder Singh. Graphical models for game theory. UAI, 2001.
[81] Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz. Correlated equilibria in graphical games. EC, 2003.
14

---

[82] Constantinos Daskalakis and Christos H Papadimitriou. On network generalization of the minmax theorem. In International Colloquium on Automata, Languages, and Programming. pages 423 4344. Springer, 2009.
[83] Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. Exploration-exxloitation in multi-agent competition: convergence with bounded rationality. NewrIPS, 2021.
[84] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi-agent reinforcement learning with networked agents. ICML, 2018.
[85] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Networked multi-agent reinforcement learning in continuous spaces. CDC, 2018.
[86] Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning for multiagent networked systems. Operations Research, 2022.
[87] Xin Liu, Honghao Wei, and Lei Ying. Scalable and sample efficient distributed policy gradient algorithms in multi-agent networked systems. arXiv preprint crXiv:2212.06357 2022.
[88] Yizhou Zhang, Guannan Qu, Pan Xu, Yiheng Lin, Zaiwei Chen, and Adam Wierman, Global convergence of localized policy iteration in networked multi-agent reinforcement learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-51, 2023.
[89] Zhaoyi Zhou, Zaiwei Chen, Yiheng Lin, and Adam Wierman. Convergence rates for localized actor-critic in networked markov potential games. UAI, 2023.
[90] Georgios Piliouras, Lillian Ratliff, Ryann Sim, and Stratis Skoulakis. Fast convergence of optimistic gradient ascent in network zero-sum extensive form games. SAGT, 2022.
[91] Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-268. 1991.
[92] Jan Peters, Katharina Mulling, and Yasemin Altun. Relative entropy policy search. 2010.
[93] Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regularizzed Markov decision processes. NeurlPS, 2017.
[94] Tuomas Haarnoja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. ICMI., 2017.
[95] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global conver- gence rates of softmax policy gradient methods. ICML, 2020.
[96] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563- 2578. 2022.
[97] Mingyang Liu, Asuman E. Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive-form games. ICLR, 2023.
[98] Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Mare Lanctot, loannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement lcarning, quantal response equilibria, and two-player zero-sum games. ICLR, 2023.
[99] Lloyd Shapley. Some topics in two-person games. Advances in game theory, 52:1-29, 1964.
[100] Muhammed O Sayin. On the global convergence of stochastic fictitious play in stochastic games with turn-based controllers. CDC, 2022.
[101] Asuman Ozdaglar, Muhammed O Sayin, and Kaiqing Zhang. Independent learning in stochas- tie games. International Congress of Mathematicians, 2022.
[102] Fivos Kalogiannis and Joannis Panageas. Zero-sum polymatrix Markov games: Equilibrium collapse and efficient computation of Nash equilibria. NeurIPS, 2023.
15

---

[103] Jens Grossklags, Nicolas Christin, and John Chuang. Secure or insure? a gaeo-the analysis of information security games. WWW, 2008.
[104] Robert Wilson. Game-theoretic analysis of trading processes. Technical report, Stanford University, 1985.
[105] Robert Wilson. Game theoretic analysis of trading. In Advances in Economic Theory: Fifth World Congress, number 12, page 33. CUP Archive, 1989.
[106] Dayong Zhang, Lei Lei, Qiang Ji, and Ali M Kutan. Economic policy uncertainty in the us and china and their impact on the global markets. Economic Modelling, 79:47-56, 2019.
[107] Michael Beckley. The power of nations: Measuring what matters. International Security. 43(2):7-44, 2018.
[108] Charles Freedman, Michael Kumhof, Douglas Laxton, Dirk Muir, and Susanna Mursula. Global effects of fiscal stimulus during crisis. Journal of monetary economics, 5765):506- 526, 2010.
[109] Klaus Armingeon. The politics of fiscal responses to the crisis of 2008-20000 Governance, 25(4):543-555 565,, 2012.
[110] Fábio Augusto Reis Gomes, Sergio Naruhiko Sakurai, and Gian Paulo Soave. Government spending multipliers in good times and bad times: The case of emerging markets. Macroeco- nomic Dynamics, 26(3):726-768, 2022.
[111] Richard D) McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
[112] Richard McKelvey and Thomas Palfrey, Quantal response equilibria for extensive form games. Experimental economics, 1:9-41, 1998.
[113] Panayotis Mertikopoollos and William H Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 1194)1297-1124 2016.
[114] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning general games. NeurIPS, 2021.
[115] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o() log t) swap regret in multiplayer games. NeurlPS, 2022.
[116] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung- Seung-Weilo Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. NeurIPS, 2022.
[117] David Reeb and Michael M Wolf. Tight bound on relative entropy by entropy difference. IEEE Transactions on Information Theory, 1188))145811473 2015.
[118] Haipeng Luo. Introduction to online optimization//laming (fall 2022), lecture note
[119] Yang Cai, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games. arXiv preprint 2303023303 2023.
16


Reviews:
[{"review_id": "3Fre50eAK1", "reviewer": "Reviewer_SApy", "summary": "The paper studies multi-player zero-sum Markov games with networked interactions, generalizing the well-studied class of polymatrix normal-form games. They first show that Markov coarse correlated equilibria (CCE) collapse to Markov Nash equilibria (NE), allowing to focus on computing Markov CCE for which they provide polynomial-time algorithms based on optimistic multiplicative weights update. They also rely on recent advances to show that the stronger notion of stationary CCE is PPAD-hard, unless the network is star-shaped. For the latter class of Markov games, they establish that fictitious play converges asymptotically to the set of stationary NE.   ", "questions": "Some minor issues:\n\n1. The exposition in Section 3 regarding Markov games with network interactions appears to be more complex than what is actually needed. I would recommend slightly revising and simplifying the exposition in Section 3.1 \n2. Is there a polynomial algorithm for computing stationary NE under a star-shaped topology? The results based on FP do not give any non-asymptotic guarantees\n3. A related paper worth inclusing: “Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games” \n4. Propositions and theorems are typically in italic, but I leave this up to the authors\n5. Line 373: approximates -> approximate\n6. Line 668: correlated equilibria (CCE)\n7. Line 718: do -> take\n8. Line 719: gives -> which gives\n9. Line 1001: It maybe good to point to Appendix E here for the definition of a differential inclusion as it is quite non standard\n", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a natural subclass of Markov games inspired by a number of positive results on polymatrix zero-sum normal-form games. The authors motivate this class with a number of concrete examples and applications, and they make concrete contributions towards understanding the complexity of computing equilibria in that class of games. In particular, they show that certain positive results in normal-form games can be extended to their Markov games counterpart as well, eluding a number of hardness results in general Markov games. These are some of the few positive results for Markov NE under a non-trivial class of multi-player games, so I believe the results will be valued by the community. \n\nThe paper also appears sound; I did not find any notable issue in the proofs. The paper is also well-written and organized, and the key ideas are nicely exposed in the main body. ", "weaknesses": "There are a couple of issues regarding the exposition/novelty of the results. First, the authors claim that they provide the first guarantees even in zero-sum polymatrix normal-form games under fictitious-play dynamics, but this does not appear to be the case. In particular, see the paper \"Fictitious play in Networks.\" (Note that the latter paper also provides guarantees under discrete-time FP.) In fact, the results of the latter paper apply without the restrictive assumption of a star-shaped topology. So the authors should carefully clarify the connection with the aforementioned paper. I should note that this does not affect significantly the narrative of the paper since the results on the more general class of Markov games are novel and non-trivial even in light of that other paper. For completeness, it would be good to see if your techniques provide asymptotic guarantees for polymatrix zero-sum normal-form games without the star-shaped assumption. \n\nThe second issue relates to the novelty of the results in Section 6. In light of the collapse of Markov CCE with Markov NE, one can obtain immediately a polynomial-time algorithm using any algorithm for computing Markov CCE (e.g., the one by Daskalakis et al. 2022). In contrast, instead of using known algorithms, the authors design a new algorithm whose analysis is quite technically involved; it is not clear why the authors did not simply rely on known algorithms. At the very least, the authors should clarify that getting a Markov NE follows directly by the shown collapse; the current write-up can cause confusion. The designed algorithm based on OMWU has the nice property of getting a rate of $1/T$, which is certainly not the case with other algorithms for computing Markov CCE, but this is not highlighted at all. Regarding the last point, if one only cares about centralized algorithms, it should be possible to use the ellipsoid against hope algorithm of Papadimitriou and Roughgarden (along with backward induction) to get an exact Markov CCE (and hence Markov NE).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comparison with prior work**. Thank you very much for bringing up the work “Fictitious play in networks” to our attention. We were not aware of the paper, and will add the reference in our updated version. We will also revise the statement regarding the first FP in zero-sum polymatrix games in the paper. Compared with the work, we allow more general stepsizes beyond the $1/T$ one. We also would like to point out that for the matrix case, we did *not* require the topology of the network to be of “star-shape” for the FPP to hold. The star-shaped condition is only required for the *Markov game* case.\n\nAs pointed out by the reviewer, this does not change the narrative of our paper, as our focus was on the Markov game case, and viewed the one for the matrix case as a bonus result. Thank you again for kindly pointing out the reference. \n\n\n**Results in Sec. 6.** Indeed, given the equilibrium collapse result, one can use the existing algorithms for computing Markov CCE to find Markov NE, e.g., as in Daskalakis et al., 2022. We developed different algorithms as we believe they could constitute new contributions to the work. We wanted to include more solid technical results than “just applying” existing algorithms. We also wanted to have some algorithm that is natural and not completely “centralized”. We will emphasize this point to avoid confusion. \n\nA final remark is that, the algorithm in Daskalakis et al., 2022 is specifically designed for “learning” Markov CCE without model knowledge, a more challenging setting than the “equilibrium computation” setting we consider here. Thus, directly applying it will lead to worse iteration complexity than our equilibrium computation algorithms. As pointed out by the reviewer, Our designed algorithm based on OMWU indeed offers $\\tilde{O}(1/\\epsilon)$ convergence rate, distinguishing it from other algorithms for computing Markov CCE with the general structure. We will make these points clear in our updated version. \n\n**Minor issues.**\n\n1. We will simplify the exposition in Sec. 3.1\n\n2. Thanks for raising this very good point. Yes, we can use value-iteration to compute Markov stationary NE for the star-shaped case, for a fixed $\\gamma$. The key to obtaining the fictitious-play property, as we pointed out in lines 350-367 in the Remark on page 8, is to *re-formulate* the NE computation in this case as a **minimax optimization** problem for each stage, and show the corresponding value-iteration operator is “contracting”. With this contracting property, one can readily show that VI can find the Markov NE efficiently. We did not emphasize this as it is folklore to obtain efficient computation using contracting VI operators. We will stress this point in our updated version.\n\\\\\n3. Thank you very much for bringing up the reference. We will include the discussion in our updated version.\n\n4. Thanks for the suggestion. We will fix this formatting issue.\n\n5-8. Thanks for the careful reading. We will fix these typos.\n\n9. We will add the definition of differential inclusion in the updated version.\n\nThank you very much again for the valuable comments on improving our paper. We hope the responses have addressed them satisfactorily. \n"}, {"review_id": "5cmikTGnrR", "reviewer": "Reviewer_GndM", "summary": "The authors define a notion of Markov Games with local interactions with the extra assumption that are zero-sum (inspired from the polymatrix/graphical games that appeared in papers in Algorithmic Game Theory). They manage to show that Markovian Coarse Correlated Equilibria correspond to Markovian Nash Equilibria when marginalized (called the phenomenon collapsing) in their setting. They also show that approximating stationary and Markovian NE  is PPAD-hard and they finally provide an algorithm that gives Markovian non-stationary NE for their class of Markov Games.", "questions": "Can you elaborate more on the uniqueness of the QRE? If this is the case for infinite horizon settings, why your algorithm does not work for infinite horizon and you need to truncate after log(1/eps) episodes?", "limitations": "Not applicable", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors manage to define another class of Markov games in which finding NE (Markovian but not stationary) is tractable. The collapsing phenomenon is quite interesting and the idea of using QRE to get Markovian non-stationary NE is natural and elegant.", "weaknesses": "The model assumes some decomposability of the probability transition matrix that makes the model a bit complicated to parse. It seems though that the model captures interesting settings. The hardness result is not surprising and seems straightforward from Daskalakis et al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our equilibrium collapsing result interesting, and the algorithmic idea natural and elegant. We respond to your reviews point-by-point as follows.\n\n**Hardness result seems not surprising and straightforward from Daskalakis et al.** We agree that the result *relies on* Daskalakis et al, but respectfully disagree that it is straightforward from it. To show the result, we needed to carefully construct the reward functions for the players in MZNMGs, and identify the “sufficient” (and later turns out to be “necessary”) conditions for the Markov stationary CCE to be computationally intractable, i.e., the network structure is not a star shape. The necessary part is justified by our result on the contracting property of the VI operator (see the response to Reviewer SApy, and in lines 350-367 in the Remark on page 8). This “star-shaped” condition also inspired us to study the fictitious-play property under it, and justified the computation of “non-stationary” CCE later, separating what is possible and what is not in this class of games. We believe the result is important and not a trivial application of Daskalakis et al. 2022.\n\nMoreover, these results have important implications for the computational hardness literature. Consider the static polymatrix game as an example. Its fascinating aspect lies in the dichotomy between the computational **hardness** of computing the Nash Equilibrium (NE) of two-player general-sum static games, and the computational **tractability** of computing the NE of two-player zero-sum static games. This contrast underlines the significance of polymatrix games from a complexity perspective. In the realm of Markov games, our study contributes by exploring special cases of *multi-player zero-sum* games. This new class of games adds on a new dimension to the complexity spectrum, as we can draw interesting contrasts between these cases and their static-game counterparts. By bridging this gap, we hope to deepen the understanding of computational complexity results in the field of Markov games.\n\n\n**Uniqueness of QRE.** It is correct that in the **finite-horizon** setting, the QRE, which is non-stationary, is unique. This can be shown by backward induction – the QRE for the matrix game (i.e., the MZNG) at the last time step is unique, due to reference [62] in the paper; this fact can then be used to show the uniqueness of the previous timestep by induction. This is also the reason why we truncated after log(1/\\epsilon) steps and compute “non-stationary” equilibrium in Sec. 6. \n\nIn the **infinite-horizon** discounted setting, the QRE of the MZNMG is not necessarily unique (and *we never claimed so*). In general, it is unclear if the “QRE + value-iteration” operator is contracting, or possesses any good property that leads to the “uniqueness” of the fixed point (which corresponds to the QRE of the Markov game). This is also eluded by our hardness result – if the “QRE + value-iteration” operator is contracting, then an “approximate” stationary CCE can be obtained by iterating this operator and choosing a small enough regularization, contradicting our hardness result. \n\nFinally, we also remark that, the “uniqueness” of the QRE does not necessarily mean the existence of an easy way to “compute” the equilibrium, either. In particular, uniqueness may not necessarily come from the contracting property of the VI-operator, or some other properties that may lead to efficient computation algorithms. We will add these discussions in the updated version of the paper.\n\nThank you very much again for the helpful and insightful comments on improving our paper. We hope the responses have addressed them satisfactorily. \n"}, {"review_id": "jNTOk22GnS", "reviewer": "Reviewer_J94i", "summary": "The paper focuses on the problem of computing both in a centralized and in a decentralized way equilibria for a special class of stochastic games. These are games that may be found in multiple states. At each state players have a set of available actions, that once played will define both the reward that each player achieves and the next state in which the game will be found. It is known that with only two players or multi-player potential games equilibria of these games can be efficiently computed by fictitious play. The paper consider multi-player non-potential games such that the utility that a player achieves by playing an action can be decomposed as the sum of the utilities that this action will give in two-players games against a few of other players. Indeed, it is known that these games in their normal form (non stochastic non repeated) enjoy a lot of common properties with the two-player zero sum games, such as the possibility to efficiently compute an equilibirum.\n\nUnfortunately, the answer of the paper is essentially negative: computing an equilibrium for this class of stochastic games is hard even for coarse correlated equilibrium, unless the utility relationships is such that there is a center player c such that the utility of all remaining players depends on c only. In this case, fictitious play is known to converge to the equilibrium under opportune assumptions on the rate at which the relevant learning value are updated. Finally, it is showed that is possible to compute through multiplicative weights updates a dynamics converging to an approximation of a non-stationary equilibrium, i.e., an equilibrium that is not a fixed point independent of history.", "questions": "Does decomposable tranisition matrix mean that N_c >= 1? If so, I believe that would make the definition more easy to grasp to write down this fact.\n\nRemove double point at the end of page 8.", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The problem attracted the interest of the community in recent years, and hence it is relevant. Moreover it is a well-motivated class of problems, both for their applications and for the theoretical foundations (as stated above in the summary).\n\nThe contribution is clearly stated, and the paper is quite easy to read.", "weaknesses": "The results are essentially negative and positive cases have quite limited applicztion.\nE.g., Prop 3 (stating correlated equilibria are the same as Nash equilibria) only holds for decomposable  transition matrix, that in turn mean that there must be at least a single player that depends on all other player, that is often not the case (usually local interactions are very local).\nThm 1 allows equilibrium computation only for a further restriction of this class. And convergence of fictitious play holds under further assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our results well-motivated, contributions clearly stated, and the paper easy to follow. We respond to your reviews point-by-point as follows.\n\n**The results are essentially negative and positive cases have limited applications.** Regarding Prop. 3, first, the result applies to all MZNMGs as long as it is not a “two-player” case (which is a reduced case, as it is just a standard two-player Markov game), since by our Prop. 1, an MZNMG with “more than two-players” should have the decomposability of the transition dynamics. Second, a decomposable transition dynamics does not necessarily mean “there must be at least a single player that depends on all other players”, as we emphasized in our paper that it can have an ensemble structure. Moreover, In Prop. 1, we allowed the set $\\mathcal{N}_c$ to be empty. Sorry for the confusion of the statement, and we have updated them in the manuscript in the supplementary material. These conditions might sound restrictive, but by our Prop. 1, they are the “necessary” conditions for an MG to be an MZNMG. \n\nFinally, we remark that *after* submitting our paper, an independent work [1] was posted on arxiv, which also concerns zero-sum Markov polymatrix games. Notably, the “definition” of the game therein that enables “equilibrium collapse” and “equilibrium computation” is based on the “switched/turn-based” controller transition dynamics, which is covered by our “ensemble/decomposable” dynamics, according to our remarks in lines 191-205 at the end of page 4. \n\n**Conditions that enable fictitious-play property.** Our “star-shaped” condition that enables fictitious-play is inspired by our hardness result in Theorem 1, as a graph that does not contain a triangle or 3-path subgraph has to be a star shape (see our Prop. 5). Without such a condition, it is unclear how to construct a “contracting” value-iteration operator, which is essential in the current analysis of the fictitious play in MZNMGs. We discussed the importance of the condition in the remark at the end of page 8. \n\n**Does decomposable transition dynamics mean $\\mathcal{N}_c\\geq1$?** Sorry for the confusion. When saying “decomposable”, we actually allowed N_c=0, which corresponds to the other cases discussed in Prop. 1. Being aware of the confusion, we have cleaned up and updated the statement of Prop 1 in the manuscript in the supplementary material (and colored the changes). We will also keep the changes in the updated version.\n\n**Remove the double-point at the end of page 8.** We will do it in the updated version.\n\nThank you very much again for the helpful comments on improving our paper. We hope the responses have addressed them satisfactorily. Please let us know if there are any other comments we can address to help you reevaluate our paper.\n\n\nReferences:\n\n[1] Fivos Kalogiannis and Ioannis Panageas. \"Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria.\" arXiv preprint arXiv:2305.14329 (2023).\n\n"}, {"review_id": "DVUlCpwsCf", "reviewer": "Reviewer_xjXv", "summary": "The paper studies the problem of learning equilibria in multi-player zero-sum Markov games with networked local interactions (abbreviated as MZNMGs for short). In such games, the set of Markov CCEs collapses into that of Markov NEs. The paper shows that finding approximate Markov stationary CCEs is PPAD-hard in MZNMGs with infinite horizon, unless the network structure has a specific star shape. Then, the paper proves that in games with such a structure fictitious-play-based dynamics are guaranteed to converge to a Markov stationary NE. Moreover, the paper also shows that the negative PPAD-hardness result can be circumvented by considering Markov non-stationary CCEs, providing finite-iteration convergence guarantees for an algorithm based on optimistic multiplication weight updates.", "questions": "1) What is the relation between the results in this paper and the following recent work?\n\nFoster, Dylan J., Noah Golowich, and Sham M. Kakade. \"Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games.\" arXiv preprint arXiv:2303.12287 (2023).", "limitations": "None.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "ORIGINALITY\n\nThe paper proposes a new class of Markov games and it shows that such a class of games enjoys some appealing properties in terms of convergence of learning dynamics.\n\nQUALITY\n\nThe claims seem sound (but I did not check the proofs in details).\n\nCLARITY\n\nThe paper is well written.\n\nSIGNIFICENCE\n\nThe problem of learning equilibria in Markov games has receiving considerable attention over the last years, and the results presented in the paper could be of interest to both researchers in algorithmic game theory and those in multi-agent RL.", "weaknesses": "ORIGINALITY\n\nThe ideas behind the presented results and the techniques used to prove them seem adaptations and combinations of already known results and techniques. The authors should more specifically address the novelty of their results/techniques.\n\nCLARITY\n\nThe notation used in the paper is quite cumbersome, and in many spots it is easy to get lost in symbols. I think that these issues are inherent in the model studied in the paper, since it encompasses many elements, but I encourage the authors to try to lighten the notation as much as possible.\n\nMINOR COMMENTS\n\n- The experimental results seem an unneeded extra in this paper, I would consider removing them (actually, they are only discussed in the abstract and in the last section of the Appendix).\n- The discussion on related works in neglecting the recent works addressing the problem of learning correlated equilibria in sequential games. These are related to Markov games and should be adequately discussed.\n- It is not clear what you mena by single controller.\n- Line 107: It should be $\\Delta(\\mathcal{A})$ rather than $\\Delta(\\mathcal{A}_i)$.\n- Line 122 and onward, the notation $\\mu_i, \\pi_{-I}$ has not been introduced.\n- Line 162, it is not clear why $I \\neq j$.\n- Please give more textual intuition to Propositions 1 and 2.\n- Lines 260-261, discuss more why Markovianity is important, it is not clear otherwise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our paper sound, well-written and significant. We respond to your reviews point-by-point as follows.\n\n**Originality.** Thank you for your comment. We agree that some of the ideas and techniques are based on existing works. However, non-trivial ideas and techniques are proposed in the paper, which include but are not limited to: 1). The if and only if conditions of transition and rewards, for a Markov game to be qualified as a MZNMG (Prop .1); 2). Reduction of our MZNMG model to general-sum MGs, and the proof for computation hardness; 3). Identifying the structures, i.e., the star-shaped ones, under which equilibrium computation and FPP are possible; 4). Reformulating the star-shaped MZNMG value-iteration operator as a “minimax” form to enable the convergence of fictitious-play; 5). New algorithm and proofs for non-stationary NE computation in MZNMGs. We will emphasize more on these points in our updated version. \n\nWe also emphasize that the techniques of single-agent MDP theory or two-player zero-sum MG theory are not directly applicable to every theorem's proof due to the multi-agent structure. Moreover, we'll expand Section 6, on the convergence results of not only OMWU but also MWU (which is not analyzed in the previous literature) and various algorithms in our updated version of the paper.\n\n\n**Clarity.** Thanks for pointing out that the notation is “cumbersome”, and thanks for understanding that the complication “inherently came from the complication of the model” we studied. We will try our best to lighten the notation in the updated version.\n\n**Minor comments.** \n1. Experiments: Thanks for the suggestion. We thought adding some experiments to validate our theory would be a plus to a theory-oriented paper. We can add back more details in the main paper when we have more space in the final version.\n2. Related work: Thank you very much for bringing up the recent works on learning CE in sequential/extensive games. We will surely include them in our updated version.\n3. Notation typos: Thanks for the careful reading. We will clean up the typos and make them clear.\n4. More intuition: Thanks for the suggestion, we will add more explanations regarding the intuition of proving Prop. 1 and 2. Regarding the importance of Markovianity, as our proof of Prop. 3 is based on backward induction over states, and it is the Markovian policies that preserve the polymatrix structure while inducing in a backward fashion. We will add more details on this also.\n\n**Relationship to Foster et al.** Thanks for bringing up this recent work. This work also established PPAD-hardness for computation, but for having “no-regret” algorithms in general Markov games. It has also provided “statistical” hardness results (even regardless of the computation tractability) for no-regret learning in Markov games without knowing the model. Note that the setting in Foster et al is “finite-horizon”, and the equilibrium they end up finding is “non-stationary”. The authors showed that even in this case, achieving “no-regret” is hard. In contrast, our hardness result is for “computation” only, and it is for Markov stationary CCE-computation. Note that to compute CCE, one may use “no-regret” learning algorithms, but it is not necessarily always the case – one may use algorithms that are not necessarily no-regret to obtain CCE, e.g., Daskalakis et al. and our paper. “No-regret” (in the face of arbitrary adversaries) is a more challenging goal to achieve (than (CC)equilibrium computation). \n\nFinally, we remark, also as stated in Foster et al. Sec. 6.4, that the two results are *not comparable* – stationary Markov CCE as we considered are not “sparse” (see their Definition 3.1), which is key to their hardness result; while they showed the hardness without imposing the “stationarity” condition (as they focused on the “finite-horizon” setting). We will add this discussion in our updated version. \n\nThank you very much again for the insightful comments for helping improve our paper. We hope the responses have addressed them satisfactorily. Please let us know if there are any other comments we can address to help you improve the rating of our paper.\n\n"}, {"review_id": "AdvoPFhpyC", "reviewer": "Reviewer_AdnB", "summary": "The paper considers a subclass of Markov Games (MG) that have local interactions and a zero-sum structure for their Q value functions. This subclass generalizes zero-sum polymatrix games. It's shown that the marginal distribution of a Markov CCE for these games is a Markov  NE. It's then shown that computing a stationary Markov CCE/NE is PPAD-hard. It's then shown that a fictitious play type algorithm converges to a stationary Markov CCE for the special case where the local interactions are given by a star graph where the player at the center of the star controls the state transitions. It's then shown that another algorithm based on optimistic multiplicative weight updates converges to a non-stationary Markov ", "questions": "Q1: Most of the paper analyzes the computation of stationary Markov CCE/NE.  Why is this interesting that stationary equilibrium is hard to compute if a non-stationary one isn't? Why do we want to compute the equilibrium in the first place? The research question proposed in Lines 36-37 is already answered by the non-stationary part of the paper. \n\nQ2: Why does \\mathcal{E}_r appear in a  MZNMG? (e.g., Figure 1 t comes from a polymatrix zero-sum game, but a MZNMG is not defined using a polymatrix zero-sum game. Why is another graph even needed? shouldn't the reward dependencies be dictated by \\mathcal{E}_Q? why would these two graphs be different?  \n\nQ3: Are there interesting cases beyond a single (state-dependent) player driving the state transitions? Given that it was done in [50], I think that a detailed comparison with [50] is needed. ", "limitations": "The technical limitations in this paper are discussed. There is no potential negative societal impact since the paper is computational. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Markov game is a challenging class of games with limited results. The paper makes some progress for this class of games. The analysis is rigorous and non-trivial. The technical aspects of the results are well-discussed. ", "weaknesses": "The motivation for this class of games is unclear and weak. The motivation for the results of this class of games is also vague. The paper is dry and technical with little insight. The presentation is notationally heavy and some of the statements are a bit sloppy. \n\nI'm not sure what meaning the proposed class of games has beyond its technical definition and the paper does very little to expose such meaning. The definition is done on the Q values, which is awkward and unintuitive, and then proposition 1 basically states that a better definition exists. In a polymatrix zero-sum game, the decomposition of the reward makes simple sense. To generalize them to MG, the paper here adds that the transition probabilities need to be decomposable - which doesn't seem nice or intuitive anymore beyond trivial special cases (one player controls the transitions, please see Q3 below). The paper presents one example (even though the title is \"Examples of M(Z)NMGs\") of such a game which is highly contrived, and even for this example, the strong bipartite graph structure condition is needed. This is very unconvincing regarding how useful this class of games is. \n\nThe results for stationary equilibrium are a bit disappointing. The hardness result would be more interesting if it was already agreed that this class of games is interesting - but otherwise, it just looks like a reason not to consider this class of games proposed here. A star structure with the central player controlling the transitions basically means that the N-1 different games are almost separate (up to the mutual state). No motivation is provided for wanting to compute a stationary equilibrium, so these disappointing results are uncalled for. If nothing meaningful can be said there, and there is no reason to believe this case is of special importance, I don't see why the stationary case is any interesting.  \n\nThe statements of the definition and proposition are mostly messy. They are written as one block of text even if they are split into several cases, and if some equations are more important than others. Therefore they are unnecessarily hard to digest. \n\nMore Comments: \n\nThe acronyms are very confusing because they never follow the first letters of the words. \n\nIn Definition 1, Multi-player MG is italic but \"with networked local interactions\" isn't, making it look like only the italic part is the issue here. \n\n\"every stage game with continuation payoffs being the payoff matrices qualifies as an\" - continuation payoffs? \n\nProposition 1 (b) - by always, you mean for every discount factor? this is a bit confusing as stated. \n\nThe definition of N_c can use some words to explain the meaning. This is also true for other definitions in the paper.\n\nThe caption of Figure 1 doesn't explain what's going on (not even that the red and blue are the nodes in the set N_c). Also, shouldn't the arrow by an equality? \n\n\"based on the PCP for PPAD conjecture\" - I guess you mean, if the conjecture holds, then... otherwise nothing can be based on a conjecture \n\nLine 165: if we do not know a priori about  - no \"about\" needed \n\nWhat's the point of the title of Subsection 5.1? that's the only case and only subsection \n\nLine 367 - double period \n\nThe statement of Theorem 2 is lacking and misleading. The main assumption is the star structure (and a single player driving the state transitions), and it's not stated here. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our analysis rigorous and non-trivial, and the technical parts well-discussed. We acknowledge your main comments regarding *motivations*, and sincerely hope our responses below could help you appreciate the significance of the class of games and equilibrium we consider. \n\n**Motivation of the game model and comparing to [50] (Q3)).** As we stated in the introduction, the study of this class of model mainly came from two important motivations in “game theory” and “learning in games”: 1) the emerging behavior of natural *learning dynamics*, e.g., fictitious-play (FP); 2) the *computation tractability* of equilibrium. We push the boundaries in both of these two aspects. Before our work, the only known types of “Markov games (MG)” where FP can reach the equilibrium are either zero-sum [1-3], or identical-interest [4-5]. It was unknown if there are other MGs in which fictitious-play dynamics would reach equilibrium in the long-run. Similarly, before our work, regarding equilibrium computation complexity we know that: a) computing Markov NE (both stationary and non-stationary) is tractable (in polynomial time) for zero-sum and potential MGs; b) computing non-stationary Markov CCE is tractable for general-sum MGs; c) computing stationary Markov CCE is intractable for general-sum MGs [6]. It was unknown if there exist other types of MGs where (Markov) NE maybe *tractable*, and/or Markov stationary CCE maybe *tractable*. The motivation of our work follows exactly from the seminal works of [7-10] (push the boundary on *what types of games have fictitious-play property*), and that of [11-12] (push the boundary on *what types of games may have computationally tractable algorithms for finding the NE*), in the normal-form game setting. We believe these are strong motivations.\n\nFor Definition 1, we have established the structural results in Prop. 1, regarding the if and only if condition for an MG to be qualified as an MZNMG, in terms of its reward and transition dynamics. Essentially, what our model requires is the transition dynamics being an “ensemble” of some transition dynamics that is controlled by each controller agent individually. We emphasize that this “ensemble” dynamics is more than just “single-controller” case in [50], i.e., “one player controls the transitions”, which covers “switched/turn-based” case (though even the single-controller case is an important class of MGs in its own right, see [50]’s Ch 3 and 6, and is definitely not a “trivial” one).\n\nNote that all our examples (*note that we have more than just “one” example, as we stated at the beginning of Sec. 3.2*), which generalize polymatrix matrix games to the Markov setting, satisfy this structure naturally. Hence, we respectfully disagree that the class of games we introduced is vacuous.\n\nFinally, and perhaps encouragingly, we remark that “after” submission of our paper to NeurIPS, a new work [14] was posted on arxiv, which also concerns the generalization of zero-sum polymatrix games to the MG setting. This independent work carries exactly the same motivation as ours. Furthermore, we note that [14] “defines” the zero-sum polymatrix MGs as the ones where: 1) the reward is zero-sum polymatrix, and 2) the transition dynamics is ”switched-controller/turn-based”. This model aligns with and is covered by ours. We hope both of our independent works may *strengthen the motivation of considering this type of MG in the community*. \n\n\n**The motivation for studying stationary equilibrium and Q1).** For infinite-horizon discounted MGs, “stationary” equilibrium is a very natural solution concept to consider. In fact, we believe it is more natural than the non-stationary one, which mainly started to attract attention in the recent literature of *multi-agent RL*, which exclusively focused on the “finite-horizon episodic” setting for ease of exposition and studying the “exploration” problem in RL. Specifically, starting from Shapley’s seminal work [15] that introduced this MG model, to the classical MG literature in economics [16-20], and to the classical literature of multi-agent RL in MGs [21-22], they all focused on studying “stationary” equilibrium in this setting. It is natural since in “single-agent MDPs”, such a policy class is the most widely studied one in infinite-horizon settings, and it should be important to ask about the computational tractability for this class of solutions in the multi-agent game setting. \n\nFinally, “stationary” equilibrium and its stark contrast to “non-stationary” equilibrium in terms of computation complexity have been a central topic in several recent breakthrough results [23-24]. It was shown that “stationary” equilibrium can be computationally intractable, while the “non-stationary” counterpart can be computed using backward induction. This is particularly interesting since it is in stark contrast to the single-agent setting, where there is no such difference. Hence, we believe studying stationary equilibrium in MGs is a well-motivated topic. We believe studying the computation of this type of equilibria can help us paint a more complete picture of equilibrium computation for this new class of MGs, and better understand the fundamental limit of this model. \n\n**Q2 Answer).** We intended to keep $E_r$ in Figure 1, in order to demonstrate the fact that the graph that characterizes the separable property of the “reward” can be different from the graph that characterizes the separable property of Q-functions. We will make sure to introduce this notation property and explain it more explicitly. \n\nWe will also correct the minor grammar issues/typos and presentation issues. \n\nThank you very much again for the insightful comments for helping improve our paper. Please let us know if there are any other comments we can address to help you improve the rating of our paper.\n\n[14] \"Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria.\" arXiv:2305.14329.\n\n"}]

Author rebuttal:

Meta-review: Accept with a large number of expert and clearly supporting reviews. The authors are encouraged to address the reviewers' suggestions in improving the final version of their paper.
Decision: Accept (poster)