IEEE/CAA Journal of Automatica Sinica  2018, Vol. 5 Issue(4): 818-826   PDF    
A Matrix Approach to the Modeling and Analysis of Networked Evolutionary Games With Time Delays
Guodong Zhao1, Yuzhen Wang2, Haitao Li1     
1. School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China;
2. School of Control Science and Engineering, Shandong University, Jinan 250061, China
Abstract: Using the semi-tensor product method, this paper investigates the modeling and analysis of networked evolutionary games (NEGs) with finite memories, and presents a number of new results. Firstly, a kind of algebraic expression is formulated for the networked evolutionary games with finite memories, based on which the behavior of the corresponding evolutionary game is analyzed. Secondly, under a proper assumption, the existence of Nash equilibrium of the given networked evolutionary games is proved and a free-type strategy sequence is designed for the convergence to the Nash equilibrium. Finally, an illustrative example is worked out to support the obtained new results.
Key words: Fictitious play process     Nash equilibrium     networked evolutionary games (NEGs)     semi-tensor product of matrices    
Ⅰ. INTRODUCTION

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 two-dimensional 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 semi-tensor 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 ( $\tau$ steps), where $1\leq\tau<\infty$ . Therefore, the hypothesis that all the players in the NEGs can remember their neighbors' strategies in the past $\tau$ steps is reasonable. Without the network [15], [16] investigated the optimization and identification, separately, in evolutionary games with $\tau$ -memory. Although there were some excellent results on the study of NEGs with one memory and evolutionary games with $\tau$ -memory, there are, to our best knowledge, no results available on NEGs with $\tau$ memories.

In this paper, we model the NEGs with $\tau$ memories and construct an algebraic formulation for the given systems based on $\tau$ -memory version of fictitious play process. The main contributions of this paper are as follows: 1) The STP method is firstly applied to the study of the NEGs with $\tau$ memories, and a new theoretical framework is established via this method; 2) A general procedure is proposed to design a free-type strategy sequence for the convergence of the Nash equilibrium, which can be easily realized with the help of MATLAB toolbox established in [8].

The remainder of the paper is organized as follows. Section Ⅱ contains some necessary preliminaries on the semi-tensor 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: $\mathbb{ R}_{m\times n}$ denotes the set of $m\times n$ real matrices. $\mathbb{ R}_{m\times n}^+$ denotes the set of $m\times n$ nonnegative real matrices. $\Delta_n = \{\Delta_n^i|i=1, 2, \ldots, n\}$ , where $\delta_{n}^i$ is the $i$ th column of the identity matrix $I_n$ . An $n\times t$ matrix $M$ is called a logical matrix, if $M=[\Delta_n^{i_1}\;\Delta_n^{i_2}\;\ldots\;\Delta_n^{i_t}]$ and $M$ is briefly denoted by $M=\Delta_n[i_1\;i_2\;\ldots\;i_t]$ . Define the set of $n\times t$ logical matrices as ${\mathcal{L}}_{n\times t}$ . $Col_i(L)\ (Row_i(L))$ is the $i$ th column (row) of matrix $L$ . For a set $E$ , $|E|$ denotes the number of elements in $E$ .

Ⅱ. PRELIMINARIES

In this section, we present some necessary preliminaries, which will be used in the sequel.

Definition 1 [8]: The semi-tensor product of two matrices $A$ $\in$ $\mathbb{R}_{m\times n}$ and $B\in \mathbb{ R}_{p\times t}$ is defined as $A\ltimes B=(A\otimes I_{\frac{\alpha}{n}})(B\otimes I_{\frac{\alpha}{p}})$ , where $\alpha=lcm(n, p)$ is the least common multiple of $n$ and $p$ , and $\otimes$ is the Kronecker product.

It is noted that the semi-tensor product is a generalization of the ordinary matrix product, and thus we can simply call it "product" and omit the symbol " $\ltimes$ " without confusion.

Definition 2: Let $M\in \mathbb{ R}_{q\times s}$ and $N\in\mathbb{ R}_{p\times s}$ . Define the Khatri-Rao product of $M$ and $N$ , denoted by $M\ast N$ , as $M$ $\ast$ $N$ $=[Col_1(M)\ltimes Col_1(N)\ \ Col_2(M)\ltimes Col_2(N)\ \ldots\ Col_s(M)$ $\ltimes$ $Col_s(N)]\in\mathbb{ R}_{pq\times s}$ .

The semi-tensor product of matrices has the following fundamental properties.

Lemma 1 [8]: 1) Let $X\in\mathbb{ R}_m$ and $Y\in\mathbb{ R}_n$ be two column vectors. Then, $W_{[m, n]}XY=YX$ , where $W_{[m, n]}$ is called the swap matrix. Especially, $W_{[n, n]}=W_{[n]}$ . 2) (Pseudo-commutative property) Let $X\in\mathbb{ R}_t$ and $A\in\mathbb{ R}_{m\times n}$ . Then, $XA$ $=$ $(I_t\otimes A)X$ holds.

Lemma 2 [8]: Let $X=(x_{i_1, i_2, \ldots, i_k})$ be a column vector with its elements arranged by the ordered multi-index $Id(i_1, $ $\ldots, $ $i_k;$ $n_1, \ldots, n_k)$ (Definition 2.3 on Page 23 of [8]). Then

