# Networked Anti-Coordination Games Meet Graphical Dynamical Systems:
Equilibria and Convergence

Zirou Qiu 1,2 Chen Chen  2 Madhav V. Marathe  1,2 S. S. Ravi  2,3
Daniel J. Rosenkrantz  2,3 Richard E. Stearns  2,3 Anil Vullikanti1,2

###### Abstract

Abstract. Evolutionary anti-coordination games on networks capture real-world
strategic situations such as traffic routing and market competition. In such
games, agents maximize their utility by choosing actions that differ from
their neighbors’ actions. Two important problems concerning evolutionary games
are the existence of a pure Nash equilibrium (NE) and the convergence time of
the dynamics. In this work, we study these two problems for anti-coordination
games under sequential and synchronous update schemes. For each update scheme,
we examine two decision modes based on whether an agent considers its own
previous action (self essential) or not (self non-essential) in choosing its
next action. Using a relationship between games and dynamical systems, we show
that for both update schemes, finding an NE can be done efficiently under the
self non-essential mode but is computationally intractable under the self
essential mode. To cope with this hardness, we identify special cases for
which an NE can be obtained efficiently. For convergence time, we show that
the best-response dynamics converges in a polynomial number of steps in the
synchronous scheme for both modes; for the sequential scheme, the convergence
time is polynomial only under the self non-essential mode. Through
experiments, we empirically examine the convergence time and the equilibria
for both synthetic and real-world networks.

##  1 Introduction

Evolutionary anti-coordination (AC) games have been widely used to model real-
world strategic situations such as product marketing [25], balanced traffic
routing [16], and social competition [10]. In the networked version of such a
game, vertices are agents (players), and edges are interactions between
agents. At each time step, agents make new decisions based on the decisions of
their neighbors [39]. Specifically, under the best-response dynamics of an
anti-coordination game with binary actions, each agent maximizes its utility
at the current time step by choosing a particular action (i.e., $0$ or $1$) if
and only if a sufficient number of its neighbors chose the opposite action at
the previous step [31]. There are two main types of update schemes for
evolutionary games, where agents either choose actions synchronously or
sequentially [1].

The decision mode where each agent only considers its neighbors’ actions in
making its decisions is common in the game theory literature [17].
Nevertheless, in real-world situations where agents compete for resources, it
is natural for an agent to also consider its own previous action before
choosing a new action [17, 36, 26]. For example, drivers on a highway can be
seen as agents in an evolutionary anti-coordination game, where people switch
lanes to avoid traffic. In particular, an agent’s choice of lanes in the next
time step is influenced by both its current lane and the lanes of neighboring
cars. Such considerations motivate us to investigate two decision modes: ($i$)
self essential (SE), where each agent considers both its previous action and
the actions of its neighbors, and $(ii)$ self non-essential (SN), where each
agent only considers the actions of its neighbors111Our usage of the word
“essential” here is based on the term “essential variable” used in the context
of Boolean (and other) functions to indicate the dependence of a function on a
variable [34]..

Pure Nash equilibria (NE) are a central concept in game theory [3, 30]. In
evolutionary games, another key notion is the time it takes for the best-
response dynamics to reach an NE or a limit cycle [13, 20]. Nevertheless,
researchers have given limited attention to efficiently finding an NE for
anti-coordination games under the SE and SN modes. Further, to our knowledge,
whether the best-response dynamics of anti-coordination games has a polynomial
convergence time remains open. In this work, we close the gap with a
systematic study of the following two problems for the synchronous and
sequential games under both SE and SN modes: $(i)$ Equilibrium
existence/finding (EQE/EQF): Does the game have an NE, and if so, can we find
one efficiently? $(ii)$ Convergence (Conv): Starting from an action profile,
how fast does the best-response dynamics converge222We use convergence to mean
that the dynamics reaches a limit cycle of length at most $2$ (e.g., an NE is
a limit cycle of length $1$). For games considered in this work, it is known
that the length of each limit cycle is at most $2$, except for SE sequential
AC games, where there can be limit cycles of exponential length. to a cycle of
length at most $2$?

The best-response dynamics of an evolutionary anti-coordination game can be
specified using a threshold framework [2]. This naturally allows us to model
such a game as a graphical dynamical system [9]. In such a system, at each
time step, each vertex uses its local function to compute its state in the
next time step. To model anti-coordination games, the domain is Boolean, and
the local functions are inverted-threshold functions whereby each vertex $u$
is assigned state $1$ for the next step if and only if enough neighboring
vertices of $u$ are currently in state $0$. Graphical dynamical systems are
commonly used to model the propagation of contagions and decision-making
processes over networks [9]. Here, we use dynamical systems with inverted-
threshold functions as a theoretical framework to study EQE/EQF and Conv
problems for evolutionary networked anti-coordination games.

Main Contributions

  * •

Finding an NE. We demonstrate an interesting contrast in the complexity of
EQE/EQF between the SE and SN modes for anti-coordination games. In
particular, we show that EQE/EQF is NP-hard under the SE mode for both
synchronous and sequential games, even on bipartite graphs. Further, we show
that the corresponding counting problem is #P-hard. On the other hand, we can
find an NE efficiently under the SN mode for synchronous and sequential games.
We also identify special cases (e.g., the underlying graph is a DAG, or even-
cycle free) of EQE/EQF for the SE mode where an NE can be efficiently found.

  * •

Convergence. We show that starting from an arbitrary action profile, the best-
response dynamics of synchronous anti-coordination games under either SE or SN
mode converge in $O(m)$ time steps, where $m$ is the number of edges in the
underlying graph. Further, we establish a similar $O(m)$ bound on the
convergence time for sequential anti-coordination games under the SN mode. We
do not consider the convergence problem for the sequential games under the SE
mode since such systems can have exponentially long cycles [8].

  * •

Empirical analysis. We study the contrast in the empirical convergence time
for both modes under different classes of networks. Further, we perform
simulations to explore how convergence time changes with network density. We
also investigate the number of equilibria for problem instances of reasonable
sizes.

Problems | SN-SyACG | SE-SyACG | SN-SACG | SE-SACG
---|---|---|---|---
EQE / EQF |  Trivial / P |  NP-hard |  Trivial / P |  NP-hard
Conv | $O(m)$ | $O(m)$ | $O(m)$ | NA

Table 1: Overview of key results. All results, except those marked with
“Trivial” and “NA”, are established in this paper. SyACG (SACG) denotes
synchronous (sequential) anti-coordination game, and SE (SN) stands for the
self essential (self non-essential) mode. The number of edges is $m$. The
entry “Trivial” for EQE denotes that the corresponding game always has a NE
[28]. “NA” denotes that the problem is not applicable since there can be
exponentially long cycles [8]. For Conv, $O(m)$ is the number of steps for the
best-response dynamics to reach a limit cycle.

##  2 Related Work

#### The existence of NE.

The self non-essential sequential anti-coordination games are potential games
and always have an NE [37]. This argument follows from [28], which guarantees
the existence of NE at the maximum potential. Further, Monderer and Shapley
[28] show that general potential games converge in finite time. Note that this
result does not imply a polynomial-time algorithm in finding an NE. Kun et al.
[21] study a special form of anti-coordination games where each agent chooses
the decision that is the opposite of the majority of neighboring decisions,
and show that in such a game, an NE can be found efficiently. Vanelli et al.
[37] examine synchronous games with both coordinating and anti-coordinating
agents. They present several special cases on the threshold distributions for
the existence of NE.

Auletta et al. [5] define the class of generalized discrete preference games
and show that such games always have an NE. They also show that every ordinal
potential game with binary actions can be reduced to a discrete preference
game. Goles and Martinez [18] prove that for synchronous coordination games,
the length of any limit cycle is at most $2$. Many researchers have studied
the existence of NE in other games of different forms (e.g., [35, 14]).

#### Limiting behavior.

Adam et al. [2] show that the length of a limit cycle in a synchronous anti-
coordination game is at most $2$. However, they did not bound the convergence
time to reach a limit cycle. Ramazi, Riehl, and Cao [31] investigate the
convergence time for asynchronous self non-essential anti-coordination games;
they establish that an NE will be reached in finite time. We note that the
asynchronous dynamic they consider is different from the sequential dynamic
studied in our work, and their convergence result does not imply ours.

