RESEARCH PAPER 2018 January 61 1

Design of zero-determinant strategies and its application to networked
repeated games

<EMAIL_ADDRESS>
Cheng D Z

Cheng D Z, Li C X

# Design of zero-determinant strategies and its application to networked
repeated games

Daizhan CHENG  Changxi LI  Key Laboratory of Systems and Control, Academy of
Mathematics and Systems Sciences,
Chinese Academy of Sciences, Beijing 100190, China  Center for Systems and
Control, College of Engineering, Peking University, Beijing 100871, China.

###### Abstract

Using semi-tensor product (STP) of matrices, the profile evolutionary equation
(PEE) for repeated finite games is obtained. By virtue of PEE, the zero-
determinant (ZD) strategies are developed for general finite games. A formula
is then obtained to design ZD strategies for general finite games with multi-
player and asymmetric strategies. A necessary and sufficient condition is
obtained to ensure the availability of the designed ZD strategies. It follows
that player $i$ is able to unilaterally design $k_{i}-1$ (one less than the
number of her strategies) dominating linear relations about the expected
payoffs of all players. Finally, the fictitious opponent player is proposed
for networked repeated games (NRGs). A technique is proposed to simplify the
model by reducing the number of frontier strategies.

###### keywords:

finite repeated game, profile evolutionary equation, ZD strategy, networked
repeated games, semi-tensor product of matrices.

##  1 Introduction

In 2012, the zero-determinant (ZD) strategy was firstly proposed by Press and
Dyson [25], which shows that in an iterated prisoner’s dilemma there exist
strategies that dominate any evolutionary opponent. Since then it has
attracted considerable attention from game theoretic community as well as
computer, information, systems and control communities. [15] calls it “an
underway revolution in game theory”, because it reveals that in a repeated
game, a player can unilaterally control her opponent’s payoff.

A significant development in the following researches is the so-called “Akin’s
Lemma” [2], which is a generalization of Press-Dyson’s pioneering work without
using determinant form. Akin’s original work is about two player two strategy
game (prisoner’s dilemma). Then various extensions have been done. In [20] the
ZD strategies of two player two strategy discounted games were discussed. [23]
considers two player continuous strategy discounted games. A surprising fact
is: as a player adopts ZD strategy, her actions restricting to two discrete
levels of cooperation are enough to enforce a linear relationship between
payoffs of two players even the opponent has infinitely many donation levels
to choose. Multiplayer ZD strategies in games with two actions have been
discussed both for undiscounted payoffs [19, 24] and for discounted payoffs
[13]. The most general case with multi-player and arbitrary number of
strategies is also investigated by [32, 31].

Meanwhile, the characteristics of ZD strategies have also be investigated
widely. Particularly, the stability of ZD strategy was analyzed in [28]; the
robustness of ZD strategies has been investigated in [4]; the ZD strategies of
noisy repeated games were investigated by [16]; the influence of misperception
on ZD strategies was discussed in [12], and the evolutionary stability of ZD
strategies has also been investigated widely [27, 1, 18]. ZD strategy
technique has also been used for some particular kinds of games, such as
application to public goods games [24], mining pole games [3], snowdrift game
[33], etc.

The early works concern more about the ZD strategy design [25, 19, 17]. Most
later works focus on general properties of linear relation for average payoffs
of players. For instance, [32] proved the existence of the solution of a set
of linear relations of average payoffs enforced by ZD strategies and the
independence of the relations. [31] is also concentrated on the existence
theorem.

When the applications of ZD strategies to real game problems are concerned,
the design formulas or numerical algorithms are necessary. [29] provides a
method to design ZD strategies for $2\times 2$ asymmetric games. When
asymmetric games are considered, the shortage of similar works in previous
studies has been claimed in [29].

Another promising development of ZD strategy is its application to networked
evolutionary games. For instance, [28] considers the extortion strategy under
myopic best response arrangement over networks. Several kinds of evolutions of
ZD strategy on networked evolutionary games are revealed by [26, 34]. [30]
considers the cooperative mining ZD strategy in block-chain networks, etc.

Recently, a new matrix product, called the semi-tensor product (STP) of
matrices, was proposed [5, 6], and it has been applied to solve some problems
in game theory, including the modeling and analysis of networked repeated
games (NRGs) [8], providing a formula to verify whether a finite game is
potential [7], investigating the vector space structure of finite games and
its orthogonal decompositions [10, 14], application to traffic congestion
games [35] and diffusion games [22], just to mention a few. Readers who are
interested in the STP approach to finite games are referred to a survey paper
[11].

Using STP, this paper presents a profile evolutionary equation (PEE) for
general finite repeated games, which is essentially the same as the Markov
matrix for the memory-one game in [25]. Then a detailed design technique and
rigorous proofs are presented for this general case, which are generalizations
of those proposed firstly by [25]. A necessary and sufficient condition is
obtained for the availability of ZD strategies. As a by product, we also prove
that if a player has $k_{i}$ strategies she can provide unilaterally $k_{i}-1$
linear payoff relations using ZD strategies.

Finally, the ZD strategies for networked repeated games (NRGs) are
investigated. By proposing and using fictitious opponent player (FOP) a
networked repeated game can be transferred to a two player game, where a
player, say, player $i$, plays with the FOP, who represents the whole network
except player $i$. The ZD strategies for player $i$ are designed for $i$ vs
FOP.

The rest of this paper is organized as follows: A brief survey on STP is given
in Section 2. Then it is used to develop profile evolutionary equation (PEE)
of finite repeated games. Finally, some properties of transition matrix of PPE
are investigated, which are important for designing ZD strategies. Section 3
deduces a general formula for designing ZD strategies. A necessary and
sufficient condition for the designed ZD strategies to be available is
presented. Thereafter, some numerical examples are discussed to illustrate the
design procedure. The FOP is proposed in Section 4 for NRGs. Using FOP, the
technique of ZD strategies becomes applicable to NRGs. Section 5 is a brief
conclusion.

Before ending this section, the notations used in this paper is presented.
${\mathcal{M}}_{m\times n}$ is the set of $m\times n$ dimensional real
matrices. $M^{*}$ is the adjoint matrix of $M$. $\sigma(M)$ is the set of
eigenvalues of $M$. $\rho(M)$ is the spectral radius of $M$. $M>0$ ($M\geq 0$)
represents that all entries of $M$ are positive (non-negative). $\ltimes$ is
the STP of matrices. $\operatorname{Col}(A)$ ($\operatorname{Row}(A)$) is the
set of columns (rows) of $A$; $\operatorname{Col}_{i}(A)$
($\operatorname{Row}_{i}(A)$): the $i$-th column (row) of $A$.
${\mathcal{D}}_{k}=\\{1,2,\cdots,k\\}$. $\delta_{k}^{i}$ is the $i$-th column
of identity matrix $I_{k}$. $\delta_{k}^{0}$ is for a zero vector of dimension
$k$. ${\mathcal{B}}=\\{0,1\\}$; and
${\mathcal{B}}^{k}=\\{(b_{1},\cdots,b_{k})^{T}\;|\;b_{i}\in{\mathcal{B}},\;\forall
i\\}$.
$\Delta_{k}=\operatorname{Col}(I_{k})=\left\\{\delta_{k}^{i}\;|\;i=1,\cdots,k\right\\}$
$L\in{\mathcal{M}}_{m\times n}$ is called a logical matrix, if
$\operatorname{Col}(L)\subset\Delta_{m}$. Let
$L=\left[\delta_{m}^{i_{1}},\delta_{m}^{i_{2}},\cdots,\delta_{m}^{i_{n}}\right]$,
it is briefly denoted by $L=\delta_{m}[i_{1},i_{2},\cdots,i_{n}]$.
${\mathcal{L}}_{m\times n}$ is the set of $m\times n$ logical matrices.
$\Upsilon^{m}$ is the set of $m$ dimensional (column) random vectors. That is,
$x=(x_{1},x_{2},\cdots,x_{m})^{T}\in\Upsilon^{m}$ means $x_{i}\geq 0$,
$\forall i$, and $\mathop{\sum}\limits_{i=1}^{m}x_{i}=1$. $\Upsilon_{m\times
n}$ is the set of $m\times n$ (column) random matrices. That is,
$A\in\Upsilon_{m\times n}$, if and only if, columns of $A$, i.e.,
$\operatorname{Col}_{j}(A)$, $j=1,2,\cdots,n$, are random vectors.
${\mathcal{G}}_{[n;k_{1},k_{2},\cdots,k_{n}]}$ is the set of finite non-
cooperative games with $n$ players, and player $i$ has $k_{i}$ strategies,
$i=1,2,\cdots,n$.

##  2 Modeling of Finite Repeated Games

###  2.1 A Brief Survey on STP

######  Definition 2.1.

[5, 6] Let $M\in{\mathcal{M}}_{m\times n}$, $N\in{\mathcal{M}}_{p\times q}$,
and $t:=\operatorname{lcm}(n,p)$ be the least common multiple of $n$ and $p$.
Then the STP of $M$ and $N$ is defined as

$\displaystyle M\ltimes N:=\left(M\otimes I_{t/n}\right)\left(N\otimes
I_{t/p}\right)\in{\mathcal{M}}_{(mt/n)\times(qt/p)},$ (1)

where $\otimes$ is the Kronecker product.

######  Remark 2.2.

  * (i)

STP is a generalization of conventional matrix product. That is, if $n=p$,
then $M\ltimes N=MN$. It is not necessary (and almost impossible) to distinct
STP from conventional matrix product, because in a computing process, the
product might shift from one to the other because of the changes of
dimensions. Hence in most cases the symbol $\ltimes$ is omitted.

  * (ii)

As a generalization, STP keeps all major properties of conventional matrix
product available, including associativity, distributivity, etc. All the
properties of matrix product used in this paper are the same for both
conventional matrix product and STP.

  * (iii)

Since conventional matrix product can be considered as a special case of STP,
all the matrix products used in this paper without product symbol are assumed
to be STP.

Next, we consider how to express a finite-valued mapping (or logical mapping)
into a matrix form using STP.

Let $f:{\mathcal{D}}_{m}\rightarrow{\mathcal{D}}_{n}$ be a mapping from a
finite set to another finite set. Then we can identify $j\in{\mathcal{D}}_{m}$
with its vector form $\vec{j}:=\delta_{m}^{j}\in\Delta_{m}$. In this way, $f$
can be regarded as a mapping $f:\Delta_{m}\rightarrow\Delta_{n}$. In the
sequel $\vec{j}$ is simply denoted by $j$ again if there is no possible
confusion.

######  Proposition 2.3.

Let $f:{\mathcal{D}}_{m}\rightarrow{\mathcal{D}}_{n}$. Then there exists a
unique matrix $M_{f}\in{\mathcal{L}}_{m\times n}$, called the structure matrix
of $f$, such that as the arguments are expressed into their vector forms, we
have

