Finding the Nash equilibria of $n$-person noncooperative games via solving the system of equations

1.   Introduction

Game theory is a mathematical theory that studies interactions between decision makers. The $n$-person noncooperative game is an important part of game theory ^[1,2,3]. As we all know, Von Neumann ^[4] and Nash ^[5,6] established the models of matrix games and $n$-person finite noncooperative games respectively, and Nash proposed the core equilibrium concept in noncooperative games, called Nash equilibrium, and proved that this kind game has at least one mixed strategies equilibrium point. At present, the $n$-person noncooperative game and its related researches have been widely used in mathematics, economics, operations research, biology, textile industry and other fields ^{[7,8,9,10,11]}. In these researches and applications, the key point is how to find Nash equilibrium points effectively, which largely depends on the good mathematical description of the problem. Therefore, it is very important to find a suitable mathematical model when solving games.

At present, there are many mathematical methods to solve the Nash equilibria, mainly by equating finding Nash equilibria to a fixed point problem, an optimization problem or a tensor complementarity problem. The finding Nash equilibria is equivalent to the fixed point problem, which is mainly handled by the Brouwer fixed point theorem, the Kakutani fixed point theorem and the KyFan point theorem. Many scholars have made a lot of researches in this field ^{[12,13,14,15]}. Furthermore, the research that finding Nash equilibria is equivalent to the optimization problem is springing up. Because the equilibrium points are natural actions of self interested behavior in competitive situations. In other words, at an equilibrium point, each competitor is maximizing his payoff against all other competitive actions in the situation. Therefore, finding a Nash equilibrium is generally as a nonconvex optimization problem, which has been sufficiently studied in ^{[16,17,18,19,20]}. Further, some scholars also have equated the finding Nash equilibria to the tensor complementarity problem ^{[21,22,23,24]}, and the player's payoff function is given by a homogeneous polynomial defined by this player's payoff tensor. In addition to the above usual methods for finding Nash equilibria, in recent years, with the extensive research of multi-agent systems in social science and engineering systems, using distributed algorithms seeking Nash equilibria has become an emerging research topic. This method provides solutions for complex engineering games^{[25,26,27,28,29,30,31]}, such as generalized games with coupled constraints, aggregative games with non-smooth objective functions and uncertain games, etc.

Although the above research methods and calculation methods have solved a large number of games. With the complexity of real problems and the diversification of games, the above methods have some disadvantages in the computing process, such as high computational complexity, cumbersome derivation process and complex algorithm design. Therefore, we propose a new equivalent method of finding Nash equilibria in this paper, which directly applies the definition of Nash equilibrium to establish an equivalent relationship with the system of equations, and transform the problem of finding the Nash equilibria into solving the system of equations. So that it can be calculated using the developed method of solving the system of equations. Therefore, compared with finding the Nash equilibria equivalent to the fixed point problem and nonconvex optimization problem, the proposed method does not need to define complex set valued mapping, no have tedious theoretical derivation and proof. Compared with find the Nash equilibria equivalent to the tensor complementarity problem, the proposed method does not need to consider the nonlinear complementarity and nonsmooth of the payoff function. This method provides a new idea for find the Nash equilibria, which can be easily understood and applied by readers with weak mathematical foundation. On the one hand, this method broadens the expression form of Nash equilibria and provides a new method for finding Nash equilibria. It reduces the difficulty of seeking Nash equilibria, and only needs to consider the calculation methods of the equivalent equations. On the other hand, this equivalent method also has certain significance for the realization of Nash equilibrium: since the equations are derived from the definition of Nash equilibrium, each equation essentially represents the rational behavior of the player. In each equation, the probability of each component of the Nash equilibrium is greater than 0 is meaning that the corresponding pure strategy is in the direction of increasing the profit, that is, the direction of Nash equilibrium realization. Therefore, this method has certain research significance.

This paper is organized as follows: In Section 2, we give the basic definitions of the game and an equivalence theorem between the Nash equilibria of $n$-person noncooperative game and the solutions of equations. In Section 3, we propose the ADECA algorithm and prove its convergence theoretically through the finite state Markov chain. This algorithm applies the DE algorithm to the population space of the CA algorithm, and uses the belief space of the CA to extract hidden evolutionary knowledge and guides the evolution of the population space. Additionally, the DE algorithm is adaptively improved to enhance the performance of the ADECA algorithm. The equivalence theorem of the Nash equilibria and the superiority of the ADECA algorithm proposed in this paper are verified by examples in Section 4.

2.   The basic definitions and equivalence theorem of $n$-person noncooperative game

2.1.   The $n$-person noncooperative game

Definition 2.1. ^[32] We consider a $n$-person noncooperative game $\Gamma = \{(N, S^{i}, P^{i}, X^{i}, U^{i}), i = 1, \ldots, n\}$

where

(1) $N = \{1, \ldots, n\}$ is the set of players and $n$ is the number of players;

(2) $S^{i} = \{s_{1}^i, \ldots, s_{m_{i}}^i\}, \; \forall i\in N$ is the pure strategy set of player $i$, $m_{i}$ represents the number of strategies available to player $i$, $S = \prod_{i = 1}^nS^{i}$;