$ \left[I_{\prod\nolimits_{i=1}^{t-1}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 multi-index $Id(i_1, \ldots, i_{t+1}, i_{t}, \ldots, $ $i_k;n_1, \ldots, $ $n_{t+1}, $ $n_t, \ldots, n_k)$ .

Lemma 3 [8]: Define the retrievers as

$ \begin{align*} S_{i, k}^n= 1_{k^{i-1}}^{T} \otimes I_k \otimes 1_{k^{n-i}}^{T} \end{align*} $

where $1_s^{T}=(\underbrace{1, 1, \ldots, 1}_s)$ and $i$ $=$ $1, $ $2, $ $\ldots, n$ .

Then, for $x=\ltimes_{i=1}^n x_i$ , $x_i=S_{i, k}^n x$ holds, where $x_i\in \Delta_{k}$ and $i=1, 2, \ldots, n$ .

Lemma 4 [8]: Assume $x=\ltimes_{i=1}^l x_i$ , where $x_i\in\Delta_k$ and $i$ $=$ $1, 2, \ldots, l$ . Define

$ \Psi_{l, k}=\prod\limits_{i=1}^l\bigg(I_{k^{i-1}}\otimes\big[(I_k\otimes W_{[k, k^{l-i}]})M_{r, k}\big]\bigg) $

then $x^2=\Psi_{l, k}x$ holds, where

$ 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- $k$ power-reducing matrix satisfying $z^2=M_{r, k}z$ , $z$ $\in$ $\Delta_k$ , and $0_k\in\mathbb{ R}_k$ is a zero vector.

Lemma 5 [13]: Assume $X\in\Delta_p$ and $Y\in \Delta_q$ . Define two dummy matrices, named by "front-maintaining operator (FMO)" and "rear-maintaining operator (RMO)" respectively, as

$ \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 $D_f^{p, q}XY=X$ , $D_r^{p, q}XY=Y$ .

An $n$ -ary pseudo-logical (or logical) function $f(x_1, $ $x_2, $ $\ldots, $ $x_n)$ is a mapping from $\Delta_{k}^n$ to $\mathbb{ R}$ (or from $\Delta_{k}^n$ to $\Delta_{m}$ ). The following result shows how to express a pseudo-logical (or logical) function into its algebraic form.

Lemma 6 [14]: Let $f:\Delta_{k}^n\rightarrow \mathbb{ R}$ (or $f:\Delta_{k}^n\rightarrow \Delta_{m}$ ) be a pseudo-logical (or logical) function. Then there exists a unique matrix $M_f\in\mathbb{ R}_{1\times k^n}$ (or $M_f\in\mathcal{L}_{m\times k^n}$ ), called the structural matrix of $f$ , such that

$ f(x_1, x_2, \ldots, x_n)=M_f\ltimes_{i=1}^nx_i $

where $x_i\in \Delta_{k}, \ i=1, 2, \ldots, n$ , $Col_j(M_f)=f(\Delta_{k^n}^j)$ , and $j$ $=$ $1, 2, \ldots, k^n$ .

In the following, we recall some notation in game theory.

A normal finite game $(N, S, P)$ , considered in this paper, consists of three factors [17]: $1)$ $n$ players $N=\{1, 2, \ldots, n\}$ ; $2)$ Player $i$ has strategy set $S_i$ , $S=\prod_{i=1}^n S_i$ is the set of strategy profiles, $i\in N$ ; $3)$ Player $i$ has its payoff function $p_iS\rightarrow\mathbb{R}$ , $P=\{p_1, p_2, \ldots, p_n\}$ is the set of payoff functions, $i$ $\in$ $\mathbb{N}$ .

Definition 3 [17]: In an $n$ -player normal form finite game $G$ $=\{S_1, \ldots, S_n; p_1, \ldots, p_n\}$ , the strategy profile $(s_1^*, s_2^*, \ldots, $ $s_n^*)$ is a Nash equilibrium (NE) if, for each player $i$ , $s_i^*$ is (at least tied for) player $i$ 's best response to the strategies specified for the $n-1$ other players, $(s_1^*, \ldots, s_{i-1}^*, s_{i+1}^*, \ldots, s_n^*)$ , that is,

$ \begin{align*} &p_i\left(s_1^*, \ldots, s_{i-1}^*, s_i^*, s_{i+1}^*, \ldots, s_{n}^*\right)\notag\\ &\qquad \geq p_i\left(s_1^*, \ldots, s_{i-1}^*, s_i, s_{i+1}^*, \ldots, s_{n}^*\right) \end{align*} $

for every feasible strategy $s_i\in S_i$ , where $S_i$ is the set of strategies of player $i$ and $p_i$ is the corresponding payoff function.

Definition 4 [13]: 1) A normal game with two players is called a fundamental network game (FNG), if $S_1=$ $S_2$ $=$ $S_0=\{1, 2, \ldots, k\}$ and player $i$ 's payoff function is $c_i= c_i(x, y)$ , where $x$ is player 1's strategy, $y$ is player 2's strategy, and $i$ $=$ $1, 2$ . Namely, $N=\{1, 2\}$ , $S=S_0\times S_0$ , and $P=\{c_1, c_2\}$ ; $2)$ An FNG is symmetric, if $c_1(x, y)=c_2(y, x)$ , $\forall x, y\in S_0$ .

Ⅲ. MAIN RESULTS

This section firstly describes the definitions of NEGs with $\tau$ memories and $\tau$ -memory version of fictitious play process. Then, based on the above definitions, a kind of algebraic expression is formulated for the given NEGs. Finally, by adding a pseudo-player to the game, a free-type strategy sequence is designed to guarantee the convergence of Nash equilibrium.

A. Modeling of NEG With $\tau$ Memories

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 $\tau$ memories, which consists of the following three ingredients:

1) A network: its topological structure is a connected undirected graph $(N, {E})$ , where $N=\{1, 2, \ldots, n\}$ is the set of all players, and ${E}=\{(i, j)|$ there exists interaction between players $i$ and $j\}$ is the set of edges.

