$\displaystyle\
\,c(({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}4})$
$\displaystyle,\Omega)=1:$ $\displaystyle\hskip
19.91684pt({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}4})\stackrel{{\scriptstyle
1}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}4})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}4})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}4})\in\Omega.$

The following example demonstrates that Theorem 7.9 cannot be generalized to
all mixed binary-type populations.

######  Example 7.17.

Consider a population with
$({\color[rgb]{1,0,0}m^{a}},{\color[rgb]{0,0.88,0}n^{a}},{\color[rgb]{1,0,0}m^{c}},{\color[rgb]{0,0,1}n^{c}})=({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}3})$.
The payoff matrices are set to result in the following utility functions (Fig.
7):

Figure 7: Utility functions of the conformists and nonconformists in Example
7.17.

$\displaystyle C^{a}(n^{C})=-\frac{26}{25}n^{C}+\frac{473}{50},$
$\displaystyle D^{a}(n^{C})=\frac{21}{100}n^{C}+\frac{341}{100};$
$\displaystyle C^{c}(n^{C})=\frac{451}{400}n^{C}-\frac{241}{80},$
$\displaystyle D^{c}(n^{C})=-\frac{81}{100}n^{C}+9.$

Therefore, the tempers are
$({\color[rgb]{0,0.88,0}\tau^{a}},{\color[rgb]{0,0,1}\tau^{c}})=({\color[rgb]{0,0.88,0}4.84},{\color[rgb]{0,0,1}6.2})$.
The dynamics have three equilibria

$\bm{x}=({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0}),\quad\bm{y}=({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0}),\quad\bm{z}=({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}3}).$

It is straightforward to see that there is no other minimal invariant set.
Indeed, starting from each of the $72$ different states, we can find an
activation sequence leading to one of the equilibria under the unperturbed
dynamics. We estimate the minimum cost of transition from each of these
equilibria to the others.

_Case 1:_ Transition between two mixed equilibria. Consider the following path
from $\bm{x}$ to $\bm{y}$:

$\displaystyle\bm{x}\to({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})\to\bm{y}.$

The cost of the first step equals $1$ as it requires an anticoordinating
imitator that is cooperating to become active and make a mistake. However, the
second step is costless, for at
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$,
cooperation is the optimal strategy for imitators (Fig. 7). Hence,
$c(\bm{x},\bm{y})=1$. Similarly, $c(\bm{y},\bm{x})=1$.

_Case 2:_ Transition between a mixed and an extreme equilibrium. Consider the
following path from $\bm{z}$ to $\bm{x}$:

$\displaystyle\bm{z}\stackrel{{\scriptstyle
1}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}3})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}2})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0}$
$\displaystyle,{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}1})$
$\displaystyle\downarrow{\\!\scriptstyle 0}$
$\displaystyle({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0}$
$\displaystyle,{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})\stackrel{{\scriptstyle
0}}{{\to}}\bm{x}.$

Since at $\bm{z}$, cooperation and defection are both optimal, the first step
of this path takes place only if an anticoordinating imitator that is
cooperating becomes active and trembles. All the later steps are costless
(steps 5 and 7 are costless because of the optimality of defecting at their
initial states). Hence, $c(\bm{z},\bm{x})=1$. Similarly, it can be shown that
$c(\bm{z},\bm{y})=1$. We show that $c(\bm{x},\bm{z})\geq 2$. Suppose not. Then
there is a path of cost $1$ from $\bm{x}$ to $\bm{z}$. We assume, without loss
of generality, that the second state on this path is not $\bm{x}$ itself.
Hence, the first step needs exactly one mistake, while other steps are all
costless. The second state would be one of the following points:

$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}1}).$

However, no costless path starting from one of these states leads to $\bm{z}$.
To see this, again without loss of generality, we limit ourselves to paths
without the same consecutive states. If the initial state is either
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$
or
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})$,
the second step would be one of $\bm{x}$ and $\bm{y}$. These are equilibrium
states, and leaving them is impossible unless the active agent trembles.
Starting from
$({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$,
the next state is $\bm{x}$. A costless path with the initial state
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$,
has either $\bm{x}$, or
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})$
as the second state. In the latter case, the third step is
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})$,
which was proved to lead to $\bm{x}$ or $\bm{y}$. Finally, if the path starts
at
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}1})$,
in one step it goes to one of $\bm{x}$ and
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}1})$.
In the latter case, the next step will be
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$
that was investigated before. Similarly, it can be shown that
$c(\bm{y},\bm{z})\geq 2$.

Case 1 together with Case 2 implies (see (35))

