Consensus Time in 3-Majority and 2-Choices Is Determined by the Maximum Initial Opinion Density

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 3-Majority 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.