Unexploitable games and unbeatable strategies

Imitation is simple behavior which uses successful actions of others in order to deal with one’s own problems. Copying the behavior of others is sometimes successful in human society [1]. In biological systems, a mechanism such that genes are passed from parents to offspring is naturally adopted [2]. In economics, it has been discussed that equilibria are realized not due to rational thinking but due to imitation [3, 4]. On the other hand, piracy is generally prohibited in creative activities [5]. When there are multiple agents who imitate others, complicated dynamics can occur [6]. In general, success of imitation depends on whether profit of a copying agent coincides with those of other agents or not, which is a subject of game theory [7].

When we restrict our attention to repeated two-player symmetric games, one of the candidates which characterize successfulness of imitation is unbeatability [8, 9]. Unbeatability literally means that the imitating agent cannot be beaten, or, cannot be exploited. For infinitely repeated two-player symmetric games, it has been known that there exists an unbeatable imitation strategy, called the Imitate-If-Better (IIB) strategy, if and only if the game does not contain any cycles similar to the rock-paper-scissors cycle [8]. Furthermore, it has also been proved that the Tif-for-Tat (TFT) strategy [10, 11], which imitates the opponent’s previous action, is unbeatable if and only if the game is a potential game [9].

Recently, it has been pointed out that the existence of unbeatable imitation strategies may be related to the existence of unbeatable zero-determinant (ZD) strategies [12]. ZD strategies are a class of memory-one strategies in infinitely repeated games, which unilaterally enforce linear relationships between payoffs of players [13]. Although ZD strategies were originally introduced in the prisoner’s dilemma game, they have been extended to broader situations [14, 15, 16, 17, 18]. Furthermore, the control ability of ZD strategies has also been extended [19, 20, 21]. As application studies, ZD strategies have been applied to several problems in the field of information and communications technology, such as resource sharing in wireless networks [22, 23], mining in blockchain [24], crowdsourcing [25], the Internet of Things [26], cloud computing [27], and data trading [28]. In terms of unbeatable strategies, the author proved that the unbeatable TFT is a ZD strategy in two-player symmetric games [29]. In addition, for two-player symmetric games where the unbeatable imitation strategy exists, unbeatable ZD strategies also exist [12]. These results suggest that there may be some relation between the existence of unbeatable imitation strategies and the existence of unbeatable ZD strategies, even in multi-player symmetric games.

The purpose of this paper is investigating the existence of unbeatable imitation strategies and unbeatable ZD strategies in multi-player totally symmetric games [30]. Concretely, we introduce a class of multi-player totally symmetric games called unexploitable games. Unexploitable games are an extension of two-player symmetric games without generalized-rock-paper-scissors cycles to multi-player case. We show that the unexploitable property of the stage game is a sufficient condition for the existence of unbeatable ZD strategies and the unbeatable IIB strategy. We also explain these results in the public goods game [31], which is the simplest example of unexploitable games.

This paper is organized as follows. In Section II, we define a model of infinitely repeated multi-player totally symmetric games. In Section III, we introduce basic concepts used in the later sections, such as ZD strategies, unbeatable strategies, and imitation strategies. In Section IV, we introduce the concept of unexploitable games, and provide our main results on the existence of unbeatable ZD strategies and unbeatable imitation strategies in unexploitable games. In Section V, we demonstrate our results in the public goods game. Section VI is devoted to concluding remarks.

We consider an infinitely repeated game with $N$ players [32]. The stage game is $G:=\left(\mathcal{N},\left\{A_{j}\right\}_{j\in\mathcal{N}},\left\{s_{j}\right\}_{j\in\mathcal{N}}\right)$, where $\mathcal{N}:=\left\{1,\cdots,N\right\}$ is the set of players, $A_{j}$ is the set of actions of player $j\in\mathcal{N}$, and $s_{j}:\prod_{k=1}^{N}A_{k}\rightarrow\mathbb{R}$ is the payoff of player $j\in\mathcal{N}$. We collectively write $\mathcal{A}:=\prod_{j=1}^{N}A_{j}$ and $\bm{a}:=\left(a_{1},\cdots,a_{N}\right)\in\mathcal{A}$, and call $\bm{a}$ an action profile. We write a probability $L$-simplex by $\Delta_{L}$. We also introduce the notations $a_{-j}:=\left(a_{1},\cdots,a_{j-1},a_{j+1},\cdots,a_{N}\right)\in\prod_{k\neq j}A_{k}$ and $-j:=\mathcal{N}\backslash\left\{j\right\}$. (Below, when we want to emphasize the action of player $j$ in $\bm{a}$, we write $\bm{a}=\left(a_{j},a_{-j}\right)$.) We assume that the stage game is totally symmetric [30], that is, $A_{j}=A$ $(\forall j\in\mathcal{N})$ and for every permutation $\pi$ on $\mathcal{N}$,

for any $j\in\mathcal{N}$ and for any $\bm{a}\in\mathcal{A}$, where $\bm{a}_{\pi}:=\left(a_{\pi(1)},\cdots,a_{\pi(N)}\right)$ and $A$ is some set. We also assume that $A$ is finite, and write $A=\left\{1,\cdots,L\right\}$, where $L\in\mathbb{N}$ is the number of actions.

We repeat the stage game $G$ infinitely. We write an action of player $j$ at round $t\geq 1$ as $a_{j}^{(t)}$. The behavior strategy of player $j\in\mathcal{N}$ is described as $\mathcal{T}_{j}:=\left\{T^{(t)}_{j}\right\}_{t=1}^{\infty}$, where $T^{(t)}_{j}:\mathcal{A}^{t-1}\to\Delta_{L}$ is the conditional probability at $t$-th round. We write the expectation of the quantity $B$ with respect to strategies of all players by $\mathbb{E}[B]$. We consider the case that the payoff of player $j\in\mathcal{N}$ in the infinitely repeated game is given by

