On Matrix Method of Symmetric Games

Game theory studies mathematical models of strategic interactions among rational agents. Modern game theory was formally established after John von Neumann proved the basic principles of game theory [19, 25], which has been paid wide attention and applied to many fields such as economics, biology, finance, computer science and so on. The concept of symmetric game was first proposed by von Neumann in [25], and the details can be seen in [27], which is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. In other words, a symmetric game means that all players have the same set of strategies and fair payoffs. In real world, symmetric games are universal. For example, the well-known games rock-paper-scissors, prisoner’s dilemma are symmetric games. Moreover, the importance of symmetric game lies in the discussion on existence of Nash equilibria [16, 23]. Therefore, how to check whether a game is a symmetric game is an important problem. In [4], symmetric games are classified into three types, including ordinary symmetric games, renaming symmetric games and name-irrelevant games. The symmetric games discussed in this paper are actually ordinary symmetric games.

In the past decade, Cheng and his collaborators applied the semi-tensor product (STP) of matrices to game theory [11, 13], which enable a game to be expressed as a linear representation. Based on the linear representations of games, some problems about potential games, networked games and evolutionary games have been solved [6, 13, 21]. It should be noted that the matrix method based on STP is also powerful for symmetric games. In [8], algebraic conditions for symmetric games have been proposed by using the linear representation of symmetric group in structure vectors. Compared with the results in [8], some simpler algebraic conditions for symmetric games are given in [9] via some STP operations. Furthermore, for Boolean games, a group of bases of the symmetric game subspace is constructed via a recursive procedure in [9]. For general finite games, construction algorithms of bases of symmetric game subspaces are given in [15] and [20], respectively. It should be noted that the concept of strategy multiplicity vector and an equivalent condition for symmetric games in [4] play an important role in [9] [15] and [20].

In this paper, we still use the matrix method based on STP to investigate symmetric games. However, due to the introduction of adjacent transpositions, some new equivalent conditions for symmetric games are derived, and the proof is greatly simplified via a purely algebraic approach without using the concept of strategy multiplicity vector [4]. Based on our results, a group of bases of the symmetric game subspace can be easily constructed, and the testing equations with the minimum number can be concretely determined.

The rest of this paper is organized as follows: Section 2 gives some preliminaries and problem statement. In Section 3, the main results are presented. Section 4 is a brief conclusion.

In this section, we give some necessary preliminaries and problem statement. Firstly, we list the following notations.

• $\bullet$

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

• $\bullet$

  $\delta_{k}^{i}:$ the $i$-th column of $I_{k}$;

• $\bullet$

  $\Delta_{k}:=\{\delta_{k}^{i}:i=1,2,\cdots,k\}$;

• $\bullet$

  $\delta_{k}[i_{1}~{}i_{2}~{}\cdots i_{n}]:=[\delta_{k}^{i_{1}}~{}\delta_{k}^{i_{2}}~{}\cdots~{}\delta_{k}^{i_{n}}]$;

• $\bullet$

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

• $\bullet$

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

• $\bullet$

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

• $\bullet$

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

• $\bullet$

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

• $\bullet$

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

• $\bullet$

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

If $n$ and $p$ in Definition 2 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$.

Given a game $G\in\mathcal{G}_{[n;k]}$, by using the semi-tensor product method [6], one can write each strategy $x_{i}$ into a vector form $x_{i}\in\Delta_{k}$, and express every payoff function $c_{i}$ as

where $\ltimes_{j=1}^{n}x_{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}$.

For example, letting $m=2$, $n=3$, we get the swap matrix

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

By Lemma 2, one can easily get

This section will present a simple matrix approach to test symmetric games.

By Definition 4, to test whether $G\in\mathcal{G}_{[n;k]}$ is symmetric, it seems that (4) should be checked for every permutation $\sigma$. But actually it is only needed to check (4) for the permutations of a generator of $G\in\mathcal{G}_{[n;k]}$. This is due to the fact that the compound permutation $\sigma_{2}\circ\sigma_{1}$ satisfies (4) if both permutations $\sigma_{1}$ and $\sigma_{2}$ satisfy (4). For the readability, we write the demonstration as follows:

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 (4).

In the following, we will use $\mu_{r}$ to represent the adjacent transposition $(r,r+1)$. From Definition 4 and Lemma 2, the following lemma follows:

Now we can use the semi-tensor product method to investigate symmetric games.

By (2), we rewrite the right hand side of (6) into the matrix form as follows:

From (2) and (7), it follows that (6) is equivalent to(5). Therefore, by Lemma 2, the proposition is proved. $\blacksquare$ Now, we present our main result on testing symmetric games. For the readability of this paper and without loss of generality, we first consider the case of $n=4$.

First of all, by the properties of Kronecker product and the property (2) of swap matrices, we have the properties of $T_{\mu_{i}}$ as follows:

We write (6) of Proposition 1 for every $r=1,2,3$ as follows:

Let

Then Eqs. (12)-(14) can be rewritten as

By using an elementary row transformation, one can easily get the equivalent form of (17) as follows:

where

Applying a group of elementary row transformations to $\tilde{A}_{3}$ yields

Using the properties of $T_{\mu_{i}}$ shown by (LABEL:eqn12), we have

So, (18) is equivalent to (8). The proof is complete. $\blacksquare$

By Theorem 1, symmetric games have been clearly described by a simple form. Then the problem is how to simply determine the dimension and bases of the symmetric game subspace. From (8), we see that the key to solve the problem is the following linear equations:

where $x$ is the $k^{3}$-dimensional unknown vector. For the linear equation (25), we give a lemma as follows:

Let $x=(x_{pqr})$ be a $k^{3}$-dimensional column vector arranged by the ordered multi-index Id$(i_{1},i_{2},i_{3};k,k,k)$, that is,

Then, by the property of $W_{[k]}$, $x$ is a solution of (25) if and only if

which is equivalent to

So all the free variables of the linear equations are

whose number is $C_{k+2}^{3}$ by Theorem 2.5.1 of [2] on counting number of combinations of a multiset. $\Box$

The proof of Lemma 4 actually provides an effective approach to construct a group of bases of the solution space $\mathcal{X}_{3}$ of (25). Based on the bases, we also can easily get the minimum number of equivalent equations to (25). See the details as follows:

For every given repeatable combination $pqr$ $(1\leq p\leq q\leq r\leq k)$, denote by $P_{pqr}$ the set composed of all the repeatable permutation of $pqr$. For example, $P_{111}=\{111\}$, $P_{112}=\{112,121,211\}$, $P_{123}=\{123,231,312,132,321,213\}$.

From the equivalent equations (28) and the free variables shown by (29), it follows that the set of $\eta^{pqr}$ $(1\leq p\leq q\leq r\leq k)$ is a group of bases of the solution space $\mathcal{X}_{3}$. By the construction of $\zeta_{pqr}^{uvw}$, it is straightforward to see that each $\zeta_{pqr}^{uvw}$ is orthogonal to $\mathcal{X}_{3}$. Since the total number of $\zeta_{pqr}^{uvw}$ is $\sum_{1\leq p\leq q\leq r\leq k}(|P_{pqr}|-1)=\sum_{1\leq p\leq q\leq r\leq k}|P_{pqr}|-C_{k+2}^{3}=k^{3}-C_{k+2}^{3}=k^{3}-\mbox{dim}(\mathcal{X}_{3})$, we conclude that the set of $\zeta_{pqr}^{uvw}$ $(uvw\in P_{pqr},uvw\neq{pqr})$ is a group of bases of $\mathcal{X}_{3}^{\perp}$. For example, when $k=2$, we have

Based on Theorem 1, Lemma 4 and Lemma lem6, one can investigate the dimension and bases of the symmetric game subspace.

It is easy to see that

By Theorem 1 and Lemma 4, we can easily get the dimension of the symmetric game subspace $\mathcal{S}_{[4;k]}$ is $kC_{k+2}^{3}$. Using $M_{\mathcal{X}_{3}}$ composed of the bases of (25), we get a group of bases of the solution space of (8):

By the properties of swap matrices, we have that

So, (33) is just (30). Moreover, from (32) and Lemma 5, it follows that (8) is equivalent to (31). Since the coefficient matrix of (31) has a full row rank, the testing equations have the minimum number. $\blacksquare$

In the rest of this paper, we consider the general finite game $G\in\mathcal{G}_{[n;k]}$.

According to Proposition 1, $G\in\mathcal{G}_{[n;k]}$ is a symmetric game if and only if

where

Let $F_{1}=I_{n-2}\otimes(T_{\mu_{n-1}}T_{\mu_{n-2}}\cdots T_{\mu_{1}})$ and $F_{r}=I_{n-3}\otimes(T_{\mu_{n-1}}T_{\mu_{n-2}}\cdots T_{\mu_{r}})$ for every $2\leq r\leq n-1$. Then a series of elementary row transformations to $(\ref{eqn37})$ results in