# Equilibration of Coordinating Imitation and Best-Response Dynamics

Nazanin Hasheminejad and Pouria Ramazi

###### Abstract

Decision-making individuals are often considered to be either _imitators_ who
copy the action of their most successful neighbors or _best-responders_ who
maximize their benefit against the current actions of their neighbors. In the
context of _coordination games_ , where neighboring individuals earn more if
they take the same action, by means of potential functions, it was shown that
populations of all imitators and populations of all best-responders
equilibrate in finite time when they become active to update their decisions
sequentially. However, for mixed populations of the two, the equilibration was
shown only for specific activation sequences. It is therefore, unknown,
whether a potential function also exists for mixed populations or if there
actually exists a counter example where an activation sequence prevents
equilibration. We show that in a _linear graph_ , the number of “sections” (a
sequence of consecutive individuals taking the same action) serves as a
potential function, leading to equilibration, and that this result can be
extended to _sparse trees_. The existence of a potential function for other
types of networks remains an open problem.

_Keywords._ Decision making, best-response, imitation, coordination game,
convergence.

##  1 Introduction

Evolutionary game theory has been successfully applied in different
applications ranging from cancer and epidemiology to finance and rumour
propagation [1, 2, 3, 4]. In the context of decision-making, individuals are
modeled as game-playing agents who choose from a number of available
strategies and accordingly earn payoffs against their matched opponents. The
agents revise their decisions according to some update rules, the most common
being _(myopic) best-response_ and _imitation_. An agent following best-
response, called a _best-responder_ , chooses the strategy that maximizes its
payoff against its neighbors given that they would not change their
strategies. On the other hand, an agent following imitation, known as an
_imitator_ , simply imitates a neighbor with a higher payoff. The wide use of
best response by human has been confirmed in experimental studies [5].
Similarly, imitation behavior emerges in several real-world scenarios, such as
employees’ “costumer sweethearting” [6], building cultural intelligence [7],
and training language models [8].

Researchers have explored the existence and convergence towards an equilibrium
point in both imitation and best-response dynamics [9, 10, 11, 12]. In the
anti-coordination context where the highest-earning decision is the opposite
of the opponent’s, a population of best-responders converges to an equilibrium
state [13]. The same holds for a population of best-responders in the
coordination context, where the highest-earning strategy matches the
opponent’s [13, 14]. For populations of imitators, however, equilibration is
guaranteed only in the coordination context [15, Theorem 1]. All of these
studies used a potential function to prove equilibrium convergence. Clearly, a
mixed population of imitators and best-responders may not equilibrate and
undergo perpetual fluctuations. The outcome is known for the anti-coordination
case: equilibration can take place if and only if there exists an equilibrium
[16]. What about a mixed population of imitators and best-responders in the
coordination context? The existence of an activation sequence was established
in [17] that would drive any such mixed population to an equilibrium state. It
however remains open whether a potential function exists for such populations,
or if there is a counter example where an activation sequence can prevent a
mixed population from equilibration.

We start tackling this problem for the simple _linear graph_ and find that the
number of the so-called “sections” (consecutive same-strategy playing agents)
serves as a potential function. We then extend the results to a ring. Next, we
proceed to a _starlike_ graph, a central “branching node” connected to several
linear graphs or “branches”. We show that there always exists a branch where
the number of sections in that branch will again be a potential function,
establishing equilibration. Finally, we generalize the idea to _sparse trees_
, i.e., trees where the distance between each two branching nodes is at least
three.

##  2 Model

Consider an undirected network $\mathcal{G}$ over a finite set
$\mathcal{N}=\\{1,2,\ldots,n\\}$ of agents who decide between strategies
$\mathtt{A}$ and $\mathtt{B}$ over time $t=0,1,2,\ldots$. For each agent
$i\in\mathcal{N}$, the network defines a set of _neighbors_
$\mathcal{N}_{i}\subseteq\mathcal{N}\setminus\\{i\\}$ that are connected to
agent $i$. At every time step, each agent $i\in\mathcal{N}$ plays a two-player
_(row-column) coordination game_ with each of its neighbors
$j\in\mathcal{N}_{i}$ and earns a payoff according to their strategies and its
payoff matrix

$\bm{\pi}^{i}=\begin{bmatrix}R_{i}&S_{i}\\\ T_{i}&P_{i}\end{bmatrix},\
\min\\{R_{i},P_{i}\\}>\max\\{T_{i},S_{i}\\}$ (1)

where $R_{i},S_{i},T_{i}$, and $P_{i}$ are agent $i$’s payoffs when agents $i$
and $j$ play strategy pairs $(\mathtt{A},\mathtt{A})$,
$(\mathtt{A},\mathtt{B})$, $(\mathtt{B},\mathtt{A})$, and
$(\mathtt{B},\mathtt{B})$. Then agent $i$’s _utility_ $u_{i}$ is the
accumulated payoff earned against all of its neighbors:
$u_{i}(\bm{x})=\sum_{j\in\mathcal{N}_{i}}\bm{\pi}^{i}_{x_{i},x_{j}}$ where
$x_{k}$ is the strategy of agent $k$, the _state_ $\bm{x}=[x_{k}]$ is the
vector of all agents’ strategies, and $\bm{X}_{pq}$ denotes the entry of
matrix $\bm{X}$ at row $p$ and column $q$. Agents update their strategies
based on the type of _update rule_ they follow, which is either _best
response_ , that is to choose the strategy that maximizes its utility, or
_imitation_ , that is to copy the strategy of its highest earning neighbor.
The updates happen asynchronously over time, i.e., at each time step, a single
agent becomes active to update its strategy at the next time step. More
specifically, agent $i$ active at time $t$ updates its strategy at time $t+1$
to the following if it is an _imitator_ :

