Consensus Time in 3-Majority and 2-Choices Is Determined by the Maximum Initial Opinion Density
arXiv:2606.11778v1 [cs.DC] 10 Jun 2026
Niccolò D’Archivio Université Côte d’Azur, Inria, CNRS, i3s, Sophia Antipolis, France [email protected] https://sites.google.com/view/niccolo-darchivio/home ORCID: 0009-0005-9491-2928
Abstract We establish the correct parameter governing the convergence time of the 3-Majority and 2-Choices dynamics on the complete graph in the synchronous model. Recent work [Shimizu and Shiraga, PODC’25] provides matching upper and lower bounds on the number of rounds to consensus, but only in a weak sense: the bounds are shown to coincide for some initial opinion configuration. In contrast, we obtain tight bounds in a strong sense, with upper and lower bounds matching up to logarithmic factors for every initial configuration. Let α(0) be the initial opinion-frequency vector, and denote by ∥α(0)√ ∥∞ its maximum entry. We show that 3Majority reaches consensus in Θ̃(min{∥α(0) ∥−1 ∞ , n}) rounds w.h.p., while 2-Choices reaches consensus in Θ̃(∥α(0) ∥−1 ∞ ) rounds w.h.p. Our results demonstrate that the convergence time of both dynamics is governed not by global parameters such as the number of opinions k or the squared ℓ2 norm of the initial opinion distribution, but rather by the “local” parameter ∥α(0) ∥∞ , the maximum initial opinion density.
Keywords: 3-Majority dynamics, 2-Choices dynamics, opinion dynamics, consensus, distributed algorithms, convergence time, infinity norm
1
Introduction
We study two well-known opinion dynamics: 3-Majority and 2-Choices. These dynamics have received considerable attention in the distributed computing community, as they are simple yet powerful protocols for the consensus problem and its variants [4]. They are defined on a distributed system of n agents, each holding an opinion in [k], where 2 ≤ k ≤ n. The agents interact in synchronous rounds on the complete graph with self-loops. In each round, every agent samples a few other agents and updates its opinion according to a simple rule. In 3-Majority, each agent samples three agents and adopts the majority opinion among them, breaking ties uniformly at random. In 2-Choices, each agent samples two agents and adopts their opinion if they coincide; otherwise, it keeps its current opinion. The goal is to reach consensus, i.e., a configuration where all agents hold the same opinion. We are interested in the number of rounds needed to reach consensus with high probability, as a function of the initial opinion configuration. To describe the state of the system at round t, we use the opinion-frequency vector α(t) = (αt (i))i∈[k] , where αt (i) is the fraction of agents holding opinion i at round t. We refer to α(t) as the configuration at round t. Two important parameters of a configuration are γt = P ∥α(t) ∥22 = i∈[k] αt (i)2 for the squared ℓ2 norm of the opinion distribution, and mt = ∥α(t) ∥∞ = maxi∈[k] αt (i) for the maximum opinion density. The ratio between these two quantities servea 1
as proxy for the “balance” of a configuration. See figure 1 for a visual representation of the ratio γt /mt for all possible configurations with three opinions. While it always holds that mt ≥ γt , equality holds if and only if all nonzero opinion frequencies are equal. Thus, we call α(t) a balanced configuration if γt = Θ(mt ). On the other hand, if there are only a few opinions with large density and many with small density, then mt is much larger than γt , and we call α(t) an unbalanced configuration. Recent work by Shimizu and Shiraga [19] gives upper bounds on the convergence time of 3-Majority and 2-Choices in terms of γ0 . In particular, they show that √ 3-Majority reaches consensus in Õ(min{γ0−1 , n}) rounds with high probability, while 2-Choices reaches consensus in Õ(γ0−1 ) rounds with high probability. They also show that there exists an initial configuration for which these bounds are tight, up to logarithmic factors. Thus, their result leaves open the question of whether γ0 is the correct parameter governing the convergence time of these dynamics. α0 (3) = 1
0.984 0.956 0.928 0.900 γ0 m0
0.872 0.844 0.816 0.788 0.760
α0 (1) = 1
α0 (2) = 1
0.732
Figure 1: A heatmap of the ratio γ0 /m0 for all possible initial configurations with three opinions. The corners of the triangle correspond to monochromatic configurations, where m0 = γ0 = 1. The centre of the triangle corresponds to the perfectly balanced configuration, where m0 = γ0 = 1/3. The lower γ0 /m0 the more unbalanced the configuration is.
1.1
Our Contribution
We show that the correct parameter governing the convergence time of both dynamics is m0 , the maximum initial opinion density, rather than γ0 . In particular, we show that 3-Majority reaches √ consensus in Θ̃(min{m−1 0 , n}) rounds with high probability, while 2-Choices reaches consensus in Θ̃(m−1 0 ) rounds with high probability. More precisely, we prove the following result. Theorem 1.1 (Main result, informal). Consider a configuration with opinion-frequency vector α(0) , and let m0 = ∥α(0) ∥∞ be the maximum initial opinion density. If the network is the complete graph with self-loops and agents activate synchronously, then 3-Majority reaches consensus in −1 √ Θ̃ min{m0 , n} rounds with high probability, while 2-Choices reaches consensus in Θ̃(m−1 0 ) rounds with high probability. See theorems 5.1 and 5.3 for the formal statement with the precise logarithmic factors. This result translates into a substantial improvement over the state-of-the-art upper bounds of Shimizu and Shiraga [19] for unbalanced initial configurations, where m0 is much larger than γ0 . √ For example, consider a configuration with n opinions: one opinion has density m0 = 1/ n and 2
the remaining n−1 opinions each have density (1−m0 )/(n−1), so γ0 = m20 +(1−m0 )2 /(n−1) ≈ √ 1/n. In this configuration, the convergence time of 2-Choices is Θ̃( n) by our result, while the bound of Shimizu and Shiraga would give only Õ(n). A similar gap appears for 3-Majority, leading to improvements up to a factor n1/4 on consensus time. Beyond convergence time improvements, our result sheds light on an interesting fact: the consensus time of these two dynamics does not depend on global parameters such as the number of opinions k or the squared ℓ2 norm γ0 of the initial opinion distribution, but rather on the local parameter m0 , the maximum initial opinion density. This is somewhat counterintuitive: if we fix the largest opinion density m0 , then the distribution of the remaining mass among the other opinions (which changes γ0 ) does not affect the convergence time of the dynamics. At first glance, one could expect that distributing the remaining mass among a few competing opinions would make the convergence time longer, while distributing the same mass among more opinions would make it shorter, but this is not the case. Another interesting consequence of our result is that we show for the first time a gap in the convergence time between 3-Majority and the Undecided-State dynamics. The UndecidedState is a well-known opinion dynamics in which an agent that samples an opinion different from its own becomes undecided, and an undecided agent just copies the sampled opinion. γ0 Becchetti et al. [5] proved that the Undecided-State reaches consensus in O( m 2 log n) rounds 0
with high probability, as long as the number of opinions k = O((n log n)1/3 ). This means that 3-Majority can be slower than the Undecided-State by a factor of roughly m0 /γ0 , which becomes substantial for unbalanced configurations. To the best of our knowledge, this surprising advantage of the Undecided-State over 3-Majority has passed unnoticed until now, as it exists only for unbalanced configurations, highlighting the importance of analysing the dynamics for every initial configuration. See figure 2 for a comparison of the convergence time of 3-Majority, 2-Choices, and the Undecided-State for different initial configurations. An important variant of the consensus problem is the plurality consensus problem, where the goal is to reach consensus on the initial plurality opinion, i.e., the opinion with the largest initial density. We show that, for both 3-Majority and 2-Choices, plurality consensus is ensured by local conditions, namely m0 and the bias between the largest and second-largest opinion densities. More precisely, we prove the following result. Theorem 1.2 (Plurality consensus, informal). Consider a configuration with opinion-frequency vector α(0) such that α0 (1) > α0 (2) ≥ · · · ≥ α0 (k). Let m0 = α0 (1) be the maximum initial opinion density, and let B0 = α0 (1) − α0 (2) be the density bias between the largest and secondlargest opinions. If the network is the complete graph with self-loops and agents activate q log n log n synchronously, then under the conditions m0 = ω( √n ) and B0 = ω( n ), 3-Majority reaches −2 while for consensus on opinion 1 in O(m−1 0 log n) rounds with probability at least 1 − n ,q 2
2-Choices, the same statement holds under the condition m0 = ω( (lognn) ) and B0 = ω(
m0 log n ). n
This result relaxes the state-of-the-art conditions for plurality consensus of Shimizu and 2 √ n ) for 3-Majority, and γ0 = ω( (log n) ) for 2-Choices. Shiraga [19], which require γ0 = ω( log n n Again, the improvement is substantial for unbalanced configurations, and the gap between our conditions and those of Shimizu and Shiraga can be as large as a factor of n1/4 for 3-Majority and n1/2 for 2-Choices.
2
Related Work
There is a vast body of research investigating the convergence time of simple dynamics such as 3-Majority, 2-Choices, and the Undecided-State, both in the synchronous and in the asynchronous settings. We first focus on the works on the synchronous setting. 3
Rounds to consensus
128 64
3-Majority: balanced 2-Choices: balanced Undecided-State: balanced 3-Majority: unbalanced 2-Choices: unbalanced Undecided-State: unbalanced
32 16 8 4
6
7
8
9
10
11 log2 n
12
13
14
15
16
Figure 2: Comparison of consensus time between 3-Majority, 2-Choices, and Undecided-State over 100 simulations. We fix the maximum opinion density m0 ≈ n−1/4 , and we compare two different distributions of the remaining mass among the other opinions. In the balanced case, all opinions have mass m0 , while in the unbalanced case we set all the remaining opinion density to 1/n. 3-Majority. Let us specify that all the results we mention in this subsection and the next two subsections hold on with self-loops. The work [7] proved an √ the complete graph of n nodes 2 upper bound of O (k log n + k log n)(k + log n) rounds to reach consensus that holds w.h.p., provided that k ≤ nα for a suitable positive constant α < 1. In [6], the authors showed that the synchronous 3-Majority dynamics with k opinions 1 3 converges in O(min{k, (n/ log n) q } log n) with high probability, provided that the bias of the 1
initial configuration is at least c min{2k, (n/ log n) 3 }n log n for some constant c > 0. Moreover, the authors provided a lower bound of Ω(k log n) on the convergence time to consensus, w.h.p., whenever the initial configuration is sufficiently balanced, that is, maxi∈[k] {c0 (i)} ≤ n/k + (n/k)1−ε for some ε > 0 and k ≤ (n/ log n)1/4 . 2-Choices. The work [10] compared the synchronous 3-Majority dynamics with the synchronous 2-Choices dynamics. The authors first proved a generic lower bound of Ω(min{k, n/ log n}) rounds to reach consensus starting from the initial perfectly balanced configuration, w.h.p. Furthermore, they proved that the 3-Majority dynamics works better in symmetric configurations (i.e., with no initial bias) when, e.g., maxi∈[k] {c0 (i)} = O(log n). In particular, the 3-Majority takes time at most O(n3/4 log7/8 n) to reach consensus w.h.p., regardless of any other hypothesis on the initial configuration, while the 2-Choices needs time Ω(n/ log n) whenever maxi∈[k] {c0 (i)} = O(log n). This was the first work to notice that, for a large number of opinions, the 3-Majority dynamics is polynomially (in k) faster than the 2-Choices dynamics. p The work [18] improved upon [6] and√showed that, for the 2-Choices with k = O( n/ log n) and for the 3-Majority with k = O(n1/3 / log n), the convergence time to consensus is O(k log n), with high probability. Notice that this upper bound is tight according to the lower bound by [6], at least as long as k ≤ (n/ log n)1/4 . Furthermore, the authors showed that the convergence time of the 3-Majority dynamics is O(n2/3 log3/2 n) with high probability, regardless of the number of opinions. Very recently, [19] almost tightly settled the complexity of both the 3-Majority and the 2-
4
Choices dynamics. The authors proved that, w.h.p., the 3-Majority dynamics reaches consensus √ √ in O(k log n) rounds whenever k = o( n/ log n), while it takes time O( n log2 n) for other values of k. Furthermore, √ [19] proved that plurality consensus is ensured w.h.p. as long as the initial count gap is ω( n log n). As for the 2-Choices, they showed that, w.h.p., the dynamics reaches consensus in O(k log n) rounds whenever k = o(n/ log2 n), whilep it takes time O(n log3 n) otherwise. Inpdensity notation, these plurality requirements are B0 = ω( log n/n) for 3-Majority and B0 = ω( α0 (1) log n/n) for 2-Choices.1 These results almost match the generic lower bound given by [10], up to logarithmic factors. Undecided-State Dynamics. We already introduced another well-known consensus dynamics, the Undecided-State. In the Undecided-State there is an extra opinion, the undecided opinion. The update rule works as follows: A node samples one neighbour u.a.r. and pulls its opinion. If the received opinion is different from the one it currently supports, the node becomes undecided. If the node is undecided, it just copies whatever opinion it receives. The Undecided-State has been studied both in the synchronous setting and in the population protocol model (asynchronous setting) [2, 12, 5, 15, 16, 1, 9, 3] and has often been considered to perform roughly the same as the 3-Majority dynamics. A special mention goes to [5], which analysed the Undecided-State dynamics in the synchronous setting and proved that it reaches consensus in γ0 1/3 ). O( m 2 log n) rounds with high probability, as long as the number of opinions k = O((n log n) 0
They also proved a matching lower bound up to logarithmic factors as long as k = O((n log n)1/6 ). Prior to this work, this was the only result on the Undecided-State dynamics that provided strong and tight bounds, i.e., bounds that hold for every initial configuration. A recent result √ of Cooper et al. [14] shows that the Undecided-State reaches consensus in O(min{k, n} log n) rounds with high probability, regardless of the number of opinions. Asynchronous setting. The only works that analysed the 3-Majority dynamics in the asynchronous setting are [13, 11]. In [11], the authors consider the binary opinion case and show that the convergence √ time of the asynchronous 3-Majority dynamics is O(n log n) rounds, w.h.p., and that a bias of Θ( n log n) is sufficient to ensure plurality consensus, w.h.p. The authors of [13] showed that the convergence time is O(min{kn log2 n, n3/2 log3/2 n}), w.h.p., regardless √ of the number of initial opinions. They also provided a generic lower bound of Ω(min{kn, n3/2 / log n}) rounds to reach consensus (starting from balanced configurations), w.h.p. The work [13] (which came before [19]) was the first to establish exactly how the linear-in-k dependence in the consensus time of the 3-Majority √ dynamics breaks when the number of opinions exceeds n, in which case the consensus time is sublinear in the number of opinions. The reader may observe that the asynchronous setting has the same qualitative convergence time as the synchronous model, up to a multiplicative factor n. This is to be expected: In the asynchronous setting, in a round, only one agent (sampled u.a.r.) updates its state, and hence we need roughly n rounds to activate all agents at least once (up to polylogarithmic factors). For processes with small variance (smaller than that of the voter model), convergence times from the synchronous to the asynchronous setting usually scale with such a factor. Note that this is not true for processes with large variance [8].
3
Proof Overview
The proof idea behind the upper bound of theorem 1.1 is simple. For both 3-Majority and 2-Choices, it is possible to compute the expectation of αt+1 (i) conditional on the configuration 1
This √ is the only example of initial bias that gets “close enough” to what we require in theorem 1.2, but with an extra log n factor.
5
α(t) at the previous round, and to show that E[αt+1 (i) | α(t) ] = αt (i) (1 + αt (i) − γt ) . As long as we have an unbalanced configuration, say mt ≥ 2γt , and i⋆ is an opinion with density mt , then E[αt+1 (i⋆ ) | α(t) ] = mt (1 + mt − γt ) ≥ mt (1 + 12 mt ). Assuming that mt = Ω(m0 ), the density of such an opinion grows at every round by a multiplicative factor of (1 + 12 m0 ) in expectation. Thus, if the configuration remains unbalanced up to consensus, then the convergence time is O(m−1 0 log n), which is the desired upper bound. Otherwise, let τb be the first round in which the configuration becomes balanced, i.e., γτb ≥ mτb /2. τb = O(m−1 0 log n) since the monochromatic configuration is balanced. We can apply Shimizu and Shiraga’s result to the configuration at round τb , which is balanced, to obtain consensus in Õ(γτ−1 ) = Õ(m−1 0 ) additional b rounds. To make this argument rigorous, we concentrate around the expected growth of mt in the unbalanced phase by using the Freedman inequality for martingales as in [19]. The lower bound of theorem 1.1 is also built on a lemma in [19]. In fact, they show that for any opinion i C Pr inf{t : αt (i) > c α0 (i)} ≤ ≤ α0 (i)
exp −Ω(nα0 (i)2 ) , exp(−Ω(nα0 (i))),
(
for 3-Majority, for 2-Choices,
hence, for m0 large enough, the probability that any opinion grows by a constant factor in O(m0−1 ) rounds is negligible, and thus the convergence time is Ω(m−1 0 ) w.h.p. We take care of the case of small m0 by a coupling argument: if m0 is too small, we couple the process with another process, using the same randomness, in which some opinions are merged so that the maximum initial density satisfies the condition. By symmetry and monotonicity, the convergence time of the original process is at least that of the coupled process, which is Ω(m−1 0 ) w.h.p. by the previous argument. We also extend our analysis to the plurality consensus problem. The idea is very similar to the one for consensus time. We know that the bias between the largest and any remaining opinion densities grows at every round by a multiplicative factor of (1+ 12 m0 ) in expectation, as long as the configuration is unbalanced. Thus, with the same Freedman inequality argument, we prove that the condition on the bias in theorem 1.2 is preserved until the configuration becomes balanced, and then we apply Shimizu and Shiraga’s result to the balanced configuration to obtain plurality consensus. The argument is slightly more technical for 2-Choices, as the bias growth depends on the scaled bias ηt (i, j) = √ δt (i,j) rather than the bias δt (i, j), and we need to show that max{αt (i),αt (j)}
the condition on η0 (i, j) in theorem 1.2 is preserved until the configuration becomes balanced. To do this, we show that the bias grows at a higher rate than max{αt (i), αt (j)}. In fact δt (i, j) grows at every round by a multiplicative factor of (1 + αt (i) + αt (j) − γt ) in expectation, while max{αt (i), αt (j)} grows by a multiplicative factor of (1 + max{αt (i), αt (j)} − γt ) in expectation.
4
Model and Notation
We consider the complete graph on V = [n] with self-loops. Each vertex holds an opinion in C = [k], where 2 ≤ k ≤ n. At round t, let αt (i) denote the fraction of vertices holding opinion i, and write α(t) = (αt (i))i∈C . We use mt = ∥α(t) ∥∞ = max αt (i),
γt = ∥α(t) ∥22 =
i∈C
X
αt (i)2 .
i∈C
For two opinions i, j, define the signed bias δt (i, j) = αt (i) − αt (j). For 2-Choices we also use the scaled bias δt (i, j) ηt (i, j) = p . max{αt (i), αt (j)} 6
3-Majority dynamics. In each round every vertex samples three vertices independently and uniformly from V . It adopts the majority opinion among the three samples; if all three sampled opinions are different, the tie is broken uniformly among them. 2-Choices dynamics. In each round every vertex samples two vertices independently and uniformly from V . If the two sampled vertices have the same opinion, the vertex adopts that opinion; otherwise it keeps its current opinion. Notation. We denote the consensus time by τcons = inf{t ≥ 0 : ∃i ∈ C such that αt (i) = 1}, and the first balancing time by τb = inf{t ≥ 0 : γt ≥ mt /2}. We use the convention inf ∅ = ∞. We say an event happens with high probability (w.h.p.) if it happens with probability at least 1 − n−2 .
5
Analysis: Consensus time
In this section we state and prove a formal version of theorem 1.1.
5.1
Upper bound.
Theorem 5.1 (Consensus-time upper bound). Consider any initial configuration on the complete graph with self-loops, and let m0 = ∥α(0) ∥∞ . There is a universal constant C > 0 such that the following bounds hold with high probability. For 3-Majority, ( √ Cm−1 if m0 ≥ C log n/ n, 0 log n, τcons ≤ √ C n log2 n, otherwise. For 2-Choices, Cm−1 0 log n, Cn log3 n,
(
if nm0 ≥ C(log n)2 , otherwise. √ In particular, 3-Majority reaches consensus in Õ(min{m−1 0 , n}) rounds and 2-Choices reaches consensus in Õ(m−1 0 ) rounds, as stated in theorem 1.1. τcons ≤
In the following lemma, we show that from an unbalanced configuration, the process reaches a balanced configuration in O(m−1 0 ) rounds. We also show that, up to that time, mt = Ω(m0 ). Lemma 5.2 (Fast balancing from the infinity norm). Recall the balancing time τb from section 4. There are universal constants C, c > 0 such that the following holds. For 3-Majority, if nm20 ≥ C log n, then with probability at least 1 − n−5 there is a time s ≤ Cm−1 0 such that s = τb ,
mt ≥ c m0
for every 0 ≤ t ≤ s.
For 2-Choices, the same statement holds under the condition nm0 ≥ C(log n)2 . Proof. If γ0 ≥ m0 /2, there is nothing to prove, taking s = 0. Otherwise we run the process in dyadic phases. Fix a phase scale x ≥ m0 and a phase-starting round r with mr ≥ x and γr < mr /2. Let σ = inf{u ≥ r : γu ≥ mu /2 or mu ≥ 2x or mu < x/2} and let H = ⌈20/x⌉. For u < σ, choose a plurality opinion iu by deterministic tie-breaking, so that αu (iu ) = mu . Since iu is Fu -measurable, item 1 of lemma 9.5 gives Eu [αu+1 (iu )] = mu (1 + mu − γu ) ≥ mu (1 + mu /2). 7
Thus, while u < σ,
Eu [αu+1 (iu )] − mu ≥ m2u /2 ≥ x2 /8.
Moreover, mu+1 ≥ αu+1 (iu ). Define the stopped martingale, for 0 ≤ q ≤ H, Mq =
r+q−1 X
1{u<σ} αu+1 (iu ) − Eu [αu+1 (iu )] .
u=r
By item 1 of lemma 9.6, the lower-tail increments Eu [αu+1 (iu )] − αu+1 (iu ) satisfy a one-sided Bernstein condition with D = 1/n. During the phase, mu < 2x and γu < mu /2 < x, so the variance parameter is at most 2x/n, 6x2 /n,
(
sx =
for 3-Majority, for 2-Choices.
Applying corollary 9.2 to −Mq with h = x/2 yields exp −Ω(nx2 ) , for 3-Majority, exp(−Ω(nx)), for 2-Choices.
(
P[∃q ≤ H : Mq ≤ −x/2 | Fr ] ≤
On the complement of this event, the phase cannot end by the condition mu < x/2: summing the inequalities mu+1 − mu ≥ αu+1 (iu ) − mu would force Mq ≤ −x/2 at the first such time. If the phase has not ended by time r + H, then every round before r + H has drift at least x2 /8, and hence mr+H ≥ mr + Hx2 /8 + MH > 2x, again a contradiction. Therefore, except with the displayed probability, the phase ends within H = O(1/x) rounds either by hitting τb with mτb ≥ x/2, or by reaching mass at least 2x. Starting with x = m0 and iterating over x, 2x, 4x, . . . until x ≥ 1/4, the total number of rounds is X O((2q m0 )−1 ) = O(m−1 0 ). q
If no earlier balanced time is reached, then the final doubling gives mt ≥ 1/2, which itself implies γt ≥ m2t ≥ mt /2. Thus t = τb and mt = Ω(m0 ). Moreover, on the same successful event, no phase ends through the stopping condition mu < x/2. Hence, throughout each phase and until the balancing time is reached, mu ≥ x/2 ≥ m0 /2. This gives the stated lower bound on mt for every t ≤ τb , after setting c = 1/2. The sum of the phase failure probabilities is at most n−5 after increasing C, under nm20 ≥ C log n for 3-Majority and nm0 ≥ C(log n)2 for 2-Choices. Now, we can complete the proof of theorem 5.1 by applying the Shimizu–Shiraga large-γ theorem from the random time τb , conditioned on the current configuration. Proof of theorem 5.1. Consider first either dynamics in the regime where its high-mass condition √ holds: m0 ≥ C log n/ n for 3-Majority, or nm0 ≥ C(log n)2 for 2-Choices. We condition on the event of lemma 5.2. At the balancing time s we have γs ≥ ms /2 = Ω(m0 ). √ In the 3-Majority case, by increasing C if necessary this gives γs ≥ CSS log n/ n, where CSS is the constant required by the Shimizu–Shiraga large-γ theorem. Applying that theorem from the random time s, conditioned on the current configuration, gives consensus in
O γs−1 log n ≤ O m−1 0 log n 8
additional rounds. For 2-Choices the same black-box theorem gives O(γs−1 log n) = O(m−1 0 log n) additional rounds in the high-mass regime nm0 ≥ C(log n)2 . √ If the 3-Majority high-mass condition fails, then m0 < C log n/ n, and the original Shimizu– √ Shiraga all-configuration bound gives the stated O( n log2 n) branch. For 2-Choices below nm0 ≥ C(log n)2 , we use the corresponding Shimizu–Shiraga norm-growth fallback, incurring their stated polylogarithmic loss.
5.2
Lower bound
In this section we state and prove a formal version of the lower bound in theorem 1.1. Theorem 5.3 (Consensus-time lower bound). Assume that the initial configuration is not already at consensus. There is a universal constant c > 0 such that, with probability at least 1 − n−3 , 3-Majority satisfies r n τcons ≥ c min m−1 , , 0 log n and 2-Choices satisfies τcons ≥ c min
m−1 0 ,
n . log n
The next lemma proves the elementary fact that merging opinions into a distinguished opinion can only help that distinguished opinion win. It will be helpful to give a lower bound on the consensus time when for some opinion i, its initial density α0 (i) is very small. Lemma 5.4 (Target-wise merging is monotone). Fix an opinion i and a set S ⊆ C with i ∈ S. e t be the process obtained from the initial configuration by identifying all opinions in S with Let X i, and leaving all other opinions unchanged. Let Xt be the original process. For both 3-Majority and 2-Choices, the processes can be coupled so that, for every round t, every vertex whose opinion e t . Consequently, in Xt belongs to S has opinion i in X e t (i) = 1]. PX [∃t ≤ T : αt (i) = 1] ≤ PXe [∃t ≤ T : α
Proof. Use the same sampled vertices in the two processes, and use the same tie-breaking random variable in 3-Majority. Assume inductively that the target indicator in the merged process dominates the indicator that the original opinion lies in S. For 3-Majority, replacing a sampled opinion outside the target by the target cannot decrease the probability that the majority-or-tie rule outputs the target: with zero target samples the output is outside, with one target sample the target is selected exactly in the all-distinct tie case, and with at least two target samples the merged process selects the target. For 2-Choices, if the vertex is already in the target then the only way to leave the target is to sample two equal outside opinions; after merging this event can only become less likely. If the vertex is outside the target, it enters the target only by sampling two target opinions, and this event can only become more likely after merging. This gives the coupling step by step. Now we can complete the proof of theorem 5.3 by applying lemma 9.7 from [19] to the merged process. The lemma states that if α0 (i) is large enough, it takes α0 (i)−1 rounds to increase by a constant multiplicative factor, and therefore to reach mass 1. Proof of theorem 5.3. We give the argument for a generic threshold a⋆ and then substitute the two values. Put a = max{m0 , a⋆ }. 9
If a > 1/4, the claimed lower bound is a positive constant after choosing c small enough, and it follows from the assumption that the initial configuration is not already at consensus. Hence assume a ≤ 1/4. Fix a possible winning opinion i with α0 (i) > 0. If α0 (i) ≥ a⋆ , let Si = {i}. Otherwise, add opinions to Si , starting from {i}, until its total initial mass first reaches a⋆ . By minimality, if ei = a
X
α0 (j),
j∈Si
then
ei ≤ a⋆ + m0 ≤ 2a. a⋆ ≤ a
Consider the process in which all opinions in Si are merged into i at time 0. By lemma 5.4, the probability that the original process reaches consensus on i by time T is at most the probability that, in this merged process, opinion i reaches mass 1 by time T . ei ≤ 2a ≤ 1/2, reaching mass 1 forces Let c↑α > 0 be the fixed constant in lemma 9.7. Since a ↑ the stopping time τi to occur. By lemma 9.7, there is a constant c0 > 0 such that for every ei T ≤ c0 /a
we have
e2i ) , for 3-Majority, exp −Ω(na ei )), for 2-Choices. exp(−Ω(na
(
P[τi↑ ≤ T ] ≤
ei ≤ 2a, this time is at most c0 /a ei . Choose T = c/(2a) with c ≤ c0 . Since a For 3-Majority set s log n . a⋆ = A n 2
ei ≥ a⋆ , and the failure probability for this fixed i is at most n−Ω(A ) . For 2-Choices set Then a
a⋆ = A
log n , n
and the failure probability for this fixed i is at most n−Ω(A) . Taking A large enough and union-bounding over at most n initially present opinions gives probability at most n−3 that any opinion reaches consensus before time T . The displayed lower bounds follow from T = Θ(1/ max{m0 , a⋆ }).
6
Analysis: Plurality Consensus
In this section we prove theorem 1.2. In the next lemma, we show that the bias between the plurality opinion and any other opinion is preserved until the balancing time τb . For 2-Choices, we show that the scaled bias ηt (i, j) is preserved until the balancing time τb , which is a stronger condition. Lemma 6.1 (Plurality bias up to the balancing time). Assume that α0 (1) > α0 (2) ≥ · · · ≥ α0 (k),
m0 = α0 (1),
B0 = α0 (1) − α0 (2).
Under the assumptions of theorem 1.2, with probability at least 1 − n−4 , at the time s = τb given by lemma 5.2, opinion 1 is still the plurality. Moreover, for every j ̸= 1, in 3-Majority, δs (1, j) ≥ cB0 and, in 2-Choices,
δs (1, j)2 B2 ≥c 0, ms m0
for a universal constant c > 0. 10
Proof. Write B = B0 . Let Cb and cb be the constants from lemma 5.2, put l
m
S = Cb m−1 , 0
ρ = c/2,
and let Eb be the successful event supplied by lemma 5.2. Explicitly, on this event, τb ≤ S,
mt ≥ c m0
for every 0 ≤ t ≤ τb .
Moreover, Pr[Ebc ] ≤ n−5 . 3-Majority. Define the stopping times τ∆ = inf{t ≥ 0 : ∃ℓ ̸= 1 such that δt (1, ℓ) ≤ B/2}, We prove that
τm = inf{t ≥ 0 : αt (1) ≤ ρm0 }.
Pr[τ∆ ≤ τb ] ≤ n−4 .
(1)
The 3-Majority part follows immediately from equation (1), since if s = τb < τ∆ , then δs (1, j) > B/2 for every j ̸= 1. Fix j ̸= 1 and set σ = min{τb , τ∆ , τm , S}. For t < σ, opinion 1 is the unique plurality, and hence αt (1) = mt . Moreover, t < τb implies γt < mt /2, and so at := αt (1) + αt (j) − γt ≥ αt (1) − γt > αt (1)/2. For t ≥ σ set at = 0. Let G0 = 1 and Gt+1 = Gt (1 + at ). Finally define Zt =
δt∧σ (1, j) . Gt
By item 2 of lemma 9.5, for t < σ, Et [δt+1 (1, j)] = δt (1, j)(1 + at ), while for t ≥ σ both the numerator and Gt are stopped. Hence (Zt )t≥0 is a martingale. We now bound the lower tail of this martingale. For t < σ, Zt − Zt+1 =
Et [δt+1 (1, j)] − δt+1 (1, j) . Gt+1
By item 2 of lemma 9.6, Et [δt+1 (1, j)] − δt+1 (1, j) satisfies a one-sided Bernstein condition with parameters 2 2(αt (1) + αt (j)) and . n n Since Gt+1 is Ft -measurable, scaling by 1/Gt+1 preserves the one-sided Bernstein condition with both parameters scaled in the standard way. Thus the increment Zt − Zt+1 satisfies a one-sided Bernstein condition with boundedness parameter at most 2/n and predictable variance proxy vt = 1{t<σ}
2(αt (1) + αt (j)) 8at ≤ , 2 nGt+1 nG2t+1
where the last inequality uses at > mt /2 and αt (1) + αt (j) ≤ 2mt on {t < σ}, while both sides are zero on {t ≥ σ}. The variance proxies telescope: X t<S
8 X at 8X 1 1 ≤ − 2 n t<S Gt+1 n t<S Gt Gt+1
vt ≤
11
≤
8 . n
Applying corollary 9.4 to the martingale Xt = Z0 − Zt with h = B/2, D = 2/n, and v = 8/n gives Pr[∃t ≤ S : Z0 − Zt ≥ B/2] ≤ exp −Ω(nB 2 ) . (2) If τ∆ ≤ min{τb , τm , S} and opinion j is one of the opinions attaining the minimum in the definition of τ∆ , then, at time σ = τ∆ , Z0 − Zσ = δ0 (1, j) −
δσ (1, j) B ≥B− = B/2, Gσ 2
because δ0 (1, j) ≥ B and Gσ ≥ 1. Taking a union bound over the at most n − 1 competing opinions and using equation (2), we get
Pr[τ∆ ≤ min{τb , τm , S}] ≤ n exp −Ω(nB 2 ) . On Eb , if t < τ∆ ∧ τb then opinion 1 is the plurality, and therefore αt (1) = mt ≥ c m0 > ρm0 . Thus τm cannot occur before τ∆ ∧ τb on Eb , and τb ≤ S there. Consequently,
Pr[τ∆ ≤ τb ] ≤ Pr[Ebc ] + Pr[τ∆ ≤ min{τb , τm , S}] ≤ n−5 + n exp −Ω(nB 2 ) . Since the 3-Majority plurality assumption gives B = ω( log n/n), the last display is at most n−4 for all sufficiently large n. This proves the 3-Majority part. 2-Choices. Put B q= √ 2 m0 p
and define the global scaled-bias loss time τη = inf{t ≥ 0 : ∃ℓ ̸= 1 such that ηt (1, ℓ) ≤ q}. Let
σ0 = min{τb , τη , S}.
For t < σ0 , all scaled biases ηt (1, ℓ) are positive, and hence opinion 1 is the unique plurality: αt (1) = mt . It also holds that γt < αt (1)/2. Define (
bt =
αt (1) − γt , t < σ0 , 0, t ≥ σ0 ,
Then At =
H0 = 1,
Ht+1 = Ht (1 + bt ).
αt∧σ0 (1) Ht
is a martingale by item 1 of lemma 9.5. Let τA = inf{t ≥ 0 : At ≥ 2m0 }. We first show that this stopping time is unlikely before the scaled bias is lost. Let σA = min{σ0 , τA } and stop At at σA . For t < σA , At < 2m0 ,
γt < αt (1)/2,
and so the 2-Choices variance proxy from item 1 of lemma 9.6, after scaling by the Ft -measurable factor 1/Ht+1 , is at most ut = 1{t<σA }
αt (1)(αt (1) + γt ) 6m20 . ≤ 1{t<σA } 2 n nHt+1 12
Since S = O(m−1 0 ), for a universal constant CA , X
ut ≤ CA
t<S
m0 . n
Moreover, the corresponding boundedness parameter is at most 1/n. Notice that A0 = m0 . Hence, on the event {τA ≤ σ0 }, we have σA = τA ≤ S and AτA ∧σA − A0 = AτA − m0 ≥ m0 , because AτA ≥ 2m0 by definition of τA . Therefore {τA ≤ σ0 } ⊆ {∃t ≤ S : At∧σA − A0 ≥ m0 } . Applying corollary 9.4 to the stopped martingale At∧σA − A0 with h = m0 gives Pr[τA ≤ σ0 ] ≤ exp(−Ω(nm0 )). Now fix j ̸= 1 and define Set
(
at =
(3)
σ = min{τb , τη , τA , S}.
αt (1) + αt (j) − γt , t < σ, 0, t ≥ σ,
G0 = 1,
Gt+1 = Gt (1 + at ).
Since at = bt + αt (j) ≥ bt for t < σ, we have Gt ≥ Ht for every t ≤ σ. Also, Dt =
δt∧σ (1, j) Gt
is a martingale, again by item 2 of lemma 9.5. For t < σ, opinion 1 is the plurality and the configuration is unbalanced, so αt (1) = mt ,
γt < αt (1)/2,
αt (j) ≤ αt (1).
Since t < τA , we also have αt (1) = At Ht < 2m0 Ht ≤ 2m0 Gt .
(4)
The 2-Choices variance proxy from item 2, after scaling by 1/Gt+1 , is wt = 1{t<σ}
(αt (1) + αt (j))(αt (1) + αt (j) + γt ) . nG2t+1
Using the preceding bounds and equation (4), wt ≤ 1{t<σ}
20m20 . n
Since S = O(m−1 0 ), we obtain that, for a universal constant CD , X
wt ≤ C D
t<S
m0 . n
√ The boundedness parameter is at most 2/n. Let cη = 1 − 1/ 2. Applying corollary 9.4 to the martingale D0 − Dt , with h = cη B and v = CD m0 /n, yields nB 2 Pr[∃t ≤ S : D0 − Dt ≥ cη B] ≤ exp −Ω m0 13
!!
,
(5)
where we used B ≤ m0 . If τη < min{τb , τA , S} and opinion j realises the minimum in the definition of τη , then either δτη (1, j) < 0, in which case Dτη < 0, or δτη (1, j) ≥ 0, in which case q B q B q δτη (1, j) ≤ q ατη (1) ≤ √ 2m0 Hτη = √ Hτη . 2 m0 2
Since Gτη ≥ Hτη ≥ 1, in both cases D τη =
δτη (1, j) B ≤√ . Gτη 2
As D0 = δ0 (1, j) ≥ B, the event {τη < min{τb , τA , S}} forces D0 − Dτη ≥ cη B for one of the at most n − 1 choices of j. By equation (5) and a union bound, nB 2 Pr[τη < min{τb , τA , S}] ≤ n exp −Ω m0
!!
(6)
.
On Eb , τb ≤ S. Combining this with equations (3) and (6), Pr[τη ≤ τb ] ≤ n
−5
nB 2 + exp(−Ω(nm0 )) + n exp −Ω m0
!!
.
The 2-Choices assumptions in theorem 1.2 give nm0 = ω((log n)2 ) and nB 2 /m0 = ω(log n), so the last display is at most n−4 for all sufficiently large n. Thus, with probability at least 1 − n−4 , s = τb < τη . At that time, for every j ̸= 1, B ηs (1, j) > √ , 2 m0 opinion 1 is still the plurality, and therefore δs (1, j)2 B2 = ηs (1, j)2 ≥ . ms 4m0 This proves the 2-Choices part, and the lemma follows with a universal constant c > 0. Now we can complete the proof of theorem 1.2 by applying the Shimizu–Shiraga pluralityconsensus theorem from the random time s = τb . Conditioned on the current configuration, lemma 6.1 ensures that its conditions are satisfied. Proof of theorem 1.2. At the time s = τb above, the configuration is balanced and ms = Ω(m0 ). In 3-Majority, s δs (1, j) ≥ cB0 = ω
log n n
for every j ̸= 1.
In 2-Choices, the normalized bound from lemma 6.1 gives s
δs (1, j) ≥ ω
ms log n n
for every j ̸= 1.
Hence the plurality-consensus theorem of Shimizu and Shiraga can be applied from the random balanced configuration at time s, conditioned on the current state. We use the standard highprobability form of their theorem with the constants in the assumptions chosen so that the conditional failure probability is at most n−4 . It gives consensus on opinion 1 within O(m−1 0 log n) additional rounds. Combining this with the n−4 failure probability in lemma 6.1 and with lemma 5.2, and then increasing constants if necessary, the total failure probability is at most n−2 . Since lemma 5.2 gives s = O(m−1 0 ), this proves theorem 1.2. 14
7
Conclusion and future directions
We identified the maximum initial opinion density m0 = ∥α(0) ∥∞ as the parameter governing the consensus time of both 3-Majority and 2-Choices on the complete graph. In particular, √ 3-Majority reaches consensus in Θ̃(min{m−1 0 , n}) rounds, while 2-Choices reaches consensus in Θ̃(m−1 0 ) rounds. Thus the convergence time is controlled by a local feature of the initial configuration, rather than by global parameters such as the number of opinions or the squared ℓ2 -norm γ0 . This gives substantial improvements over the bounds of Shimizu and Shiraga [19] for unbalanced configurations, where m0 can be much larger than γ0 . For 2-Choices, the improvement √ can be as large as a factor n; for 3-Majority, it can be as large as a factor n1/4 . It would be natural to investigate whether the same infinity-norm parameterisation extends to asynchronous 3-Majority and 2-Choices. Since a single asynchronous activation has the same local transition probabilities as one vertex update in the synchronous process, one possible route is to adapt the existing ℓ2 -norm analysis in the asynchronous setting. If such an analogue is available, our reduction from unbalanced to balanced configurations should yield the corresponding asynchronous bounds up to the expected factor n in the time scale. This work also exposes configurations in which 3-Majority is slower than the Undecided-State, giving a first explicit gap between these two dynamics. More precisely, 3-Majority can be slower by a factor m0 /γ0 , which becomes substantial for unbalanced configurations. It would be interesting to build on the analyses of [5, 14] to determine whether the consensus time of the Undecided-State is Θ̃(γ0 /m20 ) for arbitrary numbers of opinions, which would extend this gap beyond the currently known range.
8
Acknowledgements
The author thanks Francesco d’Amore and Emanuele Natale for helpful discussions and feedback on this work. This work has been supported by the AID INRIA-DGA project n°2023000872 “BioSwarm”.
9
Tools
We shall use the following results concerning (super)martingales. Theorem 9.1 (Freedman’s inequality; [17]). Let (Mt )t≥0 be a martingale with M0 = 0 and P increments ∆t = Mt − Mt−1 ≤ B almost surely. Let Vt = ts=1 E[∆2s | Fs−1 ]. Then, for every λ, v > 0, ! λ2 Pr[∃t : Mt ≥ λ and Vt ≤ v] ≤ exp − . 2(v + Bλ/3) Corollary 9.2 (Corollary 3.8 in [19]). Let (Xt )t∈N0 be a supermartingale associated with the natural filtration (Ft )t∈N0 . Suppose that, for every t ≥ 1, the difference Xt − Xt−1 conditioned on Ft−1 satisfies one-sided (D, s)-Bernstein condition. Then, for any h > 0, we have !
h2 /2 Pr t ≤ T, Xt − X0 ≥ h ≤ exp − . T s + (hD)/3 h
∃
i
Theorem 9.3 (Ville’s inequality; [20]). Let (Lt )t≥0 be a nonnegative supermartingale. Then, for every T ∈ N0 and every a > 0, Pr[∃t ≤ T : Lt ≥ a] ≤ 15
E[L0 ] . a
Corollary 9.4 (Predictable-variance Freedman inequality under one-sided Bernstein condition). Let (Xt )t∈N0 be a supermartingale associated with the natural filtration (Ft )t∈N0 . Suppose that, for every t ≥ 1, the difference Xt − Xt−1 conditioned on Ft−1 satisfies a one-sided (Dt , st )-Bernstein condition, where Dt , st are Ft−1 -measurable, Dt ≤ D, and T X
st ≤ v
t=1
almost surely. Then, for any h > 0, !
h2 /2 Pr[∃t ≤ T : Xt − X0 ≥ h] ≤ exp − . v + hD/3 Proof. Fix 0 < λ < 3/D and put cλ =
λ2 /2 . 1 − λD/3
By Dt ≤ D and the one-sided Bernstein condition, E[exp(λ(Xt − Xt−1 )) | Ft−1 ] ≤ exp(cλ st ). Hence Lt = exp λ(Xt − X0 ) − cλ
t X
!
ss
s=1
is a nonnegative supermartingale. By theorem 9.3, Pr[∃t ≤ T : Xt − X0 ≥ h] ≤ exp(−λh + cλ v), using
s=1 ss ≤ v almost surely. Choosing
PT
λ=
h v + hD/3
gives
!
h2 /2 . exp − v + hD/3
Lemma 9.5 (Lemma 4.1 in [19]). Consider the quantities defined in section 4 for 3-Majority or 2-Choices. Then, we have the following for any t ≥ 1: (i) For any opinion i ∈ [k], we have Et−1 [αt (i)] = αt−1 (i)(1 + αt−1 (i) − γt−1 ), (α
Vart−1 [αt (i)] ≤
t−1 (i)
n αt−1 (i)(αt−1 (i)+γt−1 ) n
for 3-Majority, for 2-Choices.
(ii) For any two distinct opinions i, j ∈ [k], we have Et−1 [δt (i, j)] = δt−1 (i, j)(1 + αt−1 (i) + αt−1 (j) − γt−1 ), Vart−1 [δt (i, j)] ≤
2 n (αt−1 (i) + αt−1 (j))
for 3-Majority,
1 (α
for 2-Choices.
n
t−1 (i) + αt−1 (j))(αt−1 (i) + αt−1 (j) + γt−1 )
16
Lemma 9.6 (Lemma 4.2 in [19]). Consider the quantities defined in section 4 for 3-Majority or 2-Choices. Then, we have the following for any t ≥ 1: (i) For any opinion i ∈ [k], both αt (i) −Et−1 [αt (i)] and Et−1 [αt (i)] − αt (i) conditioned on round t − 1 satisfy the one-sided n1 , s -Bernstein condition, where (α
s=
t−1 (i)
for 3-Majority, for 2-Choices.
n αt−1 (i)(αt−1 (i)+γt−1 ) n
(ii) For any two distinct opinions i, j ∈ [k], both δt (i, j)−E t−1 [δt (i, j)] and Et−1 [δt (i, j)]−δt (i, j), 2 conditioned on round t − 1, satisfy the one-sided n , s -Bernstein condition, where s=
2 n (αt−1 (i) + αt−1 (j))
for 3-Majority,
1 (α
for 2-Choices.
n
t−1 (i) + αt−1 (j))(αt−1 (i) + αt−1 (j) + γt−1 )
Lemma 9.7 (Item 1 of Lemma 4.4 in [19]). Fix an opinion i ∈ [k]. Let c↑α = 1/10 and define τi↑ = inf{t ≥ 0 : αt (i) ≥ (1 + c↑α )α0 (i)}. For any constant ε ∈ (0, 1), let c↑ =
(1 − ε)c↑α (1 + c↑α )2
.
Then,
Pr τi↑ ≤
c↑ ≤ α0 (i)
(
exp −Ω(nα0 (i)2 ) , exp(−Ω(nα0 (i))),
for 3-Majority, for 2-Choices.
References [1] Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. Fast convergence of k-opinion undecided state dynamics in the population protocol model. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 13–23. ACM, 2023. doi:10.1145/3583668.3594589. [2] Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Comput., 21(2):87–102, 2008. URL: https: //doi.org/10.1007/s00446-008-0059-z, doi:10.1007/S00446-008-0059-Z. [3] Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. Fast consensus via the unconstrained undecided state dynamics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 3417–3429. SIAM, 2022. doi:10.1137/1.9781611977073.135. [4] Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. SIGACT News, 51(1):58–104, March 2020. doi:10.1145/3388392.3388403.
17
[5] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality consensus in the gossip model. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 371–390, 2016. doi:10. 1137/1.9781611974331.ch28. [6] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293–306, August 2017. doi:10.1007/s00446-016-0289-4. [7] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 620–635. SIAM, 2016. URL: https: //doi.org/10.1137/1.9781611974331.ch46, doi:10.1137/1.9781611974331.CH46. [8] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. The minority dynamics and the power of synchronicity. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4155–4176. SIAM, 2024. doi:10.1137/1.9781611977912.144. [9] Petra Berenbrink, Felix Biermeier, and Christopher Hahn. Undecided state dynamics with stubborn agents. CoRR, abs/2406.07335, 2024. URL: https://doi.org/10.48550/arXiv. 2406.07335, arXiv:2406.07335, doi:10.48550/ARXIV.2406.07335. [10] Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik MallmannTrenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 335–344. ACM, 2017. doi:10.1145/3087801.3087817. [11] Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the hierarchy of distributed majority protocols. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, 26th International Conference on Principles of Distributed Systems, OPODIS 2022, December 13-15, 2022, Brussels, Belgium, volume 253 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2022.23, doi: 10.4230/LIPICS.OPODIS.2022.23. [12] Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A tight analysis of the parallel undecided-state dynamics with two colors. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 28:1–28:15. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.28, doi:10.4230/LIPICS.MFCS.2018.28. [13] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-majority dynamics with many opinions. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4095–4131. SIAM, 2025. doi:10.1137/1.9781611978322.140. [14] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Undecided state dynamics with many opinions, 2026. URL: https://arxiv.org/ abs/2603.02636, arXiv:2603.02636. 18
[15] Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a non-linear opinion dynamics with noisy interactions - (extended abstract). In Andréa Werneck Richa and Christian Scheideler, editors, Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings, volume 12156 of Lecture Notes in Computer Science, pages 255–272. Springer, 2020. doi:10.1007/978-3-030-54921-3\_15. [16] Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a nonlinear opinion dynamics with noisy interactions. Swarm Intell., 16(4):261–304, 2022. URL: https://doi.org/10.1007/s11721-022-00217-w, doi:10.1007/S11721-022-00217-W. [17] David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975. doi:10.1214/aop/1176996452. [18] Mohsen Ghaffari and Johannes 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), pages 305–313, 2018. doi:10.1145/3212734.3212738. [19] Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. CoRR, abs/2503.02426, 2025. arXiv:2503.02426, doi:10.48550/arXiv.2503.02426. [20] Jean Ville. Étude critique de la notion de collectif. Gauthier-Villars, 1939. URL: http: //eudml.org/doc/192893.
19