Goles and Martinez [18] establish that for coordination games, the dynamics
converges in a polynomial number of steps. Barrett et al. ([8]) study phase
space properties of sequential dynamical systems (which includes modeling
sequential AC games); the results imply that the length of a limit cycle in a
self essential sequential anti-coordination game can be exponential in the
number of agents. The convergence of the best-response dynamics for games of
other types has also been studied (e.g., [19, 6, 20].

#### Minority games.

Anti-coordination games are closely related to minority games [12, 4]. Many
versions of minority games have been studied. For example, Challet and Marsili
[11] study the dynamics of minority games where agents make decisions based on
the action profile history of the population. Shang et al. [27] examine the
action distribution of minority games over different network topologies.
Several other forms of minority games are studied in [24].

A more thorough discussion of related work is given in the Appendix. To our
knowledge, the complexity of EQF for SACG/SyACG has not been established; nor
has a polynomial bound on the convergence time of these games been
established. We resolve these problems in this work.

##  3 Preliminaries and Problem Definition

A networked game operates on a graph $G$ where vertices are agents and edges
represent interactions. At each discrete time step, an agent chooses a binary
action from the set $\\{0,1\\}$ based on neighbors’ actions, and receives a
payoff. Under the best-response dynamics, each agent chooses an action that
yields a maximum payoff. For the best-response dynamics of an anti-
coordination (AC) game, each agent $v$ has a nonnegative threshold
$\tau_{1}(v)$, and $v$ chooses action $1$ if and only if the number of
neighbors (plus possibly $v$ itself) that chose action $0$ is at least
$\tau_{1}(v)$ [31]. We now define the problems of interest.

######  Definition 3.1 (Equilibrium existence/finding).

Given an anti-coordination game, does it have an NE, and if so, can we find it
efficiently?

######  Definition 3.2 (Convergence).

Given an anti-coordination game and an initial action profile, how fast does
the best-response dynamics converge to a limit cycle?

We examine two decision modes, based on whether or not each agent considers
its own previous action in making a new decision. Under the self non-essential
(SN) mode, each agent only considers neighbors’ actions, whereas, under the
self essential (SE) mode, each agent considers both its own previous action
and its neighbors’ actions. We further consider two types of update schemes:
$(i)$ synchronous (SyACG): agents choose actions simultaneously; $(ii)$
sequential (SACG): at each time step, agents update their actions in a
predefined order. Overall, we examine four classes of AC games based on update
scheme (i.e., synchronous or sequential) and decision mode (i.e., SN or SE).

#### Graphical dynamical systems.

We use dynamical systems as a mathematical framework to study anti-
coordination games. We follow the notation used in [9, 32]. A synchronous
dynamical system (SyDS) over the Boolean state domain $\mathbb{B}=\\{0,1\\}$
is a pair $\mathcal{S}=(G_{\mathcal{S}}{},\mathcal{F})$;
$G_{\mathcal{S}}{}=(V,E)$ is the underlying graph, with $n=|V|$ and $m=|E|$.
We assume $G_{\mathcal{S}}{}$ is connected and undirected, unless specified
otherwise. The set $\mathcal{F}=\\{f_{1},...,f_{n}\\}$ consists of functions
with $f_{i}$ being the local function of vertex $v_{i}\in V,1\leq i\leq n$.
The output of $f_{i}$ gives the state value of $v_{i}$. In a SyDS, vertices
update states simultaneously at each time step.

A sequential dynamical system (SDS) $\mathcal{S}^{\prime}$ is a tuple
$(G_{\mathcal{S^{\prime}}}{},\mathcal{F}^{\prime},\Pi)$ where
$G_{\mathcal{S^{\prime}}}{}$ and $\mathcal{F}^{\prime}$ are defined the same
as for the above synchronous systems [29]. In addition, $\Pi$ is a permutation
of $V$ that determines the sequential order in which vertices update their
states at each time step. Specifically, each time step of
$\mathcal{S}^{\prime}$ consists of $n$ substeps, in each of which one vertex
updates its state using the current vertex states in $\mathcal{S}^{\prime}$.

#### Update rules.

To model anti-coordination dynamics, we consider inverted-threshold local
functions for the state-update of vertices. Formally, each vertex $v_{i}$ has
a fixed integer threshold $\tau_{1}(v_{i})\geq 0$. Starting from an initial
configuration, all vertices update states at each time step using their local
functions, and the next state of $v_{i}$ is $1$ iff the number of neighbors
(plus possibly $v_{i}$ itself) with state-$0$ at the previous time step (for a
synchronous scheme) or at the current time step (for a sequential scheme) is
at least $\tau_{1}(v_{i})$.

Lastly, analogous to anti-coordination games, we consider the same two
decision modes (i.e., SN and SE) for dynamical systems. Based on the schemes
(i.e., SyDS or SDS) and decision modes, we have four classes of systems that
map to the four classes of anti-coordination games described previously. We
use the notation (SN/SE, IT)-SDS/SyDS to denote different classes of systems
(IT stands for inverted-threshold). An example of SN mode is shown in Figure
1.

#### Limit cycles.

A configuration $C$ of a system $\mathcal{S}$ is a vector $C=$
$(C(v_{1}),...,C(v_{n}))$ where $C(v_{i})\in\mathbb{B}$ is the state of vertex
$v_{i}$ under $C$. The dynamics of $\mathcal{S}$ from an initial configuration
$C$ can be represented by a time-ordered sequence of configurations. A
configuration $C^{\prime}$ is the successor of $C$ if $\mathcal{S}$ evolves
from $C$ to $C^{\prime}$ in one step. Let $C^{\prime}$ be the successor of
$C$, and $C^{\prime\prime}$ be the successor of $C^{\prime}$. If
$C=C^{\prime}$, that is, no vertices undergo state changes from $C$, then $C$
is a fixed point of $\mathcal{S}$; if $C\neq C^{\prime}$, but
$C=C^{\prime\prime}$, then $C\rightleftharpoons C^{\prime}$ forms a 2-cycle of
$\mathcal{S}$.

Figure 1: Example dynamics of SDS and SyDS under the SN mode. Specifically,
$C$ is an initial configuration, and $C^{\prime}$ is its successor under
either the synchronous or the sequential (with vertex update order
$(v_{1},v_{2},v_{3},v_{4})$) mode. State-1 vertices are highlighted in blue.

The dynamics of an AC game is captured by the dynamics of the underlying
dynamical system $\mathcal{S}$. Specifically, an agent $v$’s action at time
$t$ corresponds to $v$’s state at time $t$ in $\mathcal{S}$, and $v$’s
decision threshold is described by $\tau_{1}(v)$. Moreover, the evolution of
the action profile for the game coincides with the transition of
configurations under $\mathcal{S}$. Thus, We have:

######  Observation 3.3.

A fixed point and a limit cycle of $\mathcal{S}$ correspond respectively to an
NE and a limit cycle of the action profile for the underlying anti-
coordination game.

Further, the convergence time of $\mathcal{S}$ precisely characterizes the
convergence time of the corresponding game. Given this connection, proofs of
our results for anti-coordination games are given in the context of dynamical
systems.

##  4 Equilibrium Existence and Finding

For self essential (SE) anti-coordination games, we establish that EQE (and
therefore EQF) is NP-hard, even on bipartite graphs. Further, the
corresponding counting problem is #P-hard. In contrast, for self non-essential
(SN) anti-coordination games, we can find an NE in polynomial time. We remark
that the simple difference between the two modes (i.e., whether each agent
considers its own state or not) yields a major difference in the complexity of
finding an NE. We further discuss the reasons for this contrast in a later
section. Lastly, to cope with the hardness under the SE mode, we identify
special classes where an NE (if it exists) can be found efficiently.

We first observe that if a SyDS $\mathcal{S}$ and an SDS
$\mathcal{S}^{\prime}$ have the same underlying graph and the same local
functions, then they have the same set of fixed points, regardless of the
vertex permutation $\Pi$ of $\mathcal{S}^{\prime}$.

######  Observation 4.1.

A SyDS and an SDS with the same underlying graph and the same local functions
have the same set of fixed points.

Since a fixed point of a dynamical system corresponds to an NE of the
underlying anti-coordination game, it follows that the complexities of EQE/EQF
are the same for SN-SyACG and SN-SACG. The same observation holds for SE-SyACG
and SE-SACG.

###  4.1 Intractability for the self essential mode

We establish that EQE (and therefore EQF) is hard for the anti-coordination
games under the SE mode (i.e., SE-SyACG and SE-SACG). In particular, we
present a reduction from 3SAT to EQE for the SE-SyACG (modeled as a SyDS), and
by Observation 4.1, the hardness is carried over to the SE-SACG. Further, the
reduction is parsimonious, which further implies that #EQE is #P-hard. We
present detailed proofs in the Appendix.

######  Theorem 4.2.

For both SE-SyACG and SE-SACG, EQE is NP-complete, and the counting problem
#EQE is #P-hard. These results hold even when the graph is bipartite.

###### Proof (sketch).

Given a 3SAT formula $f$, we construct a (SE, IT)-SyDS $\mathcal{S}$ such that
there is a one-to-one correspondence between satisfying assignments of $f$ and
fixed points of $\mathcal{S}$. The construction creates a positive and a
negative literal vertex for each variable in $f$, and a clause vertex for each
clause. Each clause vertex is adjacent to the corresponding literal vertices.
We construct two carefully designed gadgets to ensure that $(i)$ in any fixed
point of $\mathcal{S}$, a positive and a negative literal vertex for the same
variable have complementary values; $(ii)$ there is a one-to-one
correspondence between satisfying assignments and fixed points. ∎

###  4.2 Finding NE under the self non-essential mode

It is known that a SN-SACG always has an NE, and an NE can be found in finite
time [28]. Thus, EQE is trivially true for SN-SACG, and by Observation 4.1,
EQE is also true for SN-SyACG; however, the complexity of the search problem
EQF is not implied.

In this section, we look beyond the existence problem and show that an NE for
an SN game (i.e., SN-SyACG and SN-SACG) can be found in polynomial time.
Specifically, we show that starting an (SN, IT)-SDS $\mathcal{S}^{\prime}$
(modeling a SN-SACG) from any configuration $C$, a fixed point of
$\mathcal{S}^{\prime}$ is always reached in at most $3m$ steps. Since each
step of $\mathcal{S}^{\prime}$ can be carried out in $O(m)$ time, a fixed
point of $\mathcal{S}^{\prime}$ can be found in $O(m^{2})$ time (Theorem 4.5).
As for a (SN, IT)-SyDS $\mathcal{S}$ (modeling a SN-SyACG), we can transform
it into a corresponding SDS $\mathcal{S}^{\prime}$, and then find a fixed
point of $\mathcal{S}^{\prime}$ (obtained as described above), which is also a
fixed point of $\mathcal{S}$. We provide more details below.

The potentials. Let $\mathcal{S}^{\prime}$ be an (SN, IT)-SDS. Recall that for
each vertex $u\in V(G_{\mathcal{S}^{\prime}})$, $\tau_{1}(u)$ is the minimum
number of state-0 neighbors of $u$ such that $f_{u}$ evaluates to $1$. For the
SN mode, $\tau_{0}(u)=d(u)+1-\tau_{1}(u)$ is the minimum number of state-1
neighbors of $u$ such that $f_{u}$ evaluates to $0$. Given a configuration $C$
of $\mathcal{S}^{\prime}$, the potentials $\mathcal{P}$ of vertices, edges,
and $C$ are defined as follows.

Vertex potential: The potential of $u\in V(G_{\mathcal{S}^{\prime}})$ under
$C$ is $\mathcal{P}(C,u)=\tau_{0}(u)$ if $C(u)=0$;
$\mathcal{P}(C,u)=\tau_{1}(u)$ otherwise.

Edge potential: The potential of $e=(u,v)\in E(G_{\mathcal{S}^{\prime}})$
under $C$ is $\mathcal{P}(C,e)=1$ if $C(u)=C(v)$; $\mathcal{P}(C,e)=0$
otherwise.

Configuration potential: The potential of $C$ is the sum of the vertex
potentials and edge potentials over all vertices and edges. That is,
$\mathcal{P}(C,\mathcal{S}^{\prime})=\sum_{u\in
V(G_{\mathcal{S}^{\prime}})}\mathcal{P}(C,u)+\sum_{e\in
E(G_{\mathcal{S}^{\prime}})}\mathcal{P}(C,e)$.

We now establish that under any configuration $C$, the potential is lower and
upper bounded by polynomials in $n$ and $m$. A detailed proof is in the
Appendix.

######  Lemma 4.3.

For any configuration $C$ of $\mathcal{S}^{\prime}$, we have

$0\leq\mathcal{P}(C,\mathcal{S}^{\prime})\leq 3m$ (1)

###### Proof (sketch).

One can easily verify that the configuration potential over any configuration
is at least $0$. As for the upper bound, we argue that

$\sum_{u\in V(G_{\mathcal{S}}{})}\mathcal{P}(C,u)\leq\sum_{u\in
V(G_{\mathcal{S}}{})}\max\\{\tau_{0}(u),\tau_{1}(u)\\}\leq\sum_{u\in
V(G_{\mathcal{S}}{})}d(u)=2m$ (2)

and that the upper bound for the edge potential is $m$. The upper bound of
$3m$ for the configuration potential follows. ∎

Lemma 4.3 establishes that the configuration potential gap between any two
configurations is at most $3m$ for $\mathcal{S}^{\prime}$.

#### Decrease of potential.

Next, we argue that whenever a substep of $\mathcal{S}^{\prime}$ changes the
state of a vertex, the configuration potential decreases by at least $1$.
Consequently, the system reaches a fixed point (i.e., no vertices further
update their states) in at most $3m$ total steps. The detailed proof appears
in the Appendix.

######  Lemma 4.4.

Suppose that in a substep of $\mathcal{S}^{\prime}$ for a vertex $u$, the
evaluation of $f_{u}$ results in a state change of $u$. Let $C$ denote the
configuration before the substep, and $\hat{C}$ the configuration after the
substep. Then,
$\mathcal{P}(\hat{C},\mathcal{S}^{\prime})-\mathcal{P}(C,\mathcal{S}^{\prime})\leq-1$.

###### Proof (sketch).

Since $u$ is the only vertex that undergoes a state change, the overall
configuration potential is affected by only the change of $u$’s potential and
the potentials of edges incident to $u$. W.l.o.g., suppose $u$’s state changes
from $0$ to $1$ in the transition from $C$ to $\hat{C}$. We can show that the
change in the configuration potential is of the form

$\mathcal{P}(\hat{C},\mathcal{S}^{\prime})-\mathcal{P}(C,\mathcal{S}^{\prime})=\tau_{1}(u)+d_{1}(u)-\tau_{0}(u)-d_{0}(u)$
(3)

where $d_{0}(u)$ and $d_{1}(u)$ are the numbers of $u$’s neighbors in
state-$0$ and state-$1$ in $C$, respectively. Since $\hat{C}(u)=1$, it follows
that $d_{0}(u)\geq\tau_{1}(u)$ and $d_{1}(u)\leq\tau_{0}(u)-1$. Therefore,
$\mathcal{P}(\hat{C},\mathcal{S}^{\prime})-\mathcal{P}(C,\mathcal{S}^{\prime})\leq-1$.
∎

From the above two Lemmas, starting from an arbitrary configuration of (SN,
IT)-SDS $\mathcal{S}^{\prime}$, a fixed point is reached in $3m$ steps. Thus,
we can find a fixed point by starting with an arbitrary inititial
configuration, and simulating the operation of $\mathcal{S}^{\prime}$ for $3m$
steps. Each step consists of $n$ substeps, each of which evaluates one of the
local functions. Thus, each step can be simulated in $O(m)$ time. Overall, a
fixed point of $\mathcal{S}^{\prime}$ can be found in $O(m^{2})$ time.
Similarly, given a (SN, IT)-SyDS $\mathcal{S}$, we can first convert
$\mathcal{S}$ into an SDS $\mbox{$\mathcal{S}$}{}^{\prime}$ by assigning a
random vertex permutation, and then find a fixed point of
$\mathcal{S}^{\prime}$, which is also a fixed point $\mathcal{S}$. Lastly,
given that a fixed point of a dynamical system is an NE of the underlying self
non-essential game, we have:

######  Theorem 4.5.

For both SN-SACG and SN-SyACG, we can find an NE in $O(m^{2})$ time.

#### Remark.

A key reason for the drastic contrast in the complexity of EQE/EQF between the
SN and SE modes is the difference in the behavior of threshold-1 vertices
(i.e., vertices with $\tau_{1}=1$). In the SE mode, a threshold-1 vertex $u$
cannot be in state $0$ under any fixed point because $u$ will change to state
1 in the next step. (Since $u$ counts its own state, there is at least one $0$
input to $f_{u}$). In particular, the gadgets used in the hardness proof for
the SE mode critically depend on this fact. In contrast, such a constraint
does not hold for threshold-1 vertices under the SN mode. Hence, our hardness
proof does not carry over to the SN mode.

###  4.3 Efficient algorithms for special classes

Given the hardness of EQE/EQF for SE anti-coordination games, we identify
several sufficient conditions under which an NE can be obtained efficiently
(if one exists), as follows.

######  Theorem 4.6.

For both SE-SyACG and SE-SACG, there is a $O(m+n)$ time algorithm for EQE/EQF
for any of the following restricted cases: $(i)$ The underlying graph is a
complete graph. $(ii)$ The underlying graph has no even cycles. $(iii)$ The
underlying graph is a directed acyclic graph. $(iv)$ The threshold for each
$u$ satisfies $\tau_{1}(u)\in\\{1,d_{u}+1\\}$.

###### Proof (sketch).

The detailed proof appears in the appendix. Here, we provide a sketch for
$(i)$ (i.e., complete graphs). Let $\mathcal{P}=\\{V_{1},...,V_{k}\\}$ be the
partition of the vertex set $V$ where each block of $\mathcal{P}$ consists of
a maximal set of vertices with the same value of $\tau_{1}$, and the blocks of
$\mathcal{P}$ are indexed so that for each $i$, $1\leq i<k$, the members of
$V_{i}$ have a lower value of $\tau_{1}$ than the members of $V_{i+1}$.
Suppose that configuration $C$ is a fixed point. Let $q$ be the highest block
index such that the number of 0’s in $C$ is at least the $\tau_{1}$ value of
the vertices in $V_{q}$. Since the underlying graph is a complete graph, for
each vertex $u$, $C(u)=1$ iff $u\in V_{i}$ for some $i$ where $i\leq q$. Thus
there are only $k+1$ candidate configurations that can possibly be a fixed
point. Our algorithm constructs each of these candidates and checks if it is a
fixed point. ∎

##  5 Convergence

We have shown in the previous section that for SN-SACG, starting from any
action profile, the best-response dynamics converges to an NE in $O(m)$ steps.
In contrast, it is known that the best-response for SE-SACG could have
exponentially long limit cycles [8].

#### Remark.

The dynamics of an SDS and its corresponding SyDS can be drastically
different. Therefore, the $O(m)$ convergence time for a SACG (SDS) established
in the previous section does not imply an $O(m)$ convergence time for a SyACG
(SyDS). In fact, synchronous anti-coordination games are not potential games.
Therefore, the approach we used for SACG does not carry over to the analysis
of SyACG. Also, both SN-SyACG and SE-SyACG can have length-$2$ limit cycles,
and there are instances of SE-SyACG that do not have an NE (e.g., the
underlying graph is an odd cycle and $\tau_{1}=2$ for all vertices.).

###  5.1 Convergence of synchronous games

Synchronous anti-coordination games are not potential games. Therefore, the
results on potential games by Monderer and Shapley ([28]) do not apply. As
shown in [2], the limit cycles of such a game are of length at most $2$. In
this section, we study the convergence time to either an NE or a 2-cycle for
SN-SyACG and SE-SyACG. Using a potential function argument inspired by [18],
in Theorem 5.3 we establish that for both SN-SyACG and SE-SyACG, starting from
an arbitrary action profile, the best-response dynamics converges in $O(m)$
steps. (A detailed proof of the theorem appears in the Appendix.) Here, we
present a proof sketch for the SN mode. Let
$\mbox{$\mathcal{S}$}{}=(G_{\mathcal{S}}{},\mathcal{F})$ be a (SN, IT)-SyDS
corresponding to a given SN-SyACG.

#### The potentials.

Due to the existence of length-2 limit cycles, our definitions of potentials
at each time step account for not only the states of vertices at the current
step but also that of the next step. For SN mode, let
$\tau_{0}(u)=d(u)+1-\tau_{1}(u)$ be the minimum number of state-1 neighbors of
vertex $u$ such that $f_{u}$ evaluates to $0$. We henceforth assume that no
local function is a constant function (i.e., $1\leq\tau_{1}(u)\leq
d(u),\;\forall u\in V(G_{\mathcal{S}}{})$); a justification is given in the
Appendix. Consequently, $1\leq\tau_{0}(u)\leq d(u)$. We define
$\tilde{\tau}_{0}(u)=\tau_{0}(u)-1/2$. Given an arbitrary configuration $C$ of
$\mathcal{S}$, let $C^{{}^{\prime}}$ be the successor of $C$, and
$C^{\prime\prime}$ the successor of $C^{\prime}$.

Vertex potentials. The potential of a vertex $u$ under $C$ is defined by

$\mathcal{P}(C,u)=[C(u)+C^{{}^{\prime}}(u)]\cdot\tilde{\tau}_{0}(u)$

Edge potentials. The potential of an edge $e=(u,v)$ under $C$ is defined by

$\mathcal{P}(C,e)=C(u)\cdot C^{{}^{\prime}}(v)+C(v)\cdot C^{{}^{\prime}}(u)$

Configuration potential. The potential of a configuration $C$ is defined by

$\mathcal{P}(C,\mathcal{S})=\sum_{e\in
E(G_{\mathcal{S}}{})}\mathcal{P}(C,e)-\sum_{u\in
V(G_{\mathcal{S}}{})}\mathcal{P}(C,u)$

We now establish lower and upper bounds on the potential under an arbitrary
configuration $C$.

######  Lemma 5.1.

For any configuration $C$ of a (SN, IT)-SyDS $\mathcal{S}$, we have

$-4m+n~{}\leq~{}\mathcal{P}(C,\mathcal{S})\leq 0$

###### Proof (sketch).

One can easily verify that the maximum value of the sum of vertex potentials
is $4m-n$, which gives the lower bound. We now address the upper bound of $0$.
For each vertex $u$, let $E_{u}$ be the set of edges incident on $u$, and let
$\sigma_{u}=\sum_{u\in V(G_{\mathcal{S}}{})}C(v)$. Note that for an inverted-
threshold function $f_{u}$, $C^{\prime}(u)=1$ iff $\sigma_{u}<\tau_{0}(u)$,
i.e., iff $\sigma_{u}\leq\tau_{0}(u)-1$. Let $\beta_{u}=\sigma_{u}\cdot
C^{\prime}(u)-C^{{}^{\prime}}(u)\cdot\tilde{\tau}_{0}(u)-C(u)\cdot\tilde{\tau}_{0}(u)$.

The configuration potential can be restated as:
$\mathcal{P}(C,\mathcal{S})=\sum_{u\in V(G_{\mathcal{S}}{})}\beta_{u}$. If
$C^{{}^{\prime}}(u)=0$, then $\beta_{u}=-C(u)\cdot\tilde{\tau}_{0}(u)$, which
is at most $0$. If $C^{{}^{\prime}}(u)=1$, then
$\beta_{u}\leq({\tau}_{0}(u)-1)-\tilde{\tau}_{0}(u)$, which is at most $-1/2$.
This concludes the proof. ∎

#### Decrease of potential.

We show that from any configuration $C$, the potential decreases by at least
$1/2$ every step until a fixed point or a 2-cycle is reached. Thus, the
dynamics converges in at most $8m-2n$ steps.

######  Lemma 5.2.

Let $C$ be an arbitrary configuration of $\mathcal{S}$. Let
$\Delta(\mathcal{S})=\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})$
denote the change of configuration potential from $C$ to $C^{{}^{\prime}}$.
Then $\Delta(\mathcal{S})=0$ if and only if $C=C^{{}^{\prime\prime}}$, that is
$C$ is a fixed point or is part of a $2$-cycle $C\longleftrightarrow
C^{{}^{\prime}}$. Furthermore, if $C\neq C^{{}^{\prime\prime}}$ (i.e., the
dynamics has not converged), then, the configuration potential has decreased
by at least $1/2$, i.e., $\Delta(\mathcal{S})\leq-1/2$.