$\displaystyle f(x)=M_{f}x.$ (2)

As a corollary, Proposition 2.3 can be extended into more general form.

######  Corollary 2.4.

Let $x_{i}\in{\mathcal{D}}_{k_{i}}$, $i=1,2,\cdots,n$,
$y_{j}\in{\mathcal{D}}_{p_{j}}$, $j=1,2,\cdots,m$, and
$x=\ltimes_{i=1}^{n}x_{i}$, $y=\ltimes_{j=1}^{m}y_{j}$. Assume

$y_{j}=f_{j}(x_{1},x_{2},\cdots,x_{n}),\quad j=1,2,\cdots,m,$

which have their vector forms as

$\displaystyle y_{j}=M_{j}\ltimes_{i=1}^{n}x_{i},\quad j=1,2,\cdots,m.$ (3)

Then there exists a unique matrix $M_{F}$, called the structure matrix of the
mapping $F=(f_{1},\cdots,f_{m})$, such that

$\displaystyle y=M_{F}x,$ (4)

where

$M_{F}=M_{1}*M_{2}*\cdots*M_{n}\in{\mathcal{L}}_{\rho\times\kappa},$

and $\rho=\prod_{j=1}^{m}p_{j}$, $\kappa=\prod_{i=1}^{n}k_{i}$, and $*$ is
Kratri-Rao product of matrices. ***Let $A\in{\mathcal{M}}_{s\times n}$,
$B\in{\mathcal{M}}_{t\times n}$. Then the Khatri-Rao product of $A$ and $B$,
denoted by $A*B\in{\mathcal{M}}_{st\times n}$, is defined by [6]
$\operatorname{Col}_{i}(A*B)=\operatorname{Col}_{i}(A)\operatorname{Col}_{i}(B),\quad
i=1,2,\cdots,n.$

Similarly, we have the following result:

######  Corollary 2.5.

Let $x_{i}\in\Upsilon_{k_{i}}$, $i=1,2,\cdots,n$ and
$y_{j}\in\Upsilon_{p_{j}}$, $j=1,2,\cdots,m$, and

$\displaystyle y_{j}=M_{j}x,\quad j=1,2,\cdots,m,$ (5)

where $M_{j}\in\Upsilon_{p_{j}\times\kappa}$. If the random variables
$y_{j},j=1,2,\cdots,m$ are conditional independent on
$x_{1},x_{2},\cdots,x_{n}.$ Then there exists a unique matrix $M_{F}$ such
that

$\displaystyle y=M_{F}x,$ (6)

where

$M_{F}=M_{1}*M_{2}*\cdots*M_{n}\in\Upsilon_{\rho\times\kappa},$

which is also called the structure matrix of the mapping
$F=(f_{1},f_{2},\cdots,f_{m})$.

###  2.2 PEE of Finite Games

######  Definition 2.6.

Consider a finite game $G=(N,S,C)$, where

  * (i)

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

  * (ii)

$S=\prod_{i=1}^{n}S_{i}$ is the profile, where
$S_{i}=\\{1,2,\cdots,k_{i}\\},~{}i=1,2,\cdots,n,$ is the strategies (or
actions) of player $i$.

  * (iii)

$C=(c_{1},c_{2},\cdots,c_{n})$, where $c_{i}:S\rightarrow{\mathbb{R}}$ is the
payoff (or utility, cost) function of player $i$, $i=1,2,\cdots,n$.

The set of such finite games is denoted by
${\mathcal{G}}_{[n;k_{1},k_{2},\cdots,k_{n}]}$. A matrix formulation of the
repeated game $G\in{\mathcal{G}}_{[n;k_{1},k_{2},\cdots,k_{n}]}$ is described
as follows [8]:

  * (i)

Identifying $j\in S_{i}$ with $\delta_{k_{i}}^{j}\in\Delta_{k_{i}}$, then
$S_{i}\sim\Delta_{k_{i}}$.

  * (ii)

Setting $\kappa=\prod_{i=1}^{n}k_{i}$, then
$S\sim\Delta_{\kappa}=\prod_{i=1}^{n}\Delta_{k_{i}}$.

  * (iii)

Let $x_{i}\in\Delta_{k_{i}}$ be the vector form of a strategy for player $i$.
Then $x=\ltimes_{i=1}^{n}x_{i}\in\Delta_{\kappa}$ is a profile.

  * (iv)

For each player’s payoff function $c_{i}$, there exists a unique row vector
$V^{c}_{i}\in{\mathbb{R}}^{\kappa}$ such that

$\displaystyle c_{i}(x)=V^{c}_{i}x,\quad i=1,2,\cdots,n.$ (7)

Now consider a repeated game $G^{r}$ of $G$, which stands for (infinitely)
repeated $G$. Then each player can determine her action at $t+1$ using
historic knowledge. It was proved in [25] (see also [15]) that:“ the shortest
memory player sets the rule of the game, which means the long-memory
strategies have no advantages over the memory-one strategies”. Based on this
observation, the strategy updating rule is assumed Markov-like. That is, the
strategy of player $i$ at time $t+1$ depends on the profile at $t$ only. Then
we have [8]

$\displaystyle x_{i}(t+1)=L_{i}x(t),\quad i=1,2,\cdots,n.$ (8)

Two types of strategies are commonly used:

  * •

Pure strategy:

$L_{i}\in{\mathcal{L}}_{k_{i}\times\kappa},\quad i=1,2,\cdots,n.$

  * •

Mixed Strategy:

$L_{i}\in\Upsilon_{k_{i}\times\kappa},\quad i=1,2,\cdots,n.$

Multiplying (by STP) all equations in (8) together yields

$\displaystyle x(t+1)=Lx(t),$ (9)

where

$L=L_{1}*L_{2}*\cdots*L_{n}.$

In pure strategy case $L\in{\mathcal{L}}_{\kappa\times\kappa}$ and in mixed
strategy case $L\in\Upsilon_{\kappa\times\kappa}$. In mixed strategy case
$x(t)$ can be considered as a distribution of profiles at time $t$. If we take
into consideration that $\delta_{\kappa}^{i}$ is used to express the $i$-th
profile, then $x(t)$ can also be considered as the expected value of profile
at time $t$.

In this paper we concern only mixed strategy case. Now what a player can
manipulate is his own strategy updating rule. That is, player $i$ can only
choose his $L_{i}$.

We arrange profiles in alphabetic order as

$\begin{array}[]{ccl}S&=&\\{(s_{1},s_{2},\cdots,s_{n})\;|\;s_{i}\in
S_{i},~{}i=1,2,\cdots,n\\}\\\
{}\hfil&=&\\{(1,1,\cdots,1),(1,1,\cdots,2),\cdots,(k_{1},k_{2},\cdots,k_{n})\\}\\\
{}\hfil&:=&\\{s^{1},s^{2},\cdots,s^{\kappa}\\}.\end{array}$

Denote the probability of player $i$ choosing strategy $j$ at time $t+1$ under
the situation that the profile at time $t$ is $s^{r}$ as

$\displaystyle p^{r}_{i,j}=Prob(x_{i}(t+1)=j\;|\;x(t)=s^{r}).$ (10)

Then we have the strategy evolutionary equation (SEE) of player $i$ as

$\displaystyle x_{i}(t+1)=L_{i}x(t),$ (11)

where

$\displaystyle\begin{array}[]{l}L_{i}=\begin{bmatrix}p^{1}_{i,1}&p^{2}_{i,1}&\cdots&p^{\kappa}_{i,1}\\\
p^{1}_{i,2}&p^{2}_{i,2}&\cdots&p^{\kappa}_{i,2}\\\ \vdots&~{}&~{}&~{}\\\
p^{1}_{i,k_{i}}&p^{2}_{i,k_{i}}&\cdots&p^{\kappa}_{i,k_{i}}\\\
\end{bmatrix}\in\Upsilon_{k_{i}\times\kappa},~{}i=1,2,\cdots,n.\end{array}$
(13)

According to Corollary 2.5, we have PEE as

$\displaystyle x(t+1)=Lx(t),$ (14)

where the transition matrix

$\displaystyle L=L_{1}*L_{2}*\cdots*L_{n}.$ (15)

We give a simple example to calculate $L$.

######  Example 2.7.

Consider the repeated prisoners’ dilemma. Let $p^{r}_{i,j}$ be the probability
of player $i$ taking strategy $j\in\\{C,D\\}\sim\\{1,2\\}$ under the condition
$s^{r}$. Then a straightforward computation shows that

$\begin{array}[]{l}\begin{cases}x_{1}(t+1)=L_{1}x(t),\\\
x_{2}(t+1)=L_{2}x(t),\end{cases}\end{array}$

where

$L_{1}=\begin{bmatrix}p^{1}_{1,1}&p^{2}_{1,1}&p^{3}_{1,1}&p^{4}_{1,1}\\\
p^{1}_{1,2}&p^{2}_{1,2}&p^{3}_{1,2}&p^{4}_{1,2}\\\
\end{bmatrix},~{}L_{2}=\begin{bmatrix}p^{1}_{2,1}&p^{2}_{2,1}&p^{3}_{2,1}&p^{4}_{2,1}\\\
p^{1}_{2,2}&p^{2}_{2,2}&p^{3}_{2,2}&p^{4}_{2,2}\\\ \end{bmatrix}.$

Denote by

$\begin{array}[]{l}p_{i}=p^{i}_{1,1},~{}q_{i}=p^{i}_{2,1},\quad
i=1,2,3,4.\end{array}$

It follows that

$\begin{array}[]{l}p^{i}_{1,2}=1-p^{i}_{1,1}=1-p_{i},~{}p^{i}_{2,2}=1-p^{i}_{2,1}=1-q_{i},\quad
i=1,2,3,4.\end{array}$

Then we have

$\displaystyle\begin{array}[]{l}L=L_{1}*L_{2}{}{}\\\
=\begin{bmatrix}p^{1}_{1,1}p^{1}_{2,1}&p^{2}_{1,1}p^{2}_{2,1}&p^{3}_{1,1}p^{3}_{2,1}&p^{4}_{1,1}p^{4}_{2,1}\\\
p^{1}_{1,1}p^{1}_{2,2}&p^{2}_{1,1}p^{2}_{2,2}&p^{3}_{1,1}p^{3}_{2,2}&p^{4}_{1,1}p^{4}_{2,2}\\\
p^{1}_{1,2}p^{1}_{2,1}&p^{2}_{1,2}p^{2}_{2,1}&p^{3}_{1,2}p^{3}_{2,1}&p^{4}_{1,2}p^{4}_{2,1}\\\
p^{1}_{1,2}p^{1}_{2,2}&p^{2}_{1,2}p^{2}_{2,2}&p^{3}_{1,2}p^{3}_{2,2}&p^{4}_{1,2}p^{1}_{2,2}\\\
\end{bmatrix}\\\
=\begin{bmatrix}p_{1}q_{1}&p_{1}q_{2}&p_{2}q_{1}&p_{2}q_{2}\\\
p_{1}(1-q_{1})&p_{1}(1-q_{2})&p_{2}(1-q_{1})&p_{2}(1-q_{2})\\\
(1-p_{1})q_{1}&(1-p_{1})q_{2}&(1-p_{2})q_{1}&(1-p_{2})q_{2}\\\
(1-p_{1})(1-q_{1})&(1-p_{1})(1-q_{2})&(1-p_{2})(1-q_{1})&(1-p_{2})(1-q_{2})\\\
\end{bmatrix}\end{array}$ (19)

