Necessary and Sufficient Condition for the Existence of Zero-Determinant Strategies in Repeated Games

Although ZD strategies have been found in several stage games, such as the prisoner’s dilemma game [1], the public goods game [3, 4], the continuous donation game [5], a two-player two-action asymmetric game [21], and two-player symmetric potential games [20], the condition of the existence of ZD strategies has not been clear. In this section, we provide a necessary and sufficient condition for the existence of ZD strategies.

Proof. (Necessity) If a ZD strategy of player $j$ exists, then the Press-Dyson vectors satisfy

$\displaystyle\sum_{\sigma_{j}}c_{\sigma_{j}}\hat{T}_{j}\left(\sigma_{j}|\bm{\sigma}^{\prime}\right)$

$\displaystyle=$

$\displaystyle\sum_{k=0}^{N}\alpha_{k}s_{k}\left(\bm{\sigma}^{\prime}\right)\quad\left(\forall\bm{\sigma}^{\prime}\right)$

(15)

with some nontrivial coefficients $\left\{\alpha_{k}\right\}$ and $\left\{c_{\sigma_{j}}\right\}$ and Eq. (15) is not identically zero. Below we write $B\left(\bm{\sigma}\right):=\sum_{k=0}^{N}\alpha_{k}s_{k}\left(\bm{\sigma}\right)$ $(\forall\bm{\sigma})$. By using Eq. (5), this can be written as

$\displaystyle B\left(\bm{\sigma}^{\prime}\right)$

$\displaystyle=$

$\displaystyle\sum_{\sigma_{j}}\left(c_{\sigma_{j}}-c_{\mathrm{max}}\right)\hat{T}_{j}\left(\sigma_{j}|\bm{\sigma}^{\prime}\right)$

(16)

and

$\displaystyle B\left(\bm{\sigma}^{\prime}\right)$

$\displaystyle=$

$\displaystyle\sum_{\sigma_{j}}\left(c_{\sigma_{j}}-c_{\mathrm{min}}\right)\hat{T}_{j}\left(\sigma_{j}|\bm{\sigma}^{\prime}\right),$

(17)

where we have defined

	$\displaystyle c_{\mathrm{max}}$	$\displaystyle:=$	$\displaystyle\max_{\sigma_{j}}c_{\sigma_{j}}$		(18)
	$\displaystyle c_{\mathrm{min}}$	$\displaystyle:=$	$\displaystyle\min_{\sigma_{j}}c_{\sigma_{j}}.$		(19)

We also introduce

	$\displaystyle\sigma_{\mathrm{max}}$	$\displaystyle:=$	$\displaystyle\arg\max_{\sigma_{j}}c_{\sigma_{j}}$		(20)
	$\displaystyle\sigma_{\mathrm{min}}$	$\displaystyle:=$	$\displaystyle\arg\min_{\sigma_{j}}c_{\sigma_{j}},$		(21)

where ties may be broken arbitrarily. It should also be noted that $\sigma_{\mathrm{max}}\neq\sigma_{\mathrm{min}}$, because the left-hand-side of Eq. (15) becomes $0$ if $\sigma_{\mathrm{max}}=\sigma_{\mathrm{min}}$ and therefore $c_{\mathrm{max}}=c_{\mathrm{min}}$, which contradicts with the definition of ZD strategies. Then, by using the property (8), we obtain

	$\displaystyle B\left(\sigma_{\mathrm{max}},\sigma_{-j}^{\prime}\right)$	$\displaystyle=$	$\displaystyle\sum_{\sigma_{j}}\left(c_{\sigma_{j}}-c_{\mathrm{max}}\right)\hat{T}_{j}\left(\sigma_{j}|\sigma_{\mathrm{max}},\sigma_{-j}^{\prime}\right)$		(22)
		$\displaystyle\leq$	$\displaystyle 0\quad\left(\forall\sigma_{-j}^{\prime}\right)$

