remarkRemark exampleExample hypothesisHypothesis claimClaim
assumptionAssumption Coordinating, Anticoordinating, and ImitatingH. Le, M.
Rajaee, and P. Ramazi ex_supplement

# Heterogeneous Mixed Populations of Coordinating, Anticoordinating, and
Imitating Individuals††thanks:  Submitted to the editors DATE. This project
was partly funded by Alberta Environment and Parks. We are also grateful for
the generous funding provided by Prof. Russell Greiner.

Hien Le Faculty of Science, University of Alberta, Canada ().
<EMAIL_ADDRESS>Mohaddeseh Rajaee Department of Electrical and Computer
Engineering, Isfahan University of Technology, Iran().
<EMAIL_ADDRESS>Pouria Ramazi Department of Mathematics and
Statistics, Brock University, Canada<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Decision-making individuals are typically either an _imitator_ , who mimics
the action of the most successful individual(s), a _conformist_ (or
_coordinating individual_), who chooses an action if enough others have done
so, or a _nonconformist_ (or _anticoordinating individual_), who chooses an
action if few others have done so. Researchers have studied the asymptotic
behavior of populations comprising one or two of these types of decision-
makers, but not altogether, which we do for the first time. We consider a
population of heterogeneous individuals, each either _cooperates_ or _defects_
, and earns payoffs according to their possibly unique payoff matrix and the
total number of cooperators in the population. Over a discrete sequence of
time, the individuals revise their choices asynchronously based on the _best-
response_ or _imitation_ update rule. Those who update based on the best-
response are a conformist (resp. nonconformist) if their payoff matrix is that
of a coordination (resp. anticoordination) game. We take the distribution of
cooperators over the three types of individuals with the same payoff matrix as
the state of the system. First, we provide our simulation results, showing
that a population may admit zero, one or more equilibria at the same time, and
several non-singleton minimal positively invariant sets. Second, we find the
necessary and sufficient condition for equilibrium existence. Third, we
perform stability analysis and find that only those equilibria where the
imitators either all cooperate or all defect are likely to be stable. Fourth,
we proceed to the challenging problem of characterizing the minimal positively
invariant sets and find conditions for the existence of such sets. Finally, we
study the stochastic stability of the states under the perturbed dynamics,
where the agents are allowed to make mistakes in their decisions with a
certain small probability.

###### keywords:

Heterogeneous population, evolutionary game theory, population dynamics, best-
response, imitation, anticoordinating, coordinating, convergence analysis

91A06, 91A22, 91A26, 91A50, 91B50, 91B69, 74G10, 93C55, 93C10, 93D05

##  1 Introduction

Decision-making individuals typically take action based on either the success
or frequency of their fellows’ choices [37]. The first group simply imitates
the choice of successful others, referred to as _imitators_. The second,
decide based on how many others have chosen a particular action: some choose
an action if enough others have already taken that action, referred to as
_conformists_ or _coordinating individuals_ , whereas some choose an action if
few others have done so, referred to as _nonconformists_ or _anticoordinating
individuals_. Whether others choosing a particular action are “enough” or
“few” for the individual to choose that action is determined by her
_threshold_ or the so called _temper_. All three types are common in both
human societies and nature [9, 33, 41]. In technology markets, conformists
invest in common products to avoid risk, nonconformists develop rare products
to benefit from a monopoly [8], and imitators follow highest-earning firms
[5]. When deciding on whether to vaccine their infants, some mothers
(conformists) promote vaccination as they do not want to diverge from the
cultural norm; others (nonconformists) inhibit vaccination as they feel that
their child is not at risk since other children are vaccinated; and some
(imitators) may be in touch with an influential homeopath/naturopath [1]. The
fundamental questions regarding populations consisting of these types of
decision-makers are concerned with their asymptotic collective behavior. More
specifically, is it possible for the population to eventually settle and reach
an equilibrium where all individuals are satisfied with their decisions? If
yes, how stable is the equilibrium to changes in the decisions? More
importantly, if the population never settles, and undergoes perpetual
fluctuations, can we characterize the fluctuations, e.g., find their lengths?

_Evolutionary game theory_ models a decision-making process by a population of
interactive agents who choose between typically two strategies _cooperation_
and _defection_ , accordingly earn payoffs based on their payoff matrices, and
revise their strategies based on some update rule [32]. Imitators update based
on the _imitation update rule_ and choose the strategy of the individual(s)
with the highest payoff, and the other two types update based on the _best-
response update rule_ and choose the strategy that maximizes their payoffs.
Based on their payoff matrices, best-responders are either a conformist or
nonconformist, and are modeled by _threshold models_ , where a conformist
chooses cooperation if the total number of cooperators in the population
exceeds her threshold and _vice versa_ [30]. Populations of homogeneous
individuals [25], who have the same payoff matrix or thresholds, are analyzed
under both best-response [21, 40, 24, 2, 18] and imitation update rules [7,
15]. Heterogeneous population of conformists, and heterogeneous population of
nonconformists are both known to equilibrate and the same holds for imitators
with the _coordination_ payoff matrix [28, 30, 26]. However, imitators earning
according to the _anticoordination_ payoff matrix are reported and proven to
oscillate in their strategies under a variety of conditions [14, 16].
Recently, mixed populations of nonconformists and imitators who earn based on
the anticoordination payoff matrix are shown to equilibrate if and only if
they admit an equilibrium [20]. We have performed stability analysis for
population dynamics in [26] and later [20]. No study has reported the
asymptotic behavior of mixed-populations of conformists and nonconformists.
More generally, it remains open whether mixed-populations of all three types
of decision-makers, and under both the coordination and anticoordination
payoff matrices, admit a stable or unstable equilibrium. Moreover, none of the
above studies have addressed the challenging problem of characterizing the
oscillatory behavior of the population dynamics.

Another branch of research in evolutionary game theory considers agents that
are prone to tremble randomly in decision making. This perturbation changes
the chance of different outcomes to be observed in the long run. Those states
that are robust to the perturbation in the dynamics when the trembling rate
vanishes are called _stochastically stable_ states. T he notion of stochastic
stability, first studied in [17, 13, 39], provides also a refinement tool for
dynamics with multiple minimal invariant sets. The stochastic stability
analysis for a certain type of homogeneous population of conformists is
performed in [17], where authors provide conditions under which the only
stochastically stable state is the risk dominant equilibrium. Ellison
generalizes this result to homogeneous populations with arbitrary number of
strategies for agents to play [11]. The stochastic stability of mixed
populations of imitators and best-responders remains concealed.

We consider a mixed-population of conformists, nonconformists, and imitators
who decide between cooperation and defection and revise their choices over a
discrete sequence of time. We follow the evolutionary game theory framework
where individuals earn according to their payoff matrices, which can be unique
to each individual, resulting in a heterogeneous population, and can be both
of the coordination and anticoordination game. First, we provide numerical
examples and show that the resulting population dynamics can admit zero or
more equilibria as well as a set where the dynamics perpetually fluctuate
between several states, which turns out to be a non-singleton minimal
positively invariant set. Then we find the necessary and sufficient condition
for equilibrium existence and identify all possible equilibria that the
dynamics may possess. We interpret the results by introducing the notion of
_cooperation-preserving_ groups who tend to cooperate if they are the only
cooperators in the population. Next, we adjust the notion of equilibrium
stability for general discrete population dynamics and find the necessary and
sufficient condition for an equilibrium to be stable. We find that only those
extreme equilibria where all imitators defect or all cooperate are likely to
be stable. Next, we proceed to characterize the minimal positively invariant
sets. We approximate the sets by finding necessary conditions for a general
set to be positively invariant. We also introduce a set that can be invariant,
which helps in limiting our search when looking for a minimal positively
invariant set. Finally, we study the situation when the agents may tremble and
make errors in their decisions with a certain small probability, resulting in
perturbed dynamics. We investigate the stochastically stable states and find
that, under specific conditions, for mixed binary-type populations, if there
exist stochastically stable equilibria, an extreme equilibrium has to be one.

Our results reveal the possible outcomes of one of the most general population
dynamics considered in the literature. According to the stability analysis, we
may not expect a population to both settle and preserve the diversity of
strategies among the imitators, unless small deviations in the imitators’
strategies at that settling state result in another settling state. The
stochastic stability analysis on the other hand, imply that if an equilibrium
consisting of both imitating cooperators and defectors is persistently visited
under agents’ trembles, so does an extreme equilibrium. The results,
therefore, highlights the“robustness” of extreme equilibria under
perturbations. Moreover, the analysis on the invariant sets allows us to
estimate their cardinality and other properties such as the minimum and the
maximum number of cooperators in the set. Our results open the door to future
convergence analysis of the population dynamics.

##  2 Model

We consider a well-mixed population of $n$ agents playing 2-player games over
a discrete time sequence. At each time $t=0,1,\ldots$, every agent
$i\in\\{1,\ldots,n\\}$ plays either _cooperation_ ($C$) or _defection_ ($D$)
and accordingly earns a payoff against each of her opponents based on the
payoff matrix

(1) $\pi_{i}=\blockarray{ccc}&CD\\\ \block{c(cc)}CR_{i}S_{i}\\\
DT_{i}P_{i},\\\ ,\qquad(R_{i}+P_{i})\neq(T_{i}+S_{i}),$

where $R_{i},S_{i},T_{i}$ ad $P_{i}$ are the payoffs of $C$-against-$C$,
$C$-against-$D$, $D$-against-$C$ and $D$-against-$D$. Denote the strategy of
agent $i$ by $s_{i}\in\\{C,D\\}$ and the total number of cooperators in the
population by $n^{C}$. Then the total payoff (utility) of agent $i$ against
the population is

$\begin{cases}u_{i}^{C}=n^{C}(R_{i}-S_{i})+nS_{i}&\text{if }s_{i}=C\\\
u_{i}^{D}=n^{C}(T_{i}-P_{i})+nP_{i}&\text{if }s_{i}=D\end{cases},$

where $u^{C}_{i}$ and $u^{D}_{i}$ are the utility of agent $i$ upon playing
cooperation and defection. At each time $t$, an agent becomes active to revise
her strategy at time $t+1$ based on either the _best-response_ or _imitation
update rule_. Each agent follows only one of these two over time, and is
correspondingly called a _best-responder_ or an _imitator_. If agent $i$ is a
best-responder, she chooses the strategy that maximizes her utility; should
cooperation and defection provide her the same utility, she would stick to her
current strategy. Namely, upon activation at time $t$, agent $i$ updates her
strategy as

$s_{i}^{B}\left(t+1\right)=\begin{cases}C&\text{if
}u_{i}^{C}\left(t\right)>u_{i}^{D}\left(t\right)\\\ D&\text{if
}u_{i}^{D}\left(t\right)>u_{i}^{C}\left(t\right)\\\
s_{i}^{B}\left(t\right)&\text{if
}u_{i}^{D}\left(t\right)=u_{i}^{C}\left(t\right)\end{cases},$

where the superscript $B$ in $s_{i}^{B}$ indicates that agent $i$ is a best-
responder. By defining the _temper_ of agent $i$ as $\tau_{i}\triangleq
n(P_{i}-S_{i})/(R_{i}+P_{i}-S_{i}-T_{i})$, the above equation can be
simplified as follows when $R_{i}+P_{i}-S_{i}-T_{i}>0$:

(2) $s_{i}^{B}\left(t+1\right)=\begin{cases}C&\text{if }n^{C}(t)>\tau_{i}\\\
D&\text{if }n^{C}(t)<\tau_{i}\\\ s_{i}^{B}\left(t\right)&\text{if
}n^{C}(t)=\tau_{i}\end{cases}.$

We call an agent following this update rule a conformist or coordinating agent
as she coordinates her strategy with ‘those considerable in number’; that is,
she cooperates (resp. defects) if the number of cooperators (resp. defectors)
is greater (resp. less) than her temper. Similarly, if
$R_{i}+P_{i}-S_{i}-T_{i}<0$, the update rule is simplified to

(3) $s_{i}^{B}\left(t+1\right)=\begin{cases}C&\text{if }n^{C}(t)<\tau_{i}\\\
D&\text{if }n^{C}(t)>\tau_{i}\\\ s_{i}^{B}\left(t\right)&\text{if
}n^{C}(t)=\tau_{i}\end{cases}.$

We refer to an agent following this rule a nonconformist or anticoordinating
agent as she chooses the opposite of the strategy of ‘those considerable in
number’. So a best-responder is either a conformist or an nonconformist111 If
the equality in (1) takes place, then either $u_{i}^{D}(t)=u_{i}^{C}(t)$ for
all $t$, or one of the strategies becomes dominant and is always favored. In
either case, agent $i$ fixes her strategy the first time she updates and can
be modelled by both a conformist and an nonconformist with
$\tau\in\\{-0.5,n+0.5\\}$.. An imitator, on the other hand, ignores her own
utility and copies the strategy of the agent earning the highest utility; if
there are two highest-earners with two different strategies, she will not
switch strategies. So upon activation at time $t$, agent $i$ who is an
imitator updates her strategy as

(4) $s_{i}^{I}(t+1)=\begin{cases}C&\text{if
}C_{\mathrm{M}}(t)>D_{\mathrm{M}}(t)\\\ D&\text{if
}C_{\mathrm{M}}(t)<D_{\mathrm{M}}(t)\\\ s_{i}^{I}(t)&\text{if
}C_{\mathrm{M}}(t)=D_{\mathrm{M}}(t)\end{cases},$

where the superscript $I$ in $s_{i}^{I}$ indicates that agent $i$ is an
imitator, and $C_{\mathrm{M}}(t)$ and $D_{\mathrm{M}}(t)$ are the utility of
the highest-earning cooperator and defector at time $t$:

$\displaystyle
C_{\mathrm{M}}(t)=\sup_{i\in\mathcal{C}(t)}u_{i}^{C}(t)\quad\mathcal{C}(t)=\\{j\in\\{1,\ldots,n\\}\,|\,s_{j}(t)=C\\},$
$\displaystyle
D_{\mathrm{M}}(t)=\sup_{i\in\mathcal{D}(t)}u_{i}^{D}(t)\quad\\!\\!\mathcal{D}(t)=\\{j\in\\{1,\ldots,n\\}\,|\,s_{j}(t)=D\\},$

where given a set $\mathcal{S}$, $\sup\mathcal{S}$ is the _supremum of
$\mathcal{S}$_. By defining, $\sup\mathcal{S}\triangleq-\infty$ when
$\mathcal{S}=\emptyset$, we correctly include the case
$\mathcal{C}(t)=\emptyset$ (resp. $\mathcal{D}(t)=\emptyset$) when all agents
including the highest earner are defecting (resp. cooperating) since the
active imitator then tends to defect (resp. cooperate):
$D_{\mathrm{M}}(t)>C_{\mathrm{M}}(t)=-\infty$ (resp.
$C_{\mathrm{M}}(t)>D_{\mathrm{M}}(t)=-\infty$). Each of the above three update
rules are commonly used in the literature, either in their current or similar
forms [36, 22, 34, 4, 6, 38], under stochastic setups [35, 23, 32], under
different games [12, 15], or when the population dynamics are approximated by
continuous mean field dynamics [19, 10].

The agents can be thought of as investors in the stock market who either _buy_
or _sell_. Some simply follow the strategy of the most successful investors.
Some choose to buy when they observe enough others doing so, because they
believe that the market price will then increase. Others choose to sell when
enough others are buying since they can then sell at high prices. These three
types of investors are common in the stock market, and their coexistence is
evident. The three types of individuals also coexist when people decide
whether or not to get vaccinated [3]. When the vaccination coverage is high,
some believe that they are relatively safe and decide not to have the
vaccination. Meanwhile, under the same situation, some choose to get
vaccinated because they worry that the danger of the disease is the reason
people get vaccinated. Others do not put much thought into the problem and
just follow the most healthy individuals.

While all imitators behave in the exact same way, best-responders with
different payoff matrices may choose different strategies upon activation. We,
thus, group the best-responders with the same payoff matrix into the same
_type_ and assume that there are all together $b$ types of nonconformists,
which we refer to as the _anticoordinating types_ , and $b^{\prime}$ types of
conformists, which we refer to as the _coordinating types_. Now note that
best-responders of the same type share the same temper, and unlike
conformists, nonconformists’ tendency to cooperate increases with their
tempers. Therefore, we label the anticoordinating types in the descending
order of their tempers by $1,2,\ldots,b$ and the coordinating types in the
ascending order of their tempers by $1,2,\ldots,b^{\prime}$. By denoting the
temper of a type-$i$ nonconformist as $\tau_{i}^{a}$ and the temper of a
type-$i$ conformist as $\tau_{i}^{c}$ and assuming distinct tempers, we obtain

(5)
$\tau_{1}^{a}>\tau_{2}^{a}>\ldots>\tau_{b}^{a}\quad\text{and}\quad\tau_{1}^{c}<\tau_{2}^{c}<\ldots<\tau_{b^{\prime}}^{c}.$

We consider only the case where the tempers are not integers to avoid
unnecessary complications (see [27] for a framework for integer tempers). We
take the distribution of cooperators over the imitators and the two types of
the best-responders as the _population state_ :