###### Proof (sketch).

We define the change of potential for an edge $e=(u,v)$ as
$\Delta(e)=\mathcal{P}(C^{{}^{\prime}},e)-\mathcal{P}(C,e)$, and the change of
potential for a vertex $u$ as
$\Delta(u)=\mathcal{P}(C^{{}^{\prime}},u)-\mathcal{P}(C,u)$. Then,

$\displaystyle\Delta(\mathcal{S})$
$\displaystyle=\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})=\sum_{e\in
E(G_{\mathcal{S}}{})}\Delta(e)-\sum_{u\in V(G_{\mathcal{S}}{})}\Delta(u)$

Rearranging terms from the definition of potentials, we get

$\Delta(e)=C^{{}^{\prime}}(u)\cdot[C^{{}^{\prime\prime}}(v)-C(v)]+C^{{}^{\prime}}(v)\cdot[C^{{}^{\prime\prime}}(u)-C(u)]$
(4)

and

$\Delta(u)=[C^{{}^{\prime\prime}}(u)-C(u)]\cdot\tilde{\tau}_{0}(u)$ (5)

Now we argue that $\Delta(\mathcal{S})=0$ iff $C=C^{{}^{\prime\prime}}$. First
suppose that $C=C^{{}^{\prime\prime}}$, so that for every vertex $u$,
$C(u)=C^{{}^{\prime\prime}}(u)$. Consequently, $\Delta(e)=0$, $\forall e\in
E(G_{\mathcal{S}}{})$ and $\Delta(u)=0$, $\forall u\in V(G_{\mathcal{S}}{})$.
Now suppose that $C\neq C^{{}^{\prime\prime}}$. Let $V_{0-1}$ denote the set
of vertices $u$ such that $C(u)=0$ and $C^{{}^{\prime\prime}}(u)=1$.
Similarly, let $V_{1-0}$ denote the set of vertices $u$ such that $C(u)=1$ and
$C^{{}^{\prime\prime}}(u)=0$. We establish the following two equalities:

$\sum_{u\in V(G_{\mathcal{S}}{})}\Delta(u)=\sum_{u\in
V_{0-1}}\tilde{\tau}_{0}(u)-\sum_{u\in V_{1-0}}\tilde{\tau}_{0}(u)$ (6)

and

$\sum_{e\in E(G_{\mathcal{S}}{})}=\left(\sum_{u\in V_{0-1}}\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)-\left(\sum_{u\in V_{1-0}}\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)$ (7)

where $E_{u}$ is the set of edges incident on $u$. Recall that
$\Delta(\mathcal{S})$ equals the change in edge potentials minus the change in
vertex potentials, so by (i) and (ii) above,

$\displaystyle\small\Delta(\mathcal{S})$ $\displaystyle=\sum_{u\in
V_{0-1}}\left(\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)-\tilde{\tau}_{0}(u)\right)+\sum_{u\in
V_{1-0}}\left(\tilde{\tau}_{0}(u)-\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)\right)$

We argue that if $u\in V_{0-1}$, then:

$\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\leq\tau_{0}(u)-1=\tilde{\tau}_{0}(u)-\frac{1}{2}$ (8)

and thus $\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)-\tilde{\tau}_{0}(u)\leq-\frac{1}{2}$.
Likewise, if $u\in V_{1-0}$, then:

$\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\geq\tau_{0}(u)=\tilde{\tau}_{0}(u)+\frac{1}{2}$ (9)

and thus $\tilde{\tau}_{0}(u)-\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\leq-\frac{1}{2}$. Since $V_{0-1}\cup
V_{1-0}\neq\emptyset{}$, we have

$\Delta(\mathcal{S})\leq-\sum_{u\in V_{0-1}}\frac{1}{2}-\sum_{u\in
V_{1-0}}\frac{1}{2}\leq-\frac{1}{2}$ (10)

and the lemma follows. ∎

The above discussion establishes that starting from an arbitrary configuration
of $\mathcal{S}$, the dynamics stabilizes in $O(m)$ steps. Our convergence
time results for the SN synchronous anti-coordination games follow
immediately. In the Appendix, we also show that the above proof can be easily
extended to SE-SyACG.

######  Theorem 5.3.

For SN-SyACG and SE-SyACG, starting from any initial action profile, the
dynamics converges in $O(m)$ steps.

#### Remark.

The polynomial-time convergence (to either an NE or a 2-cycle) for SE-SyACG
does not contradict the results in the previous section where we showed that
determining if a SE-SyACG has an NE is hard. In particular, despite the fast
convergence to a limit cycle, the limit cycle will often be a 2-cycle.

##  6 Experimental Studies

We conduct experiments to study the contrast between the empirical convergence
time of synchronous anti-coordination games under the two modes (SN and SE) on
networks with varying structures, shown in Table 2. Specifically, astroph,
google+ and Deezer are real-world social networks [33, 23, 22], and synthetic
networks from the classes Gnp, scale-free [7], and small-world [38]. Further,
we investigate the contrast in the number of Nash equilibria for small problem
instances under the two modes.

All experiments were conducted on Intel Xeon(R) Linux machines with 64GB of
RAM. Source code, documentation, and selected networks appear in the code
supplement.

###  6.1 Experimental results on convergence

Convergence time on networks. For each network, we randomly generate $200$
copies of threshold assignments, where $\tau_{1}(u)$ is chosen uniformly at
random in the range $[1,d(u)+1]$ for the SE mode, and in the range $[1,d(u)]$
for the SN mode. This gives us $200$ problem instances for each network. Next,
for each instance, we construct random initial configurations using various
probabilities $p$ of each vertex having state $0$. In particular, we vary
$p=0.1,0.3,...,0.9$, and for each $p$, we generate $500$ random initial
configurations. This gives us $2,500$ initial configurations for each instance
and a total of $500,000$ simulations of the dynamics on each network. The
average number of steps to converge are shown in Table 2. Note that this
average for all the examined networks is less than $20$ for both modes.
Further, the maximum number of steps (over all simulations) for the SE and SN
modes are $53$ and $24$ respectively.

Network | $n$ | $m$ | Avg. steps (SE) | Avg. steps (SN)
---|---|---|---|---
Small-world | 10,000 | 90,000 | 14.41 | 12.71
Scale-free | 10,000 | 97,219 | 12.78 | 11.66
Gnp | 10,000 | 99,562 | 13.09 | 12.71
astroph | 17,903 | 196,972 | 17.31 | 13.72
google+ | 23,613 | 39,182 | 7.36 | 7.05
Deezer | 28,281 | 92,752 | 14.41 | 12.29

Table 2: Convergence for different networks. Average number of time steps for
the best-response dynamics to converge to a NE or a 2-cycle under the SE and
SN modes.

Impact of network density on convergence time. We study the contrast in the
average convergence time between the two modes under different network
densities. Specifically, we simulate the dynamics on Gnp networks of size
$10,000$, with average degrees varying from $5$ to $100$. The results appear
in Fig. 2. The variances of the two modes are shown as shaded regions, with
one stdev above and below the mean. Overall, as the network density increases,
we observe a close to linear increase in the convergence time and the variance
for the SE mode. In contrast, the convergence time and the variance for the SN
mode change marginally.

Figure 2: Impact of network density on the average number of steps for the SE
and SN modes to converge. The underlying Gnp networks have $10,000$ vertices
with average degrees varying from $5$ to $100$. The variances for the SE and
the SN modes are shown in the beige and blue shaded regions, respectively.

To gain additional insight, we computed the average (over all pairs of
consecutive steps) number $\overline{n}$ of vertices whose states change every
$2$ steps until convergence. As suggested by Lemma 5.2 in section 5, a higher
$\overline{n}$ implies a faster decrease in the system potential. Overall, the
value of $\overline{n}$ for the SE mode and SN mode are $312.24$ and $544.4$,
respectively. This provides one reason for the observed difference in the
convergence time between the two modes. Further, the maximum convergence time
over all simulations for the SE mode is $186$, whereas that for the SN mode is
only $25$.

###  6.2 Experimental results on NE existence

As we have shown, determining whether a game has an NE is intractable for the
SE mode but easy for the SN mode. Here, we compare the number of NE in small
instances between the two modes. In particular, we construct $100$ Gnp
networks of size $20$ with average degrees of $4$. For each Gnp network, we
construct $200$ different threshold assignments where $\tau_{1}(u)$ is
selected uniformly at random in range $[1,d(u)]$. This gives us a total of
$20,000$ instances for each mode. Lastly, for each instance, we check all
$2^{20}$ possible configurations and count the number of NE among them.

Figure 3: The distribution of the number of instances with at most 28 NE. The
underlying Gnp networks are of size $20$ with an average degree of $4$.

The contrast in the number of NE. For the SE mode, $710$ instances have NE.
Among these $710$ instances, $706$ have exactly one NE each, and the remaining
$4$ instances have $2$ NE each. In contrast, all the $20,000$ instances for
the SN mode have at least one NE, and the average number of NE per instance is
$7.26$. Specifically, $75.61\%$ of the SN instances have at most $9$ NE, and
$98\%$ have at most $28$ NE. For $1\leq\eta\leq 28$, the number of instances
with $\eta$ NE is shown in Fig. 3. This shows a contrast in the number of NE
for the two modes. Further, most configurations that are NE under the SN mode
are no longer NE under the SE mode.

##  7 Conclusions and Future Work

We studied the problem of finding Nash equilibria in evolutionary anti-
coordination games. We also considered the convergence problem for such games.
Our results present a contrast between the self essential (SE) and self non-
essential (SN) modes w.r.t. the complexity of finding NE. Further, we
rigorously established an upper bound on the convergence time for both modes
by showing that the best-response dynamics reaches a limit cycle in a
polynomial number of steps. One possible future direction is to tighten the
bound on convergence time as the empirical convergence time is much smaller
than the theoretical bound. Another direction is to study the problem of
finding an approximate NE [15] for the SE anti-coordination games, since
finding an exact NE is hard under the SE mode. Lastly, it is also of interest
to examine the existence of other forms of NE such as mixed-strategy
equilibria in anti-coordination games.

## References

  * [1] Elie M Adam, Munther A Dahleh, and Asuman Ozdaglar.  On the behavior of threshold models over finite networks.  In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 2672–2677. IEEE, 2012.
  * [2] Elie M Adam, Munther A Dahleh, and Asuman Ozdaglar.  On threshold models over finite networks.  preprint arXiv:1211.0654, 2012.
  * [3] Martin Aleksandrov and Toby Walsh.  Pure Nash equilibria in online fair division.  In IJCAI, pages 42–48, 2017.
  * [4] W Brian Arthur.  Inductive reasoning and bounded rationality.  The American economic review, 84(2):406–411, 1994.
  * [5] Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Persiano.  Generalized discrete preference games.  In IJCAI, volume 16, pages 53–59, 2016.
  * [6] Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab Seyed Mirrokni, and Alexander Skopalik.  Fast convergence to nearly optimal solutions in potential games.  In Proceedings of the 9th ACM conference on Electronic commerce, pages 264–273, 2008.
  * [7] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [8] Chris Barrett, Harry B Hunt Iii, Madhav V Marathe, SS Ravi, Daniel J Rosenkrantz, and Richard E Stearns.  On some special classes of sequential dynamical systems.  Annals of Combinatorics, 7(4):381–408, 2003.
  * [9] Christopher L Barrett, Harry B Hunt III, Madhav V Marathe, SS Ravi, Daniel J Rosenkrantz, and Richard E Stearns.  Complexity of reachability problems for finite discrete dynamical systems.  JCSS, 72(8):1317–1345, 2006.
  * [10] Yann Bramoullé.  Anti-coordination and social interactions.  Games and Economic Behavior, 58(1):30–49, 2007.
  * [11] Damien Challet and Matteo Marsili.  Relevance of memory in minority games.  Physical Review E, 62(2):1862, 2000.
  * [12] Thorsten Chmura and Thomas Pitz.  Successful strategies in repeated minority games.  Physica A: Statistical Mechanics and its Applications, 363(2):477–480, 2006.
  * [13] George Christodoulou, Vahab S Mirrokni, and Anastasios Sidiropoulos.  Convergence and approximation in potential games.  In STACS, pages 349–360. Springer, 2006.
  * [14] Vincent Conitzer and Tuomas Sandholm.  Complexity results about nash equilibria.  In Georg Gottlob and Toby Walsh, editors, IJCAI-03, pages 765–771. Morgan Kaufmann, 2003.
  * [15] Tomas Feder, Hamid Nazerzadeh, and Amin Saberi.  Approximating nash equilibria using small-support strategies.  In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 352–354, 2007.
  * [16] Syed Md Galib and Irene Moser.  Road traffic optimisation using an evolutionary game.  In GECCO-13, pages 519–526, 2011.
  * [17] Robert Gibbons.  A primer in game theory.  Harvester Wheatsheaf New York, 1992.
  * [18] Eric Goles and Servet Martinez.  Neural and automata networks: dynamical behavior and applications, volume 58.  Springer Science & Business Media, 2013.
  * [19] Samuel Ieong, Robert McGrew, Eugene Nudelman, Yoav Shoham, and Qixiang Sun.  Fast and compact: A simple class of congestion games.  In AAAI, volume 5, pages 489–494, 2005.
  * [20] Matthew O Jackson and Yves Zenou.  Games on networks.  In Handbook of game theory with economic applications, volume 4, pages 95–163. Elsevier, 2015.
  * [21] Jeremy Kun, Brian Powers, and Lev Reyzin.  Anti-coordination games and stable graph colorings.  In International Symposium on Algorithmic Game Theory, pages 122–133. Springer, 2013.
  * [22] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2–es, 2007.
  * [23] Jure Leskovec and Julian Mcauley.  Learning to discover social circles in ego networks.  Advances in neural information processing systems, 25, 2012.
  * [24] Yi Li, Rick Riolo, and Robert Savit.  Evolution in minority games.(ii). games with variable strategy spaces.  Physica A: Statistical Mechanics and its Applications, 276(1-2):265–283, 2000.
  * [25] Jona Linde, Joep Sonnemans, and Jan Tuinstra.  Strategies and evolution in the minority game: A multi-round strategy experiment.  Games and economic behavior, 86:77–95, 2014.
  * [26] Siu Ming Lo, Hui-Chi Huang, Peng Wang, and KK Yuen.  A game theory based exit selection model for evacuation.  Fire Safety Journal, 41(5):364–369, 2006.
  * [27] Radu Manuca, Yi Li, Rick Riolo, and Robert Savit.  The structure of adaptive competition in minority games.  Physica A: Statistical Mechanics and its Applications, 282(3-4):559–608, 2000.
  * [28] Dov Monderer and Lloyd S Shapley.  Potential games.  Games and economic behavior, 14(1):124–143, 1996.
  * [29] Henning Mortveit and Christian Reidys.  An introduction to sequential dynamical systems.  Springer Science & Business Media, 2007.
  * [30] Noam Nissan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors.  Algorithmic Game Theory.  Cambridge University Press, New York, NY, 2007.
  * [31] Pouria Ramazi, James Riehl, and Ming Cao.  Networks of conforming or nonconforming individuals tend to reach satisfactory decisions.  Proceedings of the National Academy of Sciences, 113(46):12985–12990, 2016.
  * [32] Daniel J Rosenkrantz, Madhav V Marathe, S. S. Ravi, and Richard E Stearns.  Synchronous dynamical systems on directed acyclic graphs (dags): Complexity and algorithms.  In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 11334–113432, 2021.
  * [33] Benedek Rozemberczki and Rik Sarkar.  Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models.  In Proceedings of the 29th ACM international conference on information & knowledge management, pages 1325–1334, 2020.
  * [34] Arto Salomaa.  On essential variables of functions, especially in the algebra of logic.  Mathematica, 339:1–11, 1963.
  * [35] Sunil Simon and Dominik Wojtczak.  Constrained pure Nash equilibria in polymatrix games.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
  * [36] Arne Traulsen, Dirk Semmann, Ralf D Sommerfeld, Hans-Jürgen Krambeck, and Manfred Milinski.  Human strategy updating in evolutionary games.  Proceedings of the National Academy of Sciences, 107(7):2962–2966, 2010.
  * [37] Martina Vanelli, Laura Arditti, Giacomo Como, and Fabio Fagnani.  On games with coordinating and anti-coordinating agents.  IFAC-PapersOnLine, 53(2):10975–10980, 2020.
  * [38] Duncan J Watts and Steven H Strogatz.  Collective dynamics of ‘small-world’networks.  nature, 393(6684):440–442, 1998.
  * [39] H Peyton Young.  The evolution of social norms.  Economics, 7(1):359–387, 2015.

