Evolutionary anti-coordination (AC) games have been widely used to model real-world strategic situations such as product marketing (Linde, Sonnemans, and Tuinstra 2014), balanced traffic routing (Galib and Moser 2011), and social competition (Bramoullé 2007). 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 (Young 2015). 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 (Ramazi, Riehl, and Cao 2016). There are two main types of update schemes for evolutionary games: agents either choose actions synchronously or sequentially (Adam, Dahleh, and Ozdaglar 2012a).
The decision mode where each agent only considers its neighbors' actions in making its decisions is common in the game theory literature (Gibbons 1992). 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 (Gibbons 1992;Traulsen et al. 2010;Lo et al. 2006). For example, drivers on a highway can be seen as agents in an evolutionary anticoordination 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 neighborsfoot_0 .
Pure Nash equilibria (NE) are a central concept in game theory (Aleksandrov and Walsh 2017;Nissan et al. 2007). In evolutionary games, another key notion is the time it takes for the best-response dynamics to reach an NE or a limit cycle (Christodoulou, Mirrokni, and Sidiropoulos 2006;Jackson and Zenou 2015). 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 one be found efficiently? (ii) CONVERGENCE (CONV): Starting from an action profile, how fast does the best-response dynamics converge to a limit cycle of length at most 2?
The best-response dynamics of an evolutionary anticoordination game can be specified using a threshold framework (Adam, Dahleh, and Ozdaglar 2012b). This naturally allows us to model such a game as a graphical dynamical system (Barrett et al. 2006). In such a system, at every 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 as-signed 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 (Barrett et al. 2006). 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.
• Finding an NE. We demonstrate a 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, one 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 anticoordination 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 (Barrett et al. 2003). • 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. 1996). "NA" denotes that the problem is not applicable due to exponentially long cycles (Barrett et al. 2003). For CONV, O(m) is the number of steps for the best-response dynamics to reach a limit cycle.
The existence of NE. The self non-essential sequential anticoordination games are potential games and always have an NE (Vanelli et al. 2020). This result follows from Monderer and Shapley (1996), which guarantees the existence of NE at the maximum potential. Further, Monderer and Shapley (1996) show that general potential games converge in finite time. Note that this result does not imply a polynomialtime algorithm in finding an NE. Kun et al. (2013) 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. (2020) examine synchronous games with both coordinating and anticoordinating agents. They present several special cases of threshold distributions for the existence of NE. Auletta et al. (2016) 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 (2013) 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 (e.g., (Simon and Wojtczak 2017;Conitzer and Sandholm 2003)).
Limiting behavior. Adam et al. (2012b) 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 (2016) 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 dynamics they consider is different from the sequential dynamics studied in our work, and their convergence result does not imply ours. Goles and Martinez (2013) establish that for coordination games, the dynamics converges in a polynomial number of steps. Barrett et al. (2003) study phase space properties of sequential dynamical systems (which can model sequential AC games); these 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., (Ieong et al. 2005;Awerbuch et al. 2008;Jackson and Zenou 2015).
Minority games. Anti-coordination games are closely related to minority games (Chmura and Pitz 2006;Arthur 1994). Many versions of minority games have been studied. For example, Challet and Marsili (2000) study the dynamics of minority games where agents make decisions based on the action profile history of the population. Shang et al. (2000) examine the action distribution of minority games over different network topologies. Several other forms of minority games are studied in (Li, Riolo, and Savit 2000).
A more thorough discussion of related work is given in (Qiu et al. 2022). 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.
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 (i.e., an action from the set {0, 1}) based on neighbors' actions, and receives a payoff. Under the best-response dynamics, agents choose actions that yield the maximum payoff. For the best-response dynamics of an anti-coordination (AC) game, each agent v has a nonnegative threshold τ 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 τ 1 (v) (Ramazi, Riehl, and Cao 2016). We now define the problems of interest. EQUILIBRIUM EXISTENCE/FINDING (EQE/EQF): Given an anti-coordination game, does it have an NE, and if so, can one be found it efficiently? CONVERGENCE (CONV): Given an anti-coordination game and an initial action profile, how fast does the best-response dynamics converge to a limit cycle of length at most 2?
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 its 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 choose 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 anticoordination games. We follow the notation used in (Barrett et al. 2006;Rosenkrantz et al. 2021). A synchronous dynamical system (SyDS) over the Boolean state domain B = {0, 1} is a pair S = (G S , F ); G S = (V, E) is the underlying graph, with n = |V | and m = |E|. We assume G S is connected and undirected, unless specified otherwise. The set F = {f 1 , ..., f n } consists of functions with f i being the local function of vertex v i ∈ V, 1 ≤ i ≤ 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) S ′ is a tuple (G S ′ , F ′ , Π) where G S ′ and F ′ are the same as those for the synchronous systems defined above (Mortveit and Reidys 2007). In addition, Π 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 S ′ consists of n substeps, in each of which one vertex updates its state using the current vertex states.
Update rules. To model anti-coordination dynamics, we consider inverted-threshold local functions for the stateupdate of vertices. Formally, each vertex v i has a fixed integer threshold τ 1 (v i ) ≥ 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) in state-0 at the previous time step (for the synchronous scheme) or at the current time step (for the sequential scheme) is at least τ 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 "invertedthreshold"). An example of SN mode appears in Figure 1.
Limit cycles. A configuration C of a system S is a vector C = (C(v 1 ), ..., C(v n )) where C(v i ) ∈ B is the state of vertex v i under C. The dynamics of S from an initial configuration C can be represented by a time-ordered sequence of configurations. Specifically, a configuration C ′ is the successor of C if S evolves from C to C ′ in one step. A limit cycle of S is a closed sequence of configurations in the phase space (Foster and Young 1990). In particular, let C ′ be the successor of C, and C ′′ be the successor of
synchronous scheme sequential scheme Figure 1: Example dynamics of SDS and SyDS under the SN mode. Specifically, C is an initial configuration, and C ′ is its successor under either the synchronous or the sequential mode (with vertex update order ⟨v 1 , v 2 , v 3 , v 4 ⟩). State-1 vertices are highlighted in blue.
The dynamics of an AC game is captured by the dynamics of the underlying dynamical system S. Specifically, an agent v's action at time t corresponds to v's state at time t in S, and v's decision threshold is described by τ 1 (v). Moreover, the evolution of the action profile for the game coincides with the transition of configurations under S. Thus, we have: Observation 1. A fixed point and a limit cycle of 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 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.
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) anticoordination games, one 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 discuss the reasons for this difference 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 S and an SDS S ′ have the same underlying graph and the same local functions, then they have the same set of fixed points, regardless of the vertex permutation Π of S ′ . Observation 2. 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.
We establish that EQE (and therefore EQF) is hard for the anti-coordination games under the SE mode (i.e., for 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 2, the hardness carries over to SE-SACG. Further, the reduction is parsimonious, which further implies that #EQE is #P-hard. We present detailed proofs in (Qiu et al. 2022). Theorem 3. 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 an appropriate (SE, IT)-SyDS 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 S, a positive and a negative literal vertex for the same variable have complementary values; and (ii) there is a one-to-one correspondence between the satisfying assignments of f and the fixed points of S.
It is known that a SN-SACG always has an NE, and one can be found in finite time (Monderer and Shapley 1996). Thus, EQE is trivial for SN-SACG, and by Observation 2, EQE is also trivial for SN-SyACG. However, these observations don't resolve the complexity of the search problem EQF.
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 S ′ (modeling a SN-SACG) from any configuration C, a fixed point of S ′ is always reached in at most 3m steps. Since each step of S ′ can be carried out in O(m) time, a fixed point of S ′ can be found in O(m 2 ) time (Theorem 6). As for a (SN, IT)-SyDS S (modeling a SN-SyACG), we can transform it into a corresponding SDS S ′ , and then find a fixed point of S ′ (obtained as described above), which is also a fixed point of S. We provide more details below.
The potentials. Let S ′ be an (SN, IT)-SDS. Recall that for each vertex u ∈ V (G S ′ ), τ 1 (u) is the minimum number of state-0 neighbors of u such that f u evaluates to 1. For the SN mode, τ 0 (u) = deg(u) + 1 -τ 1 (u) is the minimum number of state-1 neighbors of u such that f u evaluates to 0. Given a configuration C of S ′ , the potentials P of vertices, edges, and C are defined as follows. Vertex potential: The potential of u ∈
Configuration potential: The potential of C is the sum of the vertex potentials and edge potentials over all vertices and edges. That is, P(C, S ′ ) = u∈V (G S ′ ) P(C, u) + e∈E(G S ′ ) P(C, e).
The following lemma establishes lower and upper bounds on the potential of any configuration. A detailed proof of the lemma is in (Qiu et al. 2022). Lemma 4. For any configuration C of S ′ , we have
Proof (sketch). One can verify that the configuration potential is always at least 0. As for the upper bound, we argue that
, and that an upper bound on the total edge potential is m. The upper bound of 3m for the configuration potential follows.
Lemma 4 establishes that the configuration potential gap between any two configurations is at most 3m for S ′ .
Decrease of potential. Next, we argue that whenever a substep of S ′ 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. A detailed proof appears in (Qiu et al. 2022). Lemma 5. Suppose that in a substep of S ′ 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 Ĉ the configuration after the substep. Then, P( Ĉ, S ′ ) -P(C, S ′ ) ≤ -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 on u. W.l.o.g., suppose u's state changes from 0 to 1 in the transition from C to Ĉ. We can show that the change in the configuration potential is given by
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 Ĉ(u) = 1, it follows that d 0 (u) ≥ τ 1 (u) and d 1 (u) ≤ τ 0 (u) -1. Therefore, P( Ĉ, S ′ ) -P(C, S ′ ) ≤ -1.
From the above two lemmas, it follows that starting from an arbitrary configuration of (SN, IT)-SDS S ′ , a fixed point is reached in at most 3m steps. Thus, we can find a fixed point by starting with an arbitrary initial configuration, and simulating the operation of S ′ for at most 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 S ′ can be found in O(m 2 ) time. Similarly, given a (SN, IT)-SyDS S, we can first convert S into an SDS S ′ by assigning an arbitrary vertex permutation, and then find a fixed point of S ′ , which is also a fixed point S. Lastly, given that a fixed point of a dynamical system is an NE of the underlying self non-essential game, we have: Theorem 6. For both SN-SACG and SN-SyACG, an NE can be found in O(m 2 ) time.
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 τ 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.
Given the hardness of EQE/EQF for SE anti-coordination games, we identify several sufficient conditions under which an NE (if one exists) can be obtained efficiently.
Theorem 7. 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 τ 1 (u) ∈ {1, d u + 1}.
A detailed proof appears in (Qiu et al. 2022).
Here, we provide a sketch for (i), i.e., complete graphs. Let P = {V 1 , ..., V k } be the partition of the vertex set V where each block of P consists of a maximal set of vertices with the same value of τ 1 , and the blocks of P are indexed so that for each i, 1 ≤ i < k, the members of V i have a lower value of τ 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 τ 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 ∈ V i for some i where i ≤ q. Thus there are only k + 1 candidate configurations that can possibly be fixed points. Our algorithm constructs each of these candidates, and checks if it is a fixed point.
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 (Barrett et al. 2003).
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 Sy-ACG. 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 τ 1 = 2 for all vertices.).
Synchronous anti-coordination games are not potential games. Therefore, the results on potential games by Monderer and Shapley (1996) do not apply. As shown in (Adam, Dahleh, and Ozdaglar 2012b), 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 (Goles and Martinez 2013), in Theorem 10 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 (Qiu et al. 2022).) Here, we present a proof sketch for the SN mode. Let S = (G S , 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 step account for not only the states of vertices at the current step but also that of the next step. For SN mode, let τ 0 (u) = deg(u) + 1 -τ 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 ≤ τ 1 (u) ≤ deg(u), ∀u ∈ V (G S )); a justification is given in (Qiu et al. 2022). Consequently, 1 ≤ τ 0 (u) ≤ deg(u). We define τ0 (u) = τ 0 (u) -1/2. Given any configuration C of S, let C ′ be the successor of C , and C ′′ the successor of C ′ . Vertex potentials. The potential of a vertex u under C is defined by
Edge potentials. The potential of an edge e = (u, v) under C is defined by
Configuration potential. The potential of a configuration C is defined by P(C , S) = e∈E(G S ) P(C , e) -u∈V (G S ) P(C , u). We now establish lower and upper bounds on the potential under an arbitrary configuration C. Lemma 8. For any configuration C of a (SN, IT)-SyDS S, -4m + n ≤ P(C, S) ≤ 0.
Proof (sketch). One can verify that the maximum value of the sum of vertex potentials is 4m -n, hence the lower bound. We now discuss the upper bound. For each vertex u, let σ u = v∈N (u) C(v), where N (u) is the set of neighbors of the vertex u. Note that for inverted-threshold function
The configuration potential can be restated as:
, which is at most -1/2. This concludes the proof.
Decrease of potential. We now show that from any configuration C , the potential decreases by at least 1/2 in every step until a fixed point or a 2-cycle is reached.
e., the dynamics has not converged), then, the configuration potential has decreased by at least 1/2, i.e., ∆(S) ≤ -1/2. Proof (sketch). We define the change of potential for an edge e = (u, v) as ∆(e) = P(C ′ , e) -P(C , e), and the change of potential for a vertex u as ∆(u) = P(C ′ , u) -P(C , u). Then,
Rearranging terms from the definition of potentials, we get
and ′′ (u) = 0. We establish the following two equations:
where E u is the set of edges incident on u.
Recall that ∆(S) equals the change in edge potentials minus the change in vertex potentials, so by (i) and (ii) above,
We argue that if u ∈ V 0-1 , then:
and the lemma follows.
The above discussion establishes that starting from an arbitrary configuration of S, the dynamics stabilizes in at most 8m -2n steps. Our convergence time results for the SN synchronous anti-coordination games follow immediately. In (Qiu et al. 2022), we also show that the above proof can be easily extended to SE-SyACG. Theorem 10. 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.
We conduct experiments to study the contrast between the empirical convergence time of synchronous anticoordination 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 (Rozemberczki and Sarkar 2020;Leskovec and Mcauley 2012;Leskovec, Kleinberg, and Faloutsos 2007), and synthetic networks from the classes Gnp, scalefree (Barabási and Albert 1999), and small-world (Watts and Strogatz 1998). 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. For source code and selected networks see: https://github.com/bridgelessqiu/AntiCoord.
Convergence time on networks. For each network, we randomly generate 200 instances of threshold assignments, where τ 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 let 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 is 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. 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. contrast, the convergence time and the variance for the SN mode change marginally.
To gain additional insight, we computed the average (over all pairs of consecutive steps) number n of vertices whose states change every 2 steps until convergence. As suggested by Lemma 9 in Section 5, a higher n implies a faster decrease in the system potential. Overall, the value of 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.
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 τ 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.
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 ≤ η ≤ 28, the number of instances with η NE is shown in Fig. 3. This shows a contrast in the number of NE for the
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 nonessential (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 bestresponse 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 (Feder, Nazerzadeh, and Saberi 2007) for the SE anticoordination 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.
The word "essential" is based on the term "essential variable" used in the context of Boolean functions(Salomaa 1963).The Thirty-Seventh AAAI Conference on Artificial Intelligence