# Modeling and Stability Analysis for Markov Jump Networked Evolutionary Games

Authors: Guodong Zhao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper investigates the algebraic formulation and stability analysis for a class of Markov jump networked evolutionary games by using the semitensor product method and presents a number of new results. Firstly, a proper algorithm is constructed to convert the given networked evolutionary games into an algebraic expression. Secondly, based on the algebraic expression, the stability of the given game is analyzed and an equivalent criterion is given. Finally, an example works out to support the new results.


---

## Body

## 1. Introduction

The importance of networked evolutionary games (NEGs) [1] has been recognized many scholars recently. Unlike traditional n-player game, an NEG consists of a network graph and a basic game. The nodes in the network represent players and the edges in the network represent interaction relationship among players. Every player in the given game only plays with its neighbors. Furthermore, in the given game, players have the specialized strategy updating rules to adjust their own strategy choices. They are only affected by their neighbors. It coincides with an obvious fact that, in many practical economic activities, each individual is only in contract with its trade partners. This distinguishing feature makes NEGs theory be a very appealing research topic in recent years [2].In the last decades, a very useful mathematical tool, called the semitensor product method (STP) of matrices, has been proposed by [3]. With this tool, [3] proposed a method to transform Boolean networks, Boolean control networks, and mix-valued logical networks into some kinds of difference equations. Then, one could investigate them by using mathematical tools in control theory.Up to now, this method has been successfully applied to the analysis and control of Boolean networks and mix-valued logical networks, and many essential results have been obtained, such as the calculation of fixed points and cycles and the controllability and observability of Boolean networks; see [3–19] for details. References [17, 20] presented the recent applications for STP method in engineering and finite-valued systems, respectively. See [20–29] for more recent developments about the application of STP method in logical networks.In recent years, many scholars have attempted to study NEGs via STP method. For many specific NEGs, they transformed the given NEGs into some proper algebraic expressions, logical networks, for example. Based on “the myopic best response adjustment rule”, [30] designed a proper algorithm to construct the structural matrices of the updating laws for every players in the given NEG. Reference [31] gave the description of the NEG and investigated the relationship between the given NEG and the given logical networks. NEGs defined on finite networks were considered by [32], which converted the given NEGs to a kind of logical networks and solved the optimization problem when one player was regarded as a control. Reference [33] investigated evolutionary game theoretic demand-side management and control for a class of networked smart grid. A class of event-triggered control for finite evolutionary networked games was studied by [34]. Reference [16] studied stochastic set stabilization of n-person random evolutionary Boolean games and its applications.It is worth noting that all of the above results are concentrated on NEGs with pure strategy dynamics except [16]. However, the fact that most evolutionary games are related to random dynamics more or less cannot be neglected. The work [35] considered an interesting evolutionary game. In the game, major player is with infinite time horizon and the other players, called minor players, are with finite time horizons. At any time, when some new players enter the evolutionary game, the number of them is a random variable, which has a distribution depending on the number of the players who have entered the game at that moment. This situation is called random entrance, which is modeled as a Markov chain. In random entrance, there exists a long living player which has interaction relationships with the other players and the interactions are existing for a certain period. This situation is very common, University-Student Games [36], for example.Actually, we can model the above evolutionary games with random entrance as a kind of networked evolutionary defined on finite networks. For every time, the entered players make up a network. The given game evolves on these finite networks. Thus, this paper considers this kind of networked evolutionary games as Markov jump networked evolutionary games (MJNEGs). In this paper, we would give the formal description of MJNEGs and analyze the stability of MJNEGs.The main works of this paper are as follows:(1) The STP method is firstly applied to the study of MJNEGs. (2) The method to formulate the given MJNEGs as an algebraic expression is proposed. (3) The stability analysis of MJNEGs is presented in this paper, and an equivalent test criterion is given.Notations:  Rm×n denotes the set of m×n real matrices. Rm×n+ denotes the set of m×n nonnegative real matrices. Δn≔δni∣i=1,2,…,n, where δni is the i-th column of the identity matrix In. An n×t matrix M is called a logical matrix, if M=[δni1δni2⋯δnit] and denote M briefly by M=δn[i1i2⋯it]. Define the set of n×t logical matrices as Ln×t. Coli(L)(Rowi(L)) is the i-th column (row) of matrix L. r=(r1,…,rk)T∈Rk is a probabilistic vector, if ri≥0, i=1,…,k, and ∑i=1kri=1. Υk denotes the set of k dimensional probabilistic vectors. If M∈Rm×n+ and Col(M)⊂Υm, M is called a probabilistic matrix. Υm×n denotes the set of m×n probabilistic matrices. ⋉ denotes the default matrix product throughout this paper. Please refer to [3] for the definition and properties of STP. Because ⋉ is a generalization of the ordinary matrix product. We omit “⋉” without confusion and call it “product”. M∗N denotes Khatri-Rao product of M and N.


## 2. Preliminaries