######  Remark 2.8.

It is easy to verify that the transition matrix in PEE (refer to (19)) is
essentially the transpose of the Markov matrix for the memory one game in
[25]. Corresponding to the “column order” of [25] there is a “row order”
change in (19). This is because our profiles are ordered in alphabetic as
$CC,~{}CD,~{}DC,~{}DD$, while [25] uses the order $CC,~{}DC,~{}CD,~{}DD$.

###  2.3 Properties of PEE

In this subsection we investigate some properties of the transition matrix $L$
of PEE, which are required for designing ZD strategies. As aforementioned in
Remark 2.8, $L$ is the same as the Markov transition matrix for the memory one
game in [25] (only with a transpose). So $L$ is a column random matrix. This
difference does not affect the following discussion. Hence the following
argument is a mimic of the corresponding argument in [25]. What we are going
to do is to extend it to general case and put it on a solid mathematical
foundation.

In the sequel, we need an assumption on $L$. To present it, some preparation
is necessary.

A random square matrix $M$ is called a primitive matrix if there exists a
finite integer $s>0$ such that $M^{s}>0$ [21]. Some nice properties of
primitive matrix are cited as follows:

######  Proposition 2.9.

(Perron-Frobenius Theorem)[21] Let $L$ be a primitive stochastic matrix. Then

  * (i)

$\rho(L)=1$ and there exists a unique $\lambda\in\sigma(L)$ such that
$|\lambda|=1$.

  * (ii)

$\displaystyle\lim_{t\rightarrow\infty}L^{t}=P>0.$ (20)

Moreover, $P=uv^{T}$, where $Lu=u$, $u>0$, $L^{T}v=v$, $v>0$.

We are ready to present our fundamental assumption.

Assumption A-1: $L$ is primitive.

######  Remark 2.10.

  * (i)

A-1 is not always true. For instance, consider (19) and let $p^{2}_{1,1}=0$,
$p^{3}_{1,1}=0$, $p^{4}_{1,1}=0$, and $p^{4}_{2,1}=0$. Then $L$ is not
primitive.

  * (ii)

If $0<p^{r}_{i,j}<1$, $\forall r,i,j$, then a straightforward verification
shows that $L$ is primitive. So A-1 is always true except a zero-measure set.

  * (iii)

According to Proposition 2.9, we have the following immediate conclusions. (a)
If $L$ is primitive, then

$\displaystyle\operatorname{rank}(L-I_{\kappa})=\kappa-1.$ (21)

(b) There exists $P=uv^{T}$, where $Lu=u$, $u>0$, $L^{T}v=v$, $v>0$, such that
(20) holds. That is,

$\displaystyle\lim_{t\rightarrow\infty}L^{t}=uv^{T}.$ (22)

######  Proposition 2.11.

Let $L$ be a $\kappa\times\kappa$ column primitive stochastic matrix. Define
$M:=L-I_{\kappa}$ and denote by $M^{*}$ its adjoint matrix. Then

  * (i)

$\operatorname{rank}(M^{*})=1$.

  * (ii)

$\displaystyle\operatorname{Col}_{j}(M^{*})\neq 0,\quad j=1,2,\cdots,\kappa.$
(23)

The proof of this proposition and all other proofs can be found in Appendix.

######  Proposition 2.12.

Consider the PEE (14). If $L$ is primitive, then

$\displaystyle x^{*}:=\lim_{t\rightarrow\infty}x(t)=u/\|u\|,$ (24)

where $u$ comes from (22).

Hereafter, we assume $u$ has been normalized. Then $x^{*}=u$ is the only
normalized eigenvector of $L$ corresponding to eigenvalue $1$.

######  Proposition 2.13.

Assume $L$ is primitive, then

$\displaystyle\operatorname{Col}_{j}(M^{*})\propto u,\quad\forall j.$ (25)

Combining (23) and (25) yields

$\displaystyle\operatorname{Col}_{j}(M^{*})=\mu_{j}u,\quad\mu_{j}\neq
0,\;\;j=1,2,\cdots,\kappa.$ (26)

##  3 Design of ZD Strategies for Repeated Games

###  3.1 A Universal Formula for ZD-strategies

Consider the transition matrix $L$ of PEE (14). Recall the finite game $G$.
For player $i$ with action $j$, define an indicative vector
$\xi_{i,j}\in{\mathbb{R}}^{\kappa}$ as follows

$\displaystyle\xi_{i,j}=\ltimes_{\tau=1}^{n}\gamma_{\tau},$ (27)

where

$\gamma_{\tau}=\begin{cases}\mathbf{1}_{k_{\tau}},\tau\neq i,\\\
\delta_{k_{i}}^{j},~{}\tau=i.\\\ \end{cases}$

$\xi_{i,j}\in{\mathbb{R}}^{\kappa}$ is called strategy extraction vector,
which has the following property.

######  Lemma 3.1.

Consider the FRG $G^{r}$. Strategy extraction vector
$\xi_{i,j}\in{\mathbb{R}}^{\kappa}$ has the following property

$\displaystyle\begin{array}[]{ccl}\xi_{i,j}^{\top}L&=&\sum_{a\in\Phi_{i,j}}\operatorname{Row}_{a}(L)\\\
&=&[p^{1}_{i,j},p^{2}_{i,j},\cdots,p^{\kappa}_{i,j}],~{}\forall i\in N,\forall
j\in A_{i}.\end{array}$ (30)

where $\Phi_{i,j}=\\{a=(a_{1},\ldots,a_{n})\in A~{}|~{}a_{i}=j\\}\subseteq A$.

Proof: According to the definition of $\xi_{i,j}$ and $L$, we have

$\displaystyle\begin{array}[]{ccl}\xi_{i,j}^{\top}L&=&\xi_{i,j}^{\top}[\operatorname{Col}_{1}(L),\operatorname{Col}_{2}(L),\cdots,\operatorname{Col}_{k}(L)]\\\
&=&[\xi_{i,j}^{\top}\operatorname{Col}_{1}(L),\xi_{i,j}^{\top}\operatorname{Col}_{2}(L),\cdots,\xi_{i,j}^{\top}\operatorname{Col}_{k}(L)],\end{array}$

where for each column

$\displaystyle\begin{array}[]{ccl}\xi_{i,j}^{\top}\operatorname{Col}_{r}(L)&=&(\ltimes_{\tau=1}^{n}\gamma_{\tau}^{\top})(\ltimes_{s=1}^{n}\operatorname{Col}_{r}(L_{s}))\\\
&=&(\otimes_{\tau=1}^{n}\gamma_{\tau}^{\top})(\otimes_{s=1}^{n}\operatorname{Col}_{r}(L_{s}))\\\
&=&\otimes_{s=1}^{n}(\gamma_{s}^{\top}\operatorname{Col}_{r}(L_{s}))\\\
&=&p^{r}_{i,j}.\end{array}$

The second equality comes from STP’s property. The third equality comes from
the property of Kronecker product.

$\Box$

######  Remark 3.2.

(i) The strategy extraction vector $\xi_{i,j}\in{\mathbb{R}}^{\kappa}$ is
called “Repeat” strategy in the existing works [23], [32]. (ii) The purpose of
equation (30) is to pick out the set of rows from matrix $L$, which involve
$p^{r}_{i,j}$. The row labels of such set are denoted by $\Phi_{i,j}$. Then
$\xi_{i,j}^{\top}L$ is the summation of the rows in $L$, which are labeled by
$\Phi_{i,j}$. For each pair $(i,j)$, $\xi_{i,j}^{\top}L$ realizes an
elementary (equivalent) transformation for $L$, which results in a row of $L$
which contains $p_{i,j}$ only, i.e., this new row does not involve
$p^{d}_{s,r}$, $(s,r)\neq(i,j)$.

If $L$ is primitive, then it has a stationary distribution
$\mu\in\Upsilon^{\kappa}$ satisfying

$\displaystyle L\mu=\mu\Leftrightarrow(L-I)\mu=0.$ (31)

Multiplying $\xi_{i,j}$ to both sides of (31) yields that

$\displaystyle[\xi_{i,j}^{\top}L-\xi_{i,j}^{\top}]\mu=0.$ (32)

Let $T_{i}=[\xi_{i}^{\top}L-\xi_{i}^{\top}],$ where
$\xi_{i}=[\xi_{i,1},\xi_{i,2},\cdots,\xi_{i,k_{i}}].$ According to [32], the
ZD strategy of player $i$ belong to the interaction of two subspaces.

######  Definition 3.3.

[32] The ZD strategy $L_{i}$ of player $i$ exists if and only if

$\displaystyle\operatorname{Span}(V)\cap\operatorname{Span}(T_{i}^{\top})\neq\\{{\bf
0}_{\kappa}\\},$ (33)

where $V=[{\bf
1}_{\kappa},(V_{1}^{c})^{\top},(V_{2}^{c})^{\top},\cdots,(V_{n}^{c})^{\top}].$

######  Remark 3.4.

Definition 3.3 can be used to detect whether a given strategy $L_{i}$ is a ZD
strategy or not. However, it is difficult to design a zero-determinant
strategy for a given game.

In the following, we only consider how to derive player $i$’s zero-determinant
strategy $p_{i,j}$ associated with action $j$ using $\xi_{i,j},$ where
$p_{i,j}=[p^{1}_{i,j},p^{2}_{i,j},\cdots,p^{\kappa}_{i,j}].$ A general design
formula is presented in the following:

######  Proposition 3.5.

Consider a repeated game $G^{r}$, where
$G\in{\mathcal{G}}_{[n;k_{1},k_{2},\cdots,k_{n}]}$. Assume player $i$ is aimed
at a set of linear relations on the expected payoffs as

$\displaystyle\begin{array}[]{l}\ell_{i,j}(Ec_{1},Ec_{2},\cdots,Ec_{n},1)=0,\quad
1\leq i\leq n;j=1,2,\cdots,k_{i}-1,\end{array}$ (35)

where $\ell_{i,j}$ is a linear function and $Ec_{i}$ is the expected payoff of
player $i$. Then her ZD strategies can be designed as

