Daizhan CHENG,Hongsheng QI,Fehuang HE,Tingting XU,Hairong DONG

1.Institute of Systems Science,Chinese Academy of Sciences,Beijing 100190,China;

2.Institute of Astronautics,Harbin Institute of Technology,Harbin Heilongjiang 150080,China;

3.State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University,Beijing 100044,China

Semi-tensor product approach to networked evolutionary games

Daizhan CHENG1?,Hongsheng QI1,Fehuang HE2,Tingting XU1,Hairong DONG3

1.Institute of Systems Science,Chinese Academy of Sciences,Beijing 100190,China;

2.Institute of Astronautics,Harbin Institute of Technology,Harbin Heilongjiang 150080,China;

3.State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University,Beijing 100044,China

In this paper a comprehensive introduction for modeling and control of networked evolutionary games(NEGs)via semi-tensor product(STP)approach is presented.First,we review the mathematical model of an NEG,which consists of three ingredients:network graph,fundamental network game,and strategy updating rule.Three kinds of network graphs are considered,which are i)undirected graph for symmetric games;ii)directed graph for asymmetric games,and iii)d-directed graph for symmetric games with partial neighborhood information.Three kinds of fundamental evolutionary games(FEGs)are discussed,which are i)two strategies and symmetric(S-2);ii)two strategies and asymmetric(A-2);and iii)three strategies and symmetric(S-3).Three strategy updating rules(SUR)are introduced,which are i)Unconditional Imitation(UI);ii)Fermi Rule(FR);iii)Myopic Best Response Adjustment Rule(MBRA).First,we review the fundamental evolutionary equation(FEE)and use it to construct network profile dynamics(NPD)of NEGs.

To show how the dynamics of an NEG can be modeled as a discrete time dynamics within an algebraic state space,the fundamental evolutionary equation(FEE)of each player is discussed.Using FEEs,the network strategy profile dynamics(NSPD)is built by providing efficient algorithms.Finally,we consider three more complicated NEGs:i)NEG with different length historical information,ii)NEG with multi-species,and iii)NEG with time-varying payoffs.In all the cases,formulas are provided to construct the corresponding NSPDs.Using these NSPDs,certain properties are explored.Examples are presented to demonstrate the model constructing method,analysis and control design technique,and to reveal certain dynamic behaviors of NEGs.

Networked evolutionary game;Fundamental evolutionary equation;Strategy profile dynamics;Homogeneous/heterogeneous NEG;Semi-tensor product of matrices

1 Introduction

Game theory as a branch of mathematics is initiated by the work of von Neumann[1],and followed by a book[2]based on this work.Since that it has been developed rapidly and become a formal,mathematical discipline.Roughly speaking,J.Nash has made a significant contribution to non-cooperative game by proposing the Nash equilibrium[3].As for cooperative game,L.S.Shapley,the co-winner of Nobel Prize in Economics 2012,has made some important contributions such as Shapley value,potential game,etc.[4,5].

Game theory and control theory share some common ideas,such as optimization,stability and stabilization.A game may be considered as an 'advanced control system' where the control objects are intelligent.In fact,differential game has been the topic for both disciplines for many years.Hence,the game-based control or the control oriented game could be a challenging new direction for control scientists.

In the last decades,the investigation of evolutionary games(EG)attracts a great attention from scientists in cross disciplines,because evolutionary game has wide background from biological systems[6,7],economical systems[8],social systems[9],physical systems[10],etc.

In original study of EG the topological relationship among players in the EG is mostly ignored.That is,assume each player gambles with all others,or randomly choose some partners.However,in many practical cases the situation is not like this.Therefore,in recent years the networked EG(NEG)becomes a hot topic.Roughly speaking,an NEG adds a graph with players as its nodes and sides describing the neighborhoods of each players.Then,each player only gambles with its neighbors[10-12].Since there are no many proper tools to deal with NEG,most of the researches are based on either simulations or statistics.Readers interested in this topic are referred to some survey articles[13-15],just to name few.

Recently,the semi-tensor product(STP)of matrices has been proposed for investigating(Boolean andk-valued logical)networks and network-based games[16,17].The readers are also referred to a survey paper[18]and the references therein for more details.Some other interesting developments include i)topological structure of networks[19-21];ii)controllability and control design of various kinds of control networks[22-26];iii)optimal control and game related optimization[22,27];iv)network stability and stabilization[28];v)decoupling[29,30];vi)technique for reducing complexity[31];and vii)various applications to control and signal processing etc.[25,32-35].

The key point in the above works is:using STP and the vector form expression of logical variables,an algebraic state space model is proposed to describe a logical process.Under this framework,the state space approach in control theory can be used to analysing and designing the logical dynamic process.

