Optimal assignment of infrastructure construction workers

1.   Introduction

Game theory is a mathematical theory studying competitive phenomena. Since John von Neumann proved the basic principles of game theory, modern game theory was formally established ^[1,2], which has been paid wide attention and applied to biology, economics, computer science, and many other fields. For example, biologists use game theory to predict certain outcomes of evolution. Economists regard the game theory as one of the standard analysis tools of economics.

The concept of symmetric games is first proposed by John von Neumann in ^[2]. The symmetry of a game means that all players have the same set of strategies and fair payoffs, that is, the payoffs depend only on the strategies employed, not on who is playing them. Because fair games are more realistic and acceptable, many common games are symmetric games such as the well-known games rock-paper-scissors and prisoner's dilemma. In recent years, many problems about symmetric games have been investigated in ^[3], ^[4], ^[5], and ^[6]. In addition, based on the definition of symmetric games, the concepts of skew-symmetric games, asymmetric games and the symmetric-based decomposition of finite games have been proposed in ^[4]. Although the bases of the symmetric game subspace and the skew-symmetric game subspace have been constructed in ^[4], the vector space structure of the asymmetric game subspace has not been revealed. Therefore, the motivation of this paper is to explore the vector space structure of the asymmetric game subspace and thoroughly solve the problem of symmetric-based decomposition of finite games. In our recent paper ^[6], a new method to construct a basis of the symmetric game subspace has been proposed, which gives us great inspiration for the study of skew-symmetric games, asymmetric games, and symmetric-based decomposition of finite games.

In the past decade, the semi-tensor product (STP) of matrices has been successfully applied to game theory by Cheng and his collaborators ^[7], which enables a game to be expressed in an algebraic form. In this paper, we still use the matrix method based on STP to investigate skew-symmetric games, asymmetric games and symmetric-based decomposition of finite games. First, by the semi-tensor product method based on adjacent transpositions, necessary and sufficient conditions for testing skew-symmetric games are obtained. Then, based on the necessary and sufficient conditions, a basis of the skew-symmetric game subspace is constructed explicitly. In addition, the discriminant equations for skew-symmetric games with the minimum number are derived concretely. According to the construction methods of the basis of the symmetric game subspace in ^[6] and the basis of the skew-symmetric game subspace in this paper, a basis of the asymmetric game subspace is constructed for the first time. Therefore, the problem of symmetric-based decomposition of finite games is completely solved.

The rest of this paper is organized as follows: Section 2 gives some preliminaries. Section 3 studies skew-symmetric games and skew-symmetric game subspace. Section 4 studies asymmetric games and solves the problem of symmetric-based decomposition of finite games. Section 5 is a brief conclusion.

2.   Preliminaries

In this section, some necessary preliminaries are given. Firstly, we list the following notations.

● $\mathcal{D} = \{0, 1\}:$ the set of values of logical variables;

● $\delta_k^i:$ the $i$-th column of $I_k$;

● $\Delta_k: = \{\delta_k^i: i = 1, 2, \cdots, k\}$;

● $\delta_k[i_1\; i_2\; \cdots i_n]: = [\delta_k^{i_1}\; \delta_k^{i_2}\; \cdots\; \delta_k^{i_n}]$;

● ${\mathcal{M}}_{m\times n}:$ the set of $m\times n$ matrices;

● ${\mathcal{L}}_{m\times n}: = \{L\in{\mathcal{M}}_{m\times n}| {\rm{Col}}(L)\subseteq{\Delta}_m\}$;

● $\ltimes:$ the left semi-tensor product of matrices;

● $\textbf{1}_n$: the $n$-dimensional column vector of ones;

● $0_{m\times n}$: the $m\times n$ matrix with zero entries;

● $\textbf{S}_n$: the $n$-th order symmetric group, i.e., a permutation group that is composed of all the permutations of $n$ things;

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

Definition 2.1 (^[7]). Let $A\in\mathcal{M}_{m\times n}$, $B\in\mathcal{M}_{p\times q}$. The left semi-tensor product of $A$ and $B$ is defined as

