Emergence and Stability of Self-Evolved Cooperative Strategies using Stochastic Machines

Our proposed model uses stochastic Moore machines to represent sequential behaviors. SMMs have been studied in the context of strategy modeling in literature, and in fact there exist algorithms such as MDI [15], GIATI [16] that can be used to approximate and predict the stochastic automaton used by one’s opponent [17]. A stochastic Moore machine is a tuple $M=\langle S,s_{0},\Phi,\Lambda,T,G\rangle$ where:

• •

  $S=\{s_{0},...,s_{n}\}$ is a finite set of states.

• •

  $s_{0}$ is the initial state.

• •

  $\Phi$ is the set of input alphabets (observations).

• •

  $\Lambda$ is the set of output alphabets (actions).

• •

  $T:S\bigtimes\Phi\mapsto[0,1]^{n+1}$ is the transition probabilities between states.

• •

  $G:S\mapsto\Lambda$ is the mapping between state and action.

This automaton, when at state $s_{i}\in S$, takes in input $\phi\in\Phi$ and moves to any state $s_{j}$ with probability $p_{j}(s_{i},\phi)$, and performs action $\lambda\in\Lambda$. For this paper, $\Phi=\{C,D\}$ and $\Lambda=\{C,D\}$ represent each agent’s choice between cooperation (C) and defection (D).

In order for the probabilistic automaton (PA) to be valid, the transition probabilities must satisfy the following condition:

and

The number of states in the PA thus represents the size of memory of the agent, and a larger number of states would allow for the description of richer behavioral schemas. Ben-Porath [18] utilized the minimal number of states necessary to define a strategy as its complexity measure, hence we can also treat the number of states as a measure of strategy complexity.

Our choice of SMMs to represent sequential strategies was inspired by previous works on automata [7] [18]. While most work on this topic has used deterministic automata, we believe that a stochastic model is necessary in solving certain games. For instance, it allows for fair coordination in games with dominance structure, as will be discussed in Section IV (c).

The stochastic Moore machine modeling of sequential behavior is ideal for use in evolutionary algorithms, as it readily gives a genotypic representation of behavior. Specifically, we can represent the evolvable genotype of a Moore machine as $\langle T,\Theta,G\rangle$, where:

• •

  $T:S\bigtimes\Phi\mapsto[0,1]^{n+1}$ is the transition probabilities between each pair of states.

• •

  $\Theta=\{\theta_{0},...,\theta_{n}\}$ is the probability vector of starting at each state, such that $p(s_{0}=s_{i})=\theta_{i}$.

• •

  $G:S\mapsto\Lambda$ is the mapping between each state $s_{i}$ and its corresponding action

Since both $T$ and $\Theta$ are comprised of real numbers, we can develop various numerical functions to manipulate these quantities and model certain phenomena. For instance, we model mutation as the addition of Gaussian noise upon $T$ and $\Theta$, which implicitly changes the behavior of the agent by modifying the transition and initial probabilities of its states.

The difficulty in applying Gaussian addition onto probability vectors is that it may break the constraints defined in Equation 1 and 2. In past works, this was resolved by normalizing the probability vector after additive mutation [8]. However, this approach leads to asymmetry in the direction of mutation, because a negative mutation ($\delta<0$) is scaled up by normalization while a positive mutation ($\delta>0$) is scaled down. Figure 2 illustrates the net result of this behavior. The presence of such a bias makes the mutation mechanism unsuitable for evolutionary simulation due to its compounding effects on the population genome.

To mitigate this effect, and to improve upon previous methods we propose a novel mutation mechanism for probability vectors. We know that in order for transition probabilities to sum up to one, net changes to the probabilities vector must be zero, i.e. $\sum\mathcal{N}(0,\sigma^{2})=0$. We achieve this by pairing randomly-chosen entries of the probability vector $p(s,\phi)=T_{s\phi}$, where $s\in S,\phi\in\Phi$, when applying Gaussian mutation. That is, when performing a mutation operation, we pick $i,j$ such that $i\neq j$ to perform $mutate(i,j,s,\phi)$, defined as

This operation can be performed indefinitely with the probabilities sum remaining invariant. However, the non-negative constraint on probability values as expressed in Equation 2 may still be violated when the magnitude of a negative mutation is larger than the current probability value. To mitigate this, we make adjustments to the value of $\delta$ in $mutate(i,j,s,\phi)$ prior to applying the mutation,

When applied to a 2D vector, our proposed mechanism leads to a near-even distribution of values for a gene, as illustrated in Figure 2 (b). It is also empirically shown to be generalizable to N-dimensional vectors (refer to the Appendix). On the basis that an unbiased mutation mechanism should not favor any particular gene, we also devised a metric to compare the performance of our mechanism with linear normalization by measuring the closeness of fit between the observed frequency of genes with the highest value under mutation operations (hereon referred to as highest-value frequency) with that of a uniform distribution. We defined the null hypothesis as the highest-value frequency being drawn from a non-uniform distribution, and calculated its p-value as one minus the probability obtained through Chi-square test. Hence, a low p-value indicates a greater confidence in an unbiased distribution. Fig. 3 shows that our proposed mechanism outperforms the conventionally-used mutation mechanism in this regard, maintaining low p-values across iterations.