2) An FNG: if $(i, j)\in {E}$ , then $i$ and $j$ play the FNG in the network with strategies $x_i(t)$ and $x_j(t)$ at time $t$ , respectively.

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 $x_j(l)\in S_0$ is the strategy of player $j$ at time $l$ , $l=t$ - $\tau+1, t-\tau+2, \ldots, t$ , ${N}_{i}$ is the neighborhood of player $i$ , that is, $j \in {N}_{i}$ if and only if $(i, j)\in \mathcal{E}$ , $i\in{ N}$ . Obviously, $i$ $\notin$ ${N}_{i}$ and $j \in \mathcal N_{i}\Leftrightarrow i \in{N}_{j}$ .

In the given NEG, at each time, player $i$ only plays with its neighbors, and its aggregate payoff $p_{i}: S_0^n\rightarrow \mathbb{ R}$ is the sum of payoffs gained by playing with all its neighbors, i.e.,

$ \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 $x_{-i}=(x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)$ and $c$ is the payoff function of the FNG.

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 $\tau$ -memory version of fictitious play process [18].

For player $i\in N$ , define the empirical frequency, $q_i^{j}(t)$ , as the percentage of stages at which player $i$ has chosen the strategy $j\in S_0$ from time $t-\tau+1$ to time $t$ , i.e.,

$ \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 $x_i(l)\in S_0$ is player $i$ 's strategy chosen at time $l= t$ - $\tau+1, t-\tau+2, \ldots, t$ , and $I\{\cdot\}$ is indicator function. Now, define the empirical frequency vector for player $i$ at time $t$ as

$ \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 $i$ at time $t+1$ is based on the presumption that other players are playing randomly and independently according to empirical frequency vector $q_j(t)$ , where $j=1, \ldots, i-1, i+1, \ldots, n$ . Under this presumption, the expected payoff function for the strategy $x_i\in S_0$ of player $i$ is

$ \begin{align} U_i\left(x_i, q_{-i}(t)\right)=\sum\limits_{x_{-i}\in S^{n-1}} \bigg(p_i(x_i, x_{-i})\prod\limits_{x_j\in x_{-i}} q_j^{x_j}(t)\bigg) \end{align} $ (4)

where $q_{-i}(t)=(q_1(t), \ldots, q_{i-1}(t), q_{i+1}(t), \ldots, q_n(t))$ and $x_{-i}$ $=(x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)$ . In the $\tau$ -memory version of fictitious play process, player $i$ used the expected payoff (4) to select a strategy at time $t+1$ from the set

$ \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 $i$ 's best response to $q_{-i}(t)$ . Based on this, we have

$ x_i(t+1)\in EP_i(q_{-i}(t)). $

It is noted that player $i$ may have more than one best responses, that is, $|EP_i(q_{-i}(t))|>1$ . In this case, we define a priority for the strategy choice as follows: for $x, \ y\in S_0$ , $x$ has priority over $y$ , if and only if $x>y$ . Then, player $i$ chooses its strategy according to the following way:

$ \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 $|EP_{i}(q_i(t))|> 1$ holds, we randomly choose one with equal probability. That is,

$ \begin{align}\label{3.3.8} P\left\{x_i(t+1)=x^*\in EP_{i}(q_{-i}(t))\right\}=\frac{1}{\left|EP_{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 $s\geq 2$ , which is called a cycle with length $s$ .

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 With $\tau$ Memories

This 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 $\tau$ memories can be regarded as a logical network, based on which the dynamics can be converted into an algebraic form by using the STP. According to the $\tau$ -memory version of fictitious play process depicted in Section Ⅲ-A, the strategy of player $i$ at time $t+1$ is the best response against its empirical frequency vector (3) generated from its neighbors at time $t$ . Thus, to obtain the algebraic formulation of the NEG with $\tau$ memories, one can take the following three steps: 1) convert the payoff function of each player into an algebraic form; 2) convert the expected payoff function (4) of each player into an algebraic form; 3) identify the best strategy for every player by the algebraic form of its expected payoff function (4).

In Step 1, using the vector form of logical variables, we identify $S_0 \sim \Delta_k$ , where " $\sim$ " denotes that the strategy $j\in S_0$ is equivalent to $\delta_k^j \in \Delta_k, ~j=1, 2, \ldots, k$ . Then, by Lemma 1, Lemma 5, Lemma 6, and (1), the payoff function of player $i$ can be expressed as

$ \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^{n-2}}W_{[k^{j-1}, k]}\notag\\ &\qquad\, +\sum\limits_{j>i, j\in\mathcal{N}_i} D_f^{k, k^{n-2}}W_{[k^{j-2}, k]}\Big)x_{-i}(t)x_i(t)\nonumber\\ &\quad=M_{i}x_{-i}(t)x_i(t) \end{align} $ (7)

where $M_c\in\mathbb{ R}_{1\times k^2}$ is the structural matrix of the FNG's payoff function and $M_{i}\in\mathbb{ R}_{1\times k^n}$ is the structural matrix of $p_{i}$ , $x_i(t)$ $\in\Delta_k$ is the strategy of player $i$ at time $t$ , and $x_{-i}(t)=$ $x_1(t)$ $\ltimes \cdots \ltimes x_{i-1}(t)\ltimes x_{i+1}(t)\ltimes \cdots \ltimes x_n(t)\in \Delta_{k^{n-1}}$ .

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_{i-1}(t)\ltimes z_{i+1}(t)\ltimes\cdots\ltimes z_n(t) \end{cases} \end{align} $ (8)

where $z_i(t)\in \Delta_{k^{\tau}}$ , $z(t)\in \Delta_{k^{n\tau}}$ , and $z_{-i}(t)\in\Delta_{k^{(n-1)\tau}}$ .

The following proposition gives the formulation of expected payoff function (4) for player $i$ and constructs its corresponding structural matrix $M_i^c$ , $i\in N$ .