(3) $P^{i}:S\rightarrow \mathbb{R}, \; \forall i\in N$ represents the payoff function of player $i$;

(4) $X^{i} = \{x^{i} = (x_{1}^i, \ldots, x_{\mathscr{K}}^i, \ldots, x_{m_{i}}^i):x_{\mathscr{K}}^i\geq0, \sum_{\mathscr{K} = 1}^{m_{i}}x_{\mathscr{K}}^i = 1\}, \ \forall i\in N$ is the set of mixed strategies. $X = \prod_{i = 1}^nX^{i}$, and each mixed strategy profile meets $x = (x^{1}, x^{2}, \ldots, x^{n})\in X$;

(5) $U^{i}:X\rightarrow \mathbb{R}, \; \forall i\in N$ represents the expected payoff function of player $i$.

where $u_{i}(x)$ represents the expected payoff value of player $i$ when he chooses a mixed strategy $x^{i} = (x_{1}^i, \ldots, x_{m_{i}}^i)\in X^{i}$. $p_{i}(s_{\mathscr{K}_{i}}^i, \ldots, s_{\mathscr{K}_{n}}^n)$ represents the payoff value of player $i$ when each player chooses pure strategy $s_{\mathscr{K}_{i}}^i\in S^{i}, i = 1, \ldots, n$.

Denote by

where $s_{\mathscr{K}_{i}}^i(1\leq \mathscr{K}_{i}\leq m_{i})$ is pure strategy of player $i$. $(x\|s_{\mathscr{K}_{i}}^i)$ represents $s_{\mathscr{K}_{i}}^i$ instead of $x^i$ of player $i$, and the other players do not change their own mixed strategy.

Definition 2.2. If $x^{\ast} = (x_{1}^{\ast}, \ldots, x_{n}^{\ast})$, such that $u_{i}(x_{i}^{\ast}, x_{i^{\wedge}}^{\ast}) = \max\limits_{y^i\in X^i}u_{i}(y^{i}, x_{i^{\wedge}}^{\ast}), \; \forall i\in N$, then $x^{\ast}$ is a Nash equilibrium point of $n$-person noncooperative game, where $i^{\wedge} = N\backslash \{i\}, \ \forall i\in N$.

Conclusion 2.1. ^[20] Mixed strategy $x^{\ast} = (x_1^{\ast}, \ldots, x_n^{\ast})\in X$ is a Nash equilibrium point of a game $\Gamma$ if and only if $u_{i}(x^{\ast}) \geq u_{i}(x^{\ast}\| s_{\mathscr{K}_{i}}^i)$, where, $\mathscr{K}_i = m_1, \ldots, m_n, i = 1, \ldots, n$.

2.2.   Equivalence theorem of the Nash equilibria and solutions of the system of equations

Theorem 2.1. For any $n$-person finite noncooperative game, the mixed strategy profile,

is a Nash equilibrium if and only if there is a set of real numbers

such that $\lambda_{\mathscr{\mathfrak{E}}_i \mathscr{K}_i}^{i}$ and $x = \left(x^{1}, x^{2}, \ldots, x^{n}\right)$ satisfy the following equations:

Proof. Necessity: Assume that $x = \left(x^{1}, x^{2}, \ldots, x^{n}\right)\in X, x^{i} = \left(x_{1}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{i}}^{i}, \ldots, x_{m_{i}}^{i}\right), \forall i \in N$ is a Nash equilibrium. Then the expected payoff of player $i$ under this equilibrium is

if $x_{\mathscr{\mathfrak{E}}_{h_{1}}}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{h_{l}}}^{i} > 0, x_{\mathscr{\mathfrak{E}}_{h_{l+1}}}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{h_{m_i}}}^{i} = 0$, then for each $\mathscr{\mathfrak{E}}_i \in\{\mathscr{\mathfrak{E}}_{h_1}, \ldots, \mathscr{\mathfrak{E}}_{h_l}\}$, $\mathscr{K}_i \in\{1, \ldots, m_i\}$, and $\mathscr{K}_i\neq \mathscr{\mathfrak{E}}_i$, we have

(Contradiction): Assuming that the above formula (2.3) does not hold, then there is a certain $\mathscr{\mathfrak{E}}_i \in\{\mathscr{\mathfrak{E}}_{h_1}, \ldots, \mathscr{\mathfrak{E}}_{h_l}\}$, $\mathscr{K}_i\neq \mathscr{\mathfrak{E}}_i$, where $\mathscr{K}_i \in\{1, \ldots, m_i\}$, such that

For the convenience of writing, let $\mathscr{\mathfrak{E}}_i = 1$, $\mathscr{K}_i = 2$, that is,

Taking $y = \left(x^{1}, \ldots, x^{i-1}, y^{i}, x^{i+1}, \ldots, x^{n}\right), y^{i} = \left(0, x_{1}^{i}+x_{2}^{i}, x_{3}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{i}}^{i}, \ldots, x_{m_{i}}^{i}\right)$, and combining inequality (2.4) with the formula (2.2), we obtain