$\displaystyle\gamma(\bm{x})=\gamma(\bm{y})=2\qquad\text{and}\qquad\gamma(\bm{z})\geq
3.$

According to Proposition 7.5, the maximal stochastically stable set is
$\\{\bm{x},\bm{y}\\}$, which is empty of extreme equilibria.

##  8 Concluding Remarks

We have studied mixed populations of imitators, conformists and nonconformists
who asynchronously decide between cooperation and defection over time,
resulting in the population dynamics. We have found the necessary and
sufficient condition for a population state to be an equilibrium. The
equilibria take a similar structure to those of exclusive populations of
conformists and exclusive populations of nonconformists. That is, one can find
an anticoordinating benchmark type $j_{1}$ and a coordinating benchmark type
$j^{\prime}_{1}$ such that at equilibrium, all nonconformists with thresholds
higher than or equal to that of $j_{1}$ and conformists with thresholds lower
than or equal to that of $j^{\prime}_{1}$ cooperate and all other best-
responders defect [26, 27]. The structure is also similar to those of
exclusive populations of imitators, where either all imitators cooperate, all
defect, or there are both a cooperating and defecting highest earner in the
population.

The stability results imply that in general populations, the extreme
equilibria where the imitators either all cooperate or all defect are most
likely the only equilibria that are stable against changes in strategies.
Furthermore, the stochastic stability results imply that at least in the
binary-type case, if the extreme state corresponding to each mixed equilibrium
is an equilibrium, then at least one extreme equilibrium is stochastically
stable; unless no other equilibrium is stochastically stable. That is, under
the stated condition, if the population dynamics are slightly noisy, where
individuals, with a low frequency, play the opposite strategy than what their
update rules imply, an extreme equilibrium will be visited infinitely often by
the solution trajectory, and the frequency of this visitation does not vanish
as the noise converges to zero. These results highlight the robustness of
extreme equilibria.

We have partially characterized the minimal invariant sets by finding
necessary conditions. We have established the existence of anticoordinating
benchmark types $j_{1},j_{2}$ and coordinating benchmark types
$j^{\prime}_{1},j^{\prime}_{2}$ such that at the minimal invariant set, all
nonconformists with thresholds higher than that of $j_{1}$ and all conformists
with thresholds lower than that of $j^{\prime}_{1}$ cooperate and all
nonconformists with thresholds lower than that of $j_{2}$ and all conformists
with thresholds higher than that of $j^{\prime}_{2}$ defect. If the minimum
and maximum numbers of cooperators in the minimal invariant set are known,
then we know the benchmarks exactly, i.e., which agents will fix their
strategies in the long run and which others will keep wandering. Particularly,
the wandering conformists will infinitely often all simultaneously cooperate
and infinitely often all simultaneously defect, when the solution trajectory
enters the invariant set. The wandering nonconformists are less harmonious and
seem to be the key in finding the extremum number of cooperators in the
minimal invariant set, which in turn may lead to an explicit formulation of
the set and is left as future work.

## Acknowledgments

This work was funded in part by Alberta Environment and Parks. We would like
to thank Prof. Russell Greiner for a generous funding and Prof. John Bowman
for his support.