The STP has also been used to the modeling,analysis and control design of the NEGs[36].Some other related topics have also discussed,such as the evolutionarily stable strategy[37],the calculation of potential games[38].The key point remains the same:We found that the strategy profile dynamics of finite NEGs can also be expressed into a mix-valued logical dynamic system.Then,the algebraic state space model for Boolean networks can also be used for finite NEGs.Then,this model provides a very convenient and efficient framework for investigating EG.

The purpose of this paper is to introduce this framework and then to provide a comprehensive discussion for this STP approach to the modeling,analysis and control of various NEGs.An NEG discussed in this paper consists of three factors:i)network Graph,which is used to describe the topological structure of players;ii)fundamental Network Game,which is the game played by players lying on the same edges;iii)strategy Updating Rule,which is the rule used by each players to determine their next strategy.Further information about these 3 factors is as follows:

?Network graph:three different graphs are mainly discussed:i)undirected graph,which is used for the NEGs with symmetric fundamental network games(FNG);ii)directed graph,which is used for the NEGs with asymmetric FNGs;and iii)d-directed graph,which is used for symmetric games with partial neighborhood information.Finally,the uniform hypergraph case is briefly discussed.

?Fundamental network game:three kinds of FNGs are mainly discussed:i)each player has two strategies and the game is symmetric(S-2);ii)each player has two strategies and the game is asymmetric(A-2);and iii)each player has three strategies and the game is symmetric(S-3).It is clear that anyS-korA-kcan be used as the FNG.

?Strategy updating rule:three strategy updating rules(SUR)are mainly introduced:i)unconditional imitation(UI);ii)Fermi rule(FR);and iii)myopic best response adjustment rule(MBRA).Certain more general SURs are also briefly discussed.

Next,we introduce the fundamental evolutionary equation(FEE)for each player,which describes the strategy dynamics of each player.It was firstly introduced in[36],and we give more details.In addition,an algorithm for calculating the network profile dynamic equation of the overall network using each player's FEEs is presented.

The technique is then applied to three more complicated cases:i)NEGs with different length historical information,which allow some players to use longer neighborhood historical information and leads to higher orderk-valued logical dynamic networks;ii)NEGs with multispecies,which can be used to describe the evolution of co-existing spices;and iii)NEGs with time-varying payoffs,which are particularly suitable for financial problems,where the prices,profits,etc.are time-varying.

Finally,the control problems of NEGs are explored.It is shown that the control of NEGs can also be formulated as controlled mix-valued logical dynamics.Therefore,the known control results about mix-valued logical networks are applicable to the control NEGs.Some standard control problems such as controllability etc.are investigated.

For statement ease,some notations and basic concepts are introduced first.

?Notations:

i)MmXn:the set ofmXnreal matrices.

ii)Col(M)(Row(M))is the set of columns(rows)ofM.Coli(M)(Rowi(M))is theith column(row)ofM.

ii)Dk:={1,2,...,k},k≥2.iii)theith column of the identity matrixIn.

vi)A matrixL∈MmXnis called a logical matrix if the columns ofL,denoted by Col(L),are of the form of δkm.That is,

Denote by LmXnthe set ofmXnlogical matrices.

vii)IfL∈LnXr,by definition it can be expressed asFor the sake of compactness,it is briefly denoted as

viii)A matrixL∈MmXnis called a probabilistic matrix if the columns ofLaremth dimensional probabilistic vectors.That is,

The set ofmXnprobabilistic matrices is denoted by ΥmXn.

ix)IfL∈ΥmXn,ifwhereC1?ΔmandC2? ΥmΔm,and|C2|? |C1|.Then,for notational compactness,we still use the shorthand

?Operators:

i)Semi-tensor product of matrices[16,17]:

Definition 1LetM∈MmXnandN∈MpXq,andt=lcm{n,p}be the least common multiple ofnandp.The semi-tensor product ofMandN,denoted byM■N,is defined as

where?is the Kronecker product.

ii)Khatri-Rao product of matrices[39]:

Definition 2LetM∈MpXm,N∈MqXm.Then,the Khatri-Rao product is defined as

Proposition 1LetX∈Rmbe a column andMis a matrix.Then,

iii)Swap matrix[16,17]:

Definition 3A matrixW[m,n]∈MmXn,defined by

is called the(m,n)th dimensional swap matrix.

The basic function of the swap matrix is to 'swap' two vectors.That is,

Proposition 2LetX∈RmandY∈Rnbe two columns.Then,

