Control design to minimize the number of bankrupt players for networked evolutionary games with bankruptcy mechanism

1.   Introduction

With the emerging technologies and rapid development of complex networks, networked evolutionary games (NEGs) have been widely used in popular research fields such as multi-agent learning ^[1], transportation networks ^[2], and social networks ^[3]. An NEG is comprised of a network graph, a fundamental networked game (FNG), and a strategy-updating rule (SUR), and each player decides its strategy at the next step by a pre-defined SUR. Unconditional imitation, Fermi rule, and myopic best response adjustment are three commonly used SURs. Under these SURs, a number of approaches have been proposed to study the dynamics of NEGs, including the mean-field approach ^[4] and Monte Carlo simulation method ^[5]. It can be observed that these methods mainly focus on qualitative analysis by numerical simulations, make it difficult to present strict theoretical results to analyze and regulate the evolutionary behaviors of each player in an NEG.

In order to deal with finite-valued logical dynamic systems, a new matrix multiplication called semi-tensor product (STP) of matrices, was proposed by Professor Cheng ^[6]. The outstanding advantage of STP is that it can convert any finite-valued system into an algebraic state-space representation form ^[7]. Based on this form, many results and methods about classical control theory can be directly used to study finite-valued logical dynamic systems. Under the STP method, many fundamental problems of logical networks have been solved, such as stability and stabilization^[8,9,10], controllability and observability^[11,12,13], and optimal control ^[14,15]. In a game, each player has strategy set, which can be either discrete or continuous ^[16,17]. When the number of players in the game and the strategies of each player are both finite, its dynamics can be modelled as a logical network. The logical network assigns a value to the strategy of the player and represents SUR as a propositional logical formula; thus, the dynamics of a game can be studied as a logical dynamic system.

Up to now, the STP method has been successfully applied in the research of NEGs. In ^[18], authors frist provided a standard process to convert a general NEG into an algebraic form by STP method, and studied some control problems of an NEG. In ^[19], authors discussed the dynamical behavior of NEGs, and added a control player in the game so that the payoff to this player was maximized by designing a strategy control scheme. Some other problems of NEGs have also been solved under the framework of STP, including stability analysis ^[20,21], strategy optimization ^[22], and strategy consensus ^[23,24]. The survey papers ^[25] and ^[26] gave a detailed introduction to the application of STP in finite games. In addition, this powerful tool has also been successfully used to other types of games, such as potential games ^[27,28], congestion games ^[29], and Bayesian games ^[30].

In economic systems, the bankruptcy of financial institutions and enterprises is a common phenomenon. Generally, for any individual, in order to ensure their survival, their profits need to meet a minimum requirement. When this minimum requirement is not met, the individual or organization will face extinction. Therefore, it is of practical significance to study the bankruptcy mechanism of the games. Authors in ^[31] first studied the chain reaction of bankruptcy behavior and the cooperation in evolutionary games and found that a cascading bankruptcy process may occur when defection strategies exist. Authors in ^[32] studied the cascading failure in a scale-free network, and discussed the influence of the number of law enforcers on the evolutionary game. Since there is no strict theoretical framework for the systematic analysis of such games, these works used only numerical simulation methods to study the dynamics of games, and did not provide schemes to avoid players going bankruptcy.

In ^[33], the STP method was firstly applied to study the control problem of NEGs with bankruptcy mechanism, and a control sequence was designed to avoid any player going bankrupt. Authors in ^[34] investigated the state-feedback control design problem to avoid all players going bankrupt. Authors in ^[35] studied the minimum-time strategy optimization problem for NEGs with bankruptcy mechanism by designing a kind of state-feedback controllers. However, in a real economic market, sometimes it is challenging to avoid bankruptcy for all enterprises despite the effort of the government to regulate the decisions of certain financial institutions or companies. For instance, some small and medium-sized businesses are particularly prone to bankruptcy when economy is sluggish. In these cases, it becomes a meaningful topic to minimize the number of bankrupt enterprises, which can be modeled as the problem of minimizing the number of bankrupt players for NEGs with bankruptcy mechanism. As far as we know, there is no literature on how to minimize the number of bankrupt players in an NEG.

Motivated by this, we intend to study the strategy optimization problem for NEGs; our main goal is to design a state-feedback control such that the number of bankrupt players is minimized. The major contributions are as follows: (1) The sets of profiles with different numbers of bankrupt players are defined and a desired profile set in which the number of bankrupt players is no higher than a given value is obtained. Moreover, the convergence region of the desired profile set is calculated. (2) For any profile in the convergence region of the desired profile set, we propose a controller design method to minimize the number of bankrupt players. It is noted that if the given number of bankrupt players is 0, our results will degenerate into the results of avoiding all players going bankrupt.