## References

  * [1] J. D. Allen, M. K. Othus, R. C. Shelton, Y. Li, N. Norman, L. Tom, and M. G. del Carmen, Parental decision making about the hpv vaccine, Cancer Epidemiology and Prevention Biomarkers, 19 (2010), pp. 2187–2198.
  * [2] C. Alós-Ferrer, Finite population dynamics and mixed equilibria, International Game Theory Review, 5 (2003), pp. 263–290.
  * [3] E. Bodine-Baron, S. Nowak, R. Varadavas, and N. Sood, Conforming and non-conforming peer effects in vaccination decisions, tech. report, National Bureau of Economic Research, 2013.
  * [4] M. Bravo and M. Faure, Reinforcement learning with restrictions on the action set, SIAM Journal on Control and Optimization, 53 (2015), pp. 287–312.
  * [5] L. Bursztyn, F. Ederer, B. Ferman, and N. Yuchtman, Understanding mechanisms underlying peer effects: Evidence from a field experiment on financial decisions, Econometrica, 82 (2014), pp. 1273–1301.
  * [6] A. C. Chapman, D. S. Leslie, A. Rogers, and N. R. Jennings, Convergent learning algorithms for unknown reward games, SIAM Journal on Control and Optimization, 51 (2013), pp. 3154–3180.
  * [7] G. Cimini, C. Castellano, and A. Sánchez, Dynamics to equilibrium in network games: individual behavior and global response, PloS one, 10 (2015), p. e0120343.
  * [8] T. Collins, Imitation: A catalyst for innovation and endogenous growth, Economic Modelling, 51 (2015), pp. 299–307.
  * [9] L. B. Cunningham, R. Baldick, and M. L. Baughman, An empirical study of applied game theory: Transmission constrained cournot behavior, IEEE Transactions on power systems, 17 (2002), pp. 166–172.
  * [10] O. Diekmann and S. A. van Gils, On the cyclic replicator equation and the dynamics of semelparous populations, SIAM Journal on Applied Dynamical Systems, 8 (2009), pp. 1160–1189.
  * [11] G. Ellison, Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution, The Review of Economic Studies, 67 (2000), pp. 17–45.
  * [12] S. R. Etesami, A simple framework for stability analysis of state-dependent networks of heterogeneous agents, SIAM Journal on Control and Optimization, 57 (2019), pp. 1757–1782.
  * [13] D. Foster and P. Young, Stochastic evolutionary game dynamics*, Theoretical population biology, 38 (1990), pp. 219–232.
  * [14] Y. Fu and P. Ramazi, Asynchronous decision-making dynamics under imitation update rule in heterogeneous populations, under review.
  * [15] A. Govaert, P. Ramazi, and M. Cao, Convergence of imitation dynamics for public goods games on networks, in Proc. IEEE 56th Conference on Decision and Control (CDC), IEEE, 2017, pp. 4982–4987.
  * [16] K. A. Henderson, C. T. Bauch, and M. Anand, Alternative stable states and the sustainability of forests, grasslands, and agriculture, Proceedings of the National Academy of Sciences, 113 (2016), pp. 14552–14559.
  * [17] M. Kandori, G. J. Mailath, and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica: Journal of the Econometric Society, (1993), pp. 29–56.
  * [18] G. E. Kreindler and H. P. Young, Fast convergence in evolutionary equilibrium selection, Games and Economic Behavior, 80 (2013), pp. 39–67.
  * [19] R. Laraki and P. Mertikopoulos, Inertial game dynamics and applications to constrained optimization, SIAM Journal on Control and Optimization, 53 (2015), pp. 3141–3170.
  * [20] H. Le and P. Ramazi, Heterogeneous mixed ppulations of best-responders and imitators: Equilibrium convergence and stability, IEEE Transactions on Automatic Control, (2020).
  * [21] M. Lelarge, Diffusion and cascading behavior in random networks, Games and Economic Behavior, 75 (2012), pp. 752–775.
  * [22] H. Li and X. Ding, A control lyapunov function approach to feedback stabilization of logical control networks, SIAM Journal on Control and optimization, 57 (2019), pp. 810–831.
  * [23] A. Montanari and A. Saberi, The spread of innovations in social networks, Proceedings of the National Academy of Sciences, 107 (2010), pp. 20196–20201.
  * [24] D. Oyama, W. H. Sandholm, and O. Tercieux, Sampling best response dynamics and deterministic equilibrium selection, Theoretical Economics, 10 (2015), pp. 243–281.
  * [25] P. Ramazi and M. Cao, Stability analysis for replicator dynamics of evolutionary snowdrift games, in Proc. 53rd IEEE Conference on Decision and Control (CDC), IEEE, 2014, pp. 4515–4520.
  * [26] P. Ramazi and M. Cao, Asynchronous decision-making dynamics under best-response update rule in finite heterogeneous populations, IEEE Transactions on Automatic Control, 63 (2018), pp. 742–751.
  * [27] P. Ramazi and M. Cao, Convergence of linear threshold decision-making dynamics in finite heterogeneous populations, Automatica, 119 (2020), p. 109063.
  * [28] P. Ramazi, J. Riehl, and M. Cao, Networks of conforming or nonconforming individuals tend to reach satisfactory decisions, Proceedings of the National Academy of Sciences, 113 (2016), pp. 12985–12990.
  * [29] P. Ramazi and M. H. Roohi, Characterizing oscillations in heterogeneous mixed populations of coordinators and anticoordinators, Under review.
  * [30] J. Riehl, P. Ramazi, and M. Cao, A survey on the analysis and control of evolutionary matrix games, Annual Reviews in Control, (2018).
  * [31] K. Rozen, A‘dual’-improved shortcut to the long run, (2008).
  * [32] W. H. Sandholm, Population games and evolutionary dynamics, MIT Press, 2010.
  * [33] J. M. Smith, The theory of games and the evolution of animal conflicts, Journal of theoretical biology, 47 (1974), pp. 209–221.
  * [34] B. Swenson, S. Kar, J. Xavier, and D. S. Leslie, Robustness properties in fictitious-play-type algorithms, SIAM Journal on Control and Optimization, 55 (2017), pp. 3295–3318.
  * [35] S. Tan, J. Lü, and Z. Lin, Emerging behavioral consensus of evolutionary dynamics on complex networks, SIAM Journal on Control and Optimization, 54 (2016), pp. 3258–3272.
  * [36] N. Tsakas, Imitating the most successful neighbor in social networks, Review of Network Economics, 12 (2014), pp. 403–435.
  * [37] P. van den Berg, L. Molleman, and F. J. Weissing, Focus on the success of others leads to selfish behavior, Proceedings of the National Academy of Sciences, 112 (2015), pp. 2912–2917.
  * [38] X. Wang, W. Chen, and J. Zhao, The evolution of cooperation within the multigame environment based on the particle swarm optimization algorithm, Physics Letters A, 384 (2020), p. 126165.
  * [39] H. P. Young, The evolution of conventions, Econometrica: Journal of the Econometric Society, (1993), pp. 57–84.
  * [40] H. P. Young, The dynamics of social innovation, Proceedings of the National Academy of Sciences, 108 (2011), pp. 21285–21291.
  * [41] K. Z. Zhou, Innovation, imitation, and new product performance: The case of china, Industrial Marketing Management, 35 (2006), pp. 394–402.

