--- title: "Biased Majority Opinion Dynamics: Exploiting Graph k-domination" authors: - "Hicham Lesfari" - "Frédéric Giroire" - "Stéphane Pérennes" doi: "10.24963/ijcai.2022/54" url: "https://ijcai.org/proceedings/2022/54" pdf: "https://ijcai.org/proceedings/2022/0054.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "377-383" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Agent Societies" - "Agent-based and Multi-agent Systems: Agent-Based Simulation and Emergence" - "Agent-based and Multi-agent Systems: Agent Theories and Models" --- # Biased Majority Opinion Dynamics: Exploiting Graph k-domination Hicham Lesfari, Frédéric Giroire, Stéphane Pérennes *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 377-383. DOI: [10.24963/ijcai.2022/54](https://doi.org/10.24963/ijcai.2022/54) ## Abstract We study opinion dynamics in multi-agent networks where agents hold binary opinions and are influenced by their neighbors while being biased towards one of the two opinions, called the superior opinion. The dynamics is modeled by the following process: at each round, a randomly selected agent chooses the superior opinion with some probability α, and with probability 1-α it conforms to the opinion manifested by the majority of its neighbors. In this work, we exhibit classes of network topologies for which we prove that the expected time for consensus on the superior opinion can be exponential. This answers an open conjecture in the literature. In contrast, we show that in all cubic graphs, convergence occurs after a polynomial number of rounds for every α. We rely on new structural graph properties by characterizing the opinion formation in terms of multiple domination, stable and decreasing structures in graphs, providing an interplay between bias, consensus and network structure. Finally, we provide both theoretical and experimental evidence for the existence of decreasing structures and relate it to the rich behavior observed on the expected convergence time of the opinion diffusion model. ## Full text ## 1 Introduction In everyday life, when sharing or forming an opinion about a set of issues of interest, individuals often consult with their friends, relatives, acquaintances, or others, in their close social group. Furthermore, with the widespread use of online social networks, social influence comes to play a prominent role in several phenomena such as the diffusion of technological innovations, the rise of political movements, and the intensification of fears during outbreaks. Consequently, there has been a growing interest in understanding the opinion-forming processes that drive the formation of consensus and opinion clustering in social systems. Opinion dynamics are mathematical models that enable to investigate how a group of agents change their beliefs under the influence of other agents. While various models considered in the literature confer the same intrinsic value to all opinions [Coates et al., 2018], an agent may be biased towards a "preferred" opinion; for instance, reflecting intrinsic superiority of one alternative (e.g., a technological innovation) over the status quo. We represent a multi-agent network by a graph made up of n agents that are modeled as nodes, and an edge between two nodes corresponds to a relation between the respective agents such as friendship, common interests, or advice. We focus on the scenario where each agent must choose between two alternatives by exhibiting a bias toward one of the opinions. In the remainder, we use labels 0 and 1 for the two opinions and we assume 1 is the superior opinion. 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 α (called bias), the agent adopts 1, while with probability 1-α, the agent adopts to the majority opinion on the basis of those held by its neighbors in the underlying network. When α > 0 the process always converge to global adoption of the opinion 1. Since dynamics are aimed at modeling the spread of opinions, an important issue is to determine how fast the superior opinion takes over the network [Mossel and Tamuz, 2017]. In [Anagnostopoulos et al., 2020], the authors show that under the linear voter rule, where agents copy the opinion of a randomly selected neighbor, consensus is reached quickly within O( 1α n logn) rounds regardless of the underlying topology. In contrast, under the non-linear majority rule where agents update their opinion to the majority opinion in their neighborhood, it turns out that the convergence time is super-polynomial in expectation whenever the network is dense (i.e., when the minimum degree is ω(log n)). One might wonder if the converse occurs, namely, whether the biased majority dynamics always affords (expected) polynomial convergence to the absorbing state when the network is not dense. While this is indeed the case for cycles, trees, and disconnected cliques of size O(log n), understanding the behavior of the dynamics remains open for bounded degree topologies, inducing challenging open problems formulated in [Anagnostopoulos et al., 2020; Cruciani et al., 2021]. In this work, we aim at contributing to the general understanding of the evolution of biased opinion dynamics under the non-linear majority rule by studying their behavior theoretically and empirically. We make the following contributions: - We show a polynomial time convergence for new classes of topologies (namely, cubic graphs) and characterize them in terms of stable structures. - We answer negatively to the open problem in [Anagnostopoulos et al., 2020] by exhibiting classes of network topologies (namely, random ∆-regular bipartite graphs with ∆ ≥ 5) for which we prove that the expected time for consensus on the superior opinion is exponential for small values of α. - We provide insights into the dynamical properties of network structures that are implicitly responsible for the dichotomy between the slow and fast consensus behavior, in light of a generalized notion of domination in graphs. To the best of our knowledge, this is the first work on biased opinion dynamics that characterizes consensus in terms of multiple domination. - Finally, we support our theoretical findings by consistent experiments, relating the speed of consensus with properties of the network structures. The rest of this paper is organized as follows. In Section 2, we review the related works. In Section 3, we formally describe the biased opinion dynamics under the non-linear majority rule. In Section 4, we present an extension of standard domination in graphs and leverage it to analyze the expected time to reach consensus for random bipartite regular graphs in Sections 5 and 6. Then we validate our theoretical results through experiments and discuss the obtained results in Section 7. Finally, we draw our conclusions in Section 8. ## 2 RelatedWork The problem we consider lies at the intersection of several areas for which there is a vast amount of existing literature. In what follows, we discuss contributions that most closely relate to the topics of this work. Opinion diffusion and consensus. A substantial line of research has been devoted to the study of opinion dynamics, mostly motivated by phenomena that arise from social sciences, to physics and biology. Some recent contributions analyzed the spread of opinion formation in social influence [Out and N. Zehmakan, 2021; Zehmakan, 2021]. For a more detailed survey on opinion dynamics in multiagent systems, we refer the reader to [Coates et al., 2018; Becchetti et al., 2020]. In this paper, we study the non-linear majority rule which originates from the study of agreement phenomena in spin systems [Krapivsky and Redner, 2003]. It has lately received renewed attention, mostly around the investigation of the time and conditions that cause agents to reach consensus. Consensus and biased majority. Some forms of bias have been considered in the literature. In [Mukhopadhyay et al., 2020], each agent updates each of its opinions at points of different independent Poisson point processes, which introduces a bias towards the opinion with the lowest firing rate frequency. The works closest to ours are [Anagnostopoulos et al., 2020; Cruciani et al., 2021]. In [Anagnostopoulos et al., 2020], the speed of convergence under the majority rule is shown to be affected by the underlying topology, namely, is superpolynomial for dense networks. The synchronous setting has been considered in [Cruciani et al., 2021] with qualitatively consistent findings, albeit under a different model where agents sample k neighbors uniformly at random with replacement and update their state to the most frequent state among those in the sample. Yet, these results only apply to very dense networks with minimum degree ω(n). We show that the expected convergence time can be exponential even in sparse networks, suggesting a more complicated dependence of the convergence time on the degree distribution. Our overall approach is different since it characterizes the majority opinion formation in terms of multiple domination in graphs, providing an interplay between bias, consensus and network structure. Majority and graph domination. Network structure plays a crucial rule in opinion diffusion under several models [Donnelly and Welsh, 1983; Hassin and Peleg, 1999; Cooper et al., 2013; Morris, 2000]. [Auletta et al., 2015] showed that initial majority can be subverted for all but some topologies, including cliques and quasi-cliques. Moreover, while there exist always an initial opinion distribution, such that the final majority will reflect the initial one, regardless of the topology, computing an initial opinion configuration that will subvert an initial majority is topology-dependent and NP-hard in general [Auletta et al., 2018]. Dominating sets can be useful to reach all the nodes efficiently in the network. The books [Haynes et al., 2013; Haynes, 2017] supply a comprehensive introduction to theoretical and applied facets of domination in graphs. ## 3 Majority Dynamics In this section, we define the terminology used throughout the paper. Then, we describe the Majority Dynamics. Notation and Preliminaries. We model the multi-agent network by an undirected graph G = (V,E) with |V | = n nodes, each node v ∈ V representing an agent. The system evolves in discrete time steps and, at any given time t ∈ N, each node v holds an opinion x(t) v ∈ {0, 1} (see Definition 1). We denote by Xt = (x(t) 1 , . . . , x(t) n ) the corresponding state of the system at time t. For each v ∈ V , we denote the open neighborhood of v with Γ(v) := {u ∈ V : {u, v} ∈ E} and the degree of v with d(v) := |Γ(v)|. For any X ⊆ V , let G[X] denote the subgraph of G induced by X. Finally, for a family of events {En}n∈N we say that En occurs with high probability (w.h.p, for short) if a constant k > 0 exists such that P(En) = 1 - O(n-k ), for every sufficiently large n. Definition 1. For every t > 0, a node v is said to be active if x(t) v is 1. Otherwise, it is idle. Moreover, we say that a subset S of V is active if every node in S is active. M-Dynamics. We study the random process {Xt}t∈N defined on G as follows: starting from the initial state X0 = (0, . . . , 0), in each round t, every node v ∈ At updates its value according to the non-linear rule: where At ⊆ V is the set of nodes that update their opinion, α ∈ (0, 1] (modeling the bias) is the probability to transition to the superior opinion, and MG(v, Xt-1) is the value held in configuration Xt-1 by the majority of the neighbors of node v in G: and ties are broken uniformly at random, that is, if ∑w∈Γ(v) x(t-1) w = Γ(v) 2 then MG(v,Xt-1) = 0 or 1 with probability 1/2. Stabilization. The M-Dynamics is a discrete-time Markov chain with a very large state space of size 2n and has 1 = (1, . . . , 1)⊤ as the only absorbing state. This implies that, since the graphs are finite, such an absorbing state will be reached in finite time with probability 1. We use τα(G) to denote the stabilization time, which is the number of rounds for the process to reach the absorbing state 1: Models. We distinguish between two main models of the Mdynamics, which differ according to the choice of At: - Asynchronous (Async). In each round t, some agent vt, chosen randomly, updates its opinion, At = {vt}. - Synchronous (Sync). In each round t, all agents update their opinion concurrently, that is, At = V . Our results and proof techniques are similar between the Async and Sync models. For the sake of space, we present our results for Async. ## 4 Decreasing Structures and k-Domination In this section, we relate the notion of domination to the MDynamics and introduce the concept of decreasing sets. ## 4.1 Multiple Domination We present a generalized extension of domination in graphs. Definition 2 (k-domination). Let S ⊆ V and k ∈ {1, . . . , n}. - We say that a vertex v is k-dominated by S (equivalently, S k-dominates v) if |Γ(v)∩S| ≥ k. We denote by Dk(S) the set of all nodes k-dominated by S. - Let U ⊆ V . U is said to be k-dominated by S if S kdominates all vertices u ∈ U, that is, if U ⊆ Dk(S). When k = 1, a 1-dominating set S of smallest size such that D1(S) = n is called a minimum dominating set and its size is known as the domination number, denoted by γ(n). The problem of determining γ(n) is one of the core NPcomplete optimization problems in graph theory and remains NP-complete even for planar graphs of maximum degree 3 [Garey and Johnson, 1979]. In the following, we focus on the case of majority domination. Definition 3 (M-domination). Let S ⊆ V . We say that a vertex v is M-dominated by S (equivalently, S M-dominates v) if v is k-dominated by S with k = ⌊ N(v) 2 ⌋ + 1. We denote by DM(S) the set of all nodes M-dominated by S. The decision problem of finding a set S of size s such that |DM(S)| = l for arbitrary non-negative integers s, l is NPhard. The proof is omitted for the sake of space. Note that for ∆-regular graphs where ∆ = 2k - 1, the notions of M-domination and k-domination become identical. ## 4.2 Stable and Decreasing Structures In order to analyze the stabilization time of the M-dynamics, we first introduce the notions of stability and decrease. Definition 4. Let S ⊆ V . S is stable if S ⊆ DM(S). Once stable structures become active under the M-dynamics at some round t, they remain active forever (i.e., for all rounds t′ ≥ t). Hence, we introduce the following definition. Definition 6. A subset S of V is stabilized if S is active and stable. Its induced subgraph G[S] is also said to be stabilized. Note that, informally, a simple condition for polynomial time stabilization is the existence of a covering of G by small stable structures as we illustrate in Section 5 for cubic graphs. Large bias. For large values of α, [Anagnostopoulos et al., 2020] shows that the stabilization time is polynomial for dense networks, but leaves as open the case for sparse networks. In the following theorem, whose proof is omitted for the sake of space, we show that the stabilization time is also fast for ∆-regular graphs whenever the bias α is greater than some threshold value that depends on the degree. Theorem1. Let Gbe a∆-random regular graph on n nodes. Whenever α ≥ k-1 ∆ where k = ⌈ ∆+1 2 ⌉, then the expected stabilization time for the Async M-Dynamics is polynomial. ## 5 Fast Stabilization for Cubic Graphs In this section, we show that cubic graphs stabilize in expected polynomial time. Theorem 2. Let G be a cubic graph of size n. The expected absorption time for the Async M-Dynamics in G is The result is derived by observing that cubic graphs have a small girth (see Lemma 1) and by making use of properties that cycles are stable structures and that a path linking two stable substructures is itself stable (see Lemma 2). Indeed, cubic graphs are covered by logarithmic stable structures which ensures expected polynomial time stabilization. Note that Theorem 2 implies that E [τα(G)] = O(nf(α) ) where f is an increasing function of the bias α. There exist families of graphs with finite stable structures such as planar cubic graphs for which the expected stabilization time is at most g(α)nc (for some function g sensitive to the bias) where c does not depend on α. Lemma 1. [Bollob´as, 2004] Let G be a ∆-regular graph on n nodes with ∆ ≥ 3. Let g(G) denote the girth of G. Then Lemma 2. Let G be a cubic graph on n nodes. Suppose that G has a subgraph S which is either a cycle of size l or a path of length l between two stabilized structures. Let ¯ τS denote the number of rounds for S to become active. Then, we have We note that Lemma 2 implies that E [¯ τS] is still O(n1+r log n) when α = Θ( 1 nr ) for any r > 0, hence polynomial as long as r is constant. ## 6 Slow Stabilization for RandomRegular Bipartite Graphs With Odd Degree In this section, we show that there exist graphs (namely, random ∆-regular bipartite graphs with odd degree 1 ∆ ≥ 5) for which every linear substructure (of size smaller than Cn, with C a non-negative constant) is Decreasing for small values of α. This leads to an exponential expected stabilization time. ## 6.1 Model Discussion We consider random ∆-regular balanced bipartite graphs G of the form G = (A∪B, E) with |A| = |B| and E ⊂ (A, B). We first study the case of an odd degree ∆ = 2k - 1(k ≥ 3) for which there cannot be ties under the majority update rule. Let |A| = n and note that |E| = ∆n. The random regular graph model 2 that we use is analogous to the configuration model proposed by [Bollob´as, 1980]. We shall prove that there exists an α0 > 0 such that for every ∆ ≥ 5 the expected stabilization time is exponential whenever α ≤ α0. This phenomena is mainly due to the random structure which fosters the existence of small Decreasing structures. ## 6.2 Existence of Decreasing Sets In the following, we prove (see Proposition 1) that there exist ∆-regular graphs for which all sufficiently small linear sets S M-dominate a strictly smaller set (with an actual linear gap). To obtain this result, we employ Lemma 3 corresponding to the case for which sets S are contained in only one side of the bipartition of G (without loss of generality, we assume that S ⊆ A). To make the proof more comprehensive, we introduce first some auxiliary functions. Definition 7 (Decrease functions). For (σ, τ) ∈ [0, 1]2 , we let N(σ, τ ) be the expected number of pairs of subsets (S, T ) with S ⊆ A, T ⊆ B of respective sizes σn, τn such that S k-dominates T . We define ̂ F : (0, 1]2 →R as Moreover, for every β in (0, 1), we define ̂Gβ : (0, 1) → R as and we refer to β by the decrease intensity. 1 Similar results hold when the degree is even and G is non bipartite. See brief discussion in Section 7. 2 The bipartite version was introduced by [Margulis, 1973], [Pippenger, 1977], and [Valiant, 1975] to prove that expanders exist. Observe that if ̂Gβ(σ) < 0 then N(σ, βσ) < 1, which implies that all subsets S of size σn are Decreasing (with a gap β). Therefore, we refer to ̂ F and ̂G as decrease functions as they define regions of existence of decrease, namely when ̂Gβ is negative. Lemma 3. Let G = (A ∪ B,E) be a random ∆-regular bipartite graph with 2n nodes. Then, there exist 1 k-1 < β < 1 and γ∆(β) > 0 such that for any 0 < λ < γ∆(β) we have Proof. Let N(s, t) be the expected number of pairs of subsets S ⊂ A, T ⊆ B of respective sizes s, t such that S kdominates T. Since we are studying sets of linear sizes we let s = σn and t = τn with σ, τ ∈ (0, 1]. We first count the configurations that fulfill the k-domination constraints in order to get an upperbound on N(s, t): Using Stirling's approximation, we get ( n pn) ≤ 2nH(p) for every 1n ≤ p ≤ 12 . Hence, by Inequality (1), we obtain the following property which provides upperbounds on the decrease functions (see Definition 7). Property 1. Let σ, τ be positive reals in [ 1n , 12 ]. We have where and H is the binary entropy function 3 . Moreover, let We want to show that there exist σ and τ such that ̂ F(σ, τ) < 0. This implies that N(σn, τn) < 1 and therefore, that there exist random regular graphs with no subsets S of size σn that k-dominate a subset T of size τn. Note that if there exists τ ′ such that τ ′ ≤ τ and N(σn, τ ′n) < 1 then N(σn, τn) < 1. Therefore, it is sufficient to let τ = βσ for a positive real β ∈ (0, 1) and prove that ̂Gβ(σ) < 0, or alternatively, by Definition 7 and Property 1 that Gβ(σ) < 0. We have Observe that for every 0 ≤ x ≤ 12 , we have Therefore where Cβ(k, ∆) = H ( kβ ∆ ) ∆ + β log2 (∆k ) - β log2(β) + kβ log2( kβ ∆ ) + (1+β) 2 is a constant. Since log2(σ) diverges to -∞ when σ → 0, then Gβ(σ)/σ < 0 implies that kβ-(1+β) > 0, that is β > 1 k-1 . Furthermore, by setting then for every 0 < σ < σ∆(β), we have Gβ(σ)/σ < 0. Hence, there exists γ∆(β) ≥ σ∆(β) such that all linear sets |S| of size σn with 0 < σ < γ∆(β) satisfy |DM(S)| ≤ β|S| with β ∈ ( 1 k-1 , 1) and the thesis follows. Existence of decrease. Let us consider regions defined by Rβ∆ = (λ, γ∆(β)] where λ > 0 and By Lemma 3, all linear sets S of size σn with σ ∈ Rβ∆ are decreasing (with a gap of β) and will define a regime where the process is slow, leading to consensus on the superior opinion taking place after an exponential number of rounds. By plotting the variation of Gβ(σ) with σ (see Property 1), in Figure 1, we illustrate the regions R0.99 ∆ for different values of ∆. For ∆ = 5, a red vertical line indicates the value of γ5(β) ∼ 0.043. Furthermore, we note that the highest is the degree ∆, the largest is the number |Rβ∆| of linear sets which are all Decreasing in the network. We now state the general case 4 for which sets S can be in A ∪ B and not only in A. Proposition 1. Let G = (A∪B,E) be a random∆-regular bipartite graph with n nodes. Then, there exist 1 k-1 < β+ < 1 and γ∆(β+) > 0 such that for any 0 < λ < γ∆(β+) we have Proof. Let SA = S∩A, SB = S∩B, then S = SA∪SB and |S| = |SA| + |SB|. Similarly, let |DM(S)| = |DM(SA)| ∪ |DM(SB)| and |DM(S)| = |DM(SA)| + |DM(SB)|. Assume that |S| = σn with 0 < σ ≤ 1 and let r be a positive integer. - If both |SA|, |SB| ≥ σn/r, we can apply Lemma 3 twice, giving |DM(SA)| ≤ β|SA| and |DM(SB)| ≤ β|SB|. We get the result |DM(S)| ≤ β|S|. - If one side is small, assume without loss of generality that |SA| ≤ σn/r. Lemma 3 applies to SB and we have |DM(SB)| ≤ β|SB|. For SA, as the graph is ∆-regular, a set of size s cannot k-dominate a set of size larger than ∆s/k. Thus, |DM(SA)| ≤ ∆k |SA| ≤ ∆k σn r and we 4 In the case of ∆-regular graphs (∆ = 2k - 1), a k-domination corresponds to an M-domination. However, Prop. 1 can be made general without any relationship presumed with the degree ∆. get DM(S) ≤ β|SB| + ∆k σn r ≤ (β + ∆ kr )|S|. We set β+ = β + ∆ kr . By picking r such that r > ∆ k(1-β) , we have β+ < 1 and the thesis follows. ## 6.3 Exponential Stabilization Theorem 3. Let G be a random regular graph with odd degree ∆ of size n. There exists α∆ > 0 such that for every α < α∆, E [τα(G)]] is exponential for the Async MDynamics. Proof. Let St be a random variable indicating the set of active nodes at round t and let st = |St|. We first show that st has a negative drift inside a linear time interval. We then use this fact to prove that the expected stabilization time is exponential. Negative drift. Observe that the number of active nodes at time t increases by one with probability α if a node outside St is selected and with probability 1-α if a node in DM(St)\St is selected. Therefore, we get By Proposition 1, there exist 1 k-1 < β+ < 1 and γ∆(β+) > 0 such that for any 0 < λ < γ∆(β+), each subset S of V with λn ≤ |S| ≤ γ∆(β+)n, satisfies |DM(S)| ≤ β+|S|. We set λ = γ∆(β+) r n where r is a positive integer. It follows that if st ∈ [ γ∆(β+) r n, γ∆(β+)n], then since β+ - 1 < 0 we get from Inequality (3) that Therefore, by picking any α < (1 - β+) γ∆(β+) r , we get that the sequence {st}t≥0 has a fixed negative drift δ. Exponential stabilization. We study the process when it is in the critical region for which the drift is negative. The following property is derived by noting that the time to exit a linear interval by a variant of a biased random walk on {st}t≥0 with a fixed negative bias is exponential in expectation. Sketch of proof. Let T > 0. We introduce two random variables T1 = min{t < T, st = ⌈γ∆(β+)n⌉} and T0 = max{t ≤ T1, st = ⌈ γ∆(β+) 2 n⌉}. Since |St| can vary by the values in {1,-1}, then [T0, T1] has a size linear in n. We complete the argument by using concentration inequalities to show that due to the negative drift, traversing the interval [ γ∆(β+) 2 n, γ∆(β+)n] takes ∼ eΘ(n) time. □ Figure 1: Existence of regions Rβ∆ for β = 0.99 in which all linear sets S of size σn satisfy |DM(S)| ≤ β|S| (see Property 1). ![Image](https://ijcai.org/proceedings/2022/fulltext/54/image_000000_52a0664058c0b7355b830a176b681436376123e18bf07ac999bfa826c5b2c8dd.png) Figure 2: Effect of the bias α on the stabilization time τα(G) in a random∆-regular network made up of 1000 agents. ![Image](https://ijcai.org/proceedings/2022/fulltext/54/image_000001_8f28a3b9df453491cc157dfdebd6a19e9e5a7cfdff47ef0e10528b8c018674c2.png) ![Image](https://ijcai.org/proceedings/2022/fulltext/54/image_000002_27a080619d92eda40495807d51bff2b39257353e13c6db0aa6cf018b6f2da2a7.png) Figure 3: Slow-fast dichotomy behavior of the stabilization time τα(G) induced by α in random 5-regular networks of size n. Note that Property 2 provides various bounds for the bias depending on the decrease intensity β+. We get the best bound for α by setting α∆ = max 1 k-1 <β+<1(1 - β+)γ∆(β+). ## 7 Experiments and Outlook In this section, we present and discuss experiments on the stabilization time and the existence of Decreasing structures. Bias and stabilization. We first study the effect of the bias α on the stabilization time τα(G). In Figure 2, we plot τα(G) in a random ∆-regular network of size n = 1000 as a function of 1α . Each experiment over G is averaged over 10 iterations and terminated if τα(G) bypasses 1010 iterations (which requires a prohibitive computation time of 71 hours). When the bias is large (e.g. α ≥ 0.15), stabilization occurs very quickly and bears no significant dependence of the degree. The picture changes when the bias gets smaller where we observe a fast stabilization for ∆ = 3 (even for arbitrary small values of α) and a very clear explosion for ∆ ≥ 4. Moreover, the higher the degree, the sooner the explosion occurs. We also see that on a network with only 1000 agents, the convergence for α = 0.08 and ∆ = 4 takes at least 1010 iterations. In Figure 3, we visualize the impact of the size n on stabilization in a random 5-regular network. We note the presence of two regimes (values of α) RF and RS depicted respectively in gray and red. Each experiment over G is averaged over 500 (resp. 5) iterations for every α in RF (resp. RS). The first regime RF corresponds to a large bias (α ≥ 0.13) for which we observe that the network stabilizes in polynomial time (log τ/ logn is almost constant). We also conducted experiments on large cubic networks with α small, confirming what we proved in Theorem 2, that is E [τα(G)] ≤ nf (α) . In the second regime RS, stabilization takes an exponential (note that τ is observed on a logarithmic scale) number of rounds (log τ/ log n increases with n) and this occurs as soon as we start from α ∼ 0.09. Outlook. This paper leaves a number of open questions. A first one concerns closing the gap g∆ = αe - α∆ between the empirical and the theoretical values for the bias below which (expected) exponential stabilization occurs due to the existence of Decreasing structures. When ∆ = 5, the best bound α∆ is attained with a decrease intensity of β ∼ 0.9 for which we get g5 ∼ 0.08903. Note that for an arbitrary large degree ∆, we get α∆ ∼ 0.3. Furthermore, when ∆ ≥ 5, the evolution of the stabilization time during the intermediate regime (depicted in blue in Figure 3) is not completely clear and might suggest an intermediate stabilization growth (i.e., superpolynomial and subexponential) or a sharp transition between RF and RS. We also point a rather surprising result: in the course of the proof of Proposition 1 we showed that it is impossible for any (small enough) linear set S to k-dominate more that |S| k-1 nodes (note that this bound is tight), which implies that for some a0 > 0 depending only on α and ∆, we get min|S|≤a0nDk(S) ∼ |S| k-1 . Thus, maximizing almost exactly Dk(S) is trivial for small linear sets, but for larger sets, the question remains open. Unlike in the Erd˝os-R´enyi model, domination problems have not yet been solved in random regular graphs even if some works [Duckworth and Wormald, 2006; Hoppen and Mansan, 2021]) have been done. We remark that the lack of accurate results in this field somewhat preludes the gaps in our bounds since the dynamics relate to some already complex domination based questions. Finally, we believe that the techniques we have exposed can be used to prove many other results. For instance, we proved similar results in the general case of random regular graphs and planar cubic graphs. While the arguments are similar, the analysis is slightly more complicated to expose due to ties in the even degree case and the fact that S ∩Dk(S) ̸= ∅ in the non bipartite case. ## 8 Conclusion In this paper, we studied a biased opinion dynamics where agents are influenced by the majority of their neighbors. We have shown that consensus on the preferred opinion exhibits a dichotomy by proving that convergence time is always polynomial for cubic graphs, whereas it becomes exponential (for a small enough bias) in random ∆-regular graphs (∆ ≥ 4), answering an open conjecture in the literature. Moreover, we analyzed this dichotomy by exploiting structural properties of graphs in light of majority domination. An interesting avenue for further research is to to extend our results to the case of multiple opinions. ## Acknowledgements This work has been supported by the French government through the UCA JEDI (ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004) Investments in the Future projects. ## References 1. [Anagnostopoulos et al., 2020] Aris Anagnostopoulos, Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Biased opinion dynamics: When the devil is in the details. In 29th International Joint Conference on Artifi- cial Intelligence (IJCAI 2020), pages 53-59. International Joint Conferences on Artificial Intelligence Organization, 2020. 2. [Auletta et al., 2015] Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Per- siano. Minority becomes majority in social networks. In International conference on web and internet economics, pages 74-88. Springer, 2015. 3. [Auletta et al., 2018] Vincenzo Auletta, Diodato Ferraioli, and Gianluigi Greco. Reasoning about consensus when opinions diffuse through majority dynamics. In IJCAI, pages 49-55, 2018. 4. [Becchetti et al., 2020] Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. ACM SIGACT News, 51(1):58-104, 2020. 5. [Bollobás, 1980] Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311- 316, 1980. 6. [Bollobás, 2004] Béla Bollobás. Extremal graph theory. Courier Corporation, 2004. 7. [Coates et al., 2018] Adam Coates, Liangxiu Han, and An- thony Kleerekoper. A unified framework for opinion dy- namics. In Proceedings of the 17th International Confer- ence on Autonomous Agents and Multiagent Systems. In- ternational Foundation for Autonomous Agents and Mul- tiagent Systems, 2018. 8. [Cooper et al., 2013] Colin Cooper, Robert Elsasser, Hiro- taka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM Journal on Dis- crete Mathematics, 27(4):1748-1758, 2013. 9. [Cruciani et al., 2021] Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Phase transitions of the k-majority dynamics in a biased communication model. In International Conference on Distributed Com- puting and Networking 2021, pages 146-155, 2021. 10. [Donnelly and Welsh, 1983] Peter Donnelly and Dominic Welsh. Finite particle systems and infection models. In Mathematical Proceedings of the Cambridge Philosophi- cal Society, volume 94, pages 167-182. Cambridge Uni- versity Press, 1983. 11. [Duckworth and Wormald, 2006] William Duckworth and Nicholas C Wormald. On the independent domination number of random regular graphs. Combinatorics, Proba- bility and Computing, 15(4):513-522, 2006. 12. [Garey and Johnson, 1979] Michael R Garey and David S Johnson. Computers and intractability, volume 174. free- man San Francisco, 1979. 13. [Hassin and Peleg, 1999] Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to pro- portionate agreement. In International Colloquium on Au- tomata, Languages, and Programming, pages 402-411. Springer, 1999. 14. [Haynes et al., 2013] Teresa W Haynes, Stephen Hedet- niemi, and Peter Slater. Fundamentals of domination in graphs. CRC press, 2013. 15. [Haynes, 2017] TeresaW Haynes. Domination in graphs: volume 2: advanced topics. Routledge, 2017. 16. [Hoppen and Mansan, 2021] Carlos Hoppen and Giovane Mansan. Asymptotic bounds on total domination in regu- lar graphs. Discrete Mathematics, 344(4):112287, 2021. 17. [Krapivsky and Redner, 2003] Paul L Krapivsky and Sidney Redner. Dynamics of majority rule in two-state interact- ing spin systems. Physical Review Letters, 90(23):238701, 2003. 18. [Margulis, 1973] Grigorii Aleksandrovich Margulis. Ex- plicit constructions of concentrators. Problemy Peredachi Informatsii, 9(4):71-80, 1973. 19. [Morris, 2000] Stephen Morris. Contagion. The Review of Economic Studies, 67(1):57-78, 2000. 20. [Mossel and Tamuz, 2017] Elchanan Mossel and Omer Tamuz. Opinion exchange dynamics. Probability Surveys, 14:155-204, 2017. 21. [Mukhopadhyay et al., 2020] Arpan Mukhopadhyay, Ravi R Mazumdar, and Rahul Roy. Voter and majority dynam- ics with biased and stubborn agents. Journal of Statistical Physics, 181(4):1239-1265, 2020. 22. [Out and N. Zehmakan, 2021] Charlotte Out and Ahad N. Zehmakan. Majority vote in social networks: Make random friends or be stubborn to overpower elites. In 30th International Joint Conference on Artificial Intelli- gence (IJCAI 2021), pages 349-355. International Joint Conferences on Artificial Intelligence Organization, 2021. 23. [Pippenger, 1977] Nicholas Pippenger. Superconcentrators. SIAM Journal on Computing, 6(2):298-304, 1977. 24. [Valiant, 1975] Leslie G Valiant. On non-linear lower bounds in computational complexity. In Proceedings of the seventh annual ACM symposium on Theory of comput- ing, pages 45-53, 1975. 25. [Zehmakan, 2021] Ahad N Zehmakan. Majority opinion dif- fusion in social networks: An adversarial approach. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, pages 5611-5619, 2021.