Documentation

Plurality.UniformRule

Theorem 4.8 (b): a solver with the clear-majority property is uniform #

Let f have the clear-majority property and let r, g, b be distinct colors with δ_r ≤ 1 (r is returned on at most one of the six orderings of (r, g, b)). Start from 23n/60 nodes of color r, n/3 of color g and 17n/60 of color b: r is the unique plurality color with bias n/20.

One round. With only r, g, b present and x = x_r, a node adopts r only if it sees r at least twice, or sees r, g, b in an order on which f returns r (clear majority rules out everything else), so p(r) ≤ 3x² - 2x³ + δ_r x_r x_g x_b ≤ x (3x - 2x² + (1-x)²/4). For x ≤ 2/5 this is at most 0.97 x (expected_count_le), and Hoeffding's inequality bounds the probability of jumping above 2n/5 (jump_prob_le).

Many rounds. The frozen chain (frozenStep) stops as soon as r has more than 2n/5 nodes. On it, Φ = C_r 𝟙[C_r ≤ 2n/5] contracts by 0.97 in every state (frozen_potential_le), and it is stopped within T rounds with probability at most T e^{-9n/31250} (frozen_stop_le). The real and frozen chains agree until the frozen chain stops (foldl_frozen_eq). Hence r survives T₀ = O(log n) rounds with probability at most 1/4 (alive_le), and so it is never the consensus color with probability more than 1/4: f is not an (n/20, 1/4)-solver (not_solver_of_nonuniform).

theorem_4_8_b: an (n/20, 1/4)-solver with the clear-majority property has the uniform property. The paper's proof of Lemma 4.10 is a sketch covering δ_r = 1 with (δ_g, δ_b) ∈ {(3,2), (4,1)}; the argument here covers every triple with some δ ≤ 1, which is every non-uniform triple.

Three colors present #

def Plurality.Supp3 {n k : ℕ} (r g b : Fin k) (y : Config n k) :

Every node supports r, g or b.