$\bm{x}=(x^{I},x_{1}^{a},\ldots,x_{b}^{a},x_{b^{\prime}}^{c},\ldots,x_{1}^{c}),$

where $x^{I}$ is the number of cooperating imitators, and $x_{i}^{a}$ and
$x_{i}^{c}$ denote the number of cooperating nonconformists and cooperating
conformists of type-$i$. Hence, the state space is

$\displaystyle\mathcal{X}=\Big{\\{}(x^{I},x_{1}^{a},\ldots,x_{b}^{a},x_{b^{\prime}}^{c},\ldots,x_{1}^{c})\,|\,$
$\displaystyle x^{I}\in\\{0,\ldots,m\\},$ $\displaystyle
x_{i}^{a}\in\left\\{0,\ldots,n_{i}^{a}\right\\}\,\forall
i\in\\{1,\ldots,b\\},$ $\displaystyle
x_{i}^{c}\in\left\\{0,\ldots,n_{i}^{c}\right\\}\,\forall
i\in\\{1,\ldots,b^{\prime}\\}\Big{\\}},$

where $m>0$ is the number of imitators, and $n_{i}^{a}$ and $n_{i}^{c}$ are
the number of type-$i$ nonconformists and conformists. We assume that
associated with every payoff matrix, there is at least one best-responder who
earns accordingly; namely, the payoff matrices of the imitators are included
in those of the best-responders. Therefore, each imitator falls into one of
the coordinating and anticoordinating types, although the imitators are
neither conformists nor nonconformists. Since agents of the same type earn the
same payoff if they play the same strategy, we denote the utilities of
type-$i$ anticoordinating cooperators and defectors by $C_{i}^{a}$ and
$D_{i}^{a}$, and the utilities of type-$i$ coordinating cooperators and
defectors by $C_{i}^{c}$ and $D_{i}^{c}$.

The agents become active according to an _activation sequence_ , which is an
infinite sequence of agents $(i^{t})_{t=0}^{\infty}$, where $i^{t}$ is the
active agent at time $t$. The activation sequence is _asynchronous_ ; namely,
at every time $t\geq 0$, exactly one agent becomes active to update her
strategy at time $t+1$. We do not make any assumption on the activation
sequence, allowing it to be randomly generated or depend on past played
actions. Update rules (2), (3) and (4) together with the activation sequence
of the agents govern the dynamics of $\bm{x}(t)$, which we refer to as the
_population dynamics_. Indeed, the dynamics can be seen as a _multivalued
dynamical system_ as the sate $x(t)$ may end up at different states at the
next time step, based on the activation sequence. We are interested in the
limit sets of the dynamics. An _equilibrium_ of the population dynamics is a
state where every agent is satisfied with her strategy. More specifically, we
define an _equilibrium_ to be a population state $\bm{x}^{*}\in\mathcal{X}$
such that if the solution trajectory starts from that state, it remains there
afterwards under any activation sequence, i.e.,
$\bm{x}(0)=\bm{x}^{*}\Rightarrow\bm{x}(t)=\bm{x}^{*}$ for all $t\geq 0$ and
any $(i^{t})_{t=0}^{\infty}$. According to [20], mixed populations of best-
responders and imitators who play anticoordination games, will reach an
equilibrium if and only if the dynamics admit an equilibrium. However, when
both coordination and anticoordination games are played in the population,
which is the case with our setup, the population may never settle down and
exhibit perpetual fluctuations [28], even if the dynamics admit an
equilibrium. We simulate some of the asymptotic outcomes of the dynamics in
the following section. The examples also provide useful hints in developing
the results in the later sections.

##  3 Numerical examples

######  Example 3.1.

Consider a population of $75$ agents with two anticoordinating and three
coordinating types. The distribution of the population over the imitators and
different types of best-responders is
$({\color[rgb]{1,0,0}m},{\color[rgb]{0,0.88,0}n_{1}^{a}},{\color[rgb]{0,0.88,0}n_{2}^{a}},{\color[rgb]{0,0,1}n_{3}^{c}},{\color[rgb]{0,0,1}n_{2}^{c}},{\color[rgb]{0,0,1}n_{1}^{c}})=({\color[rgb]{1,0,0}20},{\color[rgb]{0,0.88,0}9},{\color[rgb]{0,0.88,0}20},{\color[rgb]{0,0,1}10},{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}15})$,
The payoff matrices are set so that they result in the following utility
functions:

$\displaystyle C_{1}^{a}(n^{C})=-\frac{16}{13}n^{C}+\frac{623}{13},$
$\displaystyle D_{1}^{a}(n^{C})=\frac{36}{13}n^{C}-\frac{768}{13};$
$\displaystyle C_{2}^{a}(n^{C})=-\frac{80}{79}n^{C}+\frac{4375}{79},$
$\displaystyle D_{2}^{a}(n^{C})=45;$ $\displaystyle
C_{3}^{c}(n^{C})=\frac{72}{43}n^{C}-\frac{1945}{43},$ $\displaystyle
D_{3}^{c}(n^{C})=-\frac{76}{43}n^{C}+\frac{4086}{43};$ $\displaystyle
C_{2}^{c}(n^{C})=\frac{4}{3}n^{C}-23,$ $\displaystyle
D_{2}^{c}(n^{C})=-\frac{2}{3}n^{C}+40;$ $\displaystyle
C_{1}^{c}(n^{C})=\frac{48}{13}n^{C}-\frac{855}{13},$ $\displaystyle
D_{1}^{c}(n^{C})=\frac{24}{13}n^{C}-\frac{291}{13}.$

Therefore, the tempers are

$({\color[rgb]{0,0.88,0}\tau_{1}^{a}},{\color[rgb]{0,0.88,0}\tau_{2}^{a}},{\color[rgb]{0,0,1}\tau_{3}^{c}},{\color[rgb]{0,0,1}\tau_{2}^{c}},{\color[rgb]{0,0,1}\tau_{1}^{c}})=({\color[rgb]{0,0.88,0}26.8},{\color[rgb]{0,0.88,0}10.3},{\color[rgb]{0,0,1}40.8},{\color[rgb]{0,0,1}31.5},{\color[rgb]{0,0,1}23.5}).$

The population dynamics admit multiple equilibria:
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}9},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}15})$,
$({\color[rgb]{1,0,0}20},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}15})$,
$({\color[rgb]{1,0,0}20},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0,1}10},{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}15})$,
and
$({\color[rgb]{1,0,0}15},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}15})$.
We observe that at any equilibrium, there are a benchmark type $j$ of
nonconformists and a benchmark type $j^{\prime}$ of conformists such that all
nonconformists of types $1,\ldots,j$ (resp. $j+1,\ldots,b$) and all
conformists of types $1,\ldots,j^{\prime}$ (resp.
$j^{\prime}+1,\ldots,b^{\prime}$) cooperate (resp. defect). At
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}9},{\color[rgb]{0,0.88,0}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}0},{\color[rgb]{0,0,1}15})$,
for example, the nonconformists’ benchmark type is ${\color[rgb]{0,0.88,0}1}$
and the conformists’ benchmark type is ${\color[rgb]{0,0,1}1}$. The total
number of cooperators is $24$, falling short of the temper of type-$1$
nonconformists and exceeding the temper of type-$1$ conformists. Hence, these
agents continue cooperating upon activation. nonconformists of type $2$ (resp.
conformists of types $2$ and $3$) also do not switch strategies, because they
are defecting and the number of cooperators exceeds (resp. falls short of)
their temper. Moreover, none of the imitators switch strategies since they are
defecting and coordinating defectors of type $3$ are the highest earners.

######  Example 3.2.

Consider a population of $75$ agents belonging to two anticoordinating and
three coordinating types. The population is distributed among the imitators
and best-responders as
$({\color[rgb]{1,0,0}m},{\color[rgb]{0,0.88,0}n_{1}^{a}},{\color[rgb]{0,0.88,0}n_{2}^{a}},{\color[rgb]{0,0,1}n_{3}^{c}},{\color[rgb]{0,0,1}n_{2}^{c}},{\color[rgb]{0,0,1}n_{1}^{c}})=({\color[rgb]{1,0,0}14},{\color[rgb]{0,0.88,0}9},{\color[rgb]{0,0.88,0}20},{\color[rgb]{0,0,1}10},{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}15})$.
Among the $14$ imitators, $4$ of them have the same payoff matrix as that of
type-$1$ nonconformists. The payoffs are set so that they result in the
following utility functions:

$\displaystyle C_{1}^{a}(n^{C})=-\frac{40}{13}n^{C}+\frac{1655}{13},$
$\displaystyle D_{1}^{a}(n^{C})=\frac{36}{13}n^{C}-\frac{378}{13};$
$\displaystyle C_{2}^{a}(n^{C})=\frac{16}{79}n^{C}+\frac{1495}{79},$
$\displaystyle D_{2}^{a}(n^{C})=\frac{64}{79}n^{C}+\frac{1003}{79};$
$\displaystyle C_{3}^{c}(n^{C})=\frac{24}{43}n^{C}-\frac{505}{43},$
$\displaystyle D_{3}^{c}(n^{C})=-\frac{40}{43}n^{C}+\frac{2103}{43};$
$\displaystyle C_{2}^{c}(n^{C})=\frac{4}{3}n^{C}-23,$ $\displaystyle
D_{2}^{c}(n^{C})=-\frac{2}{3}n^{C}+40;$ $\displaystyle
C_{1}^{c}(n^{C})=\frac{8}{13}n^{C}+\frac{345}{13},$ $\displaystyle
D_{1}^{c}(n^{C})=-\frac{16}{13}n^{C}+\frac{909}{13}.$

The tempers are, hence,

$({\color[rgb]{0,0.88,0}\tau_{1}^{a}},{\color[rgb]{0,0.88,0}\tau_{2}^{a}},{\color[rgb]{0,0,1}\tau_{3}^{c}},{\color[rgb]{0,0,1}\tau_{2}^{c}},{\color[rgb]{0,0,1}\tau_{1}^{c}})=({\color[rgb]{0,0.88,0}26.8},{\color[rgb]{0,0.88,0}10.3},{\color[rgb]{0,0,1}40.8},{\color[rgb]{0,0,1}31.5},{\color[rgb]{0,0,1}23.5}).$

The population dynamics exhibit different asymptotic outcomes for the same
initial condition where all agents defect (Fig. 1). Depending on the
activation sequence, the population may reach an equilibrium (Fig. 1(a)) or
undergo perpetual fluctuations (Fig. 1(b)). In the second case, all type-$2$
nonconformists and all conformists fix their strategies after some finite time
$T$. This is guaranteed since the number of cooperators fluctuates between
$26$ and $27$ after time $T$. When the number of cooperators is $26$, the
agents who have not fixed their strategies, i.e., the imitators and type-$1$
nonconformists, do not switch from cooperation to defection, because $26$
falls short of the nonconformists’ tempers and a cooperator of
anticoordinating type $1$ is earning the highest payoff. Such a cooperator
exists, because if all type-$1$ anticoordinating agents, i.e., the 9
nonconformists and 4 of the imitators, were defecting, then the number of
cooperators would be at most $25$. Similarly, one can verify that the number
of cooperators never exceeds $27$.

(a) Reaching a mixed equilibrium. The population reaches the equilibrium
$(14,9,0,0,0,0)$. The total number of cooperators at this state is $23$, which
exceeds the temper of type-$2$ nonconformists and falls short of the tempers
of the conformists. Hence no defecting best-responder switch strategies.
Moreover, $23$ is less than the temper of type-$1$ nonconformists, so they
keep cooperating. The imitators do not change their strategies either as the
highest earners at this state are type-$1$ nonconformists, who are
cooperating.

(b) Not reaching an equilibrium. Even though all nonconformists of type $2$
and conformists of types $2$ and $3$ defect and all type-$1$ conformists
cooperate in the long run, the population undergoes perpetual fluctuations as
the imitators and type-$1$ nonconformists keep switching strategies.

Figure 1: The population dynamics under two different randomly generated
activation sequences.

######  Example 3.3.

Consider a population of $68$ agents belonging to two anticoordinating and
three coordinating types. The population distribution over the imitators,
nonconformists, and conformists is
$({\color[rgb]{1,0,0}m},{\color[rgb]{0,0.88,0}n_{1}^{a}},{\color[rgb]{0,0.88,0}n_{2}^{a}},{\color[rgb]{0,0,1}n_{3}^{c}},{\color[rgb]{0,0,1}n_{2}^{c}},{\color[rgb]{0,0,1}n_{1}^{c}})=({\color[rgb]{1,0,0}14},{\color[rgb]{0,0.88,0}9},{\color[rgb]{0,0.88,0}20},{\color[rgb]{0,0,1}10},{\color[rgb]{0,0,1}5},{\color[rgb]{0,0,1}10})$.
Among the $14$ imitators, $4$ of them are of type-$1$ anticoordinating. The
payoffs are set so that they result in the following utility functions:

$\displaystyle C_{1}^{a}(n^{C})=-\frac{20}{7}n^{C}+\frac{845}{7},$
$\displaystyle D_{1}^{a}(n^{C})=\frac{18}{7}n^{C}-\frac{162}{7};$
$\displaystyle C_{2}^{a}(n^{C})=\frac{8}{39}n^{C}+\frac{245}{13},$
$\displaystyle D_{2}^{a}(n^{C})=\frac{16}{13}n^{C}+\frac{105}{13};$
$\displaystyle C_{3}^{c}(n^{C})=\frac{4}{7}n^{C}-\frac{85}{7},$ $\displaystyle
D_{3}^{c}(n^{C})=-\frac{20}{21}n^{C}+\frac{347}{7};$ $\displaystyle
C_{2}^{c}(n^{C})=\frac{2}{3}n^{C},$ $\displaystyle
D_{2}^{c}(n^{C})=-\frac{4}{3}n^{C}+57;$ $\displaystyle
C_{1}^{c}(n^{C})=\frac{8}{19}n^{C}+\frac{615}{19},$ $\displaystyle
D_{1}^{c}(n^{C})=-\frac{16}{19}n^{C}+\frac{1107}{19}.$

The tempers are, hence,

$({\color[rgb]{0,0.88,0}\tau_{1}^{a}},{\color[rgb]{0,0.88,0}\tau_{2}^{a}},{\color[rgb]{0,0,1}\tau_{3}^{c}},{\color[rgb]{0,0,1}\tau_{2}^{c}},{\color[rgb]{0,0,1}\tau_{1}^{c}})=({\color[rgb]{0,0.88,0}26.5},{\color[rgb]{0,0.88,0}10.5},{\color[rgb]{0,0,1}40.5},{\color[rgb]{0,0,1}28.5},{\color[rgb]{0,0,1}20.5}).$

This population does not admit any equilibrium, so it undergoes perpetual
fluctuations (Fig. 2(a)) and confines the number of cooperators to the
interval $[25,32]$ (Fig. 2(b)). It is not difficult to see that the number of
cooperators does not fall short of $21$ (nor exceeds $35$ in the long run). To
see this, consider the time when the total number of cooperators is $26$. Then
based on the utility functions, a cooperator of anticoordinating type $1$ is
earning the highest payoff. Such a cooperator is guaranteed to exist since if
all of the agents of anticoordinating type $1$ are defecting, the number of
cooperators is at most $25$. This cooperator continues playing cooperation and
earning the highest payoff when the number of cooperators decreases. So the
cooperating imitators do not switch to defection. Type-$1$ nonconformists do
not switch to defection either, because the number of cooperators is less than
their tempers. So the cooperating conformists of type $2$ are the only ones
who can switch to defection. However, there are only $5$ conformists of type
$2$. On the other hand, the above argument holds when the number of
cooperators is $24,23,22$ or $21$. Hence, the number of cooperators cannot
decrease to $20$, after it reaches $26$. Similarly, one can verify that the
number of cooperators cannot increase from $30$ to $35$.

(a) Not reaching an equilibrium. The dynamics do not possess an equilibrium.
The solution trajectories start from the state where all agents defect. All
nonconformists of type $2$ and conformists of types $2$ and $3$ defect and all
type-$1$ conformists cooperate in the long run, yet the population never
reaches an equilibrium as the imitators and type-$1$ nonconformists keep
switching strategies.

(b) The total number of cooperators. The number fluctuates between $26$ and
$30$.

Figure 2: The population dynamics and the total number of cooperators under a
randomly generated activation sequence.

##  4 Equilibria

No agent would switch strategies at equilibrium. Hence, from update rule (2),
if an nonconformist cooperates (resp. defects) at equilibrium, so will all
others with higher (resp. lower) tempers, and according to (3), if a
conformist cooperates (resp. defects), so will all others with lower (resp.
higher) tempers. Hence, we expect an equilibrium to be of the following form:

$\bm{x}_{r,j_{1},j^{\prime}_{1}}\triangleq(r,n_{1}^{a},\ldots,n_{j_{1}}^{a},0,\ldots,0,0,\ldots,0,n_{j^{\prime}_{1}}^{c},\ldots,n_{1}^{c}),$