it contradicts that $x$ is a Nash equilibrium. So we get that for each Nash equilibrium $x_{\mathscr{\mathfrak{E}}_i}^i > 0$, and $\forall \mathscr{K}_i\in\{1, \ldots, m_i\}$,

In particular, if $\mathscr{\mathfrak{E}}_i, \mathscr{K}_i \in \{\mathscr{\mathfrak{E}}_{h_1}, \ldots, \mathscr{\mathfrak{E}}_{h_l}\}$, $x_{\mathscr{\mathfrak{E}}_i}^{i}, x_{\mathscr{K}_i}^{i} > 0$, then

The following proof shows that the Nash equilibrium $x = \left(x^{1}, x^{2}, \ldots, x^{n}\right)\in X$ satisfies the system of equations in Theorem 2.1.

(ⅰ) For every $i\in N$, if $x_{\mathscr{\mathfrak{E}}_i}^i = 0$, then for each $\mathscr{K}_i\in\{1, \ldots, m_i\}, \mathscr{K}_i\neq \mathscr{\mathfrak{E}}_i$, and take $\lambda_{\mathscr{\mathfrak{E}}_i\mathscr{K}_i}^i = 0$, we have

(ⅱ) If $x_{\mathscr{\mathfrak{E}}_i}^i > 0$, then for each $\mathscr{K}_i\in\{1, \ldots, m_i\}, \mathscr{K}_i\neq \mathscr{\mathfrak{E}}_i$, that is formula (2.3),

(ⅱ-1) If the equality sign of formula (2.6) holds, take $\lambda_{\mathscr{\mathfrak{E}}_i\mathscr{K}_i}^i = 0$, then formula (2.5) holds.

(ⅱ-2) If the equality sign of formula (2.6) does not hold, that is

then take

therefore

The necessity has been proved. Next, we show the sufficiency of Theorem 2.1.

Sufficiency: If there is a set of real numbers $\lambda_{\mathscr{\mathfrak{E}}_{i} \mathscr{K}_{i}}^{i} \geq 0, i = 1, 2, \ldots, n, \mathscr{\mathfrak{E}}_{i} \neq \mathscr{K}_{i}, \mathscr{\mathfrak{E}}_{i}, \mathscr{K}_{i} \in\left\{1, 2, \ldots, m_{i}\right\}$ and mixed strategy profile $x = \left(x^{1}, x^{2}, \ldots, x^{n}\right)\in X, x^{i} = \left(x_{1}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{i}}^{i}, \ldots, x_{m_{i}}^{i}\right), i \in N$, satisfying the system of equations in Theorem 2.1, The following proof shows that $x$ is a Nash equilibrium. Let $x^{i} = \left(x_{1}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{i_k}}^{i}, x_{\mathscr{\mathfrak{E}}_{i_{k+1}}}^{i}, \ldots, x_{m_{i}}^{i}\right)$, where $x_{1}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{i_k}}^{i} > 0, x_{\mathscr{\mathfrak{E}}_{i_{k+1}}}^{i}, \ldots, x_{m_{i}}^{i} = 0$. Since $x$ satisfies the system of equations in Theorem 2.1, then for any $\mathscr{\mathfrak{E}}_i\in\{1, \ldots, \mathscr{\mathfrak{E}}_{i_k}\}$, we get

Because $x_{1}^{i}, \ldots, x_{\mathscr{\mathfrak{E}}_{i_{k}}}^{i} > 0$, for $\forall \mathscr{K}_i\in\{1, 2, \ldots, m_i\}$, we have

and because for any player $i$, the expected payoff for pure strategy is

therefore

Judging by Conclusion 2.1 that $x = (x^1, x^2, \ldots, x^n)$ is a Nash equilibrium.

2.3.   Solving the Nash equilibria of bimatrix game based on the system of equations

According to the preparatory knowledge of $n$-person finite noncooperative game and Theorem 2.1, we can get the equivalence theorem of the bimatrix game.

Corollary 2.1. Suppose the mixed strategy of the two-player finite noncooperative game is $x = (x^1, x^2)$, where $x^1 = (x^1_1, x^1_2, \ldots, x^1_{m_1}), x^1 = (x^2_1, x^2_2, \ldots, x^2_{m_2})$, and $\sum_{i = 1}^{m_1}x^1_{i} = 1$, $\sum_{i = 1}^{m_2}x^2_{i} = 1$. The payoff matrices are $A$ and $B$ respectively:

then, $x$ is a Nash equilibrium if and only if there is a set of real numbers $\lambda_{\mathscr{\mathfrak{E}}_i \mathscr{K}_i}^{i} \geq 0, i = 1, 2, \mathscr{\mathfrak{E}}_{i} \neq \mathscr{K}_{i}, \mathscr{\mathfrak{E}}_{i}, \mathscr{K}_{i} \in\left\{1, 2, \ldots, m_{i}\right\}$, such that $\lambda_{\mathscr{\mathfrak{E}}_i \mathscr{K}_i}^{i}$ and $x = (x^{1}, x^{2})$ satisfy the following equations:

where $A_{\mathscr{K}_t}(t = 1, 2)$ is the $\mathscr{K}_t$th row of matrix $A$, $B_{\mathscr{\mathfrak{E}}_t}(t = 1, 2)$ is the $\mathscr{\mathfrak{E}}_t$th column of matrix $B$, $x^1 = (x^1_1, \ldots, x^1_{m_1}), x^2 = (x^2_1, \ldots, x^2_{m_2})$, and $\mathscr{K}_1\neq \mathscr{K}_2 \in\{1, \ldots, m_1\}, \mathscr{\mathfrak{E}}_1\neq \mathfrak{E}_2 \in\{1, \ldots, m_2\}$.

For the convenience of writing, formula (2.1) can be simplified as:

where $m = \sum_{i = 1}^nm_i(m_i-1)$, $\mathscr{K} = \sum_{i = 1}^nm_i$, $\lambda_i\geq 0, i = 1, 2, \ldots, m$, and $0\leq x_i\leq1, i = 1, 2, \ldots, \mathscr{K}$, $\sum_{i = 1}^{m_1}x_i = 1, \sum_{i = m_1+1}^{m_1+m_2}x_i = 1, \ldots, \sum_{i = m_{n-1}+1}^{m_{n-1}+m_n}x_i = 1$.

According to the equivalent methods of solving the equations, the solution of the Eq (2.8) is usually equivalent to the following optimization problem, and the optimal value is 0:

An algorithm for finding the Nash equilibria based on the system of equations is given below.

3.   Adaptive differential evolution algorithm based on cultural algorithm (ADECA)

3.1.   The cultural algorithm

In 1994, Reynolds ^[33] simulated the evolution of human society and proposed a bionic intelligent computing method with a bilevel evolutionary mechanism, cultural algorithm (CA). This algorithm is composed of independently evolved population space and belief space. The population space simulates the evolution process of individuals according to certain behavioral criteria from the microscopic perspective, while the belief space simulates the evolution process of culture formation, transmission and comparison from the macroscopic perspective. Population space and belief space are two relatively independent evolutionary processes, and the two spaces are connected according to special protocols (acceptance function and influence function). Those interactions are depicted in Figure 1.

The population space is used to implement any population evolutionary algorithm. On the one hand, it evaluates the fitness value of individuals, and implements evolutionary operations such as selection, crossover and mutation for population; On the other hand, excellent individuals are provided to the belief space as samples. The belief space selects the sample individuals from the evaluated populations in the population space through the acceptance function. Under the function of knowledge updating, the hidden information carried by the sample individuals is processed and summarized, described and stored in the form of knowledge. Finally, all kinds of knowledge react on the population space through the influence function to guide the evolution of the population space, so as to accelerate the evolutionary convergence and improve the adaptability of the algorithm. The details on the interaction and influence between belief space and population space will be given below. (The following discussions are based on the assumption of solving the minimum optimization problem).

3.2.   The population space

The CA algorithm provides a computational model of a multi evolutionary processes. Therefore, from the perspective of computational model, an evolutionary algorithm that meets the requirements of CA algorithm can be regarded as an evolutionary process of population space. In this paper, the proposed algorithm uses DE algorithm with simple operation in the population space of CA algorithm.

3.2.1.   Basic DE algorithm

The DE algorithm is a new simple and robust evolutionary algorithm. It is first introduced by Storm and Price ^[34]. There are three main operations: mutation, crossover and selection operation.

(1) Mutation

The mutation operation is mainly executed to distinguish DE from other evolutionary algorithms. The mutation individual $V = (v_{i1}, \ldots, v_{ij}, \ldots, v_{iD}), i = 1, \ldots, N, j = 1, \ldots, D$ is generated by the following equation:

where $N$ and $D$ denote population size and space dimension respectively, $r1$, $r2$ and $r3$ are randomly generated integers within $[1, N]$, and $r1\neq r2\neq r3\neq i$, $F$ is a constriction factor to control the size of difference of two individuals and $t$ is the current generation.

(2) Crossover

We use the crossover between the parent and offspring with the given probability for generating new individual $U = (u_{i1}, \ldots, u_{ij}, \ldots, u_{iD})$:

where $rand(j)\in [0, 1]$ is random values, $CR\in [0, 1]$ is crossover operator, $rnbr(i)$ is a randomly selected integer on $[1, D]$, which ensure that a new individual gets at least one component value from the mutation vector.

(3) Selection

The offspring $X_{ij}^{t+1}$ is generated by selecting the individual and parent according to the following formula:

where $f(\cdot)$ is the fitness function.

Although the DE algorithm is widely used in optimization problems, with the increase of the complexity of solving problems, the DE algorithm also has some disadvantages, such as slow convergence, low accuracy and weak stability. Therefore, in order to better apply to CA algorithm, the DE algorithm is improved.

3.2.2.   Adaptive differential evolution (ADE) algorithm

