Documentation

Plurality.Model

The 3-majority dynamics with k colors (Section 2) #

n anonymous nodes each support one of k colors; a coloring is a map Config n k := Fin n → Fin k. At every round each node picks three nodes uniformly at random (including itself, with repetitions) and recolors itself according to the majority of the three colors it sees; if it sees three different colors it takes the first one.

The randomness of a round is exactly that of the binary development: ThreeMajority.Tgt3 n = Fin n → Fin n × Fin n × Fin n, one ordered triple of samples per node, drawn uniformly. Multi-round expectations are Dynamics.expList (Tgt3 n) T, and kernel f is the same process as a finite Markov kernel (Dynamics.Kernel.ofStep), which is how the phase lemma Dynamics.Kernel.nested_phases (the paper's Lemma A.4) applies.

Section 4.2 of the paper compares 3-majority with an arbitrary deterministic 3-input rule f : Fin k → Fin k → Fin k → Fin k, so the round is defined for any such rule (stepWith f) and 3-majority is the instance f = maj3.

The 3-majority round itself is defined once, for colours of any type, as ThreeMajority.stepCol (ThreeMajority.AnyStartModel): step, run and count are ThreeMajority.stepCol, ThreeMajority.runCol and ThreeMajority.colourCount at colours Fin k (step_eq_stepCol, run_eq_runCol, count_eq_colourCount).

@[reducible, inline]
abbrev Plurality.Config (n k : ℕ) :

A coloring of n nodes with k colors.

Equations
Instances For
    def Plurality.maj3 {k : ℕ} (a b c : Fin k) :
    Fin k

    The 3-majority rule: the majority color among a, b, c, and the first one, a, if all three differ.

    Equations
    Instances For
      theorem Plurality.maj3_mem {k : ℕ} (a b c : Fin k) :
      maj3 a b c = a ∨ maj3 a b c = b ∨ maj3 a b c = c
      def Plurality.stepWith {n k : ℕ} (f : Fin k → Fin k → Fin k → Fin k) (x : Config n k) (r : ThreeMajority.Tgt3 n) :
      Config n k

      One synchronous round of the 3-input dynamics with rule f: node v sees the colors of its three samples r v and adopts f of them.

      Equations
      Instances For
        def Plurality.step {n k : ℕ} (x : Config n k) (r : ThreeMajority.Tgt3 n) :
        Config n k

        One round of the 3-majority dynamics.

        Equations
        Instances For
          def Plurality.runWith {n k : ℕ} (f : Fin k → Fin k → Fin k → Fin k) (x : Config n k) (l : List (ThreeMajority.Tgt3 n)) :
          Config n k

          The coloring after consuming a list of rounds with rule f.

          Equations
          Instances For
            def Plurality.run {n k : ℕ} (x : Config n k) (l : List (ThreeMajority.Tgt3 n)) :
            Config n k

            The coloring after consuming a list of rounds of 3-majority.

            Equations
            Instances For
              @[simp]
              theorem Plurality.runWith_nil {n k : ℕ} (f : Fin k → Fin k → Fin k → Fin k) (x : Config n k) :
              runWith f x [] = x
              theorem Plurality.runWith_append {n k : ℕ} (f : Fin k → Fin k → Fin k → Fin k) (x : Config n k) (l₁ l₂ : List (ThreeMajority.Tgt3 n)) :
              runWith f x (l₁ ++ l₂) = runWith f (runWith f x l₁) l₂

              One model. The round of 3-majority is the round ThreeMajority.stepCol of 3-Majority with colours of any type, at colours Fin k: maj3 is the rule ThreeMajority.majColour on the colours of the three samples.

              theorem Plurality.run_eq_runCol {n k : ℕ} (x : Config n k) (l : List (ThreeMajority.Tgt3 n)) :

              The process run is ThreeMajority.runCol at colours Fin k.

              @[simp]
              theorem Plurality.run_cons {n k : ℕ} (x : Config n k) (r : ThreeMajority.Tgt3 n) (l : List (ThreeMajority.Tgt3 n)) :
              run x (r :: l) = run (step x r) l

              Color counts #

              def Plurality.count {n k : ℕ} (x : Config n k) (j : Fin k) :

              The number c_j of nodes supporting color j. The map count x is the paper's k-color distribution (k-cd) of x.

              Equations
              Instances For
                theorem Plurality.count_eq_colourCount {n k : ℕ} (x : Config n k) (j : Fin k) :

                count is the configuration vector ThreeMajority.colourCount at colours Fin k.

                theorem Plurality.count_le {n k : ℕ} (x : Config n k) (j : Fin k) :
                count x j ≤ n
                theorem Plurality.sum_count {n k : ℕ} (x : Config n k) :
                ∑ j : Fin k, count x j = n

                The color counts sum to n.

                theorem Plurality.sum_count_real {n k : ℕ} (x : Config n k) :
                ∑ j : Fin k, ↑(count x j) = ↑n
                theorem Plurality.sum_comp_eq_sum_count {n k : ℕ} {M : Type u_1} [AddCommMonoid M] [Module ℝ M] (x : Config n k) (F : Fin k → M) :
                ∑ v : Fin n, F (x v) = ∑ j : Fin k, ↑(count x j) • F j

                Summing a function of the colors over all nodes groups the nodes by color.

                def Plurality.Mono {n k : ℕ} (x : Config n k) (j : Fin k) :

                x is monochromatic of color j: every node supports j.

                Equations
                Instances For
                  @[implicit_reducible]
                  instance Plurality.instDecidableMono {n k : ℕ} (x : Config n k) (j : Fin k) :
                  Equations
                  def Plurality.Monochromatic {n k : ℕ} (x : Config n k) :

                  x is monochromatic (in some color).

                  Equations
                  Instances For
                    theorem Plurality.mono_iff_count {n k : ℕ} (x : Config n k) (j : Fin k) :
                    Mono x j ↔ count x j = n
                    theorem Plurality.stepWith_mono {n k : ℕ} {f : Fin k → Fin k → Fin k → Fin k} (hf : ∀ (a b c : Fin k), f a b c = a ∨ f a b c = b ∨ f a b c = c) {x : Config n k} {j : Fin k} (hx : Mono x j) (r : ThreeMajority.Tgt3 n) :
                    Mono (stepWith f x r) j

                    A 3-input rule that always returns one of its inputs keeps a monochromatic coloring monochromatic: consensus is absorbing.

                    theorem Plurality.runWith_mono {n k : ℕ} {f : Fin k → Fin k → Fin k → Fin k} (hf : ∀ (a b c : Fin k), f a b c = a ∨ f a b c = b ∨ f a b c = c) {x : Config n k} {j : Fin k} (hx : Mono x j) (l : List (ThreeMajority.Tgt3 n)) :
                    Mono (runWith f x l) j
                    theorem Plurality.run_mono {n k : ℕ} {x : Config n k} {j : Fin k} (hx : Mono x j) (l : List (ThreeMajority.Tgt3 n)) :
                    Mono (run x l) j

                    The Markov kernel #

                    Rounds exist when n ≠ 0: the instance Nonempty (Tgt3 n) for [NeZero n] is the one of ThreeMajority.AnyStartModel.

                    noncomputable def Plurality.kernel {n k : ℕ} [NeZero n] (f : Fin k → Fin k → Fin k → Fin k) :

                    The dynamics with rule f as a finite Markov kernel on colorings.

                    Equations
                    Instances For
                      theorem Plurality.kernel_event {n k : ℕ} [NeZero n] (f : Fin k → Fin k → Fin k → Fin k) (P : Config n k → Prop) [DecidablePred P] (T : ℕ) (x : Config n k) :
                      (kernel f).event P T x = Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if P (runWith f x l) then 1 else 0

                      Probabilities at time T for the kernel are expectations over T independent rounds.