Simple Dynamics for Plurality Consensus
\(n\) anonymous nodes each support one of \(k\) colors. In every round each node samples three nodes uniformly at random (with repetition, possibly itself) and adopts the majority color among them, or the first one if all three differ. If some color \(m\) leads every other color by a sufficiently large bias \(s\), the process reaches consensus on \(m\). The paper proves that this takes \(O(\lambda \log n)\) rounds w.h.p. whenever \(c_m \ge n/\lambda \) and \(s \ge c\sqrt{\lambda n\log n}\) (Theorem 24), that \(\Omega (k\log n)\) rounds are needed from balanced configurations, that 3-majority is essentially the only 3-input rule that solves plurality consensus, and that sampling \(h {\gt} 3\) nodes speeds the process up by at most a factor \(O(h^2)\).
The upper bound (Section 3), including the headline bound \(O(\min \{ k,(n/\log n)^{1/3}\} \log n)\) of Corollary 26, is fully formalized, with no sorry, on the finite probability layer of the shared dynamics package: all randomness is uniform over finite types, multi-round probabilities are iterates of a finite Markov kernel, and the concentration inequalities (Chernoff, Hoeffding, Bernstein) are proved from scratch. The lower bounds of Section 4 are formalized as well, with two exceptions where the paper’s argument does not go through: the \(\Omega (k\log n)\) bound is proved for \(k \le n^{1/4-\delta }\) rather than up to \((n/\log n)^{1/4}\), and part (a) of Theorem 4.8 (Theorem 36) leaves open rules with \(\Delta _r, \Delta _b \le 1\). Observation 3.9 (an adversary) is not formalized.
1 The model
A coloring is a map \(x \colon [n] \to [k]\). The number of nodes of color \(j\) is \(c_j = |\{ v : x(v) = j\} |\), and \(\sum _j c_j = n\). The vector \(c = (c_1,\dots ,c_k)\) is the paper’s \(k\)-color distribution (\(k\)-cd).
A 3-input rule is a map \(f \colon [k]^3 \to [k]\) with \(f(a,b,c) \in \{ a,b,c\} \). The 3-majority rule is \(\mathrm{maj}_3(a,b,c) = b\) if \(b = c\) and \(a\) otherwise; it returns the majority color, and the first color if all three differ.
A round is a map \(r \colon [n] \to [n]^3\) (the three samples of every node), drawn uniformly. The next coloring under rule \(f\) is \(v \mapsto f(x(r_v^1), x(r_v^2), x(r_v^3))\). The process after \(T\) rounds folds this step over \(T\) independent uniform rounds.
\(x\) is in consensus on \(m\) if every node has color \(m\), i.e. \(c_m = n\). For every 3-input rule, consensus is absorbing.
The process with rule \(f\) is the finite Markov kernel on colorings whose row at \(x\) is the law of one round of \(f\) from \(x\). Its \(T\)-step event probabilities are the expectations over \(T\) independent uniform rounds.
2 The next expected coloring
The new count of color \(j\) is a sum of \(n\) independent indicators, one per node. Under 3-majority, a node adopts \(j\) with probability \(x_j^2 + x_j(1 - \sum _h x_h^2)\), where \(x_h = c_h/n\).
The three samples are independent with law \((x_h)_h\). Summing the indicator of \(\mathrm{maj}_3(a,b,c) = j\) first over \(c\), then \(b\), then \(a\) gives the polynomial.
For every coloring and every color \(j\),
Multiply the adoption probability of Lemma 6 by \(n\).
3 The upper bound
3.1 Plurality, bias, \(\alpha \) and \(\gamma \)
For a \(k\)-cd \(c\) with \(\sum _h c_h = n\): \(m(c) = \max _h c_h\), \(M(c) = \{ j : c_j = m(c)\} \), the bias \(s(c) = m(c) - \max _{h \notin M(c)} c_h\) if \(|M(c)| = 1\) and \(0\) otherwise, \(\alpha (c) = (n - m(c))\, s(c)/n^2\) and \(\gamma (c) = (n\, m(c) - \sum _h c_h^2)/n^2 - \alpha (c)\).
If \(c_m = m(c)\) then \(c_h + s(c) \le m(c)\) for every \(h \ne m\), with equality for some \(h\) when \(k \ge 2\). Moreover \(\gamma (c)\, n^2 = \sum _{h \ne m} c_h\, (m(c) - s(c) - c_h)\).
For every \(k\)-cd \(c\): (a) \(0 \le s(c) \le m(c) - (n - m(c))/(k-1)\); (b) \(0 \le \alpha (c) \le \min \{ s(c)/n,\ 1/4\} \); (c) \(0 \le \gamma (c) \le 1/8\).
(a) The \(k-1\) other colors each have at most \(m(c) - s(c)\) nodes. (b) \((n - m)m \le n^2/4\) and \(s \le m\). (c) Use the identity of Lemma 9: every summand is nonnegative, the color attaining the bias contributes \(0\), and the rest is at most \(d(n - m - d) \le n^2/8\) with \(d = m(c) - s(c)\).
Let \(m \in M(c)\) and let \(\ell \ne m\) have the most nodes among the other colors. Then (a) \(\mu _m(c) = c_m(1 + \gamma + \alpha )\); (b) \(\mu _j(c) = c_j(1 + \gamma + \alpha - (m(c) - c_j)/n)\) for every \(j\); (c) \(\mu _\ell (c) = c_\ell (1 + \gamma + \alpha - s(c)/n)\).
3.2 Concentration
For \(X = \sum _i Y_i(\omega _i)\) with independent uniform coordinates: Bernstein’s inequality \(\Pr (X \ge \mathbb {E}X + \lambda ) \le \exp (-\lambda ^2/(2\sigma ^2(1 + b\lambda /(3\sigma ^2))))\) when \(Y_i - \mathbb {E}Y_i \le b\) and \(\sum _i \mathrm{Var}\, Y_i \le \sigma ^2\); Hoeffding’s inequality for \(\{ 0,1\} \) coordinates; the multiplicative Chernoff lower tail \(\Pr (X \le (1-\delta )\mu ) \le \exp (-\delta ^2\mu /2)\); and Markov’s inequality \(\Pr (X \ge 1) \le \mathbb {E}X\) for \(\{ 0,1\} \) coordinates.
3.3 Growth of the bias
If \(M(c) = \{ m\} \) then for every \(j \ne m\),
If \(M(c) = \{ m\} \) then \(\Pr (C_{m,t+1} \le c_m(1 + \gamma + \alpha /2) \mid C_t = c) \le \exp (-c_m\alpha ^2/11)\).
The multiplicative Chernoff lower tail with \(\delta = \alpha /(2(1 + \gamma + \alpha ))\).
If \(M(c) = \{ m\} \), \(0 {\lt} \lambda \le 2/3\), \(\lambda n \le c_m \le (2/3)n\) and \(s(c) \ge 22\sqrt{(1/\lambda )\, n\log n}\), then for every \(j \ne m\)
3.4 Saturation
For every \(m \in M(c)\), writing \(\bar C_{m,t+1} = n - C_{m,t+1}\),
Let \(\log n \ge 40\), \(M(c) = \{ m\} \). (i) If \(s(c) \ge n/3\) and \(n - c_m \ge n^{1/4}\log n\) then \(\Pr (\bar C_{m,t+1} \ge \frac{17}{18}(n - c_m)) \le 1/n^2\). (ii) If \(n - c_m {\lt} n^{1/4}\log n\) then \(\Pr (\bar C_{m,t+1} {\gt} 0) \le n^{-1/5}\) and \(\Pr (\bar C_{m,t+1} \ge n^{1/4}\log n) \le 1/n^2\).
The paper omits this proof. (i) By Lemma 16 and \(s\, c_m \ge n^2/9\), \(\mathbb {E}\bar C_{m,t+1} \le \frac89(n - c_m)\); apply the closed-form Chernoff upper tail at ratio \(17/16\). (ii) Here \(s(c) \ge n - 2(n - c_m)\), so \(\mathbb {E}\bar C_{m,t+1} \le 3(n-c_m)^2/n \le 3\log ^2 n\, e^{-(\log n)/2}\); apply Markov’s inequality for the first bound and the Chernoff upper tail for the second.
3.5 Nested phases and the main theorem
Let \(A_1 \supseteq \cdots \supseteq A_T\) be sets of states of a finite Markov chain such that from every state of \(A_i\) the chain stays in \(A_i\) with probability \(\ge 1-\varepsilon \) and, for \(i {\lt} T\), moves into \(A_{i+1}\) with probability \(\ge 1 - \nu \). Then from any state of \(A_1\), after \(\ell T\) steps the chain is in \(A_T\) with probability at least \(1 - T(\ell \varepsilon + \nu ^\ell )\).
The paper omits this proof. Phase by phase: within \(\ell \) steps the chain leaves \(A_i\) with probability at most \(\ell \varepsilon \), and fails to jump into \(A_{i+1}\) in each of the \(\ell \) steps with probability at most \(\nu ^\ell \). The hypothesis \(\varepsilon \le \nu \) of the paper is not needed.
Fix \(m\), \(\lambda \), \(\Lambda \) and let \(q = 1 + 1/(6\lambda )\), \(B = n^{1/4}\log n\). Growth phase \(i\): \(c_m {\gt} \frac23 n\), or \(M(c) = \{ m\} \), \(c_m \ge n/\lambda \) and \(s(c) \ge \Lambda q^i\). Saturation phase \(j\): \(n - c_m {\lt} \max \{ \frac n3 (\frac{17}{18})^j,\ B\} \). Consensus: \(c_m = n\).
If \(n - c_m {\lt} n/3\) then \(M(c) = \{ m\} \) and \(s(c) \ge n/3\). If \(m\) leads every other color by at least \(g {\gt} 0\) and \(c_m \ge g\), then \(M(c) = \{ m\} \) and \(s(c) \ge g\). A color without nodes stays without nodes.
Let \(\log n \ge 40\), \(k \ge 2\), \(\lambda \ge 3\) and \(\Lambda \ge 22\sqrt{\lambda n \log n}\). From growth phase \(i\) the chain enters growth phase \(i+1\) with probability \(\ge 1 - 1/n\). From saturation phase \(j\) it enters saturation phase \(j+1\) with probability \(\ge 1 - 1/n^2\). From fewer than \(B\) dissenting nodes it reaches consensus with probability \(\ge 1 - n^{-1/5}\), and consensus is kept with probability \(1\). The phase sets are nested, and growth phase \(i\) lies in saturation phase \(0\) once \(\Lambda q^i {\gt} n\).
Growth, case \(c_m {\gt} \frac23 n\): saturation phase \(0\) moves into saturation phase \(1\), which lies in \(\{ c_m {\gt} \frac23 n\} \). Growth, otherwise: apply Lemma 15 with \(1/\lambda \) to each other color \(j\) that currently has a node, and to the growth of \(c_m\). There are fewer than \(n - c_m\) such colors, so a union bound gives failure probability at most \(n/n^2\). Colors without nodes stay empty, and the color attaining the bias has a node (otherwise \(c_m = n\)), so after a successful round \(m\) leads every other color by \(s(c)\, q\) and Lemma 21 applies. Saturation: Lemma 17(i) above \(B\) dissenters and Lemma 17(ii) below.
With \(T_1 = \lceil \log n/\log q\rceil \) growth phases, \(T_2 = \lceil \log n/\log (18/17)\rceil + 1\) saturation phases and one consensus phase, \(T = T_1 + T_2 + 1 \le 13\lambda \log n\) for \(\lambda \ge 3\) and \(\log n \ge 40\).
\(\log (1+x) \ge x/(1+x)\) gives \(\log q \ge 1/(6\lambda +1)\) and \(\log (18/17) \ge 1/18\).
Let \(\log n \ge 40\), \(k \ge 2\) and \(\lambda \ge 3\). If \(M(c) = \{ m\} \), \(c_m \ge n/\lambda \) and \(s(c) \ge 22\sqrt{\lambda n\log n}\), then after \(10T \le 130\lambda \log n\) rounds all nodes support \(m\) with probability at least \(1 - 11T/n \ge 1 - 143\lambda \log n/n\).
Apply Lemma 18 to the kernel of 3-majority with the \(T_1\) growth phases, the \(T_2\) saturation phases and consensus, \(\varepsilon = 1/n\), \(\nu = n^{-1/5}\) and \(\ell = 10\), so that \(\nu ^\ell = n^{-2}\). The initial coloring is in growth phase \(0\); growth phase \(T_1\) lies in saturation phase \(0\) because \(\Lambda q^{T_1} \ge 22n\); saturation phase \(T_2 - 1\) lies below \(B\) dissenters because \(\frac n3(\frac{17}{18})^{T_2-1} \le \frac13\).
The paper states the failure probability as \(11T/n^2\); the extra factor \(n\) comes from the union bound over competing colors in Lemma 22, which the paper omits. The paper’s hypothesis \(\lambda {\lt} \sqrt n\) is not used; it only makes the hypothesis on \(s(c)\) satisfiable.
If \(M(c) = \{ m\} \) and \(s(c) \ge 22\sqrt{\min \{ 2k, (n/\log n)^{1/3}\} \, n\log n}\), then 3-majority reaches consensus on \(m\) in \(O(\min \{ 2k, (n/\log n)^{1/3}\} \log n)\) rounds w.h.p. Precisely, for \(\log n \ge 40\) and \(k \ge 2\): at most \(130\lambda \log n\) rounds with probability at least \(1 - 143\lambda \log n/n\).
Take \(\lambda = \min \{ 2k, (n/\log n)^{1/3}\} \). If \(\lambda = 2k\) then \(c_m \ge n/k\) by pigeonhole; otherwise \(\lambda ^3 = n/\log n\), so \(22\sqrt{\lambda n\log n} = 22n/\lambda \) and \(c_m \ge s(c) \ge n/\lambda \). Moreover \(\lambda \ge 3\) because \(k \ge 2\) and \(n = e^{\log n} \ge 27\log n\).
If \(c_m \ge n/\log ^\ell n\) and \(s(c) \ge 22\sqrt{n\log ^{\ell +1}n}\), consensus takes \(O(\log ^{\ell +1} n)\) rounds w.h.p. If \(c_m \ge n/\beta \) and \(s(c) \ge 22\sqrt{\beta n\log n}\) for a constant \(\beta \ge 3\), it takes \(O(\log n)\) rounds w.h.p.
Take \(\lambda = \log ^\ell n\) (with \(\ell \ge 1\), so that \(\lambda \ge 3\)) and \(\lambda = \beta \) in Theorem 24.
3.6 Two colors
With \(k = 2\) the set of nodes of color \(1\) evolves exactly as the binary 3-majority process of the three_majority package. Hence, if \(c_1 \ge \frac35 n\) and \(\log n \ge 30\), all nodes support color \(1\) after \(O(\log n)\) rounds with probability at least \(1 - 500/n\).
In the binary 3-majority process, if the initial majority leads by at least \(22\sqrt{3n\log n}\) nodes (a fraction \(\frac12 + O(\sqrt{\log n/n})\)) and \(\log n \ge 40\), all nodes adopt it within at most \(390\log n\) rounds with probability at least \(1 - 429\log n/n\).
4 Lower bounds
4.1 Lower bound for 3-majority
If a round-based process starts in \(G_0\) and, for every \(t {\lt} T\), one round from any state of \(G_t\) misses \(G_{t+1}\) with probability at most \(p\), then after \(T\) rounds it lies outside \(G_T\) with probability at most \(Tp\).
Induction on \(T\), conditioning on the first round.
Let \(k\sqrt{n\log n} \le b \le n/k\). If \(c_j \le n/k + b\), then \(\Pr (C_{j,t+1} \ge n/k + (1 + 3/k)b \mid C_t = c) \le 1/n^2\).
By Cauchy–Schwarz \(\sum _h c_h^2 \ge n^2/k\), so \(\mu _j \le c_j(1 + c_j/n - 1/k)\). Writing \(c_j = n/k + a\) with \(a \le b\), this is at most \(n/k + (1+1/k)b + b^2/n \le n/k + (1+2/k)b\). Hoeffding’s inequality with deviation \(b/k \ge \sqrt{n\log n}\) gives \(1/n^2\).
Let \(k \ge 3\) and suppose every color starts with at most \(n/k + b\) nodes, where \(b \ge k\sqrt{n\log n}\). If \(b(1 + 3/k)^T \le n/k\), in particular if \(T \le \frac k3 \log \frac{n}{kb}\), then the coloring after \(T\) rounds is monochromatic with probability at most \(kT/n^2\).
With \(b = \max \{ (n/k)^{1-\varepsilon }, k\sqrt{n\log n}\} \) this gives \(\Omega (k\log (n/(kb)))\) rounds, which is \(\Omega (k\log n)\) for \(k \le n^{1/4-\delta }\). The paper states \(\Omega (k\log n)\) for all \(k \le (n/\log n)^{1/4}\), but at that end \(n/k = k\sqrt{n\log n}\) and the argument gives nothing. The paper’s proof also chooses the thresholds after seeing the trajectory; the union bound needs the fixed schedule used here.
4.2 Which 3-input rules solve plurality consensus
A rule is conservative if it returns one of its inputs. It has the clear-majority property if it returns the majority color whenever two inputs agree. For colors \(r \ne b\), \(\Delta _r\) counts the orderings of \((r,r,b)\) on which the rule returns \(r\). For distinct \(r,g,b\), \(\delta _c\) counts the orderings of \((r,g,b)\) on which it returns \(c\); the rule is uniform if \(\delta _r = 2\) for all distinct triples. It is an \((s,\varepsilon )\)-solver if from every coloring whose unique plurality color \(m\) has bias at least \(s\), consensus on \(m\) is eventually reached with probability at least \(1-\varepsilon \).
Under a conservative rule a color without nodes never returns. Hence for all \(T, T_0\), the probability of consensus on \(m\) at time \(T\) is at most the probability that \(m\) has a node at time \(T_0\).
Let \(8 \mid n\). With only colors \(r, b\) present and \(x\) the fraction of \(r\), a node adopts \(r\) with probability \(p(x)\), where \(p(x) - x = x(1-x)\bigl(x(\Delta _r - 2) + (1-x)(2 - \Delta _b)\bigr)\). If \(\Delta _r \le 2 \le \Delta _b\), the number of \(r\) nodes is a supermartingale, so from \(5n/8\) nodes of \(r\) (bias \(n/4\)) consensus on \(r\) has probability at most \(5/8\) at every time: the rule is not an \((n/4, 1/4)\)-solver. Consequently, for an \((n/4, 1/4)\)-solver and every pair \(r \ne b\), either \(\Delta _r = \Delta _b = 3\) or \(\Delta _r, \Delta _b \le 1\).
\(\mathbb {E}[X_T] \le X_0\) by induction on \(T\), and \(\Pr (X_T = n) \le \mathbb {E}[X_T]/n\).
The paper claims that an \((n/4,1/4)\)-solver has the clear-majority property, i.e. that \(\Delta _r, \Delta _b \le 1\) is also impossible. Its proof uses the supermartingale property, but checks it only when red is the majority; for \(\Delta _r, \Delta _b \le 1\) it fails when red is the minority, because the process is pulled to the interior point \(x^* = (2 - \Delta _b)/(4 - \Delta _r - \Delta _b)\). That case is not formalized.
Let the rule be conservative with the clear-majority property, let only \(r, g, b\) be present and \(\delta _r \le 1\). Then \(p(r) \le 3x^2 - 2x^3 + \delta _r x_r x_g x_b \le x(3x - 2x^2 + (1-x)^2/4)\), which is at most \(0.97x\) for \(x \le 2/5\); and from \(x \le 2/5\) one round ends above \(2n/5\) with probability at most \(e^{-9n/31250}\).
Under the hypotheses of Lemma 38, starting with at most \(2n/5\) nodes of \(r\), the probability that \(r\) still has a node after \(T\) rounds is at most \(0.97^T c_r + T e^{-9n/31250}\).
Consider the chain frozen once \(r\) exceeds \(2n/5\). On it, \(\Phi = C_r\, \mathbb 1[C_r \le 2n/5]\) contracts by \(0.97\) in every state, it is frozen within \(T\) rounds with probability at most \(Te^{-9n/31250}\), and it agrees with the real chain until it is frozen.
Let \(60 \mid n\) and \(\log n \ge 20\). A rule with the clear-majority property that is an \((n/20, 1/4)\)-solver has the uniform property.
If a triple is not uniform, some color \(r\) of it has \(\delta _r \le 1\), since the three counts sum to \(6\). Start from \(23n/60\) nodes of \(r\), \(n/3\) of \(g\) and \(17n/60\) of \(b\): \(r\) is the unique plurality color with bias \(n/20\). By Lemmas 39 and 35, with \(T_0 = \lceil \log (8n)/\log (100/97)\rceil \), consensus on \(r\) has probability at most \(1/8 + 1/8\) at every time.
The paper’s proof (Lemma 4.10) is a sketch that treats \(\delta _r = 1\) with \((\delta _g,\delta _b) \in \{ (3,2),(4,1)\} \) and asserts that \(r\) “will not converge” by iterating a one-round estimate. The proof here covers every non-uniform triple and makes the iteration rigorous.
4.3 A lower bound for \(h\)-plurality
Every node samples \(h\) nodes and a uniformly random ordering \(\sigma \) of the \(h\) sample positions, and adopts the color of the position of smallest \(\sigma \)-rank among those whose color is most frequent. All tied colors appear equally often, so each is chosen with the same probability.
A node adopts \(j\) with probability at most \(x_j + \frac{h^2}{2}x_j^2\).
If \(j\) wins and is seen exactly once, all \(h\) sampled colors are distinct and \(j\) is at the position ranked first, which has probability \(x_j\). Otherwise \(j\) is seen at least twice, and \(\Pr (N_j \ge 2) \le \mathbb {E}[N_j(N_j-1)]/2 = \binom h2 x_j^2\).
If \(c_j \le a \le 2n/k\), then \(\Pr (C_{j,t+1} \ge a(1 + 2h^2/k)) \le \exp (-2(ah^2/k)^2/n)\), which is at most \(e^{-2nh^4/k^4}\) when \(a \ge n/k\).
Let \(k \ge 3\). If every color starts with at most \(\frac32\cdot \frac nk\) nodes and \(T \le \frac{k}{2h^2}\log \frac43\), then after \(T\) rounds of \(h\)-plurality the coloring is monochromatic with probability at most \(kT e^{-2nh^4/k^4}\).
As for Theorem 32, with thresholds \(\frac32\cdot \frac nk(1 + 2h^2/k)^t \le 2n/k\).