Documentation

ThreeMajority.AnyStartComparison

Comparing anonymous consensus processes (BCEKMN17, Sections 2.2 and 2.3) #

An anonymous consensus (AC) process (Definition 1) is given by a process function α that maps the current configuration to a probability vector over the colours; in one round every agent independently adopts colour a with probability α(c)_a. Its one-round kernel on configurations is acKernel α, the independent product over the agents of α c. Protocol dominance (Definition 2) is Dominates α α': c ⪰ c' implies α(c) ⪰ α'(c').

The paper proves Theorem 2 through a coupling (Lemma 1) obtained from Strassen's theorem (Theorem 3). Here Theorem 2 is stated in its distributional form, which needs no coupling: it follows from Proposition 1 alone by induction on T (see FORMALIZATION_DIFFERENCES.md).

noncomputable def ThreeMajority.acKernel {n : ℕ} {σ : Type u_1} [Fintype σ] (α : (Fin n → σ) → Dynamics.Distribution σ) :
Dynamics.Kernel (Fin n → σ)

The one-round kernel of the anonymous consensus process with process function α (BCEKMN17, Definition 1): from configuration c, the agents adopt colours independently, each with law α c.

Equations
Instances For
    def ThreeMajority.Dominates {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (α α' : (Fin n → σ) → Dynamics.Distribution σ) :

    Protocol dominance for AC-processes (BCEKMN17, Definition 2 and the remark after it): P_α dominates P_α' if c ⪰ c' implies α(c) ⪰ α'(c').

    Equations
    Instances For
      theorem ThreeMajority.multinomial_schurConvex {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (p q : Dynamics.Distribution σ) (hpq : Majorizes p.weight q.weight) (φ : (Fin n → σ) → ℝ) (hφ : SchurConvex φ) :

      Proposition 1 (BCEKMN17; Rinott 1973, Marshall–Olkin–Arnold Proposition 11.E.11), in agent form: the expectation of a Schur-convex observable of the multinomial configuration Mult(n, Θ) is a Schur-convex function of Θ.

      theorem ThreeMajority.ac_comparison {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (α α' : (Fin n → σ) → Dynamics.Distribution σ) (h : Dominates α α') (φ : (Fin n → σ) → ℝ) (hφ : SchurConvex φ) (c c' : Fin n → σ) (hc : Majorizes (countVec c) (countVec c')) (T : ℕ) :
      (acKernel α').iterate T φ c' ≤ (acKernel α).iterate T φ c

      Theorem 2 (BCEKMN17), distributional form: if the AC-process P_α dominates P_α' and c ⪰ c', then at every time T every Schur-convex observable has at least the expectation under P_α from c that it has under P_α' from c'.

      theorem ThreeMajority.ac_numColours {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (α α' : (Fin n → σ) → Dynamics.Distribution σ) (h : Dominates α α') (c : Fin n → σ) (κ T : ℕ) :
      (acKernel α').event (fun (x : Fin n → σ) => numColours x ≤ κ) T c ≤ (acKernel α).event (fun (x : Fin n → σ) => numColours x ≤ κ) T c

      Theorem 2 (BCEKMN17), for the number of colours: started from the same configuration, the dominating AC-process has at most κ colours at time T with at least the probability of the dominated one.