Appendix

Symbols | Definition
---|---
SACG | Sequential anti-coordination games
SyACG | Synchronous anti-coordination games
SE | Self essential
SN | Self non-essential
SE-SACG | Sequential anti-coordination games under self essential mode
SN-SACG | Sequential anti-coordination games under self non-essential mode
SE-SyACG | Synchronous anti-coordination games under self essential mode
SN-SyACG | Synchronous anti-coordination games under self non-essential mode
SDS | Sequential dynamical system
SyDS | Synchronous dynamical system
IT | Inverted threshold
(SE, IT)-SDS | Sequential dynamical system under self essential mode
(SN, IT)-SDS | Sequential dynamical system under self non-essential mode
(SE, IT)-SyDS | Synchronous dynamical system under self essential mode
(SN, IT)-SyDS | Synchronous dynamical system under self non-essential mode
$\mathcal{S}=(G_{\mathcal{S}}{},\mathcal{F})$ |  A SyDS $\mathcal{S}$ with underlying graph $G_{\mathcal{S}}{}$ and set of local functions $\mathcal{F}$
$\mathcal{S^{\prime}}=(G_{\mathcal{S}^{\prime}},\mathcal{F},\Pi)$ |  An SDS $\mathcal{S}^{\prime}$ where $\Pi$ is the vertex update sequence
$n$ |  The number of vertices in $G_{\mathcal{S}}{}$
$m$ |  The number of edges in $G_{\mathcal{S}}{}$
$f_{v}$ |  Local function of $v$
$\tau_{1}(v)$ |  For vertex $v$, the threshold value on the number of 0’s for $f_{v}$ to equal $1$
$\tau_{0}(v)$ |  For vertex $v$, the threshold value on the number of 1’s for $f_{v}$ to equal $0$
$N(v)$ |  The open neighborhood of $v$, i.e., the set of vertices adjacent to $v$
$N^{+}(v)$ |  The closed neighborhood of $v$, i.e., the set of vertices adjacent to $v$ and $v$ itself
$d(v)$ |  The degree of $v$
$C$ |  A configuration of $\mathcal{S}$
$C^{\prime}$ |  The successor of $C$
$C^{\prime\prime}$ |  The successor of $C^{\prime}$
$C(v)$ |  The state of $v$ in configuration $C$ of $\mathcal{S}$

Table 3: Symbols and Notation.

#### Remark.

Note that $\tau_{1}(v)$ uniquely determines $\tau_{0}(v)$. In particular,
$\tau_{0}(v)+\tau_{1}(v)=d(v)+2$ for the self essential mode, and
$\tau_{0}(v)+\tau_{1}(v)=d(v)+1$ for the self non-essential mode. Based on the
mapping between anti-coordination games and discrete dynamical systems, we
present all proofs in the context of dynamical systems.

## A Detailed Discussion of Related Work

It is known that the self non-essential sequential anti-coordination games are
potential games, and by the argument from Monderer and Shapley [28], such a
game always has an NE. In particular, a potential game admits a potential
function that increases when an agent chooses an action that yields a strictly
higher payoff [28]. Given a potential game starting from an initial action
profile, consider the sequence of profiles such that at each step, a player
updates its action to obtain a strictly higher payoff (if possible). Such a
sequence is called an improvement path, and for potential games, all the
improvement paths are of finite length (known as the finite improvement
property). More importantly, a maximal improvement path (i.e., an improvement
path that goes to a maximum of the potential) always ends at an equilibrium
point [28]. Note that this result does not immediately imply that an NE can be
reached in polynomial time, as the number of possible action profiles is
exponential in the number of agents. Further, we emphasize that anti-
coordination games under synchronous update schemes are not potential games as
limit cycles of length $2$ exist.

The book by Goles and Martinez [18] discussed the phase space properties of
dynamical systems, and one can verify that such systems also model
coordination games. In particular, they prove that for synchronous
coordination games, the length of any limit cycle is at most $2$. Their
argument uses a mathematical tool called algebraic invariants, and they show
that if we consider each limit cycle as a periodical sequence, then the length
of such a sequence is either $1$ or $2$. In the same work, Goles and Martinez
proposed a Lyapunov function for synchronous coordination games and show that
the best-response dynamics of the game converges to a limit cycle of length at
most $2$ in a polynomial number of steps. For anti-coordination games, Barrett
et al. ([8]) study phase space properties of sequential dynamical systems
(which includes modeling sequential AC games). Their results imply that when
local functions are nad’s and nor’s (which are inverted-threshold functions),
the length of a limit cycle in a self essential sequential anti-coordination
game can be $2^{O(\sqrt{n})}$ where $n$ is the number of agents. Later, Adam
et al. [2] use a combinatorial approach and argue that the length of a limit
cycle in a synchronous anti-coordination game is at most $2$. However, they
did not bound the convergence time to reach a limit cycle.

A more recent work by Ramazi, Riehl, and Cao [31] study the convergence time
for asynchronous self non-essential anti-coordination games. In their
asynchronous dynamics, agents are updated at each step in a random order, and
for each agent, the number of steps between any two consecutive updates is
guaranteed to be finite. Based on this scheme, they show that under the best-
response dynamics, an equilibrium is always reached in finite time.

## Additional Material for Section 4

In this section, we present the detailed proofs of the results given in
section 4 of the main manuscript. We start with a key observation:

######  Observation 4.1.

A SyDS and an SDS with the same underlying graph and the same set of local
functions have the same set of fixed points.

Consequently, SN-SyACG (SE-SyACG) and SN-SACG (SE-SACG) have the same
complexity for EQE / EQF.

## 4.1 Intractability for the self essential mode

We establish that Equilibrium existence (EQE) is NP-hard for self essential
synchronous anti-coordination games (SE-SyACG), and the problem remains hard
on bipartite graph. Further, the corresponding counting problem is
#P-complete. This immediately implies that Equilibrium finding (EQF) is also
hard for SE-SyACG. In particular, Let $\mathcal{S}$ be a (SE, IT)-SyDS that
models a SE-SyACG. We show that determining the existence of a fixed point of
$\mathcal{S}$ is intractable. By Observation 4.1, it follows that EQE / EQF is
also hard for SE-SACG. We now proceed with the proof.

######  Observation 4.2.

Suppose that a vertex $v$ of a (SE, IT)-SyDS $\mathcal{S}$ has threshold
$\tau_{1}(v)=1$. Then in every fixed point (if any exists) $C$ of
$\mathcal{S}$, $C(v)=1$ and at least one neighbor of $v$ has state $0$ in $C$.

######  Observation 4.3.

Suppose that a vertex $v$ of a (SE, IT)-SyDS $\mathcal{S}$ has threshold
$\tau_{1}(v)=d(v)$. Then in every fixed point (if any exists) $C$ of
$\mathcal{S}$, if $C(v)=1$, then then all neighbors of $v$ have state 0 in
$C$, and if $C(v)=0$, then at least two neighbors of $v$ have state $1$ in
$C$.

######  Lemma 4.4.

Let $\mathcal{S}$ be a (SE, IT)-SyDS whose underlying graph
$G_{\mathcal{S}}{}$ is a complete bipartite graph of the form:

  1. a.

The bipartitions $V(G_{\mathcal{S}}{})=\\{A,B\\}$.

  2. b.

$|A|=|B|=3$.

  3. c.

$\tau_{1}(v)=3,\;\forall v\in V(G_{\mathcal{S}}{})$.

The phase space of $\mathcal{S}$ has only $2$ distinct fixed points for which
either $(i)$ vertices in $A$ are in state $1$, and vertices in $B$ are in
state $0$, or $(ii)$ vice versa.

Figure 4: An example (SE, IT)-SyDS $\mathcal{S}$ for Lemma 4.4, where
$G_{\mathcal{S}}{}$ is a complete bipartite graph with bipartitions
$\\{A,B\\}$. The thresholds $\tau_{1}$ of all vertices are $3$.

###### Proof.

By the threshold values of vertices in $A$ and in $B$, it is easy to see that
the two configurations given in the Lemma are fixed points. We now argue that
the system has no other fixed points. Let $C$ be a configuration of
$\mathcal{S}$ that is different from the two fixed points above. Let
$C^{\prime}$ be the successor of $C$. We first consider the case where both
$A$ and $B$ have at least one state-$1$ vertex under $C$. Let $v\in A$ be such
a vertex in state $1$ under $C$. Note that since $B$ has at least one
state-$1$ vertex, the number of state-$0$ vertices in $v$’s closed
neighborhood is at most $|B|-1<\tau_{1}(v)$. Thus, we have $C^{\prime}(v)=0$
and $C$ is not a fixed point. Next, we consider the case where both $A$ and
$B$ have at least one state-$0$ vertex under $C$. Let $v$ and $w$ be two
state-$0$ vertices in $A$ and $B$, respectively. Since $\tau_{1}(u)=3$,
$\forall u\in V(G_{\mathcal{S}}{})$, $C(v)=0$ implies that there exists at
least two state-$1$ vertex in $B$. Similarly, $C(w)=0$ implies that there
exists at least two state-$1$ vertex in $A$. By our previous argument, it
follows that $C$ is not a fixed point. This concludes the proof. ∎

We now present the Theorem on the intractability of EQE for SE-SyACG.

######  Theorem 4.2.

For SE-SyACG, the Equilibrium existence(EQE) is NP-complete and the counting
problem #EQE is #P-complete. Further, the problem remains hard on bipartite
graphs.

###### Proof.

One can easily verify that the problem is in NP. We now establish the NP-
hardness of EQE via a reduction from 3SAT. Let $f$ be the formula for an
arbitrary 3SAT instance. We construct a SyDS $\mathcal{S}$ such that
$\mathcal{S}$ has a vertex for each literal, a vertex for each clause, and a
collection of gadgets. Further, $\mathcal{S}$ is constructed so that there is
a one-to-one correspondence between fixed points of $\mathcal{S}$ and
satisfying assignments to the given 3SAT formula $f$.

Literal vertices. For each variable $x_{i}$ in $f$, there is a positive
literal vertex $y_{i}$ and a negative literal vertex $z_{i}$ in $\mathcal{S}$.
Both these vertices have threshold $\tau_{1}(y_{i})=\tau_{1}(z_{i})=3$. Under
any configuration, we interpret positive literal vertex $y_{i}$ having state 0
as corresponding to variable $x_{i}$ being true, and negative literal vertex
$z_{i}$ having value 0 as corresponding to variable $x_{i}$ being false. Our
Gadgets (shown later) ensure that in any fixed point of $\mathcal{S}$, these
two vertices have complementary values.

Clause vertices. For each clause $c_{j}$ in $f$, there is a clause vertex
$w_{j}$, $\tau_{1}(w_{j})=1$. Further, $w_{j}$ is adjacent to each of the
literal vertices that correspond to literals occurring in clause $c_{j}$.
There is no other edges incident on $w_{j}$. From Observation 4.2, in every
fixed point of $\mathcal{S}$, $w_{j}$ has state 1, and at least one of the
adjacent literal vertices has state 0.

Gadgets. We now construct the gadgets, which involve auxiliary vertices for
the literal vertices, as follows. For each variable $x_{i}$ in $f$, there are
three auxiliary vertices, namely $a_{i}$, $d_{i}$ and $e_{i}$. In particular,

  1. $(i)$

The vertex $a_{i}$ is adjacent to both $x_{i}$’s positive literal vertex
$y_{i}$ and negative literal vertex $z_{i}$. Further, $\tau_{1}(a_{i})=1$.
From Observation 4.2, in every fixed point of $\mathcal{S}$, $a_{i}$ has state
1, and at least one of the two literal vertices $y_{i}$ and $z_{i}$ has state
0.

  2. $(ii)$

The vertex $d_{i}$ and $e_{i}$ has threshold $\tau_{1}(d_{i})=1$ and
$\tau_{1}(e_{i})=3$, respectively. Further, we introduce three auxiliary edges
$(e_{i},d_{i})$, $(e_{i},y_{i})$ and $(e_{i},z_{i})$. From Observation 4.2, in
every fixed point, $d_{i}$ has state 1, thus, its neighbor $e_{i}$ has state
0. Then, from an application of Observation 4.3 to vertex $e_{i}$, at least
one of the two literal vertices $y_{i}$ and $z_{i}$ has state 1.

The combined effect of the auxiliary vertices and edges described thus far is
that under every fixed point of $\mathcal{S}$, exactly one of $y_{i}$ and
$z_{i}$ has state 0, and exactly one has state 1.

Finally, for every literal vertex (positive or negative), denoted by $v$, we
add an auxiliary structure based on the bipartite graph in Lemma 4.4. The
structure involves five auxiliary vertices: $g_{v}^{1}$, $g_{v}^{2}$,
$h_{v}^{1}$, $h_{v}^{2}$, and $h_{v}^{3}$, each with threshold $\tau_{1}=3$
(which is the degree of each of these vertices). Consider the subsets
$A_{v}=\\{v,h_{v}^{1},h_{v}^{2}\\}$ and
$B_{v}=\\{g_{v}^{1},g_{v}^{2},g_{v}^{3}\\}$. The structure has the following
nine auxiliary edges: $(v,h_{v}^{1})$, $(v,h_{v}^{2})$, $(v,h_{v}^{3})$,
$(g_{v}^{1},h_{v}^{1})$, $(g_{v}^{1},h_{v}^{2})$, $g_{v}^{1},h_{v}^{3})$,
$(g_{v}^{2},h_{v}^{1})$, $(g_{v}^{2},h_{v}^{2})$, $(g_{v}^{2},h_{v}^{3})$.
That is, the subgraph of $\mathcal{S}$ induced on $A_{v}\cup B_{v}$ is a
complete bipartite graph with bipartitions $A_{v}$ and $B_{v}$.

By Lemma 4.4, that in any fixed point of $\mathcal{S}$, either all the
vertices in $A_{v}$ have state $1$ and all the vertices in $B_{v}$ have state
0, or vice versa. To see this, first suppose that in a given fixed point $C$,
at least one of the vertices in $B_{v}$ has state 1. Then, from Observation
4.3, the three neighbors of this vertex, namely the three vertices in $A_{v}$,
all have state 0. Consequently, since the threshold of each vertex in $B_{v}$
is 3, all three vertices in $B_{v}$ have value 1. Now suppose that none of the
vertices in $B_{v}$ has value 1, i.e., they all have value 0. Since the
threshold of each vertex in $A_{v}$ is 3, all three vertices in $A_{v}$ have
value 1.

This completes the construction of $\mathcal{S}$ which clearly takes
polynomial time. Further, the resulting graph is bipartite. We now claim that
there is a one-to-one correspondence between fixed points of $\mathcal{S}$ and
satisfying assignments of $f$.

  * $(\Rightarrow)$

Let $\alpha$ be a satisfying assignment of $f$. We construct a configuration
$C_{\alpha}$ of $\mathcal{S}$ as follows. For each variable under $\alpha$, if
$\alpha[x_{i}]=\textsc{true}$, then the positive literal vertex $y_{i}$ has
the state $C_{\alpha}(y_{i})=0$, and the negative literal vertex $z_{i}$ has
the state $C_{\alpha}(z_{i})=1$. On the other hand, if If
$\alpha[x_{i}]=\textsc{false}$, then $C_{\alpha}(y_{i})=1$ and
$C_{\alpha}(z_{i})=0$. Further, every clause vertex $w_{j}$ has state 1. As
for the states of auxiliary vertices for each $x_{i}$, we set $a_{i}$ and
$d_{i}$ to state 1, and $e_{i}$ to state $0$. Lastly, for each literal vertex
$v$, the other two members of $A_{v}$ have the same value as $v$, and the
three members of $B_{v}$ have the complement of the value of $v$ under $C$.
This completes the specification of $C_{\alpha}$. By checking the number of
state-$0$ vertices in the closed neighborhood of each vertex, it can be
verified that $C_{\alpha}$ is a fixed point of $\mathcal{S}$.

  * $(\Leftarrow)$

Let let $C$ be a fixed point of $\mathcal{S}$. Let $\alpha_{C}$ be the
assignment to $f$ where $\alpha_{C}(x_{i})=1$ iff $C_{\alpha}[y_{i}]=0$. Since
$C$ is a fixed point, every clause vertex is adjacent to at least one literal
vertex with the value 0. Thus, $\alpha_{C}$ is a satisfying assignment of $f$.