$\displaystyle\begin{array}[]{ccl}p_{i,j}&=&(p^{1}_{i,j},p^{2}_{i,j},\cdots,p^{\kappa}_{i,j})\\\
{}\hfil&=&\mu_{i,j}\ell_{i,j}\left(V^{c}_{1},V^{c}_{2},\cdots,V^{c}_{n},{\bf
1}_{\kappa}^{T}\right)+\xi_{i,j},\quad j=1,2,\cdots,k_{i}-1,\end{array}$ (38)

where $\mu_{i,j}\neq 0$ are adjustable parameters.

Proof: If $p_{i,j}$ satisfies (38), then we have

$\displaystyle\begin{array}[]{ccl}p_{i,j}-\xi_{i,j}^{\top}&=&\mu_{i,j}\ell_{i,j}\left(V^{c}_{1},V^{c}_{2},\cdots,V^{c}_{n},{\bf
1}_{\kappa}^{T}\right)\\\
&=&\mu_{i,j}\ell_{i,j}\left(Ec_{1},Ec_{2},\cdots,Ec_{n}\right)+c\\\
&=&0,\end{array}$ (42)

where $c$ is a constant. Equation (42) implies that

$\ell_{i,j}\left(Ec_{1},Ec_{2},\cdots,Ec_{n}\right)=0,~{}1\leq i\leq
n;j=1,2,\cdots,k_{i}-1.$

$\Box$

######  Remark 3.6.

Equation (38) is a fundamental formula, which provides a convenient way to
design ZD strategies for our preassigned purposes. One may concern the time
complexity of the proposed formula. We point that the complexity is related
with the number of players n, the number of strategies for each player
$k_{i}$, which will be used for the construction of vector $\xi_{i,j}$. To
reduce the complexity for designing ZD strategies, fictitious opponent player
method is proposed in Section 4.

######  Definition 3.7.

A set of ZD strategies is permissible, if the following two conditions are
satisfied.

  * (i)

$\displaystyle 0\leq p_{i,j}\leq 1,\quad j=1,2,\cdots,k_{i}-1.$ (43)

  * (ii)

$\displaystyle 0\leq\mathop{\sum}\limits_{j=1}^{k_{i}-1}p_{i,j}\leq 1.$ (44)

######  Remark 3.8.

  * (i)

It is obvious that permissibility is a fundamental requirement. Non-
permissible strategies are meaningless.

  * (ii)

It is clear that player $i$ can unilaterally design at most $|S_{i}|-1$ linear
relations. Because when $p_{i,j}$, $j<|S_{i}|$ are all determined,
$p_{i,|S_{i}|}$ is uniquely determined by

$p_{i,|S_{i}|}={\bf
1}^{T}_{\kappa}-\mathop{\sum}\limits_{j=1}^{|S_{i}|-1}p_{i,j}.$

  * (iii)

Indeed, player $i$ can design $|S_{i}|-1$ linear relations as she wish. This
is an advantage of the formula (38), because it clearly tells how many linear
relations a player may design. It was pointed out by [32] that “when the
number $M_{n}$ of possible actions for player $n$ is more than two, player $n$
may be able to employ a ZD strategy with dim $V_{n}\geq 2$ to simultaneously
enforce more than one linear relations. Such a possibility has never been
reported in the context of ZD strategies.”

  * (iv)

Of course, player $i$ needs not to design $|S_{i}|-1$ relations. If she
intends to design $r<|S_{i}|-1$ relations, equation (44) has to be modified by
reducing the summation to $r$ items.

  * (v)

The ZD design formula (38) can be used simultaneously by multi-players, or
even all $n$ players.

  * (vi)

Equation (26) is extremely important for formula (38) to be available, because
it ensures that each row in the $M=L-I_{\kappa}$ is replaceable by a designed
linear relation to get zero determinant.

Even though a set of ZD strategies is permissible, it may not be available,
which means the goal (35) may not be reached. We need the following result:

######  Theorem 3.9.

Consider a repeated game, $G^{r}$, where
$G\in{\mathcal{G}}_{[n;k_{1},k_{2},\cdots,k_{n}]}$. The stationary
distribution exists, if and only if,

  * (i)

there exists a $\mu\in\Upsilon^{\kappa}$ such that

$\displaystyle\lim_{t\rightarrow\infty}L^{t}=\mu{\bf 1}^{T}_{\kappa}.$ (45)

  * (ii)

$\displaystyle\operatorname{rank}(L-I_{\kappa})=\kappa-1.$ (46)

######  Remark 3.10.

The existence of stationary distribution $\mu$ is only a sufficient condition
for a set of ZD strategy designed by formula (38) to be available. As pointed
by [2], it can be replaced by $\lim_{t\rightarrow\infty}\sum_{k=1}^{t}x(k),$
which is the same as $\mu$ provided $\mu$ exists.

######  Remark 3.11.

To see that permissibility is not enough to ensure (45) and (46), we recall
Example 2.7. Assume

$L_{1}=\begin{bmatrix}p^{1}_{1,1}&0&p^{3}_{1,1}&0\\\
p^{1}_{1,2}&1&p^{3}_{1,2}&1\\\
\end{bmatrix},~{}L_{2}=\begin{bmatrix}p^{1}_{2,1}&0&p^{3}_{2,1}&0\\\
p^{1}_{2,2}&1&p^{3}_{2,2}&1\\\ \end{bmatrix}.$

Then it is easy to verify that

$\begin{array}[]{ccl}L=L_{1}*L_{2}=\begin{bmatrix}p^{1}_{1,1}p^{1}_{2,1}&0&p^{3}_{1,1}p^{3}_{2,1}&0\\\
p^{1}_{1,1}p^{1}_{2,2}&0&p^{3}_{1,1}p^{3}_{2,2}&0\\\
p^{1}_{1,2}p^{1}_{2,1}&0&p^{3}_{1,2}p^{3}_{2,1}&0\\\
p^{1}_{1,2}p^{1}_{2,2}&1&p^{3}_{1,2}p^{3}_{2,2}&1\\\
\end{bmatrix}~{}\sim\begin{bmatrix}p^{1}_{1,1}p^{1}_{2,1}&p^{3}_{1,1}p^{3}_{2,1}&0&0\\\
p^{1}_{1,2}p^{1}_{2,1}&p^{3}_{1,2}p^{3}_{2,1}&0&0\\\
p^{1}_{1,1}p^{1}_{2,2}&p^{3}_{1,1}p^{3}_{2,2}&0&0\\\
p^{1}_{1,2}p^{1}_{2,2}&p^{3}_{1,2}p^{3}_{2,2}&1&1\\\
\end{bmatrix}.\end{array}$

where $\sim$ stands for similar, which is caused by swapping second row with
third row and second column with third column. Then it is clear that $L^{t}$
is always similar to a block lower triangular matrix. Hence (45) can never be
satisfied. While using (38), by choosing suitable $V^{c}_{i}$, $i=1,2$ and
parameter $\mu_{1,1}$, a permissible set of ZD strateries can easily be
constructed, which provides a counter example to show permissibility is not
enough to ensure availability.

Note that verifying the two conditions in Theorem 3.9 is not an easy job.
Hence we may replace them by the following one.

######  Corollary 3.12.

Consider an repeated game, $G^{r}$, where
$G\in{\mathcal{G}}_{[n;k_{1},k_{2},\cdots,k_{n}]}$. Assume the PEE of $G^{r}$
is (9), where $L$ is primitive, then the set of ZD strategies designed by
formula (38) is available.

######  Remark 3.13.

  * (i)

Even though primitivity of $L$ is only a sufficient condition, it is almost
necessity because only a zero-measure set of $L$ may not be primitive. That
is, if $L$ is not primitive then there must be some $(r,i,j)$ with
$p^{r}_{i,j}\in{\mathcal{B}}$. So the designer, who intends to use ZD
strategies, is better to avoid using such values.

  * (ii)

Any player can not unilaterally make the conditions in Theorem 3.9 satisfied.
It depends on other players’ strategies. What the player $i$ can do is to do
her best, that is, to ensure her designed rows, $\xi_{i,j}$,
$j=1,2,\cdots,k_{i}$ are linearly independent. (A Chinese idiom says that “Mou
Shi Zai Ren, Cheng Shi Zai Tian”. (Man proposes, God disposes.)) That is the
situation for ZD strategy designer.

###  3.2 Numerical Examples

In the following, we discuss some numerical examples:

######  Example 3.14.

Consider a $G\in{\mathcal{G}}_{[3;2,3,2]}$. Since $k_{1}=2$, $k_{2}=3$, and
$k_{3}=2$, using (30), it is easy to calculate that

$\displaystyle\begin{array}[]{l}\Phi_{1,1}=\\{1,2,3,4,5,6\\},\\\
\Phi_{1,2}=\\{7,8,9,10,11,12\\},\\\ \Phi_{2,1}=\\{1,2,7,8\\},\\\
\Phi_{2,2}=\\{3,4,9,10\\},\\\ \Phi_{2,3}=\\{5,6,11,12\\},\\\
\Phi_{3,1}=\\{1,3,5,7,9,11\\},\\\ \Phi_{3,2}=\\{2,4,6,8,10,12\\}.\\\
\xi_{1,1}=[1,1,1,1,1,1,0,0,0,0,0,0],\\\
\xi_{1,2}=[0,0,0,0,0,0,1,1,1,1,1,1],\\\
\xi_{2,1}=[1,1,0,0,0,0,1,1,0,0,0,0],\\\
\xi_{2,2}=[0,0,1,1,0,0,0,0,1,1,0,0],\\\
\xi_{2,3}=[0,0,0,0,1,1,0,0,0,0,1,1],\\\
\xi_{3,1}=[1,0,1,0,1,0,1,0,1,0,1,0],\\\
\xi_{3,2}=[0,1,0,1,0,1,0,1,0,1,0,1].\\\ \end{array}$ (61)

These parameters depend on the type of games, precisely speaking, they depend
on the parameters $\\{n;k_{1},\cdots,k_{n}\\}$ only. They are independent of
particular games.

  * •

Pinning Strategy:

Assume the payoff vectors are:

$\begin{array}[]{ccl}V^{c}_{1}&=&[-3,-0.5,6,9,8,7,-4,-4.5,5,6.5,5,7],\\\
V^{c}_{2}&=&[4,-1,-5,7.5,2,3.5,8,-4,5,8,9,-2],\\\
V^{c}_{3}&=&[9,5,-6,-5.5,5.5,8,8.5,5.5,-0,-3.5,4.5,7].\end{array}$

Assume player 2 want to design pinning strategies which enforce the average
payoffs of players 1 and 3 to be

$\begin{array}[]{l}Ec_{1}=r_{1}=4,\\\ Ec_{2}=r_{2}=-3.\end{array}$

She may choose $\mu_{2,1}=\mu_{2,2}=0.1$ and then set