and

	$\displaystyle B\left(\sigma_{\mathrm{min}},\sigma_{-j}^{\prime}\right)$	$\displaystyle=$	$\displaystyle\sum_{\sigma_{j}}\left(c_{\sigma_{j}}-c_{\mathrm{min}}\right)\hat{T}_{j}\left(\sigma_{j}|\sigma_{\mathrm{min}},\sigma_{-j}^{\prime}\right)$		(23)
		$\displaystyle\geq$	$\displaystyle 0\quad\left(\forall\sigma_{-j}^{\prime}\right).$

Therefore, the ZD strategy satisfies the condition (14) with $\overline{\sigma}_{j}=\sigma_{\mathrm{max}}$ and $\underline{\sigma}_{j}=\sigma_{\mathrm{min}}$.

(Sufficiency) If there exist some nontrivial coefficients $\{\alpha_{k}\}_{k=0}^{N}$ and two different actions $\overline{\sigma}_{j}$ and $\underline{\sigma}_{j}$ of player $j$ satisfying the condition (14), we can construct a ZD strategy as follows. We first introduce $M:=\prod_{k=1}^{N}M_{k}$ and a vector notation of a $M$-component quantity $D(\bm{\sigma})\in\mathbb{R}$ by $\bm{D}:=\left(D(\bm{\sigma})\right)_{\bm{\sigma}\in\mathcal{A}}\in\mathbb{R}^{M}$. We also introduce vectors obtained from $\bm{D}$

$\displaystyle\left[\bm{D}\right]_{\sigma_{j},d}$

$\displaystyle:=$

$\displaystyle\left(D(\bm{\sigma}^{\prime})\mathbb{I}(dD(\bm{\sigma}^{\prime})>0)\mathbb{I}(\sigma_{j}^{\prime}=\sigma_{j})\right)_{\bm{\sigma}^{\prime}\in\mathcal{A}}\quad\left(\sigma_{j}\in A_{j},d\in\{+,-\}\right),$

where $\mathbb{I}(\cdots)$ is an indicator function which returns $1$ if $\cdots$ holds, and $0$ otherwise. By the definition, any $M$-component vectors $\bm{D}$ can be decomposed into linearly independent vectors

$\displaystyle\bm{D}$

$\displaystyle=$

$\displaystyle\sum_{\sigma_{j}}\sum_{d=+,-}\left[\bm{D}\right]_{\sigma_{j},d}.$

(25)

For the quantity $\bm{B}=\sum_{k=0}^{N}\alpha_{k}\bm{s}_{k}$, our assumption (14) leads to

$\displaystyle\bm{B}$

$\displaystyle=$

$\displaystyle\sum_{\sigma_{j}\neq\overline{\sigma}_{j},\underline{\sigma}_{j}}\sum_{d=+,-}\left[\bm{B}\right]_{\sigma_{j},d}+\left[\bm{B}\right]_{\overline{\sigma}_{j},-}+\left[\bm{B}\right]_{\underline{\sigma}_{j},+}.$

(26)

We also collectively write the Press-Dyson vectors of player $j$ by $\hat{\bm{T}}_{j}\left(\sigma_{j}\right):=\left(\hat{T}_{j}\left(\sigma_{j}|\bm{\sigma}^{\prime}\right)\right)_{\bm{\sigma}^{\prime}\in\mathcal{A}}$. Below we construct ZD strategies for the case $M_{j}>2$ and the case $M_{j}=2$ separately. (Because of the existence of two different actions $\overline{\sigma}_{j},\underline{\sigma}_{j}$, $M_{j}$ must be greater than $1$.)