The outline of this paper is as follows:Section 2 presents a mathematical framework for NEGs.Three basic components of an NEG,namely,network graph,FNG,and SUR,are discussed in detail.Section 3 is devoted to the FEE,which plays a key role in the investigation of NEGs.In Section 4,we consider how to construct the network profile dynamics using the FEEs of each players.Both deterministic and probabilistic cases are investigated.The modeling of controlled NEGs is discussed in Section 5.Section 6 considers three kinds of more complicated NEGs:i)NEG with different length historical information,ii)NEG with multi-species,and iii)NEG with time-varying payoffs.Section 7 is a brief conclusion.

2 Mathematical framework for NEG

This section is a comprehensive description of mathematical framework of NEGs.The main idea of which was firstly proposed in[36].

Definition 4A networked evolutionary game,denoted by((N,E),G,Π),consists of three ingredients as

i)a network(graph)(N,E);

ii)a fundamental network game(FNG),G,such that if(i,j)∈E,theniandjplay the FNG with strategiesxi(t)andxj(t),respectively.

iii)a local information based strategy updating rule(SUR).

Next,we describe these three ingredients one by one.

2.1 Network graph

We consider three kinds of network graphs.

i)Undirected graph:N={1 2...n}(n≤∞).It representsnplayers.If(i,j)∈E,theniis in the neighborhood ofj,denoted byi∈U(j).Simultaneously,j∈U(i).

ii)Directed graph:Note that the FNG is always played by two neighboring players.If the FNG is not symmetric,the directed edge is used to distinguish different roles of two players.Assume(i,j)∈E,i.e.,there is an edge fromitoj,then in the gameiis player 1 andjis player 2.Note that such directed graph does not affect the definition of neighborhoods.

Definition 5Consider an NEG with graph(N,E).

i)If(i,j)∈E,then bothi∈U(j)andj∈U(i)(no matter whether the graph is directed or not).

ii)If there exist α1,...,αλ,such thati∈U(α1),α1∈U(α2),...,αs∈U(j),where λ

Note that i)ifi∈Us(j),thenj∈Us(i);ii)ifi∈Us(j),theni∈Uh(j),h>s;iii)it is assumed thati∈U(i).

Definition 6A graph is said to be homogeneous if the graph is undirected and each node has same degree,or the graph is directed and each node has same in-degree and same out-degree.If a graph is not homogeneous it is said to be heterogeneous.

The following example shows different kinds of network graphs.

Example 1Assume there are 5 players.They form three kinds of graphs as shown in Fig 1.

Fig.1 Network graphs.

i)A cycle of undirected network graph shown in Fig.1(a).

Consider the neighborhoods of 1:

ii)A directed network graph shown in Fig.1(b).Consider the neighborhoods of 1:

2.2 Fundamental network game

Definition 7A fundamental network game(FNG)is a game with two players,i.e.,N=(i,j),and each player has the same set of strategies as

It is symmetric if the payoff functions satisfy:

Otherwise it is asymmetric.

In asymmetric case,only the directed graph can be used as the network graph.

The overall payoff of playeriat timetcould be

?Total payoff[38]:

?Average payoff:the average of its payoffs with all neighbors.Precisely,

Average payoff is assumed throughout this paper.

An FNG is determined by two key factors:i)k:the number of possible strategies;ii)type:symmetric or asymmetric.Therefore,we classify the FNGs as

?S-k:a symmetric game withkpossible strategies;

?A-k:an asymmetric game withkpossible strategies.

In the following example,we collect some commonly used FNGs.More details about the practical meanings can be found in[40-42].

Example 2We consider three simplest kinds of FNGs as follows:

?S-2:The payoff bi-matrix of this kind of games is in Table 1.

Table 1 S-2 games.

It covers many well known games.For instance,

i)if 2R>T+S>2P,it is the game of prisoner's dilemma;

ii)ifR=b-c,S=b-c,T=b,P=0,and 2b>c>b>0,it is the snowdrift game;

?A-2:The payoff bi-matrix of this kind of games is in Table 2.

Table 2 A-2 games.

It also covers many well known games.For instance,

i)ifA=H=a,B=G=b,C=D=E=F=0,anda>b>0,it is the battle of the sexes;

ii)ifE>A>C=D>B>0>F,andG=H=0,it is the game of boxed pigs;

iii)ifA=b,B=-b,C=b,D=-b E=c,F=-c,G=a,H=-a,anda>b>c>0,it is the game of battle of the Bismark see,

iv)ifA=D=F=G-a,B=C=E=H=a,anda≠0,it is the game of matching the pennies.

?S-3:The payoff bi-matrix of this kind of games is in Table 3.

Table 3 S-3 games.

Some examples are

