On a Voter Model with Context-Dependent Opinion Adoption

1 Introduction

The voter model is a well-studied stochastic process defined on a graph to model the spread of opinions (or genetic mutations, beliefs, practices, etc.) in a population [Liggett, 1985; Hassin and Peleg, 2001]. In a voter model, each node maintains a state, and when a node requires updating, it will import its state from a randomly chosen neighbor. Updates can be asynchronous, with one node activating per step [Liggett, 1985], or synchronous, with all nodes activating in parallel [Hassin and Peleg, 2001]. The voter model on a graph has been introduced in the 1970s to model opinion dynamics. The case of a complete graph is also very well-known in population genetics, where it was introduced even earlier to study the spread of mutations in a population [Ewens, 2012; Nowak, 2006].

Mathematically, among the main quantities of interest in the study of voter models, there are the fixation probability of an opinion-the probability of reaching a configuration in which each node adopts such opinion-and the expected consensus (or absorption) time-the expected number of steps before all nodes agree on an opinion. Such quantities could in principle be computed for any n-node graph by defining a Markov chain on a set of C n configurations, where C is the number of opinions, but such an approach is computationally infeasible even for moderate values of n. Therefore, a theoretical analysis of a voter process will often focus on obtaining upper and lower bounds for these quantities, still drawing heavily on the theory of Markov chains [Aldous and Fill, 2002; Levin et al., 2009], but with somewhat different approaches and tools for the synchronous and asynchronous cases.

A limitation of the standard voter process is that the dynamics is oblivious to the states of both the agent u that is updating and of the neighbor that u copies its state from, and the copying always occurs. One could easily imagine a situation (for example, in politics) where an agent holding opinion a is more willing to adopt the opinion b of a neighbor rather than to adopt opinion c. In general, the probability of abandoning opinion a in favor of opinion b might depend on both a and b. This motivates the study of biased voter models [Berenbrink et al., 2016; Sood et al., 2008] and in particular motivates us to introduce a voter model with an opinion adoption probability that depends on the context, that is, on the opinions of both agents involved in an opinion spreading step.

We define and study extensions of the voter model that allow the opinion adoption probability to depend on the pair of opinions involved in an update step. We consider both an asynchronous variant and a synchronous variant of a contextdependent voter model with two opinions, 0 and 1. We assume that an agent holding opinion c ∈ {0, 1} is willing to copy the opinion of an agent holding opinion c′ ∈ {0, 1} with some probability αc,c′ , which models the bias in the update. We study both the fixation probabilities and the expected consensus time.

1.1 Our Findings