where $r\in\\{0,\ldots,m\\}$, $j_{1}\in\\{0,\ldots,b\\}$ and
$j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$. Note that when $j_{1}=0$ (resp.
$b$), all nonconformists defect (resp. cooperate) and when $j^{\prime}_{1}=0$
(resp. $b^{\prime}$), all conformists defect (resp. cooperate). To simplify
the analysis of these extreme cases, we define
$\tau_{0}^{a}=\tau_{b^{\prime}+1}^{c}$ as a number that is greater than $n$
and all other tempers and $\tau_{b+1}^{a}=\tau_{0}^{c}$ as a negative number
that is smaller than all other tempers. Then $\tau^{a}_{j}$ and
$\tau^{c}_{j^{\prime}}$ are well-defined for all $j\in\\{0,\ldots,b+1\\}$ and
all $j^{\prime}\in\\{0,\ldots,b^{\prime}+1\\}$.

The goal of this section is to identify all equilibrium states that the
population admits. First, we prove in Lemma 4.1, that all equilibria are of
the form $\bm{x}_{r,j_{1},j^{\prime}_{1}}$. Next, we find the necessary and
sufficient conditions for states of the form $\bm{x}_{r,j_{1},j^{\prime}_{1}}$
to be an equilibrium in Lemma 4.3, Lemma 4.5, and Lemma 4.6. Finally, we
summarize the results in Theorem 4.8 and interpret them.

###  4.1 Forms of equilibria

######  Lemma 4.1.

If $\bm{x}^{*}$ is an equilibrium with $r$ cooperating imitators, then there
exist $j_{1}\in\\{0,\ldots,b\\}$ and
$j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$ such that
$\bm{x}^{*}=\bm{x}_{r,j_{1},j^{\prime}_{1}}$.

######  Proof 4.2.

Because $\tau_{0}^{a}=\tau_{b^{\prime}+1}^{c}>n$ and
$\tau_{b+1}^{a}=\tau_{0}^{c}<0$, there exists $j_{1}\in[0,b]$ and
$j^{\prime}_{1}\in[0,b^{\prime}]$ such that
$n^{C}(\bm{x}^{*})\in(\tau_{j_{1}+1}^{a},\tau_{j_{1}}^{a})$ and
$n^{C}(\bm{x}^{*})\in(\tau_{j^{\prime}_{1}}^{c},\tau_{j^{\prime}_{1}+1}^{c})$.
We prove by contradiction that $x_{i}^{a}=n_{i}^{a}$ for all
$i\in\left\\{1,\ldots,j_{1}\right\\}$. Suppose on the contrary that
$x_{i}^{a}<n_{i}^{a}$ for some $i\in\left\\{1,\ldots,j_{1}\right\\}$. Let
$\bm{x}(0)=\bm{x}^{*}$. Under an activation sequence where the first active
agent is a defecting nonconformist of type-$i$, she will switch to cooperation
in view of (2) since

$n^{C}(0)=n^{C}(\bm{x}^{*})<\tau_{j_{1}}^{a}\overset{\eqref{TemperOrder}}{\leq}\tau_{i}^{a}.$

This contradicts $\bm{x}^{*}$ being an equilibrium. Hence,
$x_{i}^{a}=n_{i}^{a}$ for all $i\in\left\\{1,\ldots,j_{1}\right\\}$. The
remaining of the proof can be done similarly.

###  4.2 Necessary and sufficient condition

For $\bm{x}_{r,j_{1},j^{\prime}_{1}}$ to be an equilibrium, cooperating (resp.
defecting) best-responders must continue playing cooperation (resp. defection)
upon activation. Hence, it must hold that

(6) $\tau_{j_{1}+1}^{a}<n_{r,j_{1},j^{\prime}_{1}}<\tau_{j_{1}}^{a},$ (7)
$\tau_{j^{\prime}_{1}}^{c}<n_{r,j_{1},j^{\prime}_{1}}<\tau_{j^{\prime}_{1}+1}^{c},$

where $n_{r,j_{1},j^{\prime}_{1}}$ is the total number of cooperators at
$\bm{x}_{r,j_{1},j^{\prime}_{1}}$:

(8) $n_{r,j_{1},j^{\prime}_{1}}\triangleq
r+\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}.$

These conditions are necessary but not sufficient because of the presence of
the imitators. At equilibrium, either all imitators play the same strategy,
resulting in $x^{I}=0$ or $m$, or there are both a defector and a cooperator
earning the highest payoff. This results in three types of equilibrium
candidates: _(i) defection equilibrium candidate
$\bm{x}_{0,j_{1},j^{\prime}_{1}}$_, _(ii) cooperation equilibrium candidate
$\bm{x}_{m,j_{1},j^{\prime}_{1}}$_, and _(iii) mixed equilibrium candidate
$\bm{x}_{r,j_{1},j^{\prime}_{1}}$, $r\in\\{1,\ldots,m-1\\}$_. For each of
these candidates, we find separately the necessary and sufficient conditions
to be an equilibrium. Denote the highest payoff earned by the cooperators of
anticoordinating types $1,\ldots,j$ and coordinating types $1,\ldots,k$ when
the total number of cooperators is $n^{C}$ by $C_{j,k}(n^{C})$, i.e.,

$C_{j,k}(n^{C})=\sup\left\\{\sup_{i\in\left\\{1,\ldots,j\right\\}}C_{i}^{a}(n^{C}),\sup_{i\in\left\\{1,\ldots,k\right\\}}C_{i}^{c}(n^{C})\right\\},$

and denote the highest payoff earned by the defectors of anticoordinating
types $j,\ldots,b$ and coordinating types $k,\ldots,b^{\prime}$ when the total
number of cooperators is $n^{C}$ by $D_{j,k}(n^{C})$, i.e.,

$D_{j,k}(n^{C})=\sup\left\\{\sup_{i\in\left\\{j,\ldots,b\right\\}}D_{i}^{a}(n^{C}),\sup_{i\in\left\\{k,\ldots,b^{\prime}\right\\}}D_{i}^{c}(n^{C})\right\\}.$

######  Lemma 4.3.

$\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is an equilibrium if and only if (6) and
$\eqref{cTemperCond}$ hold for $r=0$, and

(9) $C_{j_{1},j^{\prime}_{1}}(n_{0,j_{1},j^{\prime}_{1}})\leq
D_{j_{1}+1,j^{\prime}_{1}+1}(n_{0,j_{1},j^{\prime}_{1}}).$

######  Proof 4.4.

(Sufficiency) Let $\bm{x}(0)=\bm{x}_{0,j_{1},j^{\prime}_{1}}$. Then
$n^{C}(0)\in(\tau_{j_{1}+1}^{a},\tau_{j_{1}}^{a})$ as (6) holds for $r=0$.
Therefore, nonconformists of types $1,\ldots,j_{1}$ (resp. $j_{1}+1,\ldots,b$)
are cooperating (resp. defecting) and will not switch strategies upon
activation according to (2) since
$n^{C}(0)<\tau_{j_{1}}^{a}<\ldots<\tau_{1}^{a}$ in view of (5). Similarly, the
conformists also stick to their strategies upon activation. On the other hand,
imitators are defecting and will not change their strategies upon activation
because

$D_{\mathrm{M}}(0)\geq
D_{j_{1}+1,j^{\prime}_{1}+1}(n_{0,j_{1},j^{\prime}_{1}})\overset{\eqref{C<D}}{\geq}C_{j_{1},j^{\prime}_{1}}(n_{0,j_{1},j^{\prime}_{1}})=C_{\mathrm{M}}(0).$

So $\bm{x}(1)=\bm{x}(0)$ under any activation sequence, proving that
$\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is an equilibrium.

(Necessity) Suppose $\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is an equilibrium. Let
$\bm{x}(0)=\bm{x}_{0,j_{1},j^{\prime}_{1}}$. Because nonconformists of type
$j_{1}$ (resp. $j_{1}+1$) are cooperating (resp. defecting) and continue doing
so upon activation, according to (2) it must hold that
$n^{C}(0)<\tau_{j_{1}}^{a}$ (resp. $n^{C}(0)>\tau_{j_{1}+1}^{a}$). So (6)
holds for $r=0$. Similarly, one can prove that (7) holds for $r=0$. Now we
show by contradiction that (9) must be in force. Suppose, on the contrary,
that

(10)
$C_{j_{1},j^{\prime}_{1}}(n_{0,j_{1},j^{\prime}_{1}})>D_{j_{1}+1,j^{\prime}_{1}+1}(n_{0,j_{1},j^{\prime}_{1}}).$

Because nonconformists of types $1,\ldots,j_{1}$ and conformists of types
$1,\ldots,j^{\prime}_{1}$ do not switch from cooperation to defection upon
activation, it must hold that at time $0$, $C_{i}^{a}>D_{i}^{a}$ for any
$i\in\\{1,\ldots,j_{1}\\}$, and $C_{i}^{c}>D_{i}^{c}$ for any
$i\in\\{1,\ldots,j^{\prime}_{1}\\}$. Hence, the followings hold when
$n^{C}=n_{0,j_{1},j^{\prime}_{1}}$:

$C_{j_{1},j^{\prime}_{1}}\geq\sup_{i\in\left\\{1,\ldots,j_{1}\right\\}}C_{i}^{a}>\sup_{i\in\left\\{1,\ldots,j_{1}\right\\}}D_{i}^{a},$
$C_{j_{1},j^{\prime}_{1}}\geq\sup_{i\in\left\\{1,\ldots,j^{\prime}_{1}\right\\}}C_{i}^{c}>\sup_{i\in\left\\{1,\ldots,j^{\prime}_{1}\right\\}}D_{i}^{c},$

which together with (10) result in
$C_{\mathrm{M}}(0)=C_{j_{1},j^{\prime}_{1}}(n_{0,j_{1},j^{\prime}_{1}})>D_{1,1}(n_{0,j_{1},j^{\prime}_{1}})\geq
D_{\mathrm{M}}(0)$. So under an activation sequence where the first active
agent is an imitator, she will switch from defection to cooperation. This
contradicts that $\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is an equilibrium,
completing the proof.

So for a defection equilibrium candidate to be an equilibrium, it is necessary
and sufficient that _(i)_ the total number of cooperators is less than the
tempers of cooperating nonconformists and defecting conformists, _(ii)_ the
total number of cooperators is greater than the tempers of defecting
nonconformists and cooperating conformists, and _(iii)_ a defecting best-
responder earns the highest utility. Similarly, we find the necessary and
sufficient condition for $\bm{x}_{m,j_{1},j^{\prime}_{1}}$ to be an
equilibrium.

######  Lemma 4.5.

$\bm{x}_{m,j_{1},j^{\prime}_{1}}$ is an equilibrium if and only if (6) and (7)
hold for $r=m$, and

$C_{j_{1},j^{\prime}_{1}}(n_{m,j_{1},j^{\prime}_{1}})\geq
D_{j_{1}+1,j^{\prime}_{1}+1}(n_{m,j_{1},j^{\prime}_{1}}).$

So the necessary and sufficient condition for a cooperation equilibrium
candidate to be an equilibrium is the same as in Lemma 4.3, except that the
second condition becomes “ _(ii)_ a cooperating best-responder earns the
highest utility”.

######  Lemma 4.6.

$\bm{x}_{r,j_{1},j^{\prime}_{1}}$, $r\in\\{1,\ldots,m-1\\}$, is an equilibrium
if and only if (6) and (7) hold, and

(11)
$C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})=D_{j_{1}+1,j^{\prime}_{1}+1}(n_{r,j_{1},j^{\prime}_{1}}).$

######  Proof 4.7.

(Sufficiency) Let $\bm{x}(0)=\bm{x}_{r,j_{1},j^{\prime}_{1}}$. It suffices to
show that $\bm{x}(1)=\bm{x}(0)$ under any activation sequence. Similar to the
proof of Lemma 4.3, it can be shown that because (6) and (7) hold, best-
responders do not switch strategies upon activation. To show that imitators do
not change strategies either, we prove that
$C_{\mathrm{M}}(0)=D_{\mathrm{M}}(0)$. We first show that
$C_{\mathrm{M}}(0)\geq D_{\mathrm{M}}(0)$. Because nonconformists of types
$1,\ldots,j_{1}$ and conformists of types $1,\ldots,j_{1}$ are initially
cooperating and continue doing so upon activation, similar to the proof of the
necessity part in Lemma 4.3, it can be shown that

$C_{\mathrm{M}}(0)\geq
C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})>\sup_{i\in\\{1,\ldots,j_{1}\\}}D_{i}^{a}(n_{r,j_{1},j^{\prime}_{1}}),$

and

$C_{\mathrm{M}}(0)\geq
C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})>\sup_{i\in\\{1,\ldots,j_{1}\\}}D_{i}^{c}(n_{r,j_{1},j^{\prime}_{1}}).$

Together with (11), these yield $C_{\mathrm{M}}(0)\geq
D_{1,1}(n_{r,j_{1},j^{\prime}_{1}})\geq D_{\mathrm{M}}(0)$. Similarly, we can
show that $D_{\mathrm{M}}(0)\geq C_{\mathrm{M}}(0)$, which results in
$C_{\mathrm{M}}(0)=D_{\mathrm{M}}(0)$ and completes the proof.

(Necessity) Suppose that $\bm{x}_{r,j_{1},j^{\prime}_{1}}$ is an equilibrium.
Similar to the proof of Lemma 4.3, it can be shown that (6) and (7) must be in
force. We prove by contradiction that (11) must also hold. Suppose on the
contrary that $C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})\neq
D_{j_{1}+1,j^{\prime}_{1}+1}(n_{r,j_{1},j^{\prime}_{1}})$. Then either of the
following two cases holds:

_Case 1._
$C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})>D_{j_{1}+1,j^{\prime}_{1}+1}(n_{r,j_{1},j^{\prime}_{1}})$.
Then similar to the argument for the necessity part in Lemma 4.3, we can show
that $C_{\mathrm{M}}(0)>D_{\mathrm{M}}(0)$. This leads to a contradiction
since under an activation sequence where the first active agent is a defecting
imitator, whose existence is guaranteed because $r\leq m-1$, she switches to
cooperation.

_Case 2._
$D_{j_{1}+1,j^{\prime}_{1}+1}(n_{r,j_{1},j^{\prime}_{1}})>C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})$.
Similar to the previous case, this also results in a contradiction, completing
the proof.

So the necessary and sufficient conditions for a mixed equilibrium candidate
to be an equilibrium to be an equilibrium are _(i)_ the total number of
cooperators is less (resp. greater) than the tempers of cooperating (resp.
defecting) nonconformists and defecting (resp. cooperating) conformists, and
_(ii)_ both a defecting and cooperating best-responder earn the highest
payoff.

###  4.3 Summary of the results

The following theorem follows from and summarizes Lemmas 4.1, 4.3, 4.5 and
4.6. Denote the set of all equilibria by $\mathcal{X}^{*}$ and the set of
states $\bm{x}_{r,j_{1},j^{\prime}_{1}}$ that are equilibria by $\mathcal{E}$,
i.e.,

$\displaystyle\mathcal{E}=\Big{\\{}\bm{x}_{r,j_{1},j^{\prime}_{1}}\,|\,$
$\displaystyle
r\in\\{0,\ldots,m\\},j_{1}\in\\{0,\ldots,b\\},j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\},$
(12)
$\displaystyle\tau_{j_{1}+1}^{a}<n_{r,j_{1},j^{\prime}_{1}}<\tau_{j_{1}}^{a},\tau_{j^{\prime}_{1}}^{c}<n_{r,j_{1},j^{\prime}_{1}}<\tau_{j^{\prime}_{1}+1}^{c},$
(13) $\displaystyle C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})\geq
D_{j_{1}+1,j^{\prime}_{1}+1}(n_{r,j_{1},j^{\prime}_{1}})\text{ if }r>0,$ (14)
$\displaystyle C_{j_{1},j^{\prime}_{1}}(n_{r,j_{1},j^{\prime}_{1}})\leq
D_{j_{1}+1,j^{\prime}_{1}+1}(n_{r,j_{1},j^{\prime}_{1}})\text{ if
}r<m\Big{\\}}.$

######  Theorem 4.8.

$\mathcal{X}^{*}=\mathcal{E}$.

This theorem provides an algorithmic approach to determine the set of all
equilibria of the population dynamics. For each combination of
$(r,j_{1},j^{\prime}_{1})$ where $r\in\\{0,\ldots,m\\}$,
$j_{1}\in\\{0,\ldots,b\\}$, and $j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$,
we check Conditions (12), (13) and (14). If all of them are satisfied, then
$\bm{x}_{r,j_{1},j^{\prime}_{1}}$ is an equilibrium and is added to the set of
equilibria. Otherwise, we examine the next combination of
$(r,j_{1},j^{\prime}_{1})$. Also note that from the examples in Section 3, we
know that a single population may admit multiple equilibria with different
number of cooperating imitators $r$, or may be not possess an equilibrium at
all.

###  4.4 Interpretation of the results