Many scholars have verified that the performance of the DE algorithm mainly depends on the selection of mutation operation and related parameters. Furthermore, the mutation factor $F$ and crossover operator $CR$ directly affect the searching capability and solving efficiency of the DE algorithm ^[35]. According to formula (3.1), the mutation factor $F$ is used to control the influence of the difference vector on the mutation individual $v_i$. When $F$ is large, the difference vector $(x_{r2}-x_{r3})$ has a great influence on $v_i$ and causes a large disturbance, which is beneficial for maintaining population diversity and global search of the algorithm, but at the same time it will reduce the convergence speed; On the contrary, when $F$ is small, the disturbance is small, that is, the diversity of the population is small, which is conducive to local search of the algorithm and makes the convergence speed faster. However, the algorithm is easy to fall into the local optimal and the "premature". According to formula (3.2), when $CR$ is larger, the more contribution $v_i$ makes to $u_i$, which is beneficial to expanding new spaces and accelerating the convergence of the algorithm. However, in the later period, the mutation individuals tend to be the same, which is detrimental for maintaining population diversity, making the algorithm prone to "premature" phenomenon; Conversely, $CR$ is smaller, the more contribution $x_i$ makes, which is beneficial for maintaining population diversity. However, in this way, the ability of the algorithm to explore new spaces is weakened, and the convergence speed is relatively slow.

In order to make the algorithm have better global search capability and convergence speed, adaptive mutation and crossover operator are adopted:

where $t$ is the current iterate time, $T$ is the maximum number of iteration, $F_0$ and $CR_0$ respectively are the initial mutation factor and crossover operator. The adaptive mutation factor and crossover operator are proposed, which can adaptively determine the mutation rate and crossover rate according to the search progress of the algorithm. According to formula (3.4), since $t\in [1, T]$, then $\lambda\in [e^{1-T}, 1]\in (0, 1]$, so, $F = F_0\cdot 2^\lambda\in (F_0, 2F_0]$, that is, $2F_0$ is taken when $t = 1$, which has a larger value to avoid the algorithm "premature"; With the progress of the algorithm, the value of $F$ gradually decreases, until later close to $F_0$, which retains good information, avoids the destruction of the optimal solution, and increases the possibility of searching for the global optimal solution. The $CR = CR_0\cdot 2^\lambda\in (CR_0, 2CR_0]$ is similar: $CR$ has a large value in the early stage, which increases the exploration ability of the algorithm and avoids the algorithm falling into local optimal. In the later stage, the crossover rate is gradually reduced to retain good individuals. Therefore, the probability of finding the global optimal solution is increased.

There are two main ways of traditional mutation operations in the DE algorithm ^[36]:

where $x_{best}^{t}$ represents the best individual in the current generation, that is, the optimal position searched by this individual so far. The first mutation method has a strong global search capability but slow convergence speed. The second method has a fast convergence speed, but it is easy to fall into local optimum values. In order to overcome these shortcomings, a new mutation operation is proposed,

In the population space of this paper, in order to jump out of the local optimum and accelerate the convergence of the algorithm. Formulas (3.4) and (3.5) will be used to improve the DE algorithm.

3.3.   The belief space

Belief space adopts the $\langle S, N\rangle$ structure proposed in the literature ^[33]. Where $S = \{s^t_1, s^t_2, \ldots, s^t_i, \ldots, s^t_m\}$ is the set of optimal individuals, $s^t_i$ represents the $i$th optimal individual in the $t$th generation, and $m$ represents the size of the set. $N = \langle X_1, X_2, \ldots, X_j, \ldots, X_n\rangle$ is the normative knowledge, representing the feasible search area of the problems, where $X_j = \langle I_j, L_j, U_j\rangle$ and $n$ is the number of variables. $I_j = [l_j, u_j] = \{x|\; l_j\leq x_j\leq u_j\}$, $l_j$ and $u_j$ respectively are the upper and lower bound of variable $x_j$; $L_j$ represents the fitness value corresponding to the variable $l_j$; $U_j$ represents the fitness value of the variable $u_j$.

In order to simplify the operation process of the algorithm, only the current optimal individual $s^t$ is used to update the $S$ in belief space, and update it according to the following formula:

where $x_{best}^t$ is the optimal individual of the $t$th generation.

With the process of evolution, the search space gradually gathers in the dominant region. Therefore, when the individuals exceed the current search space, the normative knowledge $N$ is updated according to the following formula:

Formulas (3.7) and (3.9) are the updating process of upper and lower bound of variable $x_j$, formulas (3.8) and (3.10) are the updating process of fitness value of corresponding variable $x_j$.

3.4.   Acceptance function and influence function

Acceptance function and influence function are the links between belief space and population space. The acceptance function selects better individuals from the population space and submits them to the belief space for knowledge updating, and the core of its research is to select better individuals. In the early stage of evolution, the better individuals have more valuable information, so more individuals can be selected for the belief space. In the later period of evolution, the algorithm gradually converges, and the dominant individuals and their implied information are similar. In order to maintain the diversity of knowledge, the number of accepting individuals should be reduced. Therefore, the dynamic acceptance function proposed by Saleem ^[37] is used, the number of accepted individuals decreases while the number of generations increases. We get the number of accepted individuals with the following expression:

where $N$ is the population size, $t$ is the current iterate moment, in this paper, we take $P\% = 20\%$, and the number of an interval to execute the accept function is usually preset (according to the maximum number of iterations, we take the number of the interval as 5).

The main purpose of the influence function is to guide the population evolution by using knowledge of the belief space. According to the ADE model (Formula (3.5), (3.2), (3.3)), if the parent individuals are within the interval given by the normative knowledge, the particles will be updated according to the ADE algorithm. If it is outside the given interval, the offspring generation rule (formula (3.3)) becomes the following form:

3.5.   The ADECA algorithm design and experimental processes

The pseudo code of the ADECA algorithm is shown in Algorithm 1, and the specific implementation processes are described in detail as follows:

Step 1. Set the parameters of the ADECA algorithm, such as $N$, $D$, $CR_0$, $F_0$, $l$, $u$, $P$, $T$ and accuracy $\varepsilon$.

Step 2. Initializing population space and belief space. Randomly generate $N$ initial individuals $P(0)$ in population space, and each individual satisfies $\sum_{\mathscr{K}_{i} = 1}^{m_{i}}x_{\mathscr{K}_{i}}^i = 1, x_{\mathscr{K}_{i}}^i\geq0, x_{\mathscr{K}_{i}}^i\in X^{i}, i = 1, \ldots, N; \mathscr{K}_{i} = 1, \ldots, m_{i}$. The search range defined by the corresponding normative knowledge in the belief space and as the whole search space.

Step 3. Using the acceptance function (formula (3.11)) to accept better individuals and update the belief space.

Step 4. Calculating the fitness function value $f(\cdot)$ of each individual in population $P(t)$ and determining the $x_{pbest}^{t}$.

Step 5. The next generation population $P(t+1)$ is generated by mutation operation (formula (3.5)), crossover operation (formula (3.2)), selection operation (formula (3.3)).

Step 6. Updating the normative knowledge of belief space by formulas (3.7), (3.8), (3.9), (3.10).

Step 7. Determining whether to end according to the accuracy and the maximum number of iteration, and output the optimal value, otherwise, turn to step 3.

3.6.   Convergence analysis of the ADECA algorithm

As a random optimization algorithm based on population, the evolution process of the adaptive differential evolution algorithm in the population space can be described by a random process. For the convenience of discussion, considering mutation and crossover operations as a difference operator (DO), the selection operation is regarded as a selection operator (SO). The following uses the finite state Markov chain to analyze the search process of the ADECA algorithm, and use the axiomatic model ^[38] to study the probability distribution of the adaptive difference population in the decision space. Then, it is proved that the ADECA algorithm weakly converges to the global optimal solution in probability.

Definition 3.1. The DO operation randomly selects three different individuals from the population to execute formula (3.5) to generate the mutation vector $V$, and then performs crossover operation with the original target individual $X$ according to formula (3.2) to generate the middle vector $U$. This process can be regarded as a random mapping $\psi_D:\Omega \times S\rightarrow S^2$, that is

where $\Omega$ is a nonempty abstract set, its element $\omega$ is a basic event and the $S$ is the solution space.

Definition 3.2. The SO operation is a process of selecting the individual with better fitness from the middle vector $U_i$ and the target vector $X_i$ according to the greedy selection method, which is recorded as a mapping $\psi_S:S^2\rightarrow S$,

According to the above two definitions, one iteration of ADECA's population space can be seen as a mapping $\psi = (\psi_S\circ \psi_D):\Omega \times S\rightarrow S$.

Definition 3.3. ^[39] Let $X = (X_n, n = 0, 1, 2, \cdots)$ is a random process, and its state space $S$ is a finite set. If $X$ has Markov property defined by the following formula, that is, for any $n\geq 0$ and any state $i_0, i_1, \cdots, i_{n+1}\in S$, and $P\{X_0 = i_0, X_1 = i_1, \cdots, X_n = i_n\} > 0$, if

is established, $X$ is called finite Markov chain.

Here, $S$ represents the range of random variables $X_n, n = 0, 1, 2, \cdots$, that is, the set of all possible values. According to the above definition, the finite Markov chain is expressed as: in a finite state, the state of the next moment is only related to the state of the current moment.

In the ADECA algorithm, $X$ is the population space, $S$ is the solution space, $X_i$ and $X_j$ are the $i$th and $j$th generation of evolutionary individuals, respectively. Knowledge-guided differential operation and selection operation can be regarded as a random transformation from state $X_{i}\in S$ to state $X_{j}\in S$. In the process of state transition, state $X(t + 1)$ is only related to state $X(t)$, therefore, according to the definition of finite Markov chain, the evolution process of ADECA algorithm is a finite Markov chain. Assume that the state transition matrix of the difference operation guided by knowledge is $P_D$, and the state transition matrix of the selection operation is $P_S$. Since the knowledge that guides the difference operation and selection operation in each generation contains different information, the state transition matrix $P(t) = P_D(t)P_S(t)$ is different, that is, $P$ is related to the evolutionary generation $t$. Therefore, the evolutionary process of ADECA algorithm is a non-homogeneous Markov chain (process). The following uses the axiomatic model to analyze the random search process of the ADECA algorithm.

Definition 3.4. ^[40] Random variable sequence $\{X(t)\}$ weakly converges to the global optimal solution set $S^{\ast}$ in probability, if it satisfies

where $S^{\ast} = \{X|\forall Y\in S, f(X)\leq f(Y)\}$ is the global optimal solution set of the fitness function $f(\cdot)$.

