Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes the convergence time for consensus in 3-Majority and 2-Choices dynamics on complete graphs, revealing that the maximum initial opinion density is the critical parameter influencing this time. Unlike previous work that provided only weak bounds, the authors derive tight upper and lower bounds that hold for all initial configurations, demonstrating that 3-Majority reaches consensus in Θ(min{α(0) -1 ∞, √n}) rounds and 2-Choices in Θ(α(0) -1 ∞) rounds with high probability. This work clarifies the dynamics of opinion formation by showing that local parameters, rather than global ones, dictate convergence times.
Consensus time in opinion dynamics is tightly governed by local opinion density, not global configurations.
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 $\alpha$ (0) be the initial opinion-frequency vector, and denote by ___$\alpha$ (0) ___ $\infty$ its maximum entry. We show that 3-Majority reaches consensus in $\Theta$(min{___$\alpha$ (0) ___ -1 $\infty$ , $\sqrt$ n}) rounds w.h.p., while 2-Choices reaches consensus in $\Theta$(___$\alpha$ (0) ___ -1 $\infty$ ) 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 ${\ell}$ 2 norm of the initial opinion distribution, but rather by the''local''parameter ___$\alpha$ (0) ___ $\infty$ , the maximum initial opinion density.