$\displaystyle\begin{array}[]{ccl}p_{2,1}&:=&(0.1)*V^{c}_{1}-(0.4)*{\bf
1}_{12}^{T}+\xi_{2,1}\\\
{}\hfil&=&[0.3,0.55,0.2,0.5,0.4,0.3,0.2,0.15,0.1,0.25,0.1,0.3]\\\
p_{2,2}&=&(0.1)*V^{c}_{3}+(0.3)*{\bf 1}_{12}^{T}+\xi_{2,2}\\\
{}\hfil&=&[0.6,0.2,0.1,0.15,0.25,0.5,0.55,0.25,0.7,0.35,0.15,0.4].\end{array}$
(66)

It is ready to verify that the ZD strategies designed in (66) are permissible.

  * (ii)

Extortion Strategy:

Consider a $G\in{\mathcal{G}}_{[3;2,3,2]}$ again. Assume the payoff structure
vectors are as follows:

$\begin{array}[]{ccl}V^{c}_{1}&=&[16,11,-4,-8,-2,-10.3,11.4,18.5,1.2,-3,-2.5,1.5],\\\
V^{c}_{2}&=&[3,2,-1,0,5,-6,4,3,3,1,-1,7],\\\
V^{c}_{3}&=&[-2.9,0,6.8,7.1,2,-9.4,-8.2,0.4,4.6,6.1,-2,2.3].\end{array}$

Player 2 plans to design an extortion strategy against both players 1 and 3.
She may design

$\begin{array}[]{l}Ec_{2}-r=k_{1}(Ec_{1}-r),\\\
Ec_{2}-r=k_{2}(Ec_{3}-r).\end{array}$

To this end, she needs to design

$\begin{array}[]{l}p_{2,1}-\xi_{2,1}=\mu_{1}\left[(V^{c}_{2}-r{\bf
1}_{12}^{T})-k_{1}(V^{c}_{1}-r{\bf 1}_{12}^{T})\right],\\\
p_{2,3}-\xi_{2,3}=\mu_{2}\left[(V^{c}_{2}-r{\bf
1}_{12}^{T})-k_{2}(V^{c}_{3}-r{\bf 1}_{12}^{T})\right].\\\ \end{array}$

Choosing $\mu_{1}=0.05$, $\mu_{2}=0.1$, $r=1$, $k_{1}=1.1$, $k_{2}=1.2$, it
follows that

$\displaystyle\begin{array}[]{ccl}p_{2,1}&=&[0.275,0.5,0.175,0.445,0.365,0.2715,0.178,0.1375,0.0890,0.22,0.0925,0.2725],\\\
p_{2,2}&=&[0.668,0.22,0.104,0.168,0.28,0.548,0.604,0.272,0.768,0.388,0.16,0.444].\\\
\end{array}$ (69)

The ZD strategies designed in (69) are also permissible.

######  Remark 3.15.

  * (i)

In general, to design a set of permissible ZD strategies is not an easy job.
To determine related parameters we need to solve a set of linear inequalities.

  * (ii)

To verify Lemma 3.1, we calculate the matrix $M=L-I_{\kappa}$ for Example 3.14
as follows:

$\displaystyle
M=\left[\begin{array}[]{llll}p^{1}_{1,1}p^{1}_{2,1}p^{1}_{3,1}-1&p^{2}_{1,1}p^{2}_{2,1}p^{2}_{3,1}&\cdots&p^{12}_{1,1}p^{12}_{2,1}p^{12}_{3,1}\\\
p^{1}_{1,1}p^{1}_{2,1}p^{1}_{3,2}&p^{2}_{1,1}p^{2}_{2,1}p^{2}_{3,2}-1&\cdots&p^{12}_{1,1}p^{12}_{2,1}p^{12}_{3,2}\\\
p^{1}_{1,1}p^{1}_{2,2}p^{1}_{3,1}&p^{2}_{1,1}p^{2}_{2,2}p^{2}_{3,1}&\cdots&p^{12}_{1,1}p^{12}_{2,2}p^{12}_{3,1}\\\
p^{1}_{1,1}p^{1}_{2,2}p^{1}_{3,2}&p^{2}_{1,1}p^{2}_{2,2}p^{2}_{3,2}&\cdots&p^{12}_{1,1}p^{12}_{2,2}p^{12}_{3,2}\\\
p^{1}_{1,1}p^{1}_{2,3}p^{1}_{3,1}&p^{2}_{1,1}p^{2}_{2,3}p^{2}_{3,1}&\cdots&p^{12}_{1,1}p^{12}_{2,3}p^{12}_{3,1}\\\
p^{1}_{1,1}p^{1}_{2,3}p^{1}_{3,2}&p^{2}_{1,1}p^{2}_{2,1}p^{2}_{3,2}&\cdots&p^{12}_{1,1}p^{12}_{2,1}p^{12}_{3,2}\\\
p^{1}_{1,2}p^{1}_{2,1}p^{1}_{3,1}&p^{2}_{1,2}p^{2}_{2,1}p^{2}_{3,1}&\cdots&p^{12}_{1,2}p^{12}_{2,1}p^{12}_{3,1}\\\
p^{1}_{1,2}p^{1}_{2,1}p^{1}_{3,2}&p^{2}_{1,2}p^{2}_{2,1}p^{2}_{3,2}&\cdots&p^{12}_{1,2}p^{12}_{2,1}p^{12}_{3,2}\\\
p^{1}_{1,2}p^{1}_{2,2}p^{1}_{3,1}&p^{2}_{1,2}p^{2}_{2,2}p^{2}_{3,1}&\cdots&p^{12}_{1,2}p^{12}_{2,2}p^{12}_{3,1}\\\
p^{1}_{1,2}p^{1}_{2,2}p^{1}_{3,2}&p^{2}_{1,2}p^{2}_{2,2}p^{2}_{3,2}&\cdots&p^{12}_{1,2}p^{12}_{2,2}p^{12}_{3,2}\\\
p^{1}_{1,2}p^{1}_{2,3}p^{1}_{3,1}&p^{2}_{1,2}p^{2}_{2,3}p^{2}_{3,1}&\cdots&p^{12}_{1,2}p^{12}_{2,3}p^{12}_{3,1}\\\
p^{1}_{1,2}p^{1}_{2,3}p^{1}_{3,2}&p^{2}_{1,2}p^{2}_{2,1}p^{2}_{3,2}&\cdots&p^{12}_{1,2}p^{12}_{2,1}p^{12}_{3,2}-1\\\
\end{array}\right]$ (82)

Then it is easy to verify that $\Phi_{i,j}$ is the rows with each components
containing $p^{t}_{i,j}$ as a factor. Moreover, a simple calculation shows
that Lemma 3.1 is correct.

  * (iii)

To verify the availability of ZD-strategies in (66), we assume the strategies
for player 1 is

$\begin{array}[]{ccl}p_{1,1}=[0.2,0.3,0.8,0.7,0.5,0.4,0.7,0.9,0.2,0.2,0.1,0.9];\end{array}$

the strategies for player 3 is

$\begin{array}[]{ccl}p_{3,1}=[0.15,0.2,0.8,0.85,0.2,0.35,0.7,0.9,0.2,0.15,0.55,0.35].\end{array}$

Then the strategy profile dynamics is:

$x(t+1)=Lx(t),\quad t\geq 0,$

where $L$ is

$\begin{array}[]{ccl}L&=&\left[\begin{array}[]{llllllllllll}0.009&0.033&0.128&0.2975&0.04&0.042&0.098&0.1215&0.004&0.0075&0.0055&0.0945\\\
0.051&0.132&0.032&0.0525&0.16&0.078&0.042&0.0135&0.016&0.0425&0.0045&0.1755\\\
0.018&0.012&0.064&0.0892&0.025&0.07&0.2695&0.2025&0.028&0.0105&0.0083&0.126\\\
0.102&0.048&0.016&0.0158&0.1&0.13&0.1155&0.0225&0.112&0.0595&0.0067&0.234\\\
0.003&0.015&0.448&0.2082&0.035&0.028&0.1225&0.486&0.008&0.012&0.0413&0.0945\\\
0.017&0.06&0.112&0.0367&0.14&0.052&0.0525&0.054&0.032&0.068&0.0338&0.1755\\\
0.036&0.077&0.032&0.1275&0.04&0.063&0.042&0.0135&0.016&0.03&0.0495&0.0105\\\
0.204&0.308&0.008&0.0225&0.16&0.117&0.018&0.0015&0.064&0.17&0.0405&0.0195\\\
0.072&0.028&0.016&0.0383&0.025&0.105&0.1155&0.0225&0.112&0.0420&0.0743&0.014\\\
0.408&0.112&0.004&0.0068&0.1&0.195&0.0495&0.0025&0.448&0.238&0.0607&0.0260\\\
0.012&0.035&0.112&0.0893&0.035&0.042&0.0525&0.054&0.032&0.048&0.3713&0.0105\\\
0.068&0.14&0.028&0.0158&0.14&0.078&0.0225&0.006&0.128&0.272&0.3037&0.0195\\\
\end{array}\right].\end{array}$

It is easy to verify that

$\operatorname{rank}(L-I_{12})=11.$

Moreover, we also have that

$\lim_{t\rightarrow\infty}L^{t}=u{\bf 1}^{T}_{12},$

where

$\begin{array}[]{ccl}u&=&[0.0731,0.075,0.0715,0.082,0.126,0.0775,0.0434,\\\
{}\hfil&{}\hfil&~{}0.1002,0.0475,0.1278,0.0683,0.1077]^{T},\end{array}$

which is the normalized eigenvector of $L$ with respect to its (unique)
eigenvalue $1$.

##  4 Application to Networked Repeated Games

This section considers how to design ZD strategies for a player, $i$, in a
networked repeated game (NRG). We propose a method, called a fictitious
opponent player (FOP).

###  4.1 Fictitious Opponent Player

######  Definition 4.1.

[8] An NRG is a triple $((N,E),G,\Pi)$, where $(N,E)$ is a network graph,
where $N$ is the set of players; $G\in{\mathcal{G}}_{[2;k,k]}$ is a symmetric
game with two players, called the fundamental network game; $\Pi$ is the
strategy updating rule, which describes how each player to update his
strategies using his neighborhood information.

######  Remark 4.2.

  * (i)

$G\in{\mathcal{G}}_{[2;k,k]}$ is symmetric, if $S_{1}=S_{2}:=S_{0}$ and for
any $x,y\in S_{0}$

$c_{1}(x,y)=c_{2}(y,x).$

  * (ii)

If $(i,j)\in E$, then players $i$ and $j$ will play game $G$ repeatedly. In
this paper only the fixed graph is considered. Since $G$ is symmetric, then
the order of two players does not affect the result.

  * (iii)

Such an NRG is denoted by $G^{nr}=((N,E),G,\Pi)$.

