Biased Opinion Dynamics: When the Devil is in the Details

1 Introduction

Opinion formation in social groups has been the focus of extensive research. Whereas many models considered in the literature confer the same intrinsic value to all opinions [Coates et al., 2018], one might expect a group to quickly reach consensus on a clearly "superior" alternative, if present. Yet, phenomena such as groupthink may delay or even prevent such an outcome.

In this perspective, we investigate models of opinion formation in which a bias towards one of two possible opinions exists, for instance, reflecting intrinsic superiority of one alternative over the other. 1 In the remainder, we use labels 0 and

1 Characterizing the notion of "superiority" is typically context-

1 for the two opinions and we assume that 1 is the dominant opinion, that is, the one towards which the agents have a bias. We investigate this question in a mathematically tractable setting, informally described as follows.

Assume some underlying opinion dynamics D. Starting from an initial state in which all agents share opinion 0, the system evolves in rounds. In each round, one agent is selected uniformly at random. With some probability α, the agent adopts 1, whereas with probability 1-α, the agent follows D to revise its opinion on the basis of those held by its neighbors in an underlying network.

Although the general model that we consider is simple and, under mild conditions on D, the family of processes that it describes always admits global adoption of opinion 1 as the only absorbing state, convergence to this absorbing state exhibits a rich variety of behaviors, which depends in nonobvious ways on the interplay between the network structure and the underlying opinion dynamics. The relatively simple, yet general, model that we consider allows analytical investigation of the following question:

How does a particular combination of network structure and opinion dynamics affects convergence to global adoption of the dominant opinion? In particular, how conducive is a particular combination to rapid adoption?

1.1 Main Findings

In general, the interplay between underlying network structure and opinion dynamics may elicit quite different collective behaviors. In Section 4, we show that the expected time for consensus on the dominant opinion grows exponentially in the minimum degree under the majority update rule, in which agents update their opinion to the majority opinion in their neighborhoods [Krapivsky and Redner, 2003]. Using asymptotic notation and denoting the number of agents in the network by n, we obtain that the convergence time is super-polynomial in expectation whenever the minimum degree is ω(logn). One might wonder, whether the converse occurs, namely, whether a logarithmic maximum degree allows to obtain (expected) polynomial convergence time to the absorbing state. Even though we prove that this is indeed the case for specific topologies such as cycles or restricted graph families, this does not seem to hold in general (see discussion in Section 6). The results for majority are at odds with those we obtain in Section 5 for the voter model, where agents copy the opinion of a randomly selected neighbor [Liggett, 2012]. In this case, convergence to the absorbing state occurs within O ( 1α n log n) rounds with high probability, regardless of the underlying network structure. We emphasize that convergence time remains O (n1+s log n) when α = Θ ( 1 ns ) for any s > 0. Although results suggesting a negative impact of network density on convergence time have been proposed in the past, albeit for quite different models (e.g., [Montanari and Saberi, 2010]), the results above suggest that there might be more to the issue. In particular, the interplay between opinion dynamics and underlying network structure seems more complex than anticipated, with the former playing a key role in amplifying network effects. At a higher level, we provide a simple mathematical framework to investigate the interplay between opinion dynamics and underlying network structure in a unified setting, allowing comparison of different update rules with respect to a common framework. In this respect, we hope that our work moves in the direction of a shared framework to investigate opinion dynamics, as advocated in [Coates et al., 2018].

dependent and may be far from obvious. We remark that this aspect is outside the scope of this paper.

2 RelatedWork

The problem we consider touches a number of areas where similar settings have been considered, with various motivations. The corresponding literature is vast and providing an exhaustive review is infeasible here. In the paragraphs that follow, we discuss contributions that relate most closely to the topic of this paper.

2.1 Opinion Diffusion and Consensus