This section gives some necessary mathematic tools, which will be used in this paper.Lemma 1 (see [3]).
(1)
ConsiderX∈Rm and Y∈Rn as two column vectors. Then, W[m,n]XY=YX, where W[m,n] is the swap matrix. Especially W[n,n]≔W[n]. (2)
DefineX∈Rt and A∈Rm×n. Then, one gets XA=(It⊗A)X.Lemma 2 (see [31]).
ConsiderX∈Υp and Y∈Υq. Define dummy matrices, called “front-maintaining operator" and “rear-maintaining operator”, respectively, as (1)Dfp,q=δp11⋯1︸q22⋯2︸q⋯pp⋯p︸q,Drp,q=δq12⋯q︸12⋯q︸⋯12⋯q︸︸p. Then Dfp,qXY=X, Drp,qXY=Y.Lemma 3 (see [37]).
Considerf:Δkn→R (or f:Δkn→Δm) as a pseudological (or logical) function. Then, there exists a unique matrix Mf∈R1×kn (or Mf∈Lm×kn), called the structural matrix of f, such that (2)fx1,x2,…,xn=Mf⋉i=1nxi, where xi∈Δk,i=1,2,…,n, Colj(Mf)=f(δknj), and j=1,2,…,kn.In the rest of this section, we present some basic concepts in networked evolutionary games.Definition 4 (see [31]).
A normal game with two players is a fundamental network game (FNG), if the strategy set is{1,2,…,k} and player’s payoff function is c=c(x,y).


## 3. Main Results

This section firstly gives the description of MJNEGs. Then, the method to formulate the given MJNEGs is given. Finally, this section analyzes the stability of the MJNEG based on its corresponding algebraic expression.


### 3.1. Description of MJNEGs

At first, we give the description of an MJNEG as follows:(a)
A set of finite networksM≔{1,2,…,m}: the topological structure of each network is a connected undirected graph (Nz,Ez), where ∅≠Nz⊂{1,2,…,n} is the set of nodes in network z, Ez={(i,j)∣ there exists interaction between node i and node j in network z} is the set of edges, and z∈M.(b)
An FNG: if(i,j)∈Ez, then node i and node j play the FNG in network z with strategies xi(t) and xj(t) at time t, respectively.(c)
Players’ strategy updating rule: in networkz, the rule can be expressed as (3)xit=fi,zxi0,xi1,…,xit-1,xj0,xj1,…,xjt-1∣j∈Ni,z,wherexj(τ)∈S0 is the strategy of player j at time τ, τ=0,1,…,t-1, and Ni,z is the neighborhood of player i in the network z, that is, j∈Ni,z if and only if (i,j)∈Ez, i∈N, and z∈M. Obviously, i∉Ni,z and j∈Ni,z⇔i∈Nj,z.(d)
Network evolve process:{θ(t):t∈N} represents the discrete-time homogeneous Markov chain taking values in a finite set M with a transition probability matrix P=(pij)m×m as (4)pij=Pr⁡θt+1=j∣θt=i,wherepij≥0, for ∀i,j∈M, ∑j=1mpij=1 for any i∈M, and θ(t)=k represents that the MJNEG evolves on network k at time t.In networkz, at each time, node i only plays with its neighbors, and its aggregate payoff pi,z:S0Ni,z+1→R is the sum of payoffs gained by playing with all its neighbors, i.e., (5)pi,zxi,xj∣j∈Ni,z=∑j∈Ni,zcxi,xjin which c is the payoff function of the given FNG and xi,xj∈S0.In this paper, we adoptthe myopic best response adjustment rule [38], that is, every player forecasts that its neighbors will repeat their last-step strategy choice, and the strategy choice at present time is the best response against its neighbors’ strategies choice of the last one. Based on that, one has(6)xit∈Qi,z≔arg⁡maxxi∈S⁡pi,zxi,x-it-1,i∈Ni,z,z∈M.When player i may have more than one best strategies to choose, define a priority for the strategy choice as follows: x∈S0 has priority over y∈S0, if and only if x>y. Thus, player i updates its strategy according to the following expression:(7)xit=max⁡x∣x∈Qi,z,i∈Nz,z∈M.We let the initial statex¯0 for nodes j∉Nz, which are not activated at that moment in the network z; i.e., xj(t)=x¯0 holds.Remark 5.
We assign the initial statex¯0 for the new participators. It implies an obvious fact that every new participator has the same conditions when they enter the evolutionary game.In addition to the evolution of strategies for players, the Markov chain{θ(t)∣t∈N} decides the probability with which network the given MJNEG stays at a specific time t.The aim of this paper is to study the algebraic formulation and stability analysis of the given MJNEG as ak-valued switched logical system with a given switching signal as a Markov chain.


### 3.2. Algebraic Expression of the Given MJNEG

