Semi-tensor product approach to networked evolutionary games

关键词:  Networked evolutionary game  Fundamental evolutionary equation  Strategy profile dynamics  Homogeneous/heterogeneous NEG  Semi-tensor product of matrices

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

摘要:

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.

Abstract:

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.