$x_{i}(t+1)=x_{k}(t),\qquad k=\arg\max_{j\in\mathcal{N}_{i}}u_{j}(\bm{x}(t)).$
(2)

and to the following if it is a _best-responder_ :

$x_{i}(t+1)=\arg\max_{\mathtt{X}\in\\{\mathtt{A},\mathtt{B}\\}}u_{i}(\bm{x}_{i=\mathtt{X}}(t))$
(3)

where $\bm{x}_{i=\mathtt{X}}$ is the vector $\bm{x}$ where the $i^{\text{th}}$
entry is fixed to strategy $\mathtt{X}$. In the case where both strategies
$\mathtt{A}$ and $\mathtt{B}$ maximize the utilities in (2) or (3), agent $i$
does not switch strategies, i.e., $x_{i}(t+1)=x_{i}(t)$.

######  Remark 1.

The standard inequalities in a coordination game are $R_{i}>T_{i}$ and
$P_{i}>S_{i}$ [18], implying that player $i$’s payoff is maximized when
playing the same strategy as that of its opponent. What condition (1)
additionally imposes are the inequalities $P_{i}>T_{i}$ and $R_{i}>S_{i}$,
resulting in the so-called _opponent-coordination_ payoff matrix [15]. Then
agent $i$’s payoff increases if its neighbor switches her strategy to that of
agent $i$, which proves useful in constructing energy functions for imitation
dynamics.

######  Example 1.

[Programming languages] Given the required effort to master a new programming
language, programmers have to decide between two options each time they
program an application: _(i)_ the comfort of working in the already
experienced language and _(ii)_ the benefit of learning a new language. Some
base their decisions on the prevalence of the language, because common
languages are supported by a community of peers who can smoothen the learning
experience via online forums. Others may focus on how successful other
programmers were in terms of, e.g., their salaries or reputation of developed
applications. The agents here are the community of App developers who interact
via online networks. The programming languages Python and Java may be
considered as the strategies and a programmer would earn more from his peers
if they use the same language.

######  Example 2.

[Social media] Telegram and WhatsApp are two social media applications.
Individuals choosing one of them as their main communication stream may decide
based on the (weighted) frequency or satisfaction of their friends on each
platform, implying the best response and imitation update rules respectively.
The individuals also have personal preferences over the apps because of their
features, resulting in different payoff matrices.

Define the agents’ _activation sequence_ as the sequence $\langle
a_{t}\rangle_{t=0}^{\infty}$, where $a_{t}$ is the active agent at time $t$.
The activation sequence together with update rules (2) and (3) govern the
state $\bm{x}(t)$ and define the _decision-making dynamics_ , which we refer
to as the _coordinating best-response and imitation dynamics_. A state
$\bm{x}^{*}\in\\{\mathtt{A},\mathtt{B}\\}^{n}$ is an _equilibrium_ of the
dynamics if under every activation sequence, $\bm{x}(0)=\bm{x}^{*}$ implies
$\bm{x}(t)=\bm{x}^{*}$ for all $t\geq 0$. We are interested in determining
whether the dynamics eventually equilibrate. We avoid trivial cases where the
dynamics “get stuck” at a non-equilibrium state because one or more
unsatisfied agents do not get the chance to become active. To this end, we
assume the activation sequence is _persistent_ , i.e., each agent becomes
active infinitely many times [19].

It follows from the coordination condition (1) and best-response update rule
(3) that if agent $i$ tends to play $\mathtt{A}$ at some state, so does it at
any other state with more $\mathtt{A}$-playing neighbors. In a more
restrictive sense, it can be also shown that if an imitator tends to play
$\mathtt{A}$ at some state, so does it at any other state where all of its
$\mathtt{A}$-playing neighbors still play $\mathtt{A}$. This property is
referred to as _$\mathtt{A}$ -coordinating_ [17, Definition 2], based on
which, the existence of an activation sequence that would drive the dynamics
from a given initial condition to an equilibrium state was shown in [17, Lemma
1, Theorem 2]. However, it remains open whether the dynamics equilibrate under
an arbitrary persistent activation sequence.

##  3 Equilibration results

The main result of this paper is about the equilibration of “sparse trees” as
presented in the following theorem. The _distance_ of two nodes in a graph is
the number of edges in the shortest path connecting the two. A _tree_ is a
network where exactly one path connects every pair of nodes. Define a
_branching agent_ as an agent with more than two neighbors. We call a tree
network _sparse_ if the distance between every pair of its branching agents is
greater than two.

######  Theorem 3.1 (Sparse tree).

A sparse-tree network equilibrates under the coordinating best-response and
imitation dynamics with an arbitrary persistent activation sequence.

Sparse trees are a generalization of starlikes, which in turn are a
generalization of linear graphs, defined in what follows. We accordingly,
first show the result for linear graphs (as well as rings), then starlikes,
and finally sparse trees.

###  3.1 Linear graphs

Consider network $\mathcal{G}=(\mathcal{N},\mathcal{E})$ with edge set
$\mathcal{E}=\\{\\{i,i+1\\}\mid i=1,\ldots,n-1\\}$, called a _linear graph_.

######  Definition 1 (Border agent).

Given a linear graph, agent $i$ is a _right-border_ (resp. _left-border_) if
it has a different strategy compared to agent $i+1$ (resp. $i-1$). A single
agent with a strategy different from those of its two neighbors is both a
right and left border agent. An agent is a _border_ if it is right or left-
border (or both).

We consider the most “left” (resp. “right”) agent, i.e., agent 1 (resp. $n$),
as a left (resp. right) border agent. We can now define the notion of
“section” as follows (Figure 1).