At any equilibrium, cooperators form a group of agents who tend to cooperate
when they are the only ones in the population who are cooperating (all outside
the group are defecting). We call such groups _cooperation-preserving_. If a
cooperation-preserving group contains an nonconformist, the group size must be
insufficient to make her switch strategies. Moreover, if a cooperation-
preserving group contains a conformist, the group size must be sufficient for
her to keep playing her strategy. As with imitators, if one belongs to the
cooperation-preserving group, then an agent in the group must earn the highest
utility when all inside the group are cooperating and all others, outside the
group, are defecting. Clearly, the cooperators at any equilibrium form a
cooperation-preserving group. However, a state with a cooperation-preserving
group of cooperators may not be an equilibrium. The condition is necessary but
not sufficient because the defecting outsiders may switch strategies. We,
hence, define a cooperation-preserving group to be _exclusive_ if no agent
outside the group tends to cooperate when they are all defecting. So the
number of individuals in an exclusive cooperation-preserving group is too many
for the outsiderish nonconformists to cooperate but not enough for the
outsiderish conformists to cooperate. On the other hand, if an exclusive
cooperation-preserving group does not contain all of the imitators, then one
of the outsiders must earn the highest utility when they all defect. This
argument results in the following proposition

######  Proposition 4.9.

A state $x$ is an equilibrium if and only if the cooperators at $x$ form an
exclusive cooperation-preserving group.

An exclusive cooperation-preserving group, hence, contains the maximum number
of cooperative best-responders such that the group size exceeds the temper of
conformists inside the group and nonconformists outside the group but falls
short of the tempers of the nonconformists inside the group and conformists
outside the group. This is presented in (12). An exclusive cooperation-
preserving group also contains the highest earner(s) if it includes an
imitator, implied by (13). It, however, does not contain all highest earners
if it does not include all imitators, which follows from (14).

##  5 Stability analysis

For $\bm{x}\in\mathbb{Z}^{d}$, $d\in\mathbb{N}$, consider the first norm
$\left\lVert\bm{x}\right\rVert=\sum_{i=1}^{d}|x_{i}|$. An equilibrium
$\bm{x}^{*}$ is _stable_ if for any $\epsilon>0$, there exists $\delta>0$ such
that for any initial state $\bm{x}(0)$ with
$\left\lVert\bm{x}(0)-\bm{x}^{*}\right\rVert<\delta$, we have
$\left\lVert\bm{x}(t)-\bm{x}^{*}\right\rVert<\epsilon$ for all $t\geq 0$ under
any activation sequence. Because any state $\bm{x}\in\mathcal{X}$ has
$x_{i}\in\mathbb{Z}_{\geq 0}$ for all $i\in\\{1,\ldots,b+b^{\prime}+1\\}$, we
require that $\delta>1$. Otherwise, $\bm{x}^{*}$ is always stable: for
$0<\delta\leq 1$, the only initial state that satisfies
$\left\lVert\bm{x}(0)-\bm{x}^{*}\right\rVert<\delta$ is $\bm{x}^{*}$ itself;
hence, for any $\epsilon>0$, we have
$\left\lVert\bm{x}(t)-\bm{x}^{*}\right\rVert=\left\lVert\bm{x}(0)-\bm{x}^{*}\right\rVert=0<\epsilon$
for all $t\geq 0$ and for all activation sequences. Similarly, we require that
$\epsilon>1$; otherwise, no state will be stable. Indeed, to prove stability,
we only need to consider all initial states $\bm{x}(0)$ with
$\left\lVert\bm{x}(0)-\bm{x}^{*}\right\rVert=1$. If starting from such states,
$\left\lVert\bm{x}(t)-\bm{x}^{*}\right\rVert\in\\{0,1\\}$ for all $t\geq 0$
and under any activation sequence, then $\bm{x}^{*}$ is a stable equilibrium
since for any $\epsilon>1$, $\delta=2$ satisfies the condition. Otherwise,
$\bm{x}^{*}$ is unstable as the condition is violated for $\epsilon=2$. In the
same way, the stability of equilibrium states has been studied under some
discrete dynamics [20, 14, 26]; however, none of these studies provide a
general definition, which we do in the following:

######  Definition 5.1.

Consider the time-dependent discrete dynamics $\bm{x}(t+1)=f(t,\bm{x}(t))$
where $\bm{x}\in\mathbb{Z}^{d}_{\geq 0},d\in\mathbb{N},f:\mathbb{Z}_{\geq
0}\times\mathbb{Z}^{d}_{\geq 0}\to\mathbb{Z}^{d}_{\geq 0}$. Assume that the
dynamics admit some equilibrium state $\bm{x}^{*}$, i.e.,
$f(t,\bm{x}^{*})=\bm{x}^{*}\forall t\in\mathbb{Z}_{\geq 0}$. The equilibrium
$\bm{x}^{*}$ is _stable_ if for any initial state $\bm{x}(0)$ with
$\left\lVert\bm{x}(0)-\bm{x}^{*}\right\rVert=1$, it holds that
$\left\lVert\bm{x}(t)-\bm{x}^{*}\right\rVert\leq 1\,\forall
t\in\mathbb{Z}_{\geq 0}$.

In our evolutionary game theory framework, this definition implies that if the
population state starts from the closed radius-one sphere centered at the
stable equilibrium, then the state may not leave the sphere, regardless of the
activation sequence. Namely, when all agents but one, say agent $p$, play the
same strategies that they play at equilibrium, none would switch strategies
(except for agent $p$ who may switch to her equilibrium strategy). In terms of
best-responders, this implies that none would change their equilibrium
strategies when the number of cooperators is one less or more than that at the
equilibrium. Hence, we expect the following to hold for a stable equilibrium
$\bm{x}_{r,j_{1},j^{\prime}_{1}},r\in\\{0,\ldots,m\\}$:

(15) $n_{r,j_{1},j^{\prime}_{1}}\in(\tau_{j_{1}+1}^{a}+1,\tau_{j_{1}}^{a}-1),$
(16)
$n_{r,j_{1},j^{\prime}_{1}}\in(\tau_{j^{\prime}_{1}}^{c}+1,\tau_{j^{\prime}_{1}+1}^{c}-1).$

In the following three lemmas, we find the necessary and sufficient condition
for defection, cooperation, and mixed equilibria to be stable. To simplify the
analysis, we assume that $n_{i}^{a}\geq 2$ for every $i\in\\{1,\ldots,b\\}$,
$n_{i}^{c}\geq 2$ for every $i\in\\{1,\ldots,b^{\prime}\\}$, and $m\geq 1$.

######  Lemma 5.2.

Consider $j_{1}\in\\{0,\ldots,b\\}$,
$j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$, where at least one of them is
non-zero. Then $\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is a stable equilibrium if
and only if (15) and (16) hold for $r=0$, and for
$n^{C}\in\\{n_{0,j_{1},j^{\prime}_{1}}-1,n_{0,j_{1},j^{\prime}_{1}},n_{0,j_{1},j^{\prime}_{1}}+1\\}$,

(17) $C_{j_{1},j^{\prime}_{1}}(n^{C})\leq
D_{j_{1}+1,j^{\prime}_{1}+1}(n^{C}).$

######  Proof 5.3.

(Sufficiency) According to Lemma 4.3, $\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is an
equilibrium. Consider $\bm{x}(0)\in\mathcal{X}$ with
$\left\lVert\bm{x}(0)-\bm{x}_{0,j_{1},j^{\prime}_{1}}\right\rVert=1$. At time
$0$, all agents except one, say agent $p$, play the same strategies that they
play at $\bm{x}_{0,j_{1},j^{\prime}_{1}}$. It suffices to show that
$\bm{x}(1)\in\\{\bm{x}(0),\bm{x}_{0,j_{1},j^{\prime}_{1}}\\}$ under any
activation sequence since inductively it can then be show that
$\bm{x}(t)\in\\{\bm{x}(0),\bm{x}_{0,j_{1},j^{\prime}_{1}}\\}$ for any $t\geq
0$, implying that
$\left\lVert\bm{x}(t)-\bm{x}_{0,j_{1},j^{\prime}_{1}}\right\rVert\leq 1$. One
of the following cases is in force:

_Case 1:_ agent $p$ is an imitator. Then she must be cooperating; hence,
$n^{C}(0)=n_{0,j_{1},j^{\prime}_{1}}+1$. In view of (15) and (16), no best-
responder switches strategies. Moreover, because (17) holds for
$n^{C}=n_{0,j_{1},j^{\prime}_{1}}+1$, it can be shown, similar to the proof of
Lemma 4.3, that $D_{\mathrm{M}}(0)\geq C_{\mathrm{M}}(0)$. This implies all
imitators, except agent $p$, will stick to their current strategies. Thus,
$\bm{x}(1)\in\\{\bm{x}(0),\bm{x}_{0,j_{1},j^{\prime}_{1}}\\}$ under any
activation sequence.

_Case 2:_ agent $p$ is an nonconformist of some type
$j\in\\{1,\ldots,j_{1}\\}$. Then agent $p$ must be defecting, making
$n^{C}(0)=n_{0,j_{1},j^{\prime}_{1}}-1$. Hence, given (15) and (16), no best-
responder, except for agent $p$, will switch strategies. Similar to the first
case, it can be shown that no imitator will switch strategies since she is
defecting and (17) holds for $n_{0,j_{1},j^{\prime}_{1}}-1$. Hence,
$\bm{x}(1)\in\\{\bm{x}(0),\bm{x}_{0,j_{1},j^{\prime}_{1}}\\}$ under any
activation sequence.

All other cases can be handled similarly: _Case 3:_ agent $p$ is a conformist
of some type $j\in\\{1,\ldots,j^{\prime}_{1}\\}$; _Case 4:_ agent $p$ is an
nonconformist of some type $j\in\\{j_{1}+1,\ldots,b\\}$; _Case 5:_ agent $p$
is a conformist of some type $j\in\\{j^{\prime}_{1}+1,\ldots,b^{\prime}\\}$.

(Necessity) We prove by contradiction that (15), (16) and (17) must hold.
Suppose, on the contrary, that (15) does not hold. If
$n_{0,j_{1},j^{\prime}_{1}}\geq\tau_{j_{1}}^{a}-1$, then due to the assumption
of having non-integer tempers,
$n_{0,j_{1},j^{\prime}_{1}}>\tau_{j_{1}}^{a}-1$. If $j_{1}=0$, then in view of
(8), $n-m\geq n_{0,j_{1},j^{\prime}_{1}}>\tau_{j_{1}}^{a}-1>n-1$,
contradicting the assumption $m\geq 1$. Now consider the case $j_{1}\geq 1$.
For the initial state $\bm{x}(0)$ where all agents but an imitator play the
same strategies that they play at $\bm{x}_{0,j_{1},j^{\prime}_{1}}$, under an
activation sequence where the first active agent is an nonconformist of type
$j_{1}$, she will switch from cooperation to defection since
$n^{C}(0)=n_{0,j_{1},j^{\prime}_{1}}+1>\tau_{j_{1}}$. This contradicts the
stability of $\bm{x}_{0,j_{1},j^{\prime}_{1}}$ since
$\left\lVert\bm{x}(1)-\bm{x}_{0,j_{1},j^{\prime}_{1}}\right\rVert=2$.
Similarly, $n_{0,j_{1},j^{\prime}_{1}}\leq\tau_{j_{1}+1}^{a}+1$ also leads to
a contradiction. Therefore, (15) must be in force. The same argument proves
that (16) holds. Now suppose on the contrary that (17) does not hold for some
$n^{C}\in\\{n_{0,j_{1},j^{\prime}_{1}}-1,n_{0,j_{1},j^{\prime}_{1}},n_{0,j_{1},j^{\prime}_{1}}+1\\}$.
Based on Lemma 4.3, $n^{C}=n_{0,j_{1},j^{\prime}_{1}}$ satisfies (17) because
$\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is an equilibrium. Hence, one of the
followings must hold:

(18)
$C_{j_{1},j^{\prime}_{1}}(n_{0,j_{1},j^{\prime}_{1}}-1)>D_{j_{1}+1,j^{\prime}_{1}+1}(n_{0,j_{1},j^{\prime}_{1}}-1),$
(19)
$C_{j_{1},j^{\prime}_{1}}(n_{0,j_{1},j^{\prime}_{1}}+1)>D_{j_{1}+1,j^{\prime}_{1}+1}(n_{0,j_{1},j^{\prime}_{1}}+1).$

Either $j_{1}>0$ or $j^{\prime}_{1}>0$. We only prove the case with $j_{1}>0$
since the other can be handled similarly. If (18) holds, then consider an
initial state where all agents play the same strategy that they play at
$\bm{x}_{0,j_{1},j^{\prime}_{1}}$, except for an nonconformist of type
$j_{1}$. Then because $n^{a}_{j_{1}}\geq 2$, there is still one more
type-$j_{1}$ nonconformist who does not tend to switch to defection;
otherwise, $\bm{x}_{0,j_{1},j^{\prime}_{1}}$ is not stable. Thus,
$C^{a}_{j_{1}}\geq D^{a}_{j_{1}}$. It is also clear that $C^{a}_{i}\geq
D^{a}_{i}$ for all $i\in\\{1,\ldots,j_{1}-1\\}$. Hence, in view of (18),
$C_{\mathrm{M}}(0)>D_{\mathrm{M}}(0)$. Therefore, under an activation sequence
where the first active agent is an imitator, she will switch to cooperation,
yielding a contradiction. A similar argument shows that (19) also results in a
contradiction, completing the proof.

For the special case of $j_{1}=j^{\prime}_{1}=0$, the state $\bm{x}_{0,0,0}$
can be shown to be stable if and only if it is an equilibrium and
$n_{0,0,0}=0<\tau_{1}^{c}-1$, or equivalently $\tau^{c}_{1}>1$.

Compared to the equilibrium condition for a defection equilibrium candidate
(Lemma 4.3), the stability condition is slightly tighter. It requires the
number of cooperators to distance by at least one from the tempers of the
benchmark types. It also requires the defecting best-responders to earn the
highest utility, also when the total number of cooperators changes by one.
Therefore, the defection equilibrium of a population in general “is likely” to
be stable. The following results can be proven similarly to Lemma 5.2.

######  Lemma 5.4.

Consider $j_{1}\in\\{0,\ldots,b\\}$,
$j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$ where at least one of $j_{1}<b$
and $j^{\prime}_{1}<b$ hold. Then $\bm{x}_{m,j_{1},j^{\prime}_{1}}$ is a
stable equilibrium if and only if (15) and (16) hold for $r=m$, and for
$n^{C}\in\\{n_{m,j_{1},j^{\prime}_{1}}-1,n_{m,j_{1},j^{\prime}_{1}},n_{m,j_{1},j^{\prime}_{1}}+1\\}$,

$C_{j_{1},j^{\prime}_{1}}(n^{C})\geq D_{j_{1}+1,j^{\prime}_{1}+1}(n^{C}).$

For the special case of $j_{1}=b$ and $j^{\prime}_{1}=b$,
$\bm{x}_{m,j_{1},j^{\prime}_{1}}$ is a stable equilibrium if and only if it is
an equilibrium and $n_{m,b,b^{\prime}}=n>\tau_{b}^{c}+1$.

######  Lemma 5.5.

Consider $j_{1}\in\\{0,\ldots,b\\}$,
$j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$. Then for any
$r\in\\{1,\ldots,m-1\\}$, $\bm{x}_{r,j_{1},j^{\prime}_{1}}$ is a stable
equilibrium if and only if (15) and (16) hold, and for
$n^{C}\in\\{n_{r,j_{1},j^{\prime}_{1}}-1,n_{r,j_{1},j^{\prime}_{1}},n_{r,j_{1},j^{\prime}_{1}}+1\\}$,

$C_{j_{1},j^{\prime}_{1}}(n^{C})=D_{j_{1}+1,j^{\prime}_{1}+1}(n^{C}).$

The condition in the above lemma is strong since it requires
$\bm{x}_{r-1,j_{1},j^{\prime}_{1}}$, $\bm{x}_{r,j_{1},j^{\prime}_{1}}$ and
$\bm{x}_{r+1,j_{1},j^{\prime}_{1}}$ to be equilibria. Namely, the mixed
equilibrium must be surrounded by adjacent other equilibria in the state
space. It is, thus, generally “unlikely” for a mixed equilibrium to be stable.
The following theorem summarizes Lemma 5.2, Lemma 5.4 and Lemma 5.5.

######  Theorem 5.6.

For $r\in\\{0,\ldots,m\\}$, $j_{1}\in\\{0,\ldots,b\\}$ and
$j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\}$ where
$(r,j_{1},j_{1})\notin\\{(0,0,0),(m,b,b^{\prime})\\}$,
$\bm{x}_{r,j_{1},j^{\prime}_{1}}$ is a stable equilibrium if and only if (15)
and (16) hold, and for
$n^{C}\in\\{n_{r,j_{1},j^{\prime}_{1}}-1,n_{r,j_{1},j^{\prime}_{1}},n_{r,j_{1},j^{\prime}_{1}}+1\\}$,

$C_{j_{1},j^{\prime}_{1}}\leq D_{j_{1},j^{\prime}_{1}}\text{ if }r<m\text{,
and }C_{j_{1},j^{\prime}_{1}}\geq D_{j_{1},j^{\prime}_{1}}\text{ if }r>0.$

##  6 Positively invariant sets