In general, a seemingly minor feature as the form of bias we consider has a profound impact on the analytical tractability of the resulting model. While the unbiased case 1 can still be connected to a variant of the voter model and analyzed accordingly with some extra work, the same is not possible for the biased case. Specifically, in Section 3 we prove that a lazy variant of the voter model is equivalent (i.e., it produces the same distribution over possible system's configurations) to the unbiased variant of the model we consider. The proof, given in the full paper version 2 for the synchronous case, uses a coupling between the Markov chains that describe the two models. For the asynchronous case, this allows us to directly leverage known connections between the asynchronous voter model and random walks (Proposition 1). For the case of the clique, this general result can be improved, providing explicit, tight bounds on expected consensus time (Theorem 1). In the synchronous case, the above connection is not immediate (i.e., Proposition 1 does not apply) and analyzing expected time to consensus requires adapting arguments that have been used for continuos Markov chains to the synchronous, discrete setting (Theorem 2).

1 The model is unbiased when α0,1 = α1,0.

The biased case is considerably harder to analyze, the main reason being that it is no longer possible to collapse the Markov chain describing the system (whose state space is in general the exponentially large set of all possible configurations) to a "simpler" chain, e.g., a random walk on the underlying network, not even in the case of the clique. Despite these challenges, some trends emerge from specific cases. Interestingly, it is possible to derive the exact fixation probabilities for the class of regular networks, highlighting a nonlinear dependence on the bias (Theorem 3), while an asymptotically tight analysis for the clique (Theorem 4) suggests that the presence of a bias may have a positive impact on achieving faster consensus in dense networks. Though seemingly intuitive, this last aspect is not a shared property of biased opinion models in general [Montanari and Saberi, 2010; Anagnostopoulos et al., 2022]. The behavior of the model is considerably more complex and technically challenging in the synchronous, biased case. In particular, the preliminary results that we obtain highlight a general dependence of fixation probabilities (Proposition 2) and, notably, expected consensus time (Theorem 5) on both the bias and the initial configuration.

1.2 RelatedWork

For the sake of space, we mostly discuss results that are most closely related to the setting we consider.

Voter and Voter-Like Models. Due to its versatility, the voter model has been defined multiple times across different disciplines and has a vast literature. As mentioned in the introduction, the special case of the voter model on a complete graph was first introduced in mathematical genetics, being closely related to the so-called WrightFisher and Moran processes [Moran, 1958; Kimura, 1962; Ewens, 2012]. The first asynchronous formulation of a voter model on a connected graph has been proposed in the probability and statistics community in the 1970s [Liggett, 1985; Donnelly and Welsh, 1983], while [Hassin and Peleg, 2001] was the first study of this model in a synchronous setting. A classic result of these papers is that the fixation probability of an opinion c is equal to the weighted fraction of nodes holding opinion c, where the weight of a node is given by its degree [Hassin and Peleg, 2001; Sood et al., 2008].

2 http://arxiv.org/abs/2305.07377

The expected consensus time of the voter model is much more challenging to derive exactly, even for highly structured graphs. In the asynchronous case, it has often been studied by approximating the process with a continuous diffusion partial differential equation [Ewens, 2012; Sood et al., 2008; Baxter et al., 2008]. For two opinions on the complete graph, this yields the approximation

where T(n) is the expected consensus time on the n-clique, k is the number of nodes initially holding the first opinion and h(p) = -p ln p - (1 - p) ln(1 - p) [Sood et al., 2008; Ewens, 2012]. To the best of our knowledge, however, no error bound was known for such diffusion approximations 3 . Another approach is to use the duality between voter model and coalescing random walks [Liggett, 1985; Donnelly and Welsh, 1983], which involves no approximations, but the resulting formulas are hard to interpret, and to paraphrase Donnelly and Welsh [Donnelly and Welsh, 1983], "an exact evaluation of the expected absorption time for a general regular graph is a horrendous computation". As for approximations, expected consensus time for the voter model can be bounded by O((davg/dmin)(n/Φ)), where davg and dmin are, respectively, the average and minimum degrees [Berenbrink et al., 2016]. Most relevant to our discussion is the biased voter model considered by Berenbrink et al. [Berenbrink et al., 2016], in which the probability of adoption of an alternative opinion c′ depends on c′ (and only on c′ ). While our model is different if we consider more than 2 opinions, there are several other differences with respect to [Berenbrink et al., 2016] even in the binary case. In particular, Berenbrink et al. only consider the synchronous setting, they assume there is a "preferred" opinion that is never rejected and that there is a constant gap between the adoption probabilities of the preferred opinion and of the non-preferred one. Finally, they only consider the case where the number k of nodes initially holding the preferred opinion is at least Ω(logn). Thus, for example, their results do not apply in the neutral case (α01 = α10) or when k is, say, √logn. Our results for the biased, synchronous case (Theorem 5) are complementary to those in [Berenbrink et al., 2016]. While their results are stronger when the above assumptions hold, ours address the general and challenging case of an arbitrary initial configuration.

Pull vs Push. We only reviewed here models where nodes "pull" the opinion from their neighbor, since both the standard voter model and our generalization follow this rule, but we remark that "push" models, also known as invasion processes, have also been defined and studied on connected graphs [Lieberman et al., 2005; D´ıaz et al., 2016]. The asynchronous push model is sometimes called the (generalized) Moran process [D´ıaz et al., 2016; Nowak, 2006]. We remark that while the pull and push models are interchangeable on regular graphs, on irregular graphs their behavior can be markedly different.

3 For the n-clique, we show that (1) is correct within an additive O(n) term. See Theorem 1 (Section 3.1).

Other Biased Opinion Dynamics. We are aware of only a few analytically rigorous studies of biased opinion dynamics, including biased variants of the voter model [Sood et al., 2008; Berenbrink et al., 2016; Anagnostopoulos et al., 2022; Cruciani et al., 2021; Durocher et al., 2022], sometimes framed within an evolutionary game setting [Montanari and Saberi, 2010]. In general, these contributions address different models, be it because of the way in which bias in incorporated within the voting rule, the opinion dynamics itself or the temporal evolution of the process (e.g., synchronous vs asynchronous). We remark that all these aspects can deeply affect the overall behavior of the resulting dynamics. Specifically, as observed in a number of more or less recent contributions [Anagnostopoulos et al., 2022; Cruciani et al., 2021; Cooper et al., 2018; Hindersin and Traulsen, 2014], even minor changes in the model that would intuitively produce consistent results with a given baseline can actually induce fundamental differences in the overall behavior, so that it is in general hard to predict if and when results for one model more or less straightforwardly carry over to another model, even qualitatively. Less related to the spirit of this work, a large body of research addresses biased opinion dynamics using different approaches, based on approximations and/or numerical simulations. Examples include numerical simulations for large and more complex scenarios [Hindersin and Traulsen, 2014], mean-field or higher-order [Peralta et al., 2021] and/or continuous approximations [Assaf and Mobilia, 2012]. While these approaches can afford investigation of richer and more complex evolutionary game settings (e.g., [Peralta et al., 2021]), they typically require strong simplifying assumptions to ensure tractability, so that it is harder (if not impossible) to derive rigorous results.

2 Model Formulation

Notation. For a natural number k, let [k] := {0, 1, 2, . . . , k - 1}. If G = (V,E) is a graph, we write NG(u) (or simply N(u) if G can be inferred from the context) for the set of neighbors of node u in G. We write du for the degree of node u.

Model. We define an opinion dynamicsmodel on networks. The parameters of the model are: i) an underlying topology, given by a graph G on n nodes, with symmetric adjacency matrix A = (auv)u,v∈[n], where auv ∈ {0, 1}; ii) a number of opinions (or colors) C ⩾ 2; iii) an opinion acceptance matrix (αc,c′)c,c′∈[C], where αc,c′ ∈ [0, 1]. The initial opinion of each agent (node) u is encoded by some x(0) u ∈ [C].