i)ifA=F=I=0,B=E=G=a,C=D=H=-a,anda≠0,it is the game of rock-scissor-paper;

ii)ifE=a,A=b,F=c,I=0,B=G=H=D=d,C=e,anda>b>c>0>d>c,it is the Benoit-Krishna game.

2.3 Strategy updating rule

Denote byxi(t)the strategy of playeriat timet.Then,SUR is a rule which uses the local information to decide its next strategy.Precisely,

There are some commonly used SURs.

?Unconditional imitation(UI)[10]:the strategy of playeriat timet+1,i.e.,xi(t+1),is selected as the best strategy from strategies of neighborhood playersj∈U(i)at timet.Precisely,if

then

When the players with best payoff are not unique,say

we may use the following 2 options:

i)First unconditional imitation(UI-1):choose one corresponding to a priority.For instance(as a default),

This method leads to a deterministick-valued logical dynamics.

ii)Second unconditional imitation(UI-2):choose any one with equal probability.That is,

This method leads to a probabilistick-valued logical dynamics.

?Fermi rule(FM)[11,43].That is,randomly choose a neighborhoodj∈U(i).Comparingcj(t)withci(t)to determinexi(t+1)as

whereptis decided by the Fermi function

The parameter ζ>0 can be chosen arbitrary.For simplicity,throughout this paper we set ζ = ∞.Then,

This method leads to a probabilistick-valued logical dynamics.

?Myopic best response adjustment rule(MBRA)[44]:assume

then we choose

When the strategies with best payoff are not unique,say the set of best strategies is

we may use the following 2 options:

i)First MBRA(MBRA-1):Choose one corresponding to a priority.For instance(as a default),

This method leads to a deterministick-valued logical dynamics.

ii)Second MBRA(MBRA-2):Choose one with equal probability for best strategies.That is,

This method leads to a probabilistick-valued logical dynamics.

3 Fundamental evolutionary equation

Observing equation(7),sincecj(t)depends onU(j)andcan be rewritten as

We call(19)the fundamental evolutionary equation(FEE).One sees easily that the overall network evolutionary dynamics,called the network profile dynamics(NPD),is completely determined by the FEEs.It is also obvious that the FEEs are determined by network graph,FNG,and SUR.Next,we use some examples to depict the procedure for constructing FEEs.

Example 3Consider an NEG.Assume the network graph is Fig.1(a);FNG isS-2 withR=S=-1,T=2,P=0(the game of snowdrift).SUR is UI-1.Then,the FEE can be determined via Table 4.

Table 4 Payoffs→dynamics(Example 3).

where

Note that we use 'mod(5)' notation.That is,x0=x5,x-1=x4and so on.

Example 4Assume network graph is Fig.1(b);FNG isA-2 withA=H=2,B=G=1,E=F=C=D=0(the game of battle of the sexes).SUR is FM.Since the game is not symmetric,the FEEs for individual nodes are different.We need to work out them one by one.

i)If the profile is known,then the payments for each players are known.For instance,if the profile then it is easy to calculate that

ii)Comparingc1withc2,we havef1=x1=1.As forf2we have three choices:

Similarly,we can calculatefias in Table 5.

Table 5 Payoffs→dynamics(Example 4)

Finally,we have

4 From FEE to NPD

The NPD is used to describe the evolution of the overall networked games.This section consider how to construct the NPD of an NEG using its nodes' FEEs.We consider two cases:i)the FEEs are deterministic model;ii)the FEEs are probabilistic model.

4.1 Deterministic model

Assume

where

(Please refer to Definition 2 for the Khatri-Rao product'?').

Example 5Recall Example 3.Using(21),we have

Finally,we have the NPD as

where

4.2 Probabilistic model

Assume the strategies have the probabilistick-valued logical form as

Then,we have

whereM∈ΥknXkncan be calculated as

We use an example to depict it.

Example 6Recall Example 4.In fact,we can use Table 5 to calculateMcolumn by column.For instance,it is obvious that

As for Col4(M),with probability 1/4 it could beor.That is,

We simply express it as

Using this notation and a similar computation,we have

where

5 Modeling controlled NEGs

Definition 8Let((N,E),G,Π)be an NEG,andN=U∪Zbe a partition ofN.We call((U∪Z),E),G,Π)a controlled NEG,if the strategies ofu∈Ucan be chosen arbitrarily.As a result,z∈Zis called a state andu∈Uis called a control.

Using FEE,the strategy evolutionary equations can be expressed as[36]

We consider the deterministic case and the probabilistic case separately.

1)(Deterministic case) Assume.Then,we have

whereandThe notationmeans this factor is removed.

Define