Opinion dynamics are widely used to investigate how a group of agents modify their beliefs under the influence of other agents and possibly exogenous factors. A number of models have been proposed in the more or less recent past, mostly motivated by phenomena that arise in several areas, ranging from social sciences, to physics and biology. We refer the reader to [Coates et al., 2018] and references therein for a recent, general overview of opinion dynamics in multi-agent systems. A first distinction is between settings in which the set of possible beliefs is continuous, for instance, the interval [0, 1]. This setting has been the focus of extensive research in social sciences and economics [DeGroot, 1974; Friedkin and Johnsen, 1990; Friedkin and Bullo, 2017]. In this paper, we consider the case in which opinions are drawn from a discrete set, a setting that also received significant attention in the recent past. In particular, we focus on the majority rule and the voter model. Investigation of the majority update rule originates from the study of agreement phenomena in spin systems [Krapivsky and Redner, 2003]. The voter model was motivated by the study of spatial conflict between species in biology and interacting stochastic processes/particle systems in probability theory and statistics [Clifford and Sudbury, 1973; Holley et al., 1975; Liggett, 2012]. These two models have received renewed attention in the recent past, the focus mostly being on the time to achieve consensus and conditions under which consensus on one of the initial opinions is achieved with a minimum degree of confidence. The voter model is by nowwell understood. In particular, increasingly tight bounds on convergence time for general and specific topologies have been proposed over the past [Hassin and Peleg, 1999; Cooper et al., 2013], and it is known that the probability of one particular opinion to prevail is proportional to the sum of the degrees of the nodes holding that opinion at the onset of the process [Donnelly and Welsh, 1983].

2.2 Consensus and Network Structure

Network structure has been known to play an important role in opinion diffusion and influence spreading for quite some time [Morris, 2000], under a variety of models. For example, consensus under the voter model and dependence of its convergence on the underlying network topology have been thoroughly investigated [Donnelly and Welsh, 1983; Hassin and Peleg, 1999; Cooper et al., 2013]. For majority dynamics, [Auletta et al., 2015] characterized topologies for which an initial majority can be subverted, showing that this is possible for all but a handful of topologies, including cliques and quasi-cliques. On the other hand, regardless of the network, there is always an initial opinion distribution, such that the final majority will reflect the initial one, whereas computing an initial opinion configuration that will subvert an initial majority is topology-dependent and NP-hard in general [Auletta et al., 2018]. A number of recent contributions investigated (among other aspects) the relationship between network structure and consensus in opinion formation games [Ferraioli et al., 2016; Ferraioli and Ventre, 2017] and [Auletta et al., 2019] investigated extensions of the Friedkin-Johnsen model to evolving networks. 2 Even though a high expansion of the underlying graph typically accelerates convergence [Cooper et al., 2012; Kanade et al., 2019] in many opinion dynamics, some recent work explicitly points to potentially adverse effects of network structure on the spread of innovation, at least in scenarios where opinion updates occur on the basis of private utilities that reflect both the degree of local consensus and intrinsic value of the competing opinions [Montanari and Saberi, 2010; Young, 2011]. Although some of our findings are qualitatively consistent with previous work albeit under completely different models (in particular, [Montanari and Saberi, 2010]), our overall approach is very different, because it completely decouples the mechanism of opinion formation from the modeling of the bias, allowing for a clear-cut mathematical characterization of the interplay between bias, underlying opinion dynamics, and network structure.

2.3 Different Forms of Bias

Prior literature has studied the presence of bias in opinion dynamics. We briefly review contributions that are at least loosely related to our framework. For the voter and majority update rules, [Mukhopadhyay et al., 2016] introduces bias in the form of different, opinion-dependent firing-rate frequencies of the Poisson clocks that trigger agents' opinion updates, implicitly enforcing a bias toward the opinion with lower associated rate. Although different, their model is similar to ours in spirit and some of their results for the voter model are consistent with ours. Yet, these results apply only in expectation and to very dense networks with degree Ω(n), whereas our results for the voter model hold for every undirected graph. A somewhat related line of research addresses the presence of stubborn agents or zealots. Loosely speaking, stubborn agents have a bias toward some (initially or currently) held opinion, and zealots are agents that never deflect from some initial opinion. Restricting to the discrete-opinion setting, which is the focus of this paper, 3 the role of zealots and their ability to subvert an initial majority have been investigated for the voter model (see [Mobilia, 2003] and followup work), and [Auletta et al., 2017] investigates majority dynamics in the presence of stubborn agents that are biased toward the currently held opinion, providing a full characterization of conditions under which an initial majority can be subverted.