We now have established that determining if $\mathcal{S}$ has a fixed point is
NP-complete, even when the underlying graph is bipartite. Further, it can be
verified that $C=C_{\alpha_{C}}$, so the reduction is parsimonious. The NP-
hardness of EQE and the #P-hardness of the counting version #EQE for SE-SyACG
immediately follows. This concludes the proof. ∎

######  Corollary 4.5.

For SE-SACG, the Equilibrium existence(EQE) is NP-complete and the counting
problem #EQE is #P-hard. Further, the problem remains hard on bipartite
graphs.

#### Remark.

A fixed point under the SE mode is generally not a fixed point under the SN
mode. Therefore, the above hardness result does not imply a hardness of EQE
for the SN anti-coordination games.

## 4.2 Finding NE under the self non-essential mode

As pointed out in [37], a self non-essential sequential anti-coordination game
(SN-SACG) always has a pure Nash equilibrium (NE). By Observation 4.1, a self
non-essential synchronous anti-coordination game (SN-SyACG) also always has an
NE. In this section, we explore beyond the existence problem and tackle the
problem of finding an NE in a for SN mode under arbitrary network topology
(i.e., EQF). In particular, inspired by the potential function approach
developed in [9], given a (SN, IT)-SDS $\mathcal{S}^{\prime}$ (modeling a SN-
SACG), we show that starting from an arbitrary configuration, a fixed point of
$\mathcal{S}^{\prime}$ is always reached in at most $3m-n$ steps. Since each
step of $\mathcal{S}^{\prime}$ can be carried out in $O(m)$ time, a fixed
point of $\mathcal{S}^{\prime}$ is then found in $O(m^{2})$ time.
Consequently, a fixed point of a (SN, IT)-SyDS $\mathcal{S}$ (modeling a SN-
SyACG) can also be founded in $O(m^{2})$ time.

We note that our results does not follow from [9] since $(i)$ we study anti-
coordination games, and the results in [9] are for coordination games; $(ii)$
in the self non-essential mode, each vertex does not consider its own state
while playing the game, whereas [9] focuses on the case where its own state is
considered by each vertex.

If $\tau_{1}(v)=0$ or $\tau_{1}(v)=d_{v}+1$ for some vertex $v$, then $v$ is a
vertex whose state is constant after at most one transition. Thus, we can
remove $v$ from the graph and update the threshold of neighbors
correspondingly without affecting system dynamics. Without loss of generality,
we assume that there are no constant vertices, that is $1\leq\tau_{1}(v)\leq
d(v)$, $\forall v\in V(G_{\mathcal{S}^{\prime}})$.

### The potential functions and bounds

Let
$\mbox{$\mathcal{S}$}^{\prime}=(G_{\mathcal{S^{\prime}}}{},\mathcal{F}^{\prime},\Pi)$
be a (SN, IT)-SDS that models a SN-SACG. Given a configuration $C$, We now
define the potentials of vertices, edges, and the system under $C$.

The vertex potential. Given a vertex $u\in V(G_{\mathcal{S^{\prime}}}{})$, the
potential of $u$ under $C$ is defined as follows

$\displaystyle\mathcal{P}(C,u)=\begin{cases}\tau_{0}(u)&\text{if }C(u)=0\\\
\tau_{1}(u)&\text{if }C(u)=1\\\ \end{cases}$

The edge potential. Given an edge $e=(u,v)\in E(G_{\mathcal{S^{\prime}}}{})$,
the potential of $e$ under $C$ is defined as follows

$\displaystyle\mathcal{P}(C,e)=\begin{cases}1&\text{if }C(u)=C(v)\\\
0&\text{if }C(u)\neq C(v)\\\ \end{cases}$

The configuration potential. The potential of the system
$\mathcal{S}^{\prime}$ under $C$ is defined as the sum of the vertex
potentials and edge potentials over all vertices and edges.

$\mathcal{P}(C,\mathcal{S}^{\prime})=\sum_{u\in
V(G_{\mathcal{S^{\prime}}}{})}\mathcal{P}(C,u)+\sum_{e\in
E(G_{\mathcal{S^{\prime}}}{})}\mathcal{P}(C,e)$

#### A lower bound on the configuration potential.

We first establish a lower bound of the $\mathcal{P}(C,\mathcal{S}^{\prime})$
for any configuration $C$.

######  Lemma 4.3.

For any configuration $C$ of $\mathcal{S}^{\prime}$, we have

$\mathcal{P}(C,\mathcal{S}^{\prime})\geq\left(\sum_{u\in
V(G_{\mathcal{S^{\prime}}}{})}\min\\{\tau_{0}(u),\tau_{1}(u)\\}\right)+\gamma$

where $\gamma$ is the minimum number of edges whose endpoints have the same
color in $G_{\mathcal{S^{\prime}}}{}$, over all 2-coloring of
$V(G_{\mathcal{S^{\prime}}}{})$.

###### Proof.

Given any configuration $C$, since the potential of each vertex is either
$\tau_{1}(u)$ or $\tau_{0}(u)$, it immediately follows that $\sum_{u\in
V(G_{\mathcal{S}}{})}\min\\{\tau_{0}(u),\tau_{1}(u)\\}$ is the lower bound on
the sum of potentials from all vertices.

As for the bound on the sum of edge potentials, remark that $C$ corresponds to
a 2-coloring of $V(G_{\mathcal{S^{\prime}}}{})$ (i.e., each state represents a
color). Thus, the minimum number of edges whose endpoints have the same state
under $C$ is at most $\gamma$. Since each edge with the same-state endpoints
has potential value $1$, it follows that the sum of edge potential under any
configuration $C$ is at least $\gamma$. This concludes the proof. ∎

#### An upper bound on the configuration potential.

Next, we present the upper bound of the configuration potential. Given an
arbitrary configuration $C$

######  Lemma 4.4.

The configuration potential satisfies

$\mathcal{P}(C,\mathcal{S}^{\prime})\leq 3m$

###### Proof.

Observe that under an arbitrary configuration of $\mathcal{S}^{\prime}$, the
sum of vertex potential satisfies

$\sum_{u\in V(G_{\mathcal{S^{\prime}}}{})}\mathcal{P}(C,u)\leq\sum_{u\in
V(G_{\mathcal{S^{\prime}}}{})}\max\\{\tau_{0}(u),\tau_{1}(u)\\}\leq\sum_{u\in
V(G_{\mathcal{S^{\prime}}}{})}d(u)=2m$

As for the sum of edge potential $\sum_{e\in
E(G_{\mathcal{S^{\prime}}}{})}\mathcal{P}(C,e)$, it is easy to see that the
upper bound is $m$. The upper bound of the overall configuration potential
follows immediately. ∎

Overall, We have shown that the gap in the configuration potential between an
arbitrary initial configuration and a system’s converged configuration is at
most

$3m-\sum_{v\in
V(G_{\mathcal{S}}{})}\left(\min\\{\tau_{0}(v),\tau_{1}(v)\\}\right)-\gamma\leq
3m-n$ (11)

### Decrease of the potential after each update

We establish that starting from an arbitrary initial configuration that is not
a fixed point, the configuration potential of $\mathcal{S}^{\prime}$ decreases
by at least $1$ after each vertex switches its state. Given that the potential
gap is at most $3m-n/2$, it follows that the system reaches a fixed point in
at most $3m-n/2$ time steps.

######  Lemma 4.5.

Given a configuration $C$ of $\mathcal{S}^{\prime}$ that is not a fixed point.
Let $\tilde{C}$ be a configuration that results from the state change of a
single vertex $u$ due to the dynamics of $\mathcal{S}^{\prime}$. We then have
$\mathcal{P}(C,\mathcal{S}^{\prime})-\mathcal{P}(\tilde{C},\mathcal{S}^{\prime})\geq
1$.

###### Proof.

Since $u$ is the only vertex that undergoes the state change, the overall
configuration potential is affected by only the change of $u$’s potential and
the potentials of edges incident to $u$. Let $d_{0}(u)$ and $d_{1}(u)$ denote
the number of $u$’s neighbors in state-$0$ and the number of $u$’s neighbors
in state-$1$ under $C$, respectively. Without loss of generality, suppose $u$
changes its state from $C(u)=0$ to $\tilde{C}(u)=1$. Subsequently, the sums of
potentials of $u$ and edges incident to $u$ under $C$ and $\tilde{C}$ are

$\mathcal{P}(C,u)+\sum_{e=(u,v),v\in
N(u)}\mathcal{P}(C,e)=\tau_{0}(u)+d_{0}(u)$

and

$\mathcal{P}(\tilde{C},u)+\sum_{e=(u,v),v\in
N(u)}\mathcal{P}(\tilde{C},e)=\tau_{1}(u)+d_{1}(u)$

respectively. Since $\tilde{C}(u)=1$, it follows that
$d_{0}(u)\geq\tau_{1}(u)$ and $d_{1}(u)\leq\tau_{0}(u)-1$. Therefore, we have

$\displaystyle\mathcal{P}(C,\mathcal{S}^{\prime})-\mathcal{P}(\tilde{C},\mathcal{S}^{\prime})$
$\displaystyle=\mathcal{P}(C,u)+\sum_{e=(u,v),v\in
N(u)}\mathcal{P}(C,e)-\left(\mathcal{P}(\tilde{C},u)+\sum_{e=(u,v),v\in
N(u)}\mathcal{P}(\tilde{C},e)\right)$
$\displaystyle=\tau_{0}(u)+d_{0}(u)-\tau_{1}(u)-d_{1}(u)$ $\displaystyle\geq
1$

This concludes the proof. ∎

In summary, we have shown that the potential gap between any two
configurations is at most $3m-n$. Further, each change of vertex state due to
the system dynamic decreases the overall potential by at least one. Since in
each time step (before reaching a fixed point), at least one vertex updates
its state, Lemma 4.6 immediately follows.

######  Lemma 4.6.

For (SN, IT)-SDS, starting from an arbitrary initial configuration, the system
dynamics reaches a fixed point in at most $3m-n$ time steps.

In each time step, we compute the local functions of all vertices to determine
the successor configuration, which takes $O(m)$ time. Therefore, a fixed point
of $\mbox{$\mathcal{S}$}{}^{\prime}$ can be obtained in $O(m^{2})$ time. Given
that a fixed point of a (SN, IT)-SDS $\mbox{$\mathcal{S}$}{}^{\prime}$ is also
a fixed point of its twin (SN, IT)-SyDS $\mathcal{S}$, we also establish the
tractability of finding an NE for (SN, IT)-SyDS. Our results for SN anti-
coordination games follow.

######  Theorem 4.7.

For both SN-SyACG and SN-SACG, we can find a pure Nash equilibrium of the game
in $O(m^{2})$ time.

## 4.3 Finding Nash equilibria under special cases

We have established the intractability of EQE / EQF for self essential (SE)
anti-coordination games, whereas a self non-essential (SN) game admits a
polynomial time algorithm for finding an NE. In this section, we identify
several special classes of the problem instances such that an NE (if any) can
be found in polynomial time for SE anti-coordination games. Further, We extend
the results of some special classes to SN anti-coordination games such that an
NE can be found in linear time. Based on the connection between anti-
coordination games and dynamical systems, we present all proofs in the context
of synchronous dynamical systems (and the results for sequential systems
follow).

### Inclination for one action over another

We consider the special case where agents are inclined to choose one action
over the other. Specifically, during the game evolution, each agent $u$ either
$(i)$ chooses the action $1$ in the next time step if at least one agent in
$u$’s open/closed neighborhood chose action $0$ in the previous time step;
$(ii)$ chooses the action $0$ in the next time step if at least one agent in
$u$’s open/closed neighborhood chose action $1$ in the previous time step.

Observe that the case $(i)$ above corresponds to $\tau_{1}(u)=1$. Further, the
case $(ii)$ implies $\tau_{1}(u)=d(v)$ for the SN game, and
$\tau_{1}(u)=d(v)+1$ for the SE game. We call the local function of a vertex
$u$ with $\tau_{1}(u)=1$ a nand function, and of $u$ with $\tau_{1}(u)=d(v)$ /
$\tau_{1}(u)=d(v)+1$ a nor vertex function.

######  Theorem 4.8.

For SE anti-coordination games and SN anti-coordination games, an NE can be
found in $O(m+n)$ time if the corresponding local functions of vertices are
nand’s and nor’s.

###### Proof.

We first present the result for SE-SyACG, modeled by a (SE, IT)-SyDS
$\mbox{$\mathcal{S}$}{}=(G_{\mathcal{S}}{},\mathcal{F})$. Observe that under
any fixed point of $\mathcal{S}$, a nand vertex must be in state 1, and a nor
vertex must be in state 0. This uniquely determines a configuration $C$. We
can then compute $C$’s successor $C^{\prime}$, and examine if $C$ is a fixed
point in $O(m+n)$ time. We further establish the claim below

######  Claim 4.8.1.

Such a configuration $C$ is a fixed point if and only if each nor vertex is
adjacent to at least one nand vertex and vise versa.

For sufficiency, suppose $C$ is a fixed point. If there exists a nor vertex
$v$ whose neighbors are all nor vertices. Then the number of state-0 vertices
in $v$’ closed neighborhood is $d(v)+1$ (since $C$ is a fixed point, all nor
vertices are in state $0$) which equals to the threshold of $v$. Thus,
$C(v)=0\neq C^{\prime}(v)=1$ and $C$ is not a fixed point. An analogous
argument applies to the case where $v$ is a nand vertex whose neighbors are
all nand vertices. Specifically, the number of state-$0$ vertices in $v$’s
closed neighborhood is $0$. Thus, $C(v)=1\neq C^{\prime}(v)=0$. As for the
necessity of the condition, observe that if a nor vertex $v$ is adjacent to at
least one nand vertex, the number of state-$0$ vertices in $v$’s closed
neighborhood is at most $d(v)<\tau_{1}(v)$, thus, $C(v)=C^{\prime}(v)=0$.
Similarly, if a nand vertex $v$ is adjacent to at least one nor vertex, then
the number of state-$0$ vertices in $v$’s closed neighborhood is at least
$\tau_{1}(v)=1$, thus, $C(v)=C^{\prime}(v)=1$. This concludes the proof for
SE-SyACG (and thus also SE-SACG).

We now establish the result for a SN-SyACG, modeled by a (SN, IT)-SyDS,
$\bar{\mathcal{S}}=(G_{\bar{\mathcal{S}}},\mathcal{F})$. Overall, we first
construct a candidate configuration $C$ and then modify $C$ to make it a fixed
point of $\mathcal{S}$. In particular, for each vertex $v\in
V(G_{\bar{\mathcal{S}}})$, if $v$ is a nand vertex (i.e., $\tau_{1}(v)=1$), we
set $C(v)=1$. On the other hand, if $v$ is a nor vertex (i.e.,
$\tau_{1}(v)=d(v)$), set $C(v)=0$. Based on the same argument in Claim 4.8.1,
it follows that $C$ is a fixed point of $\mathcal{S}^{\prime}$ if and only if
each nand vertex is adjacent to at least one nor vertex and visa versa. If
this condition does not hold, however, there must exist at least one nand
(nor) vertex whose neighbors are all nand (nor) vertices. Subsequently, We
further modify $C$ as follows. First, for each nand vertex $v$ whose neighbors
are all in state $1$ under $C$, we set $C(v)=0$. Let $V_{nand}$ denote such a
set of vertices. Further, for each nor vertex $v$ whose neighbors are all in
state $0$ under $C$, we set $C(v)=1$. Let $V_{nor}$ denote this set of
vertices. The pseudocode is shown in Algorithm 1.

We now argue that the resulting configuration $C$ is a fixed point. Let
$C^{\prime}$ be the successor of $C$. First, observe that for each nand vertex
$u\in V(G_{\mathcal{S}}{})\setminus(V_{nand}\cup V_{nor})$, we have $C(u)=1$
(since we never change the state of vertices that are not in $V_{nand}$ or
$V_{nor}$). Furthermore, $u$ must be adjacent to at least one state-$0$
vertex, or else $u$ will be in $V_{nand}$. Similarly, for each nor vertex
$u\in V(G_{\mathcal{S}}{})\setminus(V_{nand}\cup V_{nor})$, we have that
$C(u)=0$ and $u$ is adjacent to at least one state-$1$ vertex. It immediately
follows that $C(u)=C^{\prime}(u),\;\forall u\in
V(G_{\mathcal{S}}{})\setminus(V_{nand}\cup V_{nor})$. We now consider the
states of vertices in $V_{nand}$ or $V_{nor}$. For each vertex $v\in
V_{nand}$, observe that neighbors of $v$ must all be nand vertices, or else,
$v$ is adjacent to at least one state-0 vertex (i.e., a nor vertex) which
contradicts the fact that $v\in V_{nand}$. Furthermore, we claim that