As seen in Example 3.2, the population may never settle down and undergo
perpetual fluctuations, even though it admits an equilibrium. In that case,
the population is stranded in a set of states. We define a non-empty set
$\mathcal{S}\subseteq\mathcal{X}$ to be _positively invariant_ if
$\bm{x}(0)\in\mathcal{S}$ implies $\bm{x}(t)\in\mathcal{S}\forall t\geq 0$,
under any activation sequence. For simplicity, we refer to a positively
invariant set as an _invariant set_. An invariant set is _minimal_ if it does
not contain any other invariant set except its two trivial subsets, itself and
the empty set. Similar to [14], it is easy to show that starting from any
initial condition, the population dynamics will reach a minimal invariant set
$\mathcal{O}$ in finite time and stay there hence. If the minimal invariant
set is a singleton, then it is basically an equilibrium state. Otherwise, it
is a set of more than one states, each will be visited by the solution
trajectory infinitely often:

######  Lemma 6.1 ([14]).

Consider a minimal invariant set $\mathcal{O}$. If $\bm{x}(0)\in\mathcal{O}$,
then for any state $\bar{\bm{x}}\in\mathcal{O}$ and any $T\geq 0$, there
exists some time $t\geq T$ such that $\bm{x}(t)=\bar{\bm{x}}$.

Our ultimate goal is to explicitly characterize all minimal invariant sets.
This, however, turns out to be an intricate problem. Instead, in each of the
following subsections, we find necessary conditions for a set $\mathcal{O}$ to
be minimally invariant. Namely we define a set, say $\mathcal{A}$, satisfying
the necessary conditions, and prove that $\mathcal{O}\subseteq\mathcal{A}$.
This partially informs us about the form of $\mathcal{O}$ and helps us to
limit our search in finding the minimal invariant sets. Ideally, if the
conditions are sharp enough, we would have $\mathcal{A}=\mathcal{O}$, which is
not the case with this paper and remains an open problem. Instead, we find
necessary and sufficient conditions for the set $\mathcal{A}$ to be invariant
as then the existence of a minimal invariant subset
$\mathcal{O}\subseteq\mathcal{A}$ is guaranteed.

###  6.1 Benchmark types

Consider a invariant set $\mathcal{O}$ and a solution trajectory $\bm{x}(t)$
with the initial condition $\bm{x}(0)\in\mathcal{X}$. The number of
cooperators will then be confined to the interval
$[\min_{\bm{x}\in\mathcal{O}}n^{C}(\bm{x}),\max_{\bm{x}\in\mathcal{O}}n^{C}(\bm{x})]$,
called a _fluctuation interval_. All nonconformists whose tempers are higher
than the maximum number of cooperators in the fluctuation interval must be
cooperating at any state in $\mathcal{O}$ since, otherwise, they will switch
from defection to cooperation upon activation and never change back, implying
the existence of a non-trivial subset of $\mathcal{O}$ which is invariant,
leading to a contradiction. Similarly, all nonconformists whose tempers are
lower than the minimum number of cooperators in the fluctuation interval must
be defecting. We, hence, expect the existences of anticoordinating benchmark
types $j_{1},j_{2}\in\\{0,\ldots,b+1\\}$, $j_{1}<j_{2}$, such that all
nonconformists of types $1,\ldots,j_{1}$ cooperate and all nonconformists of
types $j_{2},\ldots,b$ defect at every state in $\mathcal{O}$. By following a
similar argument, we expect the existence of coordinating benchmark types
$j^{\prime}_{1},j^{\prime}_{2}\in\\{0,\ldots,b^{\prime}+1\\}$,
$j^{\prime}_{1}<j^{\prime}_{2}$, such that all conformists of types
$1,\ldots,j^{\prime}_{1}$ cooperate and all conformists of types
$j^{\prime}_{2},\ldots,b^{\prime}$ defect at every state in $\mathcal{O}$.
Define $\mathcal{J}$ to be the set of all possible combinations of
$(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})$, i.e.,

$\displaystyle\mathcal{J}\triangleq\Big{\\{}(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\,|\,$
$\displaystyle j_{1}\in\\{0,\ldots,b\\},j_{2}\in\\{j_{1}+1,\ldots,b+1\\}$
$\displaystyle
j^{\prime}_{1}\in\\{0,\ldots,b^{\prime}\\},j^{\prime}_{2}\in\\{j^{\prime}_{1}+1,\ldots,b^{\prime}+1\\}\Big{\\}}.$

For $(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$, define the
set

$\displaystyle\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}\triangleq\Big{\\{}\bm{x}\in\mathcal{X}\,|\,x_{i}^{a}=n_{i}^{a}$
$\displaystyle\ \forall i\in\left\\{1,\ldots,j_{1}\right\\},\quad x_{i}^{a}=0\
\forall i\in\left\\{j_{2},\ldots,b\right\\},$ $\displaystyle
x_{i}^{c}=n_{i}^{c}$ $\displaystyle\ \forall
i\in\left\\{1,\ldots,j^{\prime}_{1}\right\\},\quad x_{i}^{c}=0\ \forall
i\in\left\\{j^{\prime}_{2},\ldots,b^{\prime}\right\\}\Big{\\}}.$

In what follows, we consider an arbitrary minimal invariant set $\mathcal{O}$,
and correspondingly define the minimum and maximum number of cooperators in
the set, i.e., $S=\min_{\bm{x}\in\mathcal{O}}n^{C}(\bm{x})$, and
$L=\max_{\bm{x}\in\mathcal{O}}n^{C}(\bm{x})$, and the benchmark types

(20)
$\xi_{1}\triangleq\max\left\\{j\in\left\\{0,b+1\right\\}\,|\,\tau_{j}^{a}>L\right\\},$
(21)
$\xi_{2}\triangleq\min\left\\{j\in\left\\{0,b+1\right\\}\,|\,\tau_{j}^{a}<S\right\\},$
(22)
$\xi^{\prime}_{2}\triangleq\min\left\\{j\in\left\\{0,b^{\prime}+1\right\\}\,|\,\tau_{j}^{c}>L\right\\},$
(23)
$\xi^{\prime}_{1}\triangleq\max\left\\{j\in\left\\{0,b^{\prime}+1\right\\}\,|\,\tau_{j}^{c}<S\right\\}.$

As a necessary condition for a set to be invariant, we prove that it must be
included in $\mathcal{X}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{1}}$.

######  Proposition 6.2.

$\mathcal{O}\subseteq\mathcal{X}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{1}}$.

######  Proof 6.3.

We prove by contradiction. Suppose on the contrary, that there exists
$\bm{x}\in\mathcal{O}$ such that
$\bm{x}\notin\mathcal{X}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{2}}$.
Then, one of the following cases holds:

_Case 1:_ $x_{i}^{a}<n_{i}^{a}$ for some $i\in\\{1,\ldots,\xi_{1}\\}$.
Consider the initial state $\bm{x}(0)=\bm{x}$. Under an activation sequence
where the first active agent is a defecting nonconformist of type $i$, she
will switch to cooperation and never change back since for any $t\geq 0$,
$\bm{x}(t)\in\mathcal{O}$ implies that $n^{C}(t)\leq
L\overset{\eqref{O:j_1}}{<}\tau_{\xi_{1}}^{a}\overset{\eqref{TemperOrder}}{\leq}\tau_{i}^{a}$.
This implies that $\bm{x}(t)\in\mathcal{O}\backslash\\{\bm{x}\\}$ for all
$t\geq 1$, contradicting Lemma 6.1.

Similarly, we can prove that _Case 2:_ $x_{i}^{c}<n_{i}^{c}$ for some
$i\in\\{1,\ldots,\xi^{\prime}_{1}\\}$, _Case 3:_ $x_{i}^{a}>n_{i}^{a}$ for
some $i\in\\{\xi_{2},\ldots,b\\}$ and _Case 4:_ $x_{i}^{c}>0$ for some
$i\in\\{\xi^{\prime}_{2},\ldots,b^{\prime}\\}$, all result in a contradiction,
completing the proof.

So when the population reaches a state in $\mathcal{O}$, all nonconformists of
types $1,\ldots,\eta_{1}$ and conformists of types
$1,\ldots,\eta^{\prime}_{1}$ fix their strategies to cooperation, and all
nonconformists of types $\eta_{2},\ldots,m$ and conformists of types
$\eta^{\prime}_{2},\ldots,m$ fix their strategies to defection. We call these
best-responders _fixed_ and refer to other best-responders as _wandering_.
Now, we show that all wandering conformists defect when the number of
cooperators reaches its minimum and cooperate when it reaches its maximum.

######  Lemma 6.4.

Consider a state $\bm{x}\in\mathcal{O}$. If $n^{C}(\bm{x})=S$, then
$x_{i}^{c}=0\ \forall
i\in\left\\{\xi^{\prime}_{1}+1,\ldots,\xi^{\prime}_{2}-1\right\\}$, and if
$n^{C}(\bm{x})=L$, then $x_{i}^{c}=n_{i}^{c}\ \forall
i\in\left\\{\xi^{\prime}_{1}+1,\ldots,\xi^{\prime}_{2}-1\right\\}$.

######  Proof 6.5.

First, we prove the first statement by contradiction. Suppose on the contrary
there exists $\bm{x}\in\mathcal{O}$ such that $n^{C}(\bm{x})=S$ and there is a
cooperating conformist of type
$i\in\left\\{\xi^{\prime}_{1}+1,\ldots,\xi^{\prime}_{2}-1\right\\}$. Consider
the initial state $\bm{x}(0)=\bm{x}$. Under an activation sequence where a
cooperating conformist of type $i$ is active at time $0$, she will switch to
defection, because
$S\overset{\eqref{O:j'_1}}{<}\tau_{\xi^{\prime}_{1}+1}^{c}\overset{\eqref{TemperOrder}}{\leq}\tau_{i}^{c}$.
This results in $n^{C}(1)=S-1<S$, implying $\bm{x}(1)\notin\mathcal{O}$,
contradicting the invariance of $\mathcal{O}$. The second part can be proved
similarly.

The wandering nonconformists do not necessarily form such a harmony at the
extreme number of cooperators. Nevertheless, none of them may fix their
strategies when the population dynamics are limited to $\mathcal{O}$.

######  Lemma 6.6.

For every $i\in\left\\{\xi_{1}+1,\ldots,\xi_{2}-1\right\\}$, there exist
$\bm{x},\bm{y}\in\mathcal{O}$ such that $x_{i}^{a}\neq y_{i}^{a}$.

######  Proof 6.7.

We prove by contradiction. Suppose the contrary that there exist
$i\in\left\\{\xi_{1}+1,\ldots,\xi_{2}-1\right\\}$ and
$k\in\\{0,\ldots,n_{i}^{a}\\}$ such that for all $\bm{x}\in\mathcal{O}$,
$x_{i}^{a}=k$. One of the following two cases must be in force:

_Case 1_ : $k<n_{i}^{a}$. Consider an initial state $\bm{x}(0)\in\mathcal{O}$
with $n^{C}(0)=S$. Then $x_{i}^{a}(0)=k<n_{i}^{a}$ implies the existence of a
defecting nonconformist of type $i$. Under an activation sequence where she is
the first active agent, she will switch to cooperation because
$S\overset{\eqref{O:j_2}}{<}\tau_{\xi_{2}-1}^{a}\overset{\eqref{TemperOrder}}{\leq}\tau_{i}^{a}$.
This results in $x_{i}^{a}(1)=k+1$, which contradicts the assumption of
$x_{i}^{a}$ being fixed to $k$.

_Case 2_ : $k>0$. Similarly, we can show that this also leads to a
contradiction, completing the proof.

So when the population dynamics are in $\mathcal{O}$, the wandering
nonconformists of the same types are neither all fixed to cooperation nor all
to defection.

######  Lemma 6.8.

For every $i\in\left\\{\xi_{1}+1,\ldots,\xi_{2}-1\right\\}$, there exists
$\bm{x},\bm{y}\in\mathcal{O}$ such that $0<x_{i}^{a}$ and
$y_{i}^{a}<n_{i}^{a}$.

######  Proof 6.9.

We prove by contradiction. Assume on the contrary, that no such pair of
$\bm{x}$ and $\bm{y}$ exists. Let
$i\in\left\\{\xi_{1}+1,\ldots,\xi_{2}-1\right\\}$. Then either for every state
$z\in\mathcal{O}$, $z_{i}^{a}=0$ or for every state $z\in\mathcal{O}$,
$z_{i}^{a}=n_{i}^{a}$, both contradicting Lemma 6.6.

We know that all states in a minimal invariant set $\mathcal{O}$ belong to the
set $\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ for some
$(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$. Yet this does not
make $\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ invariant. The
following result states the necessary and sufficient condition for the set
$\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ to be invariant.
Define

$\tau^{\max}_{j_{2},j^{\prime}_{1}}\triangleq\max\\{\tau_{j_{2}}^{a},\tau_{j^{\prime}_{1}}^{c}\\}\quad\text{and}\quad\tau^{\min}_{j_{1},j^{\prime}_{2}}\triangleq\min\\{\tau_{j_{1}}^{a},\tau_{j^{\prime}_{2}}^{c}\\}.$

######  Proposition 6.10.

For $(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$,
$\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ is a invariant set
if and only if the following two hold:

(24) $\displaystyle\tau^{\max}_{j_{2},j^{\prime}_{1}}<$
$\displaystyle\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c},$
(25) $\displaystyle
m+\sum_{i=1}^{j_{2}-1}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{2}-1}n_{i}^{c}<\tau^{\min}_{j_{1},j^{\prime}_{2}}.$

######  Proof 6.11.

(Necessity) Suppose $\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$
is an invariant set. We first prove by contradiction that

(26)
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}>\tau_{j_{2}}^{a}.$

If on the contrary
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}\leq\tau_{j_{2}}^{a}$,
then because of the non-integer tempers assumption,
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}<\tau_{j_{2}}^{a}$.
Hence, $j_{2}\leq b$ since $\tau_{b+1}^{a}<0$. Consider
$\bm{x}(0)=(0,n_{1}^{a},\ldots,n_{j_{1}}^{a},0,\ldots,0,0,\ldots,0,n_{j^{\prime}_{1}}^{c},\ldots,n^{c}_{1})\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$.
If a type-$j_{2}$ nonconformist is initially active, she will switch from
defection to cooperation because
$n^{C}(0)=\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}<\tau_{j_{2}}^{a}$.
So $x_{j_{2}}^{a}(1)=1$, resulting in
$\bm{x}(1)\notin\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$. This
contradicts that $\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ is
invariant. Similarly, it can be shown that
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}>\tau_{j^{\prime}_{1}}^{c}$,
which together with (26) yields (24). In the same way, by considering
$\bm{x}(0)=(m,n_{1}^{a},\ldots,n_{j_{2}-1}^{a},0,\ldots,0,0,\ldots,0,n_{j^{\prime}_{2}-1}^{c},\ldots,n^{c}_{1})$,
we can prove (25).

(Sufficiency) Suppose (24) and (25) are in force. It suffices to show that if
$\bm{x}(0)\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$, then
$\bm{x}(1)\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ under
any activation sequence. Because
$n^{C}(0)\leq\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}<\tau^{\min}_{j_{1},j^{\prime}_{2}}\leq\tau_{j_{1}}^{a}$,
nonconformists of types $1,\ldots,j_{1}$ do not switch strategies upon
activation at time $0$ as they are already cooperating. One can show the same
for the remaining of the fixed agents, completing the proof.

In essence, the necessary and sufficient invariance condition for the set
$\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ is that fixed best-
responders do not switch strategies. Note that this set is not tight enough as
$\mathcal{X}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{2}}$ may not be
invariant, although
$\mathcal{O}\subset\mathcal{X}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{2}}$.

######  Corollary 6.12.

For every $(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$ that
satisfies (24) and (25), there exists a minimal invariant set
$\mathcal{O}\subseteq\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$.

###  6.2 Minimum and maximum number of cooperators

For a subset of $\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ to
be invariant, it is necessary that every state $\bm{x}$ in the subset to
satisfy
$n^{C}(\bm{x})\in(\tau^{\max}_{j_{2},j^{\prime}_{1}},\tau^{\min}_{j_{1},j^{\prime}_{2}})$.
Thus, we confine $\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ to
the subset

$\displaystyle\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}\triangleq\Big{\\{}\bm{x}\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}\,|\,\tau^{\max}_{j_{2},j^{\prime}_{1}}<n^{C}(\bm{x})<\tau^{\min}_{j_{1},j^{\prime}_{2}}\Big{\\}}.$

It clearly holds that
$\mathcal{O}\subseteq\mathcal{S}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{1}}$,
resulting in
$\tau^{\max}_{\xi_{2},\xi^{\prime}_{1}}<n^{C}(\bm{x})<\tau^{\min}_{\xi_{1},\xi^{\prime}_{2}}$.
However, the types $\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{1}$, and in
turn the thresholds $\tau^{\max}_{\xi_{2},\xi^{\prime}_{1}}$ and
$\tau^{\min}_{\xi_{1},\xi^{\prime}_{2}}$, are defined based on the extremum
number of cooperators $S$ and $L$. So the inequality
$\tau^{\max}_{\xi_{2},\xi^{\prime}_{1}}<n^{C}(\bm{x})<\tau^{\min}_{\xi_{1},\xi^{\prime}_{2}}$
does not inform $\mathcal{O}$ further than the trivial inequality
$S<n^{C}(\bm{x})<L$. Instead, we find the necessary and sufficient condition
for $\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ to be invariant.
Because for any
$\bm{x}\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$,
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}\leq
n^{C}(\bm{x})\leq
m+\sum_{i=1}^{j_{2}-1}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{2}-1}n_{i}^{c}$, the
following must hold for
$\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ to be nonempty:

(27)
$\tau^{\max}_{j_{2},j^{\prime}_{1}}<m+\sum_{i=1}^{j_{2}-1}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{2}-1}n_{i}^{c},$
(28)
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}<\tau^{\min}_{j_{1},j^{\prime}_{2}}.$

######  Lemma 6.13.

Given $(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$ that
satisfies

(29)
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}<\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil,$

the set $\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ is
invariant, only if the followings hold:

  1. 1.

at every $\bm{x}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$
with
$n^{C}(\bm{x})=\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$, a
cooperator earns the highest payoff;

  2. 2.

$\tau_{j^{\prime}_{2}-1}^{c}<\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil<\tau_{j_{2}-1}^{a}$.

######  Proof 6.14.

First we prove Part 1. by contradiction. Suppose on the contrary, there exists
$\bm{x}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ such that
$n^{C}(\bm{x})=\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$ and
all highest earners are defectors. Because of (29),
$n^{C}(\bm{x})>\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}$,
implying the existence of a cooperator who is either an imitator, an
nonconformist of type $i\in\\{j_{1}+1,\ldots,b\\}$ or a conformist of type
$i\in\\{j^{\prime}_{1}+1,\ldots,b^{\prime}\\}$. Should the cooperator be an
imitator, she would switch to defection if she becomes active, resulting in a
state with the total number of cooperators less than
$\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$, contradicting the
invariance of $\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$.
Should one of the other two cases hold, i.e., $x^{a}_{i}>0$ or $x^{c}_{i}>0$,
then since $m>0$, the state $\bm{y}=\bm{x}+\bm{1}_{1}-\bm{1}_{1+i}$ or
$\bm{y}=\bm{x}+\bm{1}_{1}-\bm{1}_{1+b+i}$ would also be in
$\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$, where $\bm{1}_{j}$
is the vector of all zeros except for the $j^{th}$ entry that is one. In other
words, we can modify $\bm{x}$ to obtain the state
$\bm{y}\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ with the
same number of cooperators, resulting in
$\bm{y}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$, but where
instead of the best-responding cooperator, there is an imitating cooperator.
Since the type of the imitator is the same as one of the best-responders, and
the defectors among the best-responders were already earning the highest
utility at $\bm{x}$, it can be concluded that defectors also earn the highest
utility at $\bm{y}$. Hence, again the imitator would switch to defection if
she becomes active, resulting in a contradiction.

Next, we show by contradiction that
$\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil<\tau_{j_{2}-1}^{a}$.
Suppose on the contrary that
$\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil\geq\tau_{j_{2}-1}^{a}$.
Then, because of the non-integer temper assumption,
$\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil>\tau_{j_{2}-1}^{a}$.
According to
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}<\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$
and (27), there exists
$\bm{x}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ such that
$n^{C}(\bm{x})=\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$ and
an nonconformist of type $j_{2}-1$ is cooperating at $\bm{x}$. Consider the
initial state $\bm{x}(0)=\bm{x}$. Under an activation sequence where the first
active agent is a cooperating nonconformist of type $j_{2}-1$, she will switch
to defection, which also results in a contradiction. Similarly, we can show
that
$\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil>\tau_{j^{\prime}_{2}-1}^{c}$.
The proof is then complete.

######  Lemma 6.15.

Given $(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$ that
satisfies

$m+\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}>\left\lfloor\tau^{\min}_{j_{1},j^{\prime}_{2}}\right\rfloor,$

the set $\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ is
invariant, only if the followings hold:

  1. 1.

at every $\bm{x}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$
with
$n^{C}(\bm{x})=\left\lfloor\tau^{\min}_{j_{1},j^{\prime}_{2}}\right\rfloor$, a
defector earns the highest payoff;

  2. 2.

$\tau_{j_{1}+1}^{a}<\left\lfloor\tau^{\min}_{j_{1},j^{\prime}_{2}}\right\rfloor<\tau_{j^{\prime}_{1}+1}^{c}$.

######  Proof 6.16.

The proof is similar to that of Lemma 6.13.

######  Theorem 6.17.

Given $(j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1})\in\mathcal{J}$, the set
$\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ is invariant if and
only if the following two conditions hold:

  1. 1.

either
$\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}\geq\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$
or the followings hold:

    1. (a)

at every $\bm{x}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$
with
$n^{C}(\bm{x})=\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil$, a
cooperator earns the highest payoff;

    2. (b)

$\tau_{j^{\prime}_{2}-1}^{c}<\left\lceil\tau^{\max}_{j_{2},j^{\prime}_{1}}\right\rceil<\tau_{j_{2}-1}^{a}$,

  2. 2.

either
$m+\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}\leq\left\lfloor\tau^{\min}_{j_{1},j^{\prime}_{2}}\right\rfloor$
or the followings hold:

    1. (a)

at every $\bm{x}\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$
with
$n^{C}(\bm{x})=\left\lfloor\tau^{\min}_{j_{1},j^{\prime}_{2}}\right\rfloor$, a
defector earns the highest payoff;

    2. (b)

$\tau_{j_{1}+1}^{a}<\left\lfloor\tau^{\min}_{j_{1},j^{\prime}_{2}}\right\rfloor<\tau_{j^{\prime}_{1}+1}^{c}$.

######  Proof 6.18.

The necessity has been proved in Lemma 6.13 and Lemma 6.15. For sufficiency,
we show that if
$\bm{x}(0)\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$, then
$\bm{x}(1)\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$ under
any activation sequence. Similar to the proof of Proposition 6.10, we can
prove that
$\bm{x}(1)\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$. Then it
suffices to show that
$n^{C}(1)\in(\tau_{j_{2},j^{\prime}_{1}}^{\max},\tau_{j_{1},j^{\prime}_{2}}^{\min})$.
To do so, we prove that if
$n^{C}(0)=\left\lceil\tau_{j_{2},j^{\prime}_{1}}^{\max}\right\rceil$, then
$n^{C}(1)\geq n^{C}(0)$, and similarly it can be shown that if
$n^{C}(0)=\left\lfloor\tau_{j_{1},j^{\prime}_{2}}^{\min}\right\rfloor$, then
$n^{C}(1)\leq n^{C}(0)$. Because
$\bm{x}(0)\in\mathcal{S}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}\subseteq\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$,
it holds that
$\left\lceil\tau_{j_{2},j^{\prime}_{1}}^{\max}\right\rceil=n^{C}(0)\geq\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}$.
Then either of the two cases can happen:

_Case 1.1:_
$\left\lceil\tau_{j_{2},j^{\prime}_{1}}^{\max}\right\rceil=\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}$.
Because $\bm{x}(1)\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$,
we have
$n^{C}(1)\geq\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}=n^{C}(0)$.

_Case 1.2:_
$\left\lceil\tau_{j_{2},j^{\prime}_{1}}^{\max}\right\rceil>\sum_{i=1}^{j_{1}}n_{i}^{a}+\sum_{i=1}^{j^{\prime}_{1}}n_{i}^{c}$.
Then conditions 1.a and 1.b are in force. According to 1.a, a cooperator is
earning the highest payoff, implying that no imitator will switch to
defection. According to 1.b., nonconformists of types $j_{1}+1,\ldots,j_{2}-1$
and conformists of types $j^{\prime}_{1}+1,\ldots,j^{\prime}_{2}-1$ do not
switch to defection either. The same holds with the other best-responders as
$\bm{x}(0)$ and $\bm{x}(1)$ both belong to
$\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}$. So $n^{C}(1)\geq
n^{C}(0)$ under any activation sequence, completing the proof.

###  6.3 Ordered summation of the wandering nonconformists

Inspired by [29], we expect the minimal invariant set to be a subset of the
following set:

$\displaystyle\mathcal{I}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}=\Bigg{\\{}\bm{x}\in\mathcal{X}_{j_{1},j_{2},j^{\prime}_{2},j^{\prime}_{1}}\,\big{|}\,$
$\displaystyle\forall i\in\left\\{j_{1}+1,\ldots,j_{2}-1\right\\}$ (30)
$\displaystyle\sum_{k=1}^{j^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{j_{1}}n_{k}^{a}+\sum_{k=i}^{j_{2}-1}x_{k}^{a}\leq\left\lceil\tau_{i}^{a}\right\rceil,$
(31) $\displaystyle
m+\sum_{k=1}^{j^{\prime}_{2}-1}n_{k}^{c}+\sum_{k=1}^{j_{1}}n_{k}^{a}+\\!\\!\\!\sum_{k=j_{1}+1}^{i}\\!\\!\\!x_{k}^{a}+\\!\\!\sum_{k=i+1}^{j_{2}-1}\\!\\!n_{k}^{a}\geq\left\lfloor\tau_{i}^{a}\right\rfloor\Bigg{\\}}.$

For $\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{1}$ defined in (20), (21),
(22) and (23), we show the following result.

######  Proposition 6.19.

$\mathcal{O}\subseteq\mathcal{I}_{\xi_{1},\xi_{2},\xi^{\prime}_{2},\xi^{\prime}_{1}}$.

######  Proof 6.20.

We prove by induction that for every $\bm{x}\in\mathcal{O}$, (30) holds for
all $i\in\\{\xi_{1}+1,\ldots,\xi_{2}-1\\}$.

_Step 1:_ We show (30) for $i=\xi_{2}-1$. Let $\bm{x}\in\mathcal{O}$. The
result is trivial if $x_{\xi_{2}-1}^{a}=0$ since
$\sum_{k=1}^{\xi^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{\xi_{1}}n_{k}^{a}\leq
S<\tau_{\xi_{2}-1}^{a}<\left\lceil\tau_{\xi_{2}-1}^{a}\right\rceil.$ So
consider the case where $x_{\xi_{2}-1}^{a}>0$. We prove by contradiction.
Suppose on the contrary,

(32)
$\sum_{k=1}^{\xi^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{\xi_{1}}n_{k}^{a}+x_{\xi_{2}-1}^{a}>\left\lceil\tau_{\xi_{2}-1}^{a}\right\rceil.$

Consider the initial state $\bm{x}(0)=\bm{x}$. Under an activation sequence
where the first active agent is a cooperating nonconformist of type
$\xi_{2}-1$, she will switch to defection since
$n^{C}(0)\geq\sum_{k=1}^{\xi^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{\xi_{1}}n_{k}^{a}+x_{\xi_{2}-1}^{a}(0)\overset{\eqref{supsetI:eq1}}{>}\tau_{\xi_{2}-1}^{a}$.
So $x_{\xi_{2}-1}^{a}(1)=x_{\xi_{2}-1}^{a}(0)-1$. Since
$\bm{x}(0)\in\mathcal{O}$, it holds that $\bm{x}(1)\in\mathcal{O}$, which
implies that
$n^{C}(1)\geq\sum_{k=1}^{\xi_{1}}n_{i}^{c}+\sum_{k=1}^{\xi^{\prime}_{1}}n_{i}^{a}+x_{\xi_{2}-1}^{a}(1)=\sum_{k=1}^{\xi_{1}}n_{i}^{c}+\sum_{k=1}^{\xi^{\prime}_{1}}n_{i}^{a}+x_{\xi_{2}-1}^{a}(0)-1\overset{\eqref{supsetI:eq1}}{>}\tau_{\xi_{2}-1}^{a}$.
Thus, a type-$(\xi_{2}-1)$ nonconformist will not switch from defection to
cooperation at time $2$, resulting in $x_{\xi_{2}-1}^{a}(2)\leq
x_{\xi_{2}-1}^{a}(1)<x_{\xi_{2}-1}^{a}(0)$. By induction it can be shown that
$x_{\xi_{2}-1}^{a}(t)<x_{\xi_{2}-1}^{a}(0)\forall t\geq 1$. Hence,
$\bm{x}(t)\in\mathcal{O}\backslash\\{\bm{x}\\}$ for all $t\geq 1$,
contradicting the result of Lemma 6.1.

_Step 2:_ Suppose that (30) holds for some
$i\in\\{\xi_{1}+2,\ldots,\xi_{2}-1\\}$ for every $\bm{x}\in\mathcal{O}$. We
show by contradiction that it also holds for $i-1$ for every
$\bm{x}\in\mathcal{O}$. Suppose the contrary that there exists
$\bm{x}\in\mathcal{O}$ such that

(33)
$\sum_{k=1}^{\xi^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{\xi_{1}}n_{k}^{a}+\sum_{k=i-1}^{\xi_{2}-1}x_{k}^{a}>\left\lceil\tau_{i-1}^{a}\right\rceil.$

Then $x_{i-1}^{a}>0$. Otherwise, $x_{i-1}^{a}=0$, resulting in
$\left\lceil\tau_{i-1}^{a}\right\rceil\overset{\eqref{supsetI:eq2}}{<}\sum_{k=1}^{\xi^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{\xi_{1}}n_{k}^{a}+\sum_{k=i-1}^{\xi_{2}-1}x_{k}^{a}=\sum_{k=1}^{\xi^{\prime}_{1}}n_{k}^{c}+\sum_{k=1}^{\xi_{1}}n_{k}^{a}+\sum_{k=i}^{\xi_{2}-1}x_{k}^{a}\overset{\eqref{r2l}}{\leq}\left\lceil\tau_{i+1}^{a}\right\rceil$,
which contradicts (5). Consider the initial state $\bm{x}(0)=\bm{x}$. Similar
to Step 1, it can be shown that under activation sequences where the first
active agent is a cooperating nonconformist of type $i-1$,
$\sum_{k=i-1}^{\xi_{2}-1}x_{k}^{a}(t)<\sum_{k=i-1}^{\xi_{2}-1}x_{k}^{a}(0)$
for all $t\geq 1$, which also results in a contradiction.

This completes the proof by induction for (30). Similarly, we can show that
for every $\bm{x}\in\mathcal{O}$, (31) holds for any
$i\in\\{\xi_{1}+1,\ldots,\xi_{2}-1\\}$, completing the proof.

##  7 Stochastic Stability

So far, we have studied the agents’ behavior under perfect decision makings,
which requires sufficient computational capabilities and access to the
necessary information. However, in practice, such assumptions are usually near
impossible to meet. Individuals make mistakes in their decisions or need to
experiment sub-optimal strategies in order to better understand their
environment. So the real dynamics would be subjected to some _perturbation_.
To model this perturbation we suppose rather than choosing the strategy that
is the best-response to the population or imitation of the most successful,
the active individual may choose the opposite strategy with a small
probability $\varepsilon>0$. To be more precise, let
$s^{\mathfrak{UP}}_{i}(t)$ denote agent $i$’s strategy at time $t$ under the
_unperturbed_ setting; that is, $s^{\mathfrak{UP}}_{i}(t)=s^{B}_{i}(t)$ or
$s^{I}_{i}(t)$ based on whether agent $i$ is a best-responder or an imitator.
Also, define $\bar{s}^{\mathfrak{UP}}_{i}(t)$ as the opposite strategy, i.e.,
$\\{\bar{s}^{\mathfrak{UP}}_{i}(t)\\}=\\{C,D\\}-\\{s^{\mathfrak{UP}}_{i}(t)\\}$.
Upon activation at time $t$, agent $i$ at time $t+1$ plays the random strategy
$s^{\mathfrak{P}}_{i}(t+1)$ defined by

$s^{\mathfrak{P}}_{i}(t+1)=\begin{cases}s^{\mathfrak{UP}}_{i}(t+1)&\text{if
}Z^{t}=0\\\ \bar{s}^{\mathfrak{UP}}_{i}(t+1)&\text{if }Z^{t}=1\end{cases},$

where $Z^{t}$ is a Bernoulli random variable with mean $\varepsilon$. For each
$t\in\mathbb{Z}_{\geq 0}$, $Z^{t}$ is supposed to be independent of
$Z^{0},\ldots,Z^{t-1}$ and every other happenings up to and including the time
step $t$ (the previous and current states of the system, $i^{0},\ldots,i^{t}$,
etc.).

We are interested in the long-run behavior of the population dynamics in the
presence of this type of perturbation. Under some conditions, not only the
unperturbed dynamics but also the perturbed dynamics corresponding to every
$\varepsilon>0$ can be represented by a Markov chain. When the perturbed
dynamics are aperiodic and irreducible, for each $\varepsilon$, the long-run
behavior is determined by the unique corresponding stationary distribution
$\bm{\mu}^{\varepsilon}$. The limit of these stationary distributions, as
$\varepsilon$ approaches zero, provides an approximation to
$\bm{\mu}^{\varepsilon}$ for small values of $\varepsilon$. Those states of
positive weight in this limiting distribution are considered to be
_stochastically stable_ (see [13, 17] for the first emergences of this
concept). We provide a rigorous definition of stochastic stability, that is
fully explained in terms of Markov chains and their stationary distributions
[39, 11].

######  Definition 7.1.

[Regular perturbation] Suppose that $P$ is a Markov transition matrix with a
finite state space $\mathcal{X}$, i.e., for all $\bm{x},\bm{y}\in\mathcal{X}$
and all $t\in\mathbb{Z}_{\geq 0}$, the entry $P_{\bm{x}\bm{y}}$ is the
probability of reaching $\bm{y}$ at time $t+1$, given that the state at time
$t$ is $\bm{x}$. A _regular perturbation_ of $P$ is a family of Markov
transition matrices $P^{\varepsilon}$ on $\mathcal{X}$ indexed by a parameter
$\varepsilon\in(0,\bar{\varepsilon})$ for an appropriate value of
$\bar{\varepsilon}>0$ such that

  * •

The Markov chain corresponding to each $P^{\varepsilon}$ is aperiodic and
irreducible;

  * •

$P^{\varepsilon}$ is continuous in $\varepsilon$ with $\lim_{\varepsilon\to
0}P^{\varepsilon}=P$;

  * •

there exists a _cost function_
$c_{\mathcal{X}}:\mathcal{X}\times\mathcal{X}\to[0,+\infty]$ such that for all
pairs of states $\bm{x},\bm{y}\in\mathcal{X}$,

$\lim_{\varepsilon\to
0}P_{\bm{x}\bm{y}}^{\varepsilon}/\varepsilon^{c_{\mathcal{X}}(\bm{x},\bm{y})}$

exists and is strictly positive if $c_{\mathcal{X}}(\bm{x},\bm{y})<\infty$
(with $P_{\bm{x}\bm{y}}^{\varepsilon}=0$ for sufficiently small $\varepsilon$
if $c_{\mathcal{X}}(\bm{x},\bm{y})=\infty$).

We remind that $P_{\bm{x}\bm{y}}^{\varepsilon}$ is the probability of reaching
$\bm{y}$ from $\bm{x}$ in one step under the perturbed Markov chain
$P^{\varepsilon}$. So for each $\bm{x},\bm{y}\in\mathcal{X}$, the value of
$c_{\mathcal{X}}(\bm{x},\bm{y})$ shows how “unlikely” is the one-step
transition from $\bm{x}$ to $\bm{y}$ under $P^{\varepsilon}$ for small values
of $\varepsilon$, i.e., higher cost values imply more unlikely one-step
transitions.

Since the Markov chain corresponding to each $P^{\varepsilon}$ is aperiodic
and irreducible, there exists a unique _probability vector_
$\bm{\mu}^{\varepsilon}$, i.e., a vector with non-negative components that sum
to 1, which is the stationary distribution for $P^{\varepsilon}$. By
definition, we have
$\bm{\mu}^{\varepsilon}P^{\varepsilon}=\bm{\mu}^{\varepsilon}$. Indeed, the
vector $\bm{\mu}^{\varepsilon}$ determines the long-run distribution of the
chain independently of its initial distribution, i.e., for every initial
probability distribution $\bm{\bar{\mu}}$,
$\lim_{t\to+\infty}\bm{\bar{\mu}}(P^{\varepsilon})^{t}=\bm{\mu}^{\varepsilon}$.
By the continuity assumption of $P^{\varepsilon}$, we can define

$\displaystyle\bm{\mu}^{*}=\lim_{\varepsilon\to 0}\bm{\mu}^{\varepsilon}.$

Then $\bm{\mu}^{*}$ is a probability vector and is used to define the
stochastically stable states as follows.

######  Definition 7.2.

[Stochastic stability] Consider $P^{\varepsilon}$ as a regular perturbation of
$P$. A state $\bm{x}\in\mathcal{X}$ is _stochastically stable_ if
$\bm{\mu}^{*}(\bm{x})>0$. A non-empty subset of $\mathcal{X}$ is called
_stochastically stable_ if its members are all stochastically stable. The set
of all stochastically stable states is called _the maximal stochastically
stable set_.

Since $\mathcal{X}$ is assumed to be finite, the maximal stochastically stable
set is non-empty. Moreover, it is known that this set is a union of the
_recurrent classes_ of the Markov chain corresponding to $P$ [39, Theorem 4].
Note that a recurrent class of a Markov chain with finite state space
$\mathcal{X}$ is a non-empty subset $\Omega$ of $\mathcal{X}$ such that: 1)
starting from $\Omega$, the chain stays there forever with probability $1$; 2)
for any $\bm{x},\bm{y}\in\Omega$ there exists a path of positive probability
from $\bm{x}$ to $\bm{y}$. Hence, the family of recurrent classes of $P$ is
the same as the family of minimal invariant sets of the dynamics represented
by $P$.

###  7.1 Mixed binary-type populations: set-up

Inspired by the strong condition necessary for a mixed equilibrium to be
stable (Section 5), we would like to investigate the problem of whether mixed
or extreme equilibria are “more likely” to be stochastically stable. We focus
on _mixed binary-type populations_ , i.e., populations consisting of two
types: a conformist type and an nonconformist type, with some imitators from
each type. We name those imitators with the same payoff matrix as that of the
nonconformists (resp. conformists), the _anticoordinating imitators_ (resp.
_coordinating imitators_). In order to fulfill the assumptions of Definition
7.1, we need to modify the model described in Section 2.

Let $m^{a}$ and $m^{c}$ represent respectively the total number of
anticoordinating and coordinating imitators. Same as before, $n^{a}$ and
$n^{c}$ are respectively the total number of nonconformists, and conformists.
Define

$m=m^{a}+m^{c}\qquad\text{and}\qquad n=m^{a}+n^{a}+m^{c}+n^{c},$

and assume $m^{a},n^{a},m^{c},n^{c}\geq 1$. The tempers of the nonconformists
and conformists are respectively non-integer values $\tau^{a}$, and
$\tau^{c}$. The population state is represented by the frequency of
cooperating agents in each of the four subpopulations, i.e, anticoordinating
imitators, nonconformists, coordinating imitators, and conformists:

$\bm{x}=(x_{1}^{I},x^{a},x_{2}^{I},x^{c}).$

Unlike the setting in Section 2, here we use this different representation
that includes anticoordinating and coordinating imitators separately since we
need the population dynamics to be described as a Markov chain on the state
space $\mathcal{X}$. More specifically, it is necessary that for any two
states $\bm{x}$ and $\bm{y}$, the probability of transition form $\bm{x}$ to
$\bm{y}$ depends only on these states. Consider, for instance, arbitrary
$m^{a}$, $n^{a}$, $m^{c}$, and $n^{c}$ such that $m^{a}=m^{c}$. The
probability of transition from $(m^{a},n^{a},0,n^{c})$ to
$(m^{a},n^{a},1,n^{c})$ might be different from the probability of transition
from $(0,n^{a},m^{c},n^{c})$ to $(1,n^{a},m^{c},n^{c})$, for the active
utility lines at $(m^{a},n^{a},0,n^{c})$ and $(0,n^{a},m^{c},n^{c})$ are not
the same. However, both states have the same number of cooperating imitators.
This is also the case for the destination states $(m^{a},n^{a},1,n^{c})$ and
$(1,n^{a},m^{c},n^{c})$. Hence, distinguishing the imitators in the state is
required for having a Markov chain.

On the other hand, the Markov property together with the necessity of
irreducibility in the perturbed case imposes some constraints on the
activation sequence. The transition probabilities must depend only on the
source and destination states, and this dependency may not change over time.
Moreover, in the perturbed dynamics, every state must be accessible from any
other state through a path of positive probability. So we impose the following
assumption.

Suppose that for $t\in\mathbb{Z}_{\geq 0}$, the random variable $I^{t}$
represents the active agent at time $t$. The $i^{t}$ in Section 2 will then be
a realization of $I^{t}$. We assume $I^{0},I^{1},\ldots$ are independent and
identically distributed according to a positive probability vector
$p=(p_{1},\ldots,p_{n})$, i.e., for $i\in\\{1,\ldots,n\\}$ and
$t\in\mathbb{Z}_{\geq 0}$, $\mathbb{P}[I^{t}=i]=p_{i}>0$. Moreover, inside
each subpopulation, $p$ is constant; that is, $p_{i}$ is the same for all
agents $i$ that are conformists, as it is the same for all nonconformists, for
all coordinating imitators, and for all anticoordinating imitators.

Note that the positivity assumption guaranties the irreducibility necessary
for the perturbed dynamics, and assuming the “uniformity” inside
subpopulations is necessary for the Markov property.

For the explained regular perturbation, the cost function $c_{\mathcal{X}}$ is
zero exactly for those $(\bm{x},\bm{y})$ that $\bm{y}$ can be obtained from
$\bm{x}$ in one step without trembling, i.e., when $P_{\bm{x}\bm{y}}>0$ .
Moreover, $c_{\mathcal{X}}(\bm{x},\bm{y})=1$ when exactly one mistake is
needed to go from $\bm{x}$ to $\bm{y}$ in one step, i.e., for those
$(\bm{x},\bm{y})$ that $P_{\bm{x}\bm{y}}=0$ and
$P_{\bm{x}\bm{y}}^{\varepsilon}>0$ when $\varepsilon$ is small enough.
Otherwise, $c_{\mathcal{X}}(\bm{x},\bm{y})=+\infty$.

In the next subsection, we review some related notions and results we need.
For a more comprehensive reading including richer results on identifying
stochastically stable states, we refer the reader to [39, 11, 31].

###  7.2 Preliminaries

In this subsection, we abstract away the game-theoretic details, and only
focus on the ongoing dynamics, represented as Markov chains. As noted before,
it is proved in [39, Theorem 4] that the maximal stochastically stable set of
a regular perturbation of a Markov transition matrix $P$ is a non-empty union
of the recurrent classes of $P$. Intuitively, a stochastically stable
recurrent class can be reached relatively quickly from outside the class, and
the chain leaves the class with a relatively small probability. This intuition
can be rigorously explained using the cost function in Definition 7.1. Note
that transitions between different states can occur trough paths of longer
lengths, while the function $c_{\mathcal{X}}$ only describes the chance of
one-step transitions. Using this function, we define an optimal path between
any two states, or more generally, any two non-empty sets. For non-empty
subsets $\mathcal{U},\mathcal{V}\subseteq\mathcal{X}$, a _path_ from
$\mathcal{U}$ to $\mathcal{V}$ in $\mathcal{X}$ is an ordered finite tuple
$(\bm{z}_{1},\bm{z}_{2},\ldots,\bm{z}_{T})$ of distinct states of
$\mathcal{X}$, where $\bm{z}_{1}\in\mathcal{U}$, $\bm{z}_{T}\in\mathcal{V}$,
and $\bm{z}_{t}\not\in\mathcal{V}$ for $2\leq t\leq T-1$. To any path
$(\bm{z}_{1},\bm{z}_{2},\ldots,\bm{z}_{T})$, assign the _cost_ value

$\displaystyle
c(\bm{z}_{1},\bm{z}_{2},\ldots,\bm{z}_{T})=\sum_{i=1}^{T-1}c_{\mathcal{X}}(\bm{z}_{i},\bm{z}_{i+1}),$

and define the _transition cost_ from $\mathcal{U}$ to $\mathcal{V}$, denoted
by $c(\mathcal{U},\mathcal{V})$, to be the minimum cost of a path from
$\mathcal{U}$ to $\mathcal{V}$:

(34) $\displaystyle
c(\mathcal{U},\mathcal{V})=\min_{(\bm{z}_{1},\ldots,\bm{z}_{T})\in\Pi(\mathcal{U},\mathcal{V})}c(\bm{z}_{1},\ldots,\bm{z}_{T}),$

where $\Pi(\mathcal{U},\mathcal{V})$ is the set of all paths from
$\mathcal{U}$ to $\mathcal{V}$ in $\mathcal{X}$. By irreducibility of
$P^{\varepsilon}$s, there exist paths of positive probability and finite
length from an arbitrary state to any other state in the dynamics. Hence,
$c(\mathcal{U},\mathcal{V})$ is finite for non-empty $\mathcal{U}$ and
$\mathcal{V}$. In what follows, we use states instead of singletons for
convenience, e.g., $c(\bm{x},\bm{y})$, that should not be confused with
$c_{\mathcal{X}}(\bm{x},\bm{y})$, and $\Pi(\bm{x},\mathcal{U})$ are used
respectively in place of $c(\\{\bm{x}\\},\\{\bm{y}\\})$ and
$\Pi(\\{\bm{x}\\},\mathcal{U})$.

######  Remark 7.3.

Note that in the mixed binary-type population dynamics, for any non-empty
$\mathcal{U},\mathcal{V}\subseteq\mathcal{X}$, the cost function
$c(\mathcal{U},\mathcal{V})$ is the minimum number of mistakes necessary to
have a transition from an element of $\mathcal{U}$ to an element of
$\mathcal{V}$.

Using (34), we define a complete weighted digraph
$\mathcal{G}(P^{\varepsilon})$, with the vertex set consisting of all
recurrent classes of $P$, denoted by $\Omega_{1},\ldots,\Omega_{k}$. For
$i\neq j$, we assign the weight $c(\Omega_{i},\Omega_{j})$ to the edge
$\Omega_{i}\longrightarrow\Omega_{j}$. For a recurrent class $\Omega$, by an
_$\Omega$ -tree_ we mean a spanning subtree of $\mathcal{G}(P^{\varepsilon})$
rooted in $\Omega$.

######  Definition 7.4.

For the regular perturbation $P^{\varepsilon}$ of $P$, suppose $\Omega$ is a
recurrent class of $P$. An _$\Omega$ -tree_ is a spanning subtree of
$\mathcal{G}(P^{\varepsilon})$ such that for any recurrent class
$\Omega^{\prime}\neq\Omega$, there is a unique directed path in this subtree
from $\Omega^{\prime}$ to $\Omega$.

Denote the set of all $\Omega$-trees for a given $\Omega$ by
$\mathcal{T}_{\Omega}$, and define $\gamma(\Omega)$ as the minimum (additive)
weight among all elements of $\mathcal{T}_{\Omega}$; that is,

(35)
$\displaystyle\gamma(\Omega)=\min_{\tau\in\mathcal{T}_{\Omega}}\sum_{\Omega_{i}\to\Omega_{j}\in\tau}c(\Omega_{i},\Omega_{j}).$

The following has been proven in [39].

######  Proposition 7.5.

Consider the regular perturbation $P^{\varepsilon}$ and let
$\Omega_{1},\ldots,\Omega_{k}$ be the recurrent classes of $P$. A recurrent
class $\Omega$ is stochastically stable if and only if

$\displaystyle\Omega\in\operatorname*{arg\,min}_{\Omega_{j}\in\\{\Omega_{1},\ldots,\Omega_{k}\\}}\gamma(\Omega_{j}).$

Proposition 7.5 can be utilized to identify the maximal stochastically stable
set. However, since the number of rooted spanning subtrees of
$\mathcal{G}(P^{\varepsilon})$ grows exponentially with the number of
recurrent classes, more efficient methods than finding a minimum $\Omega$-tree
for every recurrent class $\Omega$ are needed. In [11], Ellison defines other
quantities helpful in finding stochastically stable sets. One is the _radius_
of a recurrent class $\Omega$, which is a measure of the “persistence” of
$\Omega$ once reached.

######  Definition 7.6.

Suppose $\Omega$ is a recurrent class of a Markov chain on $\mathcal{X}$ with
transition matrix $P$. The _basin of attraction_ of $\Omega$ is the set of
initial states from which the Markov chain reaches $\Omega$ with probability
one, i.e.,

$\mathcal{D}(\Omega)=\left\\{\bm{x}\in\mathcal{X}:\mathbb{P}[\exists
T\in\mathbb{N}\ \bm{x}(T)\in\Omega|\bm{x}(0)=\bm{x}]=1\right\\},$

where $\bm{x}(t)$ denotes the state of the chain at time $t\in\mathbb{Z}_{\geq
0}$. For the regular perturbation $P^{\varepsilon}$ of $P$, the _radius_ of
the basin of attraction of $\Omega$, i.e., $R(\Omega)$, is the _cost of
leaving_ $\mathcal{D}(\Omega)$ starting from $\Omega$; that is,

$\displaystyle R(\Omega)=c(\Omega,\mathcal{X}\setminus\mathcal{D}(\Omega)).$

The following lemma, that will be proved in Appendix A, is based on [11,
Theorem 3].

######  Lemma 7.7.

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$.

###  7.3 Mixed binary-type populations: results

Since this work is focused on comparing the stochastic stability of mixed and
extreme equilibria of mixed binary-type populations described in Section 7.1,
we first characterize the general forms of equilibrium points of this model.
Same as before, we call an equilibrium mixed if the number of its cooperating
imitators belongs to $\\{1,\ldots,m-1\\}$. Other equilibria are called
extremes. According to Lemma 4.6, any mixed equilibrium takes either of the
forms $(x_{1}^{I},n^{a},x_{2}^{I},0)$ where

$C^{a}(x_{1}^{I}+n^{a}+x_{2}^{I})=D^{c}(x_{1}^{I}+n^{a}+x_{2}^{I}),$

or $(x_{1}^{I},0,x_{2}^{I},n^{c})$ where

$C^{c}(x_{1}^{I}+x_{2}^{I}+n^{c})=D^{a}(x_{1}^{I}+x_{2}^{I}+n^{c}).$

As a result, there exists at most two distinct values of
$r\in\\{1,\ldots,m-1\\}$ that correspond to the frequency of cooperating
imitators at a mixed equilibrium. Note that the multiplicity of mixed
equilibria with a specific number of cooperating imitators is either zero or
at least two. If, say, $(x_{1}^{I},n^{a},x_{2}^{I},0)$ is a mixed equilibrium
and $x_{1}^{I}+x_{2}^{I}=r$, then any state $(z_{1}^{I},n^{a},z_{2}^{I},0)$,
where $z_{1}^{I}+z_{2}^{I}=r$, $z_{1}^{I}\in\\{0,\ldots,m^{a}\\}$, and
$z_{2}^{I}\in\\{0,\ldots,m^{c}\\}$ is a mixed equilibrium. We call these mixed
equilibria _congruent_. The situation is similar with mixed equilibria of type
$(x_{1}^{I},0,x_{2}^{I},n^{c})$. According to Lemmas 4.3 and 4.5, every
extreme equilibrium takes one of the forms $(0,0,0,0)$, $(0,n^{a},0,0)$,
$(m^{a},n^{a},m^{c},0)$, $(0,0,0,n^{c})$, $(m^{a},0,m^{c},n^{c})$, or
$(m^{a},n^{a},m^{c},n^{c})$, depending on the parameters of the population and
utility functions.

We will show that the stochastic stability of a mixed equilibrium transmits to
that of its “neighboring” extreme equilibrium defined as follows.

######  Definition 7.8.

Given the mixed equilibrium $(x_{1}^{I},n^{a},x_{2}^{I},0)$ (resp.
$(x_{1}^{I},0,x_{2}^{I},n^{c})$), we define its corresponding extreme state as
$(0,n^{a},0,0)$ (resp. $(m^{a},0,m^{c},n^{c})$).

Depending on the dominant utility functions around a mixed equilibrium, its
corresponding extreme state may be an equilibrium. If this is the case,
Theorem 7.9 states that the stochastic stability of the mixed equilibrium
implies the stochastic stability of its corresponding extreme state. In Fig. 3
the utility lines in dynamics with non-congruent mixed equilibria are
depicted. In this figure, it is supposed that the corresponding extreme state
of each mixed equilibrium is an equilibrium. The position of utility lines
around each mixed equilibrium is the same as what is shown in Fig. 3 even if
we relax the constraint of the existence of the other non-congruent mixed
equilibrium. Note that $\tau^{a}\neq\tau^{c}$ and $0<\tau^{a},\tau^{c}<n$
necessarily hold in such dynamics.

(a) $0<\tau^{a}<\tau^{c}<n$

(b) $\bm{0<\tau^{c}<\tau^{a}<n}$

Figure 3: Utility lines of population dynamics with two mixed equilibria that
their extreme states are equilibrium points.

######  Theorem 7.9.

Consider the unperturbed dynamics of a mixed binary-type population and the
described regular perturbation. Suppose that in the unperturbed dynamics, the
corresponding extreme state of each mixed equilibrium is an equilibrium. Then
the set of stochastically stable equilibria is either empty or includes an
extreme equilibrium.

######  Proof 7.10.

The result is trivial should the dynamics be empty of equilibrium. Assume that
there exists a mixed equilibrium $\bm{x}$. According to the assumptions, its
corresponding extreme state $\bm{y}$ is an extreme equilibrium. Since
$\\{\bm{y}\\}$ is an invariant set (a recurrent class) of the unperturbed
dynamics, the Markov chain may not leave it unless an agent makes a mistake,
resulting in $R(\bm{y})\geq 1$. We prove that $c(\bm{x},\bm{y})=1$, and thus,

$\displaystyle R(\bm{y})\geq c(\bm{x},\bm{y}).$

Then by means of Lemma 7.7, we conclude that either $\bm{x}$ is not
stochastically stable, or both $\bm{x}$ and $\bm{y}$ are.

Note that since $\bm{x}$ is an equilibrium, $c(\bm{x},\bm{y})\geq 1$. So to
show $c(\bm{x},\bm{y})=1$, it suffices to introduce a path of cost $1$ from
$\bm{x}$ to $\bm{y}$.

_Case 1:_ $\bm{x}=(x_{1}^{I},n^{a},x_{2}^{I},0)$, and hence,
$\bm{y}=(0,n^{a},0,0)$. Since $r=x_{1}^{I}+x_{2}^{I}\geq 1$, without loss of
generality assume that $x_{1}^{I}\geq 1$. A mistake by an active
anticoordinating imitator who is cooperating, leads to the state
$(x_{1}^{I}-1,n^{a},x_{2}^{I},0)$. Since $C^{a}(r+n^{a})=D^{c}(r+n^{a})$, and
$\bm{y}$ is an equilibrium, $D^{c}$ is the dominant utility line at all states
in the form of $(z_{1}^{I},n^{a},z_{2}^{I},0)$ with $0\leq
z_{1}^{I}+z_{2}^{I}\leq r-1$ (Fig. 3). Therefore, there is a costless path
from $(x_{1}^{I}-1,n^{a},x_{2}^{I},0)$ to $\bm{y}$, which can be obtained by
activating cooperating imitators successively. So the total cost of the given
path from $\bm{x}$ to $\bm{y}$ is one.

_Case 2:_ $\bm{x}=(x_{2}^{I},0,x_{2}^{I},n^{c})$, and hence,
$\bm{y}=(m^{a},0,m^{c},n^{c})$. Since $r=x_{1}^{I}+x_{2}^{I}\leq m-1$, we
assume without loss of generality that $x_{I}^{I}\leq m^{a}-1$. A mistake by
an active anticoordinating imitator which is defecting, changes the state of
the system to $(x_{1}^{I}+1,0,x_{2}^{I},n^{c})$.
$C^{c}(r+n^{c})=D^{a}(r+n^{c})$, and at $\bm{y}$ the dominant utility function
is $C^{c}$. Therefore, at all states in form of
$(z_{1}^{I},0,z_{2}^{I},n^{c})$, with $r+1\leq z_{1}^{I}+z_{2}^{I}\leq m$,
$C^{c}$ is the dominant utility line (Fig. 3). Hence, there exists a costless
path from $(x_{1}^{I}+1,0,x_{2}^{I},n^{c})$ to $\bm{y}$, which can be obtained
by activating defecting imitators one after another. So we have a path of cost
$1$ from $\bm{x}$ to $\bm{y}$.

######  Corollary 7.11.

Suppose that the mixed binary-type population dynamics admit the extreme
equilibria $(0,n^{a},0,0)$ and $(m^{a},0,m^{c},n^{c})$. Then, the maximal
stochastically stable set of the corresponding regular perturbation is a non-
empty union of the non-singleton minimal invariant sets of the unperturbed
dynamics or includes an extreme equilibrium.

######  Proof 7.12.

By assumption, the corresponding extreme state of each mixed equilibrium of
the population dynamics is an equilibrium. If the maximal stochastically
stable set is empty of equilibria, it is a non-empty union of the non-
singleton minimal invariant sets of the unperturbed dynamics. Otherwise, by
Theorem 7.9, at least one of the extreme equilibria is stochastically stable.

######  Remark 7.13.

Some facts justify our choices in Definition 7.8 for assigning an extreme
state to each mixed equilibrium. For instance, $(0,0,0,0)$ and
$(m^{a},n^{a},m^{c},n^{c})$ are not “in the neighborhood” of any mixed
equilibrium. Moreover, assuming that $(x_{1}^{I},n^{a},x_{2}^{I},0)$ is a
mixed equilibrium, if $(m^{a},n^{a},m^{c},0)$ is an extreme equilibrium, then
so is $(0,n^{a},0,0)$ (Fig. 3). Hence, assigning $(m^{a},n^{a},m^{c},0)$ to
$(x_{1}^{I},n^{a},x_{2}^{I},0)$ as its corresponding extreme state would yield
a weaker result compared to Theorem 7.9.

####  7.3.1 Examples

The following three examples illustrate some of the possible configurations of
the maximal stochastically stable set for mixed binary-type population
dynamics satisfying the assumptions of Theorem 7.9.

######  Example 7.14.

_[A single extreme equilibrium]_ Assume that
$({\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}1},{\color[rgb]{0,0,1}5})$,
and the payoff matrices are set so that the utility functions are the
followings:

$\displaystyle C^{a}(n^{C})=-2n^{C}+\frac{51}{5},$ $\displaystyle
D^{a}(n^{C})=5n^{C}-\frac{37}{2};$ $\displaystyle
C^{c}(n^{C})=\frac{33}{5}n^{C}-\frac{297}{10},$ $\displaystyle
D^{c}(n^{C})=-\frac{14}{5}n^{C}+\frac{63}{5}.$

Hence, 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.1},{\color[rgb]{0,0,1}4.5})$,
and it can be shown that the system has the eight equilibria

$\displaystyle({\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}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}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}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0}),$
$\displaystyle({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}5}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}5}),$