This subsection algebraically formulates the given MJNEG as Markov jumpk-valued logical system. To achieve it, we can take the following steps: (i) Find the proper structural matrices of the payoff function for every node in each networks. (ii) Find the proper structural matrix of the updating law for every node in each networks. (iii) Via the obtained structural matrices and the transition probability matrix of Markov chain {θ(t),t∈N}, we construct the algebraic formulation for the given MJNEGs.Step(i), using the vector form of logical variables, we identify S0~Δk, where S0=k, “~" denotes that the strategy j∈S0 is equivalent to δkj∈Δk,j=1,2,…,k. Then, when i∈Nz holds, by Lemmas 1, 2, and 3, and (5), the payoff function of player i in network z can be rewritten as(8)pi,zxit,xjt∣j∈Ni,z=Mc∑j∈Ni,zxitxjt=Mc∑j∈Ni,zWkxjtxit=McWk∑j<i,j∈Ni,zxjtxit+∑j>i,j∈Ni,zxjtxit=McWkDrkn-2,k2∑j<i,j∈Ni,zWkj,kn-j-1+∑j>i,j∈Ni,zWkj-1,kn-jx-itxit≔Mi,zx-itxit,where Mc∈R1×k2 is the structural matrix of the FNG’s payoff function and Mi,z∈R1×kn is the structural matrix of pi,z, xi(t)∈Δk is the strategy of player i at time t, x-i(t)≔x1(t)⋉x2(t)⋉⋯⋉xi-1(t)⋉xi+1(t)⋉⋯⋉xn(t)∈Δkn-1, and z∈M.In Step(ii), we consider the following two cases.Case I.
Ifi∈Nz, divide Mi,z into kn-1 equal blocks as (9)Mi,z=Blk1Mi,z,Blk2Mi,z,…,Blkkn-1Mi,z,where Blkl(Mi,z) is all possible benefits of player i with other players’ strategy x-i(t)=δkn-1l,l=1,2,…,kn-1.
Next, we find the best response of playeri to make its benefit maximum. For all l=1,2,…,kn-1, let the column index set Ξi,l,z, such that (10)Ξi,l,z=ξl∣ColξlBlklMi,z=max1⩽ξ⩽kColξBlklMi,z. If there are more than one maximum columns, i.e., Ξi,l,z>1, one can choose the unique column index ξi,l,z with the help of the priority of strategy choice given in (7).
By Lemma2, letting L~i,z=δk[ξi,1,z,…,ξi,kn-1,z], we can construct the algebraic form of the updating law for node i in network z as(11)xit+1=L~i,zx-it=L~i,zDrk,kn-1Wki-1,kxt≔Li,zxt.Case II.
Ifi∉Nz, by Lemma 2, we define (12)xjt+1=x¯0=Dfk,knx¯0x1tx2t⋯xnt≔Lj,zxt, where x(t)=x1(t)x2(t)⋯xn(t). Then, each new player entering the MJNEG would have the initial state x¯0.
Thus, by (11) and (12), one gets the MJNEGs evolving on fixed network z as follows: (13)xt+1=Lzxt, where x(t)=x1(t)x2(t)⋯xn(t) and Lz=L1,z∗L2,z∗⋯∗Ln,z.In Step(iii), by the aforementioned analysis, we formulate the given MJNEG as follows: (14)xk+1=Lθtxk,where {θ(t):t∈N} is the discrete-time Markov chain and x(k)=x1(k)x2(k)⋯xn(k).Based on the aforementioned analysis, the following algorithm is constructed to formulate the MJNEG.Algorithm 6.
This algorithm contains four steps:(1)
Calculate the structural matrix,Mi,z, of the payoff functions of the player in node i, when Ni,z≠∅, for each network z by (15)Mi,z=McWkDrkn-2,k2∑j<i,j∈Ni,zWkj,kn-j-1+∑j>i,j∈Ni,zWkj-1,kn-j.(2)
For each networkz, divide the matrices Mi,z into kn-1 equal blocks as (16)Mi,z=Blk1Mi,z,Blk2Mi,z,…,Blkkn-1Mi,z,and for alll=1,2,…,kn-1, find the column index ξi,l,z, such that ξi,l,z=max{j∣Colj(Blkl(Mi,z))=max1⩽ξ⩽kColξ(Blkl(Mi,z))};(3)
Formulate the MJNEG evolving on networkz under study as (17)xt+1=Lzxt,whereLz=L1,z∗L2,z∗⋯∗Ln,z, L~i,z=δk[ξi,1,z,ξi,2,z,…,ξi,kn-1,z], i∈Nz, Lj,z=Dfk,knx¯0, and j∉Nz.(4)
Finally, one has the algebraic formulation as follows:(18)xk+1=Lθtxk,wherex(k)=x1(k)x2(k)⋯xn(k).


### 3.3. Stability Analysis