Definition 3.5. ^[40] If for any $X\in B, Y\notin B$, there is $f(X) < f(Y)$, then $B\subset S$ is called the satisfactory solution set.

According to the definition, the fitness value of each individual in the satisfactory solution set is smaller than the fitness value of the individual outside the satisfactory solution set. Obviously, the global optimal solution set $S^{\ast}$ is the satisfactory solution set, and is the minimum satisfactory solution set.

Theorem 3.1. ^[40] If for any satisfactory solution set $B\subset S$, there is

and satisfy: (1)$\sum_{t = 1}^{\infty}(1-b(t)) = \infty$, (2)$\frac{a(t)}{1-b(t)}\rightarrow0$, then $\{X(t)\}$ weakly converges to the global optimal solution set $S^{\ast}$ in probability.

Corollary 3.1. ^[40] If the transition probability of $\{X(t)\}$ satisfies the condition:

Then $\{X(t)\}$ weakly converges to the global optimal solution set $S^{\ast}$ in probability.

Theorem 3.2. The ADECA algorithm weakly converges to the global optimal solution set $S^{\ast}$ in probability.

Proof. In the iteration of the ADECA algorithm, assuming the current state is $X(t) = X_i$, after the differential operation and selection operation, the next generation state is $X(t+1) = X_j$.

In the ADECA algorithm, the normative knowledge $K_{nor}$ represents the change of the feasible search space. With the evolution, the search range should be concentrated in the dominant area. In each iteration, the current optimal individual recorded by the normative knowledge is retained in the next generation population, and the optimal individual will no longer participate in the next difference operation and selection operation.

(1) When $X_i\cap B\neq \emptyset$, it means that the current optimal individual must be included in the satisfactory set $B$. From the optimal retention strategy, it can be seen that no matter which generation $t$ is, there is

(2) When $X_i\cap B = \emptyset$, it indicates that the current population $X(t) = X_i$ does not contain individuals of satisfactory set $B$. Then we consider each population $X_j$ after $X_i$, if $X_j\cap B = \emptyset$, it is obviously meaningless. Therefore, the next generation population $X_j\cap B\neq \emptyset$ is further discussed below.

When the state $X_j$ satisfies $X_j\cap B\neq \emptyset$, that is, $X_j$ contains the better individuals of the satisfactory set $B$. The transition probability generated by the difference operation under the guidance of normative knowledge is

where $Nor_k$ represents that the $k$th individual is affected by the normative knowledge, and $P(Nor_k)$ is the probability of the next generation of differential operation, $accept(Nor)$ represents the population acceptance proportion under the guidance of normative knowledge.

According to the meaning of the normative knowledge, each dimension of the individual after the difference operation does not exceed the feasible region. Therefore

and because of $accpet(Nor) > 0$, so $p_{ij}^D > 0$.

Considering that the selection mechanism of survival of the fittest is used in the ADECA algorithm to obtain the next generation population, the transition probability $p_{ij}^S > 0$, so we can get

It can be seen from Eqs (3.20) and (3.23) that the transition probability of the population evolution process of ADECA algorithm meets the condition of Corollary 3.1. It can be obtained that the state vector $\{X(t)\}$ of the ADECA algorithm weakly converges to the global optimal solution set $S^{\ast}$ in probability.

4.   Experimental design and results

In this section, some matrix games are calculated to demonstrate the effectiveness of the proposed method. Taking the classic prisoner's dilemma game, the husband and wife game and the rock-paper-scissors game as examples. The algorithm ADECA, DECA and DE are used to find the Nash equilibria based on the system of equations, and the simulation comparison figures of them are given. The parameters of the algorithm are set as: $N = 100$, $T = 300$, $F_0 = 0.4$, $CR_0 = 0.9$, $P = 0.2$, $\varepsilon = 10^{-8}$, etc. The following is the process of computing these games:

Example 4.1. Prisoner's dilemma game $\Gamma_1(S^{1}, S^{2}, X^{1}, X^{2}, A, B)$, where $S^1 = \{s^1_1, s^1_2\} = \{confess, not\; confess\}$, $S^2 = \{s^2_1, s^2_2\} = \{confess, not\; confess\}$, $X^1 = \{x^1_1, x^1_2\}$, $X^2 = \{x^2_1, x^2_2\}$, and $x_1^1, x_1^2$ respectively represent the probability of player 1, 2 choosing to confess, $x_2^1, x_2^2$ respectively represent the probability of player 1, 2 choosing not to confess, $A$ and $B$ are payoff matrices of the player in this game:

According to formula (2.7), the above game can be transformed into the following equations:

Denote each equation of the above equations by $f_i$, $i = 1, 2, 3, 4$. According to the formula (2.9), the Eq (4.1) is equivalent to the following optimization problem:

Making use of the ADECA algorithm, the DECA algorithm and the DE algorithm, we show that the solution of this problem is $x^1 = \{1, 0\}, x^2 = \{1, 0\}, \lambda_{12}^1 = \lambda_{12}^2 = 3, \lambda_{21}^1 = \lambda_{21}^2 = 0$, that is, the prisoner's dilemma game has only one pure strategy Nash equilibrium $(confess, confess)$.