and no non-singleton minimal invariant set. From Theorem 7.9 and the fact that
the maximal stochastically stable set is nonempty, we know that at least one
of
$({\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}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})$
must be stochastically stable. We claim that
$({\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})$
is the only stochastically stable state.

Figure 4: Costs of some shortest paths between equilibrium points of the
system in Example 7.14.

Fig. 4 shows a weighted digraph that is a subgraph of
$\mathcal{G}(P^{\varepsilon})$, introduced in Section 7.2. Note that
$\bm{x}\stackrel{{\scriptstyle c}}{{\longleftrightarrow}}\bm{y}$ represents
$\bm{x}\stackrel{{\scriptstyle c}}{{\longrightarrow}}\bm{y}$ and
$\bm{y}\stackrel{{\scriptstyle c}}{{\longrightarrow}}\bm{x}$ simultaneously.
To verify
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})\stackrel{{\scriptstyle
1}}{{\longrightarrow}}({\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})$,
consider the following path:

$\displaystyle({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})\stackrel{{\scriptstyle
1}}{{\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})\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}3})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0}$
$\displaystyle,{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}2})$
$\displaystyle\downarrow{\scriptstyle{0}}$
$\displaystyle({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0}$
$\displaystyle,{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}1})\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}0})\stackrel{{\scriptstyle
0}}{{\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}).$

Numbers on top of or next to arrows denote the cost of the corresponding
transition. The first transition needs exactly one mistake by an active
conformist. Therefore,

$\displaystyle
c(({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5}),({\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}))=1.$

Other costs in Fig. 4 are straightforward to calculate.

We show that
$R(({\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}))>1$.
Indeed, setting
$\bm{x}=({\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})$,
we show that for a state $\bm{y}$, if $c(\bm{x},\bm{y})=1$, then
$\bm{y}\in\mathcal{D}(\bm{x})$. So starting from $\bm{x}$, more than one
tremble is needed to leave $\mathcal{D}(\bm{x})$. Suppose there is a path of
cost $1$ from $\bm{x}$ to a state $\bm{y}$. 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 must be costless.
Therefore, the second state would be one of the following points:

$({\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}),({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0}),({\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}),({\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}).$

It is straightforward to see that each of these states and consequently
$\bm{y}$ belong to $\mathcal{D}(\bm{x})$ (for instance, activation of any
agent 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}0})$
leads to either the same state or $\bm{x}$ under the unperturbed dynamics).
Now, by Lemma 7.7,
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})$
is not stochastically stable, since

$\displaystyle
R(({\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}))>c(({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5}),({\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})).$

Moreover, the weighted edge
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})\stackrel{{\scriptstyle
1}}{{\longrightarrow}}({\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})$
implies
$R(({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5}))\leq
1$. But it is impossible to leave an equilibrium without bearing a positive
cost. Hence,
$R(({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5}))=1$.
So, by Lemma 7.7, stochastic stability of
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}5})$
results in stochastic stability of
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})$,
which we rejected earlier. Thus
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}5})$
is not stochastically stable.

Similar arguments show that neither of
$({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}5})$,
$({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}5})$,
$({\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}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})$,
nor
$({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})$
is stochastically stable. Since the maximal stochastically stable set is non-
empty, its only element is
$({\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})$.

######  Example 7.15.

_[No equilibria]_ Suppose
$({\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})$,
and the utility functions are as follows:

$\displaystyle C^{a}(n^{C})=6,$ $\displaystyle
D^{a}(n^{C})=3n^{C}-\frac{81}{10};$ $\displaystyle C^{c}(n^{C})=20n^{C}-122,$
$\displaystyle D^{c}(n^{C})=-\frac{60}{41}n^{C}+\frac{366}{41}.$

It follows that
$({\color[rgb]{0,0.88,0}\tau^{a}},{\color[rgb]{0,0,1}\tau^{c}})=({\color[rgb]{0,0.88,0}4.7},{\color[rgb]{0,0,1}6.1})$.
All equilibrium states of the dynamics together with its only non-singleton
minimal invariant set, $\Omega$, are shown in Fig. 5. We show that
$R(\Omega)>1$. By Lemma 7.7, this inequality in addition to the given costs in
Fig. 5, implies that the maximal stochastically stable set is

$\displaystyle\Omega=\left\\{({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0})\right\\}.$

Figure 5: Costs of some shortest paths between minimal invariant sets of the
population dynamics of Example 7.15.

It is straightforward to show that

$\displaystyle\mathcal{D}(\Omega)=$
$\displaystyle\left\\{({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\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}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0}),\right.$
$\displaystyle\ \
({\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}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}0}),({\color[rgb]{1,0,0}2},{\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}1},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}1}),$
$\displaystyle\ \
\\!\\!\left.({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}0},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}1}),({\color[rgb]{1,0,0}2},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}1})\right\\},$

and that

$\displaystyle\\{\bm{x}:c(\Omega,\bm{x})=1\\}=$ $\displaystyle\
\mathcal{D}(\Omega)\setminus\Omega$ $\displaystyle\subseteq$ $\displaystyle\
\mathcal{D}(\Omega).$

Hence, $R(\Omega)>1$.

######  Example 7.16.

_[Union of all minimal invariant sets]_ Suppose
$({\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}1},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}4})$,
and the utility functions are

$\displaystyle C^{a}(n^{C})=-n^{C}+\frac{109}{10},$ $\displaystyle
D^{a}(n^{C})=3n^{C}-\frac{87}{10};$ $\displaystyle
C^{c}(n^{C})=\frac{105}{31}n^{C}-\frac{693}{62},$ $\displaystyle
D^{c}(n^{C})=-\frac{79}{3}n^{C}+\frac{869}{10}.$

As a result, we have
$({\color[rgb]{0,0.88,0}\tau^{a}},{\color[rgb]{0,0,1}\tau^{c}})=({\color[rgb]{0,0.88,0}4.9},{\color[rgb]{0,0,1}3.3})$.
All equilibria of the dynamics and its unique minimal invariant set of
multiple elements, $\Omega$, are depicted in Fig. 6.

Figure 6: Costs of some shortest paths between minimal invariant sets of the
population dynamics of Example 7.16.

We prove that the maximal stochastically stable set is the union of all five
minimal invariant sets. Indeed, assuming the costs in Fig. 6 and by multiple
usage of Lemma 7.7, we deduce that stochastic stability of each minimal
invariant set results in the stochastic stability of the other four sets. For
instance, if
$({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$
is stochastically stable, then so is each of the two mixed equilibria. By
$({\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}}{{\longrightarrow}}\Omega$, we have
$R(({\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}))=1$.
So because of the edge
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})\stackrel{{\scriptstyle
1}}{{\longrightarrow}}({\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})$,
stochastic stability of
$({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})$
yields stochastic stability of
$({\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})$,
which in turn, by a similar argument yields stochastic stability of $\Omega$.

Finally, we provide some minimum cost paths corresponding to the less trivial
costs in Fig. 6:

$\displaystyle
c(({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0}),\Omega)=1:\hskip
113.81102pt$
$\displaystyle({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}0})\stackrel{{\scriptstyle
1}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}1})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}2})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2}$
$\displaystyle,{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}3})$
$\displaystyle\downarrow{\\!\scriptstyle 0}$
$\displaystyle({\color[rgb]{1,0,0}0},{\color[rgb]{0,0.88,0}2}$
$\displaystyle,{\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}1},{\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}1},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}4})\in\Omega.$

$\displaystyle
c(({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2},{\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}2},{\color[rgb]{0,0,1}4}))=1:\hskip
91.04872pt$
$\displaystyle({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}0})\stackrel{{\scriptstyle
1}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}1})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2},{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}2})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2}$
$\displaystyle,{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}3})$
$\displaystyle\downarrow{\\!\scriptstyle 0}$
$\displaystyle({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2}$
$\displaystyle,{\color[rgb]{1,0,0}0},{\color[rgb]{0,0,1}4})$
$\displaystyle\downarrow{\\!\scriptstyle 0}$
$\displaystyle({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2}$
$\displaystyle,{\color[rgb]{1,0,0}1},{\color[rgb]{0,0,1}4})$
$\displaystyle\downarrow{\\!\scriptstyle 0}$
$\displaystyle({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}2}$
$\displaystyle,{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}4})\stackrel{{\scriptstyle
0}}{{\to}}({\color[rgb]{1,0,0}1},{\color[rgb]{0,0.88,0}1},{\color[rgb]{1,0,0}2},{\color[rgb]{0,0,1}4})\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}4}).$