######  Claim 4.8.2.

Each neighbor of $v$ is not in $V_{nand}$, $\forall v\in V_{nand}$.

For contradiction, suppose $v^{\prime}$ is a neighbor of $v$ who is also in
$V_{nand}$. If $v^{\prime}$ is added to $V_{nand}$ before $v$, then $v$ cannot
also be in $V_{nand}$ since $v$ has $v^{\prime}$ as a state-$0$ neighbor under
$C$. Similarly, if $v$ is added to $V_{nand}$ before $v^{\prime}$, then
$v^{\prime}$ cannot also be in $V_{nand}$. This concludes the claim. Claim
4.8.2 implies that $v$ has no state-$0$ neighbor under $C$, thus,
$C(v)=C^{\prime}(v)=0$. By a similar argument, for each vertex $v\in V_{nor}$,
neighbors of $v$ must all be nor vertices, or else, $v$ is adjacent to at
least one state-1 vertex (i.e., a nand vertex). Moreover, each neighbor of $v$
is not in $V_{nor}$. It follows that the number of state-$0$ neighbors of $v$
is $d(v)$, and $C(v)=C^{\prime}(v)=1$. This concludes the correctness for
Algorithm 1. As for the time complexity, the for loop from line $2$ to $5$
takes $O(n)$ time, and the for loop from line $6$ to $9$ takes $O(m+n)$ time.
Therefore, the overall running time of Algorithm 1 is $O(m+n)$. The results
for SN-SyACG and SN-SACG follow. ∎

Algorithm 1 EQF_NAND_NOR_SN($\mathcal{S^{\prime}}$)

Input: A (SN, IT)-SyDS
$\bar{\mathcal{S}}=(G_{\bar{\mathcal{S}}},\mathcal{F})$, where
$\tau_{1}(v)=1\text{ or }d(v),\;\forall v\in V(G_{\bar{\mathcal{S}}})$
Output: A fixed point $C$ of $\mathcal{S}^{\prime}$

1:$C\leftarrow$ an initial configuration of all $0$’s

2:for $v\in V(G_{\mathcal{S}^{\prime}})$ do

3: if $\tau_{1}(v)=1$ then $C(v)\leftarrow 1$ $\triangleright$ $v$ is a nand
vertex

4: else if $\tau_{1}(v)=d(v)$ then $C(v)\leftarrow 0$ $\triangleright$ $v$ is
a nor vertex

5:end for

6:for $v\in V(G_{\mathcal{S}^{\prime}})$ do

7: if $\tau_{1}(v)=1$ and $C(w)=1$ for all neighbors $w\in N(v)$ then
$C(v)\leftarrow 0$ $\triangleright$ $V_{nand}=V_{nand}\cup\\{v\\}$

8: if $\tau_{1}(v)=d(v)$ and $C(w)=0$ for all neighbors $w\in N(v)$ then
$C(v)\leftarrow 1$ $\triangleright$ $V_{nor}=V_{nor}\cup\\{v\\}$

9:end for

10:return $C$

### The underlying graph is a DAG

Under a directed graph, at each time step, an agent in the self essential mode
considers its own state and the state of in-neighbors. Similarly, each agent
in the self non-essential mode only considers the states of its in-neighbors.

######  Theorem 4.9.

For both the SE anti-coordination game and the SN anti-coordination game, an
NE can be found in $O(m+n)$ time if the underlying graph is a DAG.

Algorithm 2 EQF_DAG_SE($\mathcal{S}$)

Input: A (SE, IT)-SyDS $\mathcal{S}=(G_{\mathcal{S}}{},\mathcal{F})$, where
$G_{\mathcal{S}}{}$ is a DAG
Output: A fixed point $C$ of $\mathcal{S}$ (if exists)

1:$C\leftarrow$ an initial configuration of all $0$’s

2:$V^{\prime}\leftarrow$ the set of vertices with $0$ indegree in
$G_{\mathcal{S}}{}$

3:for $v\in V^{\prime}$ do

4: if $\tau_{1}(v)=1$ then return Null $\triangleright$ The system has no
fixed points

5: else if $\tau_{1}(v)=0$ then $C(v)\leftarrow 1$

6: else if $\tau_{1}(v)=2$ then

7: $C(v)\leftarrow 0$

8: for $w\in N(v)$ do

9: if $\tau_{1}(w)\neq 0$ then $\tau_{1}(w)\leftarrow\tau_{1}(w)-1$

10: end for

11: end if

12: $V^{\prime}\leftarrow V^{\prime}\setminus\\{v\\}$

13: $V^{\prime\prime}\leftarrow$ the set of new vertices with $0$ in-degree

14: $V^{\prime}\leftarrow V^{\prime}\cup V^{\prime\prime}$

15:end for

16:return $C$

###### Proof.

We first present the result for SE-SyACG modeled by a (SE, IT)-SyDS
$\mbox{$\mathcal{S}$}{}=(G_{\mathcal{S}}{},\mathcal{F}^{\prime})$. Let
$V^{\prime}$ be the set of vertices with $0$ indegree in $G_{\mathcal{S}}{}$.
Note that $V^{\prime}\neq\emptyset$, or else, $G_{\mathcal{S}}{}$ contains
directed cycles. We first remark that $\mathcal{S}$ has no fixed points if
there exists a vertex $v\in V^{\prime}$ that is not a constant vertex (i.e.,
$\tau_{1}(v)=1,\;\exists v\in V^{\prime}$). For contrapositive, suppose
$\tau_{1}(v)=1$ for some $v\in V^{\prime}$. Given any configuration $C$ where
$C(v)=1$, it follows that $C^{\prime}(v)=0$. Similarly, if $C(v)=0$, then
$C^{\prime}(v)=1$ for such a vertex $v$. Thus, any configuration $C$ of
$\mathcal{S}$ cannot be a fixed point.

Suppose all vertices in $V^{\prime}$ are constant vertices. Our algorithm
constructs a potential fixed point $C$ as follows. For each vertex $v\in
V^{\prime}$, if $\tau_{1}(v)=0$ (i.e., $v$ is a constant-1 vertex), we set
$C(v)=1$, and remove $v$ from $G_{\mathcal{S}}{}$. On the other hand, if
$\tau_{1}(v)=2$ (i.e., $v$ is a constant-0 vertex), we set $C(v)=0$, then
decrease the threshold values of all $v$’s out-neighbors by 1 and remove $v$
from $G_{\mathcal{S}}{}$. Note that after removing $v$, we might set some
other vertices in $V(G_{\mathcal{S}}{})\setminus V^{\prime}$ to have $0$ in-
degree. Subsequently, we add these new $0$ in-degree vertices to $V^{\prime}$.
The pseudocode is shown in Algorithm 2.

If at any iteration of the algorithm, we found a vertex in $V^{\prime}$ to
have threshold $1$ (i.e., a non-constant vertex), the algorithm terminates and
concludes that $\mathcal{S}$ has no fixed points. On the other hand, if all
vertices in $V^{\prime}$ are constant vertices, it follows that the algorithm
uniquely determines a fixed point $C$ of $\mathcal{S}$. As for the running
time, we may consider the algorithm as a breadth-first search process that
takes $O(m+n)$ time. This concludes the proof SE-SyACG (and thus SE-SACG).

As for the SN anti-coordination games, note that a 0-indegree vertex $v$ is
always a constant vertex, irrespective of $\tau_{1}(v)$. Thus, a SN anti-
coordination game (either SN-SyACG or SN-SACG) has a unique equilibrium which
is determined by the threshold of each vertex. This concludes the proof. ∎

### The underlying graph has no even cycles

We first introduce three characterizations of vertices.

######  Definition .1 (Terminal vertices).

Let $G$ be an undirected graph with no even cycles. A vertex $v$ is a terminal
vertex if $v$ is not in any cycles, and $v$ is on the path between two cycles.

######  Definition .2 (Gate vertices).

Let $G$ be an undirected graph with no even cycles. A vertex $v$ is a gate
vertex if $v$ is on at least one cycle and either $(i)$ adjacent to a terminal
vertex or $(ii)$ adjacent to another vertex on another cycle, or $(iii)$ on at
least two cycles.

Intuitively, gate vertices for a cycle $\mathcal{C}$ act as “entrances” on
$\mathcal{C}$, such that a transversal from any other cycles to $\mathcal{C}$
must reach one of the gate vertices.

######  Definition .3 (Tree vertices).

Let $G$ be an undirected graph with no even cycles. A vertex $v$ is a tree
vertex if $v$ is not on any cycles and $v$ is not a terminal vertex.

Figure 5: An example graph $G$ where blue vertices are terminals, green
vertices are gates, and red vertices are tree vertices.

######  Lemma 4.10.

Given an undirected graph $G$ with no even cycles, all cycles in $G$ are edge-
disjoint.

###### Proof.

For contrapositive, suppose there exists two different odd cycles, denoted by
$\mathcal{C}$ and $\mathcal{C}^{\prime}$, such that they share a common path
$\mathcal{L}=(v_{1},...,v_{l})$ of length $l\geq 1$. Observe that the set of
vertices $V(\mathcal{C})\cup V(\mathcal{C}^{\prime})\setminus V(\mathcal{L})$
form another cycle, denoted by $\mathcal{C}^{\prime\prime}$. Let $2k+1$ and
$2k^{\prime}+1$ be the length of $\mathcal{C}$ and $\mathcal{C}^{\prime}$,
respectively, $k,k^{\prime}\geq 1$. It follows that the length of
$\mathcal{C}^{\prime\prime}$ is $2k+1+2k^{\prime}+1-2l=2(k+k^{\prime}+1-l)$
which is even. Proved by contraposition. ∎

######  Lemma 4.11.

Let $G$ be an undirected graph with no even cycles, then there must exist a
cycle $\mathcal{C}$ with at most one gate vertex.

###### Proof.

Given any cycle $\mathcal{C}$, let $v$ be a gate vertex of $\mathcal{C}$. By
the definition of gate vertices, remark that there exists at least one path
$\mathcal{P}$ from $v$ to another cycle333If $v$ is on more than one cycle,
then the path consists of only vertex $v$ itself., where $\mathcal{P}$
intersects with $\mathcal{C}$ only on $v$. For contradiction, suppose all
cycles have at least two gate vertices. Let $\mathcal{C}_{1}$ be any cycle in
$G$, and denoted by $v_{1}$ a gate vertex of $\mathcal{C}_{1}$. We label all
vertices in $C_{1}$ as visited, and consider a depth-first search (DFS)
process from $v_{1}$ that traverses unvisited vertices until another gate
vertex is found (i.e., a new cycle is reached).

During the DFS process, we label traversed vertices as visited. Let $v_{2}$ be
the gate vertex that the DFS (from $v_{1}$) encounters, and let
$\mathcal{C}_{2}$ be a cycle that contains $v_{2}$. We label vertices in
$\mathcal{C}_{2}$ also as visited. Since all cycles have at least $2$ gate
vertices, let $v_{2}^{\prime}$ be another gate vertex of $\mathcal{C}_{2}$.
Remark that there must not exists a path that consists of only unvisited
vertices (excepts the two endpoints) from $v_{2}^{\prime}$ to any visited
vertices, or else, there exists a cycle that share common edges with
$\mathcal{C}_{2}$ which contradicts $G$ being even-cycle free (Lemma 4.10). It
follows that if we continue the DFS process from $v_{2}^{\prime}$ while
traversing unvisited vertices, it must reach a new gate vertex $v_{3}$ on a
cycle $\mathcal{C}_{3}$. Let $v_{3}^{\prime}$ be another gate vertex of
$\mathcal{C}_{3}$. Similarly, there must not exists a path that consists of
only unvisited vertices (except the two endpoints) from $v_{3}^{\prime}$ to
any visited vertices. Overall, given a newly visited gate vertex $v_{k}$ on a
cycle $C_{k}$, $k\geq 2$. Let $v_{k}^{\prime}$ be another gate vertex of
$C_{k}$. By induction, there exists a path with only unvisited vertices
(except $v_{k}^{\prime}$ itself who is visited) from $v_{k}^{\prime}$ to a
cycle that is different from $C_{i}$, $i=1,...,k-1$. However, this contradicts
$G$ being finite (and thus the number of cycles is finite). The Lemma follows.
∎

Now consider a (SE, IT)-SyDS $\mathcal{S}=(G_{\mathcal{S}}{},\mathcal{F})$
that models a SE-SyACG.

######  Lemma 4.12.

Let $\mathcal{S}=(G_{\mathcal{S}}{},\mathcal{F})$ be a (SE, IT)-SyDS where the
underlying graph has no even cycles. A tree vertex $v\in V(G_{\mathcal{S}}{})$
has the same state over any fixed point $C$.

###### Proof.

We first argue that if a vertex $v$ has degree $1$, then $v$ has the same
state under any fixed point $C$. In particular, note that the threshold
$\tau_{1}(v)$ could be either $0$, $1$, $2$ or $3$. If $\tau_{1}(v)=0$ or
$\tau_{1}(v)=3$, then $v$ is a constant vertex whose state is uniquely
determined by $\tau_{1}(v)$. On the other hand, by Observation 4.2 and 4.3, we
know that $C(v)=1$ if $\tau_{1}(v)=1$ and $C(v)=0$ if $\tau_{1}(v)=2$.

Observe that if there exists at least one tree vertex in $G_{\mathcal{S}}{}$,
then at least one of the tree vertices has degree $1$. Let $v$ be any tree
vertex with degree $1$. Based on the claim above, we know that the state of
$v$ under any fixed point $C$ is predetermined. Subsequently, we can
effectively remove $v$ from the graph and update the threshold values of $v$’s
neighbor accordingly (i.e., decrease the neighbor’s threshold by one if
$C(v)=0$). By recursion, it follows that the state of any tree vertex $v$ is
the same over any fixed point of $\mathcal{S}$. ∎

######  Lemma 4.13.

Let $\mathcal{S}=(G_{\mathcal{S}}{},\mathcal{F})$ be a (SE, IT)-SyDS where the
underlying graph has no even cycles. Let $\mathcal{C}$ be a cycle in
$G_{\mathcal{S}}{}$ with at most one gate vertex. Let $u\in\mathcal{C}$ be a
non-gate vertex on $\mathcal{C}$, then the state of $u$ is the same under any
fixed point.

###### Proof.

By Lemma 4.11, we know that such a cycle $\mathcal{C}$ with at most one gate
vertex must exist. Given a non-gate vertex $u$ on $\mathcal{C}$, observe that
any of $u$’s neighbors that are not on $\mathcal{C}$ must be tree vertices.
Furthermore, by Lemma 4.12, the states of all tree vertices are predetermined
under a fixed point. Thus, we can consider the graph where all the tree
vertices are removed, and the threshold values of their non-tree neighbors are
updated accordingly. Subsequently, all non-gate vertices on $\mathcal{C}$ have
degree $2$.

######  Claim 4.13.1.

If $\mathcal{S}$ has a fixed point, then at least one non-gate vertex on
$\mathcal{C}$ does not have threshold $2$.

For contradiction, suppose all the non-gate vertices on $\mathcal{C}$ have
thresholds $2$. Since $\mathcal{C}$ is of odd length, it cannot be 2-colored.
Thus, under any configuration $C$, there must exist an edge $(u,v)$ on
$\mathcal{C}$ where the state of $u$ and $v$ are the same. Furthermore, at
least one of them is a non-gate vertex with threshold $2$. W.o.l.g., let $u$
be such a vertex. Since $u$ has degree 2, if $C(u)=C(v)=1$, then the number of
state-$0$ vertices in the closed neighborhood of $u$ is at most $1$, which is
less than $\tau_{1}(u)$. Thus, $C(u)=1\neq C^{\prime}(u)=0$ where $C^{\prime}$
is the successor of $C$. Similarly, if $C(u)=C(v)=0$, we have $C(u)=0\neq
C^{\prime}(u)=1$. Overall, it follows that $\mathcal{S}$ does not have a fixed
point if all the non-gate vertices on $\mathcal{C}$ have thresholds $2$.