The rest of this paper is organized as follows: Section 2 contains some necessary preliminaries on the STP and game theory. Section 3 is the problem formulation for this paper. Section 4 gives the main results. Section 5 gives an illustrative example. Section 6 gives a brief conclusion.

2.   Preliminaries

Notations:

● $\mathbb{R}$: the set of real numbers.

● $\Delta_n: = \{\delta_n^i\mid i = 1, 2, \cdots, n\}$.

● $\mathcal M_{m\times n}$: the set of $m\times n$ real matrices.

● $Col_i(A)$ : the $i$-th column of $A$.

● $Row_i(A)$ : the $i$-th row of $A$.

● $\mathbb{Z_+}$ : the set of positive integer.

● $\mathcal{L}_{m\times n}$ denotes the set of ${m\times n}$ logical matrices. $L\in \mathcal{L}_{m\times n}$ means $Col(L)\subseteq \ D_{m}$.

● $\mathcal{B}_{m\times n}$ : the set of ${m\times n}$ Boolean matrices. $L\in \mathcal{B}_{m\times n}$ means that all its entries are either 0 or 1.

● $A+_{\mathcal{B}}B$ : the Boolean addition of $A, B\in \mathcal{B}_{m\times n}$, where $(A+_{\mathcal{B}}B)_{i, j} = (A)_{i, j}\vee (B)_{i, j}$.

● $\underset{\mathcal{B}}{\sum}_{i = 1}^{n}(A_{i}) = A_{1}+_{\mathcal{B}}A_{2}+_{\mathcal{B}}\cdots+_{\mathcal{B}}A_{n},$ where $A_{i}\in \mathcal{B}_{m\times n}, i\in \{1, 2, \ldots, n\}.$

In the following, we give some necessary preliminaries about STP and NEG.

Definition 2.1. ^[6] 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.

The semi-tensor product is a generalization of the traditional matrix product, so the symbol $\ltimes$ is omitted below.

Lemma 2.2. ^[36] Define the retrievers as

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

Lemma 2.3. ^[36] Let $f:\mathcal{D}_{k}^n\rightarrow \mathcal{D}_{k}$ be a k-valued logical function. Then, there exists a unique $M_f\in\mathcal{L}_{m\times k^n}$, such that in vector form we have

where $M_f$ is called the structure matrix of f.

Definition 2.4. ^[18] A normal finite game G has three basic elements $(N, S, P)$, where

● $N = \{1, 2, \ldots, n\}$ is the set of players.

● $S = \Pi_{i = 1}^n S_{i}$ is the profile set, and $S_{i} = \{s_{1}, s_{2}, \ldots, s_{k_{i}}\}$ is the set of strategies of player $i$, $i\in N$.

● $P = \{p_{1}, p_{2}, \ldots, p_{n}\}$ and $p_{i}:S\rightarrow \mathbb{R}$ is the payoff function of player $i, i\in N$.

Definition 2.5. ^[18] A normal game with two players is called a fundamental network game (FNG), if

An FNG is symmetric, if $p_{1}(x, y) = p_{2}(y, x), \forall x, y \in S_{0}.$

Definition 2.6. ^[18] An NEG denoted by $((N, E), G, F)$ consists of three components, namely:

● A network graph $(N, E)$ with $N = \{1, 2, \cdots, m\}$ the set of vertices, $E \subset N\times N$ the set of edges.

● An FNG, such that if $(i, j)\in E$, then players $i$ and $j$ play the FNG.

● A local information-based strategy-updating rule $F = (f_{1}, f_{2}, \cdots, f_{n})$.

This paper considers the NEGs whose FNG is symmetric. The payoff bi-matrix of the FNG is shown in Table 1, where $a_{ij} > 0$.

Definition 2.7. ^[18] Let $N$ be the set of nodes in the network, and $E \in N \times N$ the set of edges. $U(i)$ is the set of the neighborhood of $i$, and we assume that $i \in U(i)$.

In the NEG, player $i$ only plays games with all its neighbors, and the payoff of player $i$ is the sum of the payoffs interacting with all its neighbors; in other words,

where $p_{ij} : \ S_{0}\times S_{0}\rightarrow \ \mathbb{R}$ is the payoff of player $i$ playing with its neighbor $j$ when $i$ takes strategy $x_{i}$ and $j$ takes strategy $x_{j}$.

