# invasion_dynamics_in_the_biased_voter_process__bd97dfd3.pdf Invasion Dynamics in the Biased Voter Process Loke Durocher1 , Panagiotis Karras1 , Andreas Pavlogiannis1 and Josef Tkadlec2 1Aarhus University, Aabogade 34, Aarhus, Denmark 2Harvard University, 1 Oxford Street, Cambridge, USA {panos,pavlogiannis}@cs.au.dk, tkadlec@math.harvard.edu The voter process is a classic stochastic process that models the invasion of a mutant trait A (e.g., a new opinion, belief, legend, genetic mutation, magnetic spin) in a population of agents (e.g., people, genes, particles) who share a resident trait B, spread over the nodes of a graph. An agent may adopt the trait of one of its neighbors at any time, while the invasion bias r (0, ) quantifies the stochastic preference towards (r > 1) or against (r < 1) adopting A over B. Success is measured in terms of the fixation probability, i.e., the probability that eventually all agents have adopted the mutant trait A. In this paper we study the problem of fixation probability maximization under this model: given a budget k, find a set of k agents to initiate the invasion that maximizes the fixation probability. We show that the problem is NP-hard for both r > 1 and r < 1, while the latter case is also inapproximable within any multiplicative factor. On the positive side, we show that when r > 1, the optimization function is submodular and thus can be greedily approximated within a factor 1 1/e. An experimental evaluation of some proposed heuristics corroborates our results. 1 Introduction Invasion processes are a standard framework for modeling the spread of novel traits in populations. The population structure is represented as a graph, with nodes occupied by agents, while the edge relation captures some sort of agent connection, such as spatial proximity, friendship, direct communication, or particle interaction. The invasion dynamics define the rules of trait diffusion from an agent to its neighbors. These dynamics raise a natural optimization problem that calls to choose a set of at most k initial trait-holders that maximizes a goal involving the eventual spread of the trait in the population. This type of problem has been studied extensively with a focus on influence spread on social network dynamics [Domingos and Richardson, 2001; Kempe et al., 2003; Mossel and Roch, 2007]; see [Li et al., 2018] for a survey. The voter process is a fundamental and natural probabilis- tic diffusion model that arises in evolutionary population dynamics, where the diffused trait is a mutation and the initial trait-holders are mutants. Also known as imitation updating in evolutionary game theory [Ohtsuki et al., 2006], it was initially introduced to study particle interactions [Liggett, 1985] and territorial conflict [Clifford and Sudbury, 1973]; since then, it has found numerous applications in the spread of genetic mutations (the death-birth Moran process) [Hindersin and Traulsen, 2015; Tkadlec et al., 2020], social dynamics [Castellano et al., 2009], robot coordination and swarm intelligence [Talamali et al., 2021]. In the long run, the process leads to a consensus state [Even-Dar and Shapira, 2007], in which the mutant trait is either fixated (i.e., adopted by all agents), or gone extinct. The calibre of the invasion is quantified in terms of its fixation probability [Kaveh et al., 2015; Brendborg et al., 2022]; thus, the goal of optimization in this context is to maximize the probability that the mutant trait spreads in the whole population. Unlike other models of spread, the voter process accounts for active resistance to the invasion: an agent carrying the mutant trait may not only forward it to its neighbors, but also lose it due to exposure to the resident trait from its neighbors. This model exemplifies settings such as individuals that may switch opinions, magnetic spins that may undergo transient states, and sub-species that compete in a gene pool. In this paper, we study the problem of fixation probability maximization in the context of the biased voter process: find a set of k agents initially having a mutant trait A that maximizes the fixation probability of A in a population with a preexisting resident trait B. The invasion bias r (0, ) quantifies the stochastic preference of each agent towards (r > 1) or against (r < 1) adopting A over B. Despite extensive interest in this type of optimization problem and the appeal and generality of the voter process, to our knowledge, this problem in the context of the voter process has only been studied in the restricted case r = 1, which admits a simple polynomial-time algorithm [Even-Dar and Shapira, 2007]. Yet biased invasions naturally occur in most settings: for genetic mutations, r captures the fitness (dis)advantage conferred by the new mutation [Allen et al., 2020]; for magnetic spins, r reveals the presence of a magnetic field [Antal et al., 2006]; for social traits, r accounts for the societal predisposition towards a new idea [Bhat and Redner, 2019]. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) Our contributions can be summarized as follows: 1. We show that computing the fixation probability on undirected graphs admits a fully polynomial-time approximation scheme (FPRAS). 2. We show that, notwithstanding the neutral case where r = 1, fixation maximization is NP-hard both for r > 1 and for r < 1, while the latter case is also inapproximable within any multiplicative factor. 3. On the positive side, we show that, when r > 1, the optimization function is submodular and thus can be greedily approximated within a factor 1 1/e. 2 Preliminaries Structured populations. Following the literature standard, we represent a population structure by a (generally, directed and weighted) graph G = (V, E, w) of n = |V | nodes. Each node stands for a location in some space, while a population of n agents is spread on G with one agent per node. Given a node u, we denote by N(u) = {v V : (v, u) E} the neighbors of u, and by deg(u) = |N(u)| its degree. The weight function w: E R 0 maps every edge to a nonnegative number. As a convention, we write w(v, u) = 0 if (v, u) E. We consider graphs for which the sub-graph induced by the support of w is strongly connected which is necessary for the voter process to be well-defined. We say that G is undirected if E is symmetric and irreflexive, and w(v, u) = 1 for all (v, u) E. For simplicity, when G is undirected we denote it by G = (V, E). The voter invasion process. The classic voter process models the invasion of a mutant trait A into a homogeneous population [Clifford and Sudbury, 1973; Liggett, 1985]. The process distinguishes between two types of agents, residents, who carry a resident trait B, and mutants, who carry the mutant trait A. A seed set S V defines the agents that are initially mutants. The invasion bias r > 0 is a real-valued parameter that defines the relative competitive advantage of mutants in this invasion. When r > 1 (resp., r < 1), the mutants have a competitive advantage (resp., competitive disadvantage), and the process is biased towards (resp., against) invasion, while r = 1 yields the neutral case. A configuration X V defines the set of mutants at a given time. The fitness of the agent occupying a node u V is defined as f X(u) = r, if u X 1, otherwise. The discrete-time voter invasion process [Antal et al., 2006; Even-Dar and Shapira, 2007], a.k.a. Moran death-birth process [Tkadlec et al., 2020; Allen et al., 2020], with seed set S is a stochastic process (Xi)i 0, where Xi V is a random configuration. Initially, X0 = S, and, given the current configuration X, we obtain Xi+1 in two stochastic steps. 1. (Death event): a focal agent on some node u is chosen with uniform probability 1/n. 2. (Birth event): the agent on u adopts the trait of one of its neighbors, on v, with probability: f X(v) w(v, u) P x N(u) f X(x) w(x, u). Note that the focal agent may assume its pre-existing trait, and generally, the mutant set may grow or shrink in each step. We often identify agents with the nodes they occupy and use expressions such as node v reproduces onto u to indicate that the agent occupying node u adopts the trait of the agent at node v. See Fig. 1 for an illustration. Figure 1: Initially, each node is occupied by a resident (red), except for a seed set S of nodes occupied by mutants (blue). In each step of the voter process with bias r, one random node adopts the type of one of its neighbors, with mutants having a relative (dis)advantage r. Fixation probability. As G is strongly connected, one type will spread to all nodes in finitely many steps with probability 1. The mutant invasion succeeds if the mutant trait spreads, an event called fixation. Given a graph G, a bias r, and an initial seed set S, the fixation probability, denoted as fp G r (S), is the probability that the mutants starting from S eventually fixate on G. See Fig. 2 for an illustration. Figure 2: A graph G = (V, E) of 7 nodes and fixation probability fp G r (S) for 5 different subsets S of 2 nodes vs. bias r [0.01, 100]. We have fp G r 0(S) 0, unless S forms a vertex cover (Lemma 6) and fp G r (S) 1 iff S contains two adjacent nodes. Whereas the computational complexity of determining fp G r (S) is unknown, the function is approximately computable by a simulation of the invasion process. In the next section we will show that when G is undirected, such a simulation yields an efficient approximation scheme. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) Fixation maximization. We formulate and study the optimization problem of selecting a seed set that leads to a most successful invasion, i.e., maximizes the fixation probability, subject to cardinality constraints. Formally, given a graph G, a bias r and a budget k, the task is to compute the set S = arg max S V,|S|=k fp G r (S) (1) The corresponding decision question is: Given a budget k and a threshold α [0, 1] determine whether there exists a seed set S with |S| = k such that fp G r (S) α. As Fig. 2 illustrates, different seed sets yield considerably different fixation probabilities, while the optimal choice varies depending on r, hence the intricacy of the problem. 3 Computing the Fixation Probability For r = 1, the fixation probability is additive [Broom et al., 2010]. Thus, given a graph G = (V, E, w) and a budget k, the set S that maximizes fp G r=1(S) is obtained by selecting the k largest values from the vector fp G r=1({v}) | v V , determined by solving a system of n linear equations [Allen et al., 2015]; thus the problem can be solved in polynomial time. When G is undirected, that system admits a closed-form solution [Broom et al., 2010]: fp G r=1({v}) = deg(v)/2|E|. For r = 1, the complexity of determining fp G r (S) is open. Here we show that, for undirected graphs, it can be efficiently approximated by a fully-polynomial randomized approximation scheme (FPRAS). The key component of our result is a polynomial upper bound on the expected number of steps TG r (S) until one of the types fixates; an analogous approach has been used for the so-called Moran Birth-death process [D ıaz et al., 2014]. Theorem 1. Let G = (V, E) be an undirected graph with |V | = n nodes, |E| = m edges, and maximum degree . Let S V be the initial seed set and r = 1. Then TG r (S) = O( nm) = O(n4). Proof. Without loss of generality, suppose r > 1 (otherwise we swap the role of mutants and residents). Given a current configuration X, we define a potential ϕ(X): 2V R as ϕ(X) = P v X deg(v). We show that, as we run the process, ϕ(X) increases in a controlled manner. To that end, we distinguish two types of configurations: we say that a configuration is bad if every edge uv E connects nodes of different types, and good otherwise. Note that bad configurations exist iff G is bipartite, in which case there are exactly two of them. In [Durocher et al., 2022], we show that: 1. When at a bad configuration, the next configuration is good and the potential does not change in expectation. 2. When at a good configuration, in one step the potential increases by at least s = (r 1)/(r n) in expectation. All in all, this implies that, in expectation, the potential increases by at least s over any two consecutive steps (until fixation occurs). Since at all times the potential is non-negative and upper-bounded by U = P v V deg(v) = 2m, by a standard drift theorem for submartingales [He and Yao, 2001; Lengler, 2020] the expected number of steps is at most: TG r (S) 2U s = 4r r 1 nm. Theorem 1 yields the following corollary based on the Monte Carlo method. Corollary 1. When G = (V, E) is undirected, S V , the function fp G r (S) admits a FPRAS for any r. 4 Invasion with Favorable Bias In this section we study the voter process for r > 1. We show that the problem is NP-hard (Section 4.1) but the fixation probability is monotone and submodular and can thus be efficiently approximated (Section 4.2). 4.1 Hardness of Optimization Here we consider the weakly biased process, i.e., the case r = 1 + ε for small ε > 0. Since fp G r (S) is a continuous and smooth function of r, its Taylor expansion around r = 1 is: fp G r=1+ε(S) = fp G r=1(S) + ε c(G, S) + O(ε2), (2) where c(G, S) is a constant independent of ε. Recall that fp G r=1(S) = P v S deg(v)/2|E| [Broom et al., 2010]. For dregular graphs, this yields fp G r=1(S) = d|S|/2|E|, hence the first term in Eq. (2) is constant across all equal-sized seed sets S. We thus have the following lemma. Lemma 1. For any undirected regular graph G, there exists a small constant ε > 0 such that: arg max S V,|S|=k fp G r=1+ε(S) arg max S V,|S|=k c(G, S). In light of Lemma 1, we establish the hardness of fixation maximization by computing c(G, S) analytically on regular graphs, and showing that maximizing it is NP-hard. Mc Avoy and Allen [2021] recently showed that, given G and S, the constant c(G, S) can be defined through a system of n2 linear equations. Here we determine c(G, S) explicitly for regular graphs. For each node v V , let xv = 1 iff v S. First, we restate [Mc Avoy and Allen, 2021, Proposition 2] in the special case of d-regular graphs and adapt it to our notation. Lemma 2. Fix an undirected d-regular graph G = (V, E) on n nodes and an initial configuration S V . Then c(G, S) = 1 2d2n2 X u,v V |N(u) N(v)| ηuv, (3) where ηuv comprise the unique solution to the linear system n 2 |xu xv| + 1 2d P w N(u) ηwv + 1 2d P w N(v) ηuw if u = v, 0 if u = v. (4) Intuitively, each ηuv expresses the expected number of steps in which nodes u and v are occupied by a mutant and resident, respectively. We say that an edge e E is active if its endpoints are occupied by heterotypic agents. The following lemma establishes that, on regular graphs, c(G, S) is decreasing in the number of active edges induced by S. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) Lemma 3. Let G = (V, E) be a d-regular graph on n nodes and S V an initial configuration of size |S| = k. Let a(S) be the number of active edges induced by S. Then c(G, S) = k(n k) Proof. Let |uv| be the shortest-path distance between u and v in G. We proceed in two steps. First, we claim that summing all the n2 equations in the system of Eq. (4), we obtain u,v V ηuv = n 2 2k(n k)+ X u,v V ηuv 1 |uv|=1 2ηuv. (5) 1. We have P u,v V |xu xv| = 2k(n k), since each ordered pair of heterotypic agents is counted once. 2. For a fixed pair (u, v) with |uv| 2, term 1 2dηuv appears on the right-hand side of 2d equations, namely d equations with ηwv on the left-hand side and u N(w) and d equations with ηuw on the left-hand side and v N(w). 3. For a fixed pair (u, v) with |uv| = 1, term 1 2dηuv appears on the right-hand side of 2d 2 equations, namely the above 2d equations, except for 2 cases where w {u, v}. Rearranging Eq. (5), we obtain X |uv|=1 ηuv = dnk(n k). (6) Second, we claim that summing the 2|E| equations in the system of Eq. (4) where |uv| = 1, we obtain X |uv|=1 ηuv = n 2 2a(S) + 1 u,v V 2|N(u) N(v)| ηuv, ergo, using Eq. (6) X u,v V |N(u) N(v)| ηuv = d2nk(n k) dn a(S). (7) 1. We have P |uv|=1 |xu xv| = 2a(S), since each active edge is counted exactly twice, once in each direction. 2. For a fixed pair (u, v) with |uv| = 1, let N(u, v) = N(u) N(v) be the set of common neighbors of u and v. The term 1 2dηuv then appears on the right-hand side of precisely 2|N(u, v)| equations, namely |N(u, v)| equations with ηwv on the left-hand side and |N(u, v)| equations with ηuw on the left-hand side, where w N(u, v). From Lemma 2 and Eq. (7), we obtain the desired c(G, S) = 1 2d2n2 X u,v V |N(u) N(v)| ηuv = d2nk(n k) a(S)dn 2d2n2 = k(n k) Thus, given a budget k, we maximize the fixation probability at the limit r 1, by minimizing the number of active edges. We are now ready to establish the main result in this section. Theorem 2. Fixation maximization in the biased voter process with r > 1 is NP-hard, even on regular undirected graphs. Proof. Lemma 1 and Lemma 3 imply that, for any regular undirected graph G, there exists a small ε > 0 for which arg max S V,|S|=k fp G r=1+ε(S) arg min S V,|S|=k a(S) i.e., the fixation probability is maximized by a seed set that minimizes the number of active edges. For k = n/2, this is known as the minimum bisection problem, which is NP-hard even on 3-regular graphs [Bui et al., 1987]. 4.2 Monotonicity and Submodularity A real-valued set function f is called monotone if for any two sets A and B with A B, we have f(A) f(B). Further, f is called submodular if for all sets A and B we have f(A) + f(B) f(A B) + f(A B). (8) Monotone submodular functions, even if hard to maximize, admit efficient approximations. Here we complement the hardness of Theorem 2 by showing that fp G r 1(S) is monotone and submodular. Although submodularity is well-known for some progressive invasion processes [Kempe et al., 2003], recall that our setting is non-progressive, i.e., the mutant set may grow or shrink in any step. This non-progressiveness renders submodularity a non-trivial property. Node duplication. Towards establishing monotonicity and submodularity, it is convenient to view the process in a slightly different but equivalent way, via node duplication. Consider the voter process M on a graph G with bias r > 1. The node duplication view of M is another stochastic process M = (X i)i on G, defined as follows. Let X V be the current configuration. 1. A node u is chosen for death uniformly at random (i.e., this step is identical to M). 2. We modify G = (V, E, w) to G = (V , E , w ) as follows. For every node v N(u) X, we create a duplicate v of v, and insert an edge (v , u) in G with weight w (v , u) = w(v, u). We associate v with fitness f X(v ) = r 1, while every other node v V gets fitness f X(v) = 1. Finally, we execute a stochastic birth step as in the standard voter process, i.e., we choose a node v to propagate to u with probability f X(v) w (v, u) P x f X(x) w (x, u) The new configuration X i+1 contains u if either some mutant node v or its duplicate v was chosen for reproduction. It is straightforward to see that this modified birth step preserves the probability distribution of random configurations, and thus M and M are equivalent. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) Monotonicity. Using the equivalence between the voter process and its variant with node duplication, we now establish the monotonicity of the fixation probability. Lemma 4. For any graph G and bias r, for any two seed sets S1 and S2 with S1 S2, we have fp G r (S1) fp G r (S2). Proof. First assume r > 1. Consider two processes M1 = (X 1 i )i and M2 = (X 2 i )i starting from X 1 0 = S1 and X 2 0 = S2, respectively. We establish a coupling between M1 and M2 that satisfies X 1 i X 2 i for all i 0, from which the lemma follows. In each step, we first choose the same node u for death in M2 and M1 with uniform probability. Then, we execute a birth step in M2. If the reproducing node v is present in M1, we perform the same update in M1. Otherwise, if v is a mutant duplicate absent from M1, we perform an independent birth step in M1. This coupling maintains the invariant X 1 i X 2 i , as whenever M1 takes an independent step, a mutant has reproduced in M2. Moreover, the coupling is indeed transparent to M1 and M2, as every birth event occurs with probability proportional to its agent s fitness. The monotonicity for all r follows by symmetry, as when r < 1 we can exchange the roles of mutants and residents. Using the above argument, it follows that the fixation probability of the residents grows monotonically in V \ S and, in reverse, decreases monotonically as V \ S shrinks, hence the fixation probability of the mutants grows monotonically in S. Submodularity. We now show submodularity, i.e., we have fp G r (A) + fp G r (B) fp G r (A B) + fp G r (A B). (9) To this end, it is convenient to consider the following more refined view of the invasion process. Given an initial seed set S = A B, we keep track not only of the mutant set, but also the subset of mutants that are copies of those agents initially in A, and those initially in B. Consider this refined view, and execute the invasion beyond the point where mutants fixate. With probability 1, every execution that results in the fixation of S eventually leads to the fixation of A or B (possibly both, assuming that A B = ). We can thus compute the fixation probability of S by summing over each execution that ends in the fixation of at least one of A, B. This extended process is instrumental in proving submodularity. Lemma 5. For any graph G and bias r 1, the fixation probability fp G r (S) is submodular. Proof. Consider any two sets A, B V . Let M1, M2, M3 and M4 be the four (extended) invasion processes, under node duplication, that correspond to initial seeds A, B, A B and A B, respectively. For j [4], let X j i be the ith random configuration of Mj. Moreover, let Yi (resp., Zi) be the set of nodes of M3 in step i that are occupied by mutant agents who are descendants of some agent initially in A (resp., B). We establish a four-way coupling between all Mj that preserves the following invariants: (i) Yi X 1 i (ii) Zi X 2 i and (iii) X 4 i X 1 i X 2 i . Given our extended invasion process, any execution that leads to the fixation of A B in M3 will eventually witness the fixation of at least one of A or B. Invariants (i) and (ii), then, guarantee that any fixating execution in M3 is also fixating in at least one of M1 and M2. Invariant (iii) guarantees that any fixating run execution in M4 is fixating in both M1 and M2. Hence, the three invariants imply Eq. (9), i.e., submodularity. We now establish the coupling. In each step i, we choose the same node u in all Mj to die uniformly at random. Then, as long as Yi, Zi = we perform the following steps. 1. Choose a node v to reproduce in M3 using node duplication (hence v is either an original or a duplicate node). For each process Mj in which v is a node (either original or duplicate), propagate the agent from v to u. Note that this step updates M3 and at least one of M1 and M2, while if it updates M4, it also updates both M1 and M2. 2. If v is not a node in one of M1 or M2, then perform an independent birth step in that process, choosing some node x (either original or duplicate). If x is present in M4, apply the birth event in M4 as well, otherwise apply an independent birth step in M4. If Yi = or Zi = , we perform step 2 only in the process not yet terminated. As in Lemma 4, the coupling is indeed transparent to each Mj and maintains invariants (i) (iii). Conclusively, monotonicity and submodularity lead to the following approximation guarantee [Nemhauser et al., 1978]. Theorem 3. Given a graph G and integer k, let S be the seed set that maximizes fp G r (S), and S the seed set constructed by a greedy algorithm opting for maximal returns in each step. Then fp G r (S ) (1 1/e) fp G r (S ). 5 Invasion with Infavorable Bias We now turn our attention to disadvantageous invasions, i.e., r < 1, and show that the problem is intractable. To establish our result we focus on the limit r 0, i.e., the process is infinitely biased against invasion, and write fp G 0 (S) = limr 0 fp G r (S). Our key insight is the following lemma. Lemma 6. Let G = (V, E) be an undirected graph on n nodes and S V a seed set. If S is a vertex cover on G then fp G 0 (S) > 1/nn, otherwise fp G 0 (S) = 0. Proof. First, suppose S is a vertex cover. Denote the nodes in V \ S by u1, . . . , ui. With probability 1/ni 1/nn, in the next i steps the agents at nodes u1, . . . , ui are selected for death (in this order). Since S is a vertex cover, each of them adopts the mutant trait, and mutants fixate. Second, suppose S is not a vertex cover, thus we have an edge (u, v) E with u, v S. The idea is that, in the limit r 0, the agents on u and v are overwhelmingly more likely to spread to the rest of the graph than to ever become mutants. Consider a node with a mutant and b 1 resident agents among its neighbors. Note that if an agent at such a node dies, the node gets occupied by a resident agent with probability b b+ar 1 n =: pres and by a mutant agent with prob- Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) Figure 3: Experimental comparison of heuristics on four graphs. ability ar b+ar nr =: pmut. Since G is connected, there exists an ordering (u1, . . . , uk) of the nodes in S such that node ui has a neighbor among {u1, . . . , ui 1} (V \ S), for each i = 1, . . . , k. Consider the first k steps. With probability pext 1 n pres k = 1/n2k, agents at nodes u1, . . . , uk die (in this order) and all become residents, thus mutant extinction occurs. On the other hand, by Union Bound, within this time-frame, one of u, v becomes mutant with probability puv 2 npmut 2r. If neither event occurs, in the next k steps the situation repeats. Thus, mutants fixate with probability at most puv puv+pext 2r 2r+1/n2k r 0 0. Since vertex cover is known to be hard even on regular graphs, Lemma 6 implies the following theorem. Theorem 4. Fixation maximization in the biased voter process with r < 1 is NP-hard, even on regular undirected graphs. Submodularity considerations. Lemma 6 implies that max S V,|S|=k fp G 0 (S) cannot be approximated within any multiplicative factor in polynomial time, unless P = NP, since such an algorithm would decide whether S is a vertex cover on G. That is so even though Lemma 5 implies, by symmetrically exchanging mutant and resident roles, that the extinction probability 1 fp G r (S) for r < 1 is submodular. Fixation maximization with r < 1 is thus equivalent to minimizing a submodular function subject to the constraint |S| = k. Although the minimization of submodular functions without constraints is polynomially solvable, simple cardinality constraints render it intractable [Svitkina and Fleischer, 2011]. 6 Experiments Here we present some selective case studies on the performance of various heuristics solving the fixation maximization problem for the biased voter process. Our studies do not aim to be exhaustive, but rather offer some insights that may drive future work. We consider six heuristics for the choice of the seed set, namely (i) high degree, (ii) high temperature, defined as T (u) = P v w(v, u), (iii) high pagerank, (iv) high eigenvalue centrality, (v) high betweeness centrality, (vi) high closeness centrality, and the Greedy algorithm (Theorem 3) that provides an approximation guarantee for r 1. We evaluate all methods on four networks from the Netzschleuder database [Peixoto, 2020], chosen arbitrarily. In each case, we choose a budget k equal to 5% of the nodes of the graph. Fig. 3 shows the performance for various biases r 1. The networks Wiki and Polblogs are well-optimizable by almost all heuristics, possibly except high closeness centrality in the second case that performs visibly worse (though not by much). The Twitter graph is more challenging, while the Elegans graph is the most difficult to optimize, with high variability on heuristic performance. Unsurprisingly, the Greedy algorithm dominates the performance on this benchmark, which is expected given its theoretical guarantees (Theorem 3). Among the heuristics, high pagerank appears to be the most consistently performant, and the first one to match the performance of Greedy on the Elegans network. 7 Conclusion We have studied the optimization problem of selecting a cardinality-constrained seed set of mutants that maximizes the fixation probability in the classic biased voter process. We have shown that the problem exhibits intricate complexity properties in the presence of biases r = 1. In particular, the problem is NP-hard in both regimes r > 1 and r < 1, while the latter case is also hard to approximate. On the positive side, we have shown that the optimization function is monotone and submodular, and can thus be approximated efficiently within a factor (1 1/e). Interestingly, our results on optimization hardness imply that even just computing the fixation probability over randomly chosen seed sets is also NP-hard. Random seed sets arise in genetic/biological settings [Kaveh et al., 2015; Allen et al., 2020; Tkadlec et al., 2020], due to the random nature of novel mutations. Interesting future work includes investigating better approximation factors for r > 1, and an in-depth search for good heuristics. [Allen et al., 2015] Benjamin Allen, Christine Sample, Yulia Dementieva, Ruben C Medeiros, Christopher Paoletti, and Martin A Nowak. The molecular clock of neutral evolu- Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) tion can be accelerated or slowed by asymmetric spatial structure. PLo S Computat Biol, 11(2):e1004108, 2015. [Allen et al., 2020] Benjamin Allen, Christine Sample, Robert Jencks, James Withers, Patricia Steinhagen, Lori Brizuela, Joshua Kolodny, Darren Parke, Gabor Lippner, and Yulia A. Dementieva. Transient amplifiers of selection and reducers of fixation for death-birth updating on graphs. PLOS Computat Biol, 16(1):1 20, 01 2020. [Antal et al., 2006] T. Antal, S. Redner, and V. Sood. Evolutionary dynamics on degree-heterogeneous graphs. Phys. Rev. Lett., 96:188104, May 2006. [Bhat and Redner, 2019] Deepak Bhat and S. Redner. Nonuniversal opinion dynamics driven by opposing external influences. Phys. Rev. E, 100:050301, Nov 2019. [Brendborg et al., 2022] Joachim Brendborg, Panagiotis Karras, Andreas Pavlogiannis, Asger Ullersted Rasmussen, and Josef Tkadlec. Fixation maximization in the positional moran process. ar Xiv preprint ar Xiv:2201.02248, 2022. [Broom et al., 2010] M Broom, C Hadjichrysanthou, J Rycht aˇr, and BT Stadler. Two results on evolutionary processes on general non-directed graphs. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 466(2121):2795 2798, 2010. [Bui et al., 1987] Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171 191, 1987. [Castellano et al., 2009] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics of social dynamics. Rev. Mod. Phys., 81:591 646, May 2009. [Clifford and Sudbury, 1973] Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika, 60(3):581 588, 1973. [D ıaz et al., 2014] Josep D ıaz, Leslie Ann Goldberg, George B Mertzios, David Richerby, Maria Serna, and Paul G Spirakis. Approximating fixation probabilities in the generalized moran process. Algorithmica, 69(1):78 91, 2014. [Domingos and Richardson, 2001] Pedro Domingos and Matt Richardson. Mining the network value of customers. In ACM SIGKDD, KDD 01, page 57 66, 2001. [Durocher et al., 2022] Loke Durocher, Panagiotis Karras, Andreas Pavlogiannis, and Josef Tkadlec. Invasion dynamics in the biased voter process. ar Xiv preprint ar Xiv:2201.08207, 2022. [Even-Dar and Shapira, 2007] Eyal Even-Dar and Asaf Shapira. A note on maximizing the spread of influence in social networks. In WINE, pages 281 286, 2007. [He and Yao, 2001] Jun He and Xin Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial intelligence, 127(1):57 85, 2001. [Hindersin and Traulsen, 2015] Laura Hindersin and Arne Traulsen. Most undirected random graphs are amplifiers of selection for birth-death dynamics, but suppressors of selection for death-birth dynamics. PLo S Comput Biol, 11(11):e1004437, 2015. [Kaveh et al., 2015] Kamran Kaveh, Natalia L Komarova, and Mohammad Kohandel. The duality of spatial death birth and birth death processes and limitations of the isothermal theorem. Royal Society open science, 2(4):140465, 2015. [Kempe et al., 2003] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In ACM SIGKDD, pages 137 146, 2003. [Lengler, 2020] Johannes Lengler. Drift analysis. In Theory of Evolutionary Computation, pages 89 131. Springer, 2020. [Li et al., 2018] Yuchen Li, Ju Fan, Yanhao Wang, and Kian Lee Tan. Influence maximization on social graphs: A survey. IEEE TKDE, 30(10):1852 1872, 2018. [Liggett, 1985] T. Liggett. Interacting Particle Systems. Classics in mathematics. Springer New York, 1985. [Mc Avoy and Allen, 2021] Alex Mc Avoy and Benjamin Allen. Fixation probabilities in evolutionary dynamics under weak selection. Journal of Mathematical Biology, 82(3):1 41, 2021. [Mossel and Roch, 2007] Elchanan Mossel and Sebastien Roch. On the submodularity of influence in social networks. In STOC, page 128 134, 2007. [Nemhauser et al., 1978] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions i. Math. Program., 14(1):265 294, December 1978. [Ohtsuki et al., 2006] Hisashi Ohtsuki, Christoph Hauert, Erez Lieberman, and Martin A Nowak. A simple rule for the evolution of cooperation on graphs and social networks. Nature, 441(7092):502, 2006. [Peixoto, 2020] Tiago P. Peixoto. Netzschleuder: the network catalogue, repository and centrifuge. https:// networks.skewed.de, 2020. Accessed: 2021-11-30. [Svitkina and Fleischer, 2011] Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal on Computing, 40(6):1715 1737, 2011. [Talamali et al., 2021] Mohamed S. Talamali, Arindam Saha, James A. R. Marshall, and Andreagiovanni Reina. When less is more: Robot swarms adapt better to changes with constrained communication. Science Robotics, 6(56):eabf1416, 2021. [Tkadlec et al., 2020] Josef Tkadlec, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. Limits on amplifiers of natural selection under death-birth updating. PLOS Computational Biology, 16(1):1 13, 01 2020. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)