where $\otimes$ is the Kronecker product and $\alpha = \operatorname{lcm}(n, p)$ is the least common multiple of $n$ and $p$. When no confusion may arise it is usually called the semi-tensor product (STP).

If $n$ and $p$ in Definition 2.1 satisfy $n = p$, the STP is reduced to the traditional matrix product. So, the STP is a generalized operation of the traditional matrix product. Therefore, one can directly write $A\ltimes B$ as $AB$.

Definition 2.2 (^[7]). A swap matrix $W_{[m, n]} = (w^{IJ}_{ij})$ is an $mn\times mn$ matrix, defined as follows:

Its rows and columns are labeled by double indices. The columns are arranged by the ordered multi-index Id$(i_1, i_2;m, n)$, and the rows are arranged by the ordered multi-index Id$(i_2, i_1; n, m)$. The element at the position with row index $(I, J)$ and column index $(i, j)$ is

When $m = n$, matrix $W_{[m, n]}$ is denoted by $W_{[m]}$.

Swap matrices have the following properties:

Definition 2.3. (^[8]). A finite game is a triple $G = (N, S, C)$, where

${\bf{1)}}$ $N = \{1, 2, \cdots, n\}$ is the set of $n$ players;

${\bf{ 2)}}$ $S = S_1\times S_2\times\cdots\times S_n$ is the set of strategy profiles, where $S_i = \{s_1^i, s_2^i, \cdots, s_{k_i}^i\}$ is the set of strategies of player $i$;

${\bf{ 3)}}$ $C = \{c_1, c_2, \cdots, c_n\}$ is the set of payoff functions, where $c_i: S\rightarrow \mathbb{R}$ is the payoff function of player $i$.

Denote the set composed of all the games above by $\mathcal{G}_{[n; k_1, k_2, \cdots, k_n]}$. When $|S_i| = k$ for each $i = 1, 2, \cdots, n$, we denote it by $\mathcal{G}_{[n; k]}$.

STP is a convenient tool for investigating games. Given a game $G\in\mathcal{G}_{[n; k]}$, by using the STP method ^[9], each strategy $x_i$ can be written into a vector form $x_i\in\Delta_k$, and every payoff function $c_i$ can be expressed as

where $\ltimes_{j = 1}^nx_j\in \Delta_{k^n}$ is called the STP form of the strategy profile, and $V_i^c$ is called the structure vector of $c_i$.

Definition 2.4 (^[10]). A game $G\in\mathcal{G}_{[n; k]}$ is called a symmetric game if for any permutation $\sigma\in {\bf S}_n$

for any $i = 1, 2, \cdots, n.$

3.   Skew-symmetric game and skew-symmetric game subspace

Definition 3.1 (^[4]). A game $G\in\mathcal{G}_{[n; k]}$ is called a skew-symmetric game if for any permutation $\sigma\in {\bf S}_n$

for any $i = 1, 2, \cdots, n.$

The set composed of all the skew-symmetric games in $\mathcal{G}[n; k]$ is denoted as $\mathcal{K}[n; k]$.

Lemma 3.1 (^[11]). The set of all the adjacent transpositions $(r, r+1), 1\leq r\leq n-1$ is generator of the symmetric group ${\bf{S_n}}$.

In the following, adjacent transpositions $(r, r+1), 1\leq r\leq n-1$ are represented as $\mu_r$.

Lemma 3.2. Consider $G\in\mathcal{G}_{[n; k]}$. For any $\sigma_1, \sigma_2\in {\bf{S_n}}$, if $\sigma_1$ and $\sigma_2$ satisfy

for any $i = 1, 2, \cdots, n$ and any $x_1, x_2, \cdots, x_n\in\Delta_k$, the compound permutation $\sigma_2\circ\sigma_1$ also satisfies (3.2).

Proof. For any given $x_i\in \Delta_k$, $i = 1, 2, \dots, n$, let $y_i = x_{\sigma_1^{-1}(i)}$. Then

which implies that $\sigma_2\circ\sigma_1$ satisfies (3.2).

According to Definition 3.1, Lemma 3.1 and Lemma 3.2, the following lemma follows:

Lemma 3.3. Consider $G\in\mathcal{G}_{[n; k]}$. Game $G$ is a skew-symmetric game if and only if

for any adjacent transposition $\mu_r$, $1\leq r\leq n-1$, $i = 1, 2, \cdots, n$.

Proposition 3.1. Consider $G\in\mathcal{G}_{[n; k]}$. Game $G$ is a skew-symmetric game if and only if

where $T_{\mu_r} = I_{k^{r-1}}\otimes W_{[k]}\otimes I_{k^{n-r-1}}$.

Proof. For any $i = 1, 2, \cdots, n$ and any $1\leq r\leq n-1$, we have

From (2.3) and (3.5), it follows that (3.4) is equivalent to (3.3). Therefore, the proposition is proved.

Theorem 3.1. Consider $G\in\mathcal{G}_{[n; k]}$. Game $G$ is a skew-symmetric game if and only if

where $T_{\mu_r} = I_{k^{r-1}}\otimes W_{[k]}\otimes I_{k^{n-r-1}}$, $V_G = [V_1^c\; V_2^c\; \cdots\; V_n^c]$, and the omitted elements in the coefficient matrix of (3.6) are all zeros.

Proof. Since $(W_{[k]})^{-1} = W_{[k]}$, we have $(T_{\mu_r})^{-1} = T_{\mu_r}$ for any $1\leq r\leq n-1$. Then, the equation $V_i^c = -V_{\mu_r(i)}^cT_{\mu_r}$ is equivalent to $V_{\mu_r(i)}^c = -V_i^cT_{\mu_r}$. According to Proposition 3.1, $G$ is a skew-symmetric game if and only if

where

Let the coefficient matrix of equation (3.7) be

where

Since $A_1$ is an invertible matrix, we can perform the following row transformation on the coefficient matrix of (3.7)

where

Let

We perform the following row transformation on matrix $-BA_1^{-1}A_2$

Therefore, the equivalent form of (3.7) is as follows

From the property of $W_{[k]}$ shown in (2.2), it follows that

Then, (3.18) is equivalent to (3.6). Thus, the proof is complete.

We see that the key of solving equation (3.6) is computing the solution space of the following linear equation:

where $x$ is the $k^n$-dimensional unknown vector. Considering

we only need to solve the linear equations as follows:

where $x$ is the $k^{n-1}$-dimensional unknown vector. Let $x = (x_{l_1l_2\cdots l_{n-1}})$ be arranged by the ordered multi-index Id$(i_1, i_2, \ldots, i_{n-1};k, k, \ldots, k)$, that is,

Then, by the property of $W_{[k]}$, vector $x$ is a solution of (3.22) if and only if, for any $1\leq l_1, l_2, \cdots, l_{n-1}\leq k$, the following equations hold:

i.e.

Thus, for any $1\leq r\leq n-2$, if $l_r = l_{r+1}$, then

that is,

Therefore, all the free variables of the linear equations (3.22) are

whose number is $C_{k}^{n-1}$. That is, the dimension of the solution space of linear equations (3.22) is $C_{k}^{n-1}$.

For every given repeatable combination $s_1s_2\cdots s_{n-1}, (1\leq s_1\leq s_2\leq\cdots\leq s_{n-1}\leq k)$, denote by $P_{s_1s_2\cdots s_{n-1}}$ the set composed of all the repeatable permutation of $s_1s_2\cdots s_{n-1}$. For example, $P_{122} = \{122,212,221\}$. For every given unrepeatable combination $l_1l_2\cdots l_{n-1}, (1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k)$, denote by $R_{l_1l_2\cdots l_{n-1}}$ the set composed of all the unrepeatable permutation of $l_1l_2\cdots l_{n-1}$. For example, $R_{123} = \{123,132,213,231,312,321\}$. Let

Then, any permutation in $Q$ is a repeated permutation.

Lemma 3.4. For every given unrepeatable combination $l_1l_2\cdots l_{n-1}\; (1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k)$, define a vector $\theta^{l_1l_2\cdots l_{n-1}} = x$ with the form (3.23) by