The SUR considered is the unconditional imitation updating rule with fixed priority. Let $x_{i}(t)$ denote the strategy adopted by player $i$ at time $t$ and $x(t) = \big(x_{1}(t), x_{2}(t), \cdots, x_{n}(t)\big)$; the SUR can be described in mathematical formula as

where $f_{i}$ is a finite-valued function determined by the SUR. Precisely, if

then

The players with maximum payoff may be not unique; in other words, $argmax_{j\in U(i)}p_{j}(x(t)) : = \{j_{1}^{\ast}, j_{2}^{\ast}, \cdots, j_{r}^{\ast} \}$. When $i\in \{j_{1}^{\ast}, j_{2}^{\ast}, \cdots, j_{r}^{\ast} \}$, player $i$ retains their strategy for the next moment. When $i\notin \{j_{1}^{\ast}, j_{2}^{\ast}, \cdots, j_{r}^{\ast} \},$ we select one corresponding to a priority as

Definition 2.8. ^[18] Let $N = Y\cup U$ be a partition of N. If the strategies of any $u\in U$ can be assigned arbitrarily, we call $[(Y \cup U, E), G, F ]$ a controlled NEG. Moreover, $u\in U$ is called a control player.

3.   Problem formulation of NEGs with bankruptcy mechanism

This section introduces the model of NEGs with bankruptcy mechanism, and gives its algebraic form.

In the NEGs with bankruptcy mechanism, each player usually needs to keep their payoff above a certain value in order to continue to survive. Denote $T_{i}$ as the minimum survival requirement for player $i$. When the payoff of player $i$ is below $T_{i}$, the player will exit the NEG, and the network topology will change. The change of network topology will lead to a situation where the dynamic analysis of the profiles becomes very complicated. In order to avoid the difficulties caused by the exit of players, a bankruptcy strategy in the NEG was introduces in ^[33]. When the payoff of player $i$ is no higher than $T_{i}$, the player is considered as a player whose strategy is bankruptcy $(B)$ and cannot be removed from the NEG.

When a player takes $B$ as its strategy, the payoffs obtained by themselves and all their neighbors is set to 0 through the game relationship among them. The payoff bi-matrix after adding the bankruptcy strategy is shown in Table 2.

After introducing the bankruptcy strategy $B$, the evolutionary dynamics of player $i$ can be described as

where $f_{i}$ is the formula expression of the unconditional imitation updating rule described in (2.1).

In order to regulate the evolutionary dynamics of NEG, we introduce control players into the game. For example, in reality, the government can influence the decisions of some businesses in order to increase the total benefits of the market. These businesses can be seen as the control players, and their actions can be regulated by the government. With the help of the government, it is reasonable to assume that these control players will not go bankrupt.

Divide the player set $N$ of the NEG into

where $Y$ is the set of normal players, and $U$ is the set of control players. In the NEG, the players in $Y$ should follow the SUR, and players in $U$ can take strategies freely. Assume that the first $m$ players are the control players, that is, $U = \{{1, 2, \ldots, m}\}$ and $Y = \{{m+1, m+2, \ldots, n}\}$.

Next, we give the algebraic form of the dynamics for the NEG. Identify strategies

Let $u_i(t)\in {\Delta}_{k}$ be the strategy of control player $i\in \{{1, 2, \ldots, m}\}$ at time $t$, and $y_j(t)\in {\Delta}_{k+1}$ be the strategy of player at time $t$. Using the STP method, the dynamics of a control NEG can be converted into an algebraic form as

where $u(t) = \ltimes_{i = 1}^m u_{i}(t), y(t) = \ltimes_{j = m+1}^n y_{j}(t)$.

We can study the whole evolutionary dynamics by analyzing the profile transition matrix $L$ of the NEG.

Remark 3.1. For any NEG, once the network graph, FNG, and SUR are given, its dynamics can be converted into an algebraic form like (3.2) by the STP method; one can refer to ^[18] for more details. In ^[33], a detailed procedure was proposed to convert the NEG with bankruptcy mechanism to the algebraic form (3.2); we will not repeat the description here.

The aim of this paper is to design a state-feedback controller

such that minimum players will go bankrupt starting from a given initial state, where $g_i$ is a logical function, $i\in \{1, 2, \ldots, m\}$. Based on Lemma 2.3, (3.3) must have its algebraic form, and we denote it as

where $G\in\mathcal{L}_{k^{m}\times (k+1)^{n-m}}$ is the state-feedback gain matrix.

Previous results just investigated whether all players could avoid going bankrupt under controls, such as control sequences ^[33] and state-feedback control^[34]. Keeping all players from going bankrupt is too difficult to achieve sometimes, so we investigate how to minimize the number of bankrupt players in an NEG.