Claim 4.13.1 implies that if $\mathcal{S}$ has a fixed point, then at least
one non-gate vertex $u$ on $\mathcal{C}$ has a threshold not equal to $2$. We
now argue that the state of $u$ remains the same under any fixed point $C$ of
$\mathcal{S}$. In particular, if $\tau_{1}(u)=0$ or $\tau_{1}(u)=4$, then $u$
is a constant vertex whose state is predetermined. On the other hand, if
$\tau_{1}(u)=1$, then $C(u)=1$, and if $\tau_{1}(u)=3=d(v)+1$, then $C(u)=0$.
It follows that the state of $u$ is the same under any fixed point and is
predetermined by $\tau_{1}(v)$. Thus, we may remove $u$ from the graph and
update the thresholds of $u$’s neighbors accordingly. Remark that after
removing $u$, all non-gate vertices on $\mathcal{C}$ become tree vertices.
Subsequently, by Lemma 4.12, the state of all non-gate vertices on
$\mathcal{C}$ are predetermined, and are the same over any fixed point of
$\mathcal{C}$. ∎

######  Theorem 4.14.

For a SE anti-coordination game, an NE can be found in $O(m+n)$ time if the
underlying graph has no even cycles.

###### Proof.

Let $\mbox{$\mathcal{S}$}{}=(G_{\mathcal{S}}{},\mathcal{F})$ be a (SE,
IT)-SyDS that models a SE-SyACG. Suppose $\mathcal{S}$ has a fixed point,
denoted by $C$. By Lemma 4.12, we can determine the state of all the tree
vertices under $C$ based on their threshold values, and remove all the tree
vertices from $G_{\mathcal{S}}{}$. Let $\mathcal{C}_{1}$ be a cycle that
consists of only one gate vertex. By Lemma 4.11, we can also determine the
states of all non-gate vertices on $\mathcal{C}_{1}$ and effectively eliminate
the cycle $\mathcal{C}_{1}$. Let $G_{\mathcal{S}}{}_{1}$ be the resulting
graph which is still even-cycle free. If $G_{\mathcal{S}}{}_{1}$ contains
other cycles, then there must exists another cycle that consists of only one
gate vertex. By recursively determining the state of non-gate vertices on
single-gate cycles and the states of tree vertices, it follows that we can
determine the states of all vertices under $C$ in time $O(m+n)$. Since a fixed
point of $\mathcal{S}$ corresponds to an NE of the underlying SE-SyACG, we
conclude that an NE can be found in $O(m+n)$ time for a SE-SyACG (and thus for
SE-SACG) when the underlying graph has no even cycles. ∎

With the same argument, we also establish the same result for SN anti-
coordination games.

######  Theorem 4.15.

For a SN anti-coordination game, an NE can be found in $O(m+n)$ time if the
underlying graph has no even cycles.

### The underlying graph is complete

######  Theorem 4.16.

For a SE anti-coordination game, an NE can be found in $O(n)$ time if the
underlying graph is a complete graph.

###### Proof.

Let $\mbox{$\mathcal{S}$}{}=(G_{\mathcal{S}}{},\mathcal{F})$ be a (SE,
IT)-SyDS that models a SE-SyACG. We partition the set of vertices based on
their thresholds. Specifically, let $k$ be the number of distinct thresholds
$\tau_{1}$. Let $\mathcal{P}=\\{V_{1},...,V_{k}\\}$ be a partition of the
vertex set $V(G_{\mathcal{S}}{})$, such that
$\tau_{1}(u)=\tau_{1}(v),\;\forall u,v\in V_{i},\;i=1,...,k$. Furthermore,
$\tau_{1}(u)<\tau_{1}(v),\;\forall u\in V_{i},v\in V_{j},\;1\leq i<j\leq k$.
Remark that since $G_{\mathcal{S}}{}$ is a complete graph, the closed
neighborhoods of all vertices are the same, which is $V(G_{\mathcal{S}}{})$.
Thus, given any fixed point $C$ of $\mathcal{S}$, if $C(v)=1$ for some $v\in
V_{j}$, then $C(u)=1,\forall u\in V_{i},i\leq j$.

Our algorithm consists of at most $k-1$ iterations, where in each iteration
$j$, $1\leq j\leq k-1$, we construct a configuration $C$ such that
$C(v)=1,\forall v\in V_{i},i=1,...,j$, and $C(v)=0$ otherwise. After each
iteration of the algorithm, we check if the resulting $C$ is a fixed point,
and return $C$ if so. On the other hand, if all the resulting $k-1$
configurations are not fixed points, we conclude that $\mathcal{S}$ does not
have a fixed point. The pseudocode is shown in Algorithm 3.

We establish the correctness of the algorithm. First, we claim that

######  Claim 4.16.1.

The system $\mathcal{S}$ has a fixed point if and only if there exists a
bipartition $\\{V^{\prime},V^{\prime\prime}\\}$ of $V(G_{\mathcal{S}}{})$,
such that $\max\\{\tau_{1}(v):v\in
V^{\prime}\\}\leq|V^{\prime\prime}|<\min\\{\tau_{1}(v):v\in
V^{\prime\prime}\\}$. Further, such a fixed point $C$ has vertices in
$V^{\prime}$ in state $1$, and vertices in $V^{\prime\prime}$ in state $0$.

Suppose $\mathcal{S}$ has a fixed point $C$. Let $C^{\prime}$ be the successor
of $C$. Let $V^{\prime}=\\{v:C(v)=1,v\in V(G_{\mathcal{S}}{})\\}$ and
$V^{\prime\prime}=\\{v:C(v)=0,v\in V(G_{\mathcal{S}}{})\\}$ be a bipartition
of the vertex set based on the state of vertices. We argue that
$\max\\{\tau_{1}(v):v\in V^{\prime}\\}<\min\\{\tau_{1}(v):v\in
V^{\prime\prime}\\}$. For contrapositive, assume that there exists a vertex
$v\in V^{\prime}$ such that $\tau_{1}(v)\geq\tau_{1}(w)$ for some $w\in
V^{\prime\prime}$. Since $C$ is a fixed point and $C(v)=1$, we have
$|V^{\prime\prime}|\geq\tau_{1}(v)$ (i.e., the number of state-0 vertices in
$C$ is at least $\tau_{1}(v)$). However, it follows that
$|V^{\prime\prime}|\geq\tau_{1}(v)\geq\tau_{1}(w)$, thus, $C(w)=0\neq
C^{\prime}(w)=1$ and $C$ is not a fixed point. Overall, we have
$\max\\{\tau_{1}(v):v\in
V^{\prime}\\}\leq|V^{\prime\prime}|<\min\\{\tau_{1}(v):v\in
V^{\prime\prime}\\}$.

As for the necessity of the claim, note that if such a bipartition
$\\{V^{\prime},V^{\prime\prime}\\}$ exists, we can construct a fixed point $C$
by assigning $C(v)=1,\;\forall v\in V^{\prime}$ and $C(v)=0\;\forall v\in
V^{\prime\prime}$. It follows that
$|V^{\prime\prime}|\geq\max\\{\tau_{1}(v):v\in
V^{\prime}\\}\geq\tau_{1}(v),\;\forall v\in V^{\prime}$. Thus,
$C(v)=C^{\prime}(v)=1$, $\forall v\in V^{\prime}$. Similarly, we have
$|V^{\prime\prime}|\leq\min\\{\tau_{1}(v):v\in
V^{\prime\prime}\\}\leq\tau_{1}(v),\;\forall v\in V^{\prime\prime}$ and
$C(v)=C^{\prime}(v)=0$, $\forall v\in V^{\prime\prime}$. This concludes Claim
4.16.1.

We now argue that the for loop of Algorithm 3 from line $5$ to $12$
essentially discovers if such a bipartition
$\\{V^{\prime},V^{\prime\prime}\\}$ exists. In particular, at the
$j^{\text{th}}$ iteration, $1\leq j\leq k-1$, denoted by $a_{0}$ the number of
state-$0$ vertices in $C$ (after the updates from line 6 to 8). Let
$\tau_{1}(V_{j})$ be the threshold value of vertices in $V_{j}\in\mathcal{P}$.
Observe that the algorithm effectively construct a configuration $C$ by
setting vertices in $V^{\prime}=\bigcup_{i=1}^{j}V_{i}$ to state $1$, and
vertices in $V^{\prime\prime}=\bigcup_{i=j+1}^{k}V_{i}$ to state $0$ .

######  Claim 4.16.2.

The inequality $\tau_{1}(V_{j})\leq a_{0}<\tau_{1}(V_{j+1})$ (i.e., the
condition at line 10) is satisfied if and only if $\max\\{\tau_{1}(v):v\in
V^{\prime}\\}\leq|V^{\prime\prime}|<\min\\{\tau_{1}(v):v\in
V^{\prime\prime}\\}$.

Observe that $a_{0}=|V^{\prime\prime}|$. Suppose $\tau_{1}(V_{j})\leq
a_{0}<\tau_{1}(V_{j+1})$. Since $\tau_{1}(V_{j})\geq\tau_{1}(v),\;\forall v\in
V^{\prime}=\bigcup_{i=1}^{j}V_{i}$, it follows that
$a_{0}=|V^{\prime\prime}|\geq\max\\{\tau_{1}(v):v\in V^{\prime}\\}$.
Similarly, given that $\tau_{1}(V_{j+1})\leq\tau_{1}(v),\;\forall v\in
V^{\prime\prime}=\bigcup_{j=i+1}^{k}V_{j}$, we have
$|V^{\prime\prime}|\leq\min\\{\tau_{1}(v):v\in V^{\prime\prime}\\}$. For the
other direction, by an analogous argument, it is easy to see that if
$\max\\{\tau_{1}(v):v\in
V^{\prime}\\}\leq|V^{\prime\prime}|<\min\\{\tau_{1}(v):v\in
V^{\prime\prime}\\}$, then $\tau_{1}(V_{i})\leq a_{0}<\tau_{1}(V_{i+1})$. The
correctness of the algorithm immediately follows.

Overall, the partition $\mathcal{P}$ can be constructed in $O(n)$ time via the
bucket sort. Furthermore, the for loop at line $7$ is called at most $O(n)$
time, and the operations from line $9$ to line $12$ take constant time.
Therefore, the overall running time is $O(n)$. Since a fixed point of
$\mathcal{S}$ corresponds to an NE of the underlying game, we conclude that an
NE can be found in $O(n)$ time for a SE-SyACG (and therefore for SE-SACG) when
the underlying graph is a complete graph. ∎

Algorithm 3 EQF_Complete_SE($\mathcal{S}$)

Input: A (SE, IT)-SyDS/SDS $\mathcal{S}=(G_{\mathcal{S}},\mathcal{F})$, where
$G_{\mathcal{S}}{}$ is a complete graph
Output: A fixed point $C$ of $\mathcal{S}$

1:$C\leftarrow$ an initial configuration of all $0$’s

2:$\mathcal{P}\leftarrow\\{V_{1},...,V_{k}\\}$ be a partition of
$V(G_{\mathcal{S}}{})$ such that $\tau_{u}<\tau_{v}$ iff $u\in V_{i},v\in
V_{j},1\leq i<j\leq k$

3:$\tau_{1}(V_{i})\leftarrow$ the threshold value of vertices in
$V_{i}\in\mathcal{P},i=1,...,k$

4:$a_{0}\leftarrow|V(G_{\mathcal{S}}{})|$ $\triangleright$ The number of
state-$0$ vertices in $C$

5:for $j=1$ to $k-1$ do

6: for $v\in V_{j}$ do

7: $C(v)\leftarrow 1$

8: end for

9: $a_{0}\leftarrow a_{0}-|V_{j}|$

10: if $\tau_{1}(V_{j})\leq a_{0}<\tau_{1}(V_{j+1})$ then $\triangleright$
Determine if $C$ is a fixed point return C

11: end if

12:end for

13:return Null $\triangleright$ The system has no fixed point

With the same argument, we can show that the above result for complete graphs
carries over to SN anti-coordination games.

######  Theorem 4.17.

For a SN anti-coordination game, an NE can be found in $O(n)$ time if the
underlying graph is a complete graph.

## Additional Material for Section 5

In this section, we present the detailed proofs of the convergence result for
synchronous anti-coordination games, given in section 5 of the main
manuscript. Based on the connection between the games and dynamical systems,
all proofs are given in the context of synchronous dynamical systems. We first
present the convergence result for (SN, IT)-SyDS (modeling SN-SyACG). Then
with simple modifications of the proof, the result for (SE, IT)-SyDS (modeling
SE-SyACG) follows. Let
$\mbox{$\mathcal{S}$}{}=(G_{\mathcal{S}}{},\mathcal{F})$ be a (SN, IT)-SyDS
that models a SN-SyACG. Recall that for a vertex $v$, $\tau_{0}(v)$ is the
minimum number of state-$1$ neighbors of $v$ for $f_{v}$ to equal $0$.
W.l.o.g., we assume there are no constant vertices. That is,
$1\leq\tau_{1}(u),\tau_{0}(u)\leq d(u)$ for all $u\in V(G_{\mathcal{S}}{})$.

### The potential functions and bounds

Let $C$ be an arbitrary configuration of $\mathcal{S}$ whose successor is
$C^{{}^{\prime}}$. We now define the potentials of vertices, edges, and the
system under $C$. For each vertex $u\in V(G_{\mathcal{S}}{})$, let
$\tilde{\tau}_{0}(u)=\tau_{0}(u)-1/2$.

Vertex potential. Given a vertex $u\in V(G_{\mathcal{S}}{})$, the potential of
$u$ under $C$, is defined as follows:

$\mathcal{P}(C,u)=C(u)\cdot\tilde{\tau}_{0}(u)+C^{{}^{\prime}}(u)\cdot\tilde{\tau}_{0}(u)$

Edge potentials. Given an edge $e=(u,v)\in E(G_{\mathcal{S}}{})$, the
potential of $e$ under $C$ is defined as follows:

$\mathcal{P}(C,e)=C(u)\cdot C^{{}^{\prime}}(v)+C(v)\cdot C^{{}^{\prime}}(u)$

The configuration potential. The potential of the system $\mathcal{S}$ under
$C$ is defined as the subtraction of the sum of vertex potentials from the sum
of edge potentials:

$\mathcal{P}(C,\mathcal{S})=\sum_{e\in
E(G_{\mathcal{S}}{})}\mathcal{P}(C,e)-\sum_{u\in
V(G_{\mathcal{S}}{})}\mathcal{P}(C,u)$

#### A lower bound on the configuration potential.

We first present a lower bound on the configuration potential under $C$.

######  Lemma 5.1.

The configuration potential satisfies

$\mathcal{P}(C,\mathcal{S})\geq-4m+n$

###### Proof.

First observe that the sum of edge potentials is non-negative. Further, the
sum of potentials of vertices is upper bounded by

$\displaystyle\sum_{u\in V(G_{\mathcal{S}}{})}\mathcal{P}(C,u)$
$\displaystyle=\sum_{u\in
V(G_{\mathcal{S}}{})}C(u)\cdot\tilde{\tau}_{0}(u)+C^{{}^{\prime}}(u)\cdot\tilde{\tau}_{0}(u)$
$\displaystyle\leq 2\sum_{u\in V(G_{\mathcal{S}}{})}\tilde{\tau}_{0}(u)$ (12)
$\displaystyle\leq 2\sum_{u\in V(G_{\mathcal{S}}{})}(d(u)-\frac{1}{2})$
$\displaystyle=4m-n$

The lower bound of the configuration potential immediately follows. ∎

#### An upper bound on the configuration potential.

We now present an upper bound on the configuration potentials under $C$.

######  Lemma 5.2.

The configuration potential $\mathcal{P}(C,\mathcal{S})$ is upper bounded by
$0$.

###### Proof.

Let $E_{u}=\\{(u,v):(u,v)\in E(G_{\mathcal{S}}{})\\}$ be the set of edges
incident to a vertex $u\in V(G_{\mathcal{S}}{})$. We can restate the sum of
edge potentials as follows

$\displaystyle\sum_{e\in E(G_{\mathcal{S}}{})}\mathcal{P}(C,e)$
$\displaystyle=\sum_{(u,v)\in E(G_{\mathcal{S}}{})}\left(C(u)\cdot
C^{{}^{\prime}}(v)+C(v)\cdot C^{{}^{\prime}}(u)\right)$ (13)
$\displaystyle=\sum_{u\in
V(G_{\mathcal{S}}{})}\left(C^{{}^{\prime}}(u)\cdot\sum_{(u,v)\in
E_{u}}C(v)\right)$

