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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- **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