then we have

Set

The controlled network profile evolutionary equation is expressed as

This is a standardk-valued logical control network.

2)(Probabilistic case) Assume

Note that a general procedure is provided above.However,for a particular NEG,the process may be simplified.We use some examples to depict this.

Example 7Recall Example 3.Assume players 2 and 4 are controls and the others are states.That is,

Using(2)and(4),we have

whereSimilarly,we can have

where

Finally,we have controlled NEG as

where

Example 8Recall Example 4.Assume players 3 and 4 are controls and the others are states.That is,

Then,we have

Finally,we have the networked profile evolutionary equation as

whereLcan be calculated by using the technique proposed in Example 6 as

6 Heterogeneous NEGs

This section considers some more complicated NEGs.

6.1 NEG with strategies of different length information

Definition 9Given an NEG((N,E),G,Π).

i)A player,say,i,is said to use length-r(historic)information,if

where?=max{0,t-r+1}.

ii)The NEG is said to have strategies of different length(historic)information,if there is a partitionsuch that a playerj∈Nrimplies thatjis withr-length information.

Now assumeiuses length-rinformation and lett≥r-1.Then,we have

Note that in the above equation thefiin the first equality is different from thefiin the second equation.To avoid notational complexity,we use the same notation.Now for eachjwe define

Using this set of new variables,we can express(48)into a normal form as

Define

then we have

Then,the technique developed in previous sections for standard NEGs is applicable for this case.Finally,we consider the initial values.We consider{xi(0),...,xi(r-1)|i= 1,...,n}as the initial values.In fact,only{xi(0)|i=1,...,n}are real initial values.Then,we can use the following equation:

and the method similar to(49)-(51)to calculate all other initial values.

To calculate the network profile dynamics of this kind of networks,we need the following lemma[36].

Lemma 1AssumeX∈ ΔpandY∈ Δq.We define two dummy matrices,named by 'front-maintaining operator'(FMO)and 'rear-maintaining operator'(RMO)respectively,as

Then,we have

We give an example to depict this.

Example 9Consider an NEG((N,E),G,Π),where the graph is a cycle ofn=6 nodes,and the FNG is the same as in Example 3.Assume players 2,3,4,5,6 use length-1 information,and the SUR,Π,is the same as in Example 3;and the player 1 uses length-2 information;and the SUR fort=1 it is Π,fort>1 the SUR for player 1 is as follows:using Π to getxj?(t)(t)andxj?(t-1)(t).Then,we assume

Then,the strategy dynamics for players 2,3,4,5,6 are the same as in Example 3.The strategy dynamics for player 1 is

Then,

where

Similarly,we can calculate that

where

Then,

where

As for the initial value,we have

where

Finally,we have

Then,after 18 times iterationsLconverges to the following matrix

According to this matrix(the whole set of data is omitted),we splite Δ2048into three subsets:

If initial statex0∈D1,thenast→ ∞.Else ifx0∈D2,thenElse ifx0∈D3,then

Note that not allx∈Δ2048can be chosen as the initial value,because the initial value should satisfy(56)and(57).

6.2 NEG with multi-species

Definition 10An NEG is said to havesspecies,if there is a partitionN=N1∪N2∪...∪Ns,a set of fundamental games{Gi,j|1≤i,j≤s}such that if playersp∈Ni,q∈Nj,and(p,q)∈E,thenpplays gameGi,jwithq.

To avoid the notational complexity,we assumes=2.We call these two kinds of players(nodes)whiter(W)and black(B)respectively.Then,there are three differ-ent FEGs:Gw,Gb,andGm.It is reasonable to assume thatGwandGb,which are the games between two white and two black players respectively,are symmetric,andGm,which is the game between player 1(W)and player 2(B),is asymmetric.Assume in all the three games there arekstrategies for each player.We give an example to depict this.

Example10A game with its graph depicted in Fig.2,where 4 nodes are white and two others are black.Assumek=2 and the payoff bi-matrices for three FNGs are described by

i)GwisS-2 with parameters as(snowdrift game)

ii)GbisS-2 with parameters as(hawk-dove game)

iii)GmisA-2 with parameters as

Fig.2 Graph for Example 10.

We can calculatefias in Tables 6-9.

Table 6 Payoffs→dynamics(Example 10).

Table 7 Payoffs→dynamics(Example 10).

Table 8 Payoffs→dynamics(Example 10).

Table 9 Payoffs→dynamics(Example 10).

Using SUR UI-1,We have the NEG as

where

This NEG has two fixed points(1,1,1,1,1,1)and(2,2,2,2,2,2).Besides,it has two cycles with length 2,i.e.,

