Proof of Theorem 3, p. 48 — if every member of ℋ outscores every dishonest producer, the committee is honest
ProvedCommitteeVoting.ExpConv.honest_of_separationLet , let , let be the set of dishonest producers, and let be a set of producers disjoint from (so every member of is honest) with
Let be any assignment of scores to the producers. If every member of receives strictly more votes than every dishonest producer,
then the committee is honest: every admissible committee of size (ties and filling resolved adversarially) contains at least producers outside .
This is the deterministic reduction with which the proof of Theorem 3 opens: it turns the event into the event that all members of outscore all members of , whose probability is then bounded by concentration.
Formalization Note The hypothesis is the paper's implicit convention that is a fraction; without it the claim fails (with and a committee of members cannot have honest members). The honest candidates are the complement of ; need not be all of them.
import Mathlib import Definitions.Def_CommitteeVoting_ExpConv_Committee
namespace CommitteeVoting.ExpConv
theorem honest_of_separation {m k : ℕ} (hkm : k ≤ m) {p : ℝ} (hp0 : 0 ≤ p) (hp1 : p ≤ 1)
(Mal H : Finset (Fin m)) (hdisj : Disjoint H Mal) (hcard : (1 - p) * (k : ℝ) ≤ (H.card : ℝ))
(s : Fin m → ℕ) (hsep : ∀ jh ∈ H, ∀ jm ∈ Mal, s jm < s jh) :
IsHonestOutcome k p Malᶜ s := by sorry
end CommitteeVoting.ExpConv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.