In this paper, skew-symmetric games and a symmetric-based decomposition of finite games are investigated. First, necessary and sufficient conditions for testing skew-symmetric games are obtained by the semi-tensor product method based on adjacent transpositions. By using the obtained conditions for skew-symmetric games, a basis of the skew-symmetric game subspace is constructed. Then, the discriminant equations for a skew-symmetric game with the minimum number are derived. Furthermore, based on the basis of the skew-symmetric game subspace and that of the symmetric game subspace, a basis of the asymmetric game subspace is constructed, which completely solves the problem of symmetric-based decomposition of finite games. Finally, an illustrative example is provided to validate the obtained theoretical results.
Citation: Lei Wang, Xinyun Liu, Ting Li, Jiandong Zhu. Skew-symmetric games and symmetric-based decomposition of finite games[J]. Mathematical Modelling and Control, 2022, 2(4): 257-267. doi: 10.3934/mmc.2022024
[1] | Zhiqiang Hang, Xiaolin Wang, Fangfei Li, Yi-ang Ren, Haitao Li . Learning-based DoS attack game strategy over multi-process systems. Mathematical Modelling and Control, 2024, 4(4): 424-438. doi: 10.3934/mmc.2024034 |
[2] | Jianhua Sun, Ying Li, Mingcui Zhang, Zhihong Liu, Anli Wei . A new method based on semi-tensor product of matrices for solving reduced biquaternion matrix equation $ \sum\limits_{p = 1}^l A_pXB_p = C $ and its application in color image restoration. Mathematical Modelling and Control, 2023, 3(3): 218-232. doi: 10.3934/mmc.2023019 |
[3] | Xiaomeng Wei, Haitao Li, Guodong Zhao . Kronecker product decomposition of Boolean matrix with application to topological structure analysis of Boolean networks. Mathematical Modelling and Control, 2023, 3(4): 306-315. doi: 10.3934/mmc.2023025 |
[4] | Naiwen Wang . Solvability of the Sylvester equation $ AX-XB = C $ under left semi-tensor product. Mathematical Modelling and Control, 2022, 2(2): 81-89. doi: 10.3934/mmc.2022010 |
[5] | Aidong Ge, Zhen Chang, Jun-e Feng . Solving interval type-2 fuzzy relation equations via semi-tensor product of interval matrices. Mathematical Modelling and Control, 2023, 3(4): 331-344. doi: 10.3934/mmc.2023027 |
[6] | Wenxv Ding, Ying Li, Dong Wang, AnLi Wei . Constrainted least squares solution of Sylvester equation. Mathematical Modelling and Control, 2021, 1(2): 112-120. doi: 10.3934/mmc.2021009 |
[7] | Daizhan Cheng, Ying Li, Jun-e Feng, Jianli Zhao . On numerical/non-numerical algebra: Semi-tensor product method. Mathematical Modelling and Control, 2021, 1(1): 1-11. doi: 10.3934/mmc.2021001 |
[8] | Daizhan Cheng, Zhengping Ji, Jun-e Feng, Shihua Fu, Jianli Zhao . Perfect hypercomplex algebras: Semi-tensor product approach. Mathematical Modelling and Control, 2021, 1(4): 177-187. doi: 10.3934/mmc.2021017 |
[9] | Hongli Lyu, Yanan Lyu, Yongchao Gao, Heng Qian, Shan Du . MIMO fuzzy adaptive control systems based on fuzzy semi-tensor product. Mathematical Modelling and Control, 2023, 3(4): 316-330. doi: 10.3934/mmc.2023026 |
[10] | Xueling Fan, Ying Li, Wenxv Ding, Jianli Zhao . $ \mathcal{H} $-representation method for solving reduced biquaternion matrix equation. Mathematical Modelling and Control, 2022, 2(2): 65-74. doi: 10.3934/mmc.2022008 |
In this paper, skew-symmetric games and a symmetric-based decomposition of finite games are investigated. First, necessary and sufficient conditions for testing skew-symmetric games are obtained by the semi-tensor product method based on adjacent transpositions. By using the obtained conditions for skew-symmetric games, a basis of the skew-symmetric game subspace is constructed. Then, the discriminant equations for a skew-symmetric game with the minimum number are derived. Furthermore, based on the basis of the skew-symmetric game subspace and that of the symmetric game subspace, a basis of the asymmetric game subspace is constructed, which completely solves the problem of symmetric-based decomposition of finite games. Finally, an illustrative example is provided to validate the obtained theoretical results.
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.
In this section, some necessary preliminaries are given. Firstly, we list the following notations.
● D={0,1}: the set of values of logical variables;
● δik: the i-th column of Ik;
● Δk:={δik:i=1,2,⋯,k};
● δk[i1i2⋯in]:=[δi1kδi2k⋯δink];
● Mm×n: the set of m×n matrices;
● Lm×n:={L∈Mm×n|Col(L)⊆Δm};
● ⋉: the left semi-tensor product of matrices;
● 1n: the n-dimensional column vector of ones;
● 0m×n: the m×n matrix with zero entries;
● Sn: the n-th order symmetric group, i.e., a permutation group that is composed of all the permutations of n things;
● R: the set composed of all the real numbers.
Definition 2.1 ([7]). Let A∈Mm×n, B∈Mp×q. The left semi-tensor product of A and B is defined as
A⋉B=(A⊗Iαn)(B⊗Iαp), | (2.1) |
where ⊗ is the Kronecker product and α=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⋉B as AB.
Definition 2.2 ([7]). A swap matrix W[m,n]=(wIJij) is an mn×mn matrix, defined as follows:
Its rows and columns are labeled by double indices. The columns are arranged by the ordered multi-index Id(i1,i2;m,n), and the rows are arranged by the ordered multi-index Id(i2,i1;n,m). The element at the position with row index (I,J) and column index (i,j) is
wIJij={1, I=i and J=j,0, otherwise. |
When m=n, matrix W[m,n] is denoted by W[m].
Swap matrices have the following properties:
(Ik⊗W[k])(W[k]⊗Ik)(Ik⊗W[k])=(W[k]⊗Ik)(Ik⊗W[k])(W[k]⊗Ik). | (2.2) |
Definition 2.3. ([8]). A finite game is a triple G=(N,S,C), where
1) N={1,2,⋯,n} is the set of n players;
2) S=S1×S2×⋯×Sn is the set of strategy profiles, where Si={si1,si2,⋯,siki} is the set of strategies of player i;
3) C={c1,c2,⋯,cn} is the set of payoff functions, where ci:S→R is the payoff function of player i.
Denote the set composed of all the games above by G[n;k1,k2,⋯,kn]. When |Si|=k for each i=1,2,⋯,n, we denote it by G[n;k].
STP is a convenient tool for investigating games. Given a game G∈G[n;k], by using the STP method [9], each strategy xi can be written into a vector form xi∈Δk, and every payoff function ci can be expressed as
ci(x1,x2,⋯,xn)=Vci⋉nj=1xj,i=1,2,⋯,n, | (2.3) |
where ⋉nj=1xj∈Δkn is called the STP form of the strategy profile, and Vci is called the structure vector of ci.
Definition 2.4 ([10]). A game G∈G[n;k] is called a symmetric game if for any permutation σ∈Sn
ci(x1,x2,⋯,xn)=cσ(i)(xσ−1(1),xσ−1(2),⋯,xσ−1(n)) | (2.4) |
for any i=1,2,⋯,n.
Definition 3.1 ([4]). A game G∈G[n;k] is called a skew-symmetric game if for any permutation σ∈Sn
ci(x1,x2,⋯,xn)=sgn(σ)cσ(i)(xσ−1(1),xσ−1(2),⋯,xσ−1(n)) | (3.1) |
for any i=1,2,⋯,n.
The set composed of all the skew-symmetric games in G[n;k] is denoted as K[n;k].
Lemma 3.1 ([11]). The set of all the adjacent transpositions (r,r+1),1≤r≤n−1 is generator of the symmetric group Sn.
In the following, adjacent transpositions (r,r+1),1≤r≤n−1 are represented as μr.
Lemma 3.2. Consider G∈G[n;k]. For any σ1,σ2∈Sn, if σ1 and σ2 satisfy
ci(x1,x2,⋯,xn)=sgn(σ)cσ(i)(xσ−1(1),xσ−1(2),⋯,xσ−1(n)) | (3.2) |
for any i=1,2,⋯,n and any x1,x2,⋯,xn∈Δk, the compound permutation σ2∘σ1 also satisfies (3.2).
Proof. For any given xi∈Δk, i=1,2,…,n, let yi=xσ−11(i). Then
ci(x1,x2,⋯,xn)=sgn(σ1)cσ1(i)(xσ−11(1),xσ−11(2),⋯,xσ−11(n))=sgn(σ1)cσ1(i)(y1,y2,⋯,yn)=sgn(σ2)sgn(σ1)cσ2(σ1(i))(yσ−12(1),yσ−12(2),⋯,yσ−12(n))=sgn(σ2∘σ1)cσ2∘σ1(i)(xσ−11(σ−12(1)),xσ−11(σ−12(2)),⋯,xσ−11(σ−12(n))), |
which implies that σ2∘σ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∈G[n;k]. Game G is a skew-symmetric game if and only if
ci(x1,x2,⋯,xn)=−cμr(i)(xμr(1),xμr(2),⋯,xμr(n)) | (3.3) |
for any adjacent transposition μr, 1≤r≤n−1, i=1,2,⋯,n.
Proposition 3.1. Consider G∈G[n;k]. Game G is a skew-symmetric game if and only if
Vci=−Vcμr(i)Tμr,∀i=1,2,⋯,n,1≤r≤n−1, | (3.4) |
where Tμr=Ikr−1⊗W[k]⊗Ikn−r−1.
Proof. For any i=1,2,⋯,n and any 1≤r≤n−1, we have
cμr(i)(xμr(1),xμr(2),⋯,xμr(n))=Vcμr(i)xμr(1)xμr(2)⋯xμr(n)=Vcμr(i)(x1x2⋯xr−1)(xr+1xr)(xr+2⋯xn)=Vcμr(i)(x1x2⋯xr−1)(W[k]xrxr+1)(xr+2⋯xn)=Vcμr(i)Tμrx1x2⋯xn. | (3.5) |
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∈G[n;k]. Game G is a skew-symmetric game if and only if
[IknTμ1IknTμ2⋱⋱IknTμn−1Ikn+Tμ1Ikn+Tμ2⋮Ikn+Tμn−2](VG)T=0, | (3.6) |
where Tμr=Ikr−1⊗W[k]⊗Ikn−r−1, VG=[Vc1Vc2⋯Vcn], and the omitted elements in the coefficient matrix of (3.6) are all zeros.
Proof. Since (W[k])−1=W[k], we have (Tμr)−1=Tμr for any 1≤r≤n−1. Then, the equation Vci=−Vcμr(i)Tμr is equivalent to Vcμr(i)=−VciTμr. According to Proposition 3.1, G is a skew-symmetric game if and only if
[IknTμ1IknTμ2⋱⋱IknTμn−1B1B2⋱Bn−1Bn](VG)T=0, | (3.7) |
where
B1=[Ikn+Tμ2Ikn+Tμ3⋮Ikn+Tμn−1],B2=[Ikn+Tμ3Ikn+Tμ4⋮Ikn+Tμn−1], | (3.8) |
Bn−1=[Ikn+Tμ1Ikn+Tμ2⋮Ikn+Tμn−3],Bn=[Ikn+Tμ1Ikn+Tμ2⋮Ikn+Tμn−2], | (3.9) |
Br=[Ikn+Tμ1Ikn+Tμ2⋮Ikn+Tμr−2Ikn+Tμr+1Ikn+Tμr+2⋮Ikn+Tμn−1] (3≤r≤n−2). | (3.10) |
Let the coefficient matrix of equation (3.7) be
[A1A2B0(n−2)2kn×kn0(n−2)kn×(n−1)knBn] | (3.11) |
where
A1=[IknTμ1IknTμ2⋱⋱IknTμn−2Ikn], | (3.12) |
A2=[0(n−2)kn×knTμn−1], | (3.13) |
B=[B1B2⋱Bn−1]. | (3.14) |
Since A1 is an invertible matrix, we can perform the following row transformation on the coefficient matrix of (3.7)
[I(n−1)kn−BA−11I(n−2)(n−1)knI(n−2)kn][A1A2B0(n−2)2kn×kn0(n−2)kn×(n−1)knBn]=[A1A20(n−2)2kn×(n−1)kn−BA−11A20(n−2)kn×(n−1)knBn], | (3.15) |
where
−BA−11A2=[(−1)n−1B1Tμ1Tμ2⋯Tμn−1(−1)n−2B2Tμ2Tμ3⋯Tμn−1⋮−Bn−1Tμn−1]. | (3.16) |
Let
F1=In−2⊗(Tμn−1Tμn−2⋯Tμ1), |
Fr=In−3⊗(Tμn−1Tμn−2⋯Tμr),∀2≤r≤n−1. |
We perform the following row transformation on matrix −BA−11A2
[(−1)n−1F1(−1)n−2F2⋱−Fn](−BA−11A2)=[F1B1Tμ1Tμ2⋯Tμn−1F2B2Tμ2Tμ3⋯Tμn−1⋮Fn−1Bn−1Tμn−1]. | (3.17) |
Therefore, the equivalent form of (3.7) is as follows
[IknTμ1IknTμ2⋱⋱IknTμn−1F1B1Tμ1⋯Tμn−1F2B2Tμ2⋯Tμn−1⋮Fn−1Bn−1Tμn−1Bn](VG)T=0. | (3.18) |
From the property of W[k] shown in (2.2), it follows that
Tμn−1⋯Tμr+1TμrTμiTμrTμr+1⋯Tμn−1={Tμi∀1≤i≤r−2,Tμi−1∀r+1≤i≤n−1. | (3.19) |
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:
[Ikn+Tμ1Ikn+Tμ2⋮Ikn+Tμn−2]x=0, | (3.20) |
where x is the kn-dimensional unknown vector. Considering
[Ikn+Tμ1Ikn+Tμ2⋮Ikn+Tμn−2]=[Ikn+W[k]⊗Ikn−2Ikn+Ik⊗W[k]⊗Ikn−3⋮Ikn+Ikn−3⊗W[k]⊗Ik]=[Ikn−1+W[k]⊗Ikn−3Ikn−1+Ik⊗W[k]⊗Ikn−4⋮Ikn−1+Ikn−3⊗W[k]]⊗Ik, | (3.21) |
we only need to solve the linear equations as follows:
[Ikn−1+W[k]⊗Ikn−3Ikn−1+Ik⊗W[k]⊗Ikn−4⋮Ikn−1+Ikn−3⊗W[k]]x=0, | (3.22) |
where x is the kn−1-dimensional unknown vector. Let x=(xl1l2⋯ln−1) be arranged by the ordered multi-index Id(i1,i2,…,in−1;k,k,…,k), that is,
x=(x11⋯11,x11⋯12,…,x11⋯1k,x11⋯21,x11⋯22,…,x11⋯2k,…,xkk⋯k1,xkk⋯k2,…,xkk⋯kk)T. | (3.23) |
Then, by the property of W[k], vector x is a solution of (3.22) if and only if, for any 1≤l1,l2,⋯,ln−1≤k, the following equations hold:
xl1l2l3⋯ln−1=−xl2l1l3⋯ln−1,xl1l2l3⋯ln−1=−xl1l3l2⋯ln−1,⋮xl1l2l3⋯ln−1=−xl1⋯ln−3ln−1ln−2, | (3.24) |
i.e.
xl1l2⋯ln−1=sgn(π)xπ(l1l2⋯ln−1),∀π∈Sn−1. | (3.25) |
Thus, for any 1≤r≤n−2, if lr=lr+1, then
xl1⋯lrlrlr+2⋯ln−1=−xl1⋯lrlrlr+2⋯ln−1, |
that is,
xl1⋯lrlrlr+2⋯ln−1=0. |
Therefore, all the free variables of the linear equations (3.22) are
xl1l2⋯ln−1,∀1≤l1<l2<⋯<ln−1≤k, | (3.26) |
whose number is Cn−1k. That is, the dimension of the solution space of linear equations (3.22) is Cn−1k.
For every given repeatable combination s1s2⋯sn−1,(1≤s1≤s2≤⋯≤sn−1≤k), denote by Ps1s2⋯sn−1 the set composed of all the repeatable permutation of s1s2⋯sn−1. For example, P122={122,212,221}. For every given unrepeatable combination l1l2⋯ln−1,(1≤l1<l2<⋯<ln−1≤k), denote by Rl1l2⋯ln−1 the set composed of all the unrepeatable permutation of l1l2⋯ln−1. For example, R123={123,132,213,231,312,321}. Let
Q=(⋃1≤s1≤s2≤⋯≤sn−1≤kPs1s2⋯sn−1)∖(⋃1≤l1<l2<⋯<ln−1≤kRl1l2⋯ln−1). |
Then, any permutation in Q is a repeated permutation.
Lemma 3.4. For every given unrepeatable combination l1l2⋯ln−1(1≤l1<l2<⋯<ln−1≤k), define a vector θl1l2⋯ln−1=x with the form (3.23) by
xt1t2⋯tn−1={sgn(t1t2⋯tn−1), t1t2⋯tn−1∈Rl1l2⋯ln−1,0, otherwise. |
Then the set
{θl1l2⋯ln−1| 1≤l1<l2<⋯<ln−1≤k} | (3.27) |
is a basis of the solution space ˉXn−1 of (3.22). For every l1l2⋯ln−1 (1≤l1<l2<⋯<ln−1≤k), we define |Rl1l2⋯ln−1|−1 number of vectors νr1r2⋯rn−1l1l2⋯ln−1=x with r1r2⋯rn−1∈Rl1l2⋯ln−1 and r1r2⋯rn−1≠l1l2⋯ln−1 by
xt1t2⋯tn−1={1,t1t2⋯tn−1=l1l2⋯ln−1,−sgn(t1t2⋯tn−1),t1t2⋯tn−1=r1r2⋯rn−1,0,otherwise. |
We define |Q| number of vectors λh1h2⋯hn−1=x (h1h2⋯hn−1∈Q) by
xt1t2⋯tn−1={1, t1t2⋯tn−1=h1h2⋯hn−1,0, otherwise. |
Then the set of νr1r2⋯rn−1l1l2⋯ln−1 (1≤l1<l2<⋯<ln−1≤k,r1r2⋯rn−1∈Rl1l2⋯ln−1,r1r2⋯rn−1≠l1l2⋯ln−1) and λh1h2⋯hn−1 (h1h2⋯hn−1∈Q) is a basis of the orthogonal complementary space ˉX⊥n−1. Denote by MW the matrix whose columns are composed of a basis of subspace W. Then the linear system (3.22) is equivalent to MTˉX⊥n−1x=0.
Proof. For any 1≤l1<l2<⋯<ln−1≤k, sgn(l1l2⋯ln−1)=1. From the equivalent equations (3.25) and the free variables shown by (3.26), it follows that the set of θl1l2⋯ln−1 (1≤l1<l2<⋯<ln−1≤k) is a basis of the solution space ˉXn−1. By the construction of νr1r2⋯rn−1l1l2⋯ln−1 and λh1h2⋯hn−1, it is straightforward to see that each νr1r2⋯rn−1l1l2⋯ln−1 and each λh1h2⋯hn−1 are orthogonal to ˉXn−1. The total number of νr1r2⋯rn−1l1l2⋯ln−1 is
∑1≤l1<l2<⋯<ln−1≤k(|Rl1l2⋯ln−1|−1)=∑1≤l1<l2<⋯<ln−1≤k|Rl1l2⋯ln−1|−Cn−1k. |
The total number of λh1h2⋯hn−1 is
∑1≤s1≤s2≤⋯≤sn−1≤k|Ps1s2⋯sn−1|−∑1≤l1<l2<⋯<ln−1≤k|Rl1l2⋯ln−1| |
=kn−1−∑1≤l1<l2<⋯<ln−1≤k|Rl1l2⋯ln−1|. |
Then the total number of νr1r2⋯rn−1l1l2⋯ln−1 and λh1h2⋯hn−1 is kn−1−Cn−1k, i.e. kn−1−dim(ˉXn−1). Therefore, we conclude that the set of νr1r2⋯rn−1l1l2⋯ln−1 (1≤l1<l2<⋯<ln−1≤k,r1r2⋯rn−1∈Rl1l2⋯ln−1,r1r2⋯rn−1≠l1l2⋯ln−1) and λh1h2⋯hn−1 (h1h2⋯hn−1∈Q) is a basis of ˉX⊥n−1. Then, the linear system (3.22) is equivalent to MTˉX⊥n−1x=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 K[n;k].
Theorem 3.2. The dimension of the skew-symmetric game subspace K[n;k] is kCn−1k. A basis of K[n;k] is composed of the columns of matrix
[(−1)n−1W[kn−1,k](−1)n−2Ik⊗W[kn−2,k](−1)n−3Ik2⊗W[kn−3,k]⋮(−1)2Ikn−3⊗W[k2,k]−Ikn−2⊗W[k]Ikn](MˉXn−1⊗Ik), | (3.28) |
where MˉXn−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 K[n;k] are
[IknTμ1IknTμ2⋱⋱IknTμn−1MTˉX⊥n−1⊗Ik](VG)T=0, | (3.29) |
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 K[n;k] is kCn−1k. Using MˉXn−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:
[(−1)n−1Tμ1⋯Tμn−1(MˉXn−1⊗Ik)(−1)n−2Tμ2⋯Tμn−1(MˉXn−1⊗Ik)(−1)n−3Tμ3⋯Tμn−1(MˉXn−1⊗Ik)⋮−Tμn−1(MˉXn−1⊗Ik)MˉXn−1⊗Ik]. | (3.30) |
By the property of swap matrices shown in (2.2), we have
TμsTμs+1⋯Tμn−1=Iks−1⊗W[kn−s,k] |
for each 1≤s≤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 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 K[n;k].
Remark 3.1. The coefficient matrix of (3.29) has nkn−kCn−1k number of rows and each row has at most two nonzero elements. Since Cn−1k≤kn−1, (n−1)kn≤nkn−kCn−1k≤nkn. Therefore, the computational complexity is just O(nkn) due to
limn→∞nkn(n−1)kn=limn→∞nn−1=1. |
Definition 4.1 ([4]). A game G∈G[n;k] is called an asymmetric game if its structure vector
VG∈[S[n;k]⊕K[n;k]]⊥. |
The set of asymmetric games is denoted by E[n;k].
Lemma 4.1 ([6]). The dimension of the symmetric game subspace S[n;k] is kCn−1k+n−2. A basis of S[n;k] is composed of the columns of matrix
[W[kn−1,k]Ik⊗W[kn−2,k]Ik2⊗W[kn−3,k]⋮Ikn−2⊗W[k]Ikn](MXn−1⊗Ik), | (4.1) |
where Xn−1 is the solution space of linear equations
[Ikn−1−W[k]⊗Ikn−3Ikn−1−Ik⊗W[k]⊗Ikn−4⋮Ikn−1−Ikn−3⊗W[k]]x=0, | (4.2) |
and MXn−1 is the matrix composed of a basis of Xn−1.
Let
A=[W[kn−1,k]Ik⊗W[kn−2,k]Ik2⊗W[kn−3,k]⋮Ikn−2⊗W[k]Ikn](MXn−1⊗Ik), | (4.3) |
B=[(−1)n−1W[kn−1,k](−1)n−2Ik⊗W[kn−2,k](−1)n−3Ik2⊗W[kn−3,k]⋮−Ikn−2⊗W[k]Ikn](MˉXn−1⊗Ik). | (4.4) |
It is easy to check that
[W[kn−1,k]Ik⊗W[kn−2,k]Ik2⊗W[kn−3,k]⋮Ikn−2⊗W[k]Ikn]T[(−1)n−1W[kn−1,k](−1)n−2Ik⊗W[kn−2,k](−1)n−3Ik2⊗W[kn−3,k]⋮−Ikn−2⊗W[k]Ikn]=n∑i=1(Iki−1⊗W[k,kn−i])((−1)n−iIki−1⊗W[kn−i,k])=n∑i=1(−1)n−iIkn | (4.5) |
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 Xn−1 in [6], we have
ATB=(MTXn−1⊗Ik)(n∑i=1(−1)n−iIkn)(MˉXn−1⊗Ik)=n∑i=1(−1)n−i(MTXn−1MˉXn−1⊗Ik)=0p×q, | (4.6) |
where p=kCn−1k+n−2,q=kCn−1k. That is, S[n;k] and K[n;k] are orthogonal. Therefore,
G[n;k]=S[n;k]⊕K[n;k]⊕E[n;k]. | (4.7) |
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
[ATBT]x=0, | (4.8) |
where A and B are shown in (4.3) and (4.4), composed of the bases of S[n;k] and 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 E[n;k].
Construct matrices MXn−1 and MˉXn−1 as follows:
MXn−1=[η1η2⋯ηβηβ+1⋯ηα], MˉXn−1=[θ1θ2⋯θβ], | (4.9) |
where α=Cn−1k+n−2, β=Cn−1k, and
∀1≤i≤β,∃1≤l1<l2<⋯<ln−1≤k,s.t.ηi=ηl1l2⋯ln−1, θi=θl1l2⋯ln−1, | (4.10) |
∀β+1≤i≤α,∃1≤l1≤l2≤⋯≤ln−1≤k,andl1l2⋯ln−1∈Q,s.t.ηi=ηl1l2⋯ln−1. | (4.11) |
Let
x=[(x1)T, (x2)T,…,(xn)T]T∈Rnkn, |
where xj∈Rkn. Then, (4.8) is equivalent to
{n∑j=1[(ηTi+(−1)n−j+1θTi)⊗Ik](Ikj−1⊗W[k,kn−j ])xj=0,n∑j=1[(ηTi+(−1)n−jθTi)⊗Ik](Ikj−1⊗W[k,kn−j ])xj=0,(1≤i≤β) | (4.12) |
and
n∑j=1(ηTi⊗Ik)(Ikj−1⊗W[k,kn−j])xj=0(β+1≤i≤α). | (4.13) |
According to the construction of ηi=ηl1l2⋯ln−1 and θi=θl1l2⋯ln−1 (1≤i≤β), we conclude that (4.12) is equivalent to
{∑t1t2⋯tn−1 ∈R l1l2⋯ln−1sgn(t1t2⋯tn−1 )=1 ∑1≤j≤njisoddxjt1t2⋯tj−1 lntj+1⋯tn−1+∑t1t2⋯tn−1 ∈R l1l2⋯ln−1sgn(t1t2⋯tn−1 )=−1 ∑1≤j≤njisevenxjt1t2⋯tj−1 lntj+1⋯tn−1=0,∑t1t2⋯tn−1 ∈R l1l2⋯ln−1sgn(t1t2⋯tn−1 )=−1 ∑1≤j≤njisoddxjt1t2⋯tj−1 lntj+1⋯tn−1+∑t1t2⋯tn−1 ∈R l1l2⋯ln−1sgn(t1t2⋯tn−1 )=1 ∑1≤j≤njisevenxjt1t2⋯tj−1 lntj+1⋯tn−1=0 | (4.14) |
for any 1≤l1<l2<⋯<ln−1≤k, 1≤ln≤k, and (4.13) is equivalent to
∑t1t2⋯tn−1 ∈P l1⋯ln−1 ∑1≤j≤nxjt1t2⋯tj−1 lntj+1⋯tn−1=0 | (4.15) |
for any 1≤l1≤l2≤⋯≤ln−1≤k, l1l2⋯ln−1∈Q and any 1≤ln≤k.
We first construct two sets of solution vectors of (4.14):
{μl1l2⋯ln;1t1t2⋯tn−1; j}, {μl1l2⋯ln;−1t1t2⋯tn−1; j}. |
If n is odd, let
μl1l2⋯ln;1t1t2⋯tn−1;j=[(x1)T, (x2)T,…,(xn)T]T∈Rnkn |
with each xp=(xpr1r2⋯rn),
xpr1r2⋯rn={1,p=n,r1r2⋯rn=l1l2⋯ln,−1,p=j,r1r2⋯rn=t1t2⋯tj−1lntj⋯tn−1,0,otherwise, | (4.16) |
where 1≤l1<l2<⋯<ln−1≤k, 1≤ln≤k, t1t2⋯tn−1∈Rl1⋯ln−1, 1≤j≤n satisfy one of following conditions:
(i) j=n, t1t2⋯tn−1≠l1l2⋯ln−1 and (−1)j+1=sgn(t1t2⋯tn−1),
(ii) j≠n, (−1)j+1=sgn(t1t2⋯tn−1).
Similarly, let
μl1l2⋯ln;−1t1t2⋯tn−1;j=[(x1)T, (x2)T,…,(xn)T]T∈Rnkn, |
with each xp=(xpr1r2⋯rn),
xpr1r2⋯rn={1,p=n,r1r2⋯rn=˜l1˜l2⋯˜ln−1ln,−1,p=j,r1r2⋯rn=t1t2⋯tj−1lntj⋯tn−1,0,otherwise, | (4.17) |
where t1t2⋯tn−1 and j satisfy one of the following conditions:
(i) j=n, t1t2⋯tn−1≠˜l1˜l2⋯˜ln−1=l2l1l3⋯ln−1 and (−1)j=sgn(t1⋯tn−1),
(ii) j≠n, (−1)j=sgn(t1t2⋯tn−1).
If n is even, let
μl1l2⋯ln;1t1t2⋯tn−1;j=[(x1)T, (x2)T,…,(xn)T]T∈Rnkn, |
with
xpr1r2⋯rn={1,p=n,r1r2⋯rn=l1l2⋯ln,−1,p=j,r1r2⋯rn=t1t2⋯tj−1lntj⋯tn−1,0,otherwise, | (4.18) |
where 1≤l1<l2<⋯<ln−1≤k, 1≤ln≤k, t1t2⋯tn−1∈Rl1l2⋯ln−1, 1≤j≤n satisfying one of the following conditions,
(i) j=n, t1t2⋯tn−1≠l1l2⋯ln−1 and (−1)j=sgn(t1t2⋯tn−1),
(ii) j≠n, (−1)j=sgn(t1t2⋯tn−1),
Similarly, let
μl1l2⋯ln;−1t1t2⋯tn−1;j=[(x1)T, (x2)T,…,(xn)T]T∈Rnkn, |
with
xpr1⋯rn={1,p=n,r1r2⋯rn=˜l1˜l2⋯˜ln−1ln,−1,p=j,r1r2⋯rn=t1t2⋯tj−1lntj⋯tn−1,0,otherwise, | (4.19) |
where t1t2⋯tn−1 and j satisfy one of following conditions:
(i) j=n, t1t2⋯tn−1≠˜l1˜l2⋯˜ln−1=l2l1l3⋯ln−1 and (−1)j+1=sgn(t1t2⋯tn−1),
(ii) j≠n, (−1)j+1=sgn(t1t2⋯tn−1).
Then we construct a set of solution vectors of (4.15):
{γl1l2⋯lnt1t2⋯tn−1;j}. |
Let
γl1l2⋯lnt1t2⋯tn−1;j=[(x1)T, (x2)T,…,(xn)T]T∈Rnkn |
with
xpr1⋯rn={1,p=n,r1r2⋯rn=l1l2⋯ln,−1,p=j,r1r2⋯rn=t1t2⋯tj−1lntj⋯tn−1,0,otherwise, | (4.20) |
where 1≤l1≤l2≤⋯≤ln−1≤k, l1l2⋯ln−1∈Q, 1≤ln≤k, t1t2⋯tn−1∈Pl1l2⋯ln−1, 1≤j≤n satisfy one of the following conditions:
(i) j=n, t1t2⋯tn−1≠l1l2⋯ln−1,
(ii) j≠n.
Theorem 4.1. The sets {μl1l2⋯ln;1t1t2⋯tn−1;j}, {μl1l2⋯ln;−1t1t2⋯tn−1;j} and {γl1l2⋯lnt1t2⋯tn−1;j} form a basis of the asymmetric game subspace E[n;k].
Proof. According to the construction method of μl1l2⋯ln;1t1t2⋯tn−1;j, μl1l2⋯ln;−1t1t2⋯tn−1;j and γl1l2⋯lnt1t2⋯tn−1;j, all the vectors in {μl1l2⋯ln;1t1t2⋯tn−1;j}, {μl1l2⋯ln;−1t1t2⋯tn−1;j} and {γl1l2⋯lnt1t2⋯tn−1;j} are linearly independent and satisfy both (4.14) and (4.15). Moreover, we have
|{μl1l2⋯ln;1t1t2⋯tn−1;j}|=|{μl1l2⋯ln;−1t1t2⋯tn−1;j}|=∑1≤l1<l2<⋯<ln−1≤kk(n∣Rl1l2⋯ln−1∣2−1)=∑1≤l1<l2<⋯<ln−1≤kk(n∣Rl1l2⋯ln−1∣2)−kCn−1k. |
|{γl1l2⋯lnt1t2⋯tn−1;j}|=∑1≤l1≤l2≤⋯≤ln−1≤kl1l2⋯ln−1∈Qk(n∣Pl1l2⋯ln−1∣−1)=∑1≤l1≤l2≤⋯≤ln−1≤kl1l2⋯ln−1∈Qk(n∣Pl1l2⋯ln−1∣)−(kCn−1k+n−2−kCn−1k). |
So,
∣{μl1l2⋯ln;1t1t2⋯tn−1; j}∣+∣{μl1l2⋯ln;1t1t2⋯tn−1; j}∣+∣{γl1l2⋯lnt1t2⋯tn−1; j}∣=2∑1≤l1<l2<⋯<ln−1≤kk(n∣Rl1l2⋯ln−1∣2)−2kCn−1k+∑1≤l1≤l2≤⋯≤ln−1≤kl1l2⋯ln−1 ∈Qk(n∣Pl1l2⋯ln−1∣)−(kCn−1k+n−2−kCn−1k)=∑1≤l1<l2<⋯<ln−1≤kk(n∣Rl1l2⋯ln−1∣)+∑1≤l1≤l2≤⋯≤ln−1≤kl1l2⋯ln−1 ∈Qk(n∣Pl1l2⋯ln−1∣)−kCn−1k+n−2−kCn−1k=nkn−kCn−1k+n−2−kCn−1k=nkn−dim(S[n;k])−dim(K[n;k]). |
Therefore, {μl1l2⋯ln;1t1t2⋯tn−1 ; j}, {μl1l2⋯ln;1t1t2⋯tn−1 ; j} and {γl1l2⋯lnt1t2⋯tn−1 ; j} form a basis of E[n;k].
Remark 4.1. We have given the bases of skew-symmetric game subspace K[n;k] and asymmetric game subspace E[n;k]. In our recently published paper [6], a basis of symmetric game subspace S[n;k] has also been given. Let the bases of S[n;k], K[n;k], E[n;k] be {α1,α2,⋯,αs}, {β1,β2,⋯,βt}, {γ1,γ2,⋯,γl} respectively, where s=kCn−1k+n−2, t=kCn−1k, l=nkn−kCn−1k+n−2−kCn−1k. For any G∈G[n;k], there are real numbers p1,⋯,ps,q1,⋯,qt,r1,⋯,rl such that
VG=p1α1+⋯+psαs+q1β1+⋯+ptβt+r1γ1+⋯+rlγl. |
Thus, [p1,⋯,ps,q1,⋯,qt,r1,⋯,rl]T is a solution of equation
[αT1⋯αTsβT1⋯βTtγT1⋯γTl]x=VTG. | (4.21) |
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!nkn).
Example 4.1. Consider G[3;2]. If 1≤l1<l2≤2, we have l1=1,l2=2. Then MˉX2=[0, 1, −1 0]T. If 1≤l1≤l2≤2, then l1l2=11, l1l2=12 or l1l2=22. Therefore,
MX2=[100010010001]. |
According to (3.28), a basis of K[3;2] is composed of the columns of matrix
[W[22,2]−I2⊗W[2,2]I23](MˉX2⊗I2) | (4.22) |
According to (4.1), a basis of S[3;2] is composed of the columns of matrix
[W[22,2]I2⊗W[2,2]I23](MX2⊗I2) | (4.23) |
According (4.18)-(4.20), the basis of E[3;2] and all non-zero elements in each vector are as follows:
μ121,112;1,x3121=1,x1112=−1; |
μ121,121;2,x3121=1,x2211=−1; |
μ122,112;1,x3122=1,x1212=−1; |
μ122,121;2,x3122=1,x2221=−1; |
μ121,−112;2,x3211=1,x2112=−1; |
μ121,−121;1,x3211=1,x1121=−1; |
μ122,−112;2,x3212=1,x2122=−1; |
μ122,−121;1,x3212=1,x1221=−1; |
γ11111;1,x3111=1,x1111=−1; |
γ11111;2,x3111=1,x2111=−1; |
γ11211;1,x3112=1,x1211=−1; |
γ11211;2,x3112=1,x2121=−1; |
γ22122;1,x3221=1,x1122=−1; |
γ22122;2,x3221=1,x2212=−1; |
γ22222;1,x3222=1,x1222=−1; |
γ22222;2,x3222=1,x2222=−1. |
It is easy to verify that the basis of E[3;2] are orthogonal to the columns of the matrices shown in (4.22) and (4.23).
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 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.
The research work is supported by NNSF of China under Grant 62103194, Natural Science Foundation of Shandong Province of China under Grant ZR2020QA028.
The authors declare no conflict of interest.
[1] |
H. W. Kuhn, A. W. Tucker, John von Neumannis work in the theory of games and mathematical economics, B. Am. Math. Soc., 64 (1958), 100–122. https://doi.org/10.1090/S0002-9904-1958-10209-8 doi: 10.1090/S0002-9904-1958-10209-8
![]() |
[2] |
J. V. Neumann, Zur theorie der gesellschaftsspiele, Math. Ann., 100 (1928), 295–320. https://doi.org/10.1007/BF01448847 doi: 10.1007/BF01448847
![]() |
[3] |
D. Cheng, T. Liu, Linear representation of symmetric games, IET Control Theory & Applications, 11 (2017), 3278–3287. https://doi.org/10.1049/iet-cta.2017.0620 doi: 10.1049/iet-cta.2017.0620
![]() |
[4] |
Y. Hao, D. Cheng, On skew-symmetric games, Journal of the Franklin Institute, 355 (2018), 3196–3220. https://doi.org/10.1016/j.jfranklin.2018.02.015 doi: 10.1016/j.jfranklin.2018.02.015
![]() |
[5] |
C. Li, F. He, T. Liu, D. Cheng, Symmetry-based decomposition of finite games, Sci. China Inform. Sci., 62 (2019), 1–13. https://doi.org/10.1007/s11432-017-9411-0 doi: 10.1007/s11432-017-9411-0
![]() |
[6] |
L. Wang, X. Liu, T. Li, J. Zhu, The minimum number of discriminant equations for a symmetric game, IET Control Theory & Applications, (2022). https://doi.org/10.1049/cth2.12345 (in press) doi: 10.1049/cth2.12345
![]() |
[7] | D. Cheng, H. Qi, Z. Li, Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach, London: Springer Science & Business Media, 2010. |
[8] |
D. Monderer, L. S. Shapley, Potential games, Game. Econ. Behav., 14 (1996), 124–143. https://doi.org/10.1006/game.1996.0044 doi: 10.1006/game.1996.0044
![]() |
[9] |
D. Cheng, On finite potential games, Automatica, 50 (2014), 1793–1801. https://doi.org/10.1016/j.automatica.2014.05.005 doi: 10.1016/j.automatica.2014.05.005
![]() |
[10] | O. Morgenstern, J. V. Neumann, Theory of Games and Economic Behavior, Princeton: Princeton university press, 2007. https://doi.org/10.1515/9781400829460 |
[11] |
S. M. Johnson, Generation of permutations by adjacent transposition, Math. Comput., 17 (1963), 282–285. https://doi.org/10.2307/2003846 doi: 10.2307/2003846
![]() |
[12] |
D. Cheng, T. Liu, From Boolean game to potential game, Automatica, 96 (2018), 51–60. https://doi.org/10.1016/j.automatica.2018.06.028 doi: 10.1016/j.automatica.2018.06.028
![]() |
[13] |
S. Fu, Y. Pan, J. Feng, J. Zhao, Strategy optimisation for coupled evolutionary public good games with threshold, Int. J. Control, 95 (2022), 562–571. https://doi.org/10.1080/00207179.2020.1803411 doi: 10.1080/00207179.2020.1803411
![]() |
[14] |
H. Li, X. Ding, Q. Yang, Y. Zhou, Algebraic formulation and Nash equilibrium of competitive diffusion games, Dyn. Games Appl., 8 (2018), 423–433. https://doi.org/10.1007/s13235-017-0228-4 doi: 10.1007/s13235-017-0228-4
![]() |
[15] |
H. Li, S. Wang, A. Liu, M. Xia, Simplification of Shapley value for cooperative games via minimum carrier, Control Theory and Technology, 19 (2021), 157–169. https://doi.org/10.1007/s11768-020-00003-1 doi: 10.1007/s11768-020-00003-1
![]() |
1. | Tiantian Mu, Jun‐e Feng, A survey on applications of the semi‐tensor product method in Boolean control networks with time delays, 2024, 6, 2577-8196, 10.1002/eng2.12760 | |
2. | Zhiqiang Hang, Xiaolin Wang, Fangfei Li, Yi-ang Ren, Haitao Li, Learning-based DoS attack game strategy over multi-process systems, 2024, 4, 2767-8946, 424, 10.3934/mmc.2024034 |