The 3-majority opinion-dynamics process on the complete graph #
Tgt3 n— a round configuration: every agent draws an ordered triple of samples, independently and uniformly, with replacement (an agent may sample itself, and may sample the same agent twice — harmless, since a majority of three Boolean values always exists, with no ties).step I r— one round: every agent adopts the majority opinion among its three samples' current membership in the opinion-1setI.run I l— the opinion-1set after consuming the listlof rounds.step_mono— the monotone coupling: for a fixed roundr,I ⊆ I'impliesstep I r ⊆ step I' r. Unlike the push protocol's informed set,stepis not monotone in the round index (an unlucky round can shrinkstep I rbelowI), but it is monotone inIitself for a fixedr. This is the single structural fact that lets every tail bound below be proved for a reference set of a specific size and then transported to an arbitrary set that is merely⊆or⊇that reference — replacing the martingale/optional-stopping machinery that a non-monotone process would otherwise need.
@[implicit_reducible]
Equations
- ThreeMajority.instFintypeTgt3 n = { elems := ThreeMajority.instFintypeTgt3._aux_1 n, complete := ⋯ }
The number (0, 1, 2, or 3) of a sample triple s that currently
lie in I.
Equations
Instances For
The number (0, 1, 2, or 3) of agent v's three samples, under
round r, that currently lie in I.
Equations
- ThreeMajority.sampleCount I r v = ThreeMajority.sampleCountOf I (r v)
Instances For
One round of the 3-majority process: every agent adopts the majority opinion among its three samples.
Equations
- ThreeMajority.step I r = {v : Fin n | 2 ≤ ThreeMajority.sampleCount I r v}
Instances For
The opinion-1 set after consuming a list of rounds.
Equations
- ThreeMajority.run I [] = I
- ThreeMajority.run I (r :: l) = ThreeMajority.run (ThreeMajority.step I r) l