Proposition 1: For $\forall i\in N$ , let $M_i\in\mathbb{ R}_{1\times k^n}$ be the structural matrix of the payoff function of player $i$ . Then, the expected payoff function (4) can be rewritten as $ U_i(x_i, q_{-i}(t))=M_i q_{-i}(t)x_i=M_i\ltimes C z_{-i}(t) x_i:=M_i^c z_{-i}(t)x_i, \notag $ where $M_i^c$ is the structural matrix of expected payoff function (4) for player $i$ ,

$ C=\left(\Phi S_{1, k^\tau}^{n-1}\prod\limits_{j=2}^{n-1}\left(\bigg(I_{k^{(n-1)\tau}}\otimes\big(\Phi S_{j, k^\tau}^{n-1}\big)\bigg)\Psi_{n-1, k^\tau}\right)\right) $

$\Phi=\frac{1}{\tau}\left(\sum_{l=1}^{\tau}S_{l, k}^{\tau}\right)$ , $S_{j, k^\tau}^{n-1}$ is defined as in Lemma 3, $j=1, $ $2, $ $\ldots, n-1, \Psi_{n-1, k^\tau}$ is defined as in Lemma 4, and $i\in N$ .

Proof: By Lemma 3 and (8), one gets

$ \begin{align} \begin{cases} z_j(t)=S_{j, k^\tau}^{n-1} z_{-i}(t),&j\leq i-1 \\ z_{j+1}(t)=S_{j, k^\tau}^{n-1} z_{-i}(t),&j>i-1 \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 $j$ from time $t-\tau+1$ to time $t$ , where $j=1, \ldots, i-1, i+1, \ldots, n$ . Thus, we have

$ \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 $n_j^m(t)=\sum_{l=t-\tau+1}^{t}I\{x_j(t)=\delta_k^m \}$ represents how many times player $j$ chooses strategy $m$ from time $t-\tau+1$ to $t$ , $m=1, 2, \ldots, k$ . By (3), (9), (10), and (11), one has

$ \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}^{n-1} z_{-i}(t),&j\leq i-1 \\ \Phi S_{j-1, k^\tau}^{n-1} z_{-i}(t), &j>i-1 \end{cases} \end{align} $ (13)

where $j=1, \ldots, i-1, i+1, \ldots, n$ . By virtue of Lemma 1, Lemma 4, (12), and (13), we obtain