Figure 1: A linear graph with five sections. The sections in this linear graph
are $\\{1\\}$, $\\{2\\}$, $\\{3,4,5\\}$, $\\{6,7\\}$, and $\\{8\\}$. Blue and
red are used for strategies $\mathtt{A}$ and $\mathtt{B}$, respectively.
Agents $1$, $2$, and $8$ are each both left and right borders. Agents $3$, and
$6$ are only left-borders, while agents $5$ and $7$ are right-borders. Agent
$4$ is a non-border agent.

######  Definition 2 (Section).

A _section_ in a linear graph at a given strategy state is a set of
consecutive same-strategy playing agents $p,p+1,\ldots,q$, where $q\geq p$ and
agents $p$ and $q$ are borders. The size of the section is defined as $q-p+1$.

The special case of $p=q$ results in a size-one section consisting of a single
agent. The number of sections appears to serve as a potential function
according to the following lemma. The key idea of the proof is that the
emergence of a new section requires the sequence
$(\mathtt{A},\mathtt{A},\mathtt{A})$ (resp.
$(\mathtt{B},\mathtt{B},\mathtt{B})$) to turn into
$(\mathtt{A},\mathtt{B},\mathtt{A})$ (resp.
$(\mathtt{B},\mathtt{A},\mathtt{B})$), which is impossible due to the
coordinating nature of the population dynamics.

######  Lemma 3.2.

The number of sections in a linear graph does not increase under the
coordinating best-response and imitation dynamics with an arbitrary activation
sequence.

###### Proof.

A change in the population state takes place only if a border agent is active
because other agents play the same strategy as their neighbors and hence do
not switch strategies according to update rules (3) and (2). So the number of
sections change at time $t$ only if some border agent $i$ becomes active at
time $t-1$ and switches its strategy at time $t$ to say strategy $s$. At least
one neighbor of the border agent plays $s$ at time $t-1$ as otherwise, the
agent is not border. We have the following two cases, in neither of which the
number of sections increases:

_Case 1. Agent $i$ has two neighbors, i.e., $i\not\in\\{1,n\\}$._ If both
neighbors play $s$, then the border agent itself forms a section at time
$t-1$, which disappears at time $t$. Since no other sections are generated,
this results in a reduction in the number of sections. If only one neighbor
plays $s$, then the number of sections does not change after the switch.

_Case 2. Agent $i$ has one neighbor, i.e., $i\in\\{1,n\\}$._ Then the neighbor
plays $s$ at time $t-1$, implying that agent $i$ itself again forms a section,
which disappears at time $t$, resulting in a reduction. ∎

As the number of sections are finite, in view of Lemma 3.2, there exists some
time $T>0$ when the number of sections becomes fixed and no longer changes.
The sections may still expand or shrink though, preventing equilibration.
However, one can show that once a section expands from a certain direction,
say left (i.e., in the descending order of the agents’ labels), then it may no
longer shrink from left. Namely, if the left border of a section “moves” left
after time $T$, it never “moves” right in the future. This idea is rigorously
captured in the following lemma. For every time $t\geq T$, there is the same
number of sections which we label as $1,2,\ldots,S$ from left to right, that
is in the ascending order of their left borders. Denote by $L_{s}(t)$ and
$R_{s}(t)$ the left and right borders of section $s$ at time $t\geq T$. Given
a sequence of consecutive agents $p,p+1,\ldots,q$, where $q\geq p$, denote
their strategies by $\bm{x}_{(p,p+1,\ldots,q)}$.

######  Lemma 3.3.

Consider the time $T$ when the number of sections in the linear graph is
fixed. Then for every section $s$ and any time $t_{1}\geq T$,

$L_{s}(t_{1}+1)=L_{s}(t_{1})-1\Rightarrow\forall t\geq t_{1}\
L_{s}(t+1)\\!\leq\\!L_{s}(t),$

(4)

$R_{s}(t_{1}+1)=R_{s}(t_{1})+1\Rightarrow\forall t\geq t_{1}\
R_{s}(t+1)\\!\geq\\!R_{s}(t).$

###### Proof.

We prove the first equation by contradiction; the proof of the second equation
is similar. Assume the contrary and let $t_{3}>t_{1}$ be the first time (4) is
violated, i.e., $L_{s}(t_{3}+1)=L_{s}(t_{3})+1.$ Let $t_{2}\in[t_{1},t_{3}-1]$
be the last time that the left border of $s$ decreased, i.e.,
$L_{s}(t_{2}+1)=L_{s}(t_{2})-1.$ Let agent $i$ be the left border of section
$s$ at time $t_{2}$, i.e., $i=L_{s}(t_{2})$. Then

$\displaystyle L_{s}(t_{2})=L_{s}(t_{3}+1)=i,$ (5) $\displaystyle
L_{s}(t)=i-1\quad\forall t\in[t_{2}+1,t_{3}],$ (6)

Without loss of generality, assume that $x_{i}(t_{2})=\mathtt{B}$. It is
straightforward to show that if the agents of section $s$ play a strategy, say
$\mathtt{B}$, at time $T$, then the agents of section $s$ will play
$\mathtt{B}$ at every future time step as well. Therefore, since agent $i$ is
the left border of section $s$ at time $t_{2}$ and plays $\mathtt{B}$ at
$t_{2}$, it follows that all the agents in section $s$ play $\mathtt{B}$ at
every time $t\geq T$. Thus, in view of (5) to (6),