We acknowledge that this operation may still introduce bias at the boundaries of the interval $[0,1]$ due to the clipping effects of Equation (4), and hope to address this issue in future works.

In order to model interaction we look at interactions between agents from an evolutionary game theory perspective, where each agent seeks to maximize its utility to increase its likelihood of survival and propagation. Although we do not explicitly program this objective into the agents, it emerges out of evolutionary pressure, as agents that perform well in their interactions with other agents are assigned higher fitness scores and thus can potentially stick around longer in the simulation.

We model the environment as a fixed-size population $\{M_{0},...,M_{n-1}\}$, where each $M_{i}$ represents one of the $n$ agents. To compute the fitness value of an agent, we pit it against every other agent $M_{j}$ in the population in an iterated game. We use a relative fitness metric based on each agent’s interactions with the rest of the population. The scores from a pairwise interaction can be calculated through repeated simulation. In every interaction, each pair of agents will play an iterated 2x2 normal form game for k iterations, and in each iteration the states $s_{it}$ and $s_{jt}$ of both SMMs will be tracked and updated. The payoff $u_{i}$ for a certain agent $M_{i}$ is then calculated as follows, where $M_{j}$ is the opponent:

Since the approach described above is computationally expensive, we devised a set of matrix operations that yield the time-average payoff of (5) at equilibrium. The implementation details of which are given in the Appendix.

We compute the cumulative score of an agent by adding up its pairwise score against all other agents,

which we then use as a metric of fitness in determining their survival and reproductive chances.

The chosen 2x2 normal form games are based on their game-theoretic qualities. We decided to investigate Prisoner’s Dilemma because of its interesting properties and for its lasting influence on the game theory community. We also included results from Chicken, Stag Hunt, and Battle in the Appendix.

To better understand the conditions leading to the emergence of cooperation, we analyzed the evolutionary graph of one particular selection paradigm with strong survival pressure (Paradigm (a) in Table I).

The evolutionary graph of one simulation instance is illustrated in Figure 5. Here, we noticed three distinct phases that the population went through, indicated by the red lines in the figure. By comparing the SMMs present at the windows marked by the respective phase lines (each window is defined as an average of 5 iterations), we built the following evolutionary narrative:

In the first phase (Figure 6 (a)), exploitative strategies prevailed in which cooperation was mixed with occasional defection. To counter these exploitative strategies, the agents became increasingly unforgiving towards defection, resulting in a steady increase in defection rates from window 5 to window 13. From window 13 onwards, all the SMMs had a near-zero chance of returning to the cooperative state after they had seen one defection (ie. become triggered), as can be seen in Figure 6 (b). As a result, exploitative strategies became undesirable, and the rate of defection following mutual cooperation began to dwindle. This eventually lead to more consistent cooperation, and the perfecting of the grim trigger strategy at around window 22 (Figure 6 (c)).

Grim strategy, a member of the larger class of trigger strategies, is an example of an automaton with trapping states in which a past action is remembered for the rest of the interaction [20]. We observed that this convergence towards the grim trigger strategy occurred consistently across most simulations in which cooperation emerged. When interacting with other strategies, such as pure Tit-for-Tat or occasionally-exploitative Tit-for-Tat, grim strategy punishes any defection with unforgiving retaliation but rewards cooperation with reciprocation. It is thus in any other strategy’s best interest to not defect against the grim strategy.

Moreover, we observed that after the emergence of grim strategy, the population remained stable and undisturbed by mutant invaders. The transition probabilities in the post-cooperation generations reveal that mutations do occur in the form of increasing forgiveness or exploitation rate, but these deviant strands did not prove to be beneficial to the agent and are therefore selected away before they can effectively change the population makeup. The population converged at an evolutionarily stable state as was defined by Smith: a population in which the genetic composition is restored by selection after a disturbance, provided the disturbance is not too large [1]. This however does not preclude the possibility that the existing strategies could be invaded by genetically distinct strategies, since every mutant in the evolutionary paradigm shared genetic ties with their parents. Thus, we could not conclusively verify the stronger assertion that the population converged at an evolutionarily stable strategy.

Another aspect that we investigated was the polymorphism of the evolved population, that is, whether we had not just a single strategy but rather a composition of strategies resisting disturbance. The existence of such heterogeneous populations is discussed in the next subsection.

We considered the possibility that the population may consist of distinct strategies that work well in the presence of each other – a group of mutually compatible strategies in an evolutionarily stable state. We therefore propose two approaches to the categorization of behaviorally isomorphic agents.