$ \begin{align} q_{-i}(t)=& \ltimes_{j=1}^{n-1} \Phi S_{j, k^\tau}^{n-1}z_{-i}(t)\nonumber\\ =&\ \Phi S_{1, k^\tau}^{n-1}z_{-i}(t)\Phi S_{2, k^\tau}^{n-1}z_{-i}(t)\ldots\Phi S_{n-1, k^\tau}^{n-1}z_{-i}(t)\nonumber\\ =&\ \Phi S_{1, k^\tau}^{n-1}\bigg(I_{k^{(n-1)\tau}}\otimes\big(\Phi S_{2, k^\tau}^{n-1}\big)\bigg)z_{-i}^2(t) \notag\\ &\ \times\cdots\times \Phi S_{n-1, k^\tau}^{n-1}z_{-i}(t)\nonumber\\ =&\ \Phi S_{1, k^\tau}^{n-1}\bigg(I_{k^{(n-1)\tau}}\otimes\big(\Phi S_{2, k^\tau}^{n-1}\big)\bigg)\Psi_{n-1, k^\tau}z_{-i}(t)\notag\\ &\ \times\cdots\times\Phi S_{n-1, k^\tau}^{n-1}z_{-i}(t)\nonumber\\ &\qquad\qquad\vdots\notag\\ =&\ \bigg(\Phi S_{1, k^\tau}^{n-1}\prod\limits_{j=2}^{n-1}\bigg(\bigg(I_{k^{(n-1)\tau}}\otimes\big(\Phi S_{j, k^\tau}^{n-1}\big)\bigg)\notag\\ &\ \times\Psi_{n-1, 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 $q_{-i}(t)=q_1(t)\ltimes\cdots \ltimes q_{i-1}(t)\ltimes q_{i+1}(t)\ltimes\cdots\ltimes q_n(t)$ and $i\in { N}$ .

In Step 3, we construct the structural matrices for the updating rules based on the $\tau$ -memory version of fictitious play process for all players.

By virtue of Proposition 1, for player $i\in N$ , divide $M_i^c$ into $k^{(n-1)\tau}$ equal blocks as

$ \begin{align*} M_i^c=\left[Blk_1\left(M_i^c\right), Blk_2\left(M_i^c\right), \ldots, Blk_{k^{(n-1)\tau}}\left(M_i^c\right)\right]\notag \end{align*} $

where the elements in the $l$ th block of $M_i^c$ are all the possible benefits of player $i$ under other players' strategy profile $z_{-i}(t)=\delta_{k^{(n-1)\tau}}^l$ , $l=1, 2, \ldots, k^{(n-1)\tau}$ .

Next, we search for the best response of player $i$ making its benefit maximum, that is, find the column index of the largest element for each block of $M_i^c$ . For all $l=1, 2, \ldots, k^{(n-1)\tau}$ , let $\xi_{i, l}$ be the column index such that

$ 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 $\xi_{i, l}$ according to the priority of strategy choice given in Section Ⅲ-A, that is, choose the largest column index.

Letting $\tilde{L}_i=\delta_k[\xi_{i, 1}, \xi_{i, 2}, \ldots, \xi_{i, k^{(n-1)\tau}}]$ , by Lemma 1 and Lemma 5, we can obtain the algebraic form of the updating rule for player $i$ as

$ \begin{align} x_i(t+1)&=\tilde{L}_i z_{-i}(t)=\tilde{L}_i D_{r}^{k^\tau , k^{(n-1)\tau}} z_i(t) z_{-i}(t)\notag\\ &=\tilde{L}_i D_{r}^{k^\tau, k^{(n-1)\tau}} W_{[k^{\left(i-1\right)\tau}, k^\tau]}z(t)\nonumber\\ &= L_i^x z(t) \end{align} $ (15)

where $i\in{ N}$ . By virtue of Lemma 1, Lemma 5, Lemma 4, (8), and (15), we get

$ \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^{(n-1)\tau}} z_i(t) z_{-i}(t) L_i^x z(t)\notag\\ &\quad = D_{r}^{k, k} D_{f}^{k^\tau, k^{(n-1)\tau}} W_{[k^{(i-1)\tau}, k^\tau]} z(t) L_i^x z(t) \notag\\ &\quad = D_{r}^{k, k} D_{f}^{k^\tau, k^{(n-1)\tau}} W_{[k^{(i-1)\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^{(n-1)\tau}} W_{[k^{(i-1)\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 $\tau$ memories.

Algorithm 1: This algorithm contains three steps:

1) Calculate the structural matrix, $M_i$ , of the payoff function of player $i\in N$ by

$ \begin{align*} M_i=&\ M_c W_{[k]}\Big(\sum\limits_{j<i, j\in \mathcal{N}_i} D_f^{k, k^{n-2}}W_{[k^{j-1}, k]}\notag\\ &\, +\sum\limits_{j>i, j\in\mathcal{N}_i}D_f^{k, k^{n-2}}W_{[k^{j-2}, k]}\Big).\notag \end{align*} $

2) Construct the structural matrix of expected payoff function of player $i\in N$ , $M_i^c=M_i C$ , where $C$ is defined as in Proposition 1. Then, divide the matrix $M_i^c$ into $k^{(n-1)}$ equal blocks as

$ M_i^c=\left[ Blk_1\left(M_i^c\right), Blk_2\left(M_i^c\right), \ldots, Blk_{k^{(n-1)\tau}}\left(M_i^c\right)\right] $

and for all $l=1, 2, \ldots, k^{(n-1)\tau}$ , find the column index $\xi_{i, l}$ such that

$ \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 $\tau$ memories as

$ \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^{(n-1)\tau}} W_{[k^{(i-1)\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^{(n-1)\tau}} W_{[k^{\left(i-1\right)\tau}, k^\tau]}\\ &\tilde{L}_i=\delta_k[\xi_{i, 1}, \xi_{i, 2}, \ldots, \xi_{i, k^{(n-1)\tau}}]\end{align*} $

and $i\in N$ .

Remark 1: It is important to note that the initial state $z(0)\in\Delta_{k^{n\tau}}$ , which represents the strategies adopted by all players from time $-\tau+1$ to $0$ , is prior knowledge for NEGs with $\tau$ memories.

It is obvious that the matrix $L$ can reveal all the characteristics of the given NEG completely. Thus, the dynamics of the NEG with $\tau$ memories is equivalent to the algebraic form (17).

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 $L$ .

Proposition 2: Define logical variables $z = \ltimes_{i=1}^n\ltimes_{j=1}^m x_{ij}$ and $\bar{z}=\ltimes_{j=1}^m\ltimes_{i=1}^n x_{ij}$ , where $x_{ij}\in\Delta_k$ , $i=1, 2, \ldots, n$ , and $j$ $=$ $1, $ $2, $ $\ldots, $ $m$ . Then, there exists a nonsingular matrix $T_G^{n, m}$ such that

$ \begin{align} z = T_G^{n, m} \bar{z} \end{align} $ (19)

holds.

Proof: We prove it by induction. When $n=1$ and $m=1$ , it is obvious that $z=x_{11}=I_{k}\bar{z}$ , namely, $T_G^{1, 1}=I_{k}$ .

Suppose (19) is true for $n=s$ and $m=v$ , then for $n=s + 1$ and $m=v$ we have

$ \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^{(v-1)s}]}\otimes I_{k^{v-1}}\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^{(v-1)s}]}\otimes I_{k^{v-1}}\right)\notag\\ &\quad\times\left(I_{k^{2s+1}}\otimes W_{[k, k^{(v-2)s}]}\otimes I_{k^{v-2}}\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^{(v-1)s}]}\otimes I_{k^{v-1}}\right)\notag\\ &\quad\times\left(I_{k^{2s+1}}\otimes W_{[k, k^{(v-2)s}]}\otimes I_{k^{v-2}}\right)\notag\\ &\quad\times\left(I_{k^{(v-2)(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 $n=s$ and $m=v+1$ , by Lemma 2, we have

$ \begin{align} z=&\ltimes_{i=1}^{s}\ltimes_{j=1}^{v+1} x_{ij}\notag\\ =&\left(I_{k^{(s-2)(v+1)+v}}\otimes W_{[k^v, k]}\otimes I_{k}\right)\notag\\ &\times\left(I_{k^{(s-3)(v+1)+v}}\otimes W_{[k^{2v}, k]}\otimes I_{k^2}\right)\notag\\ &\times\left(I_{k^v}\otimes W_{[k^{s-1}, k]}\otimes I_{k^{s-1}}\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^{(s-2)(v+1)+v}}\otimes W_{[k^v, k]}\otimes I_{k}\right)\notag\\ &\times\left(I_{k^{(s-3)(v+1)+v}}\otimes W_{[k^{2v}, k]}\otimes I_{k^2}\right)\notag\\ &\times\left(I_{k^v}\otimes W_{[k^{s-1}, k]}\otimes I_{k^{s-1}}\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 $n=s$ , $m=v+1$ and $n$ $=$ $s+1$ , $m=v$ , (19) holds.

Remark 2: With the help of Proposition 2, (8) can be turned into (18) by a proper coordinate transformation. So, the high-order 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 $\tau$ memories, including the fixed points and cycles.

1) The number of cycles of length $s$ for the dynamics of NEGs with $\tau$ memories, denoted by $N_s$ , is inductively determined by

$ \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 $\mathcal{P}(s)$ denotes the set of proper factors of $s$ , the proper factor of $s$ is a positive integer $k <s$ satisfying $s/k \in\mathbb{ Z}_+$ , and $\mathbb{ Z}_+$ is the set of positive integers.

2) The set of elements on cycles of length $s$ , denoted by $\mathcal{C}_s$ , is

$ \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 $\mathcal{D}_a(L)$ is the set of diagonal nonzero columns of $L$ .

C. Existence and Convergence of NE for NEGs With $\tau$ Memories

In this subsection, we design a free-type strategy sequence for a pseudo-player in the given NEG to guarantee the convergence of NE. Without loss of generality, we assume that the first player is the pseudo-player who can take strategies freely. Let $x_1(t)\in \Delta_k$ be the strategy of the pseudo-player at time $t$ , and $x_i(t)\in \Delta_k$ be the strategy of the player $i\in \{2, 3, \ldots, n\}$ at time $t$ .

First of all, using (16), one has

$ \begin{align} y(t+1)=L_v v(t)y(t) \end{align} $ (26)

where $y(t)=z_2(t)\ltimes z_3(t)\ltimes\cdots\ltimes z_n(t)$ , $v(t)=z_1(t)$ , $L_v=$ $L_2 \ast L_3\ast \cdots\ast L_n$ , and $y(0)\in \Delta_{k^{(n-1)\tau}}$ . In addition to that, by Lemma 5 and (8), $v(t)$ satisfies

$ \begin{align} & D_r^{k, k^{\tau-1}} v(t-1)\notag\\ &\qquad = x_1(t-\tau+1)\ltimes x_1(t-\tau+2)\ltimes \cdots\ltimes x_1(t-1)\notag\\ &\qquad =D_f^{k^{\tau-1}, 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^{\tau-1}} v(t-1)=D_f^{k^{\tau-1}, 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 $(k, k)$ , namely,

$ \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 $(k, k)$ as the FNG's NE. There is no difficulty to generalize it to the case that the NE is not $(k, k)$ .

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 $x^*=\underbrace{(k, k, \ldots, k)}_n$ .

Proof. With (1) and (29) in hands, since the FNG under study is symmetric, for player $i$ , one has $p_{i}(x_i, x_{-i}^*)=$ $\sum_{j\in \mathcal{N}_{i}}c(x_i, k)$ $\leq\sum_{j\in \mathcal{N}_{i}}c(k, k)=p_{i}(x_i^*, x_{-i}^*)$ , $x_i\neq k$ . Thus, $x^*$ is the given NEG's NE.

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 $z_e=\delta_{k^{n\tau}}^{k^{n\tau}}$ , namely, $Col_{k^{n\tau}}(L)$ $=$ $\delta_{k^{n\tau}}^{k^{n\tau}}$ .

Proof. $z(t)=\delta_{k^{n\tau}}^{k^{ n\tau}}$ means that, for $\forall i\in{ N}$ , $z_{i}(t)=\delta_{k^{\tau}}^{k^{\tau}}$ holds. In other words, $z(t)=\delta_{k^{n\tau}}^{k^{n\tau}}$ implies that all players choose strategy $k$ from time $t-\tau+1$ to time $t$ . Thus, by (2) and (3), one has $q_i(t)=\delta_{k}^k$ , $i\in{ N}$ . Then, using (4), we obtain

$ \begin{align} U_i(x_i, q_{-i}(t))=p_i(x_i, x_{-i}^*) \end{align} $ (30)

where $x_{-i}^*=x_1^*\ltimes\cdots \ltimes x_{i-1}^* \ltimes x_{i+1}^*\ltimes\cdots\ltimes x_n^*=(\underbrace{k, k, \ldots, k}_{n-1})$ and $i\in{ N}$ . By virtue of Theorem 1 and (30), one has

$ \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 $i\in{ N}$ . Thus, by (5) and (31), one has

$ \begin{align*} x_{i}(t+1)=Col_{k^{n\tau}}\left(L_i^x\right)=\delta_{k}^k\notag \end{align*} $

where $i\in{ N}$ . Then, it is easy to see that $x_i(t+k)=\Delta_k^k$ , $k$ $>$ $1$ , and

$ \begin{align} z_i(t+1)=\Delta^{k^\tau}_{k^\tau} \end{align} $ (32)

where $i\in{ N}$ . Because of (32), we get

$ \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 $i\in{ N}$ . So, by (8) and (33), it reaches

$ \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^{(n-1)\tau}}\left(Blk_{k^\tau}\left(L_v\right)\right)=\delta_{k^{(n-1)\tau}}^{k^{(n-1)\tau}} $

holds.

Proof: From Theorem 1, substituting the fixed point $v(t)\ltimes$ $y(t)$ $=\delta_{k^{\tau n}}^{k^{\tau n}}$ into (28), we have

$ y(t+1)=\Delta_{k^{(n-1)\tau}}^{k^{(n-1)\tau}}=L_v \ltimes \delta_{k^{ n\tau}}^{k^{n\tau}}=Col_{k^{(n-1)\tau}}(Blk_{k^\tau}(L_v)). $

Finally, we study how to design a free-type 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 $x^e_1\ltimes$ $x^e_{-1}$ $=$ $\delta_{k^{n}}^{k^{ n}}$ by a free-type strategy sequence, if there exist the integers $\mu>0$ and $1\leq \alpha\leq k^\mu$ , such that

$ \begin{align} Col_j(Blk_\alpha(\bar{L}R_\mu))=\delta_{k^{(n-1)\tau}}^{k^{(n-1)\tau}}\quad \forall\ 1\leq j \leq k^{(n-1)\tau} \end{align} $ (34)

and

$ \begin{align} D_{r}^{k, k^{\tau-1}} v(\mu-1)=\Delta_{k^{\tau-1}}^{k^{\tau-1}} \end{align} $ (35)

where $\bar{L}=L_v(I_{k^\tau}\otimes L_v)\cdots(I_{k^{(\mu-1)\tau}}\otimes L_v)$ and $R_\mu=\prod_{i=1}^{\mu-1}\left( W_{[k^\tau, k^{\tau+i-1}]}\left(I_k\otimes \Psi_{\tau-1, k} \right)\right)$ .

Proof: Firstly, using Lemma 1 and (28), one has

$ \begin{align} y(\mu)&=L_v v(\mu-1)y(\mu-1)\notag\\ &=L_v v(\mu-1)L_v v(\mu-2)y(\mu-2)\notag\\ &=L_v(I_{k^\tau}\otimes L_v)v(\mu-1)v(\mu-2)y(\mu-2)\notag\\ &=L_v(I_{k^\tau}\otimes L_v)(I_{k^{2\tau}}\otimes L_v)\cdots(I_{k^{(\mu-1)\tau}}\otimes L_v)\notag\\ &\quad\times v(\mu-1)v(\mu-2)\cdots v(0)y(0)\notag\\ &=\bar{L}v(\mu-1)v(\mu-2)\cdots v(0)y(0). \end{align} $ (36)

However, (27) implies that $\{v(t)\}_{t\geq -\tau+1}$ is not a free-type sequence. Then, define $u(t)=x_1(t)$ , by Lemma 1 and Lemma 4, $v(\mu-1)\ltimes v(\mu-2)\ltimes \cdots\ltimes v(0)$ can be rewritten as

$ \begin{align}\label{3.3.29.4} &v(\mu-1)\ltimes v(\mu-2)\ltimes \cdots\ltimes v(0)\notag\\ &\quad =\ltimes_{i=\mu-\tau}^{\mu-1} u(i) \ltimes_{i=\mu-\tau-1}^{\mu-2} u(i)\ltimes\cdots\ltimes_{i=-\tau+1}^{0}u(i)\notag\\ &\quad = W_{[k^\tau]} u(\mu-\tau-1)\left(\ltimes_{i=\mu-\tau}^{\mu-2}u(i)\right)^2 u(\mu-1)\notag\\ &\qquad\times \ltimes_{i=\mu-\tau-2}^{\mu-3}u(i)\ltimes\cdots\ltimes_{i=-\tau+1}^{0}u(i) \notag\\ &\quad =W_{[k^\tau]}\left(I_k\otimes \Psi_{\tau-1, k} \right)\ltimes_{i=\mu-\tau-1}^{\mu-1}u(i) \notag\\ &\qquad \times\ltimes_{i=\mu-\tau-2}^{\mu-3}u(i)\ltimes\cdots\ltimes_{i=-\tau+1}^{0}u(i)\notag\\ &\quad =W_{[k^\tau]}\left(I_k\otimes \Psi_{\tau-1, k} \right) W_{[k^\tau, k^{\tau+1}]}\left(I_k\otimes \Psi_{\tau-1, k} \right)\notag\\ &\qquad \times\ltimes_{i=\mu-\tau-2}^{\mu-1}u(i) \ltimes_{i=\mu-\tau-3}^{\mu-4}u(i)\ltimes\cdots\ltimes_{i=-\tau+1}^{0}u(i) \notag\\ &\quad =\prod\limits_{i=1}^{\mu-1}\left( W_{[k^\tau, k^{\tau+i-1}]}\left(I_k\otimes \Psi_{\tau-1, k} \right)\right)\left(\ltimes_{i=-\tau+1}^{\mu-1}u(i)\right)\notag\\ &\quad = R_{\mu}\left(\ltimes_{i=-\tau+1}^{\mu-1}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}^{\mu-1}u(i)\right)y(0). \end{align} $ (38)

Because of (34), (41), and (38), for $\forall y(0)\in\Delta_{k^{(n-1)\tau}}$ , we have

$ \begin{align} y(\mu)&=Blk_{\alpha}(\bar{L}R_\mu)y(0)\notag\\ &=\delta_{(n-1)\tau}[(n-1)\tau, (n-1)\tau, \ldots, (n-1)\tau]y(0)\notag\\ &=\Delta_{k^{(n-1)\tau}}^{k^{(n-1)\tau}}. \end{align} $ (39)

By(35), (41) and the definition of $v(t)$ , one has

$ \begin{align} v(t)=v(\mu)=D_{r}^{k, k^{\tau-1}} v(\mu-1)\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 $\forall y(0)\in\Delta_{k^{(n-1)\tau}}$ ,

$ \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^{(n-1)\tau}}(Blk_{k^\tau}(L_v))\notag\\ &=\Delta_{k^{(n-1)\tau}}^{k^{(n-1)\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 $v(t)$ and $y(t)$ , it is easy to prove that the evolutionary process of the game globally converges to the NE $x^e_1\ltimes x^e_{-1}=\delta_{k^{n}}^{k^{ n}}$ . In addition to that, by Lemma 3, we get the free-type strategy sequence (41).

From the proof of Theorem 3, one can easily design a free-type strategy sequence for player $1$ as follows.

Corollary 2: Consider the NEG with the algebraic form (28), and assume that Assumption 1 holds. If there exist integers $\mu>0$ and $1\leq \alpha\leq k^\mu$ , such that (34) and (35) hold, then the free-type strategy sequence which the pseudo-player adopts can be designed as

$ \begin{align} x_1(t) =\begin{cases} \widetilde{u}(t), &-\tau+1 \leq t \leq \mu-1\\[2mm] \Delta_k^k, &t\geq \mu \end{cases} \end{align} $ (41)

where $\ltimes_{i=-\tau+1}^{\mu-1}\widetilde{u}(i)=\delta_{k^{\tau}}^{\alpha}$ .

Ⅳ. AN ILLUSTRATIVE EXAMPLE

In this section, we give an illustrative example to show how to use our results to investigate networked evolutionary games with $\tau$ memories.

Example 1: Consider an NEG with the following basic factors:

1) A network topological structure, denoted by $(N, \mathcal{E})$ , as in Fig. 1, where $N=\{1, 2, 3\}$ , and $\mathcal{E}=\{(1, 2), (1, 3), (2, 3)\}$ ;

Download:
Fig. 1 The network.

2) The FNG's payoff bi-matrix shown in Table Ⅰ;