Example 4.2. Husband and wife game $\Gamma_2(S^{1}, S^{2}, X^{1}, X^{2}, A, B)$, where $S^1 = \{s^1_1, s^1_2\} = \{football \; match, fashion \; show\}$, $S^2 = \{s^2_1, s^2_2\} = \{football \; match, fashion \; show\}$, $X^1 = \{x^1_1, x^1_2\}$, $X^2 = \{x^2_1, x^2_2\}$, and A and B are the payoff matrices of player 1, 2 respectively, as shown below:

According to the above payoff matrices and the calculation steps of Example 1, it is found that this problem has two pure strategy Nash equilibria and one mixed strategy Nash equilibrium: $x^1 = (1, 0), x^2 = (1, 0); x^1 = (0, 1), x^2 = (0, 1); x^1 = (1/3, 2/3), x^2 = (2/3, 1/3)$.

Example 4.3. Rock-paper-scissors game $\Gamma_3(S^{1}, S^{2}, X^{1}, X^{2}, A, B)$, where $S^1 = \{s^1_1, s^1_2, s^1_3\} = \{rock, paper, scissors\}$, $S^2 = \{s^2_1, s^2_2, s^2_3\} = \{rock, paper, scissors\}$, $X^1 = \{x^1_1, x^1_2, x^1_3\}$, $X^2 = \{x^2_1, x^2_2, x^2_3\}$ and A, B are the payoff matrices of player 1, 2 respectively, as shown below:

Calculating this example by using the ADECA, DECA and DE algorithms, we find there is only one mixed strategy Nash equilibrium: $x^1 = (1/3, 1/3, 1/3), x^2 = (1/3, 1/3, 1/3)$.

The following Figures 2–4 are comparison figures of solving the above games with the ADECA, DECA and DE algorithms.

It can be clearly seen from Figures 2–4 that the ADECA algorithm has the best performance in the calculation process, followed by DECA algorithm, and DE algorithm is the worst, especially Figure 4 is the most obvious, where the ADECA algorithm finds the global optimal solution in the first 25 iterations, while the DECA and DE algorithms reach the optimal solution after 200 iterations. On the one hand, we found that the DECA algorithm and the DE algorithm have similar performance. This seems rational because the DECA algorithm only adds one more belief space in the implementation process, which increases the operation of extracting individual hidden information, so it is only a little faster than DE algorithm in convergence speed. On the other hand, with the increase of the number of iterations, the diversity of individuals decreases and the algorithm easily falls into a local optimum. Therefore, neither the DE algorithm nor the DECA algorithm avoids this result. However, the adaptive parameters and improved mutation operations of the ADECA algorithm have played a role, which not only maintaining the diversity of the population in the early stage of iteration, but also avoiding the destruction of the optimal solution in the later stage of iteration, and speeding up the search for the global optimal solution.

By analyzing the results obtained above, it can be seen that the ADECA algorithm proposed in this paper can well find the equilibrium solutions of matrix games based on the system of equations. Further, comparing this algorithm with the DECA and DE algorithms, we find that this algorithm has a faster convergence speed and avoids falling into the local optimum. It provides a reference for future studies on related issues.

5.   Conclusions

In this paper, we study the Nash equilibria based on the system of equations. First, we give the equivalence theorem between the Nash equilibria and the solutions of the system of equations, that is, the Nash equilibria of the $n$-person finite noncooperative game are equivalent to the solutions of the system of algebraic equations with a series of relaxation parameters. This method is a new method for solving Nash equilibria except that the finding Nash equilibria is equivalent to solving optimization problems and fixed point problems. It not only builds a bridge between these two types of problems so that people can use the theories and methods of studying one problem to study another problem, broadens the methods for finding the Nash equilibria and lays a mathematical foundation for finding the Nash equilibria based on equations in the future. However, the equivalence form is also derived from the definition of Nash equilibrium, which implies the rational behavior of players. Second, we provide an equivalent form of solving matrix games and propose the ADECA algorithm. This algorithm uses a simple DE algorithm as the population space of CA algorithm, and in order to improve the convergence ability of the algorithm and global search capability, the mutation factor and crossover operator of the DE algorithm are adaptively improved, and a more globally convergent mutation operation is also proposed. Then, its convergence is proved theoretically by using finite Markov chain. Finally, the superiority of the ADECA algorithm is verified through three classic matrix game examples, and we also show that this algorithm can be used to find the Nash equilibria based on the equations, which lays the foundation for future research.

Although the method proposed in this paper can solve n-person noncooperative games theoretically, and provides specific steps for solving matrix games. It has certain research significance. However, when calculating specific multiplayer games or more complex games, the fitness function becomes increasingly complex due to the increase of the number of participants and the number of strategies, which may lead to the result falling into the local optimal solution and ending the computing in advance. Therefore, in order to overcome the limitations of the algorithm in solving multiplayer games or more complex games, the algorithm needs to be further improved in the future.

Acknowledgments

This study was supported by the National Natural Science Foundation of China (Grant Nos. [71961003] and [12061020]), the Scientific Research Foundation of Guizhou University (Grant No. [2019]49).

Conflict of interest

The authors declare no potential conflict of interests.