This subsection investigates the stochastic global stability of the given MJNEG as(19)xt+1=Lθtxt,where x(t)=⋉i=1nxi(t) and {θ(t):t∈N} denotes the given Markov chain. In an evolutionary game, some strategy profile xe has specific meaning, Nash equilibrium, for example. This subsection analyzes the globally stability at xe in stochastic sense. In addition, because of transformation of coordinates, we assume that xe=δknkn∈Δkn holds.In the following, we give the definition for MJNEG of global stability in stochastic sense.Definition 7.
The given MJNEG with algebraic form (19) is said to be globally stable in stochastic sense at xe=δknkn∈Δkn, if, for ∀x(0) and ∀θ(t), limt→+∞E{x(t)∣x(0),θ(0)}=δknkn holds.Denotezj(t)=E{x(t)1{θ(t)=j}}, where 1{θ(t)=j} represents the Dirac measure ever the set {θ(t)=j} with j∈M. Since {θ(t)=j} is independent from {x(t)=δkni}, one has (20)Ext=∑i=1knδkniPxt=δkni=∑i=1knδkni∑j=1mPxt=δkni∣θt=jPθt=j=∑j=1m∑i=1knδkniPxt=δkniPθt=j=∑j=1mzjt.Then, we have(21)zjt+1=Ext+11θt+1=j=∑i=1mExt+11θt+1=j1θt=i=∑i=1mpijLizit.Rewritezj(t) as zj(t)=(wjT(t),μj(t))T, where wj(t)∈Rkn-1,1, μj(t)∈R and j∈M; one has (22)wjt+1=∑i=1mpi,jLi1,1wit+∑i=1mpi,jLi1,2μit,μjt+1=∑i=1mpi,jLi2,1wit+∑i=1mpi,jLi2,2μit,where j∈M and (23)Li1,1Li1,2Li2,1Li2,2=Li,Li1,1∈Υkn-1×kn-1,i∈M.Thus, via (22), the following result reveals some property for the given MJNEG.Theorem 8.
The given MJNEG with algebraic form (19) is globally stable at xe=δknkn in stochastic sense if and only if, ∀x(0) and ∀θ(t), (24)limt→+∞wit=0kn-1,∀i∈M.Proof.
Sufficient. If, ∀x(0) and ∀θ(t), (24) holds, then limt→+∞∑i=1mμi(t)=1 according to that 1=1knTE{x(t)}=1knT∑j=1mzj(t). It is easy to see that limt→+∞E{x(t)}=limt→+∞∑j=1mzj(t)=δknkn.
Necessity. If system (19) is globally stable in stochastic sense at xe=δknkn, then using Definition 7, for ∀x(0) and initial distribution of θ(t), limt→+∞E{x(t)}=δknkn, which yields that limt→+∞∑i=1mwi(t)=0kn-1. Note that wi(t)≥0, then one has, for every i∈M, limt→+∞wi(t)=0kn-1.With the help of the above theorem, we can get the main result in this paper. The following theorem gives an equivalent criterion for the stability of the given NEG.Theorem 9.
The given system with algebraic form (19) is globally stable in stochastic sense at xe=δknkn if and only if there exist vectors λi∈Rkn, i∈M such that the following conditions hold: (25)λiTδknkn=0,λiTδknt>0,∑j=1mpi,jλjTLiδknkn=0,∑j=1mpi,jλjTLi-λiTδknt<0, for i=1,2,…,m, and t=1,2,…,kn-1.Proof.
Sufficient. To prove the part of sufficient, we need first prove the fact that each network has a common fixed point as xe under conditions (25).
Assume thatxe is not a fixed point of network i0, then Li0xe≠xe, i.e., Colkn(Li0)=δkns, for some s≠kn. Subsequently, by the second equation in (25), one has that for every j∈M, λjTLi0δknkn=λjTδkns>0. Note that ∑j=1mpi0,j≥0, then there exists at least one integer j∗ such that pi0,j∗>0. Therefore, (26)∑j=1mpi0,jλjTLi0δknkn=∑j=1mλjTδkns≥pi0,j∗λjT∗δkns>0, which is contradictory to the third equation in (25). Thus, xe is a common fixed point of each network, which implies that Colkn(Li)=δknkn, for ∀i∈M. Therefore, Li1,2=0kn-1 and Li2,2=1 for ∀i∈M in (23). Then, the first equation of (22) can be rewritten as (27)wjt+1=∑i=1mpi,jLi1,1wit,j∈M.Let w(t)=(w1T(t),w2T(t),…,wmT(t))∈Rm(kn-1), then (28)wt+1=Qwk, where (29)Q=PT⊗I2n-1L1110⋯00L211⋯0⋮⋮⋱⋮00⋯Lm11∈Υm2n-1×m2n-1. It is worth noting that Q≥≥0. Thus, from Lemma 1 in [39] system, (28) is a positive system. Rewrite λi as λi=(λ^iT,0)T, where λ^i∈Rkn-1, i∈M, then by (25) and denoting λ^=(λ^1T,λ^2T,…,λ^sT)T∈Rkn-1, one has λ^>>0 and λ^T(Q-Is(kn-1))<<0. Therefore, system (28) is stable by Proposition 1 in [39]. By Theorem 8, network (19) is stochastically globally stable.
Necessity. Because system (19) is stochastically globally stable. From Theorem 8, we have (24). For Markov process {θ(k),k≥0} is ergodic, one get that there exists K∈N+ such that the probability of reaching every mode i∈M is positive after time K. Thus, for all networks, xe is a common fixed point. Otherwise, if xe is not a fixed point of network i0, then Li022=0 and Li22=1 for i≠i0. By (22) and (24), one has (30)limk→+∞∑j=1sμjk+1=limk→+∞∑j=1s∑i=1spijF22iμik=limk→+∞∑j=1s∑i=1,i≠i0spijF22iμik=limk→+∞∑i=1,i≠i0s∑j=1spijF22iμik=limk→+∞∑i=1,i≠i0sμik.
Withlimk→+∞μi(k)=1 in hands, one obtains that limk→+∞μ0(k)=0, which implies that limk→+∞zi0(k)=0kn holds. It is contrary to that the probability of every reaching mode i∈M is positive after time K. Therefore, for each i∈M, F22i=1 and F12i=0kn-1. So, w(k) satisfies (28). System (28) is a positive and stable system. Then, by Proposition 1 in [39], there exists a vector λ^=(λ^1T,λ^2T,…,λ^mT)T∈Rm(kn-1), where λ^i∈Rkn-1 and λ^i>>0, i∈M such that λ^T(Q-Im(kn-1))<<0. Define λi=(λ^iT,0)T, i∈M, then (25) holds. The proof is completed.Remark 10.
It worth noting that this manuscript consists of two important part:(1) The modeling and algebraic formulation of the given MJNEGs; (2) Based on the obtained algebraic expressions, we investigate the stability analysis for the given MJNEGs. Actually, this paper can be considered as a further research of [40]. Compared with the model adopted in [40], the description of MJNEGs is more general, i.e., the MJNEGs given in this paper can include the research target in [40] as a special case. In addition to that, the stability analysis for the MJNEGs in this paper is deeper than the stability analysis in [40]. We obtain better results in this paper.