and

6.3 NEG with time-varying payoffs

Definition 11An NEG is said to have varying payoffs,if the parameters in the payoff bi-matrix of the FEG are time-varying.

Example 11Recall Example 3,where network graph is Fig.1(a)and the SUR is UI-1.As for the FNG,we let the non-zero parameters be flexible,that is,FNG isS-2 with constraints:R=S,P=0(the generalized game of snowdrift).

Similar to Example 3,the FEE can be determined via Table 10.The parameters in Table 10 are as follows:

Table 10(Parameter-depending)payoffs→dynamics.

Hence,the FEE is

Denote by

Let Θ (with 0 ≤ Θ <2π)be defined by

Then,the parameter space can be decomposed into 5 parts as shown in Fig.3,where

Fig.3 A partition of parameter space.

It follows that

i)When(R,T)∈I,the FEE(58)is specified asf1where

ii)When(R,T)∈II,the FEE(58)is specified asf2where

iii)When(R,T)∈III,the FEE(58)is specified asf3where

iv)When(R,T)∈VI,the FEE(58)is specified asf4where

v)When(R,T)∈V,the FEE(58)is specified asf5where

Finally,we consider the NEG with time-varying payoff parameters as

Then,it is clear that the FEE becomes a periodic function with period 12,precisely,

where

Note that this is correct forSnandR∞(Graph of R with all integers as nodes).

7 Conclusions

This paper gives a comprehensive introduction for the modeling of networked evolutionary games.An NEG is formulated as a triple:i)network graph;ii)fundamental network game;iii)strategy updating rule.A detailed discussion with some illustrative examples are presented.Then,the fundamental evolutionary equation(FEE)is proposed,which determines the overall network dynamics.The formulas to calculate FEE according to the triple of NEG are obtained.The network dynamics is described by network profile dynamics.The technique is provided to build the network profile dynamics using FEE.Similarly,the dynamics of controlled NEG is also explained.Finally,three more complicated kinds of NEGs are also considered.These heterogeneous NEGs may have i)different length historical information,ii)multi-species,and iii)time-varying payoffs.

In one word,the NEGs are formulated as a mix-valued logical dynamic network,which provides a framework for rigorous mathematical analysis and control design of NEGs.There are many open problems for further investigations.For instance,

1)When the fundamental network game is withrperson(r>2)the network graph should ber-uniform hypergraph[45].

2)When fictitious play is used,the evolutionary dynamics with time-varying transition matrix needs to be considered[46].

3)Verifying evolutionarily stable strategies for NEGs is a challenging and important problem[41].

Acknowledgements

This paper is based on our two conference papers[47,48].

[1]J. von Neumann. Zur theorie der gesellschaftsspiele.Mathematische Annalen,1928,100(1):295-320.

[2]J.vonNeumann,O.Morgenstern.Theory of Games and Economic Behavior.Princeton:Princeton University Press,1944.

[3]J.Nash.Non-cooperative game.The Annals of Mathematics,1951,54(2):286-295.

[4]D.Gale,L.S.Shapley.College admissions and the stability of marriage.The American Mathematical Monthly,1962,69(1):9-15.

[5]D.Monderer,L.S.Shapley.Potential games.Games and Economic Behavior,1996,14(1):124-143.

[6]P.D.Taylor,L.B.Jonker.Evolutionary stable strategies and game dynamics.Mathematical Biosciences,1978,40(1/2):145-156.

[7]E.L.Charnov.The Theory of Sex Allocation.Princeton:Princiton University Press,1982.

[8]R.Sugden.The Economics of Rights,Cooperation and Welfre.Oxford:Blackwwell,1986.

[9]H.Ohtsuki,C.Hauert,E.Lieberman,et al.A simple rule for the evolution of cooperation on graphs and social networks.Nature,2006,441(7092):502-505.

[10]M.A.Nowak,R.M.May.Evolutionary games and spatial chaos.Nature,1992,359(6357):826-829.

[11]G.Szabo,C.Toke.Evolutionary prisoner's dilemma game on a square lattice.Physical Review E,1998,58(1):69-73.

[12]F.C.Santos,M.D.Santos,J.M.Pacheco.Social diversity promotes the emergence of cooperation in public goods games.Nature,2008,454(7201):213-216.

[13]L.Wang,F.Fu,X.Chen,et al.Evolutionary games on complex networks.CAAI Transactions on Intelligent Systems,2007,2(2):1-9(in Chinese).

[14]X.Wang,X.Li,G.Chen.Network Science:An Introduction.Beijing:Higher Education Press,2012(in Chinese).