Equations
Instances For
    theorem Plurality.Supp3.stepWith {n k : ℕ} {f : Rule k} (hf : Conservative f) {r g b : Fin k} {y : Config n k} (hy : Supp3 r g b y) (t : ThreeMajority.Tgt3 n) :
    theorem Plurality.Supp3.count_eq_zero {n k : ℕ} {r g b : Fin k} {y : Config n k} (hy : Supp3 r g b y) {c : Fin k} (hr : c ≠ r) (hg : c ≠ g) (hb : c ≠ b) :
    count y c = 0
    theorem Plurality.sum_eq_three {k : ℕ} {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) {F : Fin k → ℝ} (hF : ∀ (c : Fin k), c ≠ r → c ≠ g → c ≠ b → F c = 0) :
    ∑ c : Fin k, F c = F r + F g + F b

    One round #

    theorem Plurality.adopt_r_le {k : ℕ} {f : Rule k} (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) {a b' c : Fin k} (ha : a = r ∨ a = g ∨ a = b) (hb' : b' = r ∨ b' = g ∨ b' = b) (hc : c = r ∨ c = g ∨ c = b) :
    have e := fun (z : Fin k) => if z = r then 1 else 0; have i := fun (z z' : Fin k) => if z = z' then 1 else 0; have d := fun (u v w : Fin k) => if f u v w = r then 1 else 0; d a b' c ≤ e a * e b' + e a * e c + e b' * e c - 2 * (e a * e b' * e c) + (i a r * i b' g * i c b * d r g b + i a r * i b' b * i c g * d r b g + i a g * i b' r * i c b * d g r b + i a g * i b' b * i c r * d g b r + i a b * i b' r * i c g * d b r g + i a b * i b' g * i c r * d b g r)

    Pointwise bound on adopting r. For colors a, b', c among r, g, b, f returns r only if r appears at least twice or (a, b', c) is an ordering of (r, g, b) on which f returns r.

    theorem Plurality.avg_adopt_r_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) {y : Config n k} (hy : Supp3 r g b y) :
    Dynamics.avg (adopt f y r) ≤ 3 * frac y r ^ 2 - 2 * frac y r ^ 3 + ↑(deltaCount f r g b r) * (frac y r * frac y g * frac y b)

    Adoption probability of r with only r, g, b present: p(r) ≤ 3x² - 2x³ + δ_r x_r x_g x_b.

    theorem Plurality.poly_le (x : ℝ) (h0 : 0 ≤ x) (h1 : x ≤ 2 / 5) :
    3 * x ^ 2 - 2 * x ^ 3 + x * (1 - x) ^ 2 / 4 ≤ 97 / 100 * x

    3x² - 2x³ + x(1-x)²/4 ≤ 0.97 x for 0 ≤ x ≤ 2/5.

    theorem Plurality.expected_count_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (_hf : Conservative f) (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) (hδ : deltaCount f r g b r ≤ 1) {y : Config n k} (hy : Supp3 r g b y) (hlow : ↑(count y r) ≤ 2 * ↑n / 5) :
    ↑n * Dynamics.avg (adopt f y r) ≤ 97 / 100 * ↑(count y r)

    Contraction in expectation. With only r, g, b present, δ_r ≤ 1 and at most 2n/5 nodes of color r, the expected number of r nodes after one round is at most 0.97 times the current one.

    theorem Plurality.jump_prob_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) (hδ : deltaCount f r g b r ≤ 1) {y : Config n k} (hy : Supp3 r g b y) (hlow : ↑(count y r) ≤ 2 * ↑n / 5) :
    (Dynamics.avg fun (t : ThreeMajority.Tgt3 n) => if 2 * ↑n / 5 < ↑(count (stepWith f y t) r) then 1 else 0) ≤ Real.exp (-(9 * ↑n / 31250))

    No jump above 2n/5. From at most 2n/5 nodes of color r, one round ends with more than 2n/5 of them with probability at most exp(-9n/31250).

    The frozen chain #

    def Plurality.LowR {n k : ℕ} (r : Fin k) (y : Config n k) :

    r has at most 2n/5 nodes.

    Equations
    Instances For
      noncomputable def Plurality.frozenStep {n k : ℕ} (f : Rule k) (r : Fin k) (y : Config n k) (t : ThreeMajority.Tgt3 n) :
      Config n k

      One round of the chain that stops once r has more than 2n/5 nodes.

      Equations
      Instances For
        noncomputable def Plurality.potential {n k : ℕ} (r : Fin k) (y : Config n k) :

        The potential Φ = C_r 𝟙[C_r ≤ 2n/5].

        Equations
        Instances For
          theorem Plurality.potential_nonneg {n k : ℕ} (r : Fin k) (y : Config n k) :
          theorem Plurality.Supp3.frozen {n k : ℕ} {f : Rule k} (hf : Conservative f) {r g b : Fin k} {y : Config n k} (hy : Supp3 r g b y) (t : ThreeMajority.Tgt3 n) :
          Supp3 r g b (frozenStep f r y t)
          theorem Plurality.frozen_potential_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) (hδ : deltaCount f r g b r ≤ 1) (T : ℕ) (y : Config n k) :
          Supp3 r g b y → (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => potential r (List.foldl (frozenStep f r) y l)) ≤ (97 / 100) ^ T * potential r y

          Φ contracts in every state of the frozen chain.

          theorem Plurality.frozen_stop_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) (hδ : deltaCount f r g b r ≤ 1) (T : ℕ) {y : Config n k} (hy : Supp3 r g b y) (hlow : LowR r y) :
          (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if List.foldl (frozenStep f r) y l ∈ {z : Config n k | Supp3 r g b z ∧ LowR r z} then 0 else 1) ≤ ↑T * Real.exp (-(9 * ↑n / 31250))

          The frozen chain rarely stops.

          theorem Plurality.foldl_frozen_high {n k : ℕ} {f : Rule k} {r : Fin k} {y : Config n k} (hy : ¬LowR r y) (l : List (ThreeMajority.Tgt3 n)) :
          List.foldl (frozenStep f r) y l = y
          theorem Plurality.foldl_frozen_eq {n k : ℕ} {f : Rule k} {r : Fin k} (l : List (ThreeMajority.Tgt3 n)) (y : Config n k) :
          LowR r (List.foldl (frozenStep f r) y l) → List.foldl (frozenStep f r) y l = runWith f y l

          Coupling. If the frozen chain has not stopped, it agrees with the real one.

          theorem Plurality.Supp3.foldl_frozen {n k : ℕ} {f : Rule k} (hf : Conservative f) {r g b : Fin k} (l : List (ThreeMajority.Tgt3 n)) {y : Config n k} :
          Supp3 r g b y → Supp3 r g b (List.foldl (frozenStep f r) y l)
          theorem Plurality.alive_le {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) (hδ : deltaCount f r g b r ≤ 1) (T : ℕ) {y : Config n k} (hy : Supp3 r g b y) (hlow : LowR r y) :
          (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if 1 ≤ count (runWith f y l) r then 1 else 0) ≤ (97 / 100) ^ T * ↑(count y r) + ↑T * Real.exp (-(9 * ↑n / 31250))

          r dies out. After T rounds, r still has a node with probability at most 0.97^T C_r + T e^{-9n/31250}.

          The counterexample #

          noncomputable def Plurality.extinctRounds (n : ℕ) :

          The number T₀ = ⌈log (8n) / log (100/97)⌉ of rounds after which r has died out with probability at least 3/4.

          Equations
          Instances For
            theorem Plurality.extinct_numerics {n : ℕ} (hL : 20 ≤ Real.log ↑n) :
            (97 / 100) ^ extinctRounds n * ↑n ≤ 1 / 8 ∧ ↑(extinctRounds n) * Real.exp (-(9 * ↑n / 31250)) ≤ 1 / 8
            def Plurality.threeColor {k : ℕ} (n : ℕ) (r g b : Fin k) (a₁ a₂ : ℕ) :
            Config n k

            The coloring with nodes < a₁ colored r, nodes in [a₁, a₂) colored g and the others b.

            Equations
            Instances For
              theorem Plurality.not_solver_of_nonuniform {n k : ℕ} (h60 : 60 ∣ n) (hL : 20 ≤ Real.log ↑n) {f : Rule k} (hf : Conservative f) (hcm : ClearMajority f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) (hδ : deltaCount f r g b r ≤ 1) :
              ¬Solver f n (↑n / 20) (1 / 4)

              A non-uniform triple defeats the rule. If f has the clear-majority property and δ_r ≤ 1 for distinct r, g, b, then from 23n/60 nodes of color r, n/3 of g and 17n/60 of b (bias n/20), consensus on r has probability at most 1/4 at every time. Hence f is not an (n/20, 1/4)-solver (for 60 ∣ n, log n ≥ 20).

              theorem Plurality.theorem_4_8_b {n k : ℕ} (h60 : 60 ∣ n) (hL : 20 ≤ Real.log ↑n) {f : Rule k} (hf : Conservative f) (hcm : ClearMajority f) (hS : Solver f n (↑n / 20) (1 / 4)) :

              Theorem 4.8 (b). If f has the clear-majority property and is an (n/20, 1/4)-solver (for 60 ∣ n and log n ≥ 20), then f has the uniform property.