2 For the sake of space, we are limiting to recent contributions that are more closely related to the topics of this study.

3 Notation and Preliminaries

Let G = (V, E) be an undirected graph with |V | = n nodes, each representing an agent. Without loss of generality, we assume that V = [n] := {1, . . . , n}. The system evolves in discrete time steps 4 and, at any given time t ∈ N, each node v ∈ V holds an opinion x(t) v ∈ {0, 1}. We use the term opinion liberally here, in the sense that 0 and 1 in general represent competing alternatives, whose meaning is contextdependent and outside the scope of this paper. We denote by x(t) = (x(t) 1 , . . . , x(t) n )ᵀ the corresponding state of the system at time t. We assume that the initial state of the system is x(0) = 0 = (0, . . . , 0)ᵀ ; such assumption is discussed in Section 6. For each v ∈ V , we denote the neighborhood of v with Nv := {u ∈ V : {u, v} ∈ E} and the degree of v with dv := |Nv|. Finally, ∆ := minv∈V dv is the minimum degree of the nodes in G.

Our framework assumes that agents exhibit a bias toward one of the opinions (e.g., reflecting intrinsic superiority of a technological innovation over the status quo), without loss of generality 1, which we henceforth call the dominant opinion. We model bias as a probability, with a parameter α ∈ (0, 1]. All dynamics we consider are Markovian, that is, given the underlying graph G, the distribution of the state x(t) at round t depends only on the state x(t-1) at the end of the previous round. Moreover, they have x = 1 = (1, . . . , 1)ᵀ as the only absorbing state. We use τ to denote the absorption time, which is the number of rounds for the process to reach the absorbing state 1. Finally, for a family of events {En}n∈N we say that En occurs with high probability (w.h.p., in short) if a constant γ > 0 exists such that P(En) = 1 -O(n-γ ), for every sufficiently large n.

3 For the continuous case, there is a vast literature; see the seminal paper [Friedkin and Johnsen, 1990] and follow-up work.

4 This is equivalent to the asynchronous model in which a node revises its opinion at the arrival of an independent Poisson clock with rate 1 [Boyd et al., 2006].

4 Absorption Time for Majority Dynamics

In this section, we investigate the time to reach consensus on the dominant opinion under the majority update rule. Formally, we study the following random process: Starting from the initial state x(0) = (0, . . . , 0)ᵀ , in each round t a node u ∈ [n] is chosen uniformly at random and u updates its value according to the rule

where α ∈ (0, 1] is the bias toward the dominant opinion 1 and MG(u, x) is the value held in configuration x(t-1) = x by the majority of the neighbors of node u in graph G:

and ties are broken uniformly at random, that is, if ∑v∈Nu xv = |Nu|/2 then MG(u, x) = 0 or 1 with probability 1/2.

It is easy to see that for every positive α, the above Markov chain has 1 as the only absorbing state. However, the rate of convergence is strongly influenced by the underlying graph G. In Section 4.1 we prove a lower bound on the expected absorption time that depends exponentially on the minimum degree. This result implies super-polynomial expected absorption times for graphs whose minimum degree is ω(log n). On the other hand, in Section 4.2 we prove that the absorption time is O(n log n) on cycle graphs and in Section 4.3 we present some more graph families with sub-logarithmic maximum degree and polynomial (expected) absorption time.

4.1 SlowConvergence on High-Density Graphs

In this section we prove a general lower bound on the expected absorption time, which depends only on the minimum degree ∆. To this purpose, we use the following standard lemma on birth-and-death chains 5 (see, for example, [Levin and Peres, 2017, Section 17.3] for a proof).

Lemma 4.1. Let {Xt}t be a birth-and-death chain with state space {0, 1, . . . , n} such that for every 1 ⩽ k ⩽ n - 1