Let player $i\in N$, and $\deg(i)=d$. Then she may consider
$N\backslash\\{i\\}$ as one player, called the FOP of $i$, denoted by
$p_{-i}$. Assume $|S_{0}|=k$, the neighbors’ strategies can be considered as
the strategies of $p_{-i}$. That is, $p_{-i}$ has totally $k^{d}$ strategies.

In fact, we need not to distinct different neighbors, hence if
$S_{0}=\\{s_{1},s_{2},\cdots,s_{k}\\}$, then the set of strategies of
$p_{-i}$, denoted by $S_{-i}$, is

$\displaystyle S_{-i}=\\{\underbrace{s_{1}s_{1}\cdots
s_{1}}_{d},\underbrace{s_{1}s_{1}\cdots
s_{2}}_{d},\cdots,\underbrace{s_{k}s_{k}\cdots s_{k}}_{d}\\}.$ (83)

Each $s_{*}\in S_{-i}$ can be expressed as

$s_{*}=(\underbrace{s_{1}s_{1}\cdots
s_{1}}_{d_{1}},\underbrace{s_{2}s_{2}\cdots
s_{2}}_{d_{2}},\cdots,\underbrace{s_{k}s_{k}\cdots s_{k}}_{d_{k}}),$

where $d_{i}\geq 0$ and $d_{1}+d_{2}+\cdots+d_{k}=d$. Hence, we can also
express $s_{*}$ by $(d_{1},d_{2},\cdots,d_{k})$, which means $s_{j}$ has been
used by $d_{j}$ neighbors, $1\leq j\leq k$. Using this notation, we have

$\displaystyle S_{-i}=\\{(d_{1},d_{2},\cdots,d_{k})\;|\;d_{j}\geq 0,\;\forall
j;\;\mathop{\sum}\limits_{j=1}^{k}d_{j}=d\\}.$ (84)

It is easy to verify that define the strategies of $p_{-i}$ in this way, by
ignoring the order of neighbors, the total number of strategies is reduced
from $k^{d}$ to

$|S_{-i}|=\frac{(k+d-1)!}{(k-1)!d!}.$

Hence this treatment reduces the computational complexity.

From the point of view of player $i$, the NRG is equivalent to a game between
she and $p_{-i}$, who has the set of strategies $S_{-i}$ defined by (84). Let
$s_{*}=(d_{1},d_{2},\cdots,d_{k})\in S_{-i}$. Then the payoff functions for
$c_{i}$ and player $p_{-i}$, denoted by $c_{-i}$, are

$\displaystyle\begin{array}[]{l}c_{i}(x_{i},s_{*})=\mathop{\sum}\limits_{j=1}^{k}d_{j}c_{i}(x_{i},s_{j}),\\\
c_{-i}(x_{i},s_{*})=\mathop{\sum}\limits_{j=1}^{k}d_{j}c_{j}(x_{i},s_{j}).\\\
\end{array}$ (87)

Note that the FOP formulation is particularly suitable for using ZD
strategies, because it is not effected by the structure and size of network
graph, even though the size might be $\infty$. As long as the stationary
distribution of the overall network exists, ZD strategies are still
applicable. Moreover, it is easily designable.

###  4.2 ZD Strategies for NRGs

This section considers how to design ZD-strategies for NRGs. We describe the
process through two examples.

######  Example 4.3.

Consider prisoner’s dilemma $G$. The two strategies for both players are
cooperation ($C$) and defect ($D$). Their payoffs are described in Table 1,
where, as a convention, $T>R>P>S$.

Table 1: Payoff bi-matrix of prisoner’s dilemma $P_{1}\backslash P_{2}$ | $C$ | $D$
---|---|---
$C$ | $R,~{}R$ | $S,~{}T$
$D$ | $T,~{}S$ | $P,P$

Consider a networked repeated prisoners’ dilemma, denoted by $G^{nr}$. The
network graph, depicted by Fig. 1, is non-homogeneous.

BAC Figure 1: A Networked Prisoners’ Dilemma

  1. 1.

Consider player A. Since $\deg(A)=2$, The set of strategies of $p_{-A}$ is

$S_{-A}=\\{(CC),(CD),(DD)\\}.$

Using (87), the payoff vectors for $c_{A}$ and $c_{-A}$ are, respectively,

$\begin{array}[]{l}V^{c}_{A}=(2R,R+S,2S,2T,T+P,2P),\\\
V^{c}_{-A}=(2R,R+T,2T,2S,S+P,2P).\end{array}$

It is easy to calculate that $\kappa=6$, and

$\Phi_{1,1}=\\{1,2,3\\},~{}\xi_{1,1}=(1,1,1,0,0,0).$

     * •

Pinning Strategy: To get $Ec_{-A}=r$, the ZD strategy of player A can be
designed as

$(p^{1}_{1,1},p^{2}_{1,1},\cdots,p^{6}_{1,1})=\mu(V^{c}_{-A}-r{\bf
1}_{6}^{T})-\xi_{1,1}.$

     * •

Extortion Strategy: To get $Ec_{A}-r=\ell(Ec_{-A}-r)$ with $\ell>1$, the ZD
strategy of player A can be designed as

$\begin{array}[]{l}(p^{1}_{1,1},p^{2}_{1,1},\cdots,p^{6}_{1,1})=\mu\left((V^{c}_{A}-r{\bf
1}_{6}^{T})-\ell(V^{c}_{-A}-r{\bf 1}_{6}^{T})\right)-\xi_{1,1}.\end{array}$

  2. 2.

Consider player B. Since $\deg(B)=3$, The set of strategies of $p_{-B}$ is

$S_{-B}=\\{(CCC),(CCD),(CDD),(DDD)\\};$

Using (87), the payoff vectors for $c_{B}$ and $c_{-B}$ are, respectively,

$\begin{array}[]{ccl}V^{c}_{B}&=&(3R,2R+S,R+2S,3S,3T,2T+P,T+2P,3P),\\\
V^{c}_{-B}&=&(3R,2R+T,R+2T,3T,3S,2S+P,S+2P,3P).\end{array}$

We have $\kappa=8$ and

$\Phi_{1,1}=\\{1,2,3,4\\},~{}\xi_{1,1}=(1,1,1,1,0,0,0,0).$

The design of ZD strategies is similar to the one for $A$.

  3. 3.

Consider player C. Since $\deg(C)=4$, The set of strategies of $p_{-C}$ is

$\begin{array}[]{ccl}S_{-C}&=&\\{(CCCC),(CCCD),(CCDD),(CDDD),(DDDD)\\};\end{array}$

Using (87), the payoff vectors for $c_{C}$ and $c_{-C}$ are, respectively,

$\begin{array}[]{ccl}V^{c}_{C}&=&(4R,3R+S,2R+2S,R+3S,4S,4T,3T+P,2T+2P,T+3P,4P),\\\
V^{c}_{-C}&=&(4R,3R+T,2R+2T,R+3T,4T,4S,3S+P,2S+2P,S+3P,4P).\end{array}$

It is easy to calculate that $\kappa=10$ and

$\Phi_{1,1}=\\{1,2,3,4,5\\},~{}\xi_{1,1}=(1,1,1,1,1,0,0,0,0,0).$

The design of ZD strategies is similar to the one for $A$, or $B$.

To illustrate the effectiveness of proposed method for large games, we provide
the following example.

######  Example 4.4.

Consider a networked repeated prisoners’ dilemma, denoted by $G^{nr}$. The
network graph, depicted by Fig. 2, is a circular ring with a large number of
nodes.

Figure 2: The Cycle Ring Graph

For any given player $i$, $\deg(i)=2$. The set of strategies of $p_{-i}$ is

$S_{-i}=\\{(CC),(CD),(DD)\\}.$

Using (87), the payoff vectors for $c_{i}$ and $c_{-i}$ are, respectively,

$\begin{array}[]{l}V^{c}_{i}=(2R,R+S,2S,2T,T+P,2P),~{}V^{c}_{-i}=(2R,R+T,2T,2S,S+P,2P).\end{array}$

It is easy to calculate that $\kappa=6$, and
$\Phi_{1,1}=\\{1,2,3\\},~{}\xi_{1,1}=(1,1,1,0,0,0).$

To realize $Ec_{i}-r=0.5(Ec_{-i}-r)$, the ZD strategy of player $i$ can be
designed as

$\begin{array}[]{l}(p^{1}_{1,1},p^{2}_{1,1},\cdots,p^{6}_{1,1})=\mu\left[(V^{c}_{i}-r{\bf
1}_{6}^{T})-0.5(V^{c}_{-i}-r{\bf 1}_{6}^{T})\right]-\xi_{1,1}.\end{array}$

######  Remark 4.5.

  * (i)

In the above discussion we only provide the formula for designing ZD
strategies. A problem is: is the solution $\\{p^{i}_{j,k},k\in[1,k_{i}]\\}$
obtained from the formula permissible. From designer’s point of view, it can
be seen immediately from the numerical result. As for theoretical discussion,
it is a challenging problem and is out of the scop of this paper. We refer to
[32] for the existence of the proper solution.

  * (ii)

When an individual player $i$ in an NRD using ZD strategies, she can
“manipulate” her immediate neighbors’ payoffs from her. That is the payoffs of
the rest of the network got from her. Though it far no means she can
manipulate the whole network’s payoffs, from her individual perspective, it
might be enough.

  * (iii)

Under our FOP formulation, the ZD strategies in the NRG is exactly the same as
the one for non-networked repeated game.

  * (iv)

The existence of the zero-determinant strategies is not trivial. We refer to
[36] for some related discussion. Further investigation on the existence of ZD
strategies for NRGs seems to be necessary and interesting.

##  5 Conclusion

This paper considers the design of ZD strategies proposed by Press and Dyson
for general finite games. Using STP, a fundamental formula is presented to
numerically realize ZD strategies for finite games with multi-player and
asymmetric strategies. In addition to the generality, it simplifies the design
procedure. Then, a necessary and sufficient condition for the availability of
the designed ZD strategies is also obtained, which put the ZD technique on a
solid foundation. Some numerical examples are presented to demonstrate the
efficiency of the method proposed in this paper.

Finally, as an application of the general formula the NRGs are considered. A
new concept, called FOP, is proposed as the opponent player for a preassigned
player $i$. Using it, the ZD strategies for player $i$ is designed for the
game between herself and her FOP. It is interesting that one single player may
be able to “control” the payoff of the rest part of the network from her by
using ZD strategies, no matter how large the network is.

The research was supported by National Natural Science Foundation of China
under Grant 62103232, 62073315 and the Natural Science Fund of Shandong
Province under grant ZR2021QF005.