## 3.1. Description of MJNEGs

At first, we give the description of an MJNEG as follows:(a)
A set of finite networksM≔{1,2,…,m}: the topological structure of each network is a connected undirected graph (Nz,Ez), where ∅≠Nz⊂{1,2,…,n} is the set of nodes in network z, Ez={(i,j)∣ there exists interaction between node i and node j in network z} is the set of edges, and z∈M.(b)
An FNG: if(i,j)∈Ez, then node i and node j play the FNG in network z with strategies xi(t) and xj(t) at time t, respectively.(c)
Players’ strategy updating rule: in networkz, the rule can be expressed as (3)xit=fi,zxi0,xi1,…,xit-1,xj0,xj1,…,xjt-1∣j∈Ni,z,wherexj(τ)∈S0 is the strategy of player j at time τ, τ=0,1,…,t-1, and Ni,z is the neighborhood of player i in the network z, that is, j∈Ni,z if and only if (i,j)∈Ez, i∈N, and z∈M. Obviously, i∉Ni,z and j∈Ni,z⇔i∈Nj,z.(d)
Network evolve process:{θ(t):t∈N} represents the discrete-time homogeneous Markov chain taking values in a finite set M with a transition probability matrix P=(pij)m×m as (4)pij=Pr⁡θt+1=j∣θt=i,wherepij≥0, for ∀i,j∈M, ∑j=1mpij=1 for any i∈M, and θ(t)=k represents that the MJNEG evolves on network k at time t.In networkz, at each time, node i only plays with its neighbors, and its aggregate payoff pi,z:S0Ni,z+1→R is the sum of payoffs gained by playing with all its neighbors, i.e., (5)pi,zxi,xj∣j∈Ni,z=∑j∈Ni,zcxi,xjin which c is the payoff function of the given FNG and xi,xj∈S0.In this paper, we adoptthe myopic best response adjustment rule [38], that is, every player forecasts that its neighbors will repeat their last-step strategy choice, and the strategy choice at present time is the best response against its neighbors’ strategies choice of the last one. Based on that, one has(6)xit∈Qi,z≔arg⁡maxxi∈S⁡pi,zxi,x-it-1,i∈Ni,z,z∈M.When player i may have more than one best strategies to choose, define a priority for the strategy choice as follows: x∈S0 has priority over y∈S0, if and only if x>y. Thus, player i updates its strategy according to the following expression:(7)xit=max⁡x∣x∈Qi,z,i∈Nz,z∈M.We let the initial statex¯0 for nodes j∉Nz, which are not activated at that moment in the network z; i.e., xj(t)=x¯0 holds.Remark 5.
We assign the initial statex¯0 for the new participators. It implies an obvious fact that every new participator has the same conditions when they enter the evolutionary game.In addition to the evolution of strategies for players, the Markov chain{θ(t)∣t∈N} decides the probability with which network the given MJNEG stays at a specific time t.The aim of this paper is to study the algebraic formulation and stability analysis of the given MJNEG as ak-valued switched logical system with a given switching signal as a Markov chain.


## 3.2. Algebraic Expression of the Given MJNEG