1. (i)

   $M_{j}>2$
   For the case, we set a strategy of player $j$ as

   	$\displaystyle\hat{\bm{T}}_{j}\left(\overline{\sigma}_{j}\right)$	$\displaystyle=$	$\displaystyle\frac{1}{W}\left(\sum_{\sigma_{j}\neq\overline{\sigma}_{j},\underline{\sigma}_{j}}\left[\bm{B}\right]_{\sigma_{j},+}+\left[\bm{B}\right]_{\overline{\sigma}_{j},-}\right)$
   	$\displaystyle\hat{\bm{T}}_{j}\left(\underline{\sigma}_{j}\right)$	$\displaystyle=$	$\displaystyle-\frac{1}{W}\left(\sum_{\sigma_{j}\neq\overline{\sigma}_{j},\underline{\sigma}_{j}}\left[\bm{B}\right]_{\sigma_{j},-}+\left[\bm{B}\right]_{\underline{\sigma}_{j},+}\right)$
   	$\displaystyle\hat{\bm{T}}_{j}\left(\sigma_{j}\right)$	$\displaystyle=$	$\displaystyle\frac{1}{W}\left(-\left[\bm{B}\right]_{\sigma_{j},+}+\left[\bm{B}\right]_{\sigma_{j},-}-\frac{1}{M_{j}-2}\left[\bm{B}\right]_{\overline{\sigma}_{j},-}\right.$		(27)
   			$\displaystyle\qquad\left.+\frac{1}{M_{j}-2}\left[\bm{B}\right]_{\underline{\sigma}_{j},+}\right)\quad\left(\sigma_{j}\neq\overline{\sigma}_{j},\underline{\sigma}_{j}\right),$

   where we have defined

   $\displaystyle W$

   $\displaystyle:=$

   $\displaystyle\max_{\bm{\sigma}\in\mathcal{A}}\left|B(\bm{\sigma})\right|\neq 0.$

   (28)

   We can easily check that these vectors indeed satisfy the condition of strategies (8) and (9). In addition, the condition (5) is also satisfied because

   $\displaystyle\sum_{\sigma_{j}}\hat{\bm{T}}_{j}\left(\sigma_{j}\right)$

   $\displaystyle=$

   $\displaystyle\bm{0}.$

   (29)

   Furthermore, the strategy (27) satisfies

   $\displaystyle\hat{\bm{T}}_{j}\left(\overline{\sigma}_{j}\right)-\hat{\bm{T}}_{j}\left(\underline{\sigma}_{j}\right)$

   $\displaystyle=$

   $\displaystyle\frac{1}{W}\bm{B},$

   (30)

   where we have used Eq. (26). Therefore, the strategy (27) is a ZD strategy.

2. (ii)

   $M_{j}=2$
   For the case, we remark that the two actions of player $j$ are $\overline{\sigma}_{j}$ and $\underline{\sigma}_{j}$. We set a strategy of player $j$ as

   	$\displaystyle\hat{\bm{T}}_{j}\left(\overline{\sigma}_{j}\right)$	$\displaystyle=$	$\displaystyle\frac{1}{W}\left(\left[\bm{B}\right]_{\overline{\sigma}_{j},-}+\left[\bm{B}\right]_{\underline{\sigma}_{j},+}\right)$
   	$\displaystyle\hat{\bm{T}}_{j}\left(\underline{\sigma}_{j}\right)$	$\displaystyle=$	$\displaystyle-\hat{\bm{T}}_{j}\left(\overline{\sigma}_{j}\right),$		(31)

   where $W$ is defined by Eq. (28). We can easily check that these vectors indeed satisfy the condition of strategies (5), (8), (9). In addition, the strategy (31) satisfies

   $\displaystyle\hat{\bm{T}}_{j}\left(\overline{\sigma}_{j}\right)$

   $\displaystyle=$

   $\displaystyle\frac{1}{W}\bm{B},$

   (32)

   where we have used Eq. (26). Therefore, the strategy (31) is a ZD strategy.

$\Box$

In this subsection, we construct a ZD strategy for the case of the repeated prisoner’s dilemma game. The prisoner’s dilemma game is a two-player two-action symmetric game with following payoffs:

	$\displaystyle\bm{s}_{1}$	$\displaystyle:=$	$\displaystyle\left(s_{1}(1,1),s_{1}(1,2),s_{1}(2,1),s_{1}(2,2)\right)^{\mathsf{T}}$
		$\displaystyle=$	$\displaystyle\left(R,S,T,P\right)^{\mathsf{T}}$
	$\displaystyle\bm{s}_{2}$	$\displaystyle:=$	$\displaystyle\left(s_{2}(1,1),s_{2}(1,2),s_{2}(2,1),s_{2}(2,2)\right)^{\mathsf{T}}$		(33)
		$\displaystyle=$	$\displaystyle\left(R,T,S,P\right)^{\mathsf{T}},$

