At least 4 states are needed for majority (CRN-4) #
[MNRS14, Theorem 1]: no population protocol with at most 3 states stably computes the
majority of a 2-type population on every interaction graph, so the 4-state ambassador protocol
(ambassador_graphStablyComputes) has the minimal number of states.
The paper's proof only uses complete interaction graphs (a population V and the population
V ∪ {u, v} with two extra agents, interacting in a supergraph), so we pin the stronger form
not_stablyComputesOnGraph_top_majority: no protocol with at most 3 states stably computes
majority on the complete graphs of all nonempty populations (the standard populations of
Protocol.StablyComputes), even with ties excluded from the domain. The statement on all
connected graphs follows (not_graphStablyComputes_majority).
Proof route [MNRS14, Theorem 1]: both outputs occur, so with at most 3 states one output value
b has a single state q₁. Say b is the output of a red majority (otherwise exchange the
colors). On V = Fin 3, the inputs C₁ = (r, r, g) and C₂ = (r, r, r) both reach the
configuration "all q₁". Adding two green agents gives C₁' = (r, r, g, g, g) (green
majority) and C₂' = (r, r, r, g, g) (red majority); running the same encounters inside V
(Protocol.GraphReaches.extend) both reach the configuration "q₁ on V, green input state on
the two extra agents", from which output-stable configurations with both outputs would be
reachable: a contradiction. The paper takes |V| = 2k + 1 with k ≥ 2; k = 1 already works.
References #
- [MNRS14] G. B. Mertzios, S. E. Nikoletseas, C. L. Raptopoulos, P. G. Spirakis, Determining majority in networks with local interactions and very small local memory, ICALP 2014; arXiv:1404.7671.
A single agent has no partner on the complete graph: from c, only c is reachable.
Both outputs occur [MNRS14, proof of Theorem 1]: a protocol computing majority on the
complete graph of a single agent outputs b on the input state of b.
The core of [MNRS14, Theorem 1]. If a single state q₁ has output b, then the
protocol does not compute majority on all complete graphs: on Fin 3, the inputs (b, b, !b)
and (b, b, b) both reach "all q₁"; adding two agents of input !b (inputs (b, b, !b, !b, !b)
and (b, b, b, !b, !b), with majorities !b and b) gives a common reachable configuration
from which output-stable configurations with both outputs are reachable.
[MNRS14, Theorem 1], strong form. No population protocol with at most 3 states stably computes the majority of two input types on the complete graphs of all nonempty populations, with the tie inputs excluded from the domain.
[MNRS14, Theorem 1]. No population protocol with at most 3 states stably computes the
majority of two input types on every connected interaction graph: R(𝒫_majority) > 3.
The rank of majority is 4 [MNRS14, Theorems 1 and 2]: the 4-state ambassador protocol stably computes majority on every connected graph, and no protocol with fewer states does.