For any node u ∈ [n], we define an update process Update(u) consisting of the following steps (summarized in Algorithm 1):

1. Sample: Sample a neighbor v of u uniformly at random, i.e., according to the distribution (au1/du, . . . , aun/du) where auv = 1 if {u, v} ∈ E and auv = 0 otherwise. Here du = |N(u)| = ∑v∈[n]auv is the degree of u.
2. Compare: Compare u's opinion c = xu with v's opinion c′ = xv.

Algorithm 1 Update(u)

• 1: Sample v ∈ N(u)
• 2: c ← xu; c′ ← xv
• 3: Sample θ ∈ [0, 1]
• 4: if θ < αc,c′ then
• 5: xu ← xv
• 6: return accept
• 7: return reject
• Accept/reject: With probability αc,c′ , set xu ← xv; in this case we say u accepts v's opinion. Otherwise, we say u rejects v's opinion.

We consider two variants of the model, differing in how the updates are scheduled. In one iteration of the asynchronous variant, u ∈ [n] is sampled uniformly at random and Update(u) is applied. In one iteration of the synchronous variant, each node u ∈ [n] applies Update(u) in parallel. We denote by x(t) u the random variable encoding the opinion of node u after t iterations of either the synchronous or the asynchronous dynamics (depending on the context).

The acceptance probabilities αc,c′ are parameters of the model. We note that the parameters αc,c′ with c = c′ are irrelevant for the dynamics, since a node sampling a neighbor of identical opinion will not change opinion, irrespective of whether it accepts the neighbor's opinion or not. Hence, to specify the opinion acceptance matrix C(C - 1) parameters are sufficient; we can assume that the diagonal entries are equal to 1. In particular, when C = 2 it is enough to specify α01 and α10. When α01 = α10 = 1, the model boils down to the standard voter model [Hassin and Peleg, 2001; Liggett, 1985].

In the rest of this work we assume C = 2. In this case, we say that the model is unbiased if the opinion acceptance matrix is symmetric, i.e., α01 = α10, and biased otherwise.

Quantities of Interest. The fixation probability of opinion 1 is the probability that there exists an iteration t such that x(t) u = 1 for all u ∈ [n]. The consensus time is the index of the first iteration t such that x(t) u = x(t) v for all u, v ∈ [n].

3 The Unbiased Setting