$\displaystyle\bm{x}_{(i-2,i-1,i)}(t_{2})$
$\displaystyle=(\mathtt{A},\mathtt{A},\mathtt{B}),$
$\displaystyle\bm{x}_{(i-2,i-1,i)}(t_{2}+1)$
$\displaystyle=(\mathtt{A},\mathtt{B},\mathtt{B}),$
$\displaystyle\bm{x}_{(i-2,i-1,i)}(t)$
$\displaystyle=(\mathtt{A},\mathtt{B},*)\quad\forall t\in[t_{2}+1,t_{3}-1],$
$\displaystyle\bm{x}_{(i-2,i-1,i)}(t_{3})$
$\displaystyle=(\mathtt{A},\mathtt{B},\mathtt{B}),$
$\displaystyle\bm{x}_{(i-2,i-1,i)}(t_{3}+1)$
$\displaystyle=(\mathtt{A},\mathtt{A},\mathtt{B}).$

The reason why $x_{i-2}(t_{2})=\mathtt{A}$ is that otherwise a section would
be removed at $t_{2}+1$, which is impossible as the number of sections is
assumed to be fixed after time $T$. Similarly, $x_{i-2}(t_{3})=\mathtt{A}$ as
otherwise a new section would be generated at time $t_{3}+1$.

Now we show that the two switches of strategies of agent $i-1$ at times
$t_{2}+1$ and $t_{3}+1$ are in conflict. Note that at both times $t_{2}$ and
$t_{3}$ agent $i$ plays $\mathtt{B}$ but has at time $t_{2}$ at most and at
time $t_{3}$ at least one other $\mathtt{B}$-playing neighbor. So as the game
is coordinating, i.e., in view of (1), $u_{i}(t_{3})\geq u_{i}(t_{2}).$ We
reach a contradiction in view of Lemma 4.1 and by letting $T=t_{2}$ and
$T^{\prime}=t_{3}$. ∎

We are ready to prove the equilibration of linear graphs. Consider a section
$s$ at time $T$. We say that _the left border of section $s$ moves left at
time $t\geq T+1$_ if $L_{s}(t)=L_{s}(t-1)-1$ and _moves right_ if
$L_{s}(t)=L_{s}(t-1)+1$. Similarly, the movement of the right border is
defined.

######  Proposition 1.

A linear graph equilibrates under the coordinating best-response and imitation
dynamics with an arbitrary persistent activation sequence.

###### Proof.

Consider some section $s$ at time $T$ when the number of sections is fixed. If
the left border of section $s$ moves left at any future time, then it can only
move left afterward according to Lemma 3.3. Since the linear graph is
constrained from left by agent $1$, the left border of section $s$ will be
fixed at some time. Similarly, the right border will be fixed if it moves
right at some point. So if the left border moves left at some time and the
right border moves right, then the borders of section $s$ will be fixed for
all future times.

Now if any of the borders, say right, becomes fixed but the left one only
moves right after time $T$, then also the left border becomes fixed at some
point as it is bounded from right by the right border (cannot pass it). On the
other hand, if the right border only moves left after time $T$ and the left
only moves right, again the two will become fixed as they cannot pass each
other. Therefore, the borders of section $s$ will become fixed at some finite
time. Since $s$ was an arbitrary section, it holds that at some finite time,
the borders of every section becomes fixed. This implies equilibration as the
activation sequence is persistent. ∎

###  3.2 Extension to rings

A network $\mathcal{G}=(\mathcal{N},\mathcal{E})$ with edge set
$\mathcal{E}=\\{\\{1,2\\},\dots,\\{n,n+1\\},\\{n+1,1\\}\\}$ is a _ring_.

######  Proposition 2 (Rings).

A ring network equilibrates under the coordinating best-response and imitation
dynamics with an arbitrary persistent activation sequence.

###### Proof.

Following the same arguments used for the proof of the equilibration of a
linear graph, it can be shown that the number of sections in a ring may not
increase, and hence will become fixed at some time $T$, and that if the right
border of a section moves right at some time, it may never move left
afterwards, and vice versa. So the only possibility for the non-equilibration
of a ring is that both borders of some section $s$ only and infinitely often
move right or only and infinitely often move left. Consider the second case,
i.e., moving left. Then for every agent $i$ in the ring, there exists a time
when it belongs to the section $s$ and a time when it does not belong to the
section. Hence, it will undergo the switches from
$\bm{x}_{(i-1,i,i+1)}=(\mathtt{A},\mathtt{A},\mathtt{B})$ to
$(\mathtt{A},\mathtt{B},\mathtt{B})$ and from
$(\mathtt{B},\mathtt{B},\mathtt{A})$ to $(\mathtt{B},\mathtt{A},\mathtt{A})$.
So the agent decides differently at two states with the same number of
$\mathtt{A}$ and $\mathtt{B}$-playing neighbors. Thus, in view of (3), agent
$i$, and hence, the whole ring are imitators. In view of the convergence
result in [15, Theorem 1] for arbitrary networks of all coordinating
imitators, the proof is complete. ∎

###  3.3 Starlikes

We now proceed to a more general network: The _starlike_ [20], that is a tree
with at most one branching agent. Define a _branch_ as a linear graph that
begins from a neighbour of the branching agent and ends with a leaf but does
not contain the branching agent itself (Figure 2-a).

Figure 2: a) Starlike graph. The agent on the top is the branching agent. The
graph has three branches. b) a sparse-tree population. Each red section
demonstrates a line in the population. Blue agents are branching agents of the
population.

Definition 3 and Lemma 3.4 are for general decision-making dynamics but are
framed here according to Section 2. Definition 3 is based on the notion of
_eventually periodic sequences_ [21] and Lemma 3.4 follows standard induction
arguments.

######  Definition 3 (Eventually periodic).