## References

  * [1] Adami C, Hintze A. Evolutionary instability of zero-determinant strategies demonstrates that winning is not everything. Nature Commun, 2012, 4(1):1-8
  * [2] Akin E, The iterated prisoner’s delemma: Good strategies and their dynamics. In: Ergodic Theory, Advances in Dynamical Systems, Berlin, De Gruyter, 2016. 77-107
  * [3] Cao M, Tang C, Liu Y, Lin F, Chen Z. Application of ZD strategy in mining pool game. In: Proc 38th CCC, 2019. 880-885
  * [4] Chen J, Zinger A. The robustness of zero-determinant strategies in iterated prisoner’s dilemma games. J. Theor. Biology, 2014, 357: 46-54
  * [5] Cheng D Z, Qi H S, Li Z Q. Analysis and control of Boolean networks: A semi-tensor product approach. Springer, London, 2011
  * [6] Cheng D Z, Qi H S, Zhao Y. An introduction to semi-tensor product of matrices and its applications. World Scientific, Singapore, 2012
  * [7] Cheng D Z. On finite potential games. Automatica, 2014, 50(7): 1793-1801
  * [8] Cheng D Z, He F H, Qi H S, Xu T T. Modeling, analysis and control of networked evolutionary games. IEEE Trans Aut Contr, 2015, 60(9): 2402-2415
  * [9] Cheng D Z, Liu T, Zhang K Z. On decomposed subspaces of finite games. IEEE Trans Aut Contr, 2016, 61(11): 3651-3656.
  * [10] Cheng D Z, Liu T. Linear representation of symmetric games. IET Contr Theory Appl. 2017, 11(18): 3278-3287
  * [11] Cheng D Z, Wu Y H, Zhao G D, Fu S H. A comprehensive survey on STP approach to finite games. J Sys Sci Compl, 2021, 34(5): 1666-1680
  * [12] Cheng Z, Chen G, Hong Y. Misperception influence on zero-determinant strategies in iterated prisoner’s dilemma. Scientific Reports, 2022, 12(1): 1-9
  * [13] Govaert A, Cao M. Zero-determinant strategies in repeated multiplayer social dilemmas with discounted payoffs. IEEE Trans Aut Contr, 2020, 66(10): 4575-4588
  * [14] Hao Y, Cheng D Z. On skew-symmetric games. Journal of the Franklin Institute,2018, 355: 3196-3220
  * [15] Hao D, Rong Z H, Zhou T. Zero-determinant strategy: An underway revolution in game theory, Chin Phys B. 2014, 23(7): 078905
  * [16] Hao D, Rong Z H, Zhou T. Extortion under uncertainty: zero-determinant strategies in noisy games, Phys Rev E, 2015, 91: 052803
  * [17] He X, Dai H, Ning P, Dutta R. Zero-determinant strategies for multi-player multi-action iterated games. IEEE Signal Proc Lett, 2016, 23(3): 311-315
  * [18] Hilbe C, Nowak M A, Sigmund K. Evolution of extortion in iterative prisoner’s dilemma games. Proc Natl Acad Sci, 2013, 110(17): 6913-6918
  * [19] Hilbe C, Wu B, Traulsen A, Nowak M A. Cooperation and control in multplayer social dilemmas. Proc Natl Acad Sci, 2014, 111(46): 16425-16430
  * [20] Hilbe C, Traulsen A, Sigmund K. Partners or rivals? Strategies for the iterated prisoner’s dilemma. Games and Economic Behav, 2015, 92: 41-52
  * [21] Horn R A, Johnson C R. Matrix Analysis. Cambridge, Campbidge Univ Press, 1986
  * [22] Li H T, Ding X, Yang Q, Zhou Y. Algebraic formulation and Nash equilibrium of competitive diffusion games. Dyn Game Appl, 2018, 8: 423-433.
  * [23] McAvoy A, Hauert C. Autocratic strategies for iterated games with arbitrary action spaces. Proc Natl Acad Sci, 2016, 113(13): 3573-3578
  * [24] Pan L, Hao D, Rong Z, Zhou T. Zero-determinant strategies in iterated public goods game. Science Reports, 2015, 5: 13096
  * [25] Press W, Dyson F J. Iterated prosoner’s dilemma containes strategies that dominate any evolutionary opponent. Proc Natl Acad Sci, 2012, 109(26): 10409-10413
  * [26] Rong Z, Wu Z, Hao D, et al. Diversity of timescale promotes the maintenance of extortioners in a spatial prisoner’s dilemma game. New Journal of Physics, 2015, 17: 033032.
  * [27] Stewart A J, Plotkin J B. Extortion and cooperation in the prisoner’s dilemma. Proc Natl Acad Sci, 2013, 110(38): 15348-15353
  * [28] Szolnoki A, Perc M. Evolution of extortion in structured populations. Phys Rev E, 2014, 89(2): 022804
  * [29] Taha M A, Ghoneim A. Zero-determinant strategies in repeated asymmetric games. Applied Math Comp, 2020, 369: 124862
  * [30] Tang C, Li C, Yu X, et al. Cooperative mining in blockchain networks with zero-determinant strategies. IEEE Trans Cybernetics, 2020, 50(10): 4544-4549
  * [31] Tan R, Su Q, Wu B, Wang L. Payoff control in repeated games. In: Proc 33rd Chinese CDC, 2021. 997-1005
  * [32] Ueda M, Tanaka T. Linear algebraic structure of zero-determinant strategies in repeated games. PLoS One, 2020, 15(4): e0230973
  * [33] Wang J, Guo J, liu H, Shen A. Evolution of zero-determinant strategy on iterated snowdrift game. Acta Phus Sin, 2017, 66(18): 180203
  * [34] Xu X, Rong Z, Wu Z, et al. Extortion provides alternative routes to the evolution of cooperation in structured populations. Physical Review E, 2017, 95(5), 052302.
  * [35] Zhang J, Lou J, Qiu J, Lu J. Dynamics and covergence of huper-networked evolutionary games with time delay is strategies. Information Sciences. 2021, 563: 166-182.
  * [36] Ueda M, Necessary and sufficient condition for the existence of zero-determinant strategies in repeated games, Journal of the Physical Society of Japan 91, 084801, 2022.

## Appendix

  1. 1.

Proof of Proposition 2.11:

     * (i)

Since $L$ has unique eigenvalue $1$, $\operatorname{rank}(M)=\kappa-1$. Hence
there exists at least one $(\kappa-1)\times(\kappa-1)$ miner of $M$, which is
nonsingular. Hence, $M^{*}\neq 0$. Observing that

$\displaystyle MM^{*}=\det(M)=0,$ (88)

and $\operatorname{rank}(M)=\kappa-1$, it follows that
$\operatorname{rank}(M^{*})=1$.

     * (ii)

Assume there exists $1\leq j\leq n$ such that
$\operatorname{Col}_{j}(M^{*})=0$. Consider
$M\backslash\\{\operatorname{Row}_{j}(M)\\}$, which is obtained from $M$ by
deleting its $j$ th row. Then all its $(\kappa-1)\times(\kappa-1)$ minors have
zero determinants. That is, $M\backslash\\{\operatorname{Row}_{j}(M)\\}$ is
row-dependent.

To get contradiction, we show that any $\kappa-1$ rows of $M$ are linearly
independent. Since
$\mathop{\sum}\limits_{i=1}^{\kappa}\operatorname{Row}_{i}(M)={\bf
0}^{T}_{\kappa}$, $\operatorname{Row}_{j}(M)=-\mathop{\sum}\limits_{i\neq
j}\operatorname{Row}_{i}(M)$. If
$\operatorname{rank}(M\backslash\\{\operatorname{Row}_{j}(M)\\})<\kappa-1$,
then $\operatorname{rank}(M)<\kappa-1$, which is a contradiction.

$\Box$

  2. 2.

Proof of Proposition 2.12:

First we show that the limit exists. Since
$\\{x(t)\;|\;t=1,2,\cdots\\}\subset\Upsilon^{\kappa}$ and $\Upsilon^{\kappa}$
is a compact set, there exists a subsequence
$\\{x_{t_{i}}\;|\;i=1,2,\cdots\\}$ such that

$\lim_{i\rightarrow\infty}x_{t_{i}}=x^{*}\in\Upsilon^{\kappa}.$

Note that $\lim_{t\rightarrow\infty}L^{t}=P$, denote by $x^{0}=Px^{*}$, we
claim that

$\displaystyle\lim_{t\rightarrow\infty}x_{t}=x^{0}.$ (89)

Given any $\epsilon>0$, there exists $N_{1}$ such that when $t_{i}>N_{1}$

$\|x_{t_{i}}-x^{*}\|<\sqrt{\epsilon};$

and there exists $N_{2}>0$ such that when $t>N_{2}$

$\|M^{t}-P\|<\sqrt{\epsilon}.$

Choose an element $t_{i_{0}}>N_{1}$ from the subsequence and set

$N_{3}=t_{i_{0}}>N_{1}.$

Assume $t>N_{2}+N_{3}$, then

$x(t)=M^{t-N_{3}}x(t_{i_{0}}).$

Since $t-N_{3}>N_{2}$ and $N_{3}=t_{i_{0}}>N_{1}$, it follows that

$\|x(t)-x^{0}\|<(\sqrt{\epsilon})^{2}=\epsilon.$

(89) follows. It is also clear that $x^{0}=x^{*}$. Moreover, $Lx^{*}=x^{*}$
and $Px^{*}=x^{*}$. Now since $P=uv^{T}\in\Upsilon_{\kappa\times\kappa}$,
without loss of generality, we can normalize $u$ by replacing $u$ by
$u/\|u\|$. Then $v={\bf 1}_{\kappa}$. Moreover,

$x*=Px^{*}=uv^{T}x^{*}=u.$

$\Box$

  3. 3.

Proof of Proposition 2.13:

Note that $MM^{*}=\det(M)=0$, and $Mu=0$. Since
$\operatorname{rank}(M)=\kappa-1$, the solutions of equation $Mx=0$ is a one-
dimensional subspace. Now each column of $M^{*}$ is a solution, the conclusion
follows.

$\Box$

  4. 4.

Proof of Theorem 3.9:

(Necessity) It is obvious that $\mu$ is a stationary distribution if it
satisfies the following equation

$\displaystyle\lim_{t\rightarrow\infty}L^{t}x_{0}=u,\quad\forall
x_{0}\in\Upsilon^{\kappa}.$ (90)

We first prove $\lim_{t\rightarrow\infty}L^{t}$ exists. Since
$\Upsilon_{\kappa\times\kappa}$ is a compact set, if
$\lim_{t\rightarrow\infty}L^{t}$ does not exist, there must be at least two
subsequences $\\{L^{n_{i}}\\}$, and $\\{L^{m_{i}}\\}$, such that

$\begin{array}[]{l}\lim_{i\rightarrow\infty}L^{n_{i}}=P_{1},\lim_{i\rightarrow\infty}L^{m_{i}}=P_{2},\\\
\end{array}$

and $P_{1}\neq P_{2}$. Say,
$\operatorname{Col}_{s}(P_{1})\neq\operatorname{Col}_{s}(P_{2})$, choosing
$x_{0}=\delta_{\kappa}^{s}$, then it violates (90).

