2. School of Control Science and Engineering, Shandong University, Jinan 250061, China
In the last two decades, a great deal of interest has gone into the research of evolutionary games on graphs, namely, networked evolutionary games (NEGs) [1][4]. NEGs can be applied to investigate some practical problems, where each individual just plays game with some specific players (for example, trading partners) other than all players on a network. The network, whose nodes and edges represent, respectively, players and interaction relationship among players, depicts the topological structure of the corresponding NEG. Hence, in an NEG, a player's reward, or payoff, depends on the strategies taken by both his neighbors and himself.
One of the most important issues, among the investigation of NEGs, is to analyze each player's behavior when the evolution proceeds. Many excellent works focus on this problem. The original work [5] considered the spatial game and studied the cooperation emergence and persistence of Prisoner's Dilemma Game on twodimensional lattices. The networked adaptive dynamics of Prisoner's Dilemma Game was investigated by [6]. Recently [7] has proposed a new theoretical framework for NEGs by the semitensor product (STP) of matrices, which was established in [8] and [9]. It is worth noting that this method has been successfully applied to game theory and networked evolutionary game theory, and many essential results have been obtained. [10] gave a neat algorithm to calculate potential functions for potential games. Evolutionarily stable strategy of NEGs was considered by [11]. In addition to that, [12] and [13] investigated the optimization and control for the NEGs, respectively. [14] provided a method to convert the payoff functions of the given game to logical functions with structural matrices.
It is noticed that the above results just considered the NEGs with one memory, that is, in the NEGs, each individual determines its own strategy choice of the next move only based on its neighbors' strategies at the last step. However, many economic activities imply an obvious fact that every participator can remember more than one action of its neighbors. In this case, all the players make their strategy choices in the next move according to their neighbors' strategies in the last finite steps (
In this paper, we model the NEGs with
The remainder of the paper is organized as follows. Section Ⅱ contains some necessary preliminaries on the semitensor product and game theory. Section Ⅲ presents the main results of this paper, and Section Ⅳ gives an illustrative example to show the effectiveness of our main results, which is followed by a brief conclusion in Section Ⅴ.
Notations:
In this section, we present some necessary preliminaries, which will be used in the sequel.
Definition 1 [8]: The semitensor product of two matrices
It is noted that the semitensor product is a generalization of the ordinary matrix product, and thus we can simply call it "product" and omit the symbol "
Definition 2: Let
The semitensor product of matrices has the following fundamental properties.
Lemma 1 [8]: 1) Let
Lemma 2 [8]: Let
$ \left[I_{\prod\nolimits_{i=1}^{t1}n_i}\otimes W_{[n_t, n_{t+1}]}\otimes I_{\prod\nolimits_{i=t+2}^k n_i}\right]X $ 
is a column vector consisting of the same elements, arranged by the ordered multiindex
Lemma 3 [8]: Define the retrievers as
$ \begin{align*} S_{i, k}^n= 1_{k^{i1}}^{T} \otimes I_k \otimes 1_{k^{ni}}^{T} \end{align*} $ 
where
Then, for
Lemma 4 [8]: Assume
$ \Psi_{l, k}=\prod\limits_{i=1}^l\bigg(I_{k^{i1}}\otimes\big[(I_k\otimes W_{[k, k^{li}]})M_{r, k}\big]\bigg) $ 
then
$ M_{r, k}=\left[\begin{array}{cccc} \delta_k^1&0_k&\ldots&0_k \\ 0_k&\delta_k^2&\ldots&0_k \\ \vdots&\vdots&\ddots&\vdots\\ 0_k&0_k&\ldots&\delta_k^k \\ \end{array} \right] $ 
is the base
Lemma 5 [13]: Assume
$ \begin{align*} &D_f^{p, q}=\delta_p[\underbrace{1~ 1\ldots 1}_q ~\underbrace{2~ 2\ldots 2}_q~ \ldots~ \underbrace{p~ p\ldots p}_q]\nonumber\\ &D_r^{p, q}=\delta_q[\underbrace{\underbrace{1~2\cdots q}~\underbrace{1~2\ldots q}~\ldots~ \underbrace{1~2\ldots q}}_p].\nonumber \end{align*} $ 
Then
An
Lemma 6 [14]: Let
$ f(x_1, x_2, \ldots, x_n)=M_f\ltimes_{i=1}^nx_i $ 
where
In the following, we recall some notation in game theory.
A normal finite game
Definition 3 [17]: In an
$ \begin{align*} &p_i\left(s_1^*, \ldots, s_{i1}^*, s_i^*, s_{i+1}^*, \ldots, s_{n}^*\right)\notag\\ &\qquad \geq p_i\left(s_1^*, \ldots, s_{i1}^*, s_i, s_{i+1}^*, \ldots, s_{n}^*\right) \end{align*} $ 
for every feasible strategy
Definition 4 [13]: 1) A normal game with two players is called a fundamental network game (FNG), if
This section firstly describes the definitions of NEGs with
Without loss of generality, we assume that the FNG of the given corresponding NEG is symmetric and the game can repeat infinitely. Consider a networked evolutionary game with
1) A network: its topological structure is a connected undirected graph
2) An FNG: if
3) Players' strategy updating rules: these rules can be expressed as
$ \begin{align*} x_i(t+1)=&\ f_{i}\big(x_i(t\tau+1), \ldots, x_i(t), \notag\\ &\ x_j(t\tau+1), \ldots, x_j(t) j\in {N}_{i}\big) \end{align*} $ 
where
In the given NEG, at each time, player
$ \begin{align} p_{i}\left(x_i, x_{i}\right)=\sum\limits_{j\in \mathcal{N}_{i}}c(x_i, x_j), \quad x_i, x_j\in S_0 \end{align} $  (1) 
where
The evolutionary process of the game proceeds according to some specialized strategy adjustment rule, which is used to describe how a player chooses a proper strategy in the next step. The rest of this subsection depicts that how to design the strategy adjustment rule step by step.
In this paper, we consider the
For player
$ \begin{align} q_i^{j}(t)=\frac{1}{\tau}\sum\limits_{l=t\tau+1}^{t}I\left\{x_i(l)=j\right\} \end{align} $  (2) 
where
$ \begin{align}\label{3.3.4} q_i(t)=\left( q_i^{1}(t), q_i^{2}(t), \ldots , q_i^{k}(t) \right)^{T}. \end{align} $  (3) 
The strategy chosen by player
$ \begin{align} U_i\left(x_i, q_{i}(t)\right)=\sum\limits_{x_{i}\in S^{n1}} \bigg(p_i(x_i, x_{i})\prod\limits_{x_j\in x_{i}} q_j^{x_j}(t)\bigg) \end{align} $  (4) 
where
$ \begin{align*} &EP_i(q_{i}(t))=\notag\\ &\qquad \left\{ \tilde{x}\in S_0 ~\big~ U_i(\tilde{x}, q_{i}(t))=\max\limits_{x\in S} U_i(x, q_{i}(t)) \right\} \end{align*} $ 
which is called player
$ x_i(t+1)\in EP_i(q_{i}(t)). $ 
It is noted that player
$ \begin{align} x_i(t)=\max\left\{x x \in EP_i(q_{i}(t))\right\}. \end{align} $  (5) 
Thus, (5) leads to a pure strategy dynamics.
In addition to the idea of setting priority, there exists another option. Namely, when
$ \begin{align}\label{3.3.8} P\left\{x_i(t+1)=x^*\in EP_{i}(q_{i}(t))\right\}=\frac{1}{\leftEP_{i}(q_{i}(t))\right}. \end{align} $  (6) 
Thus, (6) leads to a mixed strategy dynamics. However, this paper concentrates on the study of the pure strategy dynamics.
There are two cases for the final dynamical behavior of pure strategy dynamics. One is that all players' strategies remain stationary at one strategy profile, which is called a fixed point, and the other is that several strategy profiles are chosen periodically with period
The aim of this paper is to study the algebraic formulation and Nash equilibrium of the given NEG as a pure strategy dynamics.
B. Algebraic Formulation of NEGs WithThis subsection investigates the algebraic formulation of the NEG given in Section ⅢA described as a pure strategy dynamics. First, we convert the dynamics of the NEG into an algebraic form.
From (5), the dynamics of the NEG with
In Step 1, using the vector form of logical variables, we identify
$ \begin{align} &p_{i}\left(x_i(t), x_{i}(t) \right)\nonumber\\ &\quad =M_c\sum\limits_{j \in \mathcal{N}_{i}}x_i(t)x_j(t)=M_c\sum\limits_{j \in \mathcal{N}_{i}}W_{[k]}x_j(t)x_i(t)\nonumber\\ &\quad=M_c W_{[k]}\left(\sum\limits_{j<i, \;j \in \mathcal{N}_{i}}x_j(t)x_i(t)+\sum\limits_{j>i, \;j \in \mathcal{N}_{i}}x_j(t)x_i(t)\right)\nonumber\\ &\quad=M_c W_{[k]}\Big(\sum\limits_{j<i, j\in \mathcal{N}_i} D_f^{k, k^{n2}}W_{[k^{j1}, k]}\notag\\ &\qquad\, +\sum\limits_{j>i, j\in\mathcal{N}_i} D_f^{k, k^{n2}}W_{[k^{j2}, k]}\Big)x_{i}(t)x_i(t)\nonumber\\ &\quad=M_{i}x_{i}(t)x_i(t) \end{align} $  (7) 
where
In Step 2, using a vector form, we define
$ \begin{align}\label{3.3.10} \begin{cases} z_i(t)=\ltimes_{l=t\tau+1}^{t} x_i(l) \\ z(t)=\ltimes_{i=1}^n z_i(t) \\ z_{i}(t)=z_1(t)\ltimes\cdots\ltimes z_{i1}(t)\ltimes z_{i+1}(t)\ltimes\cdots\ltimes z_n(t) \end{cases} \end{align} $  (8) 
where
The following proposition gives the formulation of expected payoff function (4) for player
Proposition 1: For
$ C=\left(\Phi S_{1, k^\tau}^{n1}\prod\limits_{j=2}^{n1}\left(\bigg(I_{k^{(n1)\tau}}\otimes\big(\Phi S_{j, k^\tau}^{n1}\big)\bigg)\Psi_{n1, k^\tau}\right)\right) $ 
Proof: By Lemma 3 and (8), one gets
$ \begin{align} \begin{cases} z_j(t)=S_{j, k^\tau}^{n1} z_{i}(t),&j\leq i1 \\ z_{j+1}(t)=S_{j, k^\tau}^{n1} z_{i}(t),&j>i1 \end{cases} \end{align} $  (9) 
and
$ \begin{align} x_j(t\tau+l)=S_{l, k}^{\tau} z_{j}(t), \quad l=1, 2, \ldots, \tau \end{align} $  (10) 
which denote all the strategies adopted by player
$ \begin{align} \sum\limits_{l=t\tau+1}^{t} x_j(l)=\left(\sum\limits_{l=1}^{\tau}S_{l, k}^{\tau}\right)z_j(t)=\left( \begin{array}{c} n_j^1(t) \\ n_j^2(t) \\ \vdots \\ n_j^k(t) \end{array}\right) \end{align} $  (11) 
where
$ \begin{align} q_j(t)=\frac{1}{\tau}\left(\sum\limits_{l=1}^{\tau}S_{l, k}^{\tau}\right)z_j(t)=\Phi z_j(t)=\left(\begin{array}{c} q_j^{1}(t) \\ q_j^{2}(t)\\ \vdots \\ q_j^{k}(t) \end{array} \right) \end{align} $  (12) 
and
$ \begin{align}q_j(t)=\Phi z_j(t)= \begin{cases} \Phi S_{j, k^\tau}^{n1} z_{i}(t),&j\leq i1 \\ \Phi S_{j1, k^\tau}^{n1} z_{i}(t), &j>i1 \end{cases} \end{align} $  (13) 
where
$ \begin{align} q_{i}(t)=& \ltimes_{j=1}^{n1} \Phi S_{j, k^\tau}^{n1}z_{i}(t)\nonumber\\ =&\ \Phi S_{1, k^\tau}^{n1}z_{i}(t)\Phi S_{2, k^\tau}^{n1}z_{i}(t)\ldots\Phi S_{n1, k^\tau}^{n1}z_{i}(t)\nonumber\\ =&\ \Phi S_{1, k^\tau}^{n1}\bigg(I_{k^{(n1)\tau}}\otimes\big(\Phi S_{2, k^\tau}^{n1}\big)\bigg)z_{i}^2(t) \notag\\ &\ \times\cdots\times \Phi S_{n1, k^\tau}^{n1}z_{i}(t)\nonumber\\ =&\ \Phi S_{1, k^\tau}^{n1}\bigg(I_{k^{(n1)\tau}}\otimes\big(\Phi S_{2, k^\tau}^{n1}\big)\bigg)\Psi_{n1, k^\tau}z_{i}(t)\notag\\ &\ \times\cdots\times\Phi S_{n1, k^\tau}^{n1}z_{i}(t)\nonumber\\ &\qquad\qquad\vdots\notag\\ =&\ \bigg(\Phi S_{1, k^\tau}^{n1}\prod\limits_{j=2}^{n1}\bigg(\bigg(I_{k^{(n1)\tau}}\otimes\big(\Phi S_{j, k^\tau}^{n1}\big)\bigg)\notag\\ &\ \times\Psi_{n1, k^\tau}\bigg)\bigg) z_{i}(t)\nonumber\\ :=&\ C z_{i}(t). \end{align} $  (14) 
Thus, by (7) and (14), (4) is rewritten as
$ \begin{align*} U_i(x_i, q_{i}(t))=M_i q_{i}(t) x_i = M_i C z_{i}(t) x_i =M_i^c z_{i}(t)x_i\notag \end{align*} $ 
where
In Step 3, we construct the structural matrices for the updating rules based on the
By virtue of Proposition 1, for player
$ \begin{align*} M_i^c=\left[Blk_1\left(M_i^c\right), Blk_2\left(M_i^c\right), \ldots, Blk_{k^{(n1)\tau}}\left(M_i^c\right)\right]\notag \end{align*} $ 
where the elements in the
Next, we search for the best response of player
$ Col_{\xi_{i, l}}\left(Blk_l\left(M_i^c\right)\right)\geq Col_{\xi}\left(Blk_l\left(M_i^c\right)\right)\ \forall \xi=1, 2, \ldots, k. $ 
If there are more than one maximum columns, one can pick out the unique column index
Letting
$ \begin{align} x_i(t+1)&=\tilde{L}_i z_{i}(t)=\tilde{L}_i D_{r}^{k^\tau , k^{(n1)\tau}} z_i(t) z_{i}(t)\notag\\ &=\tilde{L}_i D_{r}^{k^\tau, k^{(n1)\tau}} W_{[k^{\left(i1\right)\tau}, k^\tau]}z(t)\nonumber\\ &= L_i^x z(t) \end{align} $  (15) 
where
$ \begin{align} & z_i(t+1)\notag\\ &\quad = x_i(t\tau+2)x_i(t\tau+3)\ldots x_i(t) x_i(t+1)\notag\\ &\quad =D_{r}^{k, k} x_i(t\tau+1) x_i(t\tau+2)x_i(t\tau+3)\notag\\ &\qquad\times\cdots\times x_i(t) L_i^x z(t) \nonumber\\ &\quad =D_{r}^{k, k} D_{f}^{k^\tau, k^{(n1)\tau}} z_i(t) z_{i}(t) L_i^x z(t)\notag\\ &\quad = D_{r}^{k, k} D_{f}^{k^\tau, k^{(n1)\tau}} W_{[k^{(i1)\tau}, k^\tau]} z(t) L_i^x z(t) \notag\\ &\quad = D_{r}^{k, k} D_{f}^{k^\tau, k^{(n1)\tau}} W_{[k^{(i1)\tau}, k^\tau]} \left( I_{k^{n\tau}} \otimes L_i^x\right) z^2(t) \notag\\ &\quad = D_{r}^{k, k} D_{f}^{k^\tau, k^{(n1)\tau}} W_{[k^{(i1)\tau}, k^\tau]} \left( I_{k^{n\tau}} \otimes L_i^x\right)\notag\\ &\quad\quad\times\Psi_{n, k^\tau} z(t)\nonumber\\ &\quad = L_i z(t).\end{align} $  (16) 
Based on the above analysis, we have the following algorithm to construct the algebraic form of NEGs with
Algorithm 1: This algorithm contains three steps:
1) Calculate the structural matrix,
$ \begin{align*} M_i=&\ M_c W_{[k]}\Big(\sum\limits_{j<i, j\in \mathcal{N}_i} D_f^{k, k^{n2}}W_{[k^{j1}, k]}\notag\\ &\, +\sum\limits_{j>i, j\in\mathcal{N}_i}D_f^{k, k^{n2}}W_{[k^{j2}, k]}\Big).\notag \end{align*} $ 
2) Construct the structural matrix of expected payoff function of player
$ M_i^c=\left[ Blk_1\left(M_i^c\right), Blk_2\left(M_i^c\right), \ldots, Blk_{k^{(n1)\tau}}\left(M_i^c\right)\right] $ 
and for all
$ \begin{align*}\xi_{i, l}&=\max\{\xi_{l}\big Col_{\xi_l}\left(Blk_l\left(M_i^c\right)\right)\\ &=\max\limits_{1\leq \xi \leq k} Col_{\xi}\left(Blk_l\left(M_i^c\right)\right)\}.\end{align*} $ 
3) Construct the algebraic form of NEGs with
$ \begin{align} z(t+1)=Lz(t)\end{align} $  (17) 
where
$ \begin{align*} &L=L_1*L_2*\cdots*L_n\\ &L_i=D_{r}^{k, k} D_{f}^{k^\tau, k^{(n1)\tau}} W_{[k^{(i1)\tau}, k^\tau]} \left( I_{k^{n\tau}} \otimes L_i^x\right) \Psi_{n, k^\tau}\\ &L_i^x=\tilde{L}_i D_{r}^{k^\tau, k^{(n1)\tau}} W_{[k^{\left(i1\right)\tau}, k^\tau]}\\ &\tilde{L}_i=\delta_k[\xi_{i, 1}, \xi_{i, 2}, \ldots, \xi_{i, k^{(n1)\tau}}]\end{align*} $ 
and
Remark 1: It is important to note that the initial state
It is obvious that the matrix
However, unlike the definitions of logical variable in [8],
$ \begin{align} \begin{cases} x(t)=\ltimes_{i=1}^n x_i(t)\in \Delta_{2^n} \\ z(t)=\ltimes_{l=t\tau+1}^{t}x(l)\in \Delta_{2^{\tau n}} \end{cases} \end{align} $  (18) 
we define logical variables in this paper as (8). The following proposition shows that these two definitions are equivalent so that we can use the results in [8] to investigate the properties of
Proposition 2: Define logical variables
$ \begin{align} z = T_G^{n, m} \bar{z} \end{align} $  (19) 
holds.
Proof: We prove it by induction. When
Suppose (19) is true for
$ \begin{align} z=\ltimes_{i=1}^{s+1}\ltimes_{j=1}^v x_{ij}=\left(\ltimes_{i=1}^{s}\ltimes_{j=1}^v x_{ij}\right) \ltimes_{j=1}^v x_{s+1, j}. \end{align} $  (20) 
Using induction assumption for (20) and Lemma 2, we have
$ \begin{align} z&=T_G^{s, v}\left(\ltimes_{j=1}^v \ltimes_{i=1}^{s} x_{ij}\right)\ltimes_{j=1}^v x_{s+1, j}\notag\\ &=T_G^{s, v}\left(\ltimes_{j=1}^v x_{1j}x_{2j}\ldots x_{sj} \right) \ltimes_{j=1}^v x_{s+1, j}\notag\\ &=T_G^{s, v}\left(I_{k^s}\otimes W_{[k, k^{(v1)s}]}\otimes I_{k^{v1}}\right)\left(\ltimes_{i=1}^{s+1}x_{i, 1}\right)\notag\\ &\quad\times\left(\ltimes_{j=2}^v x_{1j}x_{2j}\ldots x_{sj} \right) \ltimes_{j=2}^v x_{s+1, j}\notag\\ &=T_G^{s, v}\left(I_{k^s}\otimes W_{[k, k^{(v1)s}]}\otimes I_{k^{v1}}\right)\notag\\ &\quad\times\left(I_{k^{2s+1}}\otimes W_{[k, k^{(v2)s}]}\otimes I_{k^{v2}}\right)\left(\ltimes_{i=1}^{s+1}x_{i, 1}\right)\notag\\ &\quad\times\left(\ltimes_{i=1}^{s+1}x_{i, 2}\right) \left(\ltimes_{j=3}^v x_{1j}x_{2j}\ldots x_{sj}\right)\ltimes_{j=3}^v x_{s+1, j}\notag\\ &\qquad\qquad\qquad\qquad\qquad \vdots\notag\\ &=T_G^{s, v}\left(I_{k^s}\otimes W_{[k, k^{(v1)s}]}\otimes I_{k^{v1}}\right)\notag\\ &\quad\times\left(I_{k^{2s+1}}\otimes W_{[k, k^{(v2)s}]}\otimes I_{k^{v2}}\right)\notag\\ &\quad\times\left(I_{k^{(v2)(s+1)+s}}\otimes W_{[k, k^s]}\otimes I_{k}\right)\bar{z}\notag\\ &=T_G^{s+1, v}\bar{z}. \end{align} $  (21) 
Similarly, for
$ \begin{align} z=&\ltimes_{i=1}^{s}\ltimes_{j=1}^{v+1} x_{ij}\notag\\ =&\left(I_{k^{(s2)(v+1)+v}}\otimes W_{[k^v, k]}\otimes I_{k}\right)\notag\\ &\times\left(I_{k^{(s3)(v+1)+v}}\otimes W_{[k^{2v}, k]}\otimes I_{k^2}\right)\notag\\ &\times\left(I_{k^v}\otimes W_{[k^{s1}, k]}\otimes I_{k^{s1}}\right)\notag\\ &\times\ltimes_{i=1}^v \ltimes_{j=1}^s x_{ij} \ltimes_{i=1}^s x_{i, v+1}. \end{align} $  (22) 
Using induction assumption for (22), we have
$ \begin{align} z=&\left(I_{k^{(s2)(v+1)+v}}\otimes W_{[k^v, k]}\otimes I_{k}\right)\notag\\ &\times\left(I_{k^{(s3)(v+1)+v}}\otimes W_{[k^{2v}, k]}\otimes I_{k^2}\right)\notag\\ &\times\left(I_{k^v}\otimes W_{[k^{s1}, k]}\otimes I_{k^{s1}}\right)\notag\\ &\times T_G^{s, v} \ltimes_{j=1}^v\ltimes_{i=1}^s x_{i, j} \ltimes_{i=1}^s x_{i, v+1}\notag\\ =&\ T_G^{s, v+1} \bar{z}. \end{align} $  (23) 
Therefore, by (21) and (23), when
Remark 2: With the help of Proposition 2, (8) can be turned into (18) by a proper coordinate transformation. So, the highorder logical network theory in [8] is also applicable to investigate the given NEG with algebraic formulation (17) in this paper. This is the main advantage to study the dynamical behavior of the game via the algebraic formulation. For example, using the results in [8], one can obtain all the final behaviors of NEGs with
1) The number of cycles of length
$ \begin{align} &N_1={\rm tr}(L)\notag\\[2mm] &N_s=\frac{{\rm tr}(L^s)\sum\limits_{k\in\mathcal{P}(s)}kN_k}{s}, \quad 2\leq s\leq k^n \end{align} $  (24) 
where
2) The set of elements on cycles of length
$ \begin{align} \mathcal{C}_s=\mathcal{D}_a(L^s)\setminus \bigcup\limits_{t\in\mathcal{P}(s)}\mathcal{D}_a(L^t) \end{align} $  (25) 
where
In this subsection, we design a freetype strategy sequence for a pseudoplayer in the given NEG to guarantee the convergence of NE. Without loss of generality, we assume that the first player is the pseudoplayer who can take strategies freely. Let
First of all, using (16), one has
$ \begin{align} y(t+1)=L_v v(t)y(t) \end{align} $  (26) 
where
$ \begin{align} & D_r^{k, k^{\tau1}} v(t1)\notag\\ &\qquad = x_1(t\tau+1)\ltimes x_1(t\tau+2)\ltimes \cdots\ltimes x_1(t1)\notag\\ &\qquad =D_f^{k^{\tau1}, k} v(t). \end{align} $  (27) 
Thus, by (26) and (27), we can obtain the algebraic form of the given NEG as
$ \begin{align} \begin{cases} y(t+1)=L_v v(t)y(t) \\[2mm] D_r^{k, k^{\tau1}} v(t1)=D_f^{k^{\tau1}, k} v(t). \end{cases} \end{align} $  (28) 
The following is a basic assumption for the given NEG.
Assumption 1: In the given NEG, the FNG has an NE
$ \begin{align} c\left(i, k\right)\leq c\left(k, k\right), \quad i\neq k. \end{align} $  (29) 
Remark 3: For convenience of calculation, Assumption 1 picks out
The following result reveals the relationship between the FNG's NEs and the corresponding NEG's NEs.
Theorem 1: Under Assumption 1, the corresponding NEG has an NE
Proof. With (1) and (29) in hands, since the FNG under study is symmetric, for player
In the following, we present a result on the fixed point of (17).
Theorem 2: Under Assumption 1, the algebraic form (17) of the given NEG has a fixed point
Proof.
$ \begin{align} U_i(x_i, q_{i}(t))=p_i(x_i, x_{i}^*) \end{align} $  (30) 
where
$ \begin{align} U_i(x_i, q_{i}(t))=p_i(x_i, x_{i}^*)\leq p_i(\Delta_k^k, x_{i}^*), \quad x_i\neq \Delta_k^k \end{align} $  (31) 
where
$ \begin{align*} x_{i}(t+1)=Col_{k^{n\tau}}\left(L_i^x\right)=\delta_{k}^k\notag \end{align*} $ 
where
$ \begin{align} z_i(t+1)=\Delta^{k^\tau}_{k^\tau} \end{align} $  (32) 
where
$ \begin{align} \delta_{ k^\tau}^{ k^\tau}=z_i(t+1)=L_i \ltimes \delta_{k^{ n\tau}}^{k^{ n\tau}}=Col_{k^{ n\tau}}\left(L_i\right) \end{align} $  (33) 
where
$ \begin{align*} \delta_{k^{ n\tau}}^{k^{n\tau}}=z(t+1)=L \ltimes \delta_{k^{ n\tau}}^{k^{ n\tau}}=Col_{k^{ n\tau}}(L).\notag \end{align*} $ 
Corollary 1: Consider the given NEG with its algebraic form (28). Under Assumption 1,
$ Col_{k^{(n1)\tau}}\left(Blk_{k^\tau}\left(L_v\right)\right)=\delta_{k^{(n1)\tau}}^{k^{(n1)\tau}} $ 
holds.
Proof: From Theorem 1, substituting the fixed point
$ y(t+1)=\Delta_{k^{(n1)\tau}}^{k^{(n1)\tau}}=L_v \ltimes \delta_{k^{ n\tau}}^{k^{n\tau}}=Col_{k^{(n1)\tau}}(Blk_{k^\tau}(L_v)). $ 
Finally, we study how to design a freetype strategy sequence to guarantee the convergence of the Nash equilibrium and present the following result.
Theorem 3: Consider the NEG with the algebraic form (28), and assume that Assumption 1 holds. Then, the evolutionary dynamics of the game globally converges to the NE
$ \begin{align} Col_j(Blk_\alpha(\bar{L}R_\mu))=\delta_{k^{(n1)\tau}}^{k^{(n1)\tau}}\quad \forall\ 1\leq j \leq k^{(n1)\tau} \end{align} $  (34) 
and
$ \begin{align} D_{r}^{k, k^{\tau1}} v(\mu1)=\Delta_{k^{\tau1}}^{k^{\tau1}} \end{align} $  (35) 
where
Proof: Firstly, using Lemma 1 and (28), one has
$ \begin{align} y(\mu)&=L_v v(\mu1)y(\mu1)\notag\\ &=L_v v(\mu1)L_v v(\mu2)y(\mu2)\notag\\ &=L_v(I_{k^\tau}\otimes L_v)v(\mu1)v(\mu2)y(\mu2)\notag\\ &=L_v(I_{k^\tau}\otimes L_v)(I_{k^{2\tau}}\otimes L_v)\cdots(I_{k^{(\mu1)\tau}}\otimes L_v)\notag\\ &\quad\times v(\mu1)v(\mu2)\cdots v(0)y(0)\notag\\ &=\bar{L}v(\mu1)v(\mu2)\cdots v(0)y(0). \end{align} $  (36) 
However, (27) implies that
$ \begin{align}\label{3.3.29.4} &v(\mu1)\ltimes v(\mu2)\ltimes \cdots\ltimes v(0)\notag\\ &\quad =\ltimes_{i=\mu\tau}^{\mu1} u(i) \ltimes_{i=\mu\tau1}^{\mu2} u(i)\ltimes\cdots\ltimes_{i=\tau+1}^{0}u(i)\notag\\ &\quad = W_{[k^\tau]} u(\mu\tau1)\left(\ltimes_{i=\mu\tau}^{\mu2}u(i)\right)^2 u(\mu1)\notag\\ &\qquad\times \ltimes_{i=\mu\tau2}^{\mu3}u(i)\ltimes\cdots\ltimes_{i=\tau+1}^{0}u(i) \notag\\ &\quad =W_{[k^\tau]}\left(I_k\otimes \Psi_{\tau1, k} \right)\ltimes_{i=\mu\tau1}^{\mu1}u(i) \notag\\ &\qquad \times\ltimes_{i=\mu\tau2}^{\mu3}u(i)\ltimes\cdots\ltimes_{i=\tau+1}^{0}u(i)\notag\\ &\quad =W_{[k^\tau]}\left(I_k\otimes \Psi_{\tau1, k} \right) W_{[k^\tau, k^{\tau+1}]}\left(I_k\otimes \Psi_{\tau1, k} \right)\notag\\ &\qquad \times\ltimes_{i=\mu\tau2}^{\mu1}u(i) \ltimes_{i=\mu\tau3}^{\mu4}u(i)\ltimes\cdots\ltimes_{i=\tau+1}^{0}u(i) \notag\\ &\quad =\prod\limits_{i=1}^{\mu1}\left( W_{[k^\tau, k^{\tau+i1}]}\left(I_k\otimes \Psi_{\tau1, k} \right)\right)\left(\ltimes_{i=\tau+1}^{\mu1}u(i)\right)\notag\\ &\quad = R_{\mu}\left(\ltimes_{i=\tau+1}^{\mu1}u(i)\right). \end{align} $  (37) 
Thus, by virtue of (37), we rewrite (36) as
$ \begin{align} y(\mu)=\bar{L}R_{\mu}\left(\ltimes_{i=\tau+1}^{\mu1}u(i)\right)y(0). \end{align} $  (38) 
Because of (34), (41), and (38), for
$ \begin{align} y(\mu)&=Blk_{\alpha}(\bar{L}R_\mu)y(0)\notag\\ &=\delta_{(n1)\tau}[(n1)\tau, (n1)\tau, \ldots, (n1)\tau]y(0)\notag\\ &=\Delta_{k^{(n1)\tau}}^{k^{(n1)\tau}}. \end{align} $  (39) 
By(35), (41) and the definition of
$ \begin{align} v(t)=v(\mu)=D_{r}^{k, k^{\tau1}} v(\mu1)\ltimes \Delta_k^k = \Delta_{k^\tau}^{k^\tau}, \quad t\geq\mu. \end{align} $  (40) 
Assuming that Assumption 1 holds, using (39), (40), and Corollary 1, one can see that for
$ \begin{align*} y(\mu+d)&=\cdots=y(\mu+1)=L_v v(\mu) y(\mu)\notag\\ &=Blk_{k^\tau}(L_v)y(\mu)=Col_{k^{(n1)\tau}}(Blk_{k^\tau}(L_v))\notag\\ &=\Delta_{k^{(n1)\tau}}^{k^{(n1)\tau}}, \quad d>0\notag \end{align*} $ 
and
$ \begin{align*} v(t)\ltimes y(t)=\Delta_{k^{n\tau}}^{k^{n\tau}}, \quad t\geq \mu\notag \end{align*} $ 
that is, by the definition of
From the proof of Theorem 3, one can easily design a freetype strategy sequence for player
Corollary 2: Consider the NEG with the algebraic form (28), and assume that Assumption 1 holds. If there exist integers
$ \begin{align} x_1(t) =\begin{cases} \widetilde{u}(t), &\tau+1 \leq t \leq \mu1\\[2mm] \Delta_k^k, &t\geq \mu \end{cases} \end{align} $  (41) 
where
In this section, we give an illustrative example to show how to use our results to investigate networked evolutionary games with
Example 1: Consider an NEG with the following basic factors:
1) A network topological structure, denoted by
Download:


Fig. 1 The network. 
2) The FNG's payoff bimatrix shown in Table Ⅰ;
3) The evolutionary rule is
With the help of Algorithm 1, the algebraic form of the game is given as
$ \begin{align} L =&\ \delta_{64}[1~ 3~ 1~ 23~ 9~ 27~ 25~ 31~ 1~ 19~ 17~ 23~ 26~ 28~ 26~ 32\notag\\ &~ 33~ 39~ 37~ 55~ 42~ 64~ 62~ 64~ 34~ 56~ 54~ 56~ 58~ 64~ 62~ 64\notag\\ &~ 1~ 7~5~ 23~ 10~ 32~ 30~ 32~ 2~ 24~ 22~ 24~ 26~ 32~ 30~ 32~ 38\notag\\ &~ 40~ 38~ 56~ 46~ 64~ 62~ 64~ 38~ 56~ 54~ 56~ 62~ 64~ 62~ 64 ]. \end{align} $  (42) 
Then, from (42), by (24) and (25), one can see that 1) the fixed points are
The rest of this section studies the strategy sequence design of the given NEG. Using Algorithm 1 and considering player 1 as a pseudoplayer, we have
$ \begin{align} L_v=&\ \delta_{16}[ 1~ 3~ 1~ 7~ 9~ 11~ 9~ 15~ 1~ 3~ 1~ 7~ 10~ 12~ 10~ 16\notag \\&~ 1~ 7~ 5~ 7~ 10~ 16~ 14~ 16~ 2~ 8~ 6~ 8~ 10~ 16~ 14~ 16~ 1\notag\\&~ 7~ 5~ 7~ 10~ 16~ 14~ 16~ 2~ 8~ 6~ 8~ 10~ 16~ 14~ 16~ 6~ 8\notag\\&~ 6~ 8~ 14~ 16~ 14~ 16~ 6~ 8~ 6~ 8~ 14~ 16~ 14~ 16 ]. \end{align} $  (43) 
By virtue of (43), a simple calculation shows that
$ \begin{align} & Blk_8\left(L_v(I_4\otimes L_v)\right)=Blk_{12}\left(L_v(I_4\otimes L_v)\right)\notag\\ &\qquad =Blk_{16}\left(L_v(I_4\otimes L_v)\right)=\delta_{16}[\underbrace{16, 16, \ldots, 16}_{16} ]. \end{align} $  (44) 
Then, from Theorem 3 and (44), the evolutionary process converges to the NE
Download:


Fig. 2 The responses strategy sequence of three players of the NEG under the given freetype strategy sequence. 
In this paper, we have investigated the modeling and analysis for a class of networked evolutionary games with finite memories based on
[1]  R. Axelrod and W. D. Hamilton, "The evolution of cooperation, " Science, vol. 211, no. 4489, pp. 13901396, Mar. 1981. 
[2]  M. A. Nowak and R. M. May, "The spatial dilemmas of evolution, " Int. J. Bifurcat. Chaos, vol. 3, no. 1, pp. 3578, Feb. 1993. http://adsabs.harvard.edu/abs/1993IJBC....3...19E 
[3]  G. Szabó and C. Töke, "Evolutionary prisoner's dilemma game on a square lattice, " Phys. Rev. E, vol. 58, no. 1, pp. 6973, Jul. 1998. http://arxiv.org/abs/condmat/9710096 
[4]  R. Sugden, The Economics of Rights, Cooperation and Welfare. Oxford, UK: Blackwell, 1986. 
[5]  M. A. Nowak and R. M. May, "Evolutionary games and spatial chaos, " Nature, vol. 359, no. 6398, pp. 826829, Oct. 1992. http://www.nature.com/doifinder/10.1038/359826a0 
[6]  M. G. Zimmermann and V. M. Eguíluz, "Cooperation, social networks, and the emergence of leadership in a prisoner's dilemma with adaptive local interactions, " Phys. Rev. E, vol. 72, no. 5, pp. 056118, Nov. 2005. http://www.ncbi.nlm.nih.gov/pubmed/16383699 
[7]  D. Z. Cheng, H. S. Qi, F. H. He, T. T. Xu, and H. R. Dong, "Semitensor product approach to networked evolutionary games, " Control Theory Technol., vol. 12, no. 2, pp. 198214, May 2014. https://link.springer.com/article/10.1007/s1176801400389 
[8]  D. Z. Cheng, H. S. Qi, and Z. Q. Li, Analysis and Control of Boolean Networks: A SemiTensor Product Approach. London, UK: Springer, 2011. 
[9]  D. Z. Cheng, H. S. Qi, and Y. Zhao, "Analysis and control of Boolean networks: a semitensor product approach, " Acta Autom. Sinica, vol. 37, no. 5, pp. 529540, May 2011. http://en.cnki.com.cn/Article_en/CJFDTotalMOTO201105004.htm 
[10]  D. Z. Cheng, "On finite potential games, " Automatica, vol. 50, no. 7, pp. 17931801, Jul. 2014. 
[11]  D. Z. Cheng, T. T. Xu, and H. S. Qi, "Evolutionarily stable strategy of networked evolutionary games, " IEEE Trans. Neural Netw. Learn. Syst., vol. 25, no. 7, pp. 13351345, Jul. 2014. http://ieeexplore.ieee.org/document/6683009/ 
[12]  P. L. Guo, Y. Z. Wang, and H. T. Li, "Algebraic formulation and strategy optimization for a class of evolutionary networked games via semitensor product method, " Automatica, vol. 49, no. 11, pp. 33843389, Nov. 2013. http://www.sciencedirect.com/science/article/pii/S0005109813004093 
[13]  D. Z. Cheng, F. H. He, H. S. Qi, and T. T. Xu, "Modeling, analysis and control of networked evolutionary games, " IEEE Trans. Autom. Control, vol. 60, no. 9, pp. 24022415, Sep. 2015. http://ieeexplore.ieee.org/document/7042754/ 
[14]  H. T. Li, Y. Z. Wang, and Z. B. Liu, "A semitensor product approach to pseudoBoolean functions with application to Boolean control networks, " Asian J. Control, vol. 16, no. 4, pp. 10731081, Jul. 2014, doi: 10.1002/asjc.767. https://www.researchgate.net/publication/264162475_A_SemiTensor_Product_Approach_to_PseudoBoolean_Functions_with_Application_to_Boolean_Control_Networks 
[15]  Y. Zhao, Z. Q. Li, and D. Z. Cheng, "Optimal control of logical control networks, " IEEE Trans. Autom. Control, vol. 56, no. 8, pp. 17661776, Aug. 2011. 
[16]  Y. F. Mu and L. Guo, Optimization and identification in a nonequilibrium dynamic game. In Proc. 48th IEEE Conf. Decision and Control, Held Jointly with 28th Chinese Control Conf., Shanghai, China, 2009, pp. 57505755. 
[17]  R. Gibbons, A Primer in Game Theory. Harlow, UK: Prentice Hall, 1992. 
[18]  D. Fudenberg and D. K. Levine, The Theory of Learning in Games. Cambridge, MA, USA: MIT Press, 1998. 
[19]  P. Zhang, Y. W. Fang, X. B. Hui, X. A. Liu, and L. LI, "Near optimal strategy for nonlinear stochastic differential games based on the technique of statistical linearization, " Acta Autom. Sinica, vol. 39, no. 4, pp. 390399, Apr. 2013. http://www.sciencedirect.com/science/article/pii/S1874102913600385 