4.   Main results

Considering realistic economic systems, we do not optimize the profiles with too many bankrupt players. For an initial profile, if no matter how we design the controller, the number of players who go bankrupt will be more than $\alpha$, we no longer optimize it.

If a player chooses a bankruptcy strategy, their payoff is 0, which will still be less than their minimum survival requirement. The bankruptcy strategy is still selected at time $t+1$ according to the strategy-updating rule. Obviously, a bankrupt player will never return to a normal player. From the above analysis, we can see that the number of bankrupt players can only stay the same or increase.

In order to minimize the number of bankrupt players, we need to search for the profiles whose number of bankrupt players is no more than $\alpha$.

According to Lemma 2.2, we can obtain that

Then we have

We can obtain that $a_{k+1}\in \{0, 1, \cdots, n-m\}$. Since the bankruptcy strategy is denoted by $\delta^{k+1}_{k+1}$, $a_{k+1}$ represents the number of bankrupt players in profile $y(t)$. Denote the set of profiles that has $i$ bankrupt players as $\Omega^{i}$. Then, $\Omega^{i}$ can be expressed as

Denote

If a profile $y\in \Omega^{\ast}$, then the number of bankrupt players in profile $y$ must be no more than $\alpha$. Therefore, we expect that the profile trajectories can converge to set $\Omega^{\ast}$. If an initial profile converges to $\Omega^{\ast}$, then it must converge to the control invariant subsets of $\Omega^{\ast}$. We give the definition of the control invariant subsets as follows.

Definition 4.1. ^[37] A set $\Lambda \subseteq \Delta_{(k+1)^{n-m}}$ is a control invariant subset of system (3.2), if for any $y(t)\in \Lambda$, there is a control $u(t)\in \Delta_{k^m}$ such that $y(t+1) \in \Lambda$.

The maximum control invariant subset of a given set $\Lambda$, denoted by $I_{c}(\Lambda)$, is the union of all control invariant subsets contained in $\Lambda$.

Remark 4.2. We need to obtain $I_c(\Omega^{\ast})$. There are many mature conclusions in calculating the maximum control invariant set of a given set such as ^[37]. We will not repeat the detailed procedure here.

The set of all profiles that converge to the invariant set $I_c(\Omega^{\ast})$ is called the convergence region of $I_c(\Omega^{\ast})$, that is

where $y(t, \delta_{(k+1)^{n-m}}^j)$ is the state at time $t$ starting from $\delta_{(k+1)^{n-m}}^j$.

If a profile can converge to $I_{c}(\Omega^{\ast})$, then the number of bankrupt players must be no more than $\alpha$ at each step in the evolutionary trajectory of this profile. If we want to find all the profiles that satisfy the condition, we just need to compute the convergence region of $I_{c}(\Omega^{\ast})$. We have the following conclusion.

Theorem 4.3. For NEGs with bankruptcy mechanism (3.2),

Proof. If $\delta^{j}_{(k+1)^{n-m}}$ converges to $I_{c}(\Omega^{\ast})$, then $\delta^{j}_{(k+1)^{n-m}}\in \mathcal{A}(I_{c}(\Omega^{\ast}))$. Since $I_{c}(\Omega^{\ast})$ is one-step reachable from any profile in the $I_{c}(\Omega^{\ast})$, we obtain that $I_{c}(\Omega^{\ast})\subseteq \mathcal{A}(I_{c}(\Omega^{\ast}))$.

Next, we prove $\mathcal{A}(I_{c}(\Omega^{\ast}))\subseteq I_{c}(\Omega^{\ast})$. Assume a profile $\delta^{j}_{(k+1)^{n-m}} \in \mathcal{A}(I_{c}(\Omega^{\ast}))$, then $\delta^{j}_{(k+1)^{n-m}}$ must converge to $I_{c}(\Omega^{\ast})$. Since the number of bankrupt players does not decrease during the evolution of the profile, starting from $\delta^{j}_{(k+1)^{n-m}}$, the number of bankrupt players at any time does not exceed $\alpha$. This means that the trajectory of $\delta^{j}_{(k+1)^{n-m}}$ stays in $\Omega^{\ast}$. Therefore, $\delta^{j}_{(k+1)^{n-m}} \in I_{c}(\Omega^{\ast}),$ then $\mathcal{A}(I_{c}(\Omega^{\ast}))\subseteq I_{c}(\Omega^{\ast})$.

To sum up, $\mathcal{A}(I_{c}(\Omega^{\ast})) = I_{c}(\Omega^{\ast}).$