##  Appendix A Modified cost function and proof of Lemma 7.7

The proof of Lemma 7.7, as mentioned before, is based on [11, Theorem 3].
Indeed, the two propositions are almost the same, with the distinction that in
[11, Theorem 3] the cost function, defined in Section 7.2, is replaced with
its modified version. This modification is done by Ellison as follows.

For an arbitrary state $\bm{x}$ and a recurrent class $\Omega$, consider the
path $(\bm{z}_{1}\ldots,\bm{z}_{T})\in\Pi(\bm{x},\Omega)$, and suppose that
$\Omega_{i_{1}}$, $\Omega_{i_{2}}$, $\ldots$, $\Omega_{i_{r}}=\Omega$ is the
sequence of recurrent classes through which the path passes consecutively
(with the convention that a recurrent class can appear on the list multiple
times but not successively). We define $c^{*}$ by

(36) $\displaystyle
c^{*}(\bm{z}_{1},\ldots,\bm{z}_{T})=c(\bm{z}_{1},\ldots,\bm{z}_{T})-\sum_{j=2}^{r-1}R(\Omega_{i_{j}}),$

and set

$\displaystyle
c^{*}(\bm{x},\Omega)=\min_{(\bm{z}_{1},\ldots,\bm{z}_{T})\in\Pi(\bm{x},\Omega)}c(\bm{z}_{1},\ldots,\bm{z}_{T}).$

For us, in spite of [11], $c^{*}$ is not an essential object. So we will not
try to justify its definition, and refer the reader to [11]. However, we
provide an evolutionary intuition given in the same paper. As Ellison
explains, the given modification of $c$ “formalizes the observation that large
evolutionary changes will occur more rapidly if it is possible for the change
to be effected via a series of more gradual steps between nearly stable
states”.

Ellison proves the following result [11, Theorem 3].

######  Proposition A.1.

Let $P^{\varepsilon}$ be a regular perturbation of $P$. For a recurrent class
$\Omega$ of $P$, and a state $\bm{x}\not\in\Omega$, if we have
$R(\Omega)>c^{*}(\bm{x},\Omega)$, then $\bm{\mu}^{*}(\bm{x})=0$. If
$R(\Omega)=c^{*}(\bm{x},\Omega)$, then $\bm{\mu}^{*}(\bm{x})>0$ implies
$\bm{\mu}^{*}(\Omega)>0$.

###  A.1 Proof of Lemma 7.7

######  Proof A.2.

According to (37), for a state $\bm{x}$ and a recurrent class $\Omega$, we
have

(37) $\displaystyle c(\bm{x},\Omega)\geq c^{*}(\bm{x},\Omega).$

Hence, assuming $\bm{x}\not\in\Omega$, if $R(\Omega)>c(\bm{x},\Omega)$, it is
concluded that $R(\Omega)>c^{*}(\bm{x},\Omega)$, and Proposition A.1 yields
$\mu^{*}(\bm{x})=0$. On the other hand, If $R(\Omega)=c(\bm{x},\Omega)$ and
$\mu^{*}(\bm{x})>0$, then, by the first part of Proposition A.1, in (37) the
equality must hold. So $R(\Omega)=c^{*}(\bm{x},\Omega)$, and according to the
second part of Proposition A.1, it holds that $\mu^{*}(\Omega)>0$.