The Voter Model with Opinion Graph

The VoteR Model with Opinion GRaph Petra BeRenbRinK1 , Thorsten GÖtte1 , Martin HoefeR2 , and Tim Koglin2 1

University of Hamburg, Germany petra.berenbrink@uni-hamburg.de thorsten.goette@uni-hamburg.de 2

arXiv:2610.16684v1 [cs.GT] 12 Oct 2026

RWTH Aachen University, Germany mhoefer@cs.rwth-aachen.de koglin@algo.rwth-aachen.de

October 14, 2026 Abstract We study the voter model with opinion graph, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a finite set A of n agents. Each agent u ∈ A has an opinion xu ∈ O, where we model opinions as vertices in an undirected opinion graph G = (O, E) with |O| = q. In each step, an agent u interacts with another agent v ∈ A. In contrast to classical voting, u adopts the opinion xv if and only if xv and xu are neighbors in G. The process is stable once all remaining opinions are an independent set in G. We analyze two variants of the process: the ordinary EdgeVOG process, which samples a pair of interacting agents uniformly at random from all possible pairs, and the productive EdgeVOG process, which samples only pairs with neighboring opinions in G. We show the following: 1. For every opinion graph and every initial configuration, ordinary EdgeVOG stabilizes within O(n2 log n) steps in expectation and with high probability. The expectation bound is asymptotically tight. For the productive EdgeVOG process, the expected stabilization time is exactly the initial number of compatible agent pairs, while O(n2 log n) steps suffice with high probability. 2. We P show that an opinion i with P initial support si survives with probability at least pi := si /(si + s ). Further, let µ = j∈N (i) j i∈O pi , then we show the probability that less than (1−δ)µ opinions 2 survive is at most exp(−δ µ/(2(∆2 + 1))) for every 0 ≤ δ ≤ 1. 3. If G has maximum degree ∆ and every opinion initially has support at most ŝ, then no opinion ever acquires more than Õ(min{n, ∆6 ŝ}) agents with high probability. This yields near-linear stabilization bounds for productive EdgeVOG on bounded-degree opinion graphs with well-spread initial configurations.

Acknowledgements We used ChatGPT 5.6 Sol and 6 Astra to assist with improving clarity, typesetting in LATEX, finding related work, as well as checking and simplifying the proofs. The authors verified the correctness and originality of all content, including references.

Contents 1

Introduction 1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Notation & Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 3 4

2 Our Results and Techniques 2.1 Bounds on the Stabilization Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Distribution of Surviving Opinions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Maximal Support on Bounded-Degree Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 9 11 13

3 Proofs 14 3.1 Proof of Proposition 1 (Properties of our Potential Function) . . . . . . . . . . . . . . . . . . . 14 3.2 Proof of Theorem 2 (Stabilization Time of the Ordinary Process) . . . . . . . . . . . . . . . . . 15 3.3 Proof of Theorem 3 (Worst-Case Stabilization Time of the Productive Process) . . . . . . . . . 16 3.4 Proof of Theorem 4 (Parameterized Stabilization Time of the Productive Process) . . . . . . . . 16 3.5 Proof of Theorem 5 (Survival of a Fixed Opinion) . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.6 Proof of Theorem 6 (Number of Surviving Opinions) . . . . . . . . . . . . . . . . . . . . . . . . 22 3.7 Proof of Theorem 7 (Maximal Support on Cycle Graphs) . . . . . . . . . . . . . . . . . . . . . . 26 3.8 Proof of Theorem 8 (Maximal Support on Bounded Degree Graphs) . . . . . . . . . . . . . . . 26 4 Tools from Probability Theory & Textbook Results 34 4.1 Bounds for Martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 Tail-Bounds for Weakly-dependent Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3 Lower Bound for the convergene of Gambler’s Ruin. . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Number of Subtrees of Size k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5 A New Analysis for Asynchronous Pull Voting on Graphs

40

1

Introduction

Opinion dynamics are a model to study how the views held by a population evolve through social interaction. They have been investigated extensively in physics, sociology, and artificial intelligence, both analytically and experimentally [22, 37, 42, 48]. Beyond their role in modeling social behavior, opinion dynamics also provide a rich setting for the design and analysis of distributed information spreading algorithms, a central topic in theoretical computer science and applied mathematics. Models originating in physics and sociology typically represent opinions as continuous quantities and often assume that agents update their views by averaging the opinions of their neighbors. Prominent examples include the French–DeGroot [17, 23], Friedkin–Johnsen [24], Hegselmann–Krause [29], and Deffuant–Weisbuch [16] models. By contrast, models studied in distributed computing and applied mathematics usually assume discrete opinions and randomized pairwise interactions. Examples include the standard voter model [5, 11, 27, 40], k-majority dynamics [3, 4, 25], and several generalized or hybrid variants [9, 10, 12, 13, 14]. A central feature of many continuous models, but one that is largely absent from discrete opinion dynamics, is the notion of so-called bounded confidence. Under this principle, agents are influenced only by opinions that are sufficiently close to their own and disregard distant opinions. This assumption reflects many real social interactions, in which not all viewpoints are regarded as equally persuasive. Voters, for example, may discount arguments associated with opposing ideological camps, while citizens may reconsider a policy position only when it is presented within an acceptable range of their prior beliefs [21]. In this paper, we study a discrete pull-voter process with bounded confidence. There are n agents and a set O of q possible opinions. The opinions form the vertex set of an undirected opinion graph G = (O, E), whose edges encode which opinions are compatible. At each step, we pick a pair of agents (u, v) uniformly at random. If the current opinions of u and v are adjacent in G, then u adopts v’s opinion; otherwise, the configuration remains unchanged. We refer to this process as the voter model with opinion graph. We consider two variants of the process. In the ordinary EdgeVOG process, the ordered pair is sampled uniformly from all pairs of distinct agents. This process may contain many idle steps, since agents with equal or incompatible opinions do not cause an update. We therefore also consider the productive EdgeVOG process, in which the interaction pair is sampled uniformly from the pairs whose current opinions are adjacent in G. We call these the productive steps. Our goal is to understand how the structure of the opinion graph affects the behavior of the process. In particular, we study how long the process takes to stabilize, how many opinions survive, and how large the support of an individual opinion can become. When the opinion graph is complete, our model reduces to the classical voter model. In this case, the expected stabilization time is O(n2 ), exactly one opinion survives and therefore eventually has support n, and a fixed opinion i survives with probability si /n, where si is its initial support. These properties can change substantially when the opinion graph is sparse and the agents are well spread over the opinions1 . Each opinion can then exchange agents with only a few other opinions. Under a uniform initial distribution, there are consequently fewer compatible pairs of agents, and an opinion becomes stable as soon as its few neighboring opinions disappear. One would therefore expect sparse opinion graphs to require fewer productive steps, preserve more opinions, and prevent individual opinions from acquiring very large support. Our results make these intuitions precise and quantify all three effects in terms of the opinion graph and the initial distribution. 1. Stabilization time. For the productive EdgeVOG process, we show that the expected stabilization time is exactly the initial number of pairs of agents whose opinions are adjacent. In particular, for a fixed distribution of agents to opinions, deleting edges from the opinion graph can only decrease the expected number of productive steps. Surprisingly, however, there are instances with only n−1 such pairs that take Ω(n2 ) steps with probability Ω( n1 ). Thus, the stabilization time does not need to be concentrated around its expectation. To obtain high-probability bounds despite this heavy tail, we show that the stabilization time is instead controlled by the largest support attained by any opinion. This connection allows us to derive refined stabilization bounds from our bounds on the maximum support and the graph’s degree. For the ordinary process, which includes idle steps, we show that stabilization takes O(n2 log n) steps 1 Note that one can always place Θ(n) agents on two neighboring opinions to enforce a large stabilization time and a large maximal support. Thus, the impact of the opinion graph G is arguably most significant if the agents are uniformly distributed over the opinions.

1