We know that only profiles starting from $\mathcal{A}(I_{c}(\Omega^{\ast}))$ can eventually achieve a number of bankrupt players no higher than $\alpha$. So we only optimize the evolution trajectories of this part of initial profiles. To optimize the trajectories of system (3.2), we should first calculate the basin of each set $I_{c}(\Omega^i), i = 0, 1, \cdots, \alpha$.

First, we seek the set of profiles that can ensure that no player goes bankrupt. Since only the profiles in $\Omega^{0}$ can guarantee that the number of bankrupt players is 0, we need to compute the maximum control invariant set $I_{c}(\Omega^{0})$ and then calculate the basin of $I_{c}(\Omega^{0})$. We get the following conclusion.

Corollary 4.4. For NEGs with bankruptcy mechanism (3.2),

Proof. The proof is similar to Theorem 4.2, so we omit this part.

If $\mathcal{A}(I_{c}(\Omega^0)) = \Omega^0$, then starting from any profile $y\in \Omega^0$, we can design a state-feedback control to ensure that no player goes bankrupt. Moreover, the corresponding state-feedback control can be obtained by the truth matrix method. According to Definition 4.1, any profile $y\in I_{c}(\Omega^0)$ will remain in the set $I_{c}(\Omega^0)$ in the next step under a control $u$. Therefore, we can construct a truth matrix as

If $T_{i, j} = 1$, it means that profile $\delta_{(k+1)^{n-m}}^{j}\in I_{c}(\Omega^0)$ can still evolve into $I_{c}(\Omega^0)$ at the next step under control $\delta_{(k+1)^{n-m}}^i$. Since $I_{c}(\Omega^0)$ is a control invariant set, we can obtain

Then the corresponding state-feedback control can be designed as

It is noted that $G$ is a logical matrix, so $Col_{i}(G)$ should not only satisfy Eq (4.2), but also belong to $\Delta_{k^{m}}$.

If $\mathcal{A}(I_{c}(\Omega^0))\neq \Omega^0$, then for any profile in $\Omega^0\backslash \mathcal{A}(I_{c}(\Omega^0))$, at least one player will go bankrupt during the evolution. We continue to find the optimal evolutionary trajectories for the other profiles.

Next, we need to seek the set of profiles that will ensure that only one player goes bankrupt. Since the number of bankrupt players cannot be reduced from any initial profile, the profile in $\Omega^{i}$ can only evolve to $\Delta_{(k+1)^{n-m}}\backslash \bigcup_{j = 0}^{i-1}\Omega^{j}$. Since the profiles in $\mathcal{A}(I_{c}(\Omega^0))$ have determined the optimal evolutionary trajectories, we just need to look for profiles where only one player eventually goes bankrupt in $(\Omega^{0}\cup \Omega^{1})\backslash \mathcal{A}(I_{c}(\Omega^0)).$

Denote $R_{0}(I_{c}(\Omega^1)) = I_{c}(\Omega^1)$ and $S_{1} = (\Omega^{0}\cup \Omega^{1})\backslash \mathcal{A}(I_{c}(\Omega^0))\cup I_{c}(\Omega^1)$, then construct

Calculate $R_{1}(I_{c}(\Omega^1)): = \{\delta_{(k+1)^{n-m}}^j|Col_{j}(T_{R_{0}(I_{c}(\Omega^1))| S_{1}})\neq \mathbf{0}_{(k+1)^m}\}$. It is obvious that for any $\delta_{(k+1)^{n-m}}^j\in R_{1}(I_{c}(\Omega^1)), R_{0}(I_{c}(\Omega^1))$ is one-step reachable from $\delta_{(k+1)^{n-m}}^j$. Check whether $R_{1}(I_{c}(\Omega^1)) = \emptyset$. If $R_{1}(I_{c}(\Omega^1)) = \emptyset$, the basin is $I_{c}(\Omega^1)$; otherwise, denote $S_2 = S_1\backslash R_1(I_{c}(\Omega^1))$, and construct $T_{R_{1}(I_{c}(\Omega^1))| S_{2}}$ as

Calculate $R_{2}(I_{c}(\Omega^1)): = \{\delta_{(k+1)^{n-m}}^j|Col_{j}(T_{R_{1}(I_{c}(\Omega^1))| S_{2}})\neq \mathbf{0}_{k^m}\}$. It is evident that for any $\delta_{(k+1)^{n-m}}^j\in R_{2}(I_{c}(\Omega^1))$, $R_{1}(I_{c}(\Omega^1))$ is one-step reachable from $\delta_{(k+1)^{n-m}}^j$. In other words, $I_{c}(\Omega^1)$ is two-step reachable from $\delta_{(k+1)^{n-m}}^j$. Check whether $R_{2}(I_{c}(\Omega^1)) = \emptyset$. When $R_{2}(I_{c}(\Omega^1)) = \emptyset$, $\mathcal{A}(I_{c}(\Omega^1)) = R_{0}(I_{c}(\Omega^1))\cup R_{1}(I_{c}(\Omega^1))$.