This subsection algebraically formulates the given MJNEG as Markov jumpk-valued logical system. To achieve it, we can take the following steps: (i) Find the proper structural matrices of the payoff function for every node in each networks. (ii) Find the proper structural matrix of the updating law for every node in each networks. (iii) Via the obtained structural matrices and the transition probability matrix of Markov chain {θ(t),t∈N}, we construct the algebraic formulation for the given MJNEGs.Step(i), using the vector form of logical variables, we identify S0~Δk, where S0=k, “~" denotes that the strategy j∈S0 is equivalent to δkj∈Δk,j=1,2,…,k. Then, when i∈Nz holds, by Lemmas 1, 2, and 3, and (5), the payoff function of player i in network z can be rewritten as(8)pi,zxit,xjt∣j∈Ni,z=Mc∑j∈Ni,zxitxjt=Mc∑j∈Ni,zWkxjtxit=McWk∑j<i,j∈Ni,zxjtxit+∑j>i,j∈Ni,zxjtxit=McWkDrkn-2,k2∑j<i,j∈Ni,zWkj,kn-j-1+∑j>i,j∈Ni,zWkj-1,kn-jx-itxit≔Mi,zx-itxit,where Mc∈R1×k2 is the structural matrix of the FNG’s payoff function and Mi,z∈R1×kn is the structural matrix of pi,z, xi(t)∈Δk is the strategy of player i at time t, x-i(t)≔x1(t)⋉x2(t)⋉⋯⋉xi-1(t)⋉xi+1(t)⋉⋯⋉xn(t)∈Δkn-1, and z∈M.In Step(ii), we consider the following two cases.Case I.
Ifi∈Nz, divide Mi,z into kn-1 equal blocks as (9)Mi,z=Blk1Mi,z,Blk2Mi,z,…,Blkkn-1Mi,z,where Blkl(Mi,z) is all possible benefits of player i with other players’ strategy x-i(t)=δkn-1l,l=1,2,…,kn-1.
Next, we find the best response of playeri to make its benefit maximum. For all l=1,2,…,kn-1, let the column index set Ξi,l,z, such that (10)Ξi,l,z=ξl∣ColξlBlklMi,z=max1⩽ξ⩽kColξBlklMi,z. If there are more than one maximum columns, i.e., Ξi,l,z>1, one can choose the unique column index ξi,l,z with the help of the priority of strategy choice given in (7).
By Lemma2, letting L~i,z=δk[ξi,1,z,…,ξi,kn-1,z], we can construct the algebraic form of the updating law for node i in network z as(11)xit+1=L~i,zx-it=L~i,zDrk,kn-1Wki-1,kxt≔Li,zxt.Case II.
Ifi∉Nz, by Lemma 2, we define (12)xjt+1=x¯0=Dfk,knx¯0x1tx2t⋯xnt≔Lj,zxt, where x(t)=x1(t)x2(t)⋯xn(t). Then, each new player entering the MJNEG would have the initial state x¯0.
Thus, by (11) and (12), one gets the MJNEGs evolving on fixed network z as follows: (13)xt+1=Lzxt, where x(t)=x1(t)x2(t)⋯xn(t) and Lz=L1,z∗L2,z∗⋯∗Ln,z.In Step(iii), by the aforementioned analysis, we formulate the given MJNEG as follows: (14)xk+1=Lθtxk,where {θ(t):t∈N} is the discrete-time Markov chain and x(k)=x1(k)x2(k)⋯xn(k).Based on the aforementioned analysis, the following algorithm is constructed to formulate the MJNEG.Algorithm 6.
This algorithm contains four steps:(1)
Calculate the structural matrix,Mi,z, of the payoff functions of the player in node i, when Ni,z≠∅, for each network z by (15)Mi,z=McWkDrkn-2,k2∑j<i,j∈Ni,zWkj,kn-j-1+∑j>i,j∈Ni,zWkj-1,kn-j.(2)
For each networkz, divide the matrices Mi,z into kn-1 equal blocks as (16)Mi,z=Blk1Mi,z,Blk2Mi,z,…,Blkkn-1Mi,z,and for alll=1,2,…,kn-1, find the column index ξi,l,z, such that ξi,l,z=max{j∣Colj(Blkl(Mi,z))=max1⩽ξ⩽kColξ(Blkl(Mi,z))};(3)
Formulate the MJNEG evolving on networkz under study as (17)xt+1=Lzxt,whereLz=L1,z∗L2,z∗⋯∗Ln,z, L~i,z=δk[ξi,1,z,ξi,2,z,…,ξi,kn-1,z], i∈Nz, Lj,z=Dfk,knx¯0, and j∉Nz.(4)
Finally, one has the algebraic formulation as follows:(18)xk+1=Lθtxk,wherex(k)=x1(k)x2(k)⋯xn(k).


## 3.3. Stability Analysis