Before embarking on the biased case, which is substantially more complex, in this section we review or prove directly results for the unbiased setting (α01 = α10). We consider the asynchronous and the synchronous variants separately. In all formulas of this section, α = α01 = α10.

3.1 Asynchronous Variant

The main, intuitive observation about the unbiased asynchronous variant of our model is that the model can equivalently be described by a suitable, "lazy" voter model, where each iteration is either an idle iteration (with probability 1-α) or an iteration of the standard asynchronous voter model (with probability α).

This in turn implies that, for the fixation probability one can simply disregard the idle iterations and therefore obtain the same fixation probability as for the standard asynchronous voter model. In an arbitrary topology, this was derived by Sood et al. [Sood et al., 2008]: if we call ϕavoter the fixation probability of the asynchronous voter model, then

where x(0) u and du are respectively the initial opinion and the degree of node u. Since x(0) u ∈ {0, 1}, the fixation probability ϕavoter is proportional to the volume of nodes initially holding opinion 14 .

In the analysis of the expected consensus time, instead, one cannot ignore the idle iterations, but since they occur with probability 1 - α independently of other random choices, their effect is simply that of slowing down the standard asynchronous voter process by a factor 1/α. This intuitive argument can be formalized through a standard Markov chain coupling argument (see Appendix B).

Proposition 1. In the unbiased asynchronous case, the fixation probability is the same as for the standard asynchronous voter model. The expected consensus time is T avoter /α, where T avoter is the expected consensus time of the standard asynchronous voter model.

On the n-Clique Topology. As discussed in the introduction, a very natural question is: how large is the expected consensus time on the n-clique as a function of n? Despite this question having been studied multiple times before, in the literature there are either diffusion approximations with unknown error [Ewens, 2012], or exact formulas involving multiple partial summations that are hard to interpret asymptotically [Glaz, 1979]. By further analyzing a result of Glaz [Glaz, 1979], we derive here an explicit formula with bounded error that is easy to interpret, which in fact agrees with the diffusion approximation up to lower order terms, thus also showing that at least in this case, the diffusion approximation (1) yields a correct estimate.

In the unbiased asynchronous model, the expected consensus time on the clique is the same as the mean absorption time of the underlying birth-death process, the state of which is summarized by the number of nodes holding opinion 1. Call Tk(n) the expected consensus time when starting from a configuration with k nodes holding opinion 1, and the remaining n - k holding opinion 0. We prove that Tk(n) = O(n2 /α), more precisely:

Theorem 1. If α01 = α10 = α (for some α > 0), then for each k = 1, . . . , n - 1,

Proof. On an n-clique, the process is equivalent to a birthand-death chain [Levin et al., 2009] on n + 1 states

4 We note incidentally that the fixation probability can also be computed by suitably relating the asynchronous model to the transition matrix of the lazy random walk we discuss in Section 3.2. This connection is only mentioned here and made rigorous in the full paper version (Appendix A).

• 0, 1, 2, . . . , n (representing the number of nodes with opinion, say, 1). Let us define the following quantities:
• pk = α01k(n - k)/n(n - 1) is the probability that the number of nodes holding opinion 1 increases from k to k + 1 when 0 ⩽ k < n,
• qk = α10k(n - k)/n(n - 1) is the probability that the number of nodes holding opinion 1 decreases from k to k - 1 when 0 < k ⩽ n.

Note that pk = qk for all k due to the assumption α01 = α10. Define the vector T(n) as T(n) = (T1(n), . . . , Tn-1(n))⊤ and consider the matrix

The matrix B is constructed so that BT(n) = 1, where 1 is the all-1 vector. This holds because of the recurrence

for the mean consensus times. Therefore, T(n) = B-11. The matrix B can be explicitly inverted thanks to its tridiagonal structure; an explicit computation (see Appendix C) yields

where Hk is the k-th harmonic number, Hk = ∑kj=1 1/j. Recalling the asymptotic expansion Hn = ln n+γ+O(1/n), where γ is the Euler-Mascheroni constant,

where h(p) = -p ln p-(1-p) ln(1-p), which is such that 0 ⩽ h(p) ⩽ ln 2 for every p ∈ [0, 1].

3.2 Synchronous Variant

The analysis of the synchronous variant in the unbiased setting relies on the tight connection between the unbiased case of the opinion dynamics we consider and (lazy) random walks on networks.