When $R_{2}(I_{c}(\Omega^1))\neq \emptyset$, we can repeat the above procedure. Since the number of profiles in $S_{1}$ is finite and $R_{i} (I_{c}(\Omega^1))\bigcap R_{j} (I_{c}(\Omega^1)) = \emptyset$, there exists $l_{1}\in \mathbb{Z_{+}}$ such that $R_{l_{1}}(I_{c}(\Omega^1)) = \emptyset$ and $R_{l_{1}-1}(I_{c}(\Omega^1))\neq\emptyset$. Therefore, we can compute that

We can use Figure 1 to show the calculation of $\mathcal{A}(I_{c}(\Omega^1))$.

Moreover, the corresponding columns of the state-feedback control can be determined by

where

We can obtain that for any initial profile starting in $\mathcal{A}(I_{c}(\Omega^1))$, we can regulate the control players such that only one player goes bankrupt eventually. Since the profiles in $\mathcal{A}(I_{c}(\Omega^1))$ cannot converge to $\Omega^{0}$, we ensure that the least players go bankrupt in these profiles.

The same method can be used to compute the convergence domain of $I_{c}(\Omega^\theta), \theta\in \{2, 3, \ldots, \alpha\}$. When we calculate the convergence domain of $I_{c}(\Omega^\theta)$, the profiles in $\mathcal{A}(I_{c}(\Omega^0))\cup \cdots \cup \mathcal{A}(I_{c}(\Omega^{\theta-1}))$ have determined the optimal evolutionary trajectories; we just need to compute the convergence domain in $(\Omega^0\cup \Omega^1\cup\cdots \cup \Omega^\theta)\backslash \big(\mathcal{A}(I_{c}(\Omega^0))\cup \cdots \cup \mathcal{A}(I_{c}(\Omega^{\theta-1}))\big)$. On this basis, an algorithm is proposed to calculate $\mathcal{A}(I_{c}(\Omega^\theta))$.

According to Algorithm 1, we can not only find the corresponding convergence domain of $I_{c}(\Omega^\theta)$, but also determine the corresponding control of each profile in it. Precisely, the state-feedback control can be designed as

where

Theorem 4.5. Consider the NEGs with bankruptcy mechanism (3.2), if the state-feedback matrix G satisfies

where $\mathrm{T^\ast} = \mathrm{T_{I_{c}(\Omega^0)|I_{c}(\Omega^0)}} +\mathrm{T^{\ast}_{\Omega^1}}+\cdots+\mathrm{T^{\ast}_{\Omega^\alpha}},$ then for any initial profile $y\in \mathcal{A}(I_{c}(\Omega^{\ast}))$, the number of bankrupt players is minimized.

Proof. We can know from the construction of the truth matrices that for any $\theta\in\{1, 2, \ldots, \alpha\}$,

where $\mathcal{A}(I_{c}(\Omega^{\theta_{1}}))\bigcap \mathcal{A}(I_{c}(\Omega^{\theta_{2}})) = \emptyset$ for any $\theta_{1}\neq \theta_{2}, \theta_{1}, \theta_{2}\in \{1, 2, \cdots, \alpha\}$.

Since $\mathcal{A}(I_{c}(\Omega^{\ast})) = \bigcup _{j = 0}^{\alpha}\mathcal{A}(I_{c}(\Omega^{j}))$, for any $\delta_{(k+1)^{n-m}}^{i}\in\mathcal{A}(I_{c}(\Omega^{\ast}))$, there exists a unique $\theta\in \{0, 1, \ldots, \alpha\}$ such that $\delta_{(k+1)^{n-m}}^{i}\in\mathcal{A}(I_{c}(\Omega^{\theta}))$.