Table Ⅰ
PAYOFF BI-MATRIX

3) The evolutionary rule is $\tau$ -version of FP process depicted in Section Ⅲ-A, where $\tau=2$ .

With the help of Algorithm 1, the algebraic form of the game is given as $z(t+1)=L z(t)$ , where

$ \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 $\delta_{64}^{1}$ and $\delta_{64}^{64}$ , that is, all players adopt the same strategy $M$ or $F$ ; 2) two cycles with length 3 are $\{\delta_{64}^{7}, $ $\delta_{64}^{25}, $ $\delta_{64}^{34}\}$ and $\{\delta_{64}^{10}, \ \delta_{64}^{19}, \ \delta_{64}^{37}\}$ , namely, the strategy profile sequences $(\{M, F, M\}$ , $\{M, M, F\}$ , $\{F, M, M\})$ and $(\{M, $ $M, F\}$ , $\{F, M, M\}$ , $\{M, F, M\})$ are two cycles adopted by the three players; 3) $N_s=0$ , $s=2$ and $4\leq s\leq 64$ .

The rest of this section studies the strategy sequence design of the given NEG. Using Algorithm 1 and considering player 1 as a pseudo-player, we have $y(t+1)=L_v v(t)y(t)$ , where

$ \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 $\{F, F, F\}$ by the strategy sequence $\{u(t)$ $=$ $\delta_2^2\}_{t\geq -\tau+1}$ , that is, player 1 adopts the strategy sequence $\{x_1(t)=F\}_{t\geq -\tau+1}$ . Fig. 2 demonstrates the effectiveness of the free-type strategy sequence, when we pick up $x_2(-1)=$ $F$ , $x_2(0)=M$ , $x_3(-1)=M$ , and $x_3(0)=F$ as initial states for the given NEG.

