Example 4.17, p. 15 — approval voting is susceptible to constructive control by partition of voters in models TE and TP
ProvedHHRControl.PV.example_4_17approval-votingelection-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1susceptibility
Example 4.17. Let and let consist of eight approval voters (bits for ):
In , and are tied. For and , is the unique approval winner of , of , and wins the run-off against , in model TE and in model TP. Consequently approval voting is susceptible to constructive control by partition of voters in both models.
This election witnesses the susceptibility part of the approval constructive 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.17, p. 15: approval voting is susceptible to constructive 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_17 :
(let P : Fin 8 → Approval 3 := ![{0}, {0}, {0}, {1}, {1}, {2}, {2}, {2}];
approval.winners 3 8 P univ univ = {0, 2} ∧
approval.winners 3 8 P univ {0, 1, 5, 6, 7} = {2} ∧
approval.winners 3 8 P univ ({0, 1, 5, 6, 7} : Finset (Fin 8))ᶜ = {1} ∧
∀ rule : TieRule, twoStage rule approval P {0, 1, 5, 6, 7} = {2}) ∧
SusceptibleCC .TE approval ∧ SusceptibleCC .TP approval := by sorry
end HHRControl.PV
Source
Hemaspaandra, Hemaspaandra & Rothe, Anyone but Him: The Complexity of Precluding an Alternative, arXiv:cs/0507027v5, p. 15, Example 4.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.