with p + q ⩽ 1. For every i ∈ {0, 1, . . . , n} let τi be the first time the chain hits state i, that is, τi = inf{t |Xt = i}. If p ̸= q, the probability that starting from state k the chain hits state n before state 0 is

5 Birth-and-death chains are Markov processes for which, if in state k, a transition could only go to either state k +1 or state k -1.

.

It is not difficult to show that, for α ⩾ 1/2, every graph with minimum degree ∆ = Ω(log n) has O(n log n) absorption time, w.h.p. 6 In the next theorem we prove that, as soon as α is smaller than 1/2, the absorption time instead becomes exponential in the minimum degree.

Theorem 4.2. Let G = (V,E) be an undirected graph with minimum degree ∆. Assume that α ⩽ (1-ε) 2 , for an arbitrary constant 0 < ε < 1. The expected absorption time for the biased opinion dynamics under the majority update rule is

Proof. Let S(t) be the set of nodes with value 1 at time t. For each node u ∈ V , let n(t) u be the fraction of its neighbors with value 1 at round t:

Finally, let ¯ τ be the first round in which n(t) u ⩾ 1/2 for at least one node v ∈ V , namely,

Note that for each round t ⩽ ¯ τ all nodes have a majority of neighbors sharing opinion 0, thus the selected agent at time t updates its state to 1 with probability α and to 0 with probability 1 - α. Moreover, clearly τ ⩾ ¯ τ. We next prove that E[¯ τ ] ⩾ e ε2 6 ∆/(2n), which implies our thesis.

Notice that, for a node u with degree du that has k neighbors with value 1 in some round and for every t ⩽ ¯ τ, the probabilities pk(u) and qk(u) of increasing and decreasing, respectively, of one unit the number of its neighbors with value 1 are

Hence, because α ⩽ (1 - ε)/2, for every k ⩾ du/(2 + ε) we have that

Note that

From Lemma 4.1 it thus follows that, for each node u, as soon as the number of its neighbors with value 1 enters in the range (du/(2+ ε), du/2), the probability that it will reach du/2 before going back to du/(2 + ε) is at most

6 Because every time a node updates its opinion the node chooses opinion 1 with probability at least α, as soon as all nodes update their opinion at least once (it happens within O(n log n) time steps, w.h.p., by a coupon collector argument) if α ⩾ 1/2, every node u will have a majority of 1s in its neighborhood, w.h.p.

using (1-x)x ⩽ e-x2 for x ∈ [0, 1]. Hence, if we denote by Yu the random variable indicating the number of trials before having at least 1/2 of the neighbors of u at 1 we have that for every t ⩾ 0

where in the last inequality we used that 1 - x ⩾ e-3x/2 for every x ∈ [0, 1 2 ). Thus,

using 1 - e-x ⩽ x for every x. Finally, by using the union bound over all nodes, we have that

Thus, for ¯ t = e ε2 6 ∆/3n we have P(¯ τ ⩽ ¯ t) ⩽ 1/2 and the thesis follows fromMarkov inequality:

4.2 Fast Convergence on the Cycle

In this section, we prove that the absorption time on an nnode cycle graph is O( 1α n log n), w.h.p. We make use of the following structural lemma, whose proof is omitted because of lack of space.

Lemma 4.3 (Structural property of cycles). Let Cn be the cycle on n nodes and let every node v ∈ V have an associated state xv ∈ {0, 1}. Let us call Bi and Si the set of nodes in state i such that: every node v ∈ Bi has both neighbors in the opposite state and every node v ∈ Si has one single neighbor in the opposite state. The following holds:

Theorem 4.4 (Cycles). Let G = Cn be the cycle on n nodes. Under the majority update rule, we have τ = O ( 1α n log n), with high probability.

Proof. Denote by Vi the set of nodes with state i. Given a configuration x ∈ {0, 1}n of Cn, let Bi = {v ∈ Vi : ∀u ∈ Nv, xu ̸= i} and Si = {v ∈ Vi : ∃u,w ∈ Nv, xu ̸= xw} (see Lemma 4.3). Let Xt be the random variable indicating the number of nodes in state 1 at round t and observe that for every k, we have:

where we have called pk = α n-k n +(1-α) ( |B0| n + 12 |S0| n ), qk = (1 - α) ( |B1| n + 1 2 |S1| n ), and rk = 1-qk -pk. Hence, the expected value of Xt, conditioned to Xt-1 = k, is

where in derivation (a) we use Lemma 4.3. Therefore:

Solving this recursion with E[X0] = 0 we get

The expected number n-Xt of nodes in state 0 at round t is thus

which is smaller than 1n for t ⩾ 2α n logn. Hence,

where in (b) we use the Markov inequality.

4.3 Further Low-Density Graph Families

It is not difficult to show that convergence times are also polynomial in the cases of trees of degree O(logn) and disconnected cliques of size O(logn). These results are summarized as the following theorem, whose proof is relatively simple and is omitted for the sake of space.

Theorem 4.5 (Trees and disconnected cliques). Assume G = (V,E) is a tree of degree O(logn) (resp. a set of disconnected cliques, each of size O(logn)). Then, for every constant α ∈ (0, 1], the expected absorption time is polynomial.

5 Absorption Time for the Voter Model

As we mentioned in the introduction, the voter model has received considerable attention as an opinion dynamics in the more and less recent past [Liggett, 2012]. It may be regarded as a "linearized" form of the majority update rule, in the sense that, upon selection, a node pulls each of the two available opinions with probability proportional to the opinion's support within the node's neighborhood. Despite such apparent similarity, the two update rules result in quite different behaviors of the biased opinion dynamics. Namely, for the voter model, absorption times to the dominant opinion are polynomial with high probability as long as 1/α is polynomial, regardless of the underlying topology. These results are clearly at odds with those of Section 4.

The biased voter model can formally be defined as follows: Starting from some initial state x(0) , at each round t a node u ∈ [n] is chosen uniformly at random and its opinion is updated as

where α ∈ (0, 1] is a parameter measuring the bias toward the better opinion 1 and VG(u, x) is the value held in configuration x(t-1) = x by a node sampled uniformly at random from the neighborhood of node u. We assume x(0) = 0 for simplicity, though we remark that Theorem 5.1 below holds for any x(0) ∈ {0, 1}n .

As the proof of Theorem 5.1 highlights, the biased opinion dynamics under the voter update rule can be succinctly described by a nonhomogeneous Markov chain [Seneta, 2006]. Although nontrivial to study in general, we are able to provide tight bounds in probability for the simplified setting we consider.

Theorem 5.1. Let G = (V,E) be an arbitrary graph. The biased opinion dynamics with voter as update rule reaches state 1 within τ = O( 1α n log n) steps, with high probability.

Proof. For every node v ∈ V , the expected state of v at time t, conditioned on x(t-1) = x is

where P = D-1A is the transition matrix of the simple random walk on G (with D the diagonal degree matrix and A the adjacency matrix of the graph) and I is the identity matrix. Considering all nodes we can write the vector form of the previous equation as follows:

This immediately implies the following equation, relating expected states at times t - 1 and t (with E[x(0) ] = x):

Now, consider 1-x(t) , the difference between the absorbing state vector 1 and the state vector at a generic time t. Obviously, (1-x(t) )v ⩾ 0 deterministically, for every v and for every t. As for the expectation of this difference, we have:

where the equality is obtained by collecting and rearranging terms, after observing that both matrices P and I have eigenvalue 1 with associated eigenvector 1. Moreover, we have

with ˆ P := n-1 n-α [( 1-α n-1 ) P + I ] a stochastic matrix. This follows immediately by observing that both P and I are stochastic, so that all rows of (1 - α)P + (n - 1)I identically sum to n - α. By solving the recursion in Eq. (1) we obtain

where in (a) we use the fact that ˆ P t is a stochastic matrix, thus with main eigenvalue 1 and associated eigenvector 1. Next, observe that for every v, we have ( ˆ P tx(0) )v ⩾ 0, so we also have

Therefore, for every t ⩾ 2α n logn and for every v ∈ V we have E[1 - x(t) v ] ⩽ 1/n2 and, because the x(t) v 's are binary random variables:

where in the second-to-last inequality we used Markov's inequality. Taking a union bound concludes the proof.

Note that Theorem 5.1 implies that the convergence time is still O (n1+s log n) when α = Θ ( 1 ns ) for any s > 0, hence polynomial as long as s is constant.

6 Discussion and Outlook

In this paper, we considered biased opinion dynamics under two popular update rules, namely majority [Krapivsky and Redner, 2003] and the voter model [Liggett, 2012]. Although related, these two models exhibit substantial differences in our setting. Whereas the voter model enforces a drift toward the majority opinion within a neighborhood, in the sense that this is adopted with probability proportional to the size of its support, majority is a nonlinear update rule, a feature that seems to play a crucial role in the scenario we consider. This is reflected in the absorption time of the resulting biased opinion dynamics, which is O ( 1α n log n) for the voter model, regardless of the underlying topology, whereas it exhibits a far richer behavior under the majority rule, being super-polynomial (possibly exponential) in dense graphs. It may be worth mentioning that in the case of two opinions, the majority rule is actually equivalent to the (unweighted) median rule, recently proposed as a credible alternative to the weighted averaging of the DeGroot's and Friedkin-Johnsen's models [Mei et al., 2019].

Both scenarios we studied are instantiations of a general model that is completely specified by a triple (z, α,D), with z an initial opinion distribution, α ∈ (0, 1] a probability measuring the magnitude of the bias toward the dominant opinion, and D an update rule that specifies some underlying opinion dynamics. In detail, a biased opinion dynamics can be succinctly described as follows. The system starts in some state x(0) = z, corresponding to the initial opinion distribution; for t > 0, let x(t-1) = x be the state at the end of step t - 1. In step t, a node v is picked uniformly at random from V and its state is updated as follows:

where DG : V × {0, 1}n → {0, 1} is the update rule. 7 When the update rule is probabilistic (as in the voter model), DG(v, x) is a random variable, conditioned to the value x of the state at the end of step t - 1.

It is simple to see that 1 is the only absorbing state of the resulting dynamics, whenever α ̸= 0 and D does not allow update of an agent's opinion to one that is not held by at least one of the agent's neighbors, which is the case for many update rules in the discrete-opinion setting. We further remark that the initial condition x(0) = 0 considered in this paper is not intrinsic to the model, it rather reflects scenarios (e.g., technology adoption) where a new, superior alternative to the status quo is introduced, but its adoption is possibly slowed by inertia of the system. Although the reasons behind system's inertia are not the focus of this paper, inertia itself is expressed here as a social pressure in the form of some update rule DG. It is worth mentioning that Theorem 5.1 and the upper bounds given in Section 4.3 hold regardless of the initial opinion distribution.

This paper leaves a number of open questions. A first one concerns general upper bounds on convergence times under the majority update rule. Even though the topology-specific upper bounds given in Section 4 might suggest general upper bounds that depend on the maximum degree, thus mirroring the result of Theorem 4.2, this turns out to not be the case, with preliminary results suggesting a more complicated dependence on degree distribution. A further question is whether expected absorption time is always O(n log n) when α ⩾ 1/2, irrespective of the underlying dynamics and topology. This is clearly true for the voter model from Theorem 5.1 and it also holds for majority, whenever the underlying network has minimum degree Ω(logn) (see comment after Lemma 4.1 and footnote 6 for a sketch of the proof on dense graphs). We finally remark that our results and most results in related work only apply to the case of two competing opinions. An obvious direction for further research is extending our results to the case of multiple opinions.

Acknowledgments

Partially supported by the ERC Advanced Grant 788893 AMDROMA, the EC H2020RIA project "SoBigData++" (871042), the MIUR PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets," and by the University of "Tor Vergata" under research programme "Mission: Sustainability" project ISIDE (grant no. E81I18000110005).

7 The subscript G highlights the fact that result of the application of a given update rule D in general depends on both the current state and the underlying graph G. The above definition can be easily adjusted to reflect the presence of weights on the edges.