in expectation and with high probability on every opinion graph. The expectation bound is asymptotically tight, even for opinion graphs of maximum degree one. Thus, while sparsity reduces the number of productive steps, it need not reduce the number of ordinary steps, since the waiting time between productive interactions may dominate. The stabilization analysis is driven by the right choice of potential: the number of pairs of agents holding adjacent opinions. We show that this quantity decreases by one in expectation whenever agents with neighboring opinions interact. Using this insight, the stabilization analysis of both processes is relatively direct. 2. Surviving opinions. Next, we show that an opinion i with initial support si survives with probability at ∑ least si/si + j∈Ni sj . This tightens and generalizes the bound of si /n from the classical voter model. More importantly, however, we prove that many opinions survive simultaneously when the graph is sparse. Let P ∑ µ := i∈O si/si + j∈Ni sj denote the sum of the individual survival guarantees. Then the probability that fewer than any fixed constant fraction of µ opinions survive is exponentially small in µ/∆2 . For graph classes such as trees and grids, this bound can be improved even further. The survival probability of a fixed opinion follows from observing that the ratio between an opinion’s support and the total support of its closed neighborhood increases in expectation and then applying standard martingale results. Proving that many opinions survive simultaneously is significantly more difficult because the survival events are not independent. The key observation is that the extinction events of opinions at distance at least three are negatively correlated (in a specific way). This allows us to prove a variant of the Chernoff bound tailored to this dependence structure. 3. Maximum support. Finally, we show that sparse opinion graphs prevent individual opinions from becoming dominant. If the opinion graph has maximum degree ∆ and every opinion initially has support at e 6 ŝ) agents. In particular, most ŝ, then, with high probability, no opinion ever acquires more than O(∆ e for constant ∆ and a uniform initial distribution, every opinion has support at most O(n/q) throughout the process. This contrasts with the classical voter model, in which one opinion eventually acquires all n agents. Together with our connection between maximum support and stabilization time, this also yields e 2 /q) with high probability. This is the most technically involved part of the a stabilization time of O(n paper. For the proof, we view the agents as tokens moving along the opinion graph. If an opinion acquires large support, then many tokens must have reached it along paths through other opinions. Tracing these paths backwards produces a witness structure in which many opinions must remain undecided while participating in many productive interactions. We show that large such structures are unlikely. Before giving the general argument, we illustrate its main ideas on cycles with uniform initial support, where we bound the maximum support by O(log n). The underlying interaction rule has appeared in earlier work. Lanchier and Scarlatos [35] focus on an infinite line of agents, where each agent interacts only with its two neighbors. They determine when every agent continues to change opinion indefinitely, and when instead every agent eventually stops changing. Hardin and Lanchier [26] consider arbitrary finite communication graphs, but their main results concern the probability of complete consensus, i.e., that exactly one opinion survives. Öztürk [43] restricts the opinion graph to powers of a path; for this graph class, he derives the exact expected number of steps. In contrast, our goal is to understand systematically how the structure of an arbitrary opinion graph affects the stabilization time, the number of surviving opinions, and the support attained by individual opinions. Structure of This Paper. In the remainder of this section we first present the related work. Then, in Section 1.2, we formally introduce the required notation and preliminaries. We then formally state the process, main results, and a sketch of our proof techniques in Section 2. In Section 3, we present the full proofs of our theorems. Finally, we present tools and folklore we use in the analysis (Section 4) and show how our techniques can be adapted to other variants of the problem (Section 5).

2

1.1 Related Work The Standard Voter Model: Our process can be regarded as a generalization of the well-known discrete voter (pull) process. The voter process was first rigorously studied in [19] in a continuous time model. In [27, 41], the voter process is studied in a discrete-time and parallel setting, where in each round every agent adopts the opinion of a randomly chosen neighbor. Initially, there are two opinions A and B, and it is shown that all agents eventually agree on one of the two opinions. In [27] the convergence time of the voter process with two initial opinions is expressed in terms of the meeting time of two in- Figure 1: Opinion graph for the twodependent discrete-time random walks, yielding a worst-case dimensional DW process with τ = 2, i.e., a grid bound of O(n3 log n). In addition, there are works that tie the graph with connections to all nodes in distance convergence time directly to graph parameters. [11] considers 2 (light blue). an arbitrary number of opinions and derive an upper bound of 1 · nν ), where the parameter ν measures the regularity of the degree sequence, ranging from 1 for Õ( (1−λ 2) regular graphs to n for the star graph. [5] proves an upper bound of O(m/(dmin · Φ)), where m is the number of edges, dmin is the minimal degree, and Φ the conductance of the graph. The Deffuant-Weisbuch Model: Moreover, our process is related to continuous opinion dynamics with bounded confidence. In particular, our model is partly inspired by the Deffuant-Weisbuch (DW) process [16, 49] with bounded confidence. In this model, we consider a set A of n agents, where each agent u ∈ A holds an opinion xu (t) ∈ [0, 1] at time t ≥ 0. In each step, an unordered pair of agents {u, v} is selected uniformly at random. If |xu (t)−xv (t)| < ε for a fixed confidence bound ε > 0, both agents move a µ-fraction towards each other, for a convergence parameter µ ∈ (0, 1/2]. Otherwise, no update occurs. Depending on the parameters ε, µ, and the initial configuration, the bounded-confidence mechanism can lead to consensus, clustering, or persistent polarization. Our model can be seen as a discretization of the DW process where we replace the standard averaging behavior by a random pull operation, as discussed in the introduction. Informally speaking, our update rule removes the notion of compromise and instead lets one of the two agents completely adopt the other’s opinion. While the DW process has been extremely popular over the last decades, the vast majority of works rely on experimental analysis [37, 38]. Analytical results on convergence properties include bounds for asymmetric [50] and heterogeneous [8] variants. More broadly, many bounded-confidence models for opinion formation have been studied; a recent survey summarizes mathematical properties and provides further references [6]. The Axelrod Model: The Axelrod model is a simple way of exploring how people influence one another. It shows how local interactions can make communities more alike while still (1, 1) (1, 2) (1, 3) allowing distinct cultural groups to emerge. Seeking formalization, let G = (V, E) be an undirected graph with n = |V | and m = |E|. Each vertex v has a so-called culture Xv = (2, 1) (2, 2) (2, 3) (Xv,1 , . . . , Xv,F ) ∈ [q]F . For {u, v} ∈ E, let the difference between the cultures of the two endpoints be s(u, v) = |{i : Xu,i = Xv,i }|. The process now updates the cultures as follows: At each step, choose an edge uniformly. With probabil(3, 1) (3, 2) (3, 3) ity s(u, v)/F , choose a disagreeing feature uniformly and let a uniformly chosen endpoint copy the other’s trait. A configuFigure 2: The opinion graph of the Axelrod ration is absorbing iff for all edges, it holds s(u, v) ∈ {0, F }, model with F = 2 and q = 3. i.e., neighboring agents are either identical or completely incompatible. Consequently, the process may end in consensus or in several mutually incompatible cultural regions. In the case F = 2, i.e., when each agent has precisely two traits (and each trait can take q different values), the Axelrod model coincides with our model on the 2-dimensional rook graph on q 2 nodes (if we exclude the idle steps). 3

Lotka Volterra Processes: Finally, a related framework is studied in [15]. The authors consider a broad class of protocols with randomly interacting agents whose opinion updates follow so-called discrete LotkaVolterra (LV-type) dynamics. More precisely, in each step, a directed pair of agents (v, w) is picked uniformly and independently at random. However, in this framework, the opinion graph can be directed and weighted: For any two opinions i, j there is probability pij ∈ [0, 1], s.t., with probability pij an agent with opinion i switches to j if it interacts with an agent with opinion j. Our protocol falls within this class as we choose pij = 1 if there is an edge {i, j} in the opinion graph and 0 otherwise. Their analysis establishes polynomial convergence-time guarantees, showing that any LV-type protocol converges in O(nc ) steps for some constant c ≫ 2 (provided that all pij ’s are constant). In contrast, we focus on a specific protocol and provide a significantly more fine-grained analysis. In particular, we show our class of processes converges after O(n2 log n) steps.

1.2 Notation & Preliminaries We consider the voter model with a simple, undirected opinion graph G = (O, E). The nodes of G are the q available opinions O = {1, . . . , q}. We let ∆ be the maximum degree in G. For the analysis, we may discard opinions with initial support zero, since they can never reappear. Thus, we assume w.l.o.g. that every opinion initially has positive support and q ≤ n. We assume n ≥ 2; the case of one agent is immediate. Passing to the induced opinion graph can only decrease its maximum degree. We use log for the natural logarithm; other bases are indicated explicitly. Moreover, there is a set A of n agents and each agent u has initially one of the q opinions. The opinion of agent u at the beginning of step t is denoted by ou (t) ∈ O. We define Si (t) as the set of agents with opinion i at the beginning of step t and Si (t) = |Si (t)|. We refer to Si (t) as the support of i at the beginning of step t. For a subset of opinions O′ ⊆ O, let SO′ (t) := {v ∈ A | ov (t) ∈ O′ } be the set of agents with an opinion from O′ in step t. Again, we define SO′ (t) = |SO′ (t)|. We denote by P (t) = {{u, v} | {ou (t), ov (t)} ∈ E} the set of productive pairs (or productive edges). Let the pair {u, v} be chosen in step t. Then, we call an opinion o ∈ O active in step t if ou (t) = o or ov (t) = o. Likewise, an edge {o, o′ } ∈ E is active (in step t) if o = ou (t) ⃗ and o′ = ov (t). We call S(t) the configuration of the system at time t. Since the interactions are the same ⃗ as (S1 (t), . . . , Sq (t)). We denote the initial for all agents with the same opinion, we can simply define S(t) configuration by ⃗s0 . Opinion i is decided in step t if either Si (t) = 0 or we have Sj (t) = 0 for all opinions j with {i, j} ∈ E. Otherwise, i is undecided. Note that once an opinion is decided, it will never become undecided again. The stabilization time is the first time step in which all opinions are decided. Moreover, we use some common terms from the analysis of (randomized) algorithms. We will use the Õ(·)-notation, which suppresses polylogarithmic factors (similar to the O(·)-notation, which suppresses constant factors). We say an event holds with high probability (w.h.p.) if it holds with probability at least 1 − 1/nc for some c > 1. Finally, we use sometimes use E [·] as shorthand for E [· | X]. X

4

2 Our Results and Techniques In this section, we give an overview of our results and the main techniques used in the respective proofs. We study two variants of the VOG process, called the ordinary EdgeVOG process and the productive EdgeVOG process. Both variants are defined with respect
to a fixed opinion graph G = (O, E) and a set of agents A A. In each step t, a pair of agents u, v ∈ 2 is selected. If their current opinions are compatible, that is, if ou (t), ov (t) ∈ E, then one of the two agents adopts the opinion of the other, with each direction chosen with probability 1/2. More precisely, either ou (t + 1) = ov (t) or ov (t + 1) = ou (t), while all other opinions remain unchanged. If the two opinions are not adjacent in G, no update occurs. The two variants differ only in how the interacting pair
is selected. In the ordinary EdgeVOG process, the pair is chosen uniformly at random from all pairs in A2 . In the productive EdgeVOG process, it is chosen uniformly from the currently productive pairs, namely those pairs whose opinions are adjacent in G. Note that the ordinary process models a well-mixed population: the communication graph is complete, and every pair of agents is equally likely to interact. This standard mean-field assumption is also used in classical versions of the voter model [27], the Deffuant–Weisbuch model [49], the Hegselmann–Krause model [29], and discrete Lotka-Volterra processes [15]. The authors of [15] note that these are the same interaction rules as in a population protocol. It is easy to see that, after removing all idle steps, the ordinary process has exactly the same distribution as the productive process. Protocol 1 Ordinary EdgeVOG on G = (O, E)

Protocol 2 Productive EdgeVOG on G = (O, E)

In each step t = 0, 1, 2, . . .: ( ) Pick a pair {u, v} ∈ A u.a.r. 2 if {ou (t), ov (t)} ∈ E: Flip a fair coin c ∈ {Heads, Tails} if c = Heads ou (t + 1) ← ov (t); else ov (t + 1) ← ou (t)

In each step t = 0, 1, 2, . . .: ( ) Let P (t) := {{u, v} ∈ A | {ou (t), ov (t)} ∈ E} 2 if P (t) = ∅: stop Pick a pair {u, v} ∈ P (t) u.a.r. Flip a fair coin c ∈ {Heads, Tails} if c = Heads ou (t + 1) ← ov (t); else ov (t + 1) ← ou (t)

Our results are organized as follows. In Section 2.1 we study the convergence times of the ordinary and of the productive EdgeVOG processes. In Section 2.2, we consider the properties of the stable configuration. We give a lower bound on the probability that a given opinion survives and a tail estimate on the number of surviving opinions. We then bound the maximum support attained by any opinion during the process in Section 2.3. Finally, we summarize our results in Section 2.4.

2.1 Bounds on the Stabilization Time We begin by presenting our potential function Ψ, which is the main tool of our analysis. Then, we present our worst-case bounds for the ordinary and productive process that are proved with the help of this potential. Finally, we give a parameterized bound for the productive process that depends on the opinion graph degree and the maximal support. The Potential Function Ψ. For the analysis of both our processes, we use a (family of) potential function(s): ⃗ For an edge i, j ∈ E, we define its potential at time t as Ψij (S(t)) = Si (t) · Sj (t), where Si (t) denotes the support of opinion i. The potential associated with an opinion i ∈ O is X ⃗ ⃗ Ψi (S(t)) = Ψij (S(t)) (Potential of opinion i in step t). j∈Ni

An opinion i is called decided once either Si (t) = 0 or all its neighboring opinions have support zero. Equiv⃗ alently, i is decided precisely when Ψi (S(t)) = 0. Finally, we define the potential of the entire configuration by ⃗ Ψ(S(t)) =

X i,j∈E

1 ⃗ Ψij (S(t)) = 2

X

⃗ Ψi (S(t))

i∈O

5

⃗ (Potential of S(t)).

⃗ Note that Ψ(S(t)) = |P (t)|, since both quantities count the productive pairs. Hence, we can define the ⃗ stabilization time as T := inf{t ≥ 0 : Ψ(S(t)) = 0}. If clear from context, we will simply write Ψ(t) ⃗ instead of Ψ(S(t)). In Section 3.1, we establish several properties of these potential functions that will be used throughout the paper. Crucially, we will show that this potential exhibits a negative drift in expectation for both the ordinary and productive processes. Proposition 1. Let P(t) ∈ {0, 1} indicate that step t is productive. Then, for every possible configuration ⃗s it holds h i ⃗ + 1)) = Ψ(⃗s) − E [P(t)] . E Ψ(S(t ⃗ S(t)=⃗ s

⃗ S(t)=⃗ s

Proof sketch. The statement follows from straightforward calculation and the law of total expectation. Condi⃗ = ⃗s}. If step t is not productive, the potential remains unchanged. If the step is productive and tion on {S(t) involves opinions i and j, then one unit of support is transferred between i and j, with either direction being equally likely. With a straightforward calculation, it can be shown that Ψij decreases by one in expectation as 1 1 (si − 1)(sj + 1) + (si + 1)(sj − 1) = si sj − 1. 2 2 All other contributions remain unchanged in expectation: Consider an edge {i, k} with k ̸= j. As si increases or decreases with equal probability and sk does not change, the potential Ψik does not change in expectation. The same holds for Ψjk with k ̸= i. The potentials of edges disjoint from {i, j} do not change at all. Thus, every productive step decreases Ψ by exactly one in expectation, independently of the chosen productive edge. The statement then follows by the law of total expectation. The full proof with all calculations can be found in Section 3.1 This innocent-looking proposition is the key to many of our results, as it directly relates the convergence time to the number of productive steps. As we don’t restrict how edges are chosen, the proposition is quite flexible and may also be of independent interest. For any rule that decides on which pairs are picked, we simply need to bound the time in which Ψ(0) productive pairs are picked to obtain the expected runtime. In particular, it gives a simpler proof of the corresponding bound for asynchronous pull voting on regular communication graphs in [14]; see Section 5. Note that the potential has been used before by Öztürk[43]. Stabilization Time of the Ordinary Process Given our potential, we consider the worst-case convergence times of the ordinary EdgeVOG process. Rather surprisingly, the bounds for the ordinary process do not depend on the initial configuration nor the opinion graph. Instead, regardless of the opinion graph and the initial configuration, the convergence time is at most essentially quadratic in the number of agents, namely Theorem 2. Let G = (O, E) be an arbitrary opinion graph and suppose the process starts in an arbitrary configuration. Then, the ordinary EdgeVOG process converges in O(n2 log n) steps in expectation and w.h.p. The bound in expectation is asymptotically tight, even when ∆ = 1. Proof sketch. For the proof, we consider the expected potential drop from step to step. Suppose that the process has potential ψ at step t. As ψ is equal to the number of productive pairs and in a complete commu

nication graph each pair is picked with probability 1/ n2 , the probability that a
step is productive is ψ/ n2 . Therefore, by Proposition 1, in each step the expected drop in potential is ψ/ n2 as well. Thus, by the law of total expectation, we get "

# ⃗ Ψ( S(t)) ⃗ + 1)) = E Ψ(S(t)) ⃗
E Ψ(S(t − = n h

i

2

1 1 − n

!

h i ⃗ E Ψ(S(t)) .

2

This fact alone is sufficient to prove Theorem 2 as we apply standard drift theorems (see [36]) to derive the stated bounds. The full proof is given in Section 3.2.

6

Recall that the standard voter model on a complete communication graph has a worst-case convergence time of Θ̃(n2 ) steps in expectation and with high probability [14]. Thus, our result provides two observations: First, up to logarithmic factors, EdgeVOG has asymptotically the same worst-case convergence time as the standard voter despite restricting the set of admissible opinions via G. Second, the bound in expectation is tight, including the logarithmic factor. To see this, let n be even and let the opinion graph consist of n/2 disjoint edges, with one agent initially holding each opinion. Each component contains exactly two agents and stabilizes as soon as this pair is selected for the first time. When r components remain undecided,
there are exactly r productive pairs, so the expected waiting time until the n next component stabilizes is 2 /r. Consequently, 

E Tordinary



 X n/2 n 1 = Θ(n2 log n). = r 2 r=1

In contrast, the productive process stabilizes after exactly n/2 steps, since each productive interaction resolves one component. Worst-Case Stabilization Time of the Productive Process We next consider the productive process, which omits all idle steps in which agents with non-adjacent opinions interact. Under a natural coupling, it therefore cannot take more steps than the ordinary process. However, rather surprisingly its stabilization time can still have a long tail: although its expectation is exactly the initial number of productive pairs, there are configurations with only n − 1 productive pairs for which the process takes Ω(n2 ) steps with probability Ω( n1 ). To be precise, it holds: Theorem 3. Let G = (O, E) be an arbitrary opinion graph and suppose the process starts in a configuration s⃗0 with |P (0)| productive pairs. Then, the productive EdgeVOG process converges in exactly |P (0)| steps in expectation and O(n2 log n) w.h.p. Furthermore, there are graphs and configurations with Ψ(0) = n − 1 that require Ω(n2 ) steps with prob. Ω( n1 ). Proof Sketch. We first determine the expectation. Since every step is productive, Proposition 1 shows that the potential decreases by exactly one in expectation in every step. The potential is non-negative and equals zero exactly when the process has stabilized. Thus, the additive drift theorem gives E [T ] = Ψ(s⃗0 ) = |P (0)|. For the tightness result, consider a star graph with n opinions and place one agent on each opinion. Let i be the central opinion. Every productive interaction involves i and one of the leaves, and either agent adopts the opinion of the other with probability 1/2. Therefore, Si (t) performs a simple symmetric random walk on {0, . . . , n} starting at 1. The process stabilizes precisely when this walk reaches 0 or n. By the standard gambler’s-ruin formula, the expected absorption time is n − 1. Moreover, the walk reaches ⌊n/2⌋ before reaching 0 with probability Θ(1/n). From there, it takes Ω(n2 ) additional steps with constant probability. Thus, the stabilization time is Ω(n2 ) with probability Ω(1/n). The full proof is given in Section 3.3. Parameterized Stabilization Time of the Productive Process Although the bounds from the previous theorem are tight for some opinion graphs and initial configurations, many natural instances stabilize much faster than the worst-case bound of O(n2 log n). Intuitively, if the opinion graph is sparse and the agents are initially spread across many opinions, the occupied part of the opinion graph should quickly break into small components, which then stabilize rapidly. This suggests that a more refined analysis should take into account both the structure of the opinion graph and the initial distribution of the agents. The following theorem confirms this intuition at a general level. We bound the stabilization time in terms of the initial number of productive pairs, the largest support attained by any opinion, and the maximum degree of the opinion graph. More precisely, for an opinion graph G, an initial configuration s⃗0 , and a constant c > 0, define     −c ⃗ . Ŝc (G, s⃗0 ) := min x ≥ 0 : Pr max max Si (t) > x S(0) = s⃗0 ≤ n (1) i∈O 0≤t≤T

Thus, Ŝc (G, s⃗0 ) is the smallest threshold such that, with probability at least 1 − n−c , no opinion ever has support larger than this threshold. 7

The following theorem provides a general parameterization rather than an explicit bound for a particular class of opinion graphs. In particular, it shows that the stabilization time can be subquadratic whenever the initial potential, the maximal support, and the maximum degree are sufficiently small. Since Ŝc (G, s⃗0 ) depends on both the opinion graph and the initial configuration, we derive an explicit bound on this quantity later in Section 2.3. Theorem 4. Let G = (O, E) be an opinion graph with maximum degree ∆, and suppose that the process starts in a configuration s⃗0 with |P (0)| productive pairs. Furthermore, let Ŝc (G, s⃗0 ) be defined asin (1) for a large enough  e |P (0)| + ∆2 Ŝc (G, s⃗0 )2 c ≥ 1. Then, with high probability, the productive EdgeVOG process stabilizes within O steps. Alternatively, the polylogarithmic factor multiplying |P (0)| can be removed at the cost of a larger polynomial dependence on ∆, giving   e ∆6 Ŝc (G, s⃗0 )2 . O (|P (0)|) + O Proof sketch. Recall that, by Proposition 1, the potential decreases by one in expectation in every step. However, it can still increase in individual steps. To obtain a high-probability bound, we therefore need to control how far the potential can rise before the process stabilizes. For this, our upper bound Ŝc (G, s⃗0 ) comes into play. For readability, write Ŝ := Ŝc (G, s⃗0 ) and b := ∆Ŝ in the remainder. If the initial configuration is already stable, there is nothing to prove. First, let τsupp be the first step in which some opinion has support larger than Ŝ, and let T̃ := T ∧ τsupp . By definition of Ŝ, the probability of such a support violation is at most n−c . Thus, it suffices to bound T̃ and afterwards add n−c to the failure probability. We stop the potential at τsupp . Its stepwise changes have absolute value at most 2b. Thus, the stopped potential is a supermartingale with bounded differences. Suppose we start from a configuration with potential ψ before a support violation. For a sufficiently large constant C, let
B := C ψ + b2 log2 n . The maximal version of Azuma’s inequality shows that the stopped potential stays below B for a suitably (B) chosen interval of Θ(B log n) steps, w.h.p.; see Lemma 12. We also use auxiliary node potentials Ψ̂i that agree with Ψi until the first support violation or the first time τB when the potential exceeds B, and are zero afterwards. For opinions at pairwise distance at least four, one interaction can affect at most one node potential. In Lemma 14, we use this observation to derive a joint moment bound for the auxiliary potentials. Equipped with these observations, we distinguish between high and low potentials. We say that a potential is high if it is larger than H := 32c∆4 b2 log2 n; otherwise, it is low. If the potential is hight, we partition the opinions into 4-separated sets and apply the variant of the Chernoff bound from Theorem 35 to each set. This variant applies to the specific dependencies captured by our joint moment bound. Starting from potential ψ, we end a phase when the potential first falls to at most max{ψ/2, H} or the support bound is violated. In Lemma 15, we show that such a phase lasts O(ψ + b2 log2 n) steps, w.h.p. This estimate holds conditional on the history at the beginning of each phase. A union bound over O(log n) phases and summing their lengths shows that the potential falls to H within O(|P (0)| + b2 log3 n) steps, w.h.p., unless the process has already stopped. Once the potential is at most H, we use the joint moment bound only for singleton sets. Summing over P (B) all opinions gives, for the auxiliary global potential Ψ̂(B) = 21 i Ψ̂i ,   h i 1 t (B) ≤ n2 e−t/B , E Ψ̂ (t) ≤ ψ 1 − B where we restart the auxiliary potentials at the beginning of this part and write ψ ≤ H for its initial potential. For t = ⌈(c + 4)B log n⌉, this expectation is at most n−(c+2) . Unless one of the bounds has been violated, the auxiliary potential is a positive integer whenever the process has not stabilized. Thus, Markov’s inequality, together with the Azuma bound, shows that the process stabilizes or violates the support bound within another O(∆4 b2 log3 n) steps, w.h.p.; see Proposition 16. Adding the probability of a support violation gives the second bound,  
T ∈ O |P (0)| + ∆4 b2 log3 n = O |P (0)| + ∆6 Ŝ 2 log3 n , 8

with high probability. Finally, the same expectation calculation can be applied directly from the initial configuration, without first reducing the potential to H. This gives O((|P (0)| + b2 log2 n) log n) steps w.h.p., proving the first bound. The details are given in Section 3.4.

2.2 Distribution of Surviving Opinions Next, we move away from stabilization time and consider the properties of a stable configuration. Recall that in the standard voter model, the process eventually reaches consensus, i.e.,exactly one opinion survives. In our process, by contrast, multiple opinions may coexist indefinitely, provided that the surviving opinions form an independent set in the opinion graph. In this section, we analyze how large the number of surviving opinions can be. To this end, we first consider the survival probability of a single opinion, and then we show that many opinions survive if the opinion graph is sufficiently sparse. Survival Probability of a Fixed Opinion Note that for a complete opinion graph it is known from the analysis of the standard pull voter process that (on a regular communication graph) an opinion survives with probability exactly sni (where si is the initial support). As it turns out, this bound naturally generalizes to our model. It holds Theorem 5. Let G = (O, E) be the opinion graph and let si ≥ 1 denote the initial support of opinion i ∈ O. Let Xi := 1{Si (T )>0} indicate whether opinion i is present in the stable configuration, then E [Xi ] ≥

si +

s Pi

j∈Ni sj

.

P Proof sketch. The lemma follows from a straightforward martingale argument. Let Mi (t) := j∈Ni Sj (t) be the total support of the opinions adjacent to i. Note that the potential of i is precisely Ψi (t) = Si (t) · Mi (t). Define τi := inf{t ≥ 0 : Ψi (t) = 0} = inf{t ≥ 0 : Si (t) = 0 or Mi (t) = 0}. Thus, τi is the first time at which we know if i itself is extinct or if all neighboring opinions are extinct. Using this definition, consider the stopped process  Si (t)   if t < τi ,  Si (t) + Mi (t) Ri (t) := (2) Si (τi )   if t ≥ τi .  Si (τi ) + Mi (τi ) At time τi , either Si (τi ) = 0 or Mi (τi ) = 0. Consequently, Ri (τi ) = 0 if opinion i becomes extinct and Ri (τi ) = 1 if all its neighboring opinions become extinct. Since extinct opinions cannot reappear, we have Ri (T ) = Ri (τi ) = Xi . A direct one-step calculation shows that (Ri (t))t≥0 is a bounded submartingale. An interaction between opinion i and one of its neighbors changes Si (t) symmetrically by ±1 while leaving Si (t)+Mi (t) unchanged. An interaction between a neighboring opinion and an opinion outside {i}∪Ni changes the denominator symmetrically by ±1. With some straightforward calculation, we can show that Ri (t) increases in expectation in this case. All other interactions leave Ri (t) unchanged. Hence, the Optional Stopping Theorem (cf. Theorem 30) yields E [Xi ] = E [Ri (T )] ≥ Ri (0) =

si +

s Pi

j∈Ni sj

.

(3)

For the detailed proof, see Section 3.5. P Now let Z := i∈O Xi be the number of surviving opinions. In the special case in which every opinion P has equal support, we have E [Z] ≥ i∈O di1+1 , where di is the degree of opinion i. For comparison, the CaroWei bound guarantees that every graph with degree sequence (di )i∈O contains a maximal independent set P of size at least i∈O di1+1 . Thus, our stochastic process produces, in expectation, an independent set whose guaranteed size matches the Caro-Wei bound. In other words, in expectation, we sample a big independent set.

9

Number of Surviving Opinions Next, we investigate what Graph class Arboricity χ(G2 ) we can show beyond the expectation, i.e., what is the probabil- Forests 1 ∆+1 ity that the surviving set is indeed large? To put it more techni- Planar graphs 3 O(∆) cally, we want to bound the probability that Z deviates from its Treewidth k k Ok (∆) √ expected size. Unfortunately, we cannot use the standard Cher- Euler genus g O( pg + 1) Og (∆) noff and Hoeffding bounds for Z as the survivals of neighbor- K -minor-free O(r log r) O (∆) r r ing opinions are highly correlated: Two neighboring opinions General graphs ⌈(∆ + 1)/2⌉ ∆2 + 1 cannot both survive. Furthermore, if two opinions have shared neighbors, these neighbors’ supports affect both nodes’ Ri (t)’s, Figure 3: Arboricity and chromatic number of the variable by which we bound the survival probability in the the square for common graph classes. ∆ is the proof of Theorem 5. Nevertheless, Theorem 6 shows that the maximal degree. The parameters k, g, and r are number of P surviving opinions is unlikely to be much smaller considered fixed. ∑ than µ := i∈O pi with pi = si/si + j∈Ni sj , even though the individual survival events are not independent. The loss compared with the usual multiplicative Chernoff bound is entirely captured by κ = χ(G2 ), i.e., chromatic number of the squared opinion graph G2 . Recall that two vertices are adjacent in G2 if their distance in G is at most two. More precisely, it holds Theorem 6. Let G = (O, E) be an opinion graph and let κ := χ(G2 ). For every 0 ≤ δ ≤ 1,  2  δ µ Pr [Z ≤ (1 − δ)µ] ≤ exp − . 2κ

(4)

Proof sketch. For every opinion i, we consider the ratio Ri (t) = Si (t)/(Si (t) + Mi (t)) from Q the previous proof. Moreover, for every set I of opinions at pairwise distance at least three, the product i∈I (1 − Ri (t)) is a supermartingale. Hence, for any such set, it holds " # Y Y E (1 − Xi ) ≤ (1 − pi ). i∈I

i∈I

It is known that for P binary random variables with this property, Chernoff and Hoeffding bounds hold too if we consider µ = i∈I pi instead of the expectation. This has, for example, been shown in [47]. Just as the standard Chernoff bound, this result can be extended to variables whose dependencies can be modeled through a graph. To get a result for all variables and not just the ones in distance 3, we now consider a coloring of G2 with κ = χ(G2 ) colors. Note that all nodes in the same color class are in distance at least 3 to each other as they form an independent set in G2 . With some straightforward adaptation to the proof of the standard Chernoff bound, we derive a bound of Pr [Z ≤ (1 − δ)µ] ≤ exp(−δ 2 µ/(2κ)). For the detailed proof, see Section 3.6. As G2 has degree at most ∆2 , the parameter κ can always be bounded by ∆2 + 1. Consequently, on a ∆-regular opinion graph with equal initial supports, Ω(q/∆) opinions survive with probability 1 − exp(−Ω(q/∆3 )). Moreover, the parameter κ can be bounded particularly well for sparse graph classes: A typical measure for sparseness is the arboricity, the number of forests a graph can be divided into. Agnarsson and Halldórsson [1] showed2 that, for every fixed a and p, there exists a constant c such that every graph G with arboricity a satisfies χ(Gp ) ≤ c · 2p · a⌈p/2⌉ · ∆⌊p/2⌋ . Given this insight, for these graphs, the theorem improves to  2   δ µ , Pr [Z ≤ (1 − δ)µ] ≤ exp −Ωa (5) ∆ where the hidden constant polynomially depends on the arboricity bound a. Additionally, as the average degree of these graphs is at most 2a, with a uniform initialization, it holds µ ∈ Ω(q/a). Thus, for a constant a ∈ O(1), a set of size Θ(q) survives with at least constant probability independent of q and ∆. In Fig. 3 we provide an overview of well-known graph classes and their respective bounds on the arboricity and the chromatic number. 2

[1] showed the result for only planar graphs, but [33] remarked that the proof can be extended to all graphs of bounded arboricity.

10

2.3 Maximal Support on Bounded-Degree Graphs Finally, we bound the maximal support Ŝ attained by any opinion during the process. Our main result in this section gives such a bound for opinion graphs of bounded degree when the initial support of every opinion is bounded. Recall that a bound on Ŝ also gives a direct bound on the number of productive steps. The main difficulty is that neighboring opinions are affected by the same interactions, so their supports are highly dependent. The basic idea is to show that the graph quickly breaks into small connected components of active opinions, each containing only a small number of agents. The support of any opinion is then at most the total number of agents in its component. Before proving the general result, we present the argument for a cycle, where ∆ = 2 and every opinion initially has support one. This special case already contains the main idea but avoids several additional complications needed for general bounded-degree graphs. Maximal Support on a Cycle Graph On a cycle, we show that sufficiently many opinions become decided before any support grows too large. These opinions split the remaining active opinions into short paths containing only O(log n) agents. This gives the following bound. Theorem 7. Let G = (O, E) be a cycle on n opinions, and suppose that every opinion initially has support one. Then, for both the EdgeVOG and the productive EdgeVOG processes, with high probability every opinion has support O(log n) throughout the process. Proof sketch. For the analysis we adopt a random-walk-based view of the process. Each agent can be seen as a token that is assigned to the node of the opinion graph that corresponds to its opinion. Note that, whenever an agent with opinion i adopts another opinion j, the corresponding token moves to opinion j. Thus, these tokens perform a (biased) random walk. We say that an opinion is decided if either it contains no tokens, or none of its neighboring opinions contains any tokens. Moreover, once an opinion becomes empty, it can effectively be removed from the graph, since no agent can ever adopt this opinion again. With this abstraction, it is relatively straightforward to bound the maximal support for the cycle graph. We show with high probability the process quickly decomposes into connected components containing only O(log n) agents. To this end, fix an opinion i, and let Cdi and Cd′i denote the clockwise and counter-clockwise paths of d ∈ O(log n) opinions adjacent to i. If more than 2d + 1 agents ever gather at i, one agent must have started outside these paths and traversed one of them. Every internal opinion on its route must then have been productive at least twice. Now consider a fixed independent set of at least d/2 opinions on one of these paths. Each opinion initially has one agent, so it becomes extinct with probability 1/2 in its first productive interaction. For an opinion to be productive twice, this first interaction must instead increase its support. Since no interaction involves two opinions in the independent set, we can assign independent fair coins to these first interactions. Thus, the probability that an agent traverses the path is at most 2−d/2 . A union bound over both directions and all opinions gives the desired bound throughout the process. We give the full analysis in Section 3.7.

Maximal Support on Graphs of Maximum Degree ∆ For the generalization to graphs of maximum degree ∆ and initial support at most ŝ, we show that decision events of opinions at pairwise distance at least four satisfy essentially the same joint tail bound as independent events. This allows us to prove that most opinions are decided before they can attract many agents. However, each opinion may still have up to O(∆3 ) nearby opinions whose decision events are strongly correlated with its own. This leads to the relatively large polynomial dependence on ∆ in our bound (which we do not believe to be optimal). More precisely, we obtain the following result. Theorem 8 (simplified). Let G = (O, E) be an arbitrary graph of maximum degree at most ∆, where ∆ ≥ 1, and suppose that every opinion has initial support at most ŝ. For the EdgeVOG and the productive EdgeVOG processes, with high probability, every opinion has support at most Õ(min{n, ∆6 ŝ}) simultaneously for all steps t ≥ 0. Proof sketch. Fix an opinion i ∈ O. We want to show that it is unlikely that i belongs to a connected component in which many agents can accumulate. On the cycle, it was enough to find two opinions within distance 11

1

Wi6 (t) 8

1

6

Wi4 (t)

5

i

8

14

1

7

6

5

1

7 3

(a). The witness set for τ = 6.

8

i 14

4

1

7

6

5

i 14

7

4

Wi3 (t)

7 4

1

7 3

3

(b). The witness set for τ = 4.

(c). The witness set for τ = 3.

Figure 4: Witness sets of a fixed opinion i for three values of τ . The number in each node denotes how often the opinion has been productive. As τ decreases, the witness set can only grow.

O(log n) of i that become decided before being productive twice. Extending this argument to arbitrary graphs and initial configurations introduces two main obstacles. First, if an opinion initially has more than one agent, it no longer becomes extinct with probability 1/2 after its first productive step. Second, when ∆ ≥ 3, the number of connected subsets containing i grows exponentially with their size and not linearly. Thus, even if any fixed connected subset is unlikely to contain many agents, we cannot directly take a union bound over all such subsets as there are exponentially many. We address the first obstacle by showing that, for any fixed opinion i, the probability that i remains undecided after τ productive steps is at most ∆ŝ2 /τ . This follows by adapting the potential argument from Proposition 1. In particular, we show that the expected number of productive steps (that involve i) before ⃗ i becomes decided is at most Ψi (S(0)). As i has at most ∆ incident edges and the initial potential of each 2 ⃗ such edge is at most ŝ , it holds Ψi (S(0)) ≤ ∆ŝ2 . The claim then follows from Markov’s inequality. Next, we consider the dependencies between these opinions: If I ⊆ O consists of opinions at pairwise distance at least four, then the probability that every opinion in I remains undecided after τ productive steps is at most (∆ŝ2 /τ )|I| . Thus, for the purpose of tail bounds, sufficiently distant opinions behave as if their decision events were independent. The precise statement and its proof are given in Lemma 27. To address the second obstacle, we introduce so-called witness sets: Fix an opinion i and parameters τ, t ≥ 0. Informally, the witness set Wiτ (t) is the largest connected set containing i in which every opinion has been productive at least τ times before step t; see Definition 22 for the precise definition. Figure 4 shows three examples for different values of τ . Witness sets allow us to control how many agents can accumulate in a connected part of the active opinion graph. Any agent that holds an opinion in Wiτ (t) at time t but did not initially hold an opinion in this set must have crossed its outer boundary. This boundary contains at most ∆|Wiτ (t)| opinions, and if i has been productive at least τ times, every opinion on the outer boundary has been productive fewer than τ times; otherwise, it would belong to the witness set as we defined them to be maximal. If i has been productive fewer than τ times, the witness is {i} and its total number of productive boundary interactions is less than τ . A crude upper bound on the number of agents that can enter the witness set is therefore τ ∆|Wiτ (t)|. Consequently, if both τ and |Wiτ (t)| are small, then the total support inside the witness set is also small. However, this deterministic bound is too weak for our purposes. We therefore strengthen it slightly: Whenever a productive interaction crosses the boundary, an agent enters the witness set with probability 1/2 and leaves it with the same probability. Thus, the net influx behaves like a simple random walk. A martingale concentration bound that, with high probability, the net number of agents entering the witness √ then shows τ set is at most Õ( τ ∆ · |Wi (t)|); see Proposition 24. Given these observations, it remains to find a sufficiently small value τ ⋆ for which every witness set ⋆ τ Wi (t) is small, simultaneously for all opinions i and all times t. In Proposition 26, we show that one can choose τ ⋆ = O(∆5 ŝ2 ) such that every witness set contains at most O(∆3 log n) opinions with high probability. The main ingredient of the proof is the joint tail bound above. Let I be a set of opinions at pairwise distance at least four. The probability that every opinion in I remains undecided after τ productive steps is at most (∆ŝ2 /τ )|I| . A textbook counting argument shows that, for each fixed opinion i, there are at most O(∆4c log n ) relevant candidate witness sets containing a 4-separated set I of size c log n. Choosing τ = c′ ∆5 ŝ2 for a sufficiently large constant c′ , the probability that all opinions in such a set remain undecided is at most (1/(c′ ∆4 ))|I| . A union bound over all candidate sets therefore shows that, with high probability, no witness 12

set contains a 4-separated set of size at least c log n. Now let I be a maximal 4-separated subset of a witness set. By maximality, every opinion in the witness set is within distance three of some opinion in I. Since every ⋆ radius-three neighborhood contains O(∆3 ) opinions, we obtain |Wiτ (t)| = O(∆3 |I|) = O(∆3 log n). √ ⋆ Finally, the witness set initially contains at most ŝ|Wiτ (t)| agents, and its net influx is at most Õ( τ ⋆ ∆ · ⋆ ⋆ |Wiτ (t)|). Substituting τ ⋆ = O(∆5 ŝ2 ) and |Wiτ (t)| = O(∆3 log n) gives a total support of Õ(∆6 ŝ). Since the support is always at most n, this proves the claimed bound. The full proof, including the details omitted here, is given in Section 3.8.

2.4 Conclusion and Future Work We studied the voter model with opinion graph. Our goal was to understand how the structure of the opinion graph affects the stabilization time, the number of surviving opinions, and the largest support attained by an opinion. For arbitrary opinion graphs and initial configurations, both the ordinary and the productive e 2 ) steps in expectation and with high probability. For the producEdgeVOG processes stabilize within O(n tive process, we further showed that the expected stabilization time is exactly the initial number P |P (0)| of productive pairs. We also proved that an opinion i survives with probability at least si /(si + j∈Ni sj ) and established a lower-tail bound for the total number of surviving opinions. In particular, on a ∆-regular opinion graph with equally supported opinions, Ω(q/∆) opinions survive with probability 1 − exp(−Ω(q/∆3 )). Finally, if every opinion initially has support at most sb, then the support attained by any opinion is at most e O(min n, ∆6 sb) with high probability. Together with our parameterized stabilization bound, this shows that sparse opinion graphs with well-spread initial configurations can stabilize much faster than the worst-case bound while preserving many opinions and preventing any single opinion from becoming dominant. The most immediate open problem is to improve the dependence on ∆ and sb, as we do not believe that our bounds are optimal. Another direction would be to replace the maximum degree by finer structural parameters of the opinion graph, similar to our results on the survival probability. It would also be interesting to determine which of our quantitative results extend to the arbitrary interaction graphs considered by Lanchier and Scarlatos. Further directions include dynamic or asymmetric opinion graphs and a more direct comparison with continuous bounded-confidence processes such as the Deffuant–Weisbuch model.

13

3 Proofs 3.1 Proof of Proposition 1 (Properties of our Potential Function) ⃗ In this section, we define the potential function Ψ(S(t)) which forms the basis of our analysis and prove some ⃗ helpful properties. For each edge {i, j} ∈ E of the opinion graph, let Ψij (S(t)) = Si (t) · Sj (t) be the product of the endpoints’ supports in step t. We define ⃗ Ψ(S(t)) =

X

⃗ Ψij (S(t)).

(6)

{i,j}∈E

⃗ Recall that an opinion is decided if (and only if) Ψi (S(t)) = 0. Thus, the convergence time can be restated ⃗ ⃗ in terms of this potential as the random variable T := min{t ≥ 0 | Ψ(S(t)) = 0}. Note that Ψ(S(t)) ≤ 2 n(n − 1)/2 ∈ O(n ), the number of all unordered pairs of agents. For the proofs, we bound the expected ⃗ ⃗ + 1)) for the EdgeVOG process and then apply appropriate drift theorems to change from Ψ(S(t)) to Ψ(S(t derive results on the expected convergence time. The following lemma bounds the expected difference in the potential from step t to step t + 1. As we use it for several theorems, we state in a slightly technical way. Proposition 1. Let P(t) ∈ {0, 1} indicate that step t is productive. Then, for every possible configuration ⃗s it holds h i ⃗ + 1)) = Ψ(⃗s) − E [P(t)] . E Ψ(S(t ⃗ S(t)=⃗ s

⃗ S(t)=⃗ s

⃗ ⃗′ ⃗ Proof. Throughout the proof, we omit the conditioning h on {iS(t) = ⃗s} and let S = S(t + 1) for readability. ⃗ ′ ) = Ψ(⃗s) = 0. Thus, assume the process is not Further, if the process is converged, then trivially, E Ψ(S converged, and in step t, a productive pair {v, w} ∈ A × A is chosen. Finally, assume that ov = i and ow = j. Since the behavior of the process is the same no matter which particular agents with opinions i and j we choose, we simply define the event e(t) = {i, j}, which indicates that agents with opinion i and j are chosen. First, we prove the following helpful claim: ( h i ⃗ ′ ) e(t) = {i, j} = Ψkl (⃗s) − 1 if {k, l} = {i, j} Claim 9. E Ψkl (S Ψkl (⃗s) else. Proof. In the following, assume that the VOG process chooses two agents on opinions i and j connected by an edge {i, j} in step t. It is easy to verify that if e(t) = {i, j}, with probability 12 an agent from i moves to ⃗ ′) = P ⃗′ j or vice versa. We will now examine the expected change of every summand of Ψ(S {k,l}∈E Ψkl (S ). ⃗ ′ ) for the edge {i, j} ∈ E with e(t) = {i, j}. First, we consider the summand Ψij (S i ⃗ ′ ) = 1 (si − 1)(sj + 1) + 1 (si + 1)(sj − 1) = si sj − 1. Ψij (S e(t)={i,j} 2 2 E

h

Second, we consider a summand Ψil (t) for edge {i, l} ∈ E with l ̸= j. Here, only opinion i is part of the active edge. Thus, the support of i increases or decreases by 1, whereas the support of l remains unchanged. Therefore, h i
⃗ ′ ) = 1 (si − 1)sl + (si + 1)sl = si sl . E Ψil (S e(t)={i,j} 2 For Ψkj (t) with k ̸= i, the calculation is equivalent. Finally, we consider Ψkl (t) for some edge {k, l} with {k, l} ∩ {i, j} = ∅. This potential is trivially unchanged as no endpoint changes its support. Now, we use the P law of total expectation and linearity of expectation to prove the lemma. We define ρ(t) := Pr [P(t) = 1] = {i,j}∈E Pr [e(t) = {i, j}] as the probability of an productive step. h i h i ⃗ ′ ) = (1 − ρ(t)) · Ψ(⃗s) + ρ(t)E Ψ(S ⃗ ′ ) P(t) = 1 . E Ψ(S

14

(7)

Now use the linearity of expectation to get   h i X X ⃗ ′) = E  ⃗ ′ ) = E Ψ(S Ψkl (S P(t)=1

P(t)=1

{k,l}∈E

 Pr [e(t) = {i, j}] 

{i,j}∈E

P(t)=1

X

{k,l}∈E

E

e(t)={i,j}

h

i



⃗ ′)  . Ψkl (S

h i ⃗ ′ ) e(t) = {i, j} for all {k, l}, {i, j} ∈ E: Next, we apply Claim 9 to bound each E Ψkl (S E

P(t)=1

h

i

⃗ ′) = Ψ(S

X {i,j}∈E



X

Pr [e(t) = {i, j}] Ψij (t) − 1 +

P(t)=1

= (Ψ(⃗s) − 1)

X {i,j}∈E

 Ψkl (⃗s)

{k,l}∈E\{{i,j}}

Pr [e(t) = {i, j}] = (Ψ(⃗s) − 1).

P(t)=1

Substituting this in Equation (7) allows to conclude h i ⃗ ′ ) = (1 − ρ(t))Ψ(⃗s) + (Ψ(⃗s) − 1)ρ(t) = Ψ(⃗s) − ρ(t) = Ψ(⃗s) − Pr [P(t) = 1] . E Ψ(S

3.2 Proof of Theorem 2 (Stabilization Time of the Ordinary Process) In this section, we prove Theorem 2. For the first statement, in addition to Proposition 1, we use the following multiplicative drift theorem [18, 32, 45] in the version by Lengler [36]. Theorem 10 (Theorem 2.3.11 in [36] (Based on [18, 32, 45])). Let (Xt )t≥0 be a sequence of non-negative random variables with a finite state space S ⊆ R+ 0 such that 0 ∈ S. Let smin := min(S \ {0}), let T := inf{t ≥ 0 | Xt = 0}, and for t ≥ 0 and s ∈ S let ∂(s) := E[Xt − Xt+1 | Xt = s]. Suppose there exists δ > 0 such that for all s ∈ S \ {0} and all t ≥ 0 the drift is ∂t (s) ≥ δs. Then, E [T ] ≤ 1+E[ln(Xδ 0 /smin )]] . The expected convergence time for the ordinary EdgeVOG process follows from using Theorem 10 to ⃗ ⃗ bound the time when Ψ(
S(t)) becomes 0. Note that Xt here becomes the value of our potential Ψ(S(t)). n This implies X0 ≤ 2 and smin = 1. The probability to make a productive step in the global process is
n 2 ⃗ ⃗ Ψ(S(t))/ 2 ≥ Ψ(S(t))/n . Note that, by the law of total expectation, Proposition 1 implies that for every value ψ ∈ [0, n(n − 1)] we have h i h i ⃗ + 1)) Ψ(S(t)) ⃗ ⃗ E Ψ(S(t = ψ = ψ − E P(t) Ψ(S(t)) =ψ . ⃗ Therefore, for a fixed value Ψ(S(t)) = ψ, Proposition 1 implies:   h i ψ 1 ⃗ ⃗ E Ψ(S(t + 1)) Ψ(S(t)) = ψ ≤ ψ − 2 ≤ ψ 1 − 2 . n n

(8)

Thus, we can use Theorem 10 with δ = n12 and obtain an expected convergence time of O(n2 log n).
For the high probability bound, we can use (arguably) even simpler observations. Write N = n2 . Since ⃗ the probability of a productive step is exactly Ψ(S(t))/N , the law of total expectation gives " #   h h i i ⃗ Ψ( S(t)) 1 ⃗ ⃗ ⃗ E Ψ(S(t + 1)) = E Ψ(S(t)) − = 1− E Ψ(S(t)) . N N An elementary induction and 1 − 1/N ≤ e−1/N therefore yield h i ⃗ E Ψ(S(t)) ≤ Ψ(⃗s0 )e−t/N ≤ n2 e−t/N . For any fixed c > 1, choosing t = ⌈(c + 2)N log n⌉ makes this expectation at most n−c . As the potential is a nonnegative integer and is positive exactly before stabilization, Markov’s inequality gives h i ⃗ Pr [T > t] = Pr Ψ(S(t)) ≥ 1 ≤ n−c . This proves the high-probability bound in Theorem 2. 15

3.3 Proof of Theorem 3 (Worst-Case Stabilization Time of the Productive Process) First, we note that the ordinary EdgeVOG process always requires as least as many steps as the productive EdgeVOG process
(as the latter simply ignores the non-productive steps). Hence, with high probability, it e n2 steps. Therefore, we will only prove the improved bound on the expected convergence also requires O time of the productive EdgeVOG process. For the proof, we use the following drift theorem. Theorem 11 (Theorem 2.3.1 in [36] (Based on [28])). Let (Xt )t≥0 be a sequence of non-negative random variables with a finite state space S ⊆ R+ 0 such that 0 ∈ S. Let T := inf{t ≥ 0 | Xt = 0}. Suppose that there exists δ > 0 such that for all s ∈ S \ {0} and for all t ≥ 0, we have ∂t (s) := E [Xt − Xt+1 | Xt = s] = δ. Then, 0] E [T ] = E[X δ . The original formulation in [36] is slightly more general. We simplified it for our purposes3 . That being ⃗ ⃗ said, consider the potential function Ψ(S(t)) and the convergence time T := min{t ≥ 0 : Ψ(S(t)) = 0}. Our goal is to bound E [T ] using Theorem 11. Towards this end, we bound the term h i ⃗ ⃗ + 1)) Ψ(S(t)) ⃗ ∂t (s) := E Ψ(S(t)) − Ψ(S(t =s for all possible values s > 0. Note that the productive EdgeVOG process picks exactly one pair of agents per step as long as there are productive pairs and none otherwise. This means that we canhapply Proposition i 1 ⃗ to bound the change in potential. The lemma states that the potential decreases by E P(t) S(t) = ⃗s in expectation where P(t) is a random variable which equals 1 if step t is productive. Clearly, as long as there ⃗ areh productive pairs, we i have Ψ(S(t)) > 0. Thus, the probability of a productive step is 1, which means ⃗ E P(t) | Ψ(S(t)) > 0 = 1. Therefore, by Proposition 1 it holds for all s > 0 that h i h i ⃗ ⃗ + 1)) | Ψ(S(t)) ⃗ ⃗ + 1)) | Ψ(S(t)) ⃗ ∂t (s) = E Ψ(S(t)) − Ψ(S(t = s = s − E Ψ(S(t =s  h i ⃗ = s − s − E P(t) Ψ(S(t)) = s = s − (s − 1) = 1.

(9)

Thus, we have δ = 1 for all s > 0, so Theorem 11 yields an expected convergence time of E [T ] = Ψ(⃗s0 ) = |P (0)|, and the proposition follows. Consider a star graph of n opinions/nodes, with one agent holding each opinion. This configuration has n − 1 productive pairs. The process stabilizes precisely when the support of the center opinion reaches 0 or n. In each step, exactly one agent either adopts or abandons the center opinion, with both events occurring with equal probability. Consequently, the support of the center evolves as a one-dimensional random walk with absorbing barriers at 0 and n. By Lemma 36, the process requires Ω(n2 ) steps with probability Ω(1/n).

3.4 Proof of Theorem 4 (Parameterized Stabilization Time of the Productive Process) Before we start with the proof, we begin with some helpful definitions and observations. For the proof, write Ŝ = Ŝa (G, ⃗s0 ) for a sufficiently large fixed failure exponent a, and let b := ∆Ŝ. If the initial configuration is already stable, there is nothing to prove. Otherwise, ∆ ≥ 1 and b ≥ 1. Let τsupp := inf{t ≥ 0 : max Si (t) > Ŝ}, i∈O

T̃ := T ∧ τsupp .

  By definition of Ŝ, Pr τsupp < ∞ ≤ n−a . Rather than conditioning on the event that the support cap is never exceeded, we use the stopped potential ⃗ ⃗ ∧ τsupp )). := Ψ(S(t Ψ̃(S(t)) Thus, Ψ̃ freezes at the first support violation, while T̃ is the first time when the process either stabilizes or violates the cap. The original process and the stopped process agree until T̃ . Hence, a high-probability bound for T̃ gives the same bound for T after adding at most n−a to the failure probability. 3

Lengler also gives specific bounds when only an upper or lower bound of δ is known. However, as we can compute the exact value, we omitted these cases here.

16

The remaining section is structured as follows. On a high level, the proof proceeds in two phases, depending on whether the potential is large or small. In Lemma 12 we first establish an auxiliary result that is used in both phases. It shows that, for short time horizons, the potential grows at most by a small constant factor. Using this tool, we distinguish two phases. Let c ≥ 1 be a constant that will be fixed in the analysis. In the first ⃗ phase where Ψ̃(S(t)) ≥ 32c·∆4 ·b2 log2 n, we show that the potential decreases rapidly. Proposition 13 proves that within O(Ψ̃(⃗s0 )+b2 log3 n) steps the potential drops to 32c·∆4 ·b2 log2 n with high probability. The proof is based on a layered induction argument that partitions time into phases. In each phase, a constant fraction ⃗ of the remaining productive edges is eliminated. In the second case, once Ψ̃(S(t)) ≤ 32c · ∆4 · b2 log2 n, the argument no longer applies as there too few opinions left. Instead, Proposition 16 shows that in this regime the process converges within O(∆4 · b2 log3 n) additional steps with high probability. Combining both cases yields the desired convergence bound for the productive EdgeVOG process. That being said, we begin with a technical result that we need for either case: We show that the productive edges are highly concentrated if we do not observe the process for too long. Lemma 12. Let K = Ψ(⃗s0 ) + b2 log2 n. Then, for every r ≥ 1 and integer τ ≤ r2 K log n,   3/2 ⃗ Pr max Ψ̃(S(u)) > Ψ(⃗s0 ) + 8r K ≤ n−r . 0≤u≤τ

The lemma follows from the maximal upper-tail version of Azuma’s inequality (see Theorem 31) and the fact that the stepwise change of the stopped potential is bounded by 2b. ⃗ Proof. Note that (Ψ̃(S(t))) t≥0 is a supermartingale, since it is obtained by stopping the original potential at τsupp . Next, consider its stepwise difference before τsupp . W.l.o.g. let i receive an agent and let j lose an agent in step t. A direct calculation gives X X ⃗ + 1)) − Ψ(S(t)) ⃗ Ψ(S(t = Sh (t) − Sh (t) − 1. h∈Ni

h∈Nj

Since every support before this interaction is at most Ŝ, ⃗ + 1)) − Ψ̃(S(t))| ⃗ |Ψ̃(S(t ≤ ∆Ŝ + 1 ≤ 2b. This also holds for the interaction that first violates the support cap, since the bound uses the configuration before that interaction. After τsupp , the difference is zero. Thus, for τ ≥ 1, maximal Azuma gives !     (8r3/2 K)2 8rK 3/2 ⃗ Pr max Ψ̃(S(u)) > Ψ(⃗s0 ) + 8r K ≤ exp − ≤ exp − 2 ≤ n−8r ≤ n−r . 0≤u≤τ 2τ (2b)2 b log n For τ = 0, the assertion is immediate. This proves the lemma. Equipped with this lemma, we now distinguish between the two cases mentioned earlier. ⃗ (Case 1) Ψ(S(t)) ≥ 32c · ∆4 · b2 log2 n In this first part, we consider only configuration with sufficiently large potentials. We show that the potential rapidly decreases from its initial value of Ψ(⃗s0 ) to 32c · ∆4 · b2 · log2 n within O(Ψ(⃗s0 ) + b2 log3 n) steps, w.h.p. Formally, we show that the following holds: Proposition 13. For any fixed c > 3, the productive EdgeVOG process reaches a configuration with potential at most 32c∆4 b2 log2 n within Oc (Ψ(⃗s0 ) + b2 log3 n) steps w.h.p. The proof uses a layered induction. We partition the execution into O(log n) phases where phase i is s0 ) of length at most O( Ψ(⃗ + b2 log2 n) w.h.p. In other words, w.h.p., the durations decrease geometrically 2i (except for an additive term). For each phase, we show that enough productive interactions occur to eliminate at least half of the remaining productive edges with high probability (as long as the potential is at least 17

32c · ∆4 · b2 log2 n). Iterating this argument over O(log n) phases yields an exponential decay in the potential until it reaches 32c · ∆4 · b2 log2 n. Since, w.h.p., the phase lengths form a geometric sequence that sums to O(Ψ(⃗s0 ) + b2 log3 n), we conclude that the potential has fallen to 32c · ∆4 · b2 log2 n, as claimed. To prove this statement, we require an auxiliary technical result. First, we show that the potentials of 4-separated sets satisfy a suitable product bound. For B ≥ 1, define ⃗ τB := inf{t ≥ 0 : Ψ(S(t)) > B} and the auxiliary node potentials

(

(B) Ψ̂i (t) =

⃗ Ψi (S(t)), 0,

if t < τsupp ∧ τB , otherwise.

P (B) ⃗ Let Ψ̂(B) (t) = 21 i∈O Ψ̂i (t). As long as neither cap has been violated, Ψ̂(B) (t) = Ψ(S(t)). After a violation, all auxiliary node potentials remain zero. Unlike the stopped potential Ψ̃, these auxiliary potentials are killed at a support violation, so a positive frozen value cannot prevent their decay. Given this useful definition, we show Lemma 14. Consider an opinion graph G = (O, E) and threshold B ≥ 1. Further, let I ⊂ O be an arbitrary 4-separated set in G. For each t ≥ 1 define Y (B) (B) ⃗ Ψ̂i (S(t)). ΦI (t) = i∈I

Then, for all t ≥ 0, it holds:

h i Y
(B) E ΦI (t) ≤ Ψi (⃗s0 ) · (1 − B1 )t . i∈I

The proof is by induction over the time steps. Before a cap violation, at most one of the selected node potentials can change in an interaction. Killing all factors at a cap violation can only decrease their nonnegative product. Proof. As B and I are fixed, we omit them from the notation where possible. The base case t = 0 is immediate. If either cap has already been violated, all auxiliary potentials are zero and the upper bound holds trivially. For the induction step, condition on the full history F(t) and suppose that the auxiliary product is positive. ⃗ In particular, neither cap has been violated, and every opinion in I is undecided. Write ψ = Ψ(S(t)) ≤ B. First ignore the killing that may occur in step t. Since I is 4-separated, the selected edge can affect at most one node potential in the product. By Claim 9, Ψi decreases by one in expectation conditional on an interaction involving i, and does not change in expectation for all other interactions. The probability that i is ⃗ productive is Ψi (S(t))/ψ. Therefore, #  " Y Y ⃗ ⃗ + 1)) | F (t) = 1 − |I| Ψi (S(t)). E Ψi (S(t (10) ψ i∈I

i∈I

If a cap is violated in this interaction, the auxiliary product is set to zero, which only decreases it. Moreover, when the product is positive, the incident edge sets of the opinions in I are disjoint and each has positive integer potential. Hence, |I| ≤ ψ ≤ B. Using Bernoulli’s inequality, we obtain    h i  1 |I| (B) |I| (B) (B) ΦI (t) ≤ 1 − ΦI (t). E ΦI (t + 1) | F (t) ≤ 1 − B B If the current product is zero, it remains zero: either a cap was violated or one of its opinions is already decided. Thus, the same inequality holds in that case. Taking expectations and iterating gives  h i  1 t|I| Y (B) E ΦI (t) ≤ 1 − Ψi (⃗s0 ), B i∈I

which proves the lemma. For the empty set, both products are one.

18

The second auxiliary result lets bound the decrease in potential. ⃗ Lemma 15. Consider the productive EdgeVOG process at a time t < T̃ , and write ψ = Ψ(S(t)). For every fixed c ≥ 1, start a phase at time t and end it when the potential first falls to at most max{ψ/2, 32c∆4 b2 log2 n} (or when the support bound is violated). Conditional on F(t), the phase lasts O(c · ψ + b2 log2 n) steps with probability at least 1 − n−c . Proof. We begin by introducing some notation and simplifying conventions. Condition on the history up to time t, and shift the time index so that this configuration is at time zero. Write ⃗s0 for this configuration and ψ = Ψ(⃗s0 ). For the fixed constant c ≥ 1, let K = ψ + b2 log2 n,

r = 104 (c + 1)2 ,

τ = ⌈B log(32c)⌉.

B = (8r3/2 + 1)K,

These choices give τ ∈ Oc (K) and τ ≤ r2 K log n for n ≥ 2. The caps and auxiliary potentials are restarted at the beginning of the phase, using the same support threshold Ŝ. Partition O into 4-separated sets I1 , . . . , Ik by properly coloring the graph joining opinions at distance at most three. The radius-three ball bound gives k ≤ min{q, 2∆3 } ≤ min{n, 2∆4 }. P P (B) (B) For each such set I, write Ψ̂I (u) = i∈I Ψ̂i (u) and ψI = i∈I Ψi (⃗s0 ). We first show that i h (B) Pr Ψ̂I (τ ) ≥ ψI /4 + 8cb2 log n ≤ n−8c .

(11)

By Lemma 14, for every subset I ′ ⊆ I, " #   ′ Y Y (B) 1 τ |I | Y ′ Ψi (⃗s0 ) ≤ (32c)−|I | Ψi (⃗s0 ). E Ψ̂i (τ ) ≤ 1 − B ′ ′ ′ i∈I

i∈I

i∈I

Every auxiliary node potential lies in [0, b2 ], because before killing its value is at most ∆Ŝ 2 ≤ b2 . Thus, Theorem 35 applies with upper bound b2 , p = 1/(32c), xi = Ψi (⃗s0 ), and µ = ψI /(32c). If µ = 0, all the relevant auxiliary potentials vanish almost surely. Otherwise, set aI = ψI /4 + 8cb2 log n,

δ = aI /µ.

Then δ ≥ 8c ≥ e2 , and consequently h i 2 (B) Pr Ψ̂I (τ ) ≥ aI ≤ e−aI /b ≤ n−8c . This proves (11) without any lower bound on ψI or |I|. Taking a union bound over the at most n color classes, with failure probability at most n1−8c , gives 1 X (B) 1 Ψ̂Ij (τ ) ≤ Ψ(⃗s0 ) + 4ckb2 log n 2 4 k

Ψ̂(B) (τ ) =

j=1

ψ ψ ≤ + 8c∆4 b2 log n ≤ + 16c∆4 b2 log2 n ≤ max{ψ/2, 32c∆4 b2 log2 n}. 4 4 Here, we used log n ≥ log 2 > 1/2. By Lemma 12, the stopped potential exceeds B during the first τ steps with probability at most n−r . Suppose that the stopped potential has not crossed B during these steps. If the support bound has been ⃗ )), so the preceding bound violated by time τ , the phase has already ended. Otherwise, Ψ̂(B) (τ ) = Ψ(S(τ on the auxiliary potential implies that the phase has ended by time τ as well. The total failure probability is therefore at most n1−8c + n−r ≤ n−c . This proves the induction step. Equipped with lemma, we can now proceed to the proof of Proposition 13. 19

Proof of Proposition 13. We need a final set of definitions. Fix c > 3 and let H = 32c∆4 b2 log2 n. If Ψ(⃗s0 ) ≤ H, the assertion is immediate. Otherwise, let   Ψ(⃗s0 ) L = log2 , hj = max{Ψ(⃗s0 )/2j , H}, 0 ≤ j ≤ L. H Set τ0 = 0. For j ≥ 1, let τj be the first time at or after τj−1 at which either T̃ has been reached or the potential is at most hj . On a phase that starts before T̃ , Lemma 15, conditional on its starting history, implies τj − τj−1 ∈ Oc (hj−1 + b2 log2 n) with probability at least 1 − n−c . If the process has already stopped, the phase has length zero. Since L ∈ O(log n), the union bound shows that all phases satisfy these bounds w.h.p. On this event, τL ≤

L X j=1

 Oc

Ψ(⃗s0 ) + b2 log2 n 2j−1



= Oc Ψ(⃗s0 ) + b2 log3 n .

At this time, either T̃ has been reached or the potential has fallen to H. A support violation occurs with probability at most n−a , so the same conclusion holds for the original process w.h.p.

⃗ Case 2: Ψ(S(t)) ≤ 32c · ∆4 · b2 log2 n. For the last part of the analysis, we consider the process starting at configurations with a potential of at most 32c∆4 b2 log2 n. In this case, our layered induction argument falls apart as only few active opinions are left. Instead, we argue that w.h.p. the process converges after O(∆4 b2 log3 n) additional steps. Proposition 16. Suppose Ψ(⃗s0 ) ≤ 32c∆4 b2 log2 n for a fixed c ≥ 1. Then, T̃ ∈ Oc (∆4 b2 log3 n) w.h.p. Hence, the original productive process satisfies the same bound when the probability of a support violation is added to the failure probability. Proof. We introduce some notation and simplifying conventions. For the fixed c ≥ 1, let K = Ψ(⃗s0 ) + b2 log2 n,

r = 104 (c + 1)2 ,

B = (8r3/2 + 1)K,

τ = ⌈B(c + 4) log n⌉.

Then τ ∈ Oc (K log n) and τ ≤ r2 K log n. Applying Lemma 14 to singleton sets and summing yields   h i 1 τ (B) E Ψ̂ (τ ) ≤ Ψ(⃗s0 ) 1 − ≤ n2 e−τ /B ≤ n−(c+2) . B The auxiliary global potential is either the integer-valued original potential or zero. Thus, Markov’s inequality gives h i Pr Ψ̂(B) (τ ) ≥ 1 ≤ n−(c+2) . By the maximal estimate in Lemma 12, the stopped potential exceeds B during this interval with probability at most n−r . On the event {T̃ > τ }, if no such crossing occurs, the auxiliary and original potentials agree and are positive at time τ . Consequently, i h Pr T̃ > τ ≤ n−(c+2) + n−r ≤ n−c . Since K ∈ Oc (∆4 b2 log2 n) under the assumption of the proposition, this proves the claim. The same calculation, without the small-potential assumption, gives T̃ ∈ Oc ((Ψ(⃗s0 ) + b2 log2 n) log n) w.h.p., which proves the first bound in Theorem 4. For the second bound, apply Proposition 13 first and start the present argument at the first time the potential is at most 32c∆4 b2 log2 n. All estimates hold conditional on that starting history before a support violation. Adding the original failure probability n−a once gives
T ∈ Oc Ψ(⃗s0 ) + ∆4 b2 log3 n w.h.p. Substituting b = ∆Ŝ proves the second bound.

20

3.5 Proof of Theorem 5 (Survival of a Fixed Opinion) In this section, we show Theorem 5. Let G = (O, E) be the opinion graph and let si ≥ 1 denote the initial support of opinion i ∈ O. Let Xi := 1{Si (T )>0} indicate whether opinion i is present in the stable configuration, then E [Xi ] ≥

si +

s Pi

j∈Ni sj

.

The proof of the theorem follows from the following two lemmas. The first identifies the terminal value of Ri (t), while the second establishes the required submartingale property. Lemma 17. For every opinion i, we have Ri (T ) = Xi almost surely. Proof. Recall that τi is the first time at which either Si (t) = 0 or Mi (t) = 0. If Si (τi ) = 0, then opinion i is extinct and cannot reappear, since an opinion can only be copied from an agent that currently holds it. Hence, Xi = 0. Otherwise, Mi (τi ) = 0 and Si (τi ) > 0. In this case, no opinion in Ni is present. Since these opinions are extinct and cannot reappear, opinion i can no longer participate in a productive interaction and therefore survives. Hence, Xi = 1. Consequently, ( 0, if Si (τi ) = 0, Ri (τi ) = = Xi . 1, if Mi (τi ) = 0 and Si (τi ) > 0, At the stabilization time T , every opinion is either extinct or has no surviving neighboring opinion. Thus, τi ≤ T almost surely. Since Ri (t) is stopped at τi , it follows that Ri (T ) = Ri (τi ) = Xi . Lemma 18. For every opinion i, the process (Ri (t))t≥0 is a bounded submartingale with respect to the natural filtration (F(t))t≥0 . Proof. By definition, 0 ≤ Ri (t) ≤ 1 for every t ≥ 0, so the process is bounded. Moreover, on the event {τi ≤ t}, the process has already been stopped, and therefore Ri (t + 1) = Ri (t). We may thus fix a time t and work on the event {t < τi }. In particular, Si (t), Mi (t) ≥ 1. For convenience, let Li (t) := Si (t) + Mi (t) and note that Li (t) ≥ 2. It suffices to consider productive interactions, since all other interactions leave the support vector, and hence Ri (t), unchanged. For convenience, write e(t) = ⊥ if the selected interaction is not productive. Conditional on a productive edge being activated, either endpoint copies the other with probability 1/2. We distinguish three cases. 1. Suppose that the activated edge is e(t) = {i, j} for some j ∈ Ni . The pair (Si (t), Mi (t)) then changes to either (Si (t) + 1, Mi (t) − 1) or (Si (t) − 1, Mi (t) + 1), each with probability 1/2. In both cases, Li (t) remains unchanged. Therefore, Si (t) + 1 Si (t) − 1 1 1 + 2 Si (t) + 1 + Mi (t) − 1 2 Si (t) − 1 + Mi (t) + 1 Si (t) = Ri (t). = Si (t) + Mi (t)

E [Ri (t + 1) | F (t), e(t) = {i, j}] =

2. Suppose that the activated edge is e(t) = {j, k}, where j ∈ Ni and k ∈ / Ni ∪ {i}. In this case, Si (t) remains unchanged, while Mi (t), and hence Li (t), increases or decreases by one with equal probability. It follows that   Si (t) 1 Si (t)Li (t) 1 E [Ri (t + 1) | F (t), e(t) = {j, k}] = = + 2 Li (t) − 1 Li (t) + 1 Li (t)2 − 1 Si (t) Si (t) S (t)
≥ i = + = Ri (t). 2 Li (t) Li (t) Li (t) − 1 Li (t) 21

3. Finally, suppose that both endpoints of the activated edge belong to Ni . Although the interaction may redistribute support between these two opinions, it does not change their total support and hence leaves Mi (t) unchanged. An interaction whose endpoints both lie outside Ni ∪{i} also leaves Si (t) and Mi (t) unchanged. In either case, Ri (t + 1) = Ri (t). Thus, conditional on F(t) and on any possible interaction, the expected value of Ri (t+1) is at least Ri (t). By the law of total expectation, X E [Ri (t + 1) | F (t)] = Pr [e(t) = e | F (t)] E [Ri (t + 1) | F (t), e(t) = e] e∈E∪{⊥}

≥

X

Pr [e(t) = e | F (t)] Ri (t) = Ri (t).

e∈E∪{⊥}

Therefore, (Ri (t))t≥0 is a bounded submartingale. We can now complete the proof of the theorem. Since T < ∞ almost surely and (Ri (t))t≥0 is bounded, Doob’s Optional Stopping Theorem applies directly. Together with Lemmas 17 and 18, this yields Pr [Xi = 1] = E [Xi ] = E [Ri (T )] ≥ Ri (0). Finally, by the definition of Ri , we have X

Ri (0) = Si (0)/(Si (0) + Mi (0)) = si /(si +

s j ) = pi ,

j∈Ni

which proves the theorem.

3.6 Proof of Theorem 6 (Number of Surviving Opinions) For the proof of the theorem, we need two main ingredients. First, we show that the non-survival events of opinions at pairwise distance at least three satisfy a suitable negative product condition. Lemma Q 19. Let I
⊆ O be a set of opinions at pairwise distance at least three in G, and let Qi (t) := 1 − Ri (t). Then i∈I Qi (t) t≥0 is a supermartingale. The proof of this lemma is based on elementary but somewhat lengthy one-step calculations, and we postpone it until the end of this section. Our second ingredient is a variant of the Chernoff bound for random variables whose dependencies are described by a graph. In the standard setting, two variables may be dependent only if their corresponding vertices are adjacent. Consequently, the variables indexed by an independent set are mutually independent. The chromatic number χ(H) is the smallest number of colors needed to color H such that adjacent vertices receive different colors. Equivalently, it is the smallest number of independent sets into which the vertices of H can be partitioned. Applying the Chernoff argument separately to these color classes leads to a loss of a factor χ(H) in the exponent; see, for example, [31]. More precisely, we show Theorem 20. Let X1 , . . . , Xq ∈ 0, 1 be binaryPrandom variables, P let p1 , . . . , pq ∈ [0, 1], and let H be an undirected graph on [q]. Furthermore, let Z := qi=1 Xi , µ := qi=1 pi , and κ := χ(H). Suppose that, for every independent set I of H, " # Y Y E (12) (1 − Xi ) ≤ (1 − pi ). i∈I

i∈I

Then, for every 0 ≤ δ ≤ 1, 

δ2µ Pr [Z ≤ (1 − δ)µ] ≤ exp − 2κ

22

 .

The proof follows the standard argument for dependency graphs almost verbatim. In that argument, the vertices are partitioned into κ color classes, each of which is an independent set of H. Independence within a color class is used only to factor the relevant expectation into a product. In our setting, this step is replaced by the assumption in (12). We can now derive the theorem from these two statements. We apply Theorem 20 with H = G2 , the second power of G. Recall that two distinct opinions are adjacent in G2 if their distance in G is at most two. Thus, a set is independent in G2 if and only if its opinions have pairwise distance at least three in G. It therefore remains to verify (12) for every such set. More precisely, we need to show that, for every set I ⊆ O whose opinions have pairwise distance at least three, # " Y Y (1 − Xi ) ≤ (1 − pi ). (13) E i∈I

i∈I

Lemma 19 comes into play. Fix such a set I and consider the bounded supermartingale
Q This is where i∈I Qi (t) t≥0 . Recall that Qi (T ) = 1 − Xi for every i ∈ O, where T denotes the stabilization time of the process. Applying the Optional Stopping Theorem to T ∧ t and then letting t → ∞, using bounded convergence, gives " E

Y

#

"

(1 − Xi ) = E

i∈I

≤

Y

Y

# Qi (T )

i∈I

Qi (0) =

i∈I

Y

(1 − pi ).

(14)

i∈I

Thus, the variables Xi satisfy the local product assumption (12) with respect to G2 , and the theorem follows. It remains to prove Lemma 19. Proof. Fix t ≥ 0. If the process has already stabilized, the product remains constant and there is nothing to prove. Otherwise, condition on F(t) and on the unordered opinion edge e(t) activated in step t. To prove that the product process is a supermartingale, we must show that, for every possible choice of e(t),   Y Y E  Qj (t + 1) F(t), e(t) − (15) Qj (t) ≤ 0. j∈I

j∈I

If Qi (t) = 0 for some stopped i ∈ I, then the product remains zero forever and there is nothing to prove. A stopped factor with value 1 can be removed from the product. Hence, we may assume that all ratios considered below are active. Since the opinions in I have pairwise distance at least three, their closed neighborhoods are pairwise disjoint. Consequently, an opinion edge can affect at most two of the ratios. Up to exchanging the endpoints of e(t), we distinguish the following cases. 1. e(t) = {i, k} for some i ∈ I and k ∈ Ni . Among the quantities entering Qi (t), only Si (t) changes, while Li (t) remains unchanged. Therefore,  E

Y j∈I

=

 Qj (t + 1) F(t), e(t) − Y

=

j∈I\{i}

=

Y

Qj (t)

j∈I

Qj (t) · E [Qi (t + 1) | F (t), e(t)] −

j∈I\{i}

Y

Y

 Qj (t)

Y

Qj (t)

j∈I

1 Li (t) − Si (t) + 1 1 Li (t) − Si (t) − 1 + − Qi (t) 2 Li (t) 2 Li (t)

Qj (t) (Qi (t) − Qi (t)) = 0.

j∈I\{i}

23



2. e(t) = {k, ℓ} for some i ∈ I with k ∈ Ni and ℓ ∈ /

S

j∈I (Nj ∪ {j}).

In this case, Si (t) remains unchanged, while Li (t) becomes either Li (t) − 1 or Li (t) + 1, each with probability 1/2. Since the ratio is active, we have Li (t) ≥ 2. Hence,  E

Y j∈I

=

 Qj (t + 1) F(t), e(t) − Y

Y

Qj (t)

j∈I

Qj (t) · E [Qi (t + 1) | F (t), e(t)] −

j∈I\{i}

Y

Y

Qj (t)

j∈I



1 Li (t) − 1 − Si (t) 1 Li (t) + 1 − Si (t) + − Qi (t) = Qj (t) 2 Li (t) − 1 2 Li (t) + 1 j∈I\{i}   Y Li (t)Si (t) = Qj (t) 1 − − Qi (t) Li (t)2 − 1 j∈I\{i}  −1 ! Y 1 = Qj (t) Ri (t) − Ri (t) 1 − Li (t)2



j∈I\{i}

=−

Y

Qj (t)

j∈I\{i}

Ri (t) ≤ 0. Li (t)2 − 1

3. e(t) = {k, ℓ} for distinct i, j ∈ I with k ∈ Ni and ℓ ∈ Nj . This case can only occur when distG (i, j) = 3. First, we rewrite the term. Using the product-increment identity Qi (t + 1)Qj (t + 1) − Qi (t)Qj (t)

= Qi (t) Qj (t + 1) − Qj (t) + Qj (t) Qi (t + 1) − Qi (t)

+ Qi (t + 1) − Qi (t) Qj (t + 1) − Qj (t) , and using that Qi (t) and Qj (t) are F(t)-measurable, we obtain E [Qi (t + 1)Qj (t + 1) | F (t), e(t)] − Qi (t)Qj (t) = Qi (t) (E [Qj (t + 1) | F (t), e(t)] − Qj (t)) + Qj (t) (E [Qi (t + 1) | F (t), e(t)] − Qi (t)) 

 + E Qi (t + 1) − Qi (t) Qj (t + 1) − Qj (t) F(t), e(t) . We now show that each of the three summands is non-positive. The first two terms are non-positive by the calculations from the previous case. Indeed, E [Qi (t + 1) | F (t), e(t)] − Qi (t)   Li (t) − Si (t) 1 Li (t) − 1 − Si (t) Li (t) + 1 − Si (t) − = + ≤ 0. 2 Li (t) − 1 Li (t) + 1 Li (t) The same holds analogously for j. It remains to consider the last term. Define ιij ∈ {−1, 1} as the direction of the interaction, where ιij = 1 if an agent moves from ℓ ∈ Nj to k ∈ Ni , and ιij = −1 otherwise. Thus, Lj (t + 1) = Lj (t) − ιij .

Li (t + 1) = Li (t) + ιij , 24

Consequently, 

   Si (t) Si (t) Qi (t + 1) − Qi (t) = 1 − − 1− Li (t) + ιij Li (t) ιij Si (t) = , Li (t)(Li (t) + ιij ) and, analogously,    Sj (t) Sj (t) − 1− Lj (t) − ιij Lj (t) ιij Sj (t) =− . Lj (t)(Lj (t) − ιij ) 

Qj (t + 1) − Qj (t) =

1−

Therefore,

Qij (t) := Qi (t + 1) − Qi (t) Qj (t + 1) − Qj (t) Si (t)Sj (t) . =− Li (t)(Li (t) + ιij )Lj (t)(Lj (t) − ιij ) Since both outcomes of ιij are equally likely, E [Qij (t) | F (t), e(t)]   Si (t)Sj (t) Si (t)Sj (t) 1 = − − 2 Li (t)Lj (t)(Li (t) − 1)(Lj (t) + 1) Li (t)Lj (t)(Li (t) + 1)(Lj (t) − 1)   Si (t)Sj (t) 1 1 =− + ≤ 0. 2Li (t)Lj (t) (Li (t) − 1)(Lj (t) + 1) (Li (t) + 1)(Lj (t) − 1) Finally, all other factors remain unchanged, and hence " E

Y

# Qh (t + 1) F(t), e(t) −

h∈I

Y

=

Y

Qh (t)

h∈I

Qh (t) (E [Qi (t + 1)Qj (t + 1) | F (t), e(t)] − Qi (t)Qj (t)) ≤ 0.

h∈I\{i,j}

4. In all remaining cases, e(t) does not change any Qi (t) with i ∈ I, and hence " # Y Y E Qi (t + 1) F(t), e(t) − Qi (t) = 0. i∈I

i∈I

For an idle step, e(t) = ⊥ and the product remains unchanged. Since the conditional drift is non-positive for every possible choice of e(t), the law of total expectation gives " E

Y

# Qi (t + 1) F(t)

i∈I

=

X

" Pr [e(t) = e | F (t)] E

i∈I

e∈E∪{⊥}

≤

Y

Y

Qi (t),

i∈I

which proves the lemma. 25

# Qi (t + 1) F(t), e(t) = e

3.7 Proof of Theorem 7 (Maximal Support on Cycle Graphs) We first explain the analysis approach of our main results in Theorem 8 for a simple cycle graph and a fixed starting configuration. This serves as a compact illustration and a warm-up for the complete technical analysis for bounded degree graphs in Section 3.8 below. In this section, we consider the productive EdgeVOG process on Gr = (Or , Er ) with Or = {1, ..., m} and {i, j} ∈ Er whenever j = 1 + (i mod m) for all i ∈ Or . There are n agents, where the initial support of each opinion i ∈ Or is 1, i.e., n = m and |Si (0)| = 1 for all i. In the following, we adopt the random walk-based view of the process where the agents are assigned to the node of the opinion graph corresponding to the opinion they have. On a high level, the main argument for the cycle graph is as follows. Suppose that, at some point, a large number of agents is assigned to a specific node i ∈ O. Now consider one of these agents and assume that the agent followed the path p to i. It is easy to see that each node on p was active at least twice (once in the step that i entered the node and once in the step that i left the node). However, as we will see later, each node is, on average, active only rarely before being decided. Hence it is unlikely that there are many long paths crossing node i. Fix an opinion i ∈ O and a constant c ≥ 1, and let d := ⌈2(c + 2) log2 n⌉. If 2d + 1 ≥ n, the desired bound follows directly from Si (t) ≤ n. Otherwise, let Cd be the path consisting of i and the d closest opinions on either side of i in the cycle. Initially, this path contains exactly 2d + 1 agents. Thus, if i ever has more than 2d + 1 agents, at least one of them must have started outside Cd . Such an agent must traverse one of the two paths of d opinions leading to i. Each of these d opinions is involved in at least two productive interactions: one in which the agent enters and one in which it leaves. In the following, we focus, w.l.o.g., on the left path. Choose a fixed independent set I of at least d/2 opinions on this path. For each j ∈ I, consider its first productive interaction, if such an interaction occurs. Since Sj (0) = 1 and j has not previously been productive, its support immediately before this interaction is still one. With probability 1/2, its sole agent leaves, so j becomes extinct and can never be productive again. Consequently, if j is productive at least twice, its first productive interaction must increase its support. To account for the dependence between the opinions, assign an independent fair coin to each j ∈ I and use this coin to choose the direction of its first productive interaction. Since I is independent, an interaction involves at most one opinion in I, so this gives exactly the original process. The remaining interactions use fresh fair coins. If a first interaction never occurs, its assigned coin is simply unused. Thus, traversing the path requires a prescribed outcome of every coin assigned to I, and its probability is at most 2−|I| ≤ 2−d/2 . The same argument holds for the right path. Applying the union bound over both directions and all n opinions gives Pr [∃i ∈ O, t ≥ 0 : Si (t) > 2d + 1] ≤ 2n · 2−d/2 ≤ 2n−(c+1) ≤ n−c . As d ∈ O(log n), this proves the bound simultaneously for all opinions and all time steps. The ordinary process visits the same configurations after idle steps are removed, so the result also holds for that process.

3.8 Proof of Theorem 8 (Maximal Support on Bounded Degree Graphs) In this section we prove Theorem 8. It bounds the maximal support of an opinion as a function of the maximal initial support and the maximal degree in the opinion graph. In particular, we show the following more detailed theorem Theorem 21. Let G = (O, E) be an arbitrary graph with maximum degree at most ∆, where ∆ ≥ 1. Suppose ŝ is the maximal initial support. For both the EdgeVOG and the productive EdgeVOG processes, with high
probability every opinion has support at most O min{n, ∆6 ŝ log2 n, ∆9 ŝ2 log n} simultaneously for all steps t ≥ 0. Proof overview: We generalize the arguments for the cycle in Section 3.7 above. For a given opinion i ∈ O we want to bound the subset of opinions whose agents might end up on i in the final configuration. We need a more general notion than the O(log n)-neighborhood, since it may already contain all opinions and agents. Moreover, multiple agents may start on the same opinion, and therefore each such opinion is expected to be productive more than once before becoming decided. 26

Instead, our main tool for the analysis are witness sets defined as follows: For each opinion i ∈ O, time t ≥ 0, and threshold τ ≥ 0, the witness set Wiτ (t) (cf. Definition 22 below) is the largest connected subgraph containing i in which every opinion has been productive at least τ times by time t. Thus, the witness set depends on both the topology of the opinion graph and the configuration √ in step t. We furthermore assign each witness a weight proportional to its size, scaled by ŝ + min{∆τ, ∆τ log n} (cf. Definition 23 below). This weight gives a coarse upper bound on how many agents Wiτ (t) can contain in step t. The proof proceeds in two steps: First, in Proposition 24, we show that bounding the weight of Wiτ (t) directly bounds the support Si (t), w.h.p. As the weight depends on the parameter τ and the corresponding size |Wiτ (t)|, we need to argue that there is a small τ where the witness sets remain small with high probability. We will show this in Proposition 26. The main complication in proving the propositon is that productive steps of neighboring opinions are strongly correlated. For example, if a given opinion was productive τ times, then, in total, all its neighbors must also have been productive τ times. Thus, there is a positive correlation between productive events of adjacent opinions. To deal with this dependence, in Lemma 27, we show that productive steps of opinions at distance at least four behave independently for the purpose of tail bounds We then use this insight in Proposition 26 to prove that for τ ′ = 100∆5 ŝ2 , witness sets cannot grow larger than O(∆3 log n) with high probability. Together with Proposition 24, this implies the desired bound on Si (t), completing the proof. Let us start with a formal definition of the witness sets. For each opinion i and each step t, we define Pi (↑ t) as the number of productive interactions involving i in steps 0, . . . , t − 1. Thus, Pi (↑ 0) = 0, and these counts refer to the configuration at the beginning of step t. Fix a node i ∈ V , a step t ≥ 0 and a parameter τ ≥ 1. Then, we define the τ -witness Wiτ (t) of i in step t as the largest connected subset containing i in which every node experiences at least τ productive steps until step t. Definition 22 (τ -Witness). Let i ∈ V be an arbitrary opinion and let t ≥ 0 be a step. For any integer τ ≥ 0, we define the set Oτ (t) = {j ∈ O | Pj (↑ t) ≥ τ } and let Gτ (t) be the subgraph induced by Oτ (t). Then, define the unique τ -witness Wiτ (t) ⊂ O of i as the connected component containing i in Gτ (t) if i ∈ Oτ (t) and {i} otherwise. Observe that for different choices of τ , we obtain widely different witness sets in the same configuration. Furthermore, we define the weight of a witness set. Definition 23 (Weight of a τ -Witness). Suppose EdgeVOG starts in a configuration with maximum support ŝ. Then, for a fixed c ≥ 1, we define the weight of Wiτ (t) for opinion i ∈ O in step t and integer τ ≥ 0, as  n o √ ωc (Wiτ (t)) := |Wiτ (t)| · ŝ + min ∆τ, 6c ∆τ log n . The weight ωc (Wiτ (t)) represents a coarse upper bound on how many agents can be contained in Wiτ (t) by time t. Intuitively, the argument for this is as follows: Clearly, the agents initially in Wiτ (t) contribute at most |Wiτ (t)|ŝ to its support. Any increase in this support is the net traffic across its boundary. If i has been productive at least τ times, every opinion on the outer boundary has been productive fewer than τ times, by maximality of the witness. If i has been productive fewer than τ times, then the witness is {i} and its total boundary count is itself less than τ . In either case, the number of productive boundary interactions is at most ∆|Wiτ (t)|τ . Each such interaction sends one agent in either direction with equal probability. In Lemma 25, we bound this net traffic simultaneously over time. Taking a union bound over all possible sets then allows us to apply the estimate to the random witness Wiτ (t). Consequently, for any threshold τ , the weight provides an upper bound on the agents in the subset and therefore also on the support of opinion i. More formally, we show the following bound. Proposition 24. For any c ≥ 1, it holds  Pr ∀i ∈ O, t ≥ 0 :

 Si (t) ≤ min

τ ∈Z≥0

27

ωc (Wiτ (t))

≥1−

1 nc−3

.

Proof. Fix an opinion i∗ ∈ O. Clearly, the support of i∗ is at most the support of every connected subset it is contained in. In particular, it must be at most the support of any witness set. Thus, for every t ≥ 0 and every integer τ ≥ 0, it holds that Si∗ (t) ≤ SWiτ∗ (t) (t). Therefore, to prove the proposition, we show that h Pr ∀i∗ ∈ O, t, τ ∈ Z≥0 :

i SWiτ∗ (t) (t) ≤ ωc (Wiτ∗ (t)) ≥ 1 −

1 nc−3

(16)

.

We begin the proof with some definitions: For each set C ⊂ V , let NC := {j ∈ V \ C | ∃{i, j} ∈ E with i ∈ C} be the set of its neighbors. Further, for each edge e ∈ E and each step t ≥ 0, we let Pe (t) be the indicator that edge e := {i, j} is productive in step t, i.e., an agent switches its opinion from i to j or vice versa. For a set of edges S ⊆ E define PS (t) =

X

and

Pe (t)

PS (↑ t) :=

t−1 X

PS (τ ).

τ =0

e∈S

For an ordered pair (i, j) ∈ V 2 with {i, j} ∈ E let Pi→j (t) indicate that an agent moved from i to j in t. Note that Pe (t) := Pi→j (t) + Pj→i (t). P Moreover, let Pi→j (↑ t) := t−1 s=0 Pi→j (s) count how often an agent moved from i to j before step t. The net traffic that went along the edge is then defined as Ti→j (↑ t) := Pi→j (↑ t) − Pj→i (↑ t). For a subset C, define the traffic into C over the cut defined by this set as X X TC (↑ t) := Tj→i (↑ t). i∈C j∈Ni \C

Given these definitions and assuming the EdgeVOG process starts in an initial configuration ⃗s = (s1 , . . . , sq ), for any set C ⊆ V , we can show the following identity:    X X X s i +  Pj→i (↑ t) − Pi→j (↑ t) SC (t) = Si (t) = i∈C

=

=

X

i∈C

si +

i∈C

i∈C

X

X

si +

i∈C

=

X

X i∈C



X

 

X

 Tj→i (↑ t)

j∈Ni

X

si +



Pj→i (↑ t) − Pi→j (↑ t)

j∈Ni



i∈C

j∈Ni

(Ti→j (↑ t) + Tj→i (↑ t)) +

{i,j}∈E[C]

X i∈C

 

X

 Tj→i (↑ t) .

j∈Ni \C

Note that for each {i, j} ∈ E with i, j ∈ C, holds: Ti→j (↑ t) + Tj→i (↑ t) = (Pi→j (↑ t) − Pj→i (↑ t)) + (Pj→i (↑ t) − Pi→j (↑ t)) = 0. Therefore, the formula simplifies to SC (t) =

X i∈C

si +

X i∈C

 

X j∈Ni \C

28

 Tj→i (↑ t) = sC + TC (↑ t).

(17)

For the next step, we will bound the traffic TC (↑ t). Let S(C) denote the edges of the cut between C and O \ C. In Lemma 25 below, we show that for every nonempty fixed set C and every c ≥ 1, h q  i Pr ∃t ≥ 0 : TC (↑ t) ≥ 3c |C|PS(C) (↑ t) + |C| log n ≤ n−c|C| . (18) Equipped with this bound, consider the event q  o \ \n TC (↑ t) ≤ 3c E= |C|PS(C) (↑ t) + |C| log n . ∅̸=C⊆O t≥0

For c ≤ 3, the proposition is immediate, so assume c > 3. Since initially empty opinions have been discarded, q ≤ n. Thus, the union bound gives q   n   X q −ck X −(c−1)k Pr E ≤ n ≤ n ≤ n−(c−2) ≤ n−(c−3) . k k=1

k=1

In particular, this event holds simultaneously for every set and time, so it applies to the random witness sets without further conditioning. Fix i∗ , t and an integer τ ≥ 0, and write W = Wiτ∗ (t). If Pi∗ (↑ t) ≥ τ , then W is a maximal connected component of opinions whose productive counts are at least τ . Each neighbor outside W therefore has count less than τ . For every cut edge e = {i, j} with i ∈ W and j ∈ / W , we obtain Pe (↑ t) ≤ min{Pi (↑ t), Pj (↑ t)} ≤ τ.

(19)

There are at most ∆|W | cut edges, so PS(W ) (↑ t) ≤ ∆|W |τ . If instead Pi∗ (↑ t) < τ , then W = {i∗ } and PS(W ) (↑ t) = Pi∗ (↑ t) < τ ≤ ∆|W |τ . Thus, the same bound holds in both cases. For τ = 0, the cut count and its traffic are zero. For τ ≥ 1, on E and using ∆ ≥ 1, we have √  √ TW (↑ t) ≤ 3c|W | ∆τ + 1 log n ≤ 6c|W | ∆τ log n. On the other hand, the net traffic is at most the total cut count, giving TW (↑ t) ≤ ∆|W |τ. Combining both estimates with (17) yields √ SW (t) = sW + TW (↑ t) ≤ |W |ŝ + |W | min{∆τ, 6c ∆τ log n} = ωc (W ). As this holds for every opinion, time and threshold on the same event E, Equation (16) and the proposition follow. Lemma 25. Let ∅ ̸= C ⊆ O, and let S(C) be the edges of the cut between C and O \ C. Then, for every c ≥ 1, h q  i Pr ∃t ≥ 0 : TC (↑ t) ≥ 3c |C|PS(C) (↑ t) + |C| log n ≤ n−c|C| . Proof. In each step, either no cut edge is productive, or the traffic increases or decreases by one with equal probability. Thus, (TC (↑ t))t≥0 is a martingale with respect to the natural filtration, starts at zero, and has increments in {−1, 0, 1}. Moreover, a nonzero increment occurs precisely at a productive cut interaction, so t X

TC (↑ s) − TC (↑ s − 1)

2

= PS(C) (↑ t).

s=1

Applying Lemma 33 gives, for every deterministic a > 0 and integer m ≥ 1,   2 Pr ∃t ≥ 0 : PS(C) (↑ t) ≤ m, TC (↑ t) ≥ a ≤ e−a /(2m) . 29

(20)

p For each integer 1 ≤ m ≤ n2 , apply this estimate with a = 3c( |C|m+|C|) log n. The failure probability is at most exp(− 92 c2 |C| log2 n). If PS(C) (↑ t) = 0, the traffic is zero and cannot violate the claimed bound. If PS(C) (↑ t) > n2 , the threshold exceeds n, whereas TC (↑ t) = SC (t) − sC ≤ n. Thus, a union bound over m = 1, . . . , n2 gives h q  i
Pr ∃t ≥ 0 : TC (↑ t) ≥ 3c |C|PS(C) (↑ t) + |C| log n ≤ n2 exp − 92 c2 |C| log2 n ≤ n−c|C| . For the last inequality, we used n ≥ 2, c, |C| ≥ 1 and 92 c2 |C| log n ≥ c|C| + 2. This proves the lemma for both the ordinary and the productive process. It remains to find a suitable τ where the emerging components have small weight, w.h.p. Note that the weight is not simply linear in τ . To see this, consider the following two cases. If we choose a large τ , the witness set will be small, but weight is still large due to the large τ . As an extreme example, for τ ∈ Θ(n2 log n) it easy to show that at most two nodes are productive this often. Thus, the witness set contains at most 2 nodes but has a weight of Θ(n2 log n). On the other hand, a τ that is too small will result in a large witness set and therefore, a large weight. Again, as an extreme example, for τ = 0 the witness set is trivially V (assuming that G is connected). Thus, the weight is Θ(n). In Proposition 26, we show a much smaller bound for τ ′ ∈ Θ(∆5 ŝ2 ). Let T be the step in which the ′ process converges. Then it holds that Wiτ (T ) ≤ O(∆3 log n) with high probability. Proposition 26. Let τ ′ = 100∆5 ŝ2 . Then, there is a universal constant C ≥ 1 such that, for every opinion i and every integer k ≥ 1, h i ′ ⃗ Pr ∃t ≥ 0 : |Wiτ (t)| ≥ C∆3 k | S(0) = ⃗s ≤ 2−k . Before we prove the proposition, we show how it combines with Proposition 24 to imply Theorem 21. Fix a constant c > 4 and define fc (∆, ŝ) := ŝ + min{100∆6 ŝ2 , 60c∆3 ŝ log n}. Substituting τ ′ = 100∆5 ŝ2 in the definition of the weight gives exactly ′

′

ωc (Wiτ (t)) = |Wiτ (t)|fc (∆, ŝ). Let k = ⌈(c + 2) log2 n⌉, and consider the events E1 = {∀i, t, τ : Si (t) ≤ ωc (Wiτ (t))}, ′

E2 = {∀i, t : |Wiτ (t)| < C∆3 k}.   By Proposition 24, Pr E1 ≤ n−(c−3) . By Proposition 26 and a union bound over at most n opinions,   Pr E2 ≤ n2−k ≤ n−(c+1) . On E1 ∩ E2 , every support at every time is at most C∆3 kfc (∆, ŝ). Consequently,   Pr ∀i ∈ O, t ≥ 0 : Si (t) ≤ C∆3 kfc (∆, ŝ) ≥ Pr [E1 ∩ E2 ] ≥ 1 − n−(c−3) − n−(c+1) . (21) For fixed c, the support threshold is O(min{∆9 ŝ2 log n, ∆6 ŝ log2 n}). The additional term ∆3 ŝ log n is absorbed since ∆, ŝ ≥ 1 and n ≥ 2. Combining this with the deterministic bound Si (t) ≤ n proves Theorem 21. By choosing c sufficiently large, the failure exponent can be made arbitrarily large. In the remainder of this section, we prove Proposition 26. In particular, we show that, w.h.p., it holds that ′ |Wiτ (T )| ≤ O(∆3 log n) where T is the step where the process converges. Note that this is a bound on Wiτ (t) ′ for all values of t ≥ 0. On the hand, note that Wiτ (t) is monotonically increasing in t. For any connected set, in which each node is productive τ ′ times until step t, this must clearly also hold in any step t′ ≥ t. Thus, ′ ′ |Wiτ (T )| is an upper bound for all |Wiτ (t)| with t ≤ T . On the other hand, in step t ≥ T , no support changes ′ ′ because the process has converged. Therefore, |Wiτ (T )| = |Wiτ (t)| for all t ≥ T . Therefore, it suffices to ′ bound |Wiτ (T )| to derive an upper bound for all t ≥ 0. 30

In order to prove Proposition 26, we need some additional definitions. We call an opinion j ∈ O bad if its total number Pj (↑ T ) of productive interactions before stabilization is at least τ ′ = 100∆5 ŝ2 . This count includes the interaction in which j becomes decided. Otherwise, we call it good. Likewise, we call a set S ⊆ V bad if every i ∈ S is bad, and good otherwise. After j becomes decided, it is never productive again. In equations, we will use the indicator variable 1{Pj (↑T )≥τ ′ } to denote whether an opinion is good or not. In particular, we let 1{Pj (↑T )≥τ ′ } = 1 if opinion j is bad, and 1{Pj (↑T )≥τ ′ } = 0 otherwise. Given these definitions, we want to show that for each fixed opinion i, the probability that a connected set of bad nodes containing i has size at least C∆3 k is at most 2−k , for a suitable constant C. A major complication in showing that a subgraph C ⊂ V is bad is that the events that two opinions j, j ′ ∈ C are bad are not necessarily independent. In other words, we cannot directly bound each opinion j ∈ C by applying Chernoff bounds individually. Instead of considering the connected sets directly, we will consider sets where opinions are in distance at least 4. We call them 4-separated sets. For these sets, the events that the individual nodes are bad satisfy a joint upper bound. In Lemma 27 below, we show that for every 4-separated set I and every τ ′ ≥ 1, 

Pr ∀j ∈ I : Pj (↑ T ) ≥ τ

′



 ≤

∆ŝ2 τ′

|I| .

Lemma 27. Consider a 4-separated set I. Then, for every τ ′ ≥ 1, Pr [∀j ∈ I : Pj (↑ T ) ≥ τ ′ ] ≤ (∆ŝ2 /τ ′ )|I| . Proof. Before we give the idea and structure of this proof, we require some helpful definitions. W.l.o.g. let I = {1, . . . , k}, and let (F(t))t≥0 be the natural filtration generated by all edge selections and coin flips. Recall that Pi (↑ t) counts the productive interactions involving i before time t. In particular, Pi (↑ 0) = 0. Consider Y
⃗ Φ(t) := Ψi (S(t)) + Pi (↑ t) . i∈I

We first show the following claim. Claim 28. The process (Φ(t))t≥0 is a nonnegative martingale. Proof. To establish that Φ(t) is a martingale, we analyze how it behaves depending on the random productive edge e(t) chosen in step t. Fix a time t and condition on F(t). We write e(t) = ⊥ for an idle step and use Ψi (t) ⃗ as shorthand for Ψi (S(t)). Recall from Claim 9 that, conditional on the chosen productive edge, its potential decreases by one in expectation and all other edge potentials remain unchanged in expectation. Thus, the node potential of a productive opinion decreases by one in expectation, while the other node potentials remain unchanged in expectation. Moreover, since I is 4-separated, an edge cannot meet the closed neighborhoods of two different opinions in I, as this would give a path of length at most three between them. Hence, at most one factor of Φ(t) can change in a step. With this in mind, we consider the following case distinction: • If one endpoint of the chosen edge e lies in I, say i ∈ I, then Pi (↑ t + 1) = Pi (↑ t) + 1. By Claim 9, we have E [Ψi (t + 1) | F (t), e(t) = e] = Ψi (t) − 1, while all factors belonging to opinions in I \ {i} remain unchanged. Thus, we get   Y (Ψu (t) + Pu (↑ t)) E [Ψi (t + 1) + Pi (↑ t) + 1 | F (t), e(t) = e] E [Φ(t + 1) | F (t), e(t) = e] =  u∈I\{i}

 =

Y

 (Ψu (t) + Pu (↑ t)) (Ψi (t) − 1 + Pi (↑ t) + 1) = Φ(t).

u∈I\{i}

• If neither endpoint of e lies in I, but one has a neighbor i ∈ I, then all counts Pj (↑ t) with j ∈ I remain unchanged because no opinion in I is productive. There cannot be a second opinion in I whose node 31

potential is affected, by the distance argument above. Since e is not incident to i, every edge potential contributing to Ψi remains unchanged in expectation by Claim 9. Consequently, E [Ψi (t + 1) | F (t), e(t) = e] = Ψi (t). All other factors remain unchanged, so   Y E [Φ(t + 1) | F (t), e(t) = e] =  (Ψu (t) + Pu (↑ t)) E [Ψi (t + 1) + Pi (↑ t) | F (t), e(t) = e] u∈I\{i}

 =

Y

 (Ψu (t) + Pu (↑ t)) (Ψi (t) + Pi (↑ t)) = Φ(t).

u∈I\{i}

• Finally, if neither endpoint lies in I nor is adjacent to an opinion in I, then no potential and no count in the product changes. The same holds for an idle step. Hence, Φ(t + 1) = Φ(t) deterministically in either case. As these cases cover all possible outcomes, the law of total expectation gives X E [Φ(t + 1) | F (t)] = Pr [e(t) = e | F (t)] E [Φ(t + 1) | F (t), e(t) = e] = Φ(t). e∈E∪{⊥}

Finally, Φ(t) is determined by the history up to time t, all its factors are nonnegative, and Φ(t) ≤ (n2 + t)k at every fixed time t. Thus, it is adapted and integrable, and (Φ(t))t≥0 is indeed a nonnegative martingale. Equipped with this fact, we can now bound the probability that all opinions in I are bad. First observe that Y X Φ(0) = si sj ≤ (∆ŝ2 )k . (22) i∈I

j∈Ni

Q At stabilization, all node potentials are zero. Therefore, Φ(T ) = i∈I Pi (↑ T ). Let B = {∀i ∈ I : Pi (↑ T ) ≥ τ ′ } denote the event that all opinions in I are bad. For every deterministic m, optional stopping at the bounded Q stopping time T ∧ m gives E [Φ(T ∧ m)] = Φ(0). On the event B ∩ {T ≤ m}, we have Φ(T ∧ m) = i∈I Pi (↑ T ) ≥ (τ ′ )k . Since Φ is nonnegative, it follows that (τ ′ )k Pr [B ∩ {T ≤ m}] ≤ E [Φ(T ∧ m)] = Φ(0).

(23)

Finally, T < ∞ almost surely, so Pr [B ∩ {T ≤ m}] → Pr [B] as m → ∞. Taking this limit in (23) and applying (22) yields 

Pr ∀i ∈ I : Pi (↑ T ) ≥ τ

′



Φ(0) ≤ ′ k ≤ (τ )



∆ŝ2 τ′

k .

(24)

This proves the lemma. We now proceed to the proof of Proposition 26. Equipped with Lemma 27, we can bound the size of a witness via a counting argument and the union bound. Proof of Proposition 26: Fix an opinion i and an integer k ≥ 1. We show that a witness containing at least 2∆3 k opinions is unlikely. If i has been productive fewer than τ ′ times, its witness is the singleton {i}, so ′ this event cannot occur. Otherwise, every opinion in Wiτ (T ) is bad, meaning that it has been productive at least τ ′ times. For each connected set C containing i, we construct a 4-separated set IC ⊆ C using a deterministic greedy algorithm. All distances in this construction are measured in the ambient graph G. For R ⊆ O, let Bd (R) = {v ∈ O : distG (v, R) ≤ d}. Fix an ordering of the opinions to break ties.

32

GReedyNet(G, C): 1. Set IC ← {i}. 2. While C \ B3 (IC ) ̸= ∅, do the following: (a) Choose the first node j ∗ ∈ C in distance exactly four from IC . (b) Set IC ← IC ∪ {j ∗ } and recompute C \ B3 (IC ). A suitable node exists whenever the loop continues: follow a path inside C from i to an uncovered node and take the first vertex whose distance from the current set is four. Thus, the construction gives a 4-separated set covering every vertex of C within distance at most three. A radius-three ball contains at most 1 + ∆ + ∆(∆ − 1) + ∆(∆ − 1)2 ≤ 2∆3 vertices for ∆ ≥ 1. Therefore, |IC | ≥ |C|/(2∆3 ). If |C| ≥ 2∆3 k, retain only the first k nodes selected by the algorithm, including i. This prefix is still 4-separated. Moreover, every node except i was added at distance exactly four from an earlier node. Let H4 be the graph joining opinions at distance exactly four in G. The prefix is connected in H4 , whose maximum degree is at most ∆4 . Let Jk (i) denote the family of k-vertex subsets containing i that are 4-separated in G and connected in H4 . A witness of size at least 2∆3 k contains an all-bad member of this family. Consequently,    2 k i h [ ∆ŝ ′ 3 ′ τ {∀j ∈ I : Pj (↑ T ) ≥ τ } ≤ |Jk (i)| . (25) Pr |Wi (T )| ≥ 2∆ k ≤ Pr  τ′ I∈Jk (i)

Here, the first inequality is an inclusion of events; it does not require the map from connected sets to prefixes to be injective. It remains to count the possible prefixes. Every such prefix contains a spanning tree rooted at i, so we use the following bound. Lemma 29. Let G = (V, E) be a graph of maximum degree at most ∆ ≥ 1, then each node i ∈ V is part of at
k most 2e3 ∆ connected subtrees of size k. We present the proof in Section 4.4. Applying Lemma 29 to H4 gives |Jk (i)| ≤ (2e3 ∆4 )k . Since τ ′ = 100∆5 ŝ2 , Equation (25) now yields Pr ′

h

′ |Wiτ (T )| ≥ 2∆3 k

i

 ≤ (2e ∆ ) 3

′

4 k

1 100∆4

k

≤ 2−k .

As Wiτ (t) ⊆ Wiτ (T ) for every t ≥ 0, the same bound holds simultaneously over all times. This proves Proposition 26 with C = 2 and concludes the analysis.

33

4 Tools from Probability Theory & Textbook Results This sections collects some (corollaries of) prior results used in the analysis.

4.1 Bounds for Martingales We use the following standard versions of Doob’s Optional Stopping Theorem. This result is a classical cornerstone of martingale theory and can be found, for instance, in standard textbooks on probability theory and stochastic processes such as [20]. It will be used repeatedly to justify that certain carefully constructed processes preserve their expectation at suitable stopping times. Theorem 30 (Doob’s Optional Stopping Theorem). Let (X(t))t≥0 be a martingale with respect to a filtration (F(t))t≥0 , and let T be a stopping time. Suppose that at least one of the following conditions holds: 1. T is bounded by a deterministic constant. 2. T < ∞ almost surely, and there is a deterministic constant K < ∞ such that |X(t ∧ T )| ≤ K almost surely for every t ≥ 0. 3. E [T ] < ∞, and there is a deterministic constant K < ∞ such that |X(t + 1) − X(t)| ≤ K almost surely for every t ≥ 0. Then E [X(T )] = E [X(0)] . Under the same conditions, if X is a submartingale, then E [X(T )] ≥ E [X(0)]; if X is a supermartingale, then E [X(T )] ≤ E [X(0)]. While Doob’s theorem controls expectations at stopping times, we will also need tail bounds that quantify how much a martingale (or supermartingale) can deviate from its initial value over a fixed time horizon. A classical tool for this purpose is Azuma’s inequality, sometimes also referred to as the Azuma–Hoeffding inequality, which provides sub-Gaussian concentration for martingales with bounded differences; see, e.g., [2, 30, 39]. Theorem 31 (Azuma’s Ineqality). Assume that (Y (t))t≥0 is a supermartingale with |Y (t + 1) − Y (t)| ≤ b almost surely. Then, for every λ > 0 and integer T ≥ 1,     λ2 Pr max (Y (t) − Y (0)) ≥ λ ≤ exp − . 0≤t≤T 2T b2 In particular, the same bound holds for Pr [Y (T ) − Y (0) ≥ λ]. In some situations, however, it is not the value of the process at a fixed time that is of interest, but rather the maximum deviation attained over an entire time interval. Kolmogorov’s maximal inequality addresses exactly this question for martingales by relating the maximum absolute deviation to the second moment at the terminal time. This inequality is classical folklore and can be found, for example, in [34]. Theorem maximal inequality). Let (M (t))t≥0 be a real-valued martingale with M (0) = 0  322(Kolmogorov’s  and E M (t) < ∞. Then for all t ≥ 1 and all λ > 0,     E M (t)2 . Pr max |M (s)| ≥ λ ≤ 0≤s≤t λ2 The following lemma bounds a martingale in terms of its number of nonzero increments. The exponentialsupermartingale construction is a special case of Lemma 1.4 in [44]. We include a proof for completeness.

34

Lemma 33 (Tail bound in terms of nonzero increments). Let (Xt )t≥0 be a martingale with respect to a filtration (Ft )t≥0 , with X0 = 0 and Xt − Xt−1 ∈ {−1, 0, 1} almost surely for all t ≥ 1. Define Vt =

t X

(Xs − Xs−1 )2 ,

s=1

which counts the nonzero increments before or at time t. Then, for every deterministic a, v > 0,  2 a Pr [∃t ≥ 0 : Xt ≥ a, Vt ≤ v] ≤ exp − . 2v Proof. Write Dt = Xt − Xt−1 and pt = Pr [|Dt | = 1 | Ft−1 ]. Since Xt is a martingale, E [Dt | Ft−1 ] = 0. As Dt ∈ {−1, 0, 1}, this implies Pr [Dt = 1 | Ft−1 ] = Pr [Dt = −1 | Ft−1 ] = For a fixed λ > 0, define

pt . 2



 λ2 Mt = exp λXt − Vt . 2

Conditioning on Ft−1 gives  E [Mt | Ft−1 ] = Mt−1 1 − pt + pt e Here, we used

−λ2 /2 e

∞

∞

j=0

j=0

λ + e−λ



2

≤ Mt−1 .

X λ2j eλ + e−λ X λ2j 2 = ≤ = eλ /2 . j 2 (2j)! 2 j!

Thus, (Mt )t≥0 is a nonnegative supermartingale with M0 = 1; integrability follows from Mt ≤ eλt at every fixed time t. Let τa,v = inf{t ≥ 0 : Xt ≥ a, Vt ≤ v}, with τa,v = ∞ if this event never occurs. For   every deterministic integer h ≥ 1, optional stopping at the bounded stopping time τa,v ∧ h gives E Mτa,v ∧h ≤ 1. On {τa,v ≤ h}, 2 we have Mτa,v ∧h = Mτa,v ≥ eλa−λ v/2 . Since M is nonnegative, it follows that Pr [τa,v ≤ h] ≤ e−λa+λ v/2 . 2

Letting h → ∞ gives the same bound for Pr [τa,v < ∞] by continuity of probability. Finally, choosing the deterministic value λ = a/v yields the desired bound.

4.2 Tail-Bounds for Weakly-dependent Variables In several parts of our analysis, we need concentration bounds for sums of random variables that are not fully independent. We use two bounds that capture different forms of weak dependence. The first is an extension of a Chernoff bound due to Scheideler [46], based on the work of Schmidt, Siegel, and Srinivasan [47]. It applies to bounded random variables whose joint moments satisfy a suitable global upper bound. The second bound concerns binary random variables for which the required product inequality is available only for sets that are independent in a given graph. By coloring this graph and combining the color classes using Hölder’s inequality, we obtain a lower-tail bound whose exponent loses only a factor equal to the chromatic number. A similar has been used before by Janson For the first bound, our starting point is a theorem by Scheideler [46] that itself is heavily influenced by [47]. In particular, Scheideler observed that the Chernoff bounds presented in [47] for k-wise independent variables hold for a much wider class of random variables. In particular, k-wise independence is not required; instead, the variables must satisfy a specific technical inequality that is sufficient for the proof technique of [47] to go through.

35

We use the corresponding upper-tail bound under a condition on elementary symmetric polynomials. For a1 , . . . , ak ∈ R and 1 ≤ l ≤ k, define X

Pl (a1 , . . . , ak ) :=

l Y

aij .

1≤i1 <···<il ≤k j=1

The indices are distinct. In particular, Pl (p, . . . , p) =

k l l p.

Theorem 34 (Chernoff bound under a moment condition). Let X1 , . . . , Xk ∈ [0, 1] and 0 < p < 1. Suppose that, for every 1 ≤ l ≤ k,   k l E [Pl (X1 , . . . , Xk )] ≤ p. l P Set S = ki=1 Xi and µ = pk. Then, for every δ ≥ 1,
Pr [S ≥ δµ] ≤ exp −µ(δ log δ − δ + 1) . Proof. For x ∈ [0, 1] and θ ≥ 0, convexity gives eθx ≤ 1 + (eθ − 1)x. Expanding the product and applying the assumed bounds on the elementary symmetric polynomials yields h

E e

θS

i

≤

k X

(eθ − 1)l E [Pl (X1 , . . . , Xk )] ≤ 1 + p(eθ − 1)

k

≤ exp µ(eθ − 1) ,

l=0

where P0 = 1. Markov’s inequality with θ = log δ gives the claim; for δ = 1 the bound is immediate. We extend this bound to variables that are bounded by b. Namely, P Theorem 35. Let S = ki=1 Xi , where Xi ∈ [0, b] and b > 0. Suppose that 0 < p < 1 and x1 , . . . , xk ∈ [0, b] satisfy, for every subset I ⊆ [k], " # Y Y E Xi ≤ p|I| xi . (26) i∈I

Set µ = p

i∈I

Pk

i=1 xi . If µ > 0, then for every δ ≥ 1,

 µ  Pr [S ≥ δµ] ≤ exp − (δ log δ − δ + 1) . b

In particular, for δ ≥ e2 , this probability is at most exp(−δµ/b). If µ = 0, then S = 0 almost surely. Proof. We use the same argument as for Theorem 34, keeping the individual values xi in the product. Let Xi′ = Xi /b ∈ [0, 1]. For θ ≥ 0, convexity and Equation (26) give " k # " # h i  X  eθ − 1 |I| Y Y θS/b θ E e ≤E 1 + (e − 1)Xi /b = E Xi b i=1

≤

k  Y i=1

1+

I⊆[k]

i∈I

 µ  pxi θ (e − 1) ≤ exp (eθ − 1) . b b

Here, all coefficients are nonnegative, so the product assumption applies term by term. In particular, the parameter µ uses the sum over all k values xi . For µ > 0 and δ > 1, Markov’s inequality with θ = log δ gives   δµ µ Pr [S ≥ δµ] ≤ exp − log δ + (δ − 1) . b b This is the desired bound. If δ ≥ e2 , then δ log δ − δ + 1 ≥ δ. Finally, if µ = 0, the singleton cases of Equation (26) imply E [Xi ] = 0 for every i, so all variables vanish almost surely.

36

The preceding bound is useful when the required product estimate holds for arbitrary subsets of the variables. For the number of surviving opinions, however, we obtain the relevant product estimate only for opinions that are sufficiently far apart in the opinion graph. The following lemma turns such local product estimates into a global lower-tail bound. More precisely, we introduce a graph H whose independent sets are exactly the sets for which the product estimate is available. A proper coloring of H partitions the variables into classes on which the standard moment-generating-function argument applies. The dependence between different color classes costs a factor of χ(H) in the exponent. Theorem 20. Let X1 , . . . , Xq ∈ 0, 1 be binaryPrandom variables, P let p1 , . . . , pq ∈ [0, 1], and let H be an undirected graph on [q]. Furthermore, let Z := qi=1 Xi , µ := qi=1 pi , and κ := χ(H). Suppose that, for every independent set I of H, " # Y Y E (1 − Xi ) ≤ (1 − pi ). (12) i∈I

i∈I

Then, for every 0 ≤ δ ≤ 1,



δ2µ Pr [Z ≤ (1 − δ)µ] ≤ exp − 2κ

 .

Proof. We follow the textbook proof for the Chernoff bound, but with the restriction of the graph H. Fix a proper coloring of H with color classes C1 , . . . , Cκ , and let Yi := 1 − Xi be the indicator that Xi = 0. Every subset of a color class is an independent set of H. Note that for a binary random variable Y ∈ {0, 1} and every θ ≥ 0, we have ( 1 if Y = 0 exp (θY ) = exp θ if Y = 1. Therefore exp (θY ) = 1 + (eθ − 1)Y . Thus, for every θ ≥ 0, combining this fact and (12) gives " # # " # !# " " Y Y X Y X
θ |A| θ (e − 1) E Yi exp (θYi ) = E 1 + (e − 1)Yi = Yi =E E exp θ i∈Cr

i∈Cr

≤

X

(e − 1) θ

A⊆Cr

|A|

Y

i∈Cr

(1 − pi ) =

i∈A

Y

A⊆Cr

i∈A

1 + (e − 1)(1 − pi ) . θ

i∈Cr

Q P Q Here, we also used that i∈Cr (1 + Yi′ ) = A⊆Cr i∈A Yi′ where Yi′ = (eθ − 1)Yi . All coefficients in the expansion are non-negative, which is the reason why the local product assumption can be applied term by term. Since Xi = 1 − Yi , the preceding inequality implies " !# ! X Y X
E exp −θ Xi ≤ pi , 1 − pi (1 − e−θ ) ≤ exp −(1 − e−θ ) i∈Cr

i∈Cr

i∈Cr

where we used 1 − z ≤ e−z in the last step. Next, we consider all κ color classes. The color classes are not necessarily independent of each other. We handle this using Hölder’s inequality. For every λ ≥ 0, !#!1/κ !# " " κ   κ h i X X Y Y 1 − e−κλ −λZ ≤ E exp −κλ Xi ≤ exp − E e =E exp −λ Xi µ . κ r=1

i∈Cr

r=1

i∈Cr

If Z ≤ (1 − δ)µ, then e−λZ ≥ e−λ(1−δ)µ for any λ ≥ 0. Markov’s inequality therefore gives   h i E e−λZ −λZ −λ(1−δ)µ Pr [Z ≤ (1 − δ)µ] ≤ Pr [λZ ≤ λ(1 − δ)µ] = Pr e ≥e ≤ −λ(1−δ)µ e  −λZ  Using our previously computed bound for E e then gives   1−e−κλ e− κ µ 1 − e−κλ Pr [Z ≤ (1 − δ)µ] ≤ −λ(1−δ)µ = exp λ(1 − δ)µ − µ . κ e 37

It remains to find the right choice for λ. For δ = 0, the bound is trivial. For δ = 1, letting λ → ∞ in the preceding bound gives Pr [Z = 0] ≤ exp(−µ/κ) ≤ exp(−µ/(2κ)). For 0 < δ < 1, we choose λ = − κ1 log(1 − δ) so that e−κλ = 1 − δ. Substituting this value proves  µ
 Pr [Z ≤ (1 − δ)µ] ≤ exp − δ + (1 − δ) log(1 − δ) . κ As − log(1 − δ) ≥ δ for all δ ∈ (0, 1), it holds Z δ Z δ δ2 δ + (1 − δ) log(1 − δ) = − log(1 − x) dx ≥ x dx = , 2 0 0 which proves the theorem.

4.3 Lower Bound for the convergene of Gambler’s Ruin. Lemma 36. Consider the fair gambler’s ruin chain (X(t))t≥0 on {0, 1, . . . , n} with absorbing states {0, n}. Let T := min{t ≥ 0 : X(t) ∈ {0, n}}

 
be the stopping time. If X(0) = 1, then there exists an absolute constant c > 0 such that Pr T ≥ cn2 = Ω n1 . Proof. For a ∈ {0, 1, . . . , n} let τa := min{t ≥ 0 : X(t) = a}. Set m := ⌊n/2⌋. Since τ0 ∧ τm is almost surely finite and the stopped martingale is bounded between 0 and m, applying optional stopping at (τ0 ∧ τm ) ∧ r and then bounded convergence as r → ∞ yields E [X(τ0 ∧ τm )] = E [X(0)] = 1. Moreover, X(τ0 ∧ τm ) ∈ {0, m}, hence 1 = E [X(τ0 ∧ τm )] = m · Pr [τm < τ0 ] , and therefore

1 . m Let now Prm [·] be shorthand for Pr [· | X(0) = m]. Using the strong Markov property at time τm we obtain, for any t ≥ 0, 1 Pr [T ≥ t] ≥ Pr [τm < τ0 ] · Prm [T ≥ t] = · Prm [T ≥ t] . m It remains to show that Prm [T ≥ t] is bounded below by a positive constant for t = Θ(n2 ). Consider a simple random walk (S(t))t≥0 on Z with S(0) = 0. We couple it to the gambler’s ruin chain started at m so that S(t) = X(t) − m holds for all t < T . If T ≤ t, then by time t the chain must have hit either 0 or n, and thus |X(s) − m| ≥ m for some s ≤ t. Consequently,   Prm [T ≤ t] ≤ Pr max |S(s)| ≥ m . Pr [τm < τ0 ] =

0≤s≤t

By Kolmogorov’s maximal inequality (see Theorem 32) applied to the martingale (S(t))t≥0 ,     E S(t)2 Pr max |S(s)| ≥ m ≤ . 0≤s≤t m2   Since E S(t)2 = t for simple random walk on Z, we obtain Prm [T ≤ t] ≤

t . m2

Choosing t := 14 m2 gives Prm [T ≤ t] ≤ 1/4, and hence 3 Prm [T ≥ t] ≥ . 4 Putting everything together,



T ≥ 14 m2



  1 3 1 ≥ . · = Ω m 4 n

Pr   Since m = Θ(n), this implies Pr T ≥ cn2 = Ω(1/n) for some absolute constant c > 0. 38

4.4 Number of Subtrees of Size k Lemma 29. Let G = (V, E) be a graph of maximum degree at most ∆ ≥ 1, then each node i ∈ V is part of at
k most 2e3 ∆ connected subtrees of size k. Proof. We use the classical tree counting approach via the Catalan numbers [7]. There are Ck−1 ordered rooted tree shapes on k vertices, where   1 2k − 2 Ck−1 = ≤ 4k−1 . k k−1 Fix one such shape and map its root to i. We embed the remaining vertices in breadth-first order. Each nonroot vertex must be mapped to a neighbor of its parent, so it has at most ∆ choices. This gives at most ∆k−1 maps. Some maps identify vertices and do not yield a subtree, but counting these maps only increases our upper bound. Conversely, every rooted subtree can be represented by at least one ordered rooted tree shape and an injective map of this form. Therefore, for ∆ ≥ 1, the number of subtrees is at most Ck−1 ∆k−1 ≤ (4∆)k−1 ≤ (2e3 ∆)k . This also covers k = 1. The same bound applies to connected vertex sets, since each such set has a spanning tree rooted at i.

39

5 A New Analysis for Asynchronous Pull Voting on Graphs In this section, we show that our potential can also be used to analyze a simple variant of the standard pull voting process on regular graphs. Consider the following pull
voting process AsyncVoting on a connected d-regular graph G = (V, E) with n = |V | ≥ 2 and E ⊆ V2 : In each step t ≥ 0, a pair of agents {u, v} ∈ E is picked uniformly at random and then, with probability 12 each, u adopts the opinion of v or vice versa. On a regular graph, this is equivalent to first picking u uniformly at random and then letting this agent adopt the 2 opinion of a neighbor v chosen uniformly at random. We show that this process converges in O( ΦnG log n) steps, w.h.p., where ΦG is the conductance of G defined as: ΦG :=

min

S⊂V 0<|S|≤n/2

|{{u, v} ∈ E | u ∈ S, v ∈ V \ S}| . d · |S|

Formally, we show Theorem 37. Let G = (V, E) be a connected d-regular graph on n ≥ 2 vertices with conductance ΦG . Then, for any initial configuration AsyncVoting converges in O(n2/ΦG log n) steps w.h.p. Cooper and Rivera [14, Example 11] prove an expected bound of O(n2 /ΦG ) for asynchronous pull voting on regular graphs. Applying Markov’s inequality in consecutive blocks gives the same high probability bound as above. Berenbrink et al. [5] prove a related bound for synchronous lazy voting, where time is measured in rounds in which all agents update. Both papers use variance-based arguments. Our potential offers an alternative and arguably even simpler proof. Proof. First, assume that there are two opinions 0 and 1. We denote their supports by S0 (t) and S1 (t) and ⃗ define Ψ(S(t)) = S0 (t)S1 (t). Let F(t) be the natural filtration, which records the opinions of all vertices and the previous interactions. Write P(t) for the indicator that step t selects two agents with different opinions. The same calculation as in Proposition 1 gives h i ⃗ + 1)) | F (t) = Ψ(S(t)) ⃗ E Ψ(S(t − Pr [P(t) = 1 | F (t)] . Before consensus, let Ct ⊂ V be the smaller opinion class, and write s = |Ct | ∈ {1, . . . , ⌊n/2⌋}. Let ∂Ct denote the edges with one endpoint in Ct and one outside. Since |E| = dn/2, the definition of conductance gives Pr [P(t) = 1 | F (t)] =

|∂Ct | 2|∂Ct | 2ΦG s 2ΦG ⃗ = ≥ ≥ 2 Ψ(S(t)), |E| dn n n

⃗ where the last inequality uses Ψ(S(t)) = s(n − s) ≤ ns. Consequently,  h i  2Φ G ⃗ ⃗ + 1)) | F (t) ≤ 1 − E Ψ(S(t Ψ(S(t)). n2 This also holds after consensus, when the potential remains zero. Taking expectations and iterating yields     h i 2ΦG t 2ΦG t 2 ⃗ E Ψ(S(t)) ≤ Ψ(⃗s0 ) 1 − 2 . ≤ n exp − 2 n n For any fixed c > 1, choose t∗ = ⌈(c + 3)n2 log n/(2ΦG )⌉. Then the expected potential is at most n−(c+1) . As the potential is a positive integer before consensus, Markov’s inequality bounds the probability that the binary process has not reached consensus by time t∗ by n−(c+1) . Finally, consider an arbitrary initial configuration with q ≤ n opinions. For each initial opinion i, assign binary opinion 1 to its agents and 0 to all other agents. Under the same edge selections and copying directions, this projection follows exactly the binary process just analyzed. A union bound over the q projections shows that, with probability at least 1 − n−c , all projections have reached consensus by time t∗ . At that time, choose any opinion still present. Its projection contains a 1 and has reached consensus, so every agent holds that opinion. Thus, the original process has also reached consensus, proving the theorem.

40

References [1] G. Agnarsson and M. M. Halldórsson. “Coloring Powers of Planar Graphs”. In: SIAM Journal on Discrete Mathematics 16.4 (2003), pp. 651–662. doi: 10.1137/S0895480100367950. [2] K. Azuma. “Weighted sums of certain dependent random variables”. In: Tohoku Mathematical Journal 19.3 (1967), pp. 357–367. [3] L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan. “Simple dynamics for plurality consensus”. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures. 2014, pp. 247–256. [4] P. Berenbrink, A. Clementi, R. Elsässer, P. Kling, F. Mallmann-Trenn, and E. Natale. “Ignore or Comply? On Breaking Symmetry in Consensus”. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. 2017, pp. 335–344. [5] P. Berenbrink, G. Giakkoupis, A. Kermarrec, and F. Mallmann-Trenn. “Bounds on the Voter Model in Dynamic Networks”. In: ICALP. Vol. 55. 2016, 146:1–146:15. [6] C. Bernardo, C. Altafini, A. Proskurnikov, and F. Vasca. “Bounded confidence opinion dynamics: A survey”. In: Automatica 159 (2024), p. 111302. [7] E. Catalan. “Note sur une équation aux différences finies”. In: Journal de Mathématiques Pures et Appliquées 3 (1838), pp. 508–516. [8] G. Chen, W. Su, W. Mei, and F. Bullo. “Convergence properties of the heterogeneous Deffuant–Weisbuch model”. In: Automatica 114 (2020), p. 108825. [9] C. Cooper, M. Dyer, A. Frieze, and N. Rivera. “Discordant Voting Processes on Finite Graphs”. In: SIAM Journal on Discrete Mathematics 32.4 (2018), pp. 2398–2420. doi: 10.1137/16M1105979. eprint: https: //doi.org/10.1137/16M1105979. [10]

C. Cooper, M. E. Dyer, A. M. Frieze, and N. Rivera. “Discordant Voting Processes on Finite Graphs”. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP. Vol. 55. LIPIcs. 2016, 145:1–145:13. doi: 10.4230/LIPICS.ICALP.2016.145.

[11]

C. Cooper, R. Elsässer, H. Ono, and T. Radzik. “Coalescing Random Walks and Voting on Connected Graphs”. In: SIAM J. Discret. Math. 27.4 (2013), pp. 1748–1758.

[12]

C. Cooper, N. Kang, and T. Radzik. “A Simple Model of Influence”. In: Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Toronto, ON, Canada, May 23-26, 2023, Proceedings. Vol. 13894. Lecture Notes in Computer Science. 2023, pp. 164–178. doi: 10.1007/978- 3- 031- 322969\_11.

[13]

C. Cooper, N. Kang, T. Radzik, and N. Vu. “A Simple Model of Influence: Details and Variants of Dynamics”. In: Modelling and Mining Networks - 19th International Workshop, WAW 2024, Warsaw, Poland, June 3-6, 2024, Proceedings. Vol. 14671. Lecture Notes in Computer Science. 2024, pp. 32–46. doi: 10. 1007/978-3-031-59205-8\_3.

[14]

C. Cooper and N. Rivera. “The Linear Voting Model”. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP). Vol. 55. 2016, 144:1–144:12.

[15]

J. Czyzowicz, L. Gąsieniec, A. Kosowski, E. Kranakis, P. G. Spirakis, and P. Uznański. “On convergence and threshold properties of discrete Lotka-Volterra population protocols”. In: Journal of Computer and System Sciences 130 (2022), pp. 1–25.

[16]

G. Deffuant, D. Neau, F. Amblard, and G. Weisbuch. “Mixing beliefs among interacting agents”. In: Adv. Complex Syst. 03.01n04 (2000), pp. 87–98.

[17]

M. H. DeGroot. “Reaching a consensus”. In: J. Amer. Stat. Assoc. 69.345 (1974), pp. 118–121.

[18]

B. Doerr, D. Johannsen, and C. Winzen. “Non-existence of linear universal drift functions”. In: Theor. Comput. Sci. 436 (2012), pp. 71–86. doi: 10.1016/J.TCS.2012.01.048.

[19]

P. Donnelly and D. Welsh. “Finite particle systems and infection models”. In: Mathematical Proceedings of the Cambridge Philosophical Society 94.1 (1983), pp. 167–182. 41

[20]

J. L. Doob. Stochastic Processes. 1953.

[21]

J. M. Enelow and M. J. Hinich. The spatial theory of voting: An introduction. 1984.

[22]

A. Flache, M. Mäs, T. Feliciani, E. Chattoe-Brown, G. Deffuant, S. Huet, and J. Lorenz. “Models of Social Influence: Towards the Next Frontiers”. In: Journal of Artificial Societies and Social Simulation 20.4 (2017). doi: 10.18564/jasss.3521.

[23]

J. French Jr. “A formal theory of social power.” In: Psychol. Rev. 63.3 (1956), pp. 181–194.

[24]

N. Friedkin and E. Johnsen. “Social influence and opinions”. In: J. Math. Soc. 15.3-4 (1990), pp. 193–206.

[25]

M. Ghaffari and J. Lengler. “Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics”. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. PODC ’18. 2018, pp. 305–313.

[26]

M. Hardin and N. Lanchier. “Probability of Consensus in Spatial Opinion Models with Confidence Threshold”. In: ALEA Lat. Am. J. Probab. Math. Stat. 19.1 (2022), pp. 417–437. doi: 10.30757/ALEA.v1915.

[27]

Y. Hassin and D. Peleg. “Distributed Probabilistic Polling and Applications to Proportionate Agreement”. In: Information and Computation 171.2 (2001), pp. 248–268.

[28]

J. He and X. Yao. “A study of drift analysis for estimating computation time of evolutionary algorithms”. In: Natural Computing: An International Journal 3.1 (2004), pp. 21––35.

[29]

R. Hegselmann and U. Krause. “Opinion dynamics and bounded confidence: models, analysis and simulation”. In: J. Artif. Soc. Soc. Simul. 5 (2002).

[30]

W. Hoeffding. “Probability inequalities for sums of bounded random variables”. In: Journal of the American Statistical Association 58.301 (1963), pp. 13–30.

[31]

S. Janson. “Large deviations for sums of partly dependent random variables”. In: Random Structures & Algorithms 24.3 (2004), pp. 234–248. doi: https://doi.org/10.1002/rsa.20008.

[32]

D. Johannsen. “Random combinatorial structures and randomized search heuristics”. PhD thesis. Saarland University, 2010. doi: http://dx.doi.org/10.22028/D291-26016.

[33]

H. A. Kierstead, D. Yang, and J. Yi. “On Coloring Numbers of Graph Powers”. In: Discrete Mathematics 343.6 (2020), p. 111712. doi: 10.1016/j.disc.2019.111712.

[34]

A. N. Kolmogorov. Grundbegriffe der Wahrscheinlichkeitsrechnung. 1933.

[35]

N. Lanchier and S. Scarlatos. “Limiting Behavior for a General Class of Voter Models with Confidence Threshold”. In: ALEA Lat. Am. J. Probab. Math. Stat. 14.1 (2017), pp. 63–92. doi: 10.30757/ALEA.v1405.

[36]

J. Lengler. “Drift Analysis”. In: Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. 2020, pp. 89–131. doi: 10.1007/978-3-030-29414-4_2.

[37]

J. Lorenz. “Continous Opinion Dynamics under bounded confidence: A survey”. In: Int. J. Modern Phys. C 18.12 (2007), pp. 1819–1838.

[38]

J. Lorenz. “Heterogeneous bounds of confidence: Meet, discuss and find consensus!” In: Complexity 15.4 (2010), pp. 43–52.

[39]

C. McDiarmid. “Concentration”. In: Probabilistic Methods for Algorithmic Discrete Mathematics (1998), pp. 195–248.

[40]

T. Nakata, H. Imahayashi, and M. Yamashita. “A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem”. In: Networks 35.4 (2000), pp. 266–273.

[41]

T. Nakata, H. Imahayashi, and M. Yamashita. “Probabilistic Local Majority Voting for the Agreement Problem on Finite Graphs”. In: COCOON. Vol. 1627. Lecture Notes in Computer Science. 1999, pp. 330– 338.

[42]

H. Noorazar. “Recent advances in opinion propagation dynamics: A 2020 survey”. In: The European Physical Journal Plus 135.6 (2020). doi: 10.1140/epjp/s13360-020-00541-2. 42

[43]

M. K. Öztürk. “Dynamics of discrete Opinions without Compromise”. In: Adv. Complex Syst. 16.6 (2013). doi: 10.1142/S0219525913500100.

[44]

V. H. de la Peña, M. J. Klass, and T. L. Lai. “Self-normalized processes: Exponential inequalities, moment bounds and iterated logarithm laws”. In: The Annals of Probability 32.3A (2004), pp. 1902–1933. doi: 10.1214/009117904000000397.

[45]

J. E. Rowe and D. Sudholt. “The choice of the offspring population size in the (1,λ) evolutionary algorithm”. In: Theoretical Computer Science 545 (2014). Genetic and Evolutionary Computation, pp. 20–38. doi: https://doi.org/10.1016/j.tcs.2013.09.036.

[46]

C. Scheideler. Probabilistic Methods for Coordination Problems. 2000.

[47]

J. P. Schmidt, A. Siegel, and A. Srinivasan. “Chernoff-Hoeffding Bounds for Applications with Limited Independence”. In: SIAM J. Discret. Math. 8.2 (1995), pp. 223–250. doi: 10.1137/S089548019223872X.

[48]

P. Sobkowicz. “Modelling Opinion Formation with Physics Tools: Call for Closer Link with Reality”. In: Journal of Artificial Societies and Social Simulation 12.1 (2009).

[49]

G. Weisbuch, G. Deffuant, F. Amblard, and J.-P. Nadal. “Interacting Agents and Continuous Opinions Dynamics”. In: Lecture Notes in Economics and Mathematical Systems 521 (2003), pp. 225–242.

[50]

J. Zhang and G. Chen. “Convergence rate of the asymmetric Deffuant-Weisbuch dynamics”. In: J. Syst. Sci. Complex. 28 (2015), pp. 773––787.

43

Related documents

• The Voter Model with Opinion Graph#1341572
• Independent natural extension for choice functions#84673
• Zeros of the independence polynomial on recursive sequences of graphs#1129703
• Bayesian Belief Layer for Controllable Opinion Dynamics in LLM Agents#1036385
• Bayesian Belief Layer for Controllable Opinion Dynamics in LLM Agents#1006884