Hence we have decompositions

$\lim_{t\rightarrow\infty}L^{t}=P.$

Again, because of (90) $P$ should have the form that $P=[u,u,\cdots,u]$, the
conclusion is obvious.

As for the condition (ii), if $\operatorname{rank}(L-I_{\kappa})<\kappa-1$,
then $M^{*}=0$ is a zero matrix. Then (35) fails. Hence (35) can never be
obtained from (38), and ZD strategies do not work.

(Sufficiency) Replacing any row $s\in\Phi_{i,j}$ of matrix $M=L-I_{\kappa}$ by
$\xi_{i,j}$, then condition (ii) ensures (26). Using (38) and expanding the
determinant via replaced row, (35) follows. $\Box$


# AI4D - African Language Dataset Challenge

Kathleen Siminyu, Sackey Freshia, Jade Abbott, Vukosi Marivate
Masakhane, Africa
masakhane.io
<EMAIL_ADDRESS>
Kathleen Siminyu
Artificial Intelligence for Development
Africa
<EMAIL_ADDRESS>
Sackey Freshia
Jomo Kenyatta University
of Agriculture and Technology
<EMAIL_ADDRESS>
Jade Abbott
Retro Rabbit
<EMAIL_ADDRESS>
Vukosi Marivate
University of Pretoria
<EMAIL_ADDRESS>

###### Abstract

As language and speech technologies become more advanced, the lack of
fundamental digital resources for African languages, such as data, spell
checkers and Part of Speech taggers, means that the digital divide between
these languages and others keeps growing. This work details the organisation
of the AI4D - African Language Dataset
Challenge111https://zindi.africa/competitions/ai4d-african-language-dataset-
challenge, an effort to incentivize the creation, organization and discovery
of African language datasets through a competitive challenge. We particularly
encouraged the submission of annotated datasets which can be used for training
task-specific supervised machine learning models.

##  1 Introduction

Africa has a language diversity of over 2000 languages, many of which are only
spoken and not written [Eberhard et al., 2019].

As language technologies advance and more sophisticated tools are built using
Artificial Intelligence, the divide between low resource languages and others
is likely to get even larger as a common prerequisite of these advanced
systems is the existence of a large amount of digital data. African languages,
low resource languages, are at risk of being left behind [Joshi et al., 2020].

Data Science and Machine Learning skills are increasingly becoming widespread
on the African continent. This can be attributed to the rise of grassroots
capacity building efforts through organisations such as Data Science
Africa222http://www.datascienceafrica.org/, Data Science
Nigeria333http://datasciencenigeria.ai, Deep Learning
Indaba444https://deeplearningindaba.com/, as well as NLP-specific communities
such as Masakhane555https://www.masakhane.io/ [Orife et al., 2020]. These
movements have facilitated a critical mass of individuals with the relevant
skills, who speak African languages that can start contributing to the overall
body of work that currently exists and begin the work where none does. With
this challenge, we sought to engage the African NLP community in the task of
dataset creation.

##  2 Methodology

The realisation of this work was wholly driven by the intended outcome, the
need for more African language datasets for use in NLP research.

###  2.1 Framing the Challenge

Early framing of this challenge was predicated on the fact that pre-trained
language models are producing state-of-the-art NLP results [Devlin et al.,
2018, Radford et al., 2019]. African NLP would undoubtably benefit from the
creation of such language models, and so the competition was initially
envisioned as a language model challenge. Unfortunately, not only do most pre-
trained language models require large amounts of monolingual data to train,
they require labelled NLP datasets in order to usefully evaluate the models.
This motivated the decision to create a challenge focused on data collection,
rather than model building.

###  2.2 Securing Donor Funding

With the aim of creating datasets that are openly available, we prepared and
circulated a proposal and succeeded in securing donor funding. That being
committed, we tailored the challenge to take place in 2 phases. The initial
phase focused on data collection and the second phase being a more
conventional machine learning (ML) challenge, where the datasets developed in
the first phase could be used as evaluation sets for a pre-trained language
model challenge.

###  2.3 Hosting the Challenge

Our target audience was researchers, practitioners and enthusiasts from
African countries who could create datasets for the languages that they speak.
We approached Zindi666http://zindi.africa, an African data science competition
platform, to host the challenge in a bid to leverage their existing user base.
They have over 12,000 individuals signed up.

###  2.4 Evaluation of Submissions

Unlike a conventional ML challenge that would have an agreed upon automated
metric to evaluate and rank submitted models, evaluation of a challenge of
this kind cannot be automated. Instead, we put together a panel of judges with
experience in NLP who would review the datasets each month. We also indicated
in the challenge guidelines that each dataset submission should be accompanied
by a datasheet [Gebru et al., 2018] that documents its motivation,
composition, collection process, recommended uses, and so on (Example in
Appendix A).

Evaluation was done by judges analysing the datasheets and awarding points to
each submission based on a scoring rubric. The rubric took into account the
following: how representative and balanced the corpus was, the dataset size in
terms of tokens and unique tokens, whether it was annotated for a specific
downstream task, under-representation of the language in terms of digital
data, methodology of the data collection and labelling process, originality of
the data collection and labelling process (Reviewer Documentation in Appendix
B).

##  3 Results

Language | Tasks | Submissions
---|---|---
Yoruba | MT, Diacritic Verification, Text Classification, NER, misc | 7
Kiswahili | Document Classification, misc | 6
Igbo | NER, misc | 4
Hausa | Sentiment Analysis, Document classification, misc | 4
Fongbe | MT, Speech to Text, misc | 3
Amharic | Hate speech detection, stop words list, misc | 3
Asante Twi | Sentiment Analysis, MT, misc | 3
Chichewa | NER, MT | 2
Ewe | MT, misc | 2
Wolof | ASR | 1
Tunizian Arabizi | Sentiment Analysis | 1
Kikuyu | misc | 1
Kabiwe | MT | 1
Oromo | misc | 1
Zulu | misc | 1
Table 1:  Language and Task distribution of submissions.

The challenge ran for a period of five months with a total of 270 people
registering on the Zindi platform to participate.

The data in the submitted datasets was compiled from a wide variety of
sources. These were largely digital sources such as news websites, religious
texts, Facebook, Twitter and YouTube. This outcome is likely an indication of
the ease of access that online sources present, given that the data is already
digitised. Other data creation processes included participants convening to
carry out manual translation of existing pieces of text. Unique contributions
included OCR to digitize printed texts and using the user base of a commercial
application to crowd source and validate recordings of phrases and texts
common on the platform.

Observations and Lessons Learned:

  * •

Teams composed of individuals from relevant multi-disciplinary backgrounds,
including computer scientists, professional translators and linguists, were
able to create and annotate datasets that captured fundamental lexical and
semantic nuances of languages.

  * •

The challenge framing allowed for anyone to participate. While useful as an
exercise in evaluating the interest in such a challenge, the top evaluated
submissions came from teams who had been exposed to NLP research work.
Targeting such a challenge to NLP researchers could lead to higher quality
submissions in future.

  * •

A portion of submissions contained very few data points. As the aim is to use
the datasets for NLP, in future, we’d set explicit minimum requirements with
regards to the size of datasets admissible, file formats and require the
inclusion of any cleaning or pre-processing code used.

  * •

Since the challenge was evaluated monthly, we often received disparate
submissions from the same teams as they managed to obtain more data. Instead,
one large dataset built over a couple of months would have been the ideal
outcome, so in future we’d select and support teams for a sustained period of
time to enable them build sizeable datasets.

  * •

Participants and judges had to rely on their own understanding of what
”Representative and Balanced” means in a dataset. In future, more specificity
of what ”representative” and ”balanced” means would enable participants to
produce better datasets.

##  4 Future Work

A large number of opportunities were identified to support future work in
African, and low resource, language dataset creation, as follows:

  * •

Research and analysis of the legal implications of obtaining textual, visual
and audio data from a variety of online sources, which were noted as a common
source among participants. The copyright and intellectual property
implications will have to be thoroughly assessed ahead of the publication and
further public use of relevant datasets.

  * •

Outlining of best case practise techniques for protecting the identities and
privacy of users, in instances where data is obtained from social
media/content platforms like Twitter, Facebook and YouTube. Social media sites
have been noted as a common data source.

  * •

Recommended techniques for identifying and ascertaining whether data obtained
from online sources(news publications,social media and content platforms)
contains biased sentiments(sexist, racist) and offensive material(hateful), as
well as techniques for removing any biased sentiment and offensive material,
if need be, depending on the use of the dataset.

Courtesy of this dataset creation challenge, we have secured further funding
to support 5 of the top teams for a 6 month period. During this time, they
will further flesh out their datasets with the aim of using these as the basis
of future NLP challenges/shared tasks. This project will also be used as a
model case to inform evidence-based policy making concerning Artificial
Intelligence and we hope that it will be replicated to support the development
of data for other low resource languages.

## Acknowledgements

This work has been funded through a partnership between the International
Development Research Centre, the Swedish International Development Cooperation
Agency, the Knowledge4All Foundation, Zindi Africa and the AI4D-Africa
Network. The expert panel that volunteered their time to undertake the
difficult qualitative task of dataset assessment was composed of Jade Abbott -
Retro Rabbit, John Quinn - Google AI / Makerere University, Kathleen Siminyu -
AI4D-Africa, Veselin Stoyanov - Facebook AI and Vukosi Marivate - University
of Pretoria.

66footnotetext:  This work is licensed under a Creative Commons Attribution
4.0 International Licence. Licence details:
http://creativecommons.org/licenses/by/4.0/.

## References

  * [Devlin et al., 2018]  Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  2018\.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805.
  * [Eberhard et al., 2019]  David M Eberhard, Gary F. Simons, and Charles D. Fenning.  2019\.  Ethnologue: Languages of the worlds. twenty-second edition.
  * [Gebru et al., 2018]  Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumeé III, and Kate Crawford.  2018\.  Datasheets for datasets.  arXiv preprint arXiv:1803.09010.
  * [Joshi et al., 2020]  Pratik M. Joshi, Sebastin Santy, Amar Budhiraja, Kalika Bali, and Monojit Choudhury.  2020\.  The state and fate of linguistic diversity and inclusion in the nlp world.  ArXiv, abs/2004.09095.
  * [Orife et al., 2020]  Iroro Orife, Julia Kreutzer, Blessing Sibanda, Daniel Whitenack, Kathleen Siminyu, Laura Martinus, Jamiil Toure Ali, Jade Abbott, Vukosi Marivate, Salomon Kabongo, et al.  2020\.  Masakhane–machine translation for africa.  arXiv, pages arXiv–2003.
  * [Radford et al., 2019]  Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  2019\.  Language models are unsupervised multitask learners.  OpenAI Blog, 1(8):9.

## Appendix A: Copy of Outstanding Submission Datasheet

## Appendix B: Copy of Reviewer Documentation