We can further expend the configuration potential into the form

$\displaystyle\mathcal{P}(C,\mathcal{S})=\sum_{u\in
V(G_{\mathcal{S}}{})}\left(\left(C^{{}^{\prime}}(u)\sum_{(u,v)\in
E_{u}}C(v)\right)-C(u)\cdot\tilde{\tau}_{0}(u)-C^{{}^{\prime}}(u)\cdot\tilde{\tau}_{0}(u)\right)$
(14)

Note that $\sum_{(u,v)\in E_{u}}C(v)$ is exactly the number of state-$1$
neighbors of $u$ under $C$. If $C^{{}^{\prime}}(u)=0$, then

$\displaystyle\left(C^{{}^{\prime}}(u)\sum_{e=(u,v)\in
E_{u}}C(v)\right)-C(u)\cdot\tilde{\tau}_{0}(u)-C^{{}^{\prime}}(u)\cdot\tilde{\tau}_{0}(u)$
$\displaystyle=-C(u)\cdot\tilde{\tau}_{0}(u)\leq 0$ (15)

Conversely, if $C^{{}^{\prime}}(u)=1$, then by the inverted-threshold
dynamics, the number of state-$1$ neighbor of $u$ under $C$ is less than
$\tau_{0}(u)$. Subsequently, we have

$\sum_{(u,v)\in E_{u}}C(v)\leq\tau_{0}(u)-1<\tilde{\tau}_{0}(u)$ (16)

and

$\displaystyle\left(C^{{}^{\prime}}(u)\sum_{(u,v)\in
E_{u}}C(v)\right)-C^{{}^{\prime}}(u)\cdot\tilde{\tau}_{0}(u)-C(u)\cdot\tilde{\tau}_{0}(u)$
(17) $\displaystyle=\left(\sum_{(u,v)\in
E_{u}}C(v)\right)-\tilde{\tau}_{0}(u)-C(u)\cdot\tilde{\tau}_{0}(u)$
$\displaystyle\leq 0$

It follows that the overall configuration potential satisfies
$\mathcal{P}(C,\mathcal{S})\leq 0$. ∎

Overall, we have established that the gap in the configuration potential value
between two configurations is at most $4m-n$.

### Decrease of the configuration potential before convergence

In this section, we show that from a configuration $C$, the configuration
potential decrease by at least $1$ after every two time-steps, until a fixed
point or a 2-cycle is reached.

######  Lemma 5.3.

Let $C$ an arbitrary configuration of $\mathcal{S}$. We have
$\mathcal{P}(C^{{}^{\prime}},\mathcal{S})=\mathcal{P}(C,\mathcal{S})$ if and
only if $C=C^{{}^{\prime\prime}}$, that is $C$ is a fixed point or is on a
$2$-cycle $C\longleftrightarrow C^{{}^{\prime}}$. Furthermore, if $C\neq
C^{{}^{\prime\prime}}$ (i.e., the dynamic has not converged), then
$\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})\leq-1/2$.

###### Proof.

We defined the change of potential of an edge $e=(u,v)\in
E(G_{\mathcal{S}}{})$ from $C$ to $C^{{}^{\prime}}$ as

$\Delta(e)=\mathcal{P}(C^{{}^{\prime}},e)-\mathcal{P}(C,e)$ (18)

and the change of potential of a vertex $u$ as

$\Delta(u)=\mathcal{P}(C^{{}^{\prime}},u)-\mathcal{P}(C,u)$ (19)

Subsequently, the change of the configuration potential from $C$ to
$C^{{}^{\prime}}$ is as follows

$\displaystyle\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})$
(20) $\displaystyle=\sum_{e\in
E(G_{\mathcal{S}}{})}\mathcal{P}(C^{{}^{\prime}},e)-\sum_{u\in
V(G_{\mathcal{S}}{})}\mathcal{P}(C^{{}^{\prime}},u)-\sum_{e\in
E(G_{\mathcal{S}}{})}\mathcal{P}(C,e)+\sum_{u\in
V(G_{\mathcal{S}}{})}\mathcal{P}(C,u)$ $\displaystyle=\sum_{e\in
E(G_{\mathcal{S}}{})}\Delta(e)-\sum_{u\in V(G_{\mathcal{S}}{})}\Delta(u)$

We now expand $\Delta(e)$ for $e=(u,v)$ and $\Delta(u)$ as follows

$\displaystyle\Delta(e)$ $\displaystyle=\left(C^{{}^{\prime}}(u)\cdot
C^{{}^{\prime\prime}}(v)+C^{{}^{\prime}}(v)\cdot
C^{{}^{\prime\prime}}(u)\right)-\left(C(u)\cdot
C^{{}^{\prime}}(v)+C^{{}^{\prime}}(u)\cdot C(v)\right)$ (21)
$\displaystyle=C^{{}^{\prime}}(u)\cdot
C^{{}^{\prime\prime}}(v)+C^{{}^{\prime}}(v)\cdot
C^{{}^{\prime\prime}}(u)-C(u)\cdot C^{{}^{\prime}}(v)-C^{{}^{\prime}}(u)\cdot
C(v)$
$\displaystyle=C^{{}^{\prime}}(u)\cdot\left(C^{{}^{\prime\prime}}(v)-C(v)\right)+C^{{}^{\prime}}(v)\cdot\left(C^{{}^{\prime\prime}}(u)-C(u)\right)$
$\displaystyle\Delta(u)$
$\displaystyle=\left(C^{{}^{\prime}}(u)\tilde{\tau}_{0}(u)+C^{{}^{\prime\prime}}(u)\tilde{\tau}_{0}(u)\right)-\left(C(u)\tilde{\tau}_{0}(u)+C^{{}^{\prime}}(u)\tilde{\tau}_{0}(u)\right)$
(22)
$\displaystyle=\left(C^{{}^{\prime\prime}}(u)-C(u)\right)\cdot\tilde{\tau}_{0}(u)$

We argue that the change in configuration potential is $0$ if and only if
$C=C^{{}^{\prime\prime}}$.

  * $(\Leftarrow)$

Suppose $C=C^{{}^{\prime\prime}}$, it follows that
$C(u)=C^{{}^{\prime\prime}}(u)$, $\forall u\in V(G_{\mathcal{S}}{})$.
Subsequently, $\Delta(e)=0$, $\forall e\in E(G_{\mathcal{S}}{})$ and
$\Delta(u)=0$, $\forall u\in V(G_{\mathcal{S}}{})$. Overall, we conclude that
the change of potential
$\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})=0$.

  * $(\Rightarrow)$

For contrapositive, suppose $C\neq C^{{}^{\prime\prime}}$. We now show that
the configuration potential decreases by at least $1/2$. It is easy to see
that given a vertex $u$ such that $C(u)=C^{{}^{\prime\prime}}(u)$, we have
$\Delta(u)=0$. Thus, we consider the set of vertices whose states in $C$ are
different from the states in $C^{{}^{\prime\prime}}$. Let
$V_{0-1}=\\{u:C(u)=0,\;C^{{}^{\prime\prime}}(u)=1,\;u\in
V(G_{\mathcal{S}}{})\\}$ be the set of vertices whose states are $0$’s under
$C$ and are $1$’s under $C^{{}^{\prime\prime}}$. Analogously, denoted by
$V_{1-0}=\\{u:C(u)=1,\;C^{{}^{\prime\prime}}(u)=0,\;u\in
V(G_{\mathcal{S}}{})\\}$ the set of vertices whose states are $1$’s under $C$
and are $0$’s under $C^{{}^{\prime\prime}}$. We remark that since $C\neq
C^{{}^{\prime\prime}}$, $|V_{0-1}|+|V_{1-0}|\geq 1$.

We now consider the change of potential for a vertex $u$ whose state in $C$ is
different from the state in $C^{{}^{\prime\prime}}$, under the following
cases.

Case 1: The vertex $u\in V_{0-1}$. Subsequently, the change of vertex
potential for $u$ is

$\Delta(u)=\left(C^{{}^{\prime\prime}}(u)-C(u)\right)\cdot\tilde{\tau}_{0}(u)=\tilde{\tau}_{0}(u)$
(23)

Case 2: The vertex $u\in V_{1-0}$. It then follows that

$\Delta(u)=\left(C^{{}^{\prime\prime}}(u)-C(u)\right)\cdot\tilde{\tau}_{0}(u)=-\tilde{\tau}_{0}(u)$
(24)

Overall, we have

$\sum_{u\in V(G_{\mathcal{S}}{})}\Delta(u)=\sum_{u\in
V_{0-1}}\tilde{\tau}_{0}(u)-\sum_{u\in V_{1-0}}\tilde{\tau}_{0}(u)$ (25)

As for the change of edge potentials, observe that $\Delta(e)=0$ for $e=(u,v)$
if $C(u)=C^{{}^{\prime\prime}}(u)$ and $C(v)=C^{{}^{\prime\prime}}(v)$. We now
consider $\Delta(e)$, $e=(u,v)$ where either $u$ or $v$ (or both) undergoes
state change from $C$ to $C^{{}^{\prime\prime}}$.

Case 1: The state of one vertex altered, and the state of the other remained
the same. W.o.l.g., suppose the vertex $u\in V_{0-1}$, and
$C(v)=C^{{}^{\prime\prime}}(v)$. It follows that

$\displaystyle\Delta(e)$
$\displaystyle=C^{{}^{\prime}}(u)\cdot\left(C^{{}^{\prime\prime}}(v)-C(v)\right)+C^{{}^{\prime}}(v)\cdot\left(C^{{}^{\prime\prime}}(u)-C(u)\right)$
(26) $\displaystyle=C^{{}^{\prime}}(v)$

On the other hand, if $u\in V_{1-0}$, we then have
$\Delta(e)=-C^{{}^{\prime}}(v)$. Analogously, if the state of $v$ changed and
the state of $u$ remained the same, then $\Delta(e)=C^{{}^{\prime}}(u)$ when
$v\in V_{0-1}$, and $\Delta(e)=-C^{{}^{\prime}}(u)$ when $v\in V_{1-0}$.

Case 2: The the states of $u,v$ both changed in the same direction from $C$ to
$C^{{}^{\prime\prime}}$ (i.e., both from $0$ to $1$ or from $1$ to $0$).
Specifically, if $u,v\in V_{0-1}$, we then have

$\displaystyle\Delta(e)$
$\displaystyle=C^{{}^{\prime}}(u)\cdot\left(C^{{}^{\prime\prime}}(v)-C(v)\right)+C^{{}^{\prime}}(v)\cdot\left(C^{{}^{\prime\prime}}(u)-C(u)\right)$
(27) $\displaystyle=C^{{}^{\prime}}(v)+C^{{}^{\prime}}(u)$

Conversely, if $u,v\in V_{1-0}$, then
$\Delta(e)=-C^{{}^{\prime}}(v)-C^{{}^{\prime}}(u)$.

Case 3: The states of $u,v$ changed in different directions from $C$ to
$C^{{}^{\prime\prime}}$ (i.e., one from $0$ to $1$ and the other from $1$ to
$0$). W.l.o.g., suppose $u\in V_{0-1}$ and $v\in V_{1-0}$. Subsequently, we
have

$\displaystyle\Delta(e)=C^{{}^{\prime}}(v)-C^{{}^{\prime}}(u)$ (28)

Similarly, if $u\in V_{1-0}$ and $v\in V_{0-1}$, then
$\Delta(e)=C^{{}^{\prime}}(u)-C^{{}^{\prime}}(v)$

Overall, observe that for any vertex $u\in V_{0-1}$, the change of edge
potential $\Delta(e)$ for each incident edge $e=(u,v)$ has a positive term
$C^{{}^{\prime}}(v)$. Conversely, if $u\in V_{1-0}$, then $\Delta(e)$ has a
negative term $-C^{{}^{\prime}}(v)$. Let $E_{u}=\\{(u,v):(u,v)\in
E(G_{\mathcal{S}}{})\\}$ be the set of edges incident to $u\in
V(G_{\mathcal{S}}{})$, we can rewire the sum of the change in edge potentials
as

$\displaystyle\sum_{e\in E(G_{\mathcal{S}}{})}\Delta(e)=\left(\sum_{u\in
V_{0-1}}\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)\right)-\left(\sum_{u\in
V_{1-0}}\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)\right)$ (29)

In combined with Equation 25, we characterize the change in the configuration
potential from $C$ to $C^{{}^{\prime}}$ as follows

$\displaystyle\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})$
(30) $\displaystyle=\sum_{e\in E(G_{\mathcal{S}}{})}\Delta(e)-\sum_{u\in
V(G_{\mathcal{S}}{})}\Delta(u)$ $\displaystyle=\left(\sum_{u\in
V_{0-1}}\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)-\sum_{u\in
V_{1-0}}\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)\right)-\left(\sum_{u\in
V_{0-1}}\tilde{\tau}_{0}(u)-\sum_{u\in V_{1-0}}\tilde{\tau}_{0}(u)\right)$
$\displaystyle=\left(\sum_{u\in V_{0-1}}\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)-\tilde{\tau}_{0}(u)\right)+\left(\sum_{u\in
V_{1-0}}\tilde{\tau}_{0}(u)-\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)\right)$

Remark that the term $\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)$ is the number
of state-$1$ neighbors of a vertex $u$ under $C^{{}^{\prime}}$. Suppose $u\in
V_{0-1}$, that is, $C^{{}^{\prime\prime}}(u)=1$. By the dynamics of inverted-
threshold model, it follows that the number of state-$1$ neighbors of $u$
under $C^{{}^{\prime}}$ is less than $\tau_{0}(u)=\tilde{\tau}_{0}(u)+1/2$,
thus,

$\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)\leq\tau_{0}(u)-1<\tilde{\tau}_{0}(u)$

and

$\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)-\tilde{\tau}_{0}(u)\leq-\frac{1}{2}$

Conversely, if $u\in V_{1-0}$ which implies that $C^{{}^{\prime\prime}}(u)=0$.
It follows that the number of state-$1$ neighbors of $u$ is at least
$\tau_{0}(u)$. Thus,

$\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)\geq\tau_{0}(u)>\tilde{\tau}_{0}(u)$

and

$\tilde{\tau}_{0}(u)-\sum_{(u,v)\in E_{u}}C^{{}^{\prime}}(v)\leq-\frac{1}{2}$

Overall, we have

$\displaystyle\mathcal{P}(C^{{}^{\prime}},\mathcal{S})-\mathcal{P}(C,\mathcal{S})$
(31) $\displaystyle=\left(\sum_{u\in V_{0-1}}\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)-\tilde{\tau}_{0}(u)\right)+\left(\sum_{u\in
V_{1-0}}\tilde{\tau}_{0}(u)-\left(\sum_{(u,v)\in
E_{u}}C^{{}^{\prime}}(v)\right)\right)$ $\displaystyle\leq-\sum_{u\in
V_{0-1}}\frac{1}{2}-\sum_{u\in V_{1-0}}\frac{1}{2}$
$\displaystyle=-\frac{|V_{0-1}|+|V_{1-0}|}{2}$ $\displaystyle\leq-\frac{1}{2}$

This concludes the proof. ∎

Overall, we have shown that the potential gap between any two configurations
is $4m-n$. Furthermore, the overall system configuration decreases by at least
$1/2$ after each time step. It follows that for a (SN, IT)-SyDS, starting from
an arbitrary initial configuration, the system dynamic converges in at most
$8m-2n$ time steps, irrespective of the underlying network structure.
Subsequently, the convergence time result for SN-SyACG follows.

######  Theorem 5.4.

For SN-SyACG, starting from any initial action profile, the best-response
dynamic converges to a Nash equilibrium or a 2-cycle in $O(m)$ time steps.

With simple modifications of Lemma 5.3 (i.e., consider $u$ as a neighbor of
itself), we can also show that the same convergence time can be extended to
SE-SyACG.

######  Theorem 5.5.

For a SE-SyACG, starting from any initial action profile, the best-response
dynamic converges to a Nash equilibrium or a 2-cycle in $O(m)$ time steps.

######  Corollary 5.6.

For both SE-SyACG and SN-SyACG, starting from any initial action profile, the
best-response dynamic converges to a Nash equilibrium or a 2-cycle in $O(n)$
time steps if the graph is degree bounded.