Connections to Lazy RandomWalks. We next provide an equivalent formulation of our model, which reveals an interesting and useful connection to lazy random walks. To this purpose, consider the following, alternative dynamics, in which the behavior of the generic node u at each iteration is the following:

• Node u independently tosses a coin with probability of "heads" equal to α;
• If "heads", u samples a neighbor v u.a.r. and copies v's opinion; otherwise u does nothing and keeps her opinion.

Let us call M1 the synchronous model described in Section 2 andM2 the dynamics described above. ThenM1 and M2 are equivalent in the sense that, if they start from the same initial state, they generate the same probability distribution over all possible configurations of the system at any iteration t. Intuitively speaking this is true since inM1 each node first samples a neighbor and then it decides whether or not to copy its opinion according to the outcome of a coin toss, while inM2 each node first tosses a coin to decide whether or not to copy the opinion of one of the neighbors and then it samples the neighbor. Since the outcome of the coin toss and the choice of the neighbor are independent random variables, they produce the same distribution on the new opinion of the node when commuted. In the full paper version (Appendix D) we formalize the above equivalence and we prove it by appropriately coupling the two processes using an inductive argument.

Model M2 is interesting, since it describes a (lazy) voter model. As such (and as we explicitly show in the proof of Theorem 2), it is equivalent, in a probabilistic sense, to n lazy, coalescing random walks on the underlying network. This connection allows us to extrapolate the probability of consensus to a particular opinion and to adapt techniques that have been used to analyze the consensus time of the standard voter model [Hassin and Peleg, 2001; Aldous and Fill, 2002].

Theorem 2. Assume model M2 starts in a configuration in which all nodes of a subset W ⊂ V have opinion 1 and all other nodes have opinion 0. Let ϕ and T cons denote fixation probability (of opinion 1) and time to consensus, resp. Then: (I) ϕ = (∑u∈W du)/(∑u∈V du), (II) E [T cons ] ⩽ βnT hit , where T hit is the maximum expected hitting time associated with the graph and βn = O(1) when α ⩽ 1/2, while βn = ln n + 3 when α > 1/2.

Sketch of the proof. We here only give a short idea of the proof and we defer a full-detailed proof to the full paper version (Appendix E).

The proof of (I) follows from the observation that, if we call p(t) the vector p(t) = (p1(t), . . . , pn(t)) where pi(t) is the probability that node i has opinion 1 at round t conditional on the configuration at the previous round x(t-1) , then for every round t it holds that E [x(t+1) | x(t) ] = p(t+1) = Px(t) where P is the transition matrix of a lazy simple random walk on the underlying graph. Iterating the above equality we have that limt→∞E [x(t) | x(0) ] = π⊺x(0)1, where π is the stationary distribution of the random walk. Finally, the formula for ϕ follows from the fact that, for each node i, limt→∞E [x(t) i | x(0) ] equals the probability that node i ends up with opinion 1 and from the fact that the stationary probability of a simple random walk being on a node i is proportional to the degree of i.

The proof of (II) is an adaptation to our (discrete) case of the proof strategy for the continuous case described in [Aldous and Fill, 2002, Section 14.3.2]: we leverage on the relation between the convergence time of M2 and the maximum meeting time of two lazy random walks and, by using an appropriate martingale, we show that the maximum meeting time is upper bounded by the maximum hitting time (see Appendix E).

4 The Biased Setting

Without loss of generality, in the rest of this section we assume α01 ̸= α10 and we let r = α01/α10. In general, the biased setting is considerably harder to address, since the connection between our model and lazy random walks no longer applies in this setting, nor does it seem easy to track the evolution of the expected behavior of the model in a way that is mathematically useful.

4.1 Asynchronous Variant

In the asynchronous case, we give a result for the fixation probability holding for regular graphs, thanks to an equivalence with the fixation probability for the n-clique (see Appendix F). We also bound the expected consensus time in the specific case of the n-clique. The asynchronous variant of the process on the n-clique is equivalent to a birth-and-death chain on n+1 states 0, 1, 2, . . . , n representing the number of nodes with opinion 1. Now, however, the transition probabilities will not be symmetric. In fact, the transition probabilities can be specified by {pk, qk, rk}nk=0 where pk + qk + rk = 1, and:

• pk is the probability that the number of nodes holding opinion 1 increases from k to k + 1 when 0 ⩽ k < n,
• qk is the probability that the number of nodes holding opinion 1 decreases from k to k - 1 when 0 < k ⩽ n,
• rk is the probability that the number of nodes holding opinion 1 remains k when 0 ⩽ k ⩽ n.

Due to our definition of the opinion dynamics, we have p0 = qn = 0 and, for 0 < k < n,

Theorem 3. Let r = α01/α10 and let ϕk be the fixation probability of opinion 1 on a regular n-nodes graph starting from a state in which k nodes hold opinion 1. Then, for r /∈ {0, 1},

Proof. Thanks to the equivalence of the fixation probability between a regular n-nodes graph and an n-clique (see Appendix F), and by the analysis of a general birth-death process (see for example [Nowak, 2006, Section 6.2]), we get

where γj = qj/pj = α10/α01 = 1/r for all j. Hence

Note that when r → 1, we can evaluate ϕk by applying L'Hˆopital's rule to (3) and get ϕk = k/n, which is consistent with the results for the unbiased setting. When r = 0, nodes can only switch from opinion 1 to opinion 0, so clearly ϕk = 0; this is also consistent with (3) when r → 0.

It is interesting to note that the expression from (3) coincides with the fixation probability in the standard Moran process [Nowak, 2006, Chapter 6] when mutants (say, nodes with opinion 1) have a relative fitness equal to α01/α10, and in the initial configuration there are k mutants out of n nodes. In other words, on an n-nodes regular graph the ratio α01/α10 can be interpreted as a fitness of sorts, even though there is no notion of fitness or selection built in our model (recall that nodes are activated uniformly at random).

For the n-clique we are also able to bound the expected consensus time. While the logic of the proof is similar to the one of Theorem 1, the proof itself is considerably more involved in the asymmetric setting, leading to qualitatively different results-namely, an O(n log n) instead of an O(n2 ) worst case bound. The reader is deferred to the full paper version (Appendix G) for full details.

Theorem 4. If Tk(n) is the expected consensus time in the n-clique when starting from a state with k nodes holding opinion 1, and α01, α10 are constants, then for each k = 1, . . . , n - 1,

and for some values of k the above bound is tight.

4.2 Synchronous Variant

In order to bound the fixation probabilities, denote by x(t) ∈ {0, 1}n the state of the system at time t. Conditioned on the state vector x(t) , the probability that x(t+1) u = 1 can be expressed as follows:

This follows since the probability that node u samples a neighbor with opinion 1 is ∑v auvx(t) v /du and:

• when x(t) u = 1, then x(t+1) u = 1 iff either u samples a neighbor with opinion 1, or u samples a neighbor with opinion 0 and does not accept its opinion (these two events are disjoint);
• when x(t) u = 0, then x(t+1) u = 1 iff u samples a neighbor with opinion 1 and accepts its opinion.

We did not exploit the graph topology so far. In the case of the n-clique (with loops, to simplify some expressions), let k(t) be the number of nodes with opinion 1 at time t. Specializing the formulas derived above we get

Note that the expression above depends only on k(t) and x(t) u , and not on the entire state x(t) . The process is thus equivalent to sampling, at each step t, k(t) Bernoulli random variables (r.v.) with parameter βk := 1-α10(1-k(t) /n), and n-k(t) bernoulli r.v. with parameter γk := α01k(t) /n. Collectively, the outcomes of these r.v. constitute the new state x(t + 1).

Then,

which, posing y(t) = k(t) /n, can be written as

Proposition 2. Assume α01 ⩽ α10. Then the fixation probability of opinion 0 is at least the fraction of agents holding opinion 0.

Proof. Under the assumption α01 ⩽ α10,

Hence, the succession (E [y(t) ])t is monotone and bounded and attains a limit. This limit must coincide with the fixation probability, because y(t) converges in distribution to a bernoulli random variable y(∞) and E [y(∞) ] = P (y(∞) = 1) = P (∃t : y(t) = 1) equals the fixation probability. Since E [y(0) ] = y(0) = k(0) /n, the fixation probability of opinion 1 must be at most k(0) /n, so that of opinion 0 is at least 1-k(0) /n.

Regarding the expected consensus time, we show the following by using the technique of drift analysis [Lengler and Steger, 2018].