This subsection investigates the stochastic global stability of the given MJNEG as(19)xt+1=Lθtxt,where x(t)=⋉i=1nxi(t) and {θ(t):t∈N} denotes the given Markov chain. In an evolutionary game, some strategy profile xe has specific meaning, Nash equilibrium, for example. This subsection analyzes the globally stability at xe in stochastic sense. In addition, because of transformation of coordinates, we assume that xe=δknkn∈Δkn holds.In the following, we give the definition for MJNEG of global stability in stochastic sense.Definition 7.
The given MJNEG with algebraic form (19) is said to be globally stable in stochastic sense at xe=δknkn∈Δkn, if, for ∀x(0) and ∀θ(t), limt→+∞E{x(t)∣x(0),θ(0)}=δknkn holds.Denotezj(t)=E{x(t)1{θ(t)=j}}, where 1{θ(t)=j} represents the Dirac measure ever the set {θ(t)=j} with j∈M. Since {θ(t)=j} is independent from {x(t)=δkni}, one has (20)Ext=∑i=1knδkniPxt=δkni=∑i=1knδkni∑j=1mPxt=δkni∣θt=jPθt=j=∑j=1m∑i=1knδkniPxt=δkniPθt=j=∑j=1mzjt.Then, we have(21)zjt+1=Ext+11θt+1=j=∑i=1mExt+11θt+1=j1θt=i=∑i=1mpijLizit.Rewritezj(t) as zj(t)=(wjT(t),μj(t))T, where wj(t)∈Rkn-1,1, μj(t)∈R and j∈M; one has (22)wjt+1=∑i=1mpi,jLi1,1wit+∑i=1mpi,jLi1,2μit,μjt+1=∑i=1mpi,jLi2,1wit+∑i=1mpi,jLi2,2μit,where j∈M and (23)Li1,1Li1,2Li2,1Li2,2=Li,Li1,1∈Υkn-1×kn-1,i∈M.Thus, via (22), the following result reveals some property for the given MJNEG.Theorem 8.
The given MJNEG with algebraic form (19) is globally stable at xe=δknkn in stochastic sense if and only if, ∀x(0) and ∀θ(t), (24)limt→+∞wit=0kn-1,∀i∈M.Proof.
Sufficient. If, ∀x(0) and ∀θ(t), (24) holds, then limt→+∞∑i=1mμi(t)=1 according to that 1=1knTE{x(t)}=1knT∑j=1mzj(t). It is easy to see that limt→+∞E{x(t)}=limt→+∞∑j=1mzj(t)=δknkn.
Necessity. If system (19) is globally stable in stochastic sense at xe=δknkn, then using Definition 7, for ∀x(0) and initial distribution of θ(t), limt→+∞E{x(t)}=δknkn, which yields that limt→+∞∑i=1mwi(t)=0kn-1. Note that wi(t)≥0, then one has, for every i∈M, limt→+∞wi(t)=0kn-1.With the help of the above theorem, we can get the main result in this paper. The following theorem gives an equivalent criterion for the stability of the given NEG.Theorem 9.
The given system with algebraic form (19) is globally stable in stochastic sense at xe=δknkn if and only if there exist vectors λi∈Rkn, i∈M such that the following conditions hold: (25)λiTδknkn=0,λiTδknt>0,∑j=1mpi,jλjTLiδknkn=0,∑j=1mpi,jλjTLi-λiTδknt<0, for i=1,2,…,m, and t=1,2,…,kn-1.Proof.
Sufficient. To prove the part of sufficient, we need first prove the fact that each network has a common fixed point as xe under conditions (25).
Assume thatxe is not a fixed point of network i0, then Li0xe≠xe, i.e., Colkn(Li0)=δkns, for some s≠kn. Subsequently, by the second equation in (25), one has that for every j∈M, λjTLi0δknkn=λjTδkns>0. Note that ∑j=1mpi0,j≥0, then there exists at least one integer j∗ such that pi0,j∗>0. Therefore, (26)∑j=1mpi0,jλjTLi0δknkn=∑j=1mλjTδkns≥pi0,j∗λjT∗δkns>0, which is contradictory to the third equation in (25). Thus, xe is a common fixed point of each network, which implies that Colkn(Li)=δknkn, for ∀i∈M. Therefore, Li1,2=0kn-1 and Li2,2=1 for ∀i∈M in (23). Then, the first equation of (22) can be rewritten as (27)wjt+1=∑i=1mpi,jLi1,1wit,j∈M.Let w(t)=(w1T(t),w2T(t),…,wmT(t))∈Rm(kn-1), then (28)wt+1=Qwk, where (29)Q=PT⊗I2n-1L1110⋯00L211⋯0⋮⋮⋱⋮00⋯Lm11∈Υm2n-1×m2n-1. It is worth noting that Q≥≥0. Thus, from Lemma 1 in [39] system, (28) is a positive system. Rewrite λi as λi=(λ^iT,0)T, where λ^i∈Rkn-1, i∈M, then by (25) and denoting λ^=(λ^1T,λ^2T,…,λ^sT)T∈Rkn-1, one has λ^>>0 and λ^T(Q-Is(kn-1))<<0. Therefore, system (28) is stable by Proposition 1 in [39]. By Theorem 8, network (19) is stochastically globally stable.
Necessity. Because system (19) is stochastically globally stable. From Theorem 8, we have (24). For Markov process {θ(k),k≥0} is ergodic, one get that there exists K∈N+ such that the probability of reaching every mode i∈M is positive after time K. Thus, for all networks, xe is a common fixed point. Otherwise, if xe is not a fixed point of network i0, then Li022=0 and Li22=1 for i≠i0. By (22) and (24), one has (30)limk→+∞∑j=1sμjk+1=limk→+∞∑j=1s∑i=1spijF22iμik=limk→+∞∑j=1s∑i=1,i≠i0spijF22iμik=limk→+∞∑i=1,i≠i0s∑j=1spijF22iμik=limk→+∞∑i=1,i≠i0sμik.
Withlimk→+∞μi(k)=1 in hands, one obtains that limk→+∞μ0(k)=0, which implies that limk→+∞zi0(k)=0kn holds. It is contrary to that the probability of every reaching mode i∈M is positive after time K. Therefore, for each i∈M, F22i=1 and F12i=0kn-1. So, w(k) satisfies (28). System (28) is a positive and stable system. Then, by Proposition 1 in [39], there exists a vector λ^=(λ^1T,λ^2T,…,λ^mT)T∈Rm(kn-1), where λ^i∈Rkn-1 and λ^i>>0, i∈M such that λ^T(Q-Im(kn-1))<<0. Define λi=(λ^iT,0)T, i∈M, then (25) holds. The proof is completed.Remark 10.
It worth noting that this manuscript consists of two important part:(1) The modeling and algebraic formulation of the given MJNEGs; (2) Based on the obtained algebraic expressions, we investigate the stability analysis for the given MJNEGs. Actually, this paper can be considered as a further research of [40]. Compared with the model adopted in [40], the description of MJNEGs is more general, i.e., the MJNEGs given in this paper can include the research target in [40] as a special case. In addition to that, the stability analysis for the MJNEGs in this paper is deeper than the stability analysis in [40]. We obtain better results in this paper.