1. Clustering: If we were to define a function that measures the similarity in behavior between two agents, which can be thought of as a Kernel function, we would be able to make use of the wide gamut of clustering algorithms for our goal of clustering agents according to their behavior. Unfortunately, computing the similarity or showing equivalence of two finite-state automata has been shown to be undecidable [21]. Therefore, the best we could do is to interpret our agents as finite-state machine graphs and use graph similarity metrics, of which there are many [22], to compute the similarity between two agents. We plan to provide an analysis of behavioral profiles in future studies.

2. Behavioral Isomorphism: Since measuring the structural similarity between two non-deterministic machines has been shown to be undecidable, we looked at measuring behavioral similarity instead. In our experiments, we observed that the actions played by the agents in each interaction increased greatly in homogeneity after the first few dozens of iterations as agents that took different and more inferior actions were quickly selected away. Our observation is consistent with the concept of convergence as defined by Creedy [23], who stated that convergence is reached when the different machines in the population play the same actions for the duration of all repeated games. These machines can be therefore can be treated as behaviorally (not necessarily structurally) identical.

Building on this definition, we propose a simple metric to quantitatively measure the behavioral homogeneity of a population at $t$-th iteration by considering the equilibria of pairwise interactions:

where $a_{i}$ is the action probability of $M_{i}$ at horizon, and $n$ is the number of agents.

This equation finds the average mean-squared error of the horizon action probability between each pair of agents. If in horizon the pair of interacting agents have the same probability of cooperating/defecting, then they are said to be behaviorally similar under this metric. Some information may be lost due to this generalization, for instance we would not be able to differentiate a grim strategy from a Tit-for-Tat because Tit-for-Tat will be able to emulate the behavior of grim strategy within one move. But in the context of finding convergent behavior this metric still serves to inform us whether certain agents behaviorally dominate others.

To test the merit of our proposed metric, we computed it across simulations of 200 generations. We observed that $D(t)$ dropped to near zero-value in around 10 generations on average, implying that the different machines began to act homogeneously early on, and that we have a behaviorally isomorphic population by the end of the simulation. Therefore, a single agent can be considered an accurate representation of the population when discussing our results.

To demonstrate the generalizability of our proposed mutation mechanism and experimental setup, we ran simulations for other well-known games such as Chicken, Stag Hunt, and Battle under selection paradigm (a). We have included the resulting simulation graphs as well as one SMM agent (sampled from near-homogeneous populations) for each game in the Appendix.

We chose these games because they are symmetric and have interesting Nash equilibria. For instance, the Battle game (Figure 7) presents a unique coordination challenge for its players, as the Pareto outcome arises when one player takes the opposite action of the other player (e.g. CD or DC), with the cooperator receiving the smaller payoff. It is thus necessary for any surviving strategy to strike a balance between compromising and asserting dominance in the game.

The SMMs that evolved from our experimental setup achieved this balance through effective use of randomization. For instance, when DD occurs, the agents have a 63% chance of switching to cooperation in the next round. The likelihood that they both end up with an undesirable outcome (CC or DD) is thus $0.63*0.63+0.37*0.37\approx 0.53$, allowing them to achieve Pareto outcomes around 50% of the time, equivalent in performance to that of the mixed strategy Nash equilibrium.

Similarly, the evolved SMMs of Chicken and Stag Hunt also have an average performance equal to their respective mixed strategy Nash equilibria. These examples thus reveal that the proposed approach can be used to discover equilibrium strategies in games beyond IPD, and do so efficiently in very few iterations.

We assessed the proposed mechanism by comparing fit of its resulting gene-value distribution with the theoretical distribution of uniformly-sampled probability vectors (derivations can be found in the GitHub repository mentioned above),

Figure 8 illustrates the simulation result for 8D probability vectors under both linear normalization and the proposed mechanism. As indicated by (8), the theoretical distribution is in fact not uniform in N-dimensional spaces where $N>2$, but instead forms a polynomial curve.

The proposed mechanism yielded a good fit to the theoretical distribution, achieving $p<0.05$ fit across all tested dimensions (2D to 8D) at 100,000 iterations. Hence, we assert that the applicability of the mechanism generalizes to higher dimensions.

Let $\mathbf{p}_{t}$ represent the state probability vector of a SMM at a given time $t$, such that $\mathbf{p}_{0}=\Theta$ which is the probability vector of starting at each state. Referring to the definition of an evolvable genotype of Moore machine $\langle T,\Theta,G\rangle$, we model the interaction between two SMM as follows:

where $T(\phi_{k})$ is a matrix of state-to-state transition probabilities given input $\phi_{k}$, and $\mathbf{a}_{it}$ is the action probability vector of machine $M_{i}$ at iteration $t$. The same applies for machine $M_{j}$, with $i$ and $j$ flipped in the above equation. Empirically, we found that the above matrix operations converges in around 5 operations, and the resulting probability distribution gives accurate horizon values as tested by running repeated simulations for thousands of repetitions. We used this method to run the simulations discussed in this paper.