Theorem5. If Tk(n) is the expected consensus time in the nclique when starting from a configuration with k nodes holding opinion 1, and α01 = α10 - ϵ, then

In particular, Tk(n) ⩽ min(2k/ϵ, n/ϵ) for each k = 1, 2, . . . , n - 1.

Proof. We adapt a proof of [Lengler and Steger, 2018, Theorem 2.1] to our setting, since their result is not suitable for systems with more than one absorbing state. In the remainder, we assume α01 < α10, we let ϵ = α10 - α01, and we let z(t) = k(t) /n, i.e., z(t) is the fraction of agents with opinion 1 at time t. We begin by defining the following stopping time:

This definition is akin to the one given in [Lengler and Steger, 2018, Theorem 2.1], but it accounts for the presence of two absorbing states in the Markov chain defined by z(t) . Moreover, z(t) = z(t-1) for every t > T, since z(t) does not change after absorption (regardless of the absorbing state). We next note that for every t, z(t) ∈ S = {0, 1n , . . . , 1- 1n , 1}. Moreover, for every s ∈ S we have E [z(t+1) | z(t) = s] = s - ϵs(1 - s), whence:

with the last quantity at least ϵ 1n (1 - 1n ) for s ∈ S \ {0, 1}. Next:

where the first equality follows since, for s ̸∈ {0, 1}, z(t) = s implies T > t. Similarly to the proof of [Lengler and Steger, 2018, Theorem 2.1], the equality above implies

We let δ = ϵ 1n (1 - 1n ) for conciseness. We next have:

and therefore

In the derivations above, (a) simply follows from the law of total probability, considering that T ⩽ t implies z(t) ∈ {0, 1}, (b) follows from (5), while (c) follows by replacing the equation of E [z(t) ] into the last step of the derivation. Next, we note that

by definition of the z(t) , whence we obtain:

Now, observe that (6) is exactly [Lengler and Steger, 2018, (2.4) in Theorem 2.1]. From this point, the proof proceeds exactly as in [Lengler and Steger, 2018, (2.4) in Theorem 2.1], so that we finally have:

if at time t = 0 we have k agents with opinion 1.

5 Conclusions and Outlook

Natural directions for future work include considering more opinions and general topologies.

More Opinions. The case of more opinions presents no major challenges in the unbiased case, both in its asynchronous and synchronous variants, something we did not discuss for the sake of space. In this case, one can simply focus on one opinion at a time, collapsing the remaining opinions into an "other" class. Proceeding this way, it is easy to extend the results we presented in Section 3 to the general case: for k > 2 opinion, the fixation probability for opinion i is ∑u∈W du ∑u du , where W is the subset of nodes with opinion i in the initial configuration. The biased case is considerably harder and the technical barriers are twofold: one is the general difficulty of characterizing the expected change of the global state in the biased setting even in the case of 2 opinions (see next paragraph). The other is the possible presence of rock-paper-scissors like dynamics that may arise depending on the distribution of the opinion biases.

General Topologies. As also suggested by previous work, albeit for different models [Montanari and Saberi, 2010; Anagnostopoulos et al., 2022; Lesfari et al., 2022], we believe the biased case might give rise to diverse and possibly counterintuitive behaviors. In general, a crucial technical challenge is characterizing the evolution of the global state across consecutive steps, since this in general depends on the current configuration in a way that is highly topology-dependent and hard to analyze. Some recent results [Schoenebeck and Yu, 2018; Shimizu and Shiraga, 2020] proposed techniques relying on variants of the expander mixing lemma to investigate quasi-majority dynamics on expanders. Unfortunately, these techniques do not obviously extend to the biased voter models we consider. Indeed and interestingly, the class of dynamics these techniques apply to does not even include the standard voter model as a special case.

In general, we believe that extending and/or improving our results for the biased setting might require refining important techniques, such as those of [Schoenebeck and Yu, 2018; Shimizu and Shiraga, 2020] or the ones discussed in [Lengler and Steger, 2018].

Acknowledgements

• Partially supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets", the EC H2020RIA project "SoBigData++" (871042), and the MIUR PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets.
• Work of the second author was carried out in association with Istituto di Analisi dei Sistemi ed Informatica, Consiglio Nazionale delle Ricerche, Italy. · Supported by the Austrian Science Fund (FWF): P 32863-N.
• This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 947702).