If $\delta_{(k+1)^{n-m}}^{i}\in\mathcal{A}(I_{c}(\Omega^{0}))$, it holds that $Col_{i} (T_{I_{c}(\Omega^{0})|I_{c}(\Omega^{0})})\neq\mathbf{0}_{k^{m}}$, and there exists an integer $s\in \{1, 2, \ldots, k^{m}\}$ such that $[T_{I_{c}(\Omega^{0})|I_{c}(\Omega^{0})}]_{s, i}\neq 0$. It follows from (4.1) that $L\delta_{k_{m}}^{s}\delta_{(k+1)^{n-m}}^{i}\in I_{c}(\Omega^{0})$, which implies that $\delta_{(k+1)^{n-m}}^{i}$ can evolve to $I_{c}(\Omega^{0})$ at the next step under control $u = \delta_{k_{m}}^{s}$. Therefore, if $Col_{i}(G)\leq Col_{i}(T_{I_{c}(\Omega^{0})|I_{c}(\Omega^{0})})$, that is, we design $Col_{i}(G) = \delta_{k^{m}}^{s}$, the number of bankrupt players is $0$ starting from the initial profile $\delta_{(k+1)^{n-m}}^{i}$. The number of bankrupt players is minimized.

If $\delta_{(k+1)^{n-m}}^{i}\in \mathcal{A}(I_{c}(\Omega^{\theta})), \theta\in\{1, 2, \ldots, \alpha\}$, it holds that $Col_{i}(T^{\ast}_{\Omega^{\theta}})\neq \mathbf{0}_{k^{m}}$, and there are integers $w\in\{1, 2, \ldots, k^{m}\}$ and $v\in\{0, 1, \ldots, l_{\theta}-1\}$ such that $[T^{\ast}_{\Omega^{\theta}}]_{w, i}\neq 0$ and $\delta_{(k+1)^{n-m}}^{i}\in R_{v}(I_{c}(\Omega^{\theta}))$. If we design $Col_{i}(G) = \delta_{k^{m}}^{w}\leq Col_{i}(T^{\ast}_{\Omega^{\theta}})$, it follows from Algorithm 1 that $L\delta_{k^{m}}^{w}\delta_{(k+1)^{n-m}}^{i}\in R_{v-1}(I_{c}(\Omega^{\theta}))$. Therefore, $\delta_{(k+1)^{n-m}}^{i}$ gradually converges to $I_{c}(\Omega^{\theta})$, which shows that the number of bankrupt players will be $\theta$. Since $\delta_{(k+1)^{n-m}}^{i}$ cannot evolve to $I_{c}(\Omega^{0})\cup I_{c}(\Omega^{1})\cup \cdots\cup I_{c}(\Omega^{\theta-1})$, the number of bankrupt players is minimized starting from the initial profile $\delta_{(k+1)^{n-m}}^{i}$.

From the arbitrariness of profile $\delta_{(k+1)^{n-m}}^{i}$ in $\mathcal{A}(I_{c}(\Omega^{\ast}))$, the theorem is completed.

Remark 4.6. We do not optimize the profiles in $\Delta_{(k+1)^{n-m}}\backslash \mathcal{A}(I_{c}(\Omega^{\ast}))$, so the corresponding control to each profile $y\in \Delta_{(k+1)^{n-m}}\backslash \mathcal{A}(I_{c}(\Omega^{\ast}))$ can be designed arbitrarily. It is noted that G is a logical matrix, so $Col_{i}(G)$ should not only satisfy Eq (4.4) but also belong to $\Delta_{k^{m}}$.

Remark 4.7. For the control problems of NEGs with bankruptcy mechanism, previous works just studied how to avoid all players going bankrupt, which can be transformed into the set stabilization problem of the algebraic form (3.2). As the objective set for each profile in the system is the same, the core method is to calculate the largest control invariant subset of the objective set and the attraction basin of this set. However, in this paper, we aim to minimize the number of bankrupt players, which cannot be simply transformed into the set stabilization problem of (3.2). Since the optimal objective set of each profile is not known in advance, the main challenge in this paper is to determine the optimal objective set for each profile.

5.   An illustrative example

This section gives an example of how to study NEGs with bankruptcy mechanism.

Example 5.1. The basic elements of a controlled NEG are as follows:

● The network topological structure, denoted as $(Y\cup U, E)$, is shown in Figure 2. $U = \{1\}, Y = \{2, 3, 4, 5\},$ and $E = \{(1, 2), (1, 3), (1, 5), (2, 4), (3, 4)\}.$

● The FNG is $\mathbf{a\ snowdrift\ game}$, where the payoff bi-matrix is shown in Table 3. $C$ denotes cooperation and $D$ is defection. The minimal requirements of the four players are $T_{2} = T_{3} = T_{4} = 7, T_{5} = 5$.

● The SUR is the unconditional imitation with fixed priority updating rule. We assume that control player 1 will never go bankrupt, while the other players will go bankrupt if the payoff fails to meet its minimal requirement.

Identify $C\sim \delta^{1}_{3}, D\sim \delta^{2}_{3}, B\sim \delta^{3}_{3}.$ The evolutionary dynamics of this NEG can be converted into an algebraic form as:

where $u(t) = u_{1}(t)\in \Delta_{2}, y(t) = \ltimes^{5}_{i = 2}y_{i}(t)\in \Delta_{81},$ and

Next, we shall solve the optimization problem of this NEG. We first calculate the set of profiles for no more than two bankrupt players. We can obtain

Denote $\Omega^{\ast} = \Omega^{0} \cup \Omega^{1} \cup \Omega^{2}$. By constructing a truth matrix, we can obtain

Because of $\mathcal{A}(I_{c}(\Omega^{\ast})) = I_{c}(\Omega^{\ast})$, any profile in $I_{c}(\Omega^{\ast})$ ensures that no more than two players go bankrupt.

Next, we minimize the number of bankrupt players step by step. We first compute the initial profile set that eventually guarantees that all players do not go bankrupt. Then, we have

According to Proposition 4.4, we know $\mathcal{A}(I_{c}(\Omega^0)) = I_{c}(\Omega^0)$. It shows that no player is bankrupt from the initial profile $y\in I_{c}(\Omega^{0})$. By constructing the truth matrix $\mathrm{T_{I_{c}(\Omega^0)| I_{c}(\Omega^0)}}$, we can obtain

which means that the corresponding control of profiles $\delta_{81}^{1}, \delta_{81}^{2}, \delta_{81}^{4}, \delta_{81}^{10}, \delta_{81}^{11}, \delta_{81}^{13}, \delta_{81}^{14}, \delta_{81}^{28}, \delta_{81}^{29}, \delta_{81}^{31}, \delta_{81}^{32}$ is $\delta_{2}^{1}$.

Similarly, we continue to seek the set of profiles that will ensure only one player goes bankrupt. Then, we have

We can compute the convergence domain of $I_{c}(\Omega^{1})$ by Algorithm 1. It is computed that

We can obtain the truth matrix

which shows that we can design a state-feedback gain matrix $G$ to ensure that the number of bankrupt players is 1 starting from any profile $y\in \mathcal{A}(I_{c}(\Omega^{1}))$.

Furthermore, it is computed that

Moreover, by Algorithm 1, we have

We can obtain the truth matrix as

where $j\in[1:81]$. We can describe a possible profile feedback gain matrix $G$ as

where $j\in[1:81]$.

Based on the above discussion, we just need to make the corresponding state-feedback matrix satisfy

where

Then, we can design the state-feedback matrix as follows

where $j\in[1:81]$. Under this control, we can ensure that for any initial profile $y \in \mathcal{A}(I_{c}(\Omega^{\ast}))$, the number of bankrupt players is minimized.

We take initial profile $\delta_{81}^{5}$ as an example. When we take $G$ as above, the evolutionary trajectory of the profile $\delta_{81}^{5}$ can be expressed in Figure 3. We know from Figure 3 that the trajectory starting from $y(0) = \delta_{3}^{1}\delta_{3}^{1}\delta_{3}^{2}\delta_{3}^{2} = \delta_{81}^{5}$ is $\delta_{81}^{5}\rightarrow \delta_{81}^{46}\rightarrow \delta_{81}^{52}\rightarrow \delta_{81}^{25}\rightarrow \delta_{81}^{25}\rightarrow \cdots$.

We can see from Figure 3 that when the initial profile is $\delta_{81}^{5}$, and the control player always uses cooperation as their strategy, then the profile eventually converges to the fixed point $\delta_{81}^{25}$. The number of bankrupt players is minimized under these circumstances.

6.   Conclusions

This paper studied the strategy optimization problem for NEGs with bankruptcy mechanism. The existing results only considered how to avoid all players going bankrupt, but for the profiles where at least one player will go bankrupt, there is no further results. We investigated the problem of minimizing the number of bankrupt players. Within an allowed number of bankrupt players, we have designed a kind of state-feedback controller for minimizing the number of bankrupt players.

This paper only considered the ideal NEG models without the influence of other external factors. However, the actual systems may inevitably be affected by various external factors, such as changes in government policies, environmental and weather changes, and public opinion. In the future, we will consider investigating the strategy optimization problem with both disturbances and bankruptcy mechanism in NEGs.

Author contributions

Liyuan Xia: Writing-review & editing, Writing-original draft, Software, Date curation. Jianjun Wang: Writing-review & editing, Methodology, Funding acquisition, Conceptualization. Shihua Fu: Visualization, Investigation. Yuxin Gao: Visualization, Investigation. All authors have read and approved the final version of the manuscript for publication.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare no conflict of interest.