Download:
Fig. 2 The responses strategy sequence of three players of the NEG under the given free-type strategy sequence.
Ⅴ. CONCLUSION

In this paper, we have investigated the modeling and analysis for a class of networked evolutionary games with finite memories based on $\tau$ -memory version of fictitious play process. The dynamics of the given NEG has been converted into an algebraic form via the semi-tensor product. A proper algorithm has been established to construct its corresponding structural matrices. A free-type strategy sequence has been designed to guarantee the NE reachable globally. The study of an illustrating example has shown that the new results presented in this paper are very effective. It is worth noting that this paper considers NEGs with $\tau$ memories as discrete-time games. We can study NEGs with $\tau$ memories as differential games in the further research just like in [19].

REFERENCES
[1] R. Axelrod and W. D. Hamilton, "The evolution of cooperation, " Science, vol. 211, no. 4489, pp. 1390-1396, Mar. 1981.
[2] M. A. Nowak and R. M. May, "The spatial dilemmas of evolution, " Int. J. Bifurcat. Chaos, vol. 3, no. 1, pp. 35-78, 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. 69-73, Jul. 1998. http://arxiv.org/abs/cond-mat/9710096
[4] R. Sugden, The Economics of Rights, Co-operation 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. 826-829, 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, "Semi-tensor product approach to networked evolutionary games, " Control Theory Technol., vol. 12, no. 2, pp. 198-214, May 2014. https://link.springer.com/article/10.1007/s11768-014-0038-9
[8] D. Z. Cheng, H. S. Qi, and Z. Q. Li, Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach. London, UK: Springer, 2011.
[9] D. Z. Cheng, H. S. Qi, and Y. Zhao, "Analysis and control of Boolean networks: a semi-tensor product approach, " Acta Autom. Sinica, vol. 37, no. 5, pp. 529-540, May 2011. http://en.cnki.com.cn/Article_en/CJFDTotal-MOTO201105004.htm
[10] D. Z. Cheng, "On finite potential games, " Automatica, vol. 50, no. 7, pp. 1793-1801, 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. 1335-1345, 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 semi-tensor product method, " Automatica, vol. 49, no. 11, pp. 3384-3389, 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. 2402-2415, Sep. 2015. http://ieeexplore.ieee.org/document/7042754/
[14] H. T. Li, Y. Z. Wang, and Z. B. Liu, "A semi-tensor product approach to pseudo-Boolean functions with application to Boolean control networks, " Asian J. Control, vol. 16, no. 4, pp. 1073-1081, Jul. 2014, doi: 10.1002/asjc.767. https://www.researchgate.net/publication/264162475_A_Semi-Tensor_Product_Approach_to_Pseudo-Boolean_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. 1766-1776, Aug. 2011.
[16] Y. F. Mu and L. Guo, Optimization and identification in a non-equilibrium dynamic game. In Proc. 48th IEEE Conf. Decision and Control, Held Jointly with 28th Chinese Control Conf., Shanghai, China, 2009, pp. 5750-5755.
[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. 390-399, Apr. 2013. http://www.sciencedirect.com/science/article/pii/S1874102913600385