The coordinating imitation and best-response dynamics are _eventually
periodic_ under the activation sequence $\langle a_{t}\rangle_{t=0}^{\infty}$
if both the activation sequence and the resulting state $\bm{x}$ become
periodic after some finite time $t_{0}$, i.e.,

$\exists T,t_{0}\in\mathbb{N}\ \forall t\in\mathbb{N}\
[a_{t_{0}+t+T}=a_{t_{0}+t},\bm{x}_{t_{0}+t+T}=\bm{x}_{t_{0}+t}],$

where $T$ is the _periodicity after time $t_{0}$_, and time interval
$[t_{0},\infty)$ is the _periodic interval_. The activation sequence $\langle
a_{t}\rangle_{t=0}^{\infty}$ is called an _eventually periodic activation
sequence_.

######  Lemma 3.4.

If the coordinating imitation and best-response dynamics do not equilibrate
under some persistent activation sequence, then there also exists a persistent
eventually periodic activation sequence under which the population does not
equilibrate.

######  Lemma 3.5.

A starlike network equilibrates under the coordinating best-response and
imitation dynamics with an arbitrary persistent activation sequence, if the
branching agent does not switch strategies infinitely many times.

###### Proof.

It is straightforward to show that Lemmas 3.2 and 3.3 and hence proposition 1
hold if any of the end nodes in a linear graph fix their strategies.
Consequently, every branch together with the branching agent forms a linear
graph in the starlike that will equilibrate, leading to the equilibration of
the whole starlike. ∎

The equilibration of starlike networks is established in Proposition 3. The
idea of the proof is to focus on the times when the branching agent has the
maximum number of same strategy, say $\mathtt{B}$-playing, neighbors. The
moment one of these neighbors, referred to as the “special agent” switches,
the number of sections in the branch containing this special agent, referred
to as the “special branch”, will decrease, and this decrement will never be
compensated in the future. So the number of sections in the the spacial branch
is an energy-like function (see (7)). If before any of the neighbors switch,
the branching agent itself switches, then the branching agent must be an
imitator and the neighbor with the maximum utility will serve as the special
agent. Given a linear graph $P$, denote the number of sections in $P$ by
$n(P)$, and more specifically by $n(P,t)$ to denote the number at time $t$.

######  Proposition 3 (Starlike).

A starlike network equilibrates under the coordinating best-response and
imitation dynamics with an arbitrary persistent activation sequence.

###### Proof.

We prove by contradiction. By assuming the contrary, Lemma 3.4 implies the
existence of a persistent eventually periodic activation sequence denoted by
$\langle b_{t}\rangle_{t=0}^{\infty}$ with periodic interval $[t_{0},\infty)$.
The branching agent, say $i$, switches strategies under $\langle
b_{t}\rangle_{t=0}^{\infty}$ infinitely often; otherwise, the network
equilibrates due to Lemma 3.5. Let $t_{\mathtt{B}}\geq t_{0}$ be the first
time agent $i$ plays $\mathtt{B}$ and has the maximum number of
$\mathtt{B}$-playing neighbours during $[t_{0},\infty)$. Denote by $t_{1}$ the
first moment after $t_{\mathtt{B}}$ when either agent $i$ or one of its
neighbors switches strategies, resulting in the following two cases:

_Case 1: An agent $i$’s neighbour, say agent $j$, changes its strategy at time
$t_{1}$._ Consider the branch $P$ (referred to as the “special” branch)
including agent $j$ (referred to as the “special” agent). Denote the times
when agent $j$ switches strategies after $t_{1}$ by $t_{2},t_{3}\ldots$. Out
of these time steps, let $\langle
t^{\mathtt{B}}_{k}\rangle_{k=1}^{\infty}\subset\langle
t_{k}\rangle_{k=1}^{\infty}$ be those time steps such that agent $i$ had its
maximum number of $\mathtt{B}$-playing neighbors at each time
$t^{\mathtt{B}}_{k}-1$. Clearly, $t^{\mathtt{B}}_{1}=t_{1}$. We show that

$\forall k\geq 1\quad
n(P,t^{\mathtt{B}}_{k+1})-n(P,t^{\mathtt{B}}_{k})\leq-1.$ (7)

At every time $t^{\mathtt{B}}_{k}$ agent $j$ switches from $\mathtt{B}$ to
$\mathtt{A}$; otherwise, agent $i$ will have more $\mathtt{B}$-neighbors at
time $t^{\mathtt{B}}_{k}$ compared to $t_{\mathtt{B}}$. Thus, as the dynamics
are coordinating, agent $j$ has at least one $\mathtt{A}$-playing neighbour at
$t^{\mathtt{B}}_{k}$, who is not agent $i$. Because the network is starlike,
agent $j$ has at most two neighbors, so it has exactly one other neighbor, say
agent $k$, who plays $\mathtt{A}$ at $t^{\mathtt{B}}_{k}$. So $n(P)$ reduces
by one at time $t^{\mathtt{B}}_{k}$. In view of Lemma 4.2, $n(P)$ does not
increase if any agent other than $j$ switches strategies. So $n(P)$ may
increase in the future, only at times when agent $j$ switches strategies,
i.e., $t_{k+1},t_{k+2},\ldots$. We show that $n(P)$ decreases at each time
$T=t_{2r}$ for an arbitrary $r\in\mathbb{N}$. Agent $j$ switches from
$\mathtt{A}$ to $\mathtt{B}$ at time $t_{2r}$. If neighbor $k$ plays
$\mathtt{A}$ at time $T-1$, then agent $i$ plays $\mathtt{B}$ at the same
time; otherwise, agent $j$ does not tend to switch. So
$\bm{x}_{(k,j,i)}(T-1)=(\mathtt{A},\mathtt{A},\mathtt{B})$. Having the maximum
number of $\mathtt{B}$-playing neighbors at time $t_{1}$, agent $i$’s utility
at time $T-1$ is no more than at time $t_{1}-1$: $u_{i}(T-1)\leq
u_{i}(t_{1}-1).$ But this is impossible according to Lemma 4.1. So neighbor
$k$ plays $\mathtt{B}$ at time $T-1$. Then $n(P)$ reduces by the switch of
agent $j$ at time $T$. On the other hand, $n(P)$ may increase by at most one
at each time $t_{2r+1},r\in\mathbb{N}$. Therefore, there is no finite time
$T^{\prime}>t^{\mathtt{B}}_{k}$ when $n(P)$ equals its value at
$t^{\mathtt{B}}_{k}$, proving (7), a contradiction.

_Case 2: Agent $i$ switches from $\mathtt{B}$ to $\mathtt{A}$ at time
$t_{1}$._ There exists time $t_{2}>t_{1}$ when agent $i$ tends to switch back
to $\mathtt{B}$. However, the number of agent $i$’s $\mathtt{B}$-playing
neighbors is maximized at time $t_{1}$, when it switched to $\mathtt{A}$.
Hence, because of the coordinating dynamics, agent $i$ is an imitator.

Denote by $\langle T_{r}\rangle_{r=0}^{\infty}$ the time steps after $t_{0}$
that agent $i$ changes its strategy, and let $\langle
a_{r}\rangle_{r=0}^{\infty}$ be the corresponding neighbors imitated by agent
$i$. Let $a_{j}$ be an agent among $\langle a_{r}\rangle_{r=0}^{\infty}$ with
the maximum utility, i.e., $a_{j}=\arg\max_{r}u_{a_{r}}.$ So the maximum
utility among the agent $i$’s neighbors was earned by agent $a_{j}$ at time
$T_{j}$. Consider the branch $P$ including agent $a_{j}$. We show that the
number of sections in $P$ decreases at least once after time $T_{j}$ but never
increases afterwards, which is in contradiction with $T_{j}$ belonging to the
periodic interval of the activation sequence.

First, we prove the following: _Statement 1. At any time $T_{r}$, $r\geq 0$,
when agent $i$ switches to $\mathtt{A}$, agent $a_{j}$ must also play
$\mathtt{A}$._ At time $T_{j}-1$, agent $a_{j}$ plays $\mathtt{B}$ and has at
most one $\mathtt{B}$-playing neighbor. At time $T_{r}-1$, agent $i$ plays
$\mathtt{B}$, so agent $a_{j}$ has at least one $\mathtt{B}$-playing neighbor.
So if agent $a_{j}$ plays $\mathtt{B}$ at time $T_{r}$, it earns no less than
at time $T_{j}$ because of the coordinating dynamics, i.e.,
$u_{a_{j}}(T_{r})\geq u_{a_{j}}(T_{j}).$ Hence, according to the definition of
$a_{j}$, agent $a_{j}$ is a maximum earner at time $T_{r}$. Since agent $i$
does switch at time $T_{r}$, it has to switch to the strategy of agent $a_{j}$
according to (2). This is, however, impossible since both agents $a_{j}$ and
$i$ play the same strategy $\mathtt{B}$ at time $T_{r}$. This proves Statement
1.

Next, we list and investigate the possible strategy states for the pair
$(i,a_{j})$ starting from time $T_{j}$:

_Case 2.1. $\bm{x}_{(i,a_{j})}(t)=(\mathtt{B},\mathtt{B})$._ Then at the next
time $T_{r}\geq t$ when agent $i$ changes strategies, it switches to
$\mathtt{A}$. Hence, according to Statement 1,
$\bm{x}_{(i,a_{j})}(T_{r}-1)=(\mathtt{B},\mathtt{A})$. So according to Lemma
4.2, $n(P)$ reduces by at least 1 during $[t,T_{r}-1]$ as agent $i$ does not
switch strategies in this interval. We reach Case 2.2 at time $T_{r}$ as
$\bm{x}_{(i,a_{j})}(T_{r})=(\mathtt{A},\mathtt{A})$.

_Case 2.2. $\bm{x}_{(i,a_{j})}(t)=(\mathtt{A},\mathtt{A})$._ Then at the next
time $T_{s}\geq t$ when agent $i$ changes strategies, it switches to
$\mathtt{B}$. Now if agent $a_{j}$ plays $\mathtt{B}$ at time $T_{s}-1$, we
have $\bm{x}_{(i,a_{j})}(t)=(\mathtt{A},\mathtt{B})$. So again according to
Lemma 4.2, $n(P)$ reduces by at least 1 during $[t,T_{s}-1]$. We reach Case 1
at time $T_{s}$ as $\bm{x}_{(i,a_{j})}(T_{s})=(\mathtt{B},\mathtt{B})$. Now if
agent $a_{j}$ plays $\mathtt{A}$ at time $T_{s}-1$, we have
$\bm{x}_{(i,a_{j})}(t)=(\mathtt{A},\mathtt{A})$. So according to Lemma 4.2,
$n(P)$ may not increase during $[t,T_{s}-1]$. We reach Case 2.3 at time
$T_{s}$ as $\bm{x}_{(i,a_{j})}(T_{s})=(\mathtt{B},\mathtt{A})$.

_Case 2.3. $\bm{x}_{(i,a_{j})}(t)=(\mathtt{B},\mathtt{A})$._ Then at the next
time $T_{p}\geq t$ when agent $i$ changes strategies, it switches to
$\mathtt{A}$. Hence, according to Statement 1,
$\bm{x}_{(i,a_{j})}(T_{p}-1)=(\mathtt{B},\mathtt{A})$ which is the same as the
state at time $t$ in this case. So according to Lemma 4.2, $n(P)$ does not
increase during $[t,T_{p}-1]$. We reach Case 2.2 at time $T_{p}$ as
$\bm{x}_{(i,a_{j})}(T_{p})=(\mathtt{A},\mathtt{A})$.

At time $T_{j}$, the strategy state $\bm{x}_{(i,a_{j})}$ matches Case 1, where
$n(P)$ reduces. The proof is complete since it does not increase afterwards in
any of the above cases. ∎

###  3.4 Sparse-trees

We are ready to prove Theorem 3.1. The idea is to show that the “special
branches” of two branching nodes will intersect, resulting in the so-called
“golden branch” (Figure 2) which is guaranteed to equilibrate.

###### Proof of Theorem 3.1.

Equilibration of starlike networks were shown in Proposition 3. So here we
consider the case with at least two branching agents. We prove by
contradiction and consider a persistent eventually periodic activation
sequence denoted by $\langle b_{t}\rangle_{t=0}^{\infty}$ with periodic
interval $[t_{0},\infty)$. Similar to the proof of lemma 3.5, it can be shown
that at least one branching agent changes its strategy during the periodic
interval of the oscillation. We refer to the agents who change their strategy
during $[t_{0},\infty)$ a _settling_ agent and otherwise _unsettling_. For
each unsettling agent $i$, denote its special branch defined in the proof of
Proposition 3 by $P_{i}$. Equilibration can be shown using Lemma 3.5 when
there is no unsettling branching agent and similar to Proposition 3 when the
special branches of no two branching agents overlap (no golden branch). So
consider the case where there are two branching agents with the corresponding
special neighbors $i$ and $j$, and whose special branches intersect, denoted
by $P$. In view of Lemma 4.2, $n(P)$ increases only at the time steps when
either agent $i$ or $j$ switches. On the other hand, for both Case 1 and 2 in
Proposition 3, it is guaranteed that there exists some infinite time series
$\langle t^{i}_{k}\rangle_{k}^{\infty}$ (when agent $i$ switches) such that
$n(P,t^{i}_{k+1})-n(P,t^{i}_{k})\leq-1$ for all $k\geq 0$, and a some time
series $\langle t^{j}_{k}\rangle_{k}^{\infty}$ (when agent $j$ switches) such
that $n(P,t^{j}_{k+1})-n(P,t^{j}_{k})\leq-1$ for all $k\geq 0$. This is a
contradiction as then $n(P)$ is unbounded. ∎

##  4 Conclusion

We showed that every sparse tree network of coordinating heterogeneous
imitators and best-responders equilibrates under any persistent activation
sequence. This implies that neither the heterogeneity in the agents’
perceptions of the coordination game (i.e., different payoff matrices), nor
the order the agents become active can cause fluctuations in the mixed
population, at least when their connections are as sparse as a sparse-tree.
Whether dense trees or general graphs equilibrate under every activation
sequence remains an open problem. For the proof, we introduced the number of
sections in a linear graph as a potential function and generalized it to the
starlike and then sparse tree networks. The potential functions may be tested
in other decision making dynamics. For example, it is expected for the number
of sections to increase and eventually become fixed in anti-coordination games
under certain conditions [22].

## Appendix

######  Lemma 4.1.

Consider a network governed by the coordinating best-response and imitation
dynamics with an arbitrary activation sequence. Assume that the network
includes neighboring agents $p-1$ and $p$, each of degree two, and denote the
other neighbor of agent $p$ by $p+1$. If there exists some time $T\geq 0$ when
agent $p$ tends to switch strategies and
$\bm{x}_{(p-1,p,p+1)}(T)=(\mathtt{A},\mathtt{A},\mathtt{B}),$ then agent $p$
does not tend to switch strategies at any time $T^{\prime}$ when
$\bm{x}_{(p-1,p,p+1)}(T^{\prime})=(\mathtt{A},\mathtt{B},\mathtt{B})$ and when
agent $p+1$ earns non-less, i.e., $u_{p+1}(T^{\prime})\geq u_{p+1}(T)$.

###### Proof.

Should agent $p$ be a best-responder, its tendency to switch strategies at
time $T$ implies that it tends to play $\mathtt{B}$ if at least one of its
neighbors plays $\mathtt{B}$ in view of (3) and (1). Therefore, agent $p$ also
tends to play $\mathtt{B}$ at time $T^{\prime}$ since it has a
$\mathtt{B}$-playing neighbor. So consider the case where agent $p$ is an
imitator. At time $T$ agent $p$ tends to imitate agent $p+1$ who plays
$\mathtt{B}$ and has at most one other $\mathtt{B}$-playing neighbor. So agent
$p+1$ earns more than agent $p-1$, i.e., $u_{p+1}(T)>u_{p-1}(T).$ We know that
agent $p+1$ earns at time $T$ no more than at time $T^{\prime}$, i.e.,
$u_{p+1}(T)\leq u_{p+1}(T^{\prime}).$ Moreover, at both times $T$ and
$T^{\prime}$, agent $p-1$ plays $\mathtt{A}$ but has at time $T$ at least and
at time $T^{\prime}$ at most one other $\mathtt{A}$-playing neighbor, implying
$u_{p-1}(T)\geq u_{p-1}(T^{\prime}).$ These inequalities result in
$u_{p+1}\left(T^{\prime}\right)>u_{p-1}\left(T^{\prime}\right),$ which implies
the imitator agent, $p$, does not tend to change its strategy to agent
$p-1$’s. completing the proof. ∎

We say that a network _admits a linear graph_ $(1,2,\ldots,m)$ if there is a
link between node $i$ and $i+1$ for all $i=1,\ldots,m-1$ and the degree of
every node $2,\ldots,m-1$ is two. We refer to $(2,\ldots,m-1)$ as the
_interior_ of the linear graph.

######  Lemma 4.2.

Consider a network admitting the linear graph $(1,\ldots,m)$ governed by the
coordinating best-response and imitation dynamics. Then the number of sections
in the interior of the linear graph does not increase if each of the ending
agents $1$ and $m$ either are a leaf or its strategy does not change under the
activation sequence.

###### Proof.

The proof follows Lemma 3.2 with an activation sequence that does not activate
an ending agent whose strategy is fixed. ∎

## References

  * [1] M. Archetti and K. J. Pienta, “Cooperation among cancer cells: applying game theory to cancer,” _Nature Reviews Cancer_ , vol. 19, no. 2, pp. 110–117, 2019.
  * [2] Q. Li, M. Li, L. Lv, C. Guo, and K. Lu, “A new prediction model of infectious diseases with vaccination strategies based on evolutionary game theory,” _Chaos, Solitons & Fractals_, vol. 104, pp. 51–60, 2017.
  * [3] K. Coninx, G. Deconinck, and T. Holvoet, “Who gets my flex? an evolutionary game theory analysis of flexibility market dynamics,” _Applied energy_ , vol. 218, pp. 104–113, 2018.
  * [4] M. Askarizadeh, B. T. Ladani, and M. H. Manshaei, “An evolutionary game model for analysis of rumor propagation and control in social networks,” _Physica A: statistical mechanics and its applications_ , vol. 523, pp. 21–39, 2019.
  * [5] M. Mäs and H. H. Nax, “A behavioral study of “noise” in coordination games,” _Journal of Economic Theory_ , vol. 162, pp. 195–208, 2016.
  * [6] E. Ertz, L. Becker, M. Büttgen, and E. E. Izogo, “An imitation game–supervisors’ influence on customer sweethearting,” _Journal of Services Marketing_ , vol. 36, no. 3, pp. 432–444, 2022.
  * [7] R. Pauluzzo, “The imitation game: building cultural intelligence as a social learning capability to boost smes’ international performance,” _Journal of Small Business and Enterprise Development_ , vol. 28, no. 3, pp. 317–336, 2021\.
  * [8] A. Srivastava, A. Rastogi, A. Rao, A. A. M. Shoeb, A. Abid, A. Fisch, A. R. Brown, A. Santoro, A. Gupta, A. Garriga-Alonso _et al._ , “Beyond the imitation game: Quantifying and extrapolating the capabilities of language models,” _arXiv preprint arXiv:2206.04615_ , 2022.
  * [9] G. Como, F. Fagnani, and L. Zino, “Imitation dynamics in population games on community networks,” _IEEE Transactions on Control of Network Systems_ , vol. 8, no. 1, pp. 65–76, 2020.
  * [10] Y. Fu and P. Ramazi, “Evolutionary matrix-game dynamics under imitation in heterogeneous populations,” _arXiv preprint arXiv:2006.03438_ , 2020.
  * [11] I. Farahbakhsh, C. T. Bauch, and M. Anand, “Best response dynamics improve sustainability and equity outcomes in common-pool resources problems, compared to imitation dynamics,” _Journal of theoretical biology_ , vol. 509, p. 110476, 2021.
  * [12] W. Hu, G. Zhang, and H. Tian, “The stability of imitation dynamics with discrete distributed delays,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 521, pp. 218–224, 2019.
  * [13] P. Ramazi, J. Riehl, and M. Cao, “Networks of conforming or nonconforming individuals tend to reach satisfactory decisions,” _Proceedings of the National Academy of Sciences_ , vol. 113, no. 46, pp. 12 985–12 990, 2016.
  * [14] P. Ramazi and M. Cao, “Convergence of linear threshold decision-making dynamics in finite heterogeneous populations,” _Automatica_ , vol. 119, p. 109063, 2020.
  * [15] P. Ramazi, J. Riehl, and M. Cao, “The lower convergence tendency of imitators compared to best responders,” _Automatica_ , vol. 139, p. 110185, 2022.
  * [16] H. Le and P. Ramazi, “Heterogeneous mixed populations of best-responders and imitators: Equilibrium convergence and stability,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 8, pp. 3475–3488, 2020.
  * [17] N. Sakhaei, Z. Maleki, and P. Ramazi, “Equilibration analysis and control of coordinating decision-making populations,” in _2021 60th IEEE Conference on Decision and Control (CDC)_. IEEE, 2021, pp. 4314–4319.
  * [18] J. Riehl, P. Ramazi, and M. Cao, “A survey on the analysis and control of evolutionary matrix games,” _Annual Reviews in Control_ , vol. 45, pp. 87–106, 2018.
  * [19] P. Ramazi and M. Cao, “Asynchronous decision-making dynamics under best-response update rule in finite heterogeneous populations,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 3, pp. 742–751, 2017.
  * [20] G. Omidi and K. Tajbakhsh, “Starlike trees are determined by their laplacian spectrum,” _Linear Algebra and its Applications_ , vol. 422, no. 2-3, pp. 654–658, 2007.
  * [21] V. Braberman and L. Fribourg, _Formal Modeling and Analysis of Timed Systems_. Springer, 2013.
  * [22] N. Fates, D. Regnault, N. Schabanel, and E. Thierry, “Asynchronous behavior of double-quiescent elementary cellular automata,” in _LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings 7_. Springer, 2006, pp. 455–466.