where $T>R>P>S$ and $2R>T+S$. (The actions $1$ and $2$ correspond to cooperation and defection, respectively.) If we consider the quantity $\bm{B}=\sum_{k=0}^{2}\alpha_{k}\bm{s}_{k}$ with $\alpha_{1}=0$ and $\alpha_{2}=1$,

$\displaystyle\bm{B}$

$\displaystyle=$

$\displaystyle\left(R+\alpha_{0},T+\alpha_{0},S+\alpha_{0},P+\alpha_{0}\right)^{\mathsf{T}}.$

(34)

Then, if we choose $\alpha_{0}$ as $\alpha_{0}\in[-R,-P]$, we find that the actions $1$ and $2$ of player $1$ satisfy the condition of Theorem 1 as $\overline{\sigma}_{1}=2$ and $\underline{\sigma}_{1}=1$. Therefore, we conclude that the repeated prisoner’s dilemma game contains at least one ZD strategy, which is a well-known result. By using the construction method in the proof of Theorem 1, $\bm{B}$ is decomposed into

	$\displaystyle\left[\bm{B}\right]_{2,-}$	$\displaystyle=$	$\displaystyle\left(0,0,S+\alpha_{0},P+\alpha_{0}\right)^{\mathsf{T}}$
	$\displaystyle\left[\bm{B}\right]_{1,+}$	$\displaystyle=$	$\displaystyle\left(R+\alpha_{0},T+\alpha_{0},0,0\right)^{\mathsf{T}},$		(35)

and the ZD strategy is

	$\displaystyle\hat{\bm{T}}_{1}\left(2\right)$	$\displaystyle=$	$\displaystyle\frac{1}{W}\bm{B}$
	$\displaystyle\hat{\bm{T}}_{1}\left(1\right)$	$\displaystyle=$	$\displaystyle-\hat{\bm{T}}_{1}\left(2\right)$		(36)

with $W:=\max_{\bm{\sigma}\in\mathcal{A}}\left|B(\bm{\sigma})\right|$. It should be noted that this ZD strategy is called the equalizer strategy and it unilaterally enforces $\left\langle s_{2}\right\rangle^{*}=-\alpha_{0}$ [1].

Theorem 1 can be used to define a class of stage games where ZD strategies exist. In this paper, we call this class ZD games. A natural question is the relation between ZD games and other classes of stage games, such as potential games and totally symmetric games.

Here, we restrict our attention to two-player symmetric games. In other words, the payoffs satisfy $s_{2}(\sigma_{1},\sigma_{2})=s_{1}(\sigma_{2},\sigma_{1})$ $(\forall\bm{\sigma})$. We also write the set of actions as $A_{1}=A_{2}=A:=\{1,\cdots,L\}$, where $L$ is the common number of actions. We first introduce the concept of generalized rock-paper-scissors games.

We also call the complementary set of gRPS games in all two-player symmetric games as non-gRPS games. We now prove the following theorem on the relation between non-gRPS games and ZD games.

Proof. If a stage game is not a gRPS game, then, for all $A^{\prime}\subseteq A$, there exists an action $\sigma_{1}\in A^{\prime}$ such that $s_{1}^{(\mathrm{A})}\left(\sigma_{1},\sigma_{2}\right)\geq 0$ $\left(\forall\sigma_{2}\in A^{\prime}\right)$. Such action $\sigma_{1}$ is an unbeatable action in $A^{\prime}$. It should be noted that $A^{\prime}$ can be $A$. We now construct a series of unbeatable actions as follows. First, $\sigma^{*(1)}$ is an unbeatable action when the action space is $A$, that is,

$\displaystyle s_{1}^{(\mathrm{A})}\left(\sigma^{*(1)},\sigma_{2}\right)$

$\displaystyle\geq$

