--- title: "On the Convergence of Fictitious Play: A Decomposition Approach" authors: - "Yurong Chen" - "Xiaotie Deng" - "Chenchen Li" - "David Mguni" - "Jun Wang" - "Xiang Yan" - "Yaodong Yang" doi: "10.24963/ijcai.2022/26" url: "https://ijcai.org/proceedings/2022/26" pdf: "https://ijcai.org/proceedings/2022/0026.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "179-185" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Multi-agent Learning" - "Agent-based and Multi-agent Systems: Noncooperative Games" - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" --- # On the Convergence of Fictitious Play: A Decomposition Approach Yurong Chen, Xiaotie Deng, Chenchen Li, David Mguni, Jun Wang, Xiang Yan, Yaodong Yang *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 179-185. DOI: [10.24963/ijcai.2022/26](https://doi.org/10.24963/ijcai.2022/26) ## Abstract Fictitious play (FP) is one of the most fundamental game-theoretical learning frameworks for computing Nash equilibrium in n-player games, which builds the foundation for modern multi-agent learning algorithms. Although FP has provable convergence guarantees on zero-sum games and potential games, many real-world problems are often a mixture of both and the convergence property of FP has not been fully studied yet. In this paper, we extend the convergence results of FP to the combinations of such games and beyond. Specifically, we derive new conditions for FP to converge by leveraging game decomposition techniques. We further develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. Finally, we analyse a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge. ## Full text ## 1 Introduction Solving Nash equilibrium (NE) [Nash, 1950; Deng et al., 2021] in multi-player games has become a central interest in a variety of fields including but not limited to economics, computer science and artificial intelligence. Among the many NE solvers, fictitious play (FP) [Brown, 1951] is one of the most well-known learning algorithms. In FP, at each iteration, each player takes a best response to the empirical average of the opponent's previous strategies. It is guaranteed that FP dynamics converge to an NE on two-player zerosum games [Robinson, 1951] and potential games [Monderer and Shapley, 1996a; Monderer and Shapley, 1996b; Mguni et al., ], with no need to access the other player's utility information. Thus, the design principle of FP (i.e., the iterative best-response dynamics) has inspired many other approximation solutions to NE. For example, in solving two-player zero-sum games, two representative methods are double oracle (DO) [McMahan et al., 2003; Dinh et al., 2021] and policy space response oracle (PSRO) [Lanctot et al., 2017; Feng et al., 2021; Perez-Nieves et al., 2021; Liu et al., 2021] where a subgame NE is adopted as the best-responding target and multi-agent reinforcement learning (MARL) algorithms [Yang and Wang, 2020] are applied to approximate the best response. Similarly, Heinrich et al. [2015] combined fictitious self-play with deep RL methods and demonstrated remarkable performance on Leduc Poker and Limit Texas Holdem at real-world scale. Besides its inspirations for modern MARL algorithms [Muller et al., ; Yang et al., 2018], FP itself has been shown to have good performance of converging to approximate equilibria on some more general games [Candogan et al., 2013; Ostrovski and van Strien, 2014], and is still a popular interest of research to the communities of both game theory and machine learning [Swenson et al., 2018]. ∗Corresponding Author However, the assumptions of zero-sum or potential games are rather limited. As Dasgupta and Collins [2019] mentioned, adversarial learning has been modeled as a two-player zero-sum game, but chances are that the learner's loss may not equal the adversary's utility. Similar as zero-sum games characterizing full competition, potential games can be regarded as full cooperation. While in most real applications, there are both competition and cooperation among players. For example, in a market, sellers for the same type of goods are not only players competing for the same group of buyers, but also collaborators attracting more buyers to the market. More general results for FP to converge on combinations of competition and cooperation are needed, considering its current limited positive convergence results. Our techniques and results. We leverage two game decomposition techniques, Hodge Decomposition [Candogan et al., 2011] and Strategic Decomposition [Hwang and ReyBellet, 2020], to study the convergence of FP on mixtures of games modelling full competition and cooperation. The idea of game decomposition is to treat the set of games as a linear space and decompose a game into several simple basis games, whose NEs are easy to characterize. Interestingly, in both decompositions, a game is made up of a competitive part, a cooperative part and a trivial part. It is known that FP converges on all these basis games. Combining two decompositions enables us to find latent relationships among games and study how a game's dynamics is influenced by each component. We note that, however, there will be no convergence guarantee for FP on arbitrary combinations of these basis games, since they span the whole game space, and FP has been proved to fail to converge on all games [Shapley, 1964]. The contributions of this paper are as follows, - We prove that FP converges on any linear combination of a harmonic game (competition) and a potential game (cooperation), so long as they sum to be strategically equivalent to a zero-sum game or to an identical interest game. The conditions are polynomial-time checkable. - We show that, utilizing a linear parameter, games lying in these two equivalent classes can be transformed from one class into another. - We give a new analysis of the non-convergence of Continuous-time FP (CFP) on the classic example, the Shapley game, from the view of dynamical system and game decomposition, and provide a sufficient condition about initial conditions for it to converge on linear combinations of zero-sum games and identical interest games. Since many machine learning methods are built on FP, the fact that FP converges in larger game classes provides a guarantee for them to be applied to more real situations safely. We argue that the classes of games considered in our paper are of wide interest and include many important games like load balancing games [V¨ocking, 2007], cost and market sharing games with various distribution rules [Gopalakrishnan et al., 2011], and strictly competitive games [Adler et al., 2009]. Related work. Our analysis is mainly based on the techniques of game decomposition. To make the paper selfcontained, we discussed related work on game decompositions here, and put the full related work in the Appendix. Candogan et al. [2011] and Hwang and Rey-Bellet [2020] studied decompositions for finite games. Helmholtz Decomposition [Balduzzi et al., 2018], on the other hand, studied the decomposition of continuous games into potential games and Hamiltonian games. But few works are about making use of decomposition to analyze games. To the best of our knowledge, utilizing game decomposition techniques to analyze game dynamics is still a new area. Tuyls et al. [2018] decomposed an asymmetric bimatrix game, where two players have the same number of pure actions, into two one population games, from the evolutionary game theory point of view. Cheung and Tao [2021] utilized the canonical decomposition of decomposing a game into a zero-sum game and an identical interest game to study the chaotic behaviors of general-sum games under multiplicative weight dynamics. We study the convergence properties of fictitious play. Instead of checking which component dominates the other, we model the mixture of two basis games by linear combinations and see how the game patterns evolve when the parameter changes smoothly and continuously, which can also be seen as a linear homotopy from the view of homotopy method. Paper organization. Section 2 introduces necessary preliminaries. Section 3 shows our main convergence results. The illustration of transformations between cooperation and competition is shown in Example 1 and Section 3.2. Section 4 analyzes the Shapley game and give a condition for CFP to converge. Section 5 summarizes and give future work. ## 2 Background We use bold lowercase characters to denote vectors. 1n and 0n denote n-dimensional all-one and all-zero vectors, respectively, ei the vector the ith coefficient of which is 1 and all other coefficients are 0. [n] denotes the set {1, . . . , n}. ## 2.1 Games and Nash Equilibrium We focus on two-player bimatrix games. We use bold uppercase letters to denote games and uppercase letters to denote matrices: A game G is given in the bimatrix form (A,B), where the first (second) matrix in the pair denotes the payoff matrix of player 1 (player 2, respectively). Both matrices have dimension m × n, i.e., player 1 (player 2) has m (n, respectively) actions. We call an action i a pure strategy, and a distribution over all actions a mixed strategy. Denote the set of all mixed strategies as ∆m, where ∆m := {p ∈ Rm : pi ≥ 0, ∀i ∈ {1, . . . ,m}, ∑mi=1 pi = 1}. Given a game G = (A, B) and two mixed strategies p ∈ ∆m, q ∈ ∆n, player 1 (player 2)'s utility is p⊤Aq (p⊤Bq, respectively). We use BRi(·,G) to denote player i's best response set: We omit the last variable of BRi when there is no confusion. A Nash equilibrium (NE) is a pair of mixed strategies such that no one wants to deviate with the other's strategy fixed: Definition 1. Strategy pair (p∗ , q∗ ) is a Nash Equilibrium (NE) of game G = (A, B) if for any p ∈ ∆m and q ∈ ∆n, We call an NE pure when strategies in the NE are all pure strategies, and mixed otherwise. Let G be the set of all bimatrix games. Given games G1 = (A1,B1), G2 = (A2,B2) ∈ G, define their addition to be G1 +G2 := (A1 +A2,B1 +B2). Given a scalar α ∈ R and a game G = (A,B), define the scalar multiplication to be αG = (αA, αB). Now G is a linear space and we can consider the combinations and decompositions of games. ## 2.2 Basic Games and Relations among Games We introduce subspaces of G that are basic in this paper. Definition 2. Define the following subspaces of G 1. Identical interest games, I := {(A, B) ∈ G : A = B} 2. Zero-sum games, Z := {(A, B) ∈ G : A + B = 0} 3. Non-strategic games, E := {(A, B) ∈ G : A = 1mu⊤, B = v1⊤n , u ∈ Rn , v ∈ Rm} 4. Normalized games, N := {(A,B) ∈ G : ∑mj=1 Aji = 0, ∀ i ∈ [n]; ∑nj=1 Bij = 0, ∀ i ∈ [m]} Identical interest games and zero-sum games are important games in game theory and machine learning, especially in multi-agent learning and adversarial learning, with the former modeling team cooperation and the latter modeling competition. In a non-strategic game, a player's utility only depends on the other player's strategy, and is not affected by her own strategy at all. Thus any strategy pair of the game is an NE. Noticing that adding a non-strategic game to a game does not change its original game structure, e.g., the best response structure and NEs, one can define an equivalence relation between two games if they only differ by a non-strategic game (also called strategic equivalence by Hwang and Rey-Bellet [2020]), and mainly focus on the normalized games. In a normalized game, the sum of one player's utilities, with her own strategy changing and the other's fixed, equals to zero. Different from Hwang and Rey-Bellet [2020], we call two games G and G′ are additionally equivalent if G′ = G+E for some E ∈ E. Here we introduce a more general equivalence among games. Definition 3. Game G = (A,B) is strategically equivalent to game G′ = (A′ ,B′ ), if there exist two positive constants α, β ∈ R+ and a non-strategic game E ∈ E such that While additional equivalence is a special case of strategic equivalence, the notion of additional equivalence is compatible with the operations of the space. Lemma 1 shows that both equivalences preserve the best response structure. Lemma 1. Given two strategically equivalent games G and G′ , we have We use S(·) (A(·)) to denote the set of games that are strategically (additionally) equivalent to the games in ·. In particular, we call games in S(Z) (S(I)) zero-sum equivalent games (identical interest equivalent games, respectively). ## 2.3 Discrete-time Fictitious Play (DFP) In fictitious play, each player regards the empirical distribution over the other player's actions as her belief towards the other player's mixed strategy, and acts myopically to maximize her utility in the next step. Specifically, let p(t) ∈ ∆m and q(t) ∈ ∆n be the beliefs of two players' strategies at time step t, then the sequence (p(t), q(t)) is a discrete-time fictitious play (DFP) if: and for all t: With a specific tie-breaking rule, we can regard BRi(·) as a vector and the inclusion above becomes equality. In the following sections, DFP is simply called FP. With abuse of notation, the term FP refers to the dynamic rules in Eqn. (1) or the sequences generated by the rules, according to the context. We say a game has fictitious play property (FPP) if every FP sequence of it converges. Noticing that games with the same best response structure enjoy the same FPP. ## 3 Convergence on the Combinations of Cooperation and Competition In this section, we formally present our first two main results. In Section 3.1, we introduce two game decompositions, and present our results on the linear combinations of basis games. In Section 3.2, we illustrate how the players' relationships transformwith respect to the linear parameter. ## 3.1 Proof of Convergence by Game Decompositions Before formally stating our first result, we present two important game decompositions: Theorem 1 (Strategic Decomposition). [Hwang and ReyBellet, 2020] The space of games G can be decomposed as: where B := (I + E) ∩ (Z + E) is the set of zero-sum equivalent potential games, ⊕ denotes the direct sum of two linear subspaces. I + E is the space of games additionally equivalent to identical interest games, and is actually the space of all potential games. The equivalence between this definition and the one using potential function is shown in Appendix. As shown by Hwang and Rey-Bellet [2020], a two-player zero-sum equivalent potential game B ∈ B has the form for some u, y ∈ Rm, v, x ∈ Rn and E = (1mx⊤, y1⊤n ) ∈ E . That is, a player's utility is not affected by the other's strategy, which can be seen as the opposite of non-strategic games. Each player has a dominant strategy, and a pure NE exists. Theorem 2 (Hodge Decomposition). [Candogan et al., 2011] The space of games G can be decomposed as: where P := N ∩ (I +E) denotes normalized potential games, and H := {(A,B) ∈ N : mA+nB = 0} normalized harmonic games. P + E is the set of all potential games. H+E is the set of all harmonic games. The definition of normalized harmonic games tells that they are like zero-sum games. Thus both decompositions show that any bimatrix game is made up of a fully cooperative component, a fully competitive component and a component that either has both features or is trivial. Combining the decompositions and equivalences makes us able to study bimatrix games from multiple angles. Since the basis games in the decompositions generate the whole game space, FP will not converge on all combinations of them (a famous example of non-convergence is the Shapley game [Shapley, 1964]). Notice that on all basis games, however, FP will converge: results on zero-sum games and potential games are known [Monderer and Shapley, 1996a; Robinson, 1951]. When the tie-breaking rule is decided, best responses in FPs are always the same on games in B and E - a dominant strategy in B ∈ B and the prescribed strategy by the tie-breaking rule in E ∈ E - thus FP will converge. Figure 1: Game G ∈ S(Z): G = (2Z, -3Z), where Z ∈ Rm×n . In Appendix, we provide a simple proof to show that FP also converges on harmonic games. It is then interesting to study under what conditions do combinations of these games preserve FPP. By first conducting experiments on mixtures of normalized harmonic games and normalized potential games, we find out that if they are components of a zero-sum game, then FP converges on any linear combination of them. The following theorem gives the formal explanation for this phenomenon and provide a more general condition for FP to converge: if their sum is either fully competitive or cooperative, then any linear combination of these games has FPP. Recall that the set S(·) is the set of games strategically equivalent to games in · , then we have: Theorem 3. For any game G ∈ S(Z) ∪ S(I) with Hodge Decomposition, where P ∈ P, H ∈ H, E ∈ E. Then for any λ ∈ R, game λP + (1 - λ)H has FPP. We note that the decomposition of a game that is either strategically equivalent to a zero-sum game or to an identical interest game is non-trivial: It can have all game components, since a game lying in these two classes does not necessarily belong to any basis game class. One can refer to the decomposition of the game in Example 1 in Appendix C. To prove Theorem 3, we first give a necessary lemma. Lemma 2 states the properties of zero-sum equivalent potential games; it shows that sets S(I) and S(Z) are closed under the operation of adding a zero-sum equivalent potential game. With Lemma 2, we can now prove Theorem 3. The convergence of games λP+(1-λ)H are actually the trade-offs between cooperation (P) and competition (H). Though the decompositions of games considered are non-trivial, by further decomposing the components using the other decomposition, we find interesting relations among components of different decompositions, which is a key technique in our proof. Proof sketch of Theorem 3. We show the proof sketch of the case when G ∈ S(Z) here and the full proof is in Appendix. Let P = I+E = (I, I)+E, where I ∈ I, E ∈ E, I ∈ Rm×n . H can be formulated as (nZ, -mZ) for some Z ∈ Rm×n . When G = (Z ′ , -αZ ′ )+E′ ∈ S(Z), where Z ′ ∈ Rm×n , α > 0, E′ ∈ E, then we have By letting E′ - E = (E1, E2), where E1, E2 ∈ Rm×n satisfies E1 = 1mu⊤, E2 = v1⊤n , for some u ∈ Rn , v ∈ Rm, we have I and Z represented as linear combinations of Z ′ , E1 and E2. Thus for any λ ∈ R, By the definition of non-strategic games and Eqn. (2), (a2(λ)E1 +a3(λ)E2, b2(λ)E1 + b3(λ)E2) ∈ B is a zerosum equivalent potential game. When a1(λ)b1(λ) ̸= 0, game (a1(λ)Z ′ , b1(λ)Z ′ ) ∈ S(Z) ∪ S(I). By Lemma 2, λP + (1 - λ)H ∈ S(I) ∪ S(Z) and thus has FPP. When a1(λ)b1(λ) = 0, λP+(1-λ)H has one payoff matrix in the form of x1⊤n + 1my⊤ for some x ∈ Rm, y ∈ Rn . The player with this kind of payoff matrix has a dominant strategy. During each time step of FP, the player will choose her dominant strategy, and the other best responds to that dominant strategy. The sequence will converge to a pure NE. Following Theorem 3, define D to be a new set of games, in which one of the payoff matrices has the form of x1⊤n + 1my⊤ for some x ∈ Rm, y ∈ Rn , then: Corollary 1. For any game G ∈ D with Hodge Decomposition where P ∈ P, H ∈ H, E ∈ E. Then for any λ ∈ R, game λP + (1 - λ)H has FPP. Conditions in Theorem 3 and Corollary 1 can be checked in linear time, e.g. through the method by Heyman [2019]. ## 3.2 Transformations fromCooperation to Competition We use one example to show the non-trivial decompositions of games considered in Section 3.1 and how the proportions of the cooperative component and the competitive component influence the game, when λ ∈ [0, 1] ranges from 0 to 1. Example 1. A game in S(Z) is shown in Figure 1. We decompose this game using Hodge Decomposition into three components P ∈ P, H ∈ H and E ∈ E, the details of which are in Appendix C, and compute the game G(λ) = λP + (1 - λ)H. The changes of NE which FP converges to with λ changing from 0 to 1 is shown in Figure 2. In Figure 2a, the strategy trajectories are presented in the mixed strategy simplex: each vertex of the triangle is an action vi. We draw mixed strategy p = (p1, p2, p3) ∈ ∆3 on the convex combination of the vertices, ∑3i=1 pivi. The green dots represent the strategy trajectory of player 1, and the blue dots that of player 2. The star sign denotes the strategies when λ = 1. We set the step length to be 0.001. For each λ, we run FP starting from (v1, v1) for 500,000 rounds. The ![Image](https://ijcai.org/proceedings/2022/fulltext/26/image_000000_2ddeea8ac0971982e014f578924f7783045851cf3f6ce76def99d6dd0ca04103.png) ![Image](https://ijcai.org/proceedings/2022/fulltext/26/image_000001_b345ca72bd72d5bb004b46bd1ac8265afd516bef5894756b760c37ec49a5d0cd.png) (b) Equilibrium strategy changes of player 1. Figure 2: How Nash equilibrium of game λP + (1 - λ)H changes as the linear parameter λ increases from 0 to 1. (a) The changes of equilibrium strategies of both players are shown in one strategy simplex. The black arrows tell the direction of the changes. The stars denote the stopping point. When λ is small, the harmonic part dominates. The game shows more competitive patterns, as the equilibrium strategies are mixed in the interior of the strategy simplex. As λ gets larger, the support of equilibrium strategies shrinks. (b) The changes of player 1's strategy in a line chart. In the green area (when λ < 56 ), the game is zero-sum equivalent. In the yellow area (when λ > 56 ), the game is identical interest equivalent. When λ exceeds 5 6 , the game is more cooperative, and the equilibrium stays pure. strategy trajectories of both players start at the center of a strategy simplex, i.e. the uniform equilibrium of harmonic games [Candogan et al., 2011]. As λ increases, the strategies move towards the boundaries, and their supports become small. When λ is large enough, they reach a pure NE (nodes with stars), which is typical of potential games, and no longer moves. Figure 2b shows the changes of player 1's strategies in line chart. We utilize the algorithm by Heyman [2019] to decide when will G(λ) ∈ S(Z). When λ < 5 6 , The competitive part takes over, G(λ) ∈ S(Z). When λ > 56 , G(λ) ∈ S(I). When λ = 56 , G(λ) ̸∈ S(Z) ∪ S(I) but belongs to D instead. We draw the point λ = 5 6 on Figure 2b. One can find out that when λ is less than but close to 56 , the equilibrium for FP to converge to already becomes pure and never moves even when λ exceeds 56 . When λs in the above examples reach the threshold, the games enter D instead of S(Z) ∩ S(I). We argue that games in D show the same dynamic patterns with games in S(Z) ∩S(I). Specifically, we show that S(Z) ∩S(I) = A(Z) ∩A(I) = B, and players in games belonging to B have dominant strategies. In both classes of games, the players will choose a determined strategy and the dynamics converge to the corresponding pure NE directly. The process of transforming from zero-sum equivalent games to identical interest equivalent games with the changes of a linear parameter can be seen as an instinct feature of these two games, and a bridge linking non-cooperative gametheoretic view of cooperation and competition. Using a linear parameter that changes with time, we may be able to model how the relationships of players evolve in real world. Furthermore, when λ is small enough, we can regard the potential part in λP + (1 - λ)H as a small perturbation added up to a harmonic game. Our result shows that when the perturbation satisfies certain conditions, the game with perturbations can still be regarded as a zero-sum equivalent game. ## 4 Analysis on the Non-convergence Example In this section, we use game decompositions to give a new analysis of the classic non-convergent example of FP, the Shapley game [Shapley, 1964]. We consider Continuoustime Fictitious Play (CFP), a useful tool to give insights into DFP's dynamics. we present the Shapley game and introduce a novel function, the best response utility function. We give two results about initial conditions based on this function. ## 4.1 Continuous-time Fictitious Play (CFP) DFP can be regarded as an update procedure for players' empirical beliefs, where the update rate is 1. Now consider the corresponding continuous version, by rescaling the rate to δ > 0 and letting δ → 0. This equivalently defines the derivatives of the sequence (p(t), q(t)) with respect to t : 1 The detailed derivation from DFP to CFP is in Appendix D. For CFP, we define another stable state following the studies on dynamical systems. Definition 4 (Cycle). A CFP follows a cycle C if there is an integer K > 0 and a sequence of K pairs of pure strategies: It is a special case that a CFP converges to an NE when it follows a cycle. So far, all the known convergence results of CFP and DFP are the same. Intuitively, when discrete time step tends to +∞, so as the denominator of Eqn. (1), the changes of (p(t), q(t)) at each time step become infinitesimal, and will resemble the derivatives defined by Eqn. (3). Thus, CFP can provide useful insights into original DFP, though the relationships of two dynamics are still not clear. Now we study the conditions that a CFP with some initial conditions converges to an NE. 1 One can further rescale the variable t to t′ = ln t (for t > 0) to eliminate the the denominator. Figure 3: Hodge Decomposition and Strategic Decomposition of the Shapley game. It is a coincident that they are the same. ![Image](https://ijcai.org/proceedings/2022/fulltext/26/image_000002_c0730e020057d4f4e973f41b19dd9bf5b22885a2ce6bd41266ee391a12fa4589.png) ## 4.2 The Shapley Game The Shapley game, proposed by Shapley [1964], is a counterexample of FP's convergence: except under certain initial conditions, FP does not converge to NE. Figure 3 shows its payoff matrices and the two decomposition results. When two players' initial strategies are different, e.g. (1, 2), FP follows cycle C1 = {(1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (3, 2)}, but does not converge: both players' strategies will change periodically but never reach any fixed point. When their initial strategies are the same, e.g. (1, 1), FP follows another cycle C2 = {(2, 2), (1, 1), (3, 3)}, and tends to an NE (p, q), where p = q = ( 1 3 , 13 , 13 ). ## 4.3 The Best Response Utility Function We further consider more general combinations of the decomposed components G(λ) = λP + (1 - λ)H = λI + (1 - λ)Z. Define the best response utility (BRU) function for game G = (A, B) and players' strategies (p, q) to be It is the sum of maximal utilities each player can get by her best response to the opponent's strategy. We omit the last variable of U when there is no confusion. Experimental analysis (in Appendix D) on the Shapley game shows that whether DFP converges to NE or not, U always converges. For the empirical frequencies (p(t), q(t)) (t ≥ 1) obtained by CFP, consider the derivative of U(p(t), q(t)) (U(t) for short) with respect to t, for almost all t, then for any fixed t0 > 0, we have where G = A + B, i(τ) and j(τ) are short for the index of BR1(q(τ)) and BR2(p(τ)). The detailed derivation is in Appendix. This leads to a sufficient condition for the convergence of BRU. Lemma 3. For a gameG= (A,B), let G = A+B. Assume CFP follows a cycle {(i1, j1) , . . . , (iK, jK)}. If Gi1,j1 = · · · = GiK,jK , then BRU converges. Back to the Shapley game, on cycle C2, Gi1,j1 = · · · = Gi3,j3 = minGij. To be compared, on cycle C1, Gi1,j1 = · · · = Gi6,j6 > minGij . This means BRU converges but not to the minimal possible value, which coincides with the fact that the strategies fail to converge. One can further find out that when a CFP starts with the same strategies for both players, i.e., when it converges to NE, by the symmetry of the game, p(t) = q(t) for all t. Then for all strategy pairs (p(t), q(t)) related to C2, ˙U satisfies where I is the payoff matrix of the Shapley game's normalized identical interest component, and e(t) = BR1(q(t)) = BR2(p(t)). U(t) will keep decreasing till it tends to NE. Now we consider the Shapley game as a linear combination of a normalized identical interest game and a normalized zero-sum game and we state the reason formally in Theorem 4 why it converges under such initial conditions. Given a cycle C of game G such that there exist CFPs tending to C, let P(C,G) be all the mixed strategy pairs that lie on the paths following C, and Conv(S) be the closed convex hull of set S. Denote the set of G's NEs as X(G). We have Theorem 4. For game G(λ) = λI + Z for some I ∈ (I ∩ N) and G ∈ (Z ∩ N), λ ∈ R. If from an initial point, CFP on G(λ) enters the same cylce C of G(0), where C is a cycle that a convergent CFP on G(0) will tend to, and for all (p, q) ∈ Conv(P(C,G))\X(G(0)), ˙U(p, q) < 0, then CFPs on G(λ) which tend to C will converge to an NE. Theorem 4 gives a sufficient condition for a CFP to converge. Intuitively, when |λ| is small enough, the dynamics of G(λ) will resemble that of G(0). If CFPs on these games enter the same cycle of G(0), and ˙U < 0 for all points related to this cycle, then CFPs on G(λ) converge to NE. ## 5 Conclusion and FutureWork Decomposing the game space into combinations of simple classes enables us to find the new relations among games. In this paper, we use this method to prove a new condition for FP to converge and build a bridge between games modelling full competition and cooperation. We derive an instinct property for them that these two classes of games can be mutually transformed to the other with a simple parameter. This ability of mutual transformation may be applied in the dynamic multi-agent systems in which agents' relationships vary with time, which helps study complex real environments. Furthermore, we analyze the well-known example of FP's nonconvergence, the Shapley game, and give a sufficient condition for its continuous version to converge. As for the future work, the first one is to have more analysis on FP dynamics using game decomposition techniques. We note that it will be of vital importance but great challenge to give a full characterization, and it is impossible to have a convergence guarantee on arbitrary combinations of games. Another interesting problem is to study the dynamical properties of simple games, e.g., zero-sum games, with perturbations. ## Acknowledgments This work is supported by Science and Technology Innovation 2030 -"The Next Generation of Artificial Intelligence" Major Project No. (2018AAA0100901). ## References 1. [Adler et al., 2009] Ilan Adler, Constantinos Daskalakis, and Chris- tos H Papadimitriou. A note on strictly competitive games. In In- ternational Workshop on Internet and Network Economics, pages 471-474. Springer, 2009. 2. [Balduzzi et al., 2018] David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The me- chanics of n-player differentiable games. In International Con- ference on Machine Learning, pages 354-363. PMLR, 2018. 3. [Brown, 1951] George W Brown. Iterative solution of games by fic- titious play, 1951. Activity Analysis of Production and Allocation (TC Koopmans, Ed.), pages 374-376, 1951. 4. [Candogan et al., 2011] Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decompositions of games: Harmonic and potential games. Mathematics of Opera- tions Research, 36(3):474-503, 2011. 5. [Candogan et al., 2013] Ozan Candogan, Asuman Ozdaglar, and Pablo A Parrilo. Dynamics in near-potential games. Games and Economic Behavior, 82:66-90, 2013. 6. [Cheung and Tao, 2021] Yun Kuen Cheung and Yixin Tao. Chaos of learning beyond zero-sum and coordination via game decom- positions. In ICLR 2021. OpenReview.net, 2021. 7. [Dasgupta and Collins, 2019] Prithviraj Dasgupta and Joseph Collins. A survey of game theoretic approaches for adver- sarial machine learning in cybersecurity tasks. AI Magazine, 40(2):31-43, 2019. 8. [Deng et al., 2021] Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang. On the complexity of comput- ing markov perfect equilibrium in general-sum stochastic games. arXiv preprint arXiv:2109.01795, 2021. 9. [Dinh et al., 2021] Le Cong Dinh, Yaodong Yang, Zheng Tian, Nicolas Perez Nieves, Oliver Slumbers, David Henry Mguni, Haitham Bou Ammar, and Jun Wang. Online double oracle. arxiv preprint arxiv:2103.07780, 2021. 10. [Feng et al., 2021] Xidong Feng, Oliver Slumbers, Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, and Yaodong Yang. Neural auto-curricula in two-player zero-sum games. Ad- vances in Neural Information Processing Systems, 34, 2021. 11. [Gopalakrishnan et al., 2011] Ragavendran Gopalakrishnan, Ja- son R Marden, and Adam Wierman. Characterizing distribution rules for cost sharing games. In International Conference on NETwork Games, Control and Optimization (NetGCooP 2011), pages 1-4. IEEE, 2011. 12. [Heinrich et al., 2015] Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive-form games. In Proceedings of The 32nd International Conference on Machine Learning, pages 805-813, 2015. 13. [Heyman, 2019] Joseph Lee Heyman. On the Computation of Strategically Equivalent Games. ProQuest LLC, Ann Arbor, MI, 2019. Thesis (Ph.D.)-The Ohio State University. 14. [Hwang and Rey-Bellet, 2020] Sung-Ha Hwang and Luc Rey- Bellet. Strategic decompositions of normal form games: Zero- sum games and potential games. Games and Economic Behavior, 2020. 15. [Lanctot et al., 2017] Marc Lanctot, Vinicius Zambaldi, Audrūnas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In NeurIPS, pages 4193- 4206, 2017. 16. [Liu et al., 2021] Xiangyu Liu, Hangtian Jia, Ying Wen, Yaodong Yang, Yujing Hu, Yingfeng Chen, Changjie Fan, and Zhipeng Hu. Unifying behavioral and response diversity for open-ended learning in zero-sum games. NeurIPS, 2021. 17. [McMahan et al., 2003] H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions con- trolled by an adversary. In ICML-03, pages 536-543, 2003. 18. Mguni et al., ] David H Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang. Learning in nonzero-sum stochastic games with poten- tials. In ICML 2021, pages 7688-7699. PMLR. 19. [Monderer and Shapley, 1996a] Dov Monderer and Lloyd S. Shap- ley. Fictitious play property for games with identical interests. Journal of Economic Theory, 68(1):258-265, 1996. 20. [Monderer and Shapley, 1996b] Dov Monderer and Lloyd S Shap- ley. Potential games. Games and economic behavior, 14(1):124- 143, 1996. 21. Muller et al., ] Paul Muller, Shayegan Omidshafiei, Mark Row- land, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Marc Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess, Thore Graepel, and Remi Munos. A generalized training approach for multiagent learning. In ICLR 2020. 22. [Nash, 1950] John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-49, 1950. 23. [Ostrovski and van Strien, 2014] Georg Ostrovski and Sebastian van Strien. Payoff performance of fictitious play. J. Dyn. Games, 1(4):621-638, 2014. 24. [Perez-Nieves et al., 2021] Nicolas Perez-Nieves, Yaodong Yang, Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. In ICML, pages 8514-8524. PMLR, 2021. 25. [Robinson, 1951] Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2):296-301, 1951. 26. [Shapley, 1964] Lloyd Shapley. Some topics in two-person games. Advances in game theory, 52:1-29, 1964. 27. [Swenson et al., 2018] Brian Swenson, Ryan Murray, and Soum- mya Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 56(4):2734-2767, 2018. 28. [Tuyls et al., 2018] Karl Tuyls, Julien Pérolat, Marc Lanctot, Georg Ostrovski, Rahul Savani, Joel Z Leibo, Toby Ord, Thore Grae- pel, and Shane Legg. Symmetric decomposition of asymmetric games. Scientific reports, 8(1):1-20, 2018. 29. [Vöcking, 2007] Berthold Vöcking. Selfish load balancing. Algo- rithmic game theory, 20:517-542, 2007. 30. [Yang and Wang, 2020] Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theo- retical perspective. arXiv preprint arXiv:2011.00583, 2020. 31. [Yang et al., 2018] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforce- ment learning. In International Conference on Machine Learn- ing, pages 5571-5580. PMLR, 2018.