## 4. An Illustrative Example

In this section, we use a classical example University-students game [36] to show the effective of our results.Example 1.
In an evolutionary gameG with random entrance, minor players have time horizon 2. nm=2 denotes the maximum possible number of active players in Ξ. At the time t, the number of the minor players is modelled by the vector (31)yt=n0t,n1t, where nl(t)=Ilt, Il(t) is the set of players with entrance time t-l, l=0,1. Furthermore, major player plays game with minor players and minor players do not player game with each other. Thus, the random entrance is denoted by a Markov chain with states: (0,1), (1,0), and (1,1).Define an MJNEG as follows:(i)
Network topological structures, denote by(Nz,Ez), where N1={1,3}, N2={2,3}, N3={1,2,3}, E1={(1,3)}, E2={(2,3)}, E3={(1,3),(2,3)} node 3 represents the major player, and z∈M={1,2,3}. See in Figure 1.(ii)
The FNG’s payoff is shown in Table1.(iii)
The updating rule is MBRA.(iv)
Network evolve process:{θ(t):t∈N} with a transition probability matrix (32)P=0010.400.6001.Table 1
Payoff bimatrix.
Player1\Player2 M F M (2, 2) (1, 0) F (0, 1) (3, 3)Figure 1
The networks.Firstly, we rewrite the MJNEG into an algebraic expression. DenoteM~δ21, F~δ22, (0,1)~δ31, network j~δ3j, and j=1,2,3. Using the vector form of logical variables, we have pi,z=Mi,zx-i(t)xi(t), x(t)=(x1(t),x2(t),x3(t)), xi(t)∈Δ2, and z∈M.With (11), one obtains (33)M3,1=20201313,M3,2=20132013,M3,3=40333326,Mc=2013,i∈1,2,z∈M.Then, by (11) and (12), we have (34)L3,1=δ211112222,L3,2=δ211221122,L3,3=δ211222222,Li,z=δ212121212,Lj,z=δ222222222.where i∈Nz⋂{1,2}, j∉Nz⋂{1,2}, and z∈M.Thus, by (13), one has (35)L1=δ837374848,L2=δ857685768,L3=δ817282828.Solving (25), we have (36)λ1=156.583393.8453130.605187.0810103.063651.211969.13980T,λ2=154.260596.0248107.350156.5912154.3603118.992879.40380T,λ3=186.603989.6133120.765145.4087121.505451.211993.57920TTherefore, it follows from Theorem9 that the given game is globally stable at xe=δ88 in stochastic sense. Figure 2 demonstrates the effective of the calculation of λ1, λ2, and λ3.Figure 2
The trajectory of the given game.


## 5. Conclusion

This paper has investigated the algebraic formulation and stability analysis for a class of MJNEG. A proper algorithm has been constructed to convert the given MJNEG into an algebraic expression. Based on the above results, the stability of the given game has been analyzed and an equivalent criterion is given. Finally, an interesting example has proved the effectiveness of our results.In the future work, we could consider the given MJNEG with time delay. Actually, time delay is a very common situation. Many great works in the community of control and engineering have reached towards this kind of systems. See [41–60] for details.



---

*Source: 5124343-2018-11-19.xml*