$\displaystyle 0\quad\left(\forall\sigma_{2}\in A\right).$

(37)

Then, for $2\leq l\leq L$, we recursively define the set $A^{(l)}:=A\backslash\left\{\sigma^{*(1)},\cdots,\sigma^{*(l-1)}\right\}$ and an action $\sigma^{*(l)}\in A^{(l)}$ such that

$\displaystyle s_{1}^{(\mathrm{A})}\left(\sigma^{*(l)},\sigma_{2}\right)\geq 0\quad\left(\forall\sigma_{2}\in A^{(l)}\right).$

(38)

We also write $A^{(1)}:=A$. We remark that such series $\left\{\sigma^{*(l)}\right\}_{l=1}^{L}$ is well-defined due to the property of non-gRPS games.

Because $s_{1}^{(\mathrm{A})}(\sigma_{1},\sigma_{2})=\left[s_{1}(\sigma_{1},\sigma_{2})-s_{2}(\sigma_{1},\sigma_{2})\right]/2$ for two-player symmetric games, we can see that $\underline{\sigma}_{1}=\sigma^{*(1)}$ in the condition of Theorem 1:

$\displaystyle s_{1}\left(\sigma^{*(1)},\sigma_{2}\right)-s_{2}\left(\sigma^{*(1)},\sigma_{2}\right)$

$\displaystyle\geq$

$\displaystyle 0\quad\left(\forall\sigma_{2}\in A\right).$

(39)

Next, we prove that $\overline{\sigma}_{1}=\sigma^{*(L)}$:

$\displaystyle s_{1}\left(\sigma^{*(L)},\sigma_{2}\right)-s_{2}\left(\sigma^{*(L)},\sigma_{2}\right)$

$\displaystyle\leq$

$\displaystyle 0\quad\left(\forall\sigma_{2}\in A\right).$

(40)

Assume to the contrary that

$\displaystyle s_{1}^{(\mathrm{A})}\left(\sigma^{*(L)},\sigma_{2}\right)$

$\displaystyle>$

$\displaystyle 0\quad(\exists\sigma_{2}\in A).$

(41)

(Because $s_{1}^{(\mathrm{A})}$ is an anti-symmetric part, $\sigma_{2}\neq\sigma^{*(L)}$.) This is rewritten as

$\displaystyle s_{1}^{(\mathrm{A})}\left(\sigma_{2},\sigma^{*(L)}\right)$

$\displaystyle<$

$\displaystyle 0\quad(\exists\sigma_{2}\in A).$

(42)

However, since $\sigma_{2}\in\left\{\sigma^{*(1)},\cdots,\sigma^{*(L-1)}\right\}$ and $\sigma^{*(L)}\in A^{(l)}$ for $1\leq l\leq L$, this contradicts with Eq. (38). Therefore, we conclude that Eq. (40) indeed holds. We now find that Eqs. (39) and (40) correspond to the condition for the existence of ZD strategies in Theorem 1. We remark that a linear relation enforced by the ZD strategy is $\left\langle s_{1}\right\rangle^{*}=\left\langle s_{2}\right\rangle^{*}$. $\Box$

It should be noted that an unbeatable imitation strategy exists if and only if a stage game is not a gRPS game [18]. Theorem 2 also constructs an unbeatable ZD strategy, which unilaterally enforces $\left\langle s_{1}\right\rangle^{*}=\left\langle s_{2}\right\rangle^{*}$, for non-gRPS games. Both results imply that, in non-gRPS games, it is not easy for players to exploit the opponent. We also note that two-player symmetric potential games are a subset of non-gRPS games [18]. Therefore, our result directly leads to the existence of ZD strategies in two-player symmetric potential games [20].

We finally remark that the converse of Theorem 2 is not true. That is, ZD strategies can exist for some gRPS games. An example is a game in Table 1, which is a modified version of the RPS game.

Although this game contains a gRPS cycle when $A^{\prime}=\{R,P,S\}$, this game is also a ZD game, since $\overline{\sigma}$ and $\underline{\sigma}$ are regarded as the two actions in Theorem 1.