that is, we consider a repeated game with no discounting.

We remark that we frequently use the prime symbol to generate more variables whose types are the same as ones without the prime symbol.

In this section, we introduce several concepts used in later sections. We define the marginal distribution at $t$-th round obtained from the joint distribution of action profiles

for all $\bm{a}^{(t)}\in\mathcal{A}$, and the limit distribution

We also write the expectation with respect to the limit distribution $P^{*}$ by $\left\langle\cdots\right\rangle^{*}$. It should be noted that $\mathcal{S}_{k}=\left\langle s_{k}\right\rangle^{*}$ $(\forall k\in\mathcal{N})$.

The purpose of this paper is to find situations where unbeatable ZD strategies or unbeatable imitation strategies exist for the case $N>2$. For this purpose, as an extension of games without generalized rock-paper-scissors cycles in the case $N=2$ [40, 8], we introduce the concept of unexploitable games. First, we define

for all $j\in\mathcal{N}$.

It should be noted that the definition does not depend on $j$ because the stage game is totally symmetric. We also call an unexploitable game trivial if $s_{k}=s$ $(\forall k\in\mathcal{N})$ with a function $s$. For trivial unexploitable games, since the payoffs of all players are always the same, all strategies are trivially unbeatable. Below we mainly focus on non-trivial unexploitable games.

In this section, we investigate the public goods game as an example of unexploitable games. The public goods game is one of the simplest $N$-player totally symmetric games [31, 41, 42]. The set of actions $A$ is usually described as $A=\{C,D\}$, where $C$ and $D$ means cooperation and defection, respectively. The payoff of player $j\in\mathcal{N}$ is given by

where $c>0$ represents the unit of contribution and $1<r<N$. It should be noted that

that is, $D$ dominates $C$.

Next, for the public goods game, we calculate $G_{j}$ in Eq. (17). If $D$ is contained in $a_{-j}$, $G_{j}$ is the payoff of the player taking $D$. If $D$ is not contained in $a_{-j}$, $a_{-j}=(C,\cdots,C)$ and the payoffs of all players in $-j$ are equal to each other. Therefore, we obtain

Then we find that

Particularly,

Because possible subsets of $A$ are $\{C\}$, $\{D\}$, and $\{C,D\}$, and Eq. (18) trivially holds for $A^{\prime}=\{C\},\{D\}$, this inequality means that the public goods game is an unexploitable game. Therefore, Theorems 1 and 2 guarantee the existence of an unbeatable ZD strategy and an unbeatable IIB strategy, respectively.

According to Ref. [12], such unbeatable ZD strategy is constructed as

or

This strategy can be regarded as a variant of TFT, which returns cooperation if and only if all other players took cooperation in the previous round. In fact, it is reduced to TFT for the case $N=2$.

Furthermore, for the public goods game, IIB is rewritten as

Particularly,

This is nothing but the Trigger strategy [43], which returns $C$ as long as all players take $C$ in the previous round and forms a cooperative Nash equilibrium.

In this paper, we introduced the concept of unexploitable games as a class of $N$-player totally symmetric games with $N\geq 2$, which is an extension of non-generalized-rock-paper-scissors games for $N=2$. We then proved that, for infinitely repeated non-trivial unexploitable games, there exist unbeatable ZD strategies. In addition, we also proved that, for infinitely repeated unexploitable games, the IIB strategy is unbeatable. These results are a natural extension of ones for $N=2$. We also showed that the public goods game is an unexploitable game, and constructed an unbeatable ZD strategy. For the public goods game, unbeatable IIB is also equivalent to the Trigger strategy.

Although we investigated only repeated games in which the same stage game is infinitely repeated, there are many situations where the stage game changes over time or the stage game depends on past plays, such as board games. Investigating successfulness of imitation in these dynamic games is a challenging future problem.

Before ending this paper, we make three remarks. The first remark is related to necessary conditions for IIB to be unbeatable. Although unexploitable property of the stage game is a sufficient condition for IIB to be unbeatable, we could not prove that it is also a necessary condition at this stage. However, for the case $N=2$, it is a necessary and sufficient condition [8]. Further investigation is needed to specify a necessary and sufficient condition for IIB to be unbeatable. In addition, one may expect that the existence of unbeatable ZD strategies and that of unbeatable imitation strategies are related to each other. Techniques used for the proofs of the existence in this paper seem to be similar but different, as we used the existence of the strongest action and the weakest action for the proof of the former, and the order of strength of actions for the proof of the latter. Clarifying the relation between these two strategy classes is the subject of future work.

The second remark is one about finiteness of the action space. In this paper, we assumed that the set of actions $A$ is finite. However, there are many situations that $A$ is infinite, such as the Cournot oligopoly game [7]. Since we have used that $A$ is finite in the proofs of Theorems 1 and 2, we do not know these theorems can be straightforwardly extended to the case that $A$ is infinite. We would like to investigate whether these results can be extended to the case that $A$ is infinite or not, in future.

The third remark is the relation between unexploitable games and potential games [44]. For the case $N=2$, potential games are a special case of unexploitable games [8]. However, for its proof, a special property of $N=2$ was used. For $N>2$, the relation between unexploitable games and potential games is not clear. In fact, it has been known that, for the Cournot oligopoly game, which is an example of totally symmetric potential games with infinite action space, IIB can be beaten [8]. We are interested in clarifying the relation between unexploitable games and potential games for general $N\geq 2$.