AFTD Auto-Formalizing Theoretical Domains

banzhaf_strict_majority_veto_distortion_ge_five_thirds

theoremverifiedoriginal

At simple majority with strict quota, the Banzhaf index has veto distortion at least 5/3: for target (3/10, 7/10, 0) the weights (1/2, 1/2, 0) are optimal and give player 0, whose target is 3/10, a veto.

Statement

theorem banzhaf_strict_majority_veto_distortion_ge_five_thirds :
    ∃ m w : Fin 3 → ℝ, in_std_simplex m ∧ is_optimal_banzhaf_weights m (1 / 2) (1 / 2) w ∧
      1 - 1 / 2 ≤ w 0 ∧ (1 - 1 / 2) / m 0 = 5 / 3
Related work
operator (Claude), 2026-10-03: improved lower bound 5/3 (from 6/5) on the veto distortion of the Banzhaf index at simple majority with strict quota, the case left open in How Banzhaf Makes a Victor: Curing a Distortion Paradox in Weighted Voting, EC 2026, Secs. 2-3 and 5; instance m = (3/10, 7/10, 0), optimal weights (1/2, 1/2, 0); found by MILP, checked in exact arithmetic and by the Lean kernel
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • wvg_winsA coalition wins in the weighted voting game (w; q) with strict quota if its total weight exceeds q.
  • in_std_simplexA vector lies in the standard simplex: nonnegative entries summing to 1.
  • is_optimal_banzhaf_weightsWeights are optimal for the inverse power problem (m, q, beta^p) if they lie in the simplex and minimise the discrepancy over the simplex.
  • bz3_discrRational discrepancy for the target (3/10, 7/10, 0) of the index given by the pivot counts of a winning pattern.
  • bz3_checkEvery winning pattern satisfying bz3_props has discrepancy at least 2/5 for the target (3/10, 7/10, 0) (kernel computation over 256…
  • bz3_coalThe eight coalitions of three players indexed by bit pattern.
  • bz3_patternThe winning pattern of the 3-player weighted game (w; 1/2) with strict quota.
  • bz3_discrepancyFor three players and p = q = 1/2, the discrepancy for target (3/10, 7/10, 0) equals the rational discrepancy of the winning pattern.
  • bz3_props_patternThe winning pattern of a 3-player game with simplex weights and strict quota 1/2 satisfies bz3_props.

Lean source view module on GitHub

/-- **Veto distortion of Banzhaf power at simple majority with a strict quota is at least 5/3.** How Banzhaf Makes a Victor (EC 2026, Sec. 5) leaves open the case `q = 1/2` with strict quota and gives `veto-dist ≥ 6/5`. Here, for the Banzhaf index `β^{1/2}` (which at `q = 1/2` is also the adaptive Banzhaf index), the target `m = (3/10, 7/10, 0)` has the optimal weights `w* = (1/2, 1/2, 0)`, under which player 0 (`m₀ = 3/10`) holds a veto (`w*₀ ≥ 1 - q`). Hence `veto-dist_{1/2}(β^{1/2}) ≥ (1 - q)/m₀ = 5/3`. -/theorem banzhaf_strict_majority_veto_distortion_ge_five_thirds :    ∃ m w : Fin 3 → ℝ, in_std_simplex m ∧ is_optimal_banzhaf_weights m (1 / 2) (1 / 2) w ∧      1 - 1 / 2 ≤ w 0 ∧ (1 - 1 / 2) / m 0 = 5 / 3 := by  have hw : in_std_simplex ![1 / 2, 1 / 2, 0] := by    refine ⟨fun i => by fin_cases i <;> norm_num, by simp [Fin.sum_univ_three]; norm_num⟩  have hpat : bz3_pattern ![1 / 2, 1 / 2, 0] = ![false, false, false, true, false, false, false, true] := by    funext k    fin_cases k <;> simp [bz3_pattern, bz3_coal, wvg_wins, Finset.sum_insert]  refine ⟨![3 / 10, 7 / 10, 0], ![1 / 2, 1 / 2, 0],    ⟨fun i => by fin_cases i <;> norm_num, by simp [Fin.sum_univ_three]; norm_num⟩,    ⟨hw, fun w' hw' => ?_⟩, by norm_num, by norm_num⟩  rw [bz3_discrepancy, bz3_discrepancy, hpat]  have hx : bz3_pattern w' = ![bz3_pattern w' 0, bz3_pattern w' 1, bz3_pattern w' 2,      bz3_pattern w' 3, bz3_pattern w' 4, bz3_pattern w' 5, bz3_pattern w' 6, bz3_pattern w' 7] := by    funext k; fin_cases k <;> rfl  have hp := bz3_props_pattern w' hw'  rw [hx] at hp ⊢  have := bz3_check _ _ _ _ _ _ _ _ hp  have h25 : bz3_discr ![false, false, false, true, false, false, false, true] = 2 / 5 := by    decide +kernel  rw [h25]  exact_mod_cast this
See it in the graphDiscuss this resultChallenge it