Example 4.11, p. 13 — approval voting is susceptible to destructive control by partition of voters in models TE and TP
ProvedHHRControl.PV.example_4_11approval-votingelection-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1susceptibility
Example 4.11. Let and let consist of ten approval voters (bits for ):
Then is the unique approval winner of . For and , is the unique winner of and of ; they are nominated and tie in the final election, in model TE and in model TP. Consequently approval voting is susceptible to destructive control by partition of voters in both models.
This election witnesses the susceptibility part of the approval destructive clauses of Theorem 3.6.
Differences from the source:
- encoding: candidates a, b, c; voters v1, v2, … → candidates 0, 1, 2 of Fin 3; voter vᵢ is index i − 1 of Fin n; reason: 0-based indices; no instance changes
Preamble
import Mathlib import Definitions.Def_HHRControl_PV_Elections
Formal statement
namespace HHRControl.PV
open Finset
/-- Example 4.11, p. 13: approval voting is susceptible to destructive control by partition of
voters, in models TE and TP. Candidates `a, b, c` are `0, 1, 2`; an approval ballot is the set of
approved candidates. -/
theorem example_4_11 :
(let P : Fin 10 → Approval 3 :=
![{2}, {2}, {2}, {2}, {0}, {0}, {0}, {1}, {1}, {1}];
approval.winners 3 10 P univ univ = {2} ∧
approval.winners 3 10 P univ {0, 1, 4, 5, 6} = {0} ∧
approval.winners 3 10 P univ ({0, 1, 4, 5, 6} : Finset (Fin 10))ᶜ = {1} ∧
∀ rule : TieRule, twoStage rule approval P {0, 1, 4, 5, 6} = {0, 1}) ∧
SusceptibleDC .TE approval ∧ SusceptibleDC .TP approval := by sorry
end HHRControl.PV
Source
Hemaspaandra, Hemaspaandra & Rothe, Anyone but Him: The Complexity of Precluding an Alternative, arXiv:cs/0507027v5, p. 13, Example 4.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.