[15]Z.Rong,M.Tang,X.Wang,et al.A survey on 2012 complex networks.Journal of University of Science and Technology of China,2012,41(6):801-807.

[16]D.Cheng,H.Qi,Z.Li.Analysis and Control of Boolean Networks:A Semi-tensor Product Approach.London:Springer,2011.

[17]D.Cheng,H.Qi,Y.Zhao.An Introduction to Semi-tensor Product of Matrices and Its Applications.Singapore:World Scientific,2012.

[18]D.Cheng,H.Qi,Y.Zhao.Analysis and control of general logical networks-An algebraic approach.Annual Reviews in Control,2012,36(1):11-25.

[19]E.Fornasini,M.E.Valcher.On the periodic trajectories of Boolean control networks.Automatica,2013:49(5):1506-1509.

[20]E.Fornasini,M.E.Valcher.Observability,reconstructibility and state observers of Boolean control networks.IEEE Transactions on Automatic Control,2013,58(6):1390-1401.

[21]G.Hochma,M.Margaliot,E.Fornasini,et al.Symbolic dynamics of Boolean control networks.Automatica,2013,49(8):2525-2530.

[22]D.Laschov,M.Margaliot.Controllability of Boolean control networks via the Perron-Frobenius theory.Automatica,2012,48(6):1218-1223.

[23]F.Li,J.Sun.Controllability of Boolean control networks with time delays in states.Automatica,2011,47(3):603-607.

[24]F.Li,J.Sun.Controllability of probabilistic Boolean control networks.Automatica,2011,47(12):2765-2771.

[25]H.Li,Y.Wang.Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method.Automatica,2012,48(4):688-693.

[26]L.Zhang,K.Zhang.L2stability,H∞control of switched homogeneous nonlinear systems and their semi-tensor product of matrices representation.International Journal of Robust and Nonlinear Control,2013,23(6):638-652.

[27]Y.Zhao,Z.Li,D.Cheng.Optimal control of logical control networks.IEEE Transactions on Automatic Control,2011,56(8):1766-1776.

[28]R.Li,M.Yang,T.Chu.State feedback stabilization for Boolean control networks.IEEE Transactions on Automatic Control,2013,58(7):1853-1857.

[29]Z.Liu,Y.Wang.Disturbance decoupling of mix-valued logical networks via the semi-tensor product method.Automatica,2012,48(8):1839-1844.

[30]M.Yang,R.Li,T.Chu.Controller design for disturbance decoupling of Boolean control networks.Automatica,2013,49(1):273-277.

[31]Y.Zhao,J.Kim,M.Filippone.Aggregation algorithm towards large-scale Boolean network analysis.IEEE Transactions on Automatic Control,2013,58(8):1976-1985.

[32]R.Li,M.Yang,T.Chu.Synchronization design of Boolean networks via the semi-tensor product method.IEEE Transactions on Neural Networks and Learning Systems,2013,24(6):996-1001.

[33]Y.Wang,C.Zhang,Z.Liu.A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems.Automatica,2012,48(7):1227-1236.

[34]X.Xu,Y.Hong.Matrix approach to model matching of asynchrollous sequential machines.IEEE Transactions on Automatic Control,2013,58(11):2974-2979.

[35]D.Cheng,X.Xu.Bi-decomposition of multi-valued logical functions and its applications.Automatica,2013,49(7):1979-1985.

[36]D.Cheng,F.He,H.Qi,et al.Modeling,analysis and control of networked evolutionary games.IEEE Transactions on Automatic Control,provitionary accepted:http://lsc.amss.ac.cn/～dcheng/preprint/NTGAME02.pdf.

[37]D.Cheng,T.Xu,H.Qi.Evolutionarily stable strategy of networked evolutionarily games.IEEE Transactions on Neural Networks and Learning Systems:DOI 10.1109/TNNLS.2013.2293149.

[38]D.Cheng.On finite potential game.Automatica,accepted:http://lsc.amss.ac.cn/～dcheng/preprint/FPG2014.pdf.

[39]L.Ljung.T.S?derstr?m.Theory and Practice of Recursive Identification.Cambridge:The MIT Press,1982.

[40]E.Rasmusen.Games and Information:An Introduction to Game Theory.4th ed.Oxford:Basil Blackwell,2007.

[41]J.M.Smith.Evolution and the Theorem of Games.Cambridge:Cambridge University Press,1982.

[42]J.P.Benoit,V.Krishna.Finitely repeated games.Econometrica,1985,17(4):317-320.

[43]A.Traulsen,M.A.Nowak,J.M.Pacheco.Stochastic dynamics of invasion and fixation.Physical Review E,2006,74(1):DOI 10.1103/PhysRevE.74.011909.