Then the set

is a basis of the solution space $\bar{\mathcal{X}}_{n-1}$ of (3.22). For every $l_1l_2\cdots l_{n-1}$ $(1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k)$, we define $|R_{l_1l_2\cdots l_{n-1}}|-1$ number of vectors $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}} = x$ with $r_1r_2\cdots r_{n-1}\in R_{l_1l_2\cdots l_{n-1}}$ and $r_1r_2\cdots r_{n-1}\ne {l_1l_2\cdots l_{n-1}}$ by

We define $|Q|$ number of vectors $\lambda^{h_1h_2\cdots h_{n-1}} = x$ $(h_1h_2\cdots h_{n-1}\in Q)$ by

Then the set of $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}}$ $(1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k, r_1r_2\cdots r_{n-1}\in R_{l_1l_2\cdots l_{n-1}}, r_1r_2\cdots r_{n-1}\ne {l_1l_2\cdots l_{n-1}})$ and $\lambda^{h_1h_2\cdots h_{n-1}}$ $(h_1h_2\cdots h_{n-1}\in Q)$ is a basis of the orthogonal complementary space $\bar{\mathcal{X}}_{n-1}^{\perp}$. Denote by $M_\mathcal{W}$ the matrix whose columns are composed of a basis of subspace $\mathcal{W}$. Then the linear system (3.22) is equivalent to $M_{\bar{\mathcal{X}}_{n-1}^{\perp}}^\mathrm{T}x = 0$.

Proof. For any $1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k$, $\mathrm{sgn}(l_1l_2\cdots l_{n-1}) = 1$. From the equivalent equations (3.25) and the free variables shown by (3.26), it follows that the set of $\theta^{l_1l_2\cdots l_{n-1}}$ $(1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k)$ is a basis of the solution space $\bar{\mathcal{X}}_{n-1}$. By the construction of $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}}$ and $\lambda^{h_1h_2\cdots h_{n-1}}$, it is straightforward to see that each $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}}$ and each $\lambda^{h_1h_2\cdots h_{n-1}}$ are orthogonal to $\bar{\mathcal{X}}_{n-1}$. The total number of $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}}$ is

The total number of $\lambda^{h_1h_2\cdots h_{n-1}}$ is

Then the total number of $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}}$ and $\lambda^{h_1h_2\cdots h_{n-1}}$ is $k^{n-1}-C_{k}^{n-1}$, i.e. $k^{n-1}-\dim(\bar{\mathcal{X}}_{n-1})$. Therefore, we conclude that the set of $\nu_{l_1l_2\cdots l_{n-1}}^{r_1r_2\cdots r_{n-1}}$ $(1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k, r_1r_2\cdots r_{n-1}\in R_{l_1l_2\cdots l_{n-1}}, r_1r_2\cdots r_{n-1}\ne {l_1l_2\cdots l_{n-1}})$ and $\lambda^{h_1h_2\cdots h_{n-1}}$ $(h_1h_2\cdots h_{n-1}\in Q)$ is a basis of $\bar{\mathcal{X}}_{n-1}^{\perp}$. Then, the linear system (3.22) is equivalent to $M_{\bar{\mathcal{X}}_{n-1}^{\perp}}^\mathrm{T}x = 0$.

According to the above basis of the solution space of linear equations (3.22), we can construct a basis of skew-symmetric game subspace $\mathcal{K}_{[n; k]}$.

Theorem 3.2. The dimension of the skew-symmetric game subspace $\mathcal{K}_{[n; k]}$ is $kC_k^{n-1}$. A basis of $\mathcal{K}_{[n; k]}$ is composed of the columns of matrix

where $M_{\bar{\mathcal{X}}_{n-1}}$ is composed of the basis of the solution space of (3.22). Moreover, the linear equations with the minimum number to test skew-symmetric games in $\mathcal{K}_{[n; k]}$ are

where the omitted elements in the coefficient matrix of (3.29) are all zeros.