[44]H.P.Young.The evolution of conventions.Econometrica,1993,61(1):57-84.

[45]C.Berge.Graphs and Hypergraphs.Translated by E.Minieka,London:North-Hollabd Pub.,1973.

[46]D.Monderer,L.S.Shapley.Fictitious play property for games with identical interests.Journal of Economic Theory,1996,68(1):258-265.

[47]H.Qi,D.Cheng,H.Dong.On networked evolutionary games-Part 1:formulation.Proceedings of the 19th IFAC World Congress.South Africa:Cape Town,2014:http://lsc.amss.ac.cn/～dcheng/preprint/IFAC2014-NEG-part1.pdf.

[48]D.Cheng,F.He,T.Xu.On networked evolutionary games-Part 2:dynamics and control.Proceedings of the 19th IFAC World Congress.South Africa:Cape Town,2014:http://lsc.amss.ac.cn/～dcheng/preprint/IFAC2014-NEG-part2.pdf.

24 March 2014;revised 31 March 2014;accepted 31 March 2014

DOI10.1007/s11768-014-0038-9

?Corresponding author.

E-mail:dcheng@iss.ac.cn.cn.

This work was partially supported by National Natural Science Foundation of China(Nos.61273013,61333001,61104065,61322307).

?2014 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag Berlin Heidelberg

Daizhan CHENGgraduated from Department of Mechanics,Tsinghua University in 1970,received the M.S.degree from Graduate School of Chinese Academy of Sciences in 1981,and the Ph.D.degree from Washington University,St.Louis in 1985.Since 1990,he has been a professor with Institute of Systems Science,Academy of Mathematics and Systems Science,Chinese Academy of Sciences.His research interests include nonlinear control systems,switched systems,Hamiltonian systems,logical dynamic systems,and numerical realization for control design.He is the author/coauthor of 12books,over 240 journal papers and over 130 conference papers.He was Associate Editor of International Journal of Mathematical Systems,Estimation and Control(1990-1993),Automatica(1999-2002),Asian Journal of Control(2001-2004),Subject Editor of International Journal of Robust and Nonlinear Control(2005-2008),and Associate Editor of Journal of Systems Science and Complexity,Journal of Control Theory and Applications,Journal Systems Science and Mathematics,Editorin-Chief of Journal of Control Theory and Applications.He currently is the Deputy Editor-in-Chief of Control and Decision.He was the Chairman of IEEE CSS Beijing Chapter(2006-2008),Chairman of Technical Committee on Control Theory of Chinese Association of Automation(2003-2009).He was the first recipient of a second National Natural Science Award in China in 2008 and the recipient of Automatica 2008-2010 Theory/Methodology Best Paper Prize in 2011.He is IEEE Fellow(2005-)and IFAC Fellow(2008-).E-mail:dcheng@iss.ac.cn.

Hongsheng QIreceived the B.S.degree in Mathematics and Applied Mathematics from Anhui University in 2003 and received the Ph.D.degree in Systems Theory from Academy of Mathematics and Systems Science,Chinese Academy of Sciences in 2008.From July 2008 to May 2010,he was a postdoctoral fellow in the Key Laboratory of Systems Control,Chinese Academy of Sciences.In June 2010,he joined the Academy of Mathematics and Systems Science,Chinese Academy of Sciences as an assistant professor.He was the recipient of Automatica 2008-2010 Theory/Methodology Best Paper Prize in 2011.His research interests include nonlinear control,complex systems,and game theory.E-mail:qihongsh@amss.ac.cn.

Fenghua HEreceived her Ph.D.degree from Harbin Institute of Technology in 2005,where she is currently an associate professor in the Control and Simulation Center.Her current research interests include guidance and control of flight vehicles,cooperative control and game theory.E-mail:hefenghua@hit.edu.cn.

Tingting XUreceived her B.S.degree in Information and Computing Sciences from China University of Mining&Technology,Beijing in 2011.In September 2011,she became a M.S.candidate at the Key Laboratory of Systems and Control,Academy of Mathematics and Systems Science,Chinese Academy of Sciences.Her research interests include game theory,genetic regulatory network and multi-agent systems.E-mail:xutingting@amss.ac.cn.

Hairong DONGreceived her B.S.and M.S.degrees from Zhengzhou University,Zhengzhou,China,in 1996 and 1999,respectively,and the Ph.D.degree from Peking University,Beijing,China,in 2002.She is currently a professor with the State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University.Her research interests include optimal timetable design of railway systems,pedestrian dynamics and emergency evacuation,and multi-objective control of complex systems.E-mail:hrdong@bjtu.edu.cn.