Proof. By Theorem 3.1 and Lemma 3.4, we can easily get the dimension of skew-symmetric game subspace $\mathcal{K}_{[n; k]}$ is $kC_k^{n-1}$. Using $M_{\bar{\mathcal{X}}_{n-1}}$ whose columns are composed of a basis of the solution space of (3.22), we get a basis of the solution space of (3.6) as follows:

By the property of swap matrices shown in (2.2), we have

for each $1\leq s\leq n-1$. Then, (3.30) is equivalent to (3.28). That is, the set of the columns of matrix (3.28) is a basis of $\mathcal{K}_{[n; k]}$. Since (3.29) is equivalent to (3.6) and the coefficient matrix of (3.29) has a full row rank, the equations in (3.29) have the minimum number for testing skew-symmetric games in $\mathcal{K}_{[n; k]}$.

Remark 3.1. The coefficient matrix of (3.29) has $nk^n-kC_{k}^{n-1}$ number of rows and each row has at most two nonzero elements. Since $C_{k}^{n-1}\leq k^{n-1}$, $(n-1)k^n\leq nk^n-kC_{k}^{n-1}\leq nk^{n}$. Therefore, the computational complexity is just $O(nk^n)$ due to

4.   Symmetric-based decomposition of finite games

Definition 4.1 (^[4]). A game $G\in\mathcal{G}_{[n; k]}$ is called an asymmetric game if its structure vector

The set of asymmetric games is denoted by $\mathcal{E}_{[n; k]}$.

Lemma 4.1 (^[6]). The dimension of the symmetric game subspace $\mathcal{S}_{[n; k]}$ is $kC_{k+n-2}^{n-1}$. A basis of $\mathcal{S}_{[n; k]}$ is composed of the columns of matrix

where $\mathcal{X}_{n-1}$ is the solution space of linear equations

and $M_{\mathcal{X}_{n-1}}$ is the matrix composed of a basis of $\mathcal{X}_{n-1}$.

Let

It is easy to check that

Since the number of odd permutations of any combination is the same as the number of even permutations, according to the construction of a basis of $\mathcal{X}_{n-1}$ in ^[6], we have

where $p = kC_{k+n-2}^{n-1}, q = kC_{k}^{n-1}$. That is, $\mathcal{S}_{[n; k]}$ and $\mathcal{K}_{[n; k]}$ are orthogonal. Therefore,

So far, we have constructed a basis of the symmetric game subspace and that of the skew-symmetric game subspace, respectively. Next, according to the two bases, we investigate the vector space structure of the asymmetric game subspace.

Consider the following linear equations

where $A$ and $B$ are shown in (4.3) and (4.4), composed of the bases of $\mathcal{S}_{[n; k]}$ and $\mathcal{K}_{[n; k]}$, respectively. Therefore, (4.8) is the discriminant equation with the minimum number for asymmetric games, and a basis of the solution space of (4.8) is also a basis of the asymmetric game subspace $\mathcal{E}_{[n; k]}$.

Construct matrices $M_{\mathcal{X}_{n-1}}$ and $M_{\bar{\mathcal{X}}_{n-1}}$ as follows:

where $\alpha = C_{k+n-2}^{n-1}$, $\beta = C_{k}^{n-1}$, and

Let

where $x^j\in\mathbb{R}^{k^n}$. Then, (4.8) is equivalent to

and

According to the construction of $\eta_i = \eta^{l_1l_2\cdots l_{n-1}}$ and $\theta_i = \theta^{l_1l_2\cdots l_{n-1}}$ $(1\leq i\leq\beta)$, we conclude that (4.12) is equivalent to

for any $1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k$, $1\leq l_n\leq k$, and (4.13) is equivalent to

for any $1\leq l_1\leq l_2\leq\cdots\leq l_{n-1}\leq k$, $l_1l_2\cdots l_{n-1}\in Q$ and any $1\leq l_n\leq k$.

We first construct two sets of solution vectors of (4.14):

If $n$ is odd, let

with each $x^p = (x_{r_1r_2\cdots r_n}^p)$,

where $1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k$, $1\leq l_n\leq k$, $t_1t_2\cdots t_{n-1}\in R_{l_1\cdots l_{n-1}}$, $1\leq j\leq n$ satisfy one of following conditions:

${\bf{(i) }}$ $j = n$, $t_1t_2\cdots t_{n-1}\neq l_1l_2\cdots l_{n-1}$ and $(-1)^{j+1} = \mathrm{sgn}(t_1t_2\cdots t_{n-1})$,

${\bf{(ii)}}$ $j\neq n$, $(-1)^{j+1} = \mathrm{sgn}(t_1t_2\cdots t_{n-1})$.

Similarly, let

with each $x^p = (x_{r_1r_2\cdots r_n}^p)$,

where $t_1t_2\cdots t_{n-1}$ and $j$ satisfy one of the following conditions:

${\bf{(i)}}$ $j = n$, $t_1t_2\cdots t_{n-1}\neq \tilde{l}_1 \tilde{l}_2\cdots \tilde{l}_{n-1} = l_2l_1l_3\cdots l_{n-1}$ and $(-1)^j = \mathrm{sgn}(t_1\cdots t_{n-1})$,

${\bf{(ii) }}$ $j\neq n$, $(-1)^{j} = \mathrm{sgn}(t_1t_2\cdots t_{n-1})$.

If $n$ is even, let

with

where $1\leq l_1 < l_2 < \cdots < l_{n-1}\leq k$, $1\leq l_n\leq k$, $t_1t_2\cdots t_{n-1}\in R_{l_1l_2\cdots l_{n-1}}$, $1\leq j\leq n$ satisfying one of the following conditions,

${\bf{(i)}}$ $j = n$, $t_1t_2\cdots t_{n-1}\neq l_1l_2\cdots l_{n-1}$ and $(-1)^j = sgn(t_1t_2\cdots t_{n-1})$,

${\bf{(ii)}}$ $j\neq n$, $(-1)^j = sgn(t_1t_2\cdots t_{n-1})$,

Similarly, let

with

where $t_1t_2\cdots t_{n-1}$ and $j$ satisfy one of following conditions:

${\bf{(i) }}$ $j = n$, $t_1t_2\cdots t_{n-1}\neq \tilde{l}_1\tilde{l}_2\cdots \tilde{l}_{n-1} = l_2l_1l_3\cdots l_{n-1}$ and $(-1)^{j+1} = \mbox{sgn}(t_1t_2\cdots t_{n-1})$,

${\bf{(ii) }}$ $j\neq n$, $(-1)^{j+1} = \mbox{sgn}(t_1t_2\cdots t_{n-1})$.

Then we construct a set of solution vectors of (4.15):

Let

with

where $1\leq l_1\leq l_2\leq\cdots\leq l_{n-1}\leq k$, $l_1l_2\cdots l_{n-1}\in Q$, $1\leq l_n\leq k$, $t_1t_2\cdots t_{n-1}\in P_{l_1l_2\cdots l_{n-1}}$, $1\leq j\leq n$ satisfy one of the following conditions:

${\bf{(i)}}$ $j = n$, $t_1t_2\cdots t_{n-1}\neq l_1l_2\cdots l_{n-1}$,

${\bf{(ii)}}$ $j\neq n$.

Theorem 4.1. The sets $\{\mu_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n; 1}\}$, $\{\mu_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n; -1}\}$ and $\{\gamma_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n}\}$ form a basis of the asymmetric game subspace $\mathcal{E}_{[n; k]}$.

Proof. According to the construction method of $\mu_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n; 1}$, $\mu_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n; -1}$ and $\gamma_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n}$, all the vectors in $\{\mu_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n; 1}\}$, $\{\mu_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n; -1}\}$ and $\{\gamma_{t_1t_2\cdots t_{n-1}; j}^{l_1l_2\cdots l_n}\}$ are linearly independent and satisfy both (4.14) and (4.15). Moreover, we have

So,

Therefore, $\{\mu_{t_1t_2\cdots t_{n-1}\ \ ; \ \ \ j}^{l_1l_2\cdots l_n; 1}\}$, $\{\mu_{t_1t_2\cdots t_{n-1}\ \ ;\ \ \ j}^{l_1l_2\cdots l_n; 1}\}$ and $\{\gamma_{t_1t_2\cdots t_{n-1}\ \ ; \ \ \ j}^{l_1l_2\cdots l_n}\}$ form a basis of $\mathcal{E}_{[n; k]}$.

Remark 4.1. We have given the bases of skew-symmetric game subspace $\mathcal{K}_{[n; k]}$ and asymmetric game subspace $\mathcal{E}_{[n; k]}$. In our recently published paper ^[6], a basis of symmetric game subspace $\mathcal{S}_{[n; k]}$ has also been given. Let the bases of $\mathcal{S}_{[n; k]}$, $\mathcal{K}_{[n; k]}$, $\mathcal{E}_{[n; k]}$ be $\{\alpha_1, \alpha_2, \cdots, \alpha_{s} \}$, $\{\beta_1, \beta_2, \cdots, \beta_{t} \}$, $\{\gamma_1, \gamma_2, \cdots, \gamma_{l} \}$ respectively, where $s = kC_{k+n-2}^{n-1}$, $t = kC_{k}^{n-1}$, $l = nk^n-kC_{k+n-2}^{n-1}-kC_{k}^{n-1}$. For any $G\in\mathcal{G}_{[n; k]}$, there are real numbers $p_1, \cdots, p_s, q_1, \cdots, q_t, r_1, \cdots, r_l$ such that

Thus, $[p_1, \cdots, p_s, q_1, \cdots, q_t, r_1, \cdots, r_l]^\mathrm{T}$ is a solution of equation

Since the coefficient matrix of (4.21) is a nonsingular matrix and each row has less than $3n!$ nonzero elements, the computational complexity of game decomposition is less than or equal to $O(n!nk^n)$.

Example 4.1. Consider $\mathcal{G}_{[3;2]}$. If $1\leq l_1 < l_2\leq 2$, we have $l_1 = 1, l_2 = 2$. Then $M_{\bar{\mathcal{X}}_2} = \begin{bmatrix} 0, \ 1, \ -1\ 0 \end{bmatrix}^\mathrm{T}.$ If $1\leq l_1\leq l_2\leq 2$, then $l_1l_2 = 11$, $l_1l_2 = 12$ or $l_1l_2 = 22$. Therefore,

According to (3.28), a basis of $\mathcal{K}_{[3;2]}$ is composed of the columns of matrix

According to (4.1), a basis of $\mathcal{S}_{[3;2]}$ is composed of the columns of matrix

According (4.18)-(4.20), the basis of $\mathcal{E}_{[3;2]}$ and all non-zero elements in each vector are as follows:

It is easy to verify that the basis of $\mathcal{E}_{[3;2]}$ are orthogonal to the columns of the matrices shown in (4.22) and (4.23).

5.   Conclusions

This paper mainly investigates skew-symmetric game, asymmetric game and the problem of symmetric-based decomposition of finite games. By the semi-tensor product of matrices method with adjacent transpositions, necessary and sufficient conditions for testing skew-symmetric games are obtained. Based on the necessary and sufficient conditions of skew-symmetric games, a basis of skew-symmetric game subspace is constructed explicitly. In addition, the discriminant equations for skew-symmetric games with the minimum number are derived concretely, which reduce the computational complexity. Benefiting from the construction methods of the bases of symmetric game subspace and skew-symmetric game subspace given by us, a basis of asymmetric game subspace is constructed for the first time. Then, any game in $\mathcal{G}_{[n; k]}$ can be linear represented by the bases of symmetric game subspace, skew-symmetric game subspace and asymmetric game subspace given by this paper and our previous work. Therefore, the problem of symmetric-based decomposition of finite games is completely solved. Some other kind of games can also be investigated in the frame of semi-tensor product of matrices ^{[12,13,14,15]}. We will try to generalize the obtained results in our future work.

Acknowledgment

The research work is supported by NNSF of China under Grant 62103194, Natural Science Foundation of Shandong Province of China under Grant ZR2